ReDoS: Regular Expression Denial of Service の原因と解決策

概要

ReDoS（Regular Expression Denial of Service）は、特定の入力に対して正規表現のマッチングが指数関数的に遅くなる問題です。アプリケーションがハングする原因となります。

エラーメッセージ

RangeError: Maximum call stack size exceeded
# または単にハング/タイムアウト

原因

ネストした繰り返し: (a+)+ のようなパターン
重複する選択肢: (a|a)+ のようなパターン
量指定子の連続: .*.* のようなパターン
ユーザー入力の直接使用: 検証なしで正規表現に使用

解決策

1. 危険なパターンを避ける

1
2
3
4
5
6
7
8
9
// 悪い例（ReDoS脆弱性あり）
const bad1 = /(a+)+$/;
const bad2 = /([a-zA-Z]+)*$/;
const bad3 = /(a|aa)+$/;

// 良い例
const good1 = /a+$/;
const good2 = /[a-zA-Z]+$/;
const good3 = /a+$/;

2. アトミックグループを使用（対応している場合）

1
2
3
4
5
6
// JavaScriptでは非対応だが、他の言語では
// 悪い例
/\d+(?:\.\d+)?/

// 良い例（Perl, PCRE等）
/(?>\d+)(?:\.\d+)?/

3. タイムアウトを設定

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Node.jsでタイムアウト付き正規表現
const { Worker } = require('worker_threads');

function safeRegex(pattern, input, timeout = 1000) {
  return new Promise((resolve, reject) => {
    const worker = new Worker(`
      const { parentPort } = require('worker_threads');
      parentPort.on('message', ({ pattern, input }) => {
        const regex = new RegExp(pattern);
        parentPort.postMessage(regex.test(input));
      });
    `, { eval: true });

    const timer = setTimeout(() => {
      worker.terminate();
      reject(new Error('Regex timeout'));
    }, timeout);

    worker.on('message', (result) => {
      clearTimeout(timer);
      resolve(result);
    });

    worker.postMessage({ pattern, input });
  });
}

4. 入力長を制限

1
2
3
4
5
6
function validateEmail(email) {
  if (email.length > 254) {
    return false;
  }
  return /^[^\s@]+@[^\s@]+\.[^\s@]+$/.test(email);
}

5. 専用のバリデーションライブラリを使用

1
2
3
4
5
// validator.jsを使用
const validator = require('validator');

validator.isEmail('test@example.com');  // true
validator.isURL('https://example.com');  // true

6. 静的解析ツールで検出

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
# eslint-plugin-regexp
npm install --save-dev eslint-plugin-regexp

# .eslintrc.js
module.exports = {
  plugins: ['regexp'],
  rules: {
    'regexp/no-super-linear-backtracking': 'error'
  }
};

7. 文字列メソッドで代替

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// 正規表現の代わりに文字列メソッド
const str = 'hello world';

// 悪い例
/hello/.test(str);

// 良い例（シンプルな場合）
str.includes('hello');
str.startsWith('hello');
str.endsWith('world');

概要

エラーメッセージ

原因

解決策

1. 危険なパターンを避ける

2. アトミックグループを使用（対応している場合）

3. タイムアウトを設定

4. 入力長を制限

5. 専用のバリデーションライブラリを使用

6. 静的解析ツールで検出

7. 文字列メソッドで代替

JavaScript の他のエラー