Beweisbar korrekte Softwareeine praktische Einführung

Dominik Haneberg, Gerhard Schellhorn, JonathanSchmitt

1

Organisatorisches

Vorlesung:

Mittwoch 10.00 Uhr - 11.30 Uhr (1005 L1)

Versuche: (Raum 1006, 2 Termine w ählen)

Montag: 10.00 - 11.30 UhrMontag: 11.45 - 13.45 UhrMontag: 14.00 - 15.30 UhrMontag: 15.45 - 17.30 Uhr

2

Anmeldung

• Maximal 40 Teilnehmer in Zweiergruppen

• Paarweise in die erste Liste in Zweiergruppen eintragen:Ergibt Gruppennummer

• Zweite Liste: Unter der Gruppennummer aus den 4 möglichen Terminenso viele wie möglich auswählen (nicht bloss 2!)

• Wir verteilen die Gruppen auf mögliche Termine (je 2 pro Gruppe)

• Bei zuviel Teilnehmern: Los.

• Vorausgesetzt: Kenntnisse aus Logik-VorlesungLogik bestanden ⇒ bevorzugt

• Spätestens morgen: Welche Gruppennummer wann dran ist auf WWW

3

Prüfung

• Anwesenheitspflicht in den Übungen!• Vorbereitung der Aufgaben anhand der Doku• Abgabe der gelösten Aufgaben per Mail.

• 2 Mündliche Abnahmen im Semester in Zweiergruppen :⋆ 1. Abnahme nach 6 Wochen

(zu: Prädikatenlogik und Algebraische Spezifikation)⋆ 2. Abnahme am Ende

(Programmbeweisen)

• mit: Testaufgaben (KIV) & Fragen zur Vorlesung

4

Schein und Sprechstunden

Schein

2 V + 4 Ü = 8 Creditpoints für den Bereich ”Softwaretechnik” oder für denBereich ”Theoretische Informatik”

Sprechstunden

Dominik Haneberg: Raum 2032, Tel. 2178Gerhard Schellhorn: Raum 2002A, Tel. 2124Jonathan Schmitt: Raum 2028, Tel. 2176

5

BKS: Ziel und Vorgehen

Ziel: Beweisbar korrekte Software

Vorgehen1. Formale Spezifikation der Anforderungen

2. Validierung/Nachweis von Sicherheitseigenschaften

3. Programmierung

4. Beweis, dass Programm die Spezifikation erfüllt

Notwendig

Definition formaler Modelle und Aussagen ⇒ Logik

6

Verschiedene Logiken

• Aussagenlogik

• Prädikatenlogik (erster Stufe)

• Logiken höherer Stufe

• Hoare-Logik (imperative Programme)

• Dynamische Logik (imperative Programme)

• LCF (funktionale Programme)

• Temporallogik (parallele Programme)

• (Modallogik)

• (nichtmonotone Logik)

7

Warum Beweise über Programme?

Fehler in Software sind eine nicht enden wollende Geschichte: Oft nurärgerlich, manchmal sehr teuer oder sogar lebensgefährlich!

• Gepäckverteilung Flughafen Denver (1994) und Terminal 5 LondonHeathrow (2008)

• Ausfall des A340-Autopiloten

• Strahlentherapiesystem Therac-25

• Ariane 5 Explosion beim ersten Start

• Mars Climate Orbiter und Mars Polar Lander

• ...

8

Warum formale Beweise mit KIV?

These: Eine detaillierte Analyse desProgramms von Hand genügt, um seineKorrektheit nachzuweisen!

Problem

9

Warum formale Beweise mit KIV?

These: Eine detaillierte Analyse desProgramms von Hand genügt, um seineKorrektheit nachzuweisen!

Problem Beweise für Software sind häufig sehr langwierig (viele Details) unddaher noch fehleranfälliger als die Programme selbst.

⇒ Systemunterstützung mit KIV

(andere Systeme: ACL2, Isabelle, PVS, . . . )

Durch die Systemunterstützung wirddie korrekte Anwendung von Kalkülregeln sichergestellt

9

Lernziele

• Erlernen des Umgangs mit KIV

• Formales Beweisen mit KIV⋆ Umsetzen von Beweisen in einen Kalkül⋆ Automatisierung durch Simplifikation und Heuristiken⋆ Beweise für Datenstrukturen und Programme

• Strukturierte Spezifikation mit KIV

• Verschiedene Verfeinerungskonzepte um von abstraktenSpezifikationen zu konkreten Programmen zu kommen

10

Praktische Anwendung

• Einsatz von KIV durch KIV-Experten in sicherheitskritischenAnwendungen

• Einsatz von automatischen (spezialisierten) Tools:⋆ Model Checking (HW-Design, eingebettete Systeme)⋆ Bounded Model Checking, SAT checking (z.Bsp. Security Protokolle)⋆ Datenflussanalyse (z.Bsp. MS Kernel Treiber im SLAM-Projekt).⋆ predicative Abstraction und Typechecking (z.Bsp. Nullpointer

Exceptions, SPEC#)⋆ Entscheidungsprozeduren für Arithmetik (z.B. für Zeitconstraints bei

Echtzeitsystemen)⋆ . . .

• systematisches Testen mit aus Spezifikationen generierten Testfällen

• Konstruktion von endlichen Gegenbeispielen (z.B. Alloy, MACE)

• Verwendung der Vorgehensmethodik(“UML, aber eine Nummer präziser”)

11

Überblick

1. Aussagen- und Prädikatenlogik (2 Wochen)2. Beweise über Datenstrukturen (Listen) (2 Wochen)3. Algebraische Spezifikationen (1 Woche)4. Programmbeweise (Hoare, while -Schleifen) (2 Wochen)5. Modulverifikation (2 Wochen)6. Abstract State Machines und Refinement (3 Wochen)

12

Prädikatenlogikmit Sorten

und Sequenzenkalkül

13

Prädikatenlogik mit Sorten

• in Logik f. Inf.: n-stellige Funktionssymbole f ∈ Fn

Semantik: n-stellige Funktion über Grundbereich D

• BKS: gegeben ist eine endliche Menge S von Sorten.Semantik: jede Sorte bezeichnet einen Grundbereich

• Funktionen jetzt: f ∈ Fs→s′ oder einfacher: f : s→ swobei s = s1, . . . , sn mit n ≥ 0 (n = 0 : Konstante c : s)

• Vorteile:

• Theorie:

• Praxis:

14

Prädikatenlogik mit Sorten

• in Logik f. Inf.: n-stellige Funktionssymbole f ∈ Fn

Semantik: n-stellige Funktion über Grundbereich D

• BKS: gegeben ist eine endliche Menge S von Sorten.Semantik: jede Sorte bezeichnet einen Grundbereich

• Funktionen jetzt: f ∈ Fs→s′ oder einfacher: f : s→ swobei s = s1, . . . , sn mit n ≥ 0 (n = 0 : Konstante c : s)

• Vorteile:⋆ pro Datentyp eine Sorte, damit Typcheck wie in Prog.Sprachen⋆ später: leichte Erweiterbarkeit zu Higher-Order-Logik

• Theorie: Sorten können in Prädikate codiert werden

• Praxis: ohne Sorten zusätzliche Axiome und Deduktion notwendig!(z.B. nat(x) ∧ nat(y) → nat(x+ y))

• es gibt immer eine vordefinierte Sorte bool.

14

Die Sorte bool: Formeln sind auch Terme!

• Mit einer vordefinierten Sorte bool wird es möglich,Formeln und Terme der Sorte bool zu identifizieren

• logische Operatoren sind jetzt vordefinierte boolesche Funktionen:. ∧ ., . ∨ ., . → ., .↔ . : bool × bool → bool¬ . : bool → booltrue, false : bool

• Formeln ϕ,ψ und Terme t heissen jetzt Ausdrücke e

• Prädikate sind einfach Funktionen mit Zielsorte bool

• Funktionen und Prädikate heissen jetzt Operationen OP

15

Signaturen und Variablen

Eine Signatur Σ = (S,OP ) ist ein Paar mit:

• endlicher Menge S von Sorten, mit bool ∈ S

• endlicher Familie OP =⋃

s∈S∗,s′∈S

OPs→s′

von Operationssymbolen mit Argumentsorten s undErgebnissorte s′ (leere Liste von Argumentsorten: Konstante c)

• OP enthält immer die üblichen booleschen Operationen

• wie üblich: Konstanten sind null-stellige Operationen

• boolesche Konstanten = atomare Aussagen

Eine Variablenmenge X besteht aus einer abzählbar unendlichen Mengevon Variablen Xs für jede Sorte s ∈ S

16

Syntax von Ausdrücken

Ausdrücke e ∈ EXPRs(Σ,X) der Sorte s ∈ S über der Signatur Σ und überden Variablen X sind rekursiv definiert durch

• x aus Xs ist ein Ausdruck der Sorte s

• Sind e1, . . . , en Ausdrücke der Sorten s1, . . . , sn und op : s1, . . . , sn → s′,dann ist op(e1, . . . , en) ein Ausdruck der Sorte s′

• Bem.: Schreibe c statt c() für Konstanten (n = 0)

• sind e1, e2 Ausdrücke der Sorte s, so iste1 = e2 eine Formel (i.e. ein Ausdruck der Sorte bool ).

• Ist ϕ eine Formel, und x eine Variable, so sind∀ x.ϕ und ∃ x.ϕ Formeln.

EXPR(Σ,X) :=⋃

s∈S EXPRs(Σ,X), For(Σ,X) := EXPRbool(Σ,X)

Terme t ∈ T (Σ,X) sind Ausdrücke ohne Quantoren und Gleichheit.17

KIV-Syntax für Signaturen

sorts nat;

list;

constants 0 : nat;

ϕ : bool; (: 0-stelliges Pr ädikat als boolesche Konstante :)

functions f : nat × nat → nat;

g : nat, nat -> nat; (: es geht auch ASCII :)

predicates isprime : nat;

. < . : nat × nat;

variables x,y : nat;

u : list;

• Sorten, Funktionen, Prädikate, Variablen immer in dieser Reihenfolge

• Aufzählungen mit derselben Sorte nur bei Variablen

18

KIV: Infix-Schreibweise und Bindungsstärken

• Signatur: . ⊕ . : s1 × s2 → s, s1, s2, s ∈ S

• üblich: ⊕ besteht aus Sonderzeichen, z. B. +, ∗, {präfix} > {infix} > {¬} > {∧} > {∨} > {→} > {↔} > {∀,∃}

Außenklammern werden weggelassen,

Aufzählungen mit ∧, ∨ ungeklammert.

19

Sequenzenkalkül

• erfunden von Gentzen (1934)

• nur einer von vielen möglichen Kalkülen:Hilbertkalkül, natürliches Schliessen, Tableaukalkül, Modellelimination

• Charakteristik: versucht, Beweisziel auf Axiome zu reduzieren(schrittweise Vereinfachung des Problems); am menschlichenBeweisen orientiert

ϕ1, . . . , ϕn ⊢ ψ1, . . . , ψm Sequenzϕ1, . . . , ϕn Antezedent (n ≥ 0)ψ1, . . . , ψm Sukzedent (m ≥ 0)

Beachte: “⊢” ist Sequenzenpfeil, “⊢PL” ist Ableitbarkeit

20

Notation

Γ,Γ1,∆, . . . Listen von Formeln,Γ = ϕ1, . . . , ϕn, ∆ = ψ1, . . . , ψm

Γ ⊢ ∆ := ϕ1, . . . , ϕn ⊢ ψ1, . . . , ψm

Γ, ϕ ⊢ ψ := ϕ1, . . . , ϕn, ϕ ⊢ ψ

Γ, ϕ ∧ ψ,∆ ⊢ := ϕ1, . . . , ϕn, ϕ ∧ ψ,ψ1, . . . , ψm ⊢∧

[ϕ1, . . . , ϕn] := ϕ1 ∧ . . . ∧ ϕn∧

[] := true∨

[ψ1, . . . , ψm] := ψ1 ∨ . . . ∨ ψm∨

[] := false

Bedeutung einer Sequenz: Γ ⊢ ∆ =∧

Γ →∨

∆21

Sequenzenkalkül: Inferenzregeln

Regel: (n ≥ 0)

Γ1 ⊢ ∆1 Γ2 ⊢ ∆2 . . . Γn ⊢ ∆n

Γ ⊢ ∆

• Regeln werden von unten nach oben gelesen:Um Γ ⊢ ∆ (die Konklusion) zu beweisen, beweise stattdesseneinfachere Prämissen Γ1 ⊢ ∆1, . . . ,Γn ⊢ ∆n

• Bei n = 0 ist die Konklusion direkt bewiesen

• n = 1: Vereinfachung

• n = 2: Fallunterscheidung

22

Beispiel

Ein erster Beweis.

23

Sequenzenkalkül: Ableitbarkeit

Γ ⊢ ∆ ist aus einer Menge von Formeln (Axiomen) Ax ableitbar

(kurz: Ax ⊢PL Γ ⊢ ∆)

:⇔ es gibt eine Ableitung (Baum) mit

• Wurzel: Γ ⊢ ∆ (Konklusion)

• Blätter: ⊢ ϕ mit ϕ ∈ Ax (Prämissen)

• Innere Knoten durch Regelanwendungen gebildet

24

Kalkül für Aussagenlogik

ϕ,Γ ⊢ ϕ,∆(axiom)

false,Γ ⊢ ∆(false left)

Γ ⊢ true,∆(true right)

Γ′ ⊢ ∆′

Γ ⊢ ∆(weakening, Γ′ ⊆ Γ,∆′ ⊆ ∆)

Γ ⊢ ϕ,∆ ϕ,Γ ⊢ ∆

Γ ⊢ ∆(cut formula)

Γ ⊢ ϕ,∆

¬ ϕ,Γ ⊢ ∆(negation left)

ψ,Γ ⊢ ∆

Γ ⊢ ¬ ψ,∆(negation right)

ϕ,ψ,Γ ⊢ ∆

ϕ ∧ ψ,Γ ⊢ ∆(conjunction left/right)

Γ ⊢ ϕ,∆ Γ ⊢ ψ,∆

Γ ⊢ ϕ ∧ ψ,∆

ϕ,Γ ⊢ ∆ ψ,Γ ⊢ ∆

ϕ ∨ ψ,Γ ⊢ ∆(disjunction left/right)

Γ ⊢ ϕ,ψ,∆

Γ ⊢ ϕ ∨ ψ,∆

Γ ⊢ ϕ,∆ ψ,Γ ⊢ ∆

ϕ→ ψ,Γ ⊢ ∆(implication left/right)

ϕ,Γ ⊢ ψ,∆

Γ ⊢ ϕ→ ψ,∆

Γ ⊢ ϕ,ψ,∆ ϕ,ψ,Γ ⊢ ∆

ϕ↔ ψ,Γ ⊢ ∆(equivalence left/right)

ϕ,Γ ⊢ ψ,∆ ψ,Γ ⊢ ϕ,∆

Γ ⊢ ϕ↔ ψ,∆25

Regeln für Quantoren und Gleichungen

•ϕτx,∀ x.ϕ,Γ ⊢ ∆

∀ x.ϕ,Γ ⊢ ∆(all left)

Γ ⊢ ϕτx,∃ x.ϕ,∆

Γ ⊢ ∃ x.ϕ,∆(exists right)

•ϕyx,Γ ⊢ ∆

∃ x.ϕ,Γ ⊢ ∆(exists left)

Γ ⊢ ϕyx,∆

Γ ⊢ ∀ x.ϕ,∆(all right)

ϕτx die Substitution von x durch einen beliebigen Term τ in ϕ.

y ist eine neue Variable, i.e. eine die nicht frei in Q x.ϕ,Γ,∆ (Q ∈ {∀,∃})vorkommt.

Genauer: y 6∈ (free(ϕ)\{x}) ∪ free(Γ) ∪ free(∆)

•Γ ⊢ τ = τ ,∆

(reflexivity right)x = τ,Γτx ⊢ ∆

τx

x = τ,Γ ⊢ ∆(insert equation)

26

Variablen und freie Variablen eines Ausdrucks

Die Variablen eines Ausdrucks (Var(e))

Var(x) = {x} x ∈ X

Var(op(t1, . . . , tn)) =⋃n

i=1 Var(ti)

Var(e = e′) = Var(e) ∪ Var(e′)

Var(Qx.ϕ) = {x} ∪ Var(ϕ) Q ∈ {∀,∃}

Die freien Variablen einer Formel (free(ϕ)) sind genauso definiert ausser:

free(Qx.ϕ) = free(ϕ) \ {x} Q ∈ {∀,∃}

27

Substitution

die Substitution einer Variablen x durch einen Ausdruck t in e (etx)

xtx = t

ytx = y falls x 6= y

op(e1, . . . , en)tx = op((e1)

tx, . . . , (en)

tx)

(e1 = e2)tx = (e1)

tx = (e2)

tx)

(Qy.ϕ)tx =

Qy.ϕ falls y = x ∨ x 6∈ free(ϕ)

Qy.ϕtx falls y 6= x, y 6∈ free(t), x ∈ free(ϕ)

Qz.(ϕzy)tx falls y 6= x, y ∈ free(t), x ∈ free(ϕ)

(z neu, d. h. z 6∈ Var(ϕ) ∪ Var(t))

(Q ∈ {∀,∃})

28

KIV: Organisation in Projekte

Grundlegende Organisation:

• In KIV arbeitet man in (SW-Entwicklungs-) Projekten

• Jedes Projekt definiert Spezifikationen (Σ + Ax + Weiteres)

• Spezifikationen können aufeinander aufbauen

⇒ Entwicklungsgraph

• Über jeder Spezifikation kann man

Theoreme formulieren und beweisen

29

KIV: Projektauswahl- und Projektebene

4 Ebenen:

1. Projektauswahlebene• Projekte anlegen, löschen, auf einem Projekt arbeiten

2. Projektebene• zeigt den Entwicklungsgraph der Spezifikationen• Spezifikationen anlegen, ändern, löschen• Auf einer Spezifikation arbeiten

30

KIV: Spezifikations- und Beweisebene

3. Spezifikationsebene⋆ Theoreme anlegen, ändern, löschen⋆ einen Beweis führen

4. Beweisebene⋆ Beweise führen durch interaktive Anwendung von Regeln⋆ Zwei Regelsätze: Basisregeln/für’s Beweisen optimierte Regeln⋆ Backtracking, Pruning⋆ Simplifikation + Heuristiken zur automatischen Anwendung von

Regeln

31

KIV: Verzeichnisstruktur

Verzeichnisstruktur:

• Ein Projektverzeichnis

• darin:⋆ ein Unterverzeichnis specs⋆ [eine Datei devgraph für den Entwicklungsgraph]

• in specs: ein Unterverzeichnis für jede Spezifikation

• darin:⋆ eine Datei specification für Signatur, Axiome etc.⋆ eine Datei sequents für Theoreme⋆ [ein Verzeichnis proofs das geladene Theoreme, geführte Beweise

etc. speichert]

32

Bis nächsten Montag

Vorbereiten der ersten Übunganhand der Doku!

33