In der Informatik, spezifisch Softwaretechnik, sind formelle Methoden eine besondere Art von mathematischen Techniken für die Spezifizierung, Entwicklung und Überprüfung der Software und Hardware-Systeme. Der Gebrauch von formellen Methoden für die Software und das Hardware-Design wird durch die Erwartung motiviert, die, als in anderen Technikdisziplinen, passende mathematische Analyse durchführend, zur Zuverlässigkeit und Robustheit eines Designs beitragen kann. Jedoch bedeuten die hohen Kosten, formelle Methoden zu verwenden, dass sie gewöhnlich nur in der Entwicklung von Systemen der hohen Integrität verwendet werden, wo Sicherheit oder Sicherheit von am meisten äußerster Wichtigkeit sind.

Formelle Methoden werden am besten als die Anwendung einer ziemlich breiten Vielfalt von theoretischen Informatik-Grundlagen, in besonderen Logikrechnungen, formellen Sprachen, Automaten-Theorie, und Programm-Semantik, sondern auch Typ-Systemen und algebraischen Datentypen zu Problemen in der Software und Hardware-Spezifizierung und Überprüfung beschrieben.

Taxonomie

Formelle Methoden können an mehreren Niveaus verwendet werden:

Niveau 0: Formelle Spezifizierung kann übernommen werden und dann ein Programm, das davon informell entwickelt ist. Das ist formelle Methoden lite synchronisiert worden. Das kann die rentabelste Auswahl in vielen Fällen sein.

Niveau 1: Formelle Entwicklung und formelle Überprüfung können verwendet werden, um ein Programm auf eine mehr formelle Weise zu erzeugen. Zum Beispiel können Beweise von Eigenschaften oder Verbesserung von der Spezifizierung bis ein Programm übernommen werden. Das kann in Systemen der hohen Integrität am passendsten sein, die Sicherheit oder Sicherheit einschließen.

Niveau 2: Lehrsatz provers kann verwendet werden, um völlig formelle maschinenkarierte Beweise zu übernehmen. Das kann sehr teuer sein und ist nur praktisch lohnend, wenn die Kosten von Fehlern (z.B, in kritischen Teilen des Mikroprozessor-Designs) äußerst hoch sind.

Die weitere Information darüber wird unten ausgebreitet.

Als mit der Programmiersprache-Semantik können Stile von formellen Methoden wie folgt grob klassifiziert werden:

• Semantik von Denotational, in der die Bedeutung eines Systems in der mathematischen Theorie von Gebieten ausgedrückt wird. Befürworter solcher Methoden verlassen sich auf die gut verstandene Natur von Gebieten, um Bedeutung dem System zu geben; Kritiker weisen darauf hin, dass nicht jedes System als eine Funktion intuitiv oder natürlich angesehen werden kann.
• Betriebliche Semantik, in der die Bedeutung eines Systems als eine Folge von Handlungen eines (vermutlich) einfacheren rechenbetonten Modells ausgedrückt wird. Befürworter solcher Methoden weisen zur Einfachheit ihrer Modelle als ein Mittel zur ausdrucksvollen Klarheit hin; Kritiker erwidern, dass das Problem der Semantik gerade verzögert worden ist (wer definiert die Semantik des einfacheren Modells?).
• Axiomatische Semantik, in der die Bedeutung des Systems in Bezug auf Vorbedingungen und Postbedingungen ausgedrückt wird, die vorher und nach dem System wahr sind, führt eine Aufgabe beziehungsweise durch. Befürworter bemerken die Verbindung zur klassischen Logik; Kritiker bemerken, dass solche Semantik nie wirklich beschreibt, was ein System tut (bloß, was vorher und später wahr ist).

Formelle Leichtgewichtsmethoden

Einige Praktiker glauben, dass die formelle Methode-Gemeinschaft volle Formalisierung einer Spezifizierung oder Designs überbetont hat. Sie behaupten, dass das Ausdrucksvolle der Sprachen beteiligt, sowie die Kompliziertheit der Systeme, die modellieren werden, volle Formalisierung eine schwierige und teure Aufgabe macht. Als ein alternativer, verschiedener Leichtgewichtler sind formelle Methoden, die teilweise Spezifizierung und eingestellte Anwendung betonen, vorgeschlagen worden. Beispiele dieser Leichtgewichtsannäherung an formelle Methoden schließen die Legierungsgegenstand-Modellieren-Notation, die Synthese von Denney von einigen Aspekten der Z Notation mit dem Gebrauch-Fall gesteuerte Entwicklung und der CSK VDM Werkzeuge ein.

Gebrauch

Formelle Methoden können an verschiedenen Punkten durch den Entwicklungsprozess angewandt werden.

Spezifizierung

Formelle Methoden können verwendet werden, um eine Beschreibung des Systems zu geben, das an beliebigem Niveau (S) des gewünschten Details zu entwickeln ist. Diese formelle Beschreibung kann verwendet werden, um weitere Entwicklungstätigkeiten zu führen (sieh folgende Abteilungen); zusätzlich kann es verwendet werden, um nachzuprüfen, dass die Voraussetzungen für das System, das wird entwickelt, völlig und genau angegeben worden sind.

Das Bedürfnis nach formellen Spezifizierungssystemen ist seit Jahren bemerkt worden. Im Algol 58 Bericht hat John Backus eine formelle Notation präsentiert, um Programmiersprache-Syntax zu beschreiben (später hat Backus genannt Normale Form hat dann Backus-Naur Form (BNF) umbenannt). Backus hat auch geschrieben, dass eine formelle Beschreibung der Bedeutung von syntaktisch gültigen Algol-Programmen rechtzeitig für die Einschließung in den Bericht nicht vollendet wurde. "Deshalb wird die formelle Behandlung der Semantik von gesetzlichen Programmen in eine nachfolgende Zeitung eingeschlossen." Es ist nie erschienen.

Entwicklung

Sobald eine formelle Spezifizierung erzeugt worden ist, kann die Spezifizierung als ein Führer verwendet werden, während das konkrete System während des Designprozesses entwickelt (d. h., normalerweise in der Software, sondern auch potenziell in der Hardware begriffen wird). Zum Beispiel:

• Wenn die formelle Spezifizierung in einer betrieblichen Semantik ist, kann das beobachtete Verhalten des konkreten Systems im Vergleich zum Verhalten der Spezifizierung sein (der selbst rechtskräftig sein sollte oder simulateable). Zusätzlich können die betrieblichen Befehle der Spezifizierung der direkten Übersetzung in den rechtskräftigen Code zugänglich sein.
• Wenn die formelle Spezifizierung in einer axiomatischen Semantik ist, können die Vorbedingungen und Postbedingungen der Spezifizierung Behauptungen im rechtskräftigen Code werden.

Überprüfung

Sobald eine formelle Spezifizierung entwickelt worden ist, kann die Spezifizierung als die Basis verwendet werden, um Eigenschaften der Spezifizierung (und hoffentlich durch die Schlussfolgerung das entwickelte System) zu beweisen.

Von den Menschen geleiteter Beweis

Manchmal ist die Motivation, für die Genauigkeit eines Systems zu beweisen, nicht das offensichtliche Bedürfnis nach der Beruhigung der Genauigkeit des Systems, aber ein Wunsch, das System besser zu verstehen. Folglich werden einige Beweise der Genauigkeit im Stil des mathematischen Beweises erzeugt: handschriftlich (oder Schriftsatz), natürliche Sprache mit einem Niveau der für solche Beweise üblichen Zwanglosigkeit verwendend. Ein "guter" Beweis ist derjenige, der lesbar und durch andere menschliche Leser verständlich ist.

Kritiker solcher Annäherungen weisen darauf hin, dass die natürlicher Sprache innewohnende Zweideutigkeit Fehlern erlaubt, in solchen Beweisen unentdeckt zu sein; häufig können feine Fehler in den auf niedriger Stufe durch solche Beweise normalerweise überblickten Details da sein. Zusätzlich verlangt die am Produzieren solch eines guten Beweises beteiligte Arbeit ein hohes Niveau der mathematischen Kultiviertheit und des Gutachtens.

Automatisierter Beweis

Im Gegensatz, dort vergrößert Interesse am Produzieren von Beweisen der Genauigkeit solcher Systeme durch automatisierte Mittel. Automatisierte Techniken fallen in zwei allgemeine Kategorien:

• Automatisierter Lehrsatz-Beweis, in dem ein System versucht, einen formellen Beweis von Kratzer, in Anbetracht einer Beschreibung des Systems, der einer Reihe logischen Axiome und der einer Reihe von Interferenzregeln zu erzeugen.
• Musterüberprüfung, in der ein System bestimmte Eigenschaften mittels einer erschöpfenden Suche aller möglichen Staaten nachprüft, in die ein System während seiner Ausführung eingehen konnte.

Ein automatisierter Lehrsatz provers verlangt Leitung, betreffs deren Eigenschaften "interessant" genug sind fortzufahren, während andere ohne menschliches Eingreifen arbeiten. Musterkontrolleure können sich in die Überprüfung von Millionen von langweiligen Staaten wenn nicht gegeben ein genug abstraktes Modell schnell verlieren.

Befürworter solcher Systeme behaupten, dass die Ergebnisse größere mathematische Gewissheit haben als von den Menschen erzeugte Beweise, seitdem alle langweiligen Details algorithmisch nachgeprüft worden sind. Die Ausbildung, die erforderlich ist, solche Systeme zu verwenden, ist auch weniger als das erforderlich, gute mathematische Beweise mit der Hand zu erzeugen, die für eine breitere Vielfalt von Praktikern zugänglichen Techniken machend.

Kritiker bemerken, dass einige jener Systeme Orakeln ähnlich sind: Sie machen eine Verkündigung der Wahrheit, geben noch keine Erklärung dieser Wahrheit. Es gibt auch das Problem, "den verifier nachzuprüfen"; wenn das Programm, das in der Überprüfung hilft, selbst unbewiesen ist, kann es Grund geben, die Stichhaltigkeit der erzeugten Ergebnisse zu bezweifeln. Einige moderne Musterüberprüfungswerkzeuge erzeugen einen "Probeklotz", über jeden Schritt in ihrem Beweis ausführlich berichtend, es möglich machend, in Anbetracht passender Werkzeuge, unabhängiger Überprüfung zu leisten.

Kritiken

Das Feld von formellen Methoden hat seine Kritiker. Handschriftliche Beweise der Genauigkeit brauchen bedeutende Zeit (und so Geld), um, mit dem beschränkten Dienstprogramm außer dem Sichern der Genauigkeit zu erzeugen. Das macht formelle Methoden, um wahrscheinlicher in Feldern verwendet zu werden, wo es möglich ist, automatisierte Beweise mit der Software, oder in Fällen durchzuführen, wo die Kosten einer Schuld hoch sind. Beispiel: In der Eisenbahn-Technik- und Raumfahrttechnik können unentdeckte Fehler Tod herbeiführen, so sind formelle Methoden in diesem Feld populärer als in anderen Anwendungsgebieten.

Formelle Methoden und Notationen

Es gibt eine Vielfalt von formellen Methoden und verfügbaren Notationen.

Spezifizierungssprachen

• Abstrakte Staatsmaschinen (ASMs)
• ANSI/ISO C Specification Language (ACSL)
• Legierung
• B-Methode
• CADP
• Common Algebraic Specification Language (CASL)
• Prozess-Rechnungen
• CSP
• LOTOS
• π-calculus
• Schauspieler-Modell
• Esterel
• Glanz
• mCRL2
• Vollkommener Entwickler
• Netze von Petri
• ERHEBEN SIE
• BEFEUERN SIE Ada
• Spezifizierung und Beschreibungssprache
• Zeitliche Logik von Handlungen (TLA)
• USL
• VDM
• VDM-SL
• VDM ++
• Z Notation
• Rebeca das Modellieren der Sprache

Musterkontrolleure

• DREHUNG
• RICHTIG ist ein starker freier Musterkontrolleur, Simulator und Verbesserungskontrolleur für gleichzeitige Systeme und CSP Erweiterungen (z.B geteilte Variablen, Reihe, Schönheit).
• MALPAS Software Statische Analyse Toolset ist ein Industriekraft-Musterkontrolleur, der für den Formellen Beweis der Sicherheit kritische Systeme verwendet ist

Siehe auch

• Automatisierter Lehrsatz, der sich erweist
• Design durch den Vertrag
• Formelle Spezifizierung
• Formelle Überprüfung
• Formelles System
• Modell, das überprüft
• Softwaretechnik
• Spezifizierungssprache

Weiterführende Literatur

• Jean François Monin und Michael G. Hinchey, formelle Methoden, Springer, 2003, internationale Standardbuchnummer 1-85233-247-6 Verstehend.
• Jonathan P. Bowen und Michael G. Hinchey, Formelle Methoden. In Allen B. Tucker dem Jüngeren. (Hrsg.). Informatik-Handbuch, 2. Ausgabe, Abschnitt XI, Softwaretechnik, Kapitel 106, Seiten 106-1 - 106-25, Hausierer & Saal / CRC Presse, Vereinigung, um Maschinerie, 2004 Zu schätzen.
• Michael G. Hinchey, Jonathan P. Bowen, und Emil Vassev, Formelle Methoden. In Philip A. Laplante (Hrsg.). Enzyklopädie der Software Engineering, Taylor & Francis, 2010, Seiten 308-320.

Links

• Formelle Methoden Wiki
• Liste von formellen Methoden und Werkzeugen
• Formelle Methode-Veröffentlichungen
• "Who is Who" in formellen Methoden
• Formal Methods Europe (FME)

• Formelles Methode-Schlüsselwort auf Microsoft Academic Search
• Foldoc:formal Methoden