8 ms·

Go Fuzzing

269 points by 0xedb 5y ago

cinntaile 5y ago
What would you say are the main differences between a fuzzer and QuickCheck? The authors of quickcheck don't call it a fuzzer so I assume there is some difference but both seem to randomize inputs?
- exdsq 5y ago
  You're comparing fuzzing and property based testing. Fuzzing is a way of generating a load of random inputs for a system under test. For example if you had a function add(a, b) -> int you'd pass in numbers, strings, bytes, whatever you want and it'll let you know if it breaks. Property based testing is similar but you check if properties hold across these values and the tool will then shrink this to the simplest case. For example you'd say that add(a, b) takes two integers and regardless of the numbers it should always have the associative property. So in fuzzing you put in junk an see what happens, in pbt you define properties and check they hold across sane inputs.
  - Too 5y ago
    Isn't fuzzing more than just random though? I was under the impression fuzzing could introspect branches in the code and work its way backwards to generate inputs to reach that coverage?
    - exdsq 5y ago
      Yeah it can get that advanced! But the distinction is still generating junk until you get errors while pbt is about checking business logic (properties) hold under random generators. Saying this I’m sure the cutting edge of both overlap!
- Seirdy 5y ago
  I think that fuzz testing is best described in the context of two other types of tests that go beyond "traditional" unit/integration tests: property and mutation testing. The three complement each other so well in ways that are hard to describe without trying them yourself. Quickcheck is a property tester, which essentially can be thought of as a "bytecode fuzzer that also happens to check for correct behavior". It uses an algorithm to generate arbitrary inputs that satisfy a set of constraints, and then ensures that the outputs demonstrate a property of the function being fulfilled. Think about mathematical properties of functions or the lack thereof: commutativity, associativity, and even properties of linear relations you might remember from Linear Algebra. Values that violate the expected properties are saved; you can build unit tests that check these values later or cache them for future runs. Fuzzing is a form of black-box testing that repeatedly runs software differently and tries to crash it. Causes and behavior of crashes can later be inspected. Mutation testing alters every statement in your code one at a time to change its behavior. Each alteration is a "mutant". If an alteration does not cause one of your tests to fail, the mutant has not been "killed". Your goal is to have a good kill ratio. This is a far better metric for test effectiveness and dead code elimination than statement/branch coverage. Property testing is kind of like a bytecode fuzzer and mutation testing is very much like a fuzzer for your tests. But property testing is a white-box form of testing with good knowledge of your code; I'd consuder mutation testing to be "grey-box" testing of your test code. "True" fuzz testing is as black-box as you can get: just let an algorithm run your program for a long time (anywhere from hours to months) to find subtle bugs (crashes and other black-box failures) at scales humans struggle with. In conclusion: Yo dawg, I heard you like tests. So I fuzzed the mutation tests on your property tests to see if arbitrary input on arbitrary code produced arbitrary output without arbitrary exits.
- noctune 5y ago
  IMO, it's much the same and pretty much only a question of API. Property-based testing (like QuickCheck) generates randomness using a PRNG, creates a structure from that, and checks that some property holds for that structure. A fuzzer generates some arbitrary input and usually checks that the program returns successfully (i.e. doesn't crash). The reason I think they are the same is that we can rather easily turn one into the other and vice versa: - A PBT test can be turned into a fuzzer-test by sourcing the randomness from the input instead of a PRNG and failing the program if the property does not hold. - A fuzz-test can be turned into a PBT by sourcing the input from a PRNG. The real difference is that fuzzers tend to be coverage-guided, i.e. a fuzzer will use what part of your code is executed to guide its mutations and thus steer it towards more "interesting" inputs.
damagednoob 5y ago
I will never understand why this has been included in the standard library instead of as a standalone library available for download. Now it's locked to the Go release cycle and have the potential to languish because of backward compatibility concerns. The decision to include it is perplexing when other language ecosystems have chosen to keep this kind of functionality out of the standard lib, e.g. requests in python[1]. To quote Kenneth Reitz: "...the standard library is where a library goes to die." [1] https://github.com/psf/requests/issues/2424 https://github.com/psf/requests/issues/2424
- dainiusse 5y ago
  I think it is great in general. OTOH - nobody prohibits to use any third party library whoever wants to. Third party libraries also die like - https://github.com/go-check/check https://github.com/go-check/check
- Scaevolus 5y ago
  Python had an 18 month release cycle for most of its life (now 12 month), while Go has a 6 month release cycle. Many Python devs use the OS packaged Python versions, while Go devs tend to use the latest release. Integrating this in the stdlib means that more people will use basic fuzzing functionality. There's nothing preventing third party fuzzers from continuing to develop.
- smasher164 5y ago
  The Go fuzzing tool takes advantage of compiler instrumentation. It can also work with built-in Go types, in comparison to traditional fuzzing tools that just work with bytes. Additionally, integrating it into the testing tool allows it to be as easy to write as a unit test. This can help provide a batteries-included fuzzing experience.
  - staticassertion 5y ago
    This is just a work around for: a) A lack of strong typing b) A custom compiler toolchain llvm already has instrumentation/ coverage support and generics make it easy to work with higher level constructs than bytes, although you generally do want to just work with bytes when fuzzing imo. The language is weak, therefor the language has to add more and more batteries-included because extending it is purposefully difficult.
ryanschneider 5y ago
Anyone seen good articles on converting go-fuzz tests to native fuzzing? Specifics on the new corpus format and a converter from go-fuzz would be really useful. It’s great to hear that the fuzzer is built on go-fuzz so hopefully the conversion process won’t be too bad: https://github.com/dvyukov/go-fuzz/issues/329 https://github.com/dvyukov/go-fuzz/issues/329
- morelisp 5y ago
  I've pre-emptively migrated a couple projects and found that loading the old corpus files wherever you already had them and then `Add`ing them as whatever new appropriate type was the easiest way. The inclusion of types necessitates at least a minor migration. I did not find any official documentation on the format, though it's trivial to read, e.g.: go test fuzz v1 string("\xff0") Overall while the API (and of course tooling) is a huge step forward, corpus management feels like a small step backwards compared to go-fuzz - I didn't find a way to pull non-crashers into an in-repo corpus other than manually copying them out of my cache directory. And one-file-per-case still blows up a lot of repo management tools.
- aleksi 5y ago
  https://pkg.go.dev/golang.org/x/tools@v0.1.8/cmd/file2fuzz https://pkg.go.dev/golang.org/x/tools@v0.1.8/cmd/file2fuzz
deleted 5y ago
[deleted]
staticassertion 5y ago
Great to see fuzzing becoming more mainstream. Ultimately we have absurd program states, with even a trivial program's state vastly exceeding the number of particles in the universe. We need to start finding order-of-magnitude-better approaches for testing. I almost always write generated tests at this point with unit tests being a fallback for slow code or niche cases. What I dont generally write though is fuzz tests, which would really be a 'next step'. In Rust it's not very hard to do so, but it hasn't quite hit the "trivial" mark yet for me, whereas quickcheck is virtually the same amount of work to use as to not use. Languages like Go adopting and mainstreaming these practices will be a benefit to everyone. I'm curious if there's documentation on: a) The coverage approach taken b) The mutation approach taken Can you configure these? Plugin different fuzzing backends?
- fpopa 5y ago
  What kind of generated tests are you writing? Is it more similar to 'golden files'? Generate expected output and assert versus current implementation output?
  - staticassertion 5y ago
    Just taking what would normally be a unit test and having the input values be generated. Some examples: 1. I have a test for encryption/decryption functions. The data that's provided for the plaintext, additional data, and key, is generated. The assertions are: assert_ne!(plaintext, encrypted_data); assert_eq!(plaintext, decrypted_data); assert_eq!(aad, decrypted_aad); etc 2. I have some generated integration tests. For example, in our product, there are certain properties that should always hold for a given database entry. I generate a new entry on every test and have the fields for that entry provided by quickcheck, then I perform the operation, query the database, and assert that properties on those values hold. So to answer your question, yes. Sometimes you want to check a concrete output (ie: "this base64 encoded string should always equal this other value) for sanity, but in general property tests give me more confidence. I find it works particularly well with a 'given, when, then' approach, personally. edit: I'll also note that for the base64 case I'd suggest: a) A hardcoded suite of values. b) Generate property tests. assert_eq!(value, base64decode(base64encode(value)); As well as things like "contains only these characters" and "ends with [=a-zA-Z]" etc. c) Oracle tests against a "known good" implementation.
dang 5y ago
Past related thread: Go: Fuzzing Is Beta Ready - https://news.ycombinator.com/item?id=27391048 https://news.ycombinator.com/item?id=27391048 - June 2021 (53 comments)
xiaq 5y ago
Fuzzing is awesome. I just discovered an accidental O(2^n) code path in my project with fuzzing and fixed it: https://github.com/elves/elvish/commit/9cda3f643efafce2df5671bbdd609b11b4b910d5 https://github.com/elves/elvish/commit/9cda3f643efafce2df567... Edit: shortly after I wrote this comment, fuzzing discovered another pathological input - and that was fixed in https://github.com/elves/elvish/commit/04173ee8ab3c7fc4a9e793f70a1e3b58b82d3728 https://github.com/elves/elvish/commit/04173ee8ab3c7fc4a9e79... (In case people are curious, the project is a Unix shell, Elvish: https://elv.sh https://elv.sh)
- omginternets 5y ago
  > I just discovered an accidental O(2^n) code path in my project with fuzzing and fixed it I've used fuzzing to find crash/panic conditions in Go, but never to find slow paths. How does that work?
  - xiaq 5y ago
    It timed out. Since this case is O(2^n) the fuzzer managed to build a relatively short input that caused the function to not terminate for a few minutes.
    - ninkendo 5y ago
      Oh wow, I misread your original post as O(n^2) and thought “no way a fuzz test would notice mere quadratic time complexity”, but exponential is another beast entirely :-D
      - val_deleplace 5y ago
        Mere quadratic time complexity is something I would expect to timeout and catch at fuzzing time, as long as we do encourage non-tiny inputs, say 10K and beyond.
    - omginternets 5y ago
      Oh, fair. I wonder if there is a practical, general way to test for expected time complexity using fuzz tests…
jrockway 5y ago
Like many others, this was the wakeup call I needed to download go1.18beta1 and start writing some fuzz tests. I unleashed it upon my JSON log viewer, which has the goal of never suppressing a line even in the face of egregious parse errors. (The last thing you need when software goes wrong is your UI hiding stuff from you, after all.) As expected, within seconds it found that the input `{"": 0}` causes a panic. (This is a weird special case that I handled for other classes of this problem, but not this exact case!) I also got to see what happens when you have more bytes on a line than bufio.MaxScanTokenSize and realized that that is pretty low for an interactive program, especially when all you can do is exit. The ergonomics are excellent. When the fuzzer finds a failing input, it creates a file that contains the test case. You check this in and future invocations of plain "go test ./..." will use this input. "go test -fuzz=FuzzWhatever what/ever" will cause it to search for more failing inputs. Really well-designed.
- shakezula 5y ago
  This is a great example of fuzz testing finding real bugs in the wild. I think people who are against or resistant to fuzz testing haven’t properly grokked where they should be used and what class of bugs they find.
stevekemp 5y ago
I guess I'm echoing others here, but fuzzing is magical. I've given introductions to fuzz-testing to more than a few developers, and found interesting bugs in my own code using them. Until now I've used "go-fuzz", but I'm very much looking forward to having real integrated fuzzing in the standard compiler/toolchain. That has to make things easier to explain and add to more projects. Even with "100% test coverage" finding bugs due to fuzzing shows how hard testing can be.

269 points by 0xedb 5y ago

What would you say are the main differences between a fuzzer and QuickCheck? The authors of quickcheck don't call it a fuzzer so I assume there is some difference but both seem to randomize inputs?

exdsq 5y ago
You're comparing fuzzing and property based testing. Fuzzing is a way of generating a load of random inputs for a system under test. For example if you had a function add(a, b) -> int you'd pass in numbers, strings, bytes, whatever you want and it'll let you know if it breaks. Property based testing is similar but you check if properties hold across these values and the tool will then shrink this to the simplest case. For example you'd say that add(a, b) takes two integers and regardless of the numbers it should always have the associative property. So in fuzzing you put in junk an see what happens, in pbt you define properties and check they hold across sane inputs.
- Too 5y ago
  Isn't fuzzing more than just random though? I was under the impression fuzzing could introspect branches in the code and work its way backwards to generate inputs to reach that coverage?
  - exdsq 5y ago
    Yeah it can get that advanced! But the distinction is still generating junk until you get errors while pbt is about checking business logic (properties) hold under random generators. Saying this I’m sure the cutting edge of both overlap!
Seirdy 5y ago
I think that fuzz testing is best described in the context of two other types of tests that go beyond "traditional" unit/integration tests: property and mutation testing. The three complement each other so well in ways that are hard to describe without trying them yourself. Quickcheck is a property tester, which essentially can be thought of as a "bytecode fuzzer that also happens to check for correct behavior". It uses an algorithm to generate arbitrary inputs that satisfy a set of constraints, and then ensures that the outputs demonstrate a property of the function being fulfilled. Think about mathematical properties of functions or the lack thereof: commutativity, associativity, and even properties of linear relations you might remember from Linear Algebra. Values that violate the expected properties are saved; you can build unit tests that check these values later or cache them for future runs. Fuzzing is a form of black-box testing that repeatedly runs software differently and tries to crash it. Causes and behavior of crashes can later be inspected. Mutation testing alters every statement in your code one at a time to change its behavior. Each alteration is a "mutant". If an alteration does not cause one of your tests to fail, the mutant has not been "killed". Your goal is to have a good kill ratio. This is a far better metric for test effectiveness and dead code elimination than statement/branch coverage. Property testing is kind of like a bytecode fuzzer and mutation testing is very much like a fuzzer for your tests. But property testing is a white-box form of testing with good knowledge of your code; I'd consuder mutation testing to be "grey-box" testing of your test code. "True" fuzz testing is as black-box as you can get: just let an algorithm run your program for a long time (anywhere from hours to months) to find subtle bugs (crashes and other black-box failures) at scales humans struggle with. In conclusion: Yo dawg, I heard you like tests. So I fuzzed the mutation tests on your property tests to see if arbitrary input on arbitrary code produced arbitrary output without arbitrary exits.
noctune 5y ago
IMO, it's much the same and pretty much only a question of API. Property-based testing (like QuickCheck) generates randomness using a PRNG, creates a structure from that, and checks that some property holds for that structure. A fuzzer generates some arbitrary input and usually checks that the program returns successfully (i.e. doesn't crash). The reason I think they are the same is that we can rather easily turn one into the other and vice versa: - A PBT test can be turned into a fuzzer-test by sourcing the randomness from the input instead of a PRNG and failing the program if the property does not hold. - A fuzz-test can be turned into a PBT by sourcing the input from a PRNG. The real difference is that fuzzers tend to be coverage-guided, i.e. a fuzzer will use what part of your code is executed to guide its mutations and thus steer it towards more "interesting" inputs.

damagednoob 5y ago

I will never understand why this has been included in the standard library instead of as a standalone library available for download. Now it's locked to the Go release cycle and have the potential to languish because of backward compatibility concerns. The decision to include it is perplexing when other language ecosystems have chosen to keep this kind of functionality out of the standard lib, e.g. requests in python[1]. To quote Kenneth Reitz: "...the standard library is where a library goes to die." [1] https://github.com/psf/requests/issues/2424 https://github.com/psf/requests/issues/2424

dainiusse 5y ago
I think it is great in general. OTOH - nobody prohibits to use any third party library whoever wants to. Third party libraries also die like - https://github.com/go-check/check https://github.com/go-check/check
Scaevolus 5y ago
Python had an 18 month release cycle for most of its life (now 12 month), while Go has a 6 month release cycle. Many Python devs use the OS packaged Python versions, while Go devs tend to use the latest release. Integrating this in the stdlib means that more people will use basic fuzzing functionality. There's nothing preventing third party fuzzers from continuing to develop.
smasher164 5y ago
The Go fuzzing tool takes advantage of compiler instrumentation. It can also work with built-in Go types, in comparison to traditional fuzzing tools that just work with bytes. Additionally, integrating it into the testing tool allows it to be as easy to write as a unit test. This can help provide a batteries-included fuzzing experience.
- staticassertion 5y ago
  This is just a work around for: a) A lack of strong typing b) A custom compiler toolchain llvm already has instrumentation/ coverage support and generics make it easy to work with higher level constructs than bytes, although you generally do want to just work with bytes when fuzzing imo. The language is weak, therefor the language has to add more and more batteries-included because extending it is purposefully difficult.

ryanschneider 5y ago

Anyone seen good articles on converting go-fuzz tests to native fuzzing? Specifics on the new corpus format and a converter from go-fuzz would be really useful. It’s great to hear that the fuzzer is built on go-fuzz so hopefully the conversion process won’t be too bad: https://github.com/dvyukov/go-fuzz/issues/329 https://github.com/dvyukov/go-fuzz/issues/329

morelisp 5y ago
I've pre-emptively migrated a couple projects and found that loading the old corpus files wherever you already had them and then `Add`ing them as whatever new appropriate type was the easiest way. The inclusion of types necessitates at least a minor migration. I did not find any official documentation on the format, though it's trivial to read, e.g.: go test fuzz v1 string("\xff0") Overall while the API (and of course tooling) is a huge step forward, corpus management feels like a small step backwards compared to go-fuzz - I didn't find a way to pull non-crashers into an in-repo corpus other than manually copying them out of my cache directory. And one-file-per-case still blows up a lot of repo management tools.
aleksi 5y ago
https://pkg.go.dev/golang.org/x/tools@v0.1.8/cmd/file2fuzz https://pkg.go.dev/golang.org/x/tools@v0.1.8/cmd/file2fuzz

deleted 5y ago

[deleted]

staticassertion 5y ago

Great to see fuzzing becoming more mainstream. Ultimately we have absurd program states, with even a trivial program's state vastly exceeding the number of particles in the universe. We need to start finding order-of-magnitude-better approaches for testing. I almost always write generated tests at this point with unit tests being a fallback for slow code or niche cases. What I dont generally write though is fuzz tests, which would really be a 'next step'. In Rust it's not very hard to do so, but it hasn't quite hit the "trivial" mark yet for me, whereas quickcheck is virtually the same amount of work to use as to not use. Languages like Go adopting and mainstreaming these practices will be a benefit to everyone. I'm curious if there's documentation on: a) The coverage approach taken b) The mutation approach taken Can you configure these? Plugin different fuzzing backends?

fpopa 5y ago
What kind of generated tests are you writing? Is it more similar to 'golden files'? Generate expected output and assert versus current implementation output?
- staticassertion 5y ago
  Just taking what would normally be a unit test and having the input values be generated. Some examples: 1. I have a test for encryption/decryption functions. The data that's provided for the plaintext, additional data, and key, is generated. The assertions are: assert_ne!(plaintext, encrypted_data); assert_eq!(plaintext, decrypted_data); assert_eq!(aad, decrypted_aad); etc 2. I have some generated integration tests. For example, in our product, there are certain properties that should always hold for a given database entry. I generate a new entry on every test and have the fields for that entry provided by quickcheck, then I perform the operation, query the database, and assert that properties on those values hold. So to answer your question, yes. Sometimes you want to check a concrete output (ie: "this base64 encoded string should always equal this other value) for sanity, but in general property tests give me more confidence. I find it works particularly well with a 'given, when, then' approach, personally. edit: I'll also note that for the base64 case I'd suggest: a) A hardcoded suite of values. b) Generate property tests. assert_eq!(value, base64decode(base64encode(value)); As well as things like "contains only these characters" and "ends with [=a-zA-Z]" etc. c) Oracle tests against a "known good" implementation.

dang 5y ago

Past related thread: Go: Fuzzing Is Beta Ready - https://news.ycombinator.com/item?id=27391048 https://news.ycombinator.com/item?id=27391048 - June 2021 (53 comments)

xiaq 5y ago

Fuzzing is awesome. I just discovered an accidental O(2^n) code path in my project with fuzzing and fixed it: https://github.com/elves/elvish/commit/9cda3f643efafce2df5671bbdd609b11b4b910d5 https://github.com/elves/elvish/commit/9cda3f643efafce2df567... Edit: shortly after I wrote this comment, fuzzing discovered another pathological input - and that was fixed in https://github.com/elves/elvish/commit/04173ee8ab3c7fc4a9e793f70a1e3b58b82d3728 https://github.com/elves/elvish/commit/04173ee8ab3c7fc4a9e79... (In case people are curious, the project is a Unix shell, Elvish: https://elv.sh https://elv.sh)

omginternets 5y ago
> I just discovered an accidental O(2^n) code path in my project with fuzzing and fixed it I've used fuzzing to find crash/panic conditions in Go, but never to find slow paths. How does that work?
- xiaq 5y ago
  It timed out. Since this case is O(2^n) the fuzzer managed to build a relatively short input that caused the function to not terminate for a few minutes.
  - ninkendo 5y ago
    Oh wow, I misread your original post as O(n^2) and thought “no way a fuzz test would notice mere quadratic time complexity”, but exponential is another beast entirely :-D
    - val_deleplace 5y ago
      Mere quadratic time complexity is something I would expect to timeout and catch at fuzzing time, as long as we do encourage non-tiny inputs, say 10K and beyond.
  - omginternets 5y ago
    Oh, fair. I wonder if there is a practical, general way to test for expected time complexity using fuzz tests…

jrockway 5y ago

Like many others, this was the wakeup call I needed to download go1.18beta1 and start writing some fuzz tests. I unleashed it upon my JSON log viewer, which has the goal of never suppressing a line even in the face of egregious parse errors. (The last thing you need when software goes wrong is your UI hiding stuff from you, after all.) As expected, within seconds it found that the input `{"": 0}` causes a panic. (This is a weird special case that I handled for other classes of this problem, but not this exact case!) I also got to see what happens when you have more bytes on a line than bufio.MaxScanTokenSize and realized that that is pretty low for an interactive program, especially when all you can do is exit. The ergonomics are excellent. When the fuzzer finds a failing input, it creates a file that contains the test case. You check this in and future invocations of plain "go test ./..." will use this input. "go test -fuzz=FuzzWhatever what/ever" will cause it to search for more failing inputs. Really well-designed.

shakezula 5y ago
This is a great example of fuzz testing finding real bugs in the wild. I think people who are against or resistant to fuzz testing haven’t properly grokked where they should be used and what class of bugs they find.

stevekemp 5y ago

I guess I'm echoing others here, but fuzzing is magical. I've given introductions to fuzz-testing to more than a few developers, and found interesting bugs in my own code using them. Until now I've used "go-fuzz", but I'm very much looking forward to having real integrated fuzzing in the standard compiler/toolchain. That has to make things easier to explain and add to more projects. Even with "100% test coverage" finding bugs due to fuzzing shows how hard testing can be.