Plankton: Reconciling Binary Code and Debug Information

Serious bug-finding tools need to hijack your build to get code they can analyse, which fails often enough that one commercial vendor has been chasing build-system compatibility for over twenty years; Plankton (HKUST) skips the build entirely and analyses the shipped binary, using the debug information almost every project already emits — and then does the interesting part, which is inferring the roughly one fifth of variable information the debug data never had, by propagating what it does know along data dependences.

Why this problem is worth solving

The deployment barrier for static analysis has almost nothing to do with the analysis.

One loss matters more than the rest.

What people did before, and where it broke

• Wrap the compiler and capture the intermediate form. How mature analysis tools get analysable code — a custom compiler or parser substituted into the build. Where it broke. The diversity of build systems makes this a permanent maintenance burden that still fails in practice, and it is impossible when the code and its build pipeline are not yours to run.
• Lift the binary into an emulation-style representation. Several lifters faithfully model machine execution instruction by instruction, which is correct and completely general. Where it broke. The result is too low-level for analyses written against source-level structure. Run against a state-of-the-art analyser, these produce no true positives at all.
• Apply the debug information directly to the lifted code. A more sophisticated lifter reads the debug data and uses what it says. Where it broke. It treats the debug information as complete when it is not, and does not reconstruct complex aggregate types, so the analyser can only find bugs involving simple data flows.
• Use only the function boundaries from the debug data. Another lifter takes a narrow slice of what is available. Where it broke. Ignoring the rest leaves results inaccurate enough to yield nothing useful.
• Use a production decompiler. The commercial and open-source reverse engineering tools are far more mature than any research lifter. Where it broke. Their algorithms rest on predefined rules and patterns, so in the paper’s worked example they declare stack references that are fields of one structure as independent values. Their output also needs substantial manual work to become recompilable, which is often infeasible at scale.
• The gap. Everyone treated the debug information as either absent or authoritative. It is neither — it is present almost everywhere and covers roughly four fifths of what is needed, and nobody had asked what to do about the remaining fifth.

How Plankton reconstructs source-level structure

The idea

Stop trying to get into the build, and take what the build produced. The framing here is that the last mile of static analysis is not analysis at all — it is compatibility engineering. A tool must persuade an arbitrary project’s build to run its compiler instead of the real one, across more than twenty build systems and thirty-six compilers for a single language, and the paper cites a commercial vendor twenty years into that effort with the outcome still not guaranteed. Worse, an entire category of use is simply excluded, since a service scanning code it was handed cannot run a build it does not have. The binary sidesteps all of it, because it is the one artefact that always exists and depends on nothing. The question the paper then has to answer honestly is whether analysis on the lifted code behaves like analysis on the real thing, which is why the evaluation compares against source-compiled results rather than reporting bug counts. Making rigorous source-level analysis actually deployable is the motivation behind the path-sensitive typestate analysis work covered elsewhere on this site, which is the kind of analysis this is trying to put within reach.

Debug information is nearly universal and systematically incomplete, and the gap has to be inferred rather than ignored. The availability argument is stronger than it first appears — a survey of a hundred popular projects found every single one able to emit debug information, operating systems ship debug symbol packages, and it is retained because developers need it for crash diagnosis and profiling regardless of anything else. But compilers cannot map every instruction back to source, so on average only about four fifths of stack references get a name, falling to roughly a third in one large project. Prior lifters split into those that ignore this data and those that trust it completely; nobody worked on the missing fifth. The insight that makes that tractable is that code fragments connected by data dependences are also connected in their source-level properties, so what is known about one end can be pushed to the other. Treating incomplete debug information as a thing to be measured and repaired rather than assumed away is the same stance as the work on poking holes in incomplete debug information covered elsewhere on this site.

Measure against a moving target, and report that it moves. The paper’s headline is that analysis on lifted code differs from analysis on source-compiled code by 17.2 percent. What makes that number interpretable is a control the authors did not have to run — take the source-compiled representation, apply nothing but a round of standard optimisation, and compare it against its own unoptimised self. That comparison produces a slightly higher false positive rate than Plankton does, with essentially the same true positive count and comparable false negatives. In other words, the ground truth disagrees with itself by about as much as lifting from a binary disagrees with it. The authors trace this to analysers not being consistent across representations that are semantically equivalent but syntactically different, and they go further, identifying that one analyser assumes unoptimised input and that this assumption accounts for almost all of its false negatives on their output. Discovering that semantically identical programs make a tool answer differently is the same phenomenon as the compiler differential testing work covered elsewhere on this site.

Recovering a variable the debug data never named

That constraint alone does not settle it. The two could still be genuinely separate variables that the compiler placed in the same memory because their lifetimes do not overlap, which is the whole reason variable boundaries are hard to recover. Deciding between the two possibilities is what the scope analysis exists for.

Why it works

• Data dependence carries source-level identity. Two instructions linked by a value must agree on which variable that value lives in → so a name known at one end of a dependence can be pushed to the other → which is what fills gaps the debug information left, rather than merely reporting them.
• Block structure constrains scopes far more than it looks. Scopes are continuous, and any two are identical, disjoint or nested, never partly overlapping → so a handful of scattered live points plus dominance relations pin down a whole region → and rules about how compilers assign slot lifetimes make the inference match what the compiler actually did.
• Overlap plus simultaneous liveness is a proof, not a heuristic. Distinct variables never occupy overlapping memory while both are live → so two overlapping slots alive at the same instruction must be one variable or a variable and its field → and the same fact read backwards stops the over-approximate pass from merging things that are genuinely distinct.
• Counting type conversions turns type correctness into something optimisable. A strongly typed representation forces an explicit conversion wherever a type is wrong → so fewer conversions means more values carrying correct types → which converts an inference problem into minimising a number that semantics-preserving rewrites can drive down.
• Types can be wrong in both directions, so the search has to go both ways. Debug information can be over-precise as well as under-precise, since an inlined function may use a value directly while the data still calls it a pointer → so rewrites that make types less precise are needed alongside those that make them more precise → and alternating the two gives 31.4 percent fewer conversions than only sharpening.

What it costs (trade-offs and scope)

• The baseline it is measured against is itself unstable, and the paper shows this. Re-optimising the source-compiled representation and comparing it to its own unoptimised self yields a higher false positive rate than Plankton, comparable false negatives, and essentially the same true positive count. The 17.2 percent figure should be read against a target that moves about that much on its own.
• The headline numbers are the better compiler. With one compiler the false positive and negative rates are 20.7 and 20.9 percent for one analyser and 13.7 and 22.1 percent for the other. With the other compiler they rise to between 23.8 and 25.8 percent. The authors state they used the first for the main comparison to remove compiler differences, which is defensible and does mean the headline is the favourable half.
• Individual projects can be far worse than the average. On one project under the second compiler the false negative rate is 75.4 percent, falling to 15 percent only if inlining is disabled during compilation. A separate transformation added specifically to unify return instructions eliminated 216 false positives on another project.
• It needs debug information to be there. Every surveyed project can emit it, but the binary in hand must actually carry it — and it is absent for dynamically linked libraries, which measurably degrades results on two of the evaluated projects. Reading external libraries’ debug data is left as future work.
• The optimisation that recovers types breaks an assumption one client analyser makes. That analyser expects unoptimised input, and optimisation rewrites typed field arithmetic into untyped pointer arithmetic plus casts, so it stops resolving memory allocation function pointers — which the paper says accounts for almost all of its false negatives.
• Optimisation also moves the answers. Merged or deleted call sites change the reported source and sink locations, and every false negative in one bug class comes from allocations and deallocations being optimised away entirely.
• Reverse engineering gaps remain, and one is significant. Virtual tables in C++ classes cannot be parsed accurately, causing false results in C++ code.
• The metric measures agreement, not truth. Reports are compared by source and sink location against what the source-based tool found, so agreeing with that tool’s false alarms counts as success and finding a real bug it missed counts as a false positive. The paper is explicit that evaluating the analysers is not the goal.
• Scope is one architecture, one representation, and no recompilation guarantee. Only x86-64 is evaluated, only LLVM’s representation is produced, and the output cannot be reliably recompiled because some machine instructions have no counterpart and not all library functions are modelled — so downstream uses such as post-link optimisation need further work.

The evaluation

Check yourself

Sources

The paper is “Plankton: Reconciling Binary Code and Debug Information” by Anshunkang Zhou, Chengfeng Ye, Heqing Huang, Yuandao Cai and Charles Zhang at the Hong Kong University of Science and Technology, published at ASPLOS 2024 Volume 2, pages 912-928, DOI 10.1145/3620665.3640382.

This explainer is written from the full text of the published paper. Everything above comes from its own sections 1 through 6: the framing of compilation interference as the last mile problem, with the counts of build systems and compilers, the twenty-year commercial compatibility effort, and the observation that cloud scanning services cannot access build pipelines; the worked examples showing how stack slot reuse manufactures a dependence that does not exist in the source and how an allocated pointer passing through integer registers breaks the data flow and produces a false memory leak report; the survey finding all hundred examined projects able to emit debug information, alongside the measurement that only about 81 percent of stack references map to variables on average and as few as 35 percent in one project; the survey of existing lifters and production decompilers and why each falls short; the section 3 stack disambiguation algorithm with its interference definition, must-scope inference from data-flow facts, the six scope invariants and their justification in compiler slot-lifetime behaviour, the union-find merging of simultaneously live overlapping slots, and the may-scope pass with its visibility contradiction rule; the section 4 type enforcement algorithm with its type lattice, promotion and demotion rules, termination argument and dynamic fixed point; and the section 5 evaluation, including the lifter comparison across 48 binaries, the per-compiler result breakdown, the scalability and time-breakdown measurements, the ablation study, the reported effect of disabling may-scope inference, the control experiment re-optimising the source-compiled representation, and the analysis of false-case root causes including the unoptimised-input assumption, optimised-away allocations, missing debug data for dynamically linked libraries, and unparsed C++ virtual tables.