💻 computer science

Vulnerability Abundance: A formal proof of infinite vulnerabilities in code

この論文は、単一の C プログラムが無限に多くの脆弱性を許容することを形式的に証明し、脆弱性の無限性と実際のエクスプロイトの有限性を区別する「脆弱性豊富さ」という概念を提唱することで、ソフトウェアの脆弱性理論とサイバーリスク分析に新たな枠組みを提供しています。

原著者： Eireann Leverett, Jeroen van der Ham-de Vos

公開日 2026-04-10

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Eireann Leverett, Jeroen van der Ham-de Vos

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

🏭 1. 「欠陥工場」の発明

著者たちは、**「欠陥工場（Vulnerability Factory）」**という名前の、たった 622 行の小さな C プログラムを作りました。

どんな機械？
この機械は、ボタンを押すたびに新しい「ソフトウェア部品」を 1 つずつ作り出します。
何がすごい？
1 回ボタンを押すたびに、その部品には**「5 つの新しいバグ」**が必ず含まれています。
- 1 回押す → 5 つのバグ
- 100 回押す → 500 個のバグ
- 100 万回押す → 500 万個のバグ
- 無限に押し続ける → 無限のバグ

この機械は、バグを「見つける」のではなく、**「意図的に作り出す」**ように設計されています。まるで、無限に続くレゴブロックの塔を、1 個ずつ積み上げていくようなものです。

📜 2. 「無限」の証明：なぜこれが重要なのか？

これまで、セキュリティの専門家たちは「バグは有限（数え切れるほどあるが、いつかはなくなる）」のか、「無限（永遠に減らない）」のかで議論していました。

もしバグが有限なら： 全部見つけて直せば、世界は安全になるはず。
もしバグが無限なら： いくら直しても、新しいバグは次から次へと湧いてくる。

この論文は、**「バグは無限に存在しうる」**ことを、この「欠陥工場」を使って証明しました。
「1 つのプログラムから無限のバグが生まれるなら、世の中のすべてのソフトウェアを合わせれば、バグの数は間違いなく無限だ」という結論です。

例え話：
砂浜の砂粒が無限にあるかどうかは分かりませんが、「砂粒を作る機械」が無限に砂粒を作れることが証明されれば、「砂粒は無限に存在しうる」と言えるのと同じです。

🧪 3. 「化学元素」に例えた「バグの分布」

論文では、**「バグの豊富さ（Vulnerability Abundance）」という新しい概念を提案しています。これは化学の「元素の存在比」**に似ています。

化学の世界：
宇宙には水素が最も多く、酸素は地殻に多いなど、元素の「分布」が決まっています。
ソフトウェアの世界：
使う「プログラミング言語」によって、発生しやすいバグの種類が決まります。
- C 言語（古い言語）： 「メモリ破損」というバグが大量に発生する（水素のような存在）。
- Rust や Java（新しい言語）： メモリ破損は減るが、「論理ミス」や「入力ミス」のバグが主役になる（酸素や炭素のような存在）。

つまり、**「どの言語をどれだけ使っているか」**によって、世の中に溢れているバグの種類と割合（分布）が変わるのです。

⚠️ 4. 「無限のバグ」vs「限られた攻撃」

ここが最も重要なポイントです。
「バグが無限に存在する」＝「ハッカーが無限に攻撃できる」ではありません。

バグ（欠陥）： 無限に存在する。
エクスプロイト（攻撃コード）： 限られている。

例え話：

バグは「海に浮かぶ無数の小さな岩」です。
攻撃は「その岩を船で突っつくための道具」です。

海には無数の岩（バグ）がありますが、船（ハッカー）が実際に突っつくのは、**「船が停泊しやすい大きな岩（人気なソフトウェア）」**だけです。
たとえ岩が無限にあっても、船が停泊できる場所（市場シェア）が限られていれば、攻撃されるリスクは限定的になります。

重要な教訓：
「バグを全部見つけて直そう」としても、無限なので不可能です。
重要なのは、**「どのバグが、どのくらい普及しているソフトウェアにあり、攻撃されやすいか」**を計算することです。

🎯 5. 私たちにとっての結論

この論文が私たちに教えてくれることは以下の 3 点です。

完璧な安全は不可能： バグは無限に存在しうるため、「バグをゼロにする」という目標自体が非現実的です。
戦略を変える必要がある： 「バグを数える」のではなく、「バグの分布（どの言語で、どんなバグが多いか）」を理解し、リスクの高い部分に集中して対策を講じるべきです。
市場シェアが鍵： 世界中で使われているソフトウェア（Windows や Android など）に 1 つバグがあれば、それは無数の攻撃を招きます。逆に、誰も使っていないソフトのバグは、どれだけ多くてもリスクは低いです。

まとめ

この論文は、**「バグは無限の海のようなもの」だと教えてくれます。
海をすべて干上がらせることはできませんが、「潮の流れ（バグの分布）」と「船の航路（普及しているソフト）」**を理解すれば、どこに注意すべきかが見えてきます。

これからは、バグを「数える」ことよりも、**「バグの生態系」**を理解して、賢くリスクを管理していく時代が来るかもしれません。

論文要約：Vulnerability Abundance: A formal proof of infinite vulnerabilities in code

著者: E. Leverett (Concinnity Risks Ltd.), J. van der Ham-de Vos (University of Twente)
発表: New Security Paradigms Workshop (NSPW '26)

1. 概要と問題提起

本論文は、ソフトウェアの脆弱性が本質的に「有限」か「無限」かという長年の議論に対し、**構成的証明（constructive proof）**によって「無限」であることを示した画期的な研究である。
従来の議論では、脆弱性が「希薄（sparse）」であればパッチングは有効だが、「高密度（dense）」であれば個別の修正はセキュリティ向上にほとんど寄与しないという対立があった。本論文は、単一の C プログラム（「Vulnerability Factory」）が、**可算無限（countably infinite）**の個々の CVE（Common Vulnerabilities and Exposures）として割り当て可能な脆弱性を生成し得ることを数学的に証明し、ソフトウェア全体における脆弱性の総数が無限であることを導き出した。

2. 手法とアプローチ

2.1 Vulnerability Factory（脆弱性ファクトリー）の構築

著者らは、622 行の C プログラム「Vulnerability Factory」を実装し、以下の 2 つのコンポーネントで構成される。

Base Set B: 11 種類の異なる CWE（Common Weakness Enumeration）クラスに分類される既知の脆弱性（スタックバッファオーバーフロー、ヒープオーバーフロー、フォーマット文字列など）を含む 11 個の関数。
Generator G: 永続的なカウンター $n$ $n$ を読み取り、 $n$ $n$ をパラメータとして 5 つの脆弱性を含む新しい C ソースファイル（vuln_module_n.c）を生成する。
- 生成されるモジュールは、バッファサイズ（ $16+n$ ）、オーバーフロー閾値（ $INT\_MAX - n$ ）、割り当てサイズ（ $8+n$ ）などが $n$ によって変化するため、各モジュールは独立したコンポーネントとして扱われる。
- 生成されたモジュールは共有ライブラリとしてコンパイルされ、カウンター $n$ がインクリメントされる。

2.2 形式的証明とモデルチェッキング

集合論的アプローチ: 生成される脆弱性の集合 $V$ が可算無限集合（ $\aleph_0$ ）であることを、MITRE の CVE 割り当てルール（独立して修正可能、識別可能なコンポーネント、独立して発見可能）に照らして証明した。
チューリング機械の定式化: Vulnerability Factory をチューリング機械として再定義し、脆弱性の生成が計算可能（computable）であり、任意のチューリング完全なシステムで実装可能であることを示した。
モデルチェッキング: 脆弱性の数が有限の上限 $C$ に収束するという仮定に対して、モデルチェッカーが反例（カウンター例）を生成することを示し、脆弱性の生成が無限に続くことを補強した。

2.3 脆弱性豊富度（Vulnerability Abundance）の概念

化学における「元素の存在度（elemental abundance）」に倣い、ソフトウェア生態系における脆弱性クラスの比例的分布を定量化する概念「Vulnerability Abundance」を導入した。

プログラミング言語の選択（メモリ安全性の有無など）が、生成される脆弱性の種類（スペクトル）を決定する要因である。
言語の普及率やアプリケーションドメインの変化に伴い、この分布は時間とともに変化する。

3. 主要な貢献

無限脆弱性の構成的証明: 単一のプログラムが可算無限の CVE 割り当て可能な脆弱性を生成し得ることを示した具体的かつ実行可能な例（Vulnerability Factory）を提供した。
形式的証明アーティファクトの提案: Vulnerability Factory を、将来の脆弱性理論における「テスト対象（test object）」として再利用可能な証明アーティファクトとして位置づけた。
脆弱性豊富度の概念の導入: 脆弱性の「数」だけでなく、その「分布」と「種類」の比率を分析する新しい枠組みを提案し、セキュリティ投資の優先順位付けやリスク分析への応用を提唱した。
脆弱性とエクスプロイトの明確な区別: 脆弱性が無限であっても、実際に利用されるエクスプロイトは限定的であることを示した。エクスプロイトの頻度は、脆弱性の豊富度だけでなく、対象ソフトウェアの市場占有率（Market Share）に強く依存することを論じた。
密（dense）と疎（sparse）の議論への決着: 理論的な複雑性論に留まらず、具体的なプログラム例によって「脆弱性は無限に存在する（密度が高い）」ことを実証し、この議論に決着をつけた。

4. 結果と知見

無限性の証明: 生成された各モジュールは独立したコンポーネントであり、パラメータが異なるため、それぞれが独立した CVE として扱われる。したがって、生成される脆弱性の集合は無限である。
CVE 割り当てルールの適合性: MITRE のルール（独立して修正可能、独立して発見可能）を満たすため、無限の脆弱性が理論的に個別の CVE として登録可能である。
エクスプロイトの現実性: 実証データ（Kenna Security や Cyentia Institute の調査）によると、公開された CVE のうち実際に悪用されるのは 2.6%〜6% 程度に過ぎない。
- 市場占有率の乗数効果: 限られた数のエクスプロイトでも、支配的なソフトウェア（市場占有率が高いもの）を標的にすれば、広範な被害をもたらすことができる（「小規模エクスプロイトの原理」）。
実用的な限界: 物理的なマシン（C の int 型）ではカウンターに上限があるが、理論的なチューリング機械モデルでは無限であり、実用上は「事実上無限（effectively inexhaustible）」な規模（約 100 億以上）の脆弱性を生成できる。

5. 意義と将来への示唆

セキュリティ戦略の転換: 「すべての脆弱性を発見・修正する」という完全なパッチング戦略は非現実的（シシフォスの苦役）であることを示唆し、**「どの種類の脆弱性が豊富に存在し、どこにリスクが集中しているか」**を把握する「脆弱性豊富度」に基づくリスク管理の重要性を強調した。
経済的インセンティブ: 脆弱性の分布を定量化することで、どのプログラミング言語への移行（例：C/C++ から Rust へ）が最も効果的かを定量的に評価できる。
形式的検証ツールのベンチマーク: 無限に生成される構造的に類似したテストケースは、静的解析ツールやモデルチェッカーのスケーラビリティを評価するための理想的なベンチマークとなる。
理論的基盤: 脆弱性理論における「ハルティング問題」や「Busy Beaver」のような基礎的な証明対象として、Vulnerability Factory が機能する可能性を示した。

結論:
ソフトウェアの脆弱性は無限であり、それをすべて排除することは不可能である。重要なのは、無限の海（脆弱性）をすべて空にすることではなく、その海流（分布と市場占有率）を理解し、どの潮流が最も危険かを把握することである。本論文は、この新しい視点（Vulnerability Abundance）を提供し、将来のサイバーリスク分析と予防策の基礎となる。