Verification, WS 04/05

Winter term 2004/4005

Lecturers: Bernd Finkbeiner, Andreas Podelski, Patrick Maier

Tutors: Thomas Wies, Eyad Alkassar, Ruzica Piskac

Hauptstudium: Stammvorlesung theoretische Informatik

Time and place

Lecture Room: HS 001 Building 45
Lecture Time: Mondays and Wednesdays 11:15-12:45
Office Hours: Wednesdays 14:00-15:00
SPIN-Office Hour: Mondays 13:00-14:00, MPII R618

Introduction

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. 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 1020 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.

News

21.04.2005: Certificates can be collected from Brigitta Hansen, room 602, MPI.
22.02.2005: Results of final exam have been sent to you via email.
02.02.2005: No lecture on Faschingsmontag, February 7. Instead of the lecture, there will be an extended office hour in Rm. 506, Building 45. The tutorial will take place as planned (but feel free to attend one of the other groups this week instead).
11.01.2005: Tutorials start again from Monday, January 24.
10.12.2004: No lecture on Wednesday, December 22.
06.12.2004: Informations regarding written exams are available.
02.12.2004: SPIN office hour on Monday 06.12.2004 is postponed to Wednesday 08.12.2004, 13:00-14:00.
02.11.2004: Deadline for SPIN assignments (1.4 & 1.5) extended to Friday, 5.11.2004. Please read the submission guidelines.
28.10.2004: No lecture will be given on Wednesday, 3.11.2004
28.10.2004: Tutorials will start from Monday, 8.11.2004.
22.10.2004: First exercise sheet will be handed out on Wednesday, 27.10.04.

Exams

We will have two written exams and an optional supplementary exam. You will need at least 50% of the total points of all exercise sheets in order to be allowed to participate in the final and supplementary exams.

The exams will take place on the following dates:

Midterm exam: 15.12.2004, 9:00 (s.t.)-11:00, lecture rooms I and II, building 27.2
Final exam: 16.02.2005, 9:00 (s.t.)-11:00, lecture rooms I and II, building 27.2
Supplementary exam: 15.04.2005, 14:00 (s.t.)-16:00, HS 3, building 45

Supplementary exam

If you were admitted to participate in the final exam you are also allowed to take the supplementary. However, if you want to participate you must register until Friday, March 18.

You must bring the following items with you: Student card; passport or identity card; pen, stylus or pencil.

The exam will be a written exam and “open book”: You are allowed to bring with you any written material. Loose sheets must be marked by the owner’s name (As a rule of thumb, if you have never used a certain book for the tutorials, then it is unlikely to be useful to you during the exam.)

Electronic devices such as mobile phones, computers, PDAs, calculators, are not permitted.

Grading

The total grade for the lecture is the weighted average of all grades:

If one takes part only in the midterm and final exam: Midterm exam (50%) and Final exam (50%)
If one takes part in the midterm, final and supplementary exam: Midterm exam (25%), Final exam (50%) and Supplementary exam (50%)

For passing, the weighted average must be better than 4.1. If you do not take part in the midterm or final exam without excuse you fail the corresponding exam with grade 5.0.

There is one exceptions to the above rules. If the weighted average is worse than 4.1, but you scored 4.0 or better in the supplementary exam, you pass the lecture with grade 4.0.

Certificates

Certificates for the lecture can be collected from our sectretary, Brigitta Hansen, room 602, building 46.1 (MPI).