Regex Denial of Service (ReDoS): 破壊的なパターンの解説

Quick answer

Regex Denial of Service (ReDoS): 破壊的なパターンの解説: quick answer

Regex Denial of Service (ReDoS): サーバーを凍らせるパターン 🌀 シンプルなパターンがDDoS攻撃より危険な理由 1行のテキストがサーバーインフラ全体をダウンさせることを想像してください。ボットネットも大量トラフィックも不要で、ただ無害に見える正規表現にマッチさせるために巧妙に作られた文字列だけです。これはSFではありません—正規表現拒否サービス（ReDoS）は、現代ソフトウェア開発において過小評価され

What is the main takeaway from Regex Denial of Service (ReDoS): サーバーを凍らせるパターン 🌀?

Which InstaTunnel page should I read next?

Use the related pages below to continue into the most relevant documentation, product workflow, comparison page, or implementation guide.

シンプルなパターンがDDoS攻撃より危険な理由

1行のテキストがサーバーインフラ全体をダウンさせることを想像してください。ボットネットも大量トラフィックも不要で、ただ無害に見える正規表現にマッチさせるために巧妙に作られた文字列だけです。これはSFではありません—正規表現拒否サービス（ReDoS）は、現代ソフトウェア開発において過小評価されがちなセキュリティ脆弱性の一つです。

2019年、CloudflareのWebアプリケーションファイアウォールに存在した脆弱なregexパターンにより、インターネットの重要部分に影響を与える27分間のグローバル障害が発生しました。同様に、Stack Overflowも2016年に不適切な正規表現により34分間のダウンタイムを経験しています。これらの事例は、ReDoS攻撃が帯域幅ではなくアルゴリズムの複雑性を悪用するため、従来のDDoSよりも破壊的になり得ることを示しています。

ReDoSの理解：静かなサーバー殺し

正規表現拒否サービス（ReDoS）は、多くのregexエンジンがパターンを処理する方法のアルゴリズム的複雑性を悪用した攻撃です。従来の分散型DDoS攻撃が大量のインフラと帯域を必要とするのに対し、ReDoS攻撃はごく小さな、巧妙に作られた入力文字列—時には数十文字だけで—サーバーをダウンさせることが可能です。

この脆弱性は、regexエンジンがバックトラッキングと呼ばれる仕組みを使ってパターンマッチングを行う方法に由来します。regexエンジンが複数のマッチ候補を見つけたとき、それぞれの組み合わせを体系的に試行します。最悪の場合、この処理は入力サイズに対して指数関数的に増加し、CPUの枯渇とサービスの完全な停止を引き起こします。

壊滅的なバックトラッキングの数学

壊滅的なバックトラッキングは、入れ子の量指定子が指数爆発を引き起こすときに発生します。例えば、(a+)+というパターンは、a文字以上の繰り返しを意味します。このパターンに対して、”aaaaaaaaaaaaaaaaaaaaaa!“のような文字列がマッチするかどうかをエンジンが判断しようとすると、多くの計算が必要になります。

14文字の”a”と感嘆符を含む文字列では、65,000回以上のステップが必要です。30文字になると、処理時間は指数関数的に増加し、数時間かかるか、アプリケーションが無期限にハングする可能性もあります。

この数学的複雑性は、最悪ケースでO(2^n)と表され、nは入力文字列の長さです。つまり、入力に1文字追加されるごとに処理時間が倍増し、サーバーリソースを急激に消耗します。

悪意のあるregex：アプリケーションを破壊するパターン

セキュリティ研究者は、特に壊滅的なバックトラッキングに脆弱な特定のパターンを特定しています。これらの”邪悪なregex”パターンは共通の特徴を持ちます：

入れ子の量指定子

最も危険なパターンは入れ子の繰り返し演算子を含みます： - (a+)+ - 入れ子のプラス量指定子 - ([a-zA-Z]+)* - 繰り返し内の貪欲量指定子 - (a*)* - 複数レベルのスター量指定子 - (a|aa)+ - 重複するマッチを持つ選択

重複する部分式

2つの部分式が同じ文字列にマッチできる場合、regexエンジンはすべての組み合わせを探索します： - (\d+)* - “123”を1つのグループまたは3つの別々のグループとしてマッチ可能 - (x+x+)+ - 同じ文字を分割する複数の方法 - ([a-z]+\s?)* - 重複する単語と空白のマッチ

実世界の脆弱なパターン

OWASPによると、以下のパターンは”aaaaaaaaaaaaaaaaaaaaaa!“のような入力に対してReDoSに脆弱です： - (a+)+ - ([a-zA-Z]+)* - (a|aa)+ - (a|a?)+ - (.*a){x} for x > 10

最近のReDoS脆弱性：2024-2025年も脅威は続く

認識が高まる一方で、ReDoSの脆弱性は現代アプリケーションに引き続き影響を及ぼしています。最近のCVE公開例は、この脅威が依然として現役であることを示しています：

CVE-2024-9277：Langflow（バージョン1.0.18）に見つかった脆弱性により、攻撃者は非効率なregexパターンを利用してシステムを操作し、CPUリソースを著しく消耗させました。

CVE-2024-5552：KubeflowのメールバリデーションシステムがReDoS攻撃に脆弱であることが判明し、悪意のある入力が非効率な正規表現を悪用してサーバーのCPUリソースを枯渇させました。

CVE-2024-21490：Angularのng-srcsetディレクティブに含まれるregexパターンは、バックトラッキングにより超線形の実行時間に脆弱であり、壊滅的なバックトラッキングとサービス拒否を引き起こす可能性があります。

CVE-2024-27088：es5-extライブラリにReDoS脆弱性が見つかり、npmパッケージに影響を与え、広範なセキュリティ問題を示しています。

2024年の研究では、GitHubリポジトリの10%以上にReDoS脆弱なregexパターンが含まれていることが判明しました。2025年9月の”Shai-Hulud supply chain attack”は、広く使われているnpmパッケージの脆弱性を特定し修正する重要性を再認識させました。

ReDoSの仕組み：技術的な深堀り

ReDoSを理解するには、regexエンジンがパターンをどのように処理するかを把握する必要があります。ほとんどの最新実装は、バックトラッキングを伴う非決定性有限オートマトン（NFA）アプローチを採用しています。例として、/A(B|C+)+D/のパターンをエンジンが処理する流れは次の通りです：

初期マッチング：エンジンは入力文字列にパターンを試みる
パス探索：複数のマッチ候補がある場合、最初の可能なパスを選択
バックトラッキング：パスが失敗した場合、エンジンは他の組み合わせを試すために後退
指数関数的増加：入れ子の量指定子により、パスの数は指数関数的に増加

例として、/W(X|Y+)+Z/が”WYYYA”にマッチする場合を考えます。Y文字が3つだけでも、エンジンは4つの異なるマッチング組み合わせを探索しなければなりません： - YYY（すべて一緒） - YY + Y（2つに分割） - Y + YY（逆順の分割） - Y + Y + Y（すべて別々）

入力が増えると、これらの組み合わせは指数関数的に爆発します。デバッガは14文字で65,000ステップ以上を示し、30文字と非マッチの接尾辞では数秒からアプリケーションの完全停止に至ることもあります。

ReDoSが従来のDDoSより危険な理由

ReDoS攻撃は、以下の特徴により非常に巧妙です：

非対称の攻撃力：50文字のペイロードを持つ単一のHTTPリクエストだけで、数分から数時間のCPU時間を消費させることが可能です。従来のDDoSは何千ものリクエストやギガビットの帯域を必要とします。

ステルス性：ReDoS攻撃は正当なトラフィックのように見えるため、従来のセキュリティツールでは検知が難しいです。レートリミットやDDoS保護システムを回避します。

特別な条件不要：ボットネットや特殊なインフラを必要とせず、単一のデバイスから攻撃可能です。特権やユーザーの操作も不要です。

区別困難：リクエストはリソースを消費し始めるまで普通に見えます。監視システムが異常なCPU使用を検知する頃には、すでに被害が進行しています。

攻撃の広範性：現代のWebアーキテクチャのすべての層—ブラウザ、Webアプリケーションファイアウォール（WAF）、データベース、バックエンドサーバー、APIゲートウェイ—がregexパターンを処理し、悪用され得ます。

実例と影響：ケーススタディ

Cloudflare障害（2019年7月）

2019年7月2日、CloudflareはWAFに新しいregexルールを導入しましたが、その中に邪悪なパターンが含まれていました。この変更により、HTTP/HTTPSトラフィックを処理する全コアでCPU枯渇が発生し、27分間の障害となりました。この後、CloudflareはWAFをRustの非バックトラッキングregexライブラリに書き換え、GoogleのRE2に似たアルゴリズムを採用しました。

Stack Overflowの事例（2016年）

Stack Overflowは、^[\s\u200c]+|[\s\u200c]+$の正規表現を誤った投稿に対して実行した際、34分間のサービス停止を経験しました。このパターンは空白のトリミング用に設計されていましたが、エッジケースで壊滅的なバックトラッキングを引き起こし、Webサーバーの高CPUリソースを消耗し、ピーク時のサービス低下を招きました。

隠れた疫病

大規模な公開障害は2件だけですが、実際のReDoSの影響はもっと広範です。多くの事例は報告されず、一般的なパフォーマンス問題と誤診されることもあります。2024年の文献レビューでは、実戦での武器化の記録は限られていると指摘されており、多くの組織がターゲットにされていることに気付いていない可能性があります。

脆弱なパターンの特定方法

セキュリティ研究者は、邪悪なregexパターンを特定する明確な基準を設定しています。正規表現が脆弱であるのは、次の条件を満たす場合です：

入れ子の量指定子：2つの量指定子（*、+、?、{n,m}）が、ある部分式の中にもう一つを含む場合。例： (a+)+は+が内外に適用されている。

重複するマッチ：ある文字列が複数の方法で両方の部分式にマッチできる場合。例：”aaa”が1つのグループ、2つのグループ、または3つの別々のグループとしてマッチ可能。

曖昧な選択：|を使った選択で、複数のオプションが同じ入力にマッチし、指数バックトラッキングを引き起こすパターン。例：(\d?|[1-9])+は数字にマッチする複数の方法を持つ。

遅延評価の誤用：.*?something.*?のようなパターンは、”something”部分が複数の候補にマッチし得る場合に問題を引き起こす。

検出ツールと手法

ReDoSの脆弱性を特定するためのツールには次のようなものがあります：

RegEx101デバッガ：このオンラインツールは、regexのマッチングをステップごとに可視化し、必要なステップ数を示します。バックトラッキングの挙動理解に役立ちます。

静的解析ツール：RegexScalpelのようなリンターは、パターンを解析し、脆弱な構造を検出します。RegexScalpelは、PythonやNLTKなどの人気プロジェクトの16の脆弱なregexを特定・修正し、8つのCVEを確定しています。

ファジング手法：さまざまな長さの入力を生成し、実行時間の超線形増加を示すパターンを特定します。

safe-regex：このnpmパッケージは誤検知や見逃しもありますが、JavaScriptアプリケーションの自動検出に役立ちます。

防御戦略：アプリケーションを守る

1. 非バックトラッキングregexエンジンの利用

最も効果的な防御策は、ReDoSを防ぐ設計のregexエンジンに切り替えることです：

GoogleのRE2：このライブラリは、バックトラッキングを避けて線形時間で動作します。C++、Go、Pythonなどで利用可能です。

Rust Regexクレート：Rustのregexライブラリは決定性有限オートマトンを使用し、入力長に対して線形の動作を保証します。

Hyperscan：Intelの高性能regexライブラリで、バックトラッキングを防ぐモードもあります。

2. タイムアウトの設定

regex操作に厳格なタイムアウトを設定し、無限ループを防ぎます：

// JavaScript例：タイムアウト付き
function matchWithTimeout(pattern, input, timeoutMs) {
  return Promise.race([
    new Promise(resolve => resolve(pattern.test(input))),
    new Promise((_, reject) => 
      setTimeout(() => reject('Timeout'), timeoutMs)
    )
  ]);
}

多くの言語では、regexにタイムアウト設定がサポートされています。例：.NET Framework 4.5+はRegexOptions.Timeoutを提供します。

3. 脆弱なパターンの書き換え

危険なパターンを安全なものに変換します：

Before: (a+)+（脆弱） After: a+（安全—意味は同じ、入れ子の量指定子なし）

Before: (\d+)*（脆弱） After: \d*（安全—同等で簡素化）

Before: (.*a)+（脆弱） After: ([^a]*a)+（安全—文字除外を使い重複を防ぐ）

4. アトミックグループとPossessive Quantifiersの利用

これらの機能は、特定のパターン部分のバックトラッキングを防ぎます：

アトミックグループ：(?epattern)は、一度マッチしたら後退しないことをエンジンに指示します。 Possessive Quantifiers：a++やa*+は、量指定子が文字を返すのを防ぎます。

例： Before: \b\d+E（バックトラッキング可能） After: \b\d++Eまたは\b(?\d+)E（バックトラッキングなし）

5. 入力の検証とサニタイズ

防御的なプログラミングを実施します：

長さ制限：regex処理前に入力文字列の長さを制限 文字ホワイトリスト：可能な限り、入力に許容される文字セットを検証 前処理：問題のある文字を除去またはエスケープ レートリミット：リクエストごとの制限を設け、連続的な攻撃を防止

6. 静的正規表現のコンパイル

アプリ起動時にregexパターンを事前にコンパイルし、動的に作成しない：

# Python例
import re

# モジュールレベルで一度だけコンパイル
EMAIL_PATTERN = re.compile(r'^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$')

def validate_email(email):
    return EMAIL_PATTERN.match(email) is not None

これによりパフォーマンスが向上し、コードレビュー時に全パターンを監査できます。

7. 監視と検知

実行時の監視によりReDoS攻撃を検知します：

CPU使用率の監視：リクエストごとのCPU消費を監視し異常を検知 リクエスト時間の監視：通常より長いリクエストをアラート パターンの分析：実行されたregexパターンとそのパフォーマンスを記録 異常検知：機械学習を用いて異常なリクエストパターンを検出

regex開発のベストプラクティス

設計原則

最小権限の原則：目的を達成できる最も単純な構造を使用。文字列操作だけで済むならregexは避ける。

特異性優先：過度に柔軟なパターンよりも正確なパターンを書く。例：\d{3}-\d{3}-\d{4}は[\d-]+より安全です。

排他性：選択肢や連続パターンが同じ文字列に複数の方法でマッチしないように設計。

早期失敗：無効な入力は早めに拒否。特定の制約をパターンの前半に置く。

テスト戦略

境界テスト：最小・最大長の入力でテスト 悪意のある入力テスト：バックトラッキングを誘発する入力を含める パフォーマンステスト：入力サイズに応じた処理時間を測定し、線形増加を確認 リグレッションテスト：ReDoS脆弱性修正後は、以前の問題を再現するテストを追加

コードレビューのチェックリスト

正規表現を含むコードをレビューする際は、次の点を確認： - 入れ子の量指定子 ((a+)+, (.*)*) - 重複する選択 ((a|ab)+) - 複数の方法でマッチ可能な曖昧な繰り返し - regex処理前の入力検証の欠如 - ユーザ入力から動的にパターンを生成 - regex操作にタイムアウト設定がない

ReDoSの未来：新たな動向と解決策

エンジンレベルの改善

現代のプログラミング言語ランタイムはReDoS対策を進めています：

Java：Java 9以降（2016年）では、バウンド付きメモ化キャッシュが導入され、ReDoSシナリオのパフォーマンス改善に寄与しています。これはコード変更不要のパッチです。

Python、PHP、Perl：これらの言語は Spencerスタイルのバックトラッキングエンジンを引き続き使用しており、根本的な脆弱性は残っていますが、性能改善の努力も進行中です。

新たな標準：決定性有限オートマトンをデフォルトとし、必要に応じてバックトラッキングを使う設計への移行が進んでいます。

学術研究とツール

2024年の文献レビューでは、ReDoS検出・防止・緩和に関する学術的関心が高まっています。USENIX Security 2022で発表されたRegexScalpelは、「ローカライズと修正」戦略を用いて348の脆弱なパターンを自動修復し、これまでの手法より多くの修正を実現しました。

2025年8月の最新研究では、新たな防御策の体系的評価や、より良いエンジン移行支援の必要性が指摘されています。研究コミュニティは、ReDoSと他のパフォーマンスバグの類似性も指摘し、今後はより包括的な視点が求められています。

産業界の取り組み

主要なテクノロジー企業もReDoSを真剣に捉えています：

GitHubセキュリティ：脆弱性の修正を推進し、オープンソースプロジェクトのReDoS問題に関するアドバイザリを提供。

npmエコシステム：2025年9月のShai-Hulud supply chain attackは、依存関係のReDoS脆弱性スキャンの重要性を再認識させました。

クラウドプロバイダー：Cloudflareの2019年事例以降、多くのクラウド事業者は重要インフラに非バックトラッキングregexエンジンを採用しています。

ReDoSに関する誤解

“古いコードやメンテされていないコードだけに影響する”

2024-2025年のCVE公開例は、AngularやLangflow、Kubeflowといった最新フレームワークにもReDoSの脅威が存在することを示しています。

“自分たちのアプリはターゲットにならない”

ReDoSは、fuzzingや偶発的なトリガーによって発見されることが多く、ユーザ入力をregexで処理するアプリはリスクにさらされています。

“検証済みライブラリを使っているから安全”

信頼性の高いオープンソースライブラリでもReDoS脆弱性は存在します。2024年の調査では、人気のGitHubプロジェクトの10%以上が脆弱でした。依存関係の継続的な監視が必要です。

“タイムアウト設定だけで完全解決”

タイムアウトは無限ループを防ぎますが、攻撃の表面積を排除しません。攻撃者は複数リクエストにタイムアウトを仕掛けてサービス低下を引き起こすことも可能です。

“ReDoSは理論的な懸念だけ”

CloudflareやStack Overflowの実際の障害例と、継続的なCVE発見は、ReDoSが実用的かつ攻撃可能な脆弱性であることを証明しています。

結論：敬意を払うべきパターン

正規表現拒否サービスは、計算機科学の複雑性、セキュリティ脆弱性、広範な展開の完璧な嵐です。(a+)+は7文字に過ぎませんが、従来のDDoS攻撃よりもサーバーを凍らせる効果的な武器になり得ます。

ReDoS攻撃の非対称性—ごく小さな入力で指数関数的にリソースを消耗させる—は、攻撃者が最小コストで行える一方、防御側は高コストを払うクラウド環境において特に危険です。アプリケーションが入力検証や検索、データ解析にregexを多用するほど、攻撃対象は拡大します。

防御には多層的なアプローチが必要です：安全なregexエンジンの利用、タイムアウトの設定、入れ子の量指定子を避けるパターン設計、入力の事前検証とサニタイズ、異常なCPU使用を監視することです。開発チームは、regexパターンをSQLクエリやシェルコマンドと同じくらいセキュリティの観点から厳しく扱う必要があります—それは単なる文字列処理ツールではなく、潜在的な攻撃経路だからです。

幸い、意識は高まっています。最新のregexエンジンはReDoS対策を取り入れつつあり、学術研究も実用的な検出・緩和ツールを生み出しています。業界のベストプラクティスも進化しています。ただし、何百万ものアプリに展開された脆弱なパターンの膨大な遺産は、ReDoSが今後も重要なセキュリティ課題であり続けることを意味します。

覚えておいてください：(a+)+を書いたとき、それは単なるパターンではなく、インフラに対して攻撃に使える武器になり得るのです。regexの世界では、シンプルさは美学だけでなく、セキュリティの要です。