No Bit Left Behind: Using Brute-Force Lifting to Achieve Fully Static Binary Recompilation

Binary recompilation is a technique for operating directly on executable code, promising to automate retrofitting security mitigations onto legacy binaries and migrating binaries across instruction set architectures (ISAs). However, no fully automated system exists that can reliably lift arbitrary binary executables to a compiler intermediate representation (IR) such as LLVM IR, or fully statically and reliably translate non-trivial binaries from one ISA to another. The core 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, the authors 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.

The proposed approach is a fully static binary lifting system that avoids runtime translation support. The key insight is to treat every byte offset in the binary as a potential branch target, rather than attempting to distinguish code from data. This brute-force lifting constructs a superset control flow graph (CFG) that conservatively contains all feasible control flows. For statically unresolvable computed branches, the system reduces them to lookups in a dispatch table that points to the corresponding translated control flow path. The authors implemented a prototype binary recompiler from x86-64 binaries to LLVM IR, requiring no code/data heuristics. The lifting process can be formalized as follows: for a binary $B$ with byte offsets $O=\{0,1,\dots ,|B|-1\}$, the superset CFG $G=(V,E)$ is constructed where $V\subseteq O$ represents potential instruction start addresses, and $E$ represents possible control flow edges. Each byte offset $o\in O$ is considered a potential branch target, and the lifting function

translates the bytes starting at $o$ into LLVM IR instructions. The dispatch table maps each offset to its corresponding translated code block. The overall architecture is illustrated in the following Mermaid diagram: