2022/02/18 18:45
gfx
"正規表現エンジンの内部実装によって発生状況が大きく左右されるので、ReDoS に対して「この言語なら大丈夫」みたいな理解をしていると危険"
2022/02/18 18:48
ken39arg
わかりやすい。
2022/02/18 19:08
casm
めっちゃ面白い。「線形時間で実行出来ない正規表現を Syntax Error」にする新オプション、使えるようになるなら面白い。
2022/02/18 19:21
Fushihara
引数にタイムアウトを追加して過ぎたらnullを返すようになるのかな
2022/02/18 20:18
junjun777
忘れてはいけない話。
2022/02/18 20:19
otoan52
これほんと知らないと踏むよな…。いくつか分析手法があって、lintも存在するのでそれらを使うのが良いのだと思う/eslint-plugin-regexpはよく使われるんだけど、検出のアルゴリズムがあんまり良くなかった気がする
2022/02/18 20:35
flont
ハッシュ衝突のDoSとか(主に拡張された)正規表現のエンジンの計算量とか、言語仕様とCSをちゃんと理解していても気づかないところで踏みがち
2022/02/18 21:17
monopole
“計算理論の入り口として大変に魅力的な題材” まさに、面白い
2022/02/18 21:47
nilab
「ReDoS は、基本的には言語の仕様によるものではなく、正規表現エンジンの実装に依存するものですから、基本的に「この言語だから安全」みたいなことは言えません」
2022/02/18 22:22
nimroder
a?a?aaの探索、アッカーマン関数思い出した
2022/02/18 22:22
quality1
安易に正規表現使えるようにしておいてとお願いするのはやめようと思いました
2022/02/18 23:59
Aodrey
真ん中あたりでギブアップした…記事頭の結論と最後のチェックツールの話を参考にする。
2022/02/19 00:37
tettekete37564
Perl の taint モードで少し修行してこいと言いたくなるな。意図のよく分からない正規表現である事は一目とは言わないまでもすぐ分かると思うのだが / なんでっていや分かるでしょ？その正規表現を実現するコード考えれば
2022/02/19 01:57
natu3kan
正規表現エンジンの実装しだいでシステムを落とすような脆弱性になったりするんだな。
2022/02/19 03:26
BlueSkyDetector
glibcでもある話。拡張正規表現".*{10,}{10,}{10,}{10,}{10,}"でプロセスクラッシュ。当時eglibcで聞いたら都度別プロセスで実行して監視すべきと。一方bsd系のlibcだとメモリ使用上限をつけていて止まってくれる。PCREもたしか対応済
2022/02/19 05:05
nakag0711
これ外からは手も足も出ないのでプロセス殺すしかなくなるのが困る
2022/02/19 05:26
hiromichinomata
ユーザー入力でないものを脆弱性というのは間違い。PerlもPHPもRubyも鬼車なので再帰が使える。再帰のある任意のプログラミング言語Aは脆弱性のある言語なの？
2022/02/19 05:48
shion214
“です。 これが延々と続いていきます。最終的には、65536 文字の入力に対して、(65536 + 65535”
2022/02/19 06:09
harupu
末尾trimしたり `input.match(/.*\.png$/)` とかで死ぬので辛め。/^.*\.png$/や/.png$/は大丈夫だけどうっかりやりそうでむずい。
2022/02/19 06:15
zgmf-x20a
なるほどね。としか…
2022/02/19 07:29
cnln
非決定性有限オートマトン(NFA)が発生すると計算量が膨れ上がる。
2022/02/19 09:23
bluescreen
勉強になりました
2022/02/19 10:30
teramako
非決定性有限オートマトン（格好良い言葉だなあ
2022/02/19 10:39
oqzl
手元の処理系で試そう…
2022/02/19 10:57
napsucks
DoSというよりタコなプログラミングの問題と同根に思えるけど…
2022/02/19 11:05
td2sk
計算量が爆発しうる正規表現をユーザー入力のバリデーションなんかに使ってしまうとDoS攻撃を受けるのでこれも立派な脆弱性(の元)。速度保証しているre2の方が珍しいぐらい拡張が普通なので問題を知らない人が多い
2022/02/19 11:06
p1ass
“タイムアウトでプロセスを殺すのが一番確実”
2022/02/19 11:15
lizy
変換されたオートマトンを元に危険度を自動的に見積もるとか出来ないのかな
2022/02/19 12:45
buzztaiki
non-backtracking RegExp engine いいな。
2022/02/19 14:33
odz
ちょうどこの間踏んだ問題／特定の入力で問題発生するので脆弱性と呼ぶこと自体に違和感は無いかなー
2022/02/19 17:40
rryu
正規表現はあとちょっとでマッチしそうだけど実はマッチしない場合が一番遅いので、そういう最悪パターンを考えるようにすると少しはましかもしれない。
2022/02/19 19:28
ProjectionOFWord
こわっ!無限ループ発生装置!サーバー管理者大変そうですね!エレガントの罠。昔ならFor文とIf文の入れ子で、ループ脱出にGoto文使うのは嫌だとか言ってこの正規表現の罠に似た状況が発生したっぽい。富士通は正しかった!
2022/02/20 21:17
miau
トップコメ「ユーザー入力でないものを脆弱性というのは間違い」は正規表現パターンの脆弱性じゃなくて正規表現エンジン（言語？）の脆弱性と捉えているのかな。そういう主旨ではないと思うけど。
2022/02/20 22:49
zu2
良記事
2022/02/22 10:06
ooblog
#正規表現 #DoS #ReDoS #オートマトン 「プログラミング言語の問題ではなく、正規表現~重くなる入力を与えられることでサービスが落ちる~どのような表現が苦手か~トレードオフ~ツールでの判定も~正確というわけではない」
2022/02/22 13:01
kabochatori
０除算や浮動小数点誤差等の遠縁で実装上で気を付けるべき仕様って感じかな。