再DoS

正規表現によるサービス拒否( ReDoS ) ^[1]は、評価に長時間かかる正規表現や入力を提供することでサービス拒否を引き起こすアルゴリズム複雑性攻撃 です。この攻撃は、多くの^[2]正規表現実装が最悪ケースの複雑性を超線形に持つという事実を悪用します。つまり、特定の正規表現と入力の組み合わせでは、入力サイズに応じて所要時間が多項式または指数関数的に増加する可能性があります。したがって、攻撃者は特別に細工した正規表現や入力を提供することで、プログラムにかなりの時間を費やさせることができます。すると、プログラムは遅くなったり、応答しなくなったりします。^{[3] [4]}

正規表現("regex") のマッチングは、有限状態オートマトンを構築することで実行できます。regex は、各状態と入力シンボルに対して、複数の次の状態が存在する可能性がある非決定性オートマトン(NFA)に簡単に変換できます。オートマトンを構築した後は、いくつかの可能性が存在します。

• エンジンはそれを決定論的有限状態オートマトン (DFA)に変換し、入力を結果に渡って実行します。
• エンジンは、一致するものが見つかるまで、またはすべてのパスを試して失敗するまで、すべての可能なパスを1つずつ試すことがあります（「バックトラッキング」）。^{[5] [6]}
• エンジンは、非決定性オートマトンを通過するすべての可能なパスを並列に検討する場合があります。
• エンジンは、非決定性オートマトンを遅延的に（つまり、マッチ中にオンザフライで）DFA に変換する場合があります。

上記のアルゴリズムのうち、最初の 2 つは問題があります。最初のアルゴリズムが問題なのは、決定性オートマトンが最大 の状態を持つ可能性があるためです。ここで は非決定性オートマトンの状態数です。したがって、NFA から DFA への変換には指数時間かかる場合があります。2 つ目のアルゴリズムが問題なのは、非決定性オートマトンが長さ のパスを指数数持つ可能性があるためです。そのため、長さ の入力を通過するのにも指数時間 かかります。^[7] ただし、最後の 2 つのアルゴリズムは異常な動作を示しません。 ${\displaystyle 2^{m}}$${\displaystyle m}$${\displaystyle n}$${\displaystyle n}$

非病的な正規表現の場合、問題のあるアルゴリズムは通常高速であり、実際には、正規表現を O(m) 時間で「コンパイル」し、O(n) 時間で一致させることが期待できます。一方、NFA のシミュレーションと DFA の遅延計算は、最悪の場合の複雑さがO (m ^{2 n) になります。 [a]}正規表現のサービス拒否は、これらの期待がユーザーが提供する正規表現に適用され、ユーザーが提供する悪意のある正規表現が正規表現マッチャーの最悪の複雑さを引き起こす場合に発生します。

正規表現アルゴリズムは効率的に記述できますが、存在するほとんどの正規表現エンジンは、必ずしも効率的に解決できるとは限らない追加の構造で正規表現言語を拡張します。このような拡張パターンにより、ほとんどのプログラミング言語での正規表現の実装では、基本的にバックトラッキングを使用するように強制されます。

最も深刻な問題は、バックトラック正規表現の一致で発生します。バックトラック正規表現の一致では、一部のパターンの実行時間が入力文字列の長さの指数関数的になります。 ^[8]文字​​列の場合、実行時間は です。これは、正規表現が次の 3 つの特性を持つ場合に発生します。 ${\displaystyle n}$${\displaystyle O(2^{n})}$

• 正規表現は部分式に繰り返し ( +、*) を適用します。
• 部分式は複数の方法で同じ入力に一致したり、より長い一致の可能性のあるプレフィックスである入力文字列に一致したりすることができます。
• 繰り返される部分式の後に、部分式が一致しないものと一致する式が存在します。

2 番目の条件は、次の 2 つの例で説明するのが最も適切です。

• では(a|a)+$、繰り返しが部分式に適用され、交替の各側で 2 つの方法でa|a一致できます。a
• では(a+)*$、繰り返しは部分式 に適用され、またはなどにa+一致できます。aaa

これら 2 つの例では、$文字列の末尾に一致させて 3 番目の条件を満たしていますが、別の文字を使用することもできます。たとえば、(a|aa)*c同じ問題のある構造になっています。

上記の 3 つの正規表現はすべて、 形式の文字列に適用すると指数関数的に実行時間が長くなります。たとえば、バックトラッキング式エンジンで と一致させようとすると、完了するまでにかなり長い時間がかかり、の前にが追加されるごとに実行時間が約 2 倍になります。 ${\displaystyle a...a!}$aaaaaaaaaaaaaaaaaaaaaaaa!a!

指数時間ではなく多項式時間でバックトラッキングすることも可能です。これも入力が十分に長い場合に問題を引き起こす可能性がありますが、悪意のある入力が重大な影響を及ぼすにはそれよりはるかに長い必要があるため、この問題にはあまり注意が払われていません。そのようなパターンの例は、入力が任意の長さの「」のシーケンスである場合の「」です。 ${\displaystyle O(n^{x})}$a*b?a*xa

いわゆる「悪質な」または脆弱な正規表現が、オンライン正規表現リポジトリで発見されています。正規表現全体を攻撃するには、 脆弱なサブ表現を見つけるだけで十分であることに注意してください。

1. RegExLib、id=1757 (電子メール検証) -赤い部分を参照
   ^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*(@){1}[a-z0-9]+[.]{1}(([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))$
2. OWASP 検証正規表現リポジトリ、Java クラス名 -赤い部分を参照
   ^(([a-z])+.)+[A-Z]([a-z])+$

これら 2 つの例も入力の影響を受けますaaaaaaaaaaaaaaaaaaaaaaaa!。

正規表現自体がユーザー入力の影響を受ける場合 (クライアントが検索パターンを提供できる Web サービスなど)、攻撃者は悪意のある正規表現を挿入してサーバーのリソースを消費する可能性があります。したがって、ほとんどの場合、ユーザーがサーバー上で任意のパターンを実行する可能性を排除することで、正規表現によるサービス拒否を回避できます。この場合、Web アプリケーションとデータベースが主な脆弱なアプリケーションです。または、悪意のあるページによってユーザーの Web ブラウザーがハングしたり、任意の量のメモリが使用される可能性があります。

ただし、脆弱な正規表現がサーバー側にすでに存在する場合、攻撃者は最悪の動作を引き起こす入力を提供できる可能性があります。この場合、電子メール スキャナーや侵入検知システムも脆弱になる可能性があります。

ウェブアプリケーションの場合、プログラマーはシステムのクライアント側とサーバー側の両方で同じ正規表現を使用して入力を検証する場合があります。攻撃者はクライアントコードを検査して悪質な正規表現を探し、細工した入力を直接ウェブサーバーに送信してサーバーをハングさせる可能性があります。^[9]

ReDoSは、信頼できない入力が関係する場合に正規表現の実行に時間制限を設定するだけで、正規表現エンジンに変更を加えることなく軽減できます。^[10]

ReDoSは、脆弱性のない正規表現の実装を使用することで完全に回避できます。 2019年にCloudFlareのウェブアプリケーションファイアウォール（WAF）がPCRE ReDoSによってダウンした後、同社はRE2に似たアルゴリズムを使用して、バックトラックのないRust正規表現ライブラリを使用するようにWAFを書き直しました。^{[11] [12]}

脆弱な正規表現は、リンターによってプログラム的に検出できます。^[13]方法は、純粋な静的解析^{[14] [15]から}ファジング^[16]まで多岐にわたります。ほとんどの場合、問題のある正規表現は「非悪」パターンとして書き換えることができます。たとえば、(.*a)+は に書き換えることができます([^a]*a)+。表現の一部のバックトラックを無効にする強欲な一致とアトミックグループ化^[17]も、脆弱な部分を「鎮静化」するために使用できます。^{[18] [19]}

• サービス拒否攻撃
• サイバー戦争
• 低軌道イオン砲
• 高軌道イオン砲

• オープンソース アプリケーションにおける ReDoS の例:
  • DataVault の ReDoS (CVE-2009-3277)
  • EntLib の ReDoS (CVE-2009-3275)
  • NASD CORE.NET Terelik の ReDoS (CVE-2009-3276)
• ReDoSのベンチマーク
  • Achim Hoffman (2010)。「ReDoS - JavaScript における正規表現 DoS のベンチマーク」。2010 年 4 月 19 日閲覧。
  • Richard M. Smith (2010) 「正規表現によるサービス拒否 (ReDoS) 攻撃のテスト結果」。2010 年 4 月 19 日閲覧。