Program Analysis
Instructor: Venkatesh Vinayakarao
Term: Mar - Apr 2019



Welcome to the Program Analysis course! Software development has become an essential part of our daily life. Several systems around us including transportation, communication, healthcare, education and entertainment are largely enabled or supported by software. Yet, software development remains to be a human task that is prone to errors. Hence, our ability to analyze programs is very important.

In this course, we introduce several popular approaches to program analysis. We will discuss both static and dynamic analysis. We start with the well-known program representations such as Abstract Syntax Trees and Control Flow Graph. We will discuss other representations such as Dependence Graphs, and Intermediate Representations (SSA and Three Address Format). We will cover the classic Data Flow Analysis framework, Points-To Analysis (Anderson and Steensgard's Algorithm), Flow and Context Sensitivity as part of static analysis. As part of dynamic analysis, we would briefly discuss Monitor Oriented Programming. A series of guest lectures on advanced data flow analysis, program slicing and runtime verification is also planned.

The course will be a mix of both theory and practice. There will be coding assignments and hands-on tutorials on few analysis frameworks. While advanced programming skills are not required, students must be familiar with core Java to complete the assignments. There are no other pre-requisites to this course.

Key Learning Objectives

At the end of this course, you should be able to:
  • Understand and implement static and dynamic analysis
  • Perform data flow analysis (using Eclipse JDT and Soot).
  • Weave monitors in Java code for runtime verification (using AspectJ and JavaMOP).

Lecture Resources

Lecture #TopicReadingsSlides/Tutorials
1Introduction to Program AnalysisSection 4.2 of Dragon Book for Context-Free Grammars.Slides
2Fundamental Program RepresentationsSection 8.4.1 and 8.4.3 for Basic Blocks and Flow Graphs.Slides
Eclipse JDT Tutorial
Soot Unit Graphs Tutorial
3 More Program Representations Section 9.6.1 of Dragon Book for Dominators and Dominator Tree.
Soot Survivors Guide
Slides
Z3 Tutorial
4More Program RepresentationsCall Trees, Stacks and Heaps. JProfiler DemoSlides
5Introduction to Static AnalysisChapters 1 and 2 of AMMS book for Static Program Analysis. Slides
6Data Flow AnalysisChapter 4 of AMMS book for Lattices and Monotone Frameworks.Slides
7Data Flow AnalysisChapters 1 and 2 of PPA book.Slides
8Data Flow Analysis with Soot*Slides
9Pointer AnalysisChapter 9 of AMMS book.Slides
10Non-Bit Vector Analyses*Chapter 4.2.3 of DFA book.Slides
11Dynamic and Hybrid AnalysisSlides
AspectJ Tutorial
12Program Slicing* Slides
13Program Slicing* Slides
14Dynamic and Hybrid AnalysisMonitoring Oriented Programming - A Project Overview, Chen et al., 2009.
Symbolic Execution for Software Testing: Three Decades Later, Cadar and Sen, 2013.
Slides
JavaMOP Tutorial
KLEE Tutorial
Final Exam
*Guest Lecture


Evaluation
InstrumentMax Marks
Final Exam50%
Assignment 110%
Assignments 2, 3 (15% each)30%
Quiz (5 * 2%)10%

Pre-requisites
Students must bring reasonable familiarity to programming, preferably in Java.

Resources

Text
  • [AMMS] Static Program Analysis, Anders Møller and Michael I. Schwartzbach
Reference
  • [PPA] Principles of Program Analysis, Flemming Nielson, Hanne R. Nielson and Chris Hankin
  • [Dragon] Principles, Techniques, & Tools, Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman
  • [DFA] Data Flow Analysis: Theory and Practice, Uday P. Khedkar, Amitabha Sanyal and Bageshri Karkare


If you are not having fun, you are not the best student you can be!