Algoritmo eficiente de análise estática para procurar ataques do tipo variáveis contaminadas

Abstract

Tainted variable attacks are originated from program inputs maliciously crafted to exploit software vulnerabilities. These attacks are common in server-side scripting languages, such as PHP. In 1997, Orbaek and Palsberg formalized the problem of detecting these exploits as an instance of type-checking, and has give an O(V3) algorithm to solve it. A similar algorithm was, ten years later, implemented on the Pixy free-software tool. In this dissertation we give an O(V2) solution to the same problem. Our solution uses Bodik et al.'s extended Static Single Assignment (e-SSA) program representation that can be efficiently computed and it enables us to treat the problem as an instance of graph reachability, where graph edges model data dependencies between program variables. Using the same infrastructure, we compared the data-flow solution with our technique. Both approaches have detected 36 vulnerabilities in well-known PHP programs, and our tests show that our approach tends to outperform the data-flow algorithm for larger PHP programs. We have reported the bugs that we found, and the implementation of our algorithm is now available for the phc open source PHP compiler.