正規表現エンジンの内部（バックトラッキングとReDoS）

正規表現エンジンには大きく2系統あります。RE2やGoの標準ライブラリのように有限オートマトンをそのまま走らせる「オートマトン方式」と、JavaScript・Java・Python・PCRE（PHP/Perl）のように後方参照や先読みを実現するため「バックトラッキング方式」を採る系統です。後者は表現力が高い代わりに、ある種のパターンと入力で計算量が爆発します。これがReDoS（Regular expression Denial of Service）の根です。本稿は後者の内部動作を追います。

バックトラッキングという探索

バックトラッキング方式は、正規表現をNFA（非決定性有限オートマトン）とみなし、その経路を深さ優先で試します。分岐（a|b や量指定子の「もう1文字食うか／やめるか」）に出会うたびに、片方を選んで進み、行き止まりに当たったら直前の分岐まで戻って別の選択肢を試す、という探索です。

重要なのは、量指定子 * や + の既定が「貪欲（greedy）」だという点です。a+ はまず取れるだけ a を取り、後続のパターンが一致しなければ1文字ずつ手放して（バックトラックして）後続に明け渡します。この「取りすぎてから戻す」挙動が、探索木のサイズを決めます。

正規表現 a+a に "aaa" を当てる:
1. a+ が "aaa" を全部取る → 続く a に回す文字が無い → 失敗
2. a+ が "aa" まで戻す → 残り "a" を a が一致 → 成功

壊滅的バックトラッキングの仕組み

探索木が入力長に対して指数的に膨らむのが「壊滅的バックトラッキング（catastrophic backtracking）」です。典型は、量指定子がネストした構造です。

危険なパターン例: (a+)+$
入力: "aaaaaaaaaaaaaaaaaaaaaaaa!"

(a+)+ は「a の塊」を「1個以上」繰り返す構造です。n 個の a をいくつのグループにどう区切るかには 2^(n-1) 通りの分割があり、内側の a+ と外側の + がその全分割を試せてしまいます。末尾の $ は、入力末尾が ! なので必ず失敗します。エンジンは「失敗 → 別の区切り方を試す → また失敗」を全分割について繰り返し、入力1文字の増加で試行回数が倍増します。文字数を数個増やすだけで処理が数秒・数分へと跳ね上がります。

ReDoSの発生条件を見分ける

危険なパターンには共通の構造があります。地の文では量指定子をインラインコードで示します。次の3類型を覚えると、コードレビューで検出しやすくなります。

共通項は「同じ入力部分を複数の経路で一致させられる曖昧さ（ambiguity）」です。ある文字を内側の繰り返しが食うか外側が食うかが一意に決まらないと、エンジンはその全組合せを試す権利を持ってしまいます。曖昧さがゼロのパターン（決定的に進めるパターン）は、何文字与えてもバックトラックが発生しません。

回避パターン

最優先は曖昧さの除去です。エンジン任せのフラグではなく、パターンそのものを一意に書き直すのが本筋です。

• ネストを平坦化する。(a+)+ は意味的に a+ と等価なので、外側の繰り返しを外すだけで安全になります。一般に「繰り返しの中の繰り返し」は、内側を1回の一致で表せないか見直します。
• 繰り返しの中身を「重複しない文字クラス」にする。(.*)* のように何でも食う要素を入れ子にしない。.* の代わりに、区切りを否定文字クラスで明示します（例: 引用符の中身は "[^"]*" のように「引用符以外」と限定）。
• 限定一致（lazy, *?/+?）への置換は万能ではありません。最短一致でも後続が外れれば結局バックトラックは起き、曖昧さ自体は消えません。順序が変わるだけだと理解してください。

より強い手段が、バックトラックそのものを禁じる構文です。

スティッキー（y）フラグと探索位置

y（sticky）フラグは、照合の開始位置を lastIndex に固定します。通常の照合はパターンが当たる箇所を探して文字列内を前進（スキャン）しますが、y は「ちょうど lastIndex の位置から始まる一致」だけを認め、当たらなければ即失敗します。

これはReDoS対策そのものではありませんが、字句解析（トークナイザ）のように「位置を1つずつ正確に進めたい」用途で、無駄なスキャンを排し挙動を予測可能にします。g フラグも lastIndex を進めますが、当たらなければ後続位置を探し続けます。y は探さない、という違いです。

const re = /\d+/y;
re.lastIndex = 3;
re.test("abc123");   // true。位置3からちょうど一致
re.lastIndex = 0;
re.test("abc123");   // false。位置0は 'a' で即失敗（スキャンしない）

Unicode（u）フラグと正しい単位

u（Unicode）フラグは、正規表現の一致単位を「UTF-16のコード単位」から「Unicodeの符号位置（コードポイント）」へ変えます。これを付けないと、絵文字など補助面の文字はサロゲートペア（2つの16ビット）として扱われ、. が片割れだけに当たるなど不正確な結果になります。

u を付けると \u{1F600} のような符号位置エスケープや、\p{...} による Unicode プロパティエスケープ（例: 文字種・スクリプトでの一致）が使えるようになり、文字数の数え方も符号位置単位になります。バリデーションで文字数を数える、特定スクリプトだけ許可する、といった要件では u 前提で書くのが正確です。

まとめ

バックトラッキング方式は後方参照などの表現力と引き換えに、曖昧なパターンで最悪計算量が爆発します。ReDoSは「ネスト・分岐重複・隣接する曖昧な繰り返し」が「末尾で必ず失敗する条件」と組んだときに顕在化します。守りは、まずパターンから曖昧さを消すこと、可能なら原子グループ・所有量指定子で構文的にバックトラックを断つこと、そしてユーザー入力にはタイムアウトを併用することです。y は探索位置を固定して挙動を予測可能にし、u は符号位置単位の正しい一致を保証します。

関連として、入力検査の設計は フォームとバリデーション、正規表現がサニタイズ経路で関わる攻撃面は DOM-based XSSのsink/source分類と緩和原理 を、言語機能としての位置づけは JavaScript（ブラウザの動的処理）、エンジン最適化の発想は JavaScriptエンジンの内部（JITとインラインキャッシュ） もあわせてどうぞ。