Static Program Analysis

Course Information

Software Analysis or Static Program Analysis is a course of Nanjing University developed by Tian Tan and Yue Li 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, a brand new static program analysis framework called Tai-e was designed, on top of which we'll implement a series of assignments including live variable analysis, constant propagation, dead code detection, CHA call graph construction, context-insensitive and context-sensitive pointer analyses, and taint analysis.

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

LectureInstructorSlides (PDF)Videos
(Chinese)
Assignments
1. Course IntroductionYue LiIntro.pdf
2. Intermediate RepresentationYue LiIR.pdf
3. Data Flow Analysis - Applications IYue LiDFA-AP (I, II).pdf
4. Data Flow Analysis - Applications IIYue LiA1
5. Data Flow Analysis - Foundations IYue LiDFA-FD (I, II).pdf
6. Data Flow Analysis - Foundations IIYue LiA2 A3
7. Interprocedural AnalysisTian TanInter.pdfA4
8. Pointer AnalysisTian TanPTA.pdf
9. Pointer Analysis - Foundations ITian TanPTA-FD (I, II).pdf
10. Pointer Analysis - Foundations IITian TanA5
11. Pointer Analysis - Context Sensitivity ITian TanPTA-CS (I, II).pdf
12. Pointer Analysis - Context Sensitivity IITian TanA6 A7
13. Static Analysis for SecurityTian TanSecurity.pdfA8
14. Datalog-Based Program AnalysisTian TanDatalog.pdf
15. CFL-Reachability and IFDSYue LiIFDS.pdf
16. Soundness and SoundinessYue LiSoundiness.pdf

Lecture slides (PPT), and the solutions and more complete test cases of all programming assignments are available to teachers by request (sending emails to tiantan@nju.edu.cn with subject “Request of SPA teaching package”).

Reference Materials

  • Compilers: Principles, Techniques, and Tools (2nd), by Alfred V. Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman.
  • Static Program Analysis, by Anders Møller and Michael I. Schwartzbach.
  • 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, papers, and tools, which provide us great materials to build this course.