At work, I have to test a program that has 18 separate features, nearly all of which can be used in combination with each other, and each of which has multiple ways it can be used. Some of features are binary -- the feature is either used or it isn't -- but a few features have five or six variations.
I want to test each possible combination of feature, because most bugs are attributable to either a single feature or a combination of two features. A brute force way of doing this pairwise testing would require hundreds of individual tests. A cleverer version created by hand might be able to get away with using only fifty tests or so, except that there are several combinations that are invalid, and keeping track of all of them is a real headache.
It turns out there are programs designed to solve this problem. For example, jenny. I wrote a little python wrapper around jenny, so that I can use descriptive feature names instead of numbers and letters, and then I set it loose on my problem. It came up with a solution requiring only 35 tests. Since the minimum possible number of tests is at least 30, I figure 35 is pretty good. And since the problem is NP hard in the general case, "pretty good" is good enough.
A google search for combinatorial testing will yield a lot more information about the technique, if you're interested.
Posted on April 19, 2004 10:48 PM
More testing articles
There is also a significant literature on this in mathematics. You should look into Block Designs (in particular Balanced Incomplete Block Designs (BIBD)) or v-k-lambda designs.
Posted by: Matt at May 24, 2004 01:34 PMThanks for the pointer. I looked it up at mathworld, which describes a block design as "an incidence system (v, k, l) in which a set X of v points is partitioned into a family A of b subsets (blocks) in such a way that any two points determine l blocks with k points in each block, and each point is contained in r different blocks."
This isn't quite the same thing as what combinatorial testing is doing. In particular, the choice of r is not constant -- instead, it just has to be greater than one. Also, in combinatorial testing, there are constraints between the points (a.k.a. features) -- points within the same dimension cannot be tested against each other.
Posted by: Kim at May 25, 2004 11:20 AMWell, there is a lot of mathematical literature on the topic. But in my opinion there is not enough communication between the theoreticians and practitioners. The test case template needed is called a covering array. Covering arrays can provide pairwise, 3-way, or higher strength coverage. There is some background material at http://testcover.com/pub/background/index.php and you may find the test case efficiency information at http://testcover.com/pub/performance.php interesting. Good luck with your testing!
Posted by: George Sherwood at September 21, 2005 07:49 PM