Abstract
We study the efficiency 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) 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 cases, we show that there exists a bound on c beyond which R performs better than S on the average. Moreover for the first case (i), this bound depends asymptotically only on x. Assume, for example, a random test generator R takes only 10ms to generate and execute a test case. To determine whether a program works correctly for 90% of its input, the most effective systematic test generator S must not take more than 41ms to generate and execute a test case! Otherwise, R is expected to establish the 90% degree of confidence earlier.
Biography
Marcel Böhme is a Postdoctoral Fellow with Prof. Andreas Zeller at Saarland University. He completed his PhD at National University of Singapore advised by Prof. Abhik Roychoudhury and received his Dipl.-Inf. (cf. M.Sc.) from Technische Universität Dresden, Germany in 2014 and 2009, respectively. His research is on testing, debugging, and repair of evolving programs — where he seeks to understand and elucidate intrinsic properties such as the efficiency of automated testing, the complexity of realistic software errors, the reliability of automated program repair, and the interaction of faults and changes, amongst others. Generally, his work is driven towards establishing and extending the formal foundations of Software Engineering.
