Advanced Program Analysis

Course guarantor:

Jan Vitek

Lecturer:

Jan Vitek

Tutor:

Jan Vitek

Supervisor:

Department of Theoretical Computer Science

Synopsis:

In the past decade, there have been great advances in the development of

automated tools that help programmers find various kinds of quality problems in their

code. This includes tools for finding bugs and security vulnerabilities, test generation,

fault detection and localization, etc. Many of these tools rely on program analysis to

compute an approximation of a program's behavior. In this special topics course, we

will study key publications in which static and dynamic program analysis algorithms

are used to detect bugs and security vulnerabilities in programs, and how these

algorithms are used in other tools that support programmers. Both theoretical

properties and practical effectiveness of program analysis algorithms will be studied.

Requirements:

Syllabus of lectures:

1) static and dynamic techniques for finding errors, including type-based and

dataflow-based techniques

2) static and dynamic techniques for finding security vulnerabilities (e.g., taint

analysis)

3) automatic test generation (e.g., using dynamic symbolic execution)

4) analysis challenges posed by dynamic and reflective programming language

features

5) specialized string analysis techniques for tracking the flow of string values in

applications

6) suitability of program analysis algorithms for different programming languages

7) the use of open-source frameworks for program analysis

The course will be organized as follows. First, the instructor will present a few

lectures to review basic program analysis concepts and terminology (call graphs,

points-to graphs, SSA form, etc.) and key applications of program analysis

technology. Then, students and the instructor will take turns presenting publications.

Each paper presentation will be followed by a discussion. In addition to the

presentations, each student will do a modest-sized course project, which could

consist of, e.g., a literature study, the implementation/evaluation of a simple program

analysis, or the evaluation of tools that implement a program analysis. Students will

be expected to give a few short presentations about their project so that the other

course participants can provide constructive feedback. Instead of a final exam,

students will be required to write a short report about their project.

Syllabus of tutorials:

Study Objective:

To understand the motivation and algorithmic solutions to the more complex

problems from static and dynamic analysis and to familiarize with influential papers

from the area.

Study materials:

Flemming Nielson, Hanne Riis Nielson, Chris Hankin: Principles of Program Analysis,

Springer.

Note:

Further information:

https://courses.fit.cvut.cz/PI-APA/

Time-table for winter semester 2024/2025:

Time-table is not available yet

Time-table for summer semester 2024/2025:

Time-table is not available yet

The course is a part of the following study plans:

• Informatics (doctoral) (compulsory elective course)
• Informatics (compulsory elective course)