Static Program Analysis

Instructors: Yue Li and Tian Tan

Course Information

Software Analysis or Static Program Analysis is a new course of Nanjing University developed by Yue Li and Tian Tan in Spring 2020. In this course, we will learn about static program analysis, a useful technique for improving the reliability, security and performance of software, and it becomes increasingly impactful in industries nowadays. The course covers two parts: theory and practice. In theory, various materials will be introduced: from the foundations of classical data-flow and pointer analyses to some advanced topics such as security analysis and soundiness. In practice, an educational static program analysis framework called bamboo was designed, on top of which we'll implement a series of assignments including constant propagation, dead code detection, CHA call graph construction, context-insensitive and context-sensitive pointer analyses.

Prerequisites

As prerequisites, you need to understand data structures and algorithms, and to be familiar with a programming language (Java would be better than others as our assignments are implemented in it). Compiler is not a prerequisite despite that understanding it would be preferable. The course is intended for advanced undergraduates as well as graduate students at all levels.

Lectures (Fall 2020)

Date	Class	Instructor	Slides [PDF]
Sep 10 (Thur)	Course Introduction	Yue Li	Introduction.pdf
Sep 17 (Thur)	Intermediate Representation	Yue Li	IR.pdf
Sep 24 (Thur)	Data Flow Analysis - Applications I	Yue Li	DFA-AP (I,II).pdf
Oct 10 (Sat)	Data Flow Analysis - Applications II	Yue Li	See above ฅ’ω’ฅ
Oct 15 (Thur)	Data Flow Analysis - Foundations I	Yue Li	DFA-FD (I,II).pdf
Oct 22 (Thur)	Data Flow Analysis - Foundations II	Yue Li	See above ฅ’ω’ฅ
Oct 29 (Thur)	Interprocedural Analysis	Tian Tan	Inter.pdf
Nov 5 (Thur)	Pointer Analysis	Tian Tan	PTA.pdf
Nov 12 (Thur)	Pointer Analysis - Foundations I	Tian Tan	PTA-FD (I,II).pdf
Nov 26 (Thur)	Pointer Analysis - Foundations II	Tian Tan	See above ฅ’ω’ฅ
Dec 3 (Thur)	Pointer Analysis - Context Sensitivity I	Tian Tan	PTA-CS (I,II).pdf
Dec 10 (Thur)	Pointer Analysis - Context Sensitivity II	Tian Tan	See above ฅ’ω’ฅ
Dec 17 (Thur)	Static Analysis for Security	Tian Tan	Security.pdf
Dec 23 (Wed)	Datalog-Based Program Analysis	Tian Tan	Datalog.pdf
Dec 24 (Thur)	Soundness and Soundiness	Tian Tan	Soundiness.pdf
Dec 31 (Thur)	CFL-Reachability and IFDS	Tian Tan	IFDS.pdf

Assignments

1. Constant Propagation Analysis (Assignment-1-description.pdf)
2. Dead Code Detection Analysis (Assignment-2-description.pdf)
3. Class Hierarchy Analysis (Assignment-3-description.pdf)
4. Pointer Analysis (Assignment-4-description.pdf)
5. Context-Sensitive Pointer Analysis (Assignment-5-description.pdf)

Reference Materials

1. Compilers: Principles, Techniques, and Tools (2nd), by Alfred V. Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman
2. Static Program Analysis, by Anders Møller and Michael I. Schwartzbach
3. Principles of Program Analysis, by Flemming Nielson, Hanne R. Nielson and Chris Hankin

We appreciate the researchers in the community of static program analysis for their inspiring lectures and papers, which provide us great materials to build this course.