No Bit Left Behind: Using Brute-Force Lifting to Achieve Fully Static Binary Recompilation
Prototype binary lifter brute-force lifts every byte offset of x86-64 binaries to LLVM IR, enabling fully static cross-ISA recompilation without runtime support.
The paper presents a fully static, whole-program binary lifting system that treats every byte offset as a potential branch target, constructing a superset control flow graph that conservatively contains all feasible control flows. Statically unresolvable computed branches are reduced to lookups in a dispatch table pointing to translated control flow paths, eliminating runtime translation machinery on the target machine. A prototype recompiles x86-64 binaries to LLVM IR with no code/data heuristics and achieves fully static cross-compilation to AArch64 using unmodified LLVM backends.
- Brute-force lifting treats every byte offset as potential branch target
- Superset CFG conservatively contains all feasible control flows
- No runtime translation support needed on target machine
- Prototype lifts x86-64 to LLVM IR; static AArch64 cross-compilation validated
Full article248 words · extracted from arxiv.org · click to collapse
Binary recompilation is a technique for operating directly on executable code. It promises to automate two important tasks: retrofitting security mitigations onto legacy binaries, and migrating binaries across instruction set architectures (ISAs). Yet today, there is no fully automated system that can reliably lift arbitrary binary executables to a compiler intermediate representation (IR) such as LLVM IR, or that can fully statically and reliably translate non-trivial binary executables from one ISA to another. The main underlying problem is that recovering a program's control flow graph (CFG) statically is impossible in general: computed branches can jump to targets that cannot be determined without actually running the program. Existing systems resort to runtime fallback mechanisms, requiring a significant portion of the binary translation machinery to accompany the translated program on the target machine. This article presents a fully static, whole-program binary lifting system requiring no runtime translation support on the target. Rather than attempting to distinguish code from data, we treat every byte offset as a potential branch target and lift the entire binary in a brute-force manner, constructing a superset CFG that conservatively contains all feasible control flows. Statically unresolvable computed branches are thereby reduced to lookups in a dispatch table that points to the corresponding translated control flow path. We have implemented this approach as a prototype binary recompiler from x86-64 binaries to LLVM IR, requiring no code/data heuristics. We validate it with a fully static cross-compilation to AArch64, achieved by reusing existing LLVM backends with no modification.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.16423