ReDoS(正規表現によるサービス拒否)の仕組みと対策。短い入力でCPUを食い潰すバックトラックを塞ぐ

ReDoS(Regular expression Denial of Service)は、正規表現の照合処理そのものにCPU時間を使い果たさせるサービス拒否です。大量のリクエストを送りつける通常のDoSと違い、数十文字の入力を一回送るだけで、サーバーのワーカーを数秒から数分にわたって占有できてしまう点が厄介です。原因はネットワークでも認証でもなく、開発者が何気なく書いた一行の正規表現にあります。

この記事は、WebアプリケーションやAPIの実装とレビューを担当する開発者に向けて、バックトラック型の正規表現エンジンがなぜ短い入力で指数的に時間を使うのかを状態数とバックトラック回数で示し、危険なパターンの見分け方、実際に起きた障害、言語やランタイムごとの対策、静的検出ツール、設計とコードレビューでの判断基準までを整理します。

ReDoSが成立する機構#

正規表現エンジンには大きく二つの流儀があります。一つは、パターンを非決定性有限オートマトン(NFA)に変換したうえで、入力を一文字ずつ読みながら「いま到達し得る状態の集合」をまとめて進める方式です。もう一つは、あり得る経路を一本ずつ深さ優先で試し、行き止まりに当たったら直前の分岐点まで戻って別の経路を試す方式で、この戻る動作をバックトラックと呼びます。Perl、PCRE、Java、Python標準のre、JavaScriptのV8(Irregexp)、.NETの既定エンジン、Rubyの標準エンジンなど、実務で触れるエンジンの多くは後者のバックトラック型です。

バックトラック型が主流なのは、後方参照のように正規言語を超える機能や、先読みのようにオートマトンで扱うと状態数が膨らむ拡張機能を素直に実装できるうえ、典型的な入力では最初に試した経路がすぐ当たるので速いからです。問題は失敗するときです。照合に失敗したと結論づけるには、あり得る経路をすべて試し尽くさなければなりません。パターンの中に「同じ入力を複数の切り分け方で受理できる」曖昧さがあると、経路の数が入力長に対して爆発し、その全部を試す時間がそのままCPU時間になります。

MITREのCWE-1333は、この欠陥が悪用されるための条件を、バックトラックの試行回数が入力長に対して指数的であること、入力が照合に失敗し得ること、入力が十分に長くできること、の三つの組み合わせとして整理しています。ただし、これは指数的なバックトラックが問題になる典型的な条件であって、必要十分条件ではありません。CWE-1333の説明自体が最悪計算量を「非効率で、場合によっては指数的」と書いているとおり、多項式的な増え方でもReDoSは成立しますし、後述のCloudflareの例のように最終的に一致する入力でも途中で大量のバックトラックが起きます。それでも、パターンから曖昧さを取り除く、入力長を制限する、信頼できない入力に正規表現を使わない、という対策がこの三条件のどれかを崩す行為だという見方は、対策を整理するうえで役に立ちます。

MITREのCWE-1333は、最悪計算量が非効率で場合によっては指数的な正規表現を使う欠陥を定義し、エンジンがトークンの照合に失敗したときに別の経路を探して戻るバックトラックが原因だと説明しています。悪用の条件として、バックトラックの試行回数が入力長に対して指数的であること、入力が照合に失敗し得ること、入力が十分に長くできることを挙げ、緩和策として、入れ子量化子を取り除くなどバックトラックに頼らない正規表現を使うこと(効果は高)、PHPの pcre.backtrack_limit のようにバックトラック上限を設定すること(中)、信頼できない入力に正規表現を使わないこと(高)、正規表現が処理する入力長を制限すること(中)を示しています。

短い文字列でCPUを食い潰せる理由を数で見る#

OWASPのReDoSページが使う古典的な例が ^(a+)+$ です。「aが1個以上」のかたまりが1個以上続き、それで文字列全体が終わる、という意味ですが、この書き方には曖昧さがあります。たとえば入力 aaaa を受理する切り分け方は、(aaaa)、(a)(aaa)、(aa)(aa)、(a)(a)(aa) など、4文字を1個以上の区間に分ける方法の数だけあります。n個の a を区間に分ける方法は、隣り合う文字の間それぞれで「切る」「切らない」を選ぶので、切り分け方だけで 2のn乗のオーダーになります。OWASPは、aaaaX に対して16通り、aaaaaaaaaaaaaaaaX(aが16個)に対して65,536通りの経路があり、aが1文字増えるごとに倍になると説明しています。

入力が aaaa のように受理される場合、この式では最初に試した貪欲な経路(a+ が4文字全部を取り、$ が成功)で終わるので一瞬です。ところが末尾に ! が付いた aaaa! のように受理されない入力では、$ が ! の手前で失敗するたびに、エンジンは「では a+ の取り方を変えればうまくいくかもしれない」と戻り、2のn乗のオーダーの切り分けを順番に全部試してから、ようやく「一致しない」と答えます。これが指数的バックトラックの正体で、経路の総数は入力に依存し、パターンの見た目の短さとは無関係です。

Russ Cox氏は2007年の論文で、a? をn個並べたあとに a をn個並べたパターンを、aがn個の文字列に照合させる実験を示しました。バックトラック型のPerlでは29文字の入力に60秒以上かかるのに対し、状態集合を進めるThompson NFA方式では20マイクロ秒で済み、百万倍の差が出ています。バックトラック型は O(2のn乗) で n=25 を超えると実用にならない一方、Thompson NFA方式は状態リストの長さが概ねnで入力もnなので O(nの2乗) に収まる、という計算量の差が、そのまま体感時間の差になっています。

手元でも確かめました。Node.js v24.11.0 で /^(a+)+$/ に「aをn個並べて末尾に !」を与えると、n=20 で約0.18秒、n=24 で約0.65秒、n=26 で約1.4秒でした。Python 3.13.7 の re でも n=20 で約0.14秒、n=22 で約0.52秒、n=24 で約2.1秒と、2文字増えるごとにおよそ4倍になっています。30文字弱の文字列一つでリクエスト一本が数秒の間CPUを握るわけで、これを並列で数十本送れば、ワーカー数が有限のアプリケーションサーバーは他のリクエストを受け付けられなくなります。

指数的でなくても実害は出ます。単純な繰り返しの端に失敗条件があるだけの [\s]+$ のようなパターンは、失敗したとき開始位置をずらしながら再試行するため、空白がn個並ぶ入力に対する文字比較の回数は n + (n-1) + ... + 1 = n(n+1)/2 で nの2乗に比例します。手元のNode.jsで /^[\s]+|[\s]+$/ に「x、空白n個、x」を与えると、n=10,000 で約0.4秒、n=20,000 で約1.7秒、n=40,000 で約6.6秒と、入力を倍にするたびに約4倍かかりました。多項式的な増え方は指数ほど急ではありませんが、数万文字の入力はテキストエリア一つで送れるので、実務ではこちらの方が踏みやすい落とし穴です。

Russ Cox氏の「Regular Expression Matching Can Be Simple And Fast」(2007年1月)は、a? をn個と a をn個並べたパターンをaがn個の文字列に照合させたとき、Perlは29文字の入力に60秒以上を要する一方、Thompson NFA方式は20マイクロ秒で済み百万倍速いことを示しています。バックトラック方式は O(2のn乗) で n=25 を超えるとスケールしないこと、Thompson方式は長さ概ねnの状態リストを長さnの入力に対して処理するため O(nの2乗) で済むことを説明しています。

危険なパターンの見分け方#

OWASPは、細工した入力で止まってしまう正規表現を evil regex と呼び、その構造を「繰り返しを含むグループがあり、そのグループの内側に、さらに繰り返しがあるか、互いに重なり合う選択肢がある」と定義しています。例として (a+)+$、([a-zA-Z]+)*$、(a|aa)+$、(a|a?)+$ を挙げ、いずれも aaaaaaaaaaaaaaaaaaaaaaaa! のような入力で止まると説明しています。

共通する本質は曖昧さです。GitHubのCodeQLが提供する js/redos クエリの解説は、問題になる形を「r* や r+ のような繰り返しで、部分式 r が同じ文字列を複数の方法で照合できる」場合と言い表しています。同じ解説が挙げる ^_(__|.)+_$ では、部分式 (__|.)+ が __ を、第1選択肢で一度に取る方法と、第2選択肢の . を二回繰り返す方法の両方で照合できるため曖昧です。修正版の ^_(__|[^_])+_$ は第2選択肢からアンダースコアを除き、二つの選択肢が同じ文字列を受理しないようにしています。

実務で見かける危険な形を三つに分けて整理します。

三つ目は見落とされやすい形です。2019年のCloudflareの障害の原因になったパターンを単純化した .*.*=.* では、二つの .* がどこで境界を引くかが入力長だけ選べるため、失敗時はもちろん、x= の後ろに x を並べた一致する入力でも nの2乗以上の試行が起きます。手元のNode.js v24.11.0で /.*.*=.*/ に「x=」の後ろに x をn個並べた一致する入力を与えると、n=10,000 で約0.4秒、n=20,000 で約1.6秒、n=40,000 で約7.1秒と、一致するにもかかわらず入力を倍にするたびに約4倍かかりました。メールアドレスの検証でよく書かれる [\w.]+@[\w.]+\.[\w.]+ も、@ の後ろで [\w.]+ とリテラルの \. と次の [\w.]+ が同じピリオドを取り合うので、ピリオドを大量に含む入力で多項式的に遅くなります。

見分けるときの手順は次のとおりです。まず、量化子(*、+、{m,n}、?)が付いたグループの内側に、別の量化子や選択肢がないかを探します。次に、隣り合う二つの量化子付き要素が同じ文字を受理できないかを確かめます。\d+\.\d+ のようにリテラルで区切られていれば区切り位置の曖昧さはなくなりますが、\w+\s?\w+ のように区切りが省略可能だと、区切りがない場合に \w+ 同士が取り合います。ただし、区切りによる曖昧さの解消と、検索の開始位置を固定しないことによる再試行は別の問題です。^ や $ で位置を固定せずに /\d+\.\d+/ を数字だけの長い文字列に当てると、開始位置ごとに数字列を走査しては \. で失敗することを繰り返すため、手元のNode.js v24.11.0では2,000文字で約13ミリ秒、4,000文字で約48ミリ秒、8,000文字で約224ミリ秒と二次的に増えました。同じ入力に /^\d+\.\d+$/ を当てると1ミリ秒未満で終わります。全体を検証する用途では、このようにアンカーした式を使います。最後に、そのパターンが「失敗する」入力をどう受け取るかを考えます。事前検証で長さや文字種が制限されているなら、曖昧さがあっても実害は小さく抑えられます。一方で「必ず受理されるから安全」とは言えません。Cloudflareの .*.*=.* が示すとおり、一致する入力でも途中のバックトラックで時間を使うことがあります。

OWASPのReDoSページ(www-communityリポジトリ上のソース)は、ReDoSを、多くの正規表現実装が入力長に対して指数的に遅くなる極端な状況に陥る性質を突くサービス拒否と定義しています。^(a+)+$ を例に、aaaaX では16通り、aが16個の入力では65,536通りの経路があり、受理されない入力で全経路を試すことが原因だと説明します。evil regexの構造を、繰り返しを含むグループの内側に繰り返しか重なり合う選択肢がある形と定義し、(a+)+$、([a-zA-Z]+)*$、(a|aa)+$、(a|a?)+$ を例示しています。また、利用者名を検証するために利用者入力からRegexを組み立てるコードを示し、正規表現そのものを注入される形も挙げています。

実際に起きた障害#

2019年7月2日、Cloudflareは全世界で約27分間、多くのサイトが502エラーを返す障害を起こしました。原因は、WAF(Web Application Firewall)へ配信した新しいルールに含まれていた正規表現です。Cloudflareの事後報告によれば、当時のWAFはLuaで実装され内部でPCREを使っており、バックトラック方式で暴走する式から身を守る仕組みがありませんでした。問題の式は (?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*))) という長いもので、致命的だったのは末尾の .*(?:.*=.*) の部分です。事後報告は、これを単純化した .*.*=.* について、x=x で23ステップ、x= の後ろに x を20個並べた入力で555ステップ、さらにリテラル ; を後ろに足した .*.*=.*; では x=x で90ステップ、x を20個で5,353ステップと、ステップ数が入力長に対して急増する様子を示しています。ルールは13:42(UTC)に配信され、3分後に最初のアラートが上がり、14:07にWAFを止め、14:09にはトラフィックとCPUが元に戻りました。CPU使用率は世界中のサーバーでほぼ100%に張り付いていました。

Cloudflareが挙げた再発防止策の一つが、正規表現エンジンをRE2かRustのregexに切り替えることでした。どちらも実行時間の保証を持つエンジンで、バックトラックの暴走そのものを起こさない設計です。加えて、いったん外していたCPU使用量の保護機構を戻すこと、ルールのテストスイートに性能プロファイリングを組み込むこと、段階的な配信手順を整えることも列挙されています。

さらにさかのぼって2016年7月20日には、Stack Overflowが14:44(UTC)から34分間停止しました。Stack Exchangeの事後報告によれば、原因はトップページに表示される投稿に含まれていた約20,000文字連続の空白です。行頭と行末のUnicode空白を取り除くための ^[\s\u200c]+|[\s\u200c]+$ という正規表現が、空白の後ろに続く文字で $ の照合に失敗するたびに開始位置をずらして再試行し、文字クラスの検査を 20,000 + 19,999 + ... + 1 回、およそ2億回行いました(事後報告はこの合計を199,990,000回と記載していますが、正確な和は200,010,000回です)。トップページの描画のたびにこの処理が走って応答時間が悪化し、ロードバランサのヘルスチェックに失敗して全サーバーが切り離されました。修正は、この正規表現を部分文字列の関数に置き換えることでした。

二つの事例は対照的です。Cloudflareは攻撃ではなく自社のルール配信でしたが、指数的でなく多項式的な増え方でも世界規模の障害になり得ることを示しました。Stack Overflowは入れ子量化子を含まない単純な式でしたが、入力が長ければ nの2乗でも十分に致命的だと示しました。どちらも、正規表現が「ほとんどの入力で速い」ことと「すべての入力で速い」ことは別だと教えてくれます。

Cloudflareの事後報告は、2019年7月2日13:42(UTC)に配信したWAFルールの正規表現が過剰なバックトラックを起こし、世界中のサーバーでCPU使用率がほぼ100%に達して502エラーが発生したと説明しています。LuaのWAFは内部でPCREを使い、バックトラック方式で暴走する式を防ぐ仕組みがなかったこと、単純化した .*.*=.* が x=x で23ステップ、x を20個で555ステップ、; を足した式では90ステップと5,353ステップになることを示し、14:07にWAFを停止して14:09に回復したこと、再発防止としてRE2かRustのregexエンジンへの切り替え、CPU保護機構の再導入、性能プロファイリング、段階的配信を挙げています。

Stack Exchangeの事後報告は、2016年7月20日14:44(UTC)から34分間の停止について、約20,000文字の連続した空白を含む投稿に対し、行頭と行末の空白を除去する ^[\s\u200c]+|[\s\u200c]+$ が 20,000 + 19,999 + ... + 1 回(報告の記載は199,990,000回。正確な和は200,010,000回)の文字クラス検査を行う O(nの2乗) の挙動になったと説明しています。トップページの応答が遅くなりロードバランサのヘルスチェックに失敗して全サーバーが外れたこと、この正規表現を部分文字列関数に置き換えて修正したことが記されています。

ReDoSは「一発でサービスを止める」点でDDoSとは違う性質を持ちますが、ワーカー枯渇という結果は同じです。帯域や接続数の観点でのDoS対策は、次の記事で整理しています。

あわせて読みたい

DDoS攻撃とは。ボリューム型・プロトコル型・アプリ層の仕組みと、CDN/WAF/緩和サービスによる対策

言語とランタイム別の対策#

根本対策は、バックトラックに頼らないエンジンを使うことです。ただし、どのエンジンが選べるかは言語と環境で異なり、線形時間を保証するエンジンは後方参照や先読みを捨てているため、既存パターンをそのまま持ち込めない場合があります。主要な環境の状況を表にまとめます。

Goのregexpパッケージは、ドキュメントの冒頭で「この実装は入力サイズに対して線形時間で動くことを保証する」と明言し、多くのオープンソース実装がそうではないことに触れています。構文はRE2と同じで、後方参照は線形時間で実装できないため対応していません。RE2自体のREADMEは「安全性がRE2の第一の目標」と述べ、信頼できない利用者からの正規表現を危険なしに扱うことを明示的な設計目標としています。バックトラック型が「最初の選択肢が当たれば速い」楽観的な設計なのに対し、RE2はすべての選択肢を並列に評価する悲観的な設計で、その分の定数倍の負担を受け入れることで安全を買っている、という説明は、対策の考え方を端的に表しています。

Rustのregexクレートも同じ系譜で、ドキュメントは「このクレートのすべての検索は最悪でも O(m×n)(mはパターンの大きさ、nは検索対象の大きさに比例)」と保証し、効率的に実装する方法が知られていない先読みと後方参照を意図的に省いています。ただし同じドキュメントは、この O(m×n) が is_match、find、captures のような一回の検索に対する保証であり、find_iter や captures_iter で一致をすべて列挙する場合は検索が何度も走ってそれぞれが対象全体を走査し得るため、最悪 O(m×nの2乗) になると明記しています。もう一つ注意したいのは、この保証が入力に対するもので、パターンの側は別だという点です。信頼できないパターンを受け取るなら、RegexBuilderの size_limit を小さく設定し、必要に応じて広げる運用が案内されています。

.NETは、.NET 7で RegexOptions.NonBacktracking を導入しました。Microsoft Learnは、既定のバックトラック型エンジンが典型的な入力では速いが選択肢が増えると壊滅的なバックトラックに陥り得ること、NonBacktracking はバックトラックを使わずに入力長に線形の処理時間を保証し、入力にかかわらず一貫した挙動を目指すことを説明しています。一方で、RightToLeft や ECMAScript のオプションと併用できず、アトミックグループ、後方参照、バランシンググループ、条件、先読みと後読み、\G アンカーは使えません。ループ内のキャプチャについても、.NETの既定エンジンがすべての反復の値を保持するのに対し、NonBacktracking は最後の値だけを返す違いがあります。もう一つ見落としてはならないのが、Microsoft Learnの警告です。NonBacktracking は高価な入力から守るものであって、悪意あるパターンから守るものではなく、パターンは信頼できるものだという前提は変わりません。

NonBacktracking を使えない場合の.NETの守りが Regex.MatchTimeout です。一回の照合にかけられる概ねの最大時間を定め、超えると RegexMatchTimeoutException が送出されます。Regex(String, RegexOptions, TimeSpan) コンストラクタで個別に指定するか、AppDomain の REGEX_DEFAULT_MATCH_TIMEOUT プロパティでアプリケーション全体の既定を設定できます。明示しない場合の既定は InfiniteMatchTimeout、つまりタイムアウトなしなので、信頼できない入力に既定エンジンを使うなら必ず設定します。

Javaの java.util.regex.Pattern は、所有格量化子(X*+、X++、X?+)と独立した非キャプチャグループ (?>X) をサポートしており、いったん取った文字を返さないことでバックトラックの経路を切れます。ただし、Java 21のPattern APIドキュメントにはタイムアウトや線形時間の仕組みに関する記載がなく、標準ライブラリだけで暴走を止める手段は執筆時点では確認できていません。JavaでのReDoS対策は、パターンの書き換えと入力長の制限、そして必要ならRE2のJavaバインディングの採用が中心になります。

Python標準の re モジュールは3.11で、アトミックグループ (?>...) と所有格量化子 *+、++、?+、{m,n}+ をサポートしました。これらは失敗時に戻る経路を減らせますが、線形時間の保証ではなく、reのドキュメントにタイムアウトの機能は記載されていません。タイムアウトが要る場合は、re と互換のAPIを持つサードパーティの regex モジュール(照合関数に秒単位の timeout 引数があり、超過すると TimeoutError)や、RE2のPythonバインディングである google-re2(re モジュールの置き換えを掲げ、後方参照と先読みは非対応)が選択肢になります。

Rubyは3.2で、メモ化による照合アルゴリズムの改善を入れました。リリースノートは、実験では約90%の正規表現照合が線形時間で完了するようになった一方、入力長に比例したメモリを消費し得ること、後方参照や先読みを含む式や巨大な固定回数の繰り返しには適用できないことを説明しています。適用できない式のために Regexp.timeout= でグローバルなタイムアウトを、Regexp.new の timeout: キーワードで個別のタイムアウトを設定でき、超過すると Regexp::TimeoutError が上がります。Ruby 3.4のRegexpドキュメントは、正規表現のソースか対象文字列が信頼できない入力に由来する場合はタイムアウトを設定するのが賢明だと述べ、Regexp.linear_time? で線形時間の最適化が効く式かどうかを確認できます。

PHPは pcre.backtrack_limit(既定1,000,000)と pcre.recursion_limit(既定100,000)でバックトラックの上限を持ち、上限に達した照合は preg_match などが false を返し、preg_last_error でそれぞれ PREG_BACKTRACK_LIMIT_ERROR と PREG_RECURSION_LIMIT_ERROR として確認できます。CWE-1333もこの設定を緩和策として挙げていますが、上限を上げ過ぎるとスタックを使い切ってクラッシュする旨がPHPマニュアルに書かれているので、上限を上げる方向での調整は避けます。

JavaScriptは事情が複雑です。V8は2021年1月のブログで、既存のIrregexpに加えて、入力長に線形の実行を保証する実験的な非バックトラックエンジンを v8.8 から搭載したと発表しました。--enable-experimental-regexp-engine-on-excessive-backtracks フラグで、バックトラックが過剰(--regexp-backtracks-before-fallback の既定は50,000回)になった照合を新エンジンにフォールバックさせられ、--enable-experimental-regexp-engine フラグで非標準の l(linear)フラグ付き正規表現を新エンジンで実行できます。2021年の発表時点では、後方参照、先読みと後読み、大きいまたは深く入れ子の有限回繰り返し、u や i フラグを含むパターンは対象外とされていました。その後、後読みは条件付きで扱えるようになっており、Node.js v24.11.0(V8 13.6)に同梱されたV8のソース(experimental-compiler.cc)では、キャプチャグループを含まない後読みは新エンジンで扱い、先読みとキャプチャを含む後読みは --experimental-regexp-engine-capture-group-opt(既定で無効)を付けた場合だけ扱う実装になっています。後方参照は引き続き非対応で、許可されるフラグも g、y、m、s、l に限られます。手元でも --enable-experimental-regexp-engine を付けたNode.js v24.11.0で new RegExp("(?<=a)b", "l").test("ab") は true を返し、先読み、後方参照、u や i フラグ付きの式は「Cannot be executed in linear time」として拒否されました。いずれも既定では無効の実験的機能です。Node.jsの公式の「Security Best Practices」はDoS(CWE-400)の項でソケットのエラー処理やタイムアウトを扱っていますが、執筆時点ではReDoSに固有の項目はありません。実務では、パターンの書き換え、入力長の制限、eslint-plugin-regexpなどによる静的検出、そして必要ならRE2のNode.jsバインディングである node-re2(標準のRegExpを模倣する置き換えで、後方参照と先読みは非対応)の採用が中心になります。

Microsoft Learnの「Regular expression options」は、.NET 7で導入された RegexOptions.NonBacktracking がバックトラックを使わず、入力長に線形の処理時間を保証して壊滅的なバックトラックを避けると説明しています。RightToLeft や ECMAScript と併用できず、アトミックグループ、後方参照、バランシンググループ、条件、先読みと後読み、\G アンカーは使えないこと、ループ内のキャプチャは最後の値だけを提供することを記しています。また、.NETの正規表現エンジンはパターンが信頼できることを前提としており、NonBacktracking は高価な入力から守るものであって悪意あるパターンから守るものではないと警告しています。

V8のブログ(2021年1月11日)は、v8.8から、既存のIrregexpに加えて対象文字列の長さに線形の実行を保証する実験的な非バックトラックエンジンを搭載したと説明しています。--enable-experimental-regexp-engine-on-excessive-backtracks で過剰なバックトラック時のフォールバックを有効にでき、--regexp-backtracks-before-fallback N(既定50,000)で過剰とみなす回数を指定できること、--enable-experimental-regexp-engine で非標準の l フラグを認識させると常に新エンジンで実行されること、後方参照、先読みと後読み、大きいまたは深い入れ子の有限繰り返し、u や i フラグを含むパターンはフォールバックの対象外であることを記しています。

コード例で見る危険な書き方と安全な書き換え#

CWE-1333が例に挙げる (\w+\s?)*$ は、「空白で区切られた単語の並び」を検証しようとした典型的な形です。\s? が省略可能なため、\w+ を何個に区切るかが曖昧で、末尾に ! のような受理されない文字を置くと指数的にバックトラックします。JavaScriptで危険な例と書き換えを並べます。

// 危険: 入れ子の量化子。区切りの空白が省略可能なので単語の切り方が曖昧
const unsafe = /^(\w+\s?)*$/;

// 安全: 受理する形式を「半角スペース1個で区切った単語の並び」に限定し、切り方を一意にする
const safe = /^\w+( \w+)*$/;

const attack = "a".repeat(30) + "!";
// unsafe.test(attack) は入力長に対して指数的に時間がかかる
// safe.test(attack) はすぐに false を返す

書き換え後の ^\w+( \w+)*$ では、\w+ が貪欲に単語文字を取り切った後、次の反復は必ず空白で始まらなければならないので、単語の切り方は一通りしかありません。失敗するときも、\w+ が一文字ずつ返す試行が入力長の回数だけ起きるだけで、指数的にはなりません。ただし、この書き換えは受理する形式を限定した例です。元の式が受理していた空文字、タブ区切りの a\tb、末尾に空白が付いた a は、書き換え後は拒否されます。手元のNode.js v24.11.0でも、これらの入力は元の式で true、書き換え後で false になりました。元の受理範囲を維持する必要があるなら、区切りの文字種や末尾の扱いを仕様として決めてから式を組み立て、受理と拒否の両方をテストで確認します。

メールアドレスの検証で見かける形も同じ手で直せます。

// 危険: 区切り記号が省略可能で、[a-zA-Z0-9]+ の切り方が曖昧
const unsafeEmail = /^([a-zA-Z0-9])(([-.]|[_]+)?([a-zA-Z0-9]+))*@/;

// 安全: 受理する形式を「英数字の塊と区切り記号1文字の交互」に限定し、塊の切り方を一意にする
const safeEmail = /^[a-zA-Z0-9]+([-._][a-zA-Z0-9]+)*@/;

こちらも受理範囲を限定した例で、元の式が受理する a__b@ のようにアンダースコアが連続する入力は、書き換え後は拒否されます。

Pythonでは、3.11以降で使える所有格量化子が緩和策になります。所有格量化子はいったん取った文字を返さないため、失敗したときに切り方を変えて再試行する経路がなくなります。

import re

# 危険: 内側の a+ が取った文字を返しながら切り方を総当たりする
unsafe = re.compile(r"^(a+)+$")

# 緩和: 所有格量化子 a++ は取った文字を返さないので、切り方は一通りになる
# Python 3.11 以降で利用可能
possessive = re.compile(r"^(a++)+$")

data = "a" * 30 + "!"
# unsafe.match(data) は数秒から数十秒かかる
# possessive.match(data) は即座に None を返す

手元のPython 3.13.7では、所有格量化子版に30文字の攻撃入力を与えたときの照合が0.1ミリ秒未満で終わりました。ただし所有格量化子は意味を変えることがあります。a++a は、a++ がすべての a を取って返さないため、どんな入力にも一致しません。書き換えたら、受理すべき入力を受理し、拒否すべき入力を拒否することをテストで確認します。

パターンの書き換えで曖昧さを消せない、あるいは既存コードのすべての正規表現を短期間に点検できない場合の最後の砦がタイムアウトです。Node.jsの標準には正規表現のタイムアウトがないため、照合を Worker スレッドに隔離し、時間内に終わらなければ Worker を止める形で打ち切ります。

// regexTestWithTimeout.mjs
// 照合を Worker に隔離し、timeoutMs 以内に終わらなければ Worker を止めて打ち切る
import { Worker } from "node:worker_threads";

const workerSource = `
  const { parentPort, workerData } = require("node:worker_threads");
  const { source, flags, input } = workerData;
  parentPort.postMessage(new RegExp(source, flags).test(input));
`;

export function regexTestWithTimeout(source, flags, input, timeoutMs) {
  return new Promise((resolve, reject) => {
    const worker = new Worker(workerSource, {
      eval: true,
      workerData: { source, flags, input },
    });
    const timer = setTimeout(() => {
      worker.terminate();
      reject(new Error("regex match timed out"));
    }, timeoutMs);
    worker.once("message", (result) => {
      clearTimeout(timer);
      resolve(result);
    });
    worker.once("error", (err) => {
      clearTimeout(timer);
      reject(err);
    });
  });
}

このやり方には限界があります。タイムアウトまでの間はCPUを消費し続けるので、攻撃者が並列に送ればその分のCPUは奪われますし、Worker の生成には固定の費用がかかるので、リクエストごとに生成するのではなくプールを持つ設計が向きます。あくまで「無限に占有される」事態を「上限つきの占有」に変える緩和策であり、パターンの書き換えや入力長の制限と組み合わせて使います。

Pythonでタイムアウトが必要なら、regex モジュールの timeout 引数が簡潔です。

import regex

def is_valid(data: str) -> bool:
    try:
        return regex.fullmatch(r"[a-z0-9]+(-[a-z0-9]+)*", data, timeout=0.5) is not None
    except TimeoutError:
        # 照合が 0.5 秒を超えたら不正な入力として扱い、監視に記録する
        return False

利用者の入力を正規表現の一部として組み立てる場合は、必ずエスケープします。OWASPのページが挙げる「利用者名がパスワードに含まれていないか確かめるために、利用者名から Regex を作る」コードは、利用者名に evil regex を書かれた時点でパターンそのものが注入されます。文字列の包含判定なら正規表現は不要で、includes や in で済みます。どうしても正規表現に埋め込むなら、JavaScriptは RegExp.escape(ECMAScript仕様に含まれ、MDNはBaseline 2025として2025年5月以降の最新ブラウザで利用できると記載しています。手元のNode.js v24.11.0でも利用できました)、Pythonは re.escape で特殊文字を無効化してから埋め込みます。

// 危険: 利用者入力がそのままパターンになる
const bad = new RegExp(userName).test(password);

// 安全: そもそも正規表現を使わない
const good = password.includes(userName);

// 正規表現に埋め込む必要があるなら、エスケープしてリテラルとして扱う
const escaped = new RegExp(RegExp.escape(userName), "i").test(password);

エスケープはパターン注入を防ぎますが、固定のパターン側にある曖昧さは消えません。二つは別の問題として両方に手を打ちます。

静的検出ツール#

目視で曖昧さを見抜くのは慣れても難しいので、機械的な検出をCIに組み込みます。ツールには大きく、パターンをオートマトンとして解析して最悪計算量を判定する方式と、実際に攻撃入力を生成して照合時間を測るファジング方式があり、精度と速度が異なります。

recheckは「信頼できるReDoSチェッカー」を掲げ、後方参照や先読みを含む実用的な正規表現機能に対応し、ファジングと静的解析を組み合わせた検出アルゴリズムをライブラリとして提供しています。ESLintで使う eslint-plugin-redos は redos/no-vulnerable の一つのルールを持ち、checker オプションで auto、automaton、fuzz を選べ、解析の timeout(既定10,000ミリ秒)や、許容する計算量を permittableComplexities で指定できます。

eslint-plugin-regexp の no-super-linear-backtracking は、指数的または多項式的なバックトラックを禁止するルールで、recommended 設定に含まれ、多くの場合 --fix で自動修正できます。report オプションの既定 certain は、拒否される接尾辞が存在すると証明できる確実な場合だけを報告し、potential にすると可能性のある場合も報告します。ドキュメント自身が、実装は簡易的な検出方法で単純な場合しか検出できないと断っているので、recheckのような重い解析と役割を分けて使うのが実務的です。

CodeQLの js/redos クエリは、繰り返しの中に曖昧な部分式を持つ正規表現を検出し、曖昧さを取り除くか、照合する文字列が十分に短いことを保証するよう推奨しています。GitHubのコードスキャンを使っているなら、追加の設定なしに指摘が上がります。

safe-regex は古くから使われている軽量なチェッカーで、スター高さが1を超える式を危険とみなします。READMEには「偽陽性と偽陰性の両方がある」と明記されており、スター高さだけを見る仕組み上、.*.*=.* のような隣接する量化子の取り合いは検出の対象外です。ないよりはましですが、これだけで安全と判断しないでください。

eslint-plugin-regexp の no-super-linear-backtracking のドキュメントは、このルールが指数的および多項式的なバックトラックを禁止するもので、recommended 設定に含まれ、--fix による自動修正に対応すると説明しています。攻撃文字列が接頭辞、繰り返される空でない文字列、拒否される接尾辞の三つから成ること、report オプションの certain(既定)は拒否接尾辞の存在を証明できる場合だけを報告し、potential は可能性のある場合も報告することを記し、実装は簡易的な検出方法で単純な場合しか検出できないと断っています。

recheckの公式サイトは、recheckを信頼できるReDoSチェッカーと位置づけ、後方参照や先読みを含む実用的な正規表現機能に対応すること、ファジングと静的解析を組み合わせた検出アルゴリズムを実装していること、ライブラリとして公開されていてアプリケーションに組み込めることを説明しています。ESLintプラグインの利用ページは、eslint-plugin-redos が redos/no-vulnerable ルールを提供し、checker(auto、automaton、fuzz)、timeout(既定10,000ミリ秒)、permittableComplexities、ignoreErrors、cache のオプションを持つと記しています。

設計上の対策#

エンジンとパターンの対策に加えて、アプリケーションの設計で条件を崩す手立てがあります。CWE-1333が挙げる緩和策に沿って並べます。

正規表現は入力検証の道具の一つですが、検証そのものが攻撃面になるのがReDoSの皮肉なところです。入力検証を「受け入れる文字種と長さを先に決める」順序で設計しておくと、正規表現に渡る入力の長さが自然に絞られ、ReDoSの三条件のうち「入力が十分に長くできる」が崩れます。入力検証とエスケープの全体像は、次の記事で整理しています。

あわせて読みたい

入力バリデーションと出力エスケープの原則。入口で検証し、出口で文脈別にエスケープする

コードレビューのチェック観点#

レビューで正規表現を見るときの観点を、質問の形にまとめます。

1. その正規表現に、外部から来た文字列(リクエストパラメータ、ヘッダ、ファイル内容、他システムからのデータ)が渡されますか。渡されないなら優先度は下がります。
2. 量化子付きグループの内側に、別の量化子や選択肢がありますか。あるなら、内側の要素の切り方が一通りに定まるかを確かめます。
3. 隣り合う量化子付き要素が、同じ文字を受理できますか。\w+\s?\w+ や .*.* の形は取り合いが起きます。間に省略できないリテラルの区切りを置けないか検討します。
4. 選択肢の各枝は、同じ文字列を受理しますか。(a|aa)+(aa を1回でも2回の反復でも受理できる)、(\d|[0-9a-f])、(.|\s) のような重なりは、枝の一方を狭めて排他にします。
5. 受理されない入力を与えたとき、何が起きますか。テストには「一致する入力」だけでなく、「長さ上限ぎりぎりで末尾に一文字だけ不正な文字を足した入力」を含め、照合時間を測ります。
6. 入力長の上限は、その正規表現の前で保証されていますか。上限がリクエストの入口で決まっているなら、そのことをコメントで明示します。
7. エンジンは何ですか。RE2系や NonBacktracking なら一回の照合は入力長に線形に収まるため曖昧さの指摘は主に性能問題ですが(Rustの find_iter のように一致を全件列挙する場合は最悪で入力長の2乗まで増え得ます)、バックトラック型ならセキュリティ問題として扱います。
8. 正規表現の文字列を実行時に連結していませんか。連結しているなら、連結される値の出所とエスケープの有無を確認します。
9. リンタや静的解析の指摘を抑止(disable コメント)していませんか。抑止するなら理由を残し、入力長や信頼境界で守られていることを説明できるようにします。
10. その処理は本当に正規表現が必要ですか。文字列関数や専用パーサで書けるなら、そちらを提案します。

観点3と4は、正規表現を「動く」かどうかで見るレビューでは見落とされます。受理すべき入力を受理するテストは通るからです。ReDoSは主に「拒否すべき入力を拒否するのにかかる時間」の問題なので、レビューでも失敗時の挙動に目を向ける必要があります。

誤解しやすい点#

「入力は数十文字だから大丈夫」という判断は、指数的な式には通用しません。手元の計測では、^(a+)+$ に対して26文字で1秒を超えました。利用者名の上限が64文字なら、指数的な式にとっては十分すぎる長さです。入力長の上限が効くのは、上限がその式の増え方に対して十分に小さい場合だけで、指数的な式は上限で守るのではなく書き換えます。

「アンカー(^ や $)を付けているから安全」も誤りです。^(a+)+$ はアンカー付きで危険な式の代表ですし、逆にアンカーがないと開始位置をずらす再試行が加わってさらに悪化します。アンカーは受理する文字列を絞るためのもので、バックトラックの量とは別の話です。

「マッチするテストが通ったから安全」は、成功時は最初の経路で終わることが多く、失敗時の挙動を何も検証していません。しかも成功時なら安全というわけでもなく、Cloudflareの .*.*=.* は一致する入力でもステップ数が急増します。「短い式だから安全」も同じ例が示すとおり当てになりません。逆に長い式でも、各部分が排他的に区切られ、かつ ^ などで開始位置が固定されていれば、照合時間は入力長に比例する程度に収まります。開始位置を固定しない検索では、区切りに曖昧さがなくても位置ごとの再試行で二次的に増えることは上で見たとおりです。

「タイムアウトを入れたから解決」も部分的です。タイムアウトは一回の照合の上限を決めるだけで、上限いっぱいまでCPUは奪われます。並列に送られれば、上限がある分だけ攻撃の効率が下がるものの、ワーカーの枯渇は起き得ます。タイムアウトは書き換えができるまでの保険、または見落としに対する最後の砦として位置づけます。

「RE2に替えたから何でも安全」も過信です。RE2系の保証は一回の検索の入力長に対する線形性で、パターンの大きさに対する保証ではありませんし、Rustのregexのように全件列挙の反復検索では最悪で入力長の2乗になる例外もあります。Rustのregexドキュメントが size_limit を案内し、.NETのドキュメントがパターンは信頼できるものという前提を明記しているように、利用者が書いた正規表現を実行する機能では、パターンの大きさや複雑さにも上限が要ります。

「所有格量化子やアトミックグループで直せば元と同じ意味」も注意が要ります。所有格化は取った文字を返さないので、a++a のように受理範囲が変わる場合があります。書き換え後は、受理と拒否の両方のテストを通してから差し替えます。

まとめ#

ReDoS(CWE-1333)は、バックトラック型の正規表現エンジンが、主に照合に失敗する入力に対してあり得る経路を総当たりで試すことで、入力長に対して指数的または多項式的な時間を使う欠陥です。入れ子の量化子、重なり合う選択肢の繰り返し、隣り合う量化子の取り合いという三つの形が曖昧さを生み、2019年のCloudflareと2016年のStack Overflowの障害が示すように、攻撃がなくてもサービス全体を止め得ます。

対策の軸は二つです。一つは曖昧さを消すこと、すなわちパターンを排他的な区切りで書き換えるか、Go、RE2、Rust、.NET NonBacktracking のように線形時間を保証するエンジンを使うことです。もう一つは条件を崩すこと、すなわち入力長の上限を入口で決め、利用者入力からパターンを組み立てず、タイムアウトやバックトラック上限で無限を有限に変えることです。静的検出ツールをCIに組み込み、レビューでは「拒否すべき入力を拒否するのにかかる時間」に目を向ければ、一行の正規表現が全体障害に化ける事態は避けられます。

ReDoSはOWASP Top 10でいえば、入力検証の不備やセキュアでない設計の一部として扱われる問題です。Webアプリケーション全体の弱点の地図と照らし合わせるには、次の記事が役に立ちます。

あわせて読みたい

OWASP Top 10とは。開発者が押さえるべきWebの代表的リスクと対策を一気に理解する