Formale Verifikation ist nicht verifizierbar

Formal Verification Is Not Verifiable

KI hat formale Verifikation in den Mainstream gebracht – doch der Begriff „formal verifiziert“ ist irreführend. Der Autor argumentiert, dass formale Verifikation zwar starke Allaussagen trifft, aber auf schwer prüfbaren Komponenten wie Definitionen, Modellen und Provern beruht. Testing hingegen liefert einen überprüfbaren Bug-Report. Er plädiert dafür, den Begriff abzuschaffen und präzise von „formaler Verifikation bestimmter Eigenschaften“ zu sprechen, mit klaren Angaben zu Trusted Computing Base und Grenzen.

Es ist meine Meinung, dass wir so schnell wie möglich den Begriff „formal verifizierte Software“ abschaffen müssen; Nuancen müssen entstehen.
  1. johnbender

    > Das erlaubt es uns, (1) die Modellierung der Semantik der Hochsprache zu umgehen, wir können stattdessen die Semantik der Maschine modellieren – vermutlich einfachere Semantik

    ISAs sind ziemlich kompliziert und das Nachdenken über Programme in diesem Kontext ist schwierig, weshalb wir Hochsprachen haben.

    > Diese Unterscheidung in der Terminologie war früher eine umgangssprachlich akzeptierte Vorstellung: Wenn wir hörten „CompCert ist ein formal verifizierter Compiler“ oder „seL4 ist ein formal verifizierter Mikrokernel“, gingen wir davon aus, dass die Autoren keine leeren oder trivialen Eigenschaften verifiziert hatten, weil die Arbeit der Verifikation selbst einem hohen Standard unterlag, der den Ruf des Forschers stark beeinflusste.

    CompCert wurde auch umfangreich empirisch evaluiert, um die Theoreme zu überprüfen. Berühmt ist das CSmith-Paper (https://users.cs.utah.edu/~regehr/papers/pldi11-preprint.pdf), das dieses recht treffende Zitat enthält:

    > Anfang 2011 ist die in Entwicklung befindliche Version von CompCert der einzige Compiler, den wir getestet haben, bei dem Csmith keine Fehlercode-Fehler finden kann. Das liegt nicht an mangelnden Bemühungen: Wir haben etwa sechs CPU-Jahre für diese Aufgabe aufgewendet. Die scheinbare Unzerbrechlichkeit von CompCert stützt ein starkes Argument dafür, dass die Entwicklung von Compiler-Optimierungen innerhalb eines Beweisframeworks, in dem Sicherheitsprüfungen explizit und maschinell überprüft werden, greifbare Vorteile für Compiler-Nutzer hat.

    Bei meiner Arbeit haben wir dies auf CPU-Jahrtausende ausgedehnt. Ich beeile mich hinzuzufügen, dass dies natürlich nicht die Möglichkeit schlecht geformter Annahmen in der Semantik usw. ausschließt (es ist empirisch aft […]

  2. mjb

    > Für jede erststufige universell quantifizierte Eigenschaft eines Programms, die wir als property-based Test schreiben können, denke ich, werden wir in der Lage sein, Beweise auf Binärebene zu generieren, gegen Architekturmodelle, die selbst durch Millionen von Teststunden validiert wurden. Die Herausforderung, dies auf Multithread-Programme, verteilte Systeme, [..] auszudehnen, wird Jahre weiterer Arbeit erfordern, die wir über Tausende von Verifikationsingenieuren und Forschern durchführen müssen.

    Ich erwarte, dass die verteilte und nebenläufige Version davon schneller kommen wird. Tatsächlich würde ich wetten, dass bis Ende 2030 die hier genannte Messlatte für Single-Threaded-Software für Multithread- und verteilte Systeme unter nicht-adversarialen Fehlermodi erreicht sein wird. Das ist deutlich aggressiver als die meisten in diesem Bereich (und ich bin bestenfalls feldnah), aber angesichts der Fortschrittsrate denke ich, dass es tatsächlich eine eher konservative Wette ist (die wirklich aggressive Wette wäre „Juli 2027“).

    > Je mehr „bouba“ ein Stück Software oder eine gegebene Schicht hat, desto schwieriger ist es, darüber zu sprechen, was sie korrekt macht. Wir können immer über einige korrekte Attribute sprechen, aber über eine einheitliche Vorstellung von Korrektheit zu sprechen ist meiner Meinung nach nicht möglich.

    Dem stimme ich weitgehend zu, obwohl ich denke, dass wir mehr Fortschritt als erwartet bei der Quantifizierung (und damit Verifizierung) von Benutzerfreundlichkeit und „Look and Feel“-Aspekten von Software sehen werden. Das Risiko ist, dass dies auf eine „enge“ Weise geschieht, die alle „korrekten“ Software gleich aussehen und sich gleich anfühlen lässt, weil […]

  3. skybrian

    Wenn es eine Sprachspezifikation gibt und alle zustimmen, sie zu verwenden, bedeutet das, dass „sollte dieser Code kompilieren“ eine klare Bedeutung hat und ebenso „Compiler-Bug“.

    Vielleicht wäre es der richtige Weg, gemeinsame Pakete mit geteilten Spezifikationen für andere wünschenswerte Eigenschaften zu haben? Aus Sicht des Benutzers sollte das Tool wie ein Linter wirken.

    Woher wird das Vertrauen kommen? Bei einem populären Softwareprojekt kommt es von einem vertrauenswürdigen Team, das es wartet, und vielen Leuten (und Bots), die sie beobachten. Das Ergebnis wäre, dass jemand den Linter nutzen kann, ohne viel selbst verifizieren zu müssen.

    Und sicher, man sollte auch eigene, benutzerdefinierte Eigenschaften schreiben und beweisen können, aber hoffentlich baut es auf gemeinsamen Definitionen auf.

  4. Mikhail_Edoshin

    Angenommen, wir können mechanisch verifizieren, dass ein Programm einer Spezifikation entspricht, wäre unser nächster logischer Schritt, nur die Spezifikation zu behalten und das Programm mechanisch zu generieren.

    Geschriebener Code sollte an sich wie eine logische Argumentation aussehen, die für Menschen ausreicht, um die Schritte zu verifizieren.

  5. Taikonerd

    > Ein großartiges Beispiel dafür ist der jüngste „Binary Verification“-Ansatz, bei dem wir nicht Fakten über die Programme selbst beweisen, sondern Fakten über die kompilierten Binärdateien dieser Programme.

    Das ist ein interessantes Argument; ich sehe hier Vor- und Nachteile.

    Ich bin kein Formal-Methods-Mensch, aber ich würde vermuten, dass der Grund, warum man Fakten über die Programme selbst beweisen möchte, darin liegt, dass sie Informationen auf höherer Ebene „umsonst“ kodieren – zum Beispiel, dass diese Funktion eine Person zurückgibt.

    IIRC gab es Forschung zu speziellen Compilern, die TAL erzeugen würden: Typed Assembly Language. Die Idee war, dass TAL Annotationen tragen könnte, die für Beweiser hilfreich wären.

Mehr von diesem Tag

2026-11-16