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/06/18 21:46] vkuncak |
fv19:top [2019/06/18 22:03] 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 | ||
+ | ===== Introduction ===== | ||
- | **Formal verification** finds proofs that computer systems work | + | In this course we introduce formal verification as an approach for developing highly reliable systems. |
+ | |||
+ | Formal verification finds proofs that computer systems work | ||
under all scenarios of interest. Formal verification tools help developers | under all scenarios of interest. Formal verification tools help developers | ||
construct such proofs, automatically searching for proofs | construct such proofs, automatically searching for proofs | ||
Line 17: | Line 20: | ||
verified software is to perform formal verification while software is | verified software is to perform formal verification while software is | ||
developed, as opposed to after the fact. | developed, as opposed to after the fact. | ||
+ | |||
+ | In this course we will learn how to use formal verification tools and explain the theory and the practice behind building them. | ||
Line 23: | Line 28: | ||
* [[http://slideshot.epfl.ch/play/suri_moore|Machines Reasoning about Machines - EPFL talk by J Moore]] | * [[http://slideshot.epfl.ch/play/suri_moore|Machines Reasoning about Machines - EPFL talk by J Moore]] | ||
* [[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 ===== | ||
+ | |||
+ | Importance of Reliable Systems. Methodology of Formal Verification. Soundness and Completeness in Modeling and Tools. Successful Tools and Flagship Case Studies | ||
+ | |||
+ | Review of Sets, Relations, Computability, Propositional and First-Order Logic Syntax, Semantics, Sequent Calculus. | ||
+ | |||
+ | Completeness and Semi-Decidability for First-Order Logic. Inductive Definitions and Proof Trees. Higher-Order Logic and LCF Approach. | ||
+ | |||
+ | State Machines. Transition Formulas. Traces. Strongest Postconditions and Weakest Preconditions. | ||
+ | |||
+ | Hoare Logic. Inductive Invariants. Well-Founded Relations and Termination Measures | ||
+ | |||
+ | Modeling Hardware: Verilog to Sequential Circuits | ||
+ | |||
+ | Linear Temporal Logic. System Verilog Assertions. Monitors | ||
+ | |||
+ | SAT Solvers and Bounded Model Checking | ||
+ | |||
+ | Model Checking using Binary Decision Diagrams | ||
+ | |||
+ | Loop Invariants. Hoare Logic. Statically Checked Function Contracts. Relational Semantics and Fixed-Point Semantics | ||
+ | |||
+ | Symbolic Execution. Satisfiability Modulo Theories | ||
+ | |||
+ | Abstract Interpretation and Predicate Abstraction | ||
+ | |||
+ | Information Flow and Taint Analysis | ||
+ | |||
+ | Verification of Security Protocols | ||
+ | |||
+ | Dependent and Refinement Types | ||
+ | |||
+ | ===== Relevant Textbooks ===== | ||
+ | |||
+ | * 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. | ||
+ | * Tobias Nipkow, Gerwin Klein: 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. | ||
+ | * Nielson, Flemming, Nielson, Hanne R., Hankin, Chris: Principles of Program Analysis. ISBN 978-3-662-03811-6. Springer 1999. | ||
+ | * Peter B. Andrews: An Introduction to Mathematical Logic and Type Theory (To Truth Through Proof), Springer 2002. | ||
+ | * http://logitext.mit.edu/tutorial | ||
+ | |||
+ | ==== Additional Introductions and Background ==== | ||
+ | |||
+ | * Kenneth H. Rosen. Discrete Mathematics and Its Applications. E.g. 8th Edition. | ||
+ | * Formally Verified Software in the Real World. Communications of the ACM, October 2018. https://cacm.acm.org/magazines/2018/10/231372-formally-verified-software-in-the-real-world/fulltext | ||