CSE 503: Program Analysis

 

Project

The centerpiece of the course is a semester-long project, done in groups of 2–4 students. The project should make a research contribution in the area of tool support for programming tasks. As a research contribution, it should answer a question whose answer no one previously knew.

A non-exhaustive list of types of acceptable projects are:

A list of specific potential projects will be distributed at the second class meeting. (It is intentionally not being distributed until after you have completed Assignment 1.) You may select (or modify) a project from among the list of suggested ones, from your answers to Assignment 1, from other students’ answers to Assignment 1, or from other sources. The lecturer will help you choose, refine, and scope a project.

For instance, you might start from a programming problem that has vexed you and devise a solution (or demonstrate that it is a broader problem than previously recognized). You might take a paper of particular interest to you and attack one of the problems listed in its future work section. You might take a promising paper that lacks experimental evaluation, or whose methodology is flawed, and perform a proper experimental evaluation.

You should also consider building on your strengths and finding ways to leverage other work that you are doing. For instance, if you do work in AI, you might consider how machine learning could be applied to problems of program comprehension or to filtering output from program analysis tools. You also might consider using a project that you are working on, or that you worked on in the past, as a test case for a tool. Synergies with your other work are welcomed!

Your final project report should be written in the style of a conference paper, and you will present it in a CSE 503 “conference” at the end of the semester in the final exam slot (Thursday, December 15 at 10:30am). You are not required to submit your work to a conference or workshop, but you might choose to do so — this is the standard of work expected, and which the instructor will help you achieve. Please use the ACM proceedings style (http://www.acm.org/publications/proceedings-template, ACM standard conference style).

You need not close the book on the area of research you choose, but you should do a good job of discovering and clearly communicating new knowledge in that area. Do not feel overwhelmed by the final project or final report. The instructor will meet with you repeatedly for discussions, feedback, and assistance on all aspects of your project. For tips about writing a technical paper, you should read (among other resources) http://homes.cs.washington.edu/~mernst/advice/write-technical-paper.html.

Timetable

For exact dates, see the class calendar.

Week 2: Proposal

Select a group, select a project, and write a short (1–3 pages) project proposal that includes its thesis and technical approach.

Be sure to motivate your project. Your paper should start with the problem. You also must give a use case — essentially, a story about how the tool is used. For example, a software developer wants to perform a particular, realistic task, but cannot. Be specific about the problem and about why current techniques do not address it. Your tool solves that problem. Indicate exactly what inputs the developer must supply, exactly what the developer gets as output, and how that is useful in practice. Include an architectural diagram of how the pieces of your system fit together.

Include evaluation criteria. The philosopher of science Karl Popper states that a theory is scientific only if it is falsifiable — if some experiment exists that would disprove it. You need to clearly state an experimentally refutable thesis or hypothesis. You should also state your evaluation metric, which should be, at least in part, quantifiable. Another way to think of this is: how will you convince a skeptical reader that you succeeded? They aren’t going to just take your word that your project was a success.

Clearly state the scientific question or contribution. For example, how is your project an (incremental) advance over previous work? It’s good (and in some cases sufficient) that it enables developers to do something they have never been able to do before. But you can also extend a technique to a new domain, or expand a problem statement. And ideally, your results will be transferable to other domains: they will change the way that others think or act in the future, or provide guidance to programmers or to tool developers or both. Oftentimes, much of your project is not novel. That’s OK — engineering is necessary in order to do experiments or to build on previous work — so long as you can point out the part that is novel.

Week 2: Approval of proposal

Meet with the instructor for feedback on and approval of your project proposal.

Week 3: Revised proposal

Meet with the instructor for feedback on and approval of your project proposal. You should also solidify the technical approach.

Week 5: Related work and methodology complete

Submit a version of your report that includes the introduction, description of the technical approach (e.g., algorithmic details), related work, and experimental methodology (i.e., evaluation plan). These sections should address all feedback you have received so far and should be in final form: you would be happy to have this text appear in your final paper without any subsequent editing.

It is okay if this description changes as you discover flaws in your initial ideas about the methodology, subject programs, and so forth. However, it is not acceptable to simply skip this assignment by submitting something that is vague or incomplete. The purpose of this milestone is to make you think about these issues and to enunciate them in time to get feedback from your teammates, from yourself when you see what you have written, and from the instructor. Working hard on this assignment will save you a lot of time in the long run.

Your experimental methodology section should not contain vague descriptions or missing aspects of the methodology. It should specify specific subject programs, experimental protocols, specific tasks for any user evaluation, specific metrics and how they are computed, etc. The paper should contain enough detail that any reader could replicate your results, without the need for guesswork or non-trivial design decisions.

The evaluation plan should also justify your choices by explaining why your chosen metrics are the right ones, and what insights they reveal about your work. (For example, do they address the novel part of your technique, or are they end-to-end measures? Can they be directly compared to previous work, or not?) It should also indicate your criteria for success. (You should lay those out now, so that you have an objective measure when the research is complete.) This version of the paper should include all the tables or graphs (if any) that will appear in the final paper, and the structure of any textual sections of the evaluation. The tables or graphs will be empty for now, but you should know what they are.

You should have already divided the work among members of your group.

You should be able to reuse most of the text from your proposal, but you will also have to augment it. Each version of the paper should address all previous comments from the course staff.

Week 8: Code complete and initial results

Submit a version of the report that includes partial results. This draft should also include a description of the interesting parts your implementation — enough information to enable a reader to re-implement it.

If you are building a tool, you should have a prototype implementation that can run correctly end-to-end on a small example program. (For example, a compiler might be able to compile the factorial program.) Having a working implementation now will enable you to enhance it and to run experiments during the next several weeks; if you do not even yet have working code yet, you are unlikely to be able to complete a quality project in time.

As a rule of thumb, by this point you should have one row or column in each table filled in. Or, if you are doing a case study or qualitative experiment, then you should have completed a pilot study. You will find that, besides these results and the implementation description, your document did not change much in this submission. Be sure to also address previous comments and to reflect any changes in your methodology.

Week 10: Final report

Final exam week: Project presentations

You should plan to talk for 20–25 minutes, followed by 5–10 minutes for questions (though the questions may come during rather than after the talk). As with any talk, be sure to practice it before you present in class. Be sure to include plenty of examples! (Even after receiving this advice, most groups fail to include enough to make their ideas comprehensible.) For more tips, see http://homes.cs.washington.edu/~mernst/advice/giving-talk.html.