Concurrent Random Test Generation

From FSL
Jump to: navigation, search

The increasing popularity of concurrent programming, for the Internet and on the server side, has brought the issue of concurrent defect analysis to the forefront. Concurrent defects such as unintentional race conditions or deadlocks are difficult and expensive to uncover, and such faults often escape to the field. Starting this year, most processors will have multiple cores and personal computers will have hyper-threaded processors. Programs that used to work well on single-threaded and single CPU core processors are now exhibiting problems. This means the testing of multi-threaded programs and the development of technology and tools to identify concurrent defects are more crucial than ever.

There are a number of features that distinguish concurrent defect analysis from sequential testing. These differences are especially challenging because the set of possible interleavings is huge and it is not practical to try all of them. First, only a few of the interleavings actually produce concurrent faults; thus, the probability of producing a concurrent fault can be very low. Second, under the simple conditions of unit testing, the scheduler is deterministic; therefore, executing the same tests repeatedly may well produce the same set of interleavings. Furthermore, the tests that reveal faults are usually long and run under environmental conditions that are different from the ones found in the testing stage. Consequently, they are not necessarily repeatable and when a fault is detected, extensive efforts must be invested in recreating the conditions under which it occurred. When these are finally recreated, the debugging itself may mask the bug (the observer effect).

Our methodology facilitates the use of a noise maker as a testing tool. A noise maker is random test generator that causes different interleavings to happen in runtime. It seeds the program with conditional scheduling primitives, such as yield() and wait(), that may cause context switches and timeout during the execution of the program. A noise maker is aimed at increasing the likelihood of exercising an incorrect behavior related to a concurrent bug. In a typical user scenario for our tool, jBlender, a given functional test t is run (without human intervention) against P, the program under test. This is done repeatedly. jBlender seeds critical events with synchronization primitives that may cause context switches. Each time the functional test t is run, jBlender produces a potentially different interleaving, as a result of context switches caused by the seeded synchronization primitives. Once a bug has manifested, jBlender can focus the scheduling noise to discover events related with the bug and provide high reproducibility of the bug.


Personal tools