Thread-safe libraries can help programmers avoid the complexities of multithreading. However, designing libraries that guarantee thread-safety can be challenging. Detecting and eliminating atomicity violations when methods in the libraries are invoked concurrently is vital in building reliable client applications that use the libraries. While there are dynamic analyses to detect atomicity violations, these techniques are critically dependent on effective multithreaded tests. Unfortunately, designing such tests is non-trivial.
We have designed a novel and scalable tool named INTRUDER for synthesizing multithreaded tests that help detect atomicity violations. The input to the tool is the implementation of the library and a sequential seed testsuite that invokes every method in the library with random parameters. INTRUDER analyzes the execution of the sequential tests, generates variable lock dependencies and constructs a set of three accesses which when interleaved suitably in a multithreaded execution can cause an atomicity violation. Subsequently, it identifies pairs of method invocations that correspond to these accesses and invoke them concurrently from distinct threads with appropriate objects to help expose atomicity violations.
Intruder is able to synthesize 33 multithreaded tests across nine classes in less than two minutes to detect 58 harmful atomicity violations, including previously unknown violations in thread-safe classes. We also demonstrate the effectiveness of Intruder by comparing the results with other approaches designed for synthesizing multithreaded tests.
Synthesizing Tests for Detecting Atomicity Violations
We thank Anuta Mukherjee for implementing a variant of CTrigger for detecting atomicity violations in Java programs. We run this detector on the tests synthesized by Intruder.