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, exploring 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, like TigerBeetle’s VOPR or 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. Greybox fuzzers are coverage-guided, so they keep mutating inputs with the goal of pushing the system into unexplored corners.

The catch is that graybox fuzzing relies on code coverage for this feedback loop. The fuzzer keeps inputs that execute new code branches, and derives new inputs from them. This approach works well when “interesting behavior” somewhat correlates with “new code was reached”. This is a useful heuristic to catch overflows and crashes in parsers, decompression libraries, etc: Push the program into previously uncovered code, and you may find a bug.

However, in distributed systems, “interesting” system behavior often requires executing the same code paths many times. In a fuzzing harness for a distributed system this is often the case, because it calls into the same code repeatedly while driving multiple nodes of the system through different protocol states. Take Raft as an example: a fuzzing harness has to call into leader election code multiple times for the fuzzed system to actually elect a leader. If we use “ordinary” code coverage, the fuzzer will discard executions that execute this code a second time, because they aren’t covering new code.

Protocol-state guided fuzzing

IJON-style annotations, recently added to the AFL++ fuzzer, offer a way around this.

They allow us to expose protocol-level progress to the fuzzer. For a Raft harness, this could mean registering the furthest index, or the number of failed or successful elections. Exposing these as coverage to the fuzzer then helps the fuzzer to drive the system from these deep protocol states – even when the inputs do not cover new code branches.

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 measures how many RTL lines or branches were exercised. Functional coverage defines which behaviors are actually covered: did the design enter an interesting state, transition, or 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 are a software fuzzer version of this idea: they let us define protocol-level functional coverage and feed it back into the fuzzer’s search process.

Next steps

So the idea is simple:

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

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

Watch for updates. Obviously, this is not straight-forward. It takes the fuzzing harness from a mechanical blackbox to a gray/whitebox artifact that encodes some domain knowledge of the system under test. But it is a promising idea, and I’ll spend some time exploring this further. If it works, the potential is to bridge three existing ideas: coverage-guided fuzzing from software testing, functional coverage from hardware verification, and deterministic simulation from distributed-systems testing. In contrast to most model-based testing approaches, it also promises a way of driving deeper behavior and scenario coverage while staying within the implementation language of the system under test – something I have seen a lot of engineering teams prefer.

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