Coverage-guided fuzzing in Go and its probability model
Random testing would need about four billion attempts to pass a four-byte magic number. Go's coverage-guided fuzzer found a defect behind one in about a second. The difference arises because coverage guidance replaces a product of probabilities with a sum, as a simulation shows.
Fuzzing tests a program with millions of generated inputs and monitors it for crashes, hangs and incorrect results. It is one of the most effective testing techniques available.
Since Go 1.18 it is part of the standard toolchain: write a function that starts with Fuzz, run go test -fuzz, and the toolchain mutates inputs, tracks code coverage and keeps the inputs that reach new code. This article introduces a defect into a small parser, explains why ordinary tests missed it, and then examines why the fuzzer found it in about a second when random testing would need about eighteen hours.
The relevant literature is as follows.
Miller, Fredriksen and So (1990) founded the field by supplying random input to UNIX utilities, a large share of which crashed.
Böhme, Pham and Roychoudhury (2016) modelled coverage-based greybox fuzzing as a Markov chain, explaining why keeping inputs that reach new code makes an otherwise infeasible search feasible.
Böhme, Manès and Cha (2020) took an information-theoretic view, using the entropy of discovered behaviour to steer fuzzing effort.
The Go documentation describes native fuzzing and its corpus format, and the Go specification defines slice expressions, including the detail that makes the bug below silent.
Example: a parser defect
Consider a deliberately small parser for a binary record: a four-byte magic value JQ01, a length byte , then bytes of payload.
package fz
import "errors"
// ParseRecord reads a tiny binary record: a 4-byte magic "JQ01",
// a 1-byte length n, then n payload bytes. It returns the payload.
func ParseRecord(b []byte) ([]byte, error) {
if len(b) < 5 {
return nil, errors.New("short record")
}
if b[0] != 'J' || b[1] != 'Q' || b[2] != '0' || b[3] != '1' {
return nil, errors.New("bad magic")
}
n := int(b[4])
// Bug: the bound check is off by one; it should be len(b) < 5+n.
if len(b) < 4+n {
return nil, errors.New("truncated payload")
}
return b[5 : 5+n], nil
}
The bounds check is off by one. A record whose payload is one byte short passes the check, and the function returns a slice that runs one byte past the end of the input.
Why the defect does not cause a crash
An out-of-range slice might be expected to cause a panic. It does not always do so. In Go, the upper bound of a slice expression on a slice may go up to the slice's capacity, not just its length. If the input b is itself a view into a larger buffer, as it often is when data is read from a network or file, b[5:5+n] silently returns bytes that belong to whatever comes next in that buffer:
buf := make([]byte, 8)
copy(buf, "JQ01\x01X!!")
b := buf[:5] // the record is 5 bytes; capacity is 8
fmt.Printf("%q\n", b[5:6]) // prints "X": a byte from outside the record
The defect is therefore an information leak rather than a crash, which is more serious because nothing appears in the logs. My first fuzz test only checked that the payload length matched the header, and ran almost four million inputs without reporting a failure, because the slice had the right length; it just contained the wrong bytes.
Property-based testing
The improved test states a property that must always hold. A payload can never extend past the end of the input it was parsed from:
func FuzzParseRecord(f *testing.F) {
f.Add([]byte("hello"))
f.Fuzz(func(t *testing.T, b []byte) {
p, err := ParseRecord(b)
if err == nil && 5+len(p) > len(b) {
t.Fatalf("payload of %d bytes runs past the end of a %d-byte input", len(p), len(b))
}
})
}
The only seed is the string hello, which does not even start with the magic value. In five runs with an empty cache (go clean -fuzzcache, Go 1.24 on a two-core cloud machine), the fuzzer found a failing input in between about 0.7 and 1.3 seconds, and wrote it to testdata/fuzz/FuzzParseRecord/ so that it is replayed by every later go test:
go test fuzz v1
[]byte("JQ01\x01")
A five-byte record announcing one byte of payload and carrying none. After correcting the check to len(b) < 5+n, a 20-second fuzzing run found nothing.
Expected number of executions
Consider blind random testing first. To get past the magic check, an input must start with four specific bytes. For uniformly random bytes the probability is
At the roughly 65,000 executions per second the fuzzer achieved on this machine, the expected waiting time is about seconds, around 18 hours, and that is before the length byte has to be right as well.
Coverage guidance changes the problem. The check b[0] != 'J' || b[1] != 'Q' || ... is evaluated byte by byte, and each comparison is a separate branch. When a mutation happens to get the first byte right, execution reaches new code, the fuzzer notices the new coverage and keeps that input as a starting point for further mutations. The second byte is then searched from there, and so on. Instead of needing all four bytes at once, with probability , the fuzzer needs each byte in turn, with probability about per step. The expected cost goes from roughly attempts to roughly times the number of byte positions a mutation might touch: from a product to a sum. This is the central idea of coverage-guided fuzzing.
A four-digit bicycle lock shows the difference. Guessing whole combinations takes up to 10,000 attempts. A poorly made lock that gives a faint click when each wheel reaches its correct digit can be opened in at most 40, because each wheel is solved on its own. A comparison evaluated byte by byte is such a lock, and coverage feedback is the click.
Interpreting a run without failures
A fuzzing campaign that finds nothing is evidence, not proof. If executions produce no failure, the rule of three from statistical sampling in control testing bounds the failure probability by about , but only for inputs drawn the way the fuzzer draws them, which is not how attackers or real data draw them. A long run without failures shows that the parser withstands the fuzzer's input distribution; the properties checked define what withstanding means. Choosing those properties well, and seeding the corpus with realistic inputs, matters more than running longer.
The figure below compares the two strategies. Blind random testing needs about tries to match an -byte magic value, while a coverage-guided fuzzer needs roughly times (input length × 256), because it solves one byte at a time.
The race is simulated with those probabilities: each guided mutation changes one random byte of the input to a random value, and an input that gets the next byte right is kept.
Suggested settings:
- Four-byte magic value. With 4 bytes at 65,000 executions per second, the guided fuzzer finishes in a few thousand executions, a fraction of a second. Blind random testing is expected to need about 18 hours. Its bar is drawn to scale, which is why it barely moves.
- Eight bytes. Go to 8 bytes. The guided fuzzer needs a few times longer, around 18,000 executions on average instead of around 5,000, still well under a second. Blind testing now needs about nine million years.
- Faster execution. Raise the rate to a million executions per second. Blind testing at 8 bytes still needs over half a million years. Faster hardware reduces the time proportionally, while the number of attempts grows exponentially.
- Repeated runs. Each guided race takes a different number of executions, because each byte's waiting time is random (geometric). The total varies by a factor of two or three, never by a factor of a billion.
Derivation. Blind testing succeeds on one attempt with probability , so the number of attempts is geometric with mean . In the guided search, suppose the first bytes are already right. A mutation picks the right position with probability (for an input of bytes) and the right value with probability , so the waiting time for byte is geometric with mean . By linearity of expectation, the total is
a sum, against the product . For and that is about 5,000 executions instead of about 4.3 billion.
Coverage guidance turns a search whose cost is multiplicative into one whose cost is additive. This is why a fuzzer finds in seconds what random testing would not find in practice. Recommendations:
- Keep fuzz targets next to the unit tests. Every failing input is saved under
testdata/fuzzand becomes a permanent regression test. - Test properties ("the payload never runs past the input") rather than examples. The first, example-based fuzz test in this article ran four million inputs without detecting the defect.
- Run short sessions (
-fuzztime=60s) in CI for changed packages and longer ones on a schedule. - Fuzz everything that parses untrusted input. That is where a silent out-of-bounds read becomes a security incident.
References
- B. P. Miller, L. Fredriksen and B. So, "An empirical study of the reliability of UNIX utilities", Communications of the ACM, 33(12), 32-44, 1990.
- M. Böhme, V.-T. Pham and A. Roychoudhury, "Coverage-based greybox fuzzing as Markov chain", Proceedings of the ACM Conference on Computer and Communications Security (CCS), 2016.
- M. Böhme, V. J. M. Manès and S. K. Cha, "Boosting fuzzer efficiency: an information theoretic perspective", Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE), 2020.
- The Go Authors, "Go Fuzzing", Go documentation: go.dev/doc/security/fuzz.
- The Go Programming Language Specification, section "Slice expressions".