Characteristics of an Excellent Project
Here is what I'd love to see in a course project.
- Problem selection: Pick an appropriately-sized problem.
Implementing it is going to be harder than you
thought. I prioritize having something well-defined and moderately
useful over solving all of the world's problems.
Given the topic of this course, your problem should also be
related to analyzing either program code or execution traces.
(Talk to me if you'd like to study something else.)
- Implementation: Whatever you choose to investigate,
I'd like to see some code supporting your investigation.
I welcome the use of any experimental framework. The code does
not need to be production-quality, but I would like to see
something working.
- Experimental results: Your implementation should at least work
on micro-benchmarks (i.e. tiny hand-crafted pieces of code). It's
more impressive to come up with an implementation that works on at
least one real-world program, but it's quite hard to do so.
- Presentation (written and oral): Both the oral presentation
and write-up greatly influence your grade, since I'll be reading
them to figure out what you did. Make sure that they are as clear
as possible.
Please refer to Thiago's course project for a model project.
Project Ideas
Here are a couple of project ideas, in no particular order. You
should come see me to discuss your project idea. You are, of course,
free to choose a project that is not on this list; students often do
well choosing something that's related to their research.
- Extend the Java type system. We've seen non-null types as
part of Spec#. The JastAdd project implements
non-null types as a Java extension. In this project, your job is to explore
an extension to the Java type system that enables developers to specify
some program property and to verify it. Past examples of type system extensions
include non-null types and stationary fields; suggest a new type system
extension and implement it.
Here are two specific examples: 1) a type system that
identifies "tuple-like" classes, with only primitive-type fields;
2) a type system that identifies numeric values guaranteed to not
overflow.
- Making sound static analysis results available to Eclipse. Evaluate
the static analysis results currently available to Eclipse plugins and
see how they are sound or unsound. Eclipse plugins need analysis results
quickly, but sound pointer analyses need the whole program. One way to
get around this problem is to create summaries of the whole program
and to update the summaries when any file changes.
- Dynamic analysis. Consider two ways of implementing a
dynamic analysis: 1) use dynamic binary instrumentation (like PIN); or
2) statically instrument the code (i.e. with AspectJ) to collect
information about program executions. Some possible properties: "this
loop may execute at most N iterations", or "in configuration X, the
program never calls method Y". Test case generation or modification,
based on dynamic analysis results, is another possibility.
- Compare your intuition with profiling information. A famous
saying: "Premature Optimization is the Root of All Evil". (attributed to
Donald Knuth). See Rob O'Callahan for an alternate take
on the saying. The key point here, I think, is that people have terrible
intuition about where the bottlenecks are going to be. This experimental
project would compare intuition about performance with profiling results.