ReDoSとは？正規表現のバックトラック爆発を6言語7エンジンで実測し対策を判断する

ReDoSは、正規表現のマッチ処理が入力長に対して爆発的に遅くなる性質を突いて、CPUを使い切らせる攻撃です。厄介なのは、脆弱かどうかがパターンの書き方だけでは決まらない点にあります。同じ正規表現でも、動かすエンジンによって処理時間は0.00msから38秒まで開きます。ここでは実際に6言語7エンジンで計測した結果を並べ、どの対策から手を付けるべきかを判断できる形にします。

まとめ｜ReDoS対策の優先順位と前提条件

• 正式な弱点分類はCWE-1333「Inefficient Regular Expression Complexity」で、ReDoSはその別名として登録されています。
• 危険度は「パターンの計算量」「攻撃者が照合対象を制御できるか」「詰まったときの影響範囲」の3点で決まります。別スレッドへ逃がしても投入が続けばCPUは枯渇するので、非同期化は影響範囲を狭めるだけで免責にはなりません。
• 同じ^(a+)+$をa28個＋不一致文字1個の入力に当てた実測で、Python 3.14.6が38,061.4ms、Node 26.5.0が5,978.8ms、Go 1.26.5が0.00msでした。同じパターンでも、どのエンジンで動かすかで結果が変わります。
• 最優先の対策は計算量を保証するエンジンを使うこと、次が実行時タイムアウトです。パターンの手直しと入力長制限は、この2つを取れないときの補強に置きます。
• 検出ツールは選定を誤ると無意味です。safe-regexは、Stack OverflowとCloudflareを実際に落としたパターンを両方とも「safe」と判定しました。recheckは前者をpolynomial(2)、後者をpolynomial(4)として検出します。
• 有名な2件の障害はどちらも外部からの攻撃ではありません。防御の力点は入口のフィルタではなく、計算量そのものの上限に置くべきです。

ReDoSの定義と危険度の判断軸｜CWE-1333としての位置づけ

正式な弱点分類はCWE-1333、ReDoSはその別名

MITREのCWE-1333は、この弱点を The product uses a regular expression with a worst-case computational complexity that is inefficient and possibly exponential. と定義しています。同ページのAlternate Termsに「ReDoS」と「Regular Expression Denial of Service」「Catastrophic backtracking」が並び、ReDoSについては While this term is attack-focused, this is commonly used to describe the weakness. と注記されています。つまりReDoSは攻撃側の呼称で、修正対象として管理するときの正しい識別子はCWE-1333です。脆弱性報告を受け取る側はこの対応を押さえておくと分類に迷いません。

OWASPが定義したと説明されることがありますが、OWASPの現行ページに初出年の記載はありません。CWE-1333の参考文献に挙がる最古の資料はScott A. Crosbyの「Regular Expression Denial of Service」（2003年8月）で、年号を書くならここに留めるのが安全です。関連する攻撃パターンはCAPEC-492です。

帯域を使うDoSとの違いは計算量の悪用

DDoSが大量のリクエストで回線とサーバーを飽和させるのに対し、ReDoSは1リクエストでCPUを占有します。攻撃コストが極端に非対称で、数十バイトの文字列1本でワーカープロセスを数十秒止められます。1リクエストが正常な見た目のまま致命傷になるため、レート制限やWAFの流量制御ではほとんど止まりません。

優先度を決める3つの観点

入れ子の量指定子を見つけるたびに直すのは現実的ではありません。次の3点で優先度を付けます。

観点2の洗い出しは、入力の受け口を一覧化する作業と同じです。許可リストの設計と併せて整理すると重複しません。詳しくは入力バリデーションとは？防げる攻撃の範囲と許可リスト設計を実装目線で解説で扱っています。

バックトラック爆発の仕組み｜指数時間と二乗時間の見分け方

指数時間になるのは入れ子の量指定子

バックトラッキング型のエンジンは、照合に失敗すると分割の仕方を変えて再試行します。^(a+)+$のように量指定子が入れ子になっていると、n文字のaの分け方が2のn乗のオーダーで存在します。末尾に!を足して必ず不一致にすると、全組み合わせを試し尽くすまで止まりません。このパターンではaが1個増えるごとに時間が約2倍、2個で約4倍になります。

二乗時間になるのは末尾を固定した単純な量指定子

入れ子がなくても危険な形があります。Stack Overflowを落としたのは^[\s\u200c]+|[\s\u200c]+$という前後の空白を削るだけのパターンでした。同社のポストモーテムは、同じ問題を露出させる簡略版として\s+$を挙げ、This is not classic catastrophic backtracking (performance is O(n²), not exponential, in length), but it was enough. と書いています。20,000個の空白のあとに別の文字が来ると、エンジンは開始位置を1つずつずらして再探索するため、探索回数が入力長の二乗のオーダーになります。同社はこの回数を199,990,000回と記載しています。指数時間ではないのに落ちる、という点が実務では重要です。

危険な2つの形｜分割の曖昧性と開始位置の再探索

量指定子そのものが危険なのではありません。危険なのは同じ文字列に複数の分割方法が成り立つ箇所と、照合失敗のあと開始位置をずらして再探索する形の2つで、前者が指数時間、後者が二乗時間を生みます。^[a-zA-Z0-9]+$は各文字の帰属が一意に決まり両端も固定されているので、どれだけ長い入力でも線形時間で終わります。^([a-zA-Z0-9]+)+$は外側の+が同じ文字列を何通りにも分けられるため指数時間になります。記号ごとの意味と処理系ごとの方言は正規表現とは？基本記号の読み方と言語ごとの方言・ReDoS対策を実装目線で解説に整理しています。

6言語7エンジンでの実測｜同一パターンの処理時間の差

指数時間パターンの実測結果

計測に使ったのは次のコードです。末尾の!で必ず不一致にし、計測前に1回だけ空打ちしています。

const re = /^(a+)+$/;
re.test('aa!');
for (const n of [26, 28]) {
  const s = 'a'.repeat(n) + '!';
  const t0 = process.hrtime.bigint();
  re.test(s);
  const ms = Number(process.hrtime.bigint() - t0) / 1e6;
  console.log('node ' + process.versions.node + ' n=' + n + ' ms=' + ms.toFixed(1));
}

node 26.5.0 n=26 ms=1511.1
node 26.5.0 n=28 ms=5978.8

同じパターンと同じ入力を各処理系で走らせた結果です（macOS・x86_64、2026年9月20日、各1回のみの計測）。単回計測なので端数は当てになりません。0.00msは小数第2位未満という表示で、ゼロ時間という意味ではありません。読み取るのは桁の違いです。

Node とPythonは入力2文字の追加で約4倍に伸び、10万文字では計測を打ち切りました。Go・Rust・Rubyは10万文字を数十ミリ秒で終えています。PHPだけは時間が一定ですが、これは速く照合できたわけではありません。

PHPのbacktrack_limitと戻り値の扱い

PHPはpcre.backtrack_limitの既定値1,000,000を超えるとマッチ自体を中断します。

<?php
$s = str_repeat('a', 26) . '!';
$r = preg_match('/^(a+)+$/', $s);
var_dump($r);
printf("preg_last_error=%d %s\n", preg_last_error(), preg_last_error_msg());
if ($r === false) {
    echo "照合できなかった（不一致ではない）\n";
}

bool(false)
preg_last_error=2 Backtrack limit exhausted
照合できなかった（不一致ではない）

ハングしない代わりに、preg_matchが0（不一致）ではなくfalse（失敗）を返します。戻り値をif (!preg_match(...))のように真偽値として扱うと、この2つが同じ扱いに丸められます。許可リスト方式なら「拒否」に倒れて安全側ですが、危険パターンを探す拒否リスト方式では「該当なし」と解釈されて検査をすり抜けます。PHPで正規表現を検査に使うなら、戻り値は=== 1と=== falseで必ず区別してください。

二乗時間パターンでの入力長制限の効果と限界

Stack Overflowの簡略版\s+$を、空白n個＋!に当てた結果です。

指数時間と違い、二乗時間は入力長の上限で押さえ込めます。Node で80,000文字が14.4秒かかっても、2,000文字に制限すれば10ミリ秒未満で終わります。裏を返すと、投稿本文やファイルアップロードのように数万文字が正当な入力になる経路では、長さ制限を対策として使えません。Stack Overflowで問題になったのはまさに投稿本文でした。なおPHPがここで速いのはPCRE2のJITが効いているためです。pcre.jit=0を渡して同じ20,000文字を計測すると7,309.7msかかりました。既定の設定ではfalseも返していません。

線形時間を保証する系が落とす機能

下表の実装は、計算量の保証と引き換えに後方参照と先読み・後読みを捨てています。移行できるかはここで決まります。

Goのregexpは The regexp implementation provided by this package is guaranteed to run in time linear in the size of the input. と明記しています。V8の実験的エンジンは--enable-experimental-regexp-engine付きで起動すると非標準のlフラグが使えるようになり、対応できないパターンはコンパイル時に弾かれます。Node 26.5.0で確認したエラーは次のとおりです。

Invalid regular expression: /(a)\1/l: Cannot be executed in linear time
Invalid regular expression: /(?=a)a/l: Cannot be executed in linear time

実行時に遅くなるのではなく、書いた時点で失敗します。実験的機能なので本番のフラグに入れる判断は慎重にすべきですが、既存パターンが線形時間に載るかを機械的に洗い出す用途には今すぐ使えます。

実際の障害事例｜攻撃ではなかった2件の内訳

Stack Overflow 2016-07-20（34分・O(n²)）

公式ポストモーテムは On July 20, 2016 we experienced a 34 minute outage starting at 14:44 UTC. と始まり、原因を a malformed post that caused one of our regular expressions to consume high CPU on our web servers と説明しています。トリガーは -- play happy sound for player to enjoy で始まるコメント行に約20,000文字の連続する空白を含む投稿でした。それがトップページの一覧に載って表示ごとに重い照合が走り、ロードバランサのヘルスチェック先がトップページだったためサイト全体が切り離されました。修正は正規表現を部分文字列関数へ置き換えることでした。

Cloudflare 2019-07-02（27分・自社ルール配備）

Cloudflareの障害は、WAFのマネージドルールに追加した1本の正規表現が原因でした。同社はポストモーテムで The regular expression that was at the heart of the outage is という書き出しで次を公開しています。

(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))

爆発を起こしたのは末尾の.*(?:.*=.*)で、記事はさらに.*.*=.*まで簡略化して説明しています。13:42の配備で全世界のCPUが飽和し、14:07にWAFを停止、14:09に復旧という27分の停止でした。全顧客のドメインで502が返っています。Cloudflareは別記事で This was not an attack (as some have speculated) と明記しました。

2件に共通する条件

どちらも外部からの攻撃ではなく、前者は不正な形式の投稿、後者は自社のルール配備でした。しかも脆弱な正規表現はそれぞれ1本だけです。ReDoSを攻撃として警戒するだけでは足りず、攻撃者がいなくても同じ結果が出る前提で、照合に費やす時間の上限と停止時の影響範囲を決めておく必要があります。

検出ツールの実力差｜safe-regexが見逃す実障害パターン2件

recheckとsafe-regexの判定結果の差

ReDoS検出として広く紹介されているsafe-regexと、ファジングと静的解析を組み合わせたrecheckに、同じパターンを渡して比較しました。Stack OverflowとCloudflareのものは公開された全文をそのまま渡しています。

import { checkSync } from 'recheck';
import safe from 'safe-regex';

const patterns = [
  ['教科書例', '^(a+)+$'],
  ['競合記事の例', '^([a-zA-Z0-9]+)+$'],
  ['Stack Overflow 2016', '^[\\s\\u200c]+|[\\s\\u200c]+$'],
  ['Cloudflare 2019', '(?:(?:\\"|\'|\\]|\\}|\\\\|\\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|\\-|\\+)+[)]*;?((?:\\s|-|~|!|{}|\\|\\||\\+)*.*(?:.*=.*)))'],
  ['修正後', '^[a-zA-Z0-9]+$'],
];

for (const [label, src] of patterns) {
  const r = checkSync(src, '');
  const c = r.complexity;
  const detail = c ? c.type + (c.degree !== undefined ? '(' + c.degree + ')' : '') : '-';
  console.log(label);
  console.log('  recheck    : ' + r.status + ' / ' + detail);
  console.log('  safe-regex : ' + (safe(new RegExp(src)) ? 'safe' : 'vulnerable'));
}

教科書例
  recheck    : vulnerable / exponential
  safe-regex : vulnerable
競合記事の例
  recheck    : vulnerable / exponential
  safe-regex : vulnerable
Stack Overflow 2016
  recheck    : vulnerable / polynomial(2)
  safe-regex : safe
Cloudflare 2019
  recheck    : vulnerable / polynomial(3)
  safe-regex : safe
修正後
  recheck    : safe / linear
  safe-regex : safe

3件目がStack Overflowを落とした実物、4件目がCloudflareを落とした実物です。safe-regex 2.1.1はどちらも「safe」と判定しました。同版の解析器はheuristic-analyzerただ1つで、その第1ヒューリスティックが「star height > 1」＝量指定子の入れ子の有無です。入れ子のない二乗・三乗の形は原理的に検出できません。教科書的な^(a+)+$だけで試すと差が出ないため、この限界は気付きにくいところです。safe-regexが通したことを安全の根拠にはできません。検出できた場合の指摘自体は有効なので、recheckと併用する分には害がありません。recheckは複雑度の次数まで返します。

ESLintでのCI組み込みと検出範囲

recheckはESLintプラグインとしても配布され、ルールはredos/no-vulnerableの1本だけです。既定はignoreErrors: trueで、解析が時間切れになったunknownを黙って通します。CIのゲートに使うならfalseにして未判定も落としてください（eslint 10.11.0／eslint-plugin-redos 4.5.0）。

import redos from 'eslint-plugin-redos';
export default [
  {
    files: ['sample.js', 'sample2.js'],
    plugins: { redos },
    rules: { 'redos/no-vulnerable': ['error', { ignoreErrors: false }] },
  },
];

const idPattern = /^([a-zA-Z0-9]+)+$/;
const trimPattern = /^[\s\u200c]+|[\s\u200c]+$/;
const safePattern = /^[a-zA-Z0-9]+$/;
export { idPattern, trimPattern, safePattern };

const a = /^([a-zA-Z0-9]+)+$/;
const b = new RegExp('^([a-zA-Z0-9]+)+$');
const part = '([a-zA-Z0-9]+)';
const c = new RegExp('^' + part + '+$');
export { a, b, c };

sample.js
  1:19  error  Found a ReDoS vulnerable RegExp (exponential)            redos/no-vulnerable
  2:21  error  Found a ReDoS vulnerable RegExp (2nd degree polynomial)  redos/no-vulnerable

sample2.js
  1:11  error  Found a ReDoS vulnerable RegExp (exponential)  redos/no-vulnerable
  2:11  error  Found a ReDoS vulnerable RegExp (exponential)  redos/no-vulnerable

✖ 4 problems (4 errors, 0 warnings)

正規表現リテラルと、文字列リテラルを渡したnew RegExpはどちらも検出されます。一方でsample2.jsの4行目にある変数を連結して組み立てたパターンは指摘されません。動的生成が多いコードベースでは、ルール適用と併せて生成箇所を減らす方向に寄せるほうが効きます。CI全体の静的解析にどう位置付けるかはSASTとは？DAST・SCAとの違いとCI/CDへの組み込み・導入判断を実装視点で解説、言語横断でルールを書く場合はSemgrepの基本概要と静的解析ツールとして選ばれる3つの理由を参照してください。

対策の優先順位｜エンジン・実行時ガード・パターン修正・入力長制限

第1選択＝エンジン側の計算量保証

GoのregexpとRustのregexクレートは、単一の検索について既定で計算量が保証されるため、パターンを書き換える作業は要りません。ただし保証は1回の検索単位なので、全件列挙を繰り返す処理では入力サイズ側の上限も併せて決めます。.NET 7以降はRegexOptions.NonBacktrackingを渡すだけで同じ保証が得られます。まず使用中のパターンを後方参照と先読みの有無で機械的に分類し、移行できるものから移すのが最短経路です。

第2選択＝実行時タイムアウト

エンジンを替えられない場合は、照合そのものに時間上限を掛けます。Ruby 3.2以降はRegexp.timeout=（プロセス全体）とRegexp.new(..., timeout:)（個別）の2系統を持ちます。同バージョンではメモ化による最適化も入っており、先の実測でRubyが^(a+)+$を10万文字でも54.49msで返したのはこれによるものです。ただしメモ化は万能ではなく、後方参照を含むパターンでは効きません。そこはタイムアウトが受け持ちます。

Regexp.timeout = 0.5
begin
  /^(a+)+\1$/.match?('a' * 40 + '!')
rescue Regexp::TimeoutError => e
  puts "Regexp::TimeoutError: #{e.message}"
end
puts "Regexp.timeout=#{Regexp.timeout}"

Regexp::TimeoutError: regexp match timeout
Regexp.timeout=0.5

.NETはRegex(string, RegexOptions, TimeSpan)のコンストラクタでmatchTimeoutを受け取り、超過時にRegexMatchTimeoutExceptionを投げます。一方でNode.jsとPythonの標準ライブラリには照合のタイムアウトがありません（re.compile・re.searchに該当する引数はなく、RegExpにも該当するAPIはありません）。先の実測で最悪値を出したのもこの2つで、攻撃者が制御できる入力を同期的に照合している箇所があるなら最優先の見直し対象になります。

パターン書き換え後の処理時間と判定結果

Python 3.11以降はアトミックグループ(?>...)と絶対最大量指定子*+++が使えます。10万文字の入力でも^(?>a+)+$は0.06msで返りました。JavaScriptにはアトミックグループがないため、先読みと後方参照を組み合わせて同じ効果を作ります。

const vuln   = /^([a-zA-Z0-9]+)+$/;
const atomic = /^(?=((?:[a-zA-Z0-9]+)+))\1$/;
const flat   = /^[a-zA-Z0-9]+$/;

for (const s of ['abc', 'ABC123', '', 'a-b']) {
  console.log(JSON.stringify(s), vuln.test(s), atomic.test(s), flat.test(s));
}

"abc" true true true
"ABC123" true true true
"" false false false
"a-b" false false false

3者は同じ判定を返します。擬似アトミックグループは既存パターンの構造を保ったまま直せる一方で読みにくくなるため、^[a-zA-Z0-9]+$のように入れ子を外せるならそちらを選んでください。この例では外側の+が最初から不要でした。ほかのパターンで外すときは、上のようにキャプチャ位置と受理する文字列が変わらないかを照合して確かめてください。

入力長制限の限界

入力長の上限は二乗時間パターンには効きますが、指数時間パターンには頼れません。a26個で1.5秒に達するため、実用的な制限値の内側に危険域が入り込みます。入力長制限を単独の対策として扱うのは誤りです。エンジンの保証かタイムアウトを先に入れ、長さ制限はその上での被害軽減として置きます。正当な長入力を拒否する副作用もあるので、上限値は経路ごとに決めます。

主たる防壁にできない運用

目視のコードレビューを主たる防壁に据える運用は機能しません。Stack Overflowを落としたのは前後の空白を削るだけのパターンで、レビューで危険と気付ける形をしていませんでした。同じ理由で、危険なパターンの例を社内ガイドラインに列挙する方法も限界があります。redos/no-vulnerableのように機械判定をCIに置き、レビューは判定結果の採否に使ってください。

よくある質問

手元の正規表現が危険かを最短で調べる方法は？

recheckをインストールしてcheckSync(パターン, フラグ)に渡します。statusはsafe／vulnerable／unknownの3種で、vulnerableのときだけ複雑度の次数と攻撃文字列が付きます。解析が時間切れになるとunknownです。CIに常設するならESLintプラグイン版でredos/no-vulnerableをignoreErrors: false付きで有効にしてください。safe-regexは量指定子の入れ子しか見ないため、判定の根拠にはできません。

OWASPやCWEではどう分類されていますか？

修正対象としての識別子はCWE-1333「Inefficient Regular Expression Complexity」です。ReDoSはCWE-1333のAlternate Termsに登録された攻撃側の呼称で、関連する攻撃パターンはCAPEC-492です。脆弱性報告を受けた際は、この対応で分類すると表記が揺れません。

入力の文字数を制限すれば対策として十分ですか？

二乗時間のパターンには効きますが、指数時間のパターンには足りません。実測ではa26個の入力でNodeが1.5秒、Pythonが9.7秒かかっており、通常の入力長制限では防げない範囲に危険域があります。エンジンの計算量保証か実行時タイムアウトを先に入れてください。

JavaScriptにアトミックグループがない場合の書き換えは？

先読みの中で対象をまとめて捕捉し、その後方参照で照合し直す^(?=((?:[a-zA-Z0-9]+)+))\1$の形にすると、10万文字でも0.46msで終わります。ただし読みにくくなるので、外側の量指定子を外して^[a-zA-Z0-9]+$にできるならそちらを優先してください。

GoやRustへ移行できない場合の現実的な選択は？

RubyならRegexp.timeout=、.NET 7以降ならRegexOptions.NonBacktrackingかmatchTimeoutで対応できます。Node.jsとPythonの標準ライブラリには照合のタイムアウトがないため、別プロセスやワーカーに切り出して外側から打ち切る設計にするか、該当パターンを線形時間の形へ書き換える必要があります。

関連記事

• 正規表現とは？基本記号の読み方と言語ごとの方言・ReDoS対策を実装目線で解説
• 入力バリデーションとは？防げる攻撃の範囲と許可リスト設計を実装目線で解説
• SASTとは？DAST・SCAとの違いとCI/CDへの組み込み・導入判断を実装視点で解説
• Semgrepの基本概要と静的解析ツールとして選ばれる3つの理由