Testing of software with concurrent behavior

The lock-based shared memory model has proven to be error prone and difficult to test. Furthermore a simplified memory abstraction based on threads with explicit synchronization does not scale well. With the advent of multi-core programming, the exploration of alternative concurrency models has begun. These alternatives avoid unprotected access of shared variables, therefore reducing the possibility of introducing race conditions, data races or locking complications. However, testing concurrent software remains problematic because of two properties inherent to the concurrent execution of software. First and foremost, concurrent software exhibits non-deterministic behavior. Namely, the test result is not guaranteed to be identical for each test run. Moreover, replaying a particular test scenario requires a tool recording the specific set of thread interleavings. On the other hand, the number of possible states exponentially increases with the program size. This makes it practically impossible to cover the entire state space in a test run. Finally, despite the alternative concurrency model, the program is potentially still subjected to race conditions. Principally, non-deterministic behavior should be isolated, which allows testing the deterministic part. there have been three approaches. The first method is based on heuristics, which covers random testing or fuzzing. This is relatively easy to conduct, but rather hard evaluating its coverage. Next, two formal models have been used, either a lock-set or happens-before relationship. While the lock-set model becomes obsolete with the implicit locking program models, the happens-before model is still valid. Finally More specifically, it is possible to deterministically run through different paths in the state space, a technique called state space exploration. However, due to computational restrictions, this exploration is limited to a fixed number of thread interleavings. Nevertheless, as a testing strategy it is valid under the assumption that a significant number of bugs will manifest in a limited number of thread interleavings. The goal of this PhD research is developing test concepts for concurrent software. For this purpose a tool will be developed, which enhances conventional white box test scenarios to explore a well-defined set of paths in the state space.The primary goal is to maximize test coverage of the state space, while minimizing the overhead of exploring redundant states. Secondary metrics are the exclusion of false positive test results, while limiting the number of false negatives. Novel to this approach is the classification of patterns in specific alternative concurrent programming models. This permits partial order reduction in the state space. Currently, research is focused on an asynchronous concurrent model, in which patterns for race conditions between an asynchronous task and its continuation are examined.status: publishe