Structured Binary Editing with a CFG Transformation Algebra

Binary modification allows users to alter existing code or inject new code into programs without requiring source code, symbols, or debugging information. It is critically important that such modification not accidentally create a structurally invalid binary that has illegal control flow or executes invalid instructions. Unfortunately, current modification tools do not make this guarantee, instead relying on the user to manually ensure the modified binary is valid. In addition, they fail to provide high-level abstractions of the binary (e.g., functions), instead requiring the user to have a deep understanding of the idiosyncrasies of the instruction set and the behavior of the program. We present structured binary editing, which allows users to modify a program binary by modifying its control flow graph (CFG). We define an algebra of CFG transformations that is closed under a CFG validity constraint, thus ensuring that users can arbitrarily compose these transformations while preserving structural validity. We have implemented structured binary editing in the Dyninst binary analysis and instrumentation framework, creating a high-level binary modification toolkit. We demonstrate the usefulness of our approach by creating a hot patching tool that closes three vulnerabilities in a running, unmodified Apache HTTPD server without interrupting the server´s execution.