CS638 : Program Analysis 2006-2007

Welcome to the course homepage. Your instructor is Uday Khedker.

Here's the wish list for this offering.

Announcements

You can consider any topic related to program analysis which goes beyond what is covered in the class. Some examples are: Functional approach to interprocedural data flow analysis, CFL rechability in interprocedural data flow analysis, Graphs reachability based interprocedural data flow analysis etc.
I do not have a list of papers for faint variables analysis and possibly undefined analysis. You will have to search the papers. There is one aspect which I can suggest along which these frameworks can be studied: Local analysis for processing entire basic blocks rather processing each statement individually.
For points-to analysis, you could summarise various approaches to them.
Here is a set of papers which deal with heap analysis for Java: Purity analysis for java, and Free-Me analysis.
A set of papers on type inferencing for flow sensitive types: Flow sensititve types for security, and A couple of papers in Gradual Typing.

(12 Mar 2007). Slides on introduction to interprocedural data flow analysis.
(12 Feb 2007). Latest slides on theory and 4 pages in 1 page version.
(6 Feb 2007). The updated slides. I have added quite a few slides related to the discussions we had in the class yesterday. Note that there was an error in the definition of boundedness (the values are merged upto k-1 rather than upto k). The new slides contain the corrected definition.
(1 Feb 2007). Here are the slides which we used in today's lecture. I will put up newer version when I get time to update them. The slides contain some preliminary version of the slides for some additional material too.
(1 Feb 2007). Here's an interesting tutorial on lattice theory for beginners.
(16 Jan 2007). I have updated the slides with faint variables analysis and quite a few details of points-to analysis.
(15 Jan 2007). I have separated slides in three parts and have updated them. Motivation, Overview of Optimizations, Introduction to Data Flow Analysis.
(11 Jan 2007). Here is tentative schedule of lectures.
(11 Jan 2007). I have added a few slides and this is the latest version. I intend to reorganise them some time by dividing them in smaller parts.
(9 Jan 2007). Here are complete details of the assessment scheme for this course.

The paper assignment is to be done in groups of two and is the same for each group. It requires you to create examples to illustrate the application of heap reference analysis, points-to analysis, faint variables analysis, and static program slicing at the intraprocedural level in a single C program. The program should be simple and should be small (say 20 lines or less). You can assume existence of functions which you may call in the code. The deadline for this is first week of February.
The term paper involves reading research papers, preparing a report, and making a presentation. The essential requirement is some value addition in terms of examples illustrating key ideas, a precise summary, or an assessment of the idea etc. This also has to be done in groups of two. You could either select some recent research papers or choose to create a few reasonable C examples illustrating the issues at intra and interprocedural data flow analysis of any one of the following:

Points-to analysis
Static program slicing
Faints variables analysis and possibly undefined variables analysis.
You should finalise the topic by the end of January. The submission deadline is first week of April.

(8 Jan 2007). The slides used in previous two lectures are available. Here is a 4-in-1 page version. Please note that these slides may change as the course progresses. I welcome your suggestions for improvements of the slides.