正規表現テスター

2019年7月2日 13:42 UTC、Cloudflare のグローバルエッジの全サーバーで CPU 使用率が100%に達しました。HTTP トラフィックが流れなくなりました。公開されたポストモーテムによれば、原因は数分前にデプロイされた1つの新しい WAF ルールでした: (?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*))) 末尾に無制限の + が付いたその文字クラスが、特定の細工された文字列に適用されると、PCRE で指数時間のバックトラッキングを引き起こしました。正規表現エンジンは、マッチを「完成」させようと数十億通りの順列を試す暴走状態に入りました。Cloudflare の全サーバーの全 CPU が、27分間にわたり同時にこの作業に占有されました。ポストモーテムはこの障害モードに名前を与えました — catastrophic backtracking、別名 ReDoS(Regex Denial of Service)です。 メカニズムは構造的なものです。プロダクションで使われる正規表現エンジンの多く(PCRE、Java の java.util.regex、Python の re、Ruby の Onigmo、JavaScript の V8 Irregexp)は、バックトラッキングでマッチングを実装しています。パターンの後半でマッチ試行が失敗すると、エンジンは巻き戻して別の経路を試します。ネストした量指定子 — (a+)+、(.*)*、(\w*)*$ のようなパターン — では、各文字を内側と外側のグループへ振り分ける方法が指数的に増えます。30文字の入力は、エンジンが諦めるまでに 2^30 ≈ 10億回の振り分け試行を生み出し得ます。CPU は1回の正規表現マッチに数秒、数分、場合によっては数年を費やします。 注意すべきパターン: (1) 量指定子を量指定子で包んだあらゆる形 — (a+)+ が教科書的な例です。(2) 同じ接頭辞を含む選択 — (a|aa)+。(3) マッチしない可能性のあるリテラルで終わる無制限区間にかかる貪欲な量指定子 — ^(a+)+\$ を "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab" に対してテストすると、大半のエンジンが極端に遅くなります。 防御策は3つあります。(1) 構造的に免疫のあるエンジンを使う。RE2(Google)、Hyperscan、Rust の regex クレート、Go の regexp、Lua のパターンはいずれも線形時間の NFA シミュレーションを使い、バックトラックしません。代償として一部の形式のバックリファレンスや後読み(lookbehind)をサポートしませんが、実際のパターンの95%には問題ありません。RE2 はまさに Google で ReDoS インシデントが起きたために設計されたものです。(2) すべての正規表現評価に実時間のタイムアウトを設定する。Java の Pattern.matcher には組み込みのタイムアウトがなく(スレッド割り込みを使う必要があります)、.NET はまさにこの理由で Regex(pattern, options, timeout) を明示的に追加しました。(3) パターンをリントする。vuln-regex-detector、safe-regex、ESLint の no-unsafe-regex のようなツールは、最悪の構造形状を出荷前に検出します。 実践的なルール: エンドユーザーから正規表現を受け取る場合は、タイムアウトなしで言語のデフォルトエンジンを使うことを絶対に避けてください。パターンを自分で書く場合は、特にリクエスト経路上の WAF や入力バリデータにデプロイする前に、いずれかのリンターにかけてください。2019年の Cloudflare はどちらもしていませんでした。

// Catastrophic patterns
/^(a+)+$/.test('a'.repeat(30) + 'b');
// V8: ~30 seconds. Engine in tight backtracking loop.

/(.*)*=/.test('=' + 'a'.repeat(50));
// Even worse with inner unbounded greedy.

// Production safety in Node
const RE2 = require('re2');         // linear time
const safe = new RE2('(a+)+');
safe.test('a'.repeat(30) + 'b');    // returns instantly, false

// Native regex with watchdog (workers)
function timedRegex(pattern, input, ms = 50) {
  return new Promise((resolve, reject) => {
    const w = new Worker(`onmessage = e => {
      const re = new RegExp(e.data.p);
      postMessage(re.test(e.data.s));
    }`, { eval: true });
    const timer = setTimeout(() => { w.terminate(); reject(new Error('regex timeout')); }, ms);
    w.onmessage = e => { clearTimeout(timer); resolve(e.data); w.terminate(); };
    w.postMessage({ p: pattern, s: input });
  });
}

// .NET — built-in timeout
var re = new Regex(pattern, RegexOptions.None, TimeSpan.FromMilliseconds(50));

現代の正規表現実装は3つのエンジンが支配しており、それらの違いは重要です。 PCRE(Perl Compatible Regular Expressions)。PHP、nginx、Apache、そしてかつての Cloudflare の WAF などを支えてきた C ライブラリです。バックトラッキングベースで、最大限の機能セットをサポートします: バックリファレンス、後読み(PCRE2 では可変長)、再帰、アトミックグループ、絶対最大量指定子(possessive quantifier)、条件パターン、あらゆる構文の名前付きキャプチャ、コールアウト。その代償が最悪ケースの挙動 — 敵対的な入力に対する指数時間です。PCRE2(現代のフォーク)は JIT コンパイラを追加し、平均ケースの素のマッチング速度を RE2 と互角にしましたが、最悪ケースは変わりません。 RE2(Google)。Russ Cox による C++ 実装で、Go の標準ライブラリにもバインドされています。Thompson の NFA シミュレーションアルゴリズムに基づいて構築されており、エンジンは可能なパーサー状態の集合を保持し、入力に沿ってロックステップで前進させます。パターンの複雑さに関係なく、入力長に対して線形時間です。トレードオフはサポートできない機能です: 任意のバックリファレンス(正規表現が以前にマッチした任意のテキストを記憶する必要があってはなりません)、また一部のバインディングでは後読みが有界長に制限されます。実際のコードベースにある正規表現パターンの95%にとって、RE2 はいくつかの珍しい機能と引き換えに ReDoS を排除できるドロップイン代替です。Google は一連の正規表現起因の障害の後、社内サービスをすべて RE2 に移行しました。 JavaScript V8(Irregexp)。ブラウザの正規表現エンジンです。バックトラッキングベースですが高度に最適化されており、正規表現パターンを JIT レベルでネイティブコードにコンパイルします。後読み(2018年、ES2018 以降)、名前付きキャプチャ (\(?<name>...\))、Unicode プロパティエスケープ (\p{Letter})、s フラグ(dotAll)、d フラグ(マッチインデックス)をサポートします。タイムアウトのプリミティブはありません — 暴走するパターンはタブをクラッシュさせます。新しめの V8(2022年以降)には、v8 エンジンフラグで /l フラグを指定して有効化できる実験的な線形時間モードがありますが、デフォルトでは無効で、標準の JS には公開されていません。 実践的な指針: サーバーサイドでは、ユーザー入力に触れるすべてのパターンに RE2(Go はネイティブ、Node では re2 npm、Rust では regex-rs、Python では google-re2)を優先してください。より豊富な機能セットが必要でパターンを信頼できるなら PCRE を使います。ブラウザサイドでは、V8 に組み込みの保護がないことを受け入れてください — パターンをシンプルに保ち、ネストした量指定子を避け、非バックトラッキングの構文を優先します(アトミックグループ /(?>x)/ は JS にはありませんが、/(?=(x))\1/ という先読みトリックで模倣できます)。可能な限り、複雑な正規表現を明示的な文字列操作に置き換えてください — string.includes、string.split、indexOf はすべて線形時間で、際限なく高速です。 機能のミスマッチも重要です。Stack Overflow の PCRE 回答からコピーしたコードは、JavaScript で動かないことがよくあります: PCRE の可変幅後読み、絶対最大量指定子 (a++)、再帰サブルーチン ((?R))、一部の Unicode クラスは PCRE 専用です。JavaScript 専用の機能には d(hasIndices)フラグと v(Unicode-Sets)フラグ(ES2024)があります。エンジン間で移植する際は、パターンを自分のテストケースに対して実行してください — 目に見えない意味論の違いはよくあることです。

// PCRE-only that fails in JS:
preg_match('/^(?P>group)$(?<group>foo|bar)/', $s);  // recursion
preg_match('/(?<=\w+)b/', $s);                     // var-width lookbehind

// JavaScript-only:
'abcabc'.matchAll(/(?<x>\w)/dg);  // d flag → result[i].indices
[...'abc'.matchAll(/[\p{Letter}--[a]]/v)]; // v flag set difference

// Cross-engine safe baseline (works everywhere):
const safePattern = /^[a-zA-Z][a-zA-Z0-9_]{0,31}$/;

// Server: use RE2 in Node
const RE2 = require('re2');
const safe = new RE2('^([a-z]+)\\s+(\d+)$');
const m = safe.match('alice 42');
m;  // ['alice 42', 'alice', '42']

// Replace regex with string ops when you can — guaranteed O(n)
const isEmail = (s) => s.includes('@') && s.indexOf('@') === s.lastIndexOf('@');

ルックアラウンドは零幅アサーションです: 現在位置の前または後に何があるかを、文字を消費せずに検査します。4種類あります: 肯定先読み (?=...)、否定先読み (?!...)、肯定後読み (?<=...)、否定後読み (?<!...)。強力ですが、頻繁に使われすぎています。正規表現のチュートリアルで見かけるルックアラウンドのおよそ80%は、代わりにキャプチャグループを使った普通の正規表現として書くことができ、その方が速く、読みやすくなります。 正当な用途はいくつかのカテゴリに分けられます。 (1) デリミタを消費せずにトークン化する。/(?<=\D)(?=\d)|(?<=\d)(?=\D)/ のような正規表現で "abc123def" を英字と数字に分割すると、文字と数字の境界に、文字を一切消費せずに分割点が挿入されるため、.split は ["abc","123","def"] を返します。零幅でない正規表現で同じ効果を得るには、明示的な再組み立てが必要です。 (2) マッチ範囲の外にある制約をアサートする。「単位が後に続く数値を見つけたいが、単位はマッチに含めたくない」: /\d+(?=px|em|rem)/。先読みがなければ、単位をマッチに含めて(後処理で取り除く)か、キャプチャグループを使ってグループ1を参照することになります。先読みの方がすっきりします。 (3) 1つのパターンで複数の独立した制約を検証する。古典的な「パスワードは数字・英字・特殊文字を含み、12文字以上」のパターン: /^(?=.*\d)(?=.*[a-zA-Z])(?=.*[!@#$%])\S{12,}$/。各 (?=...) は位置を進めずに、文字列全体に対して1つのルールを検査します。これは機能して簡潔ですが、複数の個別のバリデーションをアプリケーションコードで行う方が明確になるという典型例でもあります。 (4) Unicode における単語境界。JavaScript の \b はデフォルトで ASCII 限定です。Unicode テキストに対して「文字の境界」をアサートするには、Unicode フラグ付きの /(?<![\p{Letter}\p{Mark}])foo(?![\p{Letter}\p{Mark}])/u が必要です。 ルックアラウンドを使うべきでないとき: キャプチャグループで済むすべての場合です。/(\d+)px/ を "12px" にマッチさせれば、後読みなしで match[1] = "12" が得られます。/(?<=\$)\d+/.exec("$42")[0] は /\$(\d+)/.exec("$42")[1] に置き換えてください — 同じデータで、より単純な正規表現になり、後読みが制限されたエンジンを含むすべてのエンジンで動作します。 微妙なパフォーマンスの落とし穴: バックトラッキングエンジンでは、量指定子付きグループの内側にあるルックアラウンドが最悪ケースの作業量を掛け算で増やすことがあります。バックトラックの各ステップでアサーションが再評価されるからです。RE2 は先読みを扱えますが、任意の後読みは扱えません。Java は 9 で有界の後読みを追加しました。Python は固定長の後読みのみをサポートします。ECMAScript は 2018 年から先読みと無制限の後読みの両方をサポートしていますが、Safari が後読みに対応したのは 2023 年になってからなので、古い Safari をサポートする必要がある場合、後読みは選択肢から外れます。

// Tokenize on letter/digit boundary (zero-width split)
'abc123def'.split(/(?<=\D)(?=\d)|(?<=\d)(?=\D)/);
// → ['abc', '123', 'def']

// Match number followed by CSS unit, exclude the unit
const px = '20px 1rem 3em'.match(/\d+(?=px|em|rem)/g);
// → ['20', '1', '3']

// Password rule with lookaheads
/^(?=.*\d)(?=.*[a-z])(?=.*[A-Z])(?=.*[!@#$%^&*])\S{12,}$/.test(pw);

// Lookbehind for dollar amount
'price $42 and €50'.match(/(?<=\$)\d+/);  // ['42']

// SAME RESULT without lookbehind (more portable)
'price $42 and €50'.match(/\$(\d+)/)[1];   // '42'

// AVOID: nested-quantifier-with-lookahead — slow on adversarial input
/^(.+(?=.+))+$/.test('a'.repeat(20) + 'X');  // backtracks badly