flawopen.com/ReDoS（壊滅的バックトラッキング）とは？/Explained

ReDoS（壊滅的バックトラッキング）とは？

CWE-1333: Inefficient Regular Expression Complexityリファレンスページ

要点

バックトラッキング型の正規表現エンジンは、マッチに失敗すると同じ入力を別の分割方法で再試行することがあります。一部の曖昧なパターンでは試行回数が入力長に対して指数的に増えます。遅延は正規表現、エンジン、入力サイズ、並行数、リソース制限に依存し、高コストの要求が繰り返されるとサービスの処理能力を使い切る可能性があります。

脆弱なパターン

# Nested quantifier
^(a+)+$

# Overlapping alternatives, quantified
^(a|aa)+$

# A long matching prefix plus a final mismatch can
# force extensive retries in vulnerable engines.
# Do not benchmark this with attacker-sized input.

より安全な例

# Bound input before matching, then use a simple
# full-string identifier rule with no nested ambiguity.
import re

IDENTIFIER = re.compile(r"[a-z0-9]{1,64}\Z")

def valid_identifier(value: str) -> bool:
    if not isinstance(value, str) or len(value) > 64:
        return False
    return IDENTIFIER.fullmatch(value) is not None

# A bound reduces worst-case work; still set request
# size, concurrency, and execution-time limits.

バックトラッキングが急増する理由

バックトラッキングエンジンでは、^(a+)+$ のようなパターンは曖昧です。aaaa を入れ子の量指定子に複数の方法で割り当てられます。最後に一致しない文字があると、文字列全体が失敗だと判断するまで複数の候補を試すことがあります。

該当するパターンでは、一致する接頭辞の後に不一致が続くと、探索経路が接頭辞の長さに対して指数的に増えることがあります。特定のパターンとエンジンの組み合わせに依存し、すべての正規表現や失敗で発生するわけではありません。並行要求では短い入力も影響するため、入力サイズ、並行数、実行時間を制限してください。

信頼できない入力が正規表現に届く場所

入力検証だけでなく、User-Agent などのヘッダー解析、ログ処理、Markdown や構文強調、URL ルーティング、コンテンツフィルター、WAF ルール、渡されたフィールドに正規表現を適用するライブラリにもリスクがあります。広く使われるパッケージでも ReDoS アドバイザリが公開されており、依存関係の確認も必要です。

よくある質問

Which languages are affected?

リスクは言語だけでなくエンジンとパターンによって決まります。一般的なバックトラッキングエンジンは特定のパターンで過剰な再試行を行うことがあります。Go の regexp は入力長に対する線形時間を保証します。Rust の regex crate は1回の検索を O(m·n)（m はパターン長、n は入力長）とし、パターン固定なら入力長に対して線形です。反復検索イテレーターの最悪計算量は異なります。これらのエンジンは後方参照など保証を妨げる機能をサポートしません。

Is a length limit enough on its own?

長さ制限は処理量を抑えますが、安全な上限はパターン、エンジン、要求頻度、サービスの予算によって異なります。曖昧なパターンも直し、解析や照合の前に上限を適用してください。

How do I find vulnerable patterns?

ReDoS 対応の静的解析ツールを使い、実際のエンジンに照らして結果を確認します。量指定子を含むグループの再反復や、接頭辞が重複する選択肢を調べ、隔離環境で入力を制限し厳格なタイムアウトを設定してテストしてください。

Can I add a timeout instead?

タイムアウトの可否はランタイムと API によって異なります。.NET では信頼できない入力との照合に明示的なタイムアウトを設定します。それ以外では各エンジンの仕様を確認し、適用可能なタイムアウトがなければ安全性の高いエンジンを使うかパターンを設計し直します。タイムアウトは入力・並行数の制限を補いますが、曖昧なパターンを効率的にはしません。

参考資料

関連項目 Node.js ReDoS：正規表現とCVE-2026-83606