A Probabilistic Analysis of the Efficiency of Automated Software Testing
- 5 October 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. 42 (4), 345-360
- https://doi.org/10.1109/tse.2015.2487274
Abstract
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 (S 0 ) 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 S 0 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 S 0 when S 0 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 S 0 may need to be significantly faster than our bounds suggest to retain efficiency over R.Keywords
Funding Information
- Singapore's Ministry of Education (MOE2010-T2-2-073, MOE-2011-T2-2-012)
- ERC
- SPECMATE
This publication has 33 references indexed in Scilit:
- Probabilistic symbolic executionPublished by Association for Computing Machinery (ACM) ,2012
- On the Danger of Coverage Directed Test Case GenerationLecture Notes in Computer Science, 2012
- Testing Container Classes: Random or Systematic?Lecture Notes in Computer Science, 2011
- Improving evolutionary testing by means of efficiency enhancement techniquesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2010
- Proofs from testsPublished by Association for Computing Machinery (ACM) ,2008
- A survey of coverage based testing toolsPublished by Association for Computing Machinery (ACM) ,2006
- DARTPublished by Association for Computing Machinery (ACM) ,2005
- Code coverage, what does it mean in terms of quality?Published by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Estimating the Number of Species: A ReviewJournal of the American Statistical Association, 1993
- A theory of fault-based testingIEEE Transactions on Software Engineering, 1990