  Random testing approaches work by generating inputs at random, or by
selecting inputs randomly from some pre-defined operational profile. One
long-standing question that arises in this and other testing contexts is as
follows: When can we stop testing? At what point can we be certain that
executing further tests in this manner will not explore previously untested
(and potentially buggy) software behaviors? This is analogous to the question
in Machine Learning, of how many training examples are required in order to
infer an accurate model. In this paper we show how probabilistic approaches to
answer this question in Machine Learning (arising from Computational Learning
Theory) can be applied in our testing context. This enables us to produce an
upper bound on the number of tests that are required to achieve a given level
of adequacy. We are the first to enable this from only knowing the number of
coverage targets (e.g. lines of code) in the source code, without needing to
observe a sample test executions. We validate this bound on a large set of Java
units, and an autonomous driving system.
