  Grey-box fuzzing is the lightweight approach of choice for finding bugs in
sequential programs. It provides a balance between efficiency and effectiveness
by conducting a biased random search over the domain of program inputs using a
feedback function from observed test executions. For distributed system
testing, however, the state-of-practice is represented today by only black-box
tools that do not attempt to infer and exploit any knowledge of the system's
past behaviours to guide the search for bugs.
  In this work, we present Mallory: the first framework for grey-box
fuzz-testing of distributed systems. Unlike popular black-box distributed
system fuzzers, such as Jepsen, that search for bugs by randomly injecting
network partitions and node faults or by following human-defined schedules,
Mallory is adaptive. It exercises a novel metric to learn how to maximize the
number of observed system behaviors by choosing different sequences of faults,
thus increasing the likelihood of finding new bugs. Our approach relies on
timeline-driven testing. Mallory dynamically constructs Lamport timelines of
the system behaviour and further abstracts these timelines into happens-before
summaries, which serve as a feedback function guiding the fuzz campaign.
Subsequently, Mallory reactively learns a policy using Q-learning, enabling it
to introduce faults guided by its real-time observation of the summaries.
  We have evaluated Mallory on a diverse set of widely-used industrial
distributed systems. Compared to the start-of-the-art black-box fuzzer Jepsen,
Mallory explores more behaviours and takes less time to find bugs. Mallory
discovered 22 zero-day bugs (of which 18 were confirmed by developers),
including 10 new vulnerabilities, in rigorously-tested distributed systems such
as Braft, Dqlite, and Redis. 6 new CVEs have been assigned.
