Accurate Disassembly of Complex Binaries Without Use of Compiler Metadata

Turning a stripped binary back into assembly instructions is the first step of every security tool that inspects compiled code, but on x86 it is genuinely hard because data is often mixed into the code and there is no reliable way to tell them apart; this work from Stony Brook builds Dassa, which flags code by how sharply its bytes deviate from the stable statistics of real data and flags data by the fact that it violates rules every valid program must obey, then combines the two with a confidence-ranked conflict resolver to disassemble complex binaries 3 to 4 times more accurately than the best tools, without needing any compiler metadata.

Why this problem is worth solving

Before any of this makes sense, it helps to see just how little structure a raw binary hands you.

The reason accuracy is so hard to win is that the two ways of being wrong pull against each other.

What people did before, and where it broke

• Linear sweep (objdump). Decode every byte in order from the start of the code section. Where it broke. It achieves high coverage but blindly decodes embedded data as instructions, producing a high false-positive rate on any complex binary.
• Recursive disassembly (Ghidra, Angr, Dyninst). Follow jumps and calls outward from known entry points, so data regions are naturally skipped. Where it broke. It cannot follow computed or indirect jumps whose targets are known only at runtime, so it misses code — on average about a fifth of it — a high false-negative rate.
• Assume clean gaps and scan them speculatively. Run recursive disassembly first, then linearly sweep the leftover gaps as if they were code. Where it broke. Real complex binaries do embed data in those gaps, so the speculative sweep reintroduces exactly the false positives recursion avoided.
• Lean on compiler metadata. Use relocation tables or C++ exception-handling metadata, which survive stripping, to distinguish code from data. Where it broke. This metadata is frequently absent (in COTS, non-Linux, or C-rather-than-C++ binaries), too large to ship (Chrome disables it), or incomplete — missing for one percent of Firefox’s code.
• Probabilistic disassembly. Assume data bytes are uniformly random and derive the low chance of code-like patterns occurring by accident in data. Where it broke. The uniform assumption is simply false — about 30 percent of data bytes are zero — which overestimates confidence by up to a hundredfold, and multiplying pattern probabilities compounds the error, leaving a 3.4 percent error rate.
• The gap. Each method fixed one failure at the cost of another, and the accurate ones quietly assumed away embedded data or trusted metadata that real binaries do not carry. What was missing was a way to attack both error types at once, on stripped binaries that genuinely mix code and data, using only what is inside the bytes themselves — which is exactly what accurate disassembly of complex binaries needs.

How Dassa works

The idea

Model the data, not the code, because data is the stable thing. The instinct is to describe what code looks like, but code is wildly variable — every program uses different opcodes and operands — so any statistical model of it is fragile. Dassa inverts the problem: it models data, which turns out to be remarkably stable. Across binaries spanning three orders of magnitude in size, the distribution of data byte values barely moves — roughly 30 percent zeros and the rest nearly uniform — so the chance that a code-like pattern (say a long jump landing at a valid target) appears in data by accident can be computed precisely and honestly. Earlier work assumed data was uniformly random and overestimated its confidence a hundredfold; Dassa measures the real distribution instead. Grounding a decision in the measured statistics of the thing you can actually characterize, with a calibrated confidence rather than an optimistic guess, is the same discipline the hardware-verification-coverage work covered elsewhere on this site follows, estimating how much a design has really been exercised from samples with honest bounds instead of trusting a convenient assumption.

Flag data by the rules that all real code must obey. To catch the code that statistics might miss without drowning in false positives, Dassa turns to the other side: properties every valid function has, that data has no reason to satisfy. Real code does not dereference a pointer it never initialized (that would fault), and it preserves the callee-saved registers the calling convention reserves. A byte sequence that violates one of these — checked by a static analysis that flags only definite, unavoidable violations — cannot be legitimate code, so it must be data. The essential move is conservatism: the analysis is designed never to accuse valid code, so a flagged violation is near-certain. Reasoning soundly about what a program must do, so that the analysis never wrongly condemns a correct program, is the same guarantee the quantum-program verification work covered elsewhere on this site is built on, whose correctness logic is careful never to certify or reject a program on unsound grounds.

Let a confidence score decide which checks to trust. The hard part is that neither signal alone reduces both error types, and the naive combinations trade one for the other: demand that both techniques agree and you cut false positives but raise false negatives; accept if either agrees and you do the reverse. Dassa’s resolution is that the statistical score is not a yes-or-no verdict but a graded confidence, and confidence is exactly what the behavior checks lack. So when a candidate scores high enough, Dassa skips the checks that tend to cause false negatives and trusts the statistics; only when the score is low does it apply the full, cautious battery. Applying an expensive safeguard only when a cheap measured signal says it is actually needed, and skipping it when confidence is already high, is the same economy the self-replicating page-table work covered elsewhere on this site practices, replicating only where a workload signal shows the copy will pay for itself.

Following a binary through Dassa

These roots are needed for the binary to load and run, so they survive stripping.

Why it works

• Data has a stable statistical signature that code violates. Code is too variable across programs to model directly → but real data bytes follow a distribution that barely changes from tiny to enormous binaries, about 30 percent zeros and the rest nearly uniform → so a byte sequence that deviates sharply from that distribution can be flagged as code with a calibrated, honest confidence instead of a guess.
• Valid code must obey rules that data has no reason to satisfy. Any real function runs without faulting and preserves the callee-saved registers the ABI reserves → but embedded data decoded as instructions routinely dereferences uninitialized pointers or clobbers those registers → so a violation of a universal code rule is near-proof that the bytes are data, caught with essentially no risk of rejecting real code.
• Speculating broadly and then pruning keeps coverage without the usual cost. Finding code reached only through computed jumps requires guessing many candidate starts, which also decodes lots of data → but ranking every candidate by its statistical score and resolving overlaps from the top down lets confident code win and occluding junk lose → so false negatives stay low without the false positives speculation normally brings.
• A graded confidence bridges the two techniques where a yes-or-no answer cannot. Combining the checks naively cuts one error type only by inflating the other → but a high statistical score lets Dassa skip the checks that cause false negatives and apply them only when confidence is low → so both error rates fall together instead of trading off against each other.
• Conservative, linear-time analysis keeps it both sound and scalable. Speculative disassembly analyzes an order of magnitude more code than the binary contains, and abstract interpretation can blow up exponentially → but flagging only definite violations and running each check in time linear in function size protects valid code and bounds the cost → so accuracy does not come at the price of soundness or scale.

What it costs (trade-offs and scope)

• It is specific to x86-64 on Linux. The whole method is wired to that platform’s conventions — the ABI’s callee-saved and argument registers, the observed byte distribution, the instruction encodings. Other architectures and object formats would need their own calibration, though disassembly is generally easier on fixed-length instruction sets to begin with.
• The conservative checks let some data through. To never reject real code, the behavior checks flag only definite violations, so embedded data that happens to obey the code rules slips past. On the hardest benchmark the register check removed only a fifth of the false positives, because most misdecoded data never touches a callee-saved register. The statistical scoring recovers much of the rest, but not all.
• The thresholds are tuned to the benchmarks. The acceptance score that yields the lowest error was chosen empirically on these datasets, and a rejection threshold they tried had to be abandoned because it inflated false negatives a hundredfold. The sweet spot could shift on a different corpus.
• It trades speed for accuracy. Dassa is about four times slower than DDisasm, its closest competitor in accuracy. It does buy back scalability — its runtime grows linearly with binary size where DDisasm can exhaust memory on large binaries — but it is not the fastest tool available.
• Some soundness rests on an argument, not a proof. To run fast, the static analysis starts from an imprecise-but-sound approximation and takes shortcuts; the authors argue the lost precision only matters on code, which lacks the loops and structures where it would bite, but that is reasoning about the workload rather than a guarantee.
• It is accurate, not perfect. The best average error is still 0.31 percent on the embedded-data benchmark. Small, but each spurious or missing instruction can ripple into whatever analysis consumes the disassembly.
• Ground truth carries its own assumptions. Accuracy is measured against a ground truth produced by a modified compiler or by disassembling debug information, so the reported numbers are only as trustworthy as those reference oracles.

The evaluation

Check yourself

Sources

The paper is “Accurate Disassembly of Complex Binaries Without Use of Compiler Metadata” by Soumyakant Priyadarshan, Huan Nguyen, and R. Sekar, published at ASPLOS 2023 (Volume 4), DOI 10.1145/3623278.3624766. The authors are at Stony Brook University, and the system, Dassa (Disassembly Aided by Statistical and Static Analysis), is released as open-source software.

This explainer is written from the full 18-page text. Everything above comes from the paper’s own sections: the introduction motivating metadata-free disassembly and stating the code-versus-data challenge; the analysis of why recursive disassembly falls short (indirectly reached code, non-returning calls, unreachable code) in Section 2; the statistical technique in Section 3 that replaces the prior uniform-random data assumption with the empirically measured byte distribution (roughly 30 percent zeros, stable across binaries from 200 kilobytes to 190 megabytes), derives per-pattern data probabilities for long unconditional and conditional control-flow transfers and function prologs, and combines evidence additively via a code-over-data score; the static analysis in Section 4 that flags data through invalid control flow, invalid pointer dereferences (via a two-point abstract-interpretation domain seeded from the ABI), and callee-saved-register violations (via a custom linear-time relational domain), with the lazy-loading and top-down fixpoint tricks for scalability; the three-phase prioritized error-correction algorithm in Section 5 (definite code, then a large superset of possible code, then confidence-ranked conflict resolution that resolves occlusions and non-returning calls and skips full checks above the acceptance threshold); and the evaluation in Section 6 on the Pang et al. and Stochfuzz benchmarks, reporting average errors 3 to 4 times lower than DDisasm, Angr, Dyninst, and Ghidra (and 3 to 10 times lower than Ghidra despite its exception-handling metadata), the 70 percent average false-positive reduction from the behavior checks at under 0.03 percent false negatives, and the linear scaling of both the static analysis and total disassembly time.