Hacker News Reader

Comment by thom | Hacker News Reader

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.

View on HN

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.

Can you give some more details about that? What kind of invariants do you test, and how?

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.l...

This was one of my favorite bugs found: 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.

Out of curiosity, how do you go about generating "random valid well defined programs"? I thought about doing something like this for testing my own toy language, but wasn't sure how to go about generating random test cases.

Basically by a top down approach. For example, to generate a random integer valued form, pick one of N fixed rules and invoke it. A rule for a form of size S might be "generate some value k in [1,S-1] and then partitions S-1 into k integers, generate an integer valued form for each, then produce the form that is their sum."

At the leaf nodes, generate constants or variables. Keep track of the variables that are in scope as you do this (and their types.)

This is a pretty standard approach used in compiler testing. In languages like C you have problems ensuring the program doesn't cause undefined behavior, but Common Lisp is much nicer in that respect -- for example, evaluation order of arguments to functions is defined, and you don't have to worry about integer operations overflowing.

All this has made me appreciate language specifications that really nail down what programs are supposed to do.

The forms generated are constrained if one wants them to be easily reducible while preserving validity. Hypothesis has a nice solution to that problem, which I didn't use, as this was done a decade and a half earlier.

Interesting, I'll have to take a stab at trying something like that. Thanks for the reply!

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.

How does this work in more complicated situations. For example, how do you use PBT to show that some operation is thread-safe?

> 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!)

One very nice example of this is Jepsen:

https://github.com/jepsen-io/jepsen

> 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.

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.

Reply on news.ycombinator.com