Oracle Driven Fuzzing

Oracle-Driven Fuzzing

A fuzzer is two things: a generator and an oracle. Everyone builds the generator. The bugs that matter are lost in the oracle — because the default oracle is "the process did not die", and almost nothing that matters kills a process. Silent truncation, a wrong signature verdict, a permission that widened, an amount off by one unit, a cache that returns another tenant's entry: all of them exit zero.

So the discipline in one line: build the strongest oracle you can afford first, then point a generator at it. A weak oracle with a billion executions proves the target does not segfault. That is rarely the claim anyone needed.

Composes with the library:

• falsifiable-testing — oracle strength, negative controls, red-first; this skill applies them where inputs are generated instead of written
• invariant-hunting — the invariant table is the property list to fuzz
• discriminating-proof — a fuzzer finding is a lead; that skill earns the verdict
• beyond-the-sink — where to point the next campaign when this one is dry
• deterministic-core — a fuzz reproducer must replay bit-for-bit (seed, version, corpus commit)
• honest-degradation — the "returned something plausible" failures this skill is built to catch

Authorization: fuzz targets you own or are authorized to test. Fuzzing a third-party production endpoint is a load test someone else did not consent to.

Part 1 — Choose the oracle before the generator

Ranked by strength. Take the strongest one the target admits, and say in the write-up which rung you used, because it bounds every claim the campaign can make.

Rungs 3–5 are the ones people skip, and they are where the interesting bugs live because they detect wrong, not merely dead.

Free oracles already in most codebases. Look for these before writing a single generator: an encoder next to a decoder; a serializer next to a parser; a cache next to the function it caches (cached(x) must equal uncached(x)); an optimized path next to a naive one; a rewrite next to the legacy code it replaces; two SDKs for the same wire protocol; the same validation implemented in the client and in the server. Every one of those pairs is a differential oracle nobody is running.

Metamorphic relations when there is no reference. State one property that must survive a transformation:

• reordering independent inputs must not change the result
• a permission-narrowing edit must never widen the effective grant
• adding an ignored field must not change the parse
• sum(chunks) must equal whole
• normalizing twice must equal normalizing once (idempotence)
• re-signing must not alter the signed bytes

Each is a fuzzable assertion that needs no ground truth.

Part 2 — The generator must be structure-aware, or it never gets past the front door

Random bytes against a target with a checksum, a magic header, a length prefix, or a schema spend the entire budget being rejected in the first 20 lines of the parser. Coverage plateaus after minutes and the campaign is measuring the validity check, not the program.

Fixes, cheapest first:

1. Seed the corpus with real inputs. Test fixtures, captured traffic, files from the repo's testdata/, previous bug reproducers. This alone changes most campaigns.
2. Fuzz below the crust. Call the internal function after the checksum, or recompute the checksum inside the harness so mutation reaches the body.
3. Use a grammar or typed generator. hypothesis/proptest strategies, protobuf/ASN.1 structure-aware mutators, an AST generator that emits only well-formed programs.
4. Fuzz the state machine, not just the payload. Generate sequences of API calls — open → write → close → write, approve → revoke → resume — and assert the invariant after each step. Most protocol and lifecycle bugs are unreachable with any single-input fuzzer.

Deliberately reserve part of the budget for malformed input. Structure-aware generation makes everything valid; the parser's error paths then go untested. Split the campaign: well-formed inputs to find logic bugs, corrupted ones to find error-handling bugs.

Part 3 — Coverage is a diagnostic, never a goal

Coverage answers one question: is the search still moving? A plateau is a signal to change the harness, not a reason to run longer.

When coverage stalls, diagnose before extending:

• Are inputs dying at a validity gate? → Part 2.
• Is a hash, timestamp, RNG, or network call making the target non-deterministic? → stub it; a non-reproducible finding is not a finding.
• Is the interesting code behind a flag, a role, or a config the harness never sets? → parameterize the harness over configurations.
• Is the oracle at rung 0? → the search may be finding things and not noticing them. This is the most common silent failure of a campaign.

Never report coverage percentage as a security claim. "87% line coverage under fuzz" says nothing about the 13%, and nothing about whether the oracle could have seen a failure in the 87%.

Part 4 — From crash to finding

A reproducer is not a finding. Between them sit four obligations:

1. Minimize. Shrink automatically (built into property-based frameworks; afl-tmin/llvm-cxxfilt-style tooling for byte fuzzers), then by hand until every remaining byte is load-bearing. A 4-byte reproducer explains itself; a 40 KB one gets closed as noise.
2. Deduplicate by root cause, not by stack. One bug produces dozens of distinct stacks. Group by the first frame in your own code and by the invariant violated. Report "one bug, 43 reproducers", never 43 findings.
3. Classify severity honestly. Ask what an attacker controls and what they gain: uncontrolled length in a memory-unsafe language is different from a KeyError in a Python handler that returns 500. Most fuzz crashes are availability-at-most, and saying so preserves credibility for the ones that are not.
4. Pass it to discriminating-proof. The crash is a plausible hypothesis about impact. The verdict is earned by an experiment with a binary oracle and a negative control — not by the fuzzer's exit code.

Record every reproducer as a permanent regression test with its seed, target version, and corpus commit, so the fix is proven and the bug cannot silently return.

Part 5 — "The fuzzer found nothing"

That sentence has five possible meanings, and only the last one is the claim people hear:

1. The oracle could not see failures (rung 0 on a memory-safe target).
2. The generator never reached the code (validity gate, missing config).
3. The campaign was too short for the search to leave the seed neighborhood.
4. The harness crashed early / the target was non-deterministic and results were discarded.
5. The target resisted N executions of this generator under this oracle.

Rule out 1–4 before writing anything. Then state 5 with its bounds — executions, oracle rung, corpus origin, coverage reached, and what was not in scope. "No bugs found" is never the right sentence; the honest one names the search. When 5 holds and the budget is spent, hand off to forensic-persistence: the exhausted axis is terrain, and the next campaign should change the oracle, not merely add hours.

Deliverable

## Fuzz campaign — <target> <version>
Harness: <entry point, what is stubbed, configurations swept>
Oracle: rung <n> — <the exact assertion>
Generator: <structure-aware? grammar? sequence-level?>
Corpus: <origin, commit, size>  Budget: <executions / wall time>
Coverage: <start → plateau, and what the plateau was diagnosed as>

### Findings (deduplicated by root cause)
<id> — invariant violated — minimized input — epistemic level — impact claim

### Not covered
<code paths the harness cannot reach, and why>

Anti-patterns

• Building the generator first and bolting on an oracle that only checks for crashes.
• Reporting "no crashes in 10M executions" as evidence the target is safe.
• Filing one finding per unique stack trace.
• Fuzzing over a network with a non-deterministic backend and calling an unreproducible failure a bug.
• Treating a coverage number as a security metric.
• Shipping a reproducer that was never minimized, and losing the triage argument to its size.
• Deleting the seed and corpus commit, making the finding impossible to replay.
• Escalating a crash straight to "vulnerability" without an impact experiment.