Stateful Property-Based Testing
Until now, we’ve mostly looked at property-based testing in the context of testing pure, stateless functions that take an input and return an output. However, property-based testing is also useful for testing stateful systems. A stateful system is a system that, well, carries state. For example, a database is a stateful system.
In our examples so far, we only used property-based testing to generate some data and then feed it to a piece of code and assert on the result of that. With stateful systems, things change: we now have to deal with setting a state and only executing some operations when the system is in a given state. Let’s see how we can use property-based testing for something like that.
Modeling the Stateful System
We know how to generate random data through our property-based testing framework. We can take advantage of this knowledge to generate random commands that we can issue on our stateful system. For example, if our stateful system is a database, we can generate random commands to issue against this system. However, if the commands are random, how do we assert on their effects on the system? Enter the system model. The whole idea behind property-based testing of a stateful system revolves around the idea of modeling the real system with a model that represents that system from the perspective we’re interested in. Once we have this model, we can execute the commands we generated on the real system and on the model and then verify that the effects of the commands match. This sounds complex, so let’s break it down with an example.
Let’s imagine we wrote a key-value store where we can write values stored under unique keys and retrieve those values using the corresponding keys.
| | iex> kv_store = KVStore.new() |
| | iex> KVStore.set(kv_store, "key1", "some value") |
| | iex> KVStore.get(kv_store, "key1") |
| | "some value" |
| | iex> KVStore.delete(kv_store, "key1") |
| | iex> KVStore.get(kv_store, "key1") |
| | nil |
This is a stateful system where the state is the set of key-value pairs stored in the key-value store created with KVStore.new/0. One thing we could test about this system is that retrieving an existing key always returns the last value set for that key or a null value if the last operation was to delete the value, no matter how many times we set or delete that key. How can we model our key-value store in order to test this property? We can start with a simple two-element tuple {key, value} that stores the key we’re interested in and its current value (or nil if the key hasn’t been set yet). Let’s use pseudocode to see how we could generate a command assuming we’ve already generated a random key called random_key:
| | def command do |
| | one_of([ |
| | command(:set, [random_key, term()]), |
| | command(:delete, [random_key]) |
| | ]) |
| | end |
For every possible command that we can issue on the stateful system, we need to define what happens to our model. Let’s continue with pseudocode:
| | def set({key, _old_value}, key, new_value) do |
| | {key, new_value} |
| | end |
| | |
| | def delete({key, _value}, key) do |
| | {key, nil} |
| | end |
Now we also need to define a get command to retrieve the current value for the key in our model:
| | def get({key, value}, key) do |
| | value |
| | end |
We have our commands reflected in the model. Now comes the fun part. We generate a random list of commands. Then, we execute those commands one by one both on the model and on the real system. Finally, we verify that the value stored in our model is the same as the value stored under our key in the stateful system.
The reason we’re being generic and not showing working code in these examples is that stream_data still doesn’t provide tools for working with stateful testing (even if it’s coming up in the future).
The Benefits of Stateful Property-Based Testing
Even if stream_data doesn’t support stateful property-based testing yet, we still wanted to mention it and go over the basic concepts behind it since it’s a powerful and useful tool. All of the benefits of property-based testing that we’ve discussed in this chapter apply to stateful property-based testing as well.
An especially useful behavior of stateful property-based testing is that the random lists of commands that we generate is shrunk in case of failure. This means that when a property fails, the framework will present us a small list of commands with small inputs that cause the failure. This can turn out to be invaluable. A great testimony of this is Google’s leveldb, where as mentioned in Joseph Wayne Norton’s slides,[54] property-based testing uncovered a sequence of 17 calls and then 31 calls that would generate ghost keys in the database. Those were shrunk sequences of commands! Reproducing those bugs would have been a nightmare for a human.