Perl Hackers Hub

第74回正規表現の脆弱性「ReDoS」徹底解説 ~原理と対策から、Perlでの最適化まで(1)

本連載では第一線のPerlハッカーが回替わりで執筆していきます。今回のハッカーは藤浪大弥さんで、テーマは「ReDoS徹底解説」⁠1)です。

ReDoS解説にあたって─⁠─ 本稿の構成など

正規表現に関わる脆弱性として「ReDoS」があります。本稿の前半では、ReDoSとはどんな脆弱性でなぜ発生するのか理論的な立場から詳細に解説し、対策のためにすることをいくつか紹介します。後半では、ReDoSへの対策あるいはマッチの高速化のための、Perlでの正規表現実装上の工夫を紹介します。

後半で説明しますが、Perlの正規表現実装にはさまざまな工夫があり、標準的な実装とはやや異なる部分があります。Perlを使ってReDoSの説明をすると本質的でない部分が生じてわかりづらくなるため、前半では解説にJavaScript(Node.js)を利用します。

今回使用するPerlのバージョンは5.36.0、Node.jsは18.4.0です。動作確認はMacBook Pro 2021(Apple M1 Pro、メモリ32GB)上で行いました。

本稿は、正規表現やオートマトン理論への基本的な知識を前提としています。正規表現に関わる用語などは『正規表現技術入門』[1]を参考とします。

ReDoS ─⁠─ マッチ時間の爆発によるDoS

正規表現のマッチには非常に多くの時間がかかることがあり、これを利用してサーバの計算リソースを枯渇させるDoSDenial of Service、サービス拒否)攻撃が成立します。このDoS攻撃はReDoSRegular Expression Denial of Serviceと呼ばれ、近年多くのWebサービスなどで問題となっています。

マッチの実装方法─⁠─ DFA型とVM型

正規表現マッチの実装方法は大きく分けて「DFADeterministic Finite-state Automaton型」「VMVirtual Machine、仮想マシン)型」の2通りが存在します。DFA型は、マッチ対象の文字列の長さに比例する時間でマッチが終了することが保証でき、ReDoSが起こりません。しかし、DFA型はメモリ消費量や実行速度の点で、多くの場合はVM型よりも不利なため、RubyやPerlなどの正規表現実装はVM型を採用しています。

VM型のバックトラックは爆発する

VM型の実装では、オートマトン理論のNFANon-deterministic Finite-state Automaton、非決定性有限状態オートマトン)の挙動をバックトラックで実現してマッチを行います。

VM型の実装では、正規表現の分岐(a|b)で左側にマッチするかを試して、失敗した場合は分岐前の状態に戻り、右側にマッチするかを試します。分岐前の状態に戻る動作がバックトラックです。繰り返し(a*)の場合も、ループを繰り返すか抜けるかの分岐が生じ、バックトラックが起こります。

バックトラックは特定の場合に計算量が爆発します。正規表現^(a|a)*$は文字aのみの文字列にマッチする正規表現です。(a|a)の部分は一見すると冗長ですが、VM型のマッチの計算量を大きく変化させます。文字列abに対するマッチの過程は図1で、1文字目のaに対して左のaでマッチし、2文字目で失敗して❶でバックトラック、次に右のaでマッチするが❷でもう一度バックトラックをして、全体でマッチに失敗することを表しています。文字列aabの場合は図2に示すものになります。

図1 ^(a|a)*$abに対するマッチの過程
図1
図2 ^(a|a)*$aabに対するマッチの過程
図2

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通りあること」が指数的な場合の原因です。ですが、この言い方はややあいまいです。より形式的な説明のため、オートマトン理論の言葉を用います。

正規表現から直接構成した(最適化などをしていない)NFAを考えます。このNFAの遷移関数中に、ある状態qから同じ状態に戻ってくる遷移のしかたが同じ文字列wに対して2通り存在することが、指数的な場合の原因です。これはEDAExponential Degree Ambiguity構造と呼ばれます図3⁠。ジグザグの矢印は、複数状態をまたがる可能性のある、空ではない文字列での遷移を表しています。

図3 EDA構造
図3

そして、EDA構造が遷移関数に存在することは、マッチの計算量が指数的になることの必要十分条件です。つまり、EDA構造の存在を判定することで、マッチの計算量が指数的かどうかがわかります。

2乗的な場合

もう一つの爆発のしかたは、計算量が文字列の長さに対して2乗的となる場合です。指数的な場合ほど爆発的にマッチ時間が増加するわけではないのですが、大きな入力を受け取る場合に問題となります。実際、前述したStackOverflowとCloudflareの事例で問題となったのは2乗的な場合の正規表現でした。また、指数的な場合ほど短い入力で異常な挙動を示すわけではないので、開発中にテストなどで見つけることが難しいです。2乗的な場合の簡単な例は^a*a*$で、a*が連続している部分が冗長で、爆発の原因となっています。

2乗的なマッチ時間の増加の様子は次のスクリプトで確認できます。文字列の長さが2の平方根倍になると、マッチ時間が2倍になっていることがわかります。最初の文字列の長さを10000としているのは、マッチ時間の増加が緩やかなためです。

リスト 2乗的な爆発を確認するスクリプト
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);
}
端末 2乗的な爆発を確認するスクリプトの実行結果
$ node poly.js
10000: 143.374ms
14142: 281.841ms
20000: 562.782ms
28284: 1.119s
40000: 2.237s

IDA構造 ─⁠─ 2乗的な場合の原因

2乗的な場合の原因となる構造はIDAInfinite Degree Ambiguity>構造と呼ばれます図4⁠。ある状態pからqへと遷移する文字列wで、p自身、q自身へと戻る遷移も可能な状況を表しています。直感的には、文字列wが繰り返された場合に、どこでpからqへと遷移するかがあいまいなため、計算量が2乗的になるわけです。IDA構造の存在も、マッチの計算量が2乗的となることの必要十分条件です。

図4 IDA構造
図4

また、このIDA構造がNFAの遷移関数中にいくつも連続すると、計算量はその個数だけ3乗的、4乗的……と上昇します。

見た目で判断することの難しさ

マッチ時間の爆発する原因となる構造を正規表現の見た目として説明します。

  • 同じ文字列でマッチのしかたが2通りある繰り返しが存在する(指数的な場合)
  • 繰り返しの間の文字列で、それらの繰り返しを1周できる(2乗的な場合)

よって、この2つに気を付けて正規表現を書けばマッチ時間の爆発は起こらなそうです。しかし、この2つに注意して正規表現を書くことは現実的ではありません。たとえば、^(a|b|ab)*$は指数的に爆発する正規表現です。abに対するマッチのしかたが2通りあることが原因なのですが、繰り返しをまたいで考える必要があるためわかりづらいです。実際にはドットや文字クラスなどのメタ文字もあり、正規表現の見た目で判断するのはより困難になります。

ReDoS対策としてよく挙げられる「正規表現の繰り返しをネストしない」が必ずしも正しいわけではないことも、本節の内容からわかるはずです。

<続きの(2)こちら。>

おすすめ記事

記事・ニュース一覧