E0 227 Program Analysis and Verification
August-December 2022, 11 am - 12.30pm Mon Wed, Room 117, CSA
K. V. Raghavan,
Teaching assistants: Arjya Das (arjyadas), Rupashree
- Aug. 3: Introduction.
- Aug. 8, 10: Lattice theory.
- Aug. 17, 22: Introduction to abstract interpretation.
- Aug. 24, 29: Correctness of abstract
interpretation. Associated lecture
- Sep. 5, 7: Kildall's algorithm. Associated
- Sep. 12, 14, 19: Call
strings approach to inter-procedural analysis.
- Sep. 21, 26: Functional approach to inter-procedural analysis.
- Sep. 28, Oct. 10, 12: Pointer analysis. Part
1 (pptx), Part 2 (pptx).
1 (pdf), Part 2 (pdf).
- Oct. 17, 19, 21: PDGs and Intraprocedural
- Oct. 26, Oct. 31, Nov. 2: Hoare
- Nov. 7, 9: Simply Typed Lambda
- Nov. 14, 16: Polymorphic
Program analysis is a collection of techniques for computing approximate
information about a program. Program analysis finds several applications:
in compilers, in tools that help programmers understand and modify
programs, and in tools that help programmers verify that programs satisfies
certain properties of interest. As software systems have become larger and
more complex there has been a lot of practical interest in using
program-analysis based tools to assist with software development. In this
course we will learn about techniques to reason about the meaning of and
the properties of a
program, and the
theory behind foundational program-analysis techniques such as abstract
interpretation, type systems, and theorem proving. We will also look at
an important application of program analysis, namely the operation of
We will assume that students have exposure to programming, the fundamental
concepts of programming languages, and the basics of mathematical logic and
discrete structures. However, no prior knowledge of program analysis is
Interpretation: Lattices, abstract join-over-all-paths analysis of a
program. Correctness of abstract information: Galois connections, abstract
interpretation as an over-approximation of concrete semantics. Dataflow
analysis: Computing an over-approximation of join-over-all-paths
information using Kildall's algorithm, by modeling the statements in the
program as a set of equations. Analysis of multi-procedure programs. Type
Systems: Monomorphic type systems. Pointer analysis of
imperative programs. Program slicing. Assertional reasoning using Hoare