Using Markov chains for test data generation

(I know, doesn't that blog title just put you to sleep?)

Here's a nice essay about some folks that used Markov chains to write a nifty test data generator.

The article does a good job of explaining the underlying theory behind Markov chains, and also explains some of the implementation details they had to overcome, such as how they used a reference implementation as an oracle, to decide whether their code had passed a particular test or not, and how they had to train their test data generator by feeding it samples of test cases that they already had in place.

I also like the fact that they didn't turn to this technique until they had already developed a large testbed of test cases via other mechanisms:

• internally-developed test cases
• test cases contributed by customers
• test cases constructed by harvesting data off the internet

These sort of test case generation techniques seem to me to be more likely to be fruitful first; it makes sense that after they felt they had exhausted the reach of such test cases, they got more innovative and turned to the Markov chain technique to try to generate more test cases.

You're never done testing. When you think you are, consider a new technique.