PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Tianjiao Huang, Po-An Chen, Nick Baron, Michael Franz

arXiv:2609.16423v1cs.CR

TL;DR

No fully automated system reliably lifts arbitrary binaries to modern compiler IR, in part because static CFG reconstruction is undecidable in general. MirrorBall brute-force lifts every byte offset into a conservative superset CFG and produces standalone LLVM IR. It demonstrates static x86-64-to-AArch64 cross-compilation, while reporting substantial costs that make the current approach unlikely to suit production deployment.

  • Problem

    No fully automated system reliably converts arbitrary stripped binaries to modern compiler IR, a capability that could support mitigation retrofits and cross-ISA compilation.

    Source: §1 · p. 2

  • Method

    MirrorBall brute-force lifts every executable byte offset into a superset CFG, avoiding code/data classification and indirect-target heuristics.

    Source: §1 · p. 2

  • Results

    MirrorBall demonstrates fully static x86-64-to-AArch64 cross-compilation through unmodified LLVM, while its measured costs range from several-fold to two orders of magnitude depending on the metric.

    Source: §1 · p. 3, §10 · p. 18

  • Takeaways & Limitations

    The paper establishes that a fully static, heuristics-free lifter without target-side translation support is achievable, while quantifying the costs of this conservative design.

    Source: §10 · p. 18

    The external-call trampoline currently returns scalar values but does not marshal composite return values.

    Source: §6.4 · p. 10

Abstract

from arXiv · show

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.

1 Introduction

Legacy binaries can be difficult to modernize, while no fully automated system reliably lifts arbitrary binaries to modern compiler IR. MirrorBall uses brute-force lifting to produce a static, standalone recompiler, demonstrating cross-ISA compilation while measuring substantial costs.

1 Introduction

  • No fully automated system reliably converts arbitrary stripped binaries to modern compiler IR, limiting the prospect of automatic mitigation retrofits and cross-ISA compilation.Legacy binaries can be costly and slow to replace, especially when source code or usable toolchains are unavailable.Source: §1 · pp. 1–2
  • MirrorBall treats every executable byte offset as a potential instruction start, building a superset CFG that avoids code/data and indirect-target heuristics.The CFG over-approximates feasible paths, including interpretations that no execution reaches.Source: §1 · p. 2
  • The contribution is a whole-program lifting pipeline that outputs standalone LLVM IR for unmodified LLVM backends, not brute-force disassembly alone.Prior superset-style disassembly was used for same-ISA binary rewriting.Source: §1 · p. 2
  • The prototype cross-compiles x86-64 binaries to AArch64 without runtime translation support, but its code expansion and slowdown make current-form deployment unlikely.The paper presents this cost characterization as a deliberate negative result and a reference point for less conservative designs.Source: §1 · pp. 2–3

2 Background

Binary recompilation lifts executables into compiler IR for modification and recompilation, but statically reconstructing their control flow is undecidable in general. Superset disassembly avoids heuristic CFG decisions by representing every candidate path, while LLVM IR offers access to reusable backends and optimization passes.

2.1 Binary Recompilation

  • Binary recompilation lifts an executable into IR, optionally modifies it, and lowers it to a functionally equivalent executable, unlike binary rewriting or runtime translation.The output must match the original on every input the original accepts.Source: §2.1 · p. 3

2.2 Binary Disassembly and Control-Flow Graph Reconstruction

  • CFG recovery must identify instruction bytes and successors, but variable-length decoding and indirect transfers make complete static reconstruction undecidable in general.Existing approaches use heuristics or input-bounded dynamic disassembly, sometimes retaining runtime fallback for omitted edges.Source: §2.2 · p. 3

2.3 Superset Disassembly

  • Superset disassembly decodes every byte offset and over-approximates indirect edges, containing the true CFG at the cost of translating unreachable blocks.This avoids guessing code versus data or indirect targets; imprecise information may affect implementation size or speed, but not which CFG edges exist.Source: §2.3 · p. 4
  • MirrorBall extends superset disassembly into a complete static pipeline producing LLVM IR for unmodified backends, while managing CFG size and runtime performance.LLVM IR also exposes recompiled programs to reusable backends and middle-end passes, but representing machine state in this source-oriented IR can add overhead.Source: §2.3 · p. 4, §2.4 · p. 4

3 Design Overview

MirrorBall lifts an executable into LLVM IR using brute-force decoding, then reconstructs and augments a recompilable program. Compilation and linking produce an executable for either the original ISA or cross-compilation to AArch64.

3 Design Overview

  • MirrorBall treats every executable-section byte offset as a possible instruction boundary and incorporates candidate transfers into an over-approximated CFG.The resulting IR is optimized and instrumented before compilation into a functionally equivalent binary.Source: §3 · p. 4
  • Each lifted basic block becomes an offset-named function, and the original binary is embedded as read-only data in the output.The output can be lowered to x86-64 or cross-compiled to AArch64; embedding supports references into original binary data.Source: Figure 1 · p. 5
  • The pipeline proceeds through brute-force lifting, ELF-based static analysis, IR augmentation, and compilation and linking.Static analysis recovers the superset CFG and runtime bootstrapping information; augmentation prepares IR for unmodified backends.Source: §3 · p. 5

4 Brute-Force Lifting

Brute-force lifting decodes from every executable-section byte offset, lifting each valid candidate block independently. A QEMU-based frontend supplies instruction semantics, while architectural state is represented in LLVM IR through globals and separate emulated memory.

4 Brute-Force Lifting

  • MirrorBall starts decoding at every executable-section byte offset and treats each valid instruction sequence as a potential basic-block entry.Decoding continues to a terminator; invalid opcodes and privileged instructions cause the candidate offset to be discarded.Source: §4 · pp. 5–6
  • Each surviving candidate block is lifted independently through QEMU TCG IR into one LLVM IR function, with architectural state modeled as globals.The emulated stack occupies memory separate from the host stack.Source: §4 · p. 6
  • QEMU provides production-tested x86-64 instruction semantics without relying on an externally recovered CFG, but its register-as-globals model is the largest measured source of runtime overhead.The resulting collection of single-block functions is valid LLVM IR before their control flow is connected.Source: §4 · p. 6

5 Static Analysis

Static analysis combines the brute-force lifted sequence with ELF metadata to recover information needed to reconnect blocks and model runtime interactions. It builds a superset CFG and records function hints, external-call signatures, and startup metadata for later augmentation and linking.

5 Static Analysis

  • The superset CFG connects each candidate block to its statically identified successors, while indirect transfers may target any valid block, including infeasible edges that add compile-time and code-size overhead.The recompiled program follows only edges it actually takes.Source: §5 · p. 6
  • ELF symbols pointing into .text provide function hints: direct-edge walks from named entries mark likely function bodies, while most superset blocks remain unflagged.Augmentation uses the hints to decide which blocks to fold into recovered functions and which to leave as single-block functions.Source: §5 · pp. 6–7
  • The analysis records dynamically linked function signatures from C++ symbol mangling or a per-symbol C mapping; uncovered calls use the generic external-call trampoline.The C mapping covers only library functions called by the evaluation suite; recovered signatures avoid the trampoline's more conservative, slower sequence.Source: §5 · p. 7
  • ELF entry-point, .init_array, .fini_array, and global-offset-table metadata supports reproducing C runtime startup and shutdown during compilation and linking.The analysis stage combines the lifted sequence with ELF metadata to gather information needed by later stages.Source: §5 · pp. 6–7

6 Augmentation

Augmentation installs control flow, recovers likely functions, and adds code to bridge calls between emulated execution and native libraries. Its CFG-completeness argument is scoped to internal edges; boundary behavior depends on separately stated assumptions and limitations.

6 Augmentation

  • The augmentation stage installs the CFG, recovers likely executed functions, and inserts trampolines at dynamically linked library boundaries before passing IR to the unmodified LLVM pipeline.After lifting and analysis, IR consists of disconnected single-block functions annotated with edge information, function hints, and external signatures.Source: §6 · p. 7

6.1 Control-Flow Patching

  • Direct branches call the lifted function at their constant target, while indirect branches and returns use dispatch_indirect to select a lifted block from the runtime target offset.Returns must be dispatched because the return address resides in emulated stack memory that the callee may have modified; musttail calls keep the native stack bounded.Source: §6.1 · pp. 7–8

6.2 Argument for CFG Completeness

  • The CFG-completeness argument says every real internal edge is preserved: every executable-section byte offset is decoded, and direct and indirect targets are installed without heuristic filtering.Its scope excludes boundary correctness, which relies on QEMU instruction semantics, ABI marshalling, and stated exclusions including self-modifying code, multithreading, and C++ exception unwinding.Source: §6.2 · p. 8

6.3 Function Recovery

  • Symbol-based recovery groups blocks reachable from named ELF symbols along direct edges, while leaving the rest as single-block functions; this approximation affects performance, not correctness.Naive merging would duplicate blocks as candidate entry points and successors are combined, compounding as recovery proceeds.Source: §6.3 · p. 9

6.4 External Call Boundary

  • External-call marshalling bridges emulated state to host registers and stack; known signatures permit direct calls, while unknown signatures use a generic trampoline that copies argument registers and restores state after the call.The generic trampoline copies the first six integer and eight floating registers; it currently does not marshal composite returns, though evaluation-suite library calls return scalars.Source: §6.4 · pp. 9–10
  • For x86-64-to-AArch64 calls, integer arguments seven and eight move from the emulated stack into AArch64 registers x6 and x7; remaining spilled arguments stay on a native-stack-backed external stack.The external stack preserves access to spilled arguments while accommodating caller data that may be immutable or mutable, without requiring complex pointer analysis.Source: §6.4 · pp. 10, 12, Figure 2 · p. 11

6.4.1 Callbacks.

  • Cross-boundary callbacks use native trampolines that marshal arguments into emulated state and return values back; unknown callback pointers are resolved through a SIGSEGV-triggered lookup.Because any byte offset could be a callback target, a trampoline is generated for every superset basic block.Source: §6.4.1 · p. 13

6.4.3 ABI-Dependent Types.

  • The augmentation pass inserts explicit conversions for long double, va_list, and struct stat because x86-64 and AArch64 encode these types differently..Source: §6.4.3 · p. 13

7 Compilation and Linking

Compilation splits the augmented IR into modules and sends them to unmodified LLVM backends to produce linked executables. The input binary is included as read-only data, not executable code.

7 Compilation and Linking

  • After augmentation, the pipeline splits the single LLVM module into multiple modules to avoid slow compilation and out-of-memory issues, then uses an unmodified LLVM backend and links the object with a small runtime library.The backend targets x86-64 for same-ISA recompilation or AArch64 for cross-architecture recompilation.Source: §7 · p. 13
  • The input binary is linked as read-only data rather than code, preserving data accesses such as string literals, jump tables, vtables, and RTTI.The host never fetches instructions from the original binary during execution.Source: §7 · p. 13
  • Table 2 compares source-compiled x86-64 binaries with MirrorBall's x86-64 recompilations by LLVM basic-block count and on-disk size.The supplied passage identifies the comparison dimensions but provides no cell values.Source: Table 2 · p. 14

8 Evaluation

MirrorBall is evaluated for completeness, code expansion, runtime overhead, and static cross-recompilation. It completes the SPECint 2006 workloads, with substantial code-size expansion and slowdowns reported for both same-ISA and cross-ISA recompilation.

8 Evaluation

  • Evaluation covers completeness, code expansion, runtime overhead, and LLVM-backed applications, using 12 SPECint 2006 C and C++ programs and repeated measurements.Unless otherwise stated, measurements use each program’s first workload; each measurement was run at least three times and reported as a mean.Source: §8 · p. 14, §8.1 · p. 14

8.2 Completeness

  • MirrorBall lifted and recompiled all 12 SPECint 2006 programs, and each completed the reference workload with output matching the source-compiled reference in both ISA configurations.The authors make no completeness claim beyond SPECint 2006.Source: §8.2 · p. 14

8.4 Runtime Overhead

  • 3.74× is the mean same-ISA runtime slowdown; Table 3 compares source-compiled x86-64 binaries with MirrorBall round-trips.The overhead can persist even with minimal dispatch and marshalling: mcf and libquantum slow down by 1.89× and 5.13×, respectively, with register-as-threadlocals traffic identified as a source.Source: Table 3 · p. 15, §8.4 · pp. 15–16

8.3 Code Expansion

  • The block-count expansion averages 49.6×, ranging from 19.3× for omnetpp to 155.4× for bzip2; on-disk size expands by a mean of 74×.The bzip2 outlier reflects overlapping interpretations in a dense binary region; on-disk expansion also includes the embedded original binary and optimizer inlining.Source: §8.3 · p. 15

8.4 Runtime Overhead

  • Callbacks were rare and not stressed by SPECint; they contributed little to overall overhead, though correct callback and setjmp/longjmp handling remains important for completeness.Table 4 counts indirect dispatches, external calls, and callbacks during one reference-workload run per round-tripped binary.Source: §8.4 · p. 16, Table 4 · p. 16

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

  • 6.64× mean slowdown across nine benchmarks compiled as one module, rising to 12.33× when three LLVM-challenging programs are split into submodules.Splitting sacrifices optimization opportunities across module boundaries; the paper identifies this overhead as a known LLVM scaling limitation, not a fundamental cross-recompilation cost.Source: §8.5 · pp. 16–17, Table 5 · p. 17

9 Discussion and Future Work

The discussion finds brute-force lifting too costly for production today, while identifying a register-model performance opportunity and input-scope boundaries. Self-modifying code remains fundamentally incompatible with fully static lifting.

9 Discussion and Future Work

  • Overheads make brute-force lifting an unlikely production choice today, especially for cross-ISA migration, where mature dynamic translators perform better on existing hardware.The authors offer the measurements as a reference baseline for future systems that narrow the superset CFG with sound static analysis.Source: §9 · p. 17
  • The register-as-threadlocal memory model causes reported runtime overhead; addressing it could enable LLVM to promote register state to SSA values.The authors identify this as the implementation’s single largest performance opportunity.Source: §9 · p. 17
  • Self-modifying code is a permanent limitation because runtime-generated code is unknown without execution, and supporting it would require target-side lifting machinery.That machinery would contradict the fully static claim.Source: §9 · p. 18
  • The prototype excludes multithreaded binaries, C++ exception unwinding, and non-x86-64 inputs, but the authors describe these as possible extensions rather than fundamental limits.The extensions respectively involve prior system approaches, .eh_frame parsing and metadata regeneration, or a new lifting front end and revised calling-convention marshalling.Source: §9 · p. 18

10 Conclusion

MirrorBall demonstrates fully static binary recompilation by brute-force construction of a superset CFG, with indirect branches handled through dispatch-table lookups. Its LLVM IR output supports unmodified backends, including static x86-64-to-AArch64 cross-compilation, but incurs substantial costs.

10 Conclusion

  • MirrorBall treats every byte offset as a potential instruction boundary, building a superset CFG whose dispatch table handles statically unresolvable indirect branches without target-side translation machinery.The graph conservatively includes feasible control-flow paths, including those hidden by overlapping instruction encodings.Source: §10 · p. 18
  • Standard LLVM IR can pass through the unmodified LLVM pipeline, demonstrated by fully static x86-64-to-AArch64 cross-recompilation using the existing AArch64 backend.LLVM’s existing backends, optimization passes, and instrumentation passes can also process the lifted IR.Source: §10 · p. 18
  • Lifting time and runtime overhead range from several-fold to two orders of magnitude, depending on the metric, making the presented approach an unlikely production choice.The authors offer these measurements as a maximally conservative baseline for future systems that narrow the superset CFG soundly.Source: §10 · p. 18
Loading 2609.16423v1…