ReDoS は「使える文字の確認」だけでは防げない

はじめに

ユーザー入力を正規表現で検証する場面は多くあります。ホスト名、メールアドレス、URL、識別子などを確認するときに、正規表現は手軽で便利です。

ただし、正規表現の書き方によっては、特定の入力で極端に時間がかかることがあります。攻撃者がその性質を利用して、サーバーの CPU を長時間使わせる攻撃が ReDoS です。これは Regular Expression Denial of Service の略で、日本語では「正規表現を悪用したサービス拒否攻撃」くらいの意味です。

この記事で扱うのは、次のような場面です。

• すでに運用中の複雑な正規表現がある
• すぐに別エンジンへ移行するのは難しい
• それでも、入力の安全性を一段引き上げたい

ここで扱うのは、ReDoS 専用の特別な手法というより、入力検証の前段に、使ってよい文字だけを許可する確認を置く という、比較的一般的な考え方です。OWASP の入力検証ガイダンス でも、受け付ける文字の集合を明示し、長さ制限を組み合わせることが勧められています。

この記事で整理したいのは、この前段の確認を ReDoS の文脈でどう位置づけるかです。これは入力検証としては自然な実装ですが、それだけで ReDoS を根本的に解決できるわけではありません。問題のある正規表現そのものの見直しや、線形時間で動く正規表現エンジンへの移行が必要になる場面もあります。

この記事では、この線引きを崩さずに、

1. ReDoS は何が起きているのか
2. 事前に使える文字を確認する方法は何に効くのか
3. 何には効かないのか
4. 実務ではどう組み合わせるのか

を順に整理します。

先に用語集

ReDoS

ReDoS は、正規表現の計算量が大きくなる入力を送りつけ、照合処理を異常に遅くする攻撃です。

バックトラッキング

JavaScript の標準正規表現エンジンは、ある入力に対して複数の解釈候補があると、それを順番に試します。途中で失敗したら、少し前に戻って別の候補を試します。この「戻って試し直す」動きがバックトラッキングです。

破滅的バックトラッキング

候補の数が爆発的に増えると、試し直しの回数も急増します。これが バックトラッキングの爆発 です。英語では catastrophic backtracking と呼ばれます。

線形時間の正規表現エンジン

一部の正規表現エンジンは、バックトラッキングを使わず、入力の長さにおおむね比例する時間で動きます。これを「線形時間で動く」と呼びます。

たとえば入力が 10 文字から 20 文字に増えたとき、処理時間もだいたい 2 倍程度に増える、という考え方です。もちろん実際には定数倍の差はありますが、少なくとも「候補の数が爆発して急に何千倍にも遅くなる」ような振る舞いは起こしにくくなります。

RE2 や Rust の regex クレートが代表例です。こうしたエンジンは、一般に ReDoS に強い設計になっています。

ReDoS の最小例

まずは、いちばん単純な例を見ます。

const re = /^(a+)+$/;

re.test('aaaaaaaaaaaaaaaaaaaaaaaaa!');      // 遅くなりやすい
re.test('aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!'); // さらに遅くなりやすい

(a+)+ は、意味だけ見ると a+ とほとんど同じです。ところが、a の並びを

• 内側の + にどこまで食べさせるか
• 外側の + を何回繰り返したことにするか

という分け方が大量にあります。

末尾に ! のような「最後に失敗する文字」があると、エンジンは

ほかの分け方なら成功するかもしれない

と考えて大量の候補を試します。これが時間のかかる原因です。

現実の正規表現で起こること

この最小例だけだと、「そんな不自然な正規表現は書かない」と思うかもしれません。実際の問題は、もっと普通の検証用正規表現で起こります。

たとえば、次のようなホスト名検証を考えます。

const fqdn = /^([a-z0-9]+\.)+[a-z]{2,}$/;

一見すると自然です。

• ([a-z0-9]+\.)+ で example. や sub. のようなラベルを繰り返す
• 最後に [a-z]{2,} で com や jp のような末尾部分を受ける

ただし、検証用の正規表現では、繰り返しの中に別の繰り返しが入った構造や、失敗時に試し直しが増えやすい構造が紛れ込むことがあります。次の例は単純化したホスト名検証です。典型的な最小例 ^(a+)+$ ほど強いものではありませんが、こうした構造を見たときに警戒するきっかけになります。

fqdn.test('a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a!');

この入力は末尾の ! で失敗します。失敗時には、エンジンが途中までの一致をどのように解釈できるかを試し直すことがあります。

この例は ^(a+)+$ のような典型的なバックトラッキングの爆発の最小例ほど強いものではありません。ここで伝えたいのは、検証用の正規表現にも「失敗時に試し直しが増えやすい構造」が入り込むことがある、という点です。

事前に使える文字を確認する理由

複雑な正規表現を完全に書き直せれば理想です。しかし、現実にはそう簡単ではありません。

JavaScript の標準正規表現には、他言語で使える次のような機能がありません。

• アトミックグループ
• 所有的量指定子 (possessive quantifier)

そのため、「この部分では絶対に後戻りさせない」という書き方がしにくくなっています。

また、既存のコードでは

• 長年使ってきた検証用正規表現がある
• 振る舞いを変えるのが怖い
• すぐに RE2 を使う構成へ移行できない

ということも珍しくありません。

そこで、正規表現そのものをすぐに変えられないときの 補助策 として、事前に使える文字を確認する方法が出てきます。

先に使える文字を確認する方法

考え方は単純です。

1. まず、「この入力に含まれてよい文字」だけを確認する
2. その確認を通ったものだけ、後段の詳細な正規表現へ渡す

コードにすると次のようになります。

function isValidHostname(input: string): boolean {
  // 1. 使ってよい文字だけで構成されているかを確認する
  if (!/^[a-z0-9.-]+$/.test(input)) return false;

  // 2. 長さも先に確認する
  if (input.length > 253) return false;

  // 3. その後で詳細な検証を行う
  return /^([a-z0-9]+\.)+[a-z]{2,}$/.test(input);
}

改善できる点

この方法の効果は、後段の正規表現に渡る入力の文字の種類を制限し、明らかに想定外の入力を早い段階で落とすこと です。

たとえば、!@#$%^&* や改行、タブ、制御文字のような入力を、後段の複雑な正規表現へ渡さずにすぐ落とせます。これは実務ではかなり有効です。

特に、

• 明らかに不正な入力を即時に落とせる
• 後段へ渡る入力の種類を絞れる
• バリデーションの責務を 1 段に分けられる

という利点があります。

改善できない点

ここが重要です。

先に使える文字を確認するだけでは、ReDoS を根本的には防げません。

理由は、ReDoS の本質が「許容される文字の中で、複数の解釈経路が爆発すること」にあるからです。

たとえば、次の入力は許容文字だけで構成されています。

'a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.1'

これは末尾が数字なので、[a-z]{2,}$ に失敗します。しかし「使える文字だけか」を見る /^[a-z0-9.-]+$/ は通ります。つまり、許容文字だけの入力でも、後段の正規表現の構造次第ではバックトラッキングは起こりえます。

したがって、この方法は

• 単純な不正入力を早く落とす
• 入力のばらつきを減らす
• 被害の起きやすい経路を狭める

という意味では有効ですが、中心的な対策ではなく補助策 と考えるべきです。

この方法が役に立つ場面

先に使える文字を確認する方法は、次のような場面で特に役に立ちます。

• 入力仕様が比較的はっきりしている
• 使ってよい文字が少ない
• 改行、制御文字、記号などを受け付ける必要がない
• 後段の正規表現が既存実装で、すぐには全面的に書き換えられない
• 失敗をなるべく安い処理で早く返したい

たとえば、ホスト名、スラッグ、識別子、短いコード値のような入力では取り入れやすいです。

この方法だけでは足りない場面

一方で、次のような入力では、この方法だけでは不十分です。

• 自由記述テキスト
• 複数行の入力
• HTML や Markdown
• 引用符や括弧など、記号自体に意味がある入力
• 許容文字だけで長い入力を作れてしまう形式

この場合は、長さ制限、パーサーの利用、正規表現の分割、線形時間で動く正規表現エンジンの利用を優先して検討します。

長さ制限との組み合わせ

ReDoS は入力長に強く依存します。バックトラッキングが 1 文字増えるごとに大きく悪化する場合、長さ制限は効果が大きくなります。

function isValidHostname(input: string): boolean {
  if (typeof input !== 'string') return false;
  if (input.length < 1 || input.length > 253) return false;
  if (!/^[a-z0-9.-]+$/.test(input)) return false;
  return /^([a-z0-9]+\.)+[a-z]{2,63}$/.test(input);
}

この順番には意味があります。

1. 型を確認する
2. 長さを確認する
3. 使ってよい文字を確認する
4. 最後に詳細な正規表現を当てる

前段で安く落とせるものは、できるだけ前で落とします。

根本的な対策

ここまでの話は補助策です。根本対策は別にあります。

1. 正規表現そのものを見直す

最初の候補は、問題のある構造を減らすことです。

• 入れ子になった繰り返しを避ける
• 曖昧な選択肢を減らす
• 1 つの巨大な正規表現を、小さな確認に分ける

たとえば、ホスト名検証であれば

• 全体長の確認
• 使ってよい文字の確認
• 各ラベル長の確認
• 先頭・末尾の - や . の確認

のように分割できることが多いです。

2. 線形時間で動く正規表現エンジン

Node.js だけで完結する環境なら、RE2 系を使う選択肢があります。

ここでいう RE2 系 とは、Google の RE2 と、それを各言語から使えるようにしたライブラリ群のことです。Node.js なら node-re2 がその代表例です。

RE2 系の特徴は、JavaScript 標準の正規表現エンジンのように大量のバックトラッキングを行わず、入力長に比例した時間で処理しやすいことです。その代わり、表現力の一部を削っています。

import RE2 from 'node-re2';

const re = new RE2('^([a-z0-9]+\\.)+[a-z]{2,}$');
re.test('a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a.a!');

RE2 系の利点は、バックトラッキングに依存しないことです。その代わり、標準正規表現と完全互換ではありません。

主な制約は次のとおりです。

• 後方参照が使えない
• 先読み / 後読みの一部が使えない
• JavaScript 標準と完全に同じ挙動にはならないことがある

また、node-re2 はネイティブモジュールなので、Edge 環境では使いにくいことがあります。

3. V8 の実験的な線形時間実装

V8 には、実験的な non-backtracking 実装があります。ただし、これは通常の JavaScript 開発でそのまま前提にできるものではありません。利用には専用のフラグが必要で、対象パターンにも制限があります。

そのため、一般的なアプリケーション設計では、

• 標準正規表現のまま安全な構造へ寄せる
• 必要なら RE2 を使う
• 補助策として長さ制限や、先に使える文字を確認する処理を組み合わせる

という順で考えるほうが現実的です。

実装例: 小さな確認に分ける

ここでのホスト名検証は、ReDoS 対策の説明用に単純化しています。実際のホスト名検証では、各ラベルの長さ、先頭・末尾のハイフン、末尾ドット、大文字小文字、IDN を扱うかどうかを別途決める必要があります。

そのうえで、1 つの大きな正規表現へ寄せすぎず、小さな確認に分けると次のように書けます。

export function isValidHostname(input: unknown): boolean {
  // 1. 型と長さを先に確認する
  if (typeof input !== 'string') return false;
  if (input.length < 1 || input.length > 253) return false;

  // 2. ここでは ASCII のホスト名だけを対象にする
  const hostname = input.toLowerCase();

  // 3. 使ってよい文字だけかを確認する
  if (!/^[a-z0-9.-]+$/.test(hostname)) return false;

  // 4. 先頭と末尾のドットはここでは許可しない
  if (hostname.startsWith('.') || hostname.endsWith('.')) return false;

  const labels = hostname.split('.');

  // 5. 各ラベルを個別に確認する
  return labels.every((label) => {
    if (label.length < 1 || label.length > 63) return false;
    if (label.startsWith('-') || label.endsWith('-')) return false;
    return /^[a-z0-9-]+$/.test(label);
  });
}

この構成のよい点は、責務がはっきり分かれることです。

• 1 段目は型と長さ
• 2 段目は使ってよい文字
• 3 段目以降は構文と各部品の確認

こうして分けると、将来の見直しもしやすくなります。

遅くなりやすい入力

対策を書くときは、どのような入力で遅くなるのかを知っておくと判断しやすくなります。

パターン 1: 入れ子の繰り返し

入力: a を n 回 + !
正規表現: ^(a+)+$

これは典型例です。最後に失敗する文字を足すことで、試し直しを大量に発生させます。

パターン 2: 重複した選択肢

入力: a を n 回 + !
正規表現: ^(a|a)+$

見た目は単純ですが、各位置で複数の候補を持つので、試し方が増えます。

パターン 3: 任意文字の曖昧な組み合わせ

入力: ' を n 回 + !
正規表現: ^.*?'.*?$

.*? のような書き方は便利ですが、前後の組み合わせによっては探索経路が増えやすくなります。

パターン 4: 任意 + 反復

入力: a を n 回
正規表現: ^(a?)+a$

あるかもしれない を何度も繰り返す構造は、やはり解釈の数を増やします。

ここで分かるのは、問題が「特殊文字があること」ではなく、同じ入力に対して複数の読み方があること だという点です。

テスト

ReDoS 対策では、通常入力だけでなく、失敗させる入力もテストに含めます。

import { describe, it, expect } from 'vitest';
import { isValidFqdn } from './fqdn';

describe('isValidFqdn', () => {
  it.each([
    ['example.com', true],
    ['sub.example.com', true],
    ['a-b.example.co.jp', true],
  ])('正常: "%s" → %s', (input, expected) => {
    expect(isValidFqdn(input)).toBe(expected);
  });

  it.each([
    ['example.com!', false],
    ['example.com\n', false],
    ['.example.com', false],
    ['', false],
    ['a'.repeat(254), false],
  ])('異常: "%s" → %s', (input, expected) => {
    expect(isValidFqdn(input)).toBe(expected);
  });
});

時間制約つきのテストも書けますが、performance.now() に強く依存すると、実行環境の差で不安定になりやすいです。CI では「異常に長く止まらないこと」を見る補助テストとして扱うほうが無難です。

静的解析

eslint-plugin-regexp を使うと、明らかに危ない正規表現を静的解析で検出できます。

pnpm add -D eslint-plugin-regexp

{
  "extends": ["plugin:regexp/recommended"],
  "rules": {
    "regexp/no-super-linear-backtracking": "error",
    "regexp/no-super-linear-move": "error"
  }
}

これは有効ですが、万能ではありません。

• 単純な危険パターンは拾いやすい
• 複雑な構造では見逃しもある
• 逆に、用途次第では問題にならないものを警告することもある

そのため、静的解析、長さ制限、先に使える文字を確認する処理、正規表現の見直しを組み合わせる考え方が大切です。

まとめ

• ReDoS の本質は、同じ入力に対する解釈経路が増え、バックトラッキングが爆発することです。
• 先に使える文字を確認する方法 は有用ですが、中心的な対策ではなく補助策です。
• この方法でできるのは、明らかに不正な入力を早く落とし、入力空間を狭めることです。
• 許容文字だけの入力でも、後段の正規表現の構造次第では ReDoS は起こりえます。
• 実務では 型確認 → 長さ制限 → 使ってよい文字の確認 → 構文や部品ごとの確認 の順に分けると扱いやすくなります。
• 根本対策は、正規表現そのものの見直し、または線形時間の正規表現エンジンへの移行です。