正規表現（Regex）の内部構造と破滅的バックトラッキング（ReDoS）防御

JavaScript、Python、Java、Ruby、PHPなど大半の主要プログラミング言語は、非決定性有限オートマトン（NFA）ベースの正規表現エンジンを内蔵しています。文字列の長さに応じて常に線形時間O(n)でマッチングが完了するDFAエンジン（grepやGoのregexp、RE2など）と異なり、NFAエンジンはキャプチャグループ、後方参照、先読み・後読みといった極めて表現力豊かな機能を提供できます。

しかし、NFAエンジンはパターン候補を推測しながら進み、途中で失敗すると直前の分岐点まで巻き戻して別の候補を探索するバックトラッキング（Backtracking）方式で動作します。非効率な正規表現パターンを記述してしまうと、この巻き戻し試行回数が入力長に対して指数関数的に爆発するリスクを孕んでいます。

Lookaround（周辺探索）は、文字列内の文字を実際に消費（マッチ結果に含める）することなく、特定の位置が前後の条件を満たしているかだけを検査する幅ゼロのアサーション（Zero-width assertion）です：

• 肯定先読み (?=...): 直後に指定のパターンが続く位置にマッチします。
  • 例: \d+(?=px) は、直後にpxが続く数値のみにマッチします（"120px"から"120"だけを抽出）。
• 否定先読み (?!...): 直後に指定のパターンが続かない位置にマッチします。
  • 例: password(?!\.bak) は、末尾に.bakが付いていないpasswordという文字列のみにマッチします。
• 肯定後読み (?<=...): 直前に指定のパターンが存在する位置にマッチします。
  • 例: (?<=\$)\d+ は、ドル記号の直後にある数値のみにマッチします（"$99"から"99"を抽出）。
• 否定後読み (?<!...): 直前に指定のパターンが存在しない位置にマッチします。

正規表現によるサービス運用妨害攻撃（ReDoS: Regular Expression Denial of Service）は、量指定子（Quantifier）が多重に入れ子になった曖昧なパターンに対し、最後の1文字だけが一致しない巧妙な文字列が入力された際に発生します。NFAエンジンが天文学的な組み合わせを総当たりでバックトラッキングし続けるため、Node.jsなどのシングルスレッドイベントループが完全にブロックされ、CPU使用率が100%に張り付いてサーバー全体が応答停止に陥ります。

// ❌ 危険なReDoS脆弱性パターン（量指定子の入れ子: (a+)+）
const vulnerableRegex = /^(a+)+$/;

// 失敗する文字列を与えると、天文学的なバックトラッキングが発生してフリーズ
// vulnerableRegex.test("aaaaaaaaaaaaaaaaaaaaaaaaaaaaab"); // 数秒〜数分間CPUを占有!

// ✅ 安全にリファクタリングされた等価パターン
const safeRegex = /^a+$/;
console.log(safeRegex.test("aaaaaaaaaaaaaaaaaaaaaaaaaaaaab")); // 線形時間（数マイクロ秒）で即座にfalse

• UUID（v4形式）の検証: ^[0-9a-fA-F]{8}-[0-9a-fA-F]{4}-4[0-9a-fA-F]{3}-[89abAB][0-9a-fA-F]{3}-[0-9a-fA-F]{12}$
• IPv4アドレスの厳格な検証: ^(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)$
• ISO 8601日時形式の検証: ^\d{4}-\d{2}-\d{2}T\d{2}:\d{2}:\d{2}(?:\.\d+)?(?:Z|[+-]\d{2}:\d{2})$
• DevUtilsのリアルタイムRegex Testerを使えば、ブラウザ上で安全にパターンを試行錯誤し、マッチング挙動を視覚的に検証できます。

ユーザー入力文字列を正規表現で処理する際、サーバーの計算量が爆発するのを防ぐための実務手法です：

1. 実行タイムアウト（Timeout）の強制: V8正規表現エンジンはJavaScriptのメインスレッド上で同期的に実行されます。悪意ある文字列が入力されるとNode.jsのイベントループ全体がブロックされます。信頼できない正規表現はWorker Threadsで分離して実行するか、実行制限時間を設けてください。
2. 原子的グループ（Atomic Groups）と絶対量指定子: PCRE系エンジン（Java、PHP、Python regex）では、絶対量指定子（a++）や原子的グループ（(?>a+)）を使用することで、一度マッチした部分へのバックトラッキングを根絶できます。
3. 実務の複合パターン - セマンティックバージョニング（SemVer 2.0）: 公式のSemVer正規表現は、非キャプチャグループ(?:...)と任意のプレリリース/ビルドメタデータをバックトラッキングの危険なく安全に解析する好例です。

// 公式RFC規格に準拠したSemVer 2.0.0正規表現
const semverRegex = /^(0|[1-9]\d*)\.(0|[1-9]\d*)\.(0|[1-9]\d*)(?:-((?:0|[1-9]\d*|\d*[a-zA-Z-][0-9a-zA-Z-]*)(?:\.(?:0|[1-9]\d*|\d*[a-zA-Z-][0-9a-zA-Z-]*))*))?(?:\+([0-9a-zA-Z-]+(?:\.[0-9a-zA-Z-]+)*))?$/;

console.log(semverRegex.test("2.1.0-alpha.1+build.20261003")); // true
console.log(semverRegex.test("v2.1.0")); // false (厳格なSemVerでは先頭の'v'は不許可)