5 ms·

With the advent of coverage based fuzzing, and how well supported it is in Go, what am I missing from not using one of the property based testing libraries? ht

With the advent of coverage based fuzzing, and how well supported it is in Go, what am I missing from not using one of the property based testing libraries? https://www.tedinski.com/2018/12/11/fuzzing-and-property-testing.html https://www.tedinski.com/2018/12/11/fuzzing-and-property-tes... Like, with the below fuzz test, and the corresponding invariant checks, isn't this all but equivalent to property tests? https://github.com/ncruces/aa/blob/505cbbf94973042cc7af4d6be6266454bb2d864e/aa_test.go#L374-L403 https://github.com/ncruces/aa/blob/505cbbf94973042cc7af4d6be... https://github.com/ncruces/aa/blob/505cbbf94973042cc7af4d6be6266454bb2d864e/util_test.go#L5-L28 https://github.com/ncruces/aa/blob/505cbbf94973042cc7af4d6be...

mrkeen 2y ago
I'm not sure how Go's fuzz tests differ from what you linked in your article, but you article said proper fuzzers need to run for days or weeks, and that PBT should approximately always chosen over fuzz testing. But I'd take one step back, and ask a more meta question about testing: does a successful test mean successful code, and vice-versa? Is there anything in Go's contract that specifies that the same inputs to the same code will yield the same output?
- randomdata 2y ago
  > does a successful test mean successful code A successful test implies that the documentation is true. That is, after all, why you are writing tests: Documentation – To explain to future developers the intent and usage behind the code you wrote. You could just as well write the documentation in Word instead, but then you'd lose the ability to perform machine verification of the documentation, which is a huge boon to moving codebases where the documentation and code are likely to fall out of sync if one is not incredibly careful (although perhaps LLMs will some day bridge that gap?). The documentation being true does not imply that the documentation is useful, of course. Writing useful documentation is still an art.
  - tennis_80 2y ago
    This is a reason I’m very keen on making sure tests are focused on requirements rather than code. A few jobs ago I would often be in a team where the entire team had turned over several times, we would be asked to do large updates to a legacy application or bump lots of dependencies and just not break anything. When pushed the product owner wouldn’t be able to describe what the app was supposed to do, particularly for unusual types of users (the account / user modelling was chaotic so say, several billing accounts per user, each with different products and access levels). At that point “foo calls bar” doesn’t clarify much intent.
bananapub 2y ago
fuzzing is clearly not a replacement for tests?
- deleted 2y ago
  [deleted]
- josephg 2y ago
  It kind of is. I often use randomised tests (fuzzing) for data structures and algorithm implementations. Throw a lot of asserts in and see if an hour of random input can find any edge cases I’ve missed. Usually the first time I run something like this it finds problems instantly. It’s very humbling. I find when I do this I don’t need to write by hand anywhere near as many tests to get my software working well. I also usually turn any failures found by the fuzzer into standalone unit tests, to make any regressions easier to find later.
  - ncruces 2y ago
    I agree, it can be. My example above matches yours (fuzzing a data structure). I coded some tests that ensure the data structure is useful, many of them test examples from papers describing the data structure, but that don't necessarily cover all the corner cases. Then I fuzzed it. I used Go's fuzzer, which is geared towards parsers and stuff. It can generate a stream of bytes and use that for fuzzing. The data structure is a set/map. So I interpret the stream of bytes as commands to add/remove random elements from the set/map. After I add an element, contains needs to return true; after I remove one, contains need to return false; if I put in a mapping, finding it must return what I just put there, etc. And at every step all the data structure invariants (that ensure logarithmic search, etc) need to hold. That was stupidly effective at finding a few bugs, all within seconds, all with sequences of less than a dozen operations. Then it stops. And you get 100% coverage. I'm assuming that, apart from ergonomics, where I kinda build my own state machine transitions out of a stream of bytes, the tooling actually seems more effective than property testing libraries. Still curious to understand what I'm missing out.
AlexErrant 2y ago
You're asserting properties, so IMO this meets the definition of PBTs ("every node of level greater than one has two children"). However, depending on the lib, you can get some nice quality of life improvements. One "nice to have" is shrinking. See the "Shrinking" section here https://tech.fpcomplete.com/blog/quickcheck-hedgehog-validity/ https://tech.fpcomplete.com/blog/quickcheck-hedgehog-validit... Having combinators to compose generators is also great. Libs may also have a known set of "bad" values that cause exceptional behavior.
- gavinhoward 2y ago
  AFL++, a fuzzer, has a tool to minimize (shrink) test cases.
- zarathustreal 2y ago
  “Properties” in the Property-based Testing sense refers to mathematical properties such as equality, associativity, commutivity, etc
- ncruces 2y ago
  The Go fuzzer, when it finds a failure, will also walk back and try to shrink inputs (and still trigger the same failure). Not sure how effective it is compared to other options, but I'm not totally missing out there. It also builds a corpus of interesting inputs over time (those that cause new branches to be taken, since that's its goal: improve coverage). I'm less sure about combinators.
kccqzy 2y ago
You can totally combine coverage based fuzzing with property based tests. When I was at Google, I really enjoyed their internal tooling for combining both. You simply write a property based test as usual, but when it comes to execution, the testing framework compiles your test in a special way to get coverage and then adjust the random input to hit increased coverage. Of course they run the test across a cluster of machines completely automatically. Traditional property based testing is implemented simply as a library, so they don't necessarily have coverage information to guide their random input generation.
hyperpape 2y ago
The distinction between property based testing and fuzzing is basically just a rough cluster of vibes. It describes a real difference, but the borders are pretty vague and precisely deciding which things are fuzzing and which are PBT isn’t really that critical. - Quick running tests, detailed assertions —> PBT - Longer tests, just looking for a crash —> fuzzing. - In between, who knows? https://hypothesis.works/articles/what-is-property-based-testing/ https://hypothesis.works/articles/what-is-property-based-tes...
- ncruces 2y ago
  Interesting read. I guess I'm mostly interested in on number 2 here: Under this point of view, a property-based testing library is really two parts: 1. A fuzzer. 2. A library of tools for making it easy to construct property-based tests using that fuzzer. What should I (we?) be building on top of Go's fuzzer to make it easier to construct property-based tests? My current strategy is to interpret a byte stream as a sequence of "commands", let those be transitions that drive my "state machine", then test all invariants I can think of at every step.
  - deleted 2y ago
    [deleted]
  - randomdata 2y ago
    > What should I (we?) be building on top of Go's fuzzer to make it easier to construct property-based tests? What's the intent behind building on top of Go's fuzzer as opposed to an approach like testing/quick takes?
    - ncruces 2y ago
      The testing/quick package is frozen and is not accepting new features. Also: https://news.ycombinator.com/item?id=30385195 https://news.ycombinator.com/item?id=30385195 But, it occurs to me I could try and build on the same API, and compare them for effectiveness.
skybrian 2y ago
As far as the API is concerned, the main thing you get is a combinator library for generating whatever random data structures you want to use. Working with Arbitrary types (which represent sets of random objects) makes it easy to write reusable functions for generating your test inputs. A library like that could probably be used along with Go’s fuzzing framework fairly easily? I still think the usual combinators (map, filter, chain, and oneOf, to use fast-check’s names) can be a bit awkward, so I’m writing a new property testing library for JavaScript that hopefully works a bit nicer. (Experimental and not published yet.)
chriswarbo 2y ago
There's a fun property-testing library for Haskell called LazySmallcheck (and a more powerful version called LazySmallcheck2012) which is sort-of coverage-based. Since Haskell values are lazy, it uses exceptions as its test data: if a particular exception gets thrown, the test must have forced that part of the test data, so it replaces that part and tries again. For example, let's say our test data is an assoc-list like `[(Int, Customer)]`, and there's a bug that's triggered by repeated keys. LazySmallcheck will run the test on the most general assoc-list there is, a _|_ value! myTest (exception A) --> throws A Since A was thrown, LSC will try again; making the list slightly more specific; which means trying both constructors `[]` and `:`: myTest [] --> test passes myTest (exception A:exception B) --> throws A The input `[]` is completely specified, and it didn't lead to any counterexample, so LSC is finished with that branch. In the `:` branch, the general pair `exception A` caused an error, so LSC will make it slightly more specific and try again: myTest ((exception A, exception C):exception B) --> throws A Since `exception A` is an Int, LSC can't use laziness to keep things general; it has to try concrete values, so it proceeds like Smallcheck; trying the "smallest" Int values: myTest ((0, exception C):exception B) --> throws B Again, LSC will make the general list `exception B` more specific: myTest ((0, exception C):[]) --> passes myTest ((0, exception C):exception A:exception B) --> throws A Since the input `(0, exception C):[]` passed the test without triggering the exception, we know the second element of that pair must be irrelevant to the result. In other words, LSC has proved the property holds for inputs `(0, X):[]` for all X! LSC hence won't try specialising `exception C`; but it will try "larger" Int values, e.g. `(1, exception C):[]`, `(-1, exception C):[]`, etc. up to a pre-defined "depth". I'll ignore these cases and focus on the branch with the longer list: myTest ((0, exception C):(exception A, exception D):exception B --> throws A Again, LSC will specialise the general Int `exception A` into specific values, starting with the "smallest": myTest ((0, exception C):(0, exception D):exception B) --> FAIL! This input has duplicate keys, which triggered the bug and caused our test to fail. Again, the fact that the exceptions inside this value didn't get thrown means those parts were irrelevant to the result. LSC indicates irrelevant values with `_`, so it will report this counterexample as `(0, _):(0, _):_`. That's more informative for understanding this bug than e.g. Smallcheck or QuickCheck, whose "minimal" counterexamples would be fully-specified values, like `(0, Customer { name = "", orders = [], discount = Nothing, joined = 1970-01-01 }):(0, Customer { name = "", orders = [], discount = Nothing, joined = 1970-01-01 }):[]`. Hence LSC's approach has three interesting features: - It has a coverage-like approach that homes-in on interesting cases, by gradually generating the parts of a value that get forced (which are usually the parts being branched on) - It can indicate which parts of a counterexample are irrelevant for the failure - It can prove some properties universally (i.e. when that input is irrelevant to the pass result)

mrkeen 2y ago

I'm not sure how Go's fuzz tests differ from what you linked in your article, but you article said proper fuzzers need to run for days or weeks, and that PBT should approximately always chosen over fuzz testing. But I'd take one step back, and ask a more meta question about testing: does a successful test mean successful code, and vice-versa? Is there anything in Go's contract that specifies that the same inputs to the same code will yield the same output?

randomdata 2y ago
> does a successful test mean successful code A successful test implies that the documentation is true. That is, after all, why you are writing tests: Documentation – To explain to future developers the intent and usage behind the code you wrote. You could just as well write the documentation in Word instead, but then you'd lose the ability to perform machine verification of the documentation, which is a huge boon to moving codebases where the documentation and code are likely to fall out of sync if one is not incredibly careful (although perhaps LLMs will some day bridge that gap?). The documentation being true does not imply that the documentation is useful, of course. Writing useful documentation is still an art.
- tennis_80 2y ago
  This is a reason I’m very keen on making sure tests are focused on requirements rather than code. A few jobs ago I would often be in a team where the entire team had turned over several times, we would be asked to do large updates to a legacy application or bump lots of dependencies and just not break anything. When pushed the product owner wouldn’t be able to describe what the app was supposed to do, particularly for unusual types of users (the account / user modelling was chaotic so say, several billing accounts per user, each with different products and access levels). At that point “foo calls bar” doesn’t clarify much intent.

bananapub 2y ago

fuzzing is clearly not a replacement for tests?

deleted 2y ago
[deleted]
josephg 2y ago
It kind of is. I often use randomised tests (fuzzing) for data structures and algorithm implementations. Throw a lot of asserts in and see if an hour of random input can find any edge cases I’ve missed. Usually the first time I run something like this it finds problems instantly. It’s very humbling. I find when I do this I don’t need to write by hand anywhere near as many tests to get my software working well. I also usually turn any failures found by the fuzzer into standalone unit tests, to make any regressions easier to find later.
- ncruces 2y ago
  I agree, it can be. My example above matches yours (fuzzing a data structure). I coded some tests that ensure the data structure is useful, many of them test examples from papers describing the data structure, but that don't necessarily cover all the corner cases. Then I fuzzed it. I used Go's fuzzer, which is geared towards parsers and stuff. It can generate a stream of bytes and use that for fuzzing. The data structure is a set/map. So I interpret the stream of bytes as commands to add/remove random elements from the set/map. After I add an element, contains needs to return true; after I remove one, contains need to return false; if I put in a mapping, finding it must return what I just put there, etc. And at every step all the data structure invariants (that ensure logarithmic search, etc) need to hold. That was stupidly effective at finding a few bugs, all within seconds, all with sequences of less than a dozen operations. Then it stops. And you get 100% coverage. I'm assuming that, apart from ergonomics, where I kinda build my own state machine transitions out of a stream of bytes, the tooling actually seems more effective than property testing libraries. Still curious to understand what I'm missing out.

AlexErrant 2y ago

You're asserting properties, so IMO this meets the definition of PBTs ("every node of level greater than one has two children"). However, depending on the lib, you can get some nice quality of life improvements. One "nice to have" is shrinking. See the "Shrinking" section here https://tech.fpcomplete.com/blog/quickcheck-hedgehog-validity/ https://tech.fpcomplete.com/blog/quickcheck-hedgehog-validit... Having combinators to compose generators is also great. Libs may also have a known set of "bad" values that cause exceptional behavior.

gavinhoward 2y ago
AFL++, a fuzzer, has a tool to minimize (shrink) test cases.
zarathustreal 2y ago
“Properties” in the Property-based Testing sense refers to mathematical properties such as equality, associativity, commutivity, etc
ncruces 2y ago
The Go fuzzer, when it finds a failure, will also walk back and try to shrink inputs (and still trigger the same failure). Not sure how effective it is compared to other options, but I'm not totally missing out there. It also builds a corpus of interesting inputs over time (those that cause new branches to be taken, since that's its goal: improve coverage). I'm less sure about combinators.

kccqzy 2y ago

You can totally combine coverage based fuzzing with property based tests. When I was at Google, I really enjoyed their internal tooling for combining both. You simply write a property based test as usual, but when it comes to execution, the testing framework compiles your test in a special way to get coverage and then adjust the random input to hit increased coverage. Of course they run the test across a cluster of machines completely automatically. Traditional property based testing is implemented simply as a library, so they don't necessarily have coverage information to guide their random input generation.

hyperpape 2y ago

The distinction between property based testing and fuzzing is basically just a rough cluster of vibes. It describes a real difference, but the borders are pretty vague and precisely deciding which things are fuzzing and which are PBT isn’t really that critical. - Quick running tests, detailed assertions —> PBT - Longer tests, just looking for a crash —> fuzzing. - In between, who knows? https://hypothesis.works/articles/what-is-property-based-testing/ https://hypothesis.works/articles/what-is-property-based-tes...

ncruces 2y ago
Interesting read. I guess I'm mostly interested in on number 2 here: Under this point of view, a property-based testing library is really two parts: 1. A fuzzer. 2. A library of tools for making it easy to construct property-based tests using that fuzzer. What should I (we?) be building on top of Go's fuzzer to make it easier to construct property-based tests? My current strategy is to interpret a byte stream as a sequence of "commands", let those be transitions that drive my "state machine", then test all invariants I can think of at every step.
- deleted 2y ago
  [deleted]
- randomdata 2y ago
  > What should I (we?) be building on top of Go's fuzzer to make it easier to construct property-based tests? What's the intent behind building on top of Go's fuzzer as opposed to an approach like testing/quick takes?
  - ncruces 2y ago
    The testing/quick package is frozen and is not accepting new features. Also: https://news.ycombinator.com/item?id=30385195 https://news.ycombinator.com/item?id=30385195 But, it occurs to me I could try and build on the same API, and compare them for effectiveness.

skybrian 2y ago

As far as the API is concerned, the main thing you get is a combinator library for generating whatever random data structures you want to use. Working with Arbitrary types (which represent sets of random objects) makes it easy to write reusable functions for generating your test inputs. A library like that could probably be used along with Go’s fuzzing framework fairly easily? I still think the usual combinators (map, filter, chain, and oneOf, to use fast-check’s names) can be a bit awkward, so I’m writing a new property testing library for JavaScript that hopefully works a bit nicer. (Experimental and not published yet.)

chriswarbo 2y ago

There's a fun property-testing library for Haskell called LazySmallcheck (and a more powerful version called LazySmallcheck2012) which is sort-of coverage-based. Since Haskell values are lazy, it uses exceptions as its test data: if a particular exception gets thrown, the test must have forced that part of the test data, so it replaces that part and tries again. For example, let's say our test data is an assoc-list like `[(Int, Customer)]`, and there's a bug that's triggered by repeated keys. LazySmallcheck will run the test on the most general assoc-list there is, a _|_ value! myTest (exception A) --> throws A Since A was thrown, LSC will try again; making the list slightly more specific; which means trying both constructors `[]` and `:`: myTest [] --> test passes myTest (exception A:exception B) --> throws A The input `[]` is completely specified, and it didn't lead to any counterexample, so LSC is finished with that branch. In the `:` branch, the general pair `exception A` caused an error, so LSC will make it slightly more specific and try again: myTest ((exception A, exception C):exception B) --> throws A Since `exception A` is an Int, LSC can't use laziness to keep things general; it has to try concrete values, so it proceeds like Smallcheck; trying the "smallest" Int values: myTest ((0, exception C):exception B) --> throws B Again, LSC will make the general list `exception B` more specific: myTest ((0, exception C):[]) --> passes myTest ((0, exception C):exception A:exception B) --> throws A Since the input `(0, exception C):[]` passed the test without triggering the exception, we know the second element of that pair must be irrelevant to the result. In other words, LSC has proved the property holds for inputs `(0, X):[]` for all X! LSC hence won't try specialising `exception C`; but it will try "larger" Int values, e.g. `(1, exception C):[]`, `(-1, exception C):[]`, etc. up to a pre-defined "depth". I'll ignore these cases and focus on the branch with the longer list: myTest ((0, exception C):(exception A, exception D):exception B --> throws A Again, LSC will specialise the general Int `exception A` into specific values, starting with the "smallest": myTest ((0, exception C):(0, exception D):exception B) --> FAIL! This input has duplicate keys, which triggered the bug and caused our test to fail. Again, the fact that the exceptions inside this value didn't get thrown means those parts were irrelevant to the result. LSC indicates irrelevant values with `_`, so it will report this counterexample as `(0, _):(0, _):_`. That's more informative for understanding this bug than e.g. Smallcheck or QuickCheck, whose "minimal" counterexamples would be fully-specified values, like `(0, Customer { name = "", orders = [], discount = Nothing, joined = 1970-01-01 }):(0, Customer { name = "", orders = [], discount = Nothing, joined = 1970-01-01 }):[]`. Hence LSC's approach has three interesting features: - It has a coverage-like approach that homes-in on interesting cases, by gradually generating the parts of a value that get forced (which are usually the parts being branched on) - It can indicate which parts of a counterexample are irrelevant for the failure - It can prove some properties universally (i.e. when that input is irrelevant to the pass result)