4 ms·

Is this similar to fuzz testing? (like american fuzzy lop?)

by rawnlq 9y ago

zie 9y ago
sort of, but not really. It's more like quickcheck. Go read the docs. It's totally awesome.
laughinghan 9y ago
Fuzzing can refer to randomly generated test inputs without bothering to minimize them when bugs are found. Property-based testing tools like Hypothesis and QuickCheck (which pioneered this approach), in addition to randomly generating test cases, when they find a test case that violates an assertion, they then start reducing the test case to try to find the minimal test case that violates the assertion. 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/ http://hypothesis.works/articles/compositional-shrinking/
- mononcqc 9y ago
  It depends. One of the places where property-based testing buys you the most benefit is when testing systems that are conceptually simple, but use a complex implementation. 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/strangeloop/lambdajam2013/master/slides/Norton-QuickCheck.html http://htmlpreview.github.io/?https://raw.github.com/strange... for example.
rhinoceraptor 9y ago
It's used just to assert properties of a function, for example if you have a function `rot13`, you could say "for all string `input`, input == rot13(rot13(input))". 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.
masklinn 9y ago
From very far away, kinda, fuzzing generally aims to find faults in systems by feeding them generated data (possibly guided by branch probes) and waiting for them to blow up. 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.
- feanaro 9y ago
  > 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. 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.
feanaro 9y ago
Somewhat contrary to what the other comments so far have said, I would say that this is definitely related to fuzzing. In fact, it is fuzzing, plain and simple, but unguided and of a more limited scope than what afl gets you. 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/ 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.
DRMacIver 9y ago
A (somewhat non-standard but I think compatible with general usage) definition I tend to use is that fuzzing is the data generation part and property-based testing is layering interesting non-trivial tests on top of fuzzing. 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.

Is this similar to fuzz testing? (like american fuzzy lop?)

by rawnlq 9y ago

Is this similar to fuzz testing? (like american fuzzy lop?)

zie 9y ago

sort of, but not really. It's more like quickcheck. Go read the docs. It's totally awesome.

laughinghan 9y ago

Fuzzing can refer to randomly generated test inputs without bothering to minimize them when bugs are found. Property-based testing tools like Hypothesis and QuickCheck (which pioneered this approach), in addition to randomly generating test cases, when they find a test case that violates an assertion, they then start reducing the test case to try to find the minimal test case that violates the assertion. 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/ http://hypothesis.works/articles/compositional-shrinking/

mononcqc 9y ago
It depends. One of the places where property-based testing buys you the most benefit is when testing systems that are conceptually simple, but use a complex implementation. 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/strangeloop/lambdajam2013/master/slides/Norton-QuickCheck.html http://htmlpreview.github.io/?https://raw.github.com/strange... for example.

rhinoceraptor 9y ago

It's used just to assert properties of a function, for example if you have a function `rot13`, you could say "for all string `input`, input == rot13(rot13(input))". 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.

masklinn 9y ago

From very far away, kinda, fuzzing generally aims to find faults in systems by feeding them generated data (possibly guided by branch probes) and waiting for them to blow up. 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.

feanaro 9y ago
> 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. 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.

feanaro 9y ago

Somewhat contrary to what the other comments so far have said, I would say that this is definitely related to fuzzing. In fact, it is fuzzing, plain and simple, but unguided and of a more limited scope than what afl gets you. 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/ 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.

DRMacIver 9y ago

A (somewhat non-standard but I think compatible with general usage) definition I tend to use is that fuzzing is the data generation part and property-based testing is layering interesting non-trivial tests on top of fuzzing. 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.