CompSci 838: Program Analysis
Spring 2006 (revised 2006/2/27)

John Tang Boyland boyland@cs.uwm.edu

925 EMS Building, 229-6986, 967-4804 (home)

A program is any formal notation used to communicate ideas precisely between people or between a person and a machine. Programs are increasingly being written and used by non-programmers to customize applications. Program analysis is the task of deriving information from programs. In this course, we will look beyond simple analyses such as lexical analysis and parsing to more ``semantic'' analysis, determining properties such as absence of type errors, cyclic dependencies or race conditions, and presence of strictness or execution independence.

Objectives

Participants will learn how to read published accounts of analysis in the literature; they will learn successful techniques for program analysis, their benefits and shortcomings; they will learn ways to understand program analyses, especially those based on accepted techniques; they will learn how to design and implement analyses that are more likely to be correct, efficient, comprehensible and extensible.

Requirements

A class in programming languages or compilers at the graduate level is required. In particular participants are expected to have practical knowledge of

If students are not sure whether they meet these requirements, they are invited to meet with the instructor or send email at any time to discuss whether they should take the course.

Required Reading

The textbook for the course is Principles of Program Analysis by Nielson, Nielson and Hankin. The latter part of the course will concern presentations of published analyses.

Project

Each student will develop his or her own project under the guidance of the instructor. The student will explore some program analysis, implement it, test it, write up a description and make a presentation. A good project could serve as the basis of a master's thesis and could even provide the starting point for research for a doctoral degree.

Possible areas for projects include

Students are encouraged to extend existing systems, such as Munson's Proteus system, Boyland's Fluid or Fiber systems, Webber's Java analysis, or use any external toolkit such as the BANE project from Berkeley, or the SUIF kit from Stanford.

Grading

The grade for the course will be computed from the following parts:

40%
Project
A mjor portion of the grade will be a course project. The project will be graded for its technical competence, clarity of exposition, and proper placement with respect to related work. There will be an opportunities to present the work of the project. There are two deadlines for the project write-ups: the earlier one is for the rough draft. The final draft is the one used for the final grade. The 40% will be divided up equally between the implementation and the writeup.
40%
Homework
There will be a written homework almost every week. It is due at the beginning of class. This homework will be based on the required reading and on lecture materials.
20%
Participation
Being of the form of a graduate seminar, it is essential that the students read the textbook and required extra papers before class and be able to contribute to the discussion. For that reason, in the latter part of the course, each student must write a paragraph summary about each article before class. Furthermore, each student will be required to comment on the presentations and draft write-ups of the other participants.
Exceptions to these rules can be made in extraordinary circumstances. Advance notice of a need for an exception should be given if possible. All graded assignments must be your own work (your own words), but you may work with other people as long as you list their names prominently on the first page of the turned in homework. Whether or not you have permission of the other, submitting someone else's work as your own is plagiarism, a serious instance of academic misconduct. Everyone is responsible for learning the material themselves.

Excellence in all areas is needed to achieve an ``A'' grade; average good performance will merit a ``B'' grade. Serious deficiencies in multiple places will lead to a ``C'' or lower grade.

Schedule

The following schedule is subject to change.


Date Topic Reading Milestone
January 23 Introduction and Partial Ordering Ch. 1.1-2  
January 25 Lattices and Fixed Points Ch. A  
January 30 Data Flow Analysis (intro) Ch. 1.3 HW #1 due
February 1 Constraint-Based Analysis (intro) Ch. 1.4  
February 6 Abstract Interpretation (intro) Ch. 1.5 HW #2 due
February 8 More on AI    
February 13 Type and Effect Systems (intro) Ch. 1.5 HW #3 due
February 15 Algorithms and Transformations Ch. 1.7-8  
February 20 Data Flow Analyses Ch. 2.1,2.3 HW #4 due
February 22 Proving Correctness of DFA Ch. 2.2  
February 27 Solving DFA Ch. 2.4 HW #5 due
March 1 Fluid CFGs    
March 6 Interprocedural Analysis (1) Ch. 2.5.0-2 HW #6 due
March 8 Interprocedural Analysis (2) Ch. 2.5.3-6  
March 13 Control-Flow Analysis Ch. 3.0-1 HW #7 due
March 15 Solving 0-CFA Ch. 3.3,3.4  
March 27 Abstract Interpretation Ch. 4.0-1 HW #8 due
March 29 Widenings Ch. 4.2  
April 3 Algorithms Ch. 6.0-2 HW #9 due
April 5 Strong Components Ch. 6.3  
April 10 Recent Analysis (1)   HW #10 due
April 12 Recent Analysis (2)    
April 17 Recent Analysis (3)    
April 19 Recent Analysis (4)    
April 24 Recent Analysis (5)   Project idea due
April 26 Recent Analysis (6)    
May 1 Recent Analysis (7)   Progress report due
May 3 Recent Analysis (8)    
May 8 Project Talks I   Project first draft due
May 10 Project Talks II    
May 15 12:30pm: Final Exam   Project due


John Tang Boyland
2006-02-27