Assignments

Program Analysis: Theory and Practice - CSCI 7135 - Fall 2025

\(\newcommand{\TirName}[1]{\text{#1}} \newcommand{\inferlab}[3]{ \let\and\qquad \begin{array}{l} \TirName{#1} \\ \displaystyle \frac{#2}{#3} \end{array} } \newcommand{\inferright}[3]{ \let\and\qquad \displaystyle \frac{#2}{#3}\TirName{#1} } \newcommand{\inferrule}[3][]{\inferlab{#1}{#2}{#3}} \newcommand{\infer}[3][]{\inferrule[#1]{#2}{#3}} \)

Final Projects

Students are expected to select and complete a substantive course project during the semester on a topic related to the class.

The main goal of the project is allow you to dive deep into an area of program analysis of interest.

Project Components and Dates

  • Project presentation (Tue Dec 9 1:30-4 p.m.)
  • Project paper (Fri Dec 12 AoE)

Project Scale

The final project is a mini-research project in program analysis, though I do not expect each project to result in novel results. I do hope some of you will get so excited by your projects that you will come see me about taking it further to, say, publication!

I do expect a consistent effort on the project in the alloted time. Notably, “one long weekend” will not suffice. I can tell. Trust me.

You may undertake the analysis part individually or in small groups (e.g., pairs), but the number of group members should depend on the size of the project. Note that the grading for a two-person project will actually require “twice as much work” rather than the standard “1.5-times as much work”. You should be able to split up the project paper (e.g., “I did section 1, Grace Hopper did section 2, and we shared section 3”), and I should be able to compare your part of the project to individual projects.

Final Deliverables and the Research Format

The final deliverables are a presentation and a paper describing your mini-research project, as well as your code or mathematical contributions that demonstrate your contribution.

The presentation and paper should be a research-style talk and manuscript. In particular, you should make sure to do the following:

  1. Define the problem that you tackle.
  2. Explain why the problem is important and interesting.
  3. Discuss why the problem is challenging by placing it in context with the related work.
  4. State your contribution (i.e., articulate your key idea or observation that addresses the problem).
  5. Demonstrate your contribution by example, in general, and through an evaluation.

There are many resources on developing research skills; here’s one that I recommend.

Starting (i.e., the Proposal)

Start your research with a draft of your final paper, consisting of at least the following three sections:

  1. Related Work. The Related Work section places the contribution of the paper in the context of the academic literature. Thus, the related work discussion should paint a picture of the scientific landscape related to your contribution. The text should not simply be summaries of some “related papers” but connect those papers with your contribution. For the proposal, make sure you identify the 1-2 papers on which your expected work most closely builds (please include the citations). Your discussion of these papers should include identification of why those most closely related papers are insufficient for the problem that you are tackling. You should aim for a few paragraphs initially.
  2. Overview. The Overview provides a concrete, example-driven description of your solution and contribution. The example should be as simple as possible but sufficient to demonstrate your algorithm or technique. It should illustrate the key challenges in tackling the problem and how your technique addresses those challenges at least on the given example. For the proposal, you should at least convey the challenges that you will tackle, though push as far as you can on this section. You should aim for half-page figure and at least a few paragraphs of text describing the figure. You should expect to iterate on this section a lot during the course of the project.
  3. Introduction. The Introduction states and motivates the problem that you are addressing in your paper. It answers (1) the problem that you are tackling, (2) why that problem is important and interesting, (3) why the problem challenging, and (4) states your technical contributions. For the proposal, you should aim for a few paragraphs for points (1)-(3), followed by a bulleted list of (4) your expected contributions.

There is no length “minimum,” but I expect a proposal with sufficient details to provide feedback will be ~2 pages in length.

Finishing (i.e., the Paper)

Your write up at the end of the semester should be in the form of a research paper, though it will likely be shorter and less complete than a submittable research paper. The project paper should follow the Research Format described above with the following sections:

  • Abstract. The Abstract states the problem, why it is important, why it is challenging, and what your contribution is (like in the Introduction but in about a sentence each).
  • Introduction.
  • Overview.
  • Technical Sections. The technical sections describe the technical details of your contribution — one per bulleted contribution from the Introduction. These sections demonstrate your contribution is general, typically through formalization and algorithm descriptions.
  • Evaluation. The Evaluation section demonstrates the effectiveness of your contribution. Depending on your project, this section might include experimental results, proofs of properties, or case studies.
  • Related Work.
  • Conclusion. The Conclusion summarizes your contributions and discusses what follows from your contribution.

You might view your project paper as if you were submitting it to, for example, PLDI, POPL, OOPSLA, ICFP, CAV, or SAS. You might want to browse the papers from PLDI 2015 or POPL 2025. Aside from giving you a number of data points for how the paper should look graphically, reading the electronic editions might trigger some ideas.

Your project paper should be concise but clearly convey what you have done. There is no length “minimum,” but I suspect papers will be about 10-15 pages in length in the PACMPL format.

Evaluation. I will evaluate the content of your mini-research project primarily through the paper (though I will want to be able to run your analyzers).

The Presentation

The Presentation should also follow the Research Format described above and parallel the Paper structure, except that it should focus on intuition and examples rather than technical details. Spend at least half your time on the problem and motivation to state your contribution, about a quarter on illustrating some aspect of your contribution, and about a quarter on demonstrating your contribution.

While preparing the talk keep in mind who your audience is. You will be presenting to colleagues who are eager to find out (1) about new exciting analyses and (2) how much fun you had. Plan to motivate the project (i.e., why is this important?) and to describe what you learned from it. Keep in mind that your colleagues have not read all the papers that you have read to do the project.

Some Ideas

Here are some starting ideas. You are not limited to these ideas; feel free to propose your own!

Classically, program analysis expects as input a complete program to produce an over-approximation of its behavior. However, modern software development practice often involve incomplete programs, such as libraries, frameworks, or components that interact with unknown or dynamic environments. How can we design program analyses that effectively handle incomplete programs while still providing useful guarantees about their behavior? For example,

  • Incremental static analysis, where the analysis is performed on-the-fly as the program is being developed or modified, rather than as a one-time batch process (e.g., Stein et al., PLDI’21).
  • Demand-driven static analysis, where the analysis is performed only on the parts of the program that are relevant to a specific query or property of interest (e.g., Stein et al., PLDI’21).
  • Static analysis of patches or updates to existing software, where the analysis must reason about the changes in isolation from the full program.
  • Static analysis of interactive applications, such as web applications or mobile apps, where the program’s behavior depends on user inputs and interactions that are not known at analysis time (e.g., Meier et al., OOPSLA’23).
  • Static analysis of distributed services, where the program interacts with other services over a network, and the behavior of those services may be unknown or dynamic.
  • Static analysis of multi-language programs, where different components of the program are written in different programming languages, and the interactions are through foreign function interfaces or serialization.
  • Static analysis of programs that use reflection or dynamic code generation, where parts of the program’s behavior are determined at runtime.
  • Static analysis of programs that rely on external configuration files or environment variables, where the program’s behavior can change based on these external inputs.