Effective Static Race Detection for Java

Author(s): Mayur Naik, Alex Aiken, John Whaley
Venue: ACM SIGPLAN Conference on Programming Language Design and Implementation
Date: 2006


Quality
3

Language: Java
Defect Type: Race conditions
Uses Annotations: Yes
Requires Annotations: No
Sound: No
Flow-sensitive: No
Context-sensitive: Yes

The authors of this paper describe a new method for finding race conditions in Java programs. The method works by selecting an initial set of pairs of memory accesses that could possibly be involved in a race condition and then refining the set of pairs through four successive stages: reachable pairs, aliasing pairs, escaping pairs, and unlocked pairs.
They also discuss the auto-generation of a main method harness for individual classes, to examine them outside of any one program.

The original set of pairs is constructed by looking at every place that a particular memory location (instance or static field or array element) is accessed according to a technique called k-object sensitivity and creating a pair for each combination of accesses. The “reachable pairs” stage eliminates pairs involving memory accesses that can’t be reached from more than one thread. The “aliasing pairs” stage eliminates pairs that involve the same field or array element, but can never access the same field or array element from the same object. The “escaping pairs” stage eliminates pairs that reference thread-local memory locations, such as references to local objects and data declared thread-local. The last stage “unlocked pairs” eliminates pairs that hold a common lock for the memory access. Pairs that remain after the last stage are candidates for race conditions, and so all of these pairs are reported. The authors point out that their initial set of memory access pairs is designed to be an over-approximation, and so there will likely be a number of false positives reported.

The authors implement their technique in a tool called Chord and employ their tool on a number of software programs ranging from ~2,600 lines of code to ~650,000 lines. Their results are quite productive, and their method finds more than a dozen bugs in a few of their test programs and more than 300 bugs in the largest program. Their method does however report many false positives as they warn about in the paper. The tool can also take quite a bit of time to run, with the median time being 1.5 minutes and the longest time being around 26 minutes. Because the initial set of pairs generated is an over-approximation, the method also consumes a large amount of memory which could make it infeasible for large projects.

0