Blackbox Fuzzing of Distributed Systems with Multi-Dimensional Inputs and Symmetry-Based Feedback Pruning

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.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-