アプリからファイアウォールにまで使われる正規表現を標的にした「ReDoS攻撃」とは？

サーバーやネットワークに意図的に負荷をかけ、サービス障害を引き起こすDoS攻撃の中でも、正規表現のパターン処理の脆弱性を利用した攻撃をReDoS攻撃と呼び、StackOverflowやCloudflareもその標的となったことがあります。パデュー大学の電気・コンピューター工学の教授であるジェームズ・デイビス氏が、ReDoS攻撃の原因となる典型的な正規表現とその対策について語っています。

The Regular Expression Denial of Service (ReDoS) cheat-sheet
https://levelup.gitconnected.com/the-regular-expression-denial-of-service-redos-cheat-sheet-a78d0ed7d865

正規表現とは、いくつかの文字列をひとつの文字列でパターンとして表現する方法のこと。ほとんどのプログラミング言語に実装されており、プログラミング言語は正規表現エンジンを使って、文字列が正規表現のパターンに一致するかを評価するとデイビス氏は説明しています。

そうした正規表現の処理を利用した攻撃がReDoS攻撃で、正規表現のパターン評価に時間を要する文字列を入力することで、サーバーの計算リソースを奪う攻撃です。正規表現はクライアント側のアプリケーションからファイアウォール、データベースに至るまであらゆる場所で利用されているので、ReDoS攻撃の対象範囲は広いと言えます。

デイビス氏は「(a|a)(b|b)c」という正規表現を例にして、正規表現エンジンの処理に時間がかかるメカニズムを説明しています。「(a|a)(b|b)c」は論理和が重ねて使用されており、評価経路が複数に分かれる正規表現です。

上記の正規表現に一致しない文字列を評価する場合、下記のような処理が正規表現エンジンによって行われるとのこと。

1：正規表現エンジンは左の点からスタートし、分岐に到達。正規表現エンジンは上の経路か下の経路のどちらかで「a」にマッチすると考え、ひとまず片方の経路を評価して先へと進みます。
2：今度は「b」の分岐に到達します。上の経路か下の経路のどちらかで「b」にマッチすると考え、片方の経路を評価して先へと進みます。
3：「c」に到達しましたが、パターンには一致しませんでした。正規表現エンジンは再び「b」の分岐へと戻ります。
4：最初に「b」の分岐で評価しなかった経路を評価し、もう一度「c」へと到達。パターンに一致しないので、「a」の分岐まで戻ります。
5：最初に「a」の分岐で評価しなかった経路を評価し、「b」の分岐へと到達。正規評価エンジンはここで再び「b」のふたつの経路を評価します。つまり、2から4の処理をもう一度繰り返します。
6：最終的に正規評価エンジンは4つの異なる経路を通り、同じ「c」を4回評価して処理を終了します。

このように、正規表現エンジンの評価には冗長な部分があるため、ReDoS攻撃の原因となる正規表現を避ける基本的な経験則は「あいまいさを排除する」ことだとデイビス氏は指摘。正規表現のあいまいさは、一般的に「｜」で表される論理和や、「*」や「+」といった量詞に起因するとのこと。

量詞の使いかたも重要です。例えば「(a|a)」と「(a|a)*」を比べた場合、正規表現エンジンが処理する分岐の数が「(a|a)*」の方が多くなっています。

ReDoS攻撃に利用される正規表現を避けてあいまいさを排除するためには、下記のような押さえるべきポイントがあるとデイビス氏は語っています。

・「(a*)*」のように量詞の中に量詞を入れるのを避ける
・「(a|a)*」のように量詞の中に論理和のパターンを入れるのを避ける
・「abc.*def.*」のように量詞を連結するのを避ける

また、もしReDoS攻撃の原因となるような正規表現を使用してしまっていても障害につながらないよう、ソフトウェア側で対処することも可能。その方法のひとつが「事前に文字列を検証する」方法です。例えば、文字列の長さを正規表現エンジンの評価前にテストすることで、評価に時間がかかる文字列を事前に排除することができます。しかし、正当な入力も排除してしまう可能性もあり、デイビス氏は文字列を事前検証する方法はあまり信用してないと語っています。

RE2などの高速な正規表現エンジンを使用することで、ReDoS攻撃を回避することもできます。しかし、こうした高速な正規評価エンジンは後方参照などの高度な機能をサポートしていなかったり、挙動が少し違ったりすることがあるとのこと。

C#／.NETで開発を行っている場合は、正規表現エンジンの評価時間にタイムアウトを設定することでReDoS攻撃に対処することが可能であるとデイビス氏は語っています。