Ripping out the knots : high-level control-flow constructs recovery from binary programs

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. A decompiler is a tool that allows to extract a source-code like representation starting from binary programs, can be an effective way to gain knowledge about the behavior of such software. In this work we decided to investigate the decompilation field, specifically the problem of high-level control constructs recovery. In particular, we had the opportunity of working within rev.ng, a unified binary analysis framework, that is able to lift a binary program to a LLVM IR representation. We start by definining the function isolation process, which is used to extract from the IR lifted by rev.ng an isolated representation for the functions identified in a binary, which is vital to our ends. In the rest of the work, we focus on the problem of recovering high-level control constructs, such as if statements and while loops, from binary programs. In doing this, we define new semantics-preserving transformations, a novel method, called the comb, for normalizing CFG regions, a procedure for reconstructing the AST of a normalized CFG region, and a set of post-processing optimizations performed on the generated AST for recovering additional control constructs. We conclude by analyzing the results obtained by the implementation of the techniques described, compared to the industry market leader, and by illustrating some future developments to our design.

La nostra vita di tutti i giorni è caratterizzata dall'interazione con una rilevante quantità di dispositivi elettronici, che usiamo per scopi lavorativi lavorativi e di svago personale La maggior parte del software eseguito da questi dispositivi non offre garanzie riguardo proprietà funzionali e non. Un decompilatore in grado di estrarre una rappresentazione in termini di codice sorgente di un eseguibile, che può essere molto utile per capire il funzionamento di tale software. Tutto ciò ci ha condotto a iniziare un'analisi delle soluzioni disponibili in questo ambito, ed ad approcciare la decompilazione. Questo ci ha condotto ad iniziare un'analisi delle soluzioni disponibili in questo ambito, ed ad approcciare la decompilazione, in particolare il problema della identificazione di costrutti di controllo ad alto livello. Abbiamo avuto l'opportunità di lavorare in questo senso utilizzando rev.ng, un framework per l'analisi di binary indipendete dalla piattaforma, che è in grado di generare, a partire da un binario, una rappresentazione di più alto livello in LLVM IR. Iniziamo con il definire il processo di isolamento di funzione, che verrà utilizzato per estrarre, per ogni funzione identificata nel binario, una separata rappresentazione. Questo sarà un aspetto vitale per il resto del nostro design. Successivamente ci focalizziamo sulla problematica di identificazione di costrutti di controllo ad alto livello, come costrutti if e cicli while, in programmi binari. Per fare ciò, definiamo alcune trasformazioni che preservano la semantica, un nuovo metodo chiamato il pettine, il cui compito è quello di normalizzare regioni del CFG, una procedura per generare l'AST di una regione normalizzata, e altre fasi di post-processing sull'AST che permettono di recuperare ulteriori costrutti di controllo. Concludiamo commentando i risultati ottenuti dall'implementazione del nostro design, comparandoci con l'attuale leader del mercato nel campo dei compilatori, e tracciando alcune possibilità di sviluppo della nostra soluzione.