E9Patch – A Powerful Static Binary Rewriter

E9Patch is a powerful static binary rewriting tool for x86_64 Linux ELF binaries. E9Patch is:

• Scalable: E9Patch can reliably rewrite large/complex binaries including web browsers (>100MB in size).
• Compatible: The rewritten binary is a drop-in replacement of the original, with no additional dependencies.
• Fast: E9Patch can rewrite most binaries in a few seconds.
• Low Overheads: Both performance and memory.
• Programmable: E9Patch is designed so that it can be easily integrated into other projects. See the E9Patch Programmer’s Guide for more information.

Background

Static binary rewriting takes as input a binary file (ELF executable or shared object, e.g. a.out) and outputs a new binary file (e.g., b.out) with some patch/modification applied to it. The patched b.out can then be used as a drop-in replacement of the original a.out. Typical binary rewriting applications include instrumentation (the addition of new instructions) or patching (replacing binary code with a new version).

Static binary rewriting is notoriously difficult. One problem is that space for the new instructions must be allocated, and this typically means that existing instructions will need to be moved in order to make room. However, some of these existing instructions may also be jump targets, meaning that the all jump/call instructions in the original binary will also need to be adjusted in the rewritten binary. Unfortunately, things get complicated very quickly:

• The complete set of targets cannot be determined statically (it is an undecidable problem in the general case of indirect calls or jumps).
• Cross-binary calls/jumps are not uncommon, for example the compare function pointer argument to libc’s qsort(). Since code pointers cannot be reliably distinguished from other data in the general case, this can mean that the entire shared library dependency tree also needs to be rewritten.

Unless all jumps and calls are perfectly adjusted, the rewritten binary will likely crash or otherwise misbehave. This is why existing static binary rewriting tools tend to scale poorly.

How E9Patch is Different

E9Patch is different to other tools in that it can statically rewrite x86_64 Linux ELF binaries without modifying the set of jump targets. To do so, E9Patch uses a set of novel low-level binary rewriting techniques, such as instruction punning, padding, and eviction that can insert or replace binary code without the need to move existing instructions. Since existing instructions are not moved, the set of jump targets remains unchanged, meaning that calls/jumps do not need to be corrected (including cross binary calls/jumps).

E9Patch is therefore highly scalable by design, and can reliably rewrite very large binaries such as Google Chrome and Firefox (>100MB in size).

To find out more on how E9Patch works, please see our PLDI’2020 paper:

• Gregory J. Duck, Xiang Gao, Abhik Roychoudhury, Binary Rewriting without Control Flow Recovery, Programming Language Design and Implementation (PLDI), 2020. PLDI’2020 Presentation

Install & Use

Copyright (C) 2020 GJDuck