Statically driven generation of concurrent tests for thread-safe classes

摘要

Concurrency testing is an important activity to expose concurrency faults in thread-safe classes. A concurrent test for a thread-safe class is a set of method call sequences that exercise the public interface of the class from multiple threads. Automatically generating fault-revealing concurrent tests within an affordable time budget is difficult due to the huge search space of possible concurrent tests. In this paper, we present DepCon(+), a novel approach that reduces the search space of concurrent tests by leveraging statically computed dependencies among public methods. DepCon(+) exploits the intuition that concurrent tests can expose thread-safety violations that manifest exceptions or deadlocks, only if they exercise some specific method dependencies. DepCon(+) provides an efficient way to identify such dependencies by statically analysing the code and relies on the computed dependencies to steer the test generation towards those concurrent tests that exhibit the computed dependencies. We developed a prototype DepCon(+) implementation for Java and evaluated the approach on 19 known concurrency faults of thread-safe classes that lead to thread-safety violations of either exception or deadlock type. The results presented in this paper show that DepCon(+) is more effective than state-of-the-art approaches in exposing the concurrency faults. The search space pruning of DepCon(+) dramatically reduces the search space of possible concurrent tests, without missing any thread-safety violations.