正規表現によるDoS(Deny of Service)を調べてみた。

Wikileaksへの(or 周辺から)のDDoSとかで、DoSって単語をちょくちょく聞くのでふと気になって調べてみた。

例えば、namazuを使って全文検索を行っているサイトで以下の検索を行うと、デフォルトで60秒間めいっぱいCPUに負荷を掛けることができます。この性質についてはnamazu公式サイトでも言及されてています。(http://www.namazu.org/security.html)

/(.|.){200}/

これは正規表現の性質によるもので、真面目に解釈すると

任意文字Aにマッチするか、任意文字Bにマッチするかの連続が200回続く文字列

を検索する事になります。ここではわかりやすいように最初の.をA、後の.をBと表現していますが、実際にはどちらも「任意文字」なので両方ともマッチします。両方ともマッチするので、コンピュータは馬鹿正直に両方の可能性があるものとして、色々試すことになります。つまり2の200乗という途方もない組み合わせを試そうとします。もちろん、途中で一個でも達成できるものがあれば良いですが、200文字未満のモノには絶対にマッチできないので、無駄な試行錯誤を行い続ける事になります。

こういう風に正規表現で「|」で繋がれた左右の要素が同じ文字を受理できるのは危険です。普通はそんなミスしないですが、google code seachで調べる限り。

(\w|_|\d)*

というコードが散見されます。これは危険です。

ちなみに同じ意味をもつ下ようなコードは実装上安全になっています。（私が調べた実装では）

[\w_\d]*

逆に、|を使わなくても以下のように、()の外で解釈しても中で解釈してもという暗黙の条件分岐が出る場合も危険です。

(a+)+

詳しく知りたい人は「ReDoS」でググって下さい。

実際どの程度までが危険なのかを調べてみました。

調べたのはruby,php,perl,.NET,java(私の好きな順）。

調べた正規表現は

• A: (.|.){200}


• B: ^(\w|_)+$


• C: ^(_+)+$


• D: ^((((\w|_)+)a)|(((\w|_)+)b))$

結果

実行してみて、すごい長い時間かかったorエラーで返ったものについてXをつけています。

_	ruby	php	perl	.NET	java
A	X	X	O	X	X
B	X	X	O	O	X
C	X	X	O	X	X
D	X	X	O	O	X

ほぼ壊滅ですがperl強いです。perlが強いのはReDoS対策されているという意味ではなくて、単に尋常じゃない最適化が掛かっているためです。.NETも健闘していますが(\w|_)+には耐えるが、(\w|.)+だと何故か駄目といった風に、よくあるミスをリカバーしているだけなのかなぁ？という印象もあります。

（もっと攻めてみないとわからないけれども）

ちなみに以下のようにトリッキーなのはさすがのPerlも駄目でした。

"_________________b___b___ab_dbabdbbababababbabababbababbab________abbabababbababbabab___________ababbababababbabababababaababba___ba_ba________b_a___________b__b___________b_________bc"

=~ /^(((\w)+)b){50}(((\w)+)b)$/ ;

(被検索単語のほうに入っているaとか_は深い意味ないです試行錯誤の跡です。)

PHPのエラー処理について

また、気をつけなきゃ行けないのはPHPのエラー時の動きです。PHPはデフォルトで非常に短い試行時間で処理をあきらめます。これによってDoS状態を抜けています。

(http://www.php.net/manual/ja/pcre.configuration.php#ini.pcre.backtrack-limit)

PHPで当該のエラーになると、preg_matchの場合はマッチしなかった事になります。またpreg_replaceは置換後の文字列が空文字列になります。たしかに何かの脅威を取り除くときの使い方は基本ブラックリスト方式なのでスマートな解決だなぁ、と思うのですが、それで問題になるようなケースではちゃんとpreg_last_errorを使って明示的にエラーが無かったか調べる必要があります。

まとめ

• 正規表現でユーザから入力させるのは気をつけよう。(ReDoSやられる）


• \w|_とか恥ずかしいコード書かない(ちゃんと理解してから書く)


• 複雑な正規表現を書くと、そういったミスをしがちなので、タイムアウトなどのReDoS対策をとる


• 特に()+とか|とか出てるときは、気をつける