Scalable Software Verification
The Scalable Software Verification course (formerly Separation Logic)is a 4th year MEng and MSc course on local reasoning about programs that manipulate the heap at the Department of Computing, Imperial College London.
Description of the Course
In the late 1960s, Tony Hoare developed Hoare logic, a formal system with a set of rules for reasoning rigorously about the correctness of imperative programs that alter the variable state. However, Hoare logic is not good at reasoning about imperative programs that alter the heap state, since the reasoning does not scale. In 2001, building on Hoare’s work and early ideas from Burstall, O’Hearn and Reynolds introduced separation logic, in which the reasoning does scale.
The course comprises two hours a week for seven weeks. It is be accompanied by comprehensive course notes, which bring together a variety of ideas from the most influential research papers.
The first four weeks will provide a basic introduction to separation logic for reasoning about mutable data structures, using linked lists and binary trees as the primary examples. You will learn how to write program specifications and prove properties of programs, both informally using sketch proofs and formally using rigorous proofs.
The next two weeks will describe tools, demonstrating that reasoning about real-world programs using separation logic is feasible. You will learn about Smallfoot, a semi-automatic verification tool based on symbolic execution, and Infer, an automatic tool based on bi-abduction. This work constitutes a breakthrough, in that it is now possible prove properties about millions of lines of code, thus making the reasoning viable for industry.
As part of the course, Facebook with Imperial ran a lab on Infer. See our Infer lab 2016 page for details
The last week will provide an introduction to concurrent separation logics. With Brookes, O’Hearn won the Godel prize for this work in 2016.
General Information for 2021 autumn term
Time: Mondays 2pm-4pm, 2nd through 9th week, Room 145 and Thursdays 11am-1pm, 2nd through 9th week, Room 145
Coursework: Published TBC / deadline TBC.
Exam: The exam will take place December, date and time TBC. It will last for 70 minutes. You will be given three questions, out of which you need to answer two of your choice.
Recommended Reading: Mike Gordon has some excellent notes on Hoare logic, which briefly touches on separation logic in the last chapter. Two good books on Hoare logic are: Logic in Computer Science: Modelling and Reasoning about Systems, Michael Huth and Mark Ryan, CUP, 2004; and The Formal Semantics of Programming Languages: an Introduction, Glynn Winskel, MIT Press, 1993.
Most of the work on separation logic is in research papers. Excellent introductions to separation logic include: O’Hearn, Reynolds and Yang’s paper on Local Reasoning about Programs that Alter Data Structures, CSL 2001, and John Reynolds’ undergraduate course notes on separation logic and survey paper Separation Logic: A Logic for Shared Mutable Data Structures, LICS 2002, both found on Reynolds’ homepage. Andrew Appel has published a book on Program Logics for Certified Compilers, CUP 2014 (a copy is available in the library).
Papers describing tool techniques include: Symbolic Execution with Separation Logic, Berdine, Calcagno, O’Hearn, APLAS’05; A Local Shape Analysis based on Separation Logic, Distefano, O’Hearn, Yang, TACAS 2006; and Compositional Shape Analysis by Means of Bi-abduction, Calcagno, Distefano, O’Hearn, Yang, JACM 2011.
The initial paper on concurrent separation logic is Resources, Concurrency and Local Reasoning, O’Hearn, TCS, 2007, and is worth a read. The survey paper Steps in Modular Specifications of Concurrent Modules, da Rocha Pinto, Dinsdale-Young, Gardner, MFPS 2015, describes some modern developments in concurrent separation logics. There are many additional interesting links given on the Piazza site and below. If you have further suggestions on what reading material might be of interest, please let us know.
Public lecture by Tony Hoare entitled “Could computers understand their own programs?”, part of the annual Wheeler lectures series.
A re recording of a broadcast by Alan Turing, describing his work on soundness, completeness, Gödel’s theorem, Turing machines etc.
Floyd’s obituary and his seminal 1967 paper Assigning meanings to programs
Wikipedia article on Hoare and his seminal 1969 paper An axiomatic basis for computer programming
Programming Language Constructs for Which It Is Impossible To Obtain Good Hoare Axiom Systems by Edmund M. Clarke Jr.
Zune bug explained in detail
Scalable Specification and Reasoning: Technical Challenges for Program Logic by Peter O’Hearn
Microsoft projects: SLAM T2 termination prover SLAyer
Wikipedia article on Material Implication the Paradoxes of Material Implication and some classic fallacies
Collection of Software Bugs and Software Glitches
The VCC verifier can be downloaded from http://vcc.codeplex.com or tried at http://www.rise4fun.com/vcc
Peter Homeier’s Sunrise system
Design by Contract (a paper by Gary T. Leavens and Yoonsik Cheon)