Programmanalyse und -verifikation
Programmanalyse und -verifikation nutzen rigorose Techniken, um das Verhalten von Programmen zu untersuchen, Fehler zu erkennen oder zu beweisen, dass Software ihre Spezifikation erfüllt.
Definition
Programmanalyse ist die automatisierte Ableitung von Eigenschaften des Programmverhaltens, ohne es auf alle Eingaben anzuwenden, und Programmverifikation ist die Feststellung, durch Beweis oder erschöpfende Prüfung, dass ein Programm eine formale Spezifikation erfüllt.
Scope
Dieser Bereich umfasst die automatisierte und semi-automatisierte Analyse von Programmen: statische Analyse und Datenfluss-Techniken, abstrakte Interpretation als vereinheitlichender Rahmen für zuverlässige Approximation, Modellprüfung von Endzustands- und parallelen Systemen sowie deduktive Verifikation mit Beweisassistenten. Er befasst sich mit der Korrektheit (Soundness), dem Kompromiss zwischen Präzision und Entscheidbarkeit sowie der Anwendung dieser Methoden zum Aufbau vertrauenswürdiger Software.
Sub-topics
Core questions
- Wie können Programmeigenschaften trotz Unentscheidbarkeit zuverlässig berechnet werden?
- Wie wägen Analysen Präzision gegen Skalierbarkeit ab?
- Wann kann die Korrektheit eines Systems erschöpfend geprüft und nicht nur getestet werden?
- Wie werden vollständige Beweise der funktionalen Korrektheit konstruiert und maschinell geprüft?
Key theories
- Abstrakte Interpretation
- Cousot und Cousot etablierten einen gittertheoretischen Rahmen, in dem zuverlässige statische Analysen als Approximationen der Semantik eines Programms abgeleitet werden, wodurch viele Analysen vereinheitlicht und deren Korrektheit (Soundness) garantiert wird.
- Modellprüfung mit Temporallogik
- Clarke, Emerson und Sistla zeigten, wie endliche, parallele Systeme automatisch gegen temporallogische Spezifikationen verifiziert werden können, indem der Zustandsraum erschöpfend untersucht wird.
- Mechanisierte End-to-End-Verifikation
- Leroys verifizierter Compiler demonstriert, dass realistische Software mit einem Beweisassistenten als korrekt erwiesen werden kann, wodurch eine maschinell geprüfte Garantie gegeben wird, dass die Kompilierung das Programmverhalten bewahrt.
Clinical relevance
Programmanalyse und -verifikation bilden die Grundlage für Werkzeuge, die Fehler und Sicherheitslücken in großem Maßstab finden, sicherheitskritische Avionik- und Automobilsoftware zertifizieren und maschinell geprüfte Compiler und Betriebssystemkerne produzieren. Sie wandeln die Korrektheit von einem auf Tests basierenden Vertrauen in nachweisbare Garantien um.
History
Die Datenflussanalyse entstand in den 1970er Jahren mit optimierenden Compilern, im selben Jahrzehnt, in dem die Cousots die abstrakte Interpretation einführten. Die Modellprüfung entstand in den frühen 1980er Jahren durch Clarke und Emerson und unabhängig davon Queille und Sifakis und wurde später mit einem Turing Award ausgezeichnet. In den 2000er Jahren gab es große industrielle Erfolge bei der statischen Analyse und mechanisierten Verifikation, wie CompCert und seL4.
Debates
- Korrektheit (Soundness) versus Praktikabilität von Analysen
- Werkzeugentwickler diskutieren, ob Analysen vollständig korrekt (sound) sein sollten, alle möglichen Fehler melden, aber viele Fehlalarme riskieren, oder bewusst unkorrekt (unsound), um Rauschen zu reduzieren und zu skalieren, eine Spannung, die industrielle Fehlerfindungs-Tools prägt.
Key figures
- Patrick Cousot
- Radhia Cousot
- Edmund Clarke
- E. Allen Emerson
- Xavier Leroy
Related topics
Seminal works
- cousot1977
- clarke1986
- leroy2009
- nielson1999
Frequently asked questions
- Was ist der Unterschied zwischen statischer Analyse und Verifikation?
- Statische Analyse leitet automatisch approximative Eigenschaften (wie mögliche Nullzeiger-Dereferenzierungen) ohne vollständige Spezifikationen ab, während Verifikation beweist, dass ein Programm eine präzise formale Spezifikation erfüllt, was typischerweise mehr Aufwand erfordert und stärkere Garantien liefert.
- Wenn Korrektheit unentscheidbar ist, wie kann Analyse funktionieren?
- Analysen umgehen die Unentscheidbarkeit, indem sie zuverlässige Approximationen berechnen: Sie können einige Möglichkeiten melden, die tatsächlich nicht auftreten können, aber sie übersehen niemals eine tatsächliche Verletzung der Eigenschaft, die sie verifizieren.