Native x86 Decompilation using Semantics-Preserving Structural Analysis and Iterative Control-Flow Structuring

There are many security tools and techniques for finding bugs, but many of them assume access to source code. We propose leveraging decompilation, the study of recovering abstractions from binary code, as a technique for applying existing source-based tools and techniques to binary programs. A decompiler must have two properties to be used for security: it must (1) be correct (is the output functionally equivalent to the binary code?), and (2) recover abstractions (e.g., the output should utilize while loops commands and not gotos). Previous work in control-flow structuring, which is a building block for decompilers, is insufficient for use in security, because it does not provide correctness and effective abstraction recovery. Specifically, we discovered that existing structuring algorithms are not semantics-preserving, which means that they cannot safely be used for decompilation without modification. Second, we found that existing structural algorithms miss opportunities for recovering control flow structure on (partially) unstructured code. We propose a new structuring algorithm that addresses these problems. We evaluate our decompiler, Phoenix, which features our new structuring algorithm, on a set of 107 real world programs from GNU coreutils. Our evaluation is an order of magnitude larger than previous studies of end-to-end decompilers. We show that our decompiler outperforms the de facto industry standard decompiler Hex-Rays in correctness by 114%, recovers 30 × more control-flow structure than existing structuring algorithms in the literature, and 28 % more than Hex-Rays.