Statische Programmanalyse

Die statische Programmanalyse untersucht Quell- oder Zwischencode, ohne ihn auszuführen, um Eigenschaften abzuleiten, wie z. B. welche Werte eine Variable annehmen kann oder ob ein Fehler auftreten kann.

Definition

Statische Programmanalyse ist die Berechnung von annähernden, aber korrekten Informationen über die möglichen Verhaltensweisen eines Programms direkt aus dessen Code, ohne es auszuführen, typischerweise durch das Lösen von Datenflussgleichungen über einem Gitter abstrakter Zustände.

Scope

Dieses Thema behandelt die Datenflussanalyse über Kontrollflussgraphen, die gitterbasierte Fixpunktberechnung, die interprozedurale Analyse, die Zeiger- und Aliasanalyse sowie die Aufrufgraph- und Kontrollflussanalyse. Es befasst sich mit den Präzisionsdimensionen (Fluss-, Kontext- und Pfad-Sensitivität), der Korrektheit von Analysen und deren Verwendung bei der Optimierung und Fehlererkennung.

Core questions

• Wie werden Programmeigenschaften durch die Propagation von Fakten über einen Kontrollflussgraphen berechnet?
• Wie beeinflussen Fluss-, Kontext- und Pfad-Sensitivität Präzision und Kosten?
• Wie wird eine korrekte Analyse über Prozeduraufrufe hinweg durchgeführt?
• Wie geht die Zeigeranalyse mit Aliasing und Indirektion um?

Key theories

Datenflussanalyse als Fixpunkt über einem Gitter

Kildall vereinte globale Programmoptimierungen als die Berechnung eines Fixpunkts von Datenflussgleichungen über einem Gitter und lieferte so den allgemeinen Rahmen für statische Analysen.

Interprozedurale Analyse mittels Graphenerreichbarkeit

Reps, Horwitz und Sagiv reduzierten eine große Klasse präziser interprozeduraler Datenflussprobleme auf die Graphenerreichbarkeit, was eine effiziente kontextsensitive Analyse über Prozedurgrenzen hinweg ermöglichte.

Prinzipien und Dimensionen der Analyse

Nielson, Nielson und Hankin systematisieren Datenfluss-, Constraint-basierte und Typ-basierte Analysen sowie die Kompromisse zwischen Präzision und Kosten, die deren Design bestimmen.

Clinical relevance

Statische Analyse treibt Compiler-Optimierungen, Tools zur Fehler- und Schwachstellenfindung, Linter und IDE-Funktionen an. Korrekte Analysen können die Abwesenheit bestimmter Fehler zertifizieren, während skalierbare heuristische Analysen weit verbreitet sind, um Defekte frühzeitig in der Entwicklung zu erkennen.

History

Die Datenflussanalyse entwickelte sich aus optimierenden Compilern, wobei Kildalls Gitter-Framework von 1973 und die Allen-Cocke-Analysen die theoretische Grundlage bildeten. Interprozedurale und Zeigeranalysen entwickelten sich in den 1980er und 1990er Jahren weiter, einschließlich der Reps-Horwitz-Sagiv-Erreichbarkeitsformulierung, und die statische Analyse skalierte später für die industrielle Fehlersuche in sehr großen Codebasen.

Debates

Präzision versus Skalierbarkeit

Analyse-Designer wägen kontinuierlich Präzisionsdimensionen wie Kontext- und Pfad-Sensitivität, die Fehlalarme reduzieren, gegen die Rechenkosten ab, die die Größe eines analysierbaren Programms begrenzen.

Key figures

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

Seminal works

• kildall1973
• reps1995
• nielson1999

Frequently asked questions

Was bedeutet es, wenn eine statische Analyse korrekt (sound) ist?

Eine korrekte Analyse übersieht niemals ein tatsächliches Auftreten der Eigenschaft, die sie prüft: Wenn sie keinen Fehler einer bestimmten Art meldet, kann diese Art von Fehler tatsächlich nicht auftreten, obwohl sie auch Fehlalarme auslösen kann.

Warum ist die Zeigeranalyse schwierig?

Zeiger und Referenzen führen zu Aliasing, bei dem mehrere Namen auf denselben Speicher verweisen, sodass die Analyse annähern muss, welche Speicherorte jeder Zeiger ansprechen kann, ein Problem, das Präzision gegen Skalierbarkeit abwägt.