Computer Science
New approach preserves multiple interpretations to improve binary decompilation accuracy
Researchers develop a decompilation technique that delays commitment to single interpretations, allowing it to resolve ambiguities using globally consistent type information.
Traditional binary decompilers make irreversible decisions at each step of analysis, committing to a single interpretation and discarding alternatives. This greedy approach leaves decompilers unable to recover compilable source code from real-world stripped binaries—a critical limitation since the evidence needed to resolve an ambiguity often appears far from where it initially arises.
The core challenge#
Compilation is inherently many-to-one: a single binary executable can arise from numerous valid source programs. Conventional decompilers handle this ambiguity poorly by freezing interpretations prematurely, preventing them from backtracking when later analysis reveals a better choice.
Superset decompilation framework#
Researchers propose Superset Decompilation, which reverses this strategy by maintaining multiple candidate interpretations simultaneously. The approach accumulates competing options across a hierarchy of intermediate representations using monotone Datalog rules. Only when all local evidence has been gathered does a weighted MaxSMT solver select a globally type-consistent C program, making the final interpretation choices.
Implementation and results#
The team built a working system in approximately 50,000 lines of Rust and Datalog that lifts stripped x86-64 Linux ELF binaries to C99 code via CompCert intermediate representations. Testing on GNU coreutils demonstrates the technique's practical viability: the decompiler achieves 93% recompilability and successfully passes 7% of the test suite—metrics that suggest meaningful progress on a notoriously difficult problem.