Blackbox Fuzzing of Distributed Systems with Multi-Dimensional Inputs and Symmetry-Based Feedback Pruning
Yong-Hao Zou, Jia-Ju Bai, Zu-Ming Jiang, Ming Yu Zhao, Diyu Zhou · 2025
This paper presents DistFuzz, which, to our knowledge, is the first feedback-guided blackbox fuzzing framework for distributed systems.The novelty of DistFuzz comes from two conceptual contributions on key aspects of distributed system fuzzing: the input space and feedback metrics.Specifically, unlike prior work that focuses on systematically mutating faults, exploiting the request-driven and timing-dependence nature of distributed systems, DistFuzz proposes a multi-dimensional input space by incorporating regular events and relative timing among events as the other two dimensions.Furthermore, observing that important state changes in distributed systems can be indicated by network messages among nodes, DistFuzz utilizes the sequences of network messages with symmetry-based pruning as program feedback, which departs from the conventional wisdom that effective feedback requires code instrumentation/analysis and/or user inputs.DistFuzz finds 52 real bugs in ten popular distributed systems in C/C++, Go, and Java.Among these bugs, 28 have been confirmed by the developers, 20 were unknown before, and 4 have been assigned with CVEs.Prior work has applied fuzzing, a promising testing technique [2], [14], [19], [22], [70], to distributed systems.A pioneer work is Jepsen [21], a blackbox fuzzer that is well-known for its effectiveness in finding consistency violations.Based on user-provided schedule generators, Jepsen randomly generates: 1) workloads to drive the system, and 2) faults injected into the systems.CrashFuzz [15] and Mallory [37] are greybox fuzzers that advance Jepsen by using different feedback to guide the mutation of injected faults.CrashFuzz uses edge coverage, a Jia-Ju Bai is the corresponding author.popular metric for single-node systems [2], [14].The feedback in Mallory requires the user to annotate code blocks that are considered to be important.Afterwards, during fuzzing, Mallory collects two types of events: 1) the invocation of userannotated code blocks, and 2) network messages among nodes.The sequence of these events is used as feedback, and Mallory considers an event sequence is uninteresting, if it is too similar to a previous one.However, the above prior work still suffers from important limitations on two key aspects of fuzzing effectiveness: 1) fuzzing input, and 2) feedback metric.Regarding fuzzing input, given the huge search space, the random generation approach used by Jepsen is highly ineffective.Furthermore, only mutating and injecting faults based on feedback, as CrashFuzz and Mallory do, can miss many bugs, as we elaborate subsequently and showcase in Figure 6 and Figure 7.Regarding fuzzing feedback, the edge coverage used by CrashFuzz is ineffective for distributed systems.This is because, unlike single-node systems, distributed systems often execute almost the same code for requests, making edge coverage saturates after exploring only a few states [37], and thus, ineffective for distributed systems.Mallory's feedback requires laborious and error-prone user annotations and more importantly, as we elaborate subsequently, misses interesting states as well as explores redundant states.This paper presents DistFuzz, which, to the best of our knowledge, is the first feedback-guided blackbox fuzzing framework for distributed systems.Table I compares DistFuzz with other fuzzers.The novelty of DistFuzz comes from the two conceptual contributions on testing input space and feedback metric, which depart from the conventional wisdom in prior distributed system fuzzers.Conceptual contribution #1: extending input space with regular events and timing intervals.For the input space of distributed systems, our new insight is that, faults are just one dimension of it.In essence, faults are rare internal events to trigger state changes in distributed systems.We identify another two important input dimensions: 1) client requests and control commands, which, in contrast to faults, are external events to trigger state changes; and 2) relative timing among different events, since, for a distributed system, same events with different timing are likely to result in different states (ex-Network and