Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/36523| Type: | Tese |
| Title: | Practical dynamic reconstruction of control flow graphs |
| Other Titles: | Reconstrução dinâmica prática de grafos de fluxo de controle |
| Authors: | Andrei Rimsa Álvares |
| First Advisor: | Fernando Magno Quintão Pereira |
| metadata.dc.contributor.advisor2: | José Nelson Amaral |
| First Referee: | José Eduardo Moreira |
| Second Referee: | Rodolfo Jardim de Azevedo |
| Third Referee: | Leonardo Barbosa e Oliveira |
| metadata.dc.contributor.referee4: | Marcos Augusto Menezes Vieira |
| Abstract: | The automatic recovery of a program’s high-level representation from its binary version is a well-studied problem in programming languages. However, most of the solutions to this problem are based on purely static approaches: techniques such as dataflow analyses or type inference are used to convert the bytes that constitute the executable code back into a control flow graph (CFG). This work departs from such a modus operandi to show that a dynamic analysis can be effective and useful, both as a standalone technique, and as a way to enhance the precision of static approaches. The experimental results provide evidence that completeness, i.e., the ability to conclude that the entire CFG has been discovered, is achievable on many functions that are part of industry-strong benchmarks. Experiments also indicate that dynamic information greatly enhances the ability of DynInst, a state-of-the-art binary reconstructor, to deal with code stripped of debugging information. These results were obtained with CFGgrind, a new implementation of a dynamic code reconstructor, built on top of valgrind. When applied to cBench, CFGgrind is 9% faster than callgrind, valgrind’s tool used to track targets of function calls; and 7% faster in Spec Cpu2017. CFGgrind recovers the complete CFG of 40% of all the procedures invoked during the standard execution of programs in Spec Cpu2017, and 37% in cBench. When combined with CFGgrind, DynInst finds 15% more CFGs for cBench, and 7% more CFGs for Spec Cpu2017. Finally, CFGgrind is more than 7 times faster than DCFG, a CFG reconstructor from Intel, and 1.28 times faster than bfTrace, a CFG reconstructor used in research. CFGgrind is also more precise than these two tools, handling operating system signals, shared code in functions, and unaligned instructions; besides supporting multi-threaded programs, exact profiling and incremental refinements. |
| Abstract: | A recuperação automática de informações de alto-nível de programas em formato binário é um importante problema estudado em linguagens de programação. Contudo, a maioria das soluções para esse problema são baseadas puramente em abordagens estáticas: técnicas como análise de fluxo de dados ou inferência de tipos são utilizadas para converter os bytes que constituem o executável de volta para o formato de um grafo de fluxo de controle (GFC). Esse trabalho se afasta desse tal modus operandi para mostrar que análises dinâmicas podem ser efetivas e úteis, tanto como uma técnica independente, quanto como uma forma de melhorar a precisão das abordagens estáticas. Os resultados experimentais mostram evidências que completude, ou seja, a habilidade de concluir que todos os caminhos de um GFC foram cobertos, é alcançada em muitas funções de benchmarks de nível industrial. Os experimentos também indicam que informações coletadas dinamicamente melhoram consideravelmente a habilidade de DynInst, um reconstrutor estático estado-da-arte, de lidar com códigos binários sem símbolos de depuração. Esses resultados foram obtidos com CFGgrind, um reconstrutor dinâmico de códigos binários, construído sobre a infraestrutura de valgrind. Quando aplicado sobre cBench, CFGgrind é 9% mais rápido que callgrind, uma ferramenta de valgrind capaz de rastrear alvos de chamadas de funções; e 7% mais rápido em Spec Cpu2017. CFGgrind recupera GFCs completos em 40% de todos os procedimentos invocados durante a execução padrão de programas em Spec Cpu2017, e 37% em cBench. Quando combinado com CFGgrind, DynInst encontra 15% mais GFCs para cBench e 7% mais GFCs para Spec Cpu2017. Finalmente, CFGgrind é 7 vezes mais rápido que DCFG, um reconstrutor de GFC desenvolvido pela Intel, e é 1.28 vezes mais rápido que bfTrace, um reconstrutor usado em pesquisa. CFGgrind é também mais preciso que essas duas ferramentas. Ele suporta tratamento de sinais de sistema operacional, códigos compartilhados em funções, instruções desalinhadas, programas multi-thread, profiling exato e refinamentos incrementais. |
| Subject: | Computação – Teses Compiladores (Programas de computador) - Teses Linguagem de programação (Computadores) – Teses Fluxo de dados (Computação) – Teses |
| language: | eng |
| metadata.dc.publisher.country: | Brasil |
| Publisher: | Universidade Federal de Minas Gerais |
| Publisher Initials: | UFMG |
| metadata.dc.publisher.department: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
| metadata.dc.publisher.program: | Programa de Pós-Graduação em Ciência da Computação |
| Rights: | Acesso Aberto |
| metadata.dc.rights.uri: | http://creativecommons.org/licenses/by/3.0/pt/ |
| URI: | http://hdl.handle.net/1843/36523 |
| Issue Date: | 5-Nov-2020 |
| Appears in Collections: | Teses de Doutorado |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| thesis.pdf | 4.42 MB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License
