Concurrency bugs are notoriously hard to detect and reproduce. Controlled concurrency testing (CCT) techniques aim to offer a solution, where a \textit{scheduler} explores the space of possible interleavings of a concurrent program looking for bugs. Since the set of possible interleavings is typically very large, these schedulers employ heuristics that prioritize the search to ``interesting'' subspaces. However, current heuristics are typically tuned to specific bug patterns, which limits their effectiveness in practice.
In this paper, we present \texttt{QL}, a learning-based CCT framework where the likelihood of an action being selected by the scheduler is influenced by earlier explorations. We leverage the classical Q-learning algorithm to explore the space of possible interleavings, allowing the exploration to adapt to the program under test, unlike previous techniques. We have implemented and evaluated \texttt{QL} on a set of microbenchmarks, complex protocols, as well as production cloud services. In our experiments, we found \texttt{QL} to consistently outperform the state-of-the-art in CCT.
Ritwika Ghosh University of Illinois at Urbana-Champaign, Chiao Hsieh University of Illinois at Urbana-Champaign, Sasa Misailovic University of Illinois at Urbana-Champaign, Sayan Mitra University of Illinois at Urbana-Champaign
Umar Farooq University of California at Riverside, Zhijia Zhao University of California at Riverside, Manu Sridharan University of California at Riverside, Iulian Neamtiu New Jersey Institute of Technology
Ritwika Ghosh University of Illinois at Urbana-Champaign, Chiao Hsieh University of Illinois at Urbana-Champaign, Sasa Misailovic University of Illinois at Urbana-Champaign, Sayan Mitra University of Illinois at Urbana-Champaign
Umar Farooq University of California at Riverside, Zhijia Zhao University of California at Riverside, Manu Sridharan University of California at Riverside, Iulian Neamtiu New Jersey Institute of Technology