Lecture: Software Analysis and Verification

Content

This course covers advanced techniques for automatic software verification, especially techniques belonging to the field of program analysis or software model checking. The course continues the bachelor course Formal Verification and Specification 1 (FSV 1). Knowledge from FSV 1 is helpful, but not mandatory. The following list provides on overview of topics covered by the course

Organization

Lecturer, Tutor: Dr. Marie-Christine Jakobs

Dates

Lecture: Mondays 9am - 12pm, Amalienstr. 73A, Room 220
First lecture: October 15th, 2018

Tutorial: Thursdays 2pm - 4pm, Amalienstr. 73A, Room 211
First tutorial: October 18th, 2018

Audience

Master Computer Science (Master Informatik)

Material

Die folgenden Materialien unterliegen dem Copyright. Teilnehmern der Vorlesung ist die Verwendung für persönliche Studien gestattet. Alle anderen Rechte sind vorbehalten.
English Translation The following material is subject to copyright. Participants of the course are granted to use the material for personal studies only. All rights are reserved.

User name and password will be announced in the lecture and the tutorial.

Lecture Slides

DateTopicsSlides
12018-10-15Organisation,
Introduction,Program Syntax
swav_01.pdf
22018-10-22Concrete semantics,
Abstract Domains, Abstract semantics
swav_02.pdf
32018-10-29Example domains,
Flow-insensitiv analysis
swav_03.pdf
42018-11-05Dataflow analysisswav_04.pdf
52018-11-12Model Checking
Configurable Program Analysis
Abstract Reachability Graph
swav_05.pdf
62018-11-19Counterexample-guided abstraction refinementswav_06.pdf
72018-11-26Sliced prefixes, large block encoding
automata-based model checking
swav_07.pdf
82018-12-03Bounded model checkingswav_08.pdf

Exercises

DateSheetExample SolutionComments
12018-10-18sheet01.pdfsolution01.pdf
22018-10-25sheet02.pdfsolution02.pdf
A2018-11-01self-study-01.pdfself-study-01-solution.pdfSelf-study assignment
32018-11-08sheet03.pdfsolution03.pdf
42018-11-15sheet04.pdfsolution04.pdf
52018-11-22sheet05.pdfsolution05.pdf
62018-11-29sheet06.pdfsolution06.pdf
62018-12-06sheet07.pdf

Exams

Literature

to be continued
  1. Nielson, Flemming, Hanne R. Nielson, and Chris Hankin. Principles of program analysis. Springer, 1999
  2. Edmund M. Clarke, Thomas A. Henzinger, Helmut Veith, Roderick Bloem (Eds.). Handbook of Model Checking. Springer, 2018.

  3. Vijay D'Silva, Daniel Kroening, Georg Weissenbacher. A Survey of Automated Techniques for Formal Software Verification. IEEE Trans. on CAD of Integrated Circuits and Systems 27(7), IEEE, 2008
  4. Ranjit Jhala and Rupak Majumdar. Software model checking. ACM Comput. Surv. 41(4), Article 21, ACM, 2009.

  5. Dirk Beyer, Thomas A. Henzinger, GrégoryThéoduloz. Configurable Software Verification: Concretizing the Convergence of Model Checking and Program Analysis. CAV 2007, Lecture Notes in Computer Science, vol 4590, Springer, 2009.
  6. Dirk Beyer, Stefan Löwe, Philipp Wendler. Sliced Path Prefixes: An Effective Method to Enable Refinement Selection. FORTE 2015, Lecture Notes in Computer Science, vol 9039, Springer, 2015.
  7. Dirk Beyer, Alessandro Cimatti, Alberto Griggio, M. Erkan Keremoglu, Roberto Sebastiani. Software model checking via large-block encoding. FMCAD 2009, IEEE, 2009.
  8. Matthias Heizmann, Jochen Hoenicke, Andreas Podelski. Refinement of Trace Abstraction. SAS 2009, Lecture Notes in Computer Science, vol 5673, 2009.