Scalable detection of security-vulnerabilities in source code

Abstract

With the advent of web technologies, services are becoming increasingly accessible on-line, for user convenience. Because of this, such systems are more susceptible to vulnerabilities, and several tools have emerged to do code analysis, not only static, but also dynamic, with the aim to detect abnormalities, such as vulnerabilities. State-of-the-art solutions for calculating data flow paths in the analysed code suffer from efficiency problems. Inefficiency appears because of the path representation, as it leads to a less efficient imple mentation. This dissertation proposes a new approach that obtains data flow paths on demand, from a represen tation that can store efficiently a set of paths and that, as a result, can have better results in terms of time efficiency. Benchmarks of the naive solution to the problem and the proposed solution in the dissertation show a drastic difference in time complexity, as the theory predicted, obtaining a time complexity ≥ O(e 2 ), for the simple solution, and a O(n + e), for the solution presented here, where e is the number of edges and n the number of nodes of the DFG extracted from the source code.

Com o advento das tecnologias web, os serviços estão a tornar-se cada vez mais acessíveis on-line, para a conveniência do usuário. Devido a isso, os tais sistemas são mais suscetíveis a vulnerabilidades, e diversas ferramentas surgiram para fazer análise de código, não apenas estática, mas também dinâmica, com o objetivo de detectar anormalidades, como vulnerabilidades. As soluções que compõem o estado de arte no cálculo de caminhos do data flow, têm problemas de eficiência nessa procura. A ineficiência aparece por causa da representação dos caminhos, pois leva a uma implementação menos eficiente. Esta dissertação propõe uma nova abordagem que obtém os caminhos do data flow de forma ”on demand”, a partir de uma representação que guarda de forma eficiente um conjunto de caminhos e por consequencia consegue ter melhores resultados em termos de eficiência em tempo. Este mecanismo tem até uma boa maneira de generalizar para algo modular. Testes de tempo da solução ingênua para o problema e a solução proposta na dissertação mostram uma diferença drástica na complexidade do tempo, como a teoria previa, tendo uma complexidade de tempo de ≥ O(e 2 ), para a solução simples, e O(n + e), para a solução apresentada aqui, onde e é o número de edges e n o número de nodos do DFG.