Formale Methoden in der Softwareentwicklung

Formale Methoden wenden mathematische Logik auf die Spezifikation, Entwicklung und Verifikation von Software an, wodurch Eigenschaften eines Systems bewiesen und nicht nur getestet werden können.

Definition

Formale Methoden sind mathematisch fundierte Techniken zur Spezifikation, Entwicklung und Verifikation von Softwaresystemen, bei denen Spezifikationen in formalen Sprachen ausgedrückt und Eigenschaften durch Beweise oder erschöpfende Zustandsraumexploration etabliert werden.

Scope

Dieses Thema behandelt formale Spezifikationssprachen wie Z, B und TLA+; axiomatische Semantik und Hoare-Logik zur Argumentation über Programmkorrektheit; Modellprüfung zur Verifikation von endlichen Zustands- und nebenläufigen Systemen; Theorembeweise und Beweisassistenten; sowie die Anwendung formaler Methoden in sicherheits- und schutzrelevanten Softwaresystemen.

Core questions

• Wie kann Softwareverhalten in einer formalen Sprache eindeutig spezifiziert werden?
• Wie wird die Programmkorrektheit in Bezug auf eine Spezifikation bewiesen?
• Wie verifiziert die Modellprüfung endliche Zustands- und nebenläufige Systeme erschöpfend?
• Wo rechtfertigen die Kosten und Vorteile formaler Methoden ihren Einsatz?

Key theories

Hoare-Logik und axiomatische Semantik

Hoare führte eine Logik von Vor- und Nachbedingungen ein, in der die Korrektheit von Programmkonstrukten durch Axiome und Inferenzregeln ausgedrückt wird, was eine Grundlage für den Beweis liefert, dass Programme ihre Spezifikationen erfüllen.

Modellprüfung

Die Modellprüfung exploriert automatisch und erschöpfend die erreichbaren Zustände eines endlichen Zustandsmodells, um temporale Logikeigenschaften zu verifizieren und Deadlocks sowie Verletzungen zu erkennen, die beim Testen wahrscheinlich übersehen würden.

Clinical relevance

Formale Methoden bieten die stärkste verfügbare Gewährleistung der Korrektheit und werden dort eingesetzt, wo ein Versagen inakzeptabel ist – Avionik, Eisenbahnsignaltechnik, Sicherheitsprotokolle und Hardware. Ihre Kosten beschränken ihren Einsatz jedoch hauptsächlich auf kritische Komponenten und nicht auf ganze große Systeme.

Evidence & guidelines

Studien zur industriellen Praxis dokumentieren die erfolgreiche Anwendung formaler Methoden in sicherheitskritischen Bereichen, und Standards wie DO-178C und die Common Criteria erkennen formale Techniken auf den höchsten Sicherheitsstufen an.

History

Die Programmverifikation wurde Ende der 1960er Jahre von Floyd und Hoare begründet, die Modellprüfung wurde Anfang der 1980er Jahre von Clarke, Emerson und Sifakis entwickelt (was mit einem Turing Award ausgezeichnet wurde), und Werkzeuge sowie Beweisassistenten haben die formale Verifikation seitdem in den industriellen Einsatz für kritische Systeme gebracht.

Debates

Skalierbarkeit und Kosten formaler Methoden

Eine anhaltende Debatte betrifft die Frage, ob formale Methoden wirtschaftlich auf große industrielle Software skalierbar sind; Fortschritte in der Automatisierung und bei leichtgewichtigen formalen Methoden haben die Anwendbarkeit erweitert, aber die vollständige Verifikation großer Systeme bleibt kostspielig.

Key figures

• C. A. R. Hoare
• Edsger Dijkstra
• Edmund Clarke
• Leslie Lamport

Seminal works

• hoare1969
• clarke1999
• woodcock2009

Frequently asked questions

Ersetzen formale Methoden das Testen?

Im Allgemeinen nein. Formale Methoden bieten starke Garantien für ein Modell oder eine Spezifikation, aber Annahmen, die Umgebung und nicht modellierte Aspekte erfordern weiterhin Tests; in der Praxis ergänzen sich beide, wobei formale Methoden auf die kritischsten Eigenschaften fokussiert sind.

Warum werden formale Methoden nicht überall eingesetzt?

Sie erfordern spezialisiertes Fachwissen und Aufwand, die für die meisten Softwaresysteme schwer zu rechtfertigen sind, wo Tests zu geringeren Kosten eine ausreichende Sicherheit bieten; formale Methoden konzentrieren sich dort, wo die Folgen eines Versagens schwerwiegend genug sind, um die Investition zu rechtfertigen.