Institut für Informationssicherheit und Verlässlichkeit (KASTEL) – Anwendungsorientierte Formale Verifikation
  • DE
Institut für Informationssicherheit und Verlässlichkeit (KASTEL) – Anwendungsorientierte Formale Verifikation
Startseite

Anwendung Formaler Verifikation

Vorlesung im Sommersemester 2010

Prof. Dr. Bernhard Beckert (BB)
Dr. Vladimir Klebanov (VK)

Zielgruppe: Diplom Informatik, Master Informatik
Vertiefungsfächer VT 1: Theoretische Grundlagen
VT 6: Softwaretechnik und Übersetzerbau
Umfang: 3 SWS
Vertiefungsfächer: Theoretische Grundlagen und Softwaretechnik und Übersetzerbau
Ort: SR 236 (Geb. 50.34)
Zeit: Do 11:30-13:00 und Fr 11:30-13:00
Erstmals: Do 15.04.2010
LVNr.: 24625

Aktuelles

21.07.2010: Die Folien zu den Themen 4 (Hybride Systeme), 5 (Verifikation von Echtzeiteigenschaften, UPPAAL) und 6 (Abstrakte Interpretation, TVLA) sind online
25.06.2010: Die am 10.06.10 ausgefallene Vorlesung wird nicht am 02.07.10 sondern am Dienstag, dem 06.07.10, um 15:45, nachgeholt.
09.06.2010: Die Vorlesung am 10.06.10 muss leider ausfallen. Sie wird am 02.07.10 nachgeholt.
06.05.2010: Die Vorlesungsfolien und Beispiele zu der Vorlesung/Übung von heute stehen zur Verfügung.
24.04.2010: Die Vorlesungsfolien zu den Vorlesungen/Übungen am 22.04.10 und 23.04.10 stehen zur Verfügung.
17.04.2010: Die Vorlesungsfolien zur Vorlesung am 15.04.10 stehen zur Verfügung.
17.04.2010: Informationen zum KeY-System stehen zur Verfügung, das für die 1. Vorlesungseinheit verwendet wird. Bitte installieren Sie KeY auf Ihrem Rechner. Falls Sie nicht schon zuvor Erfahrung mit KeY gesammelt haben, arbeiten Sie bitte die Einführung zum Beweisen von prädikatenlogischen Formeln mit KeY durch: KeYIntro.pdf.

Anwendung formaler Verifikation

Methoden für die formale Spezifikation und Verifikation - zumeist auf der Basis von Logik und Deduktion - haben einen hohen Entwicklungsstand erreicht. Es ist zu erwarten, dass sie zukünftig traditionelle Softwareentwicklungsmethoden ergänzen und teilweise ersetzen werden. Formale Methoden haben den Bereich akademischer Fallstudien hinter sich gelassen, und die Softwareindustrie zeigt ernsthaftes Interesse.

Nahezu sämtliche formale Spezifikations- und Verifikationsverfahren haben zwar die gleichen theoretisch-logischen Grundlagen, wie man sie etwa in der Vorlesung "Formale Systeme" kennenlernt. Zum erfolgreichen praktischen Einsatz müssen die Verfahren aber auf die jeweiligen Anwendungen und deren charakteristischen Eigenschaften abgestimmt sein. An die Anwendung angepasst sein müssen dabei sowohl die zur Spezifikation verwendeten Sprachen als auch die zur Verifikation verwendeten Kalküle.

Auch stellt sich bei der praktischen Anwendung die Frage nach der Skalierbarkeit, Effizienz und Benutzbarkeit (Usability) der Verfahren und Werkzeuge.

Inhalt und Struktur der Vorlesung

Die Vorlesung ist anhand verschiedener Anwendungsszenarien mit unterschiedligen Eigenschaften und Anforderungen an formale Verifikationsmethoden organisiert. In sieben Einheiten werden diese Szenarien, typische Spezifikations- und Verifikationsmethoden und Werkzeuge vorgestellt:

Anwendungsszenario Methoden
1. Verifikation funktionaler Eigenschaften imperativer und objekt-orientierter Programme Java Modeling Language
Dynamische Logik		 (BB)
2. Nachweis temporallogische Eigenschaften endlicher Strukturen Model Checking (VK)
3. Verifikation nebenläufiger Programme (Concurrency) Rely/Guarantee (VK)
4. Hybride Systeme Model Checking, Dynamische Logik für hybride Systeme (BB)
5. Verifikation von Echtzeiteigenschaften Timed Automata, UPPAAL (BB)
6. Verifikation der Eigenschaften von Datenstrukturen Abstract Interpretation, TVLA (BB)
7. Programm-/Protokollverifikation Termersetzungsverfahren (Rewriting) (VK)

Die Veranstaltung hat 3 SWS, also 21 Doppelstunden im Semester. Entsprechend besteht jede der sieben Einheiten aus zwei Doppelstunden Vorlesung und einer Doppelstunde Übung, in denen die Verfahren anhand konkreter Verifikatiossysteme von den Studierenden praktisch erprobt werden. Vorlesung und Übung gehen dabei fließend ineinander über.

Terminplan

Dieser Plan ist nicht endgültig. Verschiebungen sind möglich.

Donnerstag, 11:30-13:00, SR 236 Freitag, 11:30-13:00, SR 236
15.04.2010: V/Ü (1) 16.04.2010: ---
22.04.2010: V/Ü (1) 23.04.2010: V/Ü (1)
29.04.2010: V/Ü (1) 30.04.2010: ---
06.05.2010: V/Ü (2) 07.05.2010: V/Ü (2)
13.05.2010: --- (Chr. Himmelfahrt) 14.05.2010: V/Ü (2)
20.05.2010: V/Ü (2) 21.05.2010: V/Ü (2)
27.05.2010: --- 28.05.2010: V/Ü (5)
03.06.2010: --- (Fronleichnam) 04.06.2010: V/Ü (5)
10.06.2010: V/Ü --- 11.06.2010: V/Ü (5)
17.06.2010: V/Ü (6) 18.06.2010: V/Ü (6)
24.06.2010: V/Ü (6/4) 25.06.2010: V/Ü (4)
01.07.2010: --- 06.07.2010: (4)
08.07.2010: V/Ü (7) 09.07.2010: V/Ü (7)
15.07.2010: V/Ü (7) 16.07.2010: V/Ü (3)

Materialien

Vorlesungsfolien

Die Vorlesungsfolien werden hier jeweils nach der Vorlesung zur Verfügung gestellt.

0. Organisatorisches und Einführung

1. Funktionale Verifikation von Java-Programmen

Java Modeling Language

2. Model Checking mit SPIN

Einführung in Promela

SPIN-Grundlagen

Modellieren nebenläufiger Prozesse

Model Checking mit LTL

3. Verifikation nebenläufiger Programme mit Rely-Guarantee

Vortrag von Leonor Prensa Nieto (Autorin der Formalisierung von Rely-Guarantee in Isabelle)

4. Hybride Systeme

Folien aus dem Tutorial von Martin Fränzle, Universität Oldenburg

5. Verifikation von Echtzeiteigenschaften, UPPAAL

Folien aus dem Tutorial von Kim Larsen, Aalborg University

6. Abstrakte Interpretation, TVLA

Folien aus dem Tutorial von Patrick Cousot, ENS Paris

  • Foliensatz - Relevant: Folien 1-41, 59-66, 71-95

7. Maude

  • Folien: Einführung in Maude - relevant sind Folien 1-36, 56-79 (Vorlesung am 08.07.10, Folien freundlich überlassen von Narciso Martí-Oliet)
  • Folien: JavaFAN (Vorlesung am 09. und 15.07.10, Folien freundlich überlassen von Grigore Rosu)
  • Beispiele zu JavaFAN

Verifikationswerkzeuge

Hier werden Informationen und Links zu den in der Vorlesung verwendeten Werkzeugen bereitgestellt.

1. KeY-System

Für die Vorlesungseinheit "Verifikation funktionaler Eigenschaften imperativer und objekt-orientierter Programme" verwenden wir das KeY-System. KeY wird am KIT und der Chalmers University of Technology in Göteborg entwickelt. Es ist ein Softwareverifikationswerkzeug, mit dem die Übereinstimmung von Java-Programmen und ihrer Spezifikation formal bewiesen werden kann.

Das KeY-System besitzt eine graphische Benutzeroberfläche und ist komplett in Java geschrieben, so dass es auf jeder Plattform, für die eine virtuelle Maschine für Java zur Verfügung steht, lauffähig ist.

Version 1.4 ist die zuletzt veröffentlichte Version und kann über die Dowloadseite des KeY-Projektes bezogen werden. Wenn Sie die Software Java Web Start installiert haben (auf fast allen modernen Systemen mit Java der Fall), können Sie KeY auch direkt aus dem Internetbrowser heraus starten, ohne etwas installieren zu müssen.

Bitte installieren Sie KeY auf Ihrem Rechner. Falls Sie nicht schon zuvor Erfahrung mit KeY gesammelt haben, arbeiten Sie bitte die Einführung zum Beweisen von prädikatenlogischen Formeln mit KeY durch:
KeYIntro.pdf.

2. Model Checker SPIN

Bitte installieren Sie Spin und das Frontend jspin auf Ihrem Rechner. Um Spin in vollem Umfang nutzen zu können, ist ein C-Compiler notwendig. Bei der Installation von jspin ist es nötig, die Pfade zu spin usw. in der Datei config.cfg korrekt anzugeben.

3. Deduktive Verifikation nebenläfiger Programme

Rely-Guarantee ist eine Technik für die deduktive Verifikation nebenl&uaml;ufiger Programme. Sie wird in modernen Verifikationssystemen eingesetzt, wie z.B. dem Verifying C Compiler von Microsoft Research. Wir werden Rely-Guarantee anhand einer Formalisierung im generischen Beweiser Isabelle/HOL kennenlernen. Die Rely-Guarantee- (und die Owicki-Gries-) Theorie ist Teil der Isabelle-Distribution unter src/HOL/Hoare_Parallel. Einen Artikel zum Thema gibt es hier.

4. HieroMate

Das Tool HieroMate ermöglicht die grafische Spezifikation von Hybriden Automaten, sowie eine Erreichbarkeitsanalyse mittels Model-Checking mit Hilfe eines Constraint Solvers und dem Tool Hytech.
HieroMate wird an der Universität Koblenz-Landau entwickelt von Christian Schwarz und Ammar Mohammed Ammar. Eine Beschreibung zu dem Tool befindet sich in HieroMate: A Graphical Tool for Specification and Verification of Hierarchical Hybrid Automata.

5. UPPAAL

UPPAAL ist eine Toolumgebung zur Modellierung, Validierung und Verifikation von Echtzeitsystemen, die als Timed-Automata modelliert werden.

Eine Installationsanleitung befindet sich in dem Paket, welches auf der Projektseite zum Download zur Verfügung steht.

6. TVLA

TVLA ist ein Tool zur Erstellung von abstrakten Interpretern aus operationalen Semantiken. Mit Hilfe von TVLA können unter anderem Eigenschaften von Heap-allokierten Daten überprüft werden.

TVLA steht auf der Tool-Webseite zum Download zur Verfügung. Dieses Paket beinhaltet neben dem TVLA-Tool noch ein Manual sowie Beispiele. Außerdem befindet sich auf der Webseite ein Technischer Bericht zum dem Tool.

7. Maude

Maude ist ein Termersetzungssystem, ein Hochleistungsinterpreter für Spezifikationen in Rewriting Logic. Als Anwendung werden wir u.a. Verifikation mittels ausführbarer Java-Semantik JavaFAN behandeln. Die Maude-Webseite enthält das Manual (entspricht weitgehend dem Maude-Buch) und einen Primer (Einführung).