Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
fv19:top [2019/08/13 17:43] vkuncak [Formal Verification EPFL Course (CS-550), Fall 2019] |
fv19:top [2019/08/21 15:12] vkuncak |
||
---|---|---|---|
Line 5: | Line 5: | ||
Autumn 2019 Semester. 2h Lectures, 2h Exercises, 2h Labs. Continuous Control | Autumn 2019 Semester. 2h Lectures, 2h Exercises, 2h Labs. Continuous Control | ||
- | Instructors: [[http://lara.epfl.ch/~kuncak/|Viktor Kuncak]] and [[https://people.epfl.ch/jad.hamza?lang=en|Jad Hamza]] | + | Instructors: [[http://lara.epfl.ch/~kuncak/|Viktor Kuncak]], [[https://people.epfl.ch/jad.hamza?lang=en|Jad Hamza]], with the help of Romain Edelmann, Georg Schmid, Romain Ruetschi |
One of the verification tools used: [[http://stainless.epfl.ch/|Stainless]] | One of the verification tools used: [[http://stainless.epfl.ch/|Stainless]] | ||
- | |||
- | [[http://concrete-semantics.org|Concrete semantics]] | ||
===== Introduction ===== | ===== Introduction ===== | ||
- | In this course we introduce formal verification as an approach for developing highly reliable systems. | + | In this course we introduce formal verification as a principled approach for developing systems that do what they should do. |
Formal verification finds proofs that computer systems work | Formal verification finds proofs that computer systems work | ||
Line 34: | Line 32: | ||
In this course we will learn how to use formal verification tools and explain the theory and the practice behind them. | In this course we will learn how to use formal verification tools and explain the theory and the practice behind them. | ||
- | |||
Warmup videos by others: | Warmup videos by others: | ||
Line 41: | Line 38: | ||
* [[https://www.youtube.com/channel/UCP2eLEql4tROYmIYm5mA27A|Verification Corner videos - by Rustan Leino and others]] | * [[https://www.youtube.com/channel/UCP2eLEql4tROYmIYm5mA27A|Verification Corner videos - by Rustan Leino and others]] | ||
- | ===== Topics ===== | + | ===== Outline ===== |
+ | |||
+ | **First class: Thursday 19 September at 15:15 in the classroom INF213.** | ||
+ | |||
+ | **Part I: Introduction and Finite State Systems** | ||
+ | |||
+ | ==== Week 01, September 16 ==== | ||
+ | |||
+ | | Thursday | 15:15 | Lecture 01: Introduction. State machines | | ||
+ | | Thursday | 17:15 | Labs 01: Scala, Stainless, and State Machines | | ||
+ | | Friday | 13:15 | Exercises 01: Proofs about state machines | | ||
+ | |||
+ | ==== Week 02, September 23 ==== | ||
+ | |||
+ | | Thursday | 15:15 | Lecture 02: Explicit-State Exploration. BDDs | | ||
+ | | Thursday | 17:15 | Labs 02: Explicit-State Reachability Checker | | ||
+ | | Friday | 13:15 | Exercises 02: BDDs | | ||
+ | |||
+ | ==== Week 03, September 30 ==== | ||
+ | |||
+ | | Thursday | 15:15 | Lecture 03: Bounded Model Checking and SAT | | ||
+ | | Thursday | 17:15 | Labs 03: BDD-Based Reachability Checker | | ||
+ | | Friday | 13:15 | Exercise 03: Propositional logic and SAT | | ||
+ | |||
+ | ==== Week 04, October 7 ==== | ||
+ | |||
+ | | Thursday | 15:15 | Lecture 04: Hardware Verification | | ||
+ | | Thursday | 17:15 | Labs 04: SAT-Based Checker | | ||
+ | | Friday | 13:15 | Lecture 05: Interpolation and Other Property-Based Algorithms | | ||
+ | |||
+ | **Part II: Deductive Program Verification** | ||
+ | |||
+ | Loop Invariants. Hoare Logic. Statically Checked Function Contracts. Relational Semantics and Fixed-Point Semantics. Symbolic Execution. Satisfiability Modulo Theories. | ||
+ | |||
+ | **Part III: Abstract Interpretation** | ||
+ | |||
+ | Abstract Interpretation framework. Predicate Abstraction. | ||
+ | |||
+ | **Part IV: Proof Assistants and Verified Software** | ||
+ | |||
+ | Stainless. Isabelle. Coq. Imperative programs with Heap. Concurrency. | ||
+ | |||
+ | ===== Topic List ===== | ||
* Importance of Reliable Systems. Methodology of Formal Verification. Soundness and Completeness in Modeling and Tools. Successful Tools and Flagship Case Studies | * Importance of Reliable Systems. Methodology of Formal Verification. Soundness and Completeness in Modeling and Tools. Successful Tools and Flagship Case Studies | ||
Line 63: | Line 102: | ||
* Michael Huth and Mark Rayan: Logic in Computer Science - Modelling and Reasoning about Systems. Cambridge University Press 2004. | * Michael Huth and Mark Rayan: Logic in Computer Science - Modelling and Reasoning about Systems. Cambridge University Press 2004. | ||
* Handbook of Model Checking, https://www.springer.com/de/book/9783319105741 Springer 2018. Including Chapter Model Checking Security Protocols by David Basin. | * Handbook of Model Checking, https://www.springer.com/de/book/9783319105741 Springer 2018. Including Chapter Model Checking Security Protocols by David Basin. | ||
- | * Tobias Nipkow, Gerwin Klein: Concrete Semantics with Isabelle/HOL. http://concrete-semantics.org/concrete-semantics.pdf | + | * Tobias Nipkow, Gerwin Klein: [[http://concrete-semantics.org|Concrete semantics]] with Isabelle/HOL. http://concrete-semantics.org/concrete-semantics.pdf |
* Aaron Bradley and Zohar Manna: The Calculus of Computation - Decision Procedures with Applications to Verification, Springer 2007. | * Aaron Bradley and Zohar Manna: The Calculus of Computation - Decision Procedures with Applications to Verification, Springer 2007. | ||
* Nielson, Flemming, Nielson, Hanne R., Hankin, Chris: Principles of Program Analysis. ISBN 978-3-662-03811-6. Springer 1999. | * Nielson, Flemming, Nielson, Hanne R., Hankin, Chris: Principles of Program Analysis. ISBN 978-3-662-03811-6. Springer 1999. |