Content
Model checking is a widely used technique for automatic verification and debugging of both software and hardware, with the power to reveal subtle errors that remain undiscovered using testing.
Therefore, model checking is an effective technique to expose potential design errors and improve software and hardware reliability, and it is gaining wide industrial acceptance.
Its inventors Edmund M. Clarke, E. Allen Emerson, and Joseph Sifakis have been awarded the significant Turing award in 2007.
How does model checking work? What are its underlying principles?
This is the focus of this course! Model checking is based on well-known paradigms from automata theory, graph algorithms, logic, and data structures. In the course, we first explain what these
models actually are. We introduce temporal logics (e.g., LTL and CTL) to formalize various classes of system properties such as safety, liveness and fairness, and discuss in detail model checking algorithms for these logics.
Practicals
As part of the practicals accompanying the lecture, you will build your own simple model checker that supports two popular algorithms. Here, we first introduce you to the basics of hardware implementations, safety and liveness, as well as symbolic representation and SMT solvers. Afterward, we use these building blocks to implement the
bounded model checking algorithm you will learn in the lecture. Finally, we extend the BMC implementation so it can make unbounded proofs using K-Induction.
Material
The course is based on:
Model Checking, second edition
by Edmund M. Clarke Jr., Orna Grumberg, Daniel Kröning, Doron Peled, Helmut Veith
MIT Press,
ISBN-13: 978-0262038836
ISBN-10: 0262038838
Model Checking
The lectures on probabilistic Model Checking are based on
Principles of Model Checking
by Christel Baier and Joost-Pieter Katoen
MIT Press,
ISBN-13: 978-0262026499
ISBN-10: 026202649X
Principles of Model Checking
Previous years:
SS2021 SS2022 SS2023
Administrative Information
Lecture
There are two ways to get a grade for the lecture:
Option 1: You
participate in class and do the
homework.
Option 2: You take an
exam.
If you partisipate in class and you do the homework, you will get a grade for the course. To get a passing grade, you can miss at most two classes and skip at most two homework exercises. You get a 0-10 mark as the average of
all homework exercises. Non-handed exercises count as 0 points for the average. From the 0-10 mark, the final grades are distributed as follows:
| Points |
Grade |
| < 5 |
5 |
| 5 - 6.24 |
4 |
| 6.25 - 7.49 |
3 |
| 7.5 - 8.74 |
2 |
| 8.75 - 10 |
1 |
Homework is done in groups of one or two persons. When you submit your homework (per email), be sure to include the names and immatriculation numbers of all group members.
If you don't want to do the homework or you get a failing grade for the homework, you can do a regular exam. Please let us know when you want the exam!
Practicals
The practicals are done individually and consist of three assignments with point distribution 30/40/30. We follow the standard grading scheme, where you need more than 50% of the points for passing, and all other grades are distributed evenly in 12.5% increments. In addition to automated tests, we also rely on manual inspection of your submissions. The assignments will usually be presented after the lecture. The practicals time slots will be used for assignment presentations, tutorials and question hours. Feel free to ask questions anytime in the
Discord channel as well. Also, take advantage of our new and feature-rich
test system and see how well your submissions are doing against our test suite and other students.
Lecture Schedule
| Date |
Type |
Topic |
Lecturer |
Slides |
Homework |
| 11.03.2024 09:00-11:00 IFEG042 |
Lecture |
Intro |
Roderick |
mc01-intro |
none |
| 18.03.2024 09:00-11:00 IFEG042 |
Lecture |
SAT-Based Model Checking (BMC, k-induction) - Chapter 10 |
Roderick |
mc03-modeling, mc10-satbasedmc3 |
hw1 |
| 08.04.2024 09:00-11:00 IFEG042 |
Lecture |
SAT-Based Model Checking (interpolation) -Chapter 10 |
Roderick |
|
hw2 |
| 15.04.2024 09:00-11:00 IFEG042 |
Lecture |
SAT-Based Model Checking (PDR) - Chapter 10 |
Roderick |
|
hw3 |
| 22.04.2024 09:00-11:00 IFEG042 |
Lecture |
Temporal Logic - Chapter 4 |
Bettina |
slides_mc4 temporalLogic |
hw4 |
| 29.04.2024 09:00-11:00 IFEG042 |
Lecture |
CTL Model Checking - Chapter 5 |
Bettina |
|
|
| 06.05.2024 09:00-11:00 IFEG042 |
Lecture |
CTL Model Checking - Chapter 5 |
Bettina |
|
|
| 13.05.2024 09:00-11:00 IFEG042 |
Lecture |
LTL Model Checking -Chapter 7 |
Bettina |
|
|
| 27.05.2024 09:00-11:00 IFEG042 |
Lecture |
Probabilistic Model Checking - Chapter 10 - PRISM & Reachability in Markov Chains |
Stefan |
|
|
| 03.06.2024 09:00-11:00 IFEG042 |
Lecture |
Probabilistic Model Checking – Chapter 10 – PCTL and MDPs |
Stefan |
|
|
| 10.06.2024 09:00-11:00 IFEG042 |
Lecture |
Probabilistic Model Checking - Tempest and Shielded Reinforcement Learning |
Stefan |
|
|
| 17.06.2024 09:00-11:00 IFEG042 |
|
Reserved slot for exam (if asked for) |
|
|
|
Practicals Schedule
| Date |
Type |
Topic |
Lecturer |
Material |
| 11.03.2024 11:00-12:00 IFEG042 |
Lecture |
Intro (merged with lecture) |
Roderick |
|
| 18.03.2024 11:00-12:00 IFEG042 |
Handout |
Warmup Exercise |
Vedad |
assignment1 |
| 08.04.2024 11:00-12:00 IFEG042 |
Tutorial |
Introduction to Z3 |
Vedad |
demo-1 |
| 15.04.2024 11:00-12:00 IFEG042 |
Handout |
BMC Exercise |
Vedad |
demo-2 |
| 21.04.2024 23:59 Online |
Deadline |
Warmup Deadline |
--- |
|
| 22.04.2024 11:00-12:00 IFEG042 |
Question Hour |
Question Hour BMC |
Vedad |
assignment2 |
| 29.04.2024 11:00-12:00 IFEG042 |
Tutorial |
Hardware and Verilog |
Vedad |
|
| 06.05.2024 11:00-12:00 IFEG042 |
Handout |
K-Induction Exercise |
Vedad |
|
| 13.05.2024 11:00-12:00 IFEG042 |
Question Hour |
Question Hour K-Induction |
Vedad |
|
| 22.05.2024 23:59 Online |
Deadline |
BMC Deadline |
--- |
|
| 27.05.2024 11:00-12:00 IFEG042 |
Question Hour |
Question Hour K-Induction |
Vedad |
|
| 02.06.2024 23:59 Online |
Deadline |
K-Induction Deadline |
--- |
|
Communication and Venue
Lecture and practicals are both
on campus. However, we also encourage students to join the #MC channel (🤖) on the official
IAIK Discord server, where you can talk with other students, ask us questions about the courses and get updates.
Lecture Dates
| Date |
Begin |
End |
Location |
Event |
Type |
Comment |
| 2024/04/29 |
09:00 |
11:00 |
Seminarraum |
Abhaltung |
VO |
fix/ |
| 2024/04/29 |
11:00 |
12:00 |
Seminarraum |
Abhaltung |
UE |
fix/ |
| 2024/05/06 |
09:00 |
11:00 |
Seminarraum |
Abhaltung |
VO |
fix/ |
| 2024/05/06 |
11:00 |
12:00 |
Seminarraum |
Abhaltung |
UE |
fix/ |
| 2024/05/13 |
09:00 |
11:00 |
Seminarraum |
Abhaltung |
VO |
fix/ |
| 2024/05/13 |
11:00 |
12:00 |
Seminarraum |
Abhaltung |
UE |
fix/ |
| 2024/05/27 |
09:00 |
11:00 |
Seminarraum |
Abhaltung |
VO |
fix/ |
| 2024/05/27 |
11:00 |
12:00 |
Seminarraum |
Abhaltung |
UE |
fix/ |
| 2024/06/03 |
09:00 |
11:00 |
Seminarraum |
Abhaltung |
VO |
fix/ |
| 2024/06/03 |
11:00 |
12:00 |
Seminarraum |
Abhaltung |
UE |
fix/ |
| 2024/06/10 |
09:00 |
11:00 |
Seminarraum |
Abhaltung |
VO |
fix/ |
| 2024/06/10 |
11:00 |
12:00 |
Seminarraum |
Abhaltung |
UE |
fix/ |
| 2024/06/17 |
09:00 |
11:00 |
Seminarraum |
Abhaltung |
VO |
fix/ |
| 2024/06/17 |
11:00 |
12:00 |
Seminarraum |
Abhaltung |
UE |
fix/ |
| 2024/06/24 |
11:00 |
12:00 |
Seminarraum |
Abhaltung |
UE |
fix/ |
Lecturers
