Fuzzing support for Go

Dmitry Vyukov, dvyukov@

Mar 9, 2017

Abstract

This is a proposal to add fuzzing support as first-class citizen to Go standard toolchain (issue 19109). Fuzzing is software testing technique that involves providing random data as inputs to a computer program. Fuzzing is complementary to other testing techniques (notably unit testing) covering long tail of unexpected/invalid inputs. Currently Go provides good support for unit testing but does not provide anything for fuzzing.

Background

Fuzzing has a long history (starting from "inputting decks of punch cards taken from the trash" in 1950s) and almost all applications of fuzzing find considerable number of previously unknown bugs. At Google we have found more than 15000 bugs in various software over the last years with fuzzing.

There are several types of fuzzers based on the approach used for generation of the input data:

Coverage-guided fuzzers seems to be at the sweet spot of being simple, practical and requiring minimal user effort. The crux of the technique is as follows:

        start with some (potentially empty) corpus of inputs

        for {

                choose a random input from the corpus

                mutate the input

                execute the mutated input and collect code coverage

                if the input gives new coverage, add it to the corpus

        }

This approach is implemented for Go in a third-party go-fuzz tool. The tool has found 100+ bugs in Go standard library package within several months with a single-person effort, +100+ bugs in Go compilers (compile, asm, types, gccgo) and hundreds of bugs elsewhere.

However, go-fuzz suffers from several problems:

Goal of this proposal is to make fuzzing as easy to use as unit testing.

Proposed Solution

Fuzzing support consists of several parts: a way for user to write a fuzz function; a way to run fuzzing using the go tool and implementation details (coverage instrumentation, fuzzer algorithm, etc). Let's consider them separately.

API Support

The support is added to the testing package.

User fuzz functions are added to _test.go files and start with Fuzz akin to tests and benchmarks. Fuzz function accepts two arguments: (*testing.F, data []byte).

The data []byte argument is the random input that the function is supposed to use in some way.

The new type testing.F merely implements testing.TB interface:

The simplest fuzz function looks as follows:

// encoding/hex/fuzz_test.go

package hex

import "testing"

func FuzzDecodeString(f *testing.F, data []byte) {

        DecodeString(string(data))

}

testing.F type can later be extended with other functions if necessary.

The fuzz function signature can later be allowed to accept multiple randomly-generated arguments of different types. This is useful for fuzz tests that need multiple inputs, for example:

func FuzzRegexp(f *testing.F, re string, data []byte, posix bool) {

        var re *Regexp

        var err error

        if posix {

                re, err = CompilePOSIX(re)

        } else {

                re, err = Compile(re)

        }

        if err != nil {

                return

        }

        re.Match(data)

}

But multiple values can be extracted from the byte slice, just with more work and leading to worser fuzzer efficiency (as it will not understand the structure of the input). So such support is explicitly not part of this proposal. Here is an example of how the same can be achieved with the currently proposed interface:

func FuzzRegexp(f *testing.F, data []byte) {

        if len(data) < 0 {

                return

        }

        posix := data[0]%2 != 0

        re := string(data[1:1+len(data)/2])

        data = data[1+len(data)/2]:]

        // the rest is the same

}

Go command integration

go test is extended with the following flags:

-fuzz regexp

                Run the fuzz function matching this regexp.

        -fuzzdir dir

                Store fuzz artefacts in the specified directory.

                Default value: pkgpath/testdata/fuzz.

        -fuzzinput input

                Execute the fuzz function on this single input.

                Flag value specifies path to a file with the input.

        -fuzzminimize

                Run each input in the corpus once, collect coverage and

minimize the corpus (remove excessive inputs).

-fuzz flag must match one and only one fuzz function. This is different from -run and -bench flags which allow multiple matches. It's unclear what would be the behavior when multiple fuzz functions are selected, so for now we restrict it to only one function. Selecting multiple packages is not supported either. The restriction can be removed when/if we figure out a sane behavior for this.

Directory specified with -fuzzdir holds fuzz artefacts such as corpus of inputs and information about discovered bugs. The proposed structure is:

        fuzzdir/FuzzName/corpus

                Contains corpus of inputs. One file per input. File name is hex(sha1(input)).

                The directory can also contain user-created inputs for corpus bootstrap

                and/or to persist inputs that triggered bugs as regression tests.

                Files that are not 40-chars-of-hex are loaded but are not removed

during minimization (-fuzzminimize).

        fuzzdir/FuzzName/crashes

        Contains information about discovered bugs. Two files per bug are saved:

inputN and outputN (where N is some unique number).

inputN contains the input that triggered the bug.

outputN contains program output on the input.

pkgpath/testdata/fuzz directory can be:

For the standard library it is proposed to check in corpus into golang.org/x/fuzz repo.

-fuzzinput flag gives an easy way to confirm that the input in fact triggers a bug and retest when the bug is fixed without code modifications.

-fuzz flag is incompatible with most other flags. That is, tests and benchmarks are not run, profiles are not collected, etc. If any of the incompatible flags are specified, go test produces an error. This can be relaxed in future (e.g. collecting profiles in fuzzing mode if we find it useful).

The compatible flags are:

        -c/-i

Build/install coverage-instrumented binary/package. Potentially the requirement of selecting only one fuzz function can be relaxed in this mode, i.e. make go test -c -fuzz=.* allowed.

        -parallel n

                Number of parallel subprocesses to use for fuzzing.

                Defaults to runtime.NumCPU.

        -timeout t

                Timeout for a single fuzz function invocation.

                If the specified timeout is exceeded, it is considered as bug.

        -coverprofile cover.out

                Runs each input from the corpus once and writes coverage report

to the specified file. If -fuzzinput is specified, then writes coverage

only for the specified input.

        -v

                Enabled additional output about fuzzing progress.

                Fuzzing function output is still not shown.

go test -fuzz builds the test with code coverage instrumentation required for fuzzing. It also auto-enables fuzz build tag. Installed packages are cached under pkg/GOOS_GOARCH_fuzz/ dir.

go test runs fuzz functions as unit tests. Fuzz functions are selected with -run flag on par with tests (i.e. all by default). Fuzz functions are executed on all inputs from the corpus and on some amount of newly generated inputs (for 1s in normal mode and for 0.1s in short mode). For that matter, -fuzzdir flag can be specified without -fuzz flag.

Coverage instrumentation

Coverage instrumentation is not directly exposed to user, so we have flexibility of changing it later.

There are two additional aspects to consider:

However, both things are safely solvable later and are outside of the scope of this proposal (we can add something like testing.ReadCoverage later).

The proposed interface for compiler instrumentation is as follows:

Per edge (or basic block initially if that's simpler) compiler emits a global variable and a function call, the function accepts a pointer to the global:

var __fuzzNNN struct {

x uint64 // can be used arbitrary by the callback

// Potentially extended with source information required

// for go tool cover and/or other info.

}

...

testing.coverCallback(&__fuzzNNN)

...

There are multiple ways a fuzzer can use coverage information: collect full traces of covered PCs, collect only newly covered PCs (delta from previous runs), store covered PCs as bits in a large hashtable, count number of times each PC was hit, etc. The state of the art with respect to what's the best mode constantly evolves. The proposed instrumentation with function calls should support most of these modes seamlessly.

Implementation plan

This proposal allows incremental implementation:

-fuzzinput, -fuzzminimize and -coverprofile are not implemented. No code coverage.

But this already can work as randomized testing.

Continuous fuzzing

By continuous fuzzing we mean periodic runs of all fuzz functions on a single or multiple machines on the latest version of source code. We found this to be the most useful fuzzing setup (akin to running unit tests on every checked in change). Continuous fuzzing is not directly implemented by the proposed solution, but it is designed to support continuous fuzzing with third-party tools. Rough operation of such a system (based on our experience with ClusterFuzz) would be:

A simpler version of this can be deployed with Google Compute Storage gsutil rsync, syncing corpus both ways from multiple machines to a GCS bucket.

Potentially we may need to expose list of all fuzz functions in a package in go list output for automatic discovery (is there a better way?).

Open questions

go test interface is already quite bloated, this proposal adds more flags and slightly redefines some of the existing flags in fuzzing mode. Fuzzing mode is also incompatible with some of the existing flags. Should we add go fuzz subcommand?