A Probabilistic Analysis of the Efficiency of Automated Software Testing
We study the relative efficiencies of the random and systematic approaches to automated software testing. Using a simple but realistic set of assumptions, we propose a general model for software testing and define sampling strategies for random (R) and systematic (S0) testing, where each sampling is associated with a sampling cost: 1 and c units of time, respectively. The two most important goals of software testing are: (i) achieving in minimal time a given degree of confidence x in a program's correctness and (ii) discovering a maximal number of errors within a given time bound n. For both (i) and (ii) we show that there exists a bound on c beyond which R performs better than S0 on the average. Moreover for (i) this bound depends asymptotically only on x. We also show that the efficiency of R can be fitted to the exponential curve. Using these results we design a hybrid strategy H that starts with R and switches to S0 when S0 is expected to discover more errors per unit time. In our experiments we find that H performs similarly or better than the most efficient of both and that S0 may need to be significantly faster than our bounds suggest to retain efficiency over R.
IEEE Transactions on Software Engineering