Formale Methoden

Im Informatik, Formale Methoden sind mathematisch strenge Techniken für die Spezifikation, Entwicklung und Überprüfung von Software und Hardware- Systeme.[1] Die Verwendung formaler Methoden für Software und Hardwaredesign wird durch die Erwartung motiviert, dass die Durchführung einer geeigneten mathematischen Analyse wie in anderen technischen Disziplinen zur Zuverlässigkeit und Robustheit eines Designs beitragen kann.[2]

Formale Methoden verwenden eine Vielzahl von Theoretische Informatik Grundlagen, einschließlich Logik Kalkül, formelle Sprachen, Automatenheorie, Kontrolltheorie, Programmsemantik, Typsysteme, und Typentheorie.[3]

Hintergrund

Semi-Formen-Methoden sind Formalismen und Sprachen, die nicht vollständig betrachtet werden “formell”. Es vertieft die Aufgabe, die Semantik in einer späteren Phase zu vervollständigen, die dann entweder durch menschliche Interpretation oder durch Interpretation durch Software wie Code oder Test -Fallgeneratoren durchgeführt wird.[4]

Taxonomie

Formale Methoden können auf mehreren Ebenen verwendet werden:

Stufe 0: Formale Spezifikation kann durchgeführt werden und dann ein Programm, das informell entwickelt wurde. Dies wurde bezeichnet Formale Methoden Lite. Dies kann in vielen Fällen die kostengünstigste Option sein.

Level 1: Formale Entwicklung und formelle Überprüfung kann verwendet werden, um ein Programm formeller zu produzieren. Zum Beispiel Beweise von Eigenschaften oder Raffinesse von dem Spezifikation zu einem Programm kann durchgeführt werden. Dies kann in hohen Integritätssystemen am besten geeignet sein, die beteiligt sind Sicherheit oder Sicherheit.

Level 2: Theoremprover kann verwendet werden, um vollständig formelle maschinell überprüfte Beweise vorzunehmen. Trotz der Verbesserung der Werkzeuge und der sinkenden Kosten kann dies sehr teuer sein und lohnt sich nur, wenn die Fehlerkosten sehr hoch sind (z. B. in kritischen Teilen des Betriebssystems oder im Mikroprozessor -Design).

Weitere Informationen dazu werden erweitert unter.

Wie mit Programmiersprache Semantik, Stile formale Methoden können grob wie folgt klassifiziert werden:

  • Denotationssemantik, in der die Bedeutung eines Systems in der mathematischen Theorie von ausgedrückt wird Domänen. Befürworter solcher Methoden stützen sich auf die gut verstandene Natur von Domänen, um dem System einen Sinn zu geben; Kritiker weisen darauf hin, dass nicht jedes System intuitiv oder natürlich als Funktion betrachtet wird.
  • Betriebssemantik, in der die Bedeutung eines Systems als Folge von Aktionen eines (vermutlich) einfacheren Rechenmodells ausgedrückt wird. Befürworter solcher Methoden deuten auf die Einfachheit ihrer Modelle hin, um die Ausdrucksklarheit auszudrücken; Kritiker kontert, dass das Problem der Semantik gerade verzögert wurde (wer definiert die Semantik des einfacheren Modells?).
  • Axiomatische Semantik, in der die Bedeutung des Systems in Bezug auf das ausgedrückt wird Voraussetzungen und Postconditions die vor und nach dem System eine Aufgabe wahr sind. Befürworter beachten die Verbindung zu Klassiker Logik; Kritiker stellen fest, dass solche Semantik nie wirklich beschreiben, was für ein System tut (Nur was vor und danach wahr ist).

Leichte formale Methoden

Einige Praktiker glauben, dass die formale Methodengemeinschaft die vollständige Formalisierung einer Spezifikation oder eines Designs überbetont hat.[5][6] Sie behaupten, dass die Ausdruckskraft der beteiligten Sprachen sowie die Komplexität der modellierten Systeme die volle Formalisierung zu einer schwierigen und teuren Aufgabe machen. Als Alternative verschiedene Leicht Es wurden formale Methoden vorgeschlagen, die die Teilspezifikation und eine fokussierte Anwendung hervorheben. Beispiele für diesen leichten Ansatz zu formalen Methoden sind die Legierung Objektmodellierungsnotation,[7] Denneys Synthese einiger Aspekte der Z Notation mit Anwendungsfall getriebene Entwicklung,[8] und die CSK VDM Werkzeug.[9]

Verwendet

Formale Methoden können an verschiedenen Stellen durch die angewendet werden Entwicklungsprozess.

Spezifikation

Formale Methoden können verwendet werden, um eine Beschreibung des zu entwickelnden Systems auf der gewünschten Ebene des Details zu geben. Diese formale Beschreibung kann verwendet werden, um weitere Entwicklungsaktivitäten zu leiten (siehe folgende Abschnitte); Darüber hinaus kann es verwendet werden, um zu überprüfen, ob die Anforderungen an das zu entwickelnde System vollständig und genau spezifiziert wurden oder die Systemanforderungen formalisieren, indem sie in einer formalen Sprache mit einer präzisen und eindeutig definierten Syntax und Semantik ausgedrückt werden.

Die Notwendigkeit formaler Spezifikationssysteme ist seit Jahren festgestellt. In dem Algol 58 Bericht,[10] John Backus präsentierte eine formale Notation zur Beschreibung der Programmiersprache Syntax, später benannt Backus normale Form dann umbenannt Backus -Naur -Form (BNF).[11] Backus schrieb auch, dass eine formale Beschreibung der Bedeutung syntaktisch gültiger Algol -Programme nicht rechtzeitig zur Aufnahme in den Bericht abgeschlossen wurde. "Daher wird die formale Behandlung der Semantik von Rechtsprogrammen in ein nachfolgendes Papier aufgenommen." Es erschien nie.

Entwicklung

Die formale Entwicklung ist die Verwendung formaler Methoden als integriertes Bestandteil eines mit Werkzeug unterstützten Systementwicklungsprozesses.

Sobald eine formale Spezifikation erstellt wurde, kann die Spezifikation als Leitfaden verwendet werden, während das Betonsystem ist aufgetreten während der Entwurf Prozess (d. H. In der Regel in Software realisiert, aber auch möglicherweise in Hardware). Zum Beispiel:

  • Wenn sich die formale Spezifikation in der operativen Semantik befindet, kann das beobachtete Verhalten des konkreten Systems mit dem Verhalten der Spezifikation verglichen werden (die selbst ausführbar oder simulierbar sein sollte). Darüber hinaus können die operativen Befehle der Spezifikation für die direkte Übersetzung in ausführbaren Code zugänglich sein.
  • Wenn die formale Spezifikation in der axiomatischen Semantik liegt Behauptungen im ausführbaren Code.

Überprüfung

Die formale Überprüfung ist die Verwendung von Softwaretools, um Eigenschaften einer formalen Spezifikation zu beweisen oder zu beweisen, dass ein formales Modell einer Systemimplementierung ihre Spezifikation erfüllt.

Sobald eine formale Spezifikation entwickelt wurde, kann die Spezifikation als Grundlage für die Grundlage verwendet werden Beweis Eigenschaften der Spezifikation und nach Inferenz Eigenschaften der Systemimplementierung.

Abmeldeverifizierung

Die Verifizierung von Abmelden ist die Verwendung eines formellen Überprüfungswerkzeugs, das sehr vertrauenswürdig ist. Ein solches Tool kann herkömmliche Überprüfungsmethoden ersetzen (das Tool kann sogar zertifiziert werden).

Menschlich gerichteter Beweis

Manchmal die Motivation, das zu beweisen Richtigkeit eines Systems ist nicht das offensichtliche Bedürfnis nach Bestätigung der Richtigkeit des Systems, sondern der Wunsch, das System besser zu verstehen. Folglich werden einige Beweise der Korrektheit im Stil von produziert mathematischer Beweis: handgeschrieben (oder Typenset) verwenden Natürliche Sprachemit einer Ebene der Informalität, die solchen Beweisen gemeinsam ist. Ein "guter" Beweis ist einer, der von anderen menschlichen Lesern lesbar und verständlich ist.

Kritiker solcher Ansätze weisen darauf hin, dass die Mehrdeutigkeit Inhärent in der natürlichen Sprache ermöglicht es, Fehler in solchen Beweisen nicht erkannt zu werden. Oft können subtile Fehler in den Details auf niedriger Ebene vorhanden sein, die typischerweise durch solche Beweise übersehen werden. Darüber hinaus erfordert die Arbeit, die an der Herstellung eines so guten Beweises beteiligt ist, ein hohes Maß an mathematischer Raffinesse und Fachwissen.

Automatisierter Beweis

Im Gegensatz dazu besteht ein zunehmendes Interesse daran, mit automatisierten Mitteln Beweise für die Korrektheit solcher Systeme zu erstellen. Automatisierte Techniken fallen in drei allgemeine Kategorien:

  • Automatisierter Theorem beweisen, in dem ein System versucht, einen formalen Beweis von Grund auf neu zu erstellen, da eine Beschreibung des Systems, eine Reihe logischer Axiome und eine Reihe von Inferenzregeln.
  • Modellprüfung, in dem ein System bestimmte Eigenschaften durch eine umfassende Suche nach allen möglichen Staaten überprüft, dass ein System während seiner Ausführung eintreten könnte.
  • Abstrakte Interpretation, in dem ein System eine Überprüfung einer Verhaltenseigenschaft des Programms überprüft, wobei eine Fixpoint-Berechnung über ein (möglicherweise vollständiges) Gitter verwendet wird, das es darstellt.

Einige automatisierte Theoremprover erfordern Anleitung, welche Eigenschaften "interessant" genug sind, um zu verfolgen, während andere ohne menschliche Intervention arbeiten. Modellprüfer können sich schnell mit der Überprüfung von Millionen von uninteressanten Zuständen befassen, wenn sie nicht ein ausreichend abstraktes Modell erhalten.

Befürworter solcher Systeme argumentieren, dass die Ergebnisse eine größere mathematische Gewissheit haben als von Menschen produzierte Beweise, da alle mühsamen Details algorithmisch verifiziert wurden. Das für die Verwendung solcher Systeme erforderliche Training ist ebenfalls geringer als das, die für die Erstellung guter mathematischer Beweise von Hand erforderlich sind, wodurch die Techniken für eine breitere Vielfalt von Praktikern zugänglich sind.

Kritiker stellen fest, dass einige dieser Systeme sind Orakel: Sie machen die Wahrheit nach, geben diese Wahrheit jedoch keine Erklärung. Es gibt auch das Problem von "Überprüfung des Verifizierers"Wenn das Programm, das die Überprüfung hilft, selbst nicht bewiesen ist, kann es Grund geben, die Klang der erzeugten Ergebnisse zu bezweifeln. Einige moderne Modellprüfwerkzeuge erzeugen ein" Proof -Protokoll ", das jeden Schritt in ihrem Beweis beschreibt, und ermöglicht die Durchführung der Durchführung durchzuführen. mit geeigneten Werkzeugen, unabhängige Überprüfung.

Das Hauptmerkmal des abstrakten Interpretationsansatzes besteht darin, dass es eine Schallanalyse liefert, d. H. Es werden keine falschen Negative zurückgegeben. Darüber[12] schnelle Konvergenz zu bekommen.

Anwendungen

In verschiedenen Bereichen von Hardware und Software werden formale Methoden angewendet, einschließlich Router, Ethernet -Switches, Routing -Protokollen, Sicherheitsanwendungen und Microkernel des Betriebssystems wie z. B. Sel4. Es gibt mehrere Beispiele, in denen sie verwendet wurden, um die Funktionalität der in DCS verwendeten Hardware und Software zu überprüfen[Klarstellung erforderlich]. IBM Gebraucht ACL2ein Theorem -Prover in der AMD X86 Prozessorentwicklungsprozess. Intel verwendet solche Methoden, um seine Hardware und Firmware zu überprüfen (dauerhafte Software, die zu einem schreibgeschützten Speicher programmiert ist). Dansk Datamatik Center verwendete formale Methoden in den 1980er Jahren, um ein Compiler -System für die zu entwickeln ADA -Programmiersprache Das wurde ein langlebiges kommerzielles Produkt.[13][14]

Es gibt mehrere andere Projekte von NASA in denen formale Methoden angewendet werden, wie z. Lufttransportsystem der nächsten Generation, Unbemannte Flugzeugsystemintegration in das nationale Luftraumsystem,[15] und in der Luft koordinierte Konfliktlösung und Erkennung (Accord).[16] B-Methode mit Atelier b,[17] wird verwendet, um Sicherheitsautomatisms für die verschiedenen U -Bahnen zu entwickeln, die weltweit von installiert wurden Alstom und Siemensund auch für Gemeinsame Kriterien Zertifizierung und Entwicklung von Systemmodellen von Atmel und Stmicroelectronics.

Die formale Überprüfung wurde häufig von Hardware von den meisten bekannten Hardwareanbietern wie IBM verwendet. Intelund amd. Es gibt viele Hardwarebereiche, in denen Intel FMs verwendet hat, um die Arbeit der Produkte zu überprüfen, z. B. die parametrisierte Überprüfung des Cache-Kohärenten-Protokolls[18] Intel Core i7 Processor Execution Engine Validierung [19] (Verwendung von Theorem -Beweisen, BDDsund symbolische Bewertung), Optimierung für die Intel IA-64-Architektur unter Verwendung des Hollicht-Theorem-Provers,[20] und Überprüfung des Hochleistungs-Dual-Port-Gigabit-Ethernet-Controllers mit Unterstützung des PCI Express-Protokolls und der Intel Advance Management-Technologie unter Verwendung von Cadence.[21] In ähnlicher Weise hat IBM formale Methoden bei der Überprüfung von Krafttoren verwendet.[22] Register,[23] und funktionelle Überprüfung des IBM Power7 -Mikroprozessors.[24]

In der Softwareentwicklung

Im Software-Entwicklung, formale Methoden sind mathematische Ansätze zur Lösung von Software- (und Hardware-) Problemen bei den Anforderungen, Spezifikationen und Designstufen. Formale Methoden werden am wahrscheinlichsten auf sicherheitskritische oder sicherheitskritische Software und Systeme angewendet, wie z. Avionik -Software. Software -Sicherheitssicherungsstandards wie z. Do-178c ermöglicht die Verwendung formaler Methoden durch Ergänzung, und Gemeinsame Kriterien Mandatiert formale Methoden auf höchstem Kategorisierungsniveau.

Beispiele für formale Methoden für sequentielle Software sind die B-Methode, Die in verwendeten Spezifikationssprachen in automatisierter Theorem beweisen, HEBEN, und die Z Notation.

Im Funktionelle Programmierung, Eigentumsbasierte Tests hat die mathematische Spezifikation und die Tests (wenn nicht umfassende Tests) des erwarteten Verhaltens einzelner Funktionen ermöglicht.

Das Sprache der Objektbeschränkung (und Spezialisierungen wie z. Java -Modellierungssprache) hat ermöglicht, objektorientierte Systeme formell spezifiziert zu werden, wenn nicht unbedingt formell verifiziert.

Für gleichzeitige Software und Systeme, Petri Nets, Prozessalgebra, und endliche Staatsmaschinen (die basierend auf Automatenheorie - siehe auch Virtuelle endliche Staatsmaschine oder ereignisgesteuerte endliche Staatsmaschine) Spezifikation ausführbarer Software zulassen und kann zum Aufbau und Validieren von Anwendungsverhalten verwendet werden.

Ein weiterer Ansatz für formale Methoden in der Softwareentwicklung besteht darin, eine Spezifikation in irgendeiner Form von Logik zu schreiben - normalerweise eine Variation von Logik erster Ordnung (Fol) - und dann die Logik direkt auszuführen, als wäre es ein Programm. Das EULE Sprache basierend auf Beschreibung Logik (DL) ist ein Beispiel. Es wird auch gearbeitet, eine Version von englischer (oder eine andere natürliche Sprache) automatisch auf und aus der Logik zuzuordnen und die Logik direkt auszuführen. Beispiele sind Versuche kontrolliert Englischund Internet -Geschäftslogik, die nicht versuchen, den Wortschatz oder die Syntax zu kontrollieren. Ein Merkmal von Systemen, die die bidirektionale englisch-logische Mapping und die direkte Ausführung der Logik unterstützen, ist, dass sie ihre Ergebnisse auf Englisch oder wissenschaftlicher Ebene erläutern können.

Formale Methoden und Notationen

Es gibt eine Vielzahl von formalen Methoden und Notationen.

Spezifikationssprachen

Modellprüfer

  • ESBMC[25]
  • Malpas Software Static Analysis Toolset -Ein Modellprüfer in der Industriestärke, der zum formellen Nachweis von Sicherheitskritischen Systemen verwendet wird
  • KLOPFEN - Ein kostenloser Modellprüfer, Simulator und Verfeinerungsprüfer für gleichzeitige Systeme und CSP -Erweiterungen (z. B. gemeinsame Variablen, Arrays, Fairness)
  • DREHEN
  • Uppaal

Organisationen

Siehe auch

Verweise

  1. ^ Butler, R. W. (2001-08-06). "Was sind formale Methoden?". Abgerufen 2006-11-16.
  2. ^ Holloway, C. Michael. "Warum Ingenieure formelle Methoden berücksichtigen sollten" (PDF). 16. Konferenz für digitale Avioniksysteme (27. bis 30. Oktober 1997). Archiviert von das Original (PDF) am 16. November 2006. Abgerufen 2006-11-16. {{}}: Journal zitieren erfordert |journal= (Hilfe)
  3. ^ Monin, S. 3-4
  4. ^ X2r-2, lieferbar D5.1.
  5. ^ Daniel Jackson und Jeannette Wing, "Leichte formale Methoden", IEEE -Computer, April 1996
  6. ^ Vinu George und Rayford Vaughn, "Anwendung leichter formeller Methoden in der Anforderungstechnik" Archiviert 2006-03-01 am Wayback -Maschine, Übersprechen: Das Journal of Defense Software Engineering, Januar 2003
  7. ^ Daniel Jackson, "Legierung: Eine leichte Objektmodellierungsnotation", ACM -Transaktionen zur Software -Engineering und -Methodik (TOSEM), Band 11, Ausgabe 2 (April 2002), S. 256-290
  8. ^ Richard Denney, Erfolgsfälle mit Anwendungsfällen: intelligent arbeiten, um Qualität zu liefern, Addison-Wesley Professional Publishing, 2005, ISBN0-321-31643-6.
  9. ^ Sten Agerholm und Peter G. Larsen, "Ein leichter Ansatz für formale Methoden" Archiviert 2006-03-09 im Wayback -Maschine, Im Verfahren des internationalen Workshops zu aktuellen Trends bei angewandten formalen Methoden, Boppard, Deutschland, Springer-Verlag, Oktober 1998
  10. ^ Backus, J.W. (1959). "Die Syntax und Semantik der vorgeschlagenen internationalen algebraischen Sprache der Zürich ACM-GAMM-Konferenz". Verfahren der Internationalen Konferenz zur Informationsverarbeitung. UNESCO.
  11. ^ Knuth, Donald E. (1964), Backus Normal Form gegen Backus Naur Form. Kommunikation der ACM, 7 (12): 735–736.
  12. ^ A. Cortesi und M. Zanioli, Verbreiterung und Verengung von Operatoren für abstrakte Interpretation. Computersprachen, Systeme und Strukturen. Band 37 (1), S. 24–42, Elsevier, ISSN 1477-8424 (2011).
  13. ^ Bjørner, Abendessen; Gramm, Christus; OEST, OLE N.; Rystrøm, Leif (2011). "Dansk Datamatik Center". In Impagliazzo, John; Lundin, per; Wangler, Benkt (Hrsg.). Geschichte des nordischen Computers 3: IFIP -Fortschritte in der Informations- und Kommunikationstechnologie. Springer. S. 350–359.
  14. ^ Bjørner, Abendessen; Havelund, Klaus. "40 Jahre formaler Methoden: Einige Hindernisse und einige Möglichkeiten?". FM 2014: Formale Methoden: 19. Internationales Symposium, Singapur, 12. bis 16. Mai 2014. Proceedings (PDF). Springer. S. 42–61.
  15. ^ Gheorghe, A. V. & Ancel, E. (2008, November). Unbemannte Integration von Luftsystemen in das nationale Luftraumsystem. In Infrastruktursystemen und -diensten: Aufbau von Netzwerken für eine bessere Zukunft (Infra), 2008 erste internationale Konferenz über (S. 1-5). IEEE.
  16. ^ In der Luft koordinierte Konfliktlösung und Erkennung, http://shemesh.larc.nasa.gov/people/cam/accord/
  17. ^ "Atelier B". www.atelierb.eu.
  18. ^ C. T. Chou, P.K. Mannava, S. Park, “Eine einfache Methode zur parametrisierten Überprüfung von Cache -Kohärenzprotokollen”, Formale Methoden im computergestützten Design, S. 382–398, 2004.
  19. ^ Formale Überprüfung in der Intel® Core ™ i7 -Prozessorausführungsmotor -Validierung, http://cps-vo.org/node/1371, abgerufen am 13. September 2013.
  20. ^ J. Grundy, „Verifizierte Optimierungen für die Intel IA-64-Architektur“, in Theorem, die in höherer Ordnung logik, Springer Berlin Heidelberg, 2004, S. 215–232.
  21. ^ E. Seligman, I. Yarom, “Bekannte Methoden zur Verwendung von Cadence Conformal LEC”, Bei Intel.
  22. ^ C. Eisner, A. Nahir, K. Yorav, “Funktionale Überprüfung von macherischen Gated -Designs durch Kompositionelle Argumentation”, Computergestützte Überprüfung, Springer Berlin Heidelberg, S. 433–445.
  23. ^ P. C. Attie, H. Chockler, “Automatische Überprüfung der fehlertoleranten Registeremulationen”, Elektronische Notizen in Theoretical Information, Vol. 3, No. 149, Nr. 1, S. 49–60.
  24. ^ K. D. Schubert, W. Roesner, J. M. Ludden, J. Jackson, J. Buchert, V. Paruthi, B. Brock, “Funktionelle Überprüfung des IBM Power7 -Mikroprozessors und der Power7 -Multiprozessorsysteme”, IBM Journal of Research and Development, Vol. 55, Nr. 3.
  25. ^ "ESBMC". ESBMC.org.

Weitere Lektüre

Externe Links

Archivmaterial