2018 Reports

Partial Order Aware Concurrency Sampling

Yuan, Xinhao; Yang, Junfeng; Gu, Ronghui

We present POS, a concurrency testing approach that directly samples the partial orders of a concurrent program. POS uses a novel priority-based scheduling algorithm that naturally considers partial-order information dynamically and guarantees that each partial order will be explored with significant probability. This probabilistic guarantee of error detection is exponentially better than state-of-the-art sampling approaches. Besides theoretical guarantees, POS is extremely simple and lightweight to implement. Evaluations show that POS is effective in covering the partial-order space of micro-benchmarks and finding concurrency bugs in real-world programs such as Firefox’s JavaScript engine SpiderMonkey.

Keywords: Concurrency testing; Partial-order sampling; Randomized scheduling; Probabilistic error detection