Note the examples in this blogpost are in JavaScript, but this method can be used in most languages.

Testing shows the presence, not the absence of bugs - Edsger W Dijkstra 1969

In the last few years it has become the norm to write tests along side code to help ensure correctness in our code. This is a good thing, as long as we can define what is correct.

in most cases we test by giving the computer an example of what we want to test and ensuring that it runs correctly. This ensures that for a specific case (or maybe a few specific cases) that our code will run correctly. Let’s say we have a sort function that we wish to test, (A silly example, but it fits well in the space for a blog post). We might write some tests like this, JavaScript code:

var mocha  = require("mocha");
var assert = require("assert");

describe("sort", function() {
    it("should work on an empty list", function() {
        assert.deepEqual([],[].sort());
    });
    it("should work on a list of numbers", function() {
        assert.deepEqual([1,2,3],[1,3,2].sort());
    });
})

In this case we check the empty list and the list [1,3,2] and call it a day. But is that every possible case? What if we want a few more cases? Well we could think of a few but that is time consuming and lets face it will probably not happen under the time pressure of a normal project.

But what if we could ask the computer to do it for us? We could say tell it to generate a random list of integers and then sort that list. We could then run a number of tests to ensure that the list is sorted. If we tell the computer to generate 100 random lists (or 1,000 or 100,000) then there is a good chance that any combination that could cause a problem will be tried.

This idea is called QuickCheck, Property Based Testing or sometimes Fuzz Testing depending on the language. If you google quickcheck and your language name you should find a library to use.

There is a library for JavaScript called JSVerify that will do exactly this.

Lets see how it works. The first thing that we need is a property to test for a sort we might come up with a few properties, for example…

  • If we sort the list twice it should be the same as sorting it once
  • The length of the list should not change
  • The list is sorted

Feel free to come up with a few more

Lets look at how this would look. We use the method jsc.property to run this, it takes three parameters, a string for a test name, a description of the data to work with, in this case we pass it “array nat” which will cause it to generate an array of natural numbers (I.E. non negative integers) , and a function. The function should test something and return true if the property holds.

Now lets assume that we have a sort function badsort() which we know has some problem, but we don’t know what. So we write these two properties…

var jsc		= require("jsverify");
var _		= require("underscore");
var mocha	= require("mocha")

describe("sort", function () {
    jsc.property("sort is idempotent", "array nat",
		 function (arr) {
		     return _.isEqual(badsort(badsort(arr)),
				      badsort(arr));
		 })

    jsc.property("Length Does not Change", "array nat",
                 function (arr) {
		     return arr.length === badsort(arr).length
		 });
});

what happens when this is run? (Note this has been edited for readability)

mocha stable_sort.js


  sort
    ✓ sort is idempotent
    1) Length Does not Change


  1 passing (19ms)
  1 failing

  1) sort Length Does not Change:
     Error: Failed after 1 tests and 2 shrinks. Counterexample: [6, 6];
      at node_modules/jsverify/lib/jsverify.js:360:15
      at Object.map (node_modules/jsverify/lib/functor.js:35:12)
      at checkThrow (node_modules/jsverify/lib/jsverify.js:354:30)
      at Context.<anonymous> (node_modules/jsverify/lib/jsverify.js:400:14)

Note that the first property passes but the 2nd one fails with a counter example of [6,6]. If run again it will give another counter example, but it will still show a duplicate element, in testing this I saw [18,18], [0,0], [29,29] and others. From this we can see that badsort() is having a problem when there are repeated elements in the list.

You will also notice that the only failing cases it shows have a length of 2! There is some magic going on here! If we tell it to print out the failing cases we get this (obviously this will change every run). What JSVerify is doing here is called Shrinking, and it is in effect doing a depth first search on the solution space. It assumes that for any failing case it can always find a simpler case. So it will remove elements from a list, or reduce numbers until it can’t go any farther.

If we add a console.log when the assertion fails we get this

    ✓ sort is idempotent
[ 17, 14, 15, 26, 17 ]
[ 14, 14, 15, 26, 17 ]
[ 14, 14, 26, 17 ]
[ 14, 14, 17 ]
[ 14, 14 ]

The first line in this case has 5 elements, but in theory it could have 50 so it is not obvious that the duplicate element is the problem. In each line the library has done something to simplify the error case, which could be making the integers smaller or removing elements from the list. So the final version has 2 elements! So here the computer did the hard work for us in that it found a case in which our code is wrong, and it showed us the simplest case for which it holds.

For the record here is badsort(), you can see it removes duplicates from a list, which is just what the property said it is doing.

var badsort = _.compose(_.sortBy, _.uniq);

In this blog post I went with a very simple example to explain the idea of randomly generating a test, but there are many more complex examples where you can test not by creating parameters to a function but by creating sequences of events or the like.

I am going to be giving workshops on doing property based testing in Javascript in London, Tel Aviv and Be’er Sheva.

In addition I will be giving a workshop on testing apis and more with Properties in Python in London