Sun Mar 30 08:33:06 EDT 2014

Property based testing

- Model the state
- Wrap each API call in a state transition function (post condition)
- Generate random sequences of API calls until failure
- Verify postcondition
- On failure, shrink test

The pre/post conditions seem straightforward.  How to shrink tests?

For an ordered list of N calls, how many ordered subsets are there?
How can they be organized in a tree such that they can be searched
more effectively?

Simplification: the assumption is that some calls are irrelevant.
I.e. we've found a way to trigger a bug and we just want to simplify
that particular way - not find a new way to trigger.  So a search
strategy is a tree of permutations, with pruning for cases that stop

I.e. when removing a particular call no longer fails the test, we
label it as essential and won't test the removal of any more calls
with that one call removed as well.  Note that it might be that there
are triggerable bugs in that subtree!  But that's not what we're

So how to represent?

- A stateful test is a list of API calls together with their

- The test function is composed from the list of calls and the state
  transition model.