Analyse statique de programmes

L'analyse statique de programmes examine le code source ou intermédiaire, sans l'exécuter, afin d'en déduire des propriétés telles que les valeurs qu'une variable peut contenir ou la possibilité qu'une erreur se produise.

Definition

L'analyse statique de programmes est le calcul d'informations approximatives mais valides sur les comportements possibles d'un programme directement à partir de son code, sans l'exécuter, généralement en résolvant des équations de flux de données sur un treillis d'états abstraits.

Scope

Ce sujet couvre l'analyse de flux de données sur les graphes de flot de contrôle, le calcul de point fixe basé sur les treillis, l'analyse interprocédurale, l'analyse de pointeurs et d'alias, ainsi que l'analyse de graphes d'appels et de flot de contrôle. Il aborde les dimensions de précision (sensibilité au flot, au contexte et au chemin), la validité des analyses et leur utilisation dans l'optimisation et la détection de bogues.

Core questions

• Comment les propriétés des programmes sont-elles calculées en propageant des faits sur un graphe de flot de contrôle ?
• Comment la sensibilité au flot, au contexte et au chemin affecte-t-elle la précision et le coût ?
• Comment une analyse valide est-elle effectuée à travers les appels de procédure ?
• Comment l'analyse de pointeurs gère-t-elle l'aliasing et l'indirection ?

Key theories

L'analyse de flux de données comme point fixe sur un treillis

Kildall a unifié les optimisations globales de programmes en tant que calcul d'un point fixe d'équations de flux de données sur un treillis, fournissant ainsi le cadre général pour les analyses statiques.

L'analyse interprocédurale via la joignabilité de graphes

Reps, Horwitz et Sagiv ont réduit une grande classe de problèmes précis de flux de données interprocéduraux à la joignabilité de graphes, permettant une analyse efficace et sensible au contexte à travers les limites des procédures.

Principes et dimensions de l'analyse

Nielson, Nielson et Hankin systématisent les analyses basées sur le flux de données, les contraintes et les types, ainsi que les compromis précision-coût qui régissent leur conception.

Clinical relevance

L'analyse statique est à la base des optimisations de compilateurs, des outils de détection de bogues et de vulnérabilités, des linters et des fonctionnalités des environnements de développement intégrés (IDE). Les analyses valides peuvent certifier l'absence de certaines erreurs, tandis que les analyses heuristiques évolutives sont largement utilisées pour détecter les défauts dès le début du développement.

History

L'analyse de flux de données est née des compilateurs optimisants, le cadre de treillis de Kildall de 1973 et les analyses d'Allen-Cocke ayant fourni la base théorique. Les analyses interprocédurales et de pointeurs ont progressé au cours des années 1980 et 1990, y compris la formulation de la joignabilité de Reps-Horwitz-Sagiv, et l'analyse statique a ensuite été étendue à la détection industrielle de bogues sur de très grandes bases de code.

Debates

Précision versus évolutivité

Les concepteurs d'analyses arbitrent constamment entre les dimensions de précision telles que la sensibilité au contexte et au chemin, qui réduisent les faux positifs, et le coût computationnel qui limite la taille des programmes pouvant être analysés.

Key figures

• Gary Kildall
• Thomas Reps
• Susan Horwitz
• Flemming Nielson
• Hanne Riis Nielson

Seminal works

• kildall1973
• reps1995
• nielson1999

Frequently asked questions

Que signifie pour une analyse statique d'être valide ?

Une analyse valide ne manque jamais une occurrence réelle de la propriété qu'elle vérifie : si elle ne signale aucune erreur d'un type donné, ce type d'erreur ne peut véritablement pas se produire, bien qu'elle puisse également générer de fausses alertes.

Pourquoi l'analyse de pointeurs est-elle difficile ?

Les pointeurs et les références introduisent l'aliasing, où plusieurs noms font référence à la même mémoire ; l'analyse doit donc approximer les emplacements que chaque pointeur peut cibler, un problème qui met en balance la précision et l'évolutivité.