A probabilistic analysis of coverage methods

Coverage is an importantmeasure for the quality and completeness of the functional verification of hardware logic designs. Verification teams spend a significant amount of time looking for bugs in the design and in providing high-quality coverage. This process is performed through the use of various sampling strategies for selecting test inputs. The selection of sampling strategies to achieve the verification goals is typically carried out in an intuitive manner. We studied several commonly used sampling strategies and provide a probabilistic framework for assessing and comparing their relative values. For this analysis, we derived results for two measures of interest: first, the probability of finding a bug within a given number of samplings; and second, the expected number of samplings until a bug is detected. These results are given for both recurring sampling schemes, in which the same inputs might be selected repeatedly, and for nonrecurring sampling schemes, in which already sampled inputs are never selected again. By considering results from the theory of search, and more specifically, from the well-known multiarmed bandit problem, we demonstrate the optimality of a greedy sampling strategy within our defined framework. © 2011 ACM.