Radius aware probabilistic testing of deadlocks with guarantees

Abstract

Concurrency bugs only occur under certain interleaving. Existing randomized techniques are usually ineffective. PCT innovatively generates scheduling, before executing a program, based on priori-ties and priority change points. Hence, it provides a probabilistic guarantee to trigger concurrency bugs. PCT randomly selects prior-ity change points among all events, which might be effective for non-deadlock concurrency bugs. However, deadlocks usually in-volve two or more threads and locks, and require more ordering constraints to be triggered. We interestingly observe that, every two events of a deadlock usually occur within a short range. We gener-ally formulate this range as the bug Radius, to denote the max dis-tance of every two events of a concurrency bug. Based on the bug radius, we propose RPro (Radius aware Probabilistic testing) for triggering deadlocks. Unlike PCT, RPro selects priority change points within the radius of the targeted deadlocks but not among all events. Hence, it guarantees larger probabilities to trigger dead-locks. We have implemented RPro and PCT and evaluated them on a set of real-world benchmarks containing 10 unique deadlocks. The experimental results show that RPro triggered all deadlocks with higher probabilities (i.e., >7.7x times larger on average) than that by PCT. We also evaluated RPro with radius varying from 1 to 150 (or 300). The result shows that the radius of a deadlock is much smaller (i.e., from 2 to 114 in our experiment) than the num-ber of all events. This further confirms our observation and makes RPro meaningful in practice.