Supporting Hypothesis
stripe.com
stripe.com
When I first encountered property-based testing, I had some trouble coming up with interesting properties to test, since I was so used to thinking in terms of individual test cases. This blogpost surveys some great starting points for identifying useful properties to test: https://fsharpforfunandprofit.com/posts/property-based-testi...
Plus, it's the only thing that doesn't suffer from the "you can't find the bug you just introduced" disease, where you're (by definition) blind to the problems you don't know are there. We usually tend to test the things we wrote the code to guard against, but Hypothesis finds the actual bugs.
Great work.
Also, by "supporting Hypothesis", you mean "giving money to DR MacIver", right? This is not completely clear from the post.
It's specifically in the form of contracting me to develop some features rather than a donation of money - support for testing with Pandas, and improving the existing numpy support to a lesser extent (mostly with a goal of providing a more solid foundation for the Pandas work).
I botched the copy pasta of the embedded code snippet container. All fixed up!
Hypothesis is a quickcheck port to python, and it is immensely useful in finding edge case bugs that naive testing usually misses.
It's lovely to see it get more support and backing.
If you'll pardon the pedantry (I think the distinction matters, honest), Hypothesis isn't really a QuickCheck port. It started out life that way, and it can be used in a way that that is pretty compatible with QuickCheck, but implementation-wise it's very different and it has a bunch of interesting non-QuickCheck features.
I totally agree that this is great news though, and I'm very grateful to Stripe. :-)
thanks for your hard work, you saved me a lot of my own.
I'm only familar with QuickCheck, but what are those differences / features? Couldn't tell from a quick look at the website of Hypothesis.
This gives Hypothesis a lot more freedom to generically manipulate the data than QuickCheck has, because it has total control of a concrete representation of it.
As a result:
* Specifying a data generator is a much more declarative process - Hypothesis largely handles size/distribution issues itself.
* The fuzzing nature of Hypothesis means that it can do much smarter generation than a normal QuickCheck (though this is more potential than actual right now. The current fuzzer is "pretty good". I'll be starting a PhD soon where I hope to work on making it amazing)
* Shrinking is just a built in part of the process and users never have to define their own shrinker.
* All examples (both pre and post shrinking) can be serialized because the IR is just bytes, so Hypothesis can replay failing tests automatically without rerunning the shrinking process. This matters both because shrinking tends to be slower than generation in most QuickChecks, but also because in general shrinking is subject to "slippage" where the bugs you find after shrinking are different from the bugs you started with.
* Because you can just keep drawing data from the stream, Hypothesis tests can be much more interactive than normal QuickCheck (which does support mixing test execution and generation, but it doesn't work especially well).
* Because Hypothesis never needs to touch the values it generates, Hypothesis is much better for mutable data than the approach most QuickCheck takes.
* I haven't actually done this yet, but Conjecture is deliberately designed to be quite C like, so "at some point" it will become possible to rewrite the core in C (more likely Rust) and then new Hypotheses will spring up everywhere because 90% of the work can be done by writing bindings to a C library. QuickCheck's approach on the other hand is inherently very tied to the semantics of the host language.
The property-based testing libraries for some dynamic languages (test.check for Clojure, the various Erlang ones including QuickCheck) have some of these features, but I think they're more naturally supported in the Hypothesis model, and the Hypothesis model has a lot more room to grow.
> The fuzzing nature of Hypothesis means that it can do much smarter generation than a normal QuickCheck (though this is more potential than actual right now. The current fuzzer is "pretty good". I'll be starting a PhD soon where I hope to work on making it amazing)
Smarter in what way?
> Because you can just keep drawing data from the stream, Hypothesis tests can be much more interactive than normal QuickCheck (which does support mixing test execution and generation, but it doesn't work especially well).
What makes QuickCheck's support for this makes it work less than ideal?
> Because Hypothesis never needs to touch the values it generates, Hypothesis is much better for mutable data than the approach most QuickCheck takes.
What do you mean by not having to "touch" the values it generates?
Better at generating values that exhibit interesting behaviour in tests. QuickCheck style testing mostly only works well because it turns out that there are a lot of bugs that are relatively "dense" in the search space of tests, and doesn't do very well at finding hard to reach bugs. This means that some bugs are found with very low probability, which is bad both because you want to find them reliably and because it means that even running your tests for longer is often not enough to find interesting behaviour.
(ETA: This mostly applies to Haskell QuickCheck and derivatives. I believe the Quviq Erlang QuickCheck has had a great deal of hand tuning of its generators to get better behaviour, so its data generation is probably strictly better than Hypothesis's in many cases right now. I'm trying to get a generic mechanism for improving things without requiring this hand tuning, so hopefully at some point I'll be able to reverse that situation)
Security-oriented fuzzers do a lot of clever things to actually determine the shape of the search space and adapt to it so that they can take advantage of the structure of the program under test so that running for longer gives them more power than just repeatedly trying the same thing over and over again. I'm hoping to incorporate some of those ideas into Hypothesis but don't currently.
> What makes QuickCheck's support for this makes it work less than ideal?
Mostly that it plays very badly with shrinking (this is better but still not good in test.check and friends) and the API for it is on the clunky side.
> What do you mean by not having to "touch" the values it generates?
In classic quickcheck, the shrink API is based on taking a value and replacing it with a simpler version of itself. This means that if the value has been mutated (which is mostly not a problem in Haskell, but can be if you're using ioProperty, and is definitely a problem in QuickCheck ports to impure languages) then you run into problems. e.g. a test that appends an element to a variable sized array argument can get the shrinker into an infinite loop.
It also means that QuickCheck is limited by the type constraints on the generated values. You can't e.g. do duplicate detection because you aren't constrained to generate values on which that is meaningful.
In Hypothesis in comparison everything is based off its IR, so it can do manipulations and comparisons on that, and it doesn't matter what type the generated value is.
(Hypothesis also can't do perfect duplicate detection because it has the problem that many IR values may map to the same value, but its duplicate detection still seems to be mostly good enough in practice)
afl is guided in the sense that it uses binary instrumentation and an evolutionary algorithm to guide testing towards increased program coverage. It also exercises the whole program instead of just a preselected set of functions. There's also libFuzzer, which like afl uses coverage to guide the fuzzing process, but fuzzes only preselected entry point functions. Finally, there are unguided fuzzers like radamsa which simply mutate a bunch of known inputs to produce new ones using techniques that have been empirically shown to lead to bugs often. This is probably the most similar to what Hypothesis does.
An important mention, with regards to the QuickCheck connection, is QuickFuzz, which uses QuickCheck as a test case generator for a variety of formats in QuickFuzz which then get mutated by general-purpose fuzzers like radamsa: http://quickfuzz.org/
Overall, I'd say the goals of fuzzers like afl/libFuzzer/radamsa are very similar to the goals of libraries like Hypothesis/Quickcheck, with the former group being a bit more security-oriented while the latter group's emphasis is a bit more on general program correctness. It should be obvious those two areas are very much overlapping, though.
Also, while they're very similar in a mechanical sense since they're both about randomly generated test inputs, in a broader sense my impression is that fuzzers have a very different focus from property-based testing. I think fuzz testing typically refers to testing very complex software, like compilers, interpreters, and virtual machines, and searching for crazy edge cases, especially ones that may expose security vulnerabilities. So a lot of effort goes into generating test inputs that are unlikely to happen with a naive testing strategy (automated or manual), yet still interesting and relatively likely to trigger a bug (rather than spending too much time in the very large space of uninteresting test inputs that a naive testing strategy wouldn't come up with but also is unlikely to trigger a bug).
By contrast, I think property-based testing is typically used for testing programs that are of ordinary complexity, and quickly finding bugs due to simple but common programmer errors, which can then be quickly fixed. So a lot of effort goes into reducing any bugs that are found to the very minimal test case, which if the test input type is a nontrivial data structure can be surprisingly involved. MacIver has actually written a series of blogposts on Hypothesis' approach: http://hypothesis.works/articles/compositional-shrinking/
In doing so, you tend to have clearly defined properties that are fairly simple to validate, but a code implementation that may have very intricate internal interactions that cause all sorts of bugs.
See http://htmlpreview.github.io/?https://raw.github.com/strange... for example.
You then get different tools optimised for different spaces. Things labelled fuzzers tend to be optimised for one or two data types (usually text or bytes) and for long-running processes where you can leave the fuzzer running for days or weeks (Google spent a CPU-millenium fuzzing ffmpeg!). Property-based testing libraries on the other hand tend to be optimised for making it easy to write fuzzers for arbitrary data types and assume that tests are short running (seconds or less).
Fundamentally the tools for this are all "the same sort of thing" but there's a very large design space and most things called property-based testing libraries currently sit at more or less the opposite corner from most things called fuzzers.
Hypothesis is maybe a little closer to a classic fuzzer than a classic property-based testing library in design, but that's mostly an implementation detail at present and from the outside/API level it definitely looks more like the latter than the former.
And the test library will generate that input string randomly (or with a seed if you have a failing case you want to put in a regression suite), and if it finds a failing case it will search for the minimal input string which also fails.
Property-based testing also does pseudo-random data generation (usually guided by constraint sets either explicit or type-based) but rather than wait for stuff to blow up it checks that specific properties hold (hence the name).
In TFA's example, a fuzzer would generate random lists, feed them to reverse and see if the reverse function faults, a property-based tester checks that reversing twice yields the same list.
Property-based testers also often (though not necessarily) try to reduce their example (of the property not holding) to a simpler version thereof, AFAIK few if any fuzzer does that.
In a way, property-based testing is a step beyond fuzzing, though it is also a more structured one, and it works on much smaller scales e.g. you'll property-check a function, but you'll fuzz an entire complex software system.
Actually, it's pretty common. Both afl and libFuzzer do this. I'm not sure about the details in libFuzzer, but afl runs a test case minimization round automatically during fuzzing. The afl package also contains a specialized tool afl-tmin that does this more extensively.
It should also be mentioned that even more coarsely-grained fuzzers like afl and libFuzzer can be made to detect subtler property contradictions (i.e. less dramatic than crashes) through the use of things like AddressSanitizer/MemorySanitizer and asserts. Libraries like Hypothesis and QuickCheck are in a better position to try to construct a contradiction since they possess more language-level knowledge.