Finding Unstable Code via Compiler-Driven Differential Testing

The C standard lists 211 situations it calls UNDEFINED BEHAVIOR, and for those the compiler may do literally anything — which in practice means it assumes they never happen, and confidently deletes the code you wrote to check for them; the classic result is a program where the safety check you added is silently removed at high optimization but kept at low optimization, so the same source produces two binaries with different behaviour and one of them has a security hole; the standard defence is a SANITIZER, a tool that inserts a runtime check for one specific kind of undefined behaviour, but that only works for the kinds somebody knew how to check, and for several important kinds nobody knows how; this paper (ETH Zurich) proposes something almost embarrassingly simple — compile the program with several different compilers and optimization levels, run all the resulting binaries on the same input, and if any two disagree on the output, the program contains a bug; the disagreement IS the evidence, no specification and no instrumentation required, and plugged into a standard fuzzer it found 1409 bugs in a benchmark that sanitizers missed entirely, plus 78 new bugs in projects like curl, php and tcpdump, of which 52 were fixed and 36 were invisible to every sanitizer.

Why this problem is worth solving

The hazard here is not that a program is slow or that a check is missing — it is that code the programmer deliberately wrote can be deleted by the tool meant to translate it, so being precise about the mechanism matters.

That instability is exactly what this paper turns into a detector.

What people did before, and where it broke

• Sanitizers. Compiler-inserted runtime checks for particular classes of undefined behaviour, and the state of the art for good reason — they have very high detection rates in the classes they target and produced no false alarms on the benchmark used here. But each class needs its own bespoke check, so coverage ends where the design work ended.
• Classes nobody knows how to check. Comparing pointers into different objects has no known check design. Neither does the case where two subexpressions have conflicting side effects and the compiler may evaluate them in either order, which would require a checker that detects conflicting memory effects among subexpressions.
• Checks deliberately narrowed to stay quiet. The uninitialized-memory sanitizer reports only uninitialized values that determine a branch, precisely to avoid false alarms, so an uninitialized value that is merely printed escapes — on the benchmark it caught 7 percent of the relevant bugs.
• Static analyzers. Tools that inspect source without running it can flag suspicious patterns broadly, but they are heuristic and pay for it in false alarms, measured here at up to 46 percent, 35 percent and 69 percent for three widely used commercial and open-source analyzers.
• Differential testing in other settings. Cross-checking independent implementations is an established idea, but prior differential fuzzing work each targeted one specific domain such as comparing two protocol libraries, and typically modified the fuzzer to suit.
• The gap. Nobody had used the compilers themselves as the disagreeing implementations, which is the one framing that attacks undefined behaviour generically rather than one class at a time — and which needs no specification, no per-class checker, and no instrumentation. That is the gap this paper fills.

How disagreement becomes a bug detector

The idea

When you cannot state what is correct, use disagreement instead. Every sanitizer begins by answering a hard question — what exactly does it mean for this construct to go wrong, and what runtime check would detect it? For some constructs that question has no known answer, which is why those classes have no sanitizer. This paper sidesteps the question entirely. It never defines what correct behaviour is, and never checks any property of the program. It observes only that several real compilers disagree about what the program does, and for a program with deterministic output that alone proves something is wrong. The oracle is free because it comes from redundancy rather than from specification. Deriving a verdict from disagreement among independent implementations, rather than from a specification you may be unable to write, is the same use-redundancy-as-the-oracle discipline covered elsewhere on this site, where independent checkers or replicas cross-validate each other and divergence is the alarm.

Target the consequence, not the cause. The deeper reason this works is a choice of what to look for. Sanitizers enumerate CAUSES — this kind of overflow, that kind of invalid access — and therefore need a new checker per entry, forever. The authors instead target the shared CONSEQUENCE that all these causes produce, namely that the program stops having one meaning. Because the consequence is common to the whole category, one detector covers a diverse range at once, including kinds nobody has built a checker for and, as a bonus, bugs that are not undefined behaviour at all. The cost of this framing is equally clear and the authors state it: a cause that never produces a visible consequence is invisible, so some undefined behaviour is missed that a dedicated checker would catch. Finding the single downstream symptom that many different faults share, and detecting that instead of enumerating the faults, is the same attack-the-shared-consequence move covered elsewhere on this site, where one general mechanism replaces a growing list of special cases.

Diversity among your voters is the whole signal, and persuasiveness is a design goal. Two engineering choices deserve attention. First, since the signal comes from disagreement, it depends entirely on how DIFFERENT the implementations are. The authors measure this and the result is clean — the best pair is an unoptimizing build of one compiler against an aggressively optimizing build of the other, while the worst pair is two adjacent optimization levels of the same compiler, which share too much to disagree. Second, they justify comparing only final outputs partly on grounds of persuasion. Checking internal values would find more bugs but would produce reports developers find less convincing, whereas a difference in what the program PRINTS, between two configurations people genuinely ship, is self-evidently a real defect — and 52 of 78 reported bugs were fixed. Choosing a signal for its credibility to the people who must act on it, not only for its sensitivity, is the same measure-the-thing-that-matters instinct covered elsewhere on this site, where a technically finer metric loses to one that actually changes behaviour.

Deleting a bounds check that guards a buffer

the intent is defensive, and on a naive reading of the machine the second guard is exactly right
wrapping is precisely what would let a huge length slip past the first check

Why it works

• Undefined behaviour lets each compiler transform the program differently → binaries compiled from one source stop agreeing on what the program does → so a disagreement observed at runtime is itself proof that the source contains something the standard left unspecified.
• The detector targets the shared consequence rather than each individual cause → one mechanism covers a diverse range of undefined behaviour at once → including classes for which nobody knows how to build a dedicated check, and bugs that are not undefined behaviour at all.
• Only final outputs are compared, never internal state → nothing about the program needs instrumenting and nothing is perturbed → the method composes freely with sanitizers and with the fuzzer, which keeps its own logic untouched.
• The signal is disagreement, so it scales with how different the implementations are → an unoptimizing build of one compiler against an aggressive build of another disagrees most → that pair alone reaches about 98 percent of the benchmark detection at roughly a fifth of the cost.
• Every configuration used is one that real developers and users ship → a reported divergence demonstrates the program already misbehaves in practice → which is why developers confirmed 65 of 78 reports and fixed 52.

What it costs (trade-offs and scope)

• It cannot see a fault that leaves no trace in the output. Because only final outputs are compared, an erroneous state that never propagates to what the program prints is invisible. The authors call these vanishing errors and accept them as the price of the design.
• Not all undefined behaviour actually destabilizes a program. Compilers may simply not exploit a given instance, or may produce equivalent binaries anyway, in which case there is nothing to disagree about. Relatedly, two binaries can both go wrong in the same way — picking the same garbage value, for example — and print identically wrong output.
• It is weaker than sanitizers on their home ground. On integer errors and division by zero the dedicated sanitizer detects considerably more, and many bugs sanitizers found during fuzzing were invisible to this method. The authors are emphatic that it complements sanitizers rather than replacing them, and that both should be used.
• Programs whose output is genuinely non-deterministic break the assumption. The method needs deterministic output, though not deterministic execution — six of the 23 targets were multi-threaded or non-deterministic internally and worked fine. Where output does vary, it is usually timestamps or random values that a filtering script removes, but truly unordered output defeats it.
• Running ten builds costs roughly ten times normal execution, and triage is manual. A cheaper two-build configuration recovers most of the benefit at about twice normal cost. More awkwardly, because these bugs need not crash, there is no stack trace to point at the cause, and aligning execution traces across differently optimized binaries is hard — so deciding which reports are distinct was done by hand.

The evaluation

The tool was built on gcc 11.1 and clang 13.0 at five optimization levels each, giving ten implementations, and integrated into AFL++. It was measured first on 18142 tests from the Juliet benchmark suite spanning 20 weakness categories, where ground truth is known and each test has both a buggy and a clean variant, against three static analyzers and three sanitizers. It was then run on 23 open-source projects from 10 thousand to 4.6 million lines — including curl, php, openssl, tcpdump, wireshark, ImageMagick and libxml2 — with 24-hour fuzzing campaigns repeated 10 times, compared against the same fuzzer running sanitizer-instrumented binaries.

Check yourself

Sources

• Finding Unstable Code via Compiler-Driven Differential Testing (ACM DL, DOI 10.1145/3582016.3582053) — ASPLOS 2023.
• Author PDF — the full 14-page paper, read in full for this explainer.
• CompDiff source code (GitHub) — the tool and its AFL++ integration.