PAG's research focuses on techniques and tools for improving programmer productivity; this covers all of software engineering, from programming language design, to compiler analyses and optimizations, to dynamic analysis, to testing. If you like programming, you will enjoy this research, which is about making programming less error-prone, less tedious, and more fun. If you ever have trouble programming, you will still like the research (because you will find the results useful), and you may be inspired to come up with new projects.
The purpose of each project listed below is to perform an experiment to validate an idea, analyze some phenomenon, or otherwise advance understanding. Programming is usually necessary, but the real point is the experiments and the knowledge gained. It's quite possible to start out on a project doing development work (which can be rewarding all by itself), and later transition to making research contributions.
This page lists just a few of the potential projects the group has in mind; we can discuss others in person. In addition to the projects listed here, we are always open to new ideas! Some of these projects would make good M.Eng. or Ph.D. theses; others are the right size for a UROP; and others are starter projects to help people get up to speed on the tools and the techniques. Every project has the potential to grow into a thesis or more: in the past, starter projects have turned into published papers.
If you are interested in discussing these projects and/or doing research in the Program Analysis Group, please email jhp@csail.mit.edu to set up an appointment. Some projects below list another group member; in that case, contact them instead. (When you send the email, mention which projects interest you most. Before an interview, we'll want to see a resume, grade report, code sample, and writing sample, so it can be helpful to include those as well. Please don't just send mail saying, "I am interested in a position in your group"; that is evidence that you didn't bother to look at the group's webpages to find out what we are doing and how to best contact us.) Except in unusual circumstances, undergraduates should have received an A in 6.005 or 6.170. Other sources of information about research in the group include the PAG webpage and the publication list by topic or by date.
The best and the brightest at MIT work with PAG. A PAG MEng student has won the Charles & Jennifer Johnson Award for best MEng thesis in 5 of the past 7 years: 2002, 2003, 2006, 2007, 2008.
Students often ask about funding. UROPs for credit or pay are always available. Our policy is not to fund MEng students who have not worked in the group for at least a full semester, usually as a UROP (in other words, no full ride until you have proven yourself). Funding is contingent on good performance, so the only guarantee is your own hard work. On the other hand, no MEng student in PAG has ever been without funding, in the form of an RA, TA, or fellowship.
Contents:
We have written a dynamic dataflow analysis for
Java that determines how specific variables relate to one another.
For instance, do variables x and y ever
interact with one another? Our analysis is implemented by transforming
class files to track value comparability. The current implementation
is missing important features such as
support for native methods and a consistent approach to handling
formal parameters. We are looking for a UROP to complete the
implementation and verify its operation and scalability on significant
programs.
Our analysis is implemented in Java. A firm grasp of Java is a must. Most qualified students will have successfully completed 6.005 or 6.170, but relevant practical experience would also be very valuable.
For more information please contact Jeff Perkins (jhp@csail.mit.edu)
Our goal is to find the input that triggers the bug, if it exists. There are two challenges: 1. We must find an input that causes the specific line (42, in our example) to be executed. 2. We must find an input that causes the given variable to be null when line 42 is executed.
We plan to use two tools to overcome these challenges. 1. Randoop is a feedback-directed random test generator. It is good at exercising specific parts of your code in unexpected ways. 2. Java PathFinder is a symbolic execution engine. It is good at finding ways to slightly change input values without affecting the program's behavior too much, via a technique called concolic execution. Each of these tools must be extended in novel ways in order to achieve our goals, however.
6.005, 6.170, or equivalent is a must. The implementation language is Java.
For more information please contact Shay Artzi (artzi.mit.edu)
One problem with this approach is that it is difficult to include the JDK in the analysis. Some JDK classes are loaded before the dynamic instrumentation is available. Also, JDK classes are often used by the instrumentation itself. If those classes are also instrumented, at best, performance is sacrificed and at worst an infinite recursion results. Most instrumentation is thus limited to application code which can drastically limit its applicability.
A possible approach to resolving this problem is to instrument the JDK statically. An instrumented duplicate of each method is created. The instrumented version of the method is used by application, the uninstrumented version by the instrumentation software.
Some aspects of this approach have been tried and appear promising. The purpose of this project is to create a toolkit so that a user can easily write arbitrary instrumentation that can be applied to both the JDK and application code The toolkit would support reflection, native methods, Object methods, etc.
Our analysis is implemented in Java. A firm grasp of Java is a must. Most qualified students will have successfully completed 6.005/6.170, but relevant practical experience would also be very valuable.
For more information please contact Jeff Perkins (jhp@csail.mit.edu)
This project is, in brief, about writing a better assertion checker for Java.
Most procedures have preconditions and postconditions. Checking preconditions at run time is easy: just write an assert statement at the beginning of the routine. Checking postconditions is more troublesome: one must give a name to the return value and insert an assertion at every exit point, including return statements and exceptional exits such as those caused by throwing an exception. Furthermore, in this approach the postcondition is not documented at the beginning of the procedure. Object invariants are similarly problematic: they must be duplicated for every procedure entry and exit in a class.
Run-time checking of specifications seems deceptively easy, but has proved a difficult task. We would like to perform the research and implementation that will enable creation of a robust specification (pre- and post-condition, and object invariant) checker — both for use in our own programming, and because it will enable interesting additional research.
For more information please contact Jeff Perkins (jhp@csail.mit.edu)
The Daikon invariant
detection tool automatically generates program specifications. For
instance, given a program, it can report, "the output of procedure
getNames is always sorted", or "for every object of class
BinaryNode, this.left < this.right".
This is useful for testing, verification, documentation, program
understanding, and other tasks. Daikon is used worldwide.
We are collaborating with industrial colleagues who are using Daikon on commercial programs. They have identified both implementation and conceptual issues that, if corrected, would make the tool much more effective. We would like to brainstorm, implement, and field new algorithms and implementations that provide better scalability, that prune out extraneous output, or that identify errors as they happen.
This project offers the opportunity to bridge the gap between industry and academia and to have a real impact in practice.
For more information please contact Jeff Perkins (jhp@csail.mit.edu)
This project is for a student interested in software testing. If you value the quality and productivity that a good test suite affords, and you would like to contribute to the state of the art in mechanically generating good test suites, read on.
Writing tests is a difficult and time-consuming activity, and yet it is a crucial part of good software engineering.
The goal of our system (Randoop) is to automatically generate unit tests for arbitrary Java classes. These tests should provide reasonable coverage of the classes with minimal user support. We have an initial implementation that does a very good job with library classes (such as java.util), but is not as good with classes from arbitrary programs. Libraries are usually designed to have few restrictions on their calling sequences and parameters. Classes that make up programs often have a number of restrictions on both the sequences of calls and their parameters.
We want to extend our system to provide better coverage for such classes. We have a number of possible approaches in mind:
Our analysis is implemented in Java. A firm grasp of Java is a must. Most qualified students will have successfully completed 6.005/6.170, but relevant practical experience would also be very valuable.
For more information please contact Jeff Perkins (jhp@csail.mit.edu)
No one likes writing more tests than necessary. It is hard to know when to stop, because it is hard to measure how good your test suite is. The only thing that really matters is how many bugs the test suite finds and how many it misses. But if you knew all the bugs, you wouldn't need the test suite!
Another way of evaluating a test suite is by using fake bugs: randomly change the program, and see how many of those changed versions (known as "mutants") are detected by the test suite. This is much easier than using real bugs. However, no one knows whether whether using mutants is as good as using real bugs. In other words, does a test suite that detects many mutants also detect many real bugs?
Using a publicly available repository of real bugs and a tool for introducing mutations into a program, we will answer this question. The question has great practical importance and the answer (whether positive or negative) will be publishable and will have a dramatic effect on the theory and practice of program testing. Developers are eager to spend the correct amount of effort on their test suites, and researchers find experimenting with mutants easier than experimenting with real bugs.
For more information please contact Michael Ernst (mernst@csail.mit.edu)
This project will use Palulu, a dynamic model based test generator, developed in our group. Palulu creates dynamic execution models from example executions of a subject program. This project will extend Palulu to model interactions between instances of different classes, and will use the extended version of Palulu to create the environment drivers for the model checker JavaPathFinder.
6.005, 6.170, or equivalent is a must. The implementation language is Java.
For more information please contact Shay Artzi (artzi@MIT.EDU)
For more information please contact Michael Ernst (mernst@csail.mit.edu)
It would be wonderful to have a magic tool that told you where in your program the bugs are. This tool could either take a program for which you can reproduce a bug (but you don't know where to fix the bug), or a program for which you don't know where the bugs are (in which case it would both find bugs and tell you where to fix them). Many people have proposed such tools — as we have in previous research.
However, there is a small problem: no one knows whether these tools actually work! In fact, it's likely that some of them do not work. For instance, is it really helpful to be told the 20% of your code in which 80% of the bugs are likely to appear? You don't want to go through 20% of your code just hoping to come across an error.
We would like to devise more precise and accurate approaches to fault localization, and to evaluate both previous and new approaches. The evaluation will use real errors and real programmers to see what works in practice. The evaluation is likely to raise new research issues and to inspire ideas for improved tools.
For more information please contact Michael Ernst (mernst@csail.mit.edu)
Java 7 will extend Java's annotation system, so that annotations can be written on any use of a type. For example, a Java programmer will be able to write List<@NonNull String>, among many other uses. This capability is exciting because it enables the creation of advanced tools for error detection and error prevention — e.g., proving that your program has no null pointer exceptions.
This syntax change was proposed by Michael Ernst, who is the first non-Sun-employee to be the specification lead for a Java language change. Now, we need to complete and maintain an implementation of the syntax changes that can ship as part of the JDK (javac, javap, changes to the Java Language Specification and the JVM Specification, etc.).
This is a challenging project because of the need to modify (carefully and correctly) industrial-strength software that is used by millions of people worldwide, and to interact with Sun engineers who will take over maintenance of the system. It is an exciting project for the same reasons, and you can hardly hope to find another project with greater real-world impact.
For more information please contact Michael Ernst (mernst@csail.mit.edu)
Type-checking helps to detect and prevent errors. However, type-checking doesn't prevent enough errors: our goal is to make it even more powerful and useful to programmers. For example, Java types do not indicate whether a variable may be null, or whether a value is intended to be side-effected. As a result, a Java program can suffer from null pointer exceptions and incorrect side effects.
We have built the Checker Framework, which permits users to define their own type systems that can be plugged into javac. We would like to do further extension and evaluation of the Checker Framework and of the type systems themselves. Sample topics include:
For more information please contact Michael Ernst (mernst@csail.mit.edu)
Incorrect mutation is a source of bugs in Java. For example, a particular method should not modify its arguments, or a client may read but should never write the fields of some object. Programmers should be permitted to state immutability properties about their code, and those properties should be automatically checked, by a compiler or by a run-time system. It is expensive to check this property at run time, and to date it has been impractical to check it at compile time.
We have prototyped two different language extensions for Java that permit a programmer to specify mutability properties about a program. The language extensions then automatically indicate bugs, or verify that no bugs exist in the program (that is, the program obeys the mutability properties). The Javari language offers only so-called reference immutability. The IGJ language starts from a substantially different design, and offers both reference immutability (only mutable references can mutate an object) and object immutability (an immutable reference points to an immutable object). In preliminary experiments, both languages have proved to be useful. However, the languages need to be made more expressive; the implementations need to be made more robust; tools such as inference algorithms need to be designed and implemented; and larger-scale experiments need to be done to point out the next avenues for research.
The following projects are largely independent of one another, and each one requires design, implementation, and evaluation.
For more information please contact Michael Ernst (mernst@csail.mit.edu)
Two varieties of analyses to which this could be applied are bug detection tools (whose output is otherwise far too verbose) and inference tools. FindBugs is a bug detection tool that produces far too much output to make it reasonable to use on substantial existing projects. DynComp is an inference tool whose output could become manageable to users if they were shown it in small doses. We have many other similar analyses, however.
This is probably a simple tool to write. (Or maybe it already exists: something of this sort appears to be built into FindBugs, but it would be nice to generalize that so as to be able to wrap any analysis.)
For more information please contact Michael Ernst (mernst@csail.mit.edu)