はじめに

ブラウザだけで動く小さなツールを集めたサイトに、正規表現チェッカーを置いています。パターンと文章を入れると、一致した部分の色付け・グループの一覧・置換の結果・パターンの日本語の解説を、その場で表示するツールです。

正規表現のツールを作ると、避けて通れない問題があります。ある種のパターンを入れると、計算が終わらなくなることです。これを ReDoS（Regular expression Denial of Service）と呼びます。

この記事では、入力のたびに正規表現を実行するツールで、ReDoS が起きても画面を固めないためにやったことを書きます。やったことは次の3つです。

正規表現の実行を、画面とは別のスレッド（Web Worker）に移す
1.5秒たっても答えが返ってこなければ、Worker ごと止めて作り直す
それを Playwright のテストで確かめる

ReDoS とは

いちばん小さな例は、このパターンです。

/^(a+)+$/.test("aaaaaaaaaaaaaaaaaaaaaaaaaa!");

「a の1回以上のくり返し」を、さらに1回以上くり返しています。最後の ! のせいで一致しないと分かるまでに、正規表現エンジンは「26個の a をいくつのかたまりに分けるか」の組み合わせを、すべて試そうとします（バックトラック）。

Node.js 22（Chrome と同じ V8 エンジン）で、a の数を変えて時間を測りました。

a の数	かかった時間
20	約 11ms
22	約 44ms
24	約 174ms
26	約 698ms

a が2つ増えるごとに、約4倍になっています。この調子なら、30個で10秒を超える計算です。いっぽう、くり返しを入れ子にしない /^a+$/ なら、a が10万個でも 1ms もかかりません。

問題は、こうしたパターンがわざと作ったものとは限らないことです。メールアドレスのチェックでよく見る形に似た /^([\w.-]+)+@example\.com$/ でも、少し違う文字列を入れるだけで同じことが起きました（a が24個で約 154ms、そこから2文字ごとに約4倍）。

なぜ画面が固まるのか

JavaScript は、画面の描画・クリックや入力への反応・自分で書いた処理を、基本的に**1本のスレッド（メインスレッド）**で順番に行います。

re.test() は、終わるまで途中で止まりません。メインスレッドで ReDoS が起きると、その間はボタンも入力欄もスクロールも反応しなくなります。数十秒続けば、ブラウザが「このページは応答していません」と表示します。

入力のたびに実行するツールでは特に困ります。パターンを1文字ずつ打っている途中で、たまたま危ない形になるだけで固まるからです。

1. 正規表現を Web Worker で実行する

Web Worker は、メインスレッドとは別のスレッドで JavaScript を動かす仕組みです。Worker の中でどれだけ時間がかかっても、画面は固まりません。

このサイトは、ツールごとに JS ファイルを分けていて、Worker 用に別のファイルを置く代わりに、Worker の中身を文字列で持ち、Blob から作っています。

const WORKER_SRC = `
self.onmessage = e => {
  const { id, pattern, flags, text, repl } = e.data;
  try {
    const re = new RegExp(pattern, flags.includes("g") ? flags : flags + "g");
    const list = []; let total = 0;
    for (const m of text.matchAll(re)) {
      total++;
      if (list.length < 500) list.push({ i: m.index, s: m[0] /* グループなど */ });
      if (total > 100000) break;
    }
    let out = null;
    if (repl !== null) out = text.replace(new RegExp(pattern, flags), repl);
    self.postMessage({ id, ok: true, list, total, out });
  } catch (err) { self.postMessage({ id, ok: false, msg: String(err.message || err) }); }
};`;

let worker = null;
function newWorker() {
  if (worker) worker.terminate();
  worker = new Worker(URL.createObjectURL(new Blob([WORKER_SRC], { type: "text/javascript" })));
  worker.onmessage = onResult;
}

ポイントは次のとおりです。

一致の検索（matchAll）だけでなく、置換（replace）も Worker の中で行います。置換でも ReDoS は起きるためです。
画面に出す一致は最初の500件まで、数えるのは10万件までにしています。ReDoS とは別に、.*? のような何にでも一致するパターンで大量の結果を返さないためです。
結果には id を付けて返します（理由は後で書きます）。

CSP との関係

このサイトは CSP（Content-Security-Policy）で、読み込んでよいものを厳しく決めています。Blob から Worker を作るには、worker-src で blob: を許可する必要があります。

Content-Security-Policy: default-src 'self'; script-src 'self' ...; worker-src blob:; ...

許可したのは worker-src だけです。script-src には blob: も 'unsafe-inline' も入れていません。Worker の中身は、自分のサイトの JS ファイルに書いた固定の文字列なので、外から入ってきたコードが Worker として動くことはありません。利用者が入れるパターンや文章は、postMessage でデータとして渡しているだけです。

2. 1.5秒で打ち切って、Worker を作り直す

Worker に移しただけでは、計算は裏で走り続けます。次の入力を送っても、前の計算が終わるまで Worker は返事をしません。

そこで、1.5秒たっても返事がなければ、Worker を terminate() で止めて新しく作り直します（画面に表示する部分などは短くしています）。

function run() {
  // …パターンと文章を読み取る…
  try { new RegExp(pat, flags); }  // 書き方の誤りは、Worker に渡す前に知らせる
  catch (e) { /* 「パターンの書き方に誤りがあります」と表示 */ return; }

  const id = ++seq; pending = { id, text, flags };
  clearTimeout(timer);
  timer = setTimeout(() => {
    if (pending && pending.id === id) {
      newWorker();  // 古い Worker を止めて、新しく作る
      showError("処理に時間がかかりすぎたため中止しました。くり返しの記号（* や +）が入れ子になっていないか確認してください。");
    }
  }, 1500);
  worker.postMessage({ id, pattern: pat, flags, text, repl });
}

function onResult(e) {
  const r = e.data;
  if (!pending || r.id !== pending.id) return;  // 古い入力への返事は捨てる
  clearTimeout(timer);
  // …一致の色付け・一覧・置換の結果を表示…
}

terminate() は、Worker の計算を外から確実に止められる唯一の方法です。正規表現エンジンの中で回っている計算は、Worker の中からは止められません。
入力は 150ms 待ってから実行しています（打つたびに実行しないため）。それでも、前の結果より先に次の入力が来ることはあるので、id でいちばん新しい入力への返事だけを使います。
1.5秒にしたのは、ふつうの使い方なら一瞬で終わり、打ち切りの案内が出るまで待たされる感じも少ない長さだからです。

3. 結果とエラーの見せ方

表示は3通りに分けました。

状態	表示
パターンの書き方の誤り（`(` が閉じていないなど）	「パターンの書き方に誤りがあります：（エンジンのメッセージ）」。Worker には渡さない
1.5秒で打ち切り	「処理に時間がかかりすぎたため中止しました。くり返しの記号（* や +）が入れ子になっていないか確認してください。」
ふつうに終わった	「○件一致」と、色付け・グループの一覧・置換の結果

打ち切りの案内には、原因として多い形（入れ子のくり返し）を書いています。「エラー」だけだと、パターンが悪いのか、ツールが壊れたのか分からないからです。

4. テストで確かめる

テストは Playwright で書いています。ReDoS の確認では、次の4つを見ています。

await page.goto(BASE + "/regex");
await page.fill("#pat", "(a+)+$");
await page.fill("#text", "a".repeat(40) + "b");

// 計算中も画面は動く：100ms ごとのタイマーが、大きく遅れずに進むか
const lag = await page.evaluate(() => new Promise(resolve => {
  let last = performance.now(), max = 0, n = 0;
  const t = setInterval(() => {
    const now = performance.now(); max = Math.max(max, now - last); last = now;
    if (++n === 12) { clearInterval(t); resolve(max); }
  }, 100);
}));
// lag < 300（ms）なら、メインスレッドは止まっていない

// 1.5秒で打ち切りの案内が出る
// → 「処理に時間がかかりすぎたため中止しました」で始まるか

// 打ち切りのあとも使える（新しい Worker に入れ替わっている）
await page.fill("#pat", "a+");
await page.fill("#text", "aa b aaa");
// → 「2 件一致」

// 書き方の誤りは、Worker に渡す前に知らせる
await page.fill("#pat", "(");
// → 「パターンの書き方に誤りがあります」で始まるか

a が40個の (a+)+$ は、そのまま実行すれば何時間もかかる計算です。それでもテストは数秒で終わり、その間メインスレッドのタイマーは遅れません。あわせて、ページ全体でエラーと CSP 違反が出ていないことも見ています。

「画面が固まらない」を、目で見るだけでなく数字で確かめられるようにしたのがポイントです。

限界と注意点

この方法でできるのは、画面を守ることだけです。

**パターンが速くなるわけではありません。**危ないパターンは、1.5秒で止まるだけです。
1.5秒より少し短く終わる重い処理は、止まらずに最後まで実行されます（画面は固まりませんが、結果が出るまで待ちます）。
これはブラウザの中の話です。サーバーで利用者の正規表現を実行する場合は、同じ考え方（別のプロセス・時間の上限）に加えて、そもそも利用者にパターンを書かせない、入力の長さを制限する、バックトラックしないエンジンを使う、などの対策が必要です。

危ないパターンを書かないコツ

くり返しを入れ子にしない：(a+)+、(\w+)*、(.*)* のような形は避ける
くり返しの中で、同じ文字に一致する選択肢を並べない：(a|a)*、(\w|\d)+ など
.* を続けて並べない：.*foo.*bar.* は、一致しない長い行でとても遅くなることがある
文字の範囲を狭くする：.* の代わりに [^,]*（カンマ以外）のように、止まる場所をはっきりさせる
入力の長さに上限を付ける：長い入力ほど、悪い場合の時間は急に増える

おわりに

「入力のたびに、利用者が書いたものを実行する」ツールでは、遅い入力が来ることを前提にしておく必要があります。Web Worker で画面から切り離し、時間で打ち切り、テストで確かめる。この3つで、ReDoS が起きても画面は固まらなくなりました。

ほかのツールも、ツール横丁に置いています。入力内容はどれもサーバーに送りません。