Tech Learning Daily

2026-10-21 (Wed) — 第 96 号
AI が毎朝届ける、ソフトウェア技術の基礎解説
Lang 🌿 基礎 ⏱ 約 7 分

たった 1 行の正規表現なのに、なぜ CPU が 100% に張り付くのか？

あなたも昨日、メールアドレスや URL のバリデーションに正規表現を 1 行書いたはずだ。テストでは一瞬で通ったその 1 行が、本番で 30 文字ほどの入力を受け取った途端にリクエストを数秒止め、CPU を使い切ることがある。入力はたった 30 文字なのに、エンジンはいったい何に時間を使っているのだろうか。

🎯 3 行まとめ
  • JavaScript・Ruby・Python などの正規表現エンジンは「1 つの道を試し、失敗したら分岐点まで戻って別の道を試す」バックトラッキング方式で動く
  • (a+)+ のように同じ文字列を何通りにも区切れるパターンは、マッチに失敗する入力で区切り方を全通り試すため、1 文字増えるごとに処理時間が倍になる
  • Go や RE2 は入力長に比例する時間を保証する代わりに後方参照を捨てている。バックトラッキング型の言語ではパターンの書き換え・入力長の制限・タイムアウトで守る

正規表現エンジンは「試して、だめなら戻る」

多くの言語の正規表現エンジンは、パターンを先頭から順に入力へ当てはめ、選択肢があるたびにひとまず 1 つを選んで先へ進む。途中で行き詰まると、直前の選択肢まで戻って別の選択を試す。この「戻ってやり直す」動作をバックトラッキングと呼ぶ。V8（Node.js と Chrome）の Irregexp、Ruby の Onigmo、Python の re はいずれもこの方式だ。

選択肢を生むのは主に量指定子（*・+・{m,n} のように「何回繰り返すか」を指定する記号）と選択 | である。a+ は「a を 1 回以上」なので、入力に a が 4 つ並んでいれば「4 つ全部取る」「3 つで止める」「2 つで止める」…という選択肢がある。エンジンは貪欲に一番長い取り方から試し、後続が失敗したら 1 つずつ短くしていく。

マッチが成功する入力なら、たいてい最初の数回の試行で終わる。問題はマッチが失敗する入力だ。失敗と言い切るには「どの選択肢の組み合わせでもだめだった」ことを確かめる必要があり、エンジンは組み合わせを全部試し終えるまで答えを返せない。

区切り方が 2 倍ずつ増えるパターン

^(a+)+$ は「a が 1 個以上の塊が、1 個以上続いて行末」という意味で、結果だけ見れば ^a+$ と同じ文字列にマッチする。しかしエンジンにとっては別物だ。外側の + と内側の + が入れ子になっているため、同じ a の並びを「いくつの塊に分けるか」の選択肢が生まれる。

パターン ^(a+)+$  入力 "aaaa!"

 区切り方        末尾との照合
 ────────────────────────────
 (aaaa)        ─▶ ! ≠ $  戻る
 (aaa)(a)      ─▶ ! ≠ $  戻る
 (aa)(aa)      ─▶ ! ≠ $  戻る
 (aa)(a)(a)    ─▶ ! ≠ $  戻る
 (a)(aaa)      ─▶ ! ≠ $  戻る
 (a)(aa)(a)    ─▶ ! ≠ $  戻る
 (a)(a)(aa)    ─▶ ! ≠ $  戻る
 (a)(a)(a)(a)  ─▶ ! ≠ $  失敗
 ────────────────────────────
        ▼
 8 通り全部試して「マッチしない」
 a が n 個なら 2^(n-1) 通り

末尾の ! が $ に合わないので、どの区切り方でも必ず失敗する。人間には「区切り方を変えても末尾の ! は変わらない」と分かるが、エンジンはそれを推論しない。a が n 個なら区切り方は 2n-1 通りあり、a が 1 個増えるたびに試行回数が倍になる。実際、筆者の環境（Node.js 22）で /^(a+)+$/.test("a".repeat(n) + "!") を n ごとに別プロセスで 1 回ずつ測ると、n=20 で約 40 ミリ秒、n=26 で約 2.4 秒だった。あと 10 文字足せば 40 分を超える計算になる。

このように入力長に対して指数的に試行が増える現象を破滅的バックトラッキングと呼び、攻撃者がこれを狙ってサーバーの CPU を食い潰すことを ReDoS（Regular expression Denial of Service）と呼ぶ。入れ子の量指定子のほか、(a|a)* や (\w|\d)+ のように選択肢同士が同じ文字を取り合う形、.*.* のように何でも取る部分が隣り合う形も同じ構造を持つ。

🍱 たとえるなら

一列に並んだ生徒を「班」に区切り、班分けが決まるたびに列の最後尾を確認して「名札をつけているか」を調べる先生だ。最後尾の生徒が名札を忘れていれば、どう班を分けても不合格になる。それでもこの先生は班分けのパターンを 1 つずつ作り直しては最後尾を見に行く。生徒が 1 人増えるたびに班分けのパターンは倍になり、最後尾を見に行く回数も倍になる。

実際に世界規模の障害を起こしている

机上の話に聞こえるかもしれないが、2019 年 7 月 2 日に Cloudflare は WAF（Web Application Firewall）のルールに含まれた 1 本の正規表現で HTTP/HTTPS を処理する全 CPU コアを使い切り、27 分間サービスが停止した。原因の正規表現には .*(?:.*=.*) という「何でも取る部分が並ぶ」形が含まれていた。

同社の事後報告は、簡略化した .*.*=.* で試行回数を数えている。x=x に対しては 23 ステップだが、x= の後に x を 20 個並べると 555 ステップになり、パターン末尾に ; を足した .*.*=.*; では 5,353 ステップに増える。末尾に必須の文字を足すとマッチが失敗しやすくなり、失敗を確定するための全通り探索が走るからだ。

ここで多くの人は「.* を遅延量指定子 .*?（短い取り方から試す版）に変えればよい」と考える。しかし同じ報告によると、.*? にしても ; 付きの版は 555 と 5,353 ステップのまま変わらない。試す順番を変えても、失敗する入力では結局全通りを試すことに変わりがないからである。

戻らないエンジンは何を捨てたのか

正規表現は理論上、状態機械（入力を 1 文字ずつ読んで状態を遷移させる仕組み）に変換でき、その方式なら入力を 1 回なめるだけで判定できる。Go の regexp パッケージはドキュメントで「入力サイズに対して線形時間で動くことを保証する」と明記しており、Google の RE2 も同じ保証を掲げる。Cloudflare も障害後、実行時間の保証がある RE2 か Rust の regex エンジンへの移行を対策に挙げた。

ならば全言語がこの方式にすればよいように思える。しかし実際は、この方式では後方参照（(\w)\1 のように「前に取った文字列と同じもの」を指す記法）と先読み・後読みを扱えない。RE2 の README は「バックトラッキングでしか実装方法が知られていない構文は、原則としてサポートしない」と述べている。Perl 由来の正規表現を引き継いだ JavaScript・Ruby・Python は、この表現力を手放せないためにバックトラッキングを使い続けている。

その中間を狙う改良も進んでいる。Ruby 3.2 はメモ化（一度失敗した「入力位置 × パターン上の位置」の組を覚えて再試行しない手法）を導入し、リリースノートによれば実験した正規表現の約 90% が線形時間で終わるようになった。ただし後方参照や先読み・後読みを含むパターン、繰り返し回数の大きい固定回数指定には適用されない。V8 も v8.8 で実験的なバックトラッキングしないエンジンを追加している。

守り方: 書き換え・長さ制限・タイムアウト

第一の手段は、パターンから曖昧さを除くことだ。^(a+)+$ は ^a+$ に、(\w|\d)+ は \w+ に書き換えれば区切り方が 1 通りに決まる。Python 3.11 以降と Ruby（Onigmo）はアトミックグループ (?>...) と所有量指定子 a++ を使える。これらは「一度取った分は手放さない」指定で、内側に戻る分岐点を作らないため、区切り方の全探索が起きない。JavaScript はどちらも未サポートなので書き換えで対処する。

次に、正規表現にかける前に入力の長さを制限する。指数的な増加は n に効くので、フォームの文字数上限をサーバー側で先に検査するだけで最悪ケースの時間を大きく縮められる。

最後の防壁がタイムアウトだ。Ruby 3.2 以降は全体設定とパターン単位の両方を持つ。設定しないとタイムアウトは無く、マッチが終わるまでそのスレッドは返ってこない。

# 全正規表現に 1 秒の上限（超えると Regexp::TimeoutError）
Regexp.timeout = 1.0

# 特定のパターンだけ上限を付ける
EMAIL = Regexp.new(pattern, timeout: 0.1)

Node.js には標準のタイムアウトが無いが、V8 のフラグで「バックトラッキングが多すぎたら線形エンジンに切り替える」挙動を有効にできる。V8 ブログによると切り替えの閾値 --regexp-backtracks-before-fallback のデフォルトは 50,000 回だ。ただし実験的機能で、後方参照・先読み・u や i フラグを含むパターンには効かない。本番投入前に自分のパターンで挙動を確かめる必要がある。

node --enable-experimental-regexp-engine-on-excessive-backtracks app.js
💼 実務でどう出会うか

典型的なのは、ユーザー入力を検証するバリデーション（メールアドレス・URL・電話番号）と、ログやリクエストを解析する正規表現だ。症状は「特定のリクエストだけが極端に遅い」「CPU 使用率が 1 コアだけ 100% に張り付く」として現れる。Node.js はメインスレッドが 1 本なので、1 件の破滅的マッチでサーバー全体の応答が止まる。ライブラリ由来の脆弱性として依存パッケージのセキュリティアラートに「ReDoS」と書かれて届くことも多い。コードレビューでは、入れ子の量指定子・同じ文字を取り合う選択肢・隣り合う .* を見かけたら、マッチに失敗する長い入力で試すとよい。

⌨️ 手を動かす（5 分）

入れ子の量指定子で、入力が 2 文字増えるごとに処理時間が約 4 倍になることを Node.js で確かめる。最後に書き換えたパターンと比べる。

node -e '
for (const n of [22, 24, 26, 28, 30]) {
  const s = "a".repeat(n) + "!";
  let t = Date.now(); /^(a+)+$/.test(s);
  const bad = Date.now() - t;
  t = Date.now(); /^a+$/.test(s);
  console.log(n, "入れ子:", bad, "ms", "書換:", Date.now() - t, "ms");
}'

全体で数秒かかる。「入れ子」の列は n が 2 増えるたびに約 4 倍に伸び（最初の行はエンジンの最適化が効く前なので外れることがある）、「書換」の列はずっと 0〜1 ms のままのはずだ。末尾の ! を消してマッチが成功する入力にすると、入れ子版も一瞬で終わる。遅いのはパターンそのものではなく「失敗する入力 × 曖昧なパターン」の組み合わせであることが観察できる。

🙅 よくある誤解
  • 正規表現が遅くなるのは入力が長いときだけだ — 破滅的バックトラッキングは 30 文字程度の入力でも数十秒〜数分の時間を食う。時間を決めるのは入力長よりもパターンの曖昧さで、増え方が指数的なので短い入力でも危険になる。
  • .* を .*? にすれば回避できる — 遅延量指定子は試す順番を変えるだけで、マッチに失敗する入力では結局全通りを試す。Cloudflare の検証でも失敗ケースのステップ数は変わらなかった。
  • Go に移植すれば同じ正規表現がそのまま速く動く — Go の regexp は RE2 構文で、後方参照や先読み・後読みを受け付けない。こうしたパターンは regexp.Compile がエラーを返すので、書き換えが必要になる。
📖 用語ミニ辞典
バックトラッキング
選択肢を 1 つ選んで進み、行き詰まったら分岐点に戻って別の選択を試すマッチング方式。
量指定子
*・+・{m,n} など、直前の要素を何回繰り返すかを指定する記号。
破滅的バックトラッキング
曖昧なパターンと失敗する入力の組み合わせで、試行回数が入力長に対し指数的に増える現象。
ReDoS
破滅的バックトラッキングを意図的に起こさせて CPU を占有させるサービス妨害攻撃。
RE2
入力長に比例する実行時間を保証する Google の正規表現ライブラリ。後方参照と先読み・後読みは非対応。
アトミックグループ
(?>...)。一度マッチした内容を手放さず、内側への後戻りを禁止するグループ。
🔗 もっと深く