02242:
Program Analysis (Autumn 2009)
About the course:
Time: Mondays, 13.00-17.00
Lectures: Building 303, Auditorium 45
Teachers:
Hanne Riis Nielson
Piotr Filipuik
Course material:
[NNH]
Flemming Nielson, Hanne Riis Nielson and Chris Hankin: Principles of program
analysis, Springer Verlag, 2005 (corrected 2nd printing, ISBN 3-540-65410-0).
The book is available from the bookstore in building 101.
Preliminary schedule:
|
31-08-2009 |
Introduction |
NNH Chap. 1 pp. 1-13, 25-26 |
Project presentation |
|
07-09-2009 |
Forward Analyses |
NNH Chap. 2 pp. 35-46, 52-54 |
Exercise on RD |
|
14-09-2009 |
Backward Analyses |
NNH Chap. 2 pp. 46-52, App. A pp. 393-397 |
Exercise on LV |
|
21-09-2009 |
Monotone Frameworks |
NNH Chap. 2 pp. 65-74, App. A pp. 397-401 |
Exercise on CP |
|
28-09-2009 |
Equation Solving |
NNH Chap. 2 pp. 74-82, App. A pp. 402-404 |
Deadline for preliminary report |
|
05-10-2009 |
Discussion of preliminary report |
|
Discussion of preliminary report |
|
19-10-2009 |
Interprocedural analysis |
NNH Chap. 2 pp. 82-85, 88-101 |
Project work |
|
26-10-2009 |
Algorithms |
NNH Chap. 6 pp. 367-384 |
Project work |
|
02-11-2009 |
Alternative approaches |
NNH Chap. 1 pp. 8-13, 17-25 |
Project work |
|
09-11-2009 |
Analysis of cryptographic protocols |
|
Deadline for benchmark programs. Project
work |
|
16-11-2009 |
Succinct solver and its uses |
|
Project work |
|
23-11-2009 |
No lectures |
Use the time for project work |
Project work |
|
30-11-2009 |
End of course |
|
Deadline for final project report |
|
10,
11, 15 December 2009 |
Oral exam |
|
|
Deadlines:
Preliminary
report: deadline at 12 noon on 29th September 2009; by email to the
teachers.
Final project report:
deadline 30th
November 2009. A signed copy should be put in the mail box at
the west entrance to building 322; the report and the implementation should be
send by email to the teachers.
From the coursebase 2009/2010:
|
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 categorise them in the appropriate
analysis frameworks; explain semantic as
well as algoritmic 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 precies 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) Flow logic: This part introduces the flow logic
approach to specifying analyses and the associated techniques for obtaining
implementations in logical form. |