Program Analysis (Winter Semester 2020/21)

Quick Facts

Lecturer Prof. Dr. Michael Pradel
Teaching assistants Aryaz Eghbali, Luca Di Grazia, Daniel Lehmann, Jibesh Patra, Moiz Rauf
Course type Lecture + Exercises
Language English
Ilias Ilias course with forum and quizzes
Place Virtual

Content

This course introduces the principles and practice of automatically analyzing large software systems. The course provides an overview of program analysis and then covers three topics in more detail: Static analysis, which analyzes the source code of a program, dynamic analysis, which reasons about the runtime behavior of a program, and test generation, which creates inputs to run programs. In addition to lectures, students will deepen their understanding through a practical course project (implement a program analysis based on an existing framework) and homework assignments. Besides academic achievements, the course will help students to improve their programming skills by learning about common sources of mistakes and about techniques to find them.

Schedule

This is a preliminary schedule and may be subject to change. "L" stands for lecture, "P" stands for project, and "E" stands for exercise. Lectures will be distributed via YouTube and have a recommended time window to watch them (but you can watch them any time). Events with a precise date happen on that date. Events printed in italics happen synchronously via Webex and will not be recorded, i.e., you should plan to attend them at the given time. Events printed in bold are deadlines (strict).

Date Topic Material
Nov 2 to Nov 6, 2020 L: Introduction Part 1 (Motivation): Lecture, Slides
Part 2 (Organization): Lecture, Slides
Part 3 (Basics): Lecture, Slides
Nov 9 to Nov 13, 2020 L: Operational semantics Part 1 (Preliminaries): Lecture, Slides
Part 2 (Syntax of SIMP): Lecture, Slides
Part 3 (Abstract machine): Lecture, Slides
Part 4 (Small-step semantics): Lecture, Slides
Part 5 (Big-step semantics): Lecture, Slides
Fernandez' book
Pitts' lecture notes
Nov 13, 2020 E: Exercise 1 (operational semantics) published Exercise 1
Nov 16 to Nov 27, 2020 L: Data flow analysis Part 1 (Available expressions): Lecture, Slides
Part 2 (Basic principles): Lecture, Slides
Part 3 (More examples): Lecture, Slides
Part 4 (Solving): Lecture, Slides
Part 5 (Inter-procedural): Lecture, Slides
Part 6 (Sensitivities): Lecture, Slides
Chapter 2 of Principles of Program Analysis
Nov 20, 2020 E: Exercise 1 due
Nov 23, 2020, 11:30-13:00 E: Discussion of exercise 1
Nov 27, 2020 P: Project description published
Nov 30 to Dec 4, 2020 L: Call graph analysis
Dec 7 to Dec 11, 2020 L: Random test generation and fuzzing
Dec 14, 2020, 11:30-13:00 P: Progress meeting 1
Dec 14 to Dec 22, 2020 L: Symbolic and concolic execution
Dec 22, 2020 E: Exercise 2 (symbolic and concolic execution) published
Jan 11 to Jan 15, 2021 L: Information flow analysis
Jan 11, 2021, 11:30-13:00 P: Progress meeting 2
Jan 15, 2021 E: Exercise 2 due
Jan 18, 2021, 11:30-13:00 E: Discussion of exercise 2
Jan 18 to Jan 22, 2021 L: Slicing
Jan 22, 2021 E: Exercise 3 (Information flow and slicing) published
Jan 25 to Jan 29, 2021 L: Path profiling
Jan 29, 2021 E: Exercise 3 due
Feb 1, 2021, 11:30-13:00 E: Discussion of exercise 3
Jan 25, 2021, 11:30-13:00 P: Progress meeting 3
Feb 1 to Feb 12, 2021 L: Analysis of concurrent programs
Feb 12, 2021 P: Project due
Feb 15 to Feb 19, 2021 Presentation of course projects

Course Project

The course project is about implementing a static taint analysis for JavaScript based on the general data flow analysis framework. More details will be published during the semester.