正規表現の脆弱性 (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) と呼ばれる脆弱性です。正確に理解するのが難しい脆弱性なので、少し解説してみたいと思います。 結論 長い記事になるので、最初に「とりあえずこれだけ知っ
正規表現の"正規"とは何か気になったら正規表現の歴史を紐解くことになってしまった話
正規表現の"正規"って何 ある時ふと思いました。 「正規表現の"正規"って何だろう？」 「何を根拠に"正規"を名乗っているのか？」 と。 「誰かが『これが正規の表現だ』と言ったはず」で、 「それは周りにどうやって"正規"だと認められたのだろう」 ということが気になったので調べてみました。 "正規表現"という名前でなくて、"ジャックさんの表現"とか"記号ごちゃごちゃ表現"だったらこんな疑問も持たなかったのですけど。 数学における"正規"とは 一般に"正規"というと、"正規品"や"正規の手順"といったように"本物の(genuine)"や"公式な(official)"といった意味がありますが、数学の"正規"はちょっと違います。 数学で"正規"(および"正則"、英語では"regular"または"non-singular")は、ある概念に強い制限をかけたもの、という意味です。強い制限をかけたものは取
決定性と非決定性（DFA, NFA） | Basic Werk
0 と 1 だけで話す種族 その国の種族は 0 と 1 だけで構成されたアルファベットを使って話しているとしよう。 ただ、0 と 1 をめちゃめちゃに並べて話してもお互いに意味は通じないから、意味のある言葉にするには、0 と 1 をある規則で並べて話す。 （ここに書いた文章だってそうなってる。日本語という言語の中からひとつひとつの文字を日本語の文法に則って並べてるから、僕の言葉はあなたに通じている。これから話を進める種族の言語体系は、日本語みたいに複雑で無数にある文字の組み合わせじゃなくて、もっともっと単純に 0 と 1 だけを文字として使っているというだけだ。） さて、この種族の脳みその中を覗いてみよう。 彼らが「りんご」という意味の言葉を表すときに「001」という文字の並びを使うとする。 つまり話の中で「001」という並びに出会ったら、それを「りんご」と認識できるというわけだ。 言い換
99%のEmailアドレスにマッチする正規表現公開される | ソフトアンテナ
一見Emailアドレスにマッチする正規表現を組み立てるのは簡単そうに思えますが、RFC 5322に厳密に準拠した正規表現を創りだそうとするととんでも無い努力が必要となるようです。 「Email Address Regular Expression That 99.9% Works」は、様々なプログラミング言語ごとに、Emailアドレスに99%マッチする正規表現を掲載したサイトで、例えばPerl 5.10より前のバージョンのPerl用として、掲載されている長大な正規表現を見れば、その難易度の高さを確認することができます。 正規表現にはなんの解説もなくどのような意図をもって作られたのか説明はありません(よって99%マッチするかどうかは本当のところは不明)。ちなみに日本語で読める貴重な情報「Perlメモ」では、「perl5.6.0以前の perl ではメールアドレスの正規表現を正確に記述すること
正規表現を解析して可視化してくれるサイトが凄すぎる件
ある正規表現に対して、特定の文字列がマッチするかどうかをチェックするツールやサイトは沢山ありますが、正規表現そのものが何を意味しているのか、どんな文字列を期待しているのかを解析・解読・説明してくれるツールやサイトってなかなか見ない気がします。 他人の書いた正規表現を見て、「ん？」ってなったことはありませんか？ 例えばこれ。 1 ^[a-zA-Z0-9-_.]@([a-zA-Z0-9_-]+\.)+[a-zA-Z]{2,4}$ これくらいなら分かりますが、複雑になってくるとつらい… いつかはマスターしたいけど…今は楽したい。 そう思ってググってみると…ありました！ それがこちら。 Regexper http://www.regexper.com/ 正規表現を入力して Display をクリックすると、その正規表現が表す内容を図にして表示してくれます。 例えば先程の正規表現は、当記事の一番上の
最長一致数量子、最短一致数量子、強欲な数量子の違い
・最長一致数量子 ? 1または0回 * 0回以上 + 1回以上 {n} n回 {n,} n回以上 {n,m} n回以上、m回以下 ・最短一致数量子 ?? 1または0回 *? 0回以上 +? 1回以上 {n}? n回 {n,}? n回以上 {n,m}? n回以上、m回以下 ・強欲な数量子(絶対最大指定子) ?+ 1または0回 *+ 0回以上 ++ 1回以上 {n}+ n回 {n,}+ n回以上 {n,m}+ n回以上、m回以下 数量子の種類は 6 種類用意されていますが、それぞれに対して最長一致数量子、最短一致数量子、強欲な数量子の 3 つのタイプが用意されています。(強欲な数量子は絶対最大指定子と呼ばれることもあります)。 例えば直前の文字の 1 回または 0 回繰り返すことを表す数量子は ? ですが、単に ? と記述した場合は最長一致数量子となります。 ? のあとに ? を記述した ??
Scriptular - Javascript Regular Expression Editor
Scriptular is a javascript regular expression editor. Inspired by Rubular it gives you a simple way to test javascript regular expressions as you write them. Start by entering a regular expression and then a test string. Or give this example a try. Learn more about regular expressions in javascript.
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ReDosトラック内発表資料
ReDos検出プログラムの作成とOSSへの適用 #seccamp
正規表現エンジンを作ろう一覧