arXiv CSopen access

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

arXiv:2609.16423v1 [cs.CR] 14 Sep 2026

No Bit Left Behind: Using Brute-Force Lifting to Achieve Fully Static Binary Recompilation and Cross-Compilation of Arbitrary Binary Executables TIANJIAO HUANG, University of California, Irvine, USA PO-AN CHEN, University of California, Irvine, USA NICK BARON, University of California, Irvine, USA MICHAEL FRANZ, University of California, Irvine, USA 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. CCS Concepts: • Software and its engineering → Software maintenance tools; • Security and privacy → Software reverse engineering. Additional Key Words and Phrases: binary recompilation, binary lifting, cross-recompilation, static analysis, reverse engineering

1

Introduction

Much of the world’s software infrastructure runs on legacy binary executables: programs that were often created a long time ago and can no longer be properly maintained. There are many possible reasons why organizations might get stuck with such legacy binaries. A common cause is often a deprecated or broken toolchain, which makes it impossible to regenerate a legacy program even if its source code has survived. Another frequent problem is the absence of proper source code archiving or versioning discipline, leading to situations with multiple alternative surviving source files with unreliable file creation timestamps. It is often unclear which, if any, was used to create the legacy binary, and choosing the wrong one may resurrect subtle bugs that had already been corrected in the existing binary. Being stuck with legacy binaries leads to follow-on problems. For example, a legacy binary may require the use of legacy hardware architectures, creating a secondary “lock-in”. More seriously, legacy software may contain vulnerabilities that cannot easily be mitigated through conventional Authors’ Contact Information: Tianjiao Huang, [email protected], University of California, Irvine, Irvine, California, USA; PoAn Chen, [email protected], University of California, Irvine, Irvine, California, USA; Nick Baron, [email protected], University of California, Irvine, Irvine, California, USA; Michael Franz, [email protected], University of California, Irvine, Irvine, California, USA.

2

Huang et al.

means, and its maintainers have no short-term remedy when one is discovered, even when these vulnerabilities become known to an attacker. Modernizing such legacy binaries is often both costly and slow. It may involve rewriting the original software, possibly using new libraries or even programming languages, adapting it to new compiler toolchains and/or operating systems, and then exhaustively testing that the end result has the same functionality as the superseded legacy binary. No “quick fix” is usually available: if an attacker finds an exploitable vulnerability in the legacy binary, or if the underlying hardware platform goes out of production and can no longer be reliably sourced, it will often take substantial time before any replacement executable is available. For all of these and additional reasons, there has long been an interest in using existing binary code as the input to code modernization, removing the dependency on source code and source-code toolchains. For example, binary rewriting [9, 19, 32, 39, 52] has been used to retrofit mitigations against security vulnerabilities into existing binary executables, binary translation [13, 16, 36, 37] has been used to migrate code from one instruction set architecture (ISA) to another, and binary lifting [1, 2, 17, 18, 38, 40, 53] translates a binary executable directly into a compiler intermediate representation (IR), exposing it to the downstream compiler ecosystem. While previous work has yielded many original and valuable insights and techniques, there has so far been no fully automated system that can reliably convert arbitrary (stripped) binary executables to a modern compiler IR, which would then further enable automatic retrofitting of compiler-inserted vulnerability mitigations or fully automatic cross-compilation to a different processor ISA than the code originated in. This paper presents MirrorBall, a static binary recompiler whose central technique is superset disassembly: rather than classifying each byte as code or data, it treats every byte offset in an executable segment as a potentially valid instruction start and constructs a superset control-flow graph (CFG) that encodes every such interpretation simultaneously. The resulting CFG is an over-approximation; it contains every path a dynamic execution could take, along with many that no execution ever will. Because every potentially valid interpretation is already represented, the recompiler does not need heuristics for the two undecidable decisions at the heart of static disassembly: code-vs-data classification and indirect target identification. The absence of heuristics in the superset CFG construction allows the use of heuristics in the optimization stages of the pipeline while still guaranteeing the correctness of the final recompiled binary. Brute-force disassembly alone is not new. Prior work has used superset-style techniques for binary rewriting [7], where the goal is to produce an instrumented binary that still executes on the same ISA as the original. The contribution of this work is not the disassembly technique in isolation, but its use within a whole-program lifting pipeline that produces a fully static, standalone output artifact in LLVM IR that can be fed to unmodified LLVM backends and middle-end passes. The costs of this approach are substantial, and this paper characterizes them rather than obscures them. The whole-program emulation and the superset construction produce large code-size expansion, and lifted binaries run several times slower than their native counterparts for same-ISA recompilation, with further slowdown for cross-ISA. Among our key contributions are the following: • We present MirrorBall1 , the first static binary recompiler that doesn’t rely on heuristics to make determinations about control flow and code-vs-data. It allows the recompiled binary to execute correctly without runtime translation support. 1 A mirrorball is a sphere fragmented into thousands of small mirrors, each reflecting light from a different angle. Similarly,

MirrorBall disassembles a binary at every byte offset, producing a superset CFG that captures every possible control flow path.

No Bit Left Behind

3

• We demonstrate the practicality of our approach with a fully static x86-64-to-AArch64 cross-compilation system: lifted IR is handed directly to the unmodified LLVM AArch64 backend to produce a self-contained AArch64 executable, with no runtime translation support required on the target. • We provide a thorough characterization of the code-expansion and performance slowdown that our brute-force method costs, and argue from this data that these costs are large enough to make brute-force lifting, in its current form, an unlikely candidate for practical deployment. We report this as a deliberate negative result: it quantifies what a maximally conservative, heuristics-free static lifter costs in practice, giving the field a concrete reference point against which future, less conservative designs can be measured. 2 2.1

Background Binary Recompilation

A binary recompiler translates (lifts) an executable into a compiler intermediate representation (IR), optionally applies modifications to the IR, and lowers it back to a new executable that is functionally equivalent to the original [1, 22, 24, 30, 31, 33, 38, 53]. That is, on every input that the original executable accepts, the two must produce the same output. Binary recompilation is distinct from binary rewriting, which applies the modifications directly to the binary [6, 7, 10, 12, 20, 25, 32, 44], and from dynamic binary translation, which translates the machine instructions to a different architecture at runtime [8, 22, 35]. 2.2

Binary Disassembly and Control-Flow Graph Reconstruction

Modifying a binary executable requires relocating symbols to maintain the correct references throughout the modified binary. However, much of the relocation information is lost in the compilation process. A recompiler must find all the basic blocks to lift all the necessary binary code to IR. In order to do this, a recompiler reconstructs the control-flow graph (CFG) from the disassembled code. For every byte in the binary, a recompiler must decide whether it is part of an instruction and, if so, what the basic block’s control-flow successors are. The aggregate of these decisions over all bytes in the binary forms the CFG. An omitted edge causes the modified binary to run correctly until control reaches that edge, at which point it fails. On variable-length ISAs like x86-64, instruction boundaries are not self-evident: the same bytes decode to different instruction sequences depending on the starting offset. Indirect control-flow transfers make this more difficult because their targets might not be able to be determined statically. Compilers typically generate indirect control-flow transfers for C++ virtual dispatch, callbacks, jump tables for switch statements, and pointer mangling in glibc to protect long-lived code pointers (e.g., longjmp). Complete binary disassembly and full control-flow graph reconstruction are undecidable in general [21, 28, 42, 50]. Current practical recompilers address this in a few ways. Static disassembly with heuristics infers indirect targets from compiler-specific patterns that are toolchain- and versiondependent [18, 23, 38, 45, 51]. To fill in the remaining gaps, dynamic disassembly [1, 17] runs the program on given inputs to observe its actual control flow. The coverage of dynamic disassembly is bounded by the inputs used. When all of the above approaches are insufficient, to ensure correctness of the modified binary when an omitted edge is encountered, systems will employ a runtime fallback to handle missing control-flow edges, requiring that the binary modification system be shipped along with the modified binary.

4

2.3

Huang et al.

Superset Disassembly

To solve the problem of undecidability in binary disassembly and control-flow graph reconstruction, the text section is disassembled at every byte offset, producing a superset disassembly [7] of the real instruction stream. From this, we construct a superset CFG whose nodes are every basic block in the superset disassembly, with over-approximations for indirect control-flow edges that treats every possible control-flow destination as a valid successor. The true CFG is a subset of the superset CFG, and the rest is translated dead code that the program never reaches. The cost is size: a superset CFG contains many basic blocks and edges that the program never visits. The benefit is that the recompiler no longer needs heuristics for the two decisions that are undecidable in general: classifying a byte as code or data, and resolving the target of an indirect control-flow transfer. In our system, every offset is decoded, and every indirect branch becomes a table lookup over the full superset CFG, so no branch target is ever guessed and no candidate block is ever dropped on suspicion of being data. Later stages of the pipeline do consult imprecise or incomplete information, for example, ELF symbols to recover multi-block functions (Section 6.3), but this information never decides whether a control-flow edge exists. It only selects which of several already-correct implementations of that edge is used. A wrong guess can make the recovered IR larger or a call site slower; it cannot remove a feasible edge from the CFG or admit a path the original program could not take. Sections 5 and 6 identify each place this information is used and state what happens when it is wrong or absent. The engineering challenge of managing the size of the superset CFG and keeping the translated program’s performance within reason occupies much of the later sections. MirrorBall is the first system to extend superset disassembly to a complete, fully static recompilation pipeline that produces standard LLVM IR usable by unmodified backends. 2.4

LLVM IR as a Lifting Target

LLVM [29] is an open-source, modular, and reusable compiler infrastructure, built around LLVM IR, a Single Static Assignment (SSA) IR, to allow different frontends and backends to work with the same intermediate representation. Lifting to the LLVM IR instead of to a custom IR gives the recompiled program access to dozens of unmodified backends and the mid-level analysis and optimization passes, and is not uncommon to use as an IR for binary lifting [22, 30, 45, 53]. This choice has consequences for the rest of the system, LLVM IR was designed for frontends with access to source code; producing it from a binary requires encoding low-level machine state in a form the IR can represent. One machine instruction may have multiple effects on the program’s state, and these effects must be captured in the IR. The registers are written to and read from multiple times in each instruction, and modeling them inefficiently can lead to high overhead in the generated code. The following sections discuss our solution to these challenges. 3

Design Overview

MirrorBall is a fully static recompilation pipeline that lifts an executable binary into LLVM IR using brute-force lifting and then reconstructs a recompilable program from that IR. Since static analysis cannot determine which bytes of a binary are code, and since indirect control flow cannot be solved statically, we adopt a superset disassembly approach. Every byte offset in the executable sections is treated as a potential instruction boundary, and all control-flow transfers in these candidate instructions are incorporated into an over-approximated CFG. The recompilable IR is further optimized and instrumented before being compiled into a functionally equivalent binary. As presented in Figure 1, our recompilation pipeline consists of the following stages:

No Bit Left Behind

5

Fig. 1. High-level architecture: After brute-force lifting to LLVM IR, we lower back either to an x86-64 binary or to a cross-compiled AArch64 binary. In the output binary, each lifted basic block becomes a function named after its offset in the input binary (e.g., recompiled_440000 for the block at offset 0x440000); the input binary itself is embedded verbatim as a read-only data blob, labeled .original.binary, so that data references into it (Section 7) resolve correctly.

(1) Brute-Force Lifting: The executable sections of the input binary are disassembled at every byte offset. Each offset with a valid instruction is treated as the start of a basic block, which is lifted to LLVM IR. At this stage, each basic block is a function in its own right, with no direct control flow entering or exiting. (Section 4) (2) Static Analysis: This stage parses the ELF file to recover the superset CFG, the dynamically linked functions, and other runtime bootstrapping information. (Section 5) (3) Augmentation: Taking the results from the previous stages, this stage augments the LLVM IR with additional information and optimizations to allow it to be consumed by unmodified backends. (Section 6) (4) Compilation and Linking: The final IR is compiled and linked against the input binary to produce a functionally equivalent executable. (Section 7) 4

Brute-Force Lifting

The first stage of MirrorBall produces LLVM IR for the input binary’s executable code, before any control flow between blocks has been reconstructed. Because the precise basic blocks of a binary cannot be determined statically [7], we do not commit to a single decoded view of the program. Instead, we start decoding at every byte offset of every executable section, and treat every offset that begins a valid instruction sequence as a potential basic block entry. When decoding a given offset, we continue instruction by instruction until a basic block terminator is reached. A basic block is a sequence of instructions with a single entry point and a single exit point. We treat jmp, call, and ret as terminators. call is a terminator because the callee may

6

Huang et al.

not return to its caller. ret is a terminator and an indirect transfer as the return address stored in the stack may have been modified. If the decoder encounters an invalid opcode or a privileged instruction, the offset is discarded. We lift each surviving candidate block in isolation using a QEMU-based frontend, building on the lifting frontend of the publicly available S2E project [14]. It lifts each individual block into QEMU TCG IR, an IR intended to help the emulator to generate code for different architectures, before lifting it to LLVM IR. Lifting the complex instructions, such as the rep extension and vector instructions, are handled transparently by the QEMU frontend. The result is one LLVM IR function per candidate basic block, with no control flow crossing function boundaries. Architectural state that does not fit LLVM’s SSA model (i.e., the general-purpose registers, the program counter, the EFLAGS register, the SIMD registers) is modeled as global variables, read and written by each lifted function as needed. The lifted stack is held in a separate region of emulated memory, separated from the host’s native stack to hold the register spills from the input program’s execution. We chose QEMU’s instruction semantics over an LLVM-IR lifter such as McSema [38] or Remill [30] for two reasons. First, QEMU’s x86-64 decoder and semantics are exercised continuously by its use as a general-purpose emulator, giving us production-tested coverage of instruction classes, such as the rep family and the vector extensions, that we did not have to validate ourselves. Second, and more directly relevant to this paper’s central claim, McSema and similar LLVM-IR lifters take an externally supplied CFG as input, typically recovered by a disassembler such as IDA Pro; the correctness of the lifted program then inherits whatever code/data and indirect-target heuristics that external tool used to build the CFG. Since removing exactly that dependency is the contribution of this work, adopting such a frontend as-is would have reintroduced the heuristic we set out to eliminate, and repurposing one to consume a superset CFG instead of its own recovered CFG would have been a comparably large undertaking to building the brute-force pipeline described here. This choice is not without cost: the register-as-globals model that QEMU’s frontend leaves us with is, by our own measurement (Section 8.4), the single largest source of the runtime overhead we report, and we do not consider that cost fully settled by this design choice. At the end of this stage the input program is represented as a collection of single-block LLVM IR functions. The collection is valid LLVM IR, but without the control flow information that connects the basic blocks. 5 Static Analysis The second stage parses the brute-force lifted sequence and the input binary’s ELF metadata to recover the information needed to connect the lifted blocks and to handle the program’s interactions with its runtime environment. This stage extracts the necessary information for the later stages to reconstruct a functionally equivalent binary. Superset CFG edges. For each candidate block, we identify its successor from its terminator instruction. Direct branches have one or two constant successors, while indirect ones, including every ret instruction, may target any valid basic block. The resulting graph is the superset CFG: an over-approximation that contains every feasible control-flow edge, along with a much larger number of infeasible ones. The augmentation stage uses this graph to install inter-block control-flow. The infeasible edges contribute compile-time and code size overhead but have no functional impact, because the recompiled binary can only follow edges that the program actually takes. Symbol-based function hints. The ELF symbol table marks the entries of named functions in the input binary. Starting from each symbol that points into the .text section, we walk forward through statically resolvable direct edges by following direct jumps and stopping at any indirect transfer. The blocks reached in this walk are flagged as the likely intra-procedural body of a named

No Bit Left Behind

7

function. Blocks that are not reached, which include most of the superset, remain unflagged. The augmentation stage uses this information to decide which blocks to fold into recovered functions and which to leave as single-block functions (Section 6.3). Dynamically linked function signatures. An ELF binary might rely on external functions residing in libraries that are dynamically linked at runtime. In this paper, we refer to them as external functions or dynamically linked functions. The .dynsym section lists the symbols that the dynamic linker will resolve at runtime. For C++ symbols, the Itanium C++ ABI’s mangling scheme [15] encodes the full function signature, including the parameter list. The mangled symbol _ZNSo5writeEPKcl, for example, decodes to std::ostream::write(char const*, long); counting the implicit this parameter, this is an effective signature of (size_t, size_t, long). C symbols only contain their symbol names and do not encode their parameter lists. For these, we maintain a per-symbol mapping populated from the documentation in their man pages. This mapping is exact information, not a heuristic guess, but it is incomplete by construction: the current prototype covers only the C/C++ library functions called by our evaluation suite. A call whose callee is not covered by this mapping and cannot be resolved through .dynsym mangling is instead marshalled by the generic external-call trampoline described in subsection 6.4; consulting a recovered signature first is purely a performance optimization that avoids that trampoline’s more conservative, and slower, calling sequence. Bootstrapping metadata. The analysis records the ELF entry point, the contents of .init_array and .fini_array, and the addresses that the input binary references through the global offset table. These are needed during compilation and linking (Section 7) to reproduce the C runtime library’s startup and shutdown behavior. 6

Augmentation

After lifting and analysis, the IR is a set of disconnected single-block functions annotated with edge information, function hints, and external signatures. The augmentation stage installs the CFG, recovers functions that are more likely to be executed, and inserts trampolines required at the boundary with dynamically linked libraries. After this stage, the IR is accepted by the unmodified LLVM pipeline. 6.1 Control-Flow Patching Direct branches. For a direct branch, the target offset is a compile-time constant. Since each lifted block resides in its own LLVM function, we emit a call to the lifted function corresponding to that offset. If the offset is invalid, we emit a call to abort instead, which is unreachable in any correct execution and is removed by later optimization passes. Indirect branches and returns. For indirect branches, the target is computed at runtime. Every indirect transfer is routed through the dispatch_indirect function, which takes the indirect target, specified by the value of the emulated program counter, and transfers control to the lifted function corresponding to that offset. Offsets with invalid basic blocks are handled by emitting a call to abort. Offsets that fall in the Procedure Linkage Table are from indirect calls to dynamically linked functions and are routed onward to the external call trampoline (Subsection 6.4) instead. ret instructions are lowered the same way. Because the return address lives in emulated stack memory that the callee may have written to, we cannot lower ret as a native LLVM return; the indirect dispatcher is the only correct lowering. Tail-call optimization. Because returns are lifted as indirect calls rather than as native returns, a lifted function never truly returns to its caller. It instead tail-calls into the block pointed to by

8

Huang et al.

the return address. Without further intervention, this means the native stack grows for the entire lifetime of the lifted program. We avoid this by giving every lifted function a uniform calling convention and marking every call site as musttail. LLVM then lowers these as jumps, and the native stack remains bounded by the deepest non-tail call sequence in the runtime support code. 6.2

Argument for CFG Completeness

The central correctness claim of this paper is that the superset CFG contains every control-flow edge a real execution of the input program can take, for every input, not just the ones exercised by our evaluation suite. This subsection states the argument for that claim explicitly, and its boundary: what it establishes, and what it deliberately leaves as a separate, narrower assumption. Every real instruction-start offset survives lifting. A real execution can only ever fetch an instruction from a byte offset within a mapped executable section (excluding the runtime code generation we exclude by construction, Section 9). Brute-force lifting (Section 4) decodes every byte offset in every executable section, with no code/data classification step that could skip one, so any offset a real execution could ever use as an instruction start is among the offsets we attempt to decode. x86-64 decoding is a deterministic function of the byte sequence and the offset at which decoding begins: the same bytes starting at the same offset always decode to the same instruction, independent of what any other offset in the binary decodes to. If a real execution reaches offset 𝑂 and executes the instruction the hardware decodes there, then our decoder, decoding from that same offset 𝑂, decodes the identical instruction, because it is reading the identical bytes at the identical starting point. The one way a candidate block is discarded is an invalid opcode or a privileged instruction at its start (Section 4); by the determinism argument, this can only happen at 𝑂 if the real hardware would also fault or trap there. Discarding such an offset therefore never discards a path a correct execution could take on any input; at worst, it changes how the failure is observed (an abort in the lifted program rather than the original’s own SIGILL/SIGSEGV delivery or system-call trap), which we note as a narrow deviation in observable behavior that is out of scope of this paper. Every real edge is installed. Given that every real instruction-start offset survives as a lifted block, every control-flow edge a real execution takes must also be preserved. Direct edges are compile-time constants read from the instruction bytes and patched to a call to the corresponding lifted function (Section 6.1); by the same determinism argument, if a real execution takes that edge, the target offset is valid and was lifted, so the patched call is never the abort fallback on that path. Indirect edges, including every ret, are resolved at runtime through dispatch_indirect over the full set of surviving offsets, with no further heuristic filtering of indirect targets (Section 6.1); whatever offset the real execution computes as an indirect target, if it is an offset a real execution could reach, it survived lifting by the preceding argument, and dispatch_indirect finds it. What this argument does not cover. This argument establishes that the superset CFG is complete with respect to control-flow edges internal to the lifted program. It does not, by itself, establish that every mechanism at the boundary of that CFG is correct. We rely on three further, separately stated assumptions: (i) that the QEMU-derived semantics for a decoded instruction faithfully reproduce its architectural effect, which we inherit from QEMU’s maturity as a general-purpose emulator rather than re-derive; (ii) that the external-call marshalling described in Section 6.4 correctly bridges the two ABIs for the call shapes it claims to support, with the composite-return limitation noted there as an explicit, scoped exception; and (iii) the exclusions already stated in Section 4 and the discussion of future work, namely no self-modifying code, no multithreading, and no C++ exception unwinding in the current prototype. We consider (i) and the excluded input classes to be inherited

No Bit Left Behind

9

or scoped limitations rather than gaps in the argument above, and (ii) to be the one place where an incorrect implementation, rather than an incomplete CFG, could still produce a wrong answer. 6.3

Function Recovery

If every basic block remains its own function, the lifted binary suffers three costs simultaneously. Every control flow edge lowers to a call, which is expensive at runtime. Basic blocks that frequently jump between each other may get placed further apart, which adds pressure to the instruction cache and further hinders the performance. LLVM’s function-level passes, such as mem2reg, cannot optimize across basic block boundaries, suppressing most cross-block optimizations. Naive merging is not viable, as a source basic block of 𝑁 bytes yields 𝑁 distinct superset basic blocks, each of which may be entered as function entry point independently. If 𝐾 of the other superset basic blocks are successors, merging each successor into each of its predecessor superset functions would produce on the order of 𝑁 × 𝐾 duplicated blocks per source block, and the cost compounds as recovery proceeds. Without impacting the functional correctness of the lifted program, we opt to use heuristics to assist in recovering functions that start at the addresses that are likely to be function entry points in an actual execution. Although there are many other heuristics available for function recovery [5, 11, 46, 47], our prototype uses only the ELF symbol table information. For each ELF symbol pointing into the .text section, we connect the blocks reachable from that symbol along statically resolvable edges into one LLVM IR function. The resulting IR contains a few large functions, embedded in a much larger collection of single-block functions that cover the rest of the superset. This process is approximate: a symbol-walk may include tail-calls, and indirect targets within a named function are not folded into it. But the approximation does not affect correctness, only performance, every block, recovered or not, remains reachable through dispatch_indirect. 6.4

External Call Boundary

ELF binaries use Procedure Linkage Tables (PLT) to facilitate dynamic linking and resolved dynamically linked symbols. When a program tries to invoke a dynamically linked function, it goes through the PLT, which redirects the call to the actual function at runtime. When control reaches a PLT entry, the lifted program crosses from emulated execution into native execution. On the emulated side architectural state lives in threadlocal variables and on the emulated stack; on the native side, the shared library expects its arguments in the host architecture’s physical registers and on the host’s stack. The augmentation stage inserts marshalling code at every such boundary. The shape of that code depends on the calling conventions of both sides. Our prototype targets Linux on x86-64 and Linux on AArch64, which follow the System V AMD64 ABI [34] and AAPCS64 respectively [4]. The two conventions agree in many places but differ in two ways that affect every external call: x86-64 dedicates six integer argument registers whereas AArch64 dedicates eight, and the two architectures handle composite return values differently. Table 1 summarizes these differences. Calls with known signatures. When a callee’s signature is recorded by the static analysis phase, the marshalling code is straightforward. We read the arguments from the emulated registers and stack according to the input binary’s calling convention, place them in the parameter list, and emit a direct call. The LLVM backend will move the arguments to the native registers and stack according to the host’s calling convention. This is the common case in our evaluation suite, where .dynsym

10

Huang et al.

ABI Features Integer arguments 1-6 Integer arguments 7-8 Integer arguments 9+ Floating-point args. 1-8 Return value Return address Stack alignment

x86-64 rdi, rsi, rdx, rcx, r8, r9 Stack Stack xmm0-xmm7 rax, rdx Stack 16 bytes

AArch64 x0-x5 x6-x7 Stack v0-v7 x0, x1 lr, Stack 16 bytes

Table 1. Overview of x86-64 and AArch64 calling conventions [4, 34].

supplies the signatures of C++ functions through name mangling and our manually transcribed mapping covers C functions invoked by the benchmarks. Calls with unknown signatures. Some calls cannot be marshalled this way. Variadic functions are an example: the number and the type of arguments are determined by a format string or other convention, and might not be known at lifting time. For these, along with any functions with unknown signatures, we route through a generic trampoline: (1) Copy the emulated argument registers to the corresponding native registers. (2) Prepare a new stack containing the spilled arguments and point the native stack pointer to it. (3) Point the emulated stack pointer to the native stack. (4) Call the external function. (5) Restore the stack pointers. (6) Copy the return value from native registers into emulated state. (7) Return to the caller. The trampoline does not know the precise argument count, so it conservatively copies the first six integer registers and the first eight floating registers. There is no consequence in populating argument registers that the callee does not actually read: a callee’s compiled code only ever consumes the registers corresponding to its own parameter list, so values placed in registers beyond that list are simply never loaded. Nor does over-population corrupt the caller’s state, since argument registers are caller-saved (call-clobbered) under both the System V AMD64 ABI and AAPCS64, meaning neither convention requires their contents to survive the call. On the return path, the trampoline copies the callee’s scalar return registers back into emulated state; it does not currently marshal composite (larger-than-register) return values, whose caller-allocated return slot is addressed by a different register on each ABI (rdi on x86-64, x8 on AArch64). This is a gap in the current prototype rather than a consequence of the approach: every C/C++ library function invoked by our evaluation suite returns a scalar, and extending the trampoline to composite returns requires only bookkeeping, not a new mechanism. Argument spilling. When the number of arguments exceeds the available argument registers, both ABIs spill arguments to the caller’s stack in source order. Because x86-64 has two fewer integer argument registers than AArch64, an integer argument in the seventh or eighth position resides on the emulated stack on x86-64 but in register x6 or register x7 on AArch64. The trampoline reads these two slots from the emulated stack and writes them to x6 and x7, keeping the remaining

No Bit Left Behind

11

Fig. 2. Argument spilling: On x86-64 and AArch64, the first six integer arguments use registers. The seventh and eighth spill to stack on x86-64 but remain in a register on AArch64. Beyond the eighth, all remaining integer arguments spill to the stack.

12

Huang et al.

Fig. 3. External Callback Handling: Illustrated steps and handling of replacing callback functions with callback trampolines. All IRs were extensively simplified for readability.

spills on a stack pointed to by the native stack pointer before calling the external function. Figure 2 illustrates this. External stack management. Since the emulated x86-64 environment has two fewer argument registers than the host AArch64 environment, a naive solution to allow the external functions to access the argument passed via the emulated stack is by pointing the native stack pointer to Emulated_RSP + 16. The 16 bytes “popped” by this operation could be one of the following: • Excess arguments spilled onto the emulated stack if the argument registers are exhausted. • Caller’s immutable data that the caller does not expect to be modified across function calls (e.g., callee-saved registers). • Caller’s mutable data that the caller expects to be modified across function calls. For example, the caller might pass a pointer to a buffer on the stack and expect the scanf callee to write into it. If the data is meant to be immutable, the trampoline could restore its value after the external call, or it could keep the modification if the data is meant to be mutable. Implementing this would require complex pointer analysis. Instead, we take a conservative approach by assuming these 16 bytes could be any one of the above. We construct a separate external stack for the duration of each call. Pages from the current pointer up to the next page boundary are copied onto the external stack so that stack arguments remain addressable. Pages below this boundary are mapped as read-only and shared with the emulated stack, so that reads through caller pointers that fall there return the correct values. Pages above are allocated fresh as the callee needs them. After the call, the external stack is set aside and could be reused if similar mapping is needed for another call. 6.4.1 Callbacks. Callbacks are function pointers passed via function parameters and may be invoked by the callee at a later time. Callbacks within the input program are handled by the dispatch_indirect transparently since they are a form of indirect control flow, but callbacks that cross the boundary between the lifted program and the native libraries require special handling.

No Bit Left Behind

13

When a callback is passed from the lifted program to a native library, the pointer is an address in the input program’s code segment, which on the cross-architecture side is a sequence of x86-64 instruction bytes; if the external library calls it directly, the host architecture will attempt to decode x86-64 bytes as AArch64 instructions and fault almost immediately. For function-pointer arguments whose role is recorded in the static analysis phase (e.g., the comparator passed to qsort or std::binary_search), we replace the pointer at the call site with the address of a callback trampoline. The trampoline is a small native function that demarshals arguments from native state into emulated state, calls the lifted function corresponding to the original address, and remarshals the return value back into native state. Since every byte offset in the input program could be a callback target, and we could not statically determine which ones are actually used as callbacks, we conservatively generate a trampoline for every superset basic block. Trampolines are looked up by a generated function callback_trampoline_lookup, which maps the input binary addresses to trampoline addresses. For function-pointer arguments whose role is not recorded, the call site cannot be patched, because we cannot identify which argument holds the function-pointer. Instead, we mark the input binary’s code segment non-executable in the lifted binary. When the external library dereferences an unrecognized pointer into that segment, a SIGSEGV signal is raised; our signal handler then invokes trampoline_lookup on the faulting address and resumes execution at the corresponding trampoline. If the address falls outside the code segment, we can transfer control to the signal handler installed by the input program instead to handle its custom signal handling logic. Figure 3 illustrates this. 6.4.2 setjmp and longjmp. The POSIX functions setjmp and longjmp are special kinds of control flow transfers that allow non-local jumps that bypass the normal call and return sequence. They save and restore native execution context, including the program counter and the registers. In a lifted binary, the relevant context lives partly in emulated state (the threadlocal variables modeling the register file), which a native call to setjmp would not capture. We replace calls to these functions with helpers that save and restore the emulated state as well as the native state. 6.4.3 ABI-Dependent Types. A few types are encoded differently by x86-64 and AArch64 regardless of which side issues the call. The three we have encountered in our evaluation suite are long double, va_list, and struct stat. For each occurrence, the augmentation pass inserts an explicit conversion at the boundary. 7

Compilation and Linking

A typical codebase contains many source files. Each of them is a translation unit that will be translated into an LLVM module. Our pipeline contains a single LLVM module that captures all the superset basic blocks of the input program. To avoid slow compilation and out-of-memory issues, after augmentation, the IR is split into multiple modules before being handed to an unmodified LLVM backend. We target x86-64 for same architecture recompilation and AArch64 for cross-architecture recompilation. The backend produces an object file containing the lifted code, which we then link against a small runtime library and a read-only data segment (labeled .original.binary in Figure 1) containing the input binary. The runtime library holds the dispatcher (dispatch_indirect, callback_trampoline_lookup), the generic external-call trampoline, the SIGSEGV handler, and the helpers for setjmp and longjmp. The input binary is linked in as data, not as code. At no point during execution does the host fetch instructions from the input binary. Rather, it is linked so that read-only data accesses from lifted code remain valid (e.g., string literals, jump tables, vtables, C++ Run-Time Type Information (RTTI)).

14

Huang et al.

Basic Blocks

Benchmark astar bzip2 gcc gobmk h264ref hmmer libquantum mcf omnetpp perlbench sjeng xalancbmk Mean

On-Disk Size (MiB)

Source

Lifted

Factor

Source

Lifted

Factor

684 512 101,676 22,972 12,137 3,480 882 299 21,860 41,902 3,644 31,427

49,642 79,556 3,228,499 784,931 727,091 285,186 41,739 19,556 421,610 1,232,376 142,258 2,182,753

72.6× 155.4× 31.8× 34.2× 59.9× 82.0× 47.3× 65.4× 19.3× 29.4× 39.0× 69.5×

0.31 0.20 9.53 5.81 1.62 0.94 0.14 0.06 3.78 3.04 0.35 49.52

32.10 33.79 503.27 160.70 77.71 54.14 31.66 29.50 112.09 207.28 41.85 459.94

103.6× 169.0× 52.8× 27.7× 48.0× 57.6× 226.1× 491.7× 29.7× 68.2× 119.6× 9.3×

49.6×

73.5×

Table 2. Cost of brute-force lifting: LLVM basic-block count and on-disk size of the source-compiled x86-64 binary versus the x86-64-to-x86-64 recompiled binary produced by MirrorBall.

8

Evaluation

We evaluate MirrorBall in four areas: whether the system lifts and recompiles a standard benchmark suite (completeness), what the brute-force strategy costs in IR size (code expansion), what overhead the resulting binaries incur on the original architecture (runtime overhead), and what the system enables when composed with unmodified LLVM backends and instrumentation passes (applications). 8.1

Methodology

We use the SPECint 2006 suite [49] as our benchmark suite. SPECint 2006 contains 12 legacy C and C++ programs spanning compilers, interpreters, simulators, and compression workloads, and has been the standard correctness and performance corpus for prior binary lifters and rewriters [1, 3, 7, 26, 27, 31, 40]. All inputs are binary executables compiled with gcc 13.3.0. Each SPECint program contains one or more workloads; unless otherwise stated, we report numbers for the first workload of each program. MirrorBall produces LLVM 15 bitcode. We recompile lifted bitcode with the flags -O2 max-devirt-iteration=1 -inline-threshold=100; the lowered optimization level alleviates pressures for some of the LLVM passes that do not scale well with the size expansion. x86-64 measurements use an AMD EPYC 4564P (4.5 GHz base clock, 128 GB DDR5) running Ubuntu 22.04.2. AArch64 measurements use a Neoverse-N1 processor (3.0 GHz base clock, 64 GB DDR4) running Ubuntu 22.04.2. We ran each measurement at least three times with hyperfine [41] and report means. 8.2

Completeness

MirrorBall successfully lifted and recompiled all 12 SPECint 2006 programs. Every recompiled binary executed the full reference workload to completion and produced the output matching the source-compiled reference. The same statement holds for both the same-ISA recompilation (x86-64-to-x86-64) and cross-recompilation (x86-64-to-AArch64) configurations evaluated in the remainder of this section. We make no completeness claim outside the SPECint suite.

No Bit Left Behind

15

Benchmark

Source (s)

Lifted (s)

Slowdown

astar bzip2 gcc gobmk h264ref hmmer libquantum mcf omnetpp perlbench sjeng xalancbmk

67.02 41.66 7.97 23.32 28.09 47.47 100.43 137.26 184.16 68.12 233.61 374.39

195.50 135.46 35.15 86.23 148.83 252.01 514.75 259.08 414.90 329.88 791.66 953.27

2.92× 3.25× 4.41× 3.70× 5.30× 5.31× 5.13× 1.89× 2.25× 4.84× 3.39× 2.55×

Mean

3.74×

Table 3. Same-ISA recompilation runtime: source-compiled x86-64 binary versus the same binary lifted to LLVM IR and lowered back to x86-64 by MirrorBall.

8.3

Code Expansion

Brute-force disassembly decodes at every byte offset rather than attempting to distinguish code from data, and the resulting superset control-flow graph contains every basic block any execution could possibly reach. The cost of this conservatism shows up in the IR. Table 2 reports the LLVM basic-block count and on-disk size of each binary before and after the same-ISA recompilation. The block-count expansion ranges from 19.3× (omnetpp) to 155.4× (bzip2), with a mean of 49.6×. bzip2 is an outlier because the source contains a heavily macro-unrolled loop the compiler turns into a small but dense binary; brute-force decoding inside that region produces many overlapping superset interpretations. The remaining variation across benchmarks tracks properties of the input binary, such as instruction mix, invalid opcode and terminator density, and the proportion of embedded data, rather than any single dominant factor. On-disk size expands by a larger mean of 74×. Three factors contribute: (i) the original binary is embedded in the lifted output as a read-only data segment for data references, contributing a fixed overhead independent of lifting decisions; (ii) the lifted IR inlines aggressively during recompilation, causing short tail-calling wrappers lifted as single control-flow paths and inlined by the optimizer; and (iii) the brute-force expansion itself contributes the block-count factor. The largest size factors appear for the smallest source binaries (mcf, libquantum, and bzip2); the largest source binary (xalancbmk) exhibits the smallest size factor (9.3×). 8.4

Runtime Overhead

We measure runtime overhead by lifting each SPECint binary to LLVM IR and lowering it back to an x86-64 executable using the same backend the source compiler would have used. Table 3 reports the resulting slowdowns. The mean is 3.74×. To understand where the overhead comes from, we instrumented the lifted binaries with runtime counters at three points the lifter itself introduces: indirect-branch dispatches through the dispatch_indirect table, calls into external library code through the calling convention adapter, and callbacks from external code back into lifted code through the known-signature path. Table 4 reports the per-workload totals. The following three observations were made from this data.

16

Huang et al.

Benchmark

Indirect

External

Callbacks

astar bzip2 gcc gobmk h264ref hmmer libquantum mcf omnetpp perlbench sjeng xalancbmk

2,780,359,179 27,304 375,927,871 31,077,622 5,041,322,408 64,691,682 0 0 3,877,621,066 11,705,591,850 21,357,073,580 10,559,526,324

7,577,532 488 5,951,985 78,066,207 10,682,057 143,946,279 52,609,064 470,598 1,683,326,454 334,395,345 25,113 321,784,160

0 0 25,492 0 2,153 0 0 0 0 0 0 0

Table 4. Runtime counts of operations introduced by lifting, collected during one reference-workload run of each round-tripped binary. Indirect: dispatches through the indirect-branch table. External: calls into native library code through the calling-convention adapter. Callbacks: control transfers from external code into lifted code.

Lifter overhead is present even when dispatch and marshalling activity are minimal. Two benchmarks, mcf and libquantum, perform no indirect calls or jumps during execution. Their slowdowns are 1.89× and 5.13× respectively. Neither benchmark’s overhead can be attributed to indirectdispatch cost, and libquantum’s external-call rate (530K/s) is moderate compared to the other benchmarks, so we cannot attribute libquantum’s overhead to the external calls either. We attribute the overhead to MirrorBall’s register-as-threadlocals memory model: architectural registers are lifted as LLVM threadlocal variables, and the unmodified optimization pipeline cannot promote them to SSA values across basic-block boundaries, so most register-to-register data flow is materialized as load and store traffic to the memory the optimizer cannot prove unaliased. The spread between these two benchmarks indicates that the magnitude of this cost varies substantially with binary structure, but the data does not isolate which properties drive it. Callbacks are rare in the benchmark suite. Callbacks from external code into lifted code are nonzero but not stressed by SPECint. They do not contribute significantly to the overall overhead but the correct implementation of handling callbacks still remains important for completeness. Same applies to setjmp/longjmp handling. 8.5

Application: Static x86-64-to-AArch64 Cross-Recompilation

To demonstrate that the lifted IR can be directly consumed by the unmodified LLVM AArch64 backend, we lifted each SPECint 2006 binary from x86-64 to LLVM IR using MirrorBall, then lowered the lifted IR to AArch64 using the same unmodified LLVM AArch64 backend that lowers the source-compiled AArch64 binaries. The resulting AArch64 executable is self-contained: no runtime translation support is required on the host machine. As shown in Table 5, across the nine benchmarks the LLVM AArch64 backend can compile as a single module, the mean slowdown is 6.64×. Three benchmarks (gcc, omnetpp, and xalancbmk) produce large code sections that LLVM struggles to compile as a single module. We thus split those binaries into submodules using llvm::SplitModule and lose optimization opportunities across the split boundaries. Including these three benchmarks raises the mean to 12.33×. The split-module overhead is therefore not a fundamental cost of cross-recompilation but a consequence of a known

No Bit Left Behind

17

Benchmark astar bzip2 gobmk h264ref hmmer libquantum mcf perlbench sjeng

Source (s)

Lifted (s)

Factor

140.91 83.47 52.72 65.67 91.16 275.86 419.89 173.98 478.63

507.85 749.99 819.11 434.69 640.86 1,924.64 1,335.59 538.34 2,256.36

3.60× 8.99× 15.54× 6.62× 7.03× 6.98× 3.18× 3.09× 4.71×

Mean (9 benchmarks) gcc † omnetpp † xalancbmk † Mean (12 benchmarks)

6.64× 21.36 347.22 587.63

764.72 16,462.03 2,971.15

35.80× 47.41× 5.06× 12.33×

Table 5. Cross-recompilation runtime. Source-compiled AArch64 versus x86-64-to-AArch64 cross-recompiled, both run on identical AArch64 hardware. Programs marked † produce lifted IR that LLVM struggles to compile as a single module, so these were compiled as split modules at the cost of optimization.

scaling limitation, addressable by either incremental LLVM improvements, emitting lifted code as multiple modules from the start, or by splitting the modules in a way that preserves more optimization opportunities. omnetpp exhibits the highest cross-recompilation slowdown and also the highest number of external calls. This suggests that external calls contribute significantly to the overhead. The role of external calls is sharper in this configuration than in the same-ISA recompilation, because the extra stack management required to address the mismatch between the different number of argument registers on x86-64 and AArch64 (see Section 6.4). 9

Discussion and Future Work

Positioning. We do not think brute-force lifting, as built here, is the right engineering choice for a production deployment today. Despite our best efforts to improve the performance, the overheads in Sections 8.4 and 8.5 are large. And for cross-ISA migration specifically, they are worse than what mature dynamic binary translators already deliver on hardware that exists now. We present this as the central empirical finding of the paper. Building a fully static, heuristics-free lifter that requires no runtime translation support on the target was, prior to this work, an open question. We show that it is possible, and we measure precisely what it costs to do it this conservatively. Our measurements serve as a reference baseline: a maximally conservative baseline against which a future system that recovers a superset CFG more selectively, for example by narrowing it with a soundly verified static analysis rather than an unsound heuristic, can measure how much of this cost it recovers. Whether such a system would still satisfy the fully static, no-runtime-fallback property we start from here is a right next question for this line of research. Register model. The runtime overhead reported in Section 8.4 is a consequence of the register-asthreadlocal memory model. Addressing this would allow the unmodified LLVM pipeline to promote the register state to SSA values. This represents the single largest performance opportunity for the implementation.

18

Huang et al.

Self-modifying code. MirrorBall does not accept binaries that generate code at runtime. This is a permanent limitation of the approach: self-modifying code is fundamentally incompatible with fully static lifting, since the runtime generated code is not known without executing the program. Supporting it would require shipping the lifting machinery with the recompiled binary, which directly contradicts the fully static claim. Broader input scope. Three further classes of binary input are excluded from the prototype but are possible extensions rather than fundamental limitations. Multithreaded binaries have been handled by prior recompilation systems [17, 43]. C++ exception unwinding requires parsing the .eh_frame section and regenerating equivalent metadata for the lifted IR; prior recompilers [17, 30, 40, 48] have likewise deferred this, but nothing in the brute-force approach prohibits it. Extending the front end to non-x86-64 input ISAs is also engineering rather than research, requiring a new lifting front end and revised calling-convention marshalling at external call boundaries. 10

Conclusion

This paper introduces MirrorBall, a fully static binary lifting system built with brute-force lifting. Rather than deciding which bytes of an x86-64 ELF binary represent code and which represent data, MirrorBall treats every byte offset as a potential instruction boundary and every reachable address as a potential branch target. The resulting superset control flow graph conservatively contains every feasible control-flow path, including paths hidden behind overlapping instruction encodings. Statically unresolvable indirect branches reduce to lookups in a dispatch table over the superset CFG, removing the need for any translation machinery to accompany the lifted program on the target. The output is standard LLVM IR accepted by the unmodified LLVM pipeline. As a result, lifted binaries can be processed by the same retargetable backends, optimization passes, and instrumentation passes that LLVM already provides for source code. We demonstrate this through fully static cross-recompilation of x86-64 binaries to AArch64, achieved by feeding the lifted IR directly to LLVM’s AArch64 backend without modifying any component of the toolchain. The cost, as our evaluation shows, is substantial: the lifting time and runtime overhead inherent to producing and executing a conservative superset CFG, much of which is never reached, range from several-fold to two orders of magnitude depending on the metric (Sections 8.4 and 8.5). These costs are large enough that we do not expect brute-force lifting, in the form presented here, to be the right engineering choice for a production deployment: mature dynamic binary translators already deliver cross-ISA execution at a fraction of the overhead we report, on hardware that exists today. This is the paper’s central empirical finding. MirrorBall shows that a fully static, heuristics-free lifter with no runtime translation support on the target is achievable at all, and quantifies precisely what that guarantee costs. We offer this as a reference point for the field: a maximally conservative baseline against which future systems that relax the brute-force strategy, for instance by narrowing the superset CFG with a soundly verified static analysis rather than an unsound heuristic, can measure how much of this cost they recover. References [1] Anil Altinay, Joseph Nash, Taddeus Kroes, Prabhu Rajasekaran, Dixin Zhou, Adrian Dabrowski, David Gens, Yeoul Na, Stijn Volckaert, Cristiano Giuffrida, Herbert Bos, and Michael Franz. 2020. BinRec: dynamic binary lifting and recompilation. In Proceedings of the Fifteenth European Conference on Computer Systems (Heraklion, Greece) (EuroSys ’20). Association for Computing Machinery, New York, NY, USA, Article 36, 16 pages. doi:10.1145/3342195.3387550 [2] Kapil Anand, Matthew Smithson, Khaled Elwazeer, Aparna Kotha, Jim Gruen, Nathan Giles, and Rajeev Barua. 2013. A compiler-level intermediate representation based binary analysis and rewriting system. In Proceedings of the 8th

No Bit Left Behind

19

ACM European Conference on Computer Systems (Prague, Czech Republic) (EuroSys ’13). Association for Computing Machinery, New York, NY, USA, 295–308. doi:10.1145/2465351.2465380 [3] Mahwish Arif, Sam Ainsworth, and Timothy M. Jones. 2025. Janitizer: Rethinking Binary Tools for Practical and Comprehensive Security. In Proceedings of the 23rd ACM/IEEE International Symposium on Code Generation and Optimization (Las Vegas, NV, USA) (CGO ’25). Association for Computing Machinery, New York, NY, USA, 570–583. doi:10.1145/3696443.3708930 [4] Arm Limited. 2024. Procedure Call Standard for the Arm 64-bit Architecture (AArch64). Technical Report IHI 0055. Arm Limited. https://github.com/ARM-software/abi-aa/releases/download/2024Q3/aapcs64.pdf Document version 2024Q3. [5] Tiffany Bao, Jonathan Burket, Maverick Woo, Rafael Turner, and David Brumley. 2014. BYTEWEIGHT: Learning to Recognize Functions in Binary Code. In 23rd USENIX Security Symposium (USENIX Security 14). USENIX Association, San Diego, CA, 845–860. https://www.usenix.org/conference/usenixsecurity14/technical-sessions/presentation/bao [6] Luca Di Bartolomeo, Hossein Moghaddas, and Mathias Payer. 2023. ARMore: Pushing Love Back Into Binaries. In 32nd USENIX Security Symposium (USENIX Security 23). USENIX Association, Anaheim, CA, 6311–6328. https: //www.usenix.org/conference/usenixsecurity23/presentation/di-bartolomeo [7] Erick Bauman, Zhiqiang Lin, Kevin W Hamlen, et al. 2018. Superset Disassembly: Statically Rewriting x86 Binaries Without Heuristics.. In Symposium on Network and Distributed System Security (NDSS). 15 pages. [8] Fabrice Bellard. 2005. QEMU, a Fast and Portable Dynamic Translator. In 2005 USENIX Annual Technical Conference (USENIX ATC 05). USENIX Association, Anaheim, CA. https://www.usenix.org/conference/2005-usenix-annualtechnical-conference/qemu-fast-and-portable-dynamic-translator [9] Derek Bruening, Timothy Garnett, and Saman Amarasinghe. 2003. An infrastructure for adaptive dynamic optimization. In Proceedings of the International Symposium on Code Generation and Optimization: Feedback-Directed and Runtime Optimization (San Francisco, California, USA) (CGO ’03). IEEE Computer Society, USA, 265–275. https://dl.acm.org/ doi/10.5555/776261.776290 [10] D. Bruening, T. Garnett, and S. Amarasinghe. 2003. An infrastructure for adaptive dynamic optimization. In International Symposium on Code Generation and Optimization, 2003. CGO 2003. 265–275. doi:10.1109/CGO.2003.1191551 [11] Joan Calvet, José M. Fernandez, and Jean-Yves Marion. 2012. Aligot: cryptographic function identification in obfuscated binary programs. In Proceedings of the 2012 ACM Conference on Computer and Communications Security (Raleigh, North Carolina, USA) (CCS ’12). Association for Computing Machinery, New York, NY, USA, 169–182. doi:10.1145/2382196. 2382217 [12] Buddhika Chamith, Bo Joel Svensson, Luke Dalessandro, and Ryan R. Newton. 2017. Instruction punning: lightweight instrumentation for x86-64. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation (Barcelona, Spain) (PLDI 2017). Association for Computing Machinery, New York, NY, USA, 320–332. doi:10.1145/3062341.3062344 [13] Hongyu Chen, James McGowan, and Michael Franz. 2026. Deterministic Fully-Static Whole-Binary Translation without Heuristics. arXiv:2605.08419 [cs.CR] https://arxiv.org/abs/2605.08419 [14] Vitaly Chipounov, Volodymyr Kuznetsov, and George Candea. 2011. S2E: A Platform for in-Vivo Multi-Path Analysis of Software Systems. In International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). [15] CodeSourcery, LLC and Hewlett-Packard and IBM and Intel Corporation and Red Hat Inc. 2016. Itanium C++ ABI. https://itanium-cxx-abi.github.io/cxx-abi/abi.html. [16] Andrew Cunningham. 2025. Apple details the end of Intel Mac Support and a phaseout for Rosetta 2. https: //arstechnica.com/gadgets/2025/06/apple-details-the-end-of-intel-mac-support-and-a-phaseout-for-rosetta-2/ [17] Chinmay Deshpande, Fabian Parzefall, Felicitas Hetzelt, and Michael Franz. 2024. Polynima: Practical Hybrid Recompilation for Multithreaded Binaries. In Proceedings of the Nineteenth European Conference on Computer Systems (Athens, Greece) (EuroSys ’24). Association for Computing Machinery, New York, NY, USA, 1126–1141. doi:10.1145/3627703.3650065 [18] Alessandro Di Federico, Mathias Payer, and Giovanni Agosta. 2017. rev.ng: a unified binary analysis framework to recover CFGs and function boundaries. In Proceedings of the 26th International Conference on Compiler Construction (Austin, TX, USA) (CC 2017). Association for Computing Machinery, New York, NY, USA, 131–141. doi:10.1145/ 3033019.3033028 [19] Sushant Dinesh, Nathan Burow, Dongyan Xu, and Mathias Payer. 2020. RetroWrite: Statically Instrumenting COTS Binaries for Fuzzing and Sanitization. In 2020 IEEE Symposium on Security and Privacy (SP). 1497–1511. doi:10.1109/ SP40000.2020.00009 [20] Gregory J. Duck, Xiang Gao, and Abhik Roychoudhury. 2020. Binary rewriting without control flow recovery. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation (London, UK) (PLDI 2020). Association for Computing Machinery, New York, NY, USA, 151–163. doi:10.1145/3385412.3385972

20

Huang et al.

[21] Daniel Engel, Freek Verbeek, and Binoy Ravindran. 2024. On the Decidability of Disassembling Binaries. In Theoretical Aspects of Software Engineering: 18th International Symposium, TASE 2024, Guiyang, China, July 29 – August 1, 2024, Proceedings (Guiyang, China). Springer-Verlag, Berlin, Heidelberg, 127–145. doi:10.1007/978-3-031-64626-3_8 [22] Alexis Engelke and Martin Schulz. 2020. Instrew: leveraging LLVM for high performance dynamic binary instrumentation. In Proceedings of the 16th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments (Lausanne, Switzerland) (VEE ’20). Association for Computing Machinery, New York, NY, USA, 172–184. doi:10.1145/3381052.3381319 [23] Antonio Flores-Montoya and Eric Schulte. 2020. Datalog Disassembly. In 29th USENIX Security Symposium (USENIX Security 20). USENIX Association, 1075–1092. https://www.usenix.org/conference/usenixsecurity20/presentation/ flores-montoya [24] Niranjan Hasabnis and R. Sekar. 2016. Lifting Assembly to Intermediate Representation: A Novel Approach Leveraging Compilers. SIGARCH Comput. Archit. News 44, 2 (March 2016), 311–324. doi:10.1145/2980024.2872380 [25] Jiatai He, Qinglin Pan, Ruilin Zhao, Ji Qi, Kaiwen Liang, Jiahao Xu, Zhiyuan Li, Yuexiang Wang, Jiageng Yu, and Yanjun Wu. 2026. Chimera: Transparent and High-Performance ISAX Heterogeneous Computing via Binary Rewriting. In Proceedings of the 21st European Conference on Computer Systems (EuroSys ’26). ACM, Edinburgh, Scotland, UK, 1–17. doi:10.1145/3767295.3769323 [26] Hyungseok Kim, Soomin Kim, and Sang Kil Cha. 2025. Towards Sound Reassembly of Modern x86-64 Binaries. In Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 (Rotterdam, Netherlands) (ASPLOS ’25). Association for Computing Machinery, New York, NY, USA, 1317–1333. doi:10.1145/3676641.3716026 [27] Hyungseok Kim, Soomin Kim, Junoh Lee, Kangkook Jee, and Sang Kil Cha. 2023. Reassembly is Hard: A Reflection on Challenges and Strategies. In 32nd USENIX Security Symposium (USENIX Security 23). USENIX Association, Anaheim, CA, 1469–1486. https://www.usenix.org/conference/usenixsecurity23/presentation/kim-hyungseok [28] Sun Hyoung Kim, Dongrui Zeng, Cong Sun, and Gang Tan. 2022. BinPointer: towards precise, sound, and scalable binary-level pointer analysis. In Proceedings of the 31st ACM SIGPLAN International Conference on Compiler Construction (Seoul, South Korea) (CC 2022). Association for Computing Machinery, New York, NY, USA, 169–180. doi:10.1145/ 3497776.3517776 [29] Chris Lattner and Vikram Adve. 2004. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. In International Symposium on Code Generation and Optimization (CGO). [30] Lifting-Bits. [n. d.]. Lifting-bits/remill: Library for lifting machine code to LLVM bitcode. https://github.com/liftingbits/remill [31] Zhibo Liu, Yuanyuan Yuan, Shuai Wang, and Yuyan Bao. 2022. SoK: Demystifying Binary Lifters Through the Lens of Downstream Applications. In IEEE Symposium on Security and Privacy (S&P). [32] Chi-Keung Luk, Robert Cohn, Robert Muth, Harish Patil, Artur Klauser, Geoff Lowney, Steven Wallace, Vijay Janapa Reddi, and Kim Hazelwood. 2005. Pin: building customized program analysis tools with dynamic instrumentation. In Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation (Chicago, IL, USA) (PLDI ’05). Association for Computing Machinery, 190–200. doi:10.1145/1065010.1065034 [33] Yi-Hong Lyu, Ding-Yong Hong, Tai-Yi Wu, Jan-Jan Wu, Wei-Chung Hsu, Pangfeng Liu, and Pen-Chung Yew. 2014. DBILL: an efficient and retargetable dynamic binary instrumentation framework using llvm backend. SIGPLAN Not. 49, 7 (March 2014), 141–152. doi:10.1145/2674025.2576213 [34] Michael Matz, Jan Hubicka, Andreas Jaeger, and Mark Mitchell. 2013. System V Application Binary Interface. [35] Raphaela Mettig, Charles Glass, Andrew Case, and Golden G. Richard. 2023. Assessing the threat of Rosetta 2 on Apple Silicon devices. Forensic Science International: Digital Investigation 46 (2023), 301618. doi:10.1016/j.fsidi.2023.301618 [36] Microsoft. 2024. How emulation works on arm. https://learn.microsoft.com/en-us/windows/arm/apps-on-arm-x86emulation (accessed 2025-08-19). [37] Koh M. Nakagawa. 2021. Project Champollion: Reverse engineering Rosetta 2. https://github.com/FFRI/ ProjectChampollion (accessed 2025-08-19). [38] Trail of Bits. 2016. McSema: Static Binary Translation Framework. https://github.com/trailofbits/mcsema. Accessed: 2025-09-22. [39] Maksim Panchenko, Rafael Auler, Bill Nell, and Guilherme Ottoni. 2019. BOLT: a practical binary optimizer for data centers and beyond. In Proceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization (Washington, DC, USA) (CGO 2019). IEEE Press, 2–14. https://dl.acm.org/doi/10.5555/3314872.3314876 [40] Fabian Parzefall, Chinmay Deshpande, Felicitas Hetzelt, and Michael Franz. 2024. What You Trace is What You Get: Dynamic Stack-Layout Recovery for Binary Recompilation. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 (La Jolla, CA, USA) (ASPLOS ’24). Association for Computing Machinery, New York, NY, USA, 1250–1263. doi:10.1145/3620665.3640371 [41] David Peter. 2023. hyperfine. https://github.com/sharkdp/hyperfine

No Bit Left Behind

21

[42] Soumyakant Priyadarshan, Huan Nguyen, Rohit Chouhan, and R. Sekar. 2023. SAFER: Efficient and Error-Tolerant Binary Instrumentation. In 32nd USENIX Security Symposium (USENIX Security 23). USENIX Association, Anaheim, CA, 1451–1468. https://www.usenix.org/conference/usenixsecurity23/presentation/priyadarshan [43] Rodrigo C. O. Rocha, Dennis Sprokholt, Martin Fink, Redha Gouicem, Tom Spink, Soham Chakraborty, and Pramod Bhatotia. 2022. Lasagne: a static binary translator for weak memory model architectures. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation (San Diego, CA, USA) (PLDI 2022). Association for Computing Machinery, New York, NY, USA, 888–902. doi:10.1145/3519939.3523719 [44] Kevin Scott and Jack Davidson. 2001. Strata: A Software Dynamic Translation Infrastructure. Technical Report. University of Virginia, USA. [45] Bor-Yeh Shen, Jiunn Yeu Chen, Wei-Chung Hsu, and Wuu Yang. 2012. LLBT: an LLVM-based static binary translator. In Proceedings of the 2012 International Conference on Compilers, Architectures and Synthesis for Embedded Systems (Tampere, Finland) (CASES ’12). Association for Computing Machinery, New York, NY, USA, 51–60. doi:10.1145/2380403.2380419 [46] Eui Chul Richard Shin, Dawn Song, and Reza Moazzezi. 2015. Recognizing Functions in Binaries with Neural Networks. In 24th USENIX Security Symposium (USENIX Security 15). USENIX Association, Washington, D.C., 611–626. https://www.usenix.org/conference/usenixsecurity15/technical-sessions/presentation/shin [47] Paria Shirani, Lingyu Wang, and Mourad Debbabi. 2017. BinShape: Scalable and Robust Binary Library Function Identification Using Function Shape. In Detection of Intrusions and Malware, and Vulnerability Assessment, Michalis Polychronakis and Michael Meier (Eds.). Springer International Publishing, Cham, 301–324. [48] Matthew Smithson, Khaled ElWazeer, Kapil Anand, Aparna Kotha, and Rajeev Barua. 2013. Static binary rewriting without supplemental information: Overcoming the tradeoff between coverage and correctness. In 2013 20th Working Conference on Reverse Engineering (WCRE). 52–61. doi:10.1109/WCRE.2013.6671280 [49] Cloyce D. Spradling. 2007. SPEC CPU2006 benchmark tools. SIGARCH Comput. Archit. News 35, 1 (March 2007), 130–134. doi:10.1145/1241601.1241625 [50] Freek Verbeek, Nico Naus, and Binoy Ravindran. 2024. Verifiably Correct Lifting of Position-Independent x86-64 Binaries to Symbolized Assembly. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security (Salt Lake City, UT, USA) (CCS ’24). Association for Computing Machinery, New York, NY, USA, 2786–2798. doi:10.1145/3658644.3690244 [51] Shuai Wang, Pei Wang, and Dinghao Wu. 2015. Reassembleable disassembling. In Proceedings of the 24th USENIX Conference on Security Symposium (Washington, D.C.) (SEC’15). USENIX Association, USA, 627–642. [52] David Williams-King, Hidenori Kobayashi, Kent Williams-King, Graham Patterson, Frank Spano, Yu Jian Wu, Junfeng Yang, and Vasileios P. Kemerlis. 2020. Egalito: Layout-Agnostic Binary Recompilation. In Proceedings of the TwentyFifth International Conference on Architectural Support for Programming Languages and Operating Systems (Lausanne, Switzerland) (ASPLOS ’20). Association for Computing Machinery, New York, NY, USA, 133–147. doi:10.1145/3373376. 3378470 [53] S. Bharadwaj Yadavalli and Aaron Smith. 2019. Raising Binaries to LLVM IR with MCTOLL (WIP Paper). In Proceedings of the 20th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems (Phoenix, AZ, USA) (LCTES 2019). Association for Computing Machinery, New York, NY, USA, 213–218. doi:10.1145/ 3316482.3326354