Eric Bodden

20°C

This paper won an ACM Distinguished Paper Award at ISSTA 2008.

Racer (joint work with Klaus Havelund, published at ISSTA 2008) is a new Eraser-based algorithm to detect data races in multi-threaded Java programs.  Our implementation uses three novel pointcuts that we implemented as a language extension to AspectJ, and using a novel algorithm called Racer that makes use of these pointcuts. We applied our implementation to the NASA K9 Rover Excecutive and found 70 data races, only one of which was known to NASA developers, although extensive studies had been performed on the code, using all sorts of error detection tools, at a time where 68 of these races were already present!

Download the paper here, our extended Technical Report here, or continue reading…

New AspectJ pointcuts

So how does it work? Firstly, we added the following three pointcuts to AspectJ.

• lock() matches whenever one enters a synchronized block or synchronized method
  • one can use lock() && args(l) to expose the lock l to the advice
• unlock() matches whenever one exits a synchronized block or synchronized method
  • one can use unlock() && args(l) to expose the lock l to the advice
• maybeShared(), a “semantic pointcut”, matches any field access (set or get), but only those that may be accessing shared fields; in particular we apply a static thread-local objects analysis to make it match on as few unshared field accesses as possible

The ajc compiler also supports the first two pointcuts if you give it the -Xjoinpoints:synchronization option. However, the maybeShared() pointcut only exists in the latest version of abc.

This pointcut is implemented using a re-weaving analysis. This means that we first weave the code, instrumenting every field access, and then analyze the woven program in order to see which field accesses may be multi-threaded, using Halpert et al.‘s static thread-local objects analysis. (We perform the analysis after weaving and not before because woven aspects may change the behaviour of the program, e.g. start new threads.) For each field access that cannot be multi-threaded we then disable the instrumentation again. In a last phase we re-weave the entire program, only weaving instrumentation in the program that has not previously been disabled.

In the following example piece of code, taken from the paper, the maybeShared() pointcut would match the two field accesses (well, actually four, two writes and two reads) shown in green, but not the one in red, because the “red field” exists once per thread and is therefore not shared.

class Task implements Runnable {
	static int shared;
	static int shared_protected;
	int not_shared;

	public void run() {
	    System.out.println(shared++);
	        synchronized(Task.class) {
		    System.out.println(shared_protected++);
		}
		System.out.println(not_shared++);
	}

	public static void main(String[] args) {
		Task task1 = new Task();
		Task task2 = new Task();
		Thread thread1 = new Thread(task1);
		Thread thread2 = new Thread(task2);
		thread1.start ();
		thread2.start ();
	}
}

Racer Algorithm

Using these three pointcuts it’s now pretty straightforward to intercept the events of locking, unlocking and access to a (potentially) shared field. This is all we need to do runtime monitoring of data races!

Racer is a variant of the well-known Eraser race detection algorithm. The algorithm detects races by recording and refining so-called lock-sets. For each field f in the program we record which locks L(f) are held by the thread that accesses f. The set is refined through intersection with the old set on each new access. Once the set becomes empty, a race can almost already be reported. I write almost because there are certain situations where empty lock sets are ok:

• if a field is only accessed by a single thread
• if a field is only read from but not written to

Racer therefore keeps track of “one thread” vs. “multiple threads” and “read only” vs. “read and written” using the state machine to the right. Interestingly, this state machine looks similar to the one that Eraser uses, but not quite. Eraser was designed for C programs, while Racer was designed for Java. In C it is sound to initialize certain fields (i.e. write to them) without synchronization before the fields are first accessed by another thread. In Java that is not the case! For instance the following program contains potential for a data race.

class ThisEscape {
    int i;

    ThisEscape(EventSource source) {
        source.registerListener (
            new EventListener() {
                public void onEvent(Event e) {
                    doSomething(e); //accesses i
                }
            }
        );
        i = 42;
    }
    ...
}

The problem here is that the event listener’s onEvent method may be executed by Swing’s Event Dispatch Thread, accessing the variable i though an explicit this-reference (not shown). A this point it’s not clear whether i has the default value 0 or the value 42. Therefore we have a race! The Eraser algorithm would however not detect such a race because it allows for writes in its initialization phase. Therefore a lot of such actual races went previously undetected when applying Eraser to Java code.

Results

We applied Racer to an experimental planetary rover controller, named the K9 Executive, for a rover named K9 developed at NASA Ames Research Center.

The K9 Rover is an experimental hardware platform for autonomous wheeled rovers, targeted for the exploration of a planetary surface such as Mars. K9 is specifically used to experiment with new autonomy software. Rovers are traditionally controlled by low-level commands uploaded from Earth. The K9 Executive, a software module, provides a more flexible means of commanding a rover through the use of high-level plans in a domain specific programming language. High-level plans can for example be generated by an on-board AI-based planner. The Executive is essentially an interpreter for the plan language.

The Executive is multi-threaded. In the Figure to the right we show the threads relevant for the presentation in this paper as boxes. All threads are started from a main program in the class Main. The RuntimeExecutive thread is responsible for the overall execution of plans. The interpretation of a primitive plan element, a task, causes the RuntimeExecutive to ask the ActionExecution thread to command the vehicle to perform the task’s action. The ActionExecution thread subsequently is responsible for commanding the vehicle and reporting back the status. The ActionExecution thread updates a database whenever the status of a vehicle component changes. The ExecCondChecker (composed of two separate threads) monitors changes in the database (DbMonitor), prioritizes the changes and signals back the RuntimeExecutive through Filter.

Racer signalled 70 data races in this code, falling into the following categories.

1. One of the races had been planted in order to test race detection tools. Racer had no problem detecting it.
2. The next two races were actually in code that had been added to the Executive at a very late stage, in order to evaluate the effectiveness of a static optimization for a deadlock detection algorithm. The races concern two fields that count how often certain monitoring code is executed.
3. The remaining 67 races were all related to the initialization anti-pattern mentioned above.
   • There were 2 false positives in this category (and 65 actual races). The false positives were due to final fields (see below).

It should be noted that this code had been sighted and checked with several error detection tools in the past, when all but the two races of the second category were already present. None of the tools found the 67 races in category 3! This is because most tools were using the Eraser algorithm for race detection which is, as I explained above, not suitable for the use in Java.

FAQ – some frequent questions and answers

Can Racer produce false positives?

Yes, Racer can produce false positives but out of our 70 reported races only two were false positives. There are two primary reasons for false positives. First reason (quoting from the paper):

We wish to note that we could find only two false positives.

All were in the third category of 67 races. In these cases, a

final variable was initialized within an object’s constructor

by one thread and then accessed by another thread, without

synchronization, but after execution of the constructor had

finished. As noted above, such access is safe.

We could have excluded final variables from monitoring,

simply by conjoining the pointcuts in our Racer aspect with:

!set(final ∗ ∗) && !get(final ∗ ∗)

However, there can still be races involving final variables, for

instance if a constructor itself starts a thread. We therefore

opted to monitor final fields as well.

The second reason can be seen in the following code:

T1:
while (rideNo < 250000) {
    synchronized (Cart.class) {
        rideNo++;
    }
}

T2:
synchronized (Cart.class) {
    while (Cart.rideNo == num) { ... }
}

This code results in an empty lock set for rideNo because T1 accesses this field outside of the lock. Also the field is accessed by multiple threads and it is written. Therefore we report a race. Nevertheless, T1 is the only thread ever writing to rideNo. Therefore it may read (and read only!) rideNo without synchronization. There is a “read/read” race between the read in T1 and the read in T2 but such races are not a problem. We could maybe get around this problem by modifying the Racer state machine. Interesting food for thought…

A third source of false positives may be if you use custom locks in your program instead of synchronized blocks. In that case you would have to adjust the pointcuts in the Locking aspect.

A fourth reason is that currently we do not take all kinds of synchronization constructs into account, e.g. we do not regard that statements executed in a thread T always execute after T was started and in particular that all writes that were performed before T was started are visible to T.

The last reason is that we abstract from predicates, which can be seen in the following code, taken from this paper:

Initially: x = y = 0;
thread1 {
  x = 1;
  lock(L);
  y = 1;
  unlock(L);
}

thread2 {
  lock(L);
  if (y==1) {
    if (x != 1){
      //ERROR
    }
  }
  unlock(L);
}

Here x may seem unprotected. However it is implicitly protected by y: At line 12, if y is 1 then we know that line 5 executed and therefore the code must have synchronized on L and therefore x must have value 1 and this value must be visible to T2. This is however impossible to determine without analyzing or executing the conditionals. Sen solves this problem in his RaceFuzzer tool by actually executing the code until right before the race to see if the race actually happens or not. Racer however would warn about a potential race because x is written to unprotected. As our experiments show, code like the above rarely exists and therefore Racer actually produces very few false positives.

Can Racer miss races, i.e. produce false negatives?

No. Racer is guaranteed to find all races on the program path on which it is executed. Eraser has the same property. However if you use our maybeShared() pointcuts then you may get unsoundness because the Thread-local objects analysis that we use to optimize this pointcut makes some assumptions that are not always 100% sound.

For the evaluation in you paper, did you execute a test harness with especially good code coverage?

No we did not do any such tweaking. We simply executed the Rover Executive on one single more or less random high-level plan.

Try it yourself!

My implementation of Racer is freely available for download. The package contains a copy of the abc compiler implementing the three new pointcuts. Those pointcuts are also part of the 1.3.0 release of abc, which supports Java 5.

Acknowledgements

Klaus and I thank Clark Verbrugge for helping us validate some of the data races we found in the K9 rover executive. Also we are grateful to him, Richard Halpert, and Chris Pickett for making their thread-local objects analysis and their benchmarks available to us. We thank Stefan Savage for providing clarifications on Eraser. Part of the work described in this paper was carried out at the Jet Propulsion Laboratory, California Institute of Technology, under a contract with the National Aeronautics and Space Administration.