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

There are many security tools and techniques for analyzing software, but many of them require access to source code. We propose leveraging decompilation, the study of recovering abstractions from compiled code, to apply existing source-based tools and techniques to compiled programs. A decompiler should focus on two properties to be used for security. First, it should recover abstractions as much as possible to minimize the complexity that must be handled by the security analysis that follows. Second, it should aim to recover these abstractions correctly. Previous work in control-flow structuring, an abstraction recovery problem used in decompilers, does not provide either of these properties. Specifically, existing structuring algorithms are not semantics-preserving, which means that they cannot safely be used for decompilation without modification. Existing structural algorithms also miss opportunities for recovering control flow structure. We propose a new structuring algorithm in this paper that addresses these problems. We evaluate our decompiler, Phoenix, and our new structuring algorithm, on a set of 107 real world programs from GNUcoreutils. Our evaluation is an order of magnitude larger than previous systematic studies of end-to-end decompilers. We show that our decompiler outperforms the de facto industry standard decompiler Hex-Rays in correctness by 114%, and recovers 30× more controlflow structure than existing structuring algorithms in the literature.