アカウント名:
パスワード:
3、4年くらい前に話題になったやつだね。自分も仕事でウッカリやっちまわないかと思うとワラエナイ。パフォーマンスとしての話題正規表現:悪い表現、いい表現、最良の表現 [postd.cc]脆弱性としての話題StackExchangeが攻撃されたReDoSの効果 [ohgaki.net]
本気で速度が要求されるコードは、素人が書くべきではないということかな。もちろんCloudflareならその道の専門家が多数いるんだろうけど、そうではない人が気軽に書いちゃったんだろうか。
1個目の記事にもある通り、素人ならこういう差が出るものだってことを認識して、適切な人に任せる必要があることが分かってれば十分。初めのコードがダメなことは分かるけど、だからといって最適なコードを用意できるかと言われると難しい。
× 本気で速度が要求されるコード○ 本番用のコード
× 素人が書くべきではない○ ちゃんとテストするべき
これくらいのミスは誰でもするやろ。アカンのは「極度なCPU使用を防止する保護機能が数週間前に誤って削除されていたこと」やな。「保護機能」の詳細はわからんけど、きっとここだけが唯一かつ最凶レベル。
コードといっても正規表現だからね。言語としては最上級でしょ。性能が問題になるほど重要なら、正規表現を使わない文字列処理をすれば安全なんじゃないかと。もともとそんなにガチの用途に耐えられる設計じゃなくて痒い所に手を届かせる程度のものなんだから。
正規表現は(1-テープチューリング機械ですら)たかだかDTIME(o(nlog(n)))なのに対して普通のプログラミング言語で書いたものは停止性の証明すらできないが。
[12]\d{3}-[01]\d-[0-3]\d ([^ \[]*?)\[([^\]]*?)\]:.*
でも、この「最良の正規表現」、西暦3000年になると動かなくなるよね……。
ぜひ RFC 2550 に対応してください!
正規表現のバックトラックの落とし穴の話自体は随分前に聞いた気がする。先輩からだったかなあ。その時に、くれぐれも注意して使えと釘を刺された覚えが。
「Mastering Regular Expressions」 https://www.amazon.co.jp/dp/B007I8S1X0/ [amazon.co.jp]とりあえずコレが2006年で、バックトラックは便利だけど効率上の落とし穴があるとは書いてる。(詳しくはチャプター6をヨメってさ。)
初版の方は未確認だけど、その頃から知ってる人は知ってた話なのでは。それこそ正規表現エンジンを作ってる側の人は、その性質も込みだから最初から知ってたろうしね
この正規表現の件とか、TCP/IPやプロセッサ関連の話題なんかで当時ありきたりの話がいま伝承じみた扱いになってるのをみると何というか少しゾクリとすることがある
なあに、7payみたいにあれだけ盛大にやらかしても、責任者は責任取らなくていいんですよ。雲の上の人は気楽なもんです。
現場の危機感については、まるで聞く耳持たないんだもの。
責任を取るためだけにいるやつがその責任すら取らないんだったらマジで存在価値ないな
>とりあえずコレ
レビュー(書評)本文が英文だったのが新鮮だった。amazon.co.jp のレビューは取り扱い商品同様相互に各国amazonから自由にやりとりできてうらやましい。
つーか愚直に探索するとありきたりな表現でもくっそ遅い。単純文字列検索ですら、BM法がアルゴリズムの教科書の定番ネタだったりするくらいだし、実用の正規表現エンジンが愚直な実装であることを前提とするのは素人もいいところかと。正規表現は遅いのが当たり前で、そこから各自高速化されているのも当たり前。
そして最終的には「そのエンジンで」高速に処理できないパターンになってるかどうかの問題になる。特定の構造が遅い速いってのは環境依存のあるTipsかと。
コンパイラーが最適化してくれるからってわざわざ非効率なコードを書く必要はないんですよ。むしろやってくれるかどうかもわからない最適化に期待することこそ素人もいいところだと思うんですが
>単純文字列検索ですら、BM法がアルゴリズムの教科書の定番ネタだったりするくらいだし、単純文字列検索「だから」そういう原始的な高速化技法があるんでしょ。不特定多数の複雑なパターンマッチにおいては、一般的な最適化技法はないと思う。
仮にあっても、その正規表現を数回しか使用しないのであれば、最適化にかかる時間の方が、最適化によって短縮される時間より長くなって本末転倒。正規表現部分を何万回も何十万回も使ってボトルネックになる場合は、一流のプログラマなら正規表現なんて使わない形に書き直す。
なので不特定多数の正規表現の汎用的な最適化なんて不可能だし実装してないんじゃないだろうか。
JavaのHotSpotVMによって高度な動的最適化が日常的に利用可能になったから、そこで行われている最適化がどれほど無茶なことか分からない初心者も増えてしまったのかもしれない。HotSpotVMは、もはや初心者の理解を超えてるもんね。
>長い方がいい正規表現うっ。いかにして短くするかに腐心してきた感あり…。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
Stableって古いって意味だっけ? -- Debian初級
正規表現のバックトラック (スコア:5, 参考になる)
3、4年くらい前に話題になったやつだね。
自分も仕事でウッカリやっちまわないかと思うとワラエナイ。
パフォーマンスとしての話題
正規表現:悪い表現、いい表現、最良の表現 [postd.cc]
脆弱性としての話題
StackExchangeが攻撃されたReDoSの効果 [ohgaki.net]
Re:正規表現のバックトラック (スコア:1)
本気で速度が要求されるコードは、素人が書くべきではないということかな。
もちろんCloudflareならその道の専門家が多数いるんだろうけど、そうではない人が気軽に書いちゃったんだろうか。
1個目の記事にもある通り、素人ならこういう差が出るものだってことを認識して、適切な人に任せる必要があることが分かってれば十分。
初めのコードがダメなことは分かるけど、だからといって最適なコードを用意できるかと言われると難しい。
Re:正規表現のバックトラック (スコア:4, すばらしい洞察)
× 本気で速度が要求されるコード
○ 本番用のコード
× 素人が書くべきではない
○ ちゃんとテストするべき
これくらいのミスは誰でもするやろ。
アカンのは「極度なCPU使用を防止する保護機能が数週間前に誤って削除されていたこと」やな。「保護機能」の詳細はわからんけど、きっとここだけが唯一かつ最凶レベル。
Re:正規表現のバックトラック (スコア:1)
コードといっても正規表現だからね。言語としては最上級でしょ。性能が問題になるほど重要なら、正規表現を使わない文字列処理をすれば安全なんじゃないかと。もともとそんなにガチの用途に耐えられる設計じゃなくて痒い所に手を届かせる程度のものなんだから。
Re: (スコア:0)
正規表現は(1-テープチューリング機械ですら)たかだかDTIME(o(nlog(n)))なのに対して普通のプログラミング言語で書いたものは停止性の証明すらできないが。
Re:正規表現のバックトラック (スコア:1)
でも、この「最良の正規表現」、西暦3000年になると動かなくなるよね……。
Re: (スコア:0)
ぜひ RFC 2550 に対応してください!
Re: (スコア:0)
正規表現のバックトラックの落とし穴の話自体は随分前に聞いた気がする。
先輩からだったかなあ。その時に、くれぐれも注意して使えと釘を刺された覚えが。
「Mastering Regular Expressions」 https://www.amazon.co.jp/dp/B007I8S1X0/ [amazon.co.jp]
とりあえずコレが2006年で、バックトラックは便利だけど効率上の落とし穴があるとは書いてる。
(詳しくはチャプター6をヨメってさ。)
初版の方は未確認だけど、その頃から知ってる人は知ってた話なのでは。
それこそ正規表現エンジンを作ってる側の人は、その性質も込みだから最初から知ってたろうしね
Re:正規表現のバックトラック (スコア:2, 興味深い)
この正規表現の件とか、TCP/IPやプロセッサ関連の話題なんかで
当時ありきたりの話がいま伝承じみた扱いになってるのをみると
何というか少しゾクリとすることがある
Re: (スコア:0)
なあに、7payみたいにあれだけ盛大にやらかしても、責任者は責任取らなくていいんですよ。
雲の上の人は気楽なもんです。
現場の危機感については、まるで聞く耳持たないんだもの。
Re: (スコア:0)
責任を取るためだけにいるやつがその責任すら取らないんだったらマジで存在価値ないな
オフトピ, -1 (Was: Re:正規表現のバックトラック) (スコア:1)
>とりあえずコレ
レビュー(書評)本文が英文だったのが新鮮だった。
amazon.co.jp のレビューは取り扱い商品同様相互に
各国amazonから自由にやりとりできてうらやましい。
Re: (スコア:0)
つーか愚直に探索するとありきたりな表現でもくっそ遅い。
単純文字列検索ですら、BM法がアルゴリズムの教科書の定番ネタだったりするくらいだし、
実用の正規表現エンジンが愚直な実装であることを前提とするのは素人もいいところかと。
正規表現は遅いのが当たり前で、そこから各自高速化されているのも当たり前。
そして最終的には「そのエンジンで」高速に処理できないパターンになってるかどうかの問題になる。
特定の構造が遅い速いってのは環境依存のあるTipsかと。
Re: (スコア:0)
コンパイラーが最適化してくれるからってわざわざ非効率なコードを書く必要はないんですよ。
むしろやってくれるかどうかもわからない最適化に期待することこそ素人もいいところだと思うんですが
Re: (スコア:0)
>単純文字列検索ですら、BM法がアルゴリズムの教科書の定番ネタだったりするくらいだし、
単純文字列検索「だから」そういう原始的な高速化技法があるんでしょ。
不特定多数の複雑なパターンマッチにおいては、一般的な最適化技法はないと思う。
仮にあっても、その正規表現を数回しか使用しないのであれば、最適化に
かかる時間の方が、最適化によって短縮される時間より長くなって本末転倒。
正規表現部分を何万回も何十万回も使ってボトルネックになる場合は、一流の
プログラマなら正規表現なんて使わない形に書き直す。
なので不特定多数の正規表現の汎用的な最適化なんて不可能だし実装してないんじゃないだろうか。
JavaのHotSpotVMによって高度な動的最適化が日常的に利用可能になったから、
そこで行われている最適化がどれほど無茶なことか分からない初心者も増えて
しまったのかもしれない。
HotSpotVMは、もはや初心者の理解を超えてるもんね。
Re: (スコア:0)
>長い方がいい正規表現
うっ。いかにして短くするかに腐心してきた感あり…。