toml-node: toml.parse()における、多数のテーブル配列ヘッダーによる二乗時間計算量のDoS脆弱性
## 概要
`toml.parse()`は、多数のテーブル配列（`[[name]]`）ヘッダーによって、二乗時間計算量（O(n²)）のDoS（サービス拒否）攻撃を受ける可能性があります。`lib/compiler.js`内の`addTableArray()`関数は、関連性のないまたは異なるエントリを削除せずに、すべての`[[name]]`ヘッダーに対して2つの完全なデータ構造を再スキャンするため、n個のヘッダーを含むドキュメントのコンパイルにはO(n²)の処理時間が必要になります。約321KBの、20,000個の異なる名前を持つ`[[name]]`ブロックを含むドキュメントの解析には、約10.3秒かかります。これは、一見すると通常のTOMLの構造（フラットな設定ブロックと、1つ以上のテーブル配列セクション）であり、意図的に作成された特殊なケースではありません。これは、以前に修正されたスタックオーバーフローDoS攻撃（`GHSA-82x6-q7mm-w9cf`）とは異なるコードパスであり、キーのネストやドット付きキーは一切必要ありません。
## 影響を受けるコンポーネント/バージョン
- パッケージ: `toml` (npm)、リポジトリ `BinaryMuse/toml-node`
- 関数: `lib/compiler.js`内の`addTableArray()`
- 監査対象のコードベースにおいて、コミット`1b2ac40`（2026-07-16）に存在することが確認されました。これは、`v5.0.0`タグ（変更ログのみの変更）の1つ前のコミットであり、つまり`v5.0.0`、最新のリリース版に存在します。すべての以前のリリースに対して網羅的に検証されているわけではありませんが、影響を受ける関数は`v5.0.0`のBigInt/Temporalの変更とは無関係（`CHANGELOG.md`参照）であるため、この欠陥はさらに古いリリースにも存在する可能性があります。
## 詳細
`toml.parse(input, options)` (`index.js:5-9`)は、呼び出し元から提供された文字列を、長さや構造の検証なしに、`parser.parse()`および`compiler.compile()`に渡します。すべての`[[name]]`（テーブル配列）ヘッダーは、`reduce()`関数（`lib/compiler.js:43`）によって、`addTableArray()`関数（`lib/compiler.js:218-245`）にルーティングされます。この関数は、呼び出しごとに2つの完全な線形スキャンを実行します。
```js
assignedPaths.forEach(function(p) {
if (isSameOrSubPath(p, quotedPath)) assignedPaths.delete(p);
});
valueAssignments.forEach(function(p) {
if (isSameOrSubPath(p, quotedPath)) valueAssignments.delete(p);
});
```
(`lib/compiler.js:228-233`)
`assignedPaths` と `valueAssignments` は、ドキュメント全体で割り当てられた最上位のキー/テーブル/配列のパスごとに1つのエントリを累積します。各スキャンでは、*現在再開された* パスに一致するエントリのみが `isSameOrSubPath()` を使用して削除されます ( `lib/compiler.js:319-321`: `path === prefix || path.indexOf(prefix + ".") === 0`)。それ以外、つまり、関連性のない最上位のキー、または単に *異なる* 配列のテーブル名などは、削除されることはなく、以降のすべての `[[name]]` ヘッダーで完全に再スキャンされます。`Set.prototype.forEach` には早期終了機能がないため、これは常に呼び出しごとに現在の Set のサイズに比例する O(current Set size) の処理となり、n 個のヘッダーに対しては合計で O(n²) の処理時間となります。
## 実証
最も再現性が高いケースでは、関連性のないキーは一切不要です。N 個の配列のテーブルヘッダーがあり、それぞれが N 個の *異なる* 名前を持つ必要があります。なぜなら、名前が重複しない場合は、何も削除されないからです。
```js
const toml = require('toml');
function distinctArrayHeaders(n) {
let out = '';
for (let i = 0; i < n; i++) out += `[[a${i}]]\nv = 1\n`;
return out;
}
// 入力サイズは約 321 KB、処理時間は約 10.3 秒
toml.parse(distinctArrayHeaders(20000));
```
測定された処理時間 (Node.js、このリポジトリに対する直接実行):
| バリアント | n | 入力サイズ | 処理時間 |
|---|---|---|---|
| N 個の異なる名前を持つ `[[name]]` ヘッダー、関連性のないキーなし | 20,000 | 321 KB | 10.3 秒 |
| 同じ N 個で、すべてのヘッダーの名前が同じ (自己最適化、コントロール) | 20,000 | 240 KB | 78 ミリ秒 |
| M 個の関連性のない最上位キー + N 個の名前が同じ `[[name]]` ヘッダー | M=N=32,000 | 906 KB | 42.3 秒 |
同じ N で、入力サイズが比較可能であるにもかかわらず、異なる名前と同じ名前のケースで約 130 倍の処理時間差があることから、問題の原因が特定できます。このバグは、削除されないエントリによって Set が無限に増加することによって引き起こされ、文字列の長さやその他の要因によるものではありません。プロダクト則のチェック (混合バリアントで M と N を独立して変化させる) により、真に O(M·N) の複雑性であることがさらに確認されました。
## 影響
Node.jsはシングルスレッドであり、この同期的な、数秒から数十秒かかるコンパイル処理は、プロセスイベントループ全体をブロックします。これは、標準的なNode.jsの動作です。トリガーとなるドキュメントの形式は、トップレベルの構成キーと、1つ以上のテーブルの配列セクション（例：`[db]`の設定ブロックと`[[servers]]`のリスト）で構成されており、これは特筆すべきものではなく、一般的なTOML形式です。認証や特別なアクセス権は必要なく、このライブラリを使用するアプリケーションが1つのTOML文字列を解析できる能力のみが必要です。
## 推奨される対策
すべての`[[name]]`ヘッダーに対して、`assignedPaths`/`valueAssignments`セット全体をスキャンすることを避けてください。エントリーを、トップレベルのパスセグメントでインデックス化します（例：最初のキーコンポーネントでキー付けられた`Map<string, Set<string>>`）。これにより、`addTableArray()`関数は、再オープンされるパスに関連するバケットのみをスキャンし、スキャン時間は、そのバケットのサイズに比例し、ドキュメント全体のパスの総数には比例しません。
```js
var assignedByRoot = new Map(); // rootセグメント -> Set<フルパス>
function addTableArray(node) {
var path = node.value;
var root = path[0];
var bucket = assignedByRoot.get(root) || new Set();
bucket.forEach(function(p) {
if (isSameOrSubPath(p, quotedPath)) bucket.delete(p);
});
// ...addTableArray関数の残りの部分は変更せず、グローバルなassignedPaths/valueAssignmentsセットではなく、各ルートのバケットを読み書きします。
}
```
同様に、入力サイズまたはテーブル数の制限も、多層防御として有効です。
## 貢献者
SecDim Security Researchによって発見され、報告されました。
secdim.com | @secdim | security@secdim.com
影響を受けるパッケージ：
- npm (JavaScript) toml: 影響を受けるバージョンは5.0.0以下、5.0.1で修正済み。