6 ms·

It's really disquieting how much similarity there is between fuzzing and QuickCheck... and yet so few people have even noticed and know about either. (Yes, fuzz

It's really disquieting how much similarity there is between fuzzing and QuickCheck... and yet so few people have even noticed and know about either. (Yes, fuzzing and QC work at slightly different "levels", I suppose, but... it's all just virtual execution by the CPU, so...)

kibwen 10y ago
Worth noting that there's also an implementation of QuickCheck available for Rust (by none other than burntsushi, the author of the regex library in the OP): https://github.com/BurntSushi/quickcheck https://github.com/BurntSushi/quickcheck
- lomnakkus 10y ago
  Oh, nice!
  - burntsushi 10y ago
    Incidentally, QuickCheck is also used on the regex parser.
- im_down_w_otp 10y ago
  We've recently started testing C code via Rust QuickCheck. In addition to the relatively clean Rust -> C interface it's very nice to have higher degree of compile-time assurance of the correctness of the property model itself. As the models become non-trivial it becomes increasingly difficult to build them reliably in C itself.
  - adrianN 10y ago
    Do you have more information about that? Maybe a blog post?
    - im_down_w_otp 10y ago
      Not at the moment, but almost certainly at some point in the relatively near future.
k__ 10y ago
Just saw something like quickcheck for JavaScripts Flow. I think I will use this in the future.
munin 10y ago
I think that this is because QC can work with much richer types than fuzzers have access to. Think about the Haskell data types you know, and imagine automatically generating them. Sounds pretty easy with some algorithm, right? Now think about the Java data types you know, and the invariants on constructing them. Yeah sure they have constructors but what preconditions do those constructors require? anything impure, like I/O? are there setters? is an object really "constructed" until some setters have been called? if so, how do you know that as the test generator? It seems a lot nastier to me, which I think is why QC style automatic testing has made less inroads in impure languages. It also makes fewer inroads to fuzzing because fuzzing starts a few steps back where you know even less about the application. You could do a grammar-based fuzz of the application, but then you have to worry about the map/terrain of the grammar/application. Are you missing testing some case in the application because your grammar is incomplete? In QC, the map is the terrain because the "grammar" is just a type that your application uses and this isn't really the case in fuzzing. It could be, in fuzzing some languages (like Java) where you could interrogate the program you'r testing (even a binary program) for types that the program uses. Think about C programs though, where the application input and the "types" that the application uses are (or can be) pretty distant. Anyway, I don't think it's disquieting. I think they're two very different software assurance techniques that apply in two very different domains and that explains why people don't say too much about them in the same breath. They're united by randomness, but I don't think that much more.
- cmrx64 10y ago
  Speaking of, do you know of any tools for doing grammar-based fuzzing?
  - munin 10y ago
    peachfuzz, quickfuzz, dharma, grammfuzz. They get done a bunch and usually people wind up re-inventing lisp to make a data specification DSL, then write some generators around it and call it a day. The generation strategy usually winds up being domain specific too (are you looking for OOB bugs? dangling refs / UAF? different patterns in different structured data lead to these errors without feedback) so honestly you should pick some parser combinator in a language that you know (like construct for python, or hammer for C) and then turn it into a fuzzer for your application yourself, using the faults you want to find as inspiration for the generators you write.
Manishearth 10y ago
We (the folks who maintain the Rust fuzzers) are considering adding support for quickcheck-based fuzzers so that you can have higher-level fuzzing APIs. The rust community is pretty aware of quickcheck (there's a rust version) I would say.
cakoose 10y ago
There's another distinction besides the "level" at which they operate. They use different techniques to generate test inputs. QuickCheck-style tools typically generate inputs based on high-level static information, like types or programmer-provided specs. To reach the sophistication of modern fuzzers, you need to be smarter. For one, you should inspect the code of the function. If you know how the code branches, you can more efficiently generate inputs that exercise both sizes of the branch. But since you can't always figure out how to exercise both sizes of a branch just based on static analysis, fuzzers also observe the dynamic execution behavior of the program. This allows them to randomly adjust inputs until they know both sides of a branch have been hit. I imagine that lifting fuzzing techniques to a higher level could have efficiency benefits. Maybe someone builds a fuzzer that runs on Rust MIR? Or maybe Rust can dumps out additional metadata (alongside the LLVM bitcode) to help the fuzzer figure things out?
- eru 10y ago
  QuickCheck happens to use types (ie static information). But Python's hypothesis shows that QuickCheck works just as well with dynamic languages: https://hypothesis.readthedocs.io/en/latest/ https://hypothesis.readthedocs.io/en/latest/
  - cakoose 10y ago
    Yeah, in this case, Hypothesis uses programmer-provided input specs, which are similar but not quite the same as type declarations in a typed programming language. I'd still consider this to be essentially "static" information, since they don't change as the program executes.
    - eru 10y ago
      Perhaps. Though 'shrinking' definitely makes use of dynamic information.
galapago 10y ago
We developed a fuzzer [0] using property-based testing in Haskell using QuickCheck (as expected!) [0] http://QuickFuzz.org/ http://QuickFuzz.org/
hyperpape 10y ago
The author of Hypothesis (Python library for property based testing) has a nice article about defining property based testing and whether and how it differs from fuzzing. http://hypothesis.works/articles/what-is-property-based-testing/ http://hypothesis.works/articles/what-is-property-based-test...
dllthomas 10y ago
I think they're both examples of property based generative testing, where the property of interest in the fuzzing case is "doesn't crash".
- lomnakkus 10y ago
  You're right, I think.

kibwen 10y ago

Worth noting that there's also an implementation of QuickCheck available for Rust (by none other than burntsushi, the author of the regex library in the OP): https://github.com/BurntSushi/quickcheck https://github.com/BurntSushi/quickcheck

lomnakkus 10y ago
Oh, nice!
- burntsushi 10y ago
  Incidentally, QuickCheck is also used on the regex parser.
im_down_w_otp 10y ago
We've recently started testing C code via Rust QuickCheck. In addition to the relatively clean Rust -> C interface it's very nice to have higher degree of compile-time assurance of the correctness of the property model itself. As the models become non-trivial it becomes increasingly difficult to build them reliably in C itself.
- adrianN 10y ago
  Do you have more information about that? Maybe a blog post?
  - im_down_w_otp 10y ago
    Not at the moment, but almost certainly at some point in the relatively near future.

k__ 10y ago

Just saw something like quickcheck for JavaScripts Flow. I think I will use this in the future.

munin 10y ago

I think that this is because QC can work with much richer types than fuzzers have access to. Think about the Haskell data types you know, and imagine automatically generating them. Sounds pretty easy with some algorithm, right? Now think about the Java data types you know, and the invariants on constructing them. Yeah sure they have constructors but what preconditions do those constructors require? anything impure, like I/O? are there setters? is an object really "constructed" until some setters have been called? if so, how do you know that as the test generator? It seems a lot nastier to me, which I think is why QC style automatic testing has made less inroads in impure languages. It also makes fewer inroads to fuzzing because fuzzing starts a few steps back where you know even less about the application. You could do a grammar-based fuzz of the application, but then you have to worry about the map/terrain of the grammar/application. Are you missing testing some case in the application because your grammar is incomplete? In QC, the map is the terrain because the "grammar" is just a type that your application uses and this isn't really the case in fuzzing. It could be, in fuzzing some languages (like Java) where you could interrogate the program you'r testing (even a binary program) for types that the program uses. Think about C programs though, where the application input and the "types" that the application uses are (or can be) pretty distant. Anyway, I don't think it's disquieting. I think they're two very different software assurance techniques that apply in two very different domains and that explains why people don't say too much about them in the same breath. They're united by randomness, but I don't think that much more.

cmrx64 10y ago
Speaking of, do you know of any tools for doing grammar-based fuzzing?
- munin 10y ago
  peachfuzz, quickfuzz, dharma, grammfuzz. They get done a bunch and usually people wind up re-inventing lisp to make a data specification DSL, then write some generators around it and call it a day. The generation strategy usually winds up being domain specific too (are you looking for OOB bugs? dangling refs / UAF? different patterns in different structured data lead to these errors without feedback) so honestly you should pick some parser combinator in a language that you know (like construct for python, or hammer for C) and then turn it into a fuzzer for your application yourself, using the faults you want to find as inspiration for the generators you write.

Manishearth 10y ago

We (the folks who maintain the Rust fuzzers) are considering adding support for quickcheck-based fuzzers so that you can have higher-level fuzzing APIs. The rust community is pretty aware of quickcheck (there's a rust version) I would say.

cakoose 10y ago

There's another distinction besides the "level" at which they operate. They use different techniques to generate test inputs. QuickCheck-style tools typically generate inputs based on high-level static information, like types or programmer-provided specs. To reach the sophistication of modern fuzzers, you need to be smarter. For one, you should inspect the code of the function. If you know how the code branches, you can more efficiently generate inputs that exercise both sizes of the branch. But since you can't always figure out how to exercise both sizes of a branch just based on static analysis, fuzzers also observe the dynamic execution behavior of the program. This allows them to randomly adjust inputs until they know both sides of a branch have been hit. I imagine that lifting fuzzing techniques to a higher level could have efficiency benefits. Maybe someone builds a fuzzer that runs on Rust MIR? Or maybe Rust can dumps out additional metadata (alongside the LLVM bitcode) to help the fuzzer figure things out?

eru 10y ago
QuickCheck happens to use types (ie static information). But Python's hypothesis shows that QuickCheck works just as well with dynamic languages: https://hypothesis.readthedocs.io/en/latest/ https://hypothesis.readthedocs.io/en/latest/
- cakoose 10y ago
  Yeah, in this case, Hypothesis uses programmer-provided input specs, which are similar but not quite the same as type declarations in a typed programming language. I'd still consider this to be essentially "static" information, since they don't change as the program executes.
  - eru 10y ago
    Perhaps. Though 'shrinking' definitely makes use of dynamic information.

galapago 10y ago

We developed a fuzzer [0] using property-based testing in Haskell using QuickCheck (as expected!) [0] http://QuickFuzz.org/ http://QuickFuzz.org/

hyperpape 10y ago

The author of Hypothesis (Python library for property based testing) has a nice article about defining property based testing and whether and how it differs from fuzzing. http://hypothesis.works/articles/what-is-property-based-testing/ http://hypothesis.works/articles/what-is-property-based-test...

dllthomas 10y ago

I think they're both examples of property based generative testing, where the property of interest in the fuzzing case is "doesn't crash".

lomnakkus 10y ago
You're right, I think.