T.Terada氏の日記
■[セキュリティ]マッチするはずの正規表現がマッチしない現象
http://d.hatena.ne.jp/teracc/20100410/1270885661
の現象および周辺のケースについて、サンプルコードを書いて調べてみた。

※PHP 5.3.8 windows環境で調査

//通常
$str="abcd123";
if (preg_match('/./', $str)) {
    echo "match\n";
} else {
    echo "unmatch\n";
}
→結果:
match

//sオプションが付いていないと改行にはマッチしない
$str="\x0a";
if (preg_match('/./', $str)) {
    echo "match\n";
} else {
    echo "unmatch\n";
}
→結果:
unmatch

//sオプションが付いていれば改行にもマッチ
$str="\x0a";
if (preg_match('/./s', $str)) {
    echo "match\n";
} else {
    echo "unmatch\n";
}
→結果:
match

//否定の文字セットの場合、/sをつけなくても改行にマッチ
$str="\x0a";
if (preg_match('/[^a-z]/', $str)) {
    echo "match\n";
} else {
    echo "unmatch\n";
}
→結果:
match

//PCRE のバックトラック処理の上限を超える場合にマッチしなくなる

echo "PCRE のバックトラック処理回数の上限を超える場合にマッチしなくなる\n";
echo 'pcre.backtrack_limit:'.ini_get('pcre.backtrack_limit')."\n";
$bklimit = ini_get('pcre.backtrack_limit');

echo "case 1:マッチするケース。\n";
$str='a a';
for($i=0;$i<$bklimit-5;$i++){
    $str.=' ';
}
echo "strlen:".strlen($str)."\n";
if (preg_match('/^a(.*)a/s', $str, $match)) {
    echo "match\n";
} else {
    echo "unmatch\n";
}

echo "case 2:マッチしなくなるケース。バックトラック処理回数がここで上限を超える\n";
$str='a a';
for($i=0;$i<$bklimit-4;$i++){
    $str.=' ';
}
echo "strlen:".strlen($str)."\n";
if (preg_match('/^a(.*)a/s', $str, $match)) {
    echo "match\n";
} else {
    echo "unmatch\n";
}

echo "case 3:(参考)文字長は同じでもバックトラック処理が発生しないケースではマッチする\n";
//この場合、a(.*)aが最長マッチで一回目でマッチしてしまうのでバックトラック処理0回(のはず)
$str='a a';
for($i=0;$i<$bklimit-4;$i++){
    $str.=' ';
}
$str.='a';
echo "strlen:".strlen($str)."\n";
if (preg_match('/^a(.*)a/s', $str, $match)) {
    echo "match\n";
} else {
    echo "unmatch\n";
}
→結果:
PCRE のバックトラック処理回数の上限を超える場合にマッチしなくなる
pcre.backtrack_limit:1000000
case 1:マッチするケース。
strlen:999998
match
case 2:マッチしなくなるケース。バックトラック処理回数がここで上限を超える
strlen:999999
unmatch
case 3:(参考)文字長は同じでもバックトラック処理が発生しないケースではマッチする
strlen:1000000
match


正規表現のバックトラック処理:
メタ文字の最長マッチ後に、他の条件にもマッチさせるために、一度取得したメタ文字の最長マッチの長さを一文字ずつ少なくしていって、他の正規表現の条件に当てはまる文字列を見つけ出す処理の事をバックトラック処理という。

a*aaaaa みたいな正規表現の場合、aaaaaaをマッチさせる際に、最初のa*が6文字マッチさせてしまい、それから最終的に1文字まで短くしていってやっと全体の正規表現がマッチする、みたいな時、バックトラック処理が5回走ってa*のマッチを5文字短くしたことになる。

このバックトラック処理に上限値があり、その上限を超えると「マッチしなかった」という結果になるため、PHPの正規表現を使った入力チェック処理の書き方によっては、チェックをすり抜ける値を指定することができてしまう場合がある、ということ。
寺田氏のブログを引用させていただくと「マッチしない場合はチェックOK」というフローは駄目で、突破される可能性がある。

(同様に、PCREの再帰処理にも再帰処理の上限数(pcre.recursion_limit)を超えるとマッチしなくなる問題があるらしいが、正規表現が難解だったので今回は省略。誰か良いサンプル教えてください)

Powered by Blogger.
© WEB系情報セキュリティ学習メモ Suffusion theme by Sayontan Sinha. Converted by tmwwtw for LiteThemes.com.