Warum ist Proof Checker im Proof Carrying Code erforderlich?

9

In dem klassischen PLDI'98-Artikel von Necula "Das Design und die Implementierung eines zertifizierenden Compilers" verwendet der hochrangige Verifizierer:

  1. VCGen zur Generierung von Verifizierungsbedingungen (Sicherheitsprädikate)
  2. Logiksatz erster Ordnung, um die Bedingungen zu beweisen
  3. LF Proof Checker zur Überprüfung des Proofs aus Schritt (2)

Ich bin etwas verwirrt von Schritt (3). Warum ist es überhaupt erforderlich? Wird nur (1) und (2) nicht ausreichen? Warum vertrauen wir nicht einfach dem Beweis, den ein Theorembeweiser liefert?

proof-theory automated-theorem-proving program-verification RAM
quelle

Antworten:

19

Der Zweck der Proofprüfung besteht darin, die vertrauenswürdige Computerbasis zu minimieren .

Mit einem Proof Checker müssen weder der Compiler noch der Theorembeweiser korrekt sein. Das Papier macht diesen Punkt auf Seite 3:

Neither the compiler nor the prover need to be correct in order to be guaranteed to   
detect incorrect compiler output. This is a significant advantage since the VCGen and  
the  proof checker are significantly simpler than the compiler and the prover.

Ein Proof Checker besteht nur aus ein paar Codezeilen und kann von Hand auf Richtigkeit überprüft werden. Im Gegensatz dazu ist ein automatisierter Prüfer, der eine gute Leistung erbringt, äußerst komplex und es ist unwahrscheinlich, dass er korrekt ist. Bei gut getesteten und weit verbreiteten Prüfern treten die Fehler jedoch in Randfällen auf, die möglicherweise nicht einfach auszulösen sind. Schauen Sie sich den 30k LOC C-Code an, aus dem Lingeling besteht , ein hochmoderner SAT-Löser, um zu sehen, wie kompliziert automatisierte Theoremprüfer sein können. Ohne einen Beweisprüfer müssten Sie diesen Satzbeweis als richtig erweisen. Dies geht über das hinaus, was wir 2015 wirtschaftlich tun können.

Martin Berger
quelle
Ich bin überrascht, dass von ATPs erstellte Beweise fehlerhaft sein können. (Ich dachte, ATP können unvollständig sein, aber nicht fehlerhaft / fehlerhaft) Ich bin hier weniger informiert. Ich bin froh zu wissen, ob es bekannte Fälle von teuren Fehlern bei Beweisen gibt, die von ATPs erstellt wurden.
Ram
3
@ Ram Es gibt Tausende winziger Fehler in der Geschichte eines ernsthaften automatischen Theorembeweisers. Siehe z. B. stackoverflow.com/questions/12281085/… oder den Versionsverlauf eines solchen Tools auf github.
Cody
@Ram Zusätzlich zu Codys großartigen Ratschlägen empfehle ich, aus Erfahrung zu lernen: Schreiben Sie ein wenig ATP, z. B. einen einfachen SAT-Löser. Dies kann in wenigen Codezeilen erfolgen. Versuchen Sie dann, eine gute Leistung zu erzielen, indem Sie z. B. Klausellernen, beobachtete Literale oder interessante Heuristiken zur Variablenauswahl hinzufügen. Dann denken Sie an die Erfahrung ...
Martin Berger