Bounding Random Test Set Size with Computational Learning Theory
Open Access
- 12 July 2024
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Software Engineering
- Vol. 1 (FSE) , 2538-2560
Abstract
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, to provide an upper-bound on the number of tests required to achieve a given level of adequacy. We validate this bound on a large set of Java units, and an autonomous driving system.Keywords
All Related Versions
Funding Information
- EPSRC (EP\/T030526\/1)
This publication has 56 references indexed in Scilit:
- Reachable Coverage: Estimating Saturation in Fuzzing2023
- An Empirical Study on Mutation, Statement and Branch Coverage Fault Revelation That Avoids the Unreliable Clean Program Assumption2017
- Assessing and generating test sets in terms of behavioural adequacySoftware Testing, Verification and Reliability, 2015
- Using machine learning to refine Category-Partition test specifications and test suitesInformation and Software Technology, 2009
- Randomized Differential Testing as a Prelude to Formal Verification29th International Conference on Software Engineering (ICSE'07), 2007
- Using Vapnik–Chervonenkis Dimension to Analyze the Testing Complexity of Program SegmentsInformation and Computation, 1996
- A Formal Interpretation of Software Testing as Inductive InferenceSoftware Testing, Verification and Reliability, 1996
- Operational profiles in software-reliability engineeringIEEE Software, 1993
- Inductive inference and software testingSoftware Testing, Verification and Reliability, 1992
- An applicable family of data flow testing criteriaIEEE Transactions on Software Engineering, 1988