Using Evolutionary Algorithms to Automate the Correction of Software Vulnerabilities

Abstract

The overwhelming cost of software maintenance has rallied up the field of automated program repair, looking to free developers from the burden imposed by the continuous discovery of faults. Vulnerabilities are a particularly attractive target, given the potential impact of their exploitation while mostly following common patterns for detection and correction. There is, however, a clear lack of repair tools focusing on vulnerabilities, despite not needing an oracle for detection and having lower patch complexity. This work proposes an evolutionary framework based on Genetic Programming for the automated correction of vulnerabilities leveraging the corresponding fix patterns, allowing precise modifications in the original source code through its tree-based representation. A population of candidate fixes is evolved, guided by an assessment of their quality that checks whether the vulnerability has been fixed and functional correctness preserved. To deal with the enormous search space of possible source code modifications, we apply domain specific constraints to minimize the generation of invalid (uncompilable) code including the preservation of typing and syntactic correctness. Further, we restrict the evolutionary procedure to specific lines of code, extracted from reports of instrumentation-based tools. The repair process can then become autonomous through integration with existing vulnerability detection tools based on automatic test generation.This required focusing on a single language, and, initially, on a limited set of vulnerability types. C was chosen due its prevalent adoption for critical software, and propensity for vulnerabilities related to memory safety, ranked as some of the most dangerous. We show our (GPVE) engine's capabilities on a set of vulnerabilities injected into two data structure implementations, while looking to study the impact of their type, localization, use of fix patterns, and of different fitness functions. The engine consistently generates complex fixes, with a 87.9% success rate across 9 vulnerabilities, though often to the detriment of other non-functional properties, namely performance and understandability. Further, the use of reduced test suites allowed for the acceptance of incorrect fixes that had overfitted to its test cases.Future work will look to apply the engine to large-scale programs where high coverage test suites provide stronger guarantees over the generated fixes' correctness. Despite its limitations, our work nevertheless shows Genetic Programming's applicability when tailored to vulnerability repair, being able to efficiently evolve programs to pass test cases that otherwise revealed vulnerabilities.

O custo esmagador da manutenção de software despoletou o campo de reparação automática de programas, procurando libertar os programadores da carga imposta pela descoberta contínua de falhas. Vulnerabilidades são um alvo atraente, dado o impacto da sua exploração, mas seguindo padrões comuns de deteção e correção. Há no entanto uma clara falta de ferramentas de reparo focadas em vulnerabilidades, apesar de não necessitarem de oráculo de testes para a sua deteção e terem correções menos complexas.Este trabalho propõe uma framework evolucionária baseada em Programação Genética para a correção automática de vulnerabilidades, aproveitando os padrões de correção correspondentes, e permitindo modificações precisas no código original através da sua representação baseada em árvores. Uma população de correções candidatas é evoluida, guiada por uma avaliação da sua aptidão que verifica se a vulnerabilidade foi corrigida e a correção funcional preservada. Para lidar com o enorme espaço de procura de modificações possíveis ao código, aplicamos restrições específicas ao domínio de modo a minimizar a geração de código inválido (que não compila), incluindo a preservação da correção sintática e de tipagem. Restringimos também o processo evolucionário a linhas específicas do código, extraídas de relatórios de ferramentas baseadas em instrumentação. O processo de reparo pode então ficar autonómo, através da integração com ferramentas existentes de deteção de vulnerabilidades baseadas em geração automática de testes.Focámo-nos numa única linguagem, e, inicialmente, num conjunto limitado de tipos de vulnerabilidade. C foi escolhida devido à sua adoção para software crítico e propensão para vulnerabilidades relacionadas com acesso à memória, classificadas como das mais perigosas. Mostramos as capacidades do motor de correções ``GPVE'' num conjunto de vulnerabilidades injetadas em duas implementações de estruturas de dados, procurando estudar o impacto do seu tipo, localização, uso de padrões de correção e de funções de avaliação diferentes. O motor gera consistentemente correções complexas, com uma taxa de sucesso de 87.9% em 9 vulnerabilidades, embora por vezes em detrimento de outras propriedades não funcionais, nomeadamente desempenho e legibilidade. O uso de conjuntos reduzidos de testes possibilitou ainda a aceitação incorreta de correções sobreajustadas aos seus casos de teste.Trabalho futuro passará por aplicar o motor a programas de grande escala, com conjuntos de teste de alta cobertura que forneçam garantias fortes sobre a correção das soluções geradas. Apesar duas suas limitações, o nosso trabalho demonstra a aplicabilidade de Programação Genética ao reparo de vulnerabilidades, sendo capaz de evoluir programas eficientemente para passar em casos de teste que de outro modo revelavam vulnerabilidades.