- 1: 基本となる8つの正規表現
- 2: 正規表現とは何か/ワイルドカードとの違い
- 3: 冒頭/末尾にマッチするメタ文字とセキュリティ、文字セットの否定と範囲
- 4: 先読みと後読みを極める
- 5（特別編）
|と部分マッチのワナ - 6: 文字セットのショートハンド
- 7: Unicode文字ポイントとUnicode文字クラス
- 8: 対象の構造を意識した「適度にDRYな」書き方
- 9:
.*や.+がバックトラックで不利な理由 - 10: 危険な「Catastrophic Backtracking」前編（本記事）
主にRubyを中心としながらも、なるべく一般的な形で正規表現を解説しています。誤りやお気づきの点がありましたら@hachi8833までどうぞ🙇。
きっかけ
以下の記事のRailsセキュリティ修正で言及されていた「Catastrophic Backtracking（カタストロフィックバックトラッキング）」について自分で調べてみました。
- [CVE-2021-22902] Possible Denial of Service vulnerability in Action Dispatch - Security Announcements - Ruby on Rails Discussions
- コミット: Prevent catastrophic backtracking during mime parsing · rails/rails@40f82dc
# 同コミット差分より
MIME_NAME = "[a-zA-Z0-9][a-zA-Z0-9#{Regexp.escape('!#$&-^_.+')}]{0,126}"
MIME_PARAMETER_KEY = "[a-zA-Z0-9][a-zA-Z0-9#{Regexp.escape('!#$&-^_.+')}]{0,126}"
MIME_PARAMETER_VALUE = "#{Regexp.escape('"')}?[a-zA-Z0-9][a-zA-Z0-9#{Regexp.escape('!#$&-^_.+')}]{0,126}#{Regexp.escape('"')}?"
MIME_PARAMETER = "s*;s*#{MIME_PARAMETER_KEY}(?:=#{MIME_PARAMETER_VALUE})?"
- MIME_REGEXP = /A(?:*/*|#{MIME_NAME}/(?:*|#{MIME_NAME})(?:s*#{MIME_PARAMETER}s*)*)z/
+ MIME_REGEXP = /A(?:*/*|#{MIME_NAME}/(?:*|#{MIME_NAME})(?>s*#{MIME_PARAMETER}s*)*)z/
Catastrophic Backtrackingとは
正規表現の書き方がよくないとCatastrophic Backtrackingが発生します。現象としては「マッチしない長大な文字列を与えたときに、実行時間が異常に長くなる」というものです。サービス停止やサーバークラッシュにつながる可能性があり、危険です。正規表現の脆弱性を悪用したDoS攻撃を一般にReDoSと呼ぶそうですが、Catastrophic Backtrackingはその一種のようです。
日本語の定訳がなさそうなので、本シリーズではCatastrophic Backtrackingと英ママで表記します（ネット上では「破壊的バックトラッキング」と表記されることもあります）。
記事末尾の参考資料もどうぞ。
正規表現のバックトラックについて
正規表現のバックトラックそのものについては以下の前回記事をご覧ください。以下の記事では正規表現の量指定子*や+を単独で用いた場合のバックトラックについてのみ説明していますが、Catastrophic Backtrackingでは量指定子を(a+)+のようにネストした場合に関連します。
Catastrophic Backtrackingは簡単に発生する！
最もシンプルなパターンで考えてみましょう。
一見無害そうに見える
以下はCatastrophic Backtrackingが潜んでいる正規表現の最もシンプルな例です。一見したところ何の問題もなさそうですが、どうしてどうして凶悪です。
#正規表現
(1+)+b
# 対象文字列（マッチする）
11111111111111b
上のようにマッチする場合はわずか6ステップで完了するので、見逃されがちです。
Catastrophic Backtrackingは「マッチしない場合」に牙を剥く
同じ正規表現で、今度は対象文字列だけを変えて、マッチしないようにします。具体的には対象文字列末尾からbを削除します。
# 正規表現
(1+)+b
# 対象文字列（マッチしない）
11111111111111
対象文字列が「最後の最後で惜しくもマッチしない」ことにご注意ください。
11111111111111はわずか14文字ですが、たったこれだけで、98286ステップも費やした末にマッチに失敗します。
ざっくり、対象文字列の長さの指数関数的にステップ数が増大するので、マッチしない対象文字列が長ければ長いほどステップ数が爆発的に増えます。
対象文字列がユーザー入力の場合、マッチしない長い文字列をユーザーが入力するだけでDoSを引き起こせます。
マッチする場合は大したステップ数にならないので、「これでよし」で済まされて「マッチしないテスト」を忘れがちなのが怖いですね。
何が起こっているのか
問題の核心は、(1+)+bという正規表現のうち、(1+)+という量指定子のネスト部分が以下のように展開された形で解釈されてしまうことだと理解しています（実装はわかりませんが）。これに気づくまで割と時間がかかりました😅。
# 対象文字列の長さに合わせて()+の内側がいくらでも伸びる
1+1+1+1+1+1+1+1+1+1+1+1+1+1+...
つまり1+という正規表現が、「最大で」対象文字列1111111111の長さだけ繰り返し結合されたのと同じことになります。対象文字列が2000文字なら正規表現1+も2000回結合され、20万文字なら1+も20万回分伸びるということです。
上はあくまで正規表現1+の繰り返し結合が「最大」の場合です、実際の途中経過では、以下のようなより短いパターンもすべて網羅されてしまう点にも注意が必要です。
# 正規表現の結合が網羅される
1+1+1+1+1+1+1+
1+1+1+1+1+1+
1+1+1+1+1+
1+1+1+1+
1+1+1+
1+1+
1+
まるで正規表現が合わせ鏡で増殖したかのようなおもむきですね（合わせ鏡のように無限にはなりませんが）。
以下のように、わざとネストをなくして、最初から対象文字列の1と同じ数だけ正規表現の1+を展開済みにしてみると見えやすいかもしれません。末尾の$がなければ爆発しませんが、$を置くと小爆発します（ネストした場合ほどではありませんが）。
# 正規表現
1+1+1+1+$
# 対象文字列
1111b
組み合わせは(2^n)-1
以下を引用します。理論上は対象文字列の分割方法の組み合わせが(2^n)-1になるんですね。この組み合わせの中でそれぞれバックトラックが発生するということになります。
数値の並び
123456789を数値に分割する方法は多くあります。正確には、(2^n)-1で、nは数字列の長さです。
123456789の場合、n=9であり、 511 の組み合わせになります。n=20のより長い並びの場合、約 100万（1048575）の組み合わせになります。n=30なら、1000倍以上(1073741823 の組み合わせ)になります。
破壊的なバックトラックより
バックトラックの爆発を人力で体感する
理解のため、バックトラックの範囲とその個数に絞り込んで、爆発ぶりを体感してみることにしました（特定の実装は想定していません）。
追記
なお、以下の表は手作りしました😅（RubyのRegexpクラスにデバッグ機能があればと思いましたが、調べた範囲ではデバッグ機能を備えた正規表現ライブラリはPerlにしかなさそうです😢）。
正規表現は引き続き(1+)+bを使い、対象文字列はもっと短い11111（つまり1が5個）とします。
# 正規表現
(1+)+b
# 対象文字列
11111
最初の試行
対象文字列でバックトラックする様子を以下のように区分けして表記することにします）。
- バックトラックでマッチを試行する箇所を
()で表記 - マッチを試行しない箇所を
[]で表記
見やすさのためスペースで縦を揃え、マッチを試行しない範囲[]が縮むたびに空行を入れています（()も[]も正規表現ではありません）。
(1 1 1 1 1) # バックトラック範囲は( )で表す
(1 1 1 1)(1)
(1 1 1)(1 1)
(1 1 1)(1)(1)
(1 1)(1 1 1)
(1 1)(1 1)(1)
(1 1)(1)(1 1)
(1 1)(1)(1)(1)
(1)(1 1 1 1)
(1)(1 1 1)(1)
(1)(1 1)(1 1)
(1)(1 1)(1)(1)
(1)(1)(1 1 1)
(1)(1)(1 1)(1)
(1)(1)(1)(1 1)
(1)(1)(1)(1)(1)
[1 1 1 1](1) # マッチを試行しない範囲は[ ]で表す
[1 1 1](1 1)
[1 1 1](1)(1)
[1 1](1 1 1)
[1 1](1 1)(1)
[1 1](1)(1 1)
[1 1](1)(1)(1)
[1](1 1 1 1)
[1](1 1 1)(1)
[1](1 1)(1 1)
[1](1 1)(1)(1)
[1](1)(1 1 1)
[1](1)(1 1)(1)
[1](1)(1)(1 1)
[1](1)(1)(1)(1)
(1 1 1 1 1)から始まり、[1](1)(1)(1)(1)のようにすべての1についてバックトラック範囲()が縮退したところで、やっと最初の試行を諦めてくれます。
対象文字列の1が5個の場合、空行で区切った組み合わせの行数が16, 1, 2, 4, 8と伸びています（手動での試行なので実際の試行順序と異なる可能性があります）。
これを並べ替えて1, 2, 4, 8, 16とすると、2^0, 2^1, 2^2, 2^3, 2^4と読み替えられそうですね。少しだけ一般化すると2^0から2^(n-1)までを足し上げたものになりそうです。
最初の試行の総和も出してみる
念のため、最初のバックトラック試行回数の総和をWolfram Alpha先生に計算していただきました（まさか日本語でできるとは！）。
ステップ数の総和は先の引用どおり(2^n) - 1という解になりました。定数-1を無視すればざっくりO(2^n)という計算量になります。
参考: ランダウの記号 - Wikipedia
参考: 2の冪 - Wikipedia
最初の試行は、11111、つまりn=5の場合は(2^5) - 1で31ステップになります。
その後の試行
恐ろしいことに、これで終わりではありません。最初の試行ではバックトラック範囲の末尾が左方向に縮退しましたが、縮退は右方向にも起きます。
最初の試行を網羅してあきらめた後、やっと試行が1個進んで、今度は以下の()内でも同じことを繰り返します。
# バックトラック範囲が右方向に1文字縮退する
1 (1 1 1 1)
#↑次はここから
上では試行の開始点が1個進んで、()で囲まれた部分が右方向に縮退して1文字減ります。
つまり、最初の試行と同じようなことを、以下の()部分すべてについても繰り返すわけです。
# 対象文字列のバックトラック範囲が右方向に縮退し続ける様子
(1 1 1 1 1)
1 (1 1 1 1)
1 1 (1 1 1)
1 1 1 (1 1)
1 1 1 1 (1)
試行の開始点が前進するたびにバックトラック範囲が狭まるのでステップ数は逓減しますが、ちっともうれしくありませんね。
というわけで、最初の試行(1 1 1 1 1)から始まる長い長い旅は、1 1 1 1 (1)までたどり着いて、やっとすべてのバックトラック範囲を網羅できることになります。
そしてどの試行も、正規表現(1+)+bの末尾のbのせいで全部失敗します。
バックトラック回数の最終的な総和を推測
以上をまとめると、(1+)+bという正規表現で、対象文字列の1が5個の場合、最終的には以下の数値をすべて足し上げた回数だけバックトラックが発生するらしいと推測しました。
2^0 + 2^1 + 2^2 + 2^3 + 2^4 + # この行だけで (2^5) - 1
2^0 + 2^1 + 2^2 + 2^3 + # (2^4) - 1
2^0 + 2^1 + 2^2 + # (2^3) - 1
2^0 + 2^1 + # (2^2) - 1
2^0 # (2^1) - 1
これを足し上げると、31 + 15 + 7 + 3 + 1 = 57ステップとなり、先の31ステップより多くなります。
実装に依存しそうですが、どうやら(1+)+bという正規表現と11111bという対象文字列の場合、全体のステップは2^n - 1よりさらに増えそうだという見当はつきます。いずれにしろ、対象文字列が長くなれば大変なステップ数になることは実感できました。
再びWolfram Alpha先生に総和の一般式導出をお願いしたところ、2^(n+1) - n - 2と出ました。
実際のステップ数を見積もる算出式
上で数えたのはあくまでバックトラック部分のステップ数だけですが、実際の正規表現ではバックトラック以外のステップもあるはずです。
正規表現(1+)+bと対象文字列11111（n = 5）をそっと実験したところ、実際には終了までに183ステップを要しました（PCRE2、PHP >= 7.3の場合）。先の31ステップや57ステップよりもさらに多いですね。183に近いのは2^7.5 = 180.01933598なので、この場合ステップ数を算出する式はざっくり(2^(n+2.5) - 1)と書き換えられそうです。
念のため、冒頭で98286ステップを要した対象文字列11111111111111（n = 14）をこの式で見積もると、(2^16.5) - 1 = 92680.90002368となり、98286に近い値になりました。
もう少し精度を上げられそうです。(2^16.5847) - 1とすれば98285.11505364とさらに98286に近くなるので、これで上の式をもう一度書き換えると、およそ(2^(n + 2.5847)) - 1という式になります。
量指定子+の代わりに*を使うなど、正規表現の書き方次第ではさらにステップ数が増えるでしょうね。
次回は、Catastrophic Backtrackingが発生する条件や回避方法について書きます。
🔗 参考資料
- Runaway Regular Expressions: Catastrophic Backtracking -- 読みづらいですが汎用かつ非常に詳しく解説されています
- 破壊的なバックトラック(Catastrophic backtracking) -- JavaScript
- 正規表現でのメールアドレスチェックは見直すべき – ReDoS – yohgaki's blog
注意
通常、本シリーズでは外部の正規表現チェックWebサービスを用いていますが、本記事ではこれらのサービスに対して結果的にDoS攻撃することを防止するため、Catastrophic Backtrackingを発生させる正規表現を含むリンクは含めないようにしています。
本記事をお読みになった方も、これらのサイトでCatastrophic Backtrackingを大きな対象文字列で試すことは念のためなるべくお控えいただくようご配慮をお願いします。どうしてもやってみたい場合は、対象文字列を5〜6文字程度に減らしてください。
これらのサイトはCatastrophic Backtrackingを検出するとアラートを出して処理を中断するようになっていますが、それでもDoSにならないよう十分ご注意ください（それにCatastrophic Backtrackingを常に検出できるとも限りません）。ローカル環境で試すのがベストです。