Product Design, Manufacturing & Innovation Resources
Heim » Formale Verifizierung

Formale Verifizierung

1980
  • Edmund M. Clarke
  • E. Allen Emerson
  • Joseph Sifakis
Informatik-Ingenieur bei der Überprüfung eines formalen Verifikationsmodells im Büro.

(Abbildung dient nur zur Veranschaulichung)

Formell Überprüfung Die formale Verifikation ist die Anwendung mathematischer Methoden, um die Korrektheit eines Systementwurfs im Hinblick auf eine formale Spezifikation zu beweisen oder zu widerlegen. Im Gegensatz zum Testen, das Fehler nur bei bestimmten Eingaben aufdecken kann, beweist die formale Verifikation deren Abwesenheit für alle möglichen Eingaben. Sie beinhaltet die Erstellung eines formalen Modells des Systems und die Anwendung von Techniken wie Modellprüfung oder Theorembeweisen.

Die formale Verifikation bietet die höchste Sicherheit für die Korrektheit eines Systems. Der Prozess beginnt mit der Erstellung eines formalen Modells des Systems mithilfe einer mathematischen Sprache, beispielsweise der temporalen Logik oder der Prozessalgebra. Ein Satz von Eigenschaften, abgeleitet aus den Systemanforderungen, wird ebenfalls in einer formalen Sprache ausgedrückt. Anschließend untersucht der Verifikationsprozess mithilfe automatisierter Werkzeuge systematisch alle möglichen Zustände des Modells, um festzustellen, ob die spezifizierten Eigenschaften erfüllt sind.

Es werden zwei Haupttechniken verwendet: Modellprüfung und Theorembeweis. Die Modellprüfung ist eine automatisierte Technik, die den gesamten Zustandsraum eines endlichen Zustandsmodells untersucht. Wird eine Eigenschaft verletzt, erzeugt der Modellprüfer ein Gegenbeispiel – einen konkreten Ausführungsablauf, der den Fehler demonstriert. Dieses Verfahren ist sehr effektiv, kann aber bei sehr komplexen Systemen unter dem Problem der Zustandsraumexplosion leiden. Beim Theorembeweis werden das System und seine Eigenschaften als logische Formeln (Theoreme) dargestellt und mithilfe automatisierter oder interaktiver Beweiser ein formaler Korrektheitsbeweis erstellt. Dieser Ansatz kann auch unendliche Zustandssysteme behandeln, erfordert aber oft einen erheblichen manuellen Aufwand von Experten.

Die formale Verifikation ist zwar rechenintensiv und erfordert spezialisiertes Fachwissen, aber für sicherheitskritische Systeme, bei denen die Kosten eines Ausfalls extrem hoch sind, unerlässlich. Sie wurde erfolgreich zur Überprüfung der Korrektheit von Gleitkommaeinheiten der CPU, Kommunikationsprotokollen und Steuerungssystemen eingesetzt, wo umfassende Tests nicht durchführbar sind.

UNESCO Nomenclature: 1203
- Informatik

Typ

Software/Algorithmus

Störung

Grundlegendes

Verwendung

Nische/Spezialisiert

Vorläufer

  • Aussagen- und Prädikatenlogik
  • automata theory
  • Lambda-Rechnung
  • Programmsemantik (z. B. Hoare-Logik)
  • Theorie der Berechnungskomplexität

Anwendungen

  • Mikroprozessor-Design (z. B. Intel Pentium Fdiv Bugfix)
  • Avionik-Software (z. B. Fly-by-Wire-Systeme)
  • Analyse kryptographischer Protokolle
  • Eisenbahnsignalsysteme
  • Softwaretreiber für kritische Betriebssysteme

Patente:

NA

Potenzielle Innovationsideen

Aufgrund des hohen Datenverkehrs durch Web-Scraping-Bots, der derzeit mehr als 40.000 Anfragen pro Tag umfasst, ist dieser Inhalt ausschließlich Community-Mitgliedern vorbehalten.
> Anmelden < oder > Registrieren < (100% kostenlos) Zugriff darauf sowie auf alle anderen eingeschränkten Inhalte und Tools.

Verwandt mit: formaler Verifikation, Modellprüfung, Theorembeweisen, formalen Methoden, Korrektheit, Softwareverifikation, Hardwareverifikation, temporaler Logik.

Historischer Kontext

Formale Verifizierung

1970
1973
1980
1980
1980
1982-07-01
1988-06-01
1970
1970-01-01
1975-06-01
1980
1980
1980
1986-01-01
1990

(wenn das Datum unbekannt oder nicht relevant ist, z. B. „Strömungsmechanik“, wird eine gerundete Schätzung seines bemerkenswerten Auftretens bereitgestellt)

Verwandte Erfindungen, Innovationen und technische Prinzipien

Bilder in voller Größe und Downloads sind nur für registrierte Mitglieder 100% kostenlos verfügbar.

> Login <