02242: Program Analysis (Autumn 2011)

Dates:

The course spans the period 29^th August 2011 to 28^th November 2011.

The lectures take place Mondays from 13.00-17.00 in auditorium 45 in building 303A.

The exercise sessions and project work take place in databar 16 in building 308.

Teachers:

Hanne Riis Nielson

Michal Terepeta

Course material:

NNH Flemming Nielson, Hanne Riis Nielson and Chris Hankin: Principles of program analysis, Springer Verlag, 2005 (corrected 2^nd printing, ISBN 3-540-65410-0). The book is available from the bookstore in building 101.

Preliminary schedule:

29-08-2011	Introduction	NNH Chap 1	Project presentation
05-09-2011	Reaching Definitions Analysis	NNH Sec 2.1	Exercise 1: Program slicing
12-09-2011	Forward and Backwards Analyses	NNH Sec 2.1	Exercise 2: Unreachable code
19-09-2011	Monotone Frameworks	NNH Sec 2.3, App A	Exercise 3: Buffer overflow
26-09-2011	Equation Solving	NNH Sec 2.4, App A	Exercise 4: Algorithms and data structures
03-10-2011	Non-Distributive Frameworks	NNH Sec 2.3, App A	Exercise 5: Buffer overflow Deadline for preliminary report
10-10-2011	Discussion of reports		Discussions continued / Implementation phase
17-10-2011	Autumn vacation	-	-
24-10-2011	Advanced Algorithms	NNH Chap 6, App C	Implementation phase
31-10-2011	Interprocedural analysis	NNH Sec 2.5	Implementation phase
07-11-2011	Push Down systems		Implementation phase
14-11-2011	Alternative approaches		Experiment phase
21-11-2011	Using logic in program analysis	NNH Chap 1	Experiment phase
28-11-2011	Deadline for final report		-
12, 13, 15 December 2011	Oral exam

Deadlines:

Preliminary report: deadline: 3^rd October 2011.

Final project report: deadline 28^th November 2011.

From the coursebase 2011/2012:

General course objectives:

The students will be able to understand and apply basic program analysis formalisms and to construct and apply the analysis tools and techniques facilitated by these formalisms.

Learning objectives

A student who has met the objectives of the course will be able to:

· explain the basic concepts introduced;

· explain concrete analyses and apply them to simple programs;

· explain the role of analysis frameworks and their instances;

· formulate new analyses as variations of existing ones and categorize them in the appropriate analysis frameworks;

· explain semantic as well as algorithmic aspects related to the analyses;

· design and construct a generic software tool supporting analyses based on analysis frameworks;

· design and motivate a series of experiments using this software tool and interpret the results obtained;

· achieve the above goals in a group effort while at the same time maintaining individual accountability; and

· communicate his/her results in a clear and precise manner using a standard form for technical reports.

Content:

The course covers three main topics: (1) Data flow analysis: This part covers the classical intra-procedural analyses and their formulation as monotone frameworks. (2) Algorithms: This part covers work-list algorithms exploiting the graphical structures of the constraint systems associated with the analysis problems. (3) Logic: This part introduces an approach to specifying and implementing analyses based on logical formalisms.

The students are required to solve theoretical exercises as well as programming exercises.