Correctnessspec

Differential Testing

Compile and run the same program through two compilers, two versions or two optimization levels, and compare. It needs no oracle — the implementations are each other’s oracle — but it needs programs whose behavior the language actually pins down, which is the entire difficulty.

The question

How can I test a compiler when I have no way of knowing what the right answer is?

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

What the program is here

Two or more compilations of one source program, each producing a behavior — an output, an exit status, a trap. The object under test is not any single behavior but the *relation between them*: the language specification says these compilations must agree, so a disagreement is a bug in at least one of them. The representation exists to answer the question a single compilation cannot: was this output right, when nobody wrote down what right was.

What this phase may assume or do

Differential testing is valid only for programs whose behavior the language fully determines. If the program contains undefined behavior, every compilation is permitted to do something different and a disagreement proves nothing. If it contains merely *unspecified* or implementation-defined behavior — evaluation order of arguments, the size of int, whether char is signed — the implementations may legitimately differ there too. The generator therefore carries the entire burden: it must emit programs with exactly one permitted behavior, or the comparison is not a test.

Key points

Differential testing removes the need for an oracle by making two implementations check each other.
The three useful axes are two optimization levels of one compiler, two versions, and two independent compilers — in roughly that order of cost-effectiveness.
A program with undefined behavior may legitimately differ everywhere, so the generator must produce only programs with exactly one permitted behavior.
Csmith’s contribution is that guarantee, not the generation: UB-free by construction, with a checksum of final global state as the comparison value.
Compare behavior, never emitted code. Two correct compilers produce different assembly by design.
Reduction can introduce undefined behavior, so the interestingness script must re-check for it at every step.

Testing without an oracle

The hard part of testing a compiler is that for a program nobody wrote, nobody knows the answer. You can generate a million programs in an afternoon; you cannot hand-compute what each should print. This is the *oracle problem*, and differential testing solves it by refusing to need an oracle at all: run the program two ways and require agreement.

The insight is that two independent implementations are unlikely to have the same bug. GCC and Clang share no code in their optimizers. Version 17 and version 18 of the same compiler share most of theirs, so they are a weaker but still useful pair. -O0 and -O2 of the same compiler share the frontend entirely and differ in exactly the part you most want to test, which makes it the cheapest and often the most productive comparison of the three.

The comparison also localizes. If -O0 and -O2 disagree, the bug is in the middle-end or backend, and pass bisection will find it. If two compilers disagree but each is internally consistent across optimization levels, the disagreement is more likely to be a language-rule disagreement than a wrong-code bug — implementation-defined behavior, or one of them being wrong about the specification rather than wrong about the program.

What each comparison axis can findtypical

Axis	Shared code	Finds	Main source of false alarms
`-O0` vs `-O2`	Whole frontend	Middle-end and backend wrong-code bugs, precisely localized	Undefined behavior in the program — by far the most common
Version N vs N+1	Most of the compiler	Regressions introduced by a specific change	Deliberate behavior changes and newly exploited UB
GCC vs Clangimplementation	None	Independent bugs in either, and specification disagreements	Implementation-defined behavior, extensions, ABI differences
Native vs interpreter	Frontend only, sometimes nothing	Backend bugs, with the interpreter as a slow reference semantics	Interpreter bugs, and any place the interpreter is not the specification
Target A vs target Btarget	Everything but the backend	Backend-specific bugs	Genuine target differences: word size, endianness, float behavior

The caveat that decides whether any of it works

specThe four-way split (undefined, unspecified, implementation-defined, well-defined) is C and C++ terminology and the boundaries are drawn by those standards. Other languages divide the space very differently: Java specifies almost everything including integer overflow and evaluation order, Rust defines overflow behavior per profile and confines undefined behavior to unsafe, and Go leaves far less unspecified than C. The narrower the undefined set, the easier differential testing is — which is a genuine language-design consequence, not a footnote.

A program containing undefined behavior may legitimately behave differently under every compiler, every optimization level and every phase of the moon. Compare two such runs and you get a disagreement that means nothing, and if your generator produces such programs at any appreciable rate, your differential tester produces a stream of false reports and gets switched off.

This is not a small caveat in C. Signed overflow, shifts by the word width, uninitialized reads, out-of-bounds indexing, strict-aliasing violations, division by zero and unsequenced modification are all trivially easy to generate by accident and all undefined. Random text is not a usable generator. Random *syntactically valid* programs are not a usable generator either, because almost all of them are undefined.

What makes Csmith the reference is precisely that it solves this. It generates C programs that are large, that exercise the optimizer, and that are — by construction and by dynamic checking — free of undefined and unspecified behavior. Every arithmetic operation is wrapped so it cannot overflow or divide by zero, every index is forced in range, every variable is initialized, and the program's output is a checksum of its final global state, which gives a single value to compare. That guarantee is the product; the generation is the easy half.

Undefined behavior: every implementation may do anything. A disagreement proves nothing. The generator must exclude it entirely.
Unspecified behavior: the implementation picks from a set, need not document it, may pick differently each time. Also excludes comparison.
Implementation-defined behavior: the implementation picks and documents. Comparable across levels of one compiler, not across two compilers.
Well-defined: exactly one permitted behavior. Only this class is comparable, and only this class is worth generating.
Non-determinism in the program itself — threads, time, addresses, hash order — has to be excluded for the same reason.

Comparing behavior, not artifacts

It is tempting to compare the emitted assembly. Do not. Two correct compilers produce entirely different assembly for the same program, and so do two optimization levels of one compiler; that is the point of them. The comparison has to be on *observable behavior*: what the program printed, what it returned, whether it trapped, and — for a generator like Csmith — a checksum over the final values of all global variables.

The checksum is a deliberate design choice worth copying. A generated program that prints intermediate values gives you a large diff to interpret and lets a single divergence hide behind buffering. A program that computes for a while and then prints one hash of everything it touched gives a one-bit answer with maximum coverage per comparison, and reduces cleanly: the reducer's interestingness test is "the two checksums still differ".

The same idea works on your own code without any generator at all. Build your test suite at two optimization levels and run both. It is a few minutes of CI time and it is the cheapest differential test that exists.

The differential loop, in the form it actually takes in a script

1while true; do
2  csmith --output prog.c
3  timeout 20 gcc   -O0 prog.c -o a0 -I$CSMITH_INC || continue
4  timeout 20 gcc   -O2 prog.c -o a2 -I$CSMITH_INC || continue
5  timeout 20 clang -O2 prog.c -o c2 -I$CSMITH_INC || continue
6  o0=$(timeout 5 ./a0); o2=$(timeout 5 ./a2); c=$(timeout 5 ./c2)
7  if [ "$o0" != "$o2" ] || [ "$o0" != "$c" ]; then
8    cp prog.c "bug-$(date +%s).c"
9  fi
10done

The || continue on each compile is not sloppiness — a compiler crash or a timeout is a different bug class that a separate arm should record, and folding it into the wrong-code comparison would flood the results. Note also that -O0 is one of the three: the majority of wrong-code findings come from comparing a compiler against itself.

What to do with a disagreement

A disagreement names a set of implementations that cannot all be right; it does not name the guilty one. With three configurations, majority voting is a decent heuristic — if -O0 on both compilers agrees and one -O2 differs, the odd one out is the suspect. With two, you have to reason about it, and the first thing to check is once again whether the generator let undefined behavior through.

Then reduce, keeping the disagreement as the interestingness property, and re-check the reduced program for undefined behavior at every step. This matters more than it sounds: reducers routinely *introduce* undefined behavior while shrinking, turning a real bug report into a false one. C-Reduce integrates UB checking into the interestingness script for exactly this reason, and a reduction pipeline without that check produces confident, wrong bug reports.

How it works

The steps, in the order the compiler takes them.

Generate or select a program whose behavior the language fully determines, with no dependence on time, addresses, threads or uninitialized state.
Compile it under two or more configurations that the specification requires to agree.
Run each binary under a timeout and capture the observable behavior: output, exit status, and whether it trapped.
Compare the behaviors. Equality means nothing was learned; inequality means at least one configuration is wrong.
Before reporting, verify the program is free of undefined behavior with sanitizers and, where available, an independent checker.
Reduce with the disagreement as the interestingness predicate, re-checking definedness after each reduction step.
Attribute by majority where three or more configurations are available, and by pass bisection where the disagreement is between optimization levels of one compiler.

How it breaks

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

The generator emits undefined behavior, so the tester produces a steady stream of disagreements that are all the generator’s fault, and the team stops looking at them.
The comparison is on assembly rather than behavior, so every run "fails" and the technique is abandoned as unworkable.
The program depends on printf("%p"), on the address of a local, or on the value of an uninitialized variable, and the disagreement is between two runs of the *same* binary.
Floating point is included naively, and a legal difference in excess precision or contraction — x87 80-bit intermediates, or a fused multiply-add — is reported as a wrong-code bug.
A reducer shrinks a real bug into a program with an out-of-bounds read, and the resulting report is closed as invalid, along with the real bug behind it.
The two compilers are compared at different language standard versions, and a deliberate behavior change between C++14 and C++17 is reported as a miscompilation.

When it helps

Any compiler or translator with a second implementation available, including your own: a query planner with an interpreter fallback, a transpiler against the source language’s own runtime, a bytecode VM against a tree-walker.
Validating a compiler upgrade before rolling it out: build your own test corpus with old and new and compare, which is a differential test with a corpus you already trust to be well-defined.
Backend bring-up for a new target, where the existing target is a reference semantics you already trust.
Any project where a reference implementation exists and a fast implementation is being written — the reference is the oracle, and this is the standard way to use it.

When it hurts

Languages with large undefined or unspecified regions and no UB-free generator, where the false-alarm rate makes the technique unusable until somebody builds the generator.
Programs with intentional non-determinism: threads, randomness, time, iteration order over unordered collections. These have to be excluded rather than compared.
Floating-point-heavy code, where contraction, excess precision and reassociation are permitted to differ and a naive comparison drowns in legitimate differences.
When only one implementation exists, which is the common case for a new language and the reason [[compiler-fuzzing]] with a self-consistency property is often the only option.

What it costs

Every one of these is paid by something.

Differential testing buys an oracle for free and costs the construction of a generator that can guarantee definedness, which for C is a multi-year research artifact rather than a weekend script.
Comparing across two independent compilers buys strong independence and costs a stream of false alarms from implementation-defined behavior, extensions and ABI differences that a same-compiler comparison does not produce.
Comparing optimization levels of one compiler buys precise localization and cheap setup, and pays in coverage: a bug in the shared frontend is invisible because both sides have it.
Running everything under a timeout buys protection against generated infinite loops and costs the ability to distinguish "slow" from "hung", so a genuine compile-time explosion is silently discarded as an uninteresting case.
A checksum-of-final-state comparison buys a one-bit answer and maximum coverage per run, and costs debuggability: the checksum tells you the programs diverged and nothing about where.

What else you could do

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

Self-consistency without a second implementation: [[compiler-fuzzing]]’s equivalence-modulo-inputs technique compares a compiler against a mutated version of the same program, which needs only one compiler.
Metamorphic testing on your own programs — the property that optimization preserves output, from [[compiler-testing]] — is the same idea applied to a corpus you already have and already know is well-defined.
Prove instead of compare: [[translation-validation]] checks the actual compilation for semantic preservation, catching bugs on real programs rather than generated ones.
Run the reference implementation as an interpreter over your own IR and compare against native execution. Slower, but the interpreter is far easier to trust than a second compiler and often already exists for constant folding.

See it for yourself

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

Csmith: csmith --output prog.c then compile with -I/usr/include/csmith. Read the generated program once — the deliberate absence of undefined behavior is visible in the wrapper macros around every arithmetic operation.
YARPGen (yarpgen --std=c++ --out-dir=.) generates programs specifically aimed at scalar and loop optimizations, and unlike Csmith it emits its own expected output for self-checking.
The cheap version on your own code: build the test suite twice, -O0 and -O2 (or --release and --debug), and diff the results. cargo test versus cargo test --release is a one-line differential test.
Compiler Explorer runs several compilers and versions on one source simultaneously, which is a manual differential tester and the fastest way to check a suspicion.
Sanitize before believing anything: clang -fsanitize=undefined,address -O0 on the disagreeing program, and gcc -fsanitize=undefined as a second opinion, because the two implement overlapping but different check sets.

Plausible wrong readings

Stated the way a confident engineer states them.

"The two compilers produce different assembly, so one of them is wrong." They are supposed to. Only behavior is comparable.
"A disagreement means the newer compiler is buggy." It means one of them is. Majority voting across three configurations is a heuristic, not a verdict, and the first suspect is your own program’s definedness.
"Random program generation is easy, so this is easy." Generating programs is easy. Generating programs whose behavior the language pins down is the entire problem, and it is what Csmith is famous for.
"If both compilers agree, the program is correct." They may agree because both exploit the same undefined behavior in the same way. Agreement is weak evidence and disagreement is strong evidence — the asymmetry is inherent.

Misconceptions

The claim, and what is actually true.

Differential testing needs two compilers.

The most productive axis is one compiler at two optimization levels, which shares the frontend and differs in exactly the part most likely to be wrong.

If a generated program crashes under one compiler, that is a bug.

Not until you have established the program was well-defined. A generated program with an out-of-bounds write is entitled to crash under one compiler and not another.

Go deeper

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

overview

You cannot test a compiler on programs nobody wrote, because nobody knows what those programs should print. Differential testing gets around that: compile the same program two ways — two compilers, two versions, or just -O0 and -O2 — and if the results differ, at least one of them is wrong. The catch is that a program with undefined behavior is allowed to differ, so the programs you feed it have to be ones the language fully pins down.

practical

The cheapest version costs nothing to adopt: run your own test suite at two optimization levels in CI. The next step up is a generator. For C, use Csmith and compare -O0, -O2 on the same compiler, and -O2 on a second one. Run everything under a timeout, compare the printed checksum rather than intermediate output, and before you report anything run the disagreeing program under -fsanitize=undefined,address. When you reduce, keep the UB check inside the interestingness script or the reducer will hand you an invalid report.

advanced

The interesting limit is that differential testing finds only bugs the two sides do not share, which makes the choice of pair a coverage decision rather than a convenience. Two versions of one compiler share nearly everything and find only regressions; two independent compilers share nothing and find far more, but the false-alarm rate from implementation-defined behavior rises to meet you. Equivalence modulo inputs sidesteps the pairing question entirely by generating a second *program* rather than using a second compiler, which is why it found bugs in GCC and LLVM that a decade of Csmith runs had not — see [[compiler-fuzzing]].

How much this depends on

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

specWhich programs are comparable is a specification question and differs sharply by language. C and C++ leave signed overflow, aliasing violations and evaluation order undefined or unspecified; Java pins evaluation order and integer overflow; Rust defines overflow per build profile and confines undefined behavior to unsafe. A differential tester for Java needs a far weaker generator than one for C, and this is a consequence of language design rather than of tooling maturity.

implementationGCC and Clang differ legitimately in places that are not bugs: implementation-defined behavior such as the signedness of plain char on some targets, the layout of bitfields, and the set of accepted extensions. A cross-compiler differential tester must either restrict the generator to the common well-defined subset or maintain a list of known-legitimate differences, and the second option rots.

targetComparing across target architectures adds legitimate differences that have nothing to do with compiler bugs: word size, endianness, whether floating-point contraction into fused multiply-add is enabled by default, and the precision of intermediate results on x87. Restricting the generator to fixed-width integer types removes most of it and removes some coverage with it.

If you were asked this in an interview

You have a compiler and no test oracle. How do you test it?
Why does a program containing undefined behavior break differential testing, and what does a generator have to do about it?
Two compilers produce different assembly for the same source. What have you learned?

Connections

Securityfuzzing

Domains that do not exist yet

Testing & Reliability Engineering — The oracle problem, and differential and metamorphic testing as answers to it
Comparing two implementations to avoid needing a known-correct answer is a general testing strategy that applies to database engines, numeric libraries and protocol implementations alike. Compilers are the case where the undefined-behavior caveat dominates, and that part is ours.