PENELOPE: Weaving Threads to Violate Atomicity∗

find, and are characterized by subtle interleaving patterns that tend to man-ifest in the field, while passing extensive randomized testing in development. Furthermore, they are hard to reproduce, record, and repair, primarily because the programmer faces the difficulty of considering all the possible interleavings exercised by a nondeterministic scheduler. With the advent of multicore and many-core hardware, concurrent and parallel software feature prominently in the future, making this an important problem to solve. The interleaving explosion problem: Testing all possible interleavings, even for a program under a single test input, is infeasible as the number of possible interleaving grows exponentially with the length of executions. This interleaving explosion problem is one of the most important challenges that needs to be overcome to achieve effective testing of concurrent programs. The current technology for testing concurrent programs on a test input is stress testing — to test the program under random schedules by creating a large number of threads and strewing the code with sleep commands for random time intervals, and letting the system run and re-run for days together. This methodology is highly unsystematic, has not not proven effective in finding bugs, and does not exploit the fact that most concurrency errors can be explained using a simple schedule that uses a very few threads but an intricate interleaving of them. The focus of research in this area has hence moved to testing systematically a small subset of schedules. For instance, the CHESS tool from Microsoft [6] expects programs to use a small number of threads, and tests all schedules that use a bounded number preemptions (unforced context-switches). Atomicity-violating schedules: Our thesis is that interleaving selection must be prioritized more effectively by favoring selection of those interleav-ings that are symptomatic of common error patterns of interactions amon