Protocol-State Guided Fuzzing of Distributed Systems

How IJON-style fuzzer annotations could help drive deeper behavior and scenario coverage for distributed databases, consensus algorithms, and replicated storage systems.

After digging deeper from Dominik Tornow’s excellent paper find below, I learned that IJON-style annotations are now available in AFL++. This immediately made me wonder if the same idea could be used for testing distributed systems.

The short version: ordinary fuzzers are guided by code coverage. But in distributed systems, we driving the system via “did we execute a new code branch?” isn’t helpful. What we are going after is “did the system reach a new protocol state?”

Exploring distributed systems with deterministic simulation

Imagine a simulator harness driving a distributed database, a consensus protocol like Raft, or a replicated storage system. Many of these simulators are driven by a seeded PRNG, for example, TigerBeetle’s VOPR, RedisLabs’ virtraft2. Sometimes, this works reasonably well: the simulator explores many randomized schedules, and each run remains reproducible from its seed. If run in CI, over time, it will explore a wide range of behaviors.

But PRNG-driven simulation is still unguided with respect to protocol behavior. The simulator explores random behavior, but it does not automatically move into deep, rare, or interesting protocol states.

If we care about exercising a particular family of behaviors, it often needs to be baked into the simulator code (for example, Tigerbeetle’s VOPR hardcodes a “safety” and “liveness” phase to explore a specific family of behaviors). In the extreme case, you end up with several different simulators that bias toward leader elections, recovery from failure, and so on.

Enter fuzzing

In principle, greybox fuzzing sounds like the right tool for this problem. It is coverage-guided, so the fuzzer keeps expanding inputs that push the system into previously unexplored corners.

The catch is that ordinary fuzzer feedback is code coverage. The fuzzer keeps inputs that execute new code branches. That works well when “interesting behavior” correlates with “new code was reached.” It is a powerful heuristic to catch overflows and crashes in parsers, decompression libraries, etc.

In distributed systems, however, meaningful behavior often comes from executing the same code paths many times while the overall protocol state moves forward. For example, a Raft implementation may run the same code repeatedly while terms advance. If we use ordinary coverage, the fuzzer will discard executions that drive the system forward, but aren’t new at the code level.

Protocol-state guided fuzzing

IJON-style annotations, which recently landed in the AFL++ fuzzer, offer a way around this.

Instead of relying only on branches, the simulation harness can expose protocol-level progress to the fuzzer. For a Raft harness, that might mean that the fuzzer registers advancing the current term as progress. Or it may count election outcomes. This guides the fuzzer to keep inputs that drive the distributed system into deeper and rarer protocol states, even when those inputs do not execute new code.

One huge potential I see, is that many specialized simulation harnesses could be replaced with a single, generic harness annotated with different optimization targets for the fuzzer.

Nothing new under the sun

This is not, of and by itself, a new idea. It is closely related to the notion of functional coverage in hardware verification. In hardware, code coverage tells you which RTL lines or branches were exercised. Functional coverage lets you define the behaviors you actually care about: did the design enter this state, observe this transition, or hit this corner case?

Users of SVA/PSL in hardware description languages like Verilog, VHDL, or SystemVerilog will be familiar with covergroup, coverpoint, cross and their cousins. These let check if the design has exercised the behaviors you care about.

IJON-style annotations feel like a software fuzzer-facing version of this idea. They let us define protocol-level functional coverage and feed it back into the search process.

Next steps

So the idea is simple:

Ordinary fuzzing: “Did this input reach new code branch?”

Protocol-state guided fuzzing: “Did this input drive the distributed system into a new or deeper protocol state?”

Watch this space. I’ll spend some time exploring this further. If this works, it could give us a practical bridge between three existing ideas: coverage-guided fuzzing from software testing, functional coverage from hardware verification, and deterministic simulation from distributed-systems testing.

If you have a system in mind that lends itself for an initial exploration, please reach out.