UBFuzz: Finding Bugs in Sanitizer Implementations

Sanitizers are the compiler tools that catch memory errors like buffer overflows by inserting run-time checks, and developers trust them to fire whenever a bug executes — but nobody had systematically checked whether the sanitizers themselves silently miss bugs; this paper from ETH Zurich builds UBfuzz, which generates programs that provably contain a chosen undefined behaviour and then uses a new test oracle called crash-site mapping to tell a genuine sanitizer miss apart from a legitimate compiler optimisation, turning up 31 false-negative bugs in GCC and LLVM over five months.

Why this problem is worth solving

The bugs the tool is meant to catch are the ones that turn into real security holes, which is why a tool that quietly misses them matters.

A sanitizer is the detector, and the failure mode that matters most is the one that leaves no trace.

What people did before, and where it broke

• Generate valid, bug-free programs to test the compiler. The mature line of compiler-testing work, led by generators like Csmith, produces large random programs guaranteed to be free of undefined behaviour, then checks the compiler mishandles none of them. Where it broke. By construction these programs contain no undefined behaviour, so they can exercise a sanitizer’s plumbing but can never test whether it catches a bug — there is no bug in them to catch.
• Reuse that valid-program machinery to catch false positives. Because the generated programs are known-clean, any sanitizer report on them is a false positive, and this is trivial to check. Where it broke. It only finds the easy, self-announcing direction of error; a false negative is a missing report, and a generator of clean programs produces no bug whose absence you could detect.
• Randomly mutate a valid program to introduce bugs. Delete statements, change variable values, and hope some mutants become buggy. Where it broke. In the evaluation only about 4 percent of mutated programs actually contained undefined behaviour, they covered only a few bug types, and across a million of them not a single sanitizer false negative was found.
• Turn off a generator’s safety wrappers. Csmith normally guards every risky operation, for example rewriting division to avoid divide-by-zero; disabling those wrappers lets bugs through. Where it broke. It only ever produces three numeric bug types, and because it tends to inject several bugs at once, a missed report cannot be pinned to any one of them; it too found zero sanitizer bugs.
• Use an existing hand-built suite of buggy programs. The NIST Juliet suite is the most comprehensive public collection of programs with known undefined behaviour. Where it broke. Feeding its 16,344 sanitizer-detectable programs through the pipeline found no false negatives at all — fixed hand-written cases do not probe the odd corners where sanitizers actually break.
• Only test at the lowest optimisation level to sidestep the confusion. If optimisation is what deletes buggy code, compile everything at -O0. Where it broke. Even -O0 does basic constant folding that can remove a bug, and many real sanitizer false negatives appear only at higher optimisation levels, so testing at -O0 alone misses the most important cases.
• The gap. No one had a way to manufacture a specific, real bug on demand, and no one had a way to tell a true sanitizer miss apart from the compiler having legitimately optimised the bug away. Without both, the whole false-negative direction was untestable.

How UBfuzz manufactures a bug and then trusts the result

The idea

Instead of hoping a bug appears, measure the program and place exactly one. The generation problem looks intractable if you treat it as random search, because a specific undefined behaviour is a needle: most mutations leave a program valid, and the ones that break it usually break it in the wrong way. UBfuzz reframes bug-making as a targeted edit informed by facts. For a chosen bug type it enumerates the constructs that could exhibit it, profiles a real run to learn the concrete state at each one — a buffer’s size, a pointer’s address, whether a variable is live — and then synthesises a single shadow statement that nudges one construct across the line into misbehaviour, while every other part of the program stays valid. The bug is not stumbled upon; it is computed and installed, one per program, with its type known in advance. Turning a search for rare, hard-to-reach test inputs into a construction guided by what the program actually does at run time is the same move the deep-learning-compiler test generator covered elsewhere on this site makes, building inputs to satisfy the constraints that reach deep code rather than throwing random cases at the wall.

A missing report is not evidence until you rule out the compiler having done its job. The second, subtler half is the oracle — deciding what a silent run means. Compilers are allowed to assume programs have no undefined behaviour, so an optimiser will happily delete code it can prove is buggy, and after that deletion there is honestly nothing for the sanitizer to catch: the silence is correct, not a bug. Testing across compilers or optimisation levels surfaces plenty of discrepancies for exactly this reason, and most of them are innocent. UBfuzz’s crash-site mapping cuts through it by asking a concrete question: in the binary that did report, which single instruction crashed, and what source line is it? Then, in the silent binary, was that same source line executed at all? If it was, the buggy operation genuinely ran and the sanitizer simply failed to check it; if it was not, the optimiser removed it and the sanitizer is blameless. The hard part being the oracle rather than the input — knowing whether a silent tool is correct or broken — is the same difficulty the unstable-code differential-testing work covered elsewhere on this site confronts, where a compiler silently discarding undefined code is exactly the behaviour that has to be told apart from a fault.

Differential testing only works when the comparison is disciplined by precise run-time analysis. The design leans on differencing two builds, but naive differencing is what makes optimisation and bugs indistinguishable, so precision has to be reintroduced at both ends. On the input side, the same profiling that places the bug also keeps it inside the window the sanitizer can actually detect — the address-sanitizer, for instance, only notices overflows within about 32 bytes, so the shadow statement is tuned to land the bad access in that range rather than wildly out of bounds where the check would not fire anyway. On the oracle side, the debugger trace grounds the comparison in a specific executed instruction rather than a whole-program pass or fail. Both ends replace a vague global comparison with a measured, local one, and that is what turns thousands of ambiguous discrepancies into a handful of real findings. Making a differential test trustworthy by controlling precisely what is compared, rather than trusting a raw pass-or-fail difference, is the same discipline the speculation-contract CPU-testing work covered elsewhere on this site relies on, where the whole art is defining exactly what counts as a violation.

Following one buggy program through UBfuzz

Two kinds of log statement are inserted — one recording the address range of each stack buffer, one recording the address each candidate access will touch. They exist only to gather run-time state and are removed afterward.

Why it works

• The bug is constructed from measured facts, not stumbled upon. Random mutation leaves about 96 percent of programs with no undefined behaviour → but profiling the real run reveals the exact buffer size, address, or liveness needed to break one chosen construct → so a single synthesised statement installs a specific, known bug type in nearly every generated program, giving the 13,872 buggy programs that random methods could not produce.
• The overflow is aimed inside the detector’s own window. An arbitrarily large out-of-bounds access would exceed the roughly 32 bytes AddressSanitizer can see and so would not test detection at all → but the measured buffer size lets the shadow statement place the access just past the boundary → so the program probes the sanitizer where it is supposed to work, turning a silent run into real evidence rather than an unfair miss.
• The oracle separates a real miss from a legitimate optimisation. A silent build can mean either a sanitizer fault or the compiler correctly deleting dead buggy code → but tracing which instruction crashed in the reporting binary and checking whether that same source line runs in the silent binary distinguishes the two → so of 6,567 raw discrepancies only 58 survive, and manual review found every one of them to be a genuine sanitizer bug.
• Debug metadata is what lets the crash site be located at all. Optimised instructions have no obvious tie back to source lines → but compiling with debug information attaches a line and offset to each instruction, which the debugger reads to identify the crash site → so the mapping compares the right locations across two differently optimised binaries instead of guessing.
• Differencing two builds of one compiler avoids cross-compiler ambiguity. Comparing GCC against LLVM cannot tell whether a difference is a bug or just different legal optimisation → but comparing the same compiler at -O0 and -O2 holds the implementation fixed so the only variable is optimisation → so a mapped crash site that survives points squarely at a missing check rather than at two tools disagreeing.

What it costs (trade-offs and scope)

• The headline count is softer than 31. Of the 31 reported bugs, developers confirmed 20 as previously unknown real bugs, and only 6 were fixed — all 6 in GCC. The LLVM maintainers were less responsive and mostly labelled reports without diagnosing them, so a large share of the count is reported-but-unsettled rather than confirmed-and-fixed.
• Recall is estimated from a sample, not proven. Crash-site mapping achieved perfect precision on the 58 discrepancies it selected, but recall — whether it wrongly discards real bugs — was checked by manually inspecting only 200 of roughly 8,000 dropped discrepancies. None were real bugs in that sample, which suggests but does not establish high recall.
• The oracle assumes debug information is correct, and it is not always. Crash-site mapping depends on the instruction-to-source mapping being accurate, yet the paper notes that compiler bugs can produce wrong debug metadata, which could in principle make the oracle flag a phantom crash site. They observed no such false positive but assume correct metadata rather than handling the bad case.
• The baselines that found nothing are the authors’ own. MUSIC and Csmith-with-safety-off each generated around a million programs and found zero sanitizer bugs, and the Juliet suite likewise found none. These make the case that a targeted generator is necessary, but they are strawman comparisons the authors ran, not competing tools built for this task.
• Coverage gains are modest. Measured on sanitizer-related source files, all generators including UBfuzz produced only a moderate increase in line, function, and branch coverage over the seeds — the bug-finding comes from hitting specific fragile paths, not from broadly exercising more code.
• The bug menu is fixed and the seeds are C only. The generator supports a defined list of undefined-behaviour types wired into a table of shadow statements, and it builds on Csmith seeds, so it is C, not C++, and extending to a new bug type means adding a new construction rule by hand.
• Generality to other detectors is asserted, not shown. The paper argues the same approach could test dynamic tools like Valgrind or static tools like Infer, but the evaluation is entirely on GCC and LLVM sanitizers; nothing beyond compiler sanitizers was actually tried.
• One reported program was not a real bug. At least one report was ruled invalid by developers — a reminder that even a targeted generator plus a precise oracle produces the occasional misfire that needs human judgement to catch.

The evaluation

Check yourself

Sources

The paper is “UBfuzz: Finding Bugs in Sanitizer Implementations” by Shaohua Li and Zhendong Su, published at ASPLOS 2024, pages 435-449, DOI 10.1145/3617232.3624874. The authors are at ETH Zurich.

This explainer is written from the full 15-page text. Everything above comes from the paper’s own sections: the introduction motivating false-negative sanitizer bugs and the two challenges of generating undefined-behaviour programs and interpreting silent runs, with the confirmed-and-fixed GCC AddressSanitizer example of a missing check; the illustrative-examples section walking through shadow statement insertion on a stack-buffer-overflow seed and through crash-site mapping across an -O0 and an -O2 binary; the approach section with its table of undefined-behaviour conditions and shadow-statement instantiations and its program-generation algorithm; and the evaluation across four research questions — bug-finding with the reported, confirmed, fixed, and invalid counts for GCC and LLVM AddressSanitizer, UndefinedBehaviorSanitizer, and MemorySanitizer; the generator comparison against MUSIC, Csmith-with-safety-off, and the Juliet suite; the precision and recall of crash-site mapping on the 6,567 discrepancies; and the sanitizer-file code-coverage measurements — together with the root-cause categorisation of the bugs and the discussion of soundness and of generality to other undefined-behaviour detectors.