Techniques for test selection, give a large suite of test cases

Question

I have a huge collection of test cases (inputs). I'd like to select a small subset that's likely to catch most of the bugs. Are there any standard or known techniques in the testing literature for doing this?

---

(If it's relevant, this is to assist with fuzz testing, where you feed an input to the program and see if it crashes. I can compile a large collection of seed files, many of which are probably roughly "equivalent" in that they test the same set of features of the program; I want to select a small subset of them that have good diversity and between them will test as much of the program as possible, eliminating duplicates. I know of one techniques based upon evaluating statement coverage and using minimum set cover, but I'm wondering if this is the sort of problem that has been studied in the testing literature.)

Answer 1

You have a several options here. Implementation and effectiveness will vary, but IME, all are viable solutions.

1. Coverage - Run the tests that test changed code. If you run the same suite of tests twice on a given build, you should get the same results (otherwise, we should be discussing something different). One technique for reducing your test suite size is to run only the tests that hit changed code. You can get ultra-accurate using code coverage (tracing which tests hit which lines of code), but even some metadata on feature area may help you use something like this.

2. Random sampling - Pick a random set of tests from the whole product - or better yet, a random set of tests from each feature area. I've run multiple experiments (and encourage you to run your own) that show that a random sample of 10-15% of tests making up the test suite are highly predictive of the overall test suite pass rate. If a particular area exhibits a lower than expected pass rate, you can choose to run more tests in that area.

3. You can put a small negative weighting on tests that have always passed (especially in combination with #1 above). Given a test that has found bugs before and another test that has never found a product issue, I'd likely choose the test that has found issues before.

There are others (age of test, areas of the product with known errors, etc.), but the three above are the primary heuristics I've used for test selection.

Answer 2

D.W.,

Background Comment

I got into the software testing industry driven by a desire to answer the questions you posed. Since then, I've been examining ways to (a) create the most powerful sets of software tests that are relatively small in number, and (b) measure the actual effectiveness of such sets of tests. It's a topic I'm passionate about. (I must be passionate or nuts or both as it's currently 5:45 AM as I'm writing this...)

Design of Experiments is a decades-old field devoted to answering your question, e.g., "What should I test if I can't test everything? How can I learn as much as possible in as few tests as possible?" Design of Experiments-based test design methods are widespread in agriculture, marketing, manufacturing and many other industries. These Design of Experiments-based methods to selecting subsets of highly effective tests are absolutely applicable to the software testing field but fewer than 5% of software testers use them to select their tests.

I've been applying techniques from Design of Experiments in the software testing field intensely for 6 or so years now. Many papers and experience reports, including a paper I co-published in IEEE Computer with 3 PhD's, show that these approaches to selecting relatively small numbers of software tests work well. These techniques (most of which are referred to in user246's answer to this question) include:

• Pairwise Testing
• Combinatorial Testing
• Orthogonal Array Testing / OATS

Proposed Solution to Your Specific Question

Assume you have a system under test that has a trillion possible tests that you can think of to execute were time constraints not an issue.

Scenario 1: You do not have any information about:

• Which code was just changed (e.g., you wanted to test the whole system and it was all built from scratch and yet to be tested),
• Which tests have regularly passed in prior runs (because, in this scenario, by definition, no tests have been run previously)

In this scenario, I would strongly recommend you use a Design of Experiments-based combinatorial approach to selecting your tests. (Disclaimer: I created the test case generating tool Hexawise after measuring the effectiveness of Design of Experiments-based test case selection approaches so I could fairly be accused of being biased).

Start with a pairwise selection of tests, and as you execute those, and learn more abou the system, how it is working, where its weak points are, etc., and other ideas for tests occur to you, then edit those tests by: (a) adding new test inputs and (b) adjusting weightings on your test inputs to focus more on problem areas, and (c) time permitting, increasing the coverage strength of your generated tests to 3-way (all possible combinations of three test inputs would be tested together in at least one test case) or an even higher coverage strength if you're automating test execution.

You will find that this approach to test case selection will be:

• Far more efficient than hand-selected sets of test cases because (a) the Design of Experiments-based tests will be far less accidental repetition of combinations being tested again and again, and (b) the Design of Experiments-based tests will have far fewer gaps in coverage (e.g., 100% of dual-mode faults (AKA pairwise defects)) would be covered.

Scenario 2: You're testing the same System Under Test (for which you can think of a trillion possible tests you could theoretically execute) but this time you DO have information about:

• Which code was just changed (e.g., you wanted to test the whole system and it was all built from scratch and yet to be tested),
• Which tests have regularly passed and fails in prior runs

In this type of situation, I would encourage you to:

Start with the Design of Experiments-based approach to selecting tests just mentioned, and, as proposed by Alan, also

• Changed Code: pay particular attention to ensuring that you're including tests in your test suite that thoroughly test the recently changed code. You can do this by instructing your test generating tool to seed / include particular tests that you identify in the Design of Experiments-based tests it generates.
• Tests that have failed more often than others in prior runs: consider seeding those tests in your generated set of tests as well.

These approaches will give you:

• Maximum coverage in the fewest possible tests* (both scenarios)
• Minimum wasteful repetition (both scenarios)
• Additional focus on high priority areas (scenario 2 only - e.g., where code was changed and where known trouble spots are

*It is worth pointing out that when you select tests using this approach, you can select a coverage strength to suit your thoroughness objectives and timing constraints. You could generate a couple dozen 2-way tests (AKA pairwise tests or allpairs tests) for example if you were in an extreme hurry or a couple thousand 6-way tests if you wanted extraordinary thoroughness or a couple hundred 4-way tests. Or any number of tests in between.

Answer 3

If the following assumptions are true, you may want to try choosing a set of test cases that satisfy the pairwise criterion:

1. You can describe the behavior you want to test in terms of a set of independent parameters, each of which has a set of possible values that you want to try.
2. You can describe each test case in terms of those parameters, e.g. parameter 1 = X, parameter 3 = Y.

If assumption #1 is true, you can think about your test plan as a combinatorial problem, where each test case is as tuple of (value of parameter 1, value of parameter 2, ..., value of parameter N). If there many parameters, and each parameter has several possible values, the total number of test cases (the total number of tuples) can be unmanageable large.

The pairwise criterion is predicated on the idea that most bugs arise from either a single parameter value or the interaction between specific values for a pair of parameters. Here is the criterion: choose your tests so that every pair of possible values is exercises at least once. To learn more, search this forum for Combinatorial Testing (we should make a tag for that) or Google for "pairwise testing".

If assumption #2 is true, you may be able to choose tests that satisfy the pairwise criterion.

Answer 4

If you really must use a subset, use the test cases that have been most effective at catching bugs in the past.

Sprinkle in a batch of test cases that have particular relevance for the portions of you system most at risk (either because they have changed the most, or would have higher cost associated with a failure).

Add a smattering of others representing areas that aren't covered by the above cases.

Answer 5

I think it was James Bach that proved (well... more of "explained") why pairwise and random testing converge as the number of random tests increase. his rule of thumb for choosing the number of test is-

• Find the two variables with the biggest number of individual values
• Multiple the number of those individual values
• Multiply again by a constant (2 is a good choice :-) )
• The results is the number of tests

see James's article here

The podcast here with more details

The mathematical explanation, Birthday Paradox

Answer 6

Would this article from MS be of any use ?

Answer 7

In reading through the testing literature, I've found some research papers on "test set size minimization". They discuss using block coverage for test set minimization.

Here's how that works. Given a large collection T of test cases, they look for a subset S of test cases that has the same block coverage as T (i.e., every block that is covered by some test case in T will also be covered by some test case in S). This is a set cover problem.

I found a paper which did an experiment with this kind of test set minimization, and they found that coverage-based minimization was very effective: it had only a small reduction in the effectiveness of the test set at detecting faults, while significantly reducing the size of the test set. Here's the reference:

• Test set size minimization and fault detection effectiveness: A case study in a space application. W. Eric Wong, Joseph R. Horgan, Aditya P. Mathur, and Alberto Pasquini. Computer Software and Applications Conference (COMPSAC) 1997.

• Sidebar: Here's an interesting detail I took away from that paper. Rather than using set-cover straight off to minimize the test set, they discuss a hybrid approach to minimization using coverage.

  There are two phases. In Phase 1, they evaluate each test set, sequentially, one at a time. If a test t covers some new block that was not previously covered by a prior test, then keep t. On the other hand, if t does not cover any new block, then discard t. The set of test cases that are retained during Phase 1 are then used as an input to Phase 2. In Phase 2, we apply an algorithm for the set-cover problem to find a minimal subset of those test cases that has the same aggregate coverage. Because the input to Phase 2 has already been significantly reduced, it is possible to apply an expensive algorithm for set cover.

  Why not apply set cover to the entire set of test cases and skip Phase 1? Presumably, they are worried about the fact that the set-cover problem is exponential in the worst case. By winnowing down the size of the test pool in Phase 1, they can then apply a more expensive algorithm for set-cover that finds the exact minimum solution, rather than an approximate solution.

However, a later paper reported some cautionary notes. They found that the utility of coverage-based test set minimization varies depending upon the program. For some programs, coverage-based minimization significantly reduced the number of test cases without significantly impacting the effectiveness of the test set at detecting faults. However, for some other programs, coverage-based minimization had the side effect of significantly reducing the effectiveness of the test set. They conclude that the benefits of coverage-based minimization are unclear and hard to predict, and that this area is not as well-understood as one would like. Here's the reference:

• Empirical Studies of Test-Suite Reduction. Gregg Rothermel, Mary Jean Harrold, Jeffery von Ronne, and Christie Hong. Software Testing, Verification, and Reliability. Volume 12, issue 4, pp.219--249, December 2002.