2010年12月21日火曜日

正規表現による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をつけています。










_rubyphpperl.NETjava
AXXOXX
BXXOOX
CXXOXX
DXXOOX

ほぼ壊滅ですが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対策をとる

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





2010年12月15日水曜日

目指せ、月光町ちっさいもの倶楽部~



とりあえず、以前つくったチップ部品だけでつくったLED点滅ユニットは、真鍮線で作ったフレームに取り付けて、こんな感じになりました。


http://picasaweb.google.com/lh/photo/EL5gYgzbHBPTomfB5UriQg?feat=directlink


電池はコイン電池(CR2032)です。とりあえずその辺にころがってた電池を使ったのですが、一週間以上持ってます。意外と省エネ。








で。以前LEDが光るだけというミニマルなのでも楽しいよねと言われたので、そっちも真鍮線電池ホルダを作ってやってみた。


http://picasaweb.google.com/lh/photo/CZatY7C12t9iCtyIto8hXA?feat=directlink


ちゃんとランプシェード?もついているっす。


実用性は暗闇では役に立つけどね~程度ですが。。。LEDは電球色LEDをつかってます。


どれくらいの時間電池が持つかはまだ謎。





2010年12月3日金曜日

ちっさな昇圧回路を組んでみた



どれくらいちっさいかというと。ボタン電池よりちいさい


部品は以下の通り




  • HT7733A(3.3Vのときは 5Vのときは7750?)(共立)

  • チップコンデンサ100uFx2(秋月)

  • ダイオードSB1003(秋月)

  • コイル47uH(秋月)


回路はマニュアルのリファレンス通りで、こんな感じ


http://picasaweb.google.com/lh/photo/BxCacRGuQChsYRQ9Q3eViQ?feat=directlink


これをお湯でとける樹脂でかためて絶縁


http://picasaweb.google.com/lh/photo/11HUbVVbUntRrsvYfZII7A?feat=directlink


で。電池をのっけるとこんな感じ。とってもコンパクト


http://picasaweb.google.com/you.akira.noda/BfedPF#5546478863952462450