Greg Heartsfield home

QuickCheck Love

If you actually want to get started with QuickCheck, check out the HaskellWiki. The following is just meant to give a simple motivating example for using QuickCheck.

We’ve implemented some simple symmetric block ciphers in Haskell, all of which have encryption/decryption functions with types like the following:

tea_enc :: Int                              -- Cycle count
        -> (Word32, Word32, Word32, Word32) -- 128-bit key
        -> (Word32, Word32)                 -- Input block
        -> (Word32, Word32)                 -- Output block

For these ciphers, we want to verify the very simple property that when using the same key, encrypting and then decrypting a block will yield that same block. That property is represented with the code below (which takes the encryption/decryption ciphers, a key, and an input block as arguments):

test_identity enc dec key input =
    input == dec key (enc key input)

Now, we want to use QuickCheck to randomly generate keys and input blocks, and check the identity property. To do that, we’ll change the function to just take the cipher algorithms as arguments, and use QuickCheck to generate the rest.

test_identity enc dec =
    quickCheck (\key input ->
                input == dec key (enc key input))

Notice how it’s almost identical to our original function that tests a single instance of the property. The only change was moving the arguments that we want to vary into a lambda function, and handing it off to the quickCheck function. QuickCheck figures out how to generate the required arguments, pumps out arbitrary values, and tests them against the given property.

Finally, we can run some tests on our cipher (using 32 cycles):

TEA> test_identity (xtea_encode 32) (xtea_decode 32)
OK, passed 100 tests.

Let’s deliberately cause the property to be invalidated by changing just the encoding function and re-running the test:

TEA> test_identity (xtea_encode 32) (xtea_decode 32)
Falsifiable, after 1 tests:
(3,4294967295)
(2,1,0,4294967295)

Which tells us after the very first test, it was able to find an input block and key that make the property false. Notice the numbers QuickCheck selected for its first test, they do not appear random, and in fact, QuickCheck doesn’t necessarily generate random values for types. In this case, it is starting with what look like typical corner cases (very large numbers, zero, small numbers).

Note: QuickCheck isn’t natively able to generate arbitrary values for the type Word32, so we had to tell it how to do so, with the following code, which maps arbitrary integers onto Word32 values (courtesy of a haskell-cafe post by Sebastian Sylvan):

instance Arbitrary Word32 where
    arbitrary = do c <- arbitrary :: Gen Integer
		   return (fromIntegral c)

By making any user-defined type an instance of Arbitrary, you can have QuickCheck automatically generate tests for properties that take that type as an argument.

xUnit tests definitely have their place. Some ciphers have sets of test vectors for instance, which exploit very specific corner cases in the algorithm. But for testing general properties of code, the quickcheck style can be very intuitive.

Validate XHTML Validate CSS