Source and reproducible run: https://gitlab.com/mscupcakegkill/wrfuzz

Comparison tracing made my fuzzer worse

I built a coverage-guided fuzzer from scratch, without libFuzzer or AFL, to find out what each
component actually contributes. Then I added comparison tracing — the mechanism libFuzzer is
best known for — and the fuzzer stopped finding bugs completely.

Not "found fewer". Zero, in 200,000 executions, with lower coverage than before I added it.

This is the story of why, because it is not the story you get from reading libFuzzer's source.

The setup

The fuzzer is about 300 lines of C: sanitizer coverage for feedback, a corpus of inputs that each
reach somewhere new, and seven mutation operators applied in sequence. The target is a toy parser
for "WRM" <len> <payload>, where a payload starting with ABCD counts as a bug.

The seed is WRM\x04wxyz — the first three bytes right, everything after wrong. To find the bug
the fuzzer has to discover A, B, C and D with no prior knowledge of what it is looking for.

With coverage feedback alone it took 124,573 executions. That is bad. Random guessing would
need 256⁴ ≈ 4.3 billion, so coverage bought four orders of magnitude, but it should have bought
more. The fuzzer had no idea what the program was comparing, so it had to stumble onto each byte
by luck.

Comparison tracing is supposed to fix exactly this. Intercept every comparison, feed the compared
values back into mutation, and the fuzzer stops guessing.

The obvious implementation

One pool of 4,096 slots. Every comparison stores both of its operands. Mutation picks a random
value from the pool and writes it at a random offset in the input.

This is what I wrote first, and it is roughly what the description sounds like.

Result: no bug found in 200,000 executions, and coverage dropped from 12 edges to 10.

Dumping the pool

The fuzzer has a DUMP_CMP=1 mode that prints what comparison tracing collected. I expected to
see the characters the parser was checking for. Here is what came out:

w=1 :  8 values    <- 'W', 'R', 'M', 'A', 'B' are in here
w=8 : 97 values    <- noise from size_t comparisons

Eight useful values against ninety-seven useless ones. The program compares size_t values far
more often than it compares single bytes — lengths, buffer sizes, loop counters — and every one
of those comparisons deposits an 8-byte value that is meaningless as input.

With a 97-to-8 ratio in a single pool, the values that mattered came up about 8% of the time.
Multiply that by the chance of landing at the correct offset and the answer is: almost never.

The tracing was working. It was faithfully recording what the program compared. The problem was
that I had assumed all comparisons are equally interesting.

The fix

Three changes, and the third one is the one I did not expect to matter.

1. Split the pool by width. Four pools, one per operand width (1, 2, 4, 8 bytes), and choose
the width before choosing the value, weighted toward narrow. A 1-byte comparison is far more
likely to be about input than an 8-byte one.

2. Store one side for const_cmp. When the program compares against a constant, the constant
is the thing worth writing into the input. Plain cmp still stores both sides, because there is
no way to tell which one came from the input.

3. Favour the newest seed. Half the time, mutate from the entry most recently added to the
corpus. That is the one that reached furthest; picking uniformly throws recent progress away.

Changes 1 and 2 took 124,573 down to 2,673. Change 3 took it to 2,309.

A 54x improvement over no tracing at all, at the cost of one edge of peak coverage. The fuzzer
now finds the bug early and spends its time there instead of exploring elsewhere.

What I take from it

Comparison tracing does not produce equally useful data. The literature describes it as
"feed compared values back into mutation", which is accurate and also useless as an
implementation guide. A width-8 value from a size_t comparison and a width-1 value from a
character check are not the same kind of hint, and treating them as one pool is the difference
between 200,000 executions with no result and 2,309 with one.

A negative result is worth more than a lucky number. If I had written the naive version,
found nothing, and concluded the target was safe, I would have been wrong for the same reason
most fuzzer users are wrong: the fuzzer never reached the code. Dumping the pool took ten
minutes and turned a dead end into the only interesting thing in the project.

The measurements are the project. The fuzzer is 300 lines. The interesting part is knowing
that each line of it is worth what I claim, and being able to show the run where it was not.

Reproducing

git clone https://gitlab.com/mscupcakegkill/wrfuzz
cd wrfuzz && make && ./fuzz 200000
DUMP_CMP=1 ./fuzz 3000     # see what comparison tracing collected

The RNG seed is fixed, so a shorter run is a prefix of a longer one, and the numbers above come
out of the same binary. Windows Server 2019, clang 17.0.6, 4 vCPU.

The fuzzer catches faults in-process with structured exception handling now, but it still has no
fork-per-exec and no persistent mode, so it is not ready for real software. That is the next
thing, and it is in the README's future work alongside the limitation that matters more: this
implementation records what was compared but not where in the input it lives, which is what
AFL++'s Redqueen does and what separates an AFL++-class fuzzer from a libFuzzer-class one.