This is a follow-up to the nelli overview . There I said the fuzzer’s default mode “mutates the typed choice sequence directly instead of the bytes.” This is why that matters, and what nelli does with the structure once it stops throwing it away.

The setup

nelli turns any 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 is now a libFuzzer or AFL harness, with the same strategies, the same shrinking, and the same example database behind it.

Why byte mutation wastes its budget

A byte fuzzer flips bits in the raw buffer. But that buffer is a length-prefixed encoding of typed choices, not free-form bytes. Flip a bit in a length-prefix byte and it usually decodes into an out-of-range length: the strategy clamps it, or the decode hits an Overrun and stops. Either way the iteration produced nothing your code could run.

Point a byte-level mutator at a structured input and most of its budget goes to inputs that die at the decoder before your code is ever reached. The mutator is fine. The layer it’s aimed at is wrong.

Mutate the structure instead

The default mode, fmIR, mutates the typed choice sequence directly. Every mutant respects the constraints the strategy declared (an integer’s [min, max], a boolean’s probability, the alignment of a span), so every output is structurally valid by construction and lands as an input your code actually runs. Raw byte mutation (fmBytes) is still there for when you actually want libFuzzer-style input, but it isn’t the default.

All the IR 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 fuzz loop calls any mutator unconditionally. A no-op simply yields no new coverage, and the loop reaches for a different one next iteration.

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, which is exactly what a coverage fuzzer is hunting for.

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 keeps the sequence parseable, which 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. Because the boundary is structural, the strategy can still parse the result.
  • Delete. Drop a span’s nodes, producing a structurally smaller candidate. The strategy may reject it (a list that falls below its minimum length, say), and that rejection is discarded naturally by the loop.
  • Duplicate. Copy a span in right after itself, which grows a list or string by exactly one structural unit.

None of these can produce a sequence the strategy can’t decode, because they only ever cut and paste along the seams the strategy itself drew.

The magic-value problem, solved exactly

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), but 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 at all. 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 pretend to solve what it can’t trace.

For the branches a solver would be overkill on, this turns a magic-value barrier from a luck problem into a substitution. For the ones it can’t, symbolic execution is the next tool along, and its witnesses feed back into the same choice sequence as seeds.

Why this is the point

Byte-fuzzing a structured value spends most of its budget getting rejected at the decoder. IR mutation spends it on inputs your code runs, structural mutations respect the grammar the strategy already defines, and the comparison log defeats magic values exactly rather than by luck. Coverage (a {.cover.} pragma feeding an AFL-style bitmap) then steers the search through the same targeted machinery nelli uses for property targets. It’s the same choice sequence 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 .