and StatiC AnaLysis Group
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 performace of software, and it becomes increasingly impactful in industries nowadyas. 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 prerequsite despite that understanding it would be preferable. The course is intended for advanced undergraduates as well as graduate students at all levels.
Lectures (Spring 2020)
| Date | Class | Instructor | Slides [PDF] |
|---|---|---|---|
| Feb 26 (Wed) | Course Introduction | Yue Li | Intro.pdf |
| Mar 4 (Wed) | Intermediate Representation | Yue Li | IR.pdf |
| Mar 11 (Wed) | Data Flow Analysis - Applications I | Yue Li | DFA-AP (I,II).pdf |
| Mar 18 (Wed) | Data Flow Analysis - Applications II | Yue Li | See above ฅ’ω’ฅ |
| Mar 25 (Wed) | Data Flow Analysis - Foundations I | Yue Li | DFA-FD (I,II).pdf |
| Apr 1 (Wed) | Data Flow Analysis - Foundations II | Yue Li | See above ฅ’ω’ฅ |
| Apr 15 (Wed) | Interprocedural Analysis | Tian Tan | Inter.pdf |
| Apr 22 (Wed) | Pointer Analysis | Tian Tan | PTA.pdf |
| Apr 29 (Wed) | Pointer Analysis - Foundations I | Tian Tan | PTA-FD (I,II).pdf |
| May 6 (Wed) | Pointer Analysis - Foundations II | Tian Tan | See above ฅ’ω’ฅ |
| Apr 13 (Wed) | Pointer Analysis - Context Sensitivity I | Tian Tan | PTA-CS (I,II).pdf |
| May 20 (Wed) | Pointer Analysis - Context Sensitivity II | Tian Tan | See above ฅ’ω’ฅ |
| May 27 (Wed) | Static Analysis for Security | Tian Tan | Security.pdf |
| Jun 3 (Wed) | Datalog-Based Program Analysis | Tian Tan | Datalog.pdf |
| Jun 10 (Wed) | CFL-Reachability and IFDS | Yue Li | IFDS.pdf |
| Jun 12 (Fri) | Soundness and Soundiness | Yue Li | Soundiness.pdf |
Assignments
- Constant Propagation Analysis (Assignment-1-description.pdf)
- Dead Code Detection Analysis (Assignment-2-description.pdf)
- Class Hierarchy Analysis (Assignment-3-description.pdf)
- Pointer Analysis (Assignment-4-description.pdf)
- Context-Sensitive Pointer Analysis (Assignment-5-description.pdf)
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