パフォーマンスを意識して正規表現を書く

正規表現を書く際、どのようなパターンにマッチさせるか、どこをキャプチャするかという視点で記述することはあっても、パフォーマンスを考えて記述するというのはある程度知っている人でなければ忘れがちな視点です。

このエントリでは、バックトラックをメインに正規表現がパフォーマンスに及ぼす挙動について見ていきます。

対象の正規表現エンジン

ここでは、従来型 NFA を対象としています。具体的には、PHP の preg_ 関数で利用している PCRE や mb_ereg 関数が利用している鬼車です。Perl や Ruby、Python、Java、.NET でも従来型 NFA を採用しているので、似た挙動となるでしょう。

「従来型 NFA」や「バックトラック」などの用語については、「詳説正規表現第3版」のものを用いています。

バックトラックによるマッチ探査

正規表現エンジンでは、指定された文字列が、パターンにマッチするかどうかを判別する際、記述された正規表現で取り得るマッチパターンが見つかるように何度もマッチングを行います。

例えば、\d+\d という正規表現があり、これに 123 という文字列がマッチするか preg_match 関数でチェックします。

<?php
var_dump(preg_match('/\d+\d/', '123'));

これを実行すると、\d+ の部分は、文字列 123 にマッチします *1。しかし、次の \d にマッチする文字列が無いので、一つ前のパターン（\d+）に戻ります。次は、\d+ を 12 にマッチさせます。次の \d は、3 にマッチするので、これで全体のマッチが成功します。

下記では、この流れを示しています。()が \d+ に、{} が \d がマッチした箇所で、[]が現在マッチを試みている文字になります。

* (123)[]  <--- `\d+`はマッチするが、`\d`がマッチしないので、`\d+`へ戻る
* (12){3}  <--- `\d+`も`\d`もマッチする

正規表現は、前から順に適用されていくのですが、後続のパターンがマッチしない場合に一つ前のパターンに戻って、別のマッチ方法を試行するのをバックトラック（backtracking）と呼びます。バックトラックは、正規表現に限らず、正しい解を探るためのアルゴリズムです。詳細は、下記で。

https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%83%E3%82%AF%E3%83%88%E3%83%A9%E3%83%83%E3%82%AD%E3%83%B3%E3%82%B0

「マッチしない」を確定させるのは遠い道程

次は、マッチが失敗するパターンとして、正規表現 \d+\d[^\d] を 123 という文字列にマッチさせます。

はじめに \d+ は文字列 123 にマッチします。次の \d にマッチしない（文字列が無い）ので、バックトラックが発生します。次は、\d+は文字列 12 に、\d は文字列 3 にマッチします。最後の [^\d] にマッチしない（文字列が無い）ので、バックトラックが発生します。今度は、\d+ を文字列 1 に、\d を文字列 2 にマッチさせますが、[^\d] と文字列 3 はマッチしません。

次は、文字列の先頭を 1 文字進めて 23 に対してのマッチを試みますが、こちらもマッチには成功しません。さらに、文字列 3 に対するマッチも失敗し、最終的には全てのパターンで失敗します。

下記では、この流れを示しています。()が \d+ に、{} が \d がマッチした箇所で、[]が現在マッチを試みている文字になります。

* (123)[]    <--- `\d+`はマッチするが、`\d`がマッチしないので、バックトラック
* (12){3}[]  <--- `\d+`と`\d`がマッチするが、`[^\d]`がマッチしないので、バックトラック
* (1){2}[3]  <--- `\d+`と`\d`がマッチするが、`[^\d]`がマッチしないので、バックトラック
* 1(23)[]    <--- 1文字進めてマッチング開始。`\d+`はマッチするが、`\d`がマッチしないので、バックトラック
* 1(2){3}[]  <--- `\d+`と`\d`がマッチするが、`[^\d]`がマッチしないので、バックトラック
* 12(3)[]    <--- 1文字進めてマッチング開始。`\d+`はマッチするが、`\d`がマッチしないので、バックトラック
* 123[]      <--- 1文字進めてマッチング開始。`\d+`がマッチせずに終了

このように、「マッチしない」と結論付けるために、指定した正規表現で取り得る全てのマッチングを行います。この挙動が場合によっては、パフォーマンスに大きな影響を及ぼします。

爆発するマッチング

マッチさせるまで（マッチしないことを確定させるため）、あらゆるマッチングを行うがゆえに正規表現や文字列によっては、マッチングの組み合わせパターンが膨大になる可能性があります。

マッチングが膨大になる様を確認するために、regex101.com というサイトを利用します。このサイトでは、正規表現と文字列を指定すると、正規表現エンジンがどのようにマッチングを行っていくかを表示してくれます。

regex101.com

例えば、上記の例（\d+\d[^\d]）であれば、下のような表示となります。これを見ると、文字列 123 に対して、14 steps がかかっていることが分かります。

f:id:shin1x1:20160817160205p:plain

ここで文字列を 123456789 という 9 文字に増やすと、91 steps となります。

マッチングが膨大になる場合を見るために、(\d*\d+)+\d[^\d] という正規表現を利用します。これは、前述の \d+\d[^\d] とマッチする文字列は同じです。このパターンを前述の 9 文字にマッチさせると、なんと 33,805 steps になりました！

https://regex101.com/r/eB0dM5/1

このようにわずか 9 文字の文字列に対するマッチングでも正規表現の書き方によって、マッチングの組み合わせが膨大に膨らむことが分かります。より複雑な正規表現や与えられる文字列が長い場合は、パフォーマンスへの影響が出てきます。

ReDosという攻撃

こうした正規表現エンジンの特性を利用した攻撃が ReDos です。ReDos については、下記の大垣さんのエントリが参考になります。

ReDoSの回避 | yohgaki's blog

特に量指定子（*、?、+、{n,m}）を入れ子にしたり、同じ文字クラスを重ねたりすると組み合わせパターンが多くなるので、こうした問題が起こる可能性があります。

末尾にあるスペースにマッチ

上記の ReDos とは別のパターンですが、単純な正規表現でも DoS を引き起こす場合があります。

stackoverflow.com では、文字列前後のスペースを除去する ^[\s\u200c]+|[\s\u200c]+$ という正規表現に対して 20,000 文字のスペースが含まれた文字列が送信されたために、上記のマッチングの組み合わせが膨大になり、34 分間アクセス不能になるという事態がありました。

Stack Exchange Network Status — Outage Postmortem - July 20, 2016

StackExchangeが攻撃されたReDoSの効果 | yohgaki's blog

大垣さんのサイトでも実証されていますが、Stack Overflow の事例を参考に文字列末尾にあるスペースを正規表現でマッチさせて取り除くという処理を見てみます。

まずは、正規表現を単純化して、\s+$ を利用し、文字列は a（半角スペース 3 文字）にマッチさせる場合で動きを見ます。

この場合、下記のようにマッチングを行なわれます。半角スペースが見えるように _ としています。人間が見れば、文字列の末尾が a なので、どのようにマッチングさせても成功しないのは明白なのですが、正規表現エンジンでは、前から順に愚直に評価していきます。

* (___)[a] <--- `\s+`はマッチするが、`$`がマッチしないのでバックトラック
* (__)[_]a <--- `\s+`はマッチするが、`$`がマッチしないのでバックトラック
* (_)[_]_a <--- `\s+`はマッチするが、`$`がマッチしないのでバックトラック
* _(__)[a] <--- 1文字進めてマッチング。`\s+`はマッチするが、`$`がマッチしないのでバックトラック
* _(_)[_]a <--- `\s+`はマッチするが、`$`がマッチしないのでバックトラック
* __(_)a <--- 1文字進めてマッチング。`\s+`はマッチするが、`$`がマッチしないのでバックトラック
* ___[a] <--- 1文字進めてマッチング。`\s+`がマッチしないのでバックトラック
* ___a[] <--- 1文字進めてマッチング。`\s+`がマッチせずに終了

スペースが 3 文字ではなく、20,000 文字となれば、それだけ多くのバックトラックが発生するため、処理に時間がかかるようになります。

パフォーマンスを計測するために下記のコードを実行してみました。それぞれのスペースの最後には a が付いているのでマッチングは失敗します。

<?php
function benchmark($title, callable $target) {
    echo '# ' . $title, PHP_EOL;
    $start = microtime(true);
    $target();
    echo microtime(true) - $start, PHP_EOL;
    echo PHP_EOL;
}

$strings = [];
foreach ([20, 200, 2000, 20000, 200000] as $no) {
    $string = str_repeat(' ', $no) . 'a';
    benchmark('preg_replace' . $no, function () use ($string) {
        return preg_replace('/\s+$/', '', $string);
    });
}

このコードを PHP 5.6 と 7.0 で実行した結果が以下です。2,000文字あたりから処理速度が低下していき、20,000文字、200,000文字で急激に処理時間がかかっています。なお、5.6 より 7.0 の方が文字数が多い場合は処理が速いので、何かしらの最適化が行われているのかもしれません。

PHP 5.6.24

文字長	実行時間
20文字	0.05ms
200文字	0.35ms
2,000文字	7.2ms
20,000文字	2,438ms
200,000文字	233,513ms

PHP 7.0.9

文字長	実行時間
20文字	0.4ms
200文字	0.2ms
2,000文字	5.8ms
20,000文字	498ms
200,000文字	50,352ms

正規表現を改良

文字列末尾のスペースにマッチングさせる正規表現を改善するために \s++$ に変えてみます。元の最大量指定子（\s+）を絶対最大量指定子（\s++）に変更しただけです。

これでベンチマークを取ると下記のようになりました。両バージョンとも処理速度が改善しており、200,000 文字で見ると、PHP 5.6 で 18 倍、PHP 7.0 で 4 倍と大きな改善となっています。変更後は、PHP 5.6 と PHP 7.0 でほぼ互角になっているのも興味深い点です。

このように正規表現の書き方一つで、大きくパフォーマンスが変わる場合があります。

PHP 5.6.24

文字長	実行時間
20文字	0.17ms
200文字	0.041ms
2,000文字	1.91ms
20,000文字	172ms
200,000文字	12,879ms

PHP 7.0.9

文字長	実行時間
20文字	0.26ms
200文字	0.047ms
2,000文字	1.29ms
20,000文字	123ms
200,000文字	12,544ms

絶対最大量指定子を使った場合（ aへのマッチング）は、下記のようなマッチングを行います。絶対最大量指定子は、貪欲なマッチングとなり、かつマッチした文字列をアトミックに扱います。これにより、バックトラックの発生が抑えられるのでマッチング回数を抑制できます。これは、アトミックグループ（(?>)）でも同様の効果が得られます。

* (___)[a] <--- `\s++`はマッチするが、`$`がマッチしないのでバックトラック
* _(__)[a] <--- 1文字進めてマッチング。`\s++`はマッチするが、`$`がマッチしないのでバックトラック
* __(_)a   <--- 1文字進めてマッチング。`\s++`はマッチするが、`$`がマッチしないのでバックトラック
* ___[a]   <--- 1文字進めてマッチング。`\s++`がマッチしないのでバックトラック
* ___a[]   <--- 1文字進めてマッチング。`\s++`がマッチせずに終了

今回計測したPHPコードは、下記です。

regex_trim.php · GitHub

あえて正規表現を避ける

PHP でこの処理を単純に考えれば、ltrim関数で簡単に実装できます。

ltrim関数を使うと、200,000文字のスペース + a の場合でも、わずか 1ms 以下でした。

stackoverflow.com では、正規表現を使うことをやめ、文字列処理（substring関数）に取り替えたようです。

さいごに

正規表現の書き方や文字列が、パフォーマンスに影響を与えることを見てきました。

マッチングパターンのみに注力して記述した正規表現が、正規表現エンジンによって、上手い具合にチューニングされて動作すれば良いのですが、最適化が上手く働かないケースでは、その挙動を把握した対処を行わないとパフォーマンスの問題を抱えることになります。

このあたりは、SQL にも似たものを感じしますね。

正規表現は、Web アプリケーションにおいてはバリデーションで利用されることが多く、外部の値をいきなり正規表現にかけてチェックするということもあります。バリデーションは成功しないが、DoS となるような値を投げられて、パフォーマンスが低下したり、サービスが停止させられる場合も考えられます。

正規表現のパターンを考慮する、文字列長をチェックしておく、場合によっては正規表現を使わない、など対処法は考えられるが、まずは正規表現がパフォーマンス上の問題になりうるということを認識することが第一歩になるでしょう。

参考

正規表現エンジンの挙動については、下記の 2 冊がとても参考になります。どちらかというと、「詳説正規表現」は正規表現を利用する側、「正規表現技術入門」は正規表現エンジンを実装する側から正規表現を見た本となっています。どちらも内部の動きを分かりやすく解説しているので、本エントリのような内容をより知りたい方には特におすすめです。

どちらも Kindle 版が無いので、電子版を購入する場合は、オライリー社サイト、技術評論社サイトで購入します。