Formale Programmverifikation - Universität Freiburg · Jedes sechste DV-Projekt wurde ohne jegliches Ergebnis abgebrochen, alle Projekte überzogen die Zeit- und Kostenrahmen um

Formale Programmverifikation

Referentin: Kirsten Hradek

2


2


• Einführung/Motivation

2



• Softwareverifikation am Beispiel desHoare-Kalküls

2




• Überblick über verschiedeneVerifikationsmethoden

2





• Rechnerunterstützte Verifikationsmethoden

2






• Möglichkeiten und Grenzen der SV

3







4

Das Grundproblem:

4

Das Grundproblem:Qualitätskrise

4


Software wird zur Benutzung freigegeben, nicht wennsie nachweislich korrekt ist, sondern wenn dieHäufigkeit, mit der neue Fehler entdeckt werden, aufein für die Geschäftsleitung akzeptables Niveaugesunken ist. DAVID L. PARNAS

4


Software wird zur Benutzung freigegeben, nicht wennsie nachweislich korrekt ist, sondern wenn dieHäufigkeit, mit der neue Fehler entdeckt werden, aufein für die Geschäftsleitung akzeptables Niveaugesunken ist. DAVID L. PARNAS

Jedes sechste DV-Projekt wurde ohne jeglichesErgebnis abgebrochen, alle Projekte überzogen dieZeit- und Kostenrahmen um 100-200% und auf 100ausgelieferte Programmzeilen kommen im Durchschnittdrei Fehler. TOM DE MARCOS

5

Was bedeutet überhauptProgrammverifikation?

5

Was bedeutet überhauptProgrammverifikation?

Definition:Programmverifikation ist ein systematischer Ansatzzum Nachweis der Fehlerfreiheit von Programmen.Dabei wird bewiesen, daß ein vorgegebenesProgramm bestimmte wünschenswerteEigenschaften besitzt.

(Apt/Olderog, 1998, 1)

6

Welche Fehler können auftreten?

6


• Syntaktische Fehler

6


• Syntaktische Fehler

• Semantische Fehler

7

Programmverifikation zurQualitätssicherung?

7


• Einsetzbarkeit in der Praxis?

7



• Effizienz?

7



• Effizienz?

• Aufwand?

7



• Effizienz?

• Aufwand?

• Kosten?

7



• Effizienz?

• Aufwand?

• Kosten?

• Handhabbarkeit?

7



• Effizienz?

• Aufwand?

• Kosten?

• Handhabbarkeit?

• Vorteile gegenüber anderen Methoden?

8

Programmverifikation?

9







10

Spezifikation

10

Spezifikation• Präzise Darstellung und Beschreibung der

Eigenschaften, der Verhaltensweisen, desZusammenwirkens und des Aufbaus von(bestehenden oder zu entwickelnden) Modellen,Programmen oder Systemen

10



• Ziele:

10



• Ziele:- klareres Verständnis des Problems, seinerEigenschaften und Lösungen

10



• Ziele:- klareres Verständnis des Problems, seinerEigenschaften und Lösungen- (absolutes) Vergleichsmaß, ob ein System dengewünschten Anforderungen genügt

10



• Ziele:- klareres Verständnis des Problems, seinerEigenschaften und Lösungen- (absolutes) Vergleichsmaß, ob ein System dengewünschten Anforderungen genügt- beschreibt zusätzliche Aspekte wie Zuverlässigkeit,Robustheit, zeitl. Verhalten

11

Beweisbare Eigenschaften (1):

11


Partielle Korrektheit:Ein Programm heißt partiell korrekt, falls es nacheiner korrekten Eingabe im Falle der Termination miteiner erwarteten Ausgabe endet.

11


Partielle Korrektheit:Ein Programm heißt partiell korrekt, falls es nacheiner korrekten Eingabe im Falle der Termination miteiner erwarteten Ausgabe endet.

Totale Korrektheit:Ein Programm heißt total korrekt, falls es nach einerkorrekten Eingabe terminiert, und zwar mit einererwarteten Ausgabe.

12


12


z.B. Parallele Programme:

12



• Interferenzfreiheit

12




• Deadlock-Freiheit

12





• Korrektheit unter Fairneß-Annahmen

12





• Korrektheit unter Fairneß-Annahmen

• ...

13

Das Hoaresche Beweissystem

13


• Hoare, 1969

13


• Hoare, 1969

• Floyd 1967: Flußdiagramme

13


• Hoare, 1969


• Grundlage: Prädikatenlogik, induktive

Zusicherungs-Methode

13


• Hoare, 1969




• WHILE-Programme

13


• Hoare, 1969




• WHILE-Programme

--> Hoare-Kalkül

14

Die Sprache:

14

Die Sprache:

•Leere Anweisung: skip

14

Die Sprache:


•Wertzuweisung: u:=t

14

Die Sprache:



•sequentielle Komposition: S1;S2

14

Die Sprache:




•bedingte Anweisung: if B then S1 else S2 fi

14

Die Sprache:




•bedingte Anweisung: if B then S1 else S2 fi

•Schleife: while B do S1 od

15

Die Semantik:

15

Die Semantik:Definition allgemein:Abbildung von Anfangszuständen in Endzustände:

15


M’S÷: ✟→ P(✟) Abbildung von Anfangszustä

15



Ansätze:

15



Ansätze:• Übersetzersemantik (Rückführung auf bekannteProgrammiersprache)

15



Ansätze:• Übersetzersemantik (Rückführung auf bekannteProgrammiersprache)• denotationelle Semantik (Darstellung derZustandsänderungen mit Hilfe von Konfigurationen)

15



Ansätze:• Übersetzersemantik (Rückführung auf bekannteProgrammiersprache)• denotationelle Semantik (Darstellung derZustandsänderungen mit Hilfe von Konfigurationen)• operationelle Semantik (Darstellung derZustandsänderungen mit Hilfe von semantischen Funktionen)

15



Ansätze:• Übersetzersemantik (Rückführung auf bekannteProgrammiersprache)• denotationelle Semantik (Darstellung derZustandsänderungen mit Hilfe von Konfigurationen)• operationelle Semantik (Darstellung derZustandsänderungen mit Hilfe von semantischen Funktionen)• axiomatische Semantik (Darstellung der Auswirkungen vonZustandsänderungen auf die Eigenschaften von Zuständen)

16

Axiomatischer Ansatz:Hoare-Tripel

16


{p} S {q}

16


{p} S {q}Bedeutung:

16


{p} S {q}Bedeutung:Wenn für das Programm vor der Ausführung derAnweisung S die „Vorbedingung“ p gilt und dieAnweisung terminiert, dann gilt danach die„Nachbedingung“ q.

16


{p} S {q}Bedeutung:Wenn für das Programm vor der Ausführung derAnweisung S die „Vorbedingung“ p gilt und dieAnweisung terminiert, dann gilt danach die„Nachbedingung“ q.

17

Korrektheit (2)

17

Korrektheit (2)

{p} S {q} heißt partiell korrekt, wenn jedeterminierende Berechnung von S, die in einem p-Zustand startet, in einem q-Zustand terminiert.

17

Korrektheit (2)

{p} S {q} heißt partiell korrekt, wenn jedeterminierende Berechnung von S, die in einem p-Zustand startet, in einem q-Zustand terminiert.

{p} S {q} heißt total korrekt, wenn jedeBerechnung von S, die in einem p-Zustandstartet, terminiert und ihren Endzustand q erfüllt.

18

Korrektheit (3)

18

Korrektheit (3)Definition:Eine Korrektheitsformel {p} S {q} gilt imSinne der partiellen (bzw. totalen)Korrektheit,~{p} S {q} (bzw. ~tot {p} S {q}),falls M’S÷(’p÷) ` ’q÷bzw

Mtot’S÷ (’p÷) ` ’q÷

19

Das Hoare-Kalkül (1)

19


Beweissystem PD:

19


Beweissystem PD:

AXIOM 1: Skip-Anweisung

19


Beweissystem PD:


{p} skip {q}

19


Beweissystem PD:


{p} skip {q}

AXIOM 2: Wertzuweisung

19


Beweissystem PD:


{p} skip {q}

AXIOM 2: Wertzuweisung{p(u:=t)} u:=t {p}

20


20


REGEL 3: Sequentielle Komposition

20



{p} S1 {r}, {r} S2 {q}

20



{p} S1 {r}, {r} S2 {q} {p} S1;S2 {q}

20



{p} S1 {r}, {r} S2 {q} {p} S1;S2 {q}

REGEL 4: Bedingte Anweisung:

20



{p} S1 {r}, {r} S2 {q} {p} S1;S2 {q}


{p . B} S1 {q},{p . ÕB} S2 {q}

20



{p} S1 {r}, {r} S2 {q} {p} S1;S2 {q}


{p . B} S1 {q},{p . ÕB} S2 {q} {p} if B then S1 else S2 fi {q}

21


21


REGEL 5: Schleife:

21


REGEL 5: Schleife:

_____{p . B} S {p}______

21


REGEL 5: Schleife:

_____{p . B} S {p}______{p} while B do S od {p . Õ B}

21


REGEL 5: Schleife:


REGEL 6: Konsequenzregel:

21


REGEL 5: Schleife:


REGEL 6: Konsequenzregel:ptp1, {p1} S {q1}, q1tq

21


REGEL 5: Schleife:


REGEL 6: Konsequenzregel:ptp1, {p1} S {q1}, q1tq {p} S {q}

22

Beispiele zur Anwendung des Beweissystems PD (1):

22


S ≡ x:=x+1; y:=y+1

23


23


DIV ≡ quo:=0; rem:= x; S0,

23


DIV ≡ quo:=0; rem:= x; S0,wobei S0 ≡ while rem ú y do rem:=rem-y; quo:=quo+1 od,

23



24

25


25

Das Hoare-Kalkül (4)Totale Korrektheit:

25


REGEL 7: Schleife II:

25


REGEL 7: Schleife II:{p .B} S {p},

25


REGEL 7: Schleife II:{p .B} S {p},{p .B. t = z} S {t<z},

25


REGEL 7: Schleife II:{p .B} S {p},{p .B. t = z} S {t<z}, p tt m0,_______________

25


REGEL 7: Schleife II:{p .B} S {p},{p .B. t = z} S {t<z}, p tt m0,_______________{p} while B do S od {p .ÕB}

25


REGEL 7: Schleife II:{p .B} S {p},{p .B. t = z} S {t<z}, p tt m0,_______________{p} while B do S od {p .ÕB}

(wobei t int-Ausdruck; z int-Variable, die nicht in p, B, t, Svorkommt)

26


26


Totale Korrektheit:

26


Totale Korrektheit:

Beweissystem TD:

26


Totale Korrektheit:

Beweissystem TD:

AXIOME 1,2 und REGELN 3, 4, 6, 7

27



28

Eigenschaften von PD und TD

28


• Korrektheit

28


• Korrektheit

• Vollständigkeit

29

Systematische Entwicklungkorrekter Programme (1)

29


• Dijkstra (19??)

29


• Dijkstra (19??)

• Regeln aus den Regeln der Programmverifikation

abgeleitet

z.B. Spezifikation von Problemen in der Form

{p} S {q}

29


• Dijkstra (19??)

• Regeln aus den Regeln der Programmverifikation

abgeleitet

z.B. Spezifikation von Problemen in der Form

{p} S {q}

• syst. Entwicklung von Schleifen

S≡T; while B do R od- Schleifeninvariante -

30


30


Allgemeines Vorgehen:

30



1. Beschreiben des funktionalen Verhaltens eines

Programmes: formale Spezifikation

30





2. Beschreibung der Sicherheitsanforderungen

30






3. Nachweis der Sicherheit und Validierung von

Spezifikationen

30






3. Nachweis der Sicherheit und Validierung von

Spezifikationen

4. Implementierung und deren Verifikation

31







32

Weiterentwicklung des Hoare-Kalküls (1)

32


AXIOM A1: Invarianz:

32


AXIOM A1: Invarianz: {p} S {p}

32



REGEL A2: Disjunktion:

32



REGEL A2: Disjunktion: {p} S {q}, {r} S {q}

32



REGEL A2: Disjunktion: {p} S {q}, {r} S {q} {p - r} S {q}

32




REGEL A3: ∃ -Einführung:

32




REGEL A3: ∃ -Einführung: _{p} S {q}_

32




REGEL A3: ∃ -Einführung: _{p} S {q}_ {∃ x: p} S {q}

32




REGEL A3: ∃ -Einführung: _{p} S {q}_ {∃ x: p} S {q}

(...)

33


33


• andere deterministische Programme

33



• parallele Programme

33




• nichtdeterministische Programme

33




• nichtdeterministische Programme

• verteilte Programme

34

Beweissysteme - Ansätze:

34

Beweissysteme - Ansätze:• Unterschiedliche Semantiken:

34


34


34


• operational

34


• operational• denotational

34


• operational• denotational• algebraisch

34


• operational• denotational• algebraisch• ...

34



• Unterschiedliche Logiken

34




• Prädikaten-Logik

34




• Prädikaten-Logik• algorithmische Logik

34




• Prädikaten-Logik• algorithmische Logik• dynamische Logik

34




• Prädikaten-Logik• algorithmische Logik• dynamische Logik• LCF-Logik

34




• Prädikaten-Logik• algorithmische Logik• dynamische Logik• LCF-Logik• ...

34






34





• Rechnerunterstützte Verifikationsmethoden• ...

35







36

RechnerunterstützteVerifikationsmethoden

36


• KIV

36


• KIV• LCF-System

36


• KIV• LCF-System• Stanford-Verifier

36


• KIV• LCF-System• Stanford-Verifier• PL/CV2 Proof Checker

36


• KIV• LCF-System• Stanford-Verifier• PL/CV2 Proof Checker• Boyer-Moore-System

36


• KIV• LCF-System• Stanford-Verifier• PL/CV2 Proof Checker• Boyer-Moore-System• ...

36


• KIV• LCF-System• Stanford-Verifier• PL/CV2 Proof Checker• Boyer-Moore-System• ...

t Dialogsysteme

37

KIV

37

KIV

• Unterstützungswerkzeug zur Entwicklung korrekterSoftware

37

KIV


• graphische Oberfläche

37

KIV



• unterstützt:

37

KIV



• unterstützt:• Spezifikationsentwicklung

37

KIV



• unterstützt:• Spezifikationsentwicklung• Nachweis von Sicherheitseigenschaften

37

KIV



• unterstützt:• Spezifikationsentwicklung• Nachweis von Sicherheitseigenschaften• Implementierung

37

KIV



• unterstützt:• Spezifikationsentwicklung• Nachweis von Sicherheitseigenschaften• Implementierung• Verifikation

38

KIV - Spezifikationsentwicklung

38


• Aufbauend auf element. algebr. Spezifikationenkönnen große modulare Spezifikationen erstelltwerden

38



• Automat. Überprüfung der syntakt. Korrektheit

38




• Visualisierung als Entwicklungsgraphen, darüberBearbeitung, Verwaltung möglich

38




• Visualisierung als Entwicklungsgraphen, darüberBearbeitung, Verwaltung möglich

• große Bibliothek wiederverwendbarerStandardspezifikationen

39

KIV- Beweisen inSpezifikationen

39


• Weitgehend automatisiert, jedoch an vielen StellenInteraktion des Benutzers erforderlich

39



• Beweisgang graphisch visualisiert; darüberVerwaltung, Modifikation, Dokumentationmöglich

39



• Beweisgang graphisch visualisiert; darüberVerwaltung, Modifikation, Dokumentationmöglich

• Korrektheitsmanagement (verwaltetBeweispflichten, verhindert z.B. zyklischesverwenden von Lemmata)

40

KIV- Implementierung &Verifikation

40


• Korrektheitsmanagement

40



• Beweiskomponente (zu 80-90% automatisch)

40




• Beweisstrategie ergänzt um spezielleBeweisregeln für Programme

40





• Automatische Löschung der von Korrekturenbetroffenen Beweise

40





• Automatische Löschung der von Korrekturenbetroffenen Beweise

• Strategie zur Wiederverwendung früherer Beweise(Ersparnis von ~90% des Aufwands)

41

KIV- Anwendungen

41

KIV- Anwendungen

• Zusammenarbeit mit über 10 Behörden,Institutionen, Firmen

41

KIV- Anwendungen


• Pilotanwendungen in:

41

KIV- Anwendungen


• Pilotanwendungen in: • Raumfahrt

41

KIV- Anwendungen


• Pilotanwendungen in: • Raumfahrt• Medizintechnik

41

KIV- Anwendungen


• Pilotanwendungen in: • Raumfahrt• Medizintechnik• Automobiltechnik

41

KIV- Anwendungen


• Pilotanwendungen in: • Raumfahrt• Medizintechnik• Automobiltechnik• Bahntechnik

41

KIV- Anwendungen



• Crash-Control-Software für Airbag

41

KIV- Anwendungen



• Crash-Control-Software für Airbag• Compilerverifikation

41

KIV- Anwendungen



• Crash-Control-Software für Airbag• Compilerverifikation

• ...

42







43



• Notwendigkeit?

• Aufwand?

• Kosten?

• Handhabbarkeit?

• Vorteile gegenüber anderen Methoden?

44

Probleme

44

Probleme• Es kann nur bewiesen werden, was auch

spezifiziert wurde!

44


spezifiziert wurde!

• v.a. bei größeren Programmen sehraufwendig (-> teuer?)

44


spezifiziert wurde!


• spezielle logische u. mathematischeKenntnisse erforderlich (-> Spezialisten?)

44


spezifiziert wurde!


• spezielle logische u. mathematischeKenntnisse erforderlich (-> Spezialisten?)

• Robustheit, Zuverlässigkeit, zeitl. Verhaltenschwer formalisierbar

45

ABER:

45

ABER:• Es wird stets die Korrektheit für ALLE

Eingaben bewiesen (-> Gewißheit)

45



• frühzeitige Aufdeckung von Fehlernmöglich (-> erspart Zeit und Geld)

45




• Mittlerweile gute rechnerunterstützteVerfahren

45





• Kooperation mit Universitäten möglich

45





• Kooperation mit Universitäten möglich

• gerade bei kritischen AnwendungenSoftwareverifikation unabdingbar

46

These:

Softwareverifikation ist eine

Frage der Qualität!

47

Programmverifikation!

Documents

Formale Programmverifikation - Universität Freiburg · Jedes sechste DV-Projekt wurde ohne jegliches Ergebnis abgebrochen, alle Projekte überzogen die Zeit- und Kostenrahmen um