Keynote Talk: Effective Random Testing for Concurrent and Distributed Programs

Rupak Majumdar
MPI-SWS Kaiserslautern (Germany)


Rupak Majumdar is a Scientific Director at the Max Planck Institute for Software Systems.  His research interests are in the verification and control of reactive, real-time, hybrid, and probabilistic systems, software verification and programming languages, logic, and automata theory. He received his PhD from the University of California at Berkeley. He has received « Most Influential Paper » awards from SIGPLAN’s POPL and PLDI conferences, an NSF Career award, a Sloan Foundation fellowship, and an ERC Synergy award.


Random testing has proven to be an effective way to catch bugs in distributed systems. This is surprising, as the space of executions is enormous. We provide a theoretical justification of the effectiveness of random testing under various « small depth » hypotheses.  First, we show a general construction, using the probabilistic method from combinatorics, that shows that whenever a random test covers a fixed coverage goal with sufficiently high probability, a small randomly-chosen set of tests achieves full coverage with high probability.  In particular, we show that our construction can give test sets exponentially smaller than systematic enumeration.  Second, based on an empirical study of many bugs found by random testing in production distributed systems, we introduce notions of test coverage which capture the « small depth » hypothesis and are empirically effective in finding bugs.  Finally, we show using combinatorial arguments that for these notions of test coverage we introduce, we can find a lower bound on the probability that a random test covers a given goal. Our general construction then explains why random testing tools achieve good coverage—and hence, find bugs—quickly.




All deadlines are at 23:59 AoE

March 5th, 2021, March 19th, 2021

Abstract submission deadline

March 12th, 2021 March 26th, 2021

Paper submission deadline

April 26th, 2021 April 30th, 2021

Acceptance notification

May 10th, 2021

Camera ready

May 10th, 2021

Pre-recorded talk


Revised selected papers will be published as a post-proceedings in Springer's LNCS "Lecture Notes in Computer Science"

Partners & Sponsors