In this course we introduce formal verification as a principled approach for developing systems that do what they should do.

Moodle

Autumn 2019 Semester. 2h Lectures, 2h Exercises, 2h Labs. Continuous Control.

CS-550 in Course Catalog

Instructors: Viktor Kuncak, Jad Hamza, with the help of Romain Ruetschi

All project assignments will be in Scala. If you do not know Scala, please consider these free EPFL Courseware courses:

• Functional Programming Principles in Scala
• Functional Program Design in Scala

The primary verification tools used: Stainless. Stainless is a formal way of doing Scala.

• 40% based on the quiz on 12 December: 15:15-18:00. You can bring printed lecture and exercise slides
• 60% based on all lab assignments and home works taken together

There will be 7 labs in total: 6 fixed ones that everyone should do individually, and a 7th one that are to be done in groups of 1-3 students. You will need to present the plan for the final lab in the last week of the semester.

First class: Thursday 19 September at 15:15 in the classroom INF213.

The material consists of approximately four parts:

• I: Introduction and Finite State Systems
• II: Proof Assistants
• III: Automating Software Verification
• IV: Semantics for Verification

Part I: Introduction and Finite State Systems

Watch and understand the Talk of J Moore 'Machines Reasoning about Machines'

Reading:

• Chapter 10 of the Model Checking Handbook

Reading:

• Chapter 9 of the Model Checking Handbook
• A Lecture and material on SAT
• Chapter 24 and 2 of the Model Checking Handbook

For further reading, check some of the recent papers:

• Interpolating Property Directed Reachability (CAV 2014)
• Interpolating Strong Induction (CAV 2019)

Part II: Proof Assistants

Reading for LCF approach:

• Michael J. C. Gordon. From LCF to HOL: a short history. In Gordon Plotkin, Colin Stirling, and Mads Tofte,editors,Proof, Language, and Interaction: Essays in Honor of Robin Milner, pages 169–185. MIT Press, 2000.
• Practical Logic and Automated Reasoning (Harrison), Chapter 6

Reading for resolution:

• Practical Logic and Automated Reasoning (Harrison), Chapter 3

Reading:

• Isabelle proof assistant (with tutorials), especially Programming and Proving in Isabelle/HOL
• Concrete Semantics (source of the slides and demos)
• From LCF to Isabelle/HOL
• Isabelle Wiki
• Patter-Based Subterm Selection (for precise rewriting); see also src/HOL/ex/Rewrite_Examples.thy

More advanced:

• Isabelle programming tutorial

Part III: Automating Software Verification

• older slides

Milestones in SMT solver development:

• results of Nelson and Oppen, including Nelson's dissertation
• inclusion of SAT solvers and the DPLL(T) algorithm: Solving SAT and SAT Modulo Theories: from an Abstract Davis-Putnam-Logemann-Loveland Procedure to DPLL(T)
• The SMT-LIB initiative with standardized format, benchmarks, and competitions
• The provers such as Z3 prover

Introduction from Selected VeriFun slides (Full VeriFun slides are here)

A web demo version of the Leon system:

• http://leon.epfl.ch/
• Recording of Leon Demo

Part IV: Semantics for Verification

• Modelling local state and program heap. Intermediate verification languages (Why3, Horn clauses, Inox)
  • Example paper: SideTrail: Verifying Time-Balancing of Cryptosystems (based on Boogie)
• 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

• Aaron Bradley and Zohar Manna: The Calculus of Computation - Decision Procedures with Applications to Verification, Springer 2007.
• Handbook of Model Checking, https://www.springer.com/de/book/9783319105741 Springer 2018. Available online from within EPFL through the EPFL library
• Tobias Nipkow, Gerwin Klein: Concrete semantics with Isabelle/HOL. http://concrete-semantics.org/concrete-semantics.pdf
• John Harrison: Handbook of Practical Logic Logic and Automated Reasoning (resources)
• Michael Huth and Mark Rayan: Logic in Computer Science - Modelling and Reasoning about Systems. Cambridge University Press 2004.
• 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

• Exercises on the 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

Formal verification finds proofs that computer systems work under all scenarios of interest. Formal verification tools help developers construct such proofs, automatically searching for proofs using theorem proving and constraint solving (using, e.g. SMT solvers), and static analysis to discover program invariants. When it succeeds, formal verification is guaranteed to identify all software errors, including, for example, security vulnerabilities or cases when the computation produces a wrong numerical or symbolic result. The best approach to obtain formally verified software is to perform formal verification while software is 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 them.

A short illustrative video: What is Formal Verification? - by Galois, a formal methods company

Somewhat related past course: SAV 2017