Correctnessimplementation

Compiler Fuzzing

Generate programs nobody wrote to find crashes and, far more valuably, wrong code. Csmith and YARPGen construct programs that are well-defined by design; EMI takes the opposite route and mutates code that provably never executes, so the output must not change.

The question

How do people actually find compiler bugs, given that nobody is writing the programs that trigger them?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

A stream of generated source programs plus, for each one, a property that must hold of its compilation. The property is the whole design: "does not crash the compiler" is nearly free and finds the least valuable bugs, while "produces the same behavior as this other compilation" or "produces the same behavior as this equivalent program" require the generator to guarantee something about the program it emitted. The generator and the property are one artifact, not two.

What this phase may assume or do

A generated program is admissible as a test only if the language assigns it exactly one permitted behavior: no undefined behavior, no unspecified evaluation order that could change the result, no dependence on addresses, time, threads or uninitialized storage. For the EMI technique the precondition is different and sharper — the mutated region must be provably unexecuted on the profiled input, so that the mutation cannot affect behavior for that input under any correct compilation. Where either precondition fails, a divergence is a property of the test, not of the compiler.

Key points

Crash-finding is the cheap property; wrong-code finding is the valuable one, and it requires manufacturing an oracle.
Byte-level mutation fuzzing mostly tests the lexer, because random mutations of source text rarely parse.
Csmith’s contribution is generating C programs guaranteed free of undefined and unspecified behavior, which is what makes cross-compiler comparison valid.
YARPGen aims specifically at scalar and loop optimizations rather than at the language as a whole.
EMI mutates code the profile shows never executes, so the output must be unchanged — no second compiler and no UB-free generator required.
Dead code is not inert: it changes inlining, register pressure and CFG shape, which is why EMI reaches bugs other generators do not.
Reduce before deduplicating, and re-check definedness at every reduction step.

Two properties, very different value

Fuzzing a compiler can check two quite different things. The easy property is that the compiler does not crash, assert or hang. This finds real bugs, it is trivially checkable, and it is what a generic mutation fuzzer such as AFL or libFuzzer gives you if you point it at a compiler binary with a corpus of source files. It is also the less valuable half: a compiler crash is loud and you cannot ship it.

The hard and valuable property is that the compiler generates *correct code*. Checking it requires knowing what the program should do, which returns us to the oracle problem, and the three answers are the three techniques below. Every one of them is really a way of manufacturing an oracle out of a generator.

It is worth noting what generic byte-level mutation fuzzing does poorly here. Randomly flipping bytes in a C file produces text that does not parse about all of the time, so almost every iteration tests the lexer and stops. Coverage-guided mutation improves this considerably and still concentrates in the frontend. Finding middle-end wrong-code bugs needs a generator that understands the language, which is why compiler fuzzing is dominated by grammar-aware generators rather than by mutation.

Three generators, three ways of getting an oracletypical

Technique	How the program is produced	Where the oracle comes from	Finds
Csmith	Generated from a C grammar with UB-avoidance built into every construct	Another compiler or another optimization level must agree	Wrong-code and crash bugs across the whole pipeline
YARPGen	Generated to stress scalar and loop optimizations specifically, with generation policies that bias toward hard cases	Self-checking output plus cross-configuration comparison	Optimization bugs the general generator rarely reaches
EMI	An existing program, mutated only in code that the profile shows never executes	The original program itself: output must be unchanged	Bugs triggered by real-world code shapes rather than generated ones
Mutation fuzzing (AFL)	Byte-level mutation of a corpus, guided by coverage	Only "did not crash"	Crashes, hangs, assertion failures; almost no wrong code
Grammar-based fuzzing	Random derivations from the language grammar	Only "did not crash", unless definedness is also guaranteed	Parser and frontend robustness

Equivalence modulo inputs, which is worth understanding properly

EMI is the most elegant idea in this area and it is easy to state. Take a program and an input. Run it under a profiler and record which statements executed. Now delete, or arbitrarily mutate, statements that did *not* execute. The new program is not equivalent to the original in general — but it is equivalent *for that input*, because the code you changed never runs. So compile both and run both on that input: the outputs must be identical. If they differ, some compiler is wrong.

The reason this is powerful is that it needs no second compiler and no UB-free generator. The seed program can be anything you like, including real code from real projects, which is a distribution that generated programs cannot reproduce. And the mutation can be arbitrarily aggressive, because correctness of the test does not depend on the mutation being meaning-preserving — only on the mutated code being unreachable for the chosen input.

It also finds a class of bug the others structurally miss. Dead code is not inert to a compiler: it changes inlining decisions, it changes register pressure, it changes which loops look profitable to unroll, it changes the shape of the control-flow graph the optimizer sees. A pass that behaves differently because unreachable code perturbed a heuristic — and gets the *reachable* code wrong as a result — is exactly what EMI catches. The original Le, Afshari and Su work found well over a hundred confirmed bugs in GCC and LLVM this way, in code paths a decade of Csmith had not reached.

An EMI variant: delete what the profile says never ran

Before

int f(int n) {
  int s = 0;
  for (int i = 0; i < n; i++) {
    if (i > 1000000) {      /* profile: never taken for n = 10 */
      s += expensive(i);
      s *= 3;
    }
    s += i;
  }
  return s;
}
/* run with n = 10 */

After

int f(int n) {
  int s = 0;
  for (int i = 0; i < n; i++) {
    if (i > 1000000) {      /* body deleted; unreachable for n = 10 */
    }
    s += i;
  }
  return s;
}
/* must still print the same value for n = 10 */

Legal only when

Valid as a test only for the specific input that was profiled, and only if the profile is complete for that input: every statement removed or altered must be one the instrumented run showed did not execute. Under that condition both programs have identical observable behavior on that input for any correct compiler, so a difference in their outputs is a compiler bug rather than a difference between the programs.

Illegal when

The precondition fails if the program is non-deterministic, so a second run takes a different path — threads, time, randomness, address-dependent behavior, or an uninitialized read. It also fails if the profiling instrumentation itself perturbed which statements executed, or if the mutation touched a declaration rather than a statement and thereby changed the meaning of reachable code. In any of those cases the two programs are genuinely different and comparing their outputs proves nothing.

Running one, in practice

implementationCsmith targets C specifically and its UB-avoidance encodes the C standard’s rules; there is no drop-in equivalent for most languages, and building one is the bulk of the work in bringing this technique to a new language. YARPGen covers C and C++ with a bias toward optimization-stressing shapes. For languages with much smaller undefined regions — Java, Go, Rust safe code — a far simpler generator suffices, because definedness is largely free.

A compiler fuzzing campaign is a loop, a corpus of results and a triage queue, and the triage queue is where the real work is. A productive fuzzer produces far more findings than a team can report, most of them duplicates of the same underlying bug reached by different routes. Deduplication by reduced test case — reduce first, then hash the reduced program — is far more effective than deduplicating on stack traces or on the original generated file.

Three practical rules save most of the wasted effort. Run everything under a timeout and treat timeouts as a separate bug class rather than folding them into the wrong-code arm. Re-check definedness after every reduction step, because reducers introduce undefined behavior enthusiastically. And record the exact compiler version, flags and target with every finding, because a report that reproduces on nothing is not a report.

And point it at yourself. A fuzzer aimed at your own DSL, template engine, query compiler or serializer is usually a weekend of work with a hand-written grammar-aware generator, and it typically finds something in the first hour. The general fuzzing machinery — corpus management, coverage guidance, shrinking — is Security and Testing material; what this domain contributes is knowing which property to check and what the generator must guarantee for the check to mean anything.

Check a property stronger than "did not crash", or you are testing the least valuable third of the compiler.
Reduce before deduplicating; hash the reduced case, not the generated one.
Timeouts are their own bug class — a compile-time explosion is a real bug and a different one.
Re-verify definedness after every reduction step, inside the interestingness script.
Record version, flags and target triple with every finding, or the report is unactionable.
A grammar-aware generator for your own small language is a weekend, and finds bugs immediately.

How it works

The steps, in the order the compiler takes them.

Generate a candidate program, either from a language-aware grammar with definedness constraints, or by mutating a seed program’s provably unexecuted regions.
Compile it under two or more configurations, each under a timeout, recording crashes and hangs separately from output.
Run each binary under a timeout and capture observable behavior — typically a single checksum over final state rather than intermediate output.
Compare against the property: agreement across configurations for a generated program, or identity with the seed’s output for an EMI variant.
On divergence, verify the program is well-defined, then reduce with the divergence as the interestingness predicate.
Deduplicate on the reduced case, attribute by majority or by pass bisection, and file with version, flags and target.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

The campaign reports thousands of findings that are all the same bug, and the team abandons triage before reaching the second one.
The generator emits undefined behavior, so every report is invalid, and after three rejected reports the maintainers stop reading them.
Only crash bugs are checked, so the fuzzer runs for months while wrong-code bugs ship undisturbed.
Generated programs are enormous, so each reduction takes hours and the queue never drains.
The EMI profile is taken on a non-deterministic program, and a variant differs because it took a different path rather than because a compiler was wrong.
Timeouts are counted as wrong-code findings, and a legitimate compile-time explosion floods the results with a bug that is real but of a different kind.

When it helps

Any compiler or code generator with more than a few passes, where the interaction space is far too large for hand-written tests to cover.
Before a release, as a soak: a week of continuous fuzzing on a release branch finds what a test suite written by people who know the design cannot.
On your own DSL, template engine or query compiler, where a small grammar-aware generator is cheap and the code has never been fuzzed at all.
After a large refactor of the middle-end, where the property test on a fixed corpus passes and the interaction bugs are in shapes the corpus does not contain.

When it hurts

Without a triage budget. A fuzzer that nobody triages is a machine for generating guilt and consuming CI capacity.
For a language with a huge undefined region and no UB-free generator, where the false-positive rate makes findings worthless until somebody builds the generator.
As a pre-merge gate. Fuzzing is a continuous background activity with an unbounded runtime; putting it in the critical path of a pull request makes it flaky and slow at once.
On non-deterministic programs, where the property being checked does not hold even for a perfectly correct compiler.

What it costs

Every one of these is paid by something.

Fuzzing buys coverage of the interaction space that no hand-written suite reaches and costs continuous compute plus, more scarcely, continuous human triage attention.
A definedness-guaranteeing generator buys valid findings and costs a serious engineering project encoding the language’s undefined-behavior rules, which then has to track the standard as it changes.
EMI buys real-world program shapes and freedom from the generator problem, and costs a profiling step per seed plus the requirement that seeds be deterministic.
Checking only for crashes buys a trivially cheap setup and pays by missing the entire wrong-code class, which is the class that matters.
Aggressive reduction buys reportable test cases and costs compute plus a standing risk of introducing undefined behavior and thereby destroying a genuine finding.

What else you could do

What a different compiler or language does instead, and when that is better.

Property testing on a fixed corpus — [[compiler-testing]]’s "optimization never changes the output" — covers the same relation on programs you already trust, cheaply, and misses the shapes nobody wrote.
Translation validation checks the compilations that actually happen rather than generated ones, so it covers your real code instead of random code — see [[translation-validation]].
Formal verification removes the need to search for middle-end wrong-code bugs at all, within the verified region — see [[verified-compilers]].
Large-scale rebuild programmes — compiling an entire distribution with a new compiler — find real bugs on real code with no generator at all, and localize almost nothing.

See it for yourself

The flag, dump or tool that shows you this directly.

Csmith: csmith --seed 1234 --output prog.c, then gcc -O0 -I/usr/include/csmith prog.c -o a && ./a prints the checksum that is the comparison value.
YARPGen: yarpgen --std=c --out-dir=out emits func.c, driver.c and init.h; unlike Csmith it generates its own checks, so a single configuration can self-report.
C-Reduce / cvise: cvise ./interesting.sh prog.c, where interesting.sh must both reproduce the divergence and confirm the program is still free of undefined behavior.
Generic mutation fuzzing on a frontend: clang-fuzzer and llvm-isel-fuzzer ship with LLVM, and AFL++ over a corpus of source files finds parser crashes quickly.
For your own tool: write a grammar-aware generator and check the metamorphic property directly. Our own suite does the fixed-corpus version of this in scripts/compilers-sim.test.ts.
OSS-Fuzz runs continuous fuzzing for LLVM, GCC and many language runtimes; its public issue tracker is a good place to see what compiler fuzzing finds in practice.

Plausible wrong readings

Stated the way a confident engineer states them.

"Fuzzing means feeding random bytes to a program." That finds parser crashes. Finding wrong-code bugs needs a generator that produces valid, well-defined programs, which is a completely different artifact.
"EMI mutations have to preserve the program’s meaning." They do not, and that is the point. They only have to be unreachable for the profiled input, which is a much weaker and much easier condition to guarantee.
"If the fuzzer stops finding bugs, the compiler is correct." It means this generator has exhausted the shapes it can produce. Changing the generator usually restarts the flow immediately, which is itself the evidence.
"Dead code cannot affect the compiler, so mutating it is pointless." Dead code changes inlining budgets, register pressure and CFG shape. That it affects the compiler is precisely why the technique works.

Misconceptions

The claim, and what is actually true.

A compiler that survives fuzzing is correct.

It is free of the bugs this generator’s program distribution can express. Every new generator finds a new batch, which is the strongest available evidence that the technique measures the generator as much as the compiler.

Fuzzing is for security, not correctness.

For compilers the highest-value target is wrong code, not memory safety in the compiler process. The machinery overlaps; the property being checked does not.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

Compiler fuzzing means generating programs automatically and checking that the compiler handles them properly. Checking that it does not crash is easy and finds the least important bugs. Checking that it generates *correct* code needs some way of knowing the right answer: either generate programs whose behavior the language fully pins down and compare two compilers, or take a real program, change only the parts that never run, and require the output to stay the same.

practical

For C, run Csmith into a comparison loop across -O0, -O2 and a second compiler, all under timeouts. Budget more time for triage than for running it. Reduce every finding with cvise before you deduplicate, and put a sanitizer check inside the interestingness script so the reducer cannot hand you an invalid case. For your own DSL or code generator, skip all of that and write a small generator plus the property that optimization does not change the output — an afternoon of work that usually pays out the same day.

advanced

The instructive result is that each new generator finds a fresh population of bugs in compilers the previous generator had already exhausted. That tells you the search is bounded by the *distribution of programs the generator can express*, not by the compiler’s bug density. EMI’s significance is that it changes the distribution to "real programs, perturbed", which no synthetic grammar reaches — and it does so while needing only one compiler, which makes it the technique of choice for a language with a single implementation. The open frontier is generating programs that specifically stress the interaction between passes, since single-pass bugs in mature compilers are largely gone and phase-ordering bugs are not.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

implementationCsmith and YARPGen are C and C++ tools whose definedness logic encodes those standards specifically. There is no general-purpose equivalent for arbitrary languages, and porting the idea means re-encoding the target language’s undefined-behavior rules from scratch. For languages with small undefined regions the work is far smaller, which is one concrete way language design changes what tooling is affordable.

typicalThe claim that mutation fuzzing finds mostly frontend bugs describes byte-level mutation over source text with mainstream compilers. Structure-aware mutation — mutating an AST or IR rather than bytes, as llvm-isel-fuzzer does over IR — reaches much deeper, and blurs the line between mutation fuzzing and generation.

simplifiedThe EMI description here uses statement deletion, which is the original and clearest variant. Later work also inserts code into unexecuted regions and mutates live code in ways that are provably equivalent, each with its own precondition. The core idea — construct a second program that must behave identically on one specific input — is common to all of them.

If you were asked this in an interview

Explain equivalence modulo inputs, and say why the mutation does not need to preserve the program’s meaning.
You have one compiler and no reference implementation. How do you fuzz for wrong-code bugs?
Why does byte-level mutation fuzzing find mostly parser bugs?

Connections

Performancebenchmarking

Securityfuzzing

Domains that do not exist yet

Testing & Reliability Engineering — Fuzzing infrastructure: corpus management, coverage guidance, shrinking and triage
The loop, the corpus and the deduplication problem are the same whether the target is a compiler, an image decoder or a protocol parser, and that machinery is owned there. What this domain adds is which property to check and what the generator must guarantee for a finding to be valid at all.