正規表現とは、ある文字列のパターンを表現するための文法です。Microsoftによる文書[1]には、以下のように記載されています。

正規表現は、通常の文字 (a ～ z など) と、”メタキャラクタ” という特殊文字から構成される文字列のパターンです。パターンによって、テキスト本文を検索するときに一致する 1 つ以上の文字列を指定します。正規表現は、検索対象の文字列と文字パターンを一致させるためのテンプレートとして機能します。

例えば、日本国内の7桁の郵便番号であれば、以下のように表現することができます。

^\d{3}-\d{4}$

これは、「3桁の数字から始まり、ハイフンを挟み、4桁の数字で終わる」という意味です。

正規表現によるパターンマッチングには、膨大な計算量が必要となることがあります。そのような正規表現を悪用し、計算リソースを占有することで可用性を奪う攻撃を、ReDoS(Regular expression Denial of Service)攻撃といいます。

正規表現は様々な文字列パターンを表現できる反面、デバッグが難しく問題を見つけにくいため、ReDoS攻撃は隠れた脆弱性を突く攻撃と言えるでしょう。

脆弱な正規表現の例として、ここではマッチングさせる文字列によって計算量が大幅に増加しうる正規表現を取り上げます。

例えば以下の正規表現ですが、

A(AB|AC)*A

これは、’A’という文字に’AB’または’AC’の繰り返しが0回以上挟まれているというパターンを表現しています。

この正規表現を受理する非決定性有限オートマトンを状態遷移図で表すと以下のようになります。

上図の丸は全て状態を表していて、矢印の上の文字は入力値を表しています。例えば状態sの時に”A”という入力があった場合は状態q₁に進みます。これを繰り返し、いわば双六のように入力値を1文字ずつ処理しながら、最終的に状態aへ到達した場合に「受理」すなわち正規表現にマッチしたと判定します。

ではどうしてこの正規表現が脆弱と言えるのでしょうか。状態遷移図をよく見ると、同じ入力値で複数の異なる状態に遷移できる分岐があることがわかります。片方の分岐に進み文字列を処理していった結果、次の文字を処理できなかった場合、一旦状態を分岐の前まで戻してから、別の分岐を試行する必要が出てきます。これをバックトラックと言います。つまり、このような非決定性を持つオートマトンに、長いかつ非受理となる文字列を与えると、それだけで計算量が膨大になることがわかります。

一例として”AABACAB”という文字列がこの正規表現にマッチするかどうか判定する処理をステップごとに表します。ここでのアルゴリズムは、複数の遷移先があった場合は最も項番の小さい状態に遷移するとします。

処理No.	現状態	文字位置	入力文字	遷移先	バックトラック
1	qs	1	A	q1	×
2	q1	2	A	q3	×
3	q3	3	B	q4	×
4	q4	4	A	–	×
5	q4	4	A	q6	○(No.4)
6	q6	5	C	q7	×
7	q7	6	A	q3	×
8	q3	7	B	q4	×
9	q4	EOS	EOS	–	×
10	q7	6	A	q6	○(No.7)
11	q6	7	B	–	×
12	q1	2	A	qa	○(No.1)
13	qa	3	B	–	×

前章から、正規表現による計算量増大を防ぐには非決定性によるバックトラックの可能性を排除し、状態遷移図をシンプルにすることが有効だとわかります。

先ほどの非決定性有限オートマトンを決定性有限オートマトンに変換すると下図のようになります。

これを正規表現で表すと以下のようになります。

AA(BA|CA)*

解釈すると「”AA”の文字列の後に、”BA”または”CA”の文字列が0回以上繰り返される」というパターンになり、前出のものより複雑さが減少したことが実感できるのではないでしょうか。

先ほど同様に”AABACAB”という文字列がこの正規表現にマッチするかどうか判定する処理をステップごとに表します。

処理No.	現状態	文字位置	入力文字	遷移先	バックトラック
1	qs	1	A	q1	×
2	q1	2	A	{q3,q6,qa}	×
3	{q3,q6,qa}	3	B	q4	×
4	q4	4	A	{q3,q6,qa}	×
5	{q3,q6,qa}	5	C	q7	×
6	q7	6	A	{q3,q6,qa}	×
7	{q3,q6,qa}	7	B	q4	×
8	q7	EOS	EOS	–	×

正規表現を使用する際、都度状態遷移表を作成して非決定性を排除するのは非現実的だと思われます。そこで、ここでは正規表現による計算量を減らすための原則をまとめます。

独自の正規表現を使わない

正規表現自体を実装せずライブラリ等を用いることで、独自の脆弱性を生じさせる危険を排除します。

繰り返し文字を極力使用しない、繰り返しのネストをしない

先述の例の様に繰り返しは文字列長に対し計算量を爆発的に増大させるだけでなく、非決定性を生じさせます。繰り返しのネストの危険性については[2]が詳しいです。

複数のパターンにマッチするOR演算を極力用いない

ORを入れることにより分岐が増え、アルゴリズムが複雑化します。

可視化ツールやチェッカーを用いる

[3]や[4]のような正規表現を可視化するツールを用いるなどしてアルゴリズムが複雑になっていないかチェックすることができます。特に[4]の”Regex Debugger”という機能では、正規表現と文字列を入力することで、その文字列がどのようなステップで判定されるかを視覚的に確認することができます。

日本電信電話株式会社(NTT)と学校法人早稲田大学は、ReDoS脆弱性を判定し、自動的に修正する技術を実現しました[5][6]。発表ではこの技術について以下の様に述べています。

専門知識をもたない開発者でもこうした正規表現の脆弱性の修正が可能となり、安全なサービスの実現が期待できます。

この成果は、2022年5月22～26日に開催されるセキュリティとプライバシー分野の最難関国際会議IEEE S&P 2022（43rd IEEE Symposium on Security and Privacy）にて、下記のタイトル及び著者で発表されます。(所属組織名は投稿時のもの)

タイトル

Repairing DoS Vulnerability of Real-World Regexes

著者

Nariyoshi Chida (NTT Secure Platform Laboratories), Tachio Terauchi (Waseda University)