正規表現の脆弱性 (ReDoS) を JavaScript で学ぶ

先日、このようなツイートを書いたところ、かなりの反響がありました。 JavaScript の正規表現の脆弱性の例でいうと、例えば /\s+$/ は脆弱性があると言える console.time(); /\s+$/.test(" ".repeat(65536) + "a"); console.timeEnd(); 結構時間がかかるのがわかる。でも /\s+$/ を見て「これは危険だな」と理解出来る人はそんなにいない。JavaScript に限らないけれど。 — Takuo Kihira (@tkihira) February 17, 2022 これは一般に ReDoS (Regular expression Denial of Service) と呼ばれる脆弱性です。正確に理解するのが難しい脆弱性なので、少し解説してみたいと思います。 結論 長い記事になるので、最初に「とりあえずこれだけ知っ

[hiromichinomata]

ユーザー入力でないものを脆弱性というのは間違い。PerlもPHPもRubyも鬼車なので再帰が使える。再帰のある任意のプログラミング言語Aは脆弱性のある言語なの？

[BlueSkyDetector]

glibcでもある話。拡張正規表現".*{10,}{10,}{10,}{10,}{10,}"でプロセスクラッシュ。当時eglibcで聞いたら都度別プロセスで実行して監視すべきと。一方bsd系のlibcだとメモリ使用上限をつけていて止まってくれる。PCREもたしか対応済

[td2sk]

計算量が爆発しうる正規表現をユーザー入力のバリデーションなんかに使ってしまうとDoS攻撃を受けるのでこれも立派な脆弱性(の元)。速度保証しているre2の方が珍しいぐらい拡張が普通なので問題を知らない人が多い

[otoan52]

これほんと知らないと踏むよな…。いくつか分析手法があって、lintも存在するのでそれらを使うのが良いのだと思う/eslint-plugin-regexpはよく使われるんだけど、検出のアルゴリズムがあんまり良くなかった気がする

[cnln]

非決定性有限オートマトン(NFA)が発生すると計算量が膨れ上がる。

[rryu]

正規表現はあとちょっとでマッチしそうだけど実はマッチしない場合が一番遅いので、そういう最悪パターンを考えるようにすると少しはましかもしれない。

[nakag0711]

これ外からは手も足も出ないのでプロセス殺すしかなくなるのが困る

[flont]

ハッシュ衝突のDoSとか(主に拡張された)正規表現のエンジンの計算量とか、言語仕様とCSをちゃんと理解していても気づかないところで踏みがち

[gfx]

"正規表現エンジンの内部実装によって発生状況が大きく左右されるので、ReDoS に対して「この言語なら大丈夫」みたいな理解をしていると危険"

[tettekete37564]

Perl の taint モードで少し修行してこいと言いたくなるな。意図のよく分からない正規表現である事は一目とは言わないまでもすぐ分かると思うのだが / なんでっていや分かるでしょ？その正規表現を実現するコード考えれば

[ono_matope]

脆弱な正規表現はlinterで検知しないとだな

[kabochatori]

０除算や浮動小数点誤差等の遠縁で実装上で気を付けるべき仕様って感じかな。

[ooblog]

#正規表現 #DoS #ReDoS #オートマトン 「プログラミング言語の問題ではなく、正規表現~重くなる入力を与えられることでサービスが落ちる~どのような表現が苦手か~トレードオフ~ツールでの判定も~正確というわけではない」

[zu2]

良記事

[miau]

トップコメ「ユーザー入力でないものを脆弱性というのは間違い」は正規表現パターンの脆弱性じゃなくて正規表現エンジン（言語？）の脆弱性と捉えているのかな。そういう主旨ではないと思うけど。

[ProjectionOFWord]

こわっ!無限ループ発生装置!サーバー管理者大変そうですね!エレガントの罠。昔ならFor文とIf文の入れ子で、ループ脱出にGoto文使うのは嫌だとか言ってこの正規表現の罠に似た状況が発生したっぽい。富士通は正しかった!

[odz]

ちょうどこの間踏んだ問題／特定の入力で問題発生するので脆弱性と呼ぶこと自体に違和感は無いかなー

[buzztaiki]

non-backtracking RegExp engine いいな。

[lizy]

変換されたオートマトンを元に危険度を自動的に見積もるとか出来ないのかな

[p1ass]

“タイムアウトでプロセスを殺すのが一番確実”

[napsucks]

DoSというよりタコなプログラミングの問題と同根に思えるけど…

[oqzl]

手元の処理系で試そう…

[teramako]

非決定性有限オートマトン（格好良い言葉だなあ

[bluescreen]

勉強になりました

[apipix]

ReDoS

[zgmf-x20a]

なるほどね。としか…

[harupu]

末尾trimしたり `input.match(/.*\.png$/)` とかで死ぬので辛め。/^.*\.png$/や/.png$/は大丈夫だけどうっかりやりそうでむずい。

[shion214]

“です。 これが延々と続いていきます。最終的には、65536 文字の入力に対して、(65536 + 65535”

[natu3kan]

正規表現エンジンの実装しだいでシステムを落とすような脆弱性になったりするんだな。

[Aodrey]

真ん中あたりでギブアップした…記事頭の結論と最後のチェックツールの話を参考にする。

[nimroder]

a?a?aaの探索、アッカーマン関数思い出した

[quality1]

安易に正規表現使えるようにしておいてとお願いするのはやめようと思いました

[nilab]

「ReDoS は、基本的には言語の仕様によるものではなく、正規表現エンジンの実装に依存するものですから、基本的に「この言語だから安全」みたいなことは言えません」