Change-Based Approaches for Static Taint Analyses

In the past few years, many security problems have been discovered in all kinds of software. For some of these vulnerabilities, ill-intentioned people exploited them and successfully stole information about people and companies. The monetary cost of these vulnerabilities is real, and for this reason, many developers are trying to find these vulnerabilities before hackers do. One method to find vulnerabilities in an application before it is published is to use a static analysis tool. Taint analysis is one static analysis technique that is closely related to security. This approach simulates how data is propagated inside the application with the goal of finding locations that could either leak sensitive information or damage the integrity of the system. These analyses can take hours, depending on the tool used and the size of the codebase being analyzed. On top of taking considerable time, these analyses tend to be repeated over and over during development. The computation of taint is exhaustive and usually redone from scratch on every execution, even if the codebase has stayed nearly the same since the last analysis. This is why our work will mainly focus on how we can take advantage of the incremental nature of software development to accelerate the computation of taint. We propose new techniques to update the taint information from the changes in the source code between two versions of a given software. Our approaches are granular to the lines of code and succeed at greatly reducing the time required to find potential vulnerabilities in the projects that we analyzed.

Résumé

Les logiciels développés dans les dernières années ont souvent été aux prises avec des vulnérabilités qui ont été exploitées par des personnes mal intentionnées. Certaines de ces attaques ont coûté cher à plusieurs entreprises et particuliers dus aux données volées. Ainsi, il y a un besoin réel de déceler ces failles dans le code avant leur utilisation. Une technique pour tenter de détecter de possibles vulnérabilités dans le code avant même que le logiciel soit public est d'utiliser un outil d'analyse statique. En utilisant plus particulièrement l'analyse de teinte qui a pour but de simuler la propagation de données critiques dans le programme, il est possible de trouver des points d'accès dans le code qui ne sont pas protégés. Cependant, ces analyses peuvent prendre des heures selon l'outil utilisé et le volume de code à analyser. En plus d'être de longues analyses, elles sont souvent effectuées à répétition sur le même code au fur et à mesure qu'il est développé. Chaque fois, c'est un calcul exhaustif à partir de zéro alors que les changements dans le code sont généralement minimes en comparaison au volume total du logiciel. Instinctivement, on pourrait supposer que si les changements sont mineurs dans le code, les changements dans les résultats devraient aussi l'être. Dans ce mémoire, nous nous penchons sur des techniques tirant avantage de la nature incrémentale du développement logiciel afin d'accélérer le calcul de la teinte. Notre travail propose une technique novatrice qui met à jour la teinte en fonction des changements dans le code entre deux versions. Nous utilisons une technique qui est granulaire à la ligne de code. Avec nos améliorations, nous réussissons à largement réduire le temps de calcul nécessaire sur les projets que nous avons analysés.