Binary rewriting without control flow recovery

Static binary rewriting has numerous applications in software security and systems-such as hardening, repair, patching, instrumentation and debugging. As such, many different static binary rewriting tools have been proposed over the decades. Since binary rewriting can insert/delete/move instructions, most existing tools attempt to recover control flow information from the input binary, and then use this information to adjust the set of jump targets in the rewritten binary. Given that the static recovery of control flow information is a hard problem in general, most existing tools use heuristics or simplifying assumptions about the input binary, such as specific compilers, source languages, etc. However, the reliance on assumptions is known to be fragile and tends not to scale in practice. For example, most existing tools cannot handle very large/complex programs such as web browsers.

In this paper we present E9Patch, a tool that can statically rewrite x86_64 binaries without any knowledge of control flow information. To do so, E9Patch develops a suite of binary rewriting methodologies, such as instruction punning and eviction, that can insert jumps to trampolines without the need to move other instructions. This preserves the set of jump targets and eliminates the need for control flow recovery and related heuristics. As such, E9Patch is robust by design, and can scale to very large (>100MB) stripped binaries including web browsers such as Google Chrome and FireFox. We also evaluate the effectiveness of E9Patch against realistic applications such as binary instrumentation, hardening and patching.