Formale Programmüberprüfung in der Praxis

66

Als Softwareentwickler schreibe ich viel Code für Industrieprodukte. Relativ kompliziertes Zeug mit Klassen, Threads, einigen Designbemühungen, aber auch einigen Kompromissen für die Leistung. Ich teste viel und bin es leid zu testen. Daher interessierte ich mich für formale Proof-Tools wie Coq, Isabelle ... Könnte ich eines davon verwenden, um zu beweisen, dass mein Code fehlerfrei und fehlerfrei ist? damit? - Aber jedes Mal, wenn ich eines dieser Tools auschecke, bin ich nicht überzeugt, dass sie für die alltägliche Softwareentwicklung geeignet sind. Nun, das könnte nur ich sein, und ich suche nach Hinweisen / Meinungen / Ideen dazu :-)

Insbesondere habe ich den Eindruck, dass es eine enorme Investition erfordert, um die Objekte, Methoden ... des betrachteten Programms für den Prüfer richtig zu definieren, damit eines dieser Tools für mich funktioniert. Ich frage mich dann, ob dem Prüfer angesichts der Größe von allem, mit dem er zu tun haben würde, nicht einfach der Dampf ausgeht. Oder vielleicht müsste ich die Nebenwirkungen beseitigen (diese Beweiser-Tools scheinen mit deklarativen Sprachen wirklich gut zurechtzukommen), und ich frage mich, ob dies zu "bewährtem Code" führen würde, der nicht verwendet werden könnte, weil er nicht schnell oder nicht gut wäre klein genug. Außerdem habe ich nicht den Luxus, die Sprache zu ändern, mit der ich arbeite. Es muss Java oder C ++ sein. Ich kann meinem Chef nicht sagen, dass ich ab sofort in OXXXml codieren werde, da dies die einzige Sprache in ist Womit ich die Richtigkeit des Codes beweisen kann ...

Könnte jemand mit mehr Erfahrung mit formalen Proof-Tools einen Kommentar abgeben? Ich würde es LIEBEN , ein formales Prüferwerkzeug zu verwenden. Ich denke, sie sind großartig, aber ich habe den Eindruck, sie befinden sich in einem Elfenbeinturm, den ich aus dem niedrigen Graben von Java / C ++ nicht erreichen kann ... (PS: I auch LIEBE Haskell, OCaml ... verstehe nicht die falsche Idee: Ich bin ein Fan von deklarativen Sprachen und formalen Beweisen, ich versuche nur zu sehen, wie ich das für die Softwareentwicklung realistisch machen kann.

Update: Da dies ziemlich weit gefasst ist, versuchen wir die folgenden spezifischeren Fragen: 1) Gibt es Beispiele für die Verwendung von Testern, um die Korrektheit industrieller Java / C ++ - Programme zu beweisen? 2) Wäre Coq für diese Aufgabe geeignet? 3) Wenn Coq geeignet ist, sollte ich das Programm zuerst in Coq schreiben und dann C ++ / Java aus Coq generieren? 4) Könnte dieser Ansatz Threading- und Leistungsoptimierungen bewältigen?

Frank
quelle
3
Ich verstehe und schätze Ihr Problem, aber ich verstehe nicht, worauf diese Frage abzielt (als SE-Beitrag). Diskussion? Erfahrung? Weder ist für SE geeignet. Das "Was kann ich tun?" Ton lässt mich das Gefühl haben, dass dies auch eine zu breite Frage ist.
Raphael
3
Ich verstehe ... Ich stimme zu, dass diese Frage nicht klar formuliert wurde. Nehmen wir also an: 1) Gibt es Beispiele für die Verwendung von Testern, um die Korrektheit industrieller Java / C ++ - Programme zu beweisen? 2) Wäre Coq für diese Aufgabe geeignet? 3) Wenn Coq geeignet ist, sollte ich das Programm zuerst in Coq schreiben und Coq daraus C ++ / Java generieren lassen? 4) Konnte dieser Ansatz Threading- und Leistungsoptimierungen bewältigen?
Frank
2
Das sind also vier Fragen. 1) ist bei Software Engineering wahrscheinlich besser dran, da Sie hier wahrscheinlich nicht auf (viele) Branchenprofis treffen. 2) schmeckt etwas subjektiv, aber wir können Leute hier haben, die eine objektive Perspektive anbieten können. 3) ist, soweit ich das beurteilen kann, völlig subjektiv. 4) Ist eine nette Frage für diese Seite. Fazit: Bitte trennen Sie Ihre Fragen, gehen Sie mit dem ersten Schritt zum Software Engineering und überlegen Sie, ob Sie hier eine objektive (!) Antwort erwarten können (!), Bevor Sie 2) posten.
Raphael
10
Sie beschreiben den Traum der formalen Verifizierung, aber wir sind noch weit davon entfernt, dort zu sein. AFAIK, Programmüberprüfung ist eine nicht routinemäßige Aufgabe und gilt nur für sehr einfache Programme. Trotzdem denke ich, dass diese Frage genau richtig für die Website ist, und ich würde jemanden aus dem Bereich begrüßen, der die Grenzen seines Fachgebiets einräumt und den Stand der Technik und die Einschränkungen erklärt (möglicherweise durch Verknüpfung mit einer Umfrage) ).
Yuval Filmus
9
Das Problem beim Überprüfen von C ++ - Programmen besteht darin, dass C ++ keine genau definierte Sprache ist. Ich denke nicht, dass eine Verifizierung in großem Maßstab möglich ist, bevor nicht viele Teile von Softwaresystemen (Betriebssystem, Bibliotheken, Programmiersprachen) tatsächlich neu gestaltet wurden, um die Verifizierung zu unterstützen. Bekanntlich können Sie nicht einfach 200000 Codezeilen auf jemanden ausgeben und "Verify!" Sagen. Sie müssen gemeinsam Code verifizieren und schreiben und Ihre Programmiergewohnheiten an die Tatsache anpassen, dass Sie auch verifizieren.
Andrej Bauer

Antworten:

35

Ich werde versuchen, einige Ihrer Fragen kurz zu beantworten. Bitte bedenken Sie, dass dies nicht ausschließlich mein Forschungsgebiet ist, so dass einige meiner Informationen möglicherweise veraltet / falsch sind.

  1. Es gibt viele Tools, die speziell entwickelt wurden, um die Eigenschaften von Java und C ++ formal zu beweisen.

    Allerdings muss ich hier einen kleinen Exkurs machen: Was bedeutet es, die Richtigkeit eines Programms zu beweisen? Die Java-Typprüfung beweist eine formale Eigenschaft eines Java-Programms, dass bestimmte Fehler, wie das Hinzufügen von a floatund an int, niemals auftreten können! Ich stelle mir vor, Sie interessieren sich für viel stärkere Eigenschaften, nämlich dass Ihr Programm niemals in einen unerwünschten Zustand geraten kann oder dass die Ausgabe einer bestimmten Funktion einer bestimmten mathematischen Spezifikation entspricht. Kurz gesagt, es gibt ein breites Spektrum dessen, was es bedeuten kann, "ein Programm als richtig zu beweisen", von einfachen Sicherheitseigenschaften bis hin zum vollständigen Beweis, dass das Programm eine detaillierte Spezifikation erfüllt.

    Nun gehe ich davon aus, dass Sie daran interessiert sind, starke Eigenschaften Ihrer Programme zu beweisen. Wenn Sie an Sicherheitseigenschaften interessiert sind (Ihr Programm kann einen bestimmten Status nicht erreichen), ist die Modellprüfung im Allgemeinen der beste Ansatz . Wenn Sie jedoch das Verhalten eines Java-Programms vollständig spezifizieren möchten, verwenden Sie am besten eine Spezifikationssprache für diese Sprache, beispielsweise JML . Es gibt solche Sprachen zum Spezifizieren des Verhaltens von C-Programmen, zum Beispiel ACSL , aber ich kenne mich mit C ++ nicht aus.

  2. Sobald Sie Ihre Spezifikationen haben, müssen Sie nachweisen, dass das Programm mit dieser Spezifikation übereinstimmt.

    Dazu benötigen Sie ein Tool, das sowohl Ihre Spezifikation als auch die Betriebssemantik Ihrer Sprache (Java oder C ++) formell versteht, um den Angemessenheitssatz auszudrücken , nämlich, dass die Ausführung des Programms die Spezifikation respektiert.

    Dieses Tool sollte es Ihnen auch ermöglichen, den Beweis dieses Theorems zu formulieren oder zu generieren. Nun sind diese beiden Aufgaben (Spezifizieren und Prüfen) ziemlich schwierig, so dass sie oft in zwei Teile geteilt werden:

    • Ein Tool, das den Code, die Spezifikation und den Angemessenheitssatz analysiert. Wie Frank bereits erwähnte, ist Krakatoa ein Beispiel für ein solches Werkzeug.

    • Ein Werkzeug, das den Satz (die Sätze) automatisch oder interaktiv beweist. Coq interagiert auf diese Weise mit Krakatoa, und es gibt einige leistungsstarke automatisierte Tools wie Z3, die ebenfalls verwendet werden können.

    Ein (kleiner) Punkt: Es gibt einige Theoreme, die viel zu schwierig sind, um mit automatisierten Methoden bewiesen zu werden, und automatische Theoremprüfer weisen gelegentlich Fehler auf, die sie weniger vertrauenswürdig machen. Dies ist ein Bereich, in dem Coq im Vergleich glänzt (aber es ist nicht automatisch!).

  3. Wenn Sie Ocaml-Code generieren möchten, schreiben Sie auf jeden Fall zuerst in Coq (Gallina) und extrahieren Sie dann den Code. Coq ist jedoch schrecklich darin, C ++ oder Java zu generieren, wenn es überhaupt möglich ist.

  4. Können die oben genannten Tools Threading- und Leistungsprobleme lösen? Wahrscheinlich nicht, Performance- und Threading-Probleme lassen sich am besten mit speziell entwickelten Tools lösen, da es sich um besonders schwierige Probleme handelt. Ich bin mir nicht sicher, ob ich hier Tools empfehlen kann, obwohl Martin Hofmanns PolyNI- Projekt interessant erscheint.

Fazit: Die formale Überprüfung von Java- und C ++ - Programmen in der "realen Welt" ist ein großes und gut entwickeltes Gebiet, und Coq eignet sich für Teile dieser Aufgabe. Eine übergeordnete Übersicht finden Sie hier zum Beispiel.

Cody
quelle
Vielen Dank für diesen Beitrag und die Referenzen, die Sie hinzugefügt haben. Meines Erachtens ist es das Ziel der Softwareentwickler, Systeme schnell freizugeben, die 1) immer korrekte Ergebnisse liefern, 2) niemals versagen. Ich könnte hier ein Regressionsproblem sehen, bei dem Sie möglicherweise beweisen möchten, dass die Spezifikation selbst "fehlerfrei" ist. Sprache dafür, dann noch eine ...
Frank
6
Das Problem ist, dass das, was der Benutzer "will", normalerweise nicht in einer formalen Sprache ausgedrückt wird! Es gibt im Allgemeinen keine formelle Antwort auf die Frage: "Entspricht diese formelle Spezifikation meiner informellen Idee?". Es ist möglich, eine formale Spezifikation zu testen und zu beweisen, dass sie bestimmte mathematische Eigenschaften hat, aber letztendlich müssen Sie die Mathematik mit der realen Welt in Beziehung setzen, was ein nicht formaler Prozess ist.
Cody
Ja, natürlich - mir war immer klar, dass die formalen Methoden nur an einem genau definierten Punkt beginnen können. Ob diese Spezifikation den bewussten / unbewussten / unentdeckten Bedürfnissen der Benutzer im wirklichen Leben entspricht oder nicht, ist ein weiteres Problem, das mit formalen Methoden nicht angegangen werden kann (aber sicherlich ein Problem für Ingenieure).
Frank
Ein Satz ist per Definition ein bewiesener Satz. Sie wollen also wahrscheinlich nicht "den Satz beweisen".
Nr.
@nbro Wikipedia scheint Ihnen zuzustimmen. Mathworld definiert einen Satz jedoch als einen Satz, der " durch akzeptierte mathematische Operationen als wahr nachgewiesen werden kann ". In diesem Fall ist es nicht nur möglich, Beweise für Theoreme zu liefern, sondern auch notwendig, sie so zu nennen! :) (das ist natürlich ein Gegenstreit)
cody 10.08.17
15

Ich möchte drei bemerkenswerte Anwendungen formaler Methoden / formaler Verifizierungsinstrumente in der Industrie oder in nicht trivialen realen Systemen erwähnen. Beachten Sie, dass ich wenig Erfahrung mit diesem Thema habe und sie nur aus dem Lesen von Artikeln lerne.

  1. Das Open-Source-Tool Java Pathfinder (kurz JPF), das 2005 von der NASA veröffentlicht wurde, ist ein System zur Überprüfung von ausführbaren Java-Bytecode-Programmen (siehe Java Pathfinder @ wiki ). Es wurde verwendet, um Inkonsistenzen in der Executive-Software für den K9 Rover bei der NASA Ames zu erkennen.

  2. Dieses Dokument: Verwenden der Modellprüfung zum Auffinden schwerwiegender Dateisystemfehler @ OSDI'04 zeigt, wie die Modellprüfung zum Auffinden schwerwiegender Fehler in Dateisystemen verwendet wird. Ein System namens FiSC wird auf drei weit verbreitete, stark getestete Dateisysteme angewendet: ext3, JFS und ReiserFS, und es werden 32 schwerwiegende Fehler gefunden. Es wurde mit dem Best Paper Award ausgezeichnet.

  3. In diesem Dokument: Verwendung formaler Methoden durch Amazon Web Services @ CACM'15 wird beschrieben, wie AWS formale Methoden auf seine Produkte wie S3, DynamoDB, EBS und Internal Distributed Lock Manager anwendet. Es konzentriert sich auf das TLA + -Tool von Lamport . Übrigens hat Lamport seine eigene TLA-Toolbox intensiv genutzt. Er gibt häufig eine (ziemlich vollständige) formale Überprüfung der von ihm (sowie von den Mitautoren) vorgeschlagenen Algorithmen / Theoreme in der TLA in den Anhängen zu den Arbeiten.

Hengxin
quelle
4

Eine formale Spezifikation eines Programms ist (mehr oder weniger) ein Programm, das in einer anderen Programmiersprache geschrieben ist. Infolgedessen wird die Spezifikation sicherlich ihre eigenen Fehler enthalten.

Der Vorteil der formalen Überprüfung besteht darin, dass das Programm und die Spezifikation zwei separate Implementierungen sind und ihre Fehler unterschiedlich sind. Aber nicht immer: Eine häufig vorkommende Fehlerquelle, übersehene Fälle, trifft häufig zu. Daher ist formale Überprüfung kein Allheilmittel: Es kann immer noch eine nicht unbedeutende Anzahl von Fehlern übersehen.

Ein Nachteil der formalen Verifizierung besteht darin, dass sie etwa die doppelte Implementierungskosten verursachen kann, wahrscheinlich mehr (Sie benötigen einen Spezialisten für formale Spezifikationen und müssen die mehr oder weniger experimentellen Tools verwenden, die mit ihr geliefert werden; das wird nicht billig ).

Ich würde raten, Testfälle und Gerüste so einzurichten, dass sie automatisch ausgeführt werden, wäre eine bessere Nutzung Ihrer Zeit.

vonbrand
quelle
Der Vorteil der formalen Verifizierung besteht darin, dass ... Ein zweiter Nachteil der formalen Verifizierung besteht darin, dass ... dies verwirrend ist.
Hengxin
Ich denke, dass die Nichtübereinstimmung zwischen Spezifikation und informeller Aufgabe ein Problem der Softwareanforderungsanalyse und kein Problem der Programmierung ist.
Kaveh
3

Die formale Verifizierung ist jetzt für Programme möglich, die als Teilmenge von C ++ für sicherheitskritische eingebettete Systeme geschrieben wurden. Siehe http://eschertech.com/papers/CanCPlusPlusBeMadeAsSafeAsSpark.ppt für eine kurze Präsentation und http://eschertech.com/papers/CanCPlusPlusBeMadeAsSafeAsSpark.pdf für das gesamte Papier.

dc42
quelle
5
Danke für die Links. Zumindest ein kurzer Überblick über deren Inhalt wäre nützlich, um sich vor dem Verrotten von Links zu schützen, zumal Ihre Links zu einer Unternehmenswebsite führen: Diese werden in der Regel regelmäßig neu organisiert und töten alle Links auf der Website.
David Richerby
2

Sie stellen ein paar verschiedene Fragen. Ich bin damit einverstanden, dass formale Überprüfungsmethoden für industrielle / kommerzielle Anwendungen nicht so verbreitet sind. man sollte sich jedoch darüber im Klaren sein, dass viele "formale Verifizierungs" -Prinzipien in Compilern eingebaut sind, um die Programmkorrektheit zu bestimmen! Wenn Sie also einen modernen Compiler verwenden, verwenden Sie in gewisser Weise einen Großteil des Standes der Technik bei der formalen Verifizierung.

Sie sagen, "Ich bin es leid zu testen", aber die formale Verifizierung ist kein Ersatz für das Testen. In gewisser Weise ist es eine Variation des Testens.

Sie erwähnen Java. Es gibt viele erweiterte formale Überprüfungsmethoden, die in ein Java-Überprüfungsprogramm namens FindBugs integriert sind und in der Tat über große Codebasen ausgeführt werden können. Beachten Sie, dass sowohl "falsch positive als auch falsch negative Ergebnisse" angezeigt werden und die Ergebnisse von einem menschlichen Entwickler überprüft / analysiert werden müssen. Beachten Sie jedoch, dass es in der Regel "Antipattern" gibt, die im Code ohnehin vermieden werden sollten, auch wenn es sich nicht um echte Funktionsstörungen handelt.

Sie erwähnen Ihre spezielle Anwendung nicht mehr als "industriell". Die formale Überprüfung in der Praxis hängt in der Regel von der jeweiligen Anwendung ab.

Formale Verifikationstechniken scheinen in EE weit verbreitet zu sein, um die Schaltungskorrektheit zu beweisen, z. B. im Mikroprozessordesign.

Hier ist ein Beispiel einer Übersicht über formale Überprüfungsinstrumente im EE-Bereich von Lars Philipson .

vzn
quelle
2
Es ist irreführend zu sagen, dass "viele" formale Überprüfungsprinzipien "in Compilern eingebaut sind, um die Programmkorrektheit zu bestimmen". Sie beziehen sich auf die statische Typprüfung, die einige Compiler durchführen, aber die auf diese Weise überprüften Eigenschaften sind recht einfach, z. B. das Vermeiden des Hinzufügens einer Zahl und eines Strings. Dies ist hilfreich, aber weit entfernt von dem, was normalerweise unter "formaler Verifizierung" zu verstehen ist.
Martin Berger
2
bezog sich nicht speziell auf die statische Typprüfung, obwohl dies ein einfaches / allgemeines Beispiel ist. Die imho-Compiler-Optimierungstechniken, die weit verbreitet und fortgeschritten sind, ähneln in etwa den formalen Verifizierungsprinzipien, da sie fortgeschrittene Techniken zur Bestimmung / Darstellung der Gleichwertigkeit optimierter Programmvarianten beinhalten. Es scheint also wichtig zu sein, das Problem des "Verschiebens von Torpfosten" hier zu vermeiden und nicht anzunehmen, dass der Compiler dies tut oder in den Compiler integriert ist, sondern dass dies keine formale Überprüfung ist.
vzn
2
Ich bin mir einig, dass dies kein allgemeines Verständnis ist. Die Optimierungstechniken erstellen grob ein Modell des Programmverhaltens, z. B. einer Schleife oder eines Unterprogramms, und optimieren dieses Modell und generieren dann neuen Code, der nachweislich äquivalent ist. Einige dieser Optimierungen sind daher recht raffiniert, wenn es darum geht, Code neu zu ordnen. Für mich verwenden sie formale Verifizierungsprinzipien. Es scheint viele andere Beispiele für formale Überprüfungsmethoden im Compiler zu geben ... Die ursprüngliche Frage stellte viele verschiedene Fragen, wie viele festgestellt haben. Ich versuche definitiv nicht, alle darin enthaltenen Fragen zu beantworten.
vzn
2
Übrigens
3
das ist "der traum der formalen verifikation", auf den sich filmus oben bezieht, imho eine chimäre abstraktion, und die pragmatische / utilitaristische / realistische industrie erkennt sie weitgehend als solche an. Es ist seit Jahrzehnten bekannt, dass große Codebasen von Natur aus Bugs / Defekte pro K-Zeilen Code aufweisen, und dies wird sich nie ändern, egal wie Theorie / Technologie voranschreiten, es ist eine Tatsache menschlicher Natur. und tatsächlich haben von Menschen geschaffene mathematische Theoreme die gleichen Eigenschaften, obwohl dies nicht allgemein anerkannt wird! xy
VZN
1

Möglicherweise kann ein Modellprüfer hilfreich sein.

http://alloytools.org/documentation.html Alloy ist ein Modellprüfer.

Eine schöne Präsentation, die das Konzept der Modellprüfung mit Alloy erklärt: https://www.youtube.com/watch?v=FvNRlE4E9QQ

Zu derselben Familie von Tools gehört auch das eigenschaftsbasierte Testen. Sie alle versuchen, ein Gegenbeispiel für das angegebene Spezifikationsmodell Ihrer Software zu finden.

Tick ​​Tack
quelle