UCAM-CL-TR-844

ISSN 1476-2986 Decompilation is the process of converting programs in a low-level representation, such as machine code, into high-level programs that are human readable, compilable and seman-tically equivalent. The current de facto approach to decompilation is largely modelled on compiler theory and only focusses on one or two of these desirable goals at a time. This thesis makes the case that decompilation is more effectively accomplished through search. It is observed that software development is seldom a clean slate process and much software is available in public repositories. To back this claim, evidence is presented from three categories of software development: corporate software development, open source projects and malware creation. Evidence strongly suggests that code reuse is prevalent in all categories. Two approaches to search-based decompilation are proposed. The first approach borrows inspiration from information retrieval, and constitutes the first contribution of this thesis. It uses instruction mnemonics, control-flow sub-graphs and data constants, which ca