Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

proposal: cmd/go: make fuzzing a first class citizen, like tests or benchmarks #19109

Open
bradfitz opened this issue Feb 15, 2017 · 113 comments
Open
Assignees
Milestone

Comments

@bradfitz
Copy link
Contributor

@bradfitz bradfitz commented Feb 15, 2017

Filing a proposal on behalf of @kcc and @dvyukov:

They request that cmd/go support fuzzing natively, just like it does tests and benchmarks and race detection today.

https://github.com/dvyukov/go-fuzz exists but it's not as easy as writing tests and benchmarks and running "go test -race" today.

Should we make this easier?

Motivation
Proposal

@bradfitz bradfitz added this to the Proposal milestone Feb 15, 2017
@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Feb 15, 2017

I think it would be easier to evaluate the idea if it were slightly less abstract.

For example:

  • _test.go are permitted to contain functions of the form FuzzXxx(f *testing.F, data []byte)
  • these functions are expected to run some test based on the random bytes in data
  • errors are reported using the testing.F argument in the usual way
  • f.Useful() may be called to indicate useful data, i.e., data that parses correctly
  • f.Discard() may be called to indicate that the data should be discarded
  • go test -fuzz=. runs the fuzz functions using a regexp like -test and -bench
  • naturally go test -fuzz must also rebuild the package in fuzz mode
  • the data is cached somewhere under $GOROOT/pkg, but where?
@bradfitz
Copy link
Contributor Author

@bradfitz bradfitz commented Feb 15, 2017

@ianlancetaylor, yes, FuzzXxx(f *testing.F, ...) is what this is about. The exact API is probably TBD.

I think the first step before it's designed completely is to determine whether there's interest.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Feb 15, 2017

As a general concept, I'm in favor.

@dsnet
Copy link
Member

@dsnet dsnet commented Feb 15, 2017

I would expect that there would be an additional required flag (when fuzzing) where you specify the corpus directory.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Feb 15, 2017

Can we just cache the corpus somewhere under $GOROOT/pkg? Are there cases where a typical user would be expected to modify the corpus themselves?

@dsnet
Copy link
Member

@dsnet dsnet commented Feb 15, 2017

I think it's wrong to think of the corpus as strictly a cache. The corpus is the save state of the fuzzer and the documentation for go-fuzz even recommends committing them into a version control system. The pkg directory is treated strictly as cache and it is not uncommon for people to recommend clearing out the directory, which will unfortunately delete the fuzzer state.

A specified corpus is not so much for the user modify the corpus themselves, but for them to specify how to persist the corpus data.

@jimmyfrasche
Copy link
Member

@jimmyfrasche jimmyfrasche commented Feb 15, 2017

Could there be some default convention say a _fuzz/xxx directory (where xxx corresponds with FuzzXxx) and a method on the *testing.F object to load a different corpus from the _fuzz/ directory if necessary? It seems like it should just know where the corpus is.

@minux
Copy link
Member

@minux minux commented Feb 15, 2017

@cznic
Copy link
Contributor

@cznic cznic commented Feb 16, 2017

Quoting @dvyukov

I would appreciate if you drop a line there if you found fuzzing useful and a brief of your success story.

It was very useful for me - found bugs in several lexers.

@mvdan
Copy link
Member

@mvdan mvdan commented Feb 16, 2017

I use it regularly on a lexer/parser/formatter for Bash (https://github.com/mvdan/sh).

Having it be a first-class citizen would simplify things for me and for contributors.

@dsnet
Copy link
Member

@dsnet dsnet commented Feb 16, 2017

Found a bug in the C decoder for google/brotli by fuzzing a Go implementation of a Brotli decoder.

Also found some divergences in Go bzip2 decoders from the canonical C decoder (this and #18516). All by fuzzing.

@fatih
Copy link
Member

@fatih fatih commented Feb 16, 2017

My coworker at DigitalOcean was working on a side project to make fuzzing easier. Check his repo out here: https://github.com/tam7t/cautious-pancake Adding it here as I think it would be a valuable piece of information for this discussion.

@dgryski
Copy link
Contributor

@dgryski dgryski commented Feb 16, 2017

The README for go-fuzz lists a number of "Trophies", ( https://github.com/dvyukov/go-fuzz#trophies ) the majority of which are from the standard library, but about 20% of which are external to the Go standard libraries.

A GitHub search for Go source files with the gofuzz build tag gives ~2500 results: https://github.com/search?l=Go&q=gofuzz&type=Code&utf8=%E2%9C%93

My tutorial on fuzzing ( https://medium.com/@dgryski/go-fuzz-github-com-arolek-ase-3c74d5a3150c ) gets 50-60 "reads" per month (according to medium's stats).

@Kubuxu
Copy link

@Kubuxu Kubuxu commented Feb 16, 2017

Feature that would be also important (at least for me) would be ease of turning some selected Fuzz test cases into permanent tests. Simplest way to do it would be exporting the case data in go byte array and calling FuzzXXX function from TestXXX function but if FuzzXXX accepts *testing.F struct type it won't be possible.

@DavidVorick
Copy link

@DavidVorick DavidVorick commented Feb 16, 2017

Yes, we've found fuzzing useful in our projects multiple times. Especially sensitive code, the fuzzer will frequently find edge cases that we missed. Encoding, networking, and generally things that depend on user input.

I will say that most of the benefit is usually seen in the first tiny bit of fuzzing. There's a pretty strong diminishing returns as you continue to fuzz, at least that's what we've found.

@dvyukov
Copy link
Member

@dvyukov dvyukov commented Feb 16, 2017

As you can understand, I am very supportive for this. Traditional testing is just not enough for modern development speeds. I am ready to dedicate some time to work on parts of this.

Throwing some ideas onto the table:

  1. To flesh out the interface, we don't need to implement coverage nor any actual smartness. The interface should work if we just feed in completely random data, it will be just less useful. But I think it's the right first step. We can transparently add smartness later.

  2. It would be nice to have some default location for corpus, because it will make onboarding easier. The location probably needs to be overridable with go test flag or GOFUZZ env var.

  3. I think it's "must have" that fuzz funciton runs during normal testing. If corpus is present, each input from corpus is executed once. Plus we can run N random inputs.

  4. Thinking how we can integrate continuous fuzzing into Go std lib testing (including corpus management) would be useful to ensure that it will also work for end users in their setups.

  5. go command (or whatever runs fuzz function) might need some additional modes. For example, execute 1 given input, useful for crash debugging. Or, run all programs from corpus and dump code coverage report.

  6. I am ready to give up on f.Useful() and f.Discard() for simplicity (as far as I understand that come from go-fuzz return values). They were never proven to be useful enough. For Discard Fuzz function can just return. And fuzzer can try to figure out Useful automatically.

  7. In some cases Fuzz function needs more than just []byte. For example, regexp test needs the regular expression and a string to match. Other tests may need some additional int's and bool's. It's possible to manually split []byte into several strings and also take some bits as int's and bool's. But it's quite inconvenient and can negatively affect fuzzing efficiency (fuzzer can do better if it understands more about input structure). So we could consider allowing Fuzz function to accept a set of inputs with some restrictions on types, e.g. FuzzFoo(f *testing.F, s1, s2 string, x int, b bool). But this can be added later as backwards compatible extension. Just something to keep in mind.

  8. An alternative interface could be along the following lines:

func FuzzFoo(f *testing.F) {
  var data []byte
  f.GetRandomData(&data)
  // use data
}

GetRandomData must be called once and always with the same type.
Since the function now does not accept the additional argument, we can make it a normal test:

func TestFoo(t *testing.T) {
  var data []byte
  testing.GetRandomData(&data)
  // use data
}

This recalls testing/quick interface considerably, so maybe we could just use testing/quick for this.
go tool will need to figure out that this is a fuzzing function based on the call to testing.GetRandomData.

@dvyukov
Copy link
Member

@dvyukov dvyukov commented Feb 16, 2017

I will say that most of the benefit is usually seen in the first tiny bit of fuzzing. There's a pretty strong diminishing returns as you continue to fuzz, at least that's what we've found.

That's true to some degree, but not completely. It depends on (1) complexity of your code, (2) rate of change of your code, (3) smartness of the fuzzer engine. If your code is simple and doesn't change, then fuzzer will find everything it can in minutes. However, if your code change often, you want to run fuzzing continuously as regression testing. If your code is large and complex and fuzzer is smart enough, then it can manage to uncover complex bugs only after significant time.
One example is this bug in OpenSSL bignum asm implementation that we've found after several CPU years of fuzzing: https://github.com/google/fuzzer-test-suite/tree/master/openssl-1.1.0c
Another example is our Linux kernel fuzzing which uncovers bugs at roughly constant rate over more than a year (due to complexity of the code and frequent changes): https://github.com/google/syzkaller/wiki/Found-Bugs

@webRat
Copy link

@webRat webRat commented Feb 16, 2017

I'm fine with fuzzing, but the problem is that if you vendor in a library that fuzzes, then... you inherit all their corpus. So, I'm not a fan of corpus being checked into the project.

Case in point:
screen shot 2017-02-16 at 9 35 58 am

Overall, I think fuzzing is a must have. Glad to see a proposal to make it easier.

@btracey
Copy link
Contributor

@btracey btracey commented Feb 16, 2017

To confirm @dvyukov in #19109 (comment) , it would be really nice to have supported types other than []byte. We found bugs in both the gonum/blas implementation and the OpenBLAS library using fuzzing. It's possible to use go-fuzz, but it's kind of a pain to parse the []byte directly, (https://github.com/btracey/blasfuzz/blob/master/onevec/idamax.go).

@kardianos
Copy link
Contributor

@kardianos kardianos commented Feb 16, 2017

Suggest it goes under the subfolder testdata. Then any tools that ignore tests will also ignore this dir.

@dsnet
Copy link
Member

@dsnet dsnet commented Feb 16, 2017

@dvyukov

I think it's "must have" that fuzz funciton runs during normal testing. If corpus is present, each input from corpus is executed once. Plus we can run N random inputs.

I have concerns about how much time this is going to add to testing. My experience with fuzzing is that compiling with the fuzz instrumentation takes a significant amount of time. I'm not sure this is something we want to inflict upon every use of go test.

@Kubuxu
Copy link

@Kubuxu Kubuxu commented Feb 16, 2017

@dsnet to execute corpus and check if it doesn't fail instrumentation isn't needed. Instrumentation is needed when you want to expend/improve the corpus.

@CAFxX
Copy link
Contributor

@CAFxX CAFxX commented Feb 16, 2017

Should there be a story to make it easy to use external fuzzing engines?

@dsnet
Copy link
Member

@dsnet dsnet commented Feb 16, 2017

@Kubuxu, I'm comfortable with running the Fuzz functions as a form of test without special instrumentation, but Dmitry comment suggested running with N random inputs, which implies having the instrumentation involved.

@kcc
Copy link

@kcc kcc commented Feb 16, 2017

My 2c (I am utterly ignorant about Go, but have some ideas about fuzzing)

There are several major parts in coverage-guided fuzzing as I can see it:

  • instrumentation
  • interface
  • fuzzing engines' logic (how to mutate, choose elements to add to the corpus, etc)
  • integration with the rest of Go testing infra (I won't comment on this one -- no opinion)

Instrumentation is better to be done in the compiler, this way it's the most efficient and easy to use.
In LLVM we have these two kinds of instrumentation used for guided fuzzing:
https://clang.llvm.org/docs/SanitizerCoverage.html#tracing-pcs-with-guards (control flow feedback)
https://clang.llvm.org/docs/SanitizerCoverage.html#tracing-data-flow (data flow feedback)

The interface must be as simple as possible. For C/C++ our interface (which we use with libFuzzer, AFL, hoggfuzz, and a few others) is:

extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
  DoSomethingInterestingWithMyAPI(Data, Size);
  return 0;  // Non-zero return values are reserved for future use.
}

and the only thing I regret is that the return type is not void.
IMHO, for the first version of the interface for Go fuzzing, the go-fuzz approach is perfect:

func Fuzz(data []byte) int

(again, not confident about int return value)

Fuzzing engines and the interface should be independent.
It should be possible to plug any fuzzing engine (not necessary written in Go) to fuzz a Go fuzz target.
Such fuzzing engine may need to understand the feedback provided by the instrumentation though.
E.g. I'd love to try libFuzzer/AFL on the Go targets.
And by fuzzing engine we should understand a wider class of tools, including e.g. concolic execution tools.

And, it would be nice to have the new fuzzing engine(s) to behave similar to AFL, libFuzzer, and go-fuzz
so that they are easier to integrate with continuous fuzzing service(s) (e.g. oss-fuzz)

Should there be a story to make it easy to use external fuzzing engines?

Absolutely, see above.

it would be really nice to have supported types other than []byte.

Maybe.
For the really complex data structures our current answer is to use protobufs as the input:
https://github.com/google/libprotobuf-mutator
There is also a middle ground where you need to fuzz e.g. a pair of strings.
But I would rather have a standard adapter from from []byte into a pair of strings than to complicate the interface.

Are there cases where a typical user would be expected to modify the corpus themselves?

Corpus is not a constant. It evolves as long as the code under test changes, fuzzing techniques evolve, and simply more CPU hours are spent fuzzing.
We typically store a seed corpus in RCS, maintain a larger corpus on the fuzzing service,
and periodically merge it back to RCS.

Note: a corpus stored in RCS allows to perform regression testing (w/o fuzzing)

I also want to have cmd/cover built on compiler instrumentation to support branch coverage, but that's off-topic to this issue.

Not too much off-topic.
This approach in LLVM allows us to get various kinds of coverage data with the same compiler instrumentation, by just re-implementing the callbacks.

I'm fine with fuzzing, but the problem is that if you vendor in a library that fuzzes, then... you inherit all their corpus. So, I'm not a fan of corpus being checked into the project.

This is a price worth paying since the corpus often turns out to be a great regression test.

I have concerns about how much time this is going to add to testing. My experience with fuzzing is that compiling with the fuzz instrumentation takes a significant amount of time. I'm not sure this is something we want to inflict upon every use of go test.

If you don't enable fuzzing instrumentation (which won't be on by default, I think) you won't pay for it.

@kcc
Copy link

@kcc kcc commented Feb 16, 2017

A separate topic worth thinking about is fuzzing for equivalence between two implementations of the same protocol.

Imagine your code has
func ReferenceFoo(data []byte) SomeType and
func ExperimentalOptimizedFoo(data []byte) SomeType.

Then you can fuzz the following target to verify that the two implementations match:

func Fuzz(data []byte) int {
    if ReferenceFoo(data) != ExperimentalOptimizedFoo(data) {
       panic("ouch!")
    }
    return 0
}

This works pretty well when both things are implemented in Go.
But imagine you are porting to Go something previously written in C.
Here is a write up that describes one possible solution:
https://moderncrypto.org/mail-archive/hacs/2017/000001.html
(in short: have two processes running in parallel and exchanging data via shared memory or some such)

@FiloSottile
Copy link
Contributor

@FiloSottile FiloSottile commented Feb 17, 2017

I love this.

And I think a good solution to the corpus location, like

  • defaulting to testdata/FuzzXxx/
  • run (only) the corpus cases w/o flags

would

  • remove the need to duplicate code to "freeze" certain testcases
  • avoid sacrificing the API to fit it in a testing.T
  • be a more elegant solution that doesn't require putting binary data in source files

Projects that don't commit the corpus could use -fuzzcorpus (or similar) when fuzzing, and then copy the test cases they want to run every time in the testdata folder and check them in.

Actual fuzzing could be controlled by -fuzztime (like -benchtime).

@palsivertsen
Copy link

@palsivertsen palsivertsen commented Sep 30, 2019

I really like the gofuzz library. Fuzz function could look something like this:

func FuzzXxx(f *fuzz.Fuzzer) {
    var ints []int
    f.Fuzz(&ints)
    sort.Ints(s)
}

...where f is seeded by the go tool chain. The seed should also be printed on failures so that tests can be reran to reproduce failure scenarios.

@palsivertsen
Copy link

@palsivertsen palsivertsen commented Dec 3, 2019

Any news on this?

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Dec 3, 2019

There has been some recent work on #14565. There has not been any work on the go tool that I know of. I expect that any such work would be reported here.

@thepudds
Copy link

@thepudds thepudds commented Dec 3, 2019

The proposal document has a section at the end that covers recent related work (though the nice recent work by @mdempsky in #14565 to add initial fuzzing coverage instrumentation in the go compiler is not yet mentioned there).

@palsivertsen regarding:

Fuzz function could look something like this:

func FuzzXxx(f *fuzz.Fuzzer) {
var ints []int
f.Fuzz(&ints)
sort.Ints(s)
}

FYI, fuzzing rich signatures is supported by the fzgo tool (which is WIP prototype that follows this #19109 proposal of integrating first-class fuzzing into go test). That ability to fuzz rich signatures gives you similar flexibility to what you are suggesting there, although fzgo uses the coverage guidance from dvyukov/go-fuzz along with storage of interesting results in a corpus, which typically outperforms just randomly generating input based off of a seed (if that is what you are suggesting).

@extemporalgenome
Copy link
Contributor

@extemporalgenome extemporalgenome commented Feb 25, 2020

Following @flyingmutant's response, I agree that fuzzing as a first-class citizen with bring enormous benefit, but it needs to be more than just []byte inputs. When go-fuzz was initially released, I used it successfully to test parsers, but ran into obstacles applying fuzz testing to structured input. While go-fuzz could recognize the structure of JSON (or other repeated-structure textual formats), it could not recognize that I was using JSON as a means-to-an-end, and would spend the majority of its cycles fuzzing the JSON library, not the stateful high-level code I was hoping to test.

I believe there is a lot of opportunity for fuzzing to become a much better successor to testing/quick, perhaps even using source-guided value generation (e.g. of slices of structs, eventually with some field values generated from switch cases in the call-graph) instead of reflection-based APIs for common usecases. If well done, it could replace many, many table driven tests (the kind that's just hand-fuzzing) with simple Fuzz tests.

Conditions could also be statically specified, i.e.

func Fuzz(f *testing.F, a int, b struct { x int }) {
  // after the first *testing.F param, any other parameters may be used,
  // which will have generated values per iteration.

  // f.Require accepts only constant boolean-kinded expressions; toolchain
  // will reject if conditions are too complex or contradictory; multiple
  // f.Require calls are equivalent to a single call with &&'d expressions.
  f.Require(a > 0)
  f.Require(a < b.x && b.x < 1000)

  // ... actual test code that uses a and b
}
@palsivertsen
Copy link

@palsivertsen palsivertsen commented Mar 3, 2020

If we do type aware fuzzing, we can also create interesting features like automatic minimization. @flyingmutant does this excellently in his Rapid library.

@dvyukov
Copy link
Member

@dvyukov dvyukov commented Mar 3, 2020

@palsivertsen absolutely. Most non-structure-aware fuzzers do this too, including go-fuzz.

@flyingmutant
Copy link
Contributor

@flyingmutant flyingmutant commented Mar 4, 2020

@dvyukov you might be interested in how Hypothesis approaches structure-aware minimization -- it is quite a bit more powerful than what most property-based testing libraries do (while being byte-based and not type-based).

@networkimprov
Copy link

@networkimprov networkimprov commented Jul 22, 2020

I don't understand why the new design doc is supposed to be discussed on Reddit? Why isn't Github suitable? Could you use golang-nuts?

https://golang.org/s/draft-fuzzing-design

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Jul 23, 2020

The GitHub issue tracker is not a good place for discussion, because it hides comments and provides no threading. Reddit isn't bad in that regard.

@tooolbox
Copy link

@tooolbox tooolbox commented Jul 23, 2020

Eh. I do get the problem, but still prefer GitHub 🤷

@lavalamp
Copy link

@lavalamp lavalamp commented Oct 1, 2020

BTW, gofuzz now contains an adapter, so you can turn the []byte from go-fuzz into any structured data: https://godoc.org/github.com/google/gofuzz#NewFromGoFuzz

@tv42
Copy link

@tv42 tv42 commented Oct 1, 2020

@lavalamp Using go-fuzz's []byte as nothing but input to an PRNG would completely lose coverage-guided fuzzing though, wouldn't it? Any mutation to the []byte causes completely random codepath changes.

@lavalamp
Copy link

@lavalamp lavalamp commented Oct 1, 2020

@tv42 Take a look at the implementation-- 8 bytes are reserved for a seed, but the rest of the []byte is interpreted directly as if it were the output of the PRNG. It only actually uses the PRNG if it runs out of bytes :)

It's not a perfect system (e.g., not all bits are equally important to the output) but it's good enough that a good fuzzing algo should be able to make it work.

@josharian
Copy link
Contributor

@josharian josharian commented Oct 2, 2020

The PRNG is definitely going to waste cycles generating fuzzing outputs that are not well-targeted. From the go-fuzz perspective, it'd be better to have a way to signal that there aren't enough bytes and return. Right now the best you can do is return -1, but we could define another designated return value to mean "too short", and go-fuzz could use that as a cue to generate longer data.

cc @katiehockman for the successor to go-fuzz

@tv42
Copy link

@tv42 tv42 commented Oct 2, 2020

@lavalamp Okay ByteSource is trickier than it seemed. That still sounds like it'll exhaust the input most of the time, and use the PRNG. That'd be better translated into "uninteresting input", or a more explicit signal.

Of course, flipping the API around and producing data on-demand, as per the proposal, is a lot better.

@thepudds
Copy link

@thepudds thepudds commented Oct 2, 2020

Hi @lavalamp, using a set of bytes from the input as a seed makes it harder for the fuzzer to incrementally build out additional pieces of input after discovering new coverage, and does not play well with go-fuzz's sonar feature for automatically pulling out values from comparisons.

Within the current constraints of the dvyukov/go-fuzz and google/gofuzz, one thing you could do is return 0 for numbers once you run out of input bytes and at that point also only generate zero-length slices and strings, which makes the discovered coverage correlate better with the input []byte and generally gives go-fuzz more control.

That is the approach that fzgo (a prototype of this proposal) takes for structured fuzzing & fuzzing rich signatures, and I found that made a material difference in fuzzing efficiency.

Also, fzgo tries to play well with go-fuzz's sonar. Two sonar-related comments from fzgo's rich signature generation are here and here.

@lavalamp
Copy link

@lavalamp lavalamp commented Oct 2, 2020

Thanks for the details!

@katiehockman
Copy link
Member

@katiehockman katiehockman commented Feb 24, 2021

Note that #44551 has the latest proposal for adding fuzz testing to Go, so please direct feedback there.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet