AwesomeREA.org

2020 · Conference paper

Binary Rewriting without Control Flow Recovery

Gregory J. Duck; Xiang Gao; Abhik Roychoudhury

E9Patch statically rewrites x86-64 binaries by inserting jumps to trampolines without moving any other instruction, so the original set of jump targets is preserved and control-flow recovery, symbolization and debug information are not needed. Where a five-byte jump does not fit, instruction punning, padding and successor or neighbor eviction overlap the jump with existing bytes or relocate neighboring instructions into their own trampolines; physical page grouping reduces the memory and file-size cost of scattered trampolines. Instruction locations come from a separate frontend, a basic linear disassembler in the evaluation. The authors evaluate SPEC2006, Ubuntu 16.04 system binaries, and Chrome and Firefox builds over 100 MB, and demonstrate binary repair and heap-write hardening with low fat pointers.

Scope and limitations

This is static binary rewriting and instrumentation, not decompilation or source recovery. It relies on the frontend’s instruction locations and sizes being correct, assumes patched code is not read as data or self-modified, and assumes the input does not already use overlapping instructions. Each tactic can fail: 1,098 of about 10.5 million patch locations were not patched, baseline coverage alone was 72.79% for jumps and 81.63% for heap writes, and non-PIE binaries are harder than PIE ones. Chrome’s mixed code and data required starting disassembly after ChromeMain, and Firefox’s code was patched in libxul.so. Reported overheads, such as about 113% for Chrome and 46% for Firefox on Dromaeo DOM benchmarks with heap-write instrumentation, were measured with the PLDI prototype, with SPEC2006 compiled by GCC in non-PIE mode; they do not describe the current release.

Why it fits this collection

Adds a control-flow-agnostic static rewriting technique for stripped x86-64 binaries, a foundation for patching and instrumenting binaries whose structure has not been recovered, complementing the section’s lifting and decompilation research.

Publication and review details

Venue
PLDI 2020
Status
Conference paper
Publication / posting date
June 11, 2020
Date source
ACM’s Crossref deposit records print and online publication on 2020-06-11, and an archived copy of the ACM article page shows the same date. The June 15–20 PLDI dates printed in the paper are not substituted.
DOI
10.1145/3385412.3385972

Crossref and the archived ACM page give the three authors, the PLDI 2020 proceedings and pages 151–163; ACM metadata uses sentence case and the record follows the paper’s title capitalization. The PDF is the 13-page author’s version on Gregory J. Duck’s NUS page, linked from the repository README, and the ACM page holds the version of record. The reviewed 2026-06-28 repository commit describes x86_64 Linux ELF executables and shared objects, GPL-3.0 with some MIT-licensed files, and states that the current version is significantly improved over the prototype evaluated in the PLDI paper, with new optimizations, improved physical page grouping and slightly higher coverage. No code or experiments were run.

Sources reviewed

Source review only; experiments were not rerun for this collection. Cite the original authors using the linked paper or BibTeX.

Report an outdated entry Suggest a translation fix

Related entries

Matched by the same code repository or publication identifier.

Primary sources

  1. https://dl.acm.org/doi/10.1145/3385412.3385972
  2. https://web.archive.org/web/20251215175156/https://dl.acm.org/doi/10.1145/3385412.3385972
  3. https://api.crossref.org/works/10.1145/3385412.3385972
  4. https://comp.nus.edu.sg/~gregory/papers/e9patch.pdf
  5. README.md GitHub · GJDuck/e9patch · Revision 682ab1f
  6. LICENSE GitHub · GJDuck/e9patch · Revision 682ab1f