Mutating structure, not bytes: nelli's IR-aware fuzzing

TL;DR

nelli’s fuzzer mutates the typed choice sequence, never the raw buffer. The first version of this post said the reason was that byte mutants get rejected at the decoder. I measured it, and that is wrong: byte mutants almost always decode. The problem is that most of them decode to the exact value the parent already had. On a list of bytes, 83% of byte-level mutations change nothing, 7% are rejected, and 10% produce a new input. For mutation of the choice sequence the split is 14%, 12%, and 74%. Run as a coverage-guided campaign against a small binary parser with the same budget, byte mutation reaches 2 edges and sequence mutation reaches 18.

This follows on from the nelli overview .

The setup

nelli turns a property into a fuzz target by pointing the DataSource at a byte buffer instead of at an RNG: fuzzOnce(strategy, property, bytes). The buffer decodes into a typed choice sequence, and the strategy builds your value from that sequence. The property you already wrote becomes a libFuzzer or AFL harness, with the same strategies, the same shrinking, and the same example database behind it.

That is the door in. What happens after the door is a separate question: given an input the fuzzer wants to vary, which representation does it vary?

nelli used to offer both. There was a byte-mutation loop alongside the structural one, selected by a setting. It was removed in August. The structural mutator is now the only kernel. A byte corpus from another fuzzer still gets in: importCorpusDirAsIR decodes each file through the strategy and admits the resulting choice sequences as seeds. It just no longer drives its own loop with its own, weaker admission path.

One gap in the byte door as it stands today: integer draws read from the buffer, but float draws do not. A strategy that draws floats, fuzzed through fuzzOnce, sees one float value regardless of the bytes. That is a bug, and a byte corpus imported from another fuzzer loses its float values the same way. It does not affect the structural loop described below, which replays floats from the sequence.

What I expected, and what the measurement said

The folklore about fuzzing structured input goes like this. The buffer is an encoding with lengths and tags in it, a flipped bit lands in a length field, the decoder rejects the result, and the iteration is wasted. That is true of a grammar with a strict parser. I assumed it was true of nelli’s byte mode and wrote the first version of this post on that assumption.

The measurement: take 60 generated parents per strategy, apply one mutation at a time, and count how many mutants the strategy rejects. The byte arm uses nelli’s own former byte mutators (bit flip and byte replace, copied from the commit before they were deleted) and is seeded with the exact byte encoding of the same parents the other arm gets. 24,000 mutations per arm.

Byte mutation is rejected less often, on every shape. The reason is how the decoder is built. An integer draw in byte mode reads 8 bytes and maps them onto the constraint with raw mod (span + 1). Every byte value is in range by construction. The only way to fail is to run out of buffer. There is no strict parser for a flipped bit to offend.

So the decoder does not throw byte mutants away. Something else does.

Dead bytes

Split the mutants that decode into two groups: the ones that produce a different value from the parent, and the ones that produce the same value again.

lists(integers(0,255), 0, 64):

Four out of five byte mutations decode without complaint and hand the property the input it just ran.

The cause is in the same line of the decoder. Each integer draw consumes 8 big-endian bytes and reduces them modulo the range. When the range is 256, the result depends on the last byte only. The other seven can hold anything. A mutator choosing a byte at random hits a live one an eighth of the time.

That model predicts the inert rate for other ranges, and the measurement follows it:

The model is rough. It counts only the integer bytes. Between the integers sit the one-byte boolean “another element?” draws, which are thresholded, so a flipped bit there often leaves the decision unchanged. That is part of why the last row is not zero.

The waste is worst when the range is a power of two. Bytes and machine words are the ranges a fuzz target mostly draws from.

A smarter byte encoding would fix this particular leak, by spending one byte on a 0..255 draw. It would not fix the general problem, which is that the byte layer does not know where one choice ends and the next begins, or what range each one has. The choice sequence does.

Mutate the structure instead

The fuzz loop mutates the typed choice sequence directly. Each node carries its own constraint (an integer’s [min, max], a boolean’s probability), so a value mutator cannot produce an out-of-range value, and every change to a node is a change to the value it decodes to.

All the mutators share one contract: they are total. If the precondition can’t be met (perturb an integer in a sequence with no integer node, splice with no matching span), the mutator returns its input unchanged. So the loop calls any mutator unconditionally. A no-op yields no new coverage, and the loop reaches for a different operator next iteration. Those no-ops land in the inert column above.

Value mutators

Two mutators change values in place:

• Perturb an integer. Pick a random integer node and step it by a constraint-respecting delta. The step set is log-scaled by the constraint width (the same ±2^k distribution the targeted property-testing hill-climb uses), so one draw covers both fine and coarse moves. The result is clamped into [min, max]. If the constraint pins it, the mutator tries the other direction once and then no-ops.
• Snap to a boundary. Replace a node with a kind-respecting boundary value: min / max / shrinkTowards for an integer, the negation for a boolean, ±1 or 0 for a float, empty for a bytes or string node where the minimum size allows it. Boundary values are the inputs most likely to flip a branch.

Structural mutators, along spans

Spans are the strategy’s own structural boundaries: the startSpan / endSpan pairs it emits as it draws a list element, a record, an alternative. Mutating along those boundaries is how you get structural fuzzing without a grammar file.

• Splice. Crossover: replace a span in the current input with a span from a donor input that carries the same label.
• Delete. Drop a span’s nodes, producing a structurally smaller candidate.
• Duplicate. Copy a span in right after itself, which grows a list or string by one structural unit.

These are where the sequence arm’s rejections come from. Delete can take a list below its minimum length. Any of the three can build a value that a filter then refuses, which is why the sorted-list row in the first table is the highest at 35%. The loop discards a rejected mutant and moves on. A rejection costs one iteration and tells the fuzzer nothing, so it is waste, but it is a much smaller share of the budget than the inert mutants were on the byte side.

The payoff: coverage per iteration

Rejection and inert rates are proxies. The number that matters is how much of the code under test each layer reaches on the same budget.

The target is a small TLV message parser with a {.cover.} pragma on it: a magic first byte, a version switch, a declared record count that has to agree with the payload, and per-record tags. Both arms run the same loop (pick a parent from the corpus, apply one mutation, run it, keep the mutant if it hit a new edge) from the same 8 seed inputs. Only the mutation layer differs. The comparison log described in the next section is switched off for this run, so the sequence arm gets no help with the magic byte. Mean of 5 trials:

Final edge counts per trial were 2, 2, 2, 2, 5 for byte and 19, 18, 18, 18, 18 for sequence. In four of five trials the byte arm never got past the magic-byte check, so its corpus never grew and it spent 40,000 iterations on the same 8 parents.

What this does and does not show: the byte arm is nelli’s own former byte mode, which had two mutators. It is not AFL++ with a havoc stack and a dictionary. The claim is that inside nelli, over nelli’s encoding, the structural layer is the one worth keeping, which is why the other one is gone.

The magic-value problem

The classic wall for a coverage fuzzer is a comparison against a constant:

if input == 0xDEADBEEF:
  # the branch nothing random ever reaches

A byte fuzzer brute-forces it. A RedQueen-style tool logs the comparison and then guesses which byte offsets in the input to patch. nelli logs the comparison operands too (a {.covercmp.} pragma), and it has something a byte-level tool doesn’t: it knows which draw produced which concrete value. So “find this operand in the input and replace it with the other side of the comparison” is an exact operation for the identity-flow case: the compared value is a drawn value, mapped straight back to its choice node, with no byte-offset guessing. When a draw flows through a transform before the comparison, the lookup finds no match and falls through to a dictionary and then to identity. nelli doesn’t claim to solve what it cannot trace.

For the branches that substitution can’t reach, symbolic execution is the next tool along, and its witnesses feed back into the same choice sequence as seeds.

Where it fits

Coverage (the {.cover.} pragma feeding an AFL-style bitmap) steers this search through the same targeted machinery nelli uses for property targets. The sequence being mutated is the same one the property engine and the symbolic executor read from, so a fuzzer-found crash shrinks like any other counterexample.

Code and issues: github.com/coreyleavitt/nelli . The companion piece is how nelli reasons about integers soundly .

Corrected 2026-09-17. The first version of this post said byte mutants are mostly rejected at the decoder, and that byte mutation was still available as a non-default mode. Both were wrong. The byte loop had already been removed, and the measurements above replaced the rejection argument.