summaryrefslogtreecommitdiffstats
path: root/src/internal/fuzz
diff options
context:
space:
mode:
Diffstat (limited to 'src/internal/fuzz')
-rw-r--r--src/internal/fuzz/counters_supported.go21
-rw-r--r--src/internal/fuzz/counters_unsupported.go24
-rw-r--r--src/internal/fuzz/coverage.go107
-rw-r--r--src/internal/fuzz/encoding.go361
-rw-r--r--src/internal/fuzz/encoding_test.go409
-rw-r--r--src/internal/fuzz/fuzz.go1083
-rw-r--r--src/internal/fuzz/mem.go138
-rw-r--r--src/internal/fuzz/minimize.go95
-rw-r--r--src/internal/fuzz/minimize_test.go182
-rw-r--r--src/internal/fuzz/mutator.go300
-rw-r--r--src/internal/fuzz/mutator_test.go117
-rw-r--r--src/internal/fuzz/mutators_byteslice.go313
-rw-r--r--src/internal/fuzz/mutators_byteslice_test.go186
-rw-r--r--src/internal/fuzz/pcg.go145
-rw-r--r--src/internal/fuzz/queue.go71
-rw-r--r--src/internal/fuzz/queue_test.go58
-rw-r--r--src/internal/fuzz/sys_posix.go130
-rw-r--r--src/internal/fuzz/sys_unimplemented.go44
-rw-r--r--src/internal/fuzz/sys_windows.go147
-rw-r--r--src/internal/fuzz/trace.go35
-rw-r--r--src/internal/fuzz/worker.go1184
-rw-r--r--src/internal/fuzz/worker_test.go206
22 files changed, 5356 insertions, 0 deletions
diff --git a/src/internal/fuzz/counters_supported.go b/src/internal/fuzz/counters_supported.go
new file mode 100644
index 0000000..79e27d2
--- /dev/null
+++ b/src/internal/fuzz/counters_supported.go
@@ -0,0 +1,21 @@
+// Copyright 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+//go:build (darwin || linux || windows || freebsd) && (amd64 || arm64)
+
+package fuzz
+
+import (
+ "unsafe"
+)
+
+// coverage returns a []byte containing unique 8-bit counters for each edge of
+// the instrumented source code. This coverage data will only be generated if
+// `-d=libfuzzer` is set at build time. This can be used to understand the code
+// coverage of a test execution.
+func coverage() []byte {
+ addr := unsafe.Pointer(&_counters)
+ size := uintptr(unsafe.Pointer(&_ecounters)) - uintptr(addr)
+ return unsafe.Slice((*byte)(addr), int(size))
+}
diff --git a/src/internal/fuzz/counters_unsupported.go b/src/internal/fuzz/counters_unsupported.go
new file mode 100644
index 0000000..028065c
--- /dev/null
+++ b/src/internal/fuzz/counters_unsupported.go
@@ -0,0 +1,24 @@
+// Copyright 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// TODO: expand the set of supported platforms, with testing. Nothing about
+// the instrumentation is OS specific, but only amd64 and arm64 are
+// supported in the runtime. See src/runtime/libfuzzer*.
+//
+// If you update this constraint, also update internal/platform.FuzzInstrumeted.
+//
+//go:build !((darwin || linux || windows || freebsd) && (amd64 || arm64))
+
+package fuzz
+
+// TODO(#48504): re-enable on platforms where instrumentation works.
+// In theory, we shouldn't need this file at all: if the binary was built
+// without coverage, then _counters and _ecounters should have the same address.
+// However, this caused an init failure on aix/ppc64, so it's disabled here.
+
+// coverage returns a []byte containing unique 8-bit counters for each edge of
+// the instrumented source code. This coverage data will only be generated if
+// `-d=libfuzzer` is set at build time. This can be used to understand the code
+// coverage of a test execution.
+func coverage() []byte { return nil }
diff --git a/src/internal/fuzz/coverage.go b/src/internal/fuzz/coverage.go
new file mode 100644
index 0000000..0c5e17e
--- /dev/null
+++ b/src/internal/fuzz/coverage.go
@@ -0,0 +1,107 @@
+// Copyright 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fuzz
+
+import (
+ "fmt"
+ "math/bits"
+)
+
+// ResetCoverage sets all of the counters for each edge of the instrumented
+// source code to 0.
+func ResetCoverage() {
+ cov := coverage()
+ for i := range cov {
+ cov[i] = 0
+ }
+}
+
+// SnapshotCoverage copies the current counter values into coverageSnapshot,
+// preserving them for later inspection. SnapshotCoverage also rounds each
+// counter down to the nearest power of two. This lets the coordinator store
+// multiple values for each counter by OR'ing them together.
+func SnapshotCoverage() {
+ cov := coverage()
+ for i, b := range cov {
+ b |= b >> 1
+ b |= b >> 2
+ b |= b >> 4
+ b -= b >> 1
+ coverageSnapshot[i] = b
+ }
+}
+
+// diffCoverage returns a set of bits set in snapshot but not in base.
+// If there are no new bits set, diffCoverage returns nil.
+func diffCoverage(base, snapshot []byte) []byte {
+ if len(base) != len(snapshot) {
+ panic(fmt.Sprintf("the number of coverage bits changed: before=%d, after=%d", len(base), len(snapshot)))
+ }
+ found := false
+ for i := range snapshot {
+ if snapshot[i]&^base[i] != 0 {
+ found = true
+ break
+ }
+ }
+ if !found {
+ return nil
+ }
+ diff := make([]byte, len(snapshot))
+ for i := range diff {
+ diff[i] = snapshot[i] &^ base[i]
+ }
+ return diff
+}
+
+// countNewCoverageBits returns the number of bits set in snapshot that are not
+// set in base.
+func countNewCoverageBits(base, snapshot []byte) int {
+ n := 0
+ for i := range snapshot {
+ n += bits.OnesCount8(snapshot[i] &^ base[i])
+ }
+ return n
+}
+
+// isCoverageSubset returns true if all the base coverage bits are set in
+// snapshot.
+func isCoverageSubset(base, snapshot []byte) bool {
+ for i, v := range base {
+ if v&snapshot[i] != v {
+ return false
+ }
+ }
+ return true
+}
+
+// hasCoverageBit returns true if snapshot has at least one bit set that is
+// also set in base.
+func hasCoverageBit(base, snapshot []byte) bool {
+ for i := range snapshot {
+ if snapshot[i]&base[i] != 0 {
+ return true
+ }
+ }
+ return false
+}
+
+func countBits(cov []byte) int {
+ n := 0
+ for _, c := range cov {
+ n += bits.OnesCount8(c)
+ }
+ return n
+}
+
+var (
+ coverageEnabled = len(coverage()) > 0
+ coverageSnapshot = make([]byte, len(coverage()))
+
+ // _counters and _ecounters mark the start and end, respectively, of where
+ // the 8-bit coverage counters reside in memory. They're known to cmd/link,
+ // which specially assigns their addresses for this purpose.
+ _counters, _ecounters [0]byte
+)
diff --git a/src/internal/fuzz/encoding.go b/src/internal/fuzz/encoding.go
new file mode 100644
index 0000000..270ef7a
--- /dev/null
+++ b/src/internal/fuzz/encoding.go
@@ -0,0 +1,361 @@
+// Copyright 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fuzz
+
+import (
+ "bytes"
+ "fmt"
+ "go/ast"
+ "go/parser"
+ "go/token"
+ "math"
+ "strconv"
+ "strings"
+ "unicode/utf8"
+)
+
+// encVersion1 will be the first line of a file with version 1 encoding.
+var encVersion1 = "go test fuzz v1"
+
+// marshalCorpusFile encodes an arbitrary number of arguments into the file format for the
+// corpus.
+func marshalCorpusFile(vals ...any) []byte {
+ if len(vals) == 0 {
+ panic("must have at least one value to marshal")
+ }
+ b := bytes.NewBuffer([]byte(encVersion1 + "\n"))
+ // TODO(katiehockman): keep uint8 and int32 encoding where applicable,
+ // instead of changing to byte and rune respectively.
+ for _, val := range vals {
+ switch t := val.(type) {
+ case int, int8, int16, int64, uint, uint16, uint32, uint64, bool:
+ fmt.Fprintf(b, "%T(%v)\n", t, t)
+ case float32:
+ if math.IsNaN(float64(t)) && math.Float32bits(t) != math.Float32bits(float32(math.NaN())) {
+ // We encode unusual NaNs as hex values, because that is how users are
+ // likely to encounter them in literature about floating-point encoding.
+ // This allows us to reproduce fuzz failures that depend on the specific
+ // NaN representation (for float32 there are about 2^24 possibilities!),
+ // not just the fact that the value is *a* NaN.
+ //
+ // Note that the specific value of float32(math.NaN()) can vary based on
+ // whether the architecture represents signaling NaNs using a low bit
+ // (as is common) or a high bit (as commonly implemented on MIPS
+ // hardware before around 2012). We believe that the increase in clarity
+ // from identifying "NaN" with math.NaN() is worth the slight ambiguity
+ // from a platform-dependent value.
+ fmt.Fprintf(b, "math.Float32frombits(0x%x)\n", math.Float32bits(t))
+ } else {
+ // We encode all other values — including the NaN value that is
+ // bitwise-identical to float32(math.Nan()) — using the default
+ // formatting, which is equivalent to strconv.FormatFloat with format
+ // 'g' and can be parsed by strconv.ParseFloat.
+ //
+ // For an ordinary floating-point number this format includes
+ // sufficiently many digits to reconstruct the exact value. For positive
+ // or negative infinity it is the string "+Inf" or "-Inf". For positive
+ // or negative zero it is "0" or "-0". For NaN, it is the string "NaN".
+ fmt.Fprintf(b, "%T(%v)\n", t, t)
+ }
+ case float64:
+ if math.IsNaN(t) && math.Float64bits(t) != math.Float64bits(math.NaN()) {
+ fmt.Fprintf(b, "math.Float64frombits(0x%x)\n", math.Float64bits(t))
+ } else {
+ fmt.Fprintf(b, "%T(%v)\n", t, t)
+ }
+ case string:
+ fmt.Fprintf(b, "string(%q)\n", t)
+ case rune: // int32
+ // Although rune and int32 are represented by the same type, only a subset
+ // of valid int32 values can be expressed as rune literals. Notably,
+ // negative numbers, surrogate halves, and values above unicode.MaxRune
+ // have no quoted representation.
+ //
+ // fmt with "%q" (and the corresponding functions in the strconv package)
+ // would quote out-of-range values to the Unicode replacement character
+ // instead of the original value (see https://go.dev/issue/51526), so
+ // they must be treated as int32 instead.
+ //
+ // We arbitrarily draw the line at UTF-8 validity, which biases toward the
+ // "rune" interpretation. (However, we accept either format as input.)
+ if utf8.ValidRune(t) {
+ fmt.Fprintf(b, "rune(%q)\n", t)
+ } else {
+ fmt.Fprintf(b, "int32(%v)\n", t)
+ }
+ case byte: // uint8
+ // For bytes, we arbitrarily prefer the character interpretation.
+ // (Every byte has a valid character encoding.)
+ fmt.Fprintf(b, "byte(%q)\n", t)
+ case []byte: // []uint8
+ fmt.Fprintf(b, "[]byte(%q)\n", t)
+ default:
+ panic(fmt.Sprintf("unsupported type: %T", t))
+ }
+ }
+ return b.Bytes()
+}
+
+// unmarshalCorpusFile decodes corpus bytes into their respective values.
+func unmarshalCorpusFile(b []byte) ([]any, error) {
+ if len(b) == 0 {
+ return nil, fmt.Errorf("cannot unmarshal empty string")
+ }
+ lines := bytes.Split(b, []byte("\n"))
+ if len(lines) < 2 {
+ return nil, fmt.Errorf("must include version and at least one value")
+ }
+ version := strings.TrimSuffix(string(lines[0]), "\r")
+ if version != encVersion1 {
+ return nil, fmt.Errorf("unknown encoding version: %s", version)
+ }
+ var vals []any
+ for _, line := range lines[1:] {
+ line = bytes.TrimSpace(line)
+ if len(line) == 0 {
+ continue
+ }
+ v, err := parseCorpusValue(line)
+ if err != nil {
+ return nil, fmt.Errorf("malformed line %q: %v", line, err)
+ }
+ vals = append(vals, v)
+ }
+ return vals, nil
+}
+
+func parseCorpusValue(line []byte) (any, error) {
+ fs := token.NewFileSet()
+ expr, err := parser.ParseExprFrom(fs, "(test)", line, 0)
+ if err != nil {
+ return nil, err
+ }
+ call, ok := expr.(*ast.CallExpr)
+ if !ok {
+ return nil, fmt.Errorf("expected call expression")
+ }
+ if len(call.Args) != 1 {
+ return nil, fmt.Errorf("expected call expression with 1 argument; got %d", len(call.Args))
+ }
+ arg := call.Args[0]
+
+ if arrayType, ok := call.Fun.(*ast.ArrayType); ok {
+ if arrayType.Len != nil {
+ return nil, fmt.Errorf("expected []byte or primitive type")
+ }
+ elt, ok := arrayType.Elt.(*ast.Ident)
+ if !ok || elt.Name != "byte" {
+ return nil, fmt.Errorf("expected []byte")
+ }
+ lit, ok := arg.(*ast.BasicLit)
+ if !ok || lit.Kind != token.STRING {
+ return nil, fmt.Errorf("string literal required for type []byte")
+ }
+ s, err := strconv.Unquote(lit.Value)
+ if err != nil {
+ return nil, err
+ }
+ return []byte(s), nil
+ }
+
+ var idType *ast.Ident
+ if selector, ok := call.Fun.(*ast.SelectorExpr); ok {
+ xIdent, ok := selector.X.(*ast.Ident)
+ if !ok || xIdent.Name != "math" {
+ return nil, fmt.Errorf("invalid selector type")
+ }
+ switch selector.Sel.Name {
+ case "Float64frombits":
+ idType = &ast.Ident{Name: "float64-bits"}
+ case "Float32frombits":
+ idType = &ast.Ident{Name: "float32-bits"}
+ default:
+ return nil, fmt.Errorf("invalid selector type")
+ }
+ } else {
+ idType, ok = call.Fun.(*ast.Ident)
+ if !ok {
+ return nil, fmt.Errorf("expected []byte or primitive type")
+ }
+ if idType.Name == "bool" {
+ id, ok := arg.(*ast.Ident)
+ if !ok {
+ return nil, fmt.Errorf("malformed bool")
+ }
+ if id.Name == "true" {
+ return true, nil
+ } else if id.Name == "false" {
+ return false, nil
+ } else {
+ return nil, fmt.Errorf("true or false required for type bool")
+ }
+ }
+ }
+
+ var (
+ val string
+ kind token.Token
+ )
+ if op, ok := arg.(*ast.UnaryExpr); ok {
+ switch lit := op.X.(type) {
+ case *ast.BasicLit:
+ if op.Op != token.SUB {
+ return nil, fmt.Errorf("unsupported operation on int/float: %v", op.Op)
+ }
+ // Special case for negative numbers.
+ val = op.Op.String() + lit.Value // e.g. "-" + "124"
+ kind = lit.Kind
+ case *ast.Ident:
+ if lit.Name != "Inf" {
+ return nil, fmt.Errorf("expected operation on int or float type")
+ }
+ if op.Op == token.SUB {
+ val = "-Inf"
+ } else {
+ val = "+Inf"
+ }
+ kind = token.FLOAT
+ default:
+ return nil, fmt.Errorf("expected operation on int or float type")
+ }
+ } else {
+ switch lit := arg.(type) {
+ case *ast.BasicLit:
+ val, kind = lit.Value, lit.Kind
+ case *ast.Ident:
+ if lit.Name != "NaN" {
+ return nil, fmt.Errorf("literal value required for primitive type")
+ }
+ val, kind = "NaN", token.FLOAT
+ default:
+ return nil, fmt.Errorf("literal value required for primitive type")
+ }
+ }
+
+ switch typ := idType.Name; typ {
+ case "string":
+ if kind != token.STRING {
+ return nil, fmt.Errorf("string literal value required for type string")
+ }
+ return strconv.Unquote(val)
+ case "byte", "rune":
+ if kind == token.INT {
+ switch typ {
+ case "rune":
+ return parseInt(val, typ)
+ case "byte":
+ return parseUint(val, typ)
+ }
+ }
+ if kind != token.CHAR {
+ return nil, fmt.Errorf("character literal required for byte/rune types")
+ }
+ n := len(val)
+ if n < 2 {
+ return nil, fmt.Errorf("malformed character literal, missing single quotes")
+ }
+ code, _, _, err := strconv.UnquoteChar(val[1:n-1], '\'')
+ if err != nil {
+ return nil, err
+ }
+ if typ == "rune" {
+ return code, nil
+ }
+ if code >= 256 {
+ return nil, fmt.Errorf("can only encode single byte to a byte type")
+ }
+ return byte(code), nil
+ case "int", "int8", "int16", "int32", "int64":
+ if kind != token.INT {
+ return nil, fmt.Errorf("integer literal required for int types")
+ }
+ return parseInt(val, typ)
+ case "uint", "uint8", "uint16", "uint32", "uint64":
+ if kind != token.INT {
+ return nil, fmt.Errorf("integer literal required for uint types")
+ }
+ return parseUint(val, typ)
+ case "float32":
+ if kind != token.FLOAT && kind != token.INT {
+ return nil, fmt.Errorf("float or integer literal required for float32 type")
+ }
+ v, err := strconv.ParseFloat(val, 32)
+ return float32(v), err
+ case "float64":
+ if kind != token.FLOAT && kind != token.INT {
+ return nil, fmt.Errorf("float or integer literal required for float64 type")
+ }
+ return strconv.ParseFloat(val, 64)
+ case "float32-bits":
+ if kind != token.INT {
+ return nil, fmt.Errorf("integer literal required for math.Float32frombits type")
+ }
+ bits, err := parseUint(val, "uint32")
+ if err != nil {
+ return nil, err
+ }
+ return math.Float32frombits(bits.(uint32)), nil
+ case "float64-bits":
+ if kind != token.FLOAT && kind != token.INT {
+ return nil, fmt.Errorf("integer literal required for math.Float64frombits type")
+ }
+ bits, err := parseUint(val, "uint64")
+ if err != nil {
+ return nil, err
+ }
+ return math.Float64frombits(bits.(uint64)), nil
+ default:
+ return nil, fmt.Errorf("expected []byte or primitive type")
+ }
+}
+
+// parseInt returns an integer of value val and type typ.
+func parseInt(val, typ string) (any, error) {
+ switch typ {
+ case "int":
+ // The int type may be either 32 or 64 bits. If 32, the fuzz tests in the
+ // corpus may include 64-bit values produced by fuzzing runs on 64-bit
+ // architectures. When running those tests, we implicitly wrap the values to
+ // fit in a regular int. (The test case is still “interesting”, even if the
+ // specific values of its inputs are platform-dependent.)
+ i, err := strconv.ParseInt(val, 0, 64)
+ return int(i), err
+ case "int8":
+ i, err := strconv.ParseInt(val, 0, 8)
+ return int8(i), err
+ case "int16":
+ i, err := strconv.ParseInt(val, 0, 16)
+ return int16(i), err
+ case "int32", "rune":
+ i, err := strconv.ParseInt(val, 0, 32)
+ return int32(i), err
+ case "int64":
+ return strconv.ParseInt(val, 0, 64)
+ default:
+ panic("unreachable")
+ }
+}
+
+// parseUint returns an unsigned integer of value val and type typ.
+func parseUint(val, typ string) (any, error) {
+ switch typ {
+ case "uint":
+ i, err := strconv.ParseUint(val, 0, 64)
+ return uint(i), err
+ case "uint8", "byte":
+ i, err := strconv.ParseUint(val, 0, 8)
+ return uint8(i), err
+ case "uint16":
+ i, err := strconv.ParseUint(val, 0, 16)
+ return uint16(i), err
+ case "uint32":
+ i, err := strconv.ParseUint(val, 0, 32)
+ return uint32(i), err
+ case "uint64":
+ return strconv.ParseUint(val, 0, 64)
+ default:
+ panic("unreachable")
+ }
+}
diff --git a/src/internal/fuzz/encoding_test.go b/src/internal/fuzz/encoding_test.go
new file mode 100644
index 0000000..6f6173d
--- /dev/null
+++ b/src/internal/fuzz/encoding_test.go
@@ -0,0 +1,409 @@
+// Copyright 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fuzz
+
+import (
+ "math"
+ "strconv"
+ "testing"
+ "unicode"
+)
+
+func TestUnmarshalMarshal(t *testing.T) {
+ var tests = []struct {
+ desc string
+ in string
+ reject bool
+ want string // if different from in
+ }{
+ {
+ desc: "missing version",
+ in: "int(1234)",
+ reject: true,
+ },
+ {
+ desc: "malformed string",
+ in: `go test fuzz v1
+string("a"bcad")`,
+ reject: true,
+ },
+ {
+ desc: "empty value",
+ in: `go test fuzz v1
+int()`,
+ reject: true,
+ },
+ {
+ desc: "negative uint",
+ in: `go test fuzz v1
+uint(-32)`,
+ reject: true,
+ },
+ {
+ desc: "int8 too large",
+ in: `go test fuzz v1
+int8(1234456)`,
+ reject: true,
+ },
+ {
+ desc: "multiplication in int value",
+ in: `go test fuzz v1
+int(20*5)`,
+ reject: true,
+ },
+ {
+ desc: "double negation",
+ in: `go test fuzz v1
+int(--5)`,
+ reject: true,
+ },
+ {
+ desc: "malformed bool",
+ in: `go test fuzz v1
+bool(0)`,
+ reject: true,
+ },
+ {
+ desc: "malformed byte",
+ in: `go test fuzz v1
+byte('aa)`,
+ reject: true,
+ },
+ {
+ desc: "byte out of range",
+ in: `go test fuzz v1
+byte('☃')`,
+ reject: true,
+ },
+ {
+ desc: "extra newline",
+ in: `go test fuzz v1
+string("has extra newline")
+`,
+ want: `go test fuzz v1
+string("has extra newline")`,
+ },
+ {
+ desc: "trailing spaces",
+ in: `go test fuzz v1
+string("extra")
+[]byte("spacing")
+ `,
+ want: `go test fuzz v1
+string("extra")
+[]byte("spacing")`,
+ },
+ {
+ desc: "float types",
+ in: `go test fuzz v1
+float64(0)
+float32(0)`,
+ },
+ {
+ desc: "various types",
+ in: `go test fuzz v1
+int(-23)
+int8(-2)
+int64(2342425)
+uint(1)
+uint16(234)
+uint32(352342)
+uint64(123)
+rune('œ')
+byte('K')
+byte('ÿ')
+[]byte("hello¿")
+[]byte("a")
+bool(true)
+string("hello\\xbd\\xb2=\\xbc ⌘")
+float64(-12.5)
+float32(2.5)`,
+ },
+ {
+ desc: "float edge cases",
+ // The two IEEE 754 bit patterns used for the math.Float{64,32}frombits
+ // encodings are non-math.NAN quiet-NaN values. Since they are not equal
+ // to math.NaN(), they should be re-encoded to their bit patterns. They
+ // are, respectively:
+ // * math.Float64bits(math.NaN())+1
+ // * math.Float32bits(float32(math.NaN()))+1
+ in: `go test fuzz v1
+float32(-0)
+float64(-0)
+float32(+Inf)
+float32(-Inf)
+float32(NaN)
+float64(+Inf)
+float64(-Inf)
+float64(NaN)
+math.Float64frombits(0x7ff8000000000002)
+math.Float32frombits(0x7fc00001)`,
+ },
+ {
+ desc: "int variations",
+ // Although we arbitrarily choose default integer bases (0 or 16), we may
+ // want to change those arbitrary choices in the future and should not
+ // break the parser. Verify that integers in the opposite bases still
+ // parse correctly.
+ in: `go test fuzz v1
+int(0x0)
+int32(0x41)
+int64(0xfffffffff)
+uint32(0xcafef00d)
+uint64(0xffffffffffffffff)
+uint8(0b0000000)
+byte(0x0)
+byte('\000')
+byte('\u0000')
+byte('\'')
+math.Float64frombits(9221120237041090562)
+math.Float32frombits(2143289345)`,
+ want: `go test fuzz v1
+int(0)
+rune('A')
+int64(68719476735)
+uint32(3405705229)
+uint64(18446744073709551615)
+byte('\x00')
+byte('\x00')
+byte('\x00')
+byte('\x00')
+byte('\'')
+math.Float64frombits(0x7ff8000000000002)
+math.Float32frombits(0x7fc00001)`,
+ },
+ {
+ desc: "rune validation",
+ in: `go test fuzz v1
+rune(0)
+rune(0x41)
+rune(-1)
+rune(0xfffd)
+rune(0xd800)
+rune(0x10ffff)
+rune(0x110000)
+`,
+ want: `go test fuzz v1
+rune('\x00')
+rune('A')
+int32(-1)
+rune('�')
+int32(55296)
+rune('\U0010ffff')
+int32(1114112)`,
+ },
+ {
+ desc: "int overflow",
+ in: `go test fuzz v1
+int(0x7fffffffffffffff)
+uint(0xffffffffffffffff)`,
+ want: func() string {
+ switch strconv.IntSize {
+ case 32:
+ return `go test fuzz v1
+int(-1)
+uint(4294967295)`
+ case 64:
+ return `go test fuzz v1
+int(9223372036854775807)
+uint(18446744073709551615)`
+ default:
+ panic("unreachable")
+ }
+ }(),
+ },
+ {
+ desc: "windows new line",
+ in: "go test fuzz v1\r\nint(0)\r\n",
+ want: "go test fuzz v1\nint(0)",
+ },
+ }
+ for _, test := range tests {
+ t.Run(test.desc, func(t *testing.T) {
+ vals, err := unmarshalCorpusFile([]byte(test.in))
+ if test.reject {
+ if err == nil {
+ t.Fatalf("unmarshal unexpected success")
+ }
+ return
+ }
+ if err != nil {
+ t.Fatalf("unmarshal unexpected error: %v", err)
+ }
+ newB := marshalCorpusFile(vals...)
+ if err != nil {
+ t.Fatalf("marshal unexpected error: %v", err)
+ }
+ if newB[len(newB)-1] != '\n' {
+ t.Error("didn't write final newline to corpus file")
+ }
+
+ want := test.want
+ if want == "" {
+ want = test.in
+ }
+ want += "\n"
+ got := string(newB)
+ if got != want {
+ t.Errorf("unexpected marshaled value\ngot:\n%s\nwant:\n%s", got, want)
+ }
+ })
+ }
+}
+
+// BenchmarkMarshalCorpusFile measures the time it takes to serialize byte
+// slices of various sizes to a corpus file. The slice contains a repeating
+// sequence of bytes 0-255 to mix escaped and non-escaped characters.
+func BenchmarkMarshalCorpusFile(b *testing.B) {
+ buf := make([]byte, 1024*1024)
+ for i := 0; i < len(buf); i++ {
+ buf[i] = byte(i)
+ }
+
+ for sz := 1; sz <= len(buf); sz <<= 1 {
+ sz := sz
+ b.Run(strconv.Itoa(sz), func(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ b.SetBytes(int64(sz))
+ marshalCorpusFile(buf[:sz])
+ }
+ })
+ }
+}
+
+// BenchmarkUnmarshalCorpusfile measures the time it takes to deserialize
+// files encoding byte slices of various sizes. The slice contains a repeating
+// sequence of bytes 0-255 to mix escaped and non-escaped characters.
+func BenchmarkUnmarshalCorpusFile(b *testing.B) {
+ buf := make([]byte, 1024*1024)
+ for i := 0; i < len(buf); i++ {
+ buf[i] = byte(i)
+ }
+
+ for sz := 1; sz <= len(buf); sz <<= 1 {
+ sz := sz
+ data := marshalCorpusFile(buf[:sz])
+ b.Run(strconv.Itoa(sz), func(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ b.SetBytes(int64(sz))
+ unmarshalCorpusFile(data)
+ }
+ })
+ }
+}
+
+func TestByteRoundTrip(t *testing.T) {
+ for x := 0; x < 256; x++ {
+ b1 := byte(x)
+ buf := marshalCorpusFile(b1)
+ vs, err := unmarshalCorpusFile(buf)
+ if err != nil {
+ t.Fatal(err)
+ }
+ b2 := vs[0].(byte)
+ if b2 != b1 {
+ t.Fatalf("unmarshaled %v, want %v:\n%s", b2, b1, buf)
+ }
+ }
+}
+
+func TestInt8RoundTrip(t *testing.T) {
+ for x := -128; x < 128; x++ {
+ i1 := int8(x)
+ buf := marshalCorpusFile(i1)
+ vs, err := unmarshalCorpusFile(buf)
+ if err != nil {
+ t.Fatal(err)
+ }
+ i2 := vs[0].(int8)
+ if i2 != i1 {
+ t.Fatalf("unmarshaled %v, want %v:\n%s", i2, i1, buf)
+ }
+ }
+}
+
+func FuzzFloat64RoundTrip(f *testing.F) {
+ f.Add(math.Float64bits(0))
+ f.Add(math.Float64bits(math.Copysign(0, -1)))
+ f.Add(math.Float64bits(math.MaxFloat64))
+ f.Add(math.Float64bits(math.SmallestNonzeroFloat64))
+ f.Add(math.Float64bits(math.NaN()))
+ f.Add(uint64(0x7FF0000000000001)) // signaling NaN
+ f.Add(math.Float64bits(math.Inf(1)))
+ f.Add(math.Float64bits(math.Inf(-1)))
+
+ f.Fuzz(func(t *testing.T, u1 uint64) {
+ x1 := math.Float64frombits(u1)
+
+ b := marshalCorpusFile(x1)
+ t.Logf("marshaled math.Float64frombits(0x%x):\n%s", u1, b)
+
+ xs, err := unmarshalCorpusFile(b)
+ if err != nil {
+ t.Fatal(err)
+ }
+ if len(xs) != 1 {
+ t.Fatalf("unmarshaled %d values", len(xs))
+ }
+ x2 := xs[0].(float64)
+ u2 := math.Float64bits(x2)
+ if u2 != u1 {
+ t.Errorf("unmarshaled %v (bits 0x%x)", x2, u2)
+ }
+ })
+}
+
+func FuzzRuneRoundTrip(f *testing.F) {
+ f.Add(rune(-1))
+ f.Add(rune(0xd800))
+ f.Add(rune(0xdfff))
+ f.Add(rune(unicode.ReplacementChar))
+ f.Add(rune(unicode.MaxASCII))
+ f.Add(rune(unicode.MaxLatin1))
+ f.Add(rune(unicode.MaxRune))
+ f.Add(rune(unicode.MaxRune + 1))
+ f.Add(rune(-0x80000000))
+ f.Add(rune(0x7fffffff))
+
+ f.Fuzz(func(t *testing.T, r1 rune) {
+ b := marshalCorpusFile(r1)
+ t.Logf("marshaled rune(0x%x):\n%s", r1, b)
+
+ rs, err := unmarshalCorpusFile(b)
+ if err != nil {
+ t.Fatal(err)
+ }
+ if len(rs) != 1 {
+ t.Fatalf("unmarshaled %d values", len(rs))
+ }
+ r2 := rs[0].(rune)
+ if r2 != r1 {
+ t.Errorf("unmarshaled rune(0x%x)", r2)
+ }
+ })
+}
+
+func FuzzStringRoundTrip(f *testing.F) {
+ f.Add("")
+ f.Add("\x00")
+ f.Add(string([]rune{unicode.ReplacementChar}))
+
+ f.Fuzz(func(t *testing.T, s1 string) {
+ b := marshalCorpusFile(s1)
+ t.Logf("marshaled %q:\n%s", s1, b)
+
+ rs, err := unmarshalCorpusFile(b)
+ if err != nil {
+ t.Fatal(err)
+ }
+ if len(rs) != 1 {
+ t.Fatalf("unmarshaled %d values", len(rs))
+ }
+ s2 := rs[0].(string)
+ if s2 != s1 {
+ t.Errorf("unmarshaled %q", s2)
+ }
+ })
+}
diff --git a/src/internal/fuzz/fuzz.go b/src/internal/fuzz/fuzz.go
new file mode 100644
index 0000000..7d4fe06
--- /dev/null
+++ b/src/internal/fuzz/fuzz.go
@@ -0,0 +1,1083 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package fuzz provides common fuzzing functionality for tests built with
+// "go test" and for programs that use fuzzing functionality in the testing
+// package.
+package fuzz
+
+import (
+ "bytes"
+ "context"
+ "crypto/sha256"
+ "errors"
+ "fmt"
+ "internal/godebug"
+ "io"
+ "math/bits"
+ "os"
+ "path/filepath"
+ "reflect"
+ "runtime"
+ "strings"
+ "time"
+)
+
+// CoordinateFuzzingOpts is a set of arguments for CoordinateFuzzing.
+// The zero value is valid for each field unless specified otherwise.
+type CoordinateFuzzingOpts struct {
+ // Log is a writer for logging progress messages and warnings.
+ // If nil, io.Discard will be used instead.
+ Log io.Writer
+
+ // Timeout is the amount of wall clock time to spend fuzzing after the corpus
+ // has loaded. If zero, there will be no time limit.
+ Timeout time.Duration
+
+ // Limit is the number of random values to generate and test. If zero,
+ // there will be no limit on the number of generated values.
+ Limit int64
+
+ // MinimizeTimeout is the amount of wall clock time to spend minimizing
+ // after discovering a crasher. If zero, there will be no time limit. If
+ // MinimizeTimeout and MinimizeLimit are both zero, then minimization will
+ // be disabled.
+ MinimizeTimeout time.Duration
+
+ // MinimizeLimit is the maximum number of calls to the fuzz function to be
+ // made while minimizing after finding a crash. If zero, there will be no
+ // limit. Calls to the fuzz function made when minimizing also count toward
+ // Limit. If MinimizeTimeout and MinimizeLimit are both zero, then
+ // minimization will be disabled.
+ MinimizeLimit int64
+
+ // parallel is the number of worker processes to run in parallel. If zero,
+ // CoordinateFuzzing will run GOMAXPROCS workers.
+ Parallel int
+
+ // Seed is a list of seed values added by the fuzz target with testing.F.Add
+ // and in testdata.
+ Seed []CorpusEntry
+
+ // Types is the list of types which make up a corpus entry.
+ // Types must be set and must match values in Seed.
+ Types []reflect.Type
+
+ // CorpusDir is a directory where files containing values that crash the
+ // code being tested may be written. CorpusDir must be set.
+ CorpusDir string
+
+ // CacheDir is a directory containing additional "interesting" values.
+ // The fuzzer may derive new values from these, and may write new values here.
+ CacheDir string
+}
+
+// CoordinateFuzzing creates several worker processes and communicates with
+// them to test random inputs that could trigger crashes and expose bugs.
+// The worker processes run the same binary in the same directory with the
+// same environment variables as the coordinator process. Workers also run
+// with the same arguments as the coordinator, except with the -test.fuzzworker
+// flag prepended to the argument list.
+//
+// If a crash occurs, the function will return an error containing information
+// about the crash, which can be reported to the user.
+func CoordinateFuzzing(ctx context.Context, opts CoordinateFuzzingOpts) (err error) {
+ if err := ctx.Err(); err != nil {
+ return err
+ }
+ if opts.Log == nil {
+ opts.Log = io.Discard
+ }
+ if opts.Parallel == 0 {
+ opts.Parallel = runtime.GOMAXPROCS(0)
+ }
+ if opts.Limit > 0 && int64(opts.Parallel) > opts.Limit {
+ // Don't start more workers than we need.
+ opts.Parallel = int(opts.Limit)
+ }
+
+ c, err := newCoordinator(opts)
+ if err != nil {
+ return err
+ }
+
+ if opts.Timeout > 0 {
+ var cancel func()
+ ctx, cancel = context.WithTimeout(ctx, opts.Timeout)
+ defer cancel()
+ }
+
+ // fuzzCtx is used to stop workers, for example, after finding a crasher.
+ fuzzCtx, cancelWorkers := context.WithCancel(ctx)
+ defer cancelWorkers()
+ doneC := ctx.Done()
+
+ // stop is called when a worker encounters a fatal error.
+ var fuzzErr error
+ stopping := false
+ stop := func(err error) {
+ if err == fuzzCtx.Err() || isInterruptError(err) {
+ // Suppress cancellation errors and terminations due to SIGINT.
+ // The messages are not helpful since either the user triggered the error
+ // (with ^C) or another more helpful message will be printed (a crasher).
+ err = nil
+ }
+ if err != nil && (fuzzErr == nil || fuzzErr == ctx.Err()) {
+ fuzzErr = err
+ }
+ if stopping {
+ return
+ }
+ stopping = true
+ cancelWorkers()
+ doneC = nil
+ }
+
+ // Ensure that any crash we find is written to the corpus, even if an error
+ // or interruption occurs while minimizing it.
+ crashWritten := false
+ defer func() {
+ if c.crashMinimizing == nil || crashWritten {
+ return
+ }
+ werr := writeToCorpus(&c.crashMinimizing.entry, opts.CorpusDir)
+ if werr != nil {
+ err = fmt.Errorf("%w\n%v", err, werr)
+ return
+ }
+ if err == nil {
+ err = &crashError{
+ path: c.crashMinimizing.entry.Path,
+ err: errors.New(c.crashMinimizing.crasherMsg),
+ }
+ }
+ }()
+
+ // Start workers.
+ // TODO(jayconrod): do we want to support fuzzing different binaries?
+ dir := "" // same as self
+ binPath := os.Args[0]
+ args := append([]string{"-test.fuzzworker"}, os.Args[1:]...)
+ env := os.Environ() // same as self
+
+ errC := make(chan error)
+ workers := make([]*worker, opts.Parallel)
+ for i := range workers {
+ var err error
+ workers[i], err = newWorker(c, dir, binPath, args, env)
+ if err != nil {
+ return err
+ }
+ }
+ for i := range workers {
+ w := workers[i]
+ go func() {
+ err := w.coordinate(fuzzCtx)
+ if fuzzCtx.Err() != nil || isInterruptError(err) {
+ err = nil
+ }
+ cleanErr := w.cleanup()
+ if err == nil {
+ err = cleanErr
+ }
+ errC <- err
+ }()
+ }
+
+ // Main event loop.
+ // Do not return until all workers have terminated. We avoid a deadlock by
+ // receiving messages from workers even after ctx is cancelled.
+ activeWorkers := len(workers)
+ statTicker := time.NewTicker(3 * time.Second)
+ defer statTicker.Stop()
+ defer c.logStats()
+
+ c.logStats()
+ for {
+ var inputC chan fuzzInput
+ input, ok := c.peekInput()
+ if ok && c.crashMinimizing == nil && !stopping {
+ inputC = c.inputC
+ }
+
+ var minimizeC chan fuzzMinimizeInput
+ minimizeInput, ok := c.peekMinimizeInput()
+ if ok && !stopping {
+ minimizeC = c.minimizeC
+ }
+
+ select {
+ case <-doneC:
+ // Interrupted, cancelled, or timed out.
+ // stop sets doneC to nil so we don't busy wait here.
+ stop(ctx.Err())
+
+ case err := <-errC:
+ // A worker terminated, possibly after encountering a fatal error.
+ stop(err)
+ activeWorkers--
+ if activeWorkers == 0 {
+ return fuzzErr
+ }
+
+ case result := <-c.resultC:
+ // Received response from worker.
+ if stopping {
+ break
+ }
+ c.updateStats(result)
+
+ if result.crasherMsg != "" {
+ if c.warmupRun() && result.entry.IsSeed {
+ target := filepath.Base(c.opts.CorpusDir)
+ fmt.Fprintf(c.opts.Log, "failure while testing seed corpus entry: %s/%s\n", target, testName(result.entry.Parent))
+ stop(errors.New(result.crasherMsg))
+ break
+ }
+ if c.canMinimize() && result.canMinimize {
+ if c.crashMinimizing != nil {
+ // This crash is not minimized, and another crash is being minimized.
+ // Ignore this one and wait for the other one to finish.
+ break
+ }
+ // Found a crasher but haven't yet attempted to minimize it.
+ // Send it back to a worker for minimization. Disable inputC so
+ // other workers don't continue fuzzing.
+ c.crashMinimizing = &result
+ fmt.Fprintf(c.opts.Log, "fuzz: minimizing %d-byte failing input file\n", len(result.entry.Data))
+ c.queueForMinimization(result, nil)
+ } else if !crashWritten {
+ // Found a crasher that's either minimized or not minimizable.
+ // Write to corpus and stop.
+ err := writeToCorpus(&result.entry, opts.CorpusDir)
+ if err == nil {
+ crashWritten = true
+ err = &crashError{
+ path: result.entry.Path,
+ err: errors.New(result.crasherMsg),
+ }
+ }
+ if shouldPrintDebugInfo() {
+ fmt.Fprintf(
+ c.opts.Log,
+ "DEBUG new crasher, elapsed: %s, id: %s, parent: %s, gen: %d, size: %d, exec time: %s\n",
+ c.elapsed(),
+ result.entry.Path,
+ result.entry.Parent,
+ result.entry.Generation,
+ len(result.entry.Data),
+ result.entryDuration,
+ )
+ }
+ stop(err)
+ }
+ } else if result.coverageData != nil {
+ if c.warmupRun() {
+ if shouldPrintDebugInfo() {
+ fmt.Fprintf(
+ c.opts.Log,
+ "DEBUG processed an initial input, elapsed: %s, id: %s, new bits: %d, size: %d, exec time: %s\n",
+ c.elapsed(),
+ result.entry.Parent,
+ countBits(diffCoverage(c.coverageMask, result.coverageData)),
+ len(result.entry.Data),
+ result.entryDuration,
+ )
+ }
+ c.updateCoverage(result.coverageData)
+ c.warmupInputLeft--
+ if c.warmupInputLeft == 0 {
+ fmt.Fprintf(c.opts.Log, "fuzz: elapsed: %s, gathering baseline coverage: %d/%d completed, now fuzzing with %d workers\n", c.elapsed(), c.warmupInputCount, c.warmupInputCount, c.opts.Parallel)
+ if shouldPrintDebugInfo() {
+ fmt.Fprintf(
+ c.opts.Log,
+ "DEBUG finished processing input corpus, elapsed: %s, entries: %d, initial coverage bits: %d\n",
+ c.elapsed(),
+ len(c.corpus.entries),
+ countBits(c.coverageMask),
+ )
+ }
+ }
+ } else if keepCoverage := diffCoverage(c.coverageMask, result.coverageData); keepCoverage != nil {
+ // Found a value that expanded coverage.
+ // It's not a crasher, but we may want to add it to the on-disk
+ // corpus and prioritize it for future fuzzing.
+ // TODO(jayconrod, katiehockman): Prioritize fuzzing these
+ // values which expanded coverage, perhaps based on the
+ // number of new edges that this result expanded.
+ // TODO(jayconrod, katiehockman): Don't write a value that's already
+ // in the corpus.
+ if c.canMinimize() && result.canMinimize && c.crashMinimizing == nil {
+ // Send back to workers to find a smaller value that preserves
+ // at least one new coverage bit.
+ c.queueForMinimization(result, keepCoverage)
+ } else {
+ // Update the coordinator's coverage mask and save the value.
+ inputSize := len(result.entry.Data)
+ entryNew, err := c.addCorpusEntries(true, result.entry)
+ if err != nil {
+ stop(err)
+ break
+ }
+ if !entryNew {
+ continue
+ }
+ c.updateCoverage(keepCoverage)
+ c.inputQueue.enqueue(result.entry)
+ c.interestingCount++
+ if shouldPrintDebugInfo() {
+ fmt.Fprintf(
+ c.opts.Log,
+ "DEBUG new interesting input, elapsed: %s, id: %s, parent: %s, gen: %d, new bits: %d, total bits: %d, size: %d, exec time: %s\n",
+ c.elapsed(),
+ result.entry.Path,
+ result.entry.Parent,
+ result.entry.Generation,
+ countBits(keepCoverage),
+ countBits(c.coverageMask),
+ inputSize,
+ result.entryDuration,
+ )
+ }
+ }
+ } else {
+ if shouldPrintDebugInfo() {
+ fmt.Fprintf(
+ c.opts.Log,
+ "DEBUG worker reported interesting input that doesn't expand coverage, elapsed: %s, id: %s, parent: %s, canMinimize: %t\n",
+ c.elapsed(),
+ result.entry.Path,
+ result.entry.Parent,
+ result.canMinimize,
+ )
+ }
+ }
+ } else if c.warmupRun() {
+ // No error or coverage data was reported for this input during
+ // warmup, so continue processing results.
+ c.warmupInputLeft--
+ if c.warmupInputLeft == 0 {
+ fmt.Fprintf(c.opts.Log, "fuzz: elapsed: %s, testing seed corpus: %d/%d completed, now fuzzing with %d workers\n", c.elapsed(), c.warmupInputCount, c.warmupInputCount, c.opts.Parallel)
+ if shouldPrintDebugInfo() {
+ fmt.Fprintf(
+ c.opts.Log,
+ "DEBUG finished testing-only phase, elapsed: %s, entries: %d\n",
+ time.Since(c.startTime),
+ len(c.corpus.entries),
+ )
+ }
+ }
+ }
+
+ // Once the result has been processed, stop the worker if we
+ // have reached the fuzzing limit.
+ if c.opts.Limit > 0 && c.count >= c.opts.Limit {
+ stop(nil)
+ }
+
+ case inputC <- input:
+ // Sent the next input to a worker.
+ c.sentInput(input)
+
+ case minimizeC <- minimizeInput:
+ // Sent the next input for minimization to a worker.
+ c.sentMinimizeInput(minimizeInput)
+
+ case <-statTicker.C:
+ c.logStats()
+ }
+ }
+
+ // TODO(jayconrod,katiehockman): if a crasher can't be written to the corpus,
+ // write to the cache instead.
+}
+
+// crashError wraps a crasher written to the seed corpus. It saves the name
+// of the file where the input causing the crasher was saved. The testing
+// framework uses this to report a command to re-run that specific input.
+type crashError struct {
+ path string
+ err error
+}
+
+func (e *crashError) Error() string {
+ return e.err.Error()
+}
+
+func (e *crashError) Unwrap() error {
+ return e.err
+}
+
+func (e *crashError) CrashPath() string {
+ return e.path
+}
+
+type corpus struct {
+ entries []CorpusEntry
+ hashes map[[sha256.Size]byte]bool
+}
+
+// addCorpusEntries adds entries to the corpus, and optionally writes the entries
+// to the cache directory. If an entry is already in the corpus it is skipped. If
+// all of the entries are unique, addCorpusEntries returns true and a nil error,
+// if at least one of the entries was a duplicate, it returns false and a nil error.
+func (c *coordinator) addCorpusEntries(addToCache bool, entries ...CorpusEntry) (bool, error) {
+ noDupes := true
+ for _, e := range entries {
+ data, err := corpusEntryData(e)
+ if err != nil {
+ return false, err
+ }
+ h := sha256.Sum256(data)
+ if c.corpus.hashes[h] {
+ noDupes = false
+ continue
+ }
+ if addToCache {
+ if err := writeToCorpus(&e, c.opts.CacheDir); err != nil {
+ return false, err
+ }
+ // For entries written to disk, we don't hold onto the bytes,
+ // since the corpus would consume a significant amount of
+ // memory.
+ e.Data = nil
+ }
+ c.corpus.hashes[h] = true
+ c.corpus.entries = append(c.corpus.entries, e)
+ }
+ return noDupes, nil
+}
+
+// CorpusEntry represents an individual input for fuzzing.
+//
+// We must use an equivalent type in the testing and testing/internal/testdeps
+// packages, but testing can't import this package directly, and we don't want
+// to export this type from testing. Instead, we use the same struct type and
+// use a type alias (not a defined type) for convenience.
+type CorpusEntry = struct {
+ Parent string
+
+ // Path is the path of the corpus file, if the entry was loaded from disk.
+ // For other entries, including seed values provided by f.Add, Path is the
+ // name of the test, e.g. seed#0 or its hash.
+ Path string
+
+ // Data is the raw input data. Data should only be populated for seed
+ // values. For on-disk corpus files, Data will be nil, as it will be loaded
+ // from disk using Path.
+ Data []byte
+
+ // Values is the unmarshaled values from a corpus file.
+ Values []any
+
+ Generation int
+
+ // IsSeed indicates whether this entry is part of the seed corpus.
+ IsSeed bool
+}
+
+// corpusEntryData returns the raw input bytes, either from the data struct
+// field, or from disk.
+func corpusEntryData(ce CorpusEntry) ([]byte, error) {
+ if ce.Data != nil {
+ return ce.Data, nil
+ }
+
+ return os.ReadFile(ce.Path)
+}
+
+type fuzzInput struct {
+ // entry is the value to test initially. The worker will randomly mutate
+ // values from this starting point.
+ entry CorpusEntry
+
+ // timeout is the time to spend fuzzing variations of this input,
+ // not including starting or cleaning up.
+ timeout time.Duration
+
+ // limit is the maximum number of calls to the fuzz function the worker may
+ // make. The worker may make fewer calls, for example, if it finds an
+ // error early. If limit is zero, there is no limit on calls to the
+ // fuzz function.
+ limit int64
+
+ // warmup indicates whether this is a warmup input before fuzzing begins. If
+ // true, the input should not be fuzzed.
+ warmup bool
+
+ // coverageData reflects the coordinator's current coverageMask.
+ coverageData []byte
+}
+
+type fuzzResult struct {
+ // entry is an interesting value or a crasher.
+ entry CorpusEntry
+
+ // crasherMsg is an error message from a crash. It's "" if no crash was found.
+ crasherMsg string
+
+ // canMinimize is true if the worker should attempt to minimize this result.
+ // It may be false because an attempt has already been made.
+ canMinimize bool
+
+ // coverageData is set if the worker found new coverage.
+ coverageData []byte
+
+ // limit is the number of values the coordinator asked the worker
+ // to test. 0 if there was no limit.
+ limit int64
+
+ // count is the number of values the worker actually tested.
+ count int64
+
+ // totalDuration is the time the worker spent testing inputs.
+ totalDuration time.Duration
+
+ // entryDuration is the time the worker spent execution an interesting result
+ entryDuration time.Duration
+}
+
+type fuzzMinimizeInput struct {
+ // entry is an interesting value or crasher to minimize.
+ entry CorpusEntry
+
+ // crasherMsg is an error message from a crash. It's "" if no crash was found.
+ // If set, the worker will attempt to find a smaller input that also produces
+ // an error, though not necessarily the same error.
+ crasherMsg string
+
+ // limit is the maximum number of calls to the fuzz function the worker may
+ // make. The worker may make fewer calls, for example, if it can't reproduce
+ // an error. If limit is zero, there is no limit on calls to the fuzz function.
+ limit int64
+
+ // timeout is the time to spend minimizing this input.
+ // A zero timeout means no limit.
+ timeout time.Duration
+
+ // keepCoverage is a set of coverage bits that entry found that were not in
+ // the coordinator's combined set. When minimizing, the worker should find an
+ // input that preserves at least one of these bits. keepCoverage is nil for
+ // crashing inputs.
+ keepCoverage []byte
+}
+
+// coordinator holds channels that workers can use to communicate with
+// the coordinator.
+type coordinator struct {
+ opts CoordinateFuzzingOpts
+
+ // startTime is the time we started the workers after loading the corpus.
+ // Used for logging.
+ startTime time.Time
+
+ // inputC is sent values to fuzz by the coordinator. Any worker may receive
+ // values from this channel. Workers send results to resultC.
+ inputC chan fuzzInput
+
+ // minimizeC is sent values to minimize by the coordinator. Any worker may
+ // receive values from this channel. Workers send results to resultC.
+ minimizeC chan fuzzMinimizeInput
+
+ // resultC is sent results of fuzzing by workers. The coordinator
+ // receives these. Multiple types of messages are allowed.
+ resultC chan fuzzResult
+
+ // count is the number of values fuzzed so far.
+ count int64
+
+ // countLastLog is the number of values fuzzed when the output was last
+ // logged.
+ countLastLog int64
+
+ // timeLastLog is the time at which the output was last logged.
+ timeLastLog time.Time
+
+ // interestingCount is the number of unique interesting values which have
+ // been found this execution.
+ interestingCount int
+
+ // warmupInputCount is the count of all entries in the corpus which will
+ // need to be received from workers to run once during warmup, but not fuzz.
+ // This could be for coverage data, or only for the purposes of verifying
+ // that the seed corpus doesn't have any crashers. See warmupRun.
+ warmupInputCount int
+
+ // warmupInputLeft is the number of entries in the corpus which still need
+ // to be received from workers to run once during warmup, but not fuzz.
+ // See warmupInputLeft.
+ warmupInputLeft int
+
+ // duration is the time spent fuzzing inside workers, not counting time
+ // starting up or tearing down.
+ duration time.Duration
+
+ // countWaiting is the number of fuzzing executions the coordinator is
+ // waiting on workers to complete.
+ countWaiting int64
+
+ // corpus is a set of interesting values, including the seed corpus and
+ // generated values that workers reported as interesting.
+ corpus corpus
+
+ // minimizationAllowed is true if one or more of the types of fuzz
+ // function's parameters can be minimized.
+ minimizationAllowed bool
+
+ // inputQueue is a queue of inputs that workers should try fuzzing. This is
+ // initially populated from the seed corpus and cached inputs. More inputs
+ // may be added as new coverage is discovered.
+ inputQueue queue
+
+ // minimizeQueue is a queue of inputs that caused errors or exposed new
+ // coverage. Workers should attempt to find smaller inputs that do the
+ // same thing.
+ minimizeQueue queue
+
+ // crashMinimizing is the crash that is currently being minimized.
+ crashMinimizing *fuzzResult
+
+ // coverageMask aggregates coverage that was found for all inputs in the
+ // corpus. Each byte represents a single basic execution block. Each set bit
+ // within the byte indicates that an input has triggered that block at least
+ // 1 << n times, where n is the position of the bit in the byte. For example, a
+ // value of 12 indicates that separate inputs have triggered this block
+ // between 4-7 times and 8-15 times.
+ coverageMask []byte
+}
+
+func newCoordinator(opts CoordinateFuzzingOpts) (*coordinator, error) {
+ // Make sure all of the seed corpus has marshalled data.
+ for i := range opts.Seed {
+ if opts.Seed[i].Data == nil && opts.Seed[i].Values != nil {
+ opts.Seed[i].Data = marshalCorpusFile(opts.Seed[i].Values...)
+ }
+ }
+ c := &coordinator{
+ opts: opts,
+ startTime: time.Now(),
+ inputC: make(chan fuzzInput),
+ minimizeC: make(chan fuzzMinimizeInput),
+ resultC: make(chan fuzzResult),
+ timeLastLog: time.Now(),
+ corpus: corpus{hashes: make(map[[sha256.Size]byte]bool)},
+ }
+ if err := c.readCache(); err != nil {
+ return nil, err
+ }
+ if opts.MinimizeLimit > 0 || opts.MinimizeTimeout > 0 {
+ for _, t := range opts.Types {
+ if isMinimizable(t) {
+ c.minimizationAllowed = true
+ break
+ }
+ }
+ }
+
+ covSize := len(coverage())
+ if covSize == 0 {
+ fmt.Fprintf(c.opts.Log, "warning: the test binary was not built with coverage instrumentation, so fuzzing will run without coverage guidance and may be inefficient\n")
+ // Even though a coverage-only run won't occur, we should still run all
+ // of the seed corpus to make sure there are no existing failures before
+ // we start fuzzing.
+ c.warmupInputCount = len(c.opts.Seed)
+ for _, e := range c.opts.Seed {
+ c.inputQueue.enqueue(e)
+ }
+ } else {
+ c.warmupInputCount = len(c.corpus.entries)
+ for _, e := range c.corpus.entries {
+ c.inputQueue.enqueue(e)
+ }
+ // Set c.coverageMask to a clean []byte full of zeros.
+ c.coverageMask = make([]byte, covSize)
+ }
+ c.warmupInputLeft = c.warmupInputCount
+
+ if len(c.corpus.entries) == 0 {
+ fmt.Fprintf(c.opts.Log, "warning: starting with empty corpus\n")
+ var vals []any
+ for _, t := range opts.Types {
+ vals = append(vals, zeroValue(t))
+ }
+ data := marshalCorpusFile(vals...)
+ h := sha256.Sum256(data)
+ name := fmt.Sprintf("%x", h[:4])
+ c.addCorpusEntries(false, CorpusEntry{Path: name, Data: data})
+ }
+
+ return c, nil
+}
+
+func (c *coordinator) updateStats(result fuzzResult) {
+ c.count += result.count
+ c.countWaiting -= result.limit
+ c.duration += result.totalDuration
+}
+
+func (c *coordinator) logStats() {
+ now := time.Now()
+ if c.warmupRun() {
+ runSoFar := c.warmupInputCount - c.warmupInputLeft
+ if coverageEnabled {
+ fmt.Fprintf(c.opts.Log, "fuzz: elapsed: %s, gathering baseline coverage: %d/%d completed\n", c.elapsed(), runSoFar, c.warmupInputCount)
+ } else {
+ fmt.Fprintf(c.opts.Log, "fuzz: elapsed: %s, testing seed corpus: %d/%d completed\n", c.elapsed(), runSoFar, c.warmupInputCount)
+ }
+ } else if c.crashMinimizing != nil {
+ fmt.Fprintf(c.opts.Log, "fuzz: elapsed: %s, minimizing\n", c.elapsed())
+ } else {
+ rate := float64(c.count-c.countLastLog) / now.Sub(c.timeLastLog).Seconds()
+ if coverageEnabled {
+ total := c.warmupInputCount + c.interestingCount
+ fmt.Fprintf(c.opts.Log, "fuzz: elapsed: %s, execs: %d (%.0f/sec), new interesting: %d (total: %d)\n", c.elapsed(), c.count, rate, c.interestingCount, total)
+ } else {
+ fmt.Fprintf(c.opts.Log, "fuzz: elapsed: %s, execs: %d (%.0f/sec)\n", c.elapsed(), c.count, rate)
+ }
+ }
+ c.countLastLog = c.count
+ c.timeLastLog = now
+}
+
+// peekInput returns the next value that should be sent to workers.
+// If the number of executions is limited, the returned value includes
+// a limit for one worker. If there are no executions left, peekInput returns
+// a zero value and false.
+//
+// peekInput doesn't actually remove the input from the queue. The caller
+// must call sentInput after sending the input.
+//
+// If the input queue is empty and the coverage/testing-only run has completed,
+// queue refills it from the corpus.
+func (c *coordinator) peekInput() (fuzzInput, bool) {
+ if c.opts.Limit > 0 && c.count+c.countWaiting >= c.opts.Limit {
+ // Already making the maximum number of calls to the fuzz function.
+ // Don't send more inputs right now.
+ return fuzzInput{}, false
+ }
+ if c.inputQueue.len == 0 {
+ if c.warmupRun() {
+ // Wait for coverage/testing-only run to finish before sending more
+ // inputs.
+ return fuzzInput{}, false
+ }
+ c.refillInputQueue()
+ }
+
+ entry, ok := c.inputQueue.peek()
+ if !ok {
+ panic("input queue empty after refill")
+ }
+ input := fuzzInput{
+ entry: entry.(CorpusEntry),
+ timeout: workerFuzzDuration,
+ warmup: c.warmupRun(),
+ }
+ if c.coverageMask != nil {
+ input.coverageData = bytes.Clone(c.coverageMask)
+ }
+ if input.warmup {
+ // No fuzzing will occur, but it should count toward the limit set by
+ // -fuzztime.
+ input.limit = 1
+ return input, true
+ }
+
+ if c.opts.Limit > 0 {
+ input.limit = c.opts.Limit / int64(c.opts.Parallel)
+ if c.opts.Limit%int64(c.opts.Parallel) > 0 {
+ input.limit++
+ }
+ remaining := c.opts.Limit - c.count - c.countWaiting
+ if input.limit > remaining {
+ input.limit = remaining
+ }
+ }
+ return input, true
+}
+
+// sentInput updates internal counters after an input is sent to c.inputC.
+func (c *coordinator) sentInput(input fuzzInput) {
+ c.inputQueue.dequeue()
+ c.countWaiting += input.limit
+}
+
+// refillInputQueue refills the input queue from the corpus after it becomes
+// empty.
+func (c *coordinator) refillInputQueue() {
+ for _, e := range c.corpus.entries {
+ c.inputQueue.enqueue(e)
+ }
+}
+
+// queueForMinimization creates a fuzzMinimizeInput from result and adds it
+// to the minimization queue to be sent to workers.
+func (c *coordinator) queueForMinimization(result fuzzResult, keepCoverage []byte) {
+ if result.crasherMsg != "" {
+ c.minimizeQueue.clear()
+ }
+
+ input := fuzzMinimizeInput{
+ entry: result.entry,
+ crasherMsg: result.crasherMsg,
+ keepCoverage: keepCoverage,
+ }
+ c.minimizeQueue.enqueue(input)
+}
+
+// peekMinimizeInput returns the next input that should be sent to workers for
+// minimization.
+func (c *coordinator) peekMinimizeInput() (fuzzMinimizeInput, bool) {
+ if !c.canMinimize() {
+ // Already making the maximum number of calls to the fuzz function.
+ // Don't send more inputs right now.
+ return fuzzMinimizeInput{}, false
+ }
+ v, ok := c.minimizeQueue.peek()
+ if !ok {
+ return fuzzMinimizeInput{}, false
+ }
+ input := v.(fuzzMinimizeInput)
+
+ if c.opts.MinimizeTimeout > 0 {
+ input.timeout = c.opts.MinimizeTimeout
+ }
+ if c.opts.MinimizeLimit > 0 {
+ input.limit = c.opts.MinimizeLimit
+ } else if c.opts.Limit > 0 {
+ if input.crasherMsg != "" {
+ input.limit = c.opts.Limit
+ } else {
+ input.limit = c.opts.Limit / int64(c.opts.Parallel)
+ if c.opts.Limit%int64(c.opts.Parallel) > 0 {
+ input.limit++
+ }
+ }
+ }
+ if c.opts.Limit > 0 {
+ remaining := c.opts.Limit - c.count - c.countWaiting
+ if input.limit > remaining {
+ input.limit = remaining
+ }
+ }
+ return input, true
+}
+
+// sentMinimizeInput removes an input from the minimization queue after it's
+// sent to minimizeC.
+func (c *coordinator) sentMinimizeInput(input fuzzMinimizeInput) {
+ c.minimizeQueue.dequeue()
+ c.countWaiting += input.limit
+}
+
+// warmupRun returns true while the coordinator is running inputs without
+// mutating them as a warmup before fuzzing. This could be to gather baseline
+// coverage data for entries in the corpus, or to test all of the seed corpus
+// for errors before fuzzing begins.
+//
+// The coordinator doesn't store coverage data in the cache with each input
+// because that data would be invalid when counter offsets in the test binary
+// change.
+//
+// When gathering coverage, the coordinator sends each entry to a worker to
+// gather coverage for that entry only, without fuzzing or minimizing. This
+// phase ends when all workers have finished, and the coordinator has a combined
+// coverage map.
+func (c *coordinator) warmupRun() bool {
+ return c.warmupInputLeft > 0
+}
+
+// updateCoverage sets bits in c.coverageMask that are set in newCoverage.
+// updateCoverage returns the number of newly set bits. See the comment on
+// coverageMask for the format.
+func (c *coordinator) updateCoverage(newCoverage []byte) int {
+ if len(newCoverage) != len(c.coverageMask) {
+ panic(fmt.Sprintf("number of coverage counters changed at runtime: %d, expected %d", len(newCoverage), len(c.coverageMask)))
+ }
+ newBitCount := 0
+ for i := range newCoverage {
+ diff := newCoverage[i] &^ c.coverageMask[i]
+ newBitCount += bits.OnesCount8(diff)
+ c.coverageMask[i] |= newCoverage[i]
+ }
+ return newBitCount
+}
+
+// canMinimize returns whether the coordinator should attempt to find smaller
+// inputs that reproduce a crash or new coverage.
+func (c *coordinator) canMinimize() bool {
+ return c.minimizationAllowed &&
+ (c.opts.Limit == 0 || c.count+c.countWaiting < c.opts.Limit)
+}
+
+func (c *coordinator) elapsed() time.Duration {
+ return time.Since(c.startTime).Round(1 * time.Second)
+}
+
+// readCache creates a combined corpus from seed values and values in the cache
+// (in GOCACHE/fuzz).
+//
+// TODO(fuzzing): need a mechanism that can remove values that
+// aren't useful anymore, for example, because they have the wrong type.
+func (c *coordinator) readCache() error {
+ if _, err := c.addCorpusEntries(false, c.opts.Seed...); err != nil {
+ return err
+ }
+ entries, err := ReadCorpus(c.opts.CacheDir, c.opts.Types)
+ if err != nil {
+ if _, ok := err.(*MalformedCorpusError); !ok {
+ // It's okay if some files in the cache directory are malformed and
+ // are not included in the corpus, but fail if it's an I/O error.
+ return err
+ }
+ // TODO(jayconrod,katiehockman): consider printing some kind of warning
+ // indicating the number of files which were skipped because they are
+ // malformed.
+ }
+ if _, err := c.addCorpusEntries(false, entries...); err != nil {
+ return err
+ }
+ return nil
+}
+
+// MalformedCorpusError is an error found while reading the corpus from the
+// filesystem. All of the errors are stored in the errs list. The testing
+// framework uses this to report malformed files in testdata.
+type MalformedCorpusError struct {
+ errs []error
+}
+
+func (e *MalformedCorpusError) Error() string {
+ var msgs []string
+ for _, s := range e.errs {
+ msgs = append(msgs, s.Error())
+ }
+ return strings.Join(msgs, "\n")
+}
+
+// ReadCorpus reads the corpus from the provided dir. The returned corpus
+// entries are guaranteed to match the given types. Any malformed files will
+// be saved in a MalformedCorpusError and returned, along with the most recent
+// error.
+func ReadCorpus(dir string, types []reflect.Type) ([]CorpusEntry, error) {
+ files, err := os.ReadDir(dir)
+ if os.IsNotExist(err) {
+ return nil, nil // No corpus to read
+ } else if err != nil {
+ return nil, fmt.Errorf("reading seed corpus from testdata: %v", err)
+ }
+ var corpus []CorpusEntry
+ var errs []error
+ for _, file := range files {
+ // TODO(jayconrod,katiehockman): determine when a file is a fuzzing input
+ // based on its name. We should only read files created by writeToCorpus.
+ // If we read ALL files, we won't be able to change the file format by
+ // changing the extension. We also won't be able to add files like
+ // README.txt explaining why the directory exists.
+ if file.IsDir() {
+ continue
+ }
+ filename := filepath.Join(dir, file.Name())
+ data, err := os.ReadFile(filename)
+ if err != nil {
+ return nil, fmt.Errorf("failed to read corpus file: %v", err)
+ }
+ var vals []any
+ vals, err = readCorpusData(data, types)
+ if err != nil {
+ errs = append(errs, fmt.Errorf("%q: %v", filename, err))
+ continue
+ }
+ corpus = append(corpus, CorpusEntry{Path: filename, Values: vals})
+ }
+ if len(errs) > 0 {
+ return corpus, &MalformedCorpusError{errs: errs}
+ }
+ return corpus, nil
+}
+
+func readCorpusData(data []byte, types []reflect.Type) ([]any, error) {
+ vals, err := unmarshalCorpusFile(data)
+ if err != nil {
+ return nil, fmt.Errorf("unmarshal: %v", err)
+ }
+ if err = CheckCorpus(vals, types); err != nil {
+ return nil, err
+ }
+ return vals, nil
+}
+
+// CheckCorpus verifies that the types in vals match the expected types
+// provided.
+func CheckCorpus(vals []any, types []reflect.Type) error {
+ if len(vals) != len(types) {
+ return fmt.Errorf("wrong number of values in corpus entry: %d, want %d", len(vals), len(types))
+ }
+ valsT := make([]reflect.Type, len(vals))
+ for valsI, v := range vals {
+ valsT[valsI] = reflect.TypeOf(v)
+ }
+ for i := range types {
+ if valsT[i] != types[i] {
+ return fmt.Errorf("mismatched types in corpus entry: %v, want %v", valsT, types)
+ }
+ }
+ return nil
+}
+
+// writeToCorpus atomically writes the given bytes to a new file in testdata. If
+// the directory does not exist, it will create one. If the file already exists,
+// writeToCorpus will not rewrite it. writeToCorpus sets entry.Path to the new
+// file that was just written or an error if it failed.
+func writeToCorpus(entry *CorpusEntry, dir string) (err error) {
+ sum := fmt.Sprintf("%x", sha256.Sum256(entry.Data))[:16]
+ entry.Path = filepath.Join(dir, sum)
+ if err := os.MkdirAll(dir, 0777); err != nil {
+ return err
+ }
+ if err := os.WriteFile(entry.Path, entry.Data, 0666); err != nil {
+ os.Remove(entry.Path) // remove partially written file
+ return err
+ }
+ return nil
+}
+
+func testName(path string) string {
+ return filepath.Base(path)
+}
+
+func zeroValue(t reflect.Type) any {
+ for _, v := range zeroVals {
+ if reflect.TypeOf(v) == t {
+ return v
+ }
+ }
+ panic(fmt.Sprintf("unsupported type: %v", t))
+}
+
+var zeroVals []any = []any{
+ []byte(""),
+ string(""),
+ false,
+ byte(0),
+ rune(0),
+ float32(0),
+ float64(0),
+ int(0),
+ int8(0),
+ int16(0),
+ int32(0),
+ int64(0),
+ uint(0),
+ uint8(0),
+ uint16(0),
+ uint32(0),
+ uint64(0),
+}
+
+var debugInfo = godebug.New("fuzzdebug").Value() == "1"
+
+func shouldPrintDebugInfo() bool {
+ return debugInfo
+}
diff --git a/src/internal/fuzz/mem.go b/src/internal/fuzz/mem.go
new file mode 100644
index 0000000..4155e4e
--- /dev/null
+++ b/src/internal/fuzz/mem.go
@@ -0,0 +1,138 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fuzz
+
+import (
+ "bytes"
+ "fmt"
+ "os"
+ "unsafe"
+)
+
+// sharedMem manages access to a region of virtual memory mapped from a file,
+// shared between multiple processes. The region includes space for a header and
+// a value of variable length.
+//
+// When fuzzing, the coordinator creates a sharedMem from a temporary file for
+// each worker. This buffer is used to pass values to fuzz between processes.
+// Care must be taken to manage access to shared memory across processes;
+// sharedMem provides no synchronization on its own. See workerComm for an
+// explanation.
+type sharedMem struct {
+ // f is the file mapped into memory.
+ f *os.File
+
+ // region is the mapped region of virtual memory for f. The content of f may
+ // be read or written through this slice.
+ region []byte
+
+ // removeOnClose is true if the file should be deleted by Close.
+ removeOnClose bool
+
+ // sys contains OS-specific information.
+ sys sharedMemSys
+}
+
+// sharedMemHeader stores metadata in shared memory.
+type sharedMemHeader struct {
+ // count is the number of times the worker has called the fuzz function.
+ // May be reset by coordinator.
+ count int64
+
+ // valueLen is the number of bytes in region which should be read.
+ valueLen int
+
+ // randState and randInc hold the state of a pseudo-random number generator.
+ randState, randInc uint64
+
+ // rawInMem is true if the region holds raw bytes, which occurs during
+ // minimization. If true after the worker fails during minimization, this
+ // indicates that an unrecoverable error occurred, and the region can be
+ // used to retrieve the raw bytes that caused the error.
+ rawInMem bool
+}
+
+// sharedMemSize returns the size needed for a shared memory buffer that can
+// contain values of the given size.
+func sharedMemSize(valueSize int) int {
+ // TODO(jayconrod): set a reasonable maximum size per platform.
+ return int(unsafe.Sizeof(sharedMemHeader{})) + valueSize
+}
+
+// sharedMemTempFile creates a new temporary file of the given size, then maps
+// it into memory. The file will be removed when the Close method is called.
+func sharedMemTempFile(size int) (m *sharedMem, err error) {
+ // Create a temporary file.
+ f, err := os.CreateTemp("", "fuzz-*")
+ if err != nil {
+ return nil, err
+ }
+ defer func() {
+ if err != nil {
+ f.Close()
+ os.Remove(f.Name())
+ }
+ }()
+
+ // Resize it to the correct size.
+ totalSize := sharedMemSize(size)
+ if err := f.Truncate(int64(totalSize)); err != nil {
+ return nil, err
+ }
+
+ // Map the file into memory.
+ removeOnClose := true
+ return sharedMemMapFile(f, totalSize, removeOnClose)
+}
+
+// header returns a pointer to metadata within the shared memory region.
+func (m *sharedMem) header() *sharedMemHeader {
+ return (*sharedMemHeader)(unsafe.Pointer(&m.region[0]))
+}
+
+// valueRef returns the value currently stored in shared memory. The returned
+// slice points to shared memory; it is not a copy.
+func (m *sharedMem) valueRef() []byte {
+ length := m.header().valueLen
+ valueOffset := int(unsafe.Sizeof(sharedMemHeader{}))
+ return m.region[valueOffset : valueOffset+length]
+}
+
+// valueCopy returns a copy of the value stored in shared memory.
+func (m *sharedMem) valueCopy() []byte {
+ ref := m.valueRef()
+ return bytes.Clone(ref)
+}
+
+// setValue copies the data in b into the shared memory buffer and sets
+// the length. len(b) must be less than or equal to the capacity of the buffer
+// (as returned by cap(m.value())).
+func (m *sharedMem) setValue(b []byte) {
+ v := m.valueRef()
+ if len(b) > cap(v) {
+ panic(fmt.Sprintf("value length %d larger than shared memory capacity %d", len(b), cap(v)))
+ }
+ m.header().valueLen = len(b)
+ copy(v[:cap(v)], b)
+}
+
+// setValueLen sets the length of the shared memory buffer returned by valueRef
+// to n, which may be at most the cap of that slice.
+//
+// Note that we can only store the length in the shared memory header. The full
+// slice header contains a pointer, which is likely only valid for one process,
+// since each process can map shared memory at a different virtual address.
+func (m *sharedMem) setValueLen(n int) {
+ v := m.valueRef()
+ if n > cap(v) {
+ panic(fmt.Sprintf("length %d larger than shared memory capacity %d", n, cap(v)))
+ }
+ m.header().valueLen = n
+}
+
+// TODO(jayconrod): add method to resize the buffer. We'll need that when the
+// mutator can increase input length. Only the coordinator will be able to
+// do it, since we'll need to send a message to the worker telling it to
+// remap the file.
diff --git a/src/internal/fuzz/minimize.go b/src/internal/fuzz/minimize.go
new file mode 100644
index 0000000..0e410fb
--- /dev/null
+++ b/src/internal/fuzz/minimize.go
@@ -0,0 +1,95 @@
+// Copyright 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fuzz
+
+import (
+ "reflect"
+)
+
+func isMinimizable(t reflect.Type) bool {
+ return t == reflect.TypeOf("") || t == reflect.TypeOf([]byte(nil))
+}
+
+func minimizeBytes(v []byte, try func([]byte) bool, shouldStop func() bool) {
+ tmp := make([]byte, len(v))
+ // If minimization was successful at any point during minimizeBytes,
+ // then the vals slice in (*workerServer).minimizeInput will point to
+ // tmp. Since tmp is altered while making new candidates, we need to
+ // make sure that it is equal to the correct value, v, before exiting
+ // this function.
+ defer copy(tmp, v)
+
+ // First, try to cut the tail.
+ for n := 1024; n != 0; n /= 2 {
+ for len(v) > n {
+ if shouldStop() {
+ return
+ }
+ candidate := v[:len(v)-n]
+ if !try(candidate) {
+ break
+ }
+ // Set v to the new value to continue iterating.
+ v = candidate
+ }
+ }
+
+ // Then, try to remove each individual byte.
+ for i := 0; i < len(v)-1; i++ {
+ if shouldStop() {
+ return
+ }
+ candidate := tmp[:len(v)-1]
+ copy(candidate[:i], v[:i])
+ copy(candidate[i:], v[i+1:])
+ if !try(candidate) {
+ continue
+ }
+ // Update v to delete the value at index i.
+ copy(v[i:], v[i+1:])
+ v = v[:len(candidate)]
+ // v[i] is now different, so decrement i to redo this iteration
+ // of the loop with the new value.
+ i--
+ }
+
+ // Then, try to remove each possible subset of bytes.
+ for i := 0; i < len(v)-1; i++ {
+ copy(tmp, v[:i])
+ for j := len(v); j > i+1; j-- {
+ if shouldStop() {
+ return
+ }
+ candidate := tmp[:len(v)-j+i]
+ copy(candidate[i:], v[j:])
+ if !try(candidate) {
+ continue
+ }
+ // Update v and reset the loop with the new length.
+ copy(v[i:], v[j:])
+ v = v[:len(candidate)]
+ j = len(v)
+ }
+ }
+
+ // Then, try to make it more simplified and human-readable by trying to replace each
+ // byte with a printable character.
+ printableChars := []byte("012789ABCXYZabcxyz !\"#$%&'()*+,.")
+ for i, b := range v {
+ if shouldStop() {
+ return
+ }
+
+ for _, pc := range printableChars {
+ v[i] = pc
+ if try(v) {
+ // Successful. Move on to the next byte in v.
+ break
+ }
+ // Unsuccessful. Revert v[i] back to original value.
+ v[i] = b
+ }
+ }
+}
diff --git a/src/internal/fuzz/minimize_test.go b/src/internal/fuzz/minimize_test.go
new file mode 100644
index 0000000..2db2633
--- /dev/null
+++ b/src/internal/fuzz/minimize_test.go
@@ -0,0 +1,182 @@
+// Copyright 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+//go:build darwin || freebsd || linux || windows
+
+package fuzz
+
+import (
+ "bytes"
+ "context"
+ "errors"
+ "fmt"
+ "reflect"
+ "testing"
+ "time"
+ "unicode"
+ "unicode/utf8"
+)
+
+func TestMinimizeInput(t *testing.T) {
+ type testcase struct {
+ name string
+ fn func(CorpusEntry) error
+ input []any
+ expected []any
+ }
+ cases := []testcase{
+ {
+ name: "ones_byte",
+ fn: func(e CorpusEntry) error {
+ b := e.Values[0].([]byte)
+ ones := 0
+ for _, v := range b {
+ if v == 1 {
+ ones++
+ }
+ }
+ if ones == 3 {
+ return fmt.Errorf("bad %v", e.Values[0])
+ }
+ return nil
+ },
+ input: []any{[]byte{0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}},
+ expected: []any{[]byte{1, 1, 1}},
+ },
+ {
+ name: "single_bytes",
+ fn: func(e CorpusEntry) error {
+ b := e.Values[0].([]byte)
+ if len(b) < 2 {
+ return nil
+ }
+ if len(b) == 2 && b[0] == 1 && b[1] == 2 {
+ return nil
+ }
+ return fmt.Errorf("bad %v", e.Values[0])
+ },
+ input: []any{[]byte{1, 2, 3, 4, 5}},
+ expected: []any{[]byte("00")},
+ },
+ {
+ name: "set_of_bytes",
+ fn: func(e CorpusEntry) error {
+ b := e.Values[0].([]byte)
+ if len(b) < 3 {
+ return nil
+ }
+ if bytes.Equal(b, []byte{0, 1, 2, 3, 4, 5}) || bytes.Equal(b, []byte{0, 4, 5}) {
+ return fmt.Errorf("bad %v", e.Values[0])
+ }
+ return nil
+ },
+ input: []any{[]byte{0, 1, 2, 3, 4, 5}},
+ expected: []any{[]byte{0, 4, 5}},
+ },
+ {
+ name: "non_ascii_bytes",
+ fn: func(e CorpusEntry) error {
+ b := e.Values[0].([]byte)
+ if len(b) == 3 {
+ return fmt.Errorf("bad %v", e.Values[0])
+ }
+ return nil
+ },
+ input: []any{[]byte("ท")}, // ท is 3 bytes
+ expected: []any{[]byte("000")},
+ },
+ {
+ name: "ones_string",
+ fn: func(e CorpusEntry) error {
+ b := e.Values[0].(string)
+ ones := 0
+ for _, v := range b {
+ if v == '1' {
+ ones++
+ }
+ }
+ if ones == 3 {
+ return fmt.Errorf("bad %v", e.Values[0])
+ }
+ return nil
+ },
+ input: []any{"001010001000000000000000000"},
+ expected: []any{"111"},
+ },
+ {
+ name: "string_length",
+ fn: func(e CorpusEntry) error {
+ b := e.Values[0].(string)
+ if len(b) == 5 {
+ return fmt.Errorf("bad %v", e.Values[0])
+ }
+ return nil
+ },
+ input: []any{"zzzzz"},
+ expected: []any{"00000"},
+ },
+ {
+ name: "string_with_letter",
+ fn: func(e CorpusEntry) error {
+ b := e.Values[0].(string)
+ r, _ := utf8.DecodeRune([]byte(b))
+ if unicode.IsLetter(r) {
+ return fmt.Errorf("bad %v", e.Values[0])
+ }
+ return nil
+ },
+ input: []any{"ZZZZZ"},
+ expected: []any{"A"},
+ },
+ }
+
+ for _, tc := range cases {
+ tc := tc
+ t.Run(tc.name, func(t *testing.T) {
+ t.Parallel()
+ ws := &workerServer{
+ fuzzFn: func(e CorpusEntry) (time.Duration, error) {
+ return time.Second, tc.fn(e)
+ },
+ }
+ mem := &sharedMem{region: make([]byte, 100)} // big enough to hold value and header
+ vals := tc.input
+ success, err := ws.minimizeInput(context.Background(), vals, mem, minimizeArgs{})
+ if !success {
+ t.Errorf("minimizeInput did not succeed")
+ }
+ if err == nil {
+ t.Fatal("minimizeInput didn't provide an error")
+ }
+ if expected := fmt.Sprintf("bad %v", tc.expected[0]); err.Error() != expected {
+ t.Errorf("unexpected error: got %q, want %q", err, expected)
+ }
+ if !reflect.DeepEqual(vals, tc.expected) {
+ t.Errorf("unexpected results: got %v, want %v", vals, tc.expected)
+ }
+ })
+ }
+}
+
+// TestMinimizeFlaky checks that if we're minimizing an interesting
+// input and a flaky failure occurs, that minimization was not indicated
+// to be successful, and the error isn't returned (since it's flaky).
+func TestMinimizeFlaky(t *testing.T) {
+ ws := &workerServer{fuzzFn: func(e CorpusEntry) (time.Duration, error) {
+ return time.Second, errors.New("ohno")
+ }}
+ mem := &sharedMem{region: make([]byte, 100)} // big enough to hold value and header
+ vals := []any{[]byte(nil)}
+ args := minimizeArgs{KeepCoverage: make([]byte, len(coverageSnapshot))}
+ success, err := ws.minimizeInput(context.Background(), vals, mem, args)
+ if success {
+ t.Error("unexpected success")
+ }
+ if err != nil {
+ t.Errorf("unexpected error: %v", err)
+ }
+ if count := mem.header().count; count != 1 {
+ t.Errorf("count: got %d, want 1", count)
+ }
+}
diff --git a/src/internal/fuzz/mutator.go b/src/internal/fuzz/mutator.go
new file mode 100644
index 0000000..bb96066
--- /dev/null
+++ b/src/internal/fuzz/mutator.go
@@ -0,0 +1,300 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fuzz
+
+import (
+ "encoding/binary"
+ "fmt"
+ "math"
+ "unsafe"
+)
+
+type mutator struct {
+ r mutatorRand
+ scratch []byte // scratch slice to avoid additional allocations
+}
+
+func newMutator() *mutator {
+ return &mutator{r: newPcgRand()}
+}
+
+func (m *mutator) rand(n int) int {
+ return m.r.intn(n)
+}
+
+func (m *mutator) randByteOrder() binary.ByteOrder {
+ if m.r.bool() {
+ return binary.LittleEndian
+ }
+ return binary.BigEndian
+}
+
+// chooseLen chooses length of range mutation in range [1,n]. It gives
+// preference to shorter ranges.
+func (m *mutator) chooseLen(n int) int {
+ switch x := m.rand(100); {
+ case x < 90:
+ return m.rand(min(8, n)) + 1
+ case x < 99:
+ return m.rand(min(32, n)) + 1
+ default:
+ return m.rand(n) + 1
+ }
+}
+
+func min(a, b int) int {
+ if a < b {
+ return a
+ }
+ return b
+}
+
+// mutate performs several mutations on the provided values.
+func (m *mutator) mutate(vals []any, maxBytes int) {
+ // TODO(katiehockman): pull some of these functions into helper methods and
+ // test that each case is working as expected.
+ // TODO(katiehockman): perform more types of mutations for []byte.
+
+ // maxPerVal will represent the maximum number of bytes that each value be
+ // allowed after mutating, giving an equal amount of capacity to each line.
+ // Allow a little wiggle room for the encoding.
+ maxPerVal := maxBytes/len(vals) - 100
+
+ // Pick a random value to mutate.
+ // TODO: consider mutating more than one value at a time.
+ i := m.rand(len(vals))
+ switch v := vals[i].(type) {
+ case int:
+ vals[i] = int(m.mutateInt(int64(v), maxInt))
+ case int8:
+ vals[i] = int8(m.mutateInt(int64(v), math.MaxInt8))
+ case int16:
+ vals[i] = int16(m.mutateInt(int64(v), math.MaxInt16))
+ case int64:
+ vals[i] = m.mutateInt(v, maxInt)
+ case uint:
+ vals[i] = uint(m.mutateUInt(uint64(v), maxUint))
+ case uint16:
+ vals[i] = uint16(m.mutateUInt(uint64(v), math.MaxUint16))
+ case uint32:
+ vals[i] = uint32(m.mutateUInt(uint64(v), math.MaxUint32))
+ case uint64:
+ vals[i] = m.mutateUInt(uint64(v), maxUint)
+ case float32:
+ vals[i] = float32(m.mutateFloat(float64(v), math.MaxFloat32))
+ case float64:
+ vals[i] = m.mutateFloat(v, math.MaxFloat64)
+ case bool:
+ if m.rand(2) == 1 {
+ vals[i] = !v // 50% chance of flipping the bool
+ }
+ case rune: // int32
+ vals[i] = rune(m.mutateInt(int64(v), math.MaxInt32))
+ case byte: // uint8
+ vals[i] = byte(m.mutateUInt(uint64(v), math.MaxUint8))
+ case string:
+ if len(v) > maxPerVal {
+ panic(fmt.Sprintf("cannot mutate bytes of length %d", len(v)))
+ }
+ if cap(m.scratch) < maxPerVal {
+ m.scratch = append(make([]byte, 0, maxPerVal), v...)
+ } else {
+ m.scratch = m.scratch[:len(v)]
+ copy(m.scratch, v)
+ }
+ m.mutateBytes(&m.scratch)
+ vals[i] = string(m.scratch)
+ case []byte:
+ if len(v) > maxPerVal {
+ panic(fmt.Sprintf("cannot mutate bytes of length %d", len(v)))
+ }
+ if cap(m.scratch) < maxPerVal {
+ m.scratch = append(make([]byte, 0, maxPerVal), v...)
+ } else {
+ m.scratch = m.scratch[:len(v)]
+ copy(m.scratch, v)
+ }
+ m.mutateBytes(&m.scratch)
+ vals[i] = m.scratch
+ default:
+ panic(fmt.Sprintf("type not supported for mutating: %T", vals[i]))
+ }
+}
+
+func (m *mutator) mutateInt(v, maxValue int64) int64 {
+ var max int64
+ for {
+ max = 100
+ switch m.rand(2) {
+ case 0:
+ // Add a random number
+ if v >= maxValue {
+ continue
+ }
+ if v > 0 && maxValue-v < max {
+ // Don't let v exceed maxValue
+ max = maxValue - v
+ }
+ v += int64(1 + m.rand(int(max)))
+ return v
+ case 1:
+ // Subtract a random number
+ if v <= -maxValue {
+ continue
+ }
+ if v < 0 && maxValue+v < max {
+ // Don't let v drop below -maxValue
+ max = maxValue + v
+ }
+ v -= int64(1 + m.rand(int(max)))
+ return v
+ }
+ }
+}
+
+func (m *mutator) mutateUInt(v, maxValue uint64) uint64 {
+ var max uint64
+ for {
+ max = 100
+ switch m.rand(2) {
+ case 0:
+ // Add a random number
+ if v >= maxValue {
+ continue
+ }
+ if v > 0 && maxValue-v < max {
+ // Don't let v exceed maxValue
+ max = maxValue - v
+ }
+
+ v += uint64(1 + m.rand(int(max)))
+ return v
+ case 1:
+ // Subtract a random number
+ if v <= 0 {
+ continue
+ }
+ if v < max {
+ // Don't let v drop below 0
+ max = v
+ }
+ v -= uint64(1 + m.rand(int(max)))
+ return v
+ }
+ }
+}
+
+func (m *mutator) mutateFloat(v, maxValue float64) float64 {
+ var max float64
+ for {
+ switch m.rand(4) {
+ case 0:
+ // Add a random number
+ if v >= maxValue {
+ continue
+ }
+ max = 100
+ if v > 0 && maxValue-v < max {
+ // Don't let v exceed maxValue
+ max = maxValue - v
+ }
+ v += float64(1 + m.rand(int(max)))
+ return v
+ case 1:
+ // Subtract a random number
+ if v <= -maxValue {
+ continue
+ }
+ max = 100
+ if v < 0 && maxValue+v < max {
+ // Don't let v drop below -maxValue
+ max = maxValue + v
+ }
+ v -= float64(1 + m.rand(int(max)))
+ return v
+ case 2:
+ // Multiply by a random number
+ absV := math.Abs(v)
+ if v == 0 || absV >= maxValue {
+ continue
+ }
+ max = 10
+ if maxValue/absV < max {
+ // Don't let v go beyond the minimum or maximum value
+ max = maxValue / absV
+ }
+ v *= float64(1 + m.rand(int(max)))
+ return v
+ case 3:
+ // Divide by a random number
+ if v == 0 {
+ continue
+ }
+ v /= float64(1 + m.rand(10))
+ return v
+ }
+ }
+}
+
+type byteSliceMutator func(*mutator, []byte) []byte
+
+var byteSliceMutators = []byteSliceMutator{
+ byteSliceRemoveBytes,
+ byteSliceInsertRandomBytes,
+ byteSliceDuplicateBytes,
+ byteSliceOverwriteBytes,
+ byteSliceBitFlip,
+ byteSliceXORByte,
+ byteSliceSwapByte,
+ byteSliceArithmeticUint8,
+ byteSliceArithmeticUint16,
+ byteSliceArithmeticUint32,
+ byteSliceArithmeticUint64,
+ byteSliceOverwriteInterestingUint8,
+ byteSliceOverwriteInterestingUint16,
+ byteSliceOverwriteInterestingUint32,
+ byteSliceInsertConstantBytes,
+ byteSliceOverwriteConstantBytes,
+ byteSliceShuffleBytes,
+ byteSliceSwapBytes,
+}
+
+func (m *mutator) mutateBytes(ptrB *[]byte) {
+ b := *ptrB
+ defer func() {
+ if unsafe.SliceData(*ptrB) != unsafe.SliceData(b) {
+ panic("data moved to new address")
+ }
+ *ptrB = b
+ }()
+
+ for {
+ mut := byteSliceMutators[m.rand(len(byteSliceMutators))]
+ if mutated := mut(m, b); mutated != nil {
+ b = mutated
+ return
+ }
+ }
+}
+
+var (
+ interesting8 = []int8{-128, -1, 0, 1, 16, 32, 64, 100, 127}
+ interesting16 = []int16{-32768, -129, 128, 255, 256, 512, 1000, 1024, 4096, 32767}
+ interesting32 = []int32{-2147483648, -100663046, -32769, 32768, 65535, 65536, 100663045, 2147483647}
+)
+
+const (
+ maxUint = uint64(^uint(0))
+ maxInt = int64(maxUint >> 1)
+)
+
+func init() {
+ for _, v := range interesting8 {
+ interesting16 = append(interesting16, int16(v))
+ }
+ for _, v := range interesting16 {
+ interesting32 = append(interesting32, int32(v))
+ }
+}
diff --git a/src/internal/fuzz/mutator_test.go b/src/internal/fuzz/mutator_test.go
new file mode 100644
index 0000000..cea7e2e
--- /dev/null
+++ b/src/internal/fuzz/mutator_test.go
@@ -0,0 +1,117 @@
+// Copyright 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fuzz
+
+import (
+ "bytes"
+ "fmt"
+ "os"
+ "strconv"
+ "testing"
+)
+
+func BenchmarkMutatorBytes(b *testing.B) {
+ origEnv := os.Getenv("GODEBUG")
+ defer func() { os.Setenv("GODEBUG", origEnv) }()
+ os.Setenv("GODEBUG", fmt.Sprintf("%s,fuzzseed=123", origEnv))
+ m := newMutator()
+
+ for _, size := range []int{
+ 1,
+ 10,
+ 100,
+ 1000,
+ 10000,
+ 100000,
+ } {
+ b.Run(strconv.Itoa(size), func(b *testing.B) {
+ buf := make([]byte, size)
+ b.ResetTimer()
+
+ for i := 0; i < b.N; i++ {
+ // resize buffer to the correct shape and reset the PCG
+ buf = buf[0:size]
+ m.r = newPcgRand()
+ m.mutate([]any{buf}, workerSharedMemSize)
+ }
+ })
+ }
+}
+
+func BenchmarkMutatorString(b *testing.B) {
+ origEnv := os.Getenv("GODEBUG")
+ defer func() { os.Setenv("GODEBUG", origEnv) }()
+ os.Setenv("GODEBUG", fmt.Sprintf("%s,fuzzseed=123", origEnv))
+ m := newMutator()
+
+ for _, size := range []int{
+ 1,
+ 10,
+ 100,
+ 1000,
+ 10000,
+ 100000,
+ } {
+ b.Run(strconv.Itoa(size), func(b *testing.B) {
+ buf := make([]byte, size)
+ b.ResetTimer()
+
+ for i := 0; i < b.N; i++ {
+ // resize buffer to the correct shape and reset the PCG
+ buf = buf[0:size]
+ m.r = newPcgRand()
+ m.mutate([]any{string(buf)}, workerSharedMemSize)
+ }
+ })
+ }
+}
+
+func BenchmarkMutatorAllBasicTypes(b *testing.B) {
+ origEnv := os.Getenv("GODEBUG")
+ defer func() { os.Setenv("GODEBUG", origEnv) }()
+ os.Setenv("GODEBUG", fmt.Sprintf("%s,fuzzseed=123", origEnv))
+ m := newMutator()
+
+ types := []any{
+ []byte(""),
+ string(""),
+ false,
+ float32(0),
+ float64(0),
+ int(0),
+ int8(0),
+ int16(0),
+ int32(0),
+ int64(0),
+ uint8(0),
+ uint16(0),
+ uint32(0),
+ uint64(0),
+ }
+
+ for _, t := range types {
+ b.Run(fmt.Sprintf("%T", t), func(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ m.r = newPcgRand()
+ m.mutate([]any{t}, workerSharedMemSize)
+ }
+ })
+ }
+}
+
+func TestStringImmutability(t *testing.T) {
+ v := []any{"hello"}
+ m := newMutator()
+ m.mutate(v, 1024)
+ original := v[0].(string)
+ originalCopy := make([]byte, len(original))
+ copy(originalCopy, []byte(original))
+ for i := 0; i < 25; i++ {
+ m.mutate(v, 1024)
+ }
+ if !bytes.Equal([]byte(original), originalCopy) {
+ t.Fatalf("string was mutated: got %x, want %x", []byte(original), originalCopy)
+ }
+}
diff --git a/src/internal/fuzz/mutators_byteslice.go b/src/internal/fuzz/mutators_byteslice.go
new file mode 100644
index 0000000..d9dab1d
--- /dev/null
+++ b/src/internal/fuzz/mutators_byteslice.go
@@ -0,0 +1,313 @@
+// Copyright 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fuzz
+
+// byteSliceRemoveBytes removes a random chunk of bytes from b.
+func byteSliceRemoveBytes(m *mutator, b []byte) []byte {
+ if len(b) <= 1 {
+ return nil
+ }
+ pos0 := m.rand(len(b))
+ pos1 := pos0 + m.chooseLen(len(b)-pos0)
+ copy(b[pos0:], b[pos1:])
+ b = b[:len(b)-(pos1-pos0)]
+ return b
+}
+
+// byteSliceInsertRandomBytes inserts a chunk of random bytes into b at a random
+// position.
+func byteSliceInsertRandomBytes(m *mutator, b []byte) []byte {
+ pos := m.rand(len(b) + 1)
+ n := m.chooseLen(1024)
+ if len(b)+n >= cap(b) {
+ return nil
+ }
+ b = b[:len(b)+n]
+ copy(b[pos+n:], b[pos:])
+ for i := 0; i < n; i++ {
+ b[pos+i] = byte(m.rand(256))
+ }
+ return b
+}
+
+// byteSliceDuplicateBytes duplicates a chunk of bytes in b and inserts it into
+// a random position.
+func byteSliceDuplicateBytes(m *mutator, b []byte) []byte {
+ if len(b) <= 1 {
+ return nil
+ }
+ src := m.rand(len(b))
+ dst := m.rand(len(b))
+ for dst == src {
+ dst = m.rand(len(b))
+ }
+ n := m.chooseLen(len(b) - src)
+ // Use the end of the slice as scratch space to avoid doing an
+ // allocation. If the slice is too small abort and try something
+ // else.
+ if len(b)+(n*2) >= cap(b) {
+ return nil
+ }
+ end := len(b)
+ // Increase the size of b to fit the duplicated block as well as
+ // some extra working space
+ b = b[:end+(n*2)]
+ // Copy the block of bytes we want to duplicate to the end of the
+ // slice
+ copy(b[end+n:], b[src:src+n])
+ // Shift the bytes after the splice point n positions to the right
+ // to make room for the new block
+ copy(b[dst+n:end+n], b[dst:end])
+ // Insert the duplicate block into the splice point
+ copy(b[dst:], b[end+n:])
+ b = b[:end+n]
+ return b
+}
+
+// byteSliceOverwriteBytes overwrites a chunk of b with another chunk of b.
+func byteSliceOverwriteBytes(m *mutator, b []byte) []byte {
+ if len(b) <= 1 {
+ return nil
+ }
+ src := m.rand(len(b))
+ dst := m.rand(len(b))
+ for dst == src {
+ dst = m.rand(len(b))
+ }
+ n := m.chooseLen(len(b) - src - 1)
+ copy(b[dst:], b[src:src+n])
+ return b
+}
+
+// byteSliceBitFlip flips a random bit in a random byte in b.
+func byteSliceBitFlip(m *mutator, b []byte) []byte {
+ if len(b) == 0 {
+ return nil
+ }
+ pos := m.rand(len(b))
+ b[pos] ^= 1 << uint(m.rand(8))
+ return b
+}
+
+// byteSliceXORByte XORs a random byte in b with a random value.
+func byteSliceXORByte(m *mutator, b []byte) []byte {
+ if len(b) == 0 {
+ return nil
+ }
+ pos := m.rand(len(b))
+ // In order to avoid a no-op (where the random value matches
+ // the existing value), use XOR instead of just setting to
+ // the random value.
+ b[pos] ^= byte(1 + m.rand(255))
+ return b
+}
+
+// byteSliceSwapByte swaps two random bytes in b.
+func byteSliceSwapByte(m *mutator, b []byte) []byte {
+ if len(b) <= 1 {
+ return nil
+ }
+ src := m.rand(len(b))
+ dst := m.rand(len(b))
+ for dst == src {
+ dst = m.rand(len(b))
+ }
+ b[src], b[dst] = b[dst], b[src]
+ return b
+}
+
+// byteSliceArithmeticUint8 adds/subtracts from a random byte in b.
+func byteSliceArithmeticUint8(m *mutator, b []byte) []byte {
+ if len(b) == 0 {
+ return nil
+ }
+ pos := m.rand(len(b))
+ v := byte(m.rand(35) + 1)
+ if m.r.bool() {
+ b[pos] += v
+ } else {
+ b[pos] -= v
+ }
+ return b
+}
+
+// byteSliceArithmeticUint16 adds/subtracts from a random uint16 in b.
+func byteSliceArithmeticUint16(m *mutator, b []byte) []byte {
+ if len(b) < 2 {
+ return nil
+ }
+ v := uint16(m.rand(35) + 1)
+ if m.r.bool() {
+ v = 0 - v
+ }
+ pos := m.rand(len(b) - 1)
+ enc := m.randByteOrder()
+ enc.PutUint16(b[pos:], enc.Uint16(b[pos:])+v)
+ return b
+}
+
+// byteSliceArithmeticUint32 adds/subtracts from a random uint32 in b.
+func byteSliceArithmeticUint32(m *mutator, b []byte) []byte {
+ if len(b) < 4 {
+ return nil
+ }
+ v := uint32(m.rand(35) + 1)
+ if m.r.bool() {
+ v = 0 - v
+ }
+ pos := m.rand(len(b) - 3)
+ enc := m.randByteOrder()
+ enc.PutUint32(b[pos:], enc.Uint32(b[pos:])+v)
+ return b
+}
+
+// byteSliceArithmeticUint64 adds/subtracts from a random uint64 in b.
+func byteSliceArithmeticUint64(m *mutator, b []byte) []byte {
+ if len(b) < 8 {
+ return nil
+ }
+ v := uint64(m.rand(35) + 1)
+ if m.r.bool() {
+ v = 0 - v
+ }
+ pos := m.rand(len(b) - 7)
+ enc := m.randByteOrder()
+ enc.PutUint64(b[pos:], enc.Uint64(b[pos:])+v)
+ return b
+}
+
+// byteSliceOverwriteInterestingUint8 overwrites a random byte in b with an interesting
+// value.
+func byteSliceOverwriteInterestingUint8(m *mutator, b []byte) []byte {
+ if len(b) == 0 {
+ return nil
+ }
+ pos := m.rand(len(b))
+ b[pos] = byte(interesting8[m.rand(len(interesting8))])
+ return b
+}
+
+// byteSliceOverwriteInterestingUint16 overwrites a random uint16 in b with an interesting
+// value.
+func byteSliceOverwriteInterestingUint16(m *mutator, b []byte) []byte {
+ if len(b) < 2 {
+ return nil
+ }
+ pos := m.rand(len(b) - 1)
+ v := uint16(interesting16[m.rand(len(interesting16))])
+ m.randByteOrder().PutUint16(b[pos:], v)
+ return b
+}
+
+// byteSliceOverwriteInterestingUint32 overwrites a random uint16 in b with an interesting
+// value.
+func byteSliceOverwriteInterestingUint32(m *mutator, b []byte) []byte {
+ if len(b) < 4 {
+ return nil
+ }
+ pos := m.rand(len(b) - 3)
+ v := uint32(interesting32[m.rand(len(interesting32))])
+ m.randByteOrder().PutUint32(b[pos:], v)
+ return b
+}
+
+// byteSliceInsertConstantBytes inserts a chunk of constant bytes into a random position in b.
+func byteSliceInsertConstantBytes(m *mutator, b []byte) []byte {
+ if len(b) <= 1 {
+ return nil
+ }
+ dst := m.rand(len(b))
+ // TODO(rolandshoemaker,katiehockman): 4096 was mainly picked
+ // randomly. We may want to either pick a much larger value
+ // (AFL uses 32768, paired with a similar impl to chooseLen
+ // which biases towards smaller lengths that grow over time),
+ // or set the max based on characteristics of the corpus
+ // (libFuzzer sets a min/max based on the min/max size of
+ // entries in the corpus and then picks uniformly from
+ // that range).
+ n := m.chooseLen(4096)
+ if len(b)+n >= cap(b) {
+ return nil
+ }
+ b = b[:len(b)+n]
+ copy(b[dst+n:], b[dst:])
+ rb := byte(m.rand(256))
+ for i := dst; i < dst+n; i++ {
+ b[i] = rb
+ }
+ return b
+}
+
+// byteSliceOverwriteConstantBytes overwrites a chunk of b with constant bytes.
+func byteSliceOverwriteConstantBytes(m *mutator, b []byte) []byte {
+ if len(b) <= 1 {
+ return nil
+ }
+ dst := m.rand(len(b))
+ n := m.chooseLen(len(b) - dst)
+ rb := byte(m.rand(256))
+ for i := dst; i < dst+n; i++ {
+ b[i] = rb
+ }
+ return b
+}
+
+// byteSliceShuffleBytes shuffles a chunk of bytes in b.
+func byteSliceShuffleBytes(m *mutator, b []byte) []byte {
+ if len(b) <= 1 {
+ return nil
+ }
+ dst := m.rand(len(b))
+ n := m.chooseLen(len(b) - dst)
+ if n <= 2 {
+ return nil
+ }
+ // Start at the end of the range, and iterate backwards
+ // to dst, swapping each element with another element in
+ // dst:dst+n (Fisher-Yates shuffle).
+ for i := n - 1; i > 0; i-- {
+ j := m.rand(i + 1)
+ b[dst+i], b[dst+j] = b[dst+j], b[dst+i]
+ }
+ return b
+}
+
+// byteSliceSwapBytes swaps two chunks of bytes in b.
+func byteSliceSwapBytes(m *mutator, b []byte) []byte {
+ if len(b) <= 1 {
+ return nil
+ }
+ src := m.rand(len(b))
+ dst := m.rand(len(b))
+ for dst == src {
+ dst = m.rand(len(b))
+ }
+ // Choose the random length as len(b) - max(src, dst)
+ // so that we don't attempt to swap a chunk that extends
+ // beyond the end of the slice
+ max := dst
+ if src > max {
+ max = src
+ }
+ n := m.chooseLen(len(b) - max - 1)
+ // Check that neither chunk intersect, so that we don't end up
+ // duplicating parts of the input, rather than swapping them
+ if src > dst && dst+n >= src || dst > src && src+n >= dst {
+ return nil
+ }
+ // Use the end of the slice as scratch space to avoid doing an
+ // allocation. If the slice is too small abort and try something
+ // else.
+ if len(b)+n >= cap(b) {
+ return nil
+ }
+ end := len(b)
+ b = b[:end+n]
+ copy(b[end:], b[dst:dst+n])
+ copy(b[dst:], b[src:src+n])
+ copy(b[src:], b[end:])
+ b = b[:end]
+ return b
+}
diff --git a/src/internal/fuzz/mutators_byteslice_test.go b/src/internal/fuzz/mutators_byteslice_test.go
new file mode 100644
index 0000000..7886967
--- /dev/null
+++ b/src/internal/fuzz/mutators_byteslice_test.go
@@ -0,0 +1,186 @@
+// Copyright 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fuzz
+
+import (
+ "bytes"
+ "testing"
+)
+
+type mockRand struct {
+ values []int
+ counter int
+ b bool
+}
+
+func (mr *mockRand) uint32() uint32 {
+ c := mr.values[mr.counter]
+ mr.counter++
+ return uint32(c)
+}
+
+func (mr *mockRand) intn(n int) int {
+ c := mr.values[mr.counter]
+ mr.counter++
+ return c % n
+}
+
+func (mr *mockRand) uint32n(n uint32) uint32 {
+ c := mr.values[mr.counter]
+ mr.counter++
+ return uint32(c) % n
+}
+
+func (mr *mockRand) exp2() int {
+ c := mr.values[mr.counter]
+ mr.counter++
+ return c
+}
+
+func (mr *mockRand) bool() bool {
+ b := mr.b
+ mr.b = !mr.b
+ return b
+}
+
+func (mr *mockRand) save(*uint64, *uint64) {
+ panic("unimplemented")
+}
+
+func (mr *mockRand) restore(uint64, uint64) {
+ panic("unimplemented")
+}
+
+func TestByteSliceMutators(t *testing.T) {
+ for _, tc := range []struct {
+ name string
+ mutator func(*mutator, []byte) []byte
+ randVals []int
+ input []byte
+ expected []byte
+ }{
+ {
+ name: "byteSliceRemoveBytes",
+ mutator: byteSliceRemoveBytes,
+ input: []byte{1, 2, 3, 4},
+ expected: []byte{4},
+ },
+ {
+ name: "byteSliceInsertRandomBytes",
+ mutator: byteSliceInsertRandomBytes,
+ input: make([]byte, 4, 8),
+ expected: []byte{3, 4, 5, 0, 0, 0, 0},
+ },
+ {
+ name: "byteSliceDuplicateBytes",
+ mutator: byteSliceDuplicateBytes,
+ input: append(make([]byte, 0, 13), []byte{1, 2, 3, 4}...),
+ expected: []byte{1, 1, 2, 3, 4, 2, 3, 4},
+ },
+ {
+ name: "byteSliceOverwriteBytes",
+ mutator: byteSliceOverwriteBytes,
+ input: []byte{1, 2, 3, 4},
+ expected: []byte{1, 1, 3, 4},
+ },
+ {
+ name: "byteSliceBitFlip",
+ mutator: byteSliceBitFlip,
+ input: []byte{1, 2, 3, 4},
+ expected: []byte{3, 2, 3, 4},
+ },
+ {
+ name: "byteSliceXORByte",
+ mutator: byteSliceXORByte,
+ input: []byte{1, 2, 3, 4},
+ expected: []byte{3, 2, 3, 4},
+ },
+ {
+ name: "byteSliceSwapByte",
+ mutator: byteSliceSwapByte,
+ input: []byte{1, 2, 3, 4},
+ expected: []byte{2, 1, 3, 4},
+ },
+ {
+ name: "byteSliceArithmeticUint8",
+ mutator: byteSliceArithmeticUint8,
+ input: []byte{1, 2, 3, 4},
+ expected: []byte{255, 2, 3, 4},
+ },
+ {
+ name: "byteSliceArithmeticUint16",
+ mutator: byteSliceArithmeticUint16,
+ input: []byte{1, 2, 3, 4},
+ expected: []byte{1, 3, 3, 4},
+ },
+ {
+ name: "byteSliceArithmeticUint32",
+ mutator: byteSliceArithmeticUint32,
+ input: []byte{1, 2, 3, 4},
+ expected: []byte{2, 2, 3, 4},
+ },
+ {
+ name: "byteSliceArithmeticUint64",
+ mutator: byteSliceArithmeticUint64,
+ input: []byte{1, 2, 3, 4, 5, 6, 7, 8},
+ expected: []byte{2, 2, 3, 4, 5, 6, 7, 8},
+ },
+ {
+ name: "byteSliceOverwriteInterestingUint8",
+ mutator: byteSliceOverwriteInterestingUint8,
+ input: []byte{1, 2, 3, 4},
+ expected: []byte{255, 2, 3, 4},
+ },
+ {
+ name: "byteSliceOverwriteInterestingUint16",
+ mutator: byteSliceOverwriteInterestingUint16,
+ input: []byte{1, 2, 3, 4},
+ expected: []byte{255, 127, 3, 4},
+ },
+ {
+ name: "byteSliceOverwriteInterestingUint32",
+ mutator: byteSliceOverwriteInterestingUint32,
+ input: []byte{1, 2, 3, 4},
+ expected: []byte{250, 0, 0, 250},
+ },
+ {
+ name: "byteSliceInsertConstantBytes",
+ mutator: byteSliceInsertConstantBytes,
+ input: append(make([]byte, 0, 8), []byte{1, 2, 3, 4}...),
+ expected: []byte{3, 3, 3, 1, 2, 3, 4},
+ },
+ {
+ name: "byteSliceOverwriteConstantBytes",
+ mutator: byteSliceOverwriteConstantBytes,
+ input: []byte{1, 2, 3, 4},
+ expected: []byte{3, 3, 3, 4},
+ },
+ {
+ name: "byteSliceShuffleBytes",
+ mutator: byteSliceShuffleBytes,
+ input: []byte{1, 2, 3, 4},
+ expected: []byte{2, 3, 1, 4},
+ },
+ {
+ name: "byteSliceSwapBytes",
+ mutator: byteSliceSwapBytes,
+ randVals: []int{0, 2, 0, 2},
+ input: append(make([]byte, 0, 9), []byte{1, 2, 3, 4}...),
+ expected: []byte{3, 2, 1, 4},
+ },
+ } {
+ t.Run(tc.name, func(t *testing.T) {
+ r := &mockRand{values: []int{0, 1, 2, 3, 4, 5}}
+ if tc.randVals != nil {
+ r.values = tc.randVals
+ }
+ m := &mutator{r: r}
+ b := tc.mutator(m, tc.input)
+ if !bytes.Equal(b, tc.expected) {
+ t.Errorf("got %x, want %x", b, tc.expected)
+ }
+ })
+ }
+}
diff --git a/src/internal/fuzz/pcg.go b/src/internal/fuzz/pcg.go
new file mode 100644
index 0000000..c9ea0af
--- /dev/null
+++ b/src/internal/fuzz/pcg.go
@@ -0,0 +1,145 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fuzz
+
+import (
+ "math/bits"
+ "os"
+ "strconv"
+ "strings"
+ "sync/atomic"
+ "time"
+)
+
+type mutatorRand interface {
+ uint32() uint32
+ intn(int) int
+ uint32n(uint32) uint32
+ exp2() int
+ bool() bool
+
+ save(randState, randInc *uint64)
+ restore(randState, randInc uint64)
+}
+
+// The functions in pcg implement a 32 bit PRNG with a 64 bit period: pcg xsh rr
+// 64 32. See https://www.pcg-random.org/ for more information. This
+// implementation is geared specifically towards the needs of fuzzing: Simple
+// creation and use, no reproducibility, no concurrency safety, just the
+// necessary methods, optimized for speed.
+
+var globalInc uint64 // PCG stream
+
+const multiplier uint64 = 6364136223846793005
+
+// pcgRand is a PRNG. It should not be copied or shared. No Rand methods are
+// concurrency safe.
+type pcgRand struct {
+ noCopy noCopy // help avoid mistakes: ask vet to ensure that we don't make a copy
+ state uint64
+ inc uint64
+}
+
+func godebugSeed() *int {
+ debug := strings.Split(os.Getenv("GODEBUG"), ",")
+ for _, f := range debug {
+ if strings.HasPrefix(f, "fuzzseed=") {
+ seed, err := strconv.Atoi(strings.TrimPrefix(f, "fuzzseed="))
+ if err != nil {
+ panic("malformed fuzzseed")
+ }
+ return &seed
+ }
+ }
+ return nil
+}
+
+// newPcgRand generates a new, seeded Rand, ready for use.
+func newPcgRand() *pcgRand {
+ r := new(pcgRand)
+ now := uint64(time.Now().UnixNano())
+ if seed := godebugSeed(); seed != nil {
+ now = uint64(*seed)
+ }
+ inc := atomic.AddUint64(&globalInc, 1)
+ r.state = now
+ r.inc = (inc << 1) | 1
+ r.step()
+ r.state += now
+ r.step()
+ return r
+}
+
+func (r *pcgRand) step() {
+ r.state *= multiplier
+ r.state += r.inc
+}
+
+func (r *pcgRand) save(randState, randInc *uint64) {
+ *randState = r.state
+ *randInc = r.inc
+}
+
+func (r *pcgRand) restore(randState, randInc uint64) {
+ r.state = randState
+ r.inc = randInc
+}
+
+// uint32 returns a pseudo-random uint32.
+func (r *pcgRand) uint32() uint32 {
+ x := r.state
+ r.step()
+ return bits.RotateLeft32(uint32(((x>>18)^x)>>27), -int(x>>59))
+}
+
+// intn returns a pseudo-random number in [0, n).
+// n must fit in a uint32.
+func (r *pcgRand) intn(n int) int {
+ if int(uint32(n)) != n {
+ panic("large Intn")
+ }
+ return int(r.uint32n(uint32(n)))
+}
+
+// uint32n returns a pseudo-random number in [0, n).
+//
+// For implementation details, see:
+// https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction
+// https://lemire.me/blog/2016/06/30/fast-random-shuffling
+func (r *pcgRand) uint32n(n uint32) uint32 {
+ v := r.uint32()
+ prod := uint64(v) * uint64(n)
+ low := uint32(prod)
+ if low < n {
+ thresh := uint32(-int32(n)) % n
+ for low < thresh {
+ v = r.uint32()
+ prod = uint64(v) * uint64(n)
+ low = uint32(prod)
+ }
+ }
+ return uint32(prod >> 32)
+}
+
+// exp2 generates n with probability 1/2^(n+1).
+func (r *pcgRand) exp2() int {
+ return bits.TrailingZeros32(r.uint32())
+}
+
+// bool generates a random bool.
+func (r *pcgRand) bool() bool {
+ return r.uint32()&1 == 0
+}
+
+// noCopy may be embedded into structs which must not be copied
+// after the first use.
+//
+// See https://golang.org/issues/8005#issuecomment-190753527
+// for details.
+type noCopy struct{}
+
+// lock is a no-op used by -copylocks checker from `go vet`.
+func (*noCopy) lock() {}
+func (*noCopy) unlock() {}
diff --git a/src/internal/fuzz/queue.go b/src/internal/fuzz/queue.go
new file mode 100644
index 0000000..195d6eb
--- /dev/null
+++ b/src/internal/fuzz/queue.go
@@ -0,0 +1,71 @@
+// Copyright 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fuzz
+
+// queue holds a growable sequence of inputs for fuzzing and minimization.
+//
+// For now, this is a simple ring buffer
+// (https://en.wikipedia.org/wiki/Circular_buffer).
+//
+// TODO(golang.org/issue/46224): use a prioritization algorithm based on input
+// size, previous duration, coverage, and any other metrics that seem useful.
+type queue struct {
+ // elems holds a ring buffer.
+ // The queue is empty when begin = end.
+ // The queue is full (until grow is called) when end = begin + N - 1 (mod N)
+ // where N = cap(elems).
+ elems []any
+ head, len int
+}
+
+func (q *queue) cap() int {
+ return len(q.elems)
+}
+
+func (q *queue) grow() {
+ oldCap := q.cap()
+ newCap := oldCap * 2
+ if newCap == 0 {
+ newCap = 8
+ }
+ newElems := make([]any, newCap)
+ oldLen := q.len
+ for i := 0; i < oldLen; i++ {
+ newElems[i] = q.elems[(q.head+i)%oldCap]
+ }
+ q.elems = newElems
+ q.head = 0
+}
+
+func (q *queue) enqueue(e any) {
+ if q.len+1 > q.cap() {
+ q.grow()
+ }
+ i := (q.head + q.len) % q.cap()
+ q.elems[i] = e
+ q.len++
+}
+
+func (q *queue) dequeue() (any, bool) {
+ if q.len == 0 {
+ return nil, false
+ }
+ e := q.elems[q.head]
+ q.elems[q.head] = nil
+ q.head = (q.head + 1) % q.cap()
+ q.len--
+ return e, true
+}
+
+func (q *queue) peek() (any, bool) {
+ if q.len == 0 {
+ return nil, false
+ }
+ return q.elems[q.head], true
+}
+
+func (q *queue) clear() {
+ *q = queue{}
+}
diff --git a/src/internal/fuzz/queue_test.go b/src/internal/fuzz/queue_test.go
new file mode 100644
index 0000000..3b179af
--- /dev/null
+++ b/src/internal/fuzz/queue_test.go
@@ -0,0 +1,58 @@
+// Copyright 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fuzz
+
+import "testing"
+
+func TestQueue(t *testing.T) {
+ // Zero valued queue should have 0 length and capacity.
+ var q queue
+ if n := q.len; n != 0 {
+ t.Fatalf("empty queue has len %d; want 0", n)
+ }
+ if n := q.cap(); n != 0 {
+ t.Fatalf("empty queue has cap %d; want 0", n)
+ }
+
+ // As we add elements, len should grow.
+ N := 32
+ for i := 0; i < N; i++ {
+ q.enqueue(i)
+ if n := q.len; n != i+1 {
+ t.Fatalf("after adding %d elements, queue has len %d", i, n)
+ }
+ if v, ok := q.peek(); !ok {
+ t.Fatalf("couldn't peek after adding %d elements", i)
+ } else if v.(int) != 0 {
+ t.Fatalf("after adding %d elements, peek is %d; want 0", i, v)
+ }
+ }
+
+ // As we remove and add elements, len should shrink and grow.
+ // We should also remove elements in the same order they were added.
+ want := 0
+ for _, r := range []int{1, 2, 3, 5, 8, 13, 21} {
+ s := make([]int, 0, r)
+ for i := 0; i < r; i++ {
+ if got, ok := q.dequeue(); !ok {
+ t.Fatalf("after removing %d of %d elements, could not dequeue", i+1, r)
+ } else if got != want {
+ t.Fatalf("after removing %d of %d elements, got %d; want %d", i+1, r, got, want)
+ } else {
+ s = append(s, got.(int))
+ }
+ want = (want + 1) % N
+ if n := q.len; n != N-i-1 {
+ t.Fatalf("after removing %d of %d elements, len is %d; want %d", i+1, r, n, N-i-1)
+ }
+ }
+ for i, v := range s {
+ q.enqueue(v)
+ if n := q.len; n != N-r+i+1 {
+ t.Fatalf("after adding back %d of %d elements, len is %d; want %d", i+1, r, n, n-r+i+1)
+ }
+ }
+ }
+}
diff --git a/src/internal/fuzz/sys_posix.go b/src/internal/fuzz/sys_posix.go
new file mode 100644
index 0000000..fec6054
--- /dev/null
+++ b/src/internal/fuzz/sys_posix.go
@@ -0,0 +1,130 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+//go:build darwin || freebsd || linux
+
+package fuzz
+
+import (
+ "fmt"
+ "os"
+ "os/exec"
+ "syscall"
+)
+
+type sharedMemSys struct{}
+
+func sharedMemMapFile(f *os.File, size int, removeOnClose bool) (*sharedMem, error) {
+ prot := syscall.PROT_READ | syscall.PROT_WRITE
+ flags := syscall.MAP_FILE | syscall.MAP_SHARED
+ region, err := syscall.Mmap(int(f.Fd()), 0, size, prot, flags)
+ if err != nil {
+ return nil, err
+ }
+
+ return &sharedMem{f: f, region: region, removeOnClose: removeOnClose}, nil
+}
+
+// Close unmaps the shared memory and closes the temporary file. If this
+// sharedMem was created with sharedMemTempFile, Close also removes the file.
+func (m *sharedMem) Close() error {
+ // Attempt all operations, even if we get an error for an earlier operation.
+ // os.File.Close may fail due to I/O errors, but we still want to delete
+ // the temporary file.
+ var errs []error
+ errs = append(errs,
+ syscall.Munmap(m.region),
+ m.f.Close())
+ if m.removeOnClose {
+ errs = append(errs, os.Remove(m.f.Name()))
+ }
+ for _, err := range errs {
+ if err != nil {
+ return err
+ }
+ }
+ return nil
+}
+
+// setWorkerComm configures communication channels on the cmd that will
+// run a worker process.
+func setWorkerComm(cmd *exec.Cmd, comm workerComm) {
+ mem := <-comm.memMu
+ memFile := mem.f
+ comm.memMu <- mem
+ cmd.ExtraFiles = []*os.File{comm.fuzzIn, comm.fuzzOut, memFile}
+}
+
+// getWorkerComm returns communication channels in the worker process.
+func getWorkerComm() (comm workerComm, err error) {
+ fuzzIn := os.NewFile(3, "fuzz_in")
+ fuzzOut := os.NewFile(4, "fuzz_out")
+ memFile := os.NewFile(5, "fuzz_mem")
+ fi, err := memFile.Stat()
+ if err != nil {
+ return workerComm{}, err
+ }
+ size := int(fi.Size())
+ if int64(size) != fi.Size() {
+ return workerComm{}, fmt.Errorf("fuzz temp file exceeds maximum size")
+ }
+ removeOnClose := false
+ mem, err := sharedMemMapFile(memFile, size, removeOnClose)
+ if err != nil {
+ return workerComm{}, err
+ }
+ memMu := make(chan *sharedMem, 1)
+ memMu <- mem
+ return workerComm{fuzzIn: fuzzIn, fuzzOut: fuzzOut, memMu: memMu}, nil
+}
+
+// isInterruptError returns whether an error was returned by a process that
+// was terminated by an interrupt signal (SIGINT).
+func isInterruptError(err error) bool {
+ exitErr, ok := err.(*exec.ExitError)
+ if !ok || exitErr.ExitCode() >= 0 {
+ return false
+ }
+ status := exitErr.Sys().(syscall.WaitStatus)
+ return status.Signal() == syscall.SIGINT
+}
+
+// terminationSignal checks if err is an exec.ExitError with a signal status.
+// If it is, terminationSignal returns the signal and true.
+// If not, -1 and false.
+func terminationSignal(err error) (os.Signal, bool) {
+ exitErr, ok := err.(*exec.ExitError)
+ if !ok || exitErr.ExitCode() >= 0 {
+ return syscall.Signal(-1), false
+ }
+ status := exitErr.Sys().(syscall.WaitStatus)
+ return status.Signal(), status.Signaled()
+}
+
+// isCrashSignal returns whether a signal was likely to have been caused by an
+// error in the program that received it, triggered by a fuzz input. For
+// example, SIGSEGV would be received after a nil pointer dereference.
+// Other signals like SIGKILL or SIGHUP are more likely to have been sent by
+// another process, and we shouldn't record a crasher if the worker process
+// receives one of these.
+//
+// Note that Go installs its own signal handlers on startup, so some of these
+// signals may only be received if signal handlers are changed. For example,
+// SIGSEGV is normally transformed into a panic that causes the process to exit
+// with status 2 if not recovered, which we handle as a crash.
+func isCrashSignal(signal os.Signal) bool {
+ switch signal {
+ case
+ syscall.SIGILL, // illegal instruction
+ syscall.SIGTRAP, // breakpoint
+ syscall.SIGABRT, // abort() called
+ syscall.SIGBUS, // invalid memory access (e.g., misaligned address)
+ syscall.SIGFPE, // math error, e.g., integer divide by zero
+ syscall.SIGSEGV, // invalid memory access (e.g., write to read-only)
+ syscall.SIGPIPE: // sent data to closed pipe or socket
+ return true
+ default:
+ return false
+ }
+}
diff --git a/src/internal/fuzz/sys_unimplemented.go b/src/internal/fuzz/sys_unimplemented.go
new file mode 100644
index 0000000..8687c1f
--- /dev/null
+++ b/src/internal/fuzz/sys_unimplemented.go
@@ -0,0 +1,44 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// If you update this constraint, also update internal/platform.FuzzSupported.
+//
+//go:build !darwin && !freebsd && !linux && !windows
+
+package fuzz
+
+import (
+ "os"
+ "os/exec"
+)
+
+type sharedMemSys struct{}
+
+func sharedMemMapFile(f *os.File, size int, removeOnClose bool) (*sharedMem, error) {
+ panic("not implemented")
+}
+
+func (m *sharedMem) Close() error {
+ panic("not implemented")
+}
+
+func setWorkerComm(cmd *exec.Cmd, comm workerComm) {
+ panic("not implemented")
+}
+
+func getWorkerComm() (comm workerComm, err error) {
+ panic("not implemented")
+}
+
+func isInterruptError(err error) bool {
+ panic("not implemented")
+}
+
+func terminationSignal(err error) (os.Signal, bool) {
+ panic("not implemented")
+}
+
+func isCrashSignal(signal os.Signal) bool {
+ panic("not implemented")
+}
diff --git a/src/internal/fuzz/sys_windows.go b/src/internal/fuzz/sys_windows.go
new file mode 100644
index 0000000..aa85be7
--- /dev/null
+++ b/src/internal/fuzz/sys_windows.go
@@ -0,0 +1,147 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fuzz
+
+import (
+ "fmt"
+ "os"
+ "os/exec"
+ "syscall"
+ "unsafe"
+)
+
+type sharedMemSys struct {
+ mapObj syscall.Handle
+}
+
+func sharedMemMapFile(f *os.File, size int, removeOnClose bool) (mem *sharedMem, err error) {
+ defer func() {
+ if err != nil {
+ err = fmt.Errorf("mapping temporary file %s: %w", f.Name(), err)
+ }
+ }()
+
+ // Create a file mapping object. The object itself is not shared.
+ mapObj, err := syscall.CreateFileMapping(
+ syscall.Handle(f.Fd()), // fhandle
+ nil, // sa
+ syscall.PAGE_READWRITE, // prot
+ 0, // maxSizeHigh
+ 0, // maxSizeLow
+ nil, // name
+ )
+ if err != nil {
+ return nil, err
+ }
+
+ // Create a view from the file mapping object.
+ access := uint32(syscall.FILE_MAP_READ | syscall.FILE_MAP_WRITE)
+ addr, err := syscall.MapViewOfFile(
+ mapObj, // handle
+ access, // access
+ 0, // offsetHigh
+ 0, // offsetLow
+ uintptr(size), // length
+ )
+ if err != nil {
+ syscall.CloseHandle(mapObj)
+ return nil, err
+ }
+
+ region := unsafe.Slice((*byte)(unsafe.Pointer(addr)), size)
+ return &sharedMem{
+ f: f,
+ region: region,
+ removeOnClose: removeOnClose,
+ sys: sharedMemSys{mapObj: mapObj},
+ }, nil
+}
+
+// Close unmaps the shared memory and closes the temporary file. If this
+// sharedMem was created with sharedMemTempFile, Close also removes the file.
+func (m *sharedMem) Close() error {
+ // Attempt all operations, even if we get an error for an earlier operation.
+ // os.File.Close may fail due to I/O errors, but we still want to delete
+ // the temporary file.
+ var errs []error
+ errs = append(errs,
+ syscall.UnmapViewOfFile(uintptr(unsafe.Pointer(&m.region[0]))),
+ syscall.CloseHandle(m.sys.mapObj),
+ m.f.Close())
+ if m.removeOnClose {
+ errs = append(errs, os.Remove(m.f.Name()))
+ }
+ for _, err := range errs {
+ if err != nil {
+ return err
+ }
+ }
+ return nil
+}
+
+// setWorkerComm configures communication channels on the cmd that will
+// run a worker process.
+func setWorkerComm(cmd *exec.Cmd, comm workerComm) {
+ mem := <-comm.memMu
+ memName := mem.f.Name()
+ comm.memMu <- mem
+ syscall.SetHandleInformation(syscall.Handle(comm.fuzzIn.Fd()), syscall.HANDLE_FLAG_INHERIT, 1)
+ syscall.SetHandleInformation(syscall.Handle(comm.fuzzOut.Fd()), syscall.HANDLE_FLAG_INHERIT, 1)
+ cmd.Env = append(cmd.Env, fmt.Sprintf("GO_TEST_FUZZ_WORKER_HANDLES=%x,%x,%q", comm.fuzzIn.Fd(), comm.fuzzOut.Fd(), memName))
+ cmd.SysProcAttr = &syscall.SysProcAttr{AdditionalInheritedHandles: []syscall.Handle{syscall.Handle(comm.fuzzIn.Fd()), syscall.Handle(comm.fuzzOut.Fd())}}
+}
+
+// getWorkerComm returns communication channels in the worker process.
+func getWorkerComm() (comm workerComm, err error) {
+ v := os.Getenv("GO_TEST_FUZZ_WORKER_HANDLES")
+ if v == "" {
+ return workerComm{}, fmt.Errorf("GO_TEST_FUZZ_WORKER_HANDLES not set")
+ }
+ var fuzzInFD, fuzzOutFD uintptr
+ var memName string
+ if _, err := fmt.Sscanf(v, "%x,%x,%q", &fuzzInFD, &fuzzOutFD, &memName); err != nil {
+ return workerComm{}, fmt.Errorf("parsing GO_TEST_FUZZ_WORKER_HANDLES=%s: %v", v, err)
+ }
+
+ fuzzIn := os.NewFile(fuzzInFD, "fuzz_in")
+ fuzzOut := os.NewFile(fuzzOutFD, "fuzz_out")
+ tmpFile, err := os.OpenFile(memName, os.O_RDWR, 0)
+ if err != nil {
+ return workerComm{}, fmt.Errorf("worker opening temp file: %w", err)
+ }
+ fi, err := tmpFile.Stat()
+ if err != nil {
+ return workerComm{}, fmt.Errorf("worker checking temp file size: %w", err)
+ }
+ size := int(fi.Size())
+ if int64(size) != fi.Size() {
+ return workerComm{}, fmt.Errorf("fuzz temp file exceeds maximum size")
+ }
+ removeOnClose := false
+ mem, err := sharedMemMapFile(tmpFile, size, removeOnClose)
+ if err != nil {
+ return workerComm{}, err
+ }
+ memMu := make(chan *sharedMem, 1)
+ memMu <- mem
+
+ return workerComm{fuzzIn: fuzzIn, fuzzOut: fuzzOut, memMu: memMu}, nil
+}
+
+func isInterruptError(err error) bool {
+ // On Windows, we can't tell whether the process was interrupted by the error
+ // returned by Wait. It looks like an ExitError with status 1.
+ return false
+}
+
+// terminationSignal returns -1 and false because Windows doesn't have signals.
+func terminationSignal(err error) (os.Signal, bool) {
+ return syscall.Signal(-1), false
+}
+
+// isCrashSignal is not implemented because Windows doesn't have signals.
+func isCrashSignal(signal os.Signal) bool {
+ panic("not implemented: no signals on windows")
+}
diff --git a/src/internal/fuzz/trace.go b/src/internal/fuzz/trace.go
new file mode 100644
index 0000000..a15c370
--- /dev/null
+++ b/src/internal/fuzz/trace.go
@@ -0,0 +1,35 @@
+// Copyright 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+//go:build !libfuzzer
+
+package fuzz
+
+import _ "unsafe" // for go:linkname
+
+//go:linkname libfuzzerTraceCmp1 runtime.libfuzzerTraceCmp1
+//go:linkname libfuzzerTraceCmp2 runtime.libfuzzerTraceCmp2
+//go:linkname libfuzzerTraceCmp4 runtime.libfuzzerTraceCmp4
+//go:linkname libfuzzerTraceCmp8 runtime.libfuzzerTraceCmp8
+
+//go:linkname libfuzzerTraceConstCmp1 runtime.libfuzzerTraceConstCmp1
+//go:linkname libfuzzerTraceConstCmp2 runtime.libfuzzerTraceConstCmp2
+//go:linkname libfuzzerTraceConstCmp4 runtime.libfuzzerTraceConstCmp4
+//go:linkname libfuzzerTraceConstCmp8 runtime.libfuzzerTraceConstCmp8
+
+//go:linkname libfuzzerHookStrCmp runtime.libfuzzerHookStrCmp
+//go:linkname libfuzzerHookEqualFold runtime.libfuzzerHookEqualFold
+
+func libfuzzerTraceCmp1(arg0, arg1 uint8, fakePC uint) {}
+func libfuzzerTraceCmp2(arg0, arg1 uint16, fakePC uint) {}
+func libfuzzerTraceCmp4(arg0, arg1 uint32, fakePC uint) {}
+func libfuzzerTraceCmp8(arg0, arg1 uint64, fakePC uint) {}
+
+func libfuzzerTraceConstCmp1(arg0, arg1 uint8, fakePC uint) {}
+func libfuzzerTraceConstCmp2(arg0, arg1 uint16, fakePC uint) {}
+func libfuzzerTraceConstCmp4(arg0, arg1 uint32, fakePC uint) {}
+func libfuzzerTraceConstCmp8(arg0, arg1 uint64, fakePC uint) {}
+
+func libfuzzerHookStrCmp(arg0, arg1 string, fakePC uint) {}
+func libfuzzerHookEqualFold(arg0, arg1 string, fakePC uint) {}
diff --git a/src/internal/fuzz/worker.go b/src/internal/fuzz/worker.go
new file mode 100644
index 0000000..467c39b
--- /dev/null
+++ b/src/internal/fuzz/worker.go
@@ -0,0 +1,1184 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fuzz
+
+import (
+ "bytes"
+ "context"
+ "crypto/sha256"
+ "encoding/json"
+ "errors"
+ "fmt"
+ "io"
+ "os"
+ "os/exec"
+ "reflect"
+ "runtime"
+ "sync"
+ "time"
+)
+
+const (
+ // workerFuzzDuration is the amount of time a worker can spend testing random
+ // variations of an input given by the coordinator.
+ workerFuzzDuration = 100 * time.Millisecond
+
+ // workerTimeoutDuration is the amount of time a worker can go without
+ // responding to the coordinator before being stopped.
+ workerTimeoutDuration = 1 * time.Second
+
+ // workerExitCode is used as an exit code by fuzz worker processes after an internal error.
+ // This distinguishes internal errors from uncontrolled panics and other crashes.
+ // Keep in sync with internal/fuzz.workerExitCode.
+ workerExitCode = 70
+
+ // workerSharedMemSize is the maximum size of the shared memory file used to
+ // communicate with workers. This limits the size of fuzz inputs.
+ workerSharedMemSize = 100 << 20 // 100 MB
+)
+
+// worker manages a worker process running a test binary. The worker object
+// exists only in the coordinator (the process started by 'go test -fuzz').
+// workerClient is used by the coordinator to send RPCs to the worker process,
+// which handles them with workerServer.
+type worker struct {
+ dir string // working directory, same as package directory
+ binPath string // path to test executable
+ args []string // arguments for test executable
+ env []string // environment for test executable
+
+ coordinator *coordinator
+
+ memMu chan *sharedMem // mutex guarding shared memory with worker; persists across processes.
+
+ cmd *exec.Cmd // current worker process
+ client *workerClient // used to communicate with worker process
+ waitErr error // last error returned by wait, set before termC is closed.
+ interrupted bool // true after stop interrupts a running worker.
+ termC chan struct{} // closed by wait when worker process terminates
+}
+
+func newWorker(c *coordinator, dir, binPath string, args, env []string) (*worker, error) {
+ mem, err := sharedMemTempFile(workerSharedMemSize)
+ if err != nil {
+ return nil, err
+ }
+ memMu := make(chan *sharedMem, 1)
+ memMu <- mem
+ return &worker{
+ dir: dir,
+ binPath: binPath,
+ args: args,
+ env: env[:len(env):len(env)], // copy on append to ensure workers don't overwrite each other.
+ coordinator: c,
+ memMu: memMu,
+ }, nil
+}
+
+// cleanup releases persistent resources associated with the worker.
+func (w *worker) cleanup() error {
+ mem := <-w.memMu
+ if mem == nil {
+ return nil
+ }
+ close(w.memMu)
+ return mem.Close()
+}
+
+// coordinate runs the test binary to perform fuzzing.
+//
+// coordinate loops until ctx is cancelled or a fatal error is encountered.
+// If a test process terminates unexpectedly while fuzzing, coordinate will
+// attempt to restart and continue unless the termination can be attributed
+// to an interruption (from a timer or the user).
+//
+// While looping, coordinate receives inputs from the coordinator, passes
+// those inputs to the worker process, then passes the results back to
+// the coordinator.
+func (w *worker) coordinate(ctx context.Context) error {
+ // Main event loop.
+ for {
+ // Start or restart the worker if it's not running.
+ if !w.isRunning() {
+ if err := w.startAndPing(ctx); err != nil {
+ return err
+ }
+ }
+
+ select {
+ case <-ctx.Done():
+ // Worker was told to stop.
+ err := w.stop()
+ if err != nil && !w.interrupted && !isInterruptError(err) {
+ return err
+ }
+ return ctx.Err()
+
+ case <-w.termC:
+ // Worker process terminated unexpectedly while waiting for input.
+ err := w.stop()
+ if w.interrupted {
+ panic("worker interrupted after unexpected termination")
+ }
+ if err == nil || isInterruptError(err) {
+ // Worker stopped, either by exiting with status 0 or after being
+ // interrupted with a signal that was not sent by the coordinator.
+ //
+ // When the user presses ^C, on POSIX platforms, SIGINT is delivered to
+ // all processes in the group concurrently, and the worker may see it
+ // before the coordinator. The worker should exit 0 gracefully (in
+ // theory).
+ //
+ // This condition is probably intended by the user, so suppress
+ // the error.
+ return nil
+ }
+ if exitErr, ok := err.(*exec.ExitError); ok && exitErr.ExitCode() == workerExitCode {
+ // Worker exited with a code indicating F.Fuzz was not called correctly,
+ // for example, F.Fail was called first.
+ return fmt.Errorf("fuzzing process exited unexpectedly due to an internal failure: %w", err)
+ }
+ // Worker exited non-zero or was terminated by a non-interrupt
+ // signal (for example, SIGSEGV) while fuzzing.
+ return fmt.Errorf("fuzzing process hung or terminated unexpectedly: %w", err)
+ // TODO(jayconrod,katiehockman): if -keepfuzzing, restart worker.
+
+ case input := <-w.coordinator.inputC:
+ // Received input from coordinator.
+ args := fuzzArgs{
+ Limit: input.limit,
+ Timeout: input.timeout,
+ Warmup: input.warmup,
+ CoverageData: input.coverageData,
+ }
+ entry, resp, isInternalError, err := w.client.fuzz(ctx, input.entry, args)
+ canMinimize := true
+ if err != nil {
+ // Error communicating with worker.
+ w.stop()
+ if ctx.Err() != nil {
+ // Timeout or interruption.
+ return ctx.Err()
+ }
+ if w.interrupted {
+ // Communication error before we stopped the worker.
+ // Report an error, but don't record a crasher.
+ return fmt.Errorf("communicating with fuzzing process: %v", err)
+ }
+ if sig, ok := terminationSignal(w.waitErr); ok && !isCrashSignal(sig) {
+ // Worker terminated by a signal that probably wasn't caused by a
+ // specific input to the fuzz function. For example, on Linux,
+ // the kernel (OOM killer) may send SIGKILL to a process using a lot
+ // of memory. Or the shell might send SIGHUP when the terminal
+ // is closed. Don't record a crasher.
+ return fmt.Errorf("fuzzing process terminated by unexpected signal; no crash will be recorded: %v", w.waitErr)
+ }
+ if isInternalError {
+ // An internal error occurred which shouldn't be considered
+ // a crash.
+ return err
+ }
+ // Unexpected termination. Set error message and fall through.
+ // We'll restart the worker on the next iteration.
+ // Don't attempt to minimize this since it crashed the worker.
+ resp.Err = fmt.Sprintf("fuzzing process hung or terminated unexpectedly: %v", w.waitErr)
+ canMinimize = false
+ }
+ result := fuzzResult{
+ limit: input.limit,
+ count: resp.Count,
+ totalDuration: resp.TotalDuration,
+ entryDuration: resp.InterestingDuration,
+ entry: entry,
+ crasherMsg: resp.Err,
+ coverageData: resp.CoverageData,
+ canMinimize: canMinimize,
+ }
+ w.coordinator.resultC <- result
+
+ case input := <-w.coordinator.minimizeC:
+ // Received input to minimize from coordinator.
+ result, err := w.minimize(ctx, input)
+ if err != nil {
+ // Error minimizing. Send back the original input. If it didn't cause
+ // an error before, report it as causing an error now.
+ // TODO: double-check this is handled correctly when
+ // implementing -keepfuzzing.
+ result = fuzzResult{
+ entry: input.entry,
+ crasherMsg: input.crasherMsg,
+ canMinimize: false,
+ limit: input.limit,
+ }
+ if result.crasherMsg == "" {
+ result.crasherMsg = err.Error()
+ }
+ }
+ w.coordinator.resultC <- result
+ }
+ }
+}
+
+// minimize tells a worker process to attempt to find a smaller value that
+// either causes an error (if we started minimizing because we found an input
+// that causes an error) or preserves new coverage (if we started minimizing
+// because we found an input that expands coverage).
+func (w *worker) minimize(ctx context.Context, input fuzzMinimizeInput) (min fuzzResult, err error) {
+ if w.coordinator.opts.MinimizeTimeout != 0 {
+ var cancel func()
+ ctx, cancel = context.WithTimeout(ctx, w.coordinator.opts.MinimizeTimeout)
+ defer cancel()
+ }
+
+ args := minimizeArgs{
+ Limit: input.limit,
+ Timeout: input.timeout,
+ KeepCoverage: input.keepCoverage,
+ }
+ entry, resp, err := w.client.minimize(ctx, input.entry, args)
+ if err != nil {
+ // Error communicating with worker.
+ w.stop()
+ if ctx.Err() != nil || w.interrupted || isInterruptError(w.waitErr) {
+ // Worker was interrupted, possibly by the user pressing ^C.
+ // Normally, workers can handle interrupts and timeouts gracefully and
+ // will return without error. An error here indicates the worker
+ // may not have been in a good state, but the error won't be meaningful
+ // to the user. Just return the original crasher without logging anything.
+ return fuzzResult{
+ entry: input.entry,
+ crasherMsg: input.crasherMsg,
+ coverageData: input.keepCoverage,
+ canMinimize: false,
+ limit: input.limit,
+ }, nil
+ }
+ return fuzzResult{
+ entry: entry,
+ crasherMsg: fmt.Sprintf("fuzzing process hung or terminated unexpectedly while minimizing: %v", err),
+ canMinimize: false,
+ limit: input.limit,
+ count: resp.Count,
+ totalDuration: resp.Duration,
+ }, nil
+ }
+
+ if input.crasherMsg != "" && resp.Err == "" {
+ return fuzzResult{}, fmt.Errorf("attempted to minimize a crash but could not reproduce")
+ }
+
+ return fuzzResult{
+ entry: entry,
+ crasherMsg: resp.Err,
+ coverageData: resp.CoverageData,
+ canMinimize: false,
+ limit: input.limit,
+ count: resp.Count,
+ totalDuration: resp.Duration,
+ }, nil
+}
+
+func (w *worker) isRunning() bool {
+ return w.cmd != nil
+}
+
+// startAndPing starts the worker process and sends it a message to make sure it
+// can communicate.
+//
+// startAndPing returns an error if any part of this didn't work, including if
+// the context is expired or the worker process was interrupted before it
+// responded. Errors that happen after start but before the ping response
+// likely indicate that the worker did not call F.Fuzz or called F.Fail first.
+// We don't record crashers for these errors.
+func (w *worker) startAndPing(ctx context.Context) error {
+ if ctx.Err() != nil {
+ return ctx.Err()
+ }
+ if err := w.start(); err != nil {
+ return err
+ }
+ if err := w.client.ping(ctx); err != nil {
+ w.stop()
+ if ctx.Err() != nil {
+ return ctx.Err()
+ }
+ if isInterruptError(err) {
+ // User may have pressed ^C before worker responded.
+ return err
+ }
+ // TODO: record and return stderr.
+ return fmt.Errorf("fuzzing process terminated without fuzzing: %w", err)
+ }
+ return nil
+}
+
+// start runs a new worker process.
+//
+// If the process couldn't be started, start returns an error. Start won't
+// return later termination errors from the process if they occur.
+//
+// If the process starts successfully, start returns nil. stop must be called
+// once later to clean up, even if the process terminates on its own.
+//
+// When the process terminates, w.waitErr is set to the error (if any), and
+// w.termC is closed.
+func (w *worker) start() (err error) {
+ if w.isRunning() {
+ panic("worker already started")
+ }
+ w.waitErr = nil
+ w.interrupted = false
+ w.termC = nil
+
+ cmd := exec.Command(w.binPath, w.args...)
+ cmd.Dir = w.dir
+ cmd.Env = w.env[:len(w.env):len(w.env)] // copy on append to ensure workers don't overwrite each other.
+
+ // Create the "fuzz_in" and "fuzz_out" pipes so we can communicate with
+ // the worker. We don't use stdin and stdout, since the test binary may
+ // do something else with those.
+ //
+ // Each pipe has a reader and a writer. The coordinator writes to fuzzInW
+ // and reads from fuzzOutR. The worker inherits fuzzInR and fuzzOutW.
+ // The coordinator closes fuzzInR and fuzzOutW after starting the worker,
+ // since we have no further need of them.
+ fuzzInR, fuzzInW, err := os.Pipe()
+ if err != nil {
+ return err
+ }
+ defer fuzzInR.Close()
+ fuzzOutR, fuzzOutW, err := os.Pipe()
+ if err != nil {
+ fuzzInW.Close()
+ return err
+ }
+ defer fuzzOutW.Close()
+ setWorkerComm(cmd, workerComm{fuzzIn: fuzzInR, fuzzOut: fuzzOutW, memMu: w.memMu})
+
+ // Start the worker process.
+ if err := cmd.Start(); err != nil {
+ fuzzInW.Close()
+ fuzzOutR.Close()
+ return err
+ }
+
+ // Worker started successfully.
+ // After this, w.client owns fuzzInW and fuzzOutR, so w.client.Close must be
+ // called later by stop.
+ w.cmd = cmd
+ w.termC = make(chan struct{})
+ comm := workerComm{fuzzIn: fuzzInW, fuzzOut: fuzzOutR, memMu: w.memMu}
+ m := newMutator()
+ w.client = newWorkerClient(comm, m)
+
+ go func() {
+ w.waitErr = w.cmd.Wait()
+ close(w.termC)
+ }()
+
+ return nil
+}
+
+// stop tells the worker process to exit by closing w.client, then blocks until
+// it terminates. If the worker doesn't terminate after a short time, stop
+// signals it with os.Interrupt (where supported), then os.Kill.
+//
+// stop returns the error the process terminated with, if any (same as
+// w.waitErr).
+//
+// stop must be called at least once after start returns successfully, even if
+// the worker process terminates unexpectedly.
+func (w *worker) stop() error {
+ if w.termC == nil {
+ panic("worker was not started successfully")
+ }
+ select {
+ case <-w.termC:
+ // Worker already terminated.
+ if w.client == nil {
+ // stop already called.
+ return w.waitErr
+ }
+ // Possible unexpected termination.
+ w.client.Close()
+ w.cmd = nil
+ w.client = nil
+ return w.waitErr
+ default:
+ // Worker still running.
+ }
+
+ // Tell the worker to stop by closing fuzz_in. It won't actually stop until it
+ // finishes with earlier calls.
+ closeC := make(chan struct{})
+ go func() {
+ w.client.Close()
+ close(closeC)
+ }()
+
+ sig := os.Interrupt
+ if runtime.GOOS == "windows" {
+ // Per https://golang.org/pkg/os/#Signal, “Interrupt is not implemented on
+ // Windows; using it with os.Process.Signal will return an error.”
+ // Fall back to Kill instead.
+ sig = os.Kill
+ }
+
+ t := time.NewTimer(workerTimeoutDuration)
+ for {
+ select {
+ case <-w.termC:
+ // Worker terminated.
+ t.Stop()
+ <-closeC
+ w.cmd = nil
+ w.client = nil
+ return w.waitErr
+
+ case <-t.C:
+ // Timer fired before worker terminated.
+ w.interrupted = true
+ switch sig {
+ case os.Interrupt:
+ // Try to stop the worker with SIGINT and wait a little longer.
+ w.cmd.Process.Signal(sig)
+ sig = os.Kill
+ t.Reset(workerTimeoutDuration)
+
+ case os.Kill:
+ // Try to stop the worker with SIGKILL and keep waiting.
+ w.cmd.Process.Signal(sig)
+ sig = nil
+ t.Reset(workerTimeoutDuration)
+
+ case nil:
+ // Still waiting. Print a message to let the user know why.
+ fmt.Fprintf(w.coordinator.opts.Log, "waiting for fuzzing process to terminate...\n")
+ }
+ }
+ }
+}
+
+// RunFuzzWorker is called in a worker process to communicate with the
+// coordinator process in order to fuzz random inputs. RunFuzzWorker loops
+// until the coordinator tells it to stop.
+//
+// fn is a wrapper on the fuzz function. It may return an error to indicate
+// a given input "crashed". The coordinator will also record a crasher if
+// the function times out or terminates the process.
+//
+// RunFuzzWorker returns an error if it could not communicate with the
+// coordinator process.
+func RunFuzzWorker(ctx context.Context, fn func(CorpusEntry) error) error {
+ comm, err := getWorkerComm()
+ if err != nil {
+ return err
+ }
+ srv := &workerServer{
+ workerComm: comm,
+ fuzzFn: func(e CorpusEntry) (time.Duration, error) {
+ timer := time.AfterFunc(10*time.Second, func() {
+ panic("deadlocked!") // this error message won't be printed
+ })
+ defer timer.Stop()
+ start := time.Now()
+ err := fn(e)
+ return time.Since(start), err
+ },
+ m: newMutator(),
+ }
+ return srv.serve(ctx)
+}
+
+// call is serialized and sent from the coordinator on fuzz_in. It acts as
+// a minimalist RPC mechanism. Exactly one of its fields must be set to indicate
+// which method to call.
+type call struct {
+ Ping *pingArgs
+ Fuzz *fuzzArgs
+ Minimize *minimizeArgs
+}
+
+// minimizeArgs contains arguments to workerServer.minimize. The value to
+// minimize is already in shared memory.
+type minimizeArgs struct {
+ // Timeout is the time to spend minimizing. This may include time to start up,
+ // especially if the input causes the worker process to terminated, requiring
+ // repeated restarts.
+ Timeout time.Duration
+
+ // Limit is the maximum number of values to test, without spending more time
+ // than Duration. 0 indicates no limit.
+ Limit int64
+
+ // KeepCoverage is a set of coverage counters the worker should attempt to
+ // keep in minimized values. When provided, the worker will reject inputs that
+ // don't cause at least one of these bits to be set.
+ KeepCoverage []byte
+
+ // Index is the index of the fuzz target parameter to be minimized.
+ Index int
+}
+
+// minimizeResponse contains results from workerServer.minimize.
+type minimizeResponse struct {
+ // WroteToMem is true if the worker found a smaller input and wrote it to
+ // shared memory. If minimizeArgs.KeepCoverage was set, the minimized input
+ // preserved at least one coverage bit and did not cause an error.
+ // Otherwise, the minimized input caused some error, recorded in Err.
+ WroteToMem bool
+
+ // Err is the error string caused by the value in shared memory, if any.
+ Err string
+
+ // CoverageData is the set of coverage bits activated by the minimized value
+ // in shared memory. When set, it contains at least one bit from KeepCoverage.
+ // CoverageData will be nil if Err is set or if minimization failed.
+ CoverageData []byte
+
+ // Duration is the time spent minimizing, not including starting or cleaning up.
+ Duration time.Duration
+
+ // Count is the number of values tested.
+ Count int64
+}
+
+// fuzzArgs contains arguments to workerServer.fuzz. The value to fuzz is
+// passed in shared memory.
+type fuzzArgs struct {
+ // Timeout is the time to spend fuzzing, not including starting or
+ // cleaning up.
+ Timeout time.Duration
+
+ // Limit is the maximum number of values to test, without spending more time
+ // than Duration. 0 indicates no limit.
+ Limit int64
+
+ // Warmup indicates whether this is part of a warmup run, meaning that
+ // fuzzing should not occur. If coverageEnabled is true, then coverage data
+ // should be reported.
+ Warmup bool
+
+ // CoverageData is the coverage data. If set, the worker should update its
+ // local coverage data prior to fuzzing.
+ CoverageData []byte
+}
+
+// fuzzResponse contains results from workerServer.fuzz.
+type fuzzResponse struct {
+ // Duration is the time spent fuzzing, not including starting or cleaning up.
+ TotalDuration time.Duration
+ InterestingDuration time.Duration
+
+ // Count is the number of values tested.
+ Count int64
+
+ // CoverageData is set if the value in shared memory expands coverage
+ // and therefore may be interesting to the coordinator.
+ CoverageData []byte
+
+ // Err is the error string caused by the value in shared memory, which is
+ // non-empty if the value in shared memory caused a crash.
+ Err string
+
+ // InternalErr is the error string caused by an internal error in the
+ // worker. This shouldn't be considered a crasher.
+ InternalErr string
+}
+
+// pingArgs contains arguments to workerServer.ping.
+type pingArgs struct{}
+
+// pingResponse contains results from workerServer.ping.
+type pingResponse struct{}
+
+// workerComm holds pipes and shared memory used for communication
+// between the coordinator process (client) and a worker process (server).
+// These values are unique to each worker; they are shared only with the
+// coordinator, not with other workers.
+//
+// Access to shared memory is synchronized implicitly over the RPC protocol
+// implemented in workerServer and workerClient. During a call, the client
+// (worker) has exclusive access to shared memory; at other times, the server
+// (coordinator) has exclusive access.
+type workerComm struct {
+ fuzzIn, fuzzOut *os.File
+ memMu chan *sharedMem // mutex guarding shared memory
+}
+
+// workerServer is a minimalist RPC server, run by fuzz worker processes.
+// It allows the coordinator process (using workerClient) to call methods in a
+// worker process. This system allows the coordinator to run multiple worker
+// processes in parallel and to collect inputs that caused crashes from shared
+// memory after a worker process terminates unexpectedly.
+type workerServer struct {
+ workerComm
+ m *mutator
+
+ // coverageMask is the local coverage data for the worker. It is
+ // periodically updated to reflect the data in the coordinator when new
+ // coverage is found.
+ coverageMask []byte
+
+ // fuzzFn runs the worker's fuzz target on the given input and returns an
+ // error if it finds a crasher (the process may also exit or crash), and the
+ // time it took to run the input. It sets a deadline of 10 seconds, at which
+ // point it will panic with the assumption that the process is hanging or
+ // deadlocked.
+ fuzzFn func(CorpusEntry) (time.Duration, error)
+}
+
+// serve reads serialized RPC messages on fuzzIn. When serve receives a message,
+// it calls the corresponding method, then sends the serialized result back
+// on fuzzOut.
+//
+// serve handles RPC calls synchronously; it will not attempt to read a message
+// until the previous call has finished.
+//
+// serve returns errors that occurred when communicating over pipes. serve
+// does not return errors from method calls; those are passed through serialized
+// responses.
+func (ws *workerServer) serve(ctx context.Context) error {
+ enc := json.NewEncoder(ws.fuzzOut)
+ dec := json.NewDecoder(&contextReader{ctx: ctx, r: ws.fuzzIn})
+ for {
+ var c call
+ if err := dec.Decode(&c); err != nil {
+ if err == io.EOF || err == ctx.Err() {
+ return nil
+ } else {
+ return err
+ }
+ }
+
+ var resp any
+ switch {
+ case c.Fuzz != nil:
+ resp = ws.fuzz(ctx, *c.Fuzz)
+ case c.Minimize != nil:
+ resp = ws.minimize(ctx, *c.Minimize)
+ case c.Ping != nil:
+ resp = ws.ping(ctx, *c.Ping)
+ default:
+ return errors.New("no arguments provided for any call")
+ }
+
+ if err := enc.Encode(resp); err != nil {
+ return err
+ }
+ }
+}
+
+// chainedMutations is how many mutations are applied before the worker
+// resets the input to it's original state.
+// NOTE: this number was picked without much thought. It is low enough that
+// it seems to create a significant diversity in mutated inputs. We may want
+// to consider looking into this more closely once we have a proper performance
+// testing framework. Another option is to randomly pick the number of chained
+// mutations on each invocation of the workerServer.fuzz method (this appears to
+// be what libFuzzer does, although there seems to be no documentation which
+// explains why this choice was made.)
+const chainedMutations = 5
+
+// fuzz runs the test function on random variations of the input value in shared
+// memory for a limited duration or number of iterations.
+//
+// fuzz returns early if it finds an input that crashes the fuzz function (with
+// fuzzResponse.Err set) or an input that expands coverage (with
+// fuzzResponse.InterestingDuration set).
+//
+// fuzz does not modify the input in shared memory. Instead, it saves the
+// initial PRNG state in shared memory and increments a counter in shared
+// memory before each call to the test function. The caller may reconstruct
+// the crashing input with this information, since the PRNG is deterministic.
+func (ws *workerServer) fuzz(ctx context.Context, args fuzzArgs) (resp fuzzResponse) {
+ if args.CoverageData != nil {
+ if ws.coverageMask != nil && len(args.CoverageData) != len(ws.coverageMask) {
+ resp.InternalErr = fmt.Sprintf("unexpected size for CoverageData: got %d, expected %d", len(args.CoverageData), len(ws.coverageMask))
+ return resp
+ }
+ ws.coverageMask = args.CoverageData
+ }
+ start := time.Now()
+ defer func() { resp.TotalDuration = time.Since(start) }()
+
+ if args.Timeout != 0 {
+ var cancel func()
+ ctx, cancel = context.WithTimeout(ctx, args.Timeout)
+ defer cancel()
+ }
+ mem := <-ws.memMu
+ ws.m.r.save(&mem.header().randState, &mem.header().randInc)
+ defer func() {
+ resp.Count = mem.header().count
+ ws.memMu <- mem
+ }()
+ if args.Limit > 0 && mem.header().count >= args.Limit {
+ resp.InternalErr = fmt.Sprintf("mem.header().count %d already exceeds args.Limit %d", mem.header().count, args.Limit)
+ return resp
+ }
+
+ originalVals, err := unmarshalCorpusFile(mem.valueCopy())
+ if err != nil {
+ resp.InternalErr = err.Error()
+ return resp
+ }
+ vals := make([]any, len(originalVals))
+ copy(vals, originalVals)
+
+ shouldStop := func() bool {
+ return args.Limit > 0 && mem.header().count >= args.Limit
+ }
+ fuzzOnce := func(entry CorpusEntry) (dur time.Duration, cov []byte, errMsg string) {
+ mem.header().count++
+ var err error
+ dur, err = ws.fuzzFn(entry)
+ if err != nil {
+ errMsg = err.Error()
+ if errMsg == "" {
+ errMsg = "fuzz function failed with no input"
+ }
+ return dur, nil, errMsg
+ }
+ if ws.coverageMask != nil && countNewCoverageBits(ws.coverageMask, coverageSnapshot) > 0 {
+ return dur, coverageSnapshot, ""
+ }
+ return dur, nil, ""
+ }
+
+ if args.Warmup {
+ dur, _, errMsg := fuzzOnce(CorpusEntry{Values: vals})
+ if errMsg != "" {
+ resp.Err = errMsg
+ return resp
+ }
+ resp.InterestingDuration = dur
+ if coverageEnabled {
+ resp.CoverageData = coverageSnapshot
+ }
+ return resp
+ }
+
+ for {
+ select {
+ case <-ctx.Done():
+ return resp
+ default:
+ if mem.header().count%chainedMutations == 0 {
+ copy(vals, originalVals)
+ ws.m.r.save(&mem.header().randState, &mem.header().randInc)
+ }
+ ws.m.mutate(vals, cap(mem.valueRef()))
+
+ entry := CorpusEntry{Values: vals}
+ dur, cov, errMsg := fuzzOnce(entry)
+ if errMsg != "" {
+ resp.Err = errMsg
+ return resp
+ }
+ if cov != nil {
+ resp.CoverageData = cov
+ resp.InterestingDuration = dur
+ return resp
+ }
+ if shouldStop() {
+ return resp
+ }
+ }
+ }
+}
+
+func (ws *workerServer) minimize(ctx context.Context, args minimizeArgs) (resp minimizeResponse) {
+ start := time.Now()
+ defer func() { resp.Duration = time.Since(start) }()
+ mem := <-ws.memMu
+ defer func() { ws.memMu <- mem }()
+ vals, err := unmarshalCorpusFile(mem.valueCopy())
+ if err != nil {
+ panic(err)
+ }
+ inpHash := sha256.Sum256(mem.valueCopy())
+ if args.Timeout != 0 {
+ var cancel func()
+ ctx, cancel = context.WithTimeout(ctx, args.Timeout)
+ defer cancel()
+ }
+
+ // Minimize the values in vals, then write to shared memory. We only write
+ // to shared memory after completing minimization.
+ success, err := ws.minimizeInput(ctx, vals, mem, args)
+ if success {
+ writeToMem(vals, mem)
+ outHash := sha256.Sum256(mem.valueCopy())
+ mem.header().rawInMem = false
+ resp.WroteToMem = true
+ if err != nil {
+ resp.Err = err.Error()
+ } else {
+ // If the values didn't change during minimization then coverageSnapshot is likely
+ // a dirty snapshot which represents the very last step of minimization, not the
+ // coverage for the initial input. In that case just return the coverage we were
+ // given initially, since it more accurately represents the coverage map for the
+ // input we are returning.
+ if outHash != inpHash {
+ resp.CoverageData = coverageSnapshot
+ } else {
+ resp.CoverageData = args.KeepCoverage
+ }
+ }
+ }
+ return resp
+}
+
+// minimizeInput applies a series of minimizing transformations on the provided
+// vals, ensuring that each minimization still causes an error, or keeps
+// coverage, in fuzzFn. It uses the context to determine how long to run,
+// stopping once closed. It returns a bool indicating whether minimization was
+// successful and an error if one was found.
+func (ws *workerServer) minimizeInput(ctx context.Context, vals []any, mem *sharedMem, args minimizeArgs) (success bool, retErr error) {
+ keepCoverage := args.KeepCoverage
+ memBytes := mem.valueRef()
+ bPtr := &memBytes
+ count := &mem.header().count
+ shouldStop := func() bool {
+ return ctx.Err() != nil ||
+ (args.Limit > 0 && *count >= args.Limit)
+ }
+ if shouldStop() {
+ return false, nil
+ }
+
+ // Check that the original value preserves coverage or causes an error.
+ // If not, then whatever caused us to think the value was interesting may
+ // have been a flake, and we can't minimize it.
+ *count++
+ _, retErr = ws.fuzzFn(CorpusEntry{Values: vals})
+ if keepCoverage != nil {
+ if !hasCoverageBit(keepCoverage, coverageSnapshot) || retErr != nil {
+ return false, nil
+ }
+ } else if retErr == nil {
+ return false, nil
+ }
+ mem.header().rawInMem = true
+
+ // tryMinimized runs the fuzz function with candidate replacing the value
+ // at index valI. tryMinimized returns whether the input with candidate is
+ // interesting for the same reason as the original input: it returns
+ // an error if one was expected, or it preserves coverage.
+ tryMinimized := func(candidate []byte) bool {
+ prev := vals[args.Index]
+ switch prev.(type) {
+ case []byte:
+ vals[args.Index] = candidate
+ case string:
+ vals[args.Index] = string(candidate)
+ default:
+ panic("impossible")
+ }
+ copy(*bPtr, candidate)
+ *bPtr = (*bPtr)[:len(candidate)]
+ mem.setValueLen(len(candidate))
+ *count++
+ _, err := ws.fuzzFn(CorpusEntry{Values: vals})
+ if err != nil {
+ retErr = err
+ if keepCoverage != nil {
+ // Now that we've found a crash, that's more important than any
+ // minimization of interesting inputs that was being done. Clear out
+ // keepCoverage to only minimize the crash going forward.
+ keepCoverage = nil
+ }
+ return true
+ }
+ // Minimization should preserve coverage bits.
+ if keepCoverage != nil && isCoverageSubset(keepCoverage, coverageSnapshot) {
+ return true
+ }
+ vals[args.Index] = prev
+ return false
+ }
+ switch v := vals[args.Index].(type) {
+ case string:
+ minimizeBytes([]byte(v), tryMinimized, shouldStop)
+ case []byte:
+ minimizeBytes(v, tryMinimized, shouldStop)
+ default:
+ panic("impossible")
+ }
+ return true, retErr
+}
+
+func writeToMem(vals []any, mem *sharedMem) {
+ b := marshalCorpusFile(vals...)
+ mem.setValue(b)
+}
+
+// ping does nothing. The coordinator calls this method to ensure the worker
+// has called F.Fuzz and can communicate.
+func (ws *workerServer) ping(ctx context.Context, args pingArgs) pingResponse {
+ return pingResponse{}
+}
+
+// workerClient is a minimalist RPC client. The coordinator process uses a
+// workerClient to call methods in each worker process (handled by
+// workerServer).
+type workerClient struct {
+ workerComm
+ m *mutator
+
+ // mu is the mutex protecting the workerComm.fuzzIn pipe. This must be
+ // locked before making calls to the workerServer. It prevents
+ // workerClient.Close from closing fuzzIn while workerClient methods are
+ // writing to it concurrently, and prevents multiple callers from writing to
+ // fuzzIn concurrently.
+ mu sync.Mutex
+}
+
+func newWorkerClient(comm workerComm, m *mutator) *workerClient {
+ return &workerClient{workerComm: comm, m: m}
+}
+
+// Close shuts down the connection to the RPC server (the worker process) by
+// closing fuzz_in. Close drains fuzz_out (avoiding a SIGPIPE in the worker),
+// and closes it after the worker process closes the other end.
+func (wc *workerClient) Close() error {
+ wc.mu.Lock()
+ defer wc.mu.Unlock()
+
+ // Close fuzzIn. This signals to the server that there are no more calls,
+ // and it should exit.
+ if err := wc.fuzzIn.Close(); err != nil {
+ wc.fuzzOut.Close()
+ return err
+ }
+
+ // Drain fuzzOut and close it. When the server exits, the kernel will close
+ // its end of fuzzOut, and we'll get EOF.
+ if _, err := io.Copy(io.Discard, wc.fuzzOut); err != nil {
+ wc.fuzzOut.Close()
+ return err
+ }
+ return wc.fuzzOut.Close()
+}
+
+// errSharedMemClosed is returned by workerClient methods that cannot access
+// shared memory because it was closed and unmapped by another goroutine. That
+// can happen when worker.cleanup is called in the worker goroutine while a
+// workerClient.fuzz call runs concurrently.
+//
+// This error should not be reported. It indicates the operation was
+// interrupted.
+var errSharedMemClosed = errors.New("internal error: shared memory was closed and unmapped")
+
+// minimize tells the worker to call the minimize method. See
+// workerServer.minimize.
+func (wc *workerClient) minimize(ctx context.Context, entryIn CorpusEntry, args minimizeArgs) (entryOut CorpusEntry, resp minimizeResponse, retErr error) {
+ wc.mu.Lock()
+ defer wc.mu.Unlock()
+
+ mem, ok := <-wc.memMu
+ if !ok {
+ return CorpusEntry{}, minimizeResponse{}, errSharedMemClosed
+ }
+ mem.header().count = 0
+ inp, err := corpusEntryData(entryIn)
+ if err != nil {
+ return CorpusEntry{}, minimizeResponse{}, err
+ }
+ mem.setValue(inp)
+ defer func() { wc.memMu <- mem }()
+ entryOut = entryIn
+ entryOut.Values, err = unmarshalCorpusFile(inp)
+ if err != nil {
+ return CorpusEntry{}, minimizeResponse{}, fmt.Errorf("workerClient.minimize unmarshaling provided value: %v", err)
+ }
+ for i, v := range entryOut.Values {
+ if !isMinimizable(reflect.TypeOf(v)) {
+ continue
+ }
+
+ wc.memMu <- mem
+ args.Index = i
+ c := call{Minimize: &args}
+ callErr := wc.callLocked(ctx, c, &resp)
+ mem, ok = <-wc.memMu
+ if !ok {
+ return CorpusEntry{}, minimizeResponse{}, errSharedMemClosed
+ }
+
+ if callErr != nil {
+ retErr = callErr
+ if !mem.header().rawInMem {
+ // An unrecoverable error occurred before minimization began.
+ return entryIn, minimizeResponse{}, retErr
+ }
+ // An unrecoverable error occurred during minimization. mem now
+ // holds the raw, unmarshalled bytes of entryIn.Values[i] that
+ // caused the error.
+ switch entryOut.Values[i].(type) {
+ case string:
+ entryOut.Values[i] = string(mem.valueCopy())
+ case []byte:
+ entryOut.Values[i] = mem.valueCopy()
+ default:
+ panic("impossible")
+ }
+ entryOut.Data = marshalCorpusFile(entryOut.Values...)
+ // Stop minimizing; another unrecoverable error is likely to occur.
+ break
+ }
+
+ if resp.WroteToMem {
+ // Minimization succeeded, and mem holds the marshaled data.
+ entryOut.Data = mem.valueCopy()
+ entryOut.Values, err = unmarshalCorpusFile(entryOut.Data)
+ if err != nil {
+ return CorpusEntry{}, minimizeResponse{}, fmt.Errorf("workerClient.minimize unmarshaling minimized value: %v", err)
+ }
+ }
+
+ // Prepare for next iteration of the loop.
+ if args.Timeout != 0 {
+ args.Timeout -= resp.Duration
+ if args.Timeout <= 0 {
+ break
+ }
+ }
+ if args.Limit != 0 {
+ args.Limit -= mem.header().count
+ if args.Limit <= 0 {
+ break
+ }
+ }
+ }
+ resp.Count = mem.header().count
+ h := sha256.Sum256(entryOut.Data)
+ entryOut.Path = fmt.Sprintf("%x", h[:4])
+ return entryOut, resp, retErr
+}
+
+// fuzz tells the worker to call the fuzz method. See workerServer.fuzz.
+func (wc *workerClient) fuzz(ctx context.Context, entryIn CorpusEntry, args fuzzArgs) (entryOut CorpusEntry, resp fuzzResponse, isInternalError bool, err error) {
+ wc.mu.Lock()
+ defer wc.mu.Unlock()
+
+ mem, ok := <-wc.memMu
+ if !ok {
+ return CorpusEntry{}, fuzzResponse{}, true, errSharedMemClosed
+ }
+ mem.header().count = 0
+ inp, err := corpusEntryData(entryIn)
+ if err != nil {
+ return CorpusEntry{}, fuzzResponse{}, true, err
+ }
+ mem.setValue(inp)
+ wc.memMu <- mem
+
+ c := call{Fuzz: &args}
+ callErr := wc.callLocked(ctx, c, &resp)
+ if resp.InternalErr != "" {
+ return CorpusEntry{}, fuzzResponse{}, true, errors.New(resp.InternalErr)
+ }
+ mem, ok = <-wc.memMu
+ if !ok {
+ return CorpusEntry{}, fuzzResponse{}, true, errSharedMemClosed
+ }
+ defer func() { wc.memMu <- mem }()
+ resp.Count = mem.header().count
+
+ if !bytes.Equal(inp, mem.valueRef()) {
+ return CorpusEntry{}, fuzzResponse{}, true, errors.New("workerServer.fuzz modified input")
+ }
+ needEntryOut := callErr != nil || resp.Err != "" ||
+ (!args.Warmup && resp.CoverageData != nil)
+ if needEntryOut {
+ valuesOut, err := unmarshalCorpusFile(inp)
+ if err != nil {
+ return CorpusEntry{}, fuzzResponse{}, true, fmt.Errorf("unmarshaling fuzz input value after call: %v", err)
+ }
+ wc.m.r.restore(mem.header().randState, mem.header().randInc)
+ if !args.Warmup {
+ // Only mutate the valuesOut if fuzzing actually occurred.
+ numMutations := ((resp.Count - 1) % chainedMutations) + 1
+ for i := int64(0); i < numMutations; i++ {
+ wc.m.mutate(valuesOut, cap(mem.valueRef()))
+ }
+ }
+ dataOut := marshalCorpusFile(valuesOut...)
+
+ h := sha256.Sum256(dataOut)
+ name := fmt.Sprintf("%x", h[:4])
+ entryOut = CorpusEntry{
+ Parent: entryIn.Path,
+ Path: name,
+ Data: dataOut,
+ Generation: entryIn.Generation + 1,
+ }
+ if args.Warmup {
+ // The bytes weren't mutated, so if entryIn was a seed corpus value,
+ // then entryOut is too.
+ entryOut.IsSeed = entryIn.IsSeed
+ }
+ }
+
+ return entryOut, resp, false, callErr
+}
+
+// ping tells the worker to call the ping method. See workerServer.ping.
+func (wc *workerClient) ping(ctx context.Context) error {
+ wc.mu.Lock()
+ defer wc.mu.Unlock()
+ c := call{Ping: &pingArgs{}}
+ var resp pingResponse
+ return wc.callLocked(ctx, c, &resp)
+}
+
+// callLocked sends an RPC from the coordinator to the worker process and waits
+// for the response. The callLocked may be cancelled with ctx.
+func (wc *workerClient) callLocked(ctx context.Context, c call, resp any) (err error) {
+ enc := json.NewEncoder(wc.fuzzIn)
+ dec := json.NewDecoder(&contextReader{ctx: ctx, r: wc.fuzzOut})
+ if err := enc.Encode(c); err != nil {
+ return err
+ }
+ return dec.Decode(resp)
+}
+
+// contextReader wraps a Reader with a Context. If the context is cancelled
+// while the underlying reader is blocked, Read returns immediately.
+//
+// This is useful for reading from a pipe. Closing a pipe file descriptor does
+// not unblock pending Reads on that file descriptor. All copies of the pipe's
+// other file descriptor (the write end) must be closed in all processes that
+// inherit it. This is difficult to do correctly in the situation we care about
+// (process group termination).
+type contextReader struct {
+ ctx context.Context
+ r io.Reader
+}
+
+func (cr *contextReader) Read(b []byte) (int, error) {
+ if ctxErr := cr.ctx.Err(); ctxErr != nil {
+ return 0, ctxErr
+ }
+ done := make(chan struct{})
+
+ // This goroutine may stay blocked after Read returns because the underlying
+ // read is blocked.
+ var n int
+ var err error
+ go func() {
+ n, err = cr.r.Read(b)
+ close(done)
+ }()
+
+ select {
+ case <-cr.ctx.Done():
+ return 0, cr.ctx.Err()
+ case <-done:
+ return n, err
+ }
+}
diff --git a/src/internal/fuzz/worker_test.go b/src/internal/fuzz/worker_test.go
new file mode 100644
index 0000000..d0b21da
--- /dev/null
+++ b/src/internal/fuzz/worker_test.go
@@ -0,0 +1,206 @@
+// Copyright 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fuzz
+
+import (
+ "context"
+ "errors"
+ "flag"
+ "fmt"
+ "internal/race"
+ "io"
+ "os"
+ "os/signal"
+ "reflect"
+ "strconv"
+ "testing"
+ "time"
+)
+
+var benchmarkWorkerFlag = flag.Bool("benchmarkworker", false, "")
+
+func TestMain(m *testing.M) {
+ flag.Parse()
+ if *benchmarkWorkerFlag {
+ runBenchmarkWorker()
+ return
+ }
+ os.Exit(m.Run())
+}
+
+func BenchmarkWorkerFuzzOverhead(b *testing.B) {
+ if race.Enabled {
+ b.Skip("TODO(48504): fix and re-enable")
+ }
+ origEnv := os.Getenv("GODEBUG")
+ defer func() { os.Setenv("GODEBUG", origEnv) }()
+ os.Setenv("GODEBUG", fmt.Sprintf("%s,fuzzseed=123", origEnv))
+
+ ws := &workerServer{
+ fuzzFn: func(_ CorpusEntry) (time.Duration, error) { return time.Second, nil },
+ workerComm: workerComm{memMu: make(chan *sharedMem, 1)},
+ }
+
+ mem, err := sharedMemTempFile(workerSharedMemSize)
+ if err != nil {
+ b.Fatalf("failed to create temporary shared memory file: %s", err)
+ }
+ defer func() {
+ if err := mem.Close(); err != nil {
+ b.Error(err)
+ }
+ }()
+
+ initialVal := []any{make([]byte, 32)}
+ encodedVals := marshalCorpusFile(initialVal...)
+ mem.setValue(encodedVals)
+
+ ws.memMu <- mem
+
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ ws.m = newMutator()
+ mem.setValue(encodedVals)
+ mem.header().count = 0
+
+ ws.fuzz(context.Background(), fuzzArgs{Limit: 1})
+ }
+}
+
+// BenchmarkWorkerPing acts as the coordinator and measures the time it takes
+// a worker to respond to N pings. This is a rough measure of our RPC latency.
+func BenchmarkWorkerPing(b *testing.B) {
+ if race.Enabled {
+ b.Skip("TODO(48504): fix and re-enable")
+ }
+ b.SetParallelism(1)
+ w := newWorkerForTest(b)
+ for i := 0; i < b.N; i++ {
+ if err := w.client.ping(context.Background()); err != nil {
+ b.Fatal(err)
+ }
+ }
+}
+
+// BenchmarkWorkerFuzz acts as the coordinator and measures the time it takes
+// a worker to mutate a given input and call a trivial fuzz function N times.
+func BenchmarkWorkerFuzz(b *testing.B) {
+ if race.Enabled {
+ b.Skip("TODO(48504): fix and re-enable")
+ }
+ b.SetParallelism(1)
+ w := newWorkerForTest(b)
+ entry := CorpusEntry{Values: []any{[]byte(nil)}}
+ entry.Data = marshalCorpusFile(entry.Values...)
+ for i := int64(0); i < int64(b.N); {
+ args := fuzzArgs{
+ Limit: int64(b.N) - i,
+ Timeout: workerFuzzDuration,
+ }
+ _, resp, _, err := w.client.fuzz(context.Background(), entry, args)
+ if err != nil {
+ b.Fatal(err)
+ }
+ if resp.Err != "" {
+ b.Fatal(resp.Err)
+ }
+ if resp.Count == 0 {
+ b.Fatal("worker did not make progress")
+ }
+ i += resp.Count
+ }
+}
+
+// newWorkerForTest creates and starts a worker process for testing or
+// benchmarking. The worker process calls RunFuzzWorker, which responds to
+// RPC messages until it's stopped. The process is stopped and cleaned up
+// automatically when the test is done.
+func newWorkerForTest(tb testing.TB) *worker {
+ tb.Helper()
+ c, err := newCoordinator(CoordinateFuzzingOpts{
+ Types: []reflect.Type{reflect.TypeOf([]byte(nil))},
+ Log: io.Discard,
+ })
+ if err != nil {
+ tb.Fatal(err)
+ }
+ dir := "" // same as self
+ binPath := os.Args[0] // same as self
+ args := append(os.Args[1:], "-benchmarkworker")
+ env := os.Environ() // same as self
+ w, err := newWorker(c, dir, binPath, args, env)
+ if err != nil {
+ tb.Fatal(err)
+ }
+ tb.Cleanup(func() {
+ if err := w.cleanup(); err != nil {
+ tb.Error(err)
+ }
+ })
+ if err := w.startAndPing(context.Background()); err != nil {
+ tb.Fatal(err)
+ }
+ tb.Cleanup(func() {
+ if err := w.stop(); err != nil {
+ tb.Error(err)
+ }
+ })
+ return w
+}
+
+func runBenchmarkWorker() {
+ ctx, cancel := signal.NotifyContext(context.Background(), os.Interrupt)
+ defer cancel()
+ fn := func(CorpusEntry) error { return nil }
+ if err := RunFuzzWorker(ctx, fn); err != nil && err != ctx.Err() {
+ panic(err)
+ }
+}
+
+func BenchmarkWorkerMinimize(b *testing.B) {
+ if race.Enabled {
+ b.Skip("TODO(48504): fix and re-enable")
+ }
+
+ ws := &workerServer{
+ workerComm: workerComm{memMu: make(chan *sharedMem, 1)},
+ }
+
+ mem, err := sharedMemTempFile(workerSharedMemSize)
+ if err != nil {
+ b.Fatalf("failed to create temporary shared memory file: %s", err)
+ }
+ defer func() {
+ if err := mem.Close(); err != nil {
+ b.Error(err)
+ }
+ }()
+ ws.memMu <- mem
+
+ bytes := make([]byte, 1024)
+ ctx := context.Background()
+ for sz := 1; sz <= len(bytes); sz <<= 1 {
+ sz := sz
+ input := []any{bytes[:sz]}
+ encodedVals := marshalCorpusFile(input...)
+ mem = <-ws.memMu
+ mem.setValue(encodedVals)
+ ws.memMu <- mem
+ b.Run(strconv.Itoa(sz), func(b *testing.B) {
+ i := 0
+ ws.fuzzFn = func(_ CorpusEntry) (time.Duration, error) {
+ if i == 0 {
+ i++
+ return time.Second, errors.New("initial failure for deflake")
+ }
+ return time.Second, nil
+ }
+ for i := 0; i < b.N; i++ {
+ b.SetBytes(int64(sz))
+ ws.minimize(ctx, minimizeArgs{})
+ }
+ })
+ }
+}