Apply fuzzing to a function that parses some string

Recently the Go team released a fuzzer https://blog.golang.org/fuzz-beta

Can you help to describe what I can expect from the fuzzer in terms of test goals?

How to apply the fuzzer?

Give some insight about how long we would run it before considering it good enough

How to correlate execution failure with the code (i expect having GB of results, I am wondering how overwhelming that could be and how to handle that)

See this intentionally terrific piece of code which would definitely need to be fuzzed

package main

import (
	"fmt"
	"log"
)

func main() {
	type expectation struct {
		input  string
		output []string
	}

	expectations := []expectation{
		expectation{
			input: "foo=bar baz baz foo:1 baz ",
			output: []string{
				"foo=bar baz baz",
				"foo:1 baz",
			},
		},
		expectation{
			input: "foo=bar baz baz foo:1 baz   foo:234.mds32",
			output: []string{
				"foo=bar baz baz",
				"foo:1 baz",
				"foo:234.mds32",
			},
		},
		expectation{
			input: "foo=bar baz baz foo:1 baz   foo:234.mds32  notfoo:baz  foo:bak foo=bar baz foo:nospace foo:bar",
			output: []string{
				"foo=bar baz baz",
				"foo:1 baz",
				"foo:234.mds32",
				"notfoo:baz",
				"foo:bak",
				"foo=bar baz",
				"foo:nospace",
				"foo:bar",
			},
		},
		expectation{
			input: "foo=bar",
			output: []string{
				"foo=bar",
			},
		},
		expectation{
			input: "foo",
			output: []string{
				"foo",
			},
		},
		expectation{
			input: "=bar",
			output: []string{
				"=bar",
			},
		},
		expectation{
			input: "foo=bar baz baz foo:::1 baz  ",
			output: []string{
				"foo=bar baz baz",
				"foo:::1 baz",
			},
		},
		expectation{
			input: "foo=bar baz baz   foo:::1 baz  ",
			output: []string{
				"foo=bar baz baz",
				"foo:::1 baz",
			},
		},
	}

	for i, expectation := range expectations {
		fmt.Println("  ==== TEST ", i)
		success := true
		res := parse(expectation.input)
		if len(res) != len(expectation.output) {
			log.Printf("invalid length of results for test %v\nwanted %#v\ngot    %#v", i, expectation.output, res)
			success = false
		}
		for e, r := range res {
			if expectation.output[e] != r {
				log.Printf("invalid result for test %v at index %v\nwanted %#v\ngot    %#v", i, e, expectation.output, res)
				success = false
			}
		}
		if success {
			fmt.Println("  ==== SUCCESS")
		} else {
			fmt.Println("  ==== FAILURE")
			break
		}
		fmt.Println()
	}
}

func parse(input string) (kvs []string) {
	var lastSpace int
	var nextLastSpace int
	var n int
	var since int
	for i, r := range input {
		if r == ' ' {
			nextLastSpace = i + 1
			if i > 0 && input[i-1] == ' ' {
				continue
			}
			lastSpace = i
		} else if r == '=' || r == ':' {
			if n == 0 {
				n++
				continue
			}
			n++
			if since < lastSpace {
				kvs = append(kvs, string(input[since:lastSpace]))
			}
			if lastSpace < nextLastSpace { // there was multiple in between spaces.
				since = nextLastSpace
			} else {
				since = lastSpace + 1
			}
		}
	}
	if since < len(input) { // still one entry
		var begin int
		var end int
		begin = since
		end = len(input)
		if lastSpace > since { // rm trailing spaces it ends with 'foo:whatever    '
			end = lastSpace
		} else if since < nextLastSpace { // rm starting spaces it ends with '   foo:whatever'
			begin = nextLastSpace
		}
		kvs = append(kvs, string(input[begin:end]))
	}
	return
}

So, I dug a bit into the fuzz draft design. Here's some insights.

First, as recommended in the blog post, you have to run the Go tip:

go get golang.org/dl/gotip@latest
gotip download

The gotip command acts as a "drop-in replacement for the go command" without messing up your current installation.

Expectations

The fuzzer basically generates a corpus of variations on some function's input parameters and runs the test with them in order to discover bugs.

Instead of writing an arbitrary number of test cases yourself, you provide example inputs to the engine and the engine mutates them and calls your function with the new parameters automatically. The corpus then will be cached so it will work as a basis for regression tests.

How to apply the fuzzer?

This is covered fairly decently by the blog post and the draft design and the documentation at tip

The testing package has now a new type testing.F which you pass to the fuzz targets. As in unit tests and benchmarks, the fuzz target name must start with Fuzz prefix. So the signature will look like:

func FuzzBlah(f *testing.F) {
    // ...
}

The body of fuzz target essentially uses the testing.F API to:

Provide a seed corpus with F.Add

> The seed corpus is the user-specified set of inputs to a fuzz target which will be run by default with go test. These should be composed of meaningful inputs to test the behavior of the package, as well as a set of regression inputs for any newly discovered bugs identified by the fuzzing engine

So these are actual test case inputs of your parse function, those that you would write yourself.

func FuzzBlah(f *testing.F) {
    f.Add("foo=bar")
    f.Add("foo=bar baz baz foo:1 baz ")
    // and so on
}

Run the function with fuzzed inputs with F.Fuzz

Each fuzz target calls f.Fuzz once. The argument to Fuzz is a function that takes a testing.T and N params of the same type as those passed to f.Add. If your example test takes only one string, it would be:

func FuzzBlah(f *testing.F) {
    f.Add("foo=bar")
    f.Add("foo=bar baz baz foo:1 baz ")
    
    f.Fuzz(func(t *testing.T, input string) {

    })
}

The body of the fuzz function then is just whatever you want to test, so for example your parse function.

What is critical, I think, in understanding and using the fuzzer is that you don't test pairs of inputs and expected outputs. You do that with unit tests.

By fuzzing instead you test that the code doesn't break for a given input. The given input is randomized enough to cover corner cases. That's why the official examples:

• call t.Skip() in case of expected failures
• run countercheck functions, e.g. Marshal then Unmarshal, or url.ParseQuery then query.Encode

Cases where the input marshals correctly but then doesn't unmarshal back to the original value are unexpected failures, and those that a fuzzer is better at finding than you could be by writing manual tests.

So to put it all together, the fuzz target could be:

func FuzzBlah(f *testing.F) {
    f.Add("foo=bar")
    f.Add("foo=bar baz baz foo:1 baz ")
    // and so on
    
    f.Fuzz(func(t *testing.T, input string) {
        out := parse(input)
        // bad output, skip
        if len(out) == 0 {
            t.Skip() 
        }

        // countercheck
        enc := encode(out)
        if enc != input {
            t.Errorf("countercheck failed")
        }
    })
}

Inputs that result in a test failure will be added to the corpus, so you can fix the code and run regression tests.

Running it

You just run go test with the -fuzz <regex> flag. You can specify a duration or a number of times the fuzzer runs for with:

• -fuzztime <duration> where duration is a time.Duration string, e.g. 10m
• -fuzztime Nx where N is the number of iterations, e.g. 20x

How long or how many is enough for your tests is going to depend on what code you are testing. I trust the Go team will provide some more recommendations about that in due time.

So to wrap up:

• gotip test -fuzz . -fuzztime 20x

which will also generate the corpus in the appropriate subdirs of $GOCACHE/fuzz/.

This should be enough to get you started. As I said in the comments, the feature is early in development so there might be bugs and the documentation might be lacking. I'll probably update this answer as more info come out.