Using random test selection to gain confidence in modified software

This paper presents a method that addresses two practical issues concerning the use of random test selection for regression testing: the number of random samples needed from the test suite to provide reliable results, and the confidence levels of the predictions made by the random samples. The method applies the Chernoff bound, which has been applied in various randomized algorithms, to compute the error bound for random test selection. The paper presents three example applications, based on the method, for regression testing. The main benefits of the method are that it requires no distribution information about the test suite from which the samples are taken, and the computation of the confidence level is independent of the size of the test suite. The paper also presents the results of an empirical evaluation of the technique on a set of C programs, which have been used in many testing experiments, along with three of the GCC compilers. The results demonstrate the effectiveness of the method and show its potential for regression testing on real-world, large-scale applications.