本記事では、正規表現が極端なパフォーマンスの悪化を招く例について扱い、その背景や対策を紹介します。
対象の読者として、基本的な正規表現の記法や用途を把握している方を想定しています。また、アルゴリズムの計算量について概要レベルの理解があると望ましいです。
この記事は正規表現一般について扱うものですが、記事中の例としては JavaScript の正規表現を用います。
JavaScript では、 / と / で囲うことで正規表現を記述します。
ブラウザで Ctrl + Shift + i キーを押して Console タブを開くことで正規表現を手元で実行できますが、数秒間やそれ以上の間処理が返らないようなコードも記載しているため、十分にご注意ください。
処理が終わらない正規表現
複雑な文字列操作を行いたいとき、簡単に書き上げることができる正規表現は非常に重宝するものですね。
専用のパーサを用意しなければならないほど複雑な解析を要する文字列処理というのはほとんどないか、またはそのためのライブラリが提供されているので1、私たちは文字列の中身を検索したり置換したりするときに正規表現を多用します。
ところで、一見単純に見える正規表現でも、プログラムがフリーズしてしまうほど処理が重くなってしまうことがあるのはご存知でしょうか。
たとえば、以下の正規表現を Google Chrome (96.0.4664.110) の開発者コンソール上で実行してみます。
筆者の環境では、結果が返るまでに2秒ほどかかりました。
/(.+)+a/.test("xxxxxxxxxxxxxxxxxxxxxxxxxxx");
マッチさせる文字列の "x" の数をひとつずつ増やしていくと処理にかかる時間が倍ほどになり、すぐに全く結果が返ってこなくなります。(手元で試す際はタブがフリーズする可能性があるため注意してください。新しいタブで実行し、動かなくなった場合はタブを閉じてください)
書かれている正規表現は単純なものですが、それでも計算量が指数関数的に増大し、現実的な長さの入力でプログラムがフリーズしてしまいます。
これがなぜ処理時間の爆発を引き起こすかを理解するためには、正規表現エンジンの挙動についておさらいしておく必要があります。
計算量の爆発を引き起こす正規表現のメカニズム
正規表現の実装による差異
実は、上で触れたような問題はどのような正規表現の処理系にもあてはまるわけではありません。
$ echo "xxxxxxxxxxxxxxxxxxxxxxxxxxx" | egrep "(.+)+a"
egrep コマンドは、正規表現にマッチする行を検索するためのコマンドです。
Linux や Mac の環境がある人は、上のコマンドを実行しても処理が重くなったりせず、また "x" の個数をたくさん増やしてもまったく問題ないことが確認できるでしょう。
これは、正規表現エンジンには大きく分けて2種類の実装があることが関係しています。
つまり、 決定性有限オートマトン (DFA) と 非決定性有限オートマトン (NFA) です。2
一般に DFA を用いた正規表現の実装では、正規表現の実行にかかる時間計算量は入力文字列の長さに対して線形 3 であり、この記事で扱っているような問題とは無縁です。
現代のプログラミング言語では、正規表現に先読みなどの機能が提供されることは一般的となっていますから、多くの言語で NFA を用いた正規表現の実装が行われていると考えてよいでしょう。4
バックトラック
バックトラック(またはバックトラッキングとは、正しい結果が得られなかった場合に少し処理を巻き戻して別のパターンを試していくアルゴリズムです。
以下のような正規表現について考えてみましょう。
/x.*z/.test("vwxyz")
正規表現エンジンは、入力文字列の左から順に正規表現の先頭にマッチするものがあるかどうかを調べていきます。
まずチェックしたい文字列の先頭の v を見に行きますが、これは x ではないのでマッチしません。
同様に w もスキップされ、次の x に到達します。
そうすると、正規表現の先頭の x はマッチしましたから、その次に .* のパターンがマッチするかを確認します。
.* は任意の文字の0回以上の繰り返しを表現していますが、 * のような繰り返しを指定するパターンは、可能な限り長くマッチさせることを試みます。
つまり、 .* に当てはまる文字列として、残りの文字列全体である yz が最初に候補に上がります。
しかしこの場合、その次に正規表現の z にマッチさせたいのですが、すでに文字列の末尾に達しているためマッチすることができません。
そこで、ステップを巻き戻し、 .* に当てはまる文字を一文字短くして、 y として試していきます。
すると次のパターンは z で、見ている入力の文字も z ですから、うまく正規表現にマッチすることがわかります。
このように一度マッチに成功すると、正規表現エンジンはただちに処理を終了し、成功として結果を返します。
簡単な例についてだけ見てみましたが、以下のことがわかります。
- 入力された文字列の先頭から順にパターンに一致するか調べていく
- パターンに一致するか調べるときは、正規表現の先頭から順にパターンに当てはまるか調べる
- 繰り返しがある場合はできるだけ長くとり、その後のパターンで失敗したら戻ってきて一文字短くしてやり直す
- 正規表現のパターンの末尾まで一致したら、その時点で成功とする
- (最後まで試行して一致することがなかった場合には失敗となる)
このように、パターンのマッチに失敗したら前の手順に戻し、別のマッチを試していくアルゴリズムをバックトラックといいます。
おおむね愚直に再帰を書いて実装したらそうなるだろう、と考えられるような挙動そのままなので、深さ優先探索のようなアルゴリズムに慣れていると雰囲気をつかみやすいかと思われます。
バックトラックでの計算量増大
最初の正規表現に戻ってみましょう。わかりやすくするため、入力に与える文字列を変えてみます。
/(.+)+a/.test("0123456789");
この正規表現が入力の長さに応じて極端な計算量の増大を招くことは、さきほどのようにバックトラックの動作をたどることで理解できます。
正規表現エンジンは先頭から順にパターンにマッチさせようとしますから、まずは入力文字列の先頭から、.+ がマッチするかを調べていきます。
ここで、+ は * 同様に長く取れるだけ取ろうとするので、最初は 0123456789 に当てはめることになります。
そうすると今見ているのは入力の末尾(9の後ろ)です。
.+ にマッチする文字はもうないので .+ を2回繰り返すことはできず、 (.+)+ には 0123456789 がマッチします。
そして最後に a があるかどうかを確認し、当然失敗するためバックトラックで処理を戻します。
最初の .+ を 0123456789 にマッチさせてうまくいかなかったので、かわりに 012345678 をマッチさせます。
そうすると .+ の2回目に 9 がマッチしますが、同様に a はないので正規表現全体を一致させることはできません。
次に 01234567 のマッチを試みますが、このあたりから雲行きが怪しくなってきます。
まだマッチさせていない文字列に 89 が残っていますが、2回目の .+ として 89 と 8 を当てはめる場合の2通りを試行し、どちらも失敗します。
これを巻き戻し、 0123456 を最初にマッチさせて 789 を残します。この部分は、 [789] [78][9] [7][89] [7][8][9] のように4パターンが試されます(一度の .+ にマッチする文字列を [] で囲っています)
これを進めていくと、以下のように膨大なパターンが順に試されていくことがわかります。
[0123456789]
[012345678][9]
[01234567][89]
[01234567][8][9]
[0123456][789]
[0123456][78][9]
[0123456][7][89]
[0123456][7][8][9]
[012345][6789]
[012345][678][9]
[012345][67][89]
[012345][67][8][9]
[012345][6][789]
[012345][6][78][9]
[012345][6][7][89]
[012345][6][7][8][9]
...
結果的に、0123456789をグループごとに分ける場合の全パターンを試すことになるので、入力の長さを $n$ とすると $2^{n-1}$ 回の試行が行われることになります。
さらに、先頭からのマッチがすべて失敗したらその右の文字を見て順に同じことを繰り返すので、全体では $2^{n-1} + 2^{n-2} + ... + 2^0 = 2^n-1$ 回の計算が行われます。
計算量のオーダーでいえば、 $O(2^n)$ ですね。
バックトラックでは全パターンを試さなければ失敗という結論を出すことができないので、このような膨大な数の試行をすべて実行し、計算時間が爆発してしまいます。
ほかの遅い正規表現の例
たしかに先ほどの例では正規表現の計算量が極端に増大することがわかりました。
しかしそれはあくまで意図的に不具合を起こそうとして書いた例であって、普段書いている正規表現でそのような問題が生じるとは限らないのではないでしょうか？
残念ながら、より実際の使用例に近い正規表現であっても、書き方によって同様の問題が生じてしまいます。
まだ多少作為的ではありますが、以下の正規表現を見てみましょう。5
const regexp = /^https?:\/\/([^/]+)\/((?:.*\/)+[^/?]*)\?(.*)$/;
regexp.exec("https://example.com/////////////////////////index.html")
これは、 "https://example.com/index.html?param=value" のような URL を受け取り、ドメイン名とリクエストパス、およびクエリパラメータを抽出する正規表現で、 URL の形式が正しくなかったりクエリパラメータが設定されていないとマッチしません。
この例では、コード中に書いたように / が大量に並んでいるような文字列を受け取り、かつマッチに失敗すると処理が非常に重くなります。
ここで悪さをしているのは ((?:.*\/)+ の部分で、先ほどの単純な例のように、繰り返しを含んだパターンをさらに繰り返すことがパフォーマンスの悪化を招いています。
実際にはこの例では ((?:.*\/)+ と書く必要はなく、 単に .*\/ とすれば意図していたことは実現できています。
しかし、複雑な正規表現では、本来はよりシンプルに書けるところを非効率的に書いてしまったり、ちょっとした書き違いをしてしまうおそれは十分にあります。
その正規表現が問題なく動いているように見えるのであれば、多少まわりくどい書き方をしているぐらいなら許容されるかもしれません。
ここで問題となってくるのは、以下の点でしょう。
- 複雑な正規表現の一部にパフォーマンスの悪化を招くパターンが含まれていても、そのことに気付きづらい
- 成功する入力やちょっとした失敗の入力では問題なく動き、不具合の発覚が遅れることがある
動作確認の範囲では問題なく動いていて、しかも複雑で読みづらい正規表現の場合、意図せずにフリーズの危険性があるパターンが書かれていても見過ごされてしまう可能性が非常に高くなっています。
ReDoS 攻撃
計算量オーダーの高い正規表現は、サービス全体の脆弱性となってしまう可能性もあります。
クライアントサイドで正規表現が応答を返さなくなるとアプリがフリーズし、サーバーサイドの場合にはシステム障害に発展してしまうおそれがあります。
正規表現の実行に高い負荷がかかったことによって、 2016年には Stack Exchange のネットワークが一時的にダウンする事態に陥りました。
このレポートによると、障害の起因となった正規表現は以下のようなもので、「文字列の末尾の空白を見つける」という非常にシンプルなものでした。
/\s+$/
この正規表現がどのように実行されるのか見ていきましょう。
ほかの正規表現の例でも見たように、マッチに失敗するときに計算時間が大きくなってしまう傾向がありました。
そこで以下のように、空白が10個並んでいて、その後ろに \s にマッチしない文字 (a) があるような文字列を入力として与えてみます。
" a"
バックトラックのアルゴリズムでは、まず入力文字列の先頭を見て、 \s+ にあてはまる文字列を可能な限り長く取ろうとするのでした。
そのため、最初は空白が 10個並んだ文字列を \s+ にマッチする候補としてあてはめます。
しかし文字列の末尾には a が残っていますから、 $ にマッチさせることができずにこの試行は失敗します。
正規表現エンジンは \s+ にあてはまる候補として 9個, 8個, 7個... と順番に空白の数を減らしていきますが、この正規表現全体をマッチさせることはできないため、10回試してすべて失敗することになります。
そうすると今度は入力文字列の 2文字目から同じことを繰り返し、今度は空白 9個から始めて 9回試行されます。
最終的には、空白の個数を $n$ 個として $n + (n-1) + (n-2) + ... + 1 = \frac{1}{2}(n^2-n)$ 回だけ処理が実行されます。
つまり、計算量のオーダーは $O(n^2)$ となることがわかります。
前に見た $O(2^n)$ のような指数関数的に負荷が増大する正規表現と比較するとずいぶん控えめに見えますが、これでもサービスをダウンさせるには十分でした。
一般的に、普通のマシンが 1秒間に行うことのできる単純な繰り返し処理の回数は $10^8$ 回から $10^9$ 回ですから、 $n$ に数万程度の値を入れると処理に 1秒以上要することになります。
Stack Exchange の例では、空白が 2万文字続いたあとに空白以外の文字を付け足した文字列が与えられてサーバーが応答しなくなり、当該ページがロードバランサのヘルスチェックに使われていたためにサービス全体の停止に発展しました。
この例では、指数関数的に負荷が増大するほどの破滅的な正規表現パターンでなくても $O(n^2)$ 程度の計算量を要することがあり、それでも十分にサービスに打撃を与える可能性を孕んでいることを紹介しました。
このように正規表現に特定の入力を与えることでマッチ処理のハングを狙う DoS 攻撃を、 ReDoS といいます。
対策について
正規表現をとりまく問題について見てきましたが、これらはどのように対策することができるでしょうか。
すべての正規表現の脆弱性を一目で見極められる正規表現マスターになる、という方法よりは簡単そうな対策をいくつか考えてみましょう。
正規表現のユニットテスト
パフォーマンスの問題を抜きにしても、正規表現が意図通りに書けているかどうかをチェックするためにユニットテストを書くことは重要ですね。
この記事で扱った例では、マッチ失敗かつ特定の文字が多く含まれている場合に問題が発生していました。
正規表現が失敗するときのほうが計算に要する時間が長くなりやすいので、とても長い入力でかつマッチに失敗する例をテストケースに用意しておくよう意識すると、パフォーマンスの問題を発見できることがあるかもしれません。
しかし、不具合が含まれているにもかかわらず用意したテストケースをすべて通過してしまう可能性については留意する必要があります。
URL に対する正規表現の例では、 文字列中に / が大量に含まれている場合にのみ処理時間が爆発するようになっていたので、単に文字数が長いだけのテストケースでは問題が発見できない可能性があります。
ユーザーに正規表現を入力させない
ユーザーに正規表現を入力させるような実装は、 ReDoS 攻撃のリスクだけでなく、正規表現インジェクション https://blog.ohgaki.net/regular-expression-injection を受けるおそれもあるため非常に危険です。
ユーザーが入力した文字列を正規表現の一部のパターンとして検索する、といった場合も同様の問題が発生するため、使用できる文字を制限するか、正規表現を使わずに実装しましょう。
正規表現にかける前にチェックを行う
リクエストのバリデーションに正規表現を用いるような場合には、事前にチェック可能な項目の確認を済ませてから正規表現にかけるようにしましょう。
とくに入力の長さを事前にチェックしておくことで、数万文字の文字列のマッチングを実行する前に弾くことができます。
正規表現の実行にかかる時間を計測する
正規表現の実行前に時間の計測を開始し、一定時間が経過しても結果が出ない場合はログに出力してエラーを返す、というようなユーテリティを書くことが考えられます。
結果が出るまで 1時間待つかわりに 1秒でエラーが返ってくるようにすれば、システム全体の停止に繋がることは避けられるでしょう。
同時にパフォーマンスのよくない正規表現の発見にもつながるため、大きな効果が期待できますね。
ただし、以下の点には注意する必要があります。
- 一度開始したマッチングを途中でキャンセルできない正規表現ライブラリが多い
- (この場合、 CPU が占有されてしまうリスクを低減することが難しい)
- 問題が実際に発生した時の対策であるため、事前に気付けるわけではない
- 必ず実行時間の計測を挟むよう徹底しないと、「このくらいの小さな正規表現なら大丈夫だろう」と思ってそのまま書いた正規表現で問題が起きるかもしれない
正規表現の使用を避ける
そのプログラミング言語で提供されている文字列操作によって目的が達成できるのであれば、正規表現を使わないようにするのが効果的な対策といえます。
たとえば文字列の先頭と末尾の空白を取り除くという処理は、 JavaScript であれば以下のように trim() メソッドを使用して実現できます。
" abc ".trim();
ReDoS 攻撃 で紹介した Stack Exchange の例でも、正規表現を使わない処理に置き換えるという形で対策が行われました。
また、あらかじめ文字列を区切り文字ごとに分割するなどして、大きく複雑な正規表現をいくつかの小さな正規表現に置き換えることで、それぞれの正規表現の可読性を上げて不具合を見つけやすくなるかもしれません。
入力のバリデーションのようなよくある処理を行う場合には、自分で正規表現を書くのではなく広く使われているバリデーション用ライブラリを使用するのもよいでしょう。
たとえ内部的に正規表現が使用されていたとしても、多くのユーザーに使われて検証されたものであれば独自に書いた正規表現よりも安全だと考えられます。
おわりに
この記事では、正規表現の実行によって計算時間が爆発してしまう例とその背景・対策を紹介しました。
単純なパターンの正規表現でもパフォーマンスに大きな影響を及ぼすことがあり、また ReDoS のように正規表現を標的とした攻撃を受けてしまうリスクもあるため、正規表現を書く際には常にこのような例について意識しておきましょう。
この記事では扱うことができませんでしたが、Further Readings で紹介している 詳説 正規表現 第3版 では正規表現のパフォーマンスを高めるテクニックが紹介されています。
各々の開発者がパフォーマンスのよい正規表現を書けるようにすることで問題に気づきやすくなるかもしれませんから、バックトラックのような実行アルゴリズムも意識しつつ正規表現への理解を深めていきたいものです。
また、正規表現を解析してパフォーマンスの良くないパターンを発見するような手法も、研究レベルでは進められているようですが6 実用的なツールとしてはあまり聞いたことがないように思えます。
型チェックやユニットテストなどと同様に、プログラム中に書いた正規表現が解析されて自動的にチェックされるような時代がくるといいですね。
Further Readings
詳説 正規表現 第3版
全編を通して正規表現に関する詳細な解説がなされています。
4章ではパフォーマンスを考える上で重要となる正規表現のメカニズム、6章ではパフォーマンスのよい正規表現を書くテクニックが扱われています。
コンパイラ[第2版] 原理・技法・ツール
3章では正規表現を NFA および DFA に変換するアルゴリズムについて詳細に解説されています。
宣伝
DeNA 公式 Twitter アカウント @DeNAxTech では、 Blog記事だけでなく色々な勉強会での登壇資料も発信しています。ぜひフォローして下さい！
Follow @DeNAxTech
-
JSON文字列をパースするJSONライブラリなど ↩
-
CS系の専攻の方は、「オートマトンと言語理論」のような名前の講義で触れたことがあるかもしれません。そのような方には説明は不要でしょうし、そうでない方も違う種類のものがあるということだけ頭に留めていただければあまり気にしなくて大丈夫です。詳しく知りたい場合は Further Readings を参照してください。 ↩
-
あらかじめ用意された DFA の遷移表を入力文字数分だけ遷移することから明らか
上で例示したegrepコマンドは DFA による正規表現の実装が行われているため、正規表現の実行が極端に重くなることを回避できています。
一方で、 DFA では正規表現の先読みや後読み、最短一致のような拡張的な機能を実現することができません。 ↩ -
または、DFA と NFA の両方を組み合わせ、正規表現の内容に応じて高いパフォーマンスが発揮されるように使い分けが行われているかもしれません。
NFA を利用した実装では、バックトラックという方式によって正規表現のマッチ処理が行われており、これが本記事で扱う問題について大きく関わってくることになります。 ↩ -
他人が書いた正規表現を解読することほど疲れることはないので、真面目に読まなくても大丈夫です。 ↩