CS7938: Program Analysis (Fall 2005)

General Information

location: LCR (MEB 3147)
time: Thursdays 3:40-4:40
instructor: John Regehr, regehr@cs.utah.edu
John's office hours: after class or by appointment
prerequisites: No formal prereqs but students who have taken a compilers course will have an easier time.
class mailing list: cs7938@cs.utah.edu -- everyone enrolled in the class should subscribe to this list
add/drop policy: the University is strict on this, see here for details and also keep the academic calendar in mind
incomplete policy: incompletes are a pain for everyone and I won't give you one unless you have a documented legal or medical emergency

Program analysis is about figuring out what programs do. This course is primarily about static analysis, which means analyzing a program without running it.
This is a seminar that meets once a week. Everyone is expected to have read the assigned paper(s) before class.
Grades will be assigned based on contribution to the discussion. Obviously, to contribute you will need to attend class and also to have read the assigned papers. Students who contribute substantially to the discussion will get As.
There is no textbook for this course.
Students should sign up for 1 credit hour. The 2 and 3 hour options are for students who are doing class projects, and you should talk to me before signing up for these.

This schedule is tentative, it will change.

Date	Topic	Reading	Presenter
8/25	intro and organization (slides in PDF and PPT)	none	John
9/1	static analysis overview	Lecture Notes on Static Analysis, pages 1-34	John
9/8	posets and lattices	Principles of Program Analysis, appendix A (get photocopies from John)	Anupam
9/15	abstract interpretation basics	Abstract Interpretation, pages 1-30	Seungkeol
9/22	abstract interpretation in CIL	cXprop paper	Nathan
9/29	static single assignment	Efficiently computing static single assignment form	Venkat
10/6	Fall Break
10/13	conditional constant propagation	Constant propagation with conditional branches	Dan
10/21	types 1	Type systems, pages 1-23	Jianjun
10/27	types 2	Type systems, pages 23-38	Kevin
11/3	pointer analysis	Unification-based pointer analysis with directional assignments	Will
11/10	context sensitive pointer analysis	Cloning-Based Context-Sensitive Pointer Alias Analysis Using Binary Decision Diagrams	Yu
11/17	state machines	Checking System Rules Using System-Specific, Programmer-Written Compiler Extensions	Eun Yong
12/1	worst-case execution time	An Integrated Path and Timing Analysis Method based on Cycle-Level Symbolic Execution	Reet
12/8	combining analysis and testing	DART: Directed Automated Random Testing	Xiaofang

This page is maintained by John Regehr, mail me if you find a mistake or if any content is unclear.