No More Gotos: Decompilation Using Pattern-Independent Control-Flow Structuring and Semantics-Preserving Transformations
Download: Paper (PDF)
Date: 7 Feb 2015
Document Type: Briefing Papers
Additional Documents: Slides
Associated Event: NDSS Symposium 2015
Decompilation is important for many security applications; it facilitates the tedious task of manual malware reverse engineering and enables to use source-code based security tools on binary code. This includes tools to find vulnerabilities and perform taint tracking. Recovering high-level control constructs is essential for decompilation in order to produce structured code that is suitable for human analysts and source-based program analysis techniques. State-of-the-art decompilers rely on structural analysis, a pattern-matching approach over the control flow graph, to recover control constructs from binary code. Whenever no match is found they generate goto statements and thus produce unstructured decompiled output. Those statements are problematic because they make decompiled code harder to understand and less suitable for security analysis. In this paper, we present DREAM, the first decompiler to offer a goto free output. DREAM uses a novel patten-independent control-flow structuring algorithm, which can recover all control constructs in binary programs and produce structured decompiled code without any goto statement. We also present semanticpreserving transformations which can transform unstructured control flow graphs into structured graphs. We demonstrate the correctness of our algorithms show that we outperform both the leading industry and academic decompilers: Hex-Rays and Phoenix. We use the the GNU coreutils suite of utilities as a benchmark. Apart from reducing the number of goto statements to zero DREAM also produced more compact code (less lines of code) for 72,7% of decompiled functions compared to Hex-Rays and 98,8% compared to Phoenix. We also present a comparison of Hex-Rays and DREAM when decompiling three samples from Credix, ZeusP2P and SpyEye malware families.