Paul E. Black and Scott Ranville, Winnowing Tests: Getting Quality Coverage from a Model Checker without Quantity, Proc. 20th Digital Avionics Systems Conference (DASC), Vol. 2, pp 9B6/1-9B6/4, Daytona Beach, Florida, IEEE, October 2001.

Abstract:

    Test generation is easy: we can generate piles of tests randomly, by model checker mutation analysis of formal specifications, through path coverage, etc. But just increasing the quantity of tests may not be a cost-effective way of increasing the quality of the test. The number of tests, and hence the cost of maintaining and running large test sets, can increase exponentially with the increase in real coverage.

    We present a number of automated methods to pick out a smaller set of tests that still have good coverage. The first method is finding a subset of tests with equal coverage for a test criterion. To do this, we must measure the coverage for a test set, given a test criterion. Some possible test criteria are path coverage, n-switch, specification mutation, and branch coverage. We use a greedy algorithm to choose tests satisfying requirements of the criterion.

    Second, tests that are prefixes of other, longer tests or duplicates may be dropped. Finally, define the cross section of a requirement as the reciprocal number of tests that satisfy it. We can choose tests with the highest resolution, that is, tests satisfying requirements with the smallest cross section, since these are likely to be the most sensitive tests.

Get the paper in RTF (29k) or ASCII text (13k).

This page's URL is /~black/Papers/dasc2001.html

Updated Thu Sep 27 15:12:38 2007

Go to Black's papers or NIST home page.