正規表現のReDoS(破滅的バックトラック)を防ぐ

(a+)+$ のような正規表現は、たった30文字の入力で数秒〜数分 CPU を占有します。 これを突く攻撃が ReDoS(Regular expression Denial of Service)。2016年の Stack Overflow、 2019年の Cloudflare の大規模障害も、原因はサービス内の正規表現のバックトラック爆発でした。 本記事では「なぜ固まるのか」を分割数で説明し、脆弱パターンの見分け方・検出ツール・安全な書き換え・Node.js での防御策まで整理します。

ReDoS exploits catastrophic backtracking: a crafted input makes patterns like (a+)+$ take exponential time. This guide explains the mechanics, how to detect vulnerable patterns with recheck, and how to defend Node.js apps with RE2, worker timeouts, and input length limits.

TL;DR

• 危険なのはネスト量化子 (a+)+ と重複する選択肢 (a|aa)+。マッチ失敗時に分割の全組み合わせ(最大 2^n 通り)を試す
• 攻撃文字列の型は「繰り返し部分に長くマッチする文字列 + 必ず失敗する末尾1文字」
• 検出は recheck(ESLint プラグインあり)が確実。攻撃文字列まで提示してくれる
• 書き換えの原則: ネストを外す・選択肢の先頭が重ならないようにする・.replace(/\s+$/, "") は trimEnd() に
• ユーザー入力には正規表現の前に長さ制限。Node.js で信頼できない入力を扱うなら re2 パッケージ(線形時間)か Worker + タイムアウト
• JavaScript の RegExp 自体にタイムアウト機能はない

1. なぜ固まるのか — 計算量爆発の仕組み / How catastrophic backtracking works

JavaScript・Python・Java などの正規表現エンジンはバックトラック方式です。 マッチに失敗すると一つ前の選択点に戻り、別の取り方を試します。 ここで /^(a+)+$/ に "aaaa...a!" を与えると何が起きるか。 末尾の ! のせいで必ず失敗しますが、エンジンは「内側の a+ が何文字ずつ取るか」の 組み合わせを全て試してからでないと失敗を確定できません。a が n 文字なら分割方法は約 2^(n-1) 通り。 n=30 で約5億通りです。

// 脆弱: ネストした量化子 (nested quantifier)
const re = /^(a+)+$/;

// 攻撃文字列: 繰り返しにマッチする "a" の列 + 必ず失敗する末尾 1 文字
const attack = "a".repeat(30) + "!";

console.time("redos");
re.test(attack);   // 30 文字で数秒以上。1 文字増えるごとに所要時間は約 2 倍
console.timeEnd("redos");

重要なのは、マッチに成功する入力では一瞬で終わること。"aaaa" なら最初の試行で成功するため、 通常のテストでは気づけません。実害が出るのは攻撃者(または偶然の入力)が「ほぼマッチするが最後で失敗する」文字列を送ったときです。 指数型でなくても、Stack Overflow を止めた /\s+$/(末尾空白のトリム)のように、 空白2万文字を含む投稿で O(n²) になる「多項式型」もあります。Cloudflare の障害は WAF ルール内の .*(?:.*=.*) が原因でした。

Backtracking engines retry every way the quantifiers could split the input. With (a+)+$and 30 a's followed by "!", that is roughly 2^29 attempts before failing. Matching inputs return instantly, which is why tests rarely catch it.

2. 脆弱なパターンの見分け方と検出ツール / Spotting vulnerable patterns

目視チェックの基準は「同じ文字列を複数の経路で消費できるか」です。代表的な型は次の4つ。

確実なのは静的解析です。recheck(npm)は脆弱性の有無に加えて攻撃文字列そのものを生成して報告します。 ESLint に組み込むなら eslint-plugin-redos(内部で recheck を使用)、Python 製の regexploit も実績があります。 老舗の safe-regex はスターハイト(量化子のネスト深さ)だけを見る簡易判定で、誤検出・見逃しがある点に注意してください。

A pattern is suspect when the same substring can be consumed in multiple ways. Use recheck (also available as eslint-plugin-redos) or regexploit for static analysis — both generate the actual attack string. safe-regex only checks star height and has false positives.

3. 安全な書き換えと入力長制限 / Safe rewrites & input limits

書き換えの原則は「1つの文字列の消費方法を1通りにする」。ネストを外し、選択肢や区切りの曖昧さを消します。

// NG: (a+)+ は分割方法が指数的
/^(a+)+$/          // → /^a+$/  意味は同じ。ネストを外す

// NG: \s? が「空白を取る/取らない」の曖昧さを生む
/^(\w+\s?)*$/      // → /^\w+(\s\w+)*$/  区切りを必須にして一意化

// NG: アンカーなしの末尾トリムは O(n^2)
str.replace(/\s+$/, "");   // → str.trimEnd() を使う(正規表現不要)

JavaScript には Java や .NET にある独占的量化子(a*+)やアトミックグループ((?>...))が ないため、「バックトラックを禁止する」記法では守れません。だからこそ正規表現に渡す前の長さ制限が最後の砦になります。 バックトラックの試行回数は入力長に対して爆発するので、入力を短く保てば被害は限定されます。

function safeTest(re, input, maxLen = 256) {
  if (typeof input !== "string" || input.length > maxLen) return false;
  return re.test(input);   // 長さを制限してから実行
}

Rewrite so each input has exactly one parse: unnest quantifiers, make separators mandatory, replace regex trimming with trimEnd(). JavaScript has no possessive quantifiers or atomic groups, so always cap input length before matching untrusted data.

4. Node.js での防御 — RE2 とタイムアウト / Defenses in Node.js

信頼できない入力(ユーザー投稿・外部 API のレスポンスなど)を正規表現にかけるサーバーでは、 パターンの注意だけでなくランタイム側の防御を入れます。第一候補は Google の RE2 エンジンを使う re2 パッケージ。オートマトン方式で入力長に対して線形時間が保証され、原理的に ReDoS が起きません。

// npm install re2
const RE2 = require("re2");

// RE2 はバックトラックしない (線形時間保証)
const re = new RE2(/^(a+)+$/);
re.test("a".repeat(100000) + "!");   // 巨大入力でも一瞬で false

// 制約: 後方参照 (\1) と lookahead/lookbehind は未対応。
// 使用していると new RE2() が例外を投げるので移行時に検出できる

後方参照や先読みが必要で RE2 に移行できないパターンは、worker_threads で実行して タイムアウトで打ち切ります。RegExp の実行は同期処理でメインスレッドからは中断できない (.NET の MatchTimeout に相当する API がない)ため、殺せる別スレッドに隔離するのが唯一の打ち切り手段です。

const { Worker } = require("node:worker_threads");

function testWithTimeout(pattern, input, ms = 100) {
  return new Promise((resolve, reject) => {
    const worker = new Worker(
      'const { parentPort, workerData } = require("node:worker_threads");' +
      'parentPort.postMessage(new RegExp(workerData.p).test(workerData.s));',
      { eval: true, workerData: { p: pattern, s: input } }
    );
    const timer = setTimeout(() => {
      worker.terminate();                      // 固まった正規表現ごと強制終了
      reject(new Error("regex timeout"));
    }, ms);
    worker.on("message", (r) => { clearTimeout(timer); resolve(r); });
    worker.on("error", (e) => { clearTimeout(timer); reject(e); });
  });
}

For untrusted input use the re2 package — RE2 guarantees linear time but rejects backreferences and lookarounds at construction. Otherwise isolate the regex in a worker thread and terminate() it on timeout; a synchronous RegExp call cannot be interrupted.

English summary

ReDoS (regular expression denial of service) abuses catastrophic backtracking. Engines like V8 try every way quantifiers could split the input before declaring failure, so /^(a+)+$/against thirty a's plus "!" explores about 2^29 paths — and each extra character doubles the work. The dangerous shapes are nested quantifiers ((a+)+, (\d+)*), overlapping alternations ((a|aa)+), and unanchored trims like /\s+$/, which is quadratic and took Stack Overflow down in 2016; Cloudflare's 2019 outage came from .*(?:.*=.*) in a WAF rule. Detect issues with recheck or regexploit, which generate concrete attack strings. Fix patterns by making the parse unambiguous, cap input length before matching, and in Node.js either switch to the linear-time re2 package or run the regex in a worker thread you can terminate, because JavaScript offers no regex timeout.

まとめ

• ReDoS は「ほぼマッチして最後に失敗する」入力でバックトラックを爆発させる攻撃。成功ケースのテストでは見つからない
• ネスト量化子と重複する選択肢を避け、消費経路を1通りに書き換える
• CI に recheck / eslint-plugin-redos を入れて機械的に検出する
• ユーザー入力は長さ制限 → それでも残るリスクは re2 か Worker タイムアウトで遮断する

関連ツール / Related tools

• Regex Tester
• Diff Checker(書き換え前後のパターン比較に)
• JSON Schema Validator(入力検証の代替手段)

関連ガイド / Related guides

• 正規表現の実用パターン集 / Practical regex examples
• Lookbehind のブラウザ対応 / Regex lookbehind support
• JWT 署名検証失敗 / JWT signature verification failed