Vulnerability Abundance: A formal proof of infinite vulnerabilities in code

Probleemstelling

De kernvraag die dit artikel adresseert, is of softwarekwetsbaarheden fundamenteel eindig of oneindig zijn. Dit is geen louter academische discussie, maar heeft directe gevolgen voor beveiligingsstrategieën:

• Als kwetsbaarheden schaars (eindig) zijn, betekent het vinden en patchen van elke kwetsbaarheid een significante vermindering van het risico.
• Als kwetsbaarheden dicht (oneindig) zijn, is het patchen van individuele bugs essentieel irrelevant voor de algehele veiligheid, omdat er altijd nieuwe zullen ontstaan.

Bestaande literatuur (zoals Geer et al. en Spring) heeft theoretisch geargumenteerd dat kwetsbaarheden oneindig kunnen zijn, maar er ontbrak een constructief, uitvoerbaar bewijs dat dit daadwerkelijk demonstreert.

Methodologie

De auteurs hanteren een constructieve benadering die wiskundige bewijstechnieken combineert met praktische software-engineering:

1. De "Vulnerability Factory" (Kwetsbaarheidsfabriek):

   • De auteurs hebben een specifiek C-programma ontwikkeld (622 regels code) genaamd de Vulnerability Factory.
   • Dit programma bestaat uit twee componenten:
     • Base Set (B): Een verzameling van 11 basisfuncties, elk met één klassieke kwetsbaarheid uit een verschillende CWE-klasse (bijv. buffer overflow, format string, use-after-free).
     • Generator (G): Een module die bij elke uitvoering een persistent teller $n$ leest, een nieuw C-bronbestand (vuln_module_n.c) genereert met 5 geparametriseerde kwetsbaarheden, dit compileert tot een gedeelde bibliotheek, en de teller verhoogt.
   • De parametrisatie (bijv. buffergrootte $16+n$, drempelwaarden) zorgt ervoor dat elke gegenereerde module uniek is en een unieke exploit vereist.

2. Formalisatie:

   • Zettheorie: De kwetsbaarheden worden gedefinieerd als een verzameling $V$. De auteurs bewijzen dat deze verzameling aftelbaar oneindig is ($\aleph_0$) door aan te tonen dat er een bijectie bestaat tussen de natuurlijke getallen en de gegenereerde kwetsbaarheden.
   • CVE-toewijzing: Ze toetsen hun bewijs aan de regels van de MITRE CVE-Numbering Authority. Omdat elke gegenereerde module een apart compileerbaar component is met een onafhankelijk oplosbare kwetsbaarheid, voldoet elke instantie aan de criteria voor een uniek CVE-ID.
   • Turing-machinetheorie: Het concept wordt geformaliseerd als een Turing-machine. Dit plaatst het resultaat binnen de klassieke berekenbaarheidstheorie en toont aan dat het genereren van kwetsbaarheden een deciderbaar, structureel transparant proces is.
   • Model-checking: Een model-checking analyse wordt gesketst om de onbeperkte generatie van kwetsbaarheden te verifiëren.

Belangrijkste Bijdragen

Het artikel levert vijf significante bijdragen:

1. Constructief Bewijs: Het leveren van een concreet, uitvoerbaar programma (de Vulnerability Factory) dat bewijst dat één enkel programma een aftelbaar oneindige verzameling van distincte, CVE-toewijsbare kwetsbaarheden kan genereren.
2. Formalisatie als Bewijsartefact: Het formaliseren van de fabriek als een Turing-machine, waardoor het dient als een herbruikbaar "testobject" voor toekomstig formeel onderzoek in kwetsbaarheidstheorie.
3. Concept van "Vulnerability Abundance" (Kwetsbaarheidsovervloed): De introductie van een nieuw kader, geïllustreerd met een analogie uit de scheikunde (elementaire abundantie). Dit beschrijft de proportionele verdeling van kwetsbaarheidsklassen over het software-ecosysteem, afhankelijk van de gebruikte programmeertalen en architectuur.
4. Distinction tussen Kwetsbaarheden en Exploits: Een scherpe scheiding tussen het oneindige aantal kwetsbaarheden en het veel kleinere aantal exploits. Empirische data toont aan dat minder dan 6% van de gepubliceerde CVE's ooit in het wild wordt uitgebuit.
5. Praktische Toepassing: Het argumenteren dat het meten van kwetsbaarheidsovervloed en de interactie met software-marktaandeel waardevol is voor voorspellende cyber-risicoanalyse en het prioriteren van preventie.

Resultaten

• Oneindigheid bewezen: De verzameling $V$ van alle kwetsbaarheden die door de Vulnerability Factory kunnen worden gegenereerd, is aftelbaar oneindig. Omdat deze verzameling een deelverzameling is van alle softwarekwetsbaarheden, is de totale set van softwarekwetsbaarheden per definitie oneindig.
• Robuustheid: Het bewijs is robuust tegen bezwaren. Zelfs als een reviewer zou beweren dat bepaalde patronen (bijv. buffer overflows met verschillende maten) niet als distincte CVE's tellen, blijft de verzameling oneindig zolang er maar één template overblijft die voldoet aan de distinctheidscriteria.
• Turing-Completie: Het bewijs geldt voor elk Turing-compleet systeem. Hoewel de specifieke CWE-classes afhankelijk zijn van de taal (bijv. geheugenkwaliteiten in C vs. logica-fouten in Rust), blijft het vermogen om oneindig veel kwetsbaarheden te genereren een structurele eigenschap van berekening zelf.
• Exploitatiekloof: Hoewel kwetsbaarheden oneindig zijn, is de "exploitatiekloof" groot. De impact van een kwetsbaarheid wordt niet bepaald door het aantal kwetsbaarheden, maar door het marktaandeel van de aangetaste software. Een enkele exploit tegen een dominant platform (zoals Windows of een populaire webserver) heeft een veel grotere impact dan duizenden exploits tegen niche-software.

Betekenis en Conclusie

De paper concludeert dat de zoektocht naar "alle" kwetsbaarheden een Sisyphus-taak is, omdat de bron oneindig is. In plaats van te proberen de oceaan leeg te maken, moeten beveiligingsprofessionals de stromingen in kaart brengen:

• Verschuiving in focus: Van het tellen van individuele bugs naar het begrijpen van de abundantie (hoe vaak komen bepaalde types voor) en de dichtheid in specifieke domeinen.
• Economische implicaties: Het inzicht dat kwetsbaarheden oneindig zijn, versterkt de economische theorie dat beveiliging vaak een probleem van verkeerde prikkels is. Als kwetsbaarheden inherent oneindig zijn, moet de focus liggen op het elimineren van hele klassen van kwetsbaarheden (bijv. door over te stappen naar geheugenveilige talen zoals Rust) in plaats van het patchen van individuele bugs.
• Risicomanagement: De "kleine-exploit-principe" stelt dat een klein aantal exploits voldoende is om een groot deel van de machinepopulatie te raken, vanwege de concentratie van software-marktaandeel.

Kortom, dit artikel levert een fundamenteel bewijs dat de wereld van softwarekwetsbaarheden oneindig is, en introduceert een nieuw paradigma om deze complexiteit te analyseren en te managen door middel van het concept van kwetsbaarheidsovervloed.