Cloud services have become critical infrastructure, yet long-studied concurrency bugs continue to cause real-world failures. Ideally, we want a system for concurrency testing that offers reliable control over schedules, is efficient, and can handle real-world programs at scale. Unfortunately, existing approaches usually have to sacrifice one or more of these.

The key insight in this thesis is to adopt a behavior-centric view of concurrency testing. Rather than faithfully reproducing the exact execution environment of a concurrent or distributed program, I argue that what matters for testing is preserving and exploring the space of observable program behaviors. Guided by this principle, I design and implement three systems, Fray, Fest, and Diorama. Fray serializes multithreaded JVM programs into controlled sequential executions using shadow locks, uncovering 19 real bugs in systems like Kafka and Lucene. Fest applies greybox fuzzing-inspired feedback to prioritize schedules likely to reveal new behaviors, achieving up to 41x higher behavioral coverage. Diorama extends this approach to distributed systems by replacing the network layer with in-memory message queues and wall-clock time with a logical clock, reducing distributed executions to controllable single-process ones.

86 pages

Thesis Committee:
Rohan Padhye (Co-Chair)
Vyas Sekar (Co-Chair)
Ben Titzer
Shan Lu (Microsoft Research)

Nicolas Christin, Head, Software and Societal Systems Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu