Vulnerability Abundance: A formal proof of infinite vulnerabilities in code

1. Problem Statement

The paper addresses a foundational debate in cybersecurity: Are software vulnerabilities fundamentally finite or infinite?

• The "Sparse" View: If vulnerabilities are finite and declining, exhaustive patching is a viable security strategy.
• The "Dense" View: If vulnerabilities are effectively inexhaustible, fixing individual bugs is "Sisyphean" (futile), and security must rely on systemic resilience rather than exhaustive patching.
• The Gap: While previous arguments (e.g., by Spring and Illari) relied on computability theory (Rice's Theorem, the Halting Problem) to argue that vulnerabilities should be infinite, there was no constructive proof—no concrete, executable example demonstrating a single program that generates a countably infinite set of distinct vulnerabilities.

2. Methodology

The authors employ a constructive proof combined with formal methods and set theory.

A. The "Vulnerability Factory" (VF)

The core of the methodology is a specific C program (622 lines) named the Vulnerability Factory. It consists of two components:

1. Base Set ($B$): 11 hard-coded functions, each containing a classic vulnerability from a distinct Common Weakness Enumeration (CWE) class (e.g., Stack Buffer Overflow, Format String, Integer Overflow).
2. Generator ($G$): A loop that reads a persistent counter $n \in \mathbb{N}$. For each iteration, it:
   • Generates a new C source file (vuln_module_n.c).
   • Parameterizes five vulnerabilities within that module based on $n$ (e.g., buffer size = $16 + n$, allocation size = $8 + n$).
   • Compiles the module into a distinct shared library.
   • Increments $n$.

B. Formal Verification

• Set Theory: The authors define a vulnerability as a tuple $(c, t, p)$ where $c$ is a component, $t$ is a type, and $p$ is a parameter set. They prove that the set of generated modules creates a set of vulnerabilities $V$ with cardinality $\aleph_0$ (countably infinite).
• CVE Compliance: They verify that each generated module satisfies MITRE's CVE Counting Rules:
  1. Independently Fixable: Patching module $M_7$ does not affect $M_{42}$.
  2. Distinct Components: Each module compiles to a separate shared library.
  3. Distinct Parameters: Exploit payloads differ due to parameterization (e.g., different buffer sizes).
• Turing Machine Characterization: The VF is formalized as a Turing Machine (TM) to demonstrate that vulnerability generation is a computable, decidable process, not just an artifact of C's specific memory model.

C. Addressing Objections

The paper anticipates and refutes counterarguments:

• Objection: "Parametric variation isn't a new root cause."
  • Rebuttal: CVE rules assign IDs based on distinct components. Since each $M_n$ is a separate shared library, they are distinct components.
• Objection: "Physical computers have bounded integers."
  • Rebuttal: The proof operates over mathematical $\mathbb{N}$ (via the TM model), not C's int. Even the bounded C implementation yields $\sim 10^{10}$ vulnerabilities, which is effectively infinite for practical purposes.
• Objection: "Deliberate generation is tautological."
  • Rebuttal: The proof is existential. Once generated, the vulnerabilities exist in compiled binaries regardless of origin.

3. Key Contributions

1. Constructive Proof of Infinity: The paper provides the first rigorous, executable proof that a single program can harbor a countably infinite set of distinct, CVE-assignable vulnerabilities.
2. The Vulnerability Factory Artifact: The VF is proposed as a reusable "test object" for future formal results in vulnerability theory, similar to the Busy Beaver function in computability theory.
3. Concept of Vulnerability Abundance: The authors introduce a new metric analogous to chemical elemental abundance. Just as hydrogen dominates the universe while gold is rare, certain vulnerability classes (e.g., memory corruption in C) dominate the software ecosystem based on language choice and architecture.
4. Distinction between Vulnerabilities and Exploits: The paper rigorously separates the existence of infinite vulnerabilities from the reality of finite exploits.
5. Exploitation Exposure Model: A formula is proposed: $E(v, s) = A(t_v) \times D(s) \times P_{exploit}(v)$, linking vulnerability abundance ($A$), software deployment share ($D$), and exploit probability.

4. Results

• Infinite Set: The set of vulnerabilities $V$ generated by the VF is proven to be countably infinite ($\aleph_0$).
• Robustness: The proof holds even if a finite number of generated instances are deemed invalid; removing a finite set from an infinite set leaves an infinite set.
• Exploitation Rarity: Empirical data confirms that while vulnerabilities are infinite, exploitation is rare. Only ~2.6% to 6% of published CVEs are ever exploited in the wild.
• The "Small-Exploit Principle": Because software deployment is concentrated (monocultures), an attacker only needs a small number of exploits (targeting the top 3-4 software stacks) to saturate the risk landscape, despite the infinite pool of potential vulnerabilities.

5. Significance and Implications

• Shift in Security Strategy: The paper argues that "exhaustive patching" is a flawed strategy because the reservoir of vulnerabilities is infinite. Security must focus on vulnerability abundance (reducing the prevalence of high-risk classes) and deployment diversity (reducing monocultures).
• Language Design: The concept of "nucleosynthesis" suggests that programming languages act as filters. Memory-safe languages (Rust, Go) eliminate specific "elements" (memory corruption) but may allow others (logic errors, injection).
• Economic Alignment: By quantifying vulnerability abundance, organizations can better align incentives. If 70% of C/C++ bugs are memory safety issues, the ROI for migrating to Rust becomes mathematically quantifiable.
• Risk Modeling: Cyber-risk analysis should move from counting individual CVEs to modeling the interaction between vulnerability abundance and software market share. A rare vulnerability in a dominant platform poses a greater systemic risk than a common vulnerability in niche software.

Conclusion

The paper concludes that the set of all software vulnerabilities is necessarily infinite. However, the set of exploits is finite and driven by market dynamics. The authors propose that the future of security lies not in trying to "empty the ocean" of bugs, but in "charting its currents"—understanding the distribution of vulnerability classes and how they interact with software deployment to manage systemic risk. The Vulnerability Factory serves as a foundational proof artifact to support this new theoretical framework.