Control-flow analysis and manipulation techniques for effective binary translation and decompilation

Our everyday life is characterized by the interaction with a multitude of electronic devices, that we use for any kind of purpose, from work tasks to leisure activities. The majority of the software that runs on such devices does not offer strong guarantees in terms of functional and non-functional properties. Indeed, companies tend to be very secretive about their implementations and rarely provide access to the source code of their applications, either to protect patents and trade secrets, or in the hope to provide security by obscurity. In some fields, it is also common to find legacy code that runs parts of critical infrastructures, for which gaining access to the source is not even an option, since the company that originally provided might have run out of business. Reverse engineering is an important branch of the computer security landscape, and its purpose is to extract information about the internals, or more in general the behavior, of a piece of software (and/or hardware). In this context, decompilers are fundamental tools to perform security assessments of third-party software, that try to undo the work of the compiler. A decompiler is a tool that allows to extract a source code-like representation starting from binary programs, and can be of great help to understand the behavior of such software. In this thesis, we tackle a specific problem of the decompilation field, the recovery of high-level control constructs. To do this, we design novel control-flow restructuring techniques, and implement an entire decompiler tool on top of the rev.ng binary analysis framework. rev.ng is a binary translator tool, that is able to extract a raw representation for a binary, exploiting the LLVM and QEMU frameworks (in particular, a representation in terms of LLVM IR). As output, we obtain C pseudocode in which we are able to emit high-level control-flow construct typical of the C programming language. In the thesis, we perform extensive comparison of the produced output by our tool against the major decompiler solutions available on the market. In addition to this, we also improve the translation capability of the rev.ng framework, a key feature that enable us to also produce binaries, in which the transformations applied by our decompiler stage are reflected in the executable form. This is turn, enable us to prove that the restructuring techniques, that we apply in order to emit the C pseudocode, preserve the functionality in the binary, thus proving their correctness.

Quotidianamente interagiamo con una moltitudine di device elettronici, che utilizziamo per vari scopi, da quelli lavorativi ad attività di piacere. La maggior parte del software che è eseguito su tali device non offre garanzie robuste in termini di requisiti funzionali e non. Le aziende infatti, tendono ad adottare riservatezza nella comunicazione dei dettagli delle implementazioni software, e raramente forniscono accesso al codice sorgente delle applicazioni da loro sviluppate, sia per proteggere eventuali brevetti e segreti industriali, o nella speranza di fornire sicurezza tramite la segretezza delle implementazioni. In alcuni campi, è anche molto comune trovare componenti deprecate che sono alla base di infrastrutture critiche. Per queste componenti, pensare di ottenere accesso al codice sorgente originario è spesso impensabile, dato che aziende sviluppatrici spesso non sono più esistenti. L'ingegneria inversa (reverse engineering), è una branca molto importante della sicurezza informatica, e il suo scopo è quello di estrarre informazioni riguardo il funzionamento interno, o più in generale del comportamento, di una componente software o hardware. In questo contesto, i decompilatori, strumenti che cercano di smontare il lavoro fatto dal compilatore, sono fondamentali per effettuare valutazioni di software di terze parti. Il decompilatore infatti permette di recuperare una rappresentazione in pseudocodice a partire da un programma in forma di eseguibile, ed può essere di fondamentale aiuto nel capire il comportamento di tale software. In questa tesi, affrontiamo un sotto-problema della decompilazione, ovvero il recupero di costrutti di controllo di alto livello. Per fare ciò, progettiamo delle tecniche di trasformazione del flusso di controllo, e implementiamo un decompilatore completo all'interno del framework di analisi di eseguibili chiamato rev.ng. rev.ng è uno strumento che effettua traduzione statica di eseguibili, che è in grado di estrarre una rappresentazione di alto livello a partire da un eseguibile, basandosi sui framework LLVM e QEMU. Come risultato, otteniamo del pseudocodice in linguaggio C in cui sono presenti costrutti di controllo di alto livello tipici del linguaggi di programmazione stesso. Nella tesi, effettuiamo una comparazione esaustiva dei risultati prodotti con alcune delle più diffuse soluzioni di decompilazione presenti sul mercato. In aggiunta a ciò, abbiamo anche migliorato le capacità di traduzione di eseguibili del framework rev.ng, e questo risultato ci permetto di produrre eseguibili che rispecchiano le trasformazioni applicate durante la decompilazione. Questo a sua volta, ci permette di fornire una prova operativa che tali trasformazioni non intaccano la semantica e la funzionalità dell'eseguibile originale.