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

ReDoSは、正規表現のマッチ処理が入力長に対して爆発的に遅くなる性質を突いて、CPUを使い切らせる攻撃です。厄介なのは、脆弱かどうかがパターンの書き方だけでは決まらない点にあります。同じ正規表現と同じ入力でも、Go 1.27.2は0.01msで返し、Python 3.15.0は約15秒かかりました。自分では1本も正規表現を書いていなくても、依存ライブラリ経由で同じ問題を抱えます。ここでは6言語7エンジンの実測と、依存ライブラリの脆弱版・修正版の実測を並べ、どの対策から手を付けるべきかを判断できる形にします。

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

• 正式な弱点分類はCWE-1333「Inefficient Regular Expression Complexity」で、ReDoSはその別名として登録されています。
• 危険度は「パターンの計算量」「攻撃者が照合対象を制御できるか」「詰まったときの影響範囲」の3点で決まります。別スレッドへ逃がしても投入が続けばCPUは枯渇するので、非同期化は影響範囲を狭めるだけで免責にはなりません。
• 同じ^(a+)+$をa28個＋不一致文字1個の入力に当てた実測（Node・Pythonは3回の中央値、Goは単回）で、Python 3.15.0が14,891.5ms、Node 26.5.0が2,303.8ms、Go 1.27.2が0.01msでした。同じパターンでも、どのエンジンで動かすかで結果が変わります。
• 自分で書いた正規表現だけが対象ではありません。週6.8億ダウンロードのansi-regexは5.0.0で4万文字に約25秒かかり、5.0.1では1.0msでした。依存ライブラリのReDoSは、パターンを読むよりnpm auditなどで版を照合するほうが確実に見つかります。
• 最優先の対策は計算量を保証するエンジンを使うこと、次が実行時タイムアウトです。パターンの手直しと入力長制限は、この2つを取れないときの補強に置きます。
• 検出ツールは選定を誤ると無意味です。safe-regexは、Stack OverflowとCloudflareを実際に落としたパターンを両方とも「safe」と判定しました。recheckは前者をpolynomial(2)、後者をpolynomial(3)として検出します。
• 有名な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は攻撃側の呼称で（「Regex DoS」「正規表現DoS」とも書かれます）、修正対象として管理するときの正しい識別子はCWE-1333です。脆弱性報告を受け取る側はこの対応を押さえておくと分類に迷いません。

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

ReDoSの計算量悪用とDDoSの分散性

DDoSは攻撃元が分散していることを指し、ReDoSは正規表現の計算量を悪用する手法を指します。ReDoSでは、1リクエストでもCPUを長時間占有する場合があります。攻撃コストが極端に非対称で、数十バイトの文字列1本でワーカープロセスを数十秒止められます。1リクエストが正常な見た目のまま致命傷になるため、レート制限やWAFの流量制御ではほとんど止まりません。

ReDoS修正の優先度を決める計算量・入力経路・影響範囲

入れ子の量指定子を見つけるたびに直すのは現実的ではありません。次の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*a*$のように多項式時間で止まる場合があり、開始位置の再探索が重なると次数がさらに増えるので、原因と計算量は一対一には対応しません。^[a-zA-Z0-9]+$は各文字の帰属が一意に決まり両端も固定されているので、どれだけ長い入力でも線形時間で終わります。^([a-zA-Z0-9]+)+$は外側の+が同じ文字列を何通りにも分けられるため指数時間になります。記号ごとの意味と処理系ごとの方言は正規表現とは？基本記号の読み方と言語ごとの方言・ReDoS対策を実装目線で解説に整理しています。

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

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

計測に使ったのは次のコードです。末尾の!で必ず不一致にし、計測前に1回だけ空打ちしてから、同じ入力を3回照合した中央値を取っています。

const re = /^(a+)+$/;
re.test('aa!');
for (const n of [26, 28]) {
  const s = 'a'.repeat(n) + '!';
  const xs = [];
  for (let i = 0; i < 3; i++) {
    const t0 = process.hrtime.bigint();
    re.test(s);
    xs.push(Number(process.hrtime.bigint() - t0) / 1e6);
  }
  xs.sort((a, b) => a - b);
  console.log('node ' + process.versions.node + ' n=' + n + ' median=' + xs[1].toFixed(1));
}

node 26.5.0 n=26 median=567.0
node 26.5.0 n=28 median=2303.8

同じパターンと同じ入力を各処理系で走らせた結果です（macOS・x86_64）。0.00msは小数第2位未満という表示で、ゼロ時間という意味ではありません。読み取るのは桁の違いです。

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

9月20日に同じMacで単回計測したときは、Node 26.5.0のn=28が5,978.8msで、今回の中央値の2.6倍でした。Python 3.14.6を11月7日に3回測ったときも、n=28が21,145.2msから25,192.1msまで開いています。ほかの処理が動く機械では値がこの程度ぶれるので、自分の環境で測るときも複数回の中央値を取り、桁と伸び方（2文字で4倍）を読んでください。

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個＋!に当てた結果です。

PythonとNodeでは入力が4倍で時間が約16倍になっており、二乗時間の伸び方です。指数時間と違い、二乗時間は入力長の上限で押さえ込めます。Nodeで80,000文字が5.4秒かかっても、2,000文字に制限すれば6.30msで終わります。裏を返すと、投稿本文やファイルアップロードのように数万文字が正当な入力になる経路では、長さ制限を対策として使えません。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では後読みの(?<=a)bと(?<!a)bは通り、先読みの(?=a)a・後方参照の(a)\1・a{1000}は次のエラーで弾かれました。

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に、同じパターンを渡して比較しました（safe-regex 2.1.1／recheck 4.6.2、2026年11月7日）。Stack OverflowとCloudflareのものは公開された全文をそのまま渡しています。recheckのstatusはsafe・vulnerable・unknownの3種で、公式の説明ではsafeは「制限の範囲で攻撃文字列が見つからなかった」という意味です。

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が通したことを安全の根拠にはできません。READMEも This module has both false positives and false negatives. と、誤検知と見逃しの両方があると明記しています。危険と判定されたパターンも、recheckの判定（次数まで返ります）と実行経路で確かめてから修正対象に入れてください。

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

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

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とは？使い方・ルールの書き方・料金と無料版の検出範囲【v1.180で実測】を参照してください。

依存ライブラリのReDoS｜ansi-regexの実測とnpm auditでの検出・更新

依存ライブラリのReDoS勧告とエコシステム別集計

自社のコードをrecheckで検査しても、依存パッケージの中にある正規表現は対象になりません。GitHub Advisory DatabaseのREST API（GET /advisories?cwes=1333を全ページ取得し、GHSA IDで重複を除いた）でCWE-1333に分類された勧告を数えると、2026年11月7日時点でGitHubがレビュー済みの勧告は406件ありました（未レビューの146件は除く）。エコシステム別の内訳は次のとおりです。1件が複数のエコシステムにまたがる勧告があるため、合計は406件を超えます。

npmかPyPIを含む勧告はGHSA IDの重複を除いて322件で、レビュー済み406件の約8割です。どちらも先の実測で最悪値を出したバックトラック型のエンジンを標準に持つ環境で、標準の正規表現が線形時間を保証するGoとRustは1桁です。Node.jsとPythonのプロジェクトでは、自前のパターンの検査と同じ重みで依存の照合を回してください。

ansi-regex 5.0.0と5.0.1の処理時間

代表例がCVE-2021-3807です。ターミナルの色指定を検出するansi-regexの勧告で、3系から6系までの4系列が対象、修正版は3.0.1・4.1.1・5.0.1・6.0.1です。npmの集計APIでは2026年10月30日からの1週間に682,455,081回ダウンロードされており、直接インストールした覚えがなくても推移的依存として手元にある可能性が高いパッケージです。

勧告の概念実証と同じESC [＋セミコロンの連続を、脆弱版と修正版に渡して計測しました（Node 26.5.0、各3回の中央値）。

import { createRequire } from 'module';
const dir = process.argv[2];
const require = createRequire(dir + '/package.json');
const ansiRegex = require('ansi-regex');
const ver = require('ansi-regex/package.json').version;
for (const n of [10000, 20000, 40000]) {
  const s = '\u001B[' + ';'.repeat(n);
  const xs = [];
  for (let i = 0; i < 3; i++) {
    const t0 = process.hrtime.bigint();
    ansiRegex().test(s);
    xs.push(Number(process.hrtime.bigint() - t0) / 1e6);
  }
  xs.sort((a, b) => a - b);
  console.log('ansi-regex ' + ver + ' n=' + n + ' ms=' + xs[1].toFixed(1));
}

ansi-regex 5.0.0 n=10000 ms=1599.0
ansi-regex 5.0.0 n=20000 ms=6318.5
ansi-regex 5.0.0 n=40000 ms=24811.9
ansi-regex 5.0.1 n=10000 ms=0.3
ansi-regex 5.0.1 n=20000 ms=0.7
ansi-regex 5.0.1 n=40000 ms=1.0

脆弱版は入力が2倍になるたびに約4倍ずつ伸びており、二乗時間の増え方です。指数時間ほど急ではないので短い入力では気付けず、4万文字という現実的な長さで約25秒かかります。修正版は同じ入力を1.0msで返しました。パターンを読んで危険度を判断するより、版を上げるほうが速く確実です。

推移的依存をnpm auditで見つけて直す手順

実際に多いのは、直接の依存は安全な範囲を指定しているのに、lockfileに古い版が固定されたまま残っている状態です。[email protected]はansi-regexを^5.0.0で要求するので、lockfileが5.0.0のままなら脆弱版が使われ続けます。この状態をnpm 11.17.0で再現し、検出から修正までを流しました。

$ npm ls ansi-regex
`-- [email protected]
  `-- [email protected]

$ npm audit
ansi-regex  5.0.0
Severity: high
Inefficient Regular Expression Complexity in chalk/ansi-regex - https://github.com/advisories/GHSA-93q8-gq69-wqmw
fix available via `npm audit fix`
node_modules/ansi-regex

1 high severity vulnerability

$ npm audit fix
changed 1 package, and audited 3 packages in 645ms
found 0 vulnerabilities

$ npm ls ansi-regex
`-- [email protected]
  `-- [email protected]

親が要求する範囲の中に修正版があれば、npm audit fixだけでlockfileが書き換わります。範囲の外にしか修正版がない場合、npm auditは--forceを要求します。package.jsonで"ansi-regex": "5.0.0"と固定して試すと、Will install [email protected], which is outside the stated dependency rangeと表示されました。親パッケージ側の固定で上げられないときは、ルートのpackage.jsonにoverridesを書いて推移的依存の版を差し替えます（ルート以外のpackage.jsonでは効きません）。

{
  "overrides": {
    "ansi-regex": "5.0.1"
  }
}

Pythonではpip-auditが依存を解決したうえでPyPIの勧告と照合し、--fixで更新まで行います。手で回すのを忘れる運用なら、GitHubのDependabotに任せるのが確実です。Dependabotは新しい勧告が登録されたときにも既定ブランチを照合し直し、推移的依存の修正に親の更新が要る場合は親と子をまとめて上げるプルリクエストを作ります。設定ファイルの書き方はDependabotとは｜料金は無料・dependabot.ymlの書き方とRenovateとの違い【2026年10月】、依存の照合をSAST・SBOMとどう組み合わせるかはSCAとは？ソフトウェア構成分析の仕組みとSAST・SBOMとの違い・導入判断を解説で扱っています。

正規表現エンジン本体の脆弱性はReDoSと別に追う

依存の照合で見落としやすいのが、言語処理系に組み込まれた正規表現エンジンです。Rubyは2026年10月23日の告知で、GitLabが採番した4件のCVE（CVE-2026-89078ほか）に対応する修正版4.0.9・3.4.12・3.3.13を出しました。中身はパターンのコンパイル時に起きる二重解放と整数オーバーフローで、計算量の問題であるReDoSとは別種です。影響するのはRegexp.newなどに攻撃者が操作できる文字列を渡す場合に限られ、告知はRegexp.timeoutでは防げないと明記しています。本記事の計測に使ったRuby 4.0.6も4.0.8・4.0.9の修正を含まない版です。計測結果は計算量の比較として読み、本番はRuby本体を修正版へ上げてください。影響する書き方と洗い出しの手順はRubyの脆弱性：正規表現エンジン4件の修正版とRailsでの影響箇所の洗い出しにまとめています。

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

第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]+$のように入れ子を外せるならそちらを選んでください。この例では外側の+が最初から不要でした。ほかのパターンで外すときも、受理する文字列を比較してください。キャプチャを利用する処理では、test()だけでなくexec()の結果も比較します。この例のflatにはキャプチャグループがないので、キャプチャを参照している呼び出し側があれば合わせて直す必要があります。

入力長制限の限界

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

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

目視のコードレビューを主たる防壁に据える運用は機能しません。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です。脆弱性報告を受けた際は、この対応で分類すると表記が揺れません。

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

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

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

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

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

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

関連記事

• 正規表現とは？基本記号の読み方と言語ごとの方言・ReDoS対策を実装目線で解説
• 入力バリデーションとは？防げる攻撃の範囲と許可リスト設計を実装目線で解説
• SASTとは？DAST・SCAとの違いとCI/CDへの組み込み・導入判断を実装視点で解説
• SCAとは？ソフトウェア構成分析の仕組みとSAST・SBOMとの違い・導入判断を解説
• Semgrepとは？使い方・ルールの書き方・料金と無料版の検出範囲【v1.180で実測】