# Grammar-Based Fuzzing

A [[coverage-guided-fuzzing|coverage-guided fuzzer]] that produces random bytes will spend most of its CPU watching the target reject malformed input at the lexer. For any target with a non-trivial input format — JSON, protobuf, ASN.1, an RPC frame, a tx encoding — the interesting code lives several stages past the bytes. Grammar-based fuzzing fixes this by generating inputs from a context-free grammar so they're structurally valid by construction, and mutating *within* the grammar (rule rewrites, subtree replacements) instead of at the byte level.

The grammar is typically expressed as a list of production rules. Nautilus, AFL++ in grammar mode, and CSmith all use variants of this idea. A small JSON example from [[gosentry-go-fuzzing-fork|gosentry]]'s docs:

```json
[
  ["Json", "\\{\"postOfficeBox\":{Number}\\}"],
  ["Number", "{Digit}"],
  ["Number", "{Digit}{Number}"],
  ["Digit", "0"], ["Digit", "1"], ...
]
```

Every input is valid JSON with the expected shape, freeing the fuzzer to mutate the *number* the wrapping syntax wraps.

## Where it pays

- Compilers, parsers, query engines — anything whose interesting bugs live past the front end
- Differential testing across multiple implementations of the same spec (see [[differential-fuzzing]]) — both implementations need valid input to disagree about
- Protocol conformance fuzzing — the bytes have to look like the protocol or the receiver disconnects

## Where it doesn't help

- Lexer / parser bugs themselves — random bytes are a better fuzzer for the front end
- Targets whose input is genuinely unstructured (image pixel data, raw audio)
- Cases where the grammar is the spec under test and writing it is half the work

## Combining strategies

Production fuzzing campaigns usually mix grammar-based generation with byte-level mutation: grammar for the new-corpus seeding pass and the "produce a valid base" step, then byte-level mutations to find tokenizer/parser edge cases. [[coverage-guided-fuzzing|Coverage feedback]] works across both because the instrumentation is in the target, not in the input generator.

## Relation to structure-aware fuzzing

[[structure-aware-fuzzing]] is the in-language equivalent: instead of a grammar, the fuzzer is told the *Go/Rust/C++ type* of the input and constructs an instance directly. Grammar-based fuzzing is the right tool when the input is *bytes on the wire* (a serialized protocol, source code); structure-aware is the right tool when the input is *a value the API takes* (a struct, a typed record). gosentry supports both.