A probabilistic analysis of the efficiency of automated software testing

Marcel Böhme, Soumya Paul

Research output: Contribution to journalArticleResearchpeer-review

25 Citations (Scopus)


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.

Original languageEnglish
Article number7289448
Pages (from-to)345-360
Number of pages16
JournalIEEE Transactions on Software Engineering
Issue number4
Publication statusPublished - Apr 2016
Externally publishedYes


  • Efficient Testing
  • Error-based Partitioning
  • Partition Testing
  • Random Testing
  • Testing Theory

Cite this