CIS 673: Computer-Aided Verification, Fall 2012
Class: Tues Thurs 10.30--12.00, Towne 307
Over the past two decades, techniques for formal verification have matured
to allow analysis of real-world software.
This course will introduce students to methods and tools
for software verification.
During Fall 2012, we plan to cover following topics
- Program verification: Assertions, inductive invariants, partial vs. total correctness
- Program analysis: Dataflow analysis, Algorithms for alias analysis
- Constraint solvers: Formal logic, decision procedures, SAT solvers, SMT solvers
- Efficient search: Explicit-state vs. symbolic search, Heuristics for scalability
- Software model checking: Predicate abstraction, counter-example guided abstraction refinement, interpolants
- Theory of model checking: Temporal logics, Omega-regular languages
- Concurrency analysis: Race detection, Partial-order reduction, Context-bounded scheduling
- Software synthesis: Sketching, constraint-based synthesis, algorithmic controller synthesis
The course requires basic knowledge of algorithms, data structures,
programming languages, automata theory, computational complexity, and
The course requires mathematical maturity, and is appropriate
for graduate students who wish to pursue research in
formal methods, software analysis, or related areas.
If you need more information to decide, contact the instructor.
Reading material will consist of both survey papers and recent research papers.
Every week, students are expected to read the papers related to the topic, before
the lectures, and participate actively during class.
Each student is also expected to do a project and give a presentation at the end of the semester.
There will be no homeworks or exams.
- Sept 6, 11: Basics of program verification
Reading: Chapter 5 (pages 113 -- 152) of The Calculus of Computation, Bradley and Manna, Springer, 2007.
- Sept 13 : Modern SAT solvers
Talk by Sharad Malik
Reading: Propositional SAT solving; Marques-Silva, Malik, and Zhang.
- Sept 18, 20, Oct 1 : Satisfiability Modula Theories
Lectures: SMT tutorial by Leonardo de Moura of MSR; Part 1; Part 2; Part 3
Overview paper; De Moura and Bjorner; CACM 2011.
Detailed survey; Barrett, Seshia, Sebastiani, and Tinelli; 2009
- Sept 25, 27: Program analysis; dataflow analysis and interprocedural analysis
Lectures by Santosh Nagarkatte
- Oct 9, 11: State-space search: Explicit-state vs symbolic
Raeding: Sections 2.3 and 2.4 of Principles of Embedded Computation, Alur; Chapter 2
- Oct 18: Software model checking
BLAST tutorial slides
Overview of SLAM project in CACM, July 2011
- Course Project
- Oct 25,30: Scalable verification
Tutorial by Ken McMillan
Survey paper by Ken McMillan
- Nov 6, 8: Concurrency Verification
Slides of tutorial by Shaz Qadeer
- Nov 15,20: Program synthesis
Dimensions in Program Synthesis by Sumit Gulwani; Slides
Program synthesis by Sketching by Ras Bodik
- Nov 27, 29, Dec 4: Project presentations by students