本連載では第一線のPerlハッカーが回替わりで執筆していきます。今回のハッカーは藤浪大弥さんで、テーマは
ReDoS解説にあたって── 本稿の構成など
正規表現に関わる脆弱性として
後半で説明しますが、Perlの正規表現実装にはさまざまな工夫があり、標準的な実装とはやや異なる部分があります。Perlを使ってReDoSの説明をすると本質的でない部分が生じてわかりづらくなるため、前半では解説にJavaScript
今回使用するPerlのバージョンは5.
本稿は、正規表現やオートマトン理論への基本的な知識を前提としています。正規表現に関わる用語などは
ReDoS ── マッチ時間の爆発によるDoS
正規表現のマッチには非常に多くの時間がかかることがあり、これを利用してサーバの計算リソースを枯渇させるDoS
マッチの実装方法── DFA型とVM型
正規表現マッチの実装方法は大きく分けて
VM型のバックトラックは爆発する
VM型の実装では、オートマトン理論のNFA
VM型の実装では、正規表現の分岐(a|b)で左側にマッチするかを試して、失敗した場合は分岐前の状態に戻り、右側にマッチするかを試します。分岐前の状態に戻る動作がバックトラックです。繰り返し(a*)の場合も、ループを繰り返すか抜けるかの分岐が生じ、バックトラックが起こります。
バックトラックは特定の場合に計算量が爆発します。正規表現^(a|a)*$は文字aのみの文字列にマッチする正規表現です。(a|a)の部分は一見すると冗長ですが、VM型のマッチの計算量を大きく変化させます。文字列abに対するマッチの過程は図1で、1文字目のaに対して左のaでマッチし、2文字目で失敗して❶でバックトラック、次に右のaでマッチするが❷でもう一度バックトラックをして、全体でマッチに失敗することを表しています。文字列aabの場合は図2に示すものになります。
^(a|a)*$のabに対するマッチの過程
^(a|a)*$のaabに対するマッチの過程
aが1文字の場合はバックトラックが2回で、aが2文字の場合は4回と、指数的にバックトラックの回数が増加しています。このまま増加すると、aが3個で8回、4個で16回、そして30個で10億回以上と、バックトラックの回数が爆発します。これがReDoSが発生する原因です。
ReDoSの事例
よく知られたWebサービスでのReDoSの事例を2つ紹介します。
2016年6月、StackOverflowがReDoSによって34分間ダウンする事例がありました。報告によると、原因となったのは文字列の末尾の空白を取り除く非常に単純な正規表現でした。この正規表現を利用する部分を、文字列の置換に修正して対処したようです。
2019年7月、CloudflareがReDoSによって27分間ダウンする事例がありました。Webアプリケーションファイアウォールに設定された正規表現が原因のようです。各正規表現に問題がないことを調査し、正規表現実装をDFA型のものに切り替えて対処したとのことです。
ReDoSの原因
ReDoSの原因となる2種類のバックトラックの爆発のしかたを掘り下げて解説します。経験的にReDoSを理解していた人も、これらの原因を意識することで、より理論的な観点からReDoSに対処できます。
指数的な場合
1つ目の爆発のしかたは、マッチの計算量が文字列の長さに対して指数的となるものです。^(a|a)*$や^(a*)*$などの正規表現が相当します。
指数的なマッチ時間の増加の様子は次のスクリプトで確認できます。実行結果を見ると、1文字増えるごとに倍になっていることがわかります。
const re = /^(a|a)*$/;
for (let i = 25; i <= 30; i++) {
console.time(i);
re.exec('a'.repeat(i) + 'b');
console.timeEnd(i);
}
$ node exp.js 25: 1.622s 26: 508.272ms 27: 1.001s 28: 2.019s 29: 4.028s 30: 8.099s
※最初だけ時間がかかっているのは、おそらく最適化のため
EDA構造── 指数的な場合の原因
「繰り返しの中に同じ文字列でのマッチのしかたが2通りあること」
正規表現から直接構成した
そして、EDA構造が遷移関数に存在することは、マッチの計算量が指数的になることの必要十分条件です。つまり、EDA構造の存在を判定することで、マッチの計算量が指数的かどうかがわかります。
2乗的な場合
もう一つの爆発のしかたは、計算量が文字列の長さに対して2乗的となる場合です。指数的な場合ほど爆発的にマッチ時間が増加するわけではないのですが、大きな入力を受け取る場合に問題となります。実際、前述したStackOverflowとCloudflareの事例で問題となったのは2乗的な場合の正規表現でした。また、指数的な場合ほど短い入力で異常な挙動を示すわけではないので、開発中にテストなどで見つけることが難しいです。2乗的な場合の簡単な例は^a*a*$で、a*が連続している部分が冗長で、爆発の原因となっています。
2乗的なマッチ時間の増加の様子は次のスクリプトで確認できます。文字列の長さが2の平方根倍になると、マッチ時間が2倍になっていることがわかります。最初の文字列の長さを10000としているのは、マッチ時間の増加が緩やかなためです。
const re = /^a*a*$/;
for (let i = 10000; i <= 40001;
i *= Math.sqrt(2)) {
const n = Math.floor(i);
console.time(n);
re.exec('a'.repeat(n) + 'b');
console.timeEnd(n);
}
$ node poly.js 10000: 143.374ms 14142: 281.841ms 20000: 562.782ms 28284: 1.119s 40000: 2.237s
IDA構造 ── 2乗的な場合の原因
2乗的な場合の原因となる構造はIDA
また、このIDA構造がNFAの遷移関数中にいくつも連続すると、計算量はその個数だけ3乗的、4乗的……と上昇します。
見た目で判断することの難しさ
マッチ時間の爆発する原因となる構造を正規表現の見た目として説明します。
- 同じ文字列でマッチのしかたが2通りある繰り返しが存在する
（指数的な場合） - 繰り返しの間の文字列で、それらの繰り返しを1周できる
（2乗的な場合）
よって、この2つに気を付けて正規表現を書けばマッチ時間の爆発は起こらなそうです。しかし、この2つに注意して正規表現を書くことは現実的ではありません。たとえば、^(a|b|ab)*$は指数的に爆発する正規表現です。abに対するマッチのしかたが2通りあることが原因なのですが、繰り返しをまたいで考える必要があるためわかりづらいです。実際にはドットや文字クラスなどのメタ文字もあり、正規表現の見た目で判断するのはより困難になります。
ReDoS対策としてよく挙げられる
＜続きの