Debugger Toolchain Validation via Cross-Level Debugging

A debugger can quietly lie — showing the wrong line or the wrong variable value — and there is no obvious way to test whether it is telling the truth, because you would need to already know the right answer; this paper from Nanjing University finds an answer hiding in plain sight, by stepping through the very same compiled program two ways in the same debugger, once line-by-line and once instruction-by-instruction, and checking that the two accounts agree, which they must if both are correct, catching 27 real bugs in GDB and LLDB, many of which appear even without any compiler optimization and so were invisible to every prior tool.

Why this problem is worth solving

The tool under suspicion is one developers lean on precisely when they are most confused, which is what makes its failures so costly.

The reason these tools go under-tested is a classic obstacle in software testing.

What people did before, and where it broke

• Check variable values with hand-crafted actionable programs. One line of work builds special programs whose variables have known values at known points, then checks the debugger reports them correctly across optimization levels. Where it broke. It targets variable values specifically and leans on programs constructed for the purpose, so it covers a narrow slice of debugger behavior.
• Define trace invariants across optimized and unoptimized runs. The Debug2 line establishes invariants over the hit line, the backtrace, and function parameters, comparing an optimized build’s trace against an unoptimized reference. Where it broke. It still compares two different executables, so optimization’s deletions and reorderings make many traces genuinely incomparable, and it can only surface faults that optimization introduces.
• Study the completeness of debug information. Other work asks whether debug information is complete — whether variables that should be inspectable actually are. Where it broke. Completeness is one property among many; it does not check that the values, lines, and ordering the debugger reports are actually correct.
• Trust the unoptimized trace as the oracle. The shared assumption underneath the optimized-versus-unoptimized approach is that debugging the unoptimized build gives the right answer. Where it broke. That assumption fails for any bug present at the lowest optimization level, since then the reference itself is wrong and there is nothing correct to compare against.
• The gap. Every prior method needed either a purpose-built program or a second, differently-optimized executable to serve as a reference, which confined them to optimization-related bugs and to comparisons that optimization itself renders unreliable. What was missing was an oracle that needs no external reference at all — one derived from a single build.

How Cross-Level Debugging works

The idea

The oracle is hiding inside the tool: two views of the same run must tell the same story. The obstacle was that testing a debugger seemed to need a correct answer computed some other way. Cross-Level Debugging finds that answer without leaving the debugger, by exploiting a structural fact about how source maps to machine code: one source line compiles to many instructions, but each instruction belongs to exactly one source line. So instruction-level stepping is simply a finer-grained view of the very same execution that source-level stepping shows coarsely. Two views of one deterministic run cannot legitimately disagree — if line-by-line stepping says a line executed, or ran before another, or that a variable held some value there, instruction-by-instruction stepping of the identical binary must say the same. When they diverge, at least one of them is wrong, and the toolchain has a bug. The oracle is not an external reference at all; it is an internal consistency that correctness forces. Manufacturing a trustworthy oracle out of a relation that any correct implementation must satisfy, rather than out of a known-good answer you do not have, is the same move the sanitizer-testing work covered elsewhere on this site makes when it builds an oracle from whether a crash site still executes, deciding a silent tool is wrong without ever needing a reference tool that is right.

Because it compares one build to itself, it escapes the optimization trap entirely. The prior methods were shackled to optimization: they compared an optimized executable against an unoptimized one, so they could only ever see bugs that optimization caused, and even then the comparison was noisy because the two builds were different programs. Cross-Level Debugging compares a single build against itself at two granularities, which cuts that shackle. It runs at any optimization level, including the lowest, where a great many debugger bugs actually live — bugs that have nothing to do with optimization and that the optimized-versus-unoptimized approach can never surface because at that level its own reference is equally wrong. In the study, eleven of the eighteen confirmed bugs appeared with no optimization at all, and all four rated critical were among them. Catching the faults in the compiler-debugger contract that are unrelated to optimization, precisely the ones a differential-across-optimization method structurally cannot reach, is the same territory the missing-variable debug-information work covered elsewhere on this site explores, hunting the ways a debugger loses track of program state even in plainly compiled code.

Turn an interactive, un-batchable tool into something a framework can exhaustively poke. A debugger is awkward to test because it is interactive — its behavior depends on a live sequence of human commands issued against a running program’s state — so there is no obvious set of inputs to sweep. Devil, the framework, makes the behavior systematically explorable: it forwards the program to a randomly chosen location, by breakpoint or by stepping, to reach varied program states, then drives the debugger automatically to step all the way to exit at each level, scripting the command sequences that record locations and variable values. What was a manual, one-off interaction becomes a repeatable batch experiment that can be run across a whole test suite and every optimization level, so tens of thousands of programs can be checked without a human in the loop until a violation appears. Converting a tool that is normally exercised by hand into one that a harness can drive exhaustively and compare against an expectation is the same discipline the emulator-fidelity work covered elsewhere on this site applies, systematically locating the instructions where a supposedly faithful tool quietly diverges from the truth.

Following one bug through Devil

Because the bug shows even at -O0, the unoptimized build that prior tools trust as their oracle is itself wrong here — there is no correct reference to compare against.

Why it works

• Same executable, same input, so any disagreement is real. Prior methods compared two different builds whose traces optimization had made incomparable → but two stepping strategies run the identical binary on the identical input, one deterministic execution viewed twice → so a divergence between the traces cannot be an artifact of comparison and must be a fault in the toolchain.
• Instruction level is a strict refinement of source level, so the relations are forced. Each instruction maps to exactly one source line while a line spans many instructions → so instruction-level stepping is a finer view of the same run, and reachability, order, and value agreement must hold by construction → which means a violation is a sound bug signal that needs no known-good answer to interpret.
• It never trusts an unoptimized reference, so it works at -O0. The optimized-versus-unoptimized approach assumes the unoptimized trace is correct → but Cross-Level Debugging derives its check from one build alone, making no such assumption → so it finds the eleven-of-eighteen confirmed bugs that appear with no optimization, which prior tools structurally cannot see.
• Forwarding to random locations widens what gets exercised. Stepping only from the program’s start reaches a narrow band of states → but starting from many randomly chosen locations drives the debugger through more of the program’s behavior → so more latent discrepancies surface than a fixed entry point would reveal.
• One oracle audits both halves of the toolchain. A trace violation does not presuppose whether the compiler or the debugger erred → because both emit or consume the same debug-information contract that the relations check → so a single method exposed bugs later attributed to the debugger and to the compiler alike, seven and eight respectively among the confirmed.

What it costs (trade-offs and scope)

• It checks consistency, not correctness. The oracle only fires when the two levels disagree, so a bug that corrupts both the source-level and instruction-level view in exactly the same way produces no violation and slips through — an inherent limit of any self-consistency oracle, which cannot see errors shared by both sides.
• A violation localizes to the toolchain, not to the culprit. When the relations break, the method flags the toolchain but does not say whether the compiler or the debugger is at fault; that still takes manual diagnosis, and at least one reported issue (GDB #26061) was closed as not-a-GDB-bug because the fault lay in GCC.
• Every violation needs manual triage. One underlying bug can produce many violations, so a human must inspect each before reporting to avoid duplicates and invalid reports — real labor that the automated part does not remove.
• The headline count is softer than 27. Of the 27 reported bugs, 18 are confirmed and 12 fixed; the remainder are unconfirmed, new, duplicate, or judged not-a-bug, so the settled result is closer to the confirmed eighteen than the reported twenty-seven.
• Strong assumptions about the program under test. The technique assumes the input is well-formed, deterministic, and single-threaded, with no undefined behavior — the GCC test suite was chosen precisely because it avoids undefined behavior — so concurrency bugs and undefined-behavior interactions are out of scope.
• The three relations are unevenly useful. Reachability preservation found about two-thirds of the confirmed bugs and all four critical ones, value consistency found five, and order preservation found only one, so much of the power rests on a single relation and the others contribute at the margin.
• It presumes the debugger supports both stepping modes faithfully enough to compare. The whole method drives step and stepi against each other, which only works on debuggers that offer instruction-level stepping — and that same machinery is part of what is under test.
• The scope is C on two toolchains, and the overhead is real. Only C programs on GDB and LLDB were evaluated, so generality to other languages and debuggers is asserted rather than shown; instruction-level stepping of a whole program is slow (up to several seconds per program on Clang at -O0), over eighty percent of the suite was excluded for not compiling standalone, and random start points make coverage nondeterministic — mitigated but not erased by selective debugging.

The evaluation

Check yourself

Sources

The paper is “Debugger Toolchain Validation via Cross-Level Debugging” by Yibiao Yang, Maolin Sun, Jiangchang Wu, Qingyang Li, and Yuming Zhou, published at ASPLOS 2025, pages 279-293, DOI 10.1145/3669940.3707271. The authors are at the State Key Laboratory for Novel Software Technology, Nanjing University.

This explainer is written from the full 15-page text. Everything above comes from the paper’s own sections: the abstract and introduction framing the oracle problem and the limits of comparing optimized against unoptimized executables; the background on the debugger toolchain, debug information, and prior validation work (Li et al., Di Luna et al. Debug2, Assaiante et al.), with the motivating GDB #27151 example; the approach section formalizing the three relations — reachability preservation, order preservation, and value consistency — and the Devil algorithm of forwarding to a random location, stepping at the source and instruction levels, recording traces of locations and variable values, and comparing them, with the three illustrative bugs (GDB #27151 for R#1, GDB #95360 for R#2, LLVM #46040 for R#3); and the evaluation across five research questions covering the 27 reported bugs with 18 confirmed and 12 fixed, the optimization-level breakdown (eleven confirmed at -O0), the importance analysis (four P2-critical), the per-relation contribution (R#1 about two-thirds), the comparison with Debug2 showing the two are complementary, and the overhead measurements for compilation, execution, and source- and instruction-level stepping.