正規表現の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つ。
| 脆弱パターン / Pattern | 問題 / Problem | 攻撃文字列の例 / Attack input |
|---|---|---|
/^(a+)+$/ | ネスト量化子 / Nested quantifiers | "a".repeat(30) + "!" |
/^(\d+)*$/ | ネスト量化子(+ の外に *) | "1".repeat(30) + "a" |
/^(a|aa)+$/ | 重複する選択肢 / Overlapping alternation | "a".repeat(30) + "b" |
/\s+$/(replace でのトリム) | 多項式型 O(n²) / Polynomial | " ".repeat(20000) + "x" を含む行 |
確実なのは静的解析です。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.
実例: devtoolspot.comのRegex Testerでの対策 / How this site's own Regex Tester defends against it
このサイト自身の /tools/regex-tester/ では、入力された正規表現からネスト量指定子を検知する ヒューリスティック関数を実装しています。この記事で説明した (a+)+ のような典型的な危険パターンを 検知対象にし、ブラウザが破滅的バックトラックで固まるリスクを減らします。
function hasNestedQuantifiers(pattern: string): boolean {
return /\((?:\\.|[^()])*[+*](?:\\.|[^()])*\)(?:[+*]|\{(?:[2-9]\d*|\d{2,})(?:,\d*)?\})/.test(pattern);
}Web Worker で実行し、タイムアウト時に強制終了する完全な対策は実装コストが大きいため、今回は 「危険なパターンをヒューリスティックに検知し、検知した場合は自動実行を止めて明示的な実行ボタンを要求する」 という現実的な折衷案を採用しました。誤検知の可能性はありますが、危険と判定されない大多数のパターンでは、 従来どおりのリアルタイムハイライトを維持できます。
This site's /tools/regex-tester/ uses a heuristic to detect nested quantifiers such as(a+)+. Instead of the higher implementation cost of a Web Worker with forced timeout termination, it pauses automatic evaluation for suspicious patterns and requires an explicit run action. This may produce false positives, but preserves real-time highlighting for the large majority of patterns that are not flagged as dangerous.
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 タイムアウトで遮断する
よくある質問 / FAQ
- ReDoS はなぜ起きる?
- JavaScript などのバックトラック型エンジンは、マッチに失敗すると別の分割方法を順に試します。(a+)+ のようにネストした量化子があると 'a' の列の分割方法が 2^n 通りになり、失敗するまで全てを試すため指数時間かかります。
- (a+)+$ はなぜ危険? aaaa...! で固まるのはなぜ?
- 末尾の '!' で必ず失敗するため、エンジンは外側と内側の + の組み合わせ全パターンをバックトラックで試します。a が30文字なら約2^29通り、1文字増えるごとに試行回数は約2倍になります。
- JavaScript の正規表現にタイムアウトは設定できる?
- できません。RegExp の実行は同期処理で中断手段がありません(.NET の MatchTimeout に相当する機能はない)。Node.js では worker_threads で実行して terminate() で打ち切るか、線形時間で動く re2 パッケージを使います。
- 自分の正規表現が ReDoS 脆弱か調べる方法は?
- 静的解析ツール recheck(npm / ESLint プラグイン eslint-plugin-redos)や regexploit が攻撃文字列まで提示してくれます。簡易チェックなら safe-regex もありますが誤検出があります。
- What is ReDoS (regular expression denial of service)?
- ReDoS is an attack that feeds a crafted string to a vulnerable regex, forcing a backtracking engine into exponential (or quadratic) time and exhausting CPU. Nested quantifiers like (a+)+ and overlapping alternations like (a|aa)+ are typical causes.
- How do I prevent ReDoS in Node.js?
- Limit input length before matching, rewrite ambiguous patterns, lint with recheck, and for untrusted input use the re2 package (linear time, no backtracking) or run the regex in a worker thread you can terminate.
関連ツール / Related tools
- Regex Tester
- Diff Checker(書き換え前後のパターン比較に)
- JSON Schema Validator(入力検証の代替手段)