CSE503 - Program Analysis
This course will focus on static and dynamic program analysis techniques that can be used to perform tasks such as program verification, profiling, optimization, repair, and comprehension. Students will learn the concepts behind the techniques, and will apply their learning to develop analyses using the state-of-art tools.
Ensuring program correctness can be very challenging. Programmers depend on testing to build some confidence in the expected behavior of programs. Although testing is essential, the complexity as well as the criticality of modern software demands more rigorous techniques, in addition to testing, to ensure software correctness. The properties that programs need to satisfy vary from safety properties to security properties and in terms of expressiveness from simple predicates that check the program states at specific execution points to regular expressions and context-free grammars that check the legality of traversed program paths. In this course, we will focus on program verification and the students will learn about static analysis techniques, i.e., the techniques that can be applied to programs without running the programs as well as about dynamic analysis (or runtime monitoring) techniques that analyze programs during runtime. The students will learn about the strengths and weaknesses of both techniques and may possibly explore ways to combine them to increase their effectiveness. In the static analysis, we will primarily focus on dataflow analysis, and learn about some standard analyses that are used in program verification and optimization. However, the course will also introduce students to some advanced static analysis topics such as symbolic execution, and will cover some topics related to security analysis. We will primarily use Java as programming language and "Soot" as a static analysis tool. In the dynamic analysis part, the students will learn to specify properties of interest mainly using regular expressions and finite state automata, and use "JavaMOP" and aspects to build runtime monitors to check those properties. In the process, they will learn to develop “aspects” to instrument and monitor programs.
Please refer to the policy: https://www.iiitd.ac.in/academics/resources/academic-dishonesty
Postcondition 1 - Weeks 1-6
Classic problems in static program analysis, monotone data flow framework including lattice concepts, control flow graph, pointer analysis, analysis with Soot.
Exams, quizzes, programming assignments.
Postcondition 2 - Weeks 7-9
Runtime monitoring concepts, finite state properties, tools, and architectures, Aspects, security automata.
Exams, quizzes, a programming assignment.
Postcondition 3 - Weeks 10-13
Introduction to advanced topics including interprocedural analysis and symbolic execution.
Assignment, exams, quizzes.
For assessing the performance of students, the course will have programming assignments, in-class quizzes, a mid-sem exam and an end-sem exam. Weights of each of these elements could be:
- End-sem exam: 25%
- Mid-term Exam: 25%
- Quizzes: 10%
- Programming Assignments + (Optional) Project: 40%
Knowledge of Java programming and data structures (Equivalents of AP and DSA) is required. Some knowledge of finite state automata would help, but not required. The required FSA related concepts will be covered in the class.
Rahul Purandare: By appointment.
There is no textbook for this course. Reference material will be provided from time to time in the class. In addition, following reference books would be useful.
- "Principles of Program Analysis" by Nielson, Nielson and Hankin.
- "Data Flow Analysis: Theory and Practice" by Khedker, Sanyal and Karkare.
- "Compilers: Principles, Techniques, and Tools" by Aho, Lam, Sethi and Ullman