正規表現を使ったDoS – ReDoS

いつかは忘れるくらい前に正規表現のアルゴリズム自体を利用してDoS攻撃を行うReDoSが発表されていました。今まであまり気にしていなかったのですが、検索しても日本語のページが出てこないようでした。詳しく知るためのリンクなどを紹介します。

少し検索して出て来た日本語ページはHPのページでしたが、たまたまインデックスされていたページがヒットしたようでした。また記載されている情報は不十分でした。（ページ下のコピーライトからFortifyの情報のようです）

日本語のページで良いものは無いようなので、ReDoSの英語ページ／PDFを紹介します。

• Wikipedia
• OWASP
• CHECKMARX 2015 (PDF) CHECKMARX 2009 (PDF)

3つ目のCHECKMARXのPDFは解りやすいと思います。OWASPのページはCHECKMARXの資料が元になっているようです。攻撃可能な正規表現のパターンと攻撃文字列が載っています。

Evil Regex pattern examples

1. (a+)+
2. ([a-zA-Z]+)*
3. (a|aa)+
4. (a|a?)+
5. (.*a){x} | for x > 10

Payload: “aaaaaaaaaaaaaaaaaaX”

危険性がある正規表現は

• オーバーラップがある正規表現
• 繰り返しのネストがある正規表現

とされています。上の”Evil Regex Pattern Example”の正規表現はこの条件を満たしています。

対策も書かれており

• ReDoS脆弱性は非常に大きな問題であり、我われは検出／防止しなければならない
• 動的に生成した正規表現は使わない、もしくは適切なサニタイズを行って利用する
• どのような正規表現もReDoSに脆弱でないか使用する前に確認する
• 動的な正規表現テストツール、静的な正規表現検査ツールの開発が必要

としています。CHECKMARXは静的なコード検査ツールを販売しているメーカーなので、自社ツールにも入れるのかも知れません。CHECKMARXは今年評価したのですが、評価に利用したコードについてはReDoS脆弱性は検出していませんでした。

どのくらいの性能劣化なのか？はDZoneのRegular Expressions Denial of the Service (ReDOS) Attacks: From the Exploitation to the Preventionに記載されています。

といった感じで簡単にCPU時間を使い切ってしまいます。

日本語の紹介／解説ページが無かったようなので簡単に紹介しました。