Aspect-oriented Race Detection in Java

Eric | September 3, 2010

TSE PaperOur paper on Aspect-oriented Race Detection in Java (joint work with Klaus Havelund from NASA JPL) is now available on the TSE website and here. It’s part of a TSE special issue on best papers from ISSTA 2008.

The paper enhances the approach presented at ISSTA to also take thread spawns and joins into account. This addresses an omission in the original algorithm raised by Bill Pugh during the ISSTA conference.

Abstract:

In the past researchers have developed specialized programs to aid programmers detecting concurrent programming errors such as deadlocks, livelocks, starvation and data races. In this work we propose a language extension to the aspect-oriented programming language AspectJ, in the form of three new pointcuts, lock(), unlock() and maybeShared(). These pointcuts allow programmers to monitor program events where locks are granted or handed back, and where values are accessed that may be shared amongst multiple Java threads. We decide thread-locality using a static thread-local-objects analysis developed by others. Using the three new primitive pointcuts, researchers can directly implement efficient monitoring algorithms to detect concurrent-programming errors online. As an example, we describe a new algorithm which we call RACER, an adaption of the well-known ERASER algorithm to the memory model of Java. We implemented the new pointcuts as an extension to the AspectBench Compiler, implemented the RACER algorithm using this language extension and then applied the algorithm to the NASA K9 Rover Executive and two smaller programs. Our experiments demonstrate that our implementation is effective in finding subtle data races. In the Rover Executive RACER finds 12 data races, with no false warnings. Only one of these races was previously known.

Off to Seattle

Eric | July 17, 2008

image

I’ll be off to Seattle for the next week, presenting at Microsoft and attending ISSTA to present my paper on Racer. From what I’ve heard, Seattle is supposed to be quite beautiful, especially around this time of the year. I’ll tell you next week, so stay tuned ;-)

Comments
Comments Off on Off to Seattle
Categories
Misc, Research
Tags
Bug finding, ISSTA, Microsoft, Race detection, Racer, RacerAJ, Seattle

Data races in the JDK!

Eric | June 14, 2008

At the moment I am doing some more work on evaluating tracematches ahead-of-time. One tracematch patten that we use in our benchmarks we called ASyncIter, a simplified version of which looks as follows:

tracematch(Collection c) {
	sym sync after returning:
		call(* Collections.synchr*(..)) && args(c);
	sym iter before:
		call(* Collection.iterator()) && target(c);

	sync iter {
		if(!Thread.holdsLock(c))
			error(``Have to synchronize iterator at ''+thisJoinPoint);
        }
}

This tracematch reports an error if you create a synchronized collection and then iterate over this collection without holding a lock on the collection object. According to the JDK javadoc this is forbidden as it can lead to a race condition. One has to use synchronized collections as follows:

Read the rest of this entry »

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):

Read the rest of this entry »

Comments
Comments Off on False positives and negatives of the Racer algorithm
Categories
Research
Tags
Bug finding, Java, Race detection

Racer: Effective Race Detection Using AspectJ

Eric | May 7, 2008

image

I am happy to announce the availability of my latest publication (joint work with Klaus Havelund, to appear at ISSTA 2008). This time it’s about how to detect data races in multi-threaded Java programs using 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 here.

Comments
Comments Off on Racer: Effective Race Detection Using AspectJ
Categories
Research
Tags
AspectJ, Bug finding, Java, NASA, Race detection, Racer, Rover, Semantic pointcuts