Fri 9 Nov 2018 10:52 - 11:15 at Studio 1 - Testing Chair(s): Kim Bruce

Several recently proposed randomized testing tools for concurrent and distributed systems come with theoretical guarantees on their success. The key to these guarantees is a notion of bug depth—the minimum length of a sequence of events sufficient to expose the bug—and a characterization of $d$-hitting families of schedules—a set of schedules guaranteed to cover every bug of given depth $d$. Previous results show that in certain cases the size of a $d$-hitting family can be significantly smaller than the total number of possible schedules. However, these results either assume shared-memory multi-threading, or that the underlying partial ordering of events is known statically and has special structure. These assumptions are not met by distributed message-passing applications.

In this paper we present a randomized scheduling algorithm for testing distributed systems. In contrast to previous approaches, our algorithm works for arbitrary partially ordered sets of events revealed online as the program is being executed. We show that for partial orders of width at most $w$ and size at most $n$ (both statically unknown), our algorithm is guaranteed to sample from at most $w^2 n^{d-1}$ schedules, for every fixed bug depth $d$. Thus, our algorithm discovers a bug of depth $d$ with probability at least $1 / (w^2 n^{d-1})$. As a special case, our algorithm recovers a previous randomized testing algorithm for multi-threaded programs. Our algorithm is simple to implement, but the correctness arguments depend on difficult combinatorial results about online dimension and online chain partitioning of partially ordered sets.

We have implemented our algorithm in a randomized testing tool for distributed message-passing programs. We show that our algorithm can find bugs in distributed systems such as Zookeeper and Cassandra, and empirically outperforms naive random exploration while providing theoretical guarantees.

Fri 9 Nov

Displayed time zone: Guadalajara, Mexico City, Monterrey change

10:30 - 12:00
TestingOOPSLA at Studio 1
Chair(s): Kim Bruce Pomona College
10:30
22m
Talk
Compositional Programming and Testing of Dynamic Distributed Systems
OOPSLA
Ankush Desai University of California, Berkeley, Amar Phanishayee Microsoft Research, Shaz Qadeer Microsoft Research, Sanjit Seshia UC Berkeley
10:52
22m
Talk
Randomized Testing of Distributed Systems with Probabilistic GuaranteesDistinguished Paper Award
OOPSLA
Burcu Kulahcioglu Ozkan MPI-SWS, Germany, Rupak Majumdar MPI-SWS, Germany, Filip Niksic MPI-SWS, Mitra Tabaei Befrouei Vienna University of Technology, Georg Weissenbacher Technische Universität Wien
11:15
22m
Talk
Test Generation for Higher-Order Functions in Dynamic Languages
OOPSLA
Marija Selakovic TU Darmstadt, Germany, Michael Pradel TU Darmstadt, Rezwana Karim Nawrin Samsung Research America, Frank Tip Northeastern University
11:37
22m
Talk
Finding Broken Promises in Asynchronous JavaScript Programs
OOPSLA
Saba Alimadadi Northeastern University, Di Zhong Northeastern University, USA, Magnus Madsen Aarhus University, Frank Tip Northeastern University