Fuzzing support for Go

Dmitry Vyukov, dvyukov@

@thepudds

Mar 9, 2017

Abstract

This is a proposal to add fuzzing support as first-class citizen to Go standard toolchain (issue 19109). Discussion mailing list. http://tiny.cc/why-go-fuzz

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.

Changes to Proposal Document

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 artifacts 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 can match multiple fuzz functions, including to support invocations such as go test -fuzz=. ./.... The timing and ordering of execution is not externally specified for multiple matching fuzz functions, but the go command has the option of executing the matching fuzz functions in round-robin order (e.g., initial round can be executing each function for a short duration such as 0.1 sec, and then for progressively longer durations).

Directory specified with -fuzzdir holds fuzz artifacts 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 the 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/fuzz/GOOS_GOARCH/ 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. 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?

Recent progress

This post has some more details on recent progress and some comments on potential near-term goals. A summary of recent progress:

 FuzzRegexp(re string, input []byte, posix bool)

Recent discussions

This section attempts to help anyone catch up on recent discussions, with pointers for more details. For the two most complex topics at the end, a short summary is given in this document because there is otherwise no simple pointer to something short.

Question: Should `go test` without `-fuzz` ever be non-deterministic?

Question: Allow multiple fuzz functions to match?

Question: Source-to-source transform vs. compiler-based instrumentation?

Question: Should the proposal include a richer Fuzz function signature, or wait on that?

Question: Include -fuzztime for max duration of a fuzzing run?

Question: What should dirty your VCS status?

Based on my experience with go-fuzz, dirtying vcs status is very inconvenient. In most cases when I got a diff in corpus, I actually did not want to check it in.

Consider you pass by some OSS repo and run go test -fuzz there just for fun. Or you are contributing a change to some package and run fuzzing to test your code, but you don't want to check-in the corpus change, you just want to check-in the code change.”

Question: Should > 1 corpus location be supported, and if so, how exactly?

I wonder if it's a good idea to instead allow 2/2+ directories with input corpus?

For example, if we read inputs from testdata/something/something, but also from

-fuzzdir/-workdir if provided. Then testdata/ could contain hand-written inputs and regression

tests and is checked-in with the code (that's small number of higher-quality inputs with low

churn, so no different from unit-tests and makes sense to check-in). The second dir can contain the random inputs, there are more of them and high churn. So that is preferably checked-in somewhere else (stored in an archive or something else). Then workflow would be to simply copy the crashing input from the second dir into testdata/ and run go test -run=file_name (if the auto-generated regression test uses t.Run then this will work auto-magically).”

In addition, using GOPATH/pkg/fuzz/xxx, I'm not sure about the way the user should promote a generated input to the checked-in corpus. Having to do a manual copy seems clumsy, error-prone at best and too much arcane for the "standard user" I imagine. We would have to add tooling for this and I'm not convinced this would be better.”

Namely, testdata/fuzz/<fuzzfunc>/corpus contains the "fixed" corpus (small number of either manually created inputs or previous crashing inputs). User will need to manually copy crashing inputs from GOPATH/pkg into this location. We can even strip /corpus from the

path, because there is nothing else.

And then we have:

   GOPATH/pkg/fuzz/import/path/corpus

   GOPATH/pkg/fuzz/import/path/crashers

The first contains "dynamic" corpus files. The second new crashing

inputs and the corresponding output.”

The rest is on user: they can move files as necessary and as they see fit.”