ReDoS セーフなパターンの作成

ReDoS (正規表現サービス拒否) は、次のような攻撃のクラスです。 慎重に作成された入力により、正規表現の一致時間が爆発的に長くなります。 JS エンジンは バックトラッキング を使用します。パターンが「曖昧」な場合、 不運な入力では、指数関数的な回数の試行が実行される可能性があります。

典型的な壊滅的なパターン

Pattern: ^(a+)+$
Input:   "aaaaaaaaaaaaaaaaaaaaab"

一致させるために、エンジンは、次の範囲にある "a" の すべて の可能なパーティションを試行します。 2 つの + 量指定子。 20 個の「a」の場合、2^20 = 最大 100 万回の試行となります。 30 個の「a」で 10 億。

その他の危険な例:

• (a*)*b -- 「入れ子になった星」。
• (a|a)* -- 重複する代替案。
• (\w+)+@ -- 外部数量指定子を持つ貪欲なグループ。

危険を発見する方法

次の構造を探してください。

1. 量指定子内の量指定子: (...+)+、(...*)*、(...{n,})+。
2. 量指定子の下での重複する選択肢: (a|ab)*、(\w|\d)+。
3. 複雑な代替案を使用した先読み/後読みを繰り返します。

防御的なリライト

Dangerous:  ^(\w+\s+)+$
Safe:       ^(?:\w+\s+)*\w+$

安全なバージョンでは、基本ケースを繰り返しケースから分離し、 曖昧さ。その他のテクニック:

• 所有量指定子 (a++) -- JS ではサポートされていませんが、他のエンジンでは使用できます。
• アトミック パターン ((?>...)) -- JS にはありません。
• マッチングする前に入力の長さを制限します。
• マッチング時の タイムアウト (このコースのエディターは 500 ミリ秒のタイムアウトを持つワーカーを使用します)。

ReDoS セーフなパターンに関する推奨事項

1. 交互のオプションが相互に排他的であることを確認します ((a|a+) を使用しないなど)。
2. ネストされた量指定子を重複する式に適用することは避けてください (例: (\\s*)*)。
3. 常に、一般的なワイルドカード ドット (.*) よりも特定の否定文字クラス ([^\\n]*) を優先します。

試してみてください

復習演習

追加の課題