正規表現

編集履歴

FrontPage

概要

  • いろいろ非直感的なのでテスト駆動的に確認すること
  • 日本語に直すとよい

参考

文法

記述意味例
.任意の1文字
?直前の文字があるかないかどちらか
^文頭
$文末
*貪欲な1個以上マッチ
+貪欲な1個以上マッチ
*?控えめな0個以上マッチ
+?控えめな1個以上マッチ
{n,m}n個以上m個以下。{n,}でn個以上、{,m}でm個以下を表す
()ひとまとまりとみなしてキャプチャ
(?:)ひとまとまりとみなさずキャプチャ
[a-zA-Z0-9]a-z, A-Z, 0-9の1文字
[ABC]AもしくはBもしくはCの1文字
[^ABC]A、B、Cのいずれでもない1文字
パイプパイプの前、もしくは後ABCパイプDEFで、ABCとDEFにマッチする
(?<=abc)肯定の後読み。abcの後にマッチする
(?=abc)肯定の先読み。abcの前にマッチする
(?<!abc)否定の後読み。abcという文字列以外の直前の位置にマッチする
(?!abc)否定の先読み。abcという文字列以外の直後の位置にマッチする
\b単語の区切り目ちなみに、<と>が「単語の先頭、末尾」にマッチ
\w英単語の構成文字
\s空白文字環境依存
\d数字
\B、\W, \S, \D小文字の逆の意味
\1, \2, ...キャプチャされた順にその文字列がそのまま入る

イディオム

最短マッチ

  • 正規表現の*?は最短のマッチという意味になる

  • 基本的にではなく?のほうが最短マッチで探索打ち切りなので早くなる傾向

  • 正規表現の王道は、ちゃんとストラクチャっぽく書いてやること、そうじゃないと字面に騙されるので注意（だがめんどい）

  • キャプチャしない(:?)の中にキャプチャ()が入っている場合、キャプチャが優先される。要するに、グルーピングしたいけどキャプチャしたくはないよ、というときに使う (\s*\w)+とかのようにグルーピング必須のことはあるからね

  • 正規表現には??みたいなやつがあって、これも最短一致。

  • 先読みとか後読みとかは、ただ「そこにあればよい」「そこになければよい」というマッチングなので注意

  • JavaScriptでは正規表現を動的に作ることが出来る（当然）

  • 正規表現を最短マッチで止める方法

未整理

正規表現

  • 正規表現の部品は、リテラルテキスト、量指定子、文字クラス（1 文字にマッチするだけ）、カッコ（キャプチャ用）、アンカー（単純な^ \b など隣り合うものだけを評価。複雑な先読みがある。）

  • 従来型NFA、POSIX NFA (POSIX では「最も左の中で最も長いもの」と規定があるため、保存ステートがなくなるまで全ステートをマッチを確認する) ,DFA

    • 従来型NFA 最小量指定子があればこれ
    • POSIX NFA キャプチャ月カッコと後方参照がある
    • DFA には原理上、キャプチャ月カッコや最小量指定子、先読み後読み、条件分岐、後方参照、アトミックグループは不可能。

NFAもDFAも正規表現のコンパイルが必要だが、NFA は非常にシンプル。DFA はマップを作るのにDFAのほうがコンパイルにコストがかかる。コンパイルに時間とメモリが必要なので、遅延評価して実行時にマップづくりを遅らせることもある（トレードオフ）。

従来型 NFA もマッチなしと主張するためには同様全ての組み合わせを試すため時間がかかる。POSIX NFA 毎回それをする（最長を保証するため）

DFA のマッチスピードは正規表現とは無関係 NFA は正規表現の影響を直接受ける。

一貫性があり非常に高速なのでDFAを使いたいが、機能はNFAのほうがよい、ハイブリッド型が台頭（grep, awk）

NFA は

NFA は正規表現主導型 後方参照以外では、部分式の間に相互関係がないので、独立して別個にチェックできる エンジニアがやりたいと思うことを作り込むことができる バックトラックする 量指定子は、最大量指定子ではマッチを思考するを先に選び、最小ではしないを先に選択する マッチ不成功によってバックトラックを強いられたときに次に試すべきは最後に保存した選択肢である。 保存ステート: バックトラックのセーブポイント ステートの見方: ▲以降が▲以降にマッチするかという部分問題に切り分けている 保存ステートは stack である。

DFA はテキスト主導型

  • awk, lex, egrep には DFA なので広報参照や$1ができない
  • GNU バージョンのegrepはDFAで、マッチしなかったらNFAに切り替えるみたいなことをしている

echo =XX========================= | egrep 'X(.+)+X' が遅いなら NFA

原則は２つしかないが実装は多岐にわたる

  • 最初にマッチしたものが優先される
  • 標準の量子停止は欲張りである（*, +, ?, {m, n}）。マッチ不成立 （NFA は欲張りだから最長になっているが、DFA は全マッチを管理するので明示的に最長の文字列を出力するようになっている。これは実は裏側では異なる。DFAは原理的に最左最長マッチ。NFA は場合による）

^.([0-9][0-9])は入っている二桁以上の数字の最後の2文字をとる ^.([0-9]+)は？最後の1文字をとる a 1234 num は [0-9]+ をすると1,2,3,4のあとに▲がくるものが保存ステートになる a 1234 num は [0-9]* をすると*はゼロ個でいいのでaの前に▲で止まってマッチする 小数点以下の最初の二桁は必ず使う。三桁目は0でなければ使う。それ以下は取り除く(.\d\d[1-9]?)\d? はよいが、(.\d\d[1-9]?)\d+ だと、ちょうど3桁の場合にバグる

正規表現は必ず毎回試される

効率を測るための指標 テストとバックトラックの回数

DFA を用いた正規表現の実装では、正規表現の実行にかかる時間計算量は入力文字列の長さに対して線形 3 であり、この記事で扱っているような問題とは無縁です。 上で例示した egrep コマンドは DFA による正規表現の実装が行われているため、正規表現の実行が極端に重くなることを回避できています。 一方で、 DFA では正規表現の先読みや後読み、最短一致のような拡張的な機能を実現することができません。 /(.+)+a/.test("0123456789"); [0123456789] [012345678][9] [01234567][89] [01234567][8][9] [0123456][789] [0123456][78][9] [0123456][7][89] [0123456][7][8][9] [012345][6789] [012345][678][9] [012345][67][89] [012345][67][8][9] [012345][6][789] [012345][6][78][9] [012345][6][7][89] [012345][6][7][8][9] 正規表現への悪意ある入力 https://qiita.com/Tatamo/items/68a10c6274953e695354 const regexp = /^https?://([^/]+)/((?:./)+[^/?])?(.*)$/; regexp.exec("https://example.com/////////////////////////index.html")

ReDoS 攻撃 計算量オーダーの高い正規表現は、サービス全体の脆弱性となってしまう可能性もあります。 クライアントサイドで正規表現が応答を返さなくなるとアプリがフリーズし、サーバーサイドの場合にはシステム障害に発展してしまうおそれがあります。

正規表現の実行に高い負荷がかかったことによって、 2016年には Stack Exchange のネットワークが一時的にダウンする事態に陥りました。

https://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016 https://stackstatus.net

このレポートによると、障害の起因となった正規表現は以下のようなもので、「文字列の末尾の空白を見つける」という非常にシンプルなものでした。

/\s+$/ この正規表現がどのように実行されるのか見ていきましょう。 ほかの正規表現の例でも見たように、マッチに失敗するときに計算時間が大きくなってしまう傾向がありました。 そこで以下のように、空白が10個並んでいて、その後ろに \s にマッチしない文字 (a) があるような文字列を入力として与えてみます。

" a" バックトラックのアルゴリズムでは、まず入力文字列の先頭を見て、 \s+ にあてはまる文字列を可能な限り長く取ろうとするのでした。 そのため、最初は空白が 10個並んだ文字列を \s+ にマッチする候補としてあてはめます。 しかし文字列の末尾には a が残っていますから、 $ にマッチさせることができずにこの試行は失敗します。 正規表現エンジンは \s+ にあてはまる候補として 9個, 8個, 7個... と順番に空白の数を減らしていきますが、この正規表現全体をマッチさせることはできないため、10回試してすべて失敗することになります。 そうすると今度は入力文字列の 2文字目から同じことを繰り返し、今度は空白 9個から始めて 9回試行されます。 最終的には、空白の個数を n �

個として n+(n−1)+(n−2)+...+1=12(n2−n)

� 1. ( � − 1 ) 1. ( � − 2 ) 1. . . . 1. 1

1 2 ( � 2 − � )

回だけ処理が実行されます。

つまり、計算量のオーダーは O(n2) � ( � 2 )

となることがわかります。

前に見た O(2n) � ( 2 � )

のような指数関数的に負荷が増大する正規表現と比較するとずいぶん控えめに見えますが、これでもサービスをダウンさせるには十分でした。

一般的に、普通のマシンが 1秒間に行うことのできる単純な繰り返し処理の回数は 108 10 8

回から 109

10 9

回ですから、 n

�

に数万程度の値を入れると処理に 1秒以上要することになります。

Stack Exchange の例では、空白が 2万文字続いたあとに空白以外の文字を付け足した文字列が与えられてサーバーが応答しなくなり、当該ページがロードバランサのヘルスチェックに使われていたためにサービス全体の停止に発展しました。

この例では、指数関数的に負荷が増大するほどの破滅的な正規表現パターンでなくても O(n2) � ( � 2 )

程度の計算量を要することがあり、それでも十分にサービスに打撃を与える可能性を孕んでいることを紹介しました。

このように正規表現に特定の入力を与えることでマッチ処理のハングを狙う DoS 攻撃を、 ReDoS といいます。

ユーザーに正規表現を入力させない ユーザーに正規表現を入力させるような実装は、 ReDoS 攻撃のリスクだけでなく、正規表現インジェクション https://blog.ohgaki.net/regular-expression-injection を受けるおそれもあるため非常に危険です。 ユーザーが入力した文字列を正規表現の一部のパターンとして検索する、といった場合も同様の問題が発生するため、使用できる文字を制限するか、正規表現を使わずに実装しましょう。

ReDoS 攻撃 で紹介した Stack Exchange の例でも、正規表現を使わない処理に置き換えるという形で対策が行われました。

対策について 正規表現のユニットテスト ユーザーに正規表現を入力させない 正規表現にかける前にチェックを行う 正規表現の実行にかかる時間を計測する 正規表現の使用を避ける おわりに Further Readings 詳説 正規表現 第3版 コンパイラ[第2版] 原理・技法・ツール 宣伝

正規表現の形から問題の発生を想像するのは、とてもむずかしい 後戻りしない形の正規表現であれば発生しないのですが、正規表現の形から発生の可能性を正確に判断するのは至難の業ですし、そもそも同じ正規表現であっても後戻りするかどうかは正規表現エンジンの実装に左右されることもあります。

入力文字数が短くても発生しうる 例えば、 /(.*){1,20}[bc]/.exec('a'.repeat(25)) のように、入力文字がたったの 25 文字でも物凄く遅くなり得ます。正規表現エンジンの実装次第ですが、基本的に入力文字数の制限は本質的な解決にはなりません（なお後述しますが、例えば Go の標準の正規表現エンジンの実装では、正規表現の長さを m、入力文字を n として計算量が O(mn) となるため、入力文字数の制限が本質的な解決になることもあります）

有限入力にするという手もある。

高速化 テストとバックトラックの回数を減らす 異常系を変える 選択ではなく文字クラスを使う [^"]+など文字の除外を使う

やりすぎるとミスって計算量爆発する可能性も

正規表現とセキュリティ 正規表現と無限ループ どのようにして保存ステートを確認するのか？ ChatGPT regex101 なぜ NFA DFA と言うの？ リファレンスを見ればどっちかわかったりする？ ちょっと裏側を知ると楽しい。

最終更新: 2020-01-01