アカウント名:
パスワード:
3、4年くらい前に話題になったやつだね。自分も仕事でウッカリやっちまわないかと思うとワラエナイ。パフォーマンスとしての話題正規表現:悪い表現、いい表現、最良の表現 [postd.cc]脆弱性としての話題StackExchangeが攻撃されたReDoSの効果 [ohgaki.net]
正規表現のバックトラックの落とし穴の話自体は随分前に聞いた気がする。先輩からだったかなあ。その時に、くれぐれも注意して使えと釘を刺された覚えが。
「Mastering Regular Expressions」 https://www.amazon.co.jp/dp/B007I8S1X0/ [amazon.co.jp]とりあえずコレが2006年で、バックトラックは便利だけど効率上の落とし穴があるとは書いてる。(詳しくはチャプター6をヨメってさ。)
初版の方は未確認だけど、その頃から知ってる人は知ってた話なのでは。それこそ正規表現エンジンを作ってる側の人は、その性質も込みだから最初から知ってたろうしね
つーか愚直に探索するとありきたりな表現でもくっそ遅い。単純文字列検索ですら、BM法がアルゴリズムの教科書の定番ネタだったりするくらいだし、実用の正規表現エンジンが愚直な実装であることを前提とするのは素人もいいところかと。正規表現は遅いのが当たり前で、そこから各自高速化されているのも当たり前。
そして最終的には「そのエンジンで」高速に処理できないパターンになってるかどうかの問題になる。特定の構造が遅い速いってのは環境依存のあるTipsかと。
>単純文字列検索ですら、BM法がアルゴリズムの教科書の定番ネタだったりするくらいだし、単純文字列検索「だから」そういう原始的な高速化技法があるんでしょ。不特定多数の複雑なパターンマッチにおいては、一般的な最適化技法はないと思う。
仮にあっても、その正規表現を数回しか使用しないのであれば、最適化にかかる時間の方が、最適化によって短縮される時間より長くなって本末転倒。正規表現部分を何万回も何十万回も使ってボトルネックになる場合は、一流のプログラマなら正規表現なんて使わない形に書き直す。
なので不特定多数の正規表現の汎用的な最適化なんて不可能だし実装してないんじゃないだろうか。
JavaのHotSpotVMによって高度な動的最適化が日常的に利用可能になったから、そこで行われている最適化がどれほど無茶なことか分からない初心者も増えてしまったのかもしれない。HotSpotVMは、もはや初心者の理解を超えてるもんね。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
犯人は巨人ファンでA型で眼鏡をかけている -- あるハッカー
正規表現のバックトラック (スコア:5, 参考になる)
3、4年くらい前に話題になったやつだね。
自分も仕事でウッカリやっちまわないかと思うとワラエナイ。
パフォーマンスとしての話題
正規表現:悪い表現、いい表現、最良の表現 [postd.cc]
脆弱性としての話題
StackExchangeが攻撃されたReDoSの効果 [ohgaki.net]
Re: (スコア:0)
正規表現のバックトラックの落とし穴の話自体は随分前に聞いた気がする。
先輩からだったかなあ。その時に、くれぐれも注意して使えと釘を刺された覚えが。
「Mastering Regular Expressions」 https://www.amazon.co.jp/dp/B007I8S1X0/ [amazon.co.jp]
とりあえずコレが2006年で、バックトラックは便利だけど効率上の落とし穴があるとは書いてる。
(詳しくはチャプター6をヨメってさ。)
初版の方は未確認だけど、その頃から知ってる人は知ってた話なのでは。
それこそ正規表現エンジンを作ってる側の人は、その性質も込みだから最初から知ってたろうしね
Re: (スコア:0)
つーか愚直に探索するとありきたりな表現でもくっそ遅い。
単純文字列検索ですら、BM法がアルゴリズムの教科書の定番ネタだったりするくらいだし、
実用の正規表現エンジンが愚直な実装であることを前提とするのは素人もいいところかと。
正規表現は遅いのが当たり前で、そこから各自高速化されているのも当たり前。
そして最終的には「そのエンジンで」高速に処理できないパターンになってるかどうかの問題になる。
特定の構造が遅い速いってのは環境依存のあるTipsかと。
Re:正規表現のバックトラック (スコア:0)
>単純文字列検索ですら、BM法がアルゴリズムの教科書の定番ネタだったりするくらいだし、
単純文字列検索「だから」そういう原始的な高速化技法があるんでしょ。
不特定多数の複雑なパターンマッチにおいては、一般的な最適化技法はないと思う。
仮にあっても、その正規表現を数回しか使用しないのであれば、最適化に
かかる時間の方が、最適化によって短縮される時間より長くなって本末転倒。
正規表現部分を何万回も何十万回も使ってボトルネックになる場合は、一流の
プログラマなら正規表現なんて使わない形に書き直す。
なので不特定多数の正規表現の汎用的な最適化なんて不可能だし実装してないんじゃないだろうか。
JavaのHotSpotVMによって高度な動的最適化が日常的に利用可能になったから、
そこで行われている最適化がどれほど無茶なことか分からない初心者も増えて
しまったのかもしれない。
HotSpotVMは、もはや初心者の理解を超えてるもんね。