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 22:02] vkuncak |
fv19:top [2019/06/18 22:07] vkuncak |
||
|---|---|---|---|
| Line 4: | Line 4: | ||
| 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]] | ||
| ===== Introduction ===== | ===== Introduction ===== | ||
| Line 20: | Line 22: | ||
| 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. | ||
| + | |||
| + | Companies, research labs and research groups have developed | ||
| + | proofs of correctness of operating system kernels, brake | ||
| + | system for a metro line in Paris, compilers, databases, data | ||
| + | structures, smartcard wallets, communication protocols, and | ||
| + | distributed systems. | ||
| In this course we will learn how to use formal verification tools and explain the theory and the practice behind building them. | In this course we will learn how to use formal verification tools and explain the theory and the practice behind building them. | ||
| Line 31: | Line 39: | ||
| ===== Topics ===== | ===== Topics ===== | ||
| - | 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 |
| - | + | * Review of Sets, Relations, Computability, Propositional and First-Order Logic Syntax, Semantics, Sequent Calculus. | |
| - | 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. | |
| - | Completeness and Semi-Decidability for First-Order Logic. Inductive Definitions and Proof Trees. Higher-Order Logic and LCF Approach. | + | * Hoare Logic. Inductive Invariants. Well-Founded Relations and Termination Measures |
| - | + | * Modeling Hardware: Verilog to Sequential Circuits | |
| - | State Machines. Transition Formulas. Traces. Strongest Postconditions and Weakest Preconditions. | + | * Linear Temporal Logic. System Verilog Assertions. Monitors |
| - | + | * SAT Solvers and Bounded Model Checking | |
| - | Hoare Logic. Inductive Invariants. Well-Founded Relations and Termination Measures | + | * Model Checking using Binary Decision Diagrams |
| - | + | * Loop Invariants. Hoare Logic. Statically Checked Function Contracts. Relational Semantics and Fixed-Point Semantics | |
| - | Modeling Hardware: Verilog to Sequential Circuits | + | * Symbolic Execution. Satisfiability Modulo Theories |
| - | + | * Abstract Interpretation and Predicate Abstraction | |
| - | Linear Temporal Logic. System Verilog Assertions. Monitors | + | * Information Flow and Taint Analysis |
| - | + | * Verification of Security Protocols | |
| - | SAT Solvers and Bounded Model Checking | + | * Dependent and Refinement Types |
| - | + | ||
| - | 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 ===== | ===== Relevant Textbooks ===== | ||
| - | * 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 |
| - | + | * Aaron Bradley and Zohar Manna: The Calculus of Computation - Decision Procedures with Applications to Verification, Springer 2007. | |
| - | * Tobias Nipkow, Gerwin Klein: Concrete Semantics with Isabelle/HOL. http://concrete-semantics.org/concrete-semantics.pdf | + | * 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. | |
| - | * Aaron Bradley and Zohar Manna: The Calculus of Computation - Decision Procedures with Applications to Verification, Springer 2007. | + | * http://logitext.mit.edu/tutorial |
| - | + | ||
| - | * 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 | + | ===== Background ===== |
| - | * Kenneth H. Rosen. Discrete Mathematics and Its Applications. E.g. 8th Edition. | + | * 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 | + | * 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 |