正規表現がなぜこんなに遅い？破滅的バックトラッキングと ReDoS

動く正規表現がひとつある。投げつけたテストはすべて通り、リリースされ、数週間は誰も何の異常にも気づかない。ところがある日、少し長めの入力がやってくる——貼り付けられた段落、壊れた URL、長い空白がずらりと並んだログ行——そしてタブが固まる。CPU が 100% に張り付く。サーバー上なら、Node.js のプロセス全体がリクエストに応えなくなる。エラーは何も投げられていない。正規表現は、技術的には今も「正しい」。ただ、終わらないだけです。

これがどういう種類の「遅い」なのか、まずはっきりさせましょう。遅い正規表現がみな同じ生き物なわけではないからです。ただの多項式的な遅さ——たとえば二次なら、入力が倍になれば手間はおよそ四倍、うっとうしいが致命的ではない——もあれば、入力そのものが巨大なだけ、あるいはタイトなループの中で何度も呼んでいるだけ、というものもある。この記事はそれらの話ではありません。それらはふつうの最適化です。ここで扱うのは、もっと質の悪い一群——入力がほんの少し伸びただけで実行時間が爆発する類です。仕事量が指数的に増え、数文字足すだけでマイクロ秒が分になり、やがて永遠になる。これには名前があります。破滅的バックトラッキング（catastrophic backtracking）。そして攻撃者がその入力を意図的に送り込んでサービスを落としにかかると、それは ReDoS（正規表現によるサービス拒否）攻撃と呼ばれます。

救いなのは、これがまったく不可解ではないことです。バックトラッキング型エンジンの動き方から素直に導かれる——本シリーズの第一回で、そのエンジンを一から解き明かしました。エンジンが貪欲に食べ、行き詰まったらバックトラックすると分かっていれば、破滅的バックトラッキングはその同じ仕組みが暴走したものにすぎません。この記事はまさにそこから続きます——何が仕事量を爆発させるのか、危険な形をどう見抜くのか、それらが実際のコードのどこに潜むのか、そして——JavaScript がほとんど何のガードレールも用意していない以上——どう書き換えて抜け出すのか。

爆発はどこから来るのか

第一回のエンジンモデルを一文にまとめます。バックトラッキング型エンジンは、貪欲な量指定子がマッチ全体を完成させられないとき、巻き戻して別の分け方を試す——食べた文字を返し、別の前進路を探し、あらゆる可能性を試し尽くすまで諦めません。破滅的バックトラッキングとは、その「あらゆる可能性」が天文学的な数になってしまう場合のことです。

教科書どおりの引き金はネストした量指定子——繰り返すグループが、それ自体さらに繰り返される形です。

(a+)+$

字義どおり読めば、これは冗長です。「（一つ以上の a からなる連なり）が一つ以上、文字列末尾にアンカーされる」は、素朴な a+$ とまったく同じ文字列の集合を表します。ところがエンジンは両者が等価だと知りません。そしてこの冗長さこそが命取りになる。内側の a+ と外側の + はどちらも同じ a を取り合えるため、a の連なりは複数のやり方でグループに切り分けられる——そしてエンジンは、そのすべてを試してからでないと負けを認めない義務があると感じるのです。

わずか四文字の aaaX で動きを追ってみましょう。エンジンの初手は貪欲です。内側の a+ が三つの a を一気にひとつのグループ (aaa) として飲み込む。ここで $ が欲しいのに、カーソルは X の上に止まっている——失敗。そこでバックトラック。内側の a+ が a を一つ返して (aa) になり、外側の + がここぞと二つ目のグループを開き、内側の a+ が余った a を拾って (aa)(a) を作る。$ を試す、まだ X、失敗。もう一度バックトラック——(a)(aa)、失敗。(a)(a)(a)、失敗。三つの a の四通りすべてのグループ分けを試して、すべて失敗した後で、ようやくエンジンはこの開始位置を諦められる——そして一文字右へずれ、この責め苦を最初からやり直すのです。

三つの a に四通りのグループ分けは偶然ではありません。n 個の a には、順序つきグループへの分け方が 2ⁿ⁻¹ 通りある。そしてあの致命的な $——X の前では決して成立しない——が、エンジンに、諦める前にその一つ残らずを歩ませます。a が 10 個で 512 回、20 個で 50 万回超、30 個で 5 億回超。だから固まり方は「じわじわ」ではなく「一瞬」なのです。a を一つ足すごとに仕事量はおおよそ倍になる。これは遅いのではなく指数的——そして指数曲線は、本当に立ち上がる直前まで、ずっと平らに見えます。

どれくらいの長さで臨界に達するかを探すのはやめましょう。それはブラウザ、ハードウェア、エンジンの実装で変わります。大事なのは曲線の形——そしてもう一つ、これを性能上の癖から武器へ変える性質です。牙をむくのは、失敗するマッチのほうです。 この種のパターンはテストでは完璧に速く見えます。テストに使う入力はさっと安くマッチするからです。エンジンを完全な指数探索へ引きずり込むのは、あと一歩で成功しかける入力——ほぼ最後までマッチして、最後の一歩で失敗する入力です。攻撃者はこれを知っている。だから ReDoS のペイロードは「惜しくもマッチする」形に作り込まれます——長い a の連なり、そしてそれを最後の最後で台無しにする一文字。

危険な形、ひと目で

毎回エンジンを頭の中で走らせる必要はありません——危険なパターンの輪郭は、ほんの数種類です。ただ、どれくらい危険かは正確に区別する価値があります。まったく異なる二本のコスト曲線が「ReDoS」の一語にまとめて放り込まれていて、本物の爆弾はそのうち一方だけだからです。

指数的な形——本物の爆弾。 一文字足すごとにコストがおおよそ倍になる、上で追ったとおりのものです。その特徴は、繰り返しの上に繰り返しが乗り、しかも両層が同じ文字にマッチできること。だからひと連なりが指数的な通り数に分割できてしまう。

(a+)+$       (a*)*$       (\w+)*$       ([\w.]+)+@

量指定子の下の重なり合う選択肢は、同じ病気が姿を変えたものです。二つの枝が同じテキストにマッチできると、各文字に複数の経路が生まれ、外側の量指定子がそれを掛け合わせます。

(a|a)*$      (\w|\d)*$

\d は \w の部分集合なので、(\w|\d)* は同じ数字にマッチする経路を二つ持つ——最終的に失敗する長い数字列に対しては、それが 2ⁿ 経路になります。（枝は同じ文字の上で重なっていなければなりません。(a|ab)* のように枝が消費する長さが違うものは、より微妙な、たいていは多項式的なケースであって、確実な爆弾ではありません。）

多項式的な形——遅い、しかしまれにしか悪用できない。 隣り合う無際限の量指定子や、存在しない何かを探して走り回る .* は、指数的に爆発はしません——それでも O(n²) 以上を焼き、十分に大きな入力ではページを固められます。

.*.*=        \s*.*\s*$        a.*b.*c

これらも直すべきですが、深刻さの階級が違います。この線を知っておけば、.* を見るたびに「指数的だ」と叫ばずに済みます。

遅延に変えても、ここでは何ひとつ防げません。 「貪欲を遅延に切り替える」はよく性能対策として出回りますが、対策ではありません。遅延はエンジンが分け方を試す順序を裏返すだけ——長いほうからではなく短いほうから——で、失敗するマッチではやはりそのすべてを訪れます。(a+?)+$ は (a+)+$ とまったく同じく指数的です。*? を安全機能だと勘違いしないこと。

一つの但し書きが両方の階級を貫きます。危険な形が実際に牙をむくのは、失敗するマッチのときだけ。 悪用できるかどうかは、完全探索を強いる入力が存在するか——ふつうは繰り返す長いプレフィックスに、アンカーや必須のサフィックスを崩す一文字が続くもの——と、攻撃者がその入力をどれだけ長くできるかにかかっています。形はリスクの存在を教え、失敗経路と入力長がどれほど悪いかを決めるのです。

その違いを体で感じたいなら、これらを正規表現テスターに落とし込み、その ReDoS 解析に判定させてください——バックグラウンドで走り、危険な形をあなたの代わりに指摘します。やってはいけないのは、長い攻撃文字列を貼り付けてページが固まるのを眺めること。マッチはブラウザのメインスレッドで走るので、それで達成できるのは、解析器がとうに証明した結論を証明するために自分のタブを固めることだけです。

実際にどこに潜んでいるか

本番コードにわざわざ (a+)+$ と書く人はいません。破滅的バックトラッキングが出荷されてしまうのは、それがまったく無難に見えるパターンの中に潜むからです——とりわけバリデータの中に。信頼できないユーザー入力に向けて走らせる正規表現、まさにいちばん潜んでほしくない場所です。

メールと URL のバリデーション。 手書きのアドレスバリデータは、実在する ReDoS の CVE をずらりと背後に抱えています。そして問題を起こすものは同じ形を共有している——中身が、それを包む繰り返しと重なり合う、繰り返しグループです。ローカル部のチェックを ^([a-zA-Z0-9]+[._-]?)+@ と書いたとしましょう。読むと丁寧に見えます——「英数字、任意の区切り、それを繰り返す」。ところが区切りも @ もない長い文字列を与えると、任意の [._-]? は毎周空にマッチし、全体が ([a-zA-Z0-9]+)+ に崩れ落ちます——上で見た指数的な形が、変装しているだけなのです。（あえて無害そうに見える ^([a-zA-Z0-9]+\.)+[a-zA-Z]{2,}$ は、このバグではないことに注意。内側の文字クラスは . にマッチできず、外側の各繰り返しは必ずリテラルの . を消費するので、同じ文字を分け直す余地がありません。効いてくるのは重なりであって、「ネストした + があること」そのものではないのです。）

空白を繰り返すパターン。 ここは歩を緩める価値があります。恐ろしげな trim も、たいていは無事だからです。日常的な ^\s+|\s+$ は ReDoS リスクではありません——アンカーされた単純な連なりが二つ、ネストも重なりもない。安心して使い続けてください。危ないのはネストした形——(\s+)+、(\s*)*、あるいは外側にもう一つ量指定子を付けた (\s|\t)+ で、これが重なりを呼び戻します。空白の正規化はユーザーが送るあらゆるものに走りがちなので、ネスト版は格好の標的です——とはいえ、慌てて普通の trim まで消さないこと。

(.*,)* や繰り返しグループを含むもの全般——カンマ区切りのリスト、一連のキー値ペア、繰り返す HTML 属性、繰り返しセグメントを持つパスの解析。「（それ自体が一つ以上を含む何か）の一つ以上」と書いた瞬間、手を止めて、決め手となる一点を確かめましょう。内側と外側が同じ文字を消費できるか。もし各繰り返しがそれぞれの区切りに固定されていたり、入力が長くなりようがなかったりするなら、最悪でも測っておくべき性能コストであって、爆弾ではありません。重なりが本物で、かつ長い失敗入力があり得るときに初めて、本当の ReDoS 候補になります。

パターンの背後のパターンはこうです。バックトラック爆弾を抱えている可能性がもっとも高い正規表現は、まさにあなたが信頼できない入力に向けて走らせるもの——バリデータこそ、ネストした量指定子が自然に湧く場所だからです。「脆弱な形」と「攻撃者が操れる入力」のこの重なりが、ReDoS の脅威のすべてです。

直し方：書き換えるしかない、JavaScript は助けてくれないから

一部の正規表現エンジンは、バックトラッキングを直接止めるスイッチを渡してくれます。アトミックグループ (?>...) は「これをマッチしたら、二度と返すな」とエンジンに告げ、独占的量指定子（possessive quantifier） a++、a*+ は単一の量指定子に同じことをします。曖昧な部分にそれらを向ければ、指数探索は源から締め出されます。

そして、脳裏に焼きつける価値のある厳しい制約がこれです。JavaScript にはどちらもない。 アトミックグループなし、独占的量指定子なし、今日に至るまで。（Java、PCRE、Ruby、.NET はすべて持っています。JS が目立つ例外です。）だから JavaScript で手にできる唯一のてこは、曖昧さがそもそも存在しない形にパターンを書き換えること——重なりを取り除けば、バックトラックすべきものが何もなくなる。以下が道具箱です。おおよそ「それが答えになる頻度」の順に並べました。

1. .* や .*? の代わりに否定文字クラスを使う。 これが最も費用対効果の高い一手で、第一回がずっと前振りしていたものです。[^"]* は引用符を越えられないので、"[^"]*" と書けば中身にマッチする道はただ一つ——行き来して探ることがありません。".*"（貪欲すぎ：.* は閉じ引用符まで食べて、返さざるを得なくなる——ほんの線形のバックトラックで、それ単体では破滅ではありません）と "[^"]*"（曖昧なし、固い境界）を比べてみてください。それ単体での利点は精度と正しさ。そして本記事にとっての本当の見返りは、固い境界なら、別の量指定子の中にネストされた途端に指数化するあの重なりを作りようがない、という点です。ある連なりを終わらせる文字を名指しできるなら、「何でも、遅延で」ではなく「その文字以外の何でも」にマッチさせましょう。

".*?"    →    "[^"]*"
\w+@.*   →    \w+@[^\s@]+

二つめの例は無条件の等価ではありません——\w+@.* と \w+@[^\s@]+ は同じものにマッチしません。[^\s@]+ は末尾を「空白も二つめの @ も含まないドメイン部分」へと意図的に狭めており、たいていはそれこそがあなたの本当に欲しかったものです。どの否定集合を選ぶかは、バックトラックを避けるためだけでなく、本当の意図に合わせて決めましょう。

2. 選択肢を互いに排他にする。 枝が重なっているなら、各文字にちょうど一つの枝だけがマッチするよう組み直します。(\w|\d)* は単に \w* になる（\d はもともと \w の中だから）。重なりが敵、それを消す。

3. アンカーで開始位置を削る——ただし限界を知る。 ^/$ を適切な場所に、あるいは繰り返しグループの間に具体的な区切りを足すと、エンジンがあらゆる開始位置でマッチ全体をやり直すのを止められ、外側の線形あるいは多項式の因子が消えます。それができないのは、内側の指数的爆発を解くこと——(a+)+$ はもともとアンカーされていて、その $ こそが指数的失敗を強いている当の元凶です。アンカーは多項式のケースを助けますが、ネストした重なりの爆弾に対する解毒剤ではありません。

4. 入力を縛る——修復ではなく多層防御として。 ビジネス層で硬い長さ上限を設けること——正規表現が入力を見る前に、n 文字を超えるものを弾く——は本当に持っておく価値があり、{1,64} を + の代わりに使えばネストの深さに天井を付けられます。しかし、上限を脆弱性の除去と取り違えないこと。{1,64} でもなお最大 2⁶⁴ 経路を許し、それは天文学的に走り切れません。上限は爆発の半径を封じ込めるだけ——爆弾を実際に取り除くのは、重なりの排除です。

5. 正規表現をやめる。 仕事によっては——ネストした構造、まっとうな文法らしきもの、HTML や JSON の解析——正規言語ではなく、そこへ正規表現を無理に当てはめることこそ、そもそもこうした怪物を生む原因です。文字列を手で回すループ、文字列の区切りを渡す String.split（正規表現を渡す split(/…/) ではなく——そちらは正規表現を実行します）、あるいは本物のパーサのほうが、しばしばより単純で、より速く、そのうえこの種のバグ全体に免疫があります。

書き換えるたびに、二つを確かめましょう。マッチすべきものを今もすべてマッチするか（回帰は「より安全な」書き換えに潜むのが大好きです）、そして ReDoS チェックにもう引っかからないか。どちらも正規表現テスターに貼れば一発です——古いパターンと新しいパターンを並べ、同じ「惜しくもマッチする」入力に当ててください。

セキュリティの視点：なぜこれは単なるバグではなく DoS なのか

なぜ破滅的バックトラッキングが「性能上の厄介事」から「セキュリティ脆弱性」へと昇格するのか、はっきり述べる価値があります。その飛躍は、サーバーの動き方に固有のものだからです。

Node.js は JavaScript を単一スレッドで実行します。正規表現が破滅的バックトラッキングに入ると、そのスレッドは丸ごと占拠される——譲らず、他のリクエストも捌かず、ただ正規表現エンジンの中で空回りする。だから一つの巧妙な入力は、それを運んだリクエストだけを遅くするのではなく、そのプロセスが相手にしている全ユーザーごと凍らせます。しかもここに棘がある。setTimeout で仕掛けたリクエストのタイムアウトは、あなたを救えません。タイマーのコールバックはイベントループが空いて初めて発火できるのに、暴走中の正規表現こそがそのイベントループを人質に取っている当の相手だからです。Node は走行中の同期的な正規表現を中断できない。占拠されたスレッドは占拠されたまま、マッチが自力で終わるまで——それは実質的に永遠かもしれません。

その爆風がどこまで広がるかは、あなたの配置しだいです。単一プロセスのサーバーは真っ暗になり、一方で複数プロセスやワーカースレッド、接続を切るゲートウェイ側のタイムアウト、加えてレート制限は、その半径を縮めます。それでも核心の非対称は、そのすべてを経てなお生き残る——攻撃の代価はごくわずか、吸収の代価は不釣り合いに大きい——これこそ、ReDoS が人気ライブラリの CVE 報告にこれほど頻繁に現れる理由です。

これはまた、第一回が触れた謎を解きます。なぜ同じ危険なパターンが ripgrep では一瞬で走り、Node では固まるのか。 ripgrep（Rust の regex クレート）や Go の regexp のようなツールは有限オートマトンの上に作られています。これは別のエンジン構造で、マッチをバックトラックのまったくない一回の線形走査に変えます。それらは構造上破滅的バックトラッキングに免疫がある——引き換えに、後方参照のような、本質的にバックトラックを要する機能を落としています。あなたがどちらの種類のエンジンで走っているかが、この脅威がそもそも自分に当てはまるかを決めます。バックトラッキング型のエンジンでは——JavaScript、Python、PCRE、Java——大いに当てはまります。

ここには Node に特有の、実務上の示唆があります。あるパターンがどうしても安全に書き換えられないとき——あるいは、一つ残らず手で正しく直せる自信がないとき——それを組み込みのエンジンではなく線形エンジンで走らせることができます。Google の RE2 はまさにその線形保証を持つ有限オートマトンエンジンで、re2 という npm バインディングは Node で RegExp のほぼそのままの差し替えになります。代価は、本質的にバックトラックを要する機能です。RE2 は先読み・後読み（look-around）を一切サポートせず、後方参照もありません。 その引き換えに、マッチ時間は入力長に対して線形に増え（パターンが複雑なら定数因子が大きくなるだけ）、攻撃者が何を食わせようと、決して指数的にはなりません。信頼できないデータに向けて走らねばならない正規表現には、しばしばこれが正しい取引です。

出荷前に捕まえる

バックトラック爆弾を見つける最良のタイミングは、本番に届く前です。そしてすべてのパターンを目で追う必要はありません。本サイトの正規表現テスターは、あなたのパターンに非同期で ReDoS 解析を走らせます。正規表現を貼れば、脆弱な構造がないかをバックグラウンドで調べる。問題を見つけると、具体的な攻撃文字列——そのパターンを実際に吹き飛ばす入力——を示すので、失敗を鵜呑みにせず目で見られます。そして解析が確たる判定に届かないときは、それもまた、取り繕わずはっきりと伝えます。すべてはあなたのブラウザ内でローカルに走り、パターンはこのページを離れません。

これは煙感知器であって、合格証ではありません。きれいな結果は良い兆しですが、安全の証明ではなく、真の入力規模での実性能テストが依然として最終判断です。このチェックが買ってくれるのは、安く早い捕捉——([a-zA-Z0-9]+[._-]?)+@ が本番のログインフォームを守る役につく前に、それを爆弾だと見抜く機会です。

そのまま使えるチェックリスト

正規表現が固まったとき、あるいはユーザー入力に触れるものを出荷する前に、これを一巡させてください。

1. 走った瞬間に固まり、CPU が張り付く？ それは破滅的バックトラッキングで、普通の遅さではありません。回避策で凌ごうとせず——パターンが指数的なら、書き換えが要ります。
2. まず指数的な形を探す。 (a+)+、(\w+)*、([\w.]+)+、(a|a)*——繰り返しの上の繰り返し、または重なり合う枝で、両層が同じ文字を取り合うもの。これが本物の爆弾です。
3. 次に多項式のもの。 .*.*、\s*.*\s*——隣り合う無際限の量指定子。あるべき姿より遅く、まれに悪用できますが、同じ緊急度ではありません。
4. 遅延を当てにしない。 (a+?)+ は (a+)+ と同じく危険。*? が変えるのは探索の順序であって、その規模ではありません。
5. バリデータをいちばん厳しく見る。 メール、URL、繰り返し空白のパターンは、重なりが潜む場所であると同時に、信頼できない入力が着地する場所です。あなたが気にしている trim が本当にネストしたもの（(\s+)+）なのか、無害な ^\s+|\s+$ なのかを確かめること。
6. 外周に貼るのではなく、重なりを取り除いて直す。 .*? より否定文字クラス（[^"]*）を、選択肢を排他に、仕事が正規言語でないならパーサへ切り替える。アンカーや入力上限は被害の封じ込めを助けますが、ネストした爆弾は解体しません——そして JavaScript にはアトミックグループも独占的量指定子もないので、書き換えに尽きます。どうしても書き換えられないなら、RE2 で走らせる。
7. 書き換えても今もマッチすることを確かめ、それから ReDoS を再チェック。 新旧のパターンを並べ、あの「惜しくもマッチする」入力に当てる。

破滅的バックトラッキングは正規表現の薄暗い一角のように感じられます——それが第一回のあのバックトラッキングエンジンが、いつもどおりのことをしているだけ、ただ回数が多すぎるだけ、と見えるまでは。「貪欲に食べ、行き詰まったらバックトラック」が骨身に染みれば、危険な形はひと目で浮かび上がり、直し方はほとんどいつも同じ静かな一手です。境界をはっきり引き、エンジンに、二度と迷う余地を与えない。