正規表現サービス拒否（ReDoS）と壊滅的バックトラッキング

正規表現は非常に強力ですが、直感的に使えると思っている人を見つけるのは難しいでしょう。もちろん、あなたの知っているあの開発者のように正規表現が得意な人もいますが、多くの開発者は危険な使い方をしかねない程度の知識しか持っていません。残念ながら、正規表現とセキュリティに関する危険性は非常に高いものです。正規表現を誤解していると、攻撃者にサイトをダウンさせる機会を与えてしまう可能性があります。例として、次の正規表現を見てみましょう。

regex = /A(B|C+)+D/

分解すると、この正規表現は次のような処理を行います。

• A 文字列は「A」で始まる必要があります

• (B|C+)+ 続いて、文字列には「A」の後に「B」または「C」が1回以上続きます（+は1回以上の繰り返しに一致します）。この部分の末尾にある+は、この部分に1回以上一致することを示します。

• D 最後に、文字列のこの部分が「D」で終わることを確認します

この式は、たとえば次のような入力に一致します。

ABBD
ABCCCCD
ABCBCCCD
ACCCCCD

一般に、正規表現エンジンが一致を見つけるのにそれほど時間はかかりません。たとえば、次の30文字の文字列でテストした場合を見てみましょう。“ACCCCCCCCCCCCCCCCCCCCCCCCCCCCD”。

$ time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCD")'
0.04s user 0.01s system 95% cpu 0.052 total

予想どおり、この文字列にはすばやく一致します。処理全体にかかる時間は約52ミリ秒です（MacBook Airでテスト）。では、別の30文字の文字列をテストするとどうなるでしょうか。今回は有効な文字列ではなく、末尾の「D」を「X」に置き換えた無効な文字列を入力します。“ACCCCCCCCCCCCCCCCCCCCCCCCCCCCX”。

$ time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCX")'
1.79s user 0.02s system 99% cpu 1.812 total

すると、テストが完了するまでに約2秒もかかります。有効な文字列のテストにかかった時間の10倍以上です。この大きな差は、正規表現の評価方法によるものです。簡単に言えば、正規表現は簡単にはあきらめません。

正規表現エンジンの仕組み

正規表現エンジンの動作はそれぞれ異なりますが、大半はよく似た仕組みです。エンジンは現在の文字を受け入れる最初の方法で一致させ、次の文字に進みます。次の文字に一致しなければ、バックトラックして前の文字を別の方法で処理できないか確認します。文字列全体が最終的に一致しないとわかるまで深追いし、さらに多くの文字に複数の有効な正規表現の経路があると、バックトラックの回数が膨大になります。これが壊滅的バックトラッキングと呼ばれる現象です。短い文字列“ACCCX”を使って、この問題がどのように起きるかを見てみましょう。一見単純ですが、エンジンが3つのCに一致させる方法は4通りあります。

1. CCC

2. CC+C

3. C+CC

4. C+C+C。

エンジンは、これらの組み合わせが式に一致する可能性があるかどうかを、それぞれ試す必要があります。エンジンが実行するほかの処理も合わせると、RegEx 101 debuggerを使って、文字列が一致しないと判断するまでに合計38ステップ必要であることがわかります。さらに、文字列の検証に必要なステップ数は増え続けます。

文字列にCが14個含まれる時点で、有効かどうかを確認するだけでエンジンは65,000ステップ以上を実行します。元の文字列“ACCCCCCCCCCCCCCCCCCCCCCCCCCCCX”ではどうなるか想像してみてください。バックトラッキングがすぐに制御不能になることがわかります。以下は、RegEx101 debuggerが示したエンジンの処理のほんの一部です。

正規表現エンジンによる評価方法を踏まえると、無効な式の処理時間が大幅に増える理由が明らかになります。文字列の長さとエンジンが評価する経路数は、指数関数的な関係にあるのです。無効な文字列に文字を1つ追加するだけで、評価時間はほぼ倍になります。

$ time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCCX")'
3.51s user 0.06s system 95% cpu 3.732 total

NodeとReDoS

悪意のある攻撃者は、正規表現の解析の複雑さを悪用し、エンジンの評価に途方もない時間がかかる長く複雑な文字列を渡すことがあります。その結果、正規表現サービス拒否（ReDoS）攻撃が発生します。

どの環境でも望ましくない事態ですが、Nodeを含むJavaScript環境ではさらに深刻です。以前の記事でタイミング攻撃について説明したとおり、Node.js（およびJavaScript全般）はイベント駆動型です。

つまり、ReDoSリクエストの処理にスレッドが占有されると、そのリクエストがイベントループ全体をブロックし、アプリケーションはほかの処理を実行できなくなります。

実例

人気のmomentライブラリで最近見つかった実例を見てみましょう。momentは日付の解析、検証、操作、書式設定に使用されます。このツールでは、format()メソッドを使って日付の出力形式を指定できます。

moment().format('MMM Do YY');

//example output: Nov 22nd 16

書式を定義すると、momentは正規表現を使ってその書式を検証します。バージョン2.15.2より前のmomentでは、正規表現は次のようになっています。

var MONTHS_IN_FORMAT = /D[oD]?(\[[^\[\]]*\]|\s+)+MMMM?/;

重要なのは、式の(\[[^\[\]]*\]|\s+)+の部分です。特に、\s+は1つ以上の空白を検査します。しかし、このグループの直後にある+も、かっこ内のグループが1回以上出現することを意味します。つまり、書式に多数の空白が含まれる場合、正規表現エンジンは文字をグループ化するさまざまな方法を試して一致を探すことになります。空白全体を1つの大きなグループとして1回で一致させたり、個別のグループに分割してそれぞれ一致させたり、その中間の方法をとったりできます。その結果、有効に近い文字列の評価に長い時間がかかることがあります。

脆弱性を発見した際に投稿したこちらの例を見てみましょう。

var m = require("moment");
m.locale("be");
m().format("D                               MMN MMMM");
// Normal date format, other than the 31 spaces included in the string

この例では、多数の空白を含む40文字の文字列を渡しています。一般的なノートパソコンで実行すると、この式はイベントループを約20秒間ブロックしました。

$ time node -e '/D[oD]?(\[[^\[\]]*\]|\s+)+MMMM?/.test("D                               MMN MMMM");'
21.24s user 0.14s system 96% cpu 22.079 total

momentに脆弱性を開示した後、作者は余分な+演算子をかっこ内から削除する修正を作成しました（パッチが適用されるかどうかは、今すぐテストできます）。

var MONTHS_IN_FORMAT = /D[oD]?(\[[^\[\]]*\]|\s)+MMMM?/;

これにより、それぞれが空白の一部またはすべてを含み得る2つの異なる一致グループがなくなります。+演算子がsの後に続かなくなったため、一度に一致できる空白は1つだけです。新しい正規表現で再度テストすると、不一致を判定するまでの時間は数ミリ秒になりました。

$ time node -e '/D[oD]?(\[[^\[\]]*\]|\s)+MMMM?/.test("D                               MMN MMMM");'
0.05s user 0.02s system 53% cpu 0.135 total

壊滅的バックトラッキングを防ぐ

壊滅的バックトラッキングを防ぐには、「+」や「*」演算子が近接して使われていないか注意してください。近接している場合、壊滅的バックトラッキングを引き起こす綱引き状態に陥る可能性があります。両方の演算子が本当に必要か確認しましょう。どちらかを範囲指定に置き換えることもできます。momentのReDoS脆弱性では、「+」演算子の1つを削除して修正しました。代わりに、一方を範囲指定に置き換えて、有効な文字列で許可する空白の数を制限する方法もありました。

var MONTHS_IN_FORMAT = /D[oD]?(\[[^\[\]]*\]|\s+){0,10}MMMM?/;

正規表現の解析はかなり単純ですが、壊滅的バックトラッキングを防ぐ高度な機能を導入している言語もあります。最初に取り上げた簡略化した式を見てみましょう。

regex = /A(B|C+)+D/

アトミックグループ

説明したように、この式は壊滅的バックトラッキングを引き起こす可能性があります。Node.jsがサポートする正規表現パーサーには、この問題を解消するネイティブ機能がありません。しかし、ほかの言語にはそのような機能があります。たとえばRubyは、アトミックグループをサポートしています。アトミックグループを使うと、グループが一致した後にバックトラックしないよう、正規表現パーサーに指示できます。グループの前に?>を付けます。たとえば次のとおりです。

/A(?>B|C+)+D/

「C」が任意の数だけ続く部分を探すグループに?>を追加すると、アトミックグループになります。以前は、正規表現パーサーが競合する2つの演算子を考慮する必要がありました。グループ内の「C」は任意の回数一致でき、グループ自体も任意の回数一致できます。そのため、多数の「C」を含む無効な式が渡されると、パーサーは2つのグループの間で行き詰まり、式を有効にできる組み合わせがないか何度も試すことになります。

一方、アトミックグループを適用すると、パーサーはそのグループの一致を確定します。この場合、存在する「C」の数だけ一致します。式が無効であれば、このグループをさかのぼって再評価することはできません。ここでは一致が確定したものとして扱われます。2つの一致演算子の間で「C」を振り分ける必要がなくなるため、無効な式を非常にすばやく判定でき、壊滅的バックトラッキングを回避できます。

先読み

JavaScriptはアトミックグループをサポートしていませんが、アトミックグループと同様の効果を得るために使える先読みをサポートしています。

A(?=(B|C+))\1+D

この場合、?=を使って先読みを指定します。これは、直後に次のグループが続く場合にのみそのグループに一致することを意味します。\1を使って一致したグループをキャプチャすることで、実質的にアトミックグループを作成します。これにより、パーサーはこの一致をアトミックグループと同じように扱い、壊滅的バックトラッキングを回避します。

先読みを使った式で文字列をテストすると、不一致の判定時間が大幅に短くなったことがわかります（先読みなしでは1.8秒、使用すると94ミリ秒）。

$ time node -e '/A(?=(B|C+))\1+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCCX")'
0.05s user 0.02s system 51% cpu 0.094 total

ここでのトレードオフは複雑さです。壊滅的バックトラッキングを回避できますが、式の複雑さが増し、チームのほかのメンバーにとって読み解きにくくなるだけでなく、誤りも生じやすくなります。バックトラッキングを引き起こす演算子の組み合わせ（この場合は2つの+）を特定できるなら、わかりやすさと読みやすさを優先し、式全体を作り直すほうがよいかもしれません。

まとめ

ReDoS攻撃はアプリケーションを完全に停止させる可能性があります。イベントループによって壊滅的バックトラッキングの影響が増幅されるNode.jsの環境では、特に深刻です。

ReDoS脆弱性を防ぐには、正規表現を監視するとともに、依存関係にReDoS脆弱性がないかテストする必要があります。

ReDoS攻撃を受けやすい式を自動検出するツールはいくつか試みられています（特にsafe-regex）。しかし、簡単なテストだけでも多数の誤検知に加え、安全ではないにもかかわらず安全と判定された式がいくつも見つかりました。

依存関係のテストは比較的明確です。Snykがその作業を支援します。

いずれにしても、試してみる価値はあります。RegEx101のデバッガーのようなツールを使えば、さまざまな式を試しながら、正規表現パーサーが式に一致させるためにどのような手順を踏むかを理解できます。

時間をかけて試行錯誤すれば、いつかあなたも正規表現の豊富な知識を活かして、窮地を救う存在になるかもしれません。