utilrepo
日本語
❤️ 応援
← ブログ開発者向け

破滅的バックトラッキングとその他の正規表現の罠

バックトラッキング型の正規表現エンジンが悪意ある入力でどう爆発するか、入れ子の量指定子がなぜ ReDoS を引き起こすか、そしてそれを直すアンカー・アトミックグループ・線形エンジンを整理します。

100 万件の入力でマイクロ秒で走る正規表現が、100 万 1 件目の入力でリクエスト スレッドを数秒間止めることがあります。原因はほぼ常に同じです。重なり合う 量指定子を持つパターンに、ほぼ マッチする入力が入ってきた場合です。エンジンは あきらめる前に、失敗する方法を指数的に多く探索します。この記事では、その爆発が どう起きるか、それを引き起こすパターンをどう見分けるか、そして代わりに何を すべきかを説明します。

バックトラッキングエンジンがパターンを評価する仕組み

日常的に使う正規表現エンジンのほとんどはバックトラッキング型の NFA エンジンです。 PCRE、Java の java.util.regex、JavaScript の RegExp、Python の re、Ruby の Onigmo、.NET です。これらは 1 つの動作原理を共有しています。+ や * のような 量指定子が、ある区間を 2 通り以上の方法でマッチできるとき、エンジンは 1 つを 選んで進み、残りのパターンが失敗すると 後戻りして 次の方法を試します。

具体的に、a+ を aaa にマッチさせると次のようになります。

  • a+ が貪欲に a を 3 つすべて消費します。
  • パターンでその後に来るものが、その位置で試されます。
  • 失敗すると a+ が a を 1 つ返し、再試行します。
  • これはパターンがマッチするか、a+ が a 1 つまで減るまで繰り返されます。

単一の量指定子なら、再試行の回数は入力長に対して線形です。問題は、2 つの 量指定子が同じ文字を主張できるときに始まります。

破滅的バックトラッキングと ReDoS

このパターンを見てみましょう。

^(a+)+$

「1 つ以上の a、グループにまとめ、1 つ以上繰り返し、文字列の終端まで」という 意味です。aaaa には即座にマッチします。aaaaaaaaaaaaaaaaaaaaaaaaX にはマッチ せず (X が壊します)、そのマッチしない入力が最悪のケースです。

内側の a+ と外側の (...)+ が完全に重なります。n 個の a の並びは、2 つの 量指定子の間で 2^(n-1) 通りの異なる方法に分けられます。1 つの大きなグループ、 2 つのグループ、n 個の単独、そしてその間のあらゆる組み合わせです。文字列が 入力の終端ではなく X で終わるので、そのすべての分割が $ アンカーで失敗 します。エンジンは、マッチがないと結論づける前にそのすべてを律儀に試します。 a をもう 1 つ追加すると、作業量は倍になります。

同じ形が、より現実的に見えるパターンの中に潜んでいます。

^(\w+\s*)*$          # 空白で区切られた単語
^(\d+)*$             # 繰り返される数字グループ
(.*,)*               # カンマで区切られた何か
^([a-z]+)*$          # 典型例

それぞれ、2 つの量指定子が同じ文字をマッチできる場所で、量指定された部分式が 別の量指定子の中に入れ子になっています。失敗は、ほぼマッチする長い入力、通常は 攻撃者が制御する入力によって引き起こされます。

これが、これを単なる性能上の罠ではなくサービス拒否のベクターにする点です。 ReDoS (正規表現サービス拒否) は、入力検証に使われる正規表現、つまり メールフィールドや User-Agent パーサ、URL ルートマッチャが攻撃者の入力に さらされるときに起きます。攻撃者は数十バイトの細工された文字列を送り、サーバーは 正規表現エンジンで数秒から数分を費やし、ほんの数件のリクエストがスレッドプールを 枯渇させます。フォーラムからコピーした検証用正規表現が繰り返し原因になります。 整った入力を受け入れるように書かれているだけで、悪意あるほぼ一致に対して一度も テストされていないからです。

貪欲 vs 怠惰は解決策ではありません

よくある反射的な対応は、貪欲な量指定子を怠惰なものに変えることです。.* を .*? に、+ を +? に、「怠惰なら仕事が減る」という理屈に頼って。怠惰な 量指定子は、エンジンが可能性を試す 順序 を変えます。貪欲は最も長いマッチを 先に試して引き下がり、怠惰は最も短いものを先に試して伸ばします。可能性の 数 は 変えません。破滅的にバックトラックするパターンは、怠惰にしても同じように破滅的に バックトラックします。エンジンが探索空間のどちらの端から始めるかを変えただけ です。怠惰な量指定子は正確性のための道具 (最小の区間をマッチする) であって、 性能のための道具ではありません。

実際に効く緩和策

あいまいさを取り除きましょう。 ^(a+)+$ の本当の解は、それが ^a+$ と等価だと 気づくことです。破滅的なパターンのほとんどは、平坦であいまいさのない書き換えが あります。空白で区切られた単語が必要なら、^\w+(\s+\w+)*$ は区切りと単語が同じ 文字をマッチできないので、^(\w+\s*)*$ があいまいなところであいまいでは ありません。

パターンをアンカーしましょう。 アンカーは探索を区切ります。アンカーのない パターンは、暗黙にすべての開始位置で試され、作業量を増やし、しばしば遅さと偽の マッチの両方の原因になります。

アトミックグループか所有量指定子を使いましょう。エンジンが対応していれば。 アトミック グループ (?>...) は内容をマッチした後、その中のバックトラッキング位置を捨てます。 一度マッチすると、エンジンはその文字を返しません。所有量指定子 a++ は、単一の 量指定子に対する同じ考えの省略形です。(a+)+ を (?>a+)+ や a++ に書き換えると、 指数的な探索が線形に崩れます。エンジンの対応はまちまちです。

エンジン アトミックグループ (?>…) 所有量指定子 a++ 備考
PCRE / PCRE2 はい はい 完全対応
Java java.util.regex はい はい Java 4 / 5 から
Ruby (Onigmo) はい はい
.NET はい いいえ 所有量指定子は非対応
Python re はい はい 3.11 からアトミック + 所有
JavaScript RegExp いいえ いいえ TC39 の提案段階、lookahead で模倣

JavaScript では、アトミックグループと所有量指定子はまだ言語の一部ではなく提案 です。標準的な回避策は、lookahead と後方参照でアトミック性を模倣することです。 (?=(a+))\1 は貪欲なマッチをキャプチャし、返すことを拒みます。

線形エンジンに切り替えましょう。 RE2 (Google)、Rust の regex クレート、Go の regexp は別の実行モデルを使います。バックトラッキングなしで NFA を シミュレートし、パターンによらず入力長に対して線形なマッチ時間を保証します。 代償は機能の喪失です。後方参照も lookaround もありません。これらの機能こそが そもそもバックトラッキングを強制するからです。信頼できないパターンや信頼 できない入力を正規表現に通すなら、線形エンジンは ReDoS のクラス全体を構造的に 取り除きます。正規表現やその入力が完全には制御下にない、ユーザーに面する すべてのものにとって、それが正しいデフォルトです。

アンカー、lookaround、そしてそのコスト

^ と $ は文字列 (または行) の境界をマッチし、\b は単語の境界をマッチ します。性能上の役割を超えて、アンカーがないと正確性のバグが生じます。\d{4} は abc12345 の中でもマッチするので、^...$ のない「年」検証は garbage1999garbage を受け入れます。意図的にアンカーし、フラグによって $ が 文字列の終端をマッチするか行末をマッチするかを把握してください (MULTILINE が これを変えます)。

lookahead (?=...) / (?!...) と lookbehind (?<=...) / (?<!...) は、文字を 消費せずに何かが現れるか現れないかを表明します。パスワードの規則や「Y が後ろに 続かない X をマッチ」などに便利ですが、各表明はその位置で部分マッチを走らせ、 とくに lookbehind は内容が可変長のとき高くつくことがあります。これらはまた バックトラッキングエンジンを強制し、RE2 の類いを除外します。代替が本当により 悪いときに手を伸ばしてください。デフォルトでは使わないように。

そもそも正規表現を使うべきでないとき

正規表現は 正規 言語をマッチします。入れ子や再帰的な構造は正規ではなく、それを マッチしようとすると、壊れやすく、読めず、静かに間違ったパターンにつながります。

  • HTML と XML。 本物のパーサを使ってください。タグスープ正規表現は必ず 1 つの ケースを取りこぼします。
  • JSON、YAML、ソースコード。 入れ子の深さは無限です。正規表現は釣り合いの 取れた区切り文字を数えられません。
  • 算術式、釣り合いの取れた括弧。 同じ問題です。
  • 引用符の中にカンマが入った CSV。 専用の CSV リーダーのほうが短く正確です。

正規表現は、トークン化、平坦な形式の検証、行単位の検索・置換に適した道具です。 入れ子になるものをマッチしようとしていると気づいた瞬間、止まってパーサに手を 伸ばしてください。

出荷する前にテストする

最も安い防御は、すべての検証パターンを、本番に届く前に長くてほぼマッチする 悪意ある入力に対してテストすることです。ハッピーパスだけではなく。私たちの 正規表現テスター は、パターンをサンプル文字列に対して走らせ、 どう振る舞うかを見られるので、攻撃者が見つける前にあいまいな量指定子を捕まえ られます。そこにあいまいさのない書き換え、明示的なアンカー、そして制御しない 入力に対する線形エンジンを加えれば、破滅的なケースは決して発火しません。