Programmverifikation

Programmverifikation bezeichnet Verfahren zur mathematischen Bestätigung, dass ein Programm eine gegebene Spezifikation erfüllt. Im Gegensatz zur reinen Ausführungstests zielt sie darauf ab, Korrektheit unabhängig von Laufzeitverhalten zu beweisen. Sie gehört zu den formalen Methoden der Softwareentwicklung und wird insbesondere dort eingesetzt, wo Fehler gravierende Folgen haben können.

Zu den gängigen Ansätzen gehören die deduktive Verifikation (Beweisführung mit logischen Spezifikationen, Hoare-Triple, Vorbedingungen, Nachbedingungen und Invarianten), Model Checking (automatisierte Prüfung aller Zustände und Übergänge mithilfe temporaler Logik wie LTL oder CTL) sowie formale Spezifikationen in Sprachen wie Z, VDM oder Alloy. Beweise können mit Beweisassistenten wie Coq oder Isabelle/HOL geführt werden; oder über die Generierung von Verifikationsbedingungen (weakest precondition, Verification Condition Generation) an den Code herangezogen werden.

Verifikation ergänzt oder ersetzt Tests in sicherheitskritischen Bereichen, in denen Zuverlässigkeit unabdingbar ist, etwa in Luftfahrt, Automobil- oder Medizintechnik. Sie erfordert präzise Spezifikationen und oft eine Abstraktion der Implementierung. Kosten, Fachwissen und Skalierbarkeit sind Hindernisse, weshalb Verifikation häufig schrittweise über Refinement und formale Spezifikationen in komplexen Systemen eingesetzt wird.

Die Programmverifikation sieht sich mit grundlegenden Grenzen konfrontiert: Allgemeine Verifikation ist unentscheidbar, und die Zustands- oder Abstraktionsgröße kann zu einer Zustandsexplosion führen. Praktische Anwendungen setzen daher oft modellbasierte oder teilweise verifizierte Ansätze sowie modulare Beweise voraus.

Historisch entwickelte sich die Programmverifikation aus den formalen Methoden der 1960er Jahre. Gegenwart wird sie in Industrie- und Forschungsprojekten genutzt und durch Werkzeuge wie Coq, Isabelle/HOL, SPIN, NuSMV oder Dafny unterstützt, die formale Beweisführung, Model Checking oder automatische Codegenerierung ermöglichen.