Verification - WS 2007/08

Instructors

Tutors and tutorials

Evren Ermis, Di 17:00
Matthias Heizmann, Mi 14:00
Martin Wehrle, Do 17:00
Sergiy Bogomolov, Fr 9:00

The first tutorials start in the week of 5.11.2007-9.11.2007.

Date, Time and Place

Thursday, 11:00 c.t. - 13:00, SR 01-016, Geb. 101
Friday, 11:00 c.t. - 13:00, SR 01-016, Geb. 101
Distribution into tutorials is organized in the first lecture, i.e. on the 25.10.2007.
There are no lectures on the 1st and 2nd of November 2007.

Description

The cause of the catastrophic crash of the Ariane 5 rocket in 1996 was traced to a simple problem in the computer software that calculated the rocket's position: an overflow during an operation with a floating-point number. Despite rigorous testing of the software, the problem went unnoticed. Such software failures occur every day - though usually with less spectacular consequences.

How can one insure that computer programs actually do what they are intended to do? Simply running a program repeatedly with various inputs is inadequate, because one cannot tell which inputs might cause the program to fail. It is possible to tailor a tester to test a given program, but present-day programs are so complex that they cannot be adequately checked through conventional testing, which can leave significant bugs undetected.

Program verification uses mathematical and logical methods to prove that a program is correct. This approach was pioneered by, among others, Dijkstra, Floyd, Gries, Hoare, Lamport, Manna, Owicki and Pnueli. In the early years of verification research, the focus was on deductive proof systems. Back then, program verification was mostly done manually.

Today, we have powerful decision procedures that can, completely automatically, answer basic questions about the data types typically used by programmers. Model Checking is a "push-button" technology that can analyze finite-state abstractions of programs with as many as 10²⁰ states. Verification research continues actively in both academia and industry (see conferences like CAV and TACAS, and verification projects by IBM, Microsoft, Bell Labs and many others).

This course takes an up-to-date look at the theory and practice of program verification.

Links & Literature

Principles of Model-Checking (password protected)
Spin - Formal Verification
Temporal Verification of Reactive Systems – Safety, Zohar Manna and Amir Pnueli, Springer Verlag, ISBN: 0387944591
Büchi complementation made tighter, E. Friedgut, O. Kupferman, M. Y. Vardi, ATVA'04
- Weak alternating automata are not that weak, Orna Kupferman, Moshe Y. Vardi
- On Complementing Nondeterministic Buechi Automata, S. Gurumurthy, O. Kupferman, F. Somenzi, M. Y. Vardi

Excercises

Slides

Password protected, same password as for the script: