Formal analysis of the effectiveness and predictability of random testing

There has been a lot of work to shed light on whether random testing is actually a useful testing technique. Despite its simplicity, several successful real-world applications appear in the literature. Although it is not going to solve all possible testing problems, random testing is an essential tool in the hands of software testers. In this paper, we address general questions about random testing, such as how long random testing needs on average to achieve testing targets (e.g., coverage), how does it scale and how likely is it to yield similar results if we re-run random testing on the same testing problem. Due to its simplicity that makes the mathematical analysis of random testing tractable, we provide precise and rigorous answers to these questions. Our formal results can be applied to most types of software and testing criteria. Simulations are carried out to provide further support to our formal results. The obtained results are then used to assess the validity of empirical analyses reported in the literature. Results show that random testing is more effective and predictable than previously thought.