Instructors
Assistants
Contact
- Students:
- Tutors:
Date & Location
Lectures
- Thursday 11:00 a.m. (c.t.) - 01:00 p.m., SR 00-010/14 Geb. 101
- Friday 11:00 a.m. (c.t.) - 12:00 p.m., SR 00-010/14 Geb. 101
Exercises (Discussion Groups)
- By arrangement: Fr 9:30, Mi 11:00, Do 9:30, Do 14:00, Do 16:00
- SR 00-016 Geb. 052
- Please register for this course here!
Slides (password protected)
- 1st lecture Oct 26, 2006
- 2nd lecture Oct 27, 2006
- 3rd lecture Nov 2, 2006
- 4th lecture Nov 3, 2006
- 5th lecture Nov 9, 2006
- 6th lecture Nov 10, 2006
- 7th lecture Nov 16, 2006
- 8th lecture Nov 17, 2006
- 9th lecture Nov 23, 2006
- 10th lecture Nov 24, 2006
- 11th lecture Nov 30, 2006
- spin lectures Dec 7+8, 2006
- 14th lecture Dec 14, 2006
- 15th lecture Dec 15, 2006
- 16th lecture Jan 11, 2006
- 17th lecture Jan 12, 2006
- 18th lecture Jan 25, 2006
- 19th lecture Jan 26, 2006
- 20th+21st lecture Feb 1+2, 2006
Exercises
- exercise sheet 1 (solution)
- exercise sheet 2 (solution)
- exercise sheet 3 (solution)
- exercise sheet 4 (solution)
- exercise sheet 5 (solution)
- exercise sheet 6 (solution)
- exercise sheet 7
- exercise sheet 8 (solution)
- exercise sheet 9 (solution)
- exercise sheet 10
Exam
Instead of a written test there will be an oral exam at the end of the term. The members of each discussion group can choose whether the exam will proceed as a single or a group test. Students can obtain admissions for the final exam by participating 50% of the exercises (discussion groups).
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. 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.
Links & Literature
- Principles of Model-Checking (password protected)
- Spin - Formal Verification (a SPIN-Tutorial will held in the middle of the term)