go-fuzz icon indicating copy to clipboard operation
go-fuzz copied to clipboard

Support tests that accepts complex inputs

Open dvyukov opened this issue 8 years ago • 54 comments

Currently go-fuzz mutates and supplies to a test a byte slice, however there are cases when a test needs more complex, structured input. For example, a regexp test could accept 3 strings (regexp, replacement string and input for replacement). Or a BLAS test could accept 2 matrices of floats. It is possible to manually convert the byte slice into any necessary structure (e.g. by json unmarshal), but is tedious for complex inputs, gives unnecessary coverage, in some cases can render some inputs inputs (e.g. if it does not json unmarshal successfully) and makes mutations suboptimal.

We could allow the test function to accept several arguments of arbitrary types:

func Fuzz(s1, s2 string, n int, m []float64, x MyStruct) int

and go-fuzz will supply all these arguments. If necessary go-fuzz-build can help by extracting types and generating some thunks. Besides being very handy, it will also allow go-fuzz to do more efficient mutations (mutate each argument independently, or replace one of the arguments by the corresponding argument in another input). I think that internally go-fuzz could use some very simple serialization format to represent such inputs (json, or maybe something simpler) to store them in files and communicate with the test process.

dvyukov avatar Jul 30 '15 08:07 dvyukov

Related to testing/quick and https://github.com/google/gofuzz

dgryski avatar Jul 30 '15 09:07 dgryski

I guess there would also be the problem of getting the initial corpus in to the format that gofuzz expects.

Would it be useful to have a function that generates the initial corpus? For example, you would define func Fuzz(t T) int) and then something like func InitialCorpus() []T which would be called by go-fuzz if a flag was given. Then go-fuzz would call the InitialCorpus function and store the results in the chosen serialized format.

kisielk avatar Aug 06 '15 18:08 kisielk

I don't think requiring the use of encoding/gob is unreasonable.

dgryski avatar Aug 06 '15 18:08 dgryski

I guess there would also be the problem of getting the initial corpus in to the format that gofuzz expects.

Yes, probably. I don't know what is the right solution yet. But I don't want to design it until we have design and implementation for the main functionality. Once we have implementation of the main functionality, we can experiment with corpus creation.

dvyukov avatar Aug 06 '15 18:08 dvyukov

@dgryski iirc there's a fair bit of overhead in setting up a gob stream since it must also encode / decode the type information. If go-fuzz stays with the model of one file (and thus one gob stream) per input in the corpus that overhead could add up. On the other hand textual representations like JSON have the problem of needing to encode binary data with base64 or other textual encoding, that's not ideal either...

kisielk avatar Aug 06 '15 19:08 kisielk

I wonder if it would be possible to look at the random values testing/quick Config.Values consumes and adjust those for mutation.

tv42 avatar Aug 17 '15 22:08 tv42

@tv42 I don't get the idea. Please elaborate.

dvyukov avatar Aug 17 '15 22:08 dvyukov

@dvyukov So testing/quick is based on this idea of generating a random complex value, and feeding it either to a func(....) bool or to two functions and comparing their return values. Consider "crash fuzzing" a func([]byte) (crashed bool) of sorts.

math/rand internals are bit trickier but for the sake of this argument let's say a PRNG is a func() byte (in reality, as far as I can see it comes down to rand.Seed.Int63).

Now, instead of a fetching these random values from /dev/urandom or PRNG, imagine you do that once, while writing down the values you returned. This list of random bytes is now your []byte, your "entropy corpus". Except because of the way the randomness chains on itself, after tiny changes, it can use wildly different amounts of randomness, so you need to be ready to extend it with more random bytes, if asked for.

Now imagine each testing/quick Config.Values call just consumes from such "entropy corpus", and you mutate it between each run.

testing/quick won't quite work like that, currently; e.g. you can't see when it switches from one check function call to the next. (UPDATE: yes you can, one Config.Values call is exactly that)

Does this clarify what I was thinking about?

tv42 avatar Aug 17 '15 23:08 tv42

@tv42 I see what you mean now. Yes, it is possible to do, and it is possible to do now. If you need an int and a string, you use first 4 bytes of input as the int, next byte as string length and the remaining bytes as string data. As far as I understand, what you propose is an automation of this process. But there are two issues with this approach:

  1. If go-fuzz does not understand structure of the data, it will generate broken inputs. For example, you read string length from the input and then want to read string data, but there are no more bytes in the input (go-fuzz trimmed it). Or, on the other hand, there can be excessive unused bytes in the input, and go-fuzz will spend iterations on mutating these unused bytes.
  2. The idea of guided fuzzing is that mutations are primitive, that is, slightly alter input. If go-fuzz does not understand structure of the data, it will do mutations that radically alter input. And on the other hand it will have troubles to do some primitive mutations like appending a byte to a string, because it requires increment of a particular byte and insertion of a byte into particular position.

So I would prefer to make go-fuzz aware of the input structure.

dvyukov avatar Aug 18 '15 10:08 dvyukov

In issue 86 I was talking about QuickCheck. This is the best talk I could find about it. https://www.youtube.com/watch?v=zi0rHwfiX1Q I think testing/quick was a start, but without shrinking and parallel API calls, people are unfortunately not getting too enthusiastic about property based testing. Obviously the ideal would be to have a proper implementation of QuickCheck in go. On second thought though I think go-fuzz does something a bit different, because I think it also instruments the code?

awalterschulze avatar Sep 14 '15 08:09 awalterschulze

On second thought though I think go-fuzz does something a bit different, because I think it also instruments the code?

Yes, it does. With the goal of increasing code coverage with the generated inputs.

dvyukov avatar Sep 14 '15 08:09 dvyukov

Yes see thats great on its own :) But if it were possible to combine that with typed fields as mentioned here and shrinking as implemented by QuickCheck that would be another level of awesome.

awalterschulze avatar Sep 14 '15 11:09 awalterschulze

Can you briefly describe the idea of shrinking and parallel API calls here?

dvyukov avatar Sep 14 '15 11:09 dvyukov

I think John Hughes does it best, but I'll try.

Shrinking is done when a bug is found. It finds the smallest example that also produces the error. This can save hours/days/weeks of a developer's time. This smallest example is deterministic and when the fuzzing is rerun it consistently reproduces the same smallest example.

At the moment Fuzz is normally used to test a user specified sequence of API calls. It should be possible to do API calls in a fuzzed order, given some property constraints regarding setup, shutdown, etc. and make sure that your testing properties hold. After this sequential property based testing for an API is possible the next step is also be able to do parallel testing of these API calls. How this works in QuickCheck is a mystery to me.

The idea is that you should be able to build a super simple inefficient one process model which describes your system. This model is your testing properties.
Then you should give some other properties regarding how the API should be used, setup, shutdown, etc. Finally you should be able to run quickfuzz against your simple model and your real world optimized distributed model and always get the same answer.

awalterschulze avatar Sep 14 '15 11:09 awalterschulze

It finds the smallest example that also produces the error.

go-fuzz does this for crashes and also for inputs in corpus. I.e. when it discovers an input that gives new code coverage, it minimizes the input to minimal form that still gives the same new code coverage.

It should be possible to do API calls in a fuzzed order, given some property constraints regarding setup, shutdown, etc. and make sure that your testing properties hold.

This is possible to some degree today:

func Fuzz(data []byte) int {
  api_init()
  if data[0]%2 == 0 {
    api_call1()
    api_call2()
  } else {
    api_call2()
    api_call1()
  }
  api_fini()
}

I am not sure what would be a better API for this that go-fuzz can provide. Well, the "complex inputs" as described in the issue description will make this simpler as you can explicitly accept the bool or an array of API call identifiers to execute in test.

dvyukov avatar Sep 14 '15 12:09 dvyukov

Ok wow that is quite impressive you not only shrink to the same error type, but also the same code coverage.

Complex inputs would definitely help, but I think a little more is required. Different API calls have different numbers and types of parameters.

Lets think about fuzzing a proper memcache service or something like that and imagine that each test starts with a clean memcache.

connect()
close()
add(key, value) error
remove(key) error
size() int
get(key) []value

As my model I might use a simple interface on a map[key][]value

I want my ideal fuzzing program to call these methods in random orders with random values and even in parallel and check them against my model.

awalterschulze avatar Sep 14 '15 13:09 awalterschulze

How can such look like (of how does it look in QuickCheck)?

I am working on something similar for syscalls (an input is a sequence of random syscalls with their arguments), but is quite specialized system. I am not sure how to generalize it.

dvyukov avatar Sep 14 '15 13:09 dvyukov

I am far from a QuickCheck expert, I have only used it once or twice in haskell. In the video though, they show how they tested a database in the same way.

awalterschulze avatar Sep 14 '15 13:09 awalterschulze

SmartCheck: Automatic and Efficient Counterexample Reduction and Generalization https://www.cs.indiana.edu/~lepike/pubs/smartcheck.pdf

Amd the Haskell implementation: https://github.com/leepike/SmartCheck

dgryski avatar Sep 26 '15 08:09 dgryski

Excellent paper and nice reference to John Hughes at the end.

awalterschulze avatar Oct 01 '15 19:10 awalterschulze

Also http://www.eecs.northwestern.edu/~robby/pubs/papers/oopsla2010-kff.pdf

dgryski avatar Oct 06 '15 09:10 dgryski

And a property-based testing implementation in C, which might be easier to take ideas from than the functional-based side of things. https://github.com/silentbicycle/theft

I'm getting more and more convinced that go-fuzz is the wrong kind of place for this sort of logic.

dgryski avatar Oct 06 '15 09:10 dgryski

I found the oopsla paper quite hard to understand. I saw some random path finding use types which was very interesting, but then it, unfortunately, started loosing me.

If I understand the gofuzz instrumentation logic correctly, I think it should be able to generate random inputs in a more sophisticated manner, than just plain random. Shrinking the test input might be an orthogonal problem.

Why do you think it is not a good fit?

awalterschulze avatar Oct 19 '15 17:10 awalterschulze

FWIW, go-fuzz already does input shrinking (it is called minimization throughout the code).

dvyukov avatar Oct 19 '15 17:10 dvyukov

I am sorry, but I didn't believe you. It sounded too good to be true. So I finally tried it

func Fuzz(buf []byte) int {
    total := 0
    for i := 0; i < len(buf); i++ {
        if i%2 == 0 {
            total += int(buf[i])
        } else {
            total -= int(buf[i])
        }
    }
    if total == 42 {
        panic("yeah")
    }
    return 1
}

go-fuzz finds one crasher in a million runs and guess what its the byte 42 or ascii * Perfect :)

Then I tried to enforce some length

package whatthefuzz

import "fmt"

func Fuzz(buf []byte) int {
    total := 0
    for i := 0; i < len(buf); i++ {
        if i%2 == 0 {
            total += int(buf[i])
        } else {
            total -= int(buf[i])
        }
    }
    if total == 42 && len(buf) >= 42 {
        fmt.Printf("%#v\n", buf)
        panic("yeah")
    }
    return 1
}

And I again only got one crasher, yeah.

[]byte{0x32, 0x32, 0x32, 0x30, 0x34, 0x34, 0x36, 0x30, 0x34, 0x39, 0x32, 0x35, 0x30, 0x33, 0x31, 0x33, 0x30, 0x38, 0x30, 0x38, 0x1a, 0x37, 0x32, 0x36, 0x0, 0x0, 0x1, 0x0, 0x0, 0x4, 0x0, 0x0, 0x34, 0x30, 0x36, 0x32, 0x5b, 0x85, 0x91, 0xc4, 0x9a, 0x17, 0x35}

I think the bytes could have been less complicated, for example

[]byte{0x1, 0x0, 0x1, 0x0, 0x1, 0x0, 0x1, 0x0, 0x1, 0x0, 0x1, 0x0 ...}

Or even

[]byte{0x42, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0 ...}

So there is definitely some shrinking and the shrinking seems to find the shortest example, but not necessarily the simplest example.

awalterschulze avatar Oct 19 '15 19:10 awalterschulze

I think the current minimization is good enough. Minimization is generally NP-hard, because there can be arbitrary dependencies between bytes and length. So to do complete minimization one would need to try all possible byte sequences. Note that go-fuzz should try to replace byte that you are not looking at at all with ascii 0. This is linear problem.

dvyukov avatar Oct 19 '15 19:10 dvyukov

theft does not try all combinations, but rather has some strategies for shrinking.

Cool stuff @ ascii 0

package whatthefuzz

import "fmt"

func Fuzz(buf []byte) int {
    total := 0
    for i := 0; i < len(buf); i++ {
        if i%2 == 0 {
            total += int(buf[i])
        }
    }
    if total == 42 && len(buf) >= 7 {
        fmt.Printf("%v\n", buf)
        panic("yeah")
    }
    return 1
}

returns the following crasher

[42 48 0 48 0 48 0]

I think this works pretty well, since 48 is ascii 0.

awalterschulze avatar Oct 20 '15 07:10 awalterschulze

Only semi-related but I figured I should record this here for interested parties.

Earlier discussion here has brought up the idea of using the fuzz input []byte as a command sequence to construct a more complex data structure. Here's a different take on that, for interactive apps: take it to be a stream of user input: http://caolanm.blogspot.com/2015/10/finding-ui-crashes-by-fuzzing-input.html

tv42 avatar Nov 05 '15 03:11 tv42

If we have structured input we can access via reflection, it appears the best minimization algorithm is http://blog.acolyer.org/2015/11/17/hierarchical-delta-debugging/

dgryski avatar Jan 15 '16 09:01 dgryski

@tv42 about your comment about a random generator being something that generates bytes A random generator can be seen as an io.Reader. math/rand and crypto/rand have a func Read([]byte) (n int, err error): https://golang.org/pkg/math/rand/#Read https://golang.org/pkg/crypto/rand/#Read This is very useful to make a library that depends on a random generator to be independent of the implementation of that generator.

dolmen avatar Mar 15 '17 14:03 dolmen

https://github.com/mschoch/smat is a library that essentially converts the []byte from go-fuzz into state machine transitions, where the transition can call methods of the system under test. Interesting.

Doesn't seem to touch upon the part of creating complex data structures.

tv42 avatar Oct 09 '17 22:10 tv42

@tv42 @mschoch

Interesting

I don't see that it passes fuzz data []byte to actions. I guess they also want some randomness.

This somewhat related to what we do in syzkaller for system calls: https://github.com/google/syzkaller/blob/master/sys/linux/sys.txt

Namely, we have descriptions of calls along the lines of:

resource fd

open(name filename, ...) fd
read(fd fd, ...)
write(fd fd, ...)
close(fd fd)

And from that we can generate/mutate random sequences of calls with random arguments:

r0 = open("foo", ...)
write(r0, ....)
write(r0, ....)
read(r0, ....)
close(r0)

We don't have states per se besides constructors, i.e. there is no way to create an instance of fd resource other than calling open(). We could probably do destructors as well, but we don't at the moment.

Wonder if it's possible to figure out such description for Go types based solely on conventions. E.g. a resource is create by MakeFoo/NewFoo functions, and then if there is Close then it's a terminator, and any other methods can be called in arbitrary order between constructor and terminator.

dvyukov avatar Oct 10 '17 10:10 dvyukov

@dvyukov https://github.com/mschoch/smat/issues/2 looks like the right issue for passing fuzz data []byte to actions. And yes smat seems a bit too simplistic currently, but still, it's interesting to see these ideas pop up.

tv42 avatar Oct 10 '17 16:10 tv42

A minimal implementation of this might be to add a helper function to turn the []byte into a structure with a dumb application of binary.Read or equivalent. More intelligence can be added later.

dgryski avatar Dec 26 '17 18:12 dgryski

FWIW, I've implemented a property testing library for Go called rapid, which supports both automatic shrinking and stateful state machine based tests (which look like this). Like popular Hypothesis library, it is based internally on a stream of random data with lightweight structure on top (nested spans with free-form labels). Despite being really simple, this data structure is sufficient for quite good automatic shrinking (or mutation, which is quite similar), without shrinker/mutator having to know anything about kind of data that was generated.

As I've argued in https://github.com/golang/go/issues/19109#issuecomment-493241857, https://github.com/dvyukov/go-fuzz/issues/218#issuecomment-493269310 and https://github.com/dvyukov/go-fuzz/issues/218#issuecomment-493422943, I'd very much prefer go-fuzz to provide an interface like that instead of implementing higher-level data generation directly, which would quite heavily limit the ability to construct stateful property-based tests on top of go-fuzz.

flyingmutant avatar May 17 '19 10:05 flyingmutant

@flyingmutant what exactly do you mean by "stateful state machine based tests"? Is it calling a sequence of methods on an object? If yes, then this works with upfront data too. Namely, the input data is an array, where each element represents one method invocation, and contains method ID and the arguments.

The additional constraints can be expressed as field tags, for example:

    Data []byte `fuzz:"ascii,len=10:20"`

As noted before, unknown structure of inputs data does not play well with mutation and some other aspects of fuzzing.

Also to make fuzzing a standard technique used by majority of developers rather then a handful of security researchers, we need to make it really easy to use. Like absolutely easy. On any small complication we lose half of potential users. Security researchers are willing to send lots of time on each fuzzer, craft the data, analyze coverage, add some knobs to the code, comments out code that is hard to fuzz, collect corpuses, etc. The goal here is not require any of this. I've looked at your library and it has 82 generators and on top of it some maps and filters. It looks too complex. And since there are 82 most likely it's not the complete list and there will be more. Such fat interface is additionally problematic for inclusion into standard library and will be almost impossible to ratify. And all ranges, min/max, ascii, etc are mostly not necessary with good guided fuzzing.

dvyukov avatar May 17 '19 11:05 dvyukov

By "stateful state machine based tests" I mean calling a sequence of methods on an object, where set of valid methods and arguments can depend on the current state of the object. How do you generate method N+1 with valid arguments upfront in this case, without executing the N methods before? And without this "stateful" part it is really hard to test most real world systems conveniently or efficiently.

Regarding your points about ease of use I 100% agree. The API I've chosen for specifying generators in rapid might very well be too verbose (although I don't think emphasizing the number 82 does justice to it), and I am definitely not promoting it here. However, please consider that most modern property-based testing libraries have moved away from type-based (or metadata-based) generation, since it turned out to be non-ergonomic, even in static type-rich languages like Haskell (here is an article on this topic).

The main point I am trying to argue is that testing of most stateful systems requires ability to get new random data on as-needed basis without specifying any kind of fixed schema upfront. May I suggest the queue test from rapid as a simple "stateful" test example, so that we can see if we can improve upon its ergonomic with the "upfront" design?

flyingmutant avatar May 17 '19 13:05 flyingmutant

How do you generate method N+1 with valid arguments upfront in this case, without executing the N methods before?

Just randomly and then rely on feedback and mutations. The queue test in the proposed interface may look like the following. This is shorter, easier to read/write and looks simper to me.

func FuzzQueue(f *testing.F, size int, ops []int) {
	var state []int
	q := NewQueue(size)
	for _, v := range ops {
		if v >= 0 && len(state) < size || len(state) == 0 {
			q.Push(v)
			state = append(state, v)
		} else {
			if state[0] != q.Pop() {
				f.Failf(...)
			}
			state = state[1:]
		}
	}
}

dvyukov avatar May 17 '19 14:05 dvyukov

And all ranges, min/max, ascii, etc are mostly not necessary with good guided fuzzing.

There are several counter-arguments to this.

  1. A lot of properties worth testing are non-total and hold only for some specific kinds of inputs. How can we express them without ability to specify constraints on input data?
  2. Specifying what kind of input data our test requires drastically improves valid data generation hit rate, to the point that most property-based testing libraries consider only 100 or 200 randomized test runs a good default.
  3. Most importantly: without composition-based generators that specify what constitutes valid data, automatic shrinking fill quickly break down and give up in any non-trivial case. And good automatic shrinking is a must for property-based testing to have any kind of mainstream adoption. People tend to simply ignore failures that look sufficiently complex, and without good automatic shrinking almost all do.

flyingmutant avatar May 17 '19 14:05 flyingmutant

And all ranges, min/max, ascii, etc are mostly not necessary with good guided fuzzing.

There are several counter-arguments to this.

  1. A lot of properties worth testing are non-total and hold only for some specific kinds of inputs. How can we express them without ability to specify constraints on input data?

If I understand the question correctly, then checking if the property should hold for the current input data, and if yes, checking if it actually holds. If that property was expressed with generators somehow, then it should be check-able with imperative code too (the opposite may not always be true).

  1. Specifying what kind of input data our test requires drastically improves valid data generation hit rate, to the point that most property-based testing libraries consider only 100 or 200 randomized test runs a good default.

Some hits may be possible, see: https://github.com/dvyukov/go-fuzz/issues/65#issuecomment-493426083 But otherwise just giving up absolute efficiency in the name of simplicity. A CI can generally do 100B or 200B inputs, we don't need to fit all testing in into 100/200 inputs. Also feedback and mutations figure out the constraints automatically over time. Also if I spend several days on it, I will probably beat the property-based engine by a large margin too. It's always a tradeoff.

  1. Most importantly: without composition-based generators that specify what constitutes valid data, automatic shrinking fill quickly break down and give up in any non-trivial case. And good automatic shrinking is a must for property-based testing to have any kind of mainstream adoption. People tend to simply ignore failures that look sufficiently complex, and without good automatic shrinking almost all do.

What is the problem with shrinking? I did minimization for both interesting inputs and crashers in multiple engines without composition-based generators and without any problems.

dvyukov avatar May 17 '19 14:05 dvyukov

But otherwise just giving up absolute efficiency in the name of simplicity. A CI can generally do 100B or 200B inputs, we don't need to fit all testing in into 100/200 inputs. Also feedback and mutations figure out the constraints automatically over time. Also if I spend several days on it, I will probably beat the property-based engine by a large margin too. It's always a tradeoff.

What is the problem with shrinking? I did minimization for both interesting inputs and crashers in multiple engines without composition-based generators and without any problems.

I'd say these points are mostly about efficiency, which is especially important when testing something slow like an HTTP API.

Efficient generation and shrinking allow to use lightweight fuzzing as part of the normal interactive go test workflow everybody is used to already. This way, fuzzing can be gradually introduced and be useful even without always-on CI infrastructure.

flyingmutant avatar May 17 '19 15:05 flyingmutant

I don't question that all else being equal faster is better.

dvyukov avatar May 17 '19 15:05 dvyukov

func FuzzQueue(f *testing.F, size int, ops []int) {
	var state []int
	q := NewQueue(size)
	for _, v := range ops {
		if v >= 0 && len(state) < size || len(state) == 0 {
			q.Push(v)
			state = append(state, v)
		} else {
			if state[0] != q.Pop() {
				f.Failf(...)
			}
			state = state[1:]
		}
	}
}

Thanks a lot for the example, it looks simple indeed.

Let's say we introduce a new method Comment(index int, comment string) which associates comment with queue element at index. Can you please show how this code should be extended to cover it?

flyingmutant avatar May 17 '19 16:05 flyingmutant

We need to figure it out yet. There should be some way to represent something like a C union. Most likely it should be based on interface{}, but then the question is how to associate set of options suitable for that interface. I don't know what's the best way to do it yet.

dvyukov avatar May 17 '19 16:05 dvyukov

So the idea is to simply have something like []MethodAndArgsUnion as input, and rely only on random generation + mutation with feedback to get valid sequences? With invalid inputs calling something like f.Skip().

flyingmutant avatar May 17 '19 16:05 flyingmutant

So the idea is to simply have something like []MethodAndArgsUnion as input

yes

mutation with feedback to get valid sequences?

yes also potentially hints/constraints as field tags

With invalid inputs calling something like f.Skip().

there are several options:

  • skip the whole input
  • skip the single element (e.g. don't pop from an empty queue)
  • fix up the element, e.g. this fixes up invalid pops: https://github.com/dvyukov/go-fuzz/issues/65#issuecomment-493470662 or if domain is only ['Q', 'W', 'E'], we could do something like []byte{'Q', 'W', 'E'}[data % 3]

If we use generator functions with constraints and have e.g. IntRange(5, 10). The question it should strictly obey they the range or treat it as a hint only? If it produces only values in [5,10], then it removes the concerns of how to deal with invalid data (we generate only valid data). But it limits testing: developer by definition does not know where the bugs are! Or they would fix them already. So if we treat the range only as hint to find unexpected bugs, the we have all the same concerns and options for handling of invalid data.

dvyukov avatar May 20 '19 14:05 dvyukov

From a property-based testing standpoint, we start from properties, with different ones holding for inputs satisfying the preconditions and arbitrary inputs. So we should have 2 tests with different strict constraints:

  • TestFooDoesNotCrash: given i <- Ints(), assert foo(i) does not crash
  • TestFooIsLessThanBar: given i <- IntsRange(5, 10), assert foo(i) < bar(i)

For fuzzing-based approach, while explicit generators are not required, [5, 10] constraint should still appear in the test:

func FuzzFoo(f *fuzz.F, i int) {
        a := foo(i)
        if i >= 5 && i <= 10 {
                if a >= bar(i) {
                        f.Fail()
                }
        }
}

So on the one hand we have the convenience of constraints being figured automatically from the code, and on the other being explicit about properties and inputs brings major efficiency advantages (and potentially better separation of concerns).

IMHO having lightweight fuzzing available as part of the regular go test workflow is a must for widespread adoption. For that, I'd say that sub-100ms fuzz runs should give useful results (current overhead of rapid.Check is around 0.2ms). I am not qualified to judge if this is realistic with constraint-free fuzzing.

Is there a chance that fuzz.F can provide an (additional?) GetRandomData()-based interface like the one I sketched in https://github.com/golang/go/issues/19109#issuecomment-493241857, on top of which a constrained generator library can be built?

flyingmutant avatar May 20 '19 18:05 flyingmutant

For fuzzing-based approach, while explicit generators are not required, [5, 10] constraint should still appear in the test:

A big part of the point of fuzzing, from the security perspective, is to feed the code invalid inputs and see what happens. From that point of view, it shouldn't. If that int pretends to be an argument from an RPC call, then it really should explore all possible values.

The disconnect we're seeing here is people thinking of "testing an API called by other parts of my app" vs "testing an untrusted input mechanism".

tv42 avatar May 20 '19 23:05 tv42

Is there a chance that fuzz.F can provide an (additional?) GetRandomData()-based interface like the one I sketched in golang/go#19109 (comment), on top of which a constrained generator library can be built?

I don't know. Somebody needs to sketch an actual proposal and the proposed interface. If it's added "on top", can it be added later? If yes, then it can be considered completely separately. Can it be a helper that accepts a []byte as source of randomness and slices it into different types with required properties?

Note that the proposed approach can also do good testing in short time provided that there is already a preaccumulated corpus. So if one did a more prolonged testing session (which I would say is required anyway) and persisted the corpus somewhere, later it's possible to do regression testing with maximum coverage quickly.

dvyukov avatar May 21 '19 04:05 dvyukov

The disconnect we're seeing here is people thinking of "testing an API called by other parts of my app" vs "testing an untrusted input mechanism".

(Modern) fuzzing has appeared in the context of security and because of that it used to operate with []byte just because that's what is an external input (from disk/network), also some of them tend to assume that the user has desire to spend lots of time on the fuzzer, tune knobs, precollect corpus, etc.

This is significantly different from testing. Testing that is done during development, by a developer, testing of any code, not just the one that accepts solely []byte.

I think bridging this gap and bringing fuzzing to developers for API testing is the next big advancement in software quality. From this point it's important to provide an easy way to generate structured, typed inputs rather than just []byte. The API does not necessary use completely untrusted inputs, but the inputs do not necessary come from a single call site that we trust completely either. It's somewhere in between, let's say we want to make it "robust" and high-quality. Like a regexp library or a compiler.

dvyukov avatar May 21 '19 05:05 dvyukov

Here is a small but realistic example (in Python) of fuzz-based (or property-based) approach being introduced as an upgrade of the usual example-based test.

Notice that the software being tested does not have to belong to some special "robust" and high-quality category. Rather, fuzz-based tests should be applicable almost everywhere regular example-based tests are, and with only a small increase in test complexity give a lot more confidence in software quality.

flyingmutant avatar May 21 '19 13:05 flyingmutant

Good overview of structure aware fuzzing approaches (on top of libFuzzer): https://github.com/google/fuzzer-test-suite/blob/master/tutorial/structure-aware-fuzzing.md

flyingmutant avatar Jul 15 '19 16:07 flyingmutant

@thepudds did you implement this in fzgo? I have some memories that somebody implemented this somewhere already...

dvyukov avatar Jun 13 '20 13:06 dvyukov

Hi @dvyukov 👋

Yes, I support this in https://github.com/thepudds/fzgo

Rich signatures like FuzzRegexp(re string, input []byte, posix bool) are supported, as well as the classic Fuzz(data []byte) int form used by go-fuzz.

Public members of structs in a signature are also mutated recursively. (And I have a private branch that also handles a dozen or so common interfaces like io.Reader).

The underlying smarts for the actual fuzzing engine remain go-fuzz.

(On mobile, so just a quick note).

thepudds avatar Jun 14 '20 22:06 thepudds