Practical dynamic reconstruction of control flow graphs

• Ano de defesa: 2020
• Autor(a) principal: Andrei Rimsa Álvares
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Universidade Federal de Minas Gerais; Brasil; ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO; Programa de Pós-Graduação em Ciência da Computação; UFMG
• Palavras-chave em Português: Control flow graph; Dynamic analysis; Code instrumentation; Computação – Teses; Compiladores (Programas de computador) - Teses; Linguagem de programação (Computadores) – Teses; Fluxo de dados (Computação) – Teses
• Link de acesso: http://hdl.handle.net/1843/36523; https://orcid.org/0000-0002-0151-2900

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.