Assurances in Software Testing: A Roadmap

Marcel Böhme

Abstract

Traditional software testing often relies on heuristic-based stopping criteria and qualitative assessments of risk. This paper presents a roadmap for transitioning toward a rigorous statistical framework known as Software Testing as Species Discovery (STADS). By leveraging decades of research in ecological biostatistics, STADS treats program behaviors and vulnerabilities as biological species and test inputs as individuals within a population. This approach enables practitioners to mathematically quantify residual risk, estimate the total number of discoverable bugs, and provide a sound basis for certification in security-critical domains.

Introduction

In the development of security-critical software—such as medical devices, automotive systems, and industrial controllers—the fundamental challenge is not merely finding bugs, but knowing when to stop looking. Modern automated testing, specifically "fuzzing," generates massive volumes of random or semi-random inputs to stress-test programs. However, if a fuzzer runs for several days without identifying a crash, developers are left with a difficult question: Is the software robust, or does the fuzzer simply require more time?

Currently, the decision to terminate testing is largely driven by "experience-based" intuition rather than formal metrics. While certification standards like IEC 62443 mandate testing, they lack concrete thresholds for allowable residual risk. This paper proposes the STADS framework to bridge this gap, moving the field from vivid anecdotes toward a systematic, statistical quantification of uncertainty.

The STADS Framework: An Ecological Analogy

The core innovation of STADS is the application of ecological biostatistics to software behavior. In this framework, the testing process is modeled as a sampling problem:

  • Test Input: An individual sampled from a vast population of possible inputs.
  • Program Behavior: A "species." This can represent a specific code branch, an execution path, or a unique bug.
  • Discovery: The moment a fuzzer generates an input that triggers a previously unobserved behavior.

By treating software testing as a species discovery problem, we can apply established estimators to predict what remains hidden in the "dark matter" of the software's state space.

Mathematical Foundations of Assurance

To transform testing logs into actionable assurance data, STADS utilizes several key statistical tools:

1. Estimating Residual Risk (Good-Turing)

The Good-Turing estimator is used to calculate the probability that the next test input will reveal a new, undiscovered behavior. This is defined as the Residual Risk: $$\hat{U}(n) = f_1 / n$$ Where $n$ is the total number of tests and $f_1$ is the number of "singletons"—behaviors that have been observed exactly once. A high number of singletons suggests that the fuzzer is still discovering new territory and that the probability of finding more bugs remains high.

2. Predicting Total Species (Chao Estimators)

Chao estimators allow testers to predict the asymptotic number of species (bugs or branches) within a program. This provides a target for "completeness," allowing a manager to estimate how many vulnerabilities a specific fuzzer is capable of finding in a given target, even if they have not all been found yet.

3. Cost-Benefit Extrapolation

Using mathematical models to extrapolate the discovery curve, STADS can predict how many additional behaviors will be found if testing continues for $m$ more hours. This allows for a rigorous cost-benefit analysis, enabling organizations to decide if the predicted increase in coverage justifies the additional computational expense.

Key Insights for Software Engineering

Beyond providing metrics, the STADS framework offers several conceptual shifts in how we view software quality:

  • Testing as Sampling: Unlike physical engineering, where safety margins account for continuous stress, software behavior is discrete and discontinuous. The biological metaphor of species diversity is uniquely suited to this discrete nature.
  • The Significance of Singletons: The presence of behaviors triggered only once is a critical indicator of instability. If a testing suite produces many singletons, the testing process is far from saturation.
  • Redefining Testability: The paper suggests that "testability" can be mathematically defined as the average amount of information a program reveals about its internal behaviors per generated test input.
  • Embracing Flakiness: Rather than treating non-deterministic "flaky" tests as errors to be eliminated, the framework suggests modeling flakiness as a core property of the system using statistical distributions.

Limitations and Future Directions

While STADS provides a robust foundation, several challenges remain. The Oracle Problem is a primary concern: statistics can only quantify the discovery of recognizable behaviors. If a fuzzer triggers a vulnerability but the monitoring system (the oracle) fails to flag it as a bug, the resulting risk estimates will be overly optimistic.

Furthermore, modern grey-box fuzzers often use genetic algorithms to evolve inputs, which violates the "Independent and Identically Distributed" (IID) assumption required for basic Good-Turing statistics. Future research must focus on developing bias-correction mechanisms, such as the Horvitz-Thompson estimator, to account for the adaptive nature of modern search-based testing tools.

Conclusion

The STADS framework provides a roadmap for moving software testing from an art to a science. By quantifying residual risk and predicting testing outcomes through the lens of species discovery, we can finally provide the rigorous assurances required for the world's most critical software systems.

Summary updated

BibTeX
@inproceedings{bohme2019assurances,
  author = {Marcel Böhme},
  title = {{Assurances in Software Testing: A Roadmap}},
  booktitle = {ICSE (NIER)},
  year = {2019},
  doi = {10.1109/icse-nier.2019.00010},
}
Figure