4 ms·

My experience of property based testing is that you end up either testing trivial stuff that you don't really care about (sure, maybe you have a bug with extrem

by thom 5y ago

My experience of property based testing is that you end up either testing trivial stuff that you don't really care about (sure, maybe you have a bug with extremely large integers that can't actually happen in real life), or you're creating tests every bit as complex and buggy as the implementation itself to represent realistic states. Quite often you're just directly duplicating the logic you're testing to prove it works in all cases. These just seem like the worst kinds of test, highly coupled with implementation details. For the benefit of finding some bugs with edge cases (which may or may not be spurious), I just don't believe it's worth the effort, given that you still need all your normal tests anyway. Maybe I am just unlucky not to work in a more pure, mathsy domain, I dunno.

talaketu 5y ago
I can see how you might avoid "highly coupled with implementation details" example-based tests. With a little abstraction, you can do the same with property-based tests. Properties as external assertions that you code up as a test. An easy example is to think about the contract of a stack, and the properties that result, and how you could test those properties with arbitrary example: pushing arbitrary t of T on a stack of T results in a stack 1 deeper popping a non-empty stack results in a stack 1 shallower, etc.
- _dain_ 5y ago
  How does this work in more complicated situations. For example, how do you use PBT to show that some operation is thread-safe?
  - chriswarbo 5y ago
    > how do you use PBT to show that some operation is thread-safe? One approach is to make values to represent the "actions" we care about (e.g. "increment", "sendMessage", "delete", etc.), and write tests which take random lists of actions as arguments and execute those actions. We can calculate the expected result by either using a non-threaded 'oracle', or by generating actions with a known result (e.g. if we always generate equal numbers of "increment" and "decrement" actions, then the result should match the original value). As an example, I wrote a dynamic binding mechanism based on thread-local storage, which required special handling of thread pools to ensure futures wouldn't see stale values. To test this, I made a tiny domain-specific language (AKA a handful of classes) defining futures/awaiting, dynamic binding/lookup, and string literals/appending. I made two interpreters (AKA recursive functions) for this DSL: one using real futures/threads/dynamic-binding, the other just a straightforward calculation with a couple of stacks. To test the correctness of my dynamic binding mechanism in the face of futures/threading, I simply test that randomly-generated programs in that DSL will give the same result from both interpreters. (I also wrote a few properties to test each interpreter too!)
    - thom 5y ago
      One very nice example of this is Jepsen: https://github.com/jepsen-io/jepsen https://github.com/jepsen-io/jepsen
pfdietz 5y ago
My experience with PBT is in testing compilers. In this problem domain, it finds bugs that would be near impossible to find with traditional testing approaches. And the test generator can be made independent of the implementation, if one is testing standard language features.
- _dain_ 5y ago
  Can you give some more details about that? What kind of invariants do you test, and how?
  - pfdietz 5y ago
    I have applied it to testing Common Lisp implementations, but there has been much work on applying it to other languages (most famously C and Javascript.) I applied the following techniques: (1) Generate random valid well defined programs and see (a) if they crash the compiler, (b) cause different CL implementations to produce different outputs, (c) when modified (by addition of randomly generated optimization directives or valid type declarations) they still produce the same output. This is differential testing, which was used by McKeeman at DEC in the 1990s to test C compilers, and later improved (again, on C compilers) by Yang, Chan, Eide, and Regehr at U. of Utah (csmith, creduce). Since a running lisp image can generate and compile functions internally (this IS lisp, after all), the testing loop can be very fast. Since 2003 I have run this on and off for many billions of iterations on desktop and laptop machines on various CL implementations, now mainly on SBCL. Most of the test input reduction is handled automatically, which is a big help. (2) Generate random possibly invalid code by mutating or recombining snippets drawn from a large corpus of code, to see if it crashes the compiler (in CL implementations where the compiler is promised to never respond to bad code by signaling an error.) This was also the approach jsfunfuzz took on Javascript. (3) Extensive fuzzing of calls to standard functions in CL, using random generation of input values and random generation of valid type declarations, with the invariant being that the same values should be computed (and the compiler not fail.) This is a specialization of (1), but was sufficiently different that the bugs it found were not the same. Examples of tests produced by (1) and (3) over an early period when this was being developed. Each caused a failure in some CL implementation: https://github.com/pfdietz/ansi-test/blob/master/misc/misc.lsp https://github.com/pfdietz/ansi-test/blob/master/misc/misc.l... This was one of my favorite bugs found: https://bugs.launchpad.net/sbcl/+bug/1730699 https://bugs.launchpad.net/sbcl/+bug/1730699 The experience with this sort of testing of compilers (in any language) is that if the compiler (free or commercial) has never been subjected to it, it will immediately find bugs in the compiler.
osi 5y ago
i use property based testing for the external api of my business domain service. yes, the test code is an “oracle”, knowing what the service _should_ be doing. it’s a parallel implementation of the logic, highly geared towards the use-case of testing.
chriswarbo 5y ago
> you still need all your normal tests anyway What's a "normal test"? I tend to only write property-based tests (i.e. tests with parameters, which get run many times with random inputs). Tests without parameters tend to either be trivial, or involve a bunch of setup that would be better turning into parameters.

by thom 5y ago

talaketu 5y ago

I can see how you might avoid "highly coupled with implementation details" example-based tests. With a little abstraction, you can do the same with property-based tests. Properties as external assertions that you code up as a test. An easy example is to think about the contract of a stack, and the properties that result, and how you could test those properties with arbitrary example: pushing arbitrary t of T on a stack of T results in a stack 1 deeper popping a non-empty stack results in a stack 1 shallower, etc.

_dain_ 5y ago
How does this work in more complicated situations. For example, how do you use PBT to show that some operation is thread-safe?
- chriswarbo 5y ago
  > how do you use PBT to show that some operation is thread-safe? One approach is to make values to represent the "actions" we care about (e.g. "increment", "sendMessage", "delete", etc.), and write tests which take random lists of actions as arguments and execute those actions. We can calculate the expected result by either using a non-threaded 'oracle', or by generating actions with a known result (e.g. if we always generate equal numbers of "increment" and "decrement" actions, then the result should match the original value). As an example, I wrote a dynamic binding mechanism based on thread-local storage, which required special handling of thread pools to ensure futures wouldn't see stale values. To test this, I made a tiny domain-specific language (AKA a handful of classes) defining futures/awaiting, dynamic binding/lookup, and string literals/appending. I made two interpreters (AKA recursive functions) for this DSL: one using real futures/threads/dynamic-binding, the other just a straightforward calculation with a couple of stacks. To test the correctness of my dynamic binding mechanism in the face of futures/threading, I simply test that randomly-generated programs in that DSL will give the same result from both interpreters. (I also wrote a few properties to test each interpreter too!)
  - thom 5y ago
    One very nice example of this is Jepsen: https://github.com/jepsen-io/jepsen https://github.com/jepsen-io/jepsen

pfdietz 5y ago

My experience with PBT is in testing compilers. In this problem domain, it finds bugs that would be near impossible to find with traditional testing approaches. And the test generator can be made independent of the implementation, if one is testing standard language features.

_dain_ 5y ago
Can you give some more details about that? What kind of invariants do you test, and how?
- pfdietz 5y ago
  I have applied it to testing Common Lisp implementations, but there has been much work on applying it to other languages (most famously C and Javascript.) I applied the following techniques: (1) Generate random valid well defined programs and see (a) if they crash the compiler, (b) cause different CL implementations to produce different outputs, (c) when modified (by addition of randomly generated optimization directives or valid type declarations) they still produce the same output. This is differential testing, which was used by McKeeman at DEC in the 1990s to test C compilers, and later improved (again, on C compilers) by Yang, Chan, Eide, and Regehr at U. of Utah (csmith, creduce). Since a running lisp image can generate and compile functions internally (this IS lisp, after all), the testing loop can be very fast. Since 2003 I have run this on and off for many billions of iterations on desktop and laptop machines on various CL implementations, now mainly on SBCL. Most of the test input reduction is handled automatically, which is a big help. (2) Generate random possibly invalid code by mutating or recombining snippets drawn from a large corpus of code, to see if it crashes the compiler (in CL implementations where the compiler is promised to never respond to bad code by signaling an error.) This was also the approach jsfunfuzz took on Javascript. (3) Extensive fuzzing of calls to standard functions in CL, using random generation of input values and random generation of valid type declarations, with the invariant being that the same values should be computed (and the compiler not fail.) This is a specialization of (1), but was sufficiently different that the bugs it found were not the same. Examples of tests produced by (1) and (3) over an early period when this was being developed. Each caused a failure in some CL implementation: https://github.com/pfdietz/ansi-test/blob/master/misc/misc.lsp https://github.com/pfdietz/ansi-test/blob/master/misc/misc.l... This was one of my favorite bugs found: https://bugs.launchpad.net/sbcl/+bug/1730699 https://bugs.launchpad.net/sbcl/+bug/1730699 The experience with this sort of testing of compilers (in any language) is that if the compiler (free or commercial) has never been subjected to it, it will immediately find bugs in the compiler.

osi 5y ago

i use property based testing for the external api of my business domain service. yes, the test code is an “oracle”, knowing what the service _should_ be doing. it’s a parallel implementation of the logic, highly geared towards the use-case of testing.

chriswarbo 5y ago

> you still need all your normal tests anyway What's a "normal test"? I tend to only write property-based tests (i.e. tests with parameters, which get run many times with random inputs). Tests without parameters tend to either be trivial, or involve a bunch of setup that would be better turning into parameters.