JitterBug |
What is JitterBug? |
JitterBug transparently intercepts send- and receive-any operations, and delivers them to the application in a controlled, perturbed fashion. These perturbations help cover a larger space of possible message orderings, thereby increasing the chances of finding order-dependent bugs.
» Motivation: Message-order bias
» Technique: A message perturbation layer
» Results: Improving coverage
» Where to go for more information
Information:
Paper (PDF)
| Slides (PDF)
| BibTeX
P0 posts two receive-any operations, with 2 possible outcomes. JitterBug elicits order-dependent bugs.
P0 posts two receive-any operations, with 2 possible outcomes. JitterBug elicits order-dependent bugs.
Motivation: Message-order bias.
Consider a p-process job in which P0 posts p-1 receive-any operations. We expect all (p-1)! possible orderings will be equally likely, but observe strong machine-dependent bias in practice. Thus, extensive repeated testing may still miss order-dependent bugs!
(Click to enlarge)
Technique: A PNMPI layer that perturbs send- and receive-any operations.
We built wrappers around MPI_send and MPI_receive that intercept send- and receive-any operations, and perturbs—in a controlled manner—the order in which the application sees those messages.
» At sends: We insert random delays, where the user specifies the minimum and maximum delay times.
» At receives: We buffer up to some number of messages, and return them in permuted order. We choose the permutation deterministically.
We implemented this layer in the PNMPI framework, which extends the standard PMPI profiling interface to support multiple tool layers. Thus, JitterBug can be used in conjunction with other MPI tool layers, such as Umpire.
These techniques were inspired by irritators, originally proposed for IBM's ConTest, a tool for eliciting bugs in multithreaded applications.
Results: Improving coverage.
We evaluated these techniques on a number of model problems, eliciting bugs up to the expected theoretical limits when all message orders are equally likely.
(Click to enlarge)
More information.
For details, see our recent paper or slides, which won best paper at the Parallel and Distributed Testing and Debugging (PADTAD) Workshop, 2006.To cite JitterBug, you can use this BibTeX entry.