Static Program Analysis
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.
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.
|1. Course Introduction||Yue Li||Intro.pdf|
|2. Intermediate Representation||Yue Li||IR.pdf|
|3. Data Flow Analysis - Applications I||Yue Li||DFA-AP (I, II).pdf|
|4. Data Flow Analysis - Applications II||Yue Li||A1|
|5. Data Flow Analysis - Foundations I||Yue Li||DFA-FD (I, II).pdf|
|6. Data Flow Analysis - Foundations II||Yue Li||A2 A3|
|7. Interprocedural Analysis||Tian Tan||Inter.pdf||A4|
|8. Pointer Analysis||Tian Tan||PTA.pdf|
|9. Pointer Analysis - Foundations I||Tian Tan||PTA-FD (I, II).pdf|
|10. Pointer Analysis - Foundations II||Tian Tan||A5|
|11. Pointer Analysis - Context Sensitivity I||Tian Tan||PTA-CS (I, II).pdf|
|12. Pointer Analysis - Context Sensitivity II||Tian Tan||A6 A7|
|13. Static Analysis for Security||Tian Tan||Security.pdf||A8|
|14. Datalog-Based Program Analysis||Tian Tan||Datalog.pdf|
|15. CFL-Reachability and IFDS||Yue Li||IFDS.pdf|
|16. Soundness and Soundiness||Yue Li||Soundiness.pdf|
- 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.