False positives and negatives of the Racer algorithm

Eric | June 11, 2008

Today I gave a presentation about Racer in our lab seminar and people asked me some really interesting questions. I thought the answers might interest other people too so I would post them here…

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:

while (rideNo < 250000) {
    synchronized (Cart.class) {

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.

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

No. Racer is guaranteed to find all races in your program 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.