and StatiC AnaLysis Group
Static Program Analysis
Static Program Analysis
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, 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, pointer analysis 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.
People
Instructors: Yue Li (李樾) and Tian Tan (谭添)TAs: Shengyuan Yang (杨声远) and Qinlin Chen (陈钦霖)
Lectures (Fall 2021)
| Date | Lecture | Instructor | Slides [PDF] |
|---|---|---|---|
| Sep 2 (Thur) | 1. Course Introduction | Yue Li | Intro.pdf |
| Sep 9 (Thur) | 2. Intermediate Representation | Yue Li | IR.pdf |
| Sep 16 (Thur) | 3. Data Flow Analysis - Applications I | Yue Li | DFA-AP (I, II).pdf |
| Sep 23 (Thur) | 4. Data Flow Analysis - Applications II | Yue Li | See above ٩(๑`^´๑)۶ |
| Sep 30 (Thur) | 5. Data Flow Analysis - Foundations I | Yue Li | DFA-FD (I, II).pdf |
| Oct 9 (Sat) | 6. Data Flow Analysis - Foundations II | Yue Li | See above ٩(๑`^´๑)۶ |
| Oct 14 (Thur) | 7. Interprocedural Analysis | Tian Tan | Inter.pdf |
| Oct 21 (Thur) | 8. Pointer Analysis | Tian Tan | PTA.pdf |
| Oct 28 (Thur) | 9. Pointer Analysis - Foundations I | Tian Tan | PTA-FD (I, II).pdf |
| Nov 4 (Thur) | 10. Pointer Analysis - Foundations II | Tian Tan | See above ٩(๑`^´๑)۶ |
| Nov 11 (Thur) | 11. Pointer Analysis - Context Sensitivity I | Tian Tan | PTA-CS (I, II).pdf |
| Nov 18 (Thur) | 12. Pointer Analysis - Context Sensitivity II | Tian Tan | See above ٩(๑`^´๑)۶ |
| Nov 25 (Thur) | 13. Static Analysis for Security | Tian Tan | Security.pdf |
| Dec 2 (Thur) | 14. Datalog-Based Program Analysis | Tian Tan | Datalog.pdf |
| Dec 9 (Thur) | 15. CFL-Reachability and IFDS | Tian Tan | IFDS.pdf |
| Dec 16 (Thur) | 16. Soundness and Soundiness | Tian Tan | Soundiness.pdf |
Assignments
Overview of Programming AssignmentsTai-e Manual for Assignments
Assignment 1: Live Variable Analysis and Iterative Solver (Due: 23:00, Friday, October 8)
Assignment 2: Constant Propagation and Worklist Solver (Due: 23:00, Sunday, October 17)
Assignment 3: Dead Code Detection (Due: 23:00, Sunday, October 24)
Assignment 4: CHA and Interprocedural Constant Propagation (Due: 23:00, Thursday, November 4)
Assignment 5: Context-Insensitive Pointer Analysis (Due: 23:00, Thursday, November 18)
Assignment 6: Context-Sensitive Pointer Analysis (Due: 23:00, Thursday, December 2)
Assignment 7: Alias-Aware Interprocedural Constant Propagation (Due: 23:00, Tuesday, December 14)
Assignment 8: Taint Analysis (Due: 23:00, Sunday, December 26)
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