Bounded partial-order reduction
Authors:
Open Access
- 29 October 2013
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 48 (10) , 833-848
Abstract
Eliminating concurrency errors is increasingly important as systems rely more on parallelism for performance. Exhaustively exploring the state-space of a program's thread interleavings finds concurrency errors and provides coverage guarantees, but suffers from exponential state-space explosion . Two prior approaches alleviate state-space explosion. (1) Dynamic partial-order reduction (DPOR) provides full coverage and explores only one interleaving of independent transitions. (2) Bounded search provides bounded coverage by enumerating interleavings that do not exceed a bound. In particular, we focus on preemption-bounding. Combining partial-order reduction with preemption-bounding had remained an open problem. We show that preemption-bounded search explores the same partial orders repeatedly and consequently explores more executions than unbounded DPOR, even for small bounds. We further show that if DPOR simply uses the preemption bound to prune the state space as it explores new partial orders, it misses parts of the state space reachable in the bound and is therefore unsound. The bound essentially induces dependences between otherwise independent transitions in the DPOR state space. We introduce Bounded Partial Order Reduction (BPOR), a modification of DPOR that compensates for bound dependences. We identify properties that determine how well bounds combine with partial-order reduction. We prove sound coverage and empirically evaluate BPOR with preemption and fairness bounds. We show that by eliminating redundancies, BPOR significantly reduces testing time compared to bounded search. BPOR's faster incremental guarantees will help testers verify larger concurrent programs.Keywords
This publication has 8 references indexed in Scilit:
- Bounded partial-order reduction2013
- Delay-bounded scheduling2011
- Fair stateless model checking2008
- Iterative context bounding for systematic testing of multithreaded programs2007
- Dynamic partial-order reduction for model checking software2005
- Exploiting Object Escape and Locking Information in Partial-Order Reductions for Concurrent Object-Oriented ProgramsFormal Methods in System Design, 2004
- Model checking for programming languages using VeriSoft1997
- Defining conditional independence using collapsesTheoretical Computer Science, 1992