Paul E. Black and Scott Ranville,
Winnowing Tests: Getting Quality Coverage from a Model Checker
Proc. 20th Digital Avionics Systems
Conference (DASC), Vol. 2, pp 9B6/1-9B6/4,
Daytona Beach, Florida,
IEEE, October 2001.
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
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
Get the paper in
RTF (29k) or
ASCII text (13k).
This page's URL is /~black/Papers/dasc2001.html
Thu Sep 27 15:12:38 2007
by Paul E. Black
Black's papers or
NIST home page.