壊滅的なバックトラック：正規表現が CPU を埋める理由

一つの正規表現がサービス全体を止めるとき、原因はほぼ壊滅的なバックトラックです。試行回数が入力長に対して指数関数的に増えます。

壊れる形

/^(a+)+b$/.test('aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa')

b が無いので決して一致しません。しかし諦める前に、エンジンは a の分け方をすべて試します。外側の + と内側の + が自由に分配でき、組み合わせは 2 の n 乗です。a が 30 個で十億回の試行になります。

危険信号は量指定子の中の量指定子です。(x+)*、(x*)*、あるいは両方の枝が同じ文字に一致する (x|y)+。

対策 1：入れ子を外す

あの正規表現が表したいのは「すべて a、最後に b」です。

/^a+b$/

入れ子のない量指定子は線形です。壊滅的な正規表現の大半は、手で書き直せば済みます。

対策 2：グループを固定する

捕獲グループが本当に必要な場合は、内側を原子的グループか占有量指定子にしてバックトラックを禁じます。

/^(?:a++)+b$/     // 占有量指定子

JavaScript の後読みは ES2018 からありますが、原子的グループは ES2025 です。それまでは書き換えで回避します。

対策 3：入力長を制限する

業務上 200 文字を超えないなら、早期に弾きます。底が小さく制限されていれば指数増加は怖くありません。

対策 4：制限時間を設ける

最も堅いのは、どの正規表現も信用しないことです。

function safeTest(re, s, tag) {
  const start = Date.now();
  const worker = new Worker(/* 別スレッドで re.test(s) を実行 */);
  // 時間切れなら terminate して false
}

Node に正規表現の時間制限は無く、スレッドやプロセスの分離しかありません。RE2 のようなバックトラックしないエンジンは構造的に免疫がありますが、後方参照と後読みを失います。

チェックリスト

見えるもの	危険度
`(a+)` `(a)*`	高、指数
`(a	a)*` 枝の重複
ユーザ提供の正規表現	高、遠隔コードと同等
固定リテラル	低、バックトラック無し

最後の行が最も見落とされます。ユーザに正規表現を提出させてはいけません。 設定値ではなく、サーバ上で動くチューリング完全なプログラムです。

量指定子の中の量指定子は警報です。平坦に書き換えられないなら、制限時間を設けてください。