Tamias: Feedback-Guided Systematic Concurrency Exploration for Transparent Distributed System Fuzzing

Abstract

Existing distributed system fuzzers are limited by coarsegrained, nondeterministic event control and weak support for systematic schedule mutation. They rely on timing perturbations (e.g., injecting delays), which can influence execution but do not precisely realize the fine-grained event orderings that trigger many distributed bugs. In addition, they do not integrate systematic schedule exploration with mutation, making exploration less effective in large search spaces. This paper presents Tamias, the first distributed system testing tool to integrate transparent, feedback-guided input exploration with systematic concurrency exploration. Tamias is built on two insights: effective distributed-system fuzzing requires feedback determinism rather than full execution determinism, and systematic scheduling algorithms can be integrated with feedback-guided mutation through a replay-explore strategy that allows them to benefit from prior executions while jointly exploring the input and schedule spaces. Guided by these insights, Tamias combines lightweight feedback-deterministic transparent event control with feedback-guided input and concurrency exploration, enabling effective distributed system testing. We evaluate Tamias on six widely used distributed systems implemented in C/C++ and Go, without requiring source-code modifications. Tamias found 12 new bugs across mature releases. Our ablation study shows that replay-explore mutation improves branch coverage by up to 22% and also improves bug-finding effectiveness. Tamias improves branch coverage over the state of the art and achieves feedback determinism for branch coverage on all evaluated target systems.