An Upper Bound on the Probability That a User Encounters an Undiscovered Defect

Technical Summary: An Upper Bound on the Probability That a User Encounters an Undiscovered Defect

Problem Statement
The paper addresses a critical decision-making gap in software release management: determining the probability that a user of a released product will encounter a defect that was not discovered during beta testing. Existing literature primarily focuses on estimating the number of remaining defects (using software reliability growth models or capture-recapture methods) or the coverage of unseen classes in fuzzing contexts. However, these approaches fail to directly answer the release question because:

1. Count-based methods require an "operational profile" (the distribution of how software is used in the field) to convert a defect count into a user-facing failure probability. This profile is notoriously difficult to estimate.
2. Coverage methods (e.g., Good-Turing) have been applied to software fuzzing, where the "sampler" is a machine generating inputs. In this context, the abundance of a bug reflects the machine's randomness, not the frequency with which human users encounter it.
3. Structural complexity: Software is not a flat, exchangeable population like biological species; it has a reachability structure (trees or DAGs) where some defects are "gated" behind others. Existing methods do not account for how this architecture affects the probability of a user encountering a specific hidden defect.

The authors argue that the release decision requires a direct estimate of the user-weighted missing mass: the probability that a random user will execute a defect unseen in testing.

Methodology
The paper proposes a distribution-free estimator based on the canonical urn construction (Hernández-Suárez [10]), adapted for the software release context.

1. Data Interpretation: Each beta-test report is treated as a draw from the user population, and each distinct defect is treated as a "class." The input data is the set of report counts for each defect.
2. The Canonical Form: The authors define a population model where classes divide into:
   • Ordinary classes: Defects observed multiple times.
   • The Reservoir (All-different component): A theoretical component containing an infinite number of classes with vanishingly small probabilities, such that any draw from it yields a unique, previously unseen class.
3. Maximum Likelihood Estimation (MLE):
   • The paper demonstrates that under the canonical form, the fraction of defects reported exactly once ($s/n$), where $s$ is the number of singletons and $n$ is the total number of reports, is the exact Maximum Likelihood Estimate (MLE) of the unseen proportion ($U$).
   • Conservative Bias: The canonical form assigns every singleton (a defect seen exactly once) to the "unseen reservoir" rather than treating it as a rare ordinary class. Consequently, the estimate $s/n$ systematically overstates the true unseen proportion. This creates a one-sided, conservative upper bound, which is the desired direction for a release decision (erring on the side of caution).
4. Handling Architecture: The method is invariant to the software's internal structure (tree vs. DAG). The authors argue that the "reachability" of a defect is already encoded in the report counts: a defect behind a closed door is reported by zero users, while a defect on a common path is reported by many. Since the estimator relies solely on these counts, it automatically bounds the risk of nested, hidden defects without needing to model the reachability graph.

Key Contributions

1. Reframing the Estimand: The paper shifts the focus from estimating a residual defect count to estimating the user-facing probability of encountering an unseen defect, eliminating the need for an operational profile.
2. Theoretical Justification: It provides a rigorous MLE foundation for the $s/n$ estimator within the canonical urn framework, proving that $s/n$ is the exact MLE of the unseen mass under this construction.
3. Conservative Upper Bound: It establishes that $s/n$ is not merely an estimate but a conservative upper bound on user risk, as the canonical construction forces singletons into the unseen reservoir, ensuring the estimate never underestimates the risk.
4. Structural Invariance: It demonstrates that the estimator is robust to software architecture complexity, as the multiplicity of reports inherently captures the reachability constraints.
5. Validation: The estimator is validated against synthetic populations with known ground truth, confirming that the mean estimate consistently meets or exceeds the true missing mass ($E[s/n] \geq E[U]$).

Results

• Synthetic Validation: Experiments on synthetic populations (both uniform and heavy-tailed) show that the $s/n$ estimator is accurate but consistently conservative. In scenarios where the population is nearly saturated (all defects found), the true missing mass approaches zero, yet $s/n$ remains positive due to the over-attribution of singletons to the unseen reservoir.
• One-Sided Nature: The probability that the estimate exceeds the true unseen proportion is high (e.g., 0.89 to 1.00 in tested scenarios), confirming the bound's reliability for risk-averse decisions.
• Data Requirements: The paper highlights that the method requires encounter-level data (e.g., beta-channel telemetry or crash reports that record the number of users affected per defect). It explicitly states that standard public defect archives are unsuitable because they typically record a single entry per bug regardless of how many users encountered it, thereby destroying the multiplicity data required for the estimator.

Significance and Claims
The paper claims to provide a direct, distribution-free answer to the software release question. Its significance lies in:

• Bridging the Gap: It connects the statistical theory of coverage (Good-Turing) with the practical constraints of software release, specifically addressing the "user-facing" nature of the risk.
• Eliminating Assumptions: It removes the need for operational profiles, assumptions about the total number of defects, or models of the program's internal structure.
• Decision Support: It offers a principled, conservative metric ($s/n$) that allows developers to decide when to release: continue testing until the upper bound of the probability of encountering an unseen defect falls below a tolerated risk threshold.

The authors remain modest regarding the method's limitations, noting that it applies to the software state at the moment of calculation and requires specific types of telemetry data (encounter-level) rather than standard bug tracking logs. They do not claim to solve the problem of estimating the total number of defects, but rather the specific probability of user exposure to the unknown.