Browse Theses

Concurrent programs are notoriously difficult to write and debug, a problem that is becoming acute with the recent shift in hardware from uniprocessors to multicore processors. A fundamental concurrency bug is a race : a condition in a shared-memory multithreaded program in which a pair of threads may access the same memory location without any ordering enforced between the accesses, and at least one of the accesses is a write. Despite thirty years of research on race detection, today's concurrent programs are still riddled with harmful races.

We present an effective approach to static race detection for Java. We dissect the specification of a race to identify four natural conditions, each of which is sufficient for proving a given pair of accesses race-free, and all of which are necessary in practice as different pairs of accesses may be race-free for different reasons. We present four static analyses each of which conservatively approximates a separate condition while together enabling the overall algorithm to report a useful set of potential races. We have implemented our approach and report upon our experience applying it to a suite of eight multithreaded Java programs which includes a mix of libraries, complete programs, previously studied programs, and newer, real-world, open-source programs.

For complete programs, the approach is sound in that it finds all races. On our benchmark suite, the approach is precise in that it has a false positive rate of 25% (only one in every four reported races is not in fact a race) and it is reasonably scalable in that it is fully automatic and checks programs comprising hundreds of thousands of Java bytecodes in a few minutes. Finally, the approach is effective, finding tens to hundreds of previously unknown concurrency bugs in mature and widely used Java programs in our benchmark suite, many of which were fixed upon reporting.