Subject Infrastructure Repository

Get Access!
 
Home
SIR Software Objects
 
SIR Users and Publications
Frequently Asked Questions
Repository License
 
Acknowledgments

Object Biography: Concurrency Testing Subjects

The concurrency testing subjects are a collection of Java programs that exhibit the characteristics of multithreaded activities requiring arbitration. The subjects are useful in studying both the behavior of concurrent program designs and also for model checking analysis. These subjects were collected and used by Dwyer et al. in [DwyerFSE06] to study factors affecting path-sensitive error detection techniques.

The concurrency subjects presented here consist of the suites of programs compiled by the Bandera [Dwyer06] and Java PathFinder (JPF) [Visser00] projects. These programs cover nearly all of the multi-threaded programs that were used as of 2006 in evaluating path-sensitive Java analyses in the literature; some papers also used Java standard library implementations as analysis subjects.

The examples can be divided into two kinds: concurrency error kernels and realistic programs. Concurrency error kernels are very simple programs that distill the essence of a particular concurrency error. Examples include adapted versions from the concurrency literature, such as dining philosophers, as well as programs that exhibit Java-specific errors. A student independently implemented kernels for the Java concurrent bug patterns (CBP) described in [Farchi03]. These kernels typically include the control and data structures required to exhibit the error and nothing else. Realistic programs are small to medium size programs that perform a computation over rich data structures. They tend to be much larger than the concurrency kernels, often accept input data that parameterizes the computation, and include significant control and data structures that are unrelated to the error.

These examples also contain variants on examples from a collection of multi-threaded Java programs being developed at IBM to support testing and analysis research [Eytani07]. This set of programs overlaps with the Bandera and JPF programs to some extent, but it also includes a number of programs that were developed to encode common Java concurrency bug patterns. Many of the IBM benchmarks were written following standard forms of parameterization, e.g., the degree of multi-threading in an example was indicated by a string "little", "average", or "lot", for error reporting, e.g., error messages were printed to a log file, and for perturbing the schedules so as to make errors more difficult to detect by testing, e.g., by inserting random "sleep()" calls. These examples were transformed to further parameterize them, e.g., programs accept an integer that indicates the degree of multithreading, to indicate errors through assertion violations, and to remove "sleep()" calls; this last step being easily automated. One example transformation performed was non-trivial. This involved refactoring the Account example into a version called AccountSubtype that uses an interface and sub-typing to organize different types of accounts, e.g., checking, savings, etc. The rationale for this was that it is a more realistic object-oriented structure for this program and the fault was related to account type, so this might help us understand the interaction between OO structure and fault detection. In all cases, the resultant transformed versions of the IBM benchmark programs are considered behaviorally equivalent to the original versions.

The subjects available from the SIR website are:

Subject NameConcurrency Bug Type
accountDeadlock, Race
accountsubtypeDeadlock, Race
airlineRace
alarm_clockNull Pointer Exception
allocationVectorNo Lock
boundedBufferDeadlock
cleanDeadlock
daisyAssert
deadlockDeadlock
deosAssert
diningPhilosophersDeadlock
elevatorArray Index Out-Of-Bounds Exception
groovyDeadlock
langRace
linkedlistNull Pointer Exception
log4j1Deadlock
log4j2Atomicity
log4j3Null Pointer Exception
loseNotifyDeadlock
nested_monitorDeadlock
piperDeadlock
pool1Race
pool2Race
pool3Race
pool4Deadlock
pool5Deadlock
pool6Deadlock
producer_consumerRace
raxextendedRace
raxextended2Race
readers_writersDeadlock, Race
reorderAtomicity
replicated_workersDeadlock
sleepingBarberDeadlock
twoStageTwo Stage Access
wrongLockWrong Lock

Description of bug classifications:

BugDescription
DeadlockResource allocation contention problem
RaceThread execution order and execution speed problem
No LockResource use contention resolution problem
AssertWhen resources (time) insufficient for task scheduled
Array Index Out-Of-Bounds ExceptionArray manipulation problems in a multithreaded context
Null Pointer ExceptionNull pointer referenced due to unprotected field access
AtomicityA non-interference between threads problem
Two Stage AccessA failure to lock all relevant datasets throughout a transaction problem
Wrong LockDifferent locks are obtained by different threads problem

A more detailed description of the concurrency bug types classifications can be found in [Farchi03].


[Eytani07]. Eytani, Y. and Havelund, K. and Stoller, S.D. and Ur, S., "Toward a framework and benchmark for testing tools for multi-threaded programs", in Concurrency and Computation: Practice and Experience, Vol 19, Issue 3, pp 267-279. John Wiley & Sons Ltd. 2007.

[DwyerFSE06]. Dwyer, M.B. and Person, S. amd Elbaum, S., "Controlling factors in evaluating path-sensitive error detection techniques ", in Proceedings of the 14th ACM SIGSOFT Symposium on Foundations of Software Engineering, November 2006.

[Dwyer06]. Dwyer, M.B. and Hatcliff, J. and Hoosier, M. and Ranganath, V. and Robby and Wallentine, T., "Evaluating the effectiveness of program slicing for model reduction of concurrent object-oriented programs ", in Proceedings of the 12th International Conference on Tools and Algorithms for Construction and Analysis of Systems, 2006.

[Farchi03]. Farchi, E. and Nir, Y. and Ur, S., "Concurrent bug patterns and how to test them", in Proceedings of the 17th International Symposium on Parallel and Distributed Processing, 2003.

[Visser00]. Visser, W. and Havelund, K. and Brat, G. and Park, S., "Checking programs", in Proceedings of the 15th IEEE Conference on Automated Software Engineering, September 2000.

 


Try the following link to upgrade the page display. (Explanation)