アドカレ2021
技術ブログ

正規表現が ReDoS 脆弱になる 3 つの経験則

正規表現が ReDoS 脆弱になる 3 つの経験則

はじめに

皆さんこんにちは．3回生のらん（@ran350jp）です．

文字列マッチングに便利な正規表現ですが，テキトーに書くと脆弱になり得るという情報を耳にしてから色々と原因や対策を調べていました．

しかし，多くの記事で紹介されていた対策方法は，「独自の正規表現を使用しないー」とか「 * や + などの繰り返し表現はなるべく使わないー」とかいう なんともふわっとしたものでした．これでは「いやぁ確かにそうなんかもしれんけど…そうゆう訳にはいかんやんか…」と納得できません．

つまり，「本質的に何が問題」で，「具体的にどんな特徴のある正規表現が脆弱になり得るのか」を知りたい訳です．

そこで，様々な文献を調査してみました．本記事では調査して溜まった知見を紹介していきます．

本記事は， Purdue大学のJames Davis教授による “The Regular Expression Denial of Service (ReDoS) cheat-sheet” を参考にしています．

目次

  • 結論
    • ReDoS 脆弱性 の原因
    • ReDoS 脆弱になる 3 つの経験則
    • 対策
  • 前置き
    • 正規表現 とは
    • ReDoS 攻撃 とは
    • 攻撃例
    • 被害事例
    • 問題点
  • 正規表現エンジン
    • 正規表現エンジンとは
    • バックトラックとは
  • ReDoS の原因
    • バックトラックの増加
    • ReDoS 脆弱になる 3 つの経験則
    • 曖昧さ
  • 対策
    • 問題のある曖昧な表現を取り除く
    • ReDoS 脆弱性検出ツール
    • タイムアウトを設定する
    • DFA型エンジンを使う
  • おわりに

結論

ReDoS 脆弱性 の原因

VM型正規表現エンジンでの，組み合わせ爆発によるバックトラックの増加

ReDoS 脆弱になる 3 つの経験則

1. 量指定子がネストされている

マッチング処理時間は指数関数的に増加．　例　(a+)+b

2. 選択の両方にサブマッチし得るパターンが繰り返されている

マッチング処理時間は指数関数的に増加．　例　(a|.)+b

3. 繰り返し表現が連結している

マッチング処理時間は多項式的に増加．　例　a.+b.+c

対策

  • recheck などの ReDoS 脆弱性検出ツールを用いる
  • タイムアウトを設定する
  • Google/RE2 などの DFA型エンジンを使う

前置き

知っとるわという方は本章は読み飛ばしちゃってください

正規表現 とは

正規表現は、文字列の集合を一つの文字列で表現する方法の一つである。

https://ja.wikipedia.org/wiki/正規表現

用途としては，ユーザの入力が指定のフォーマットに従っているかを検証したいとき や，文章内である特徴をもった文字列を検索したいとき などに使用されます．

構文としては，連接，選択，繰り返しの3つの基本演算を備えています．

連接

ab という正規表現があった場合，a というパターンの直後に b というパターンが続きます．

選択

| 演算子を用いると，それぞれのパターンのどれかに一致すればマッチが成立します． 例えば， ab|cd という正規表現は ab または cd というパターンを表します．

繰り返し

* や + などの量指定子を用いると，繰り返しを表現できます． 例えば， a+b という正規表現は， 1回以上の a の繰り返しの後に b が続くパターンを表し， b や ab ， aab などの文字にマッチします．

ReDoS 攻撃 とは

評価に非常に長い時間がかかる正規表現を提供することによってサービス拒否を生成するアルゴリズムの複雑さの攻撃

https://en.wikipedia.org/wiki/ReDoS からの翻訳

脆弱な正規表現に対してマッチしない長い文字列を与えると，実行時間が異常に長くなるという現象が起こります．このような脆弱性を利用してサーバーの計算リソースを奪う攻撃を ReDoS 攻撃と呼びます．

攻撃例

具体的な攻撃例を見てみましょう．はじめに紹介した3つのパターンが ReDoS 脆弱になることを確認してみます．

実験1 (a+)+b

正規表現 (a+)+b に対して，連続した n 文字の a を入力として与え，マッチング処理を実行させてみます．

そして， a，aa，aaa，…，と入力文字列を増やしたときにマッチング処理にかかる時間を計測してみます．

実行環境： Google Chrome (ver 94.0.4606.81) DevTools Console

以下は，入力文字列の長さと正規表現マッチングにかかった時間を出力する JavaScript プログラムです．

for(let i=1; i<=30; i++) {
    const start = new Date().getTime();
    
    const regex = /(a+)+b/;
    regex.test("a".repeat(i));
    
    const end = new Date().getTime();
    console.log(`${i} :${(end-start)/1000}s`);
}

結果は右図の通り．たった30文字のマッチング処理にもかかわらず，30 秒もかかっていることがわかります．

また，その増え方に着目すると，後半にかけて急激に増加しており，入力文字列が1文字増えるごとに約2倍長くなっています．つまり，指数関数的に計算量が増える処理だということがわかります．

入力文字列長：マッチング時間
実験2 (a|.)+b

今度は実験1から，正規表現パターンを (a|.)+b に変更してマッチング処理を実行させてみます．

for(let i=1; i<=30; i++) {
    const start = new Date().getTime();
    
    const regex = /(a|.)+b/;
    regex.test("a".repeat(i));
    
    const end = new Date().getTime();
    console.log(`${i} :${(end-start)/1000}s`);
}

結果は右図の通り．実験1と同様に，指数関数的に計算量が増えています．

入力文字列長：マッチング時間
実験3 a.+b.+c

最後に，正規表現 a.+b.+c に対して， ab，abab，ababab，…，と入力文字列を増やしたときにマッチング処理にかかる時間を計測してみます．今度の入力文字列は1文字ずつではなく，500文字ずつ増やして8000文字になるまで調べます．

for(let i=0; i<= 8000; i+=1000) {
    const start = new Date().getTime();
    
    const regex = /a.+b.+c/;
    regex.test("ab".repeat(i/2));
    
    const end = new Date().getTime();
    console.log(`${i} :${(end-start)/1000}s`);
}

結果は右図の通り．処理時間の増え方は実験１，２より緩やかですが，計算量は多項式的に増加していることがわかります．

入力文字列長：マッチング時間

被害事例

問題点

以下のような問題点が挙げられます．

  • 正規表現は，ブラウザやファイヤーウォール，Webサーバ，データベースなど様々な処理系で使用されているために攻撃の対象範囲が広い．
  • ReDoS 脆弱性のある表現は，文法的には正しいため実行時にエラーにならない．
  • 多くのスクリプト言語で採用されている正規表現エンジンでは，マッチング処理が無限に続くのか，近い将来停止するかを事前に知ることができない．
  • 正規表現の難読性により隠れた脆弱性に気づけない．

正規表現エンジン

正規表現エンジン とは

正規表現エンジンは，正規表現と文字列を受け取り，正規表現が文字列と一致するかどうかを判断します．ReDoS の原因はこの正規表現エンジンの検索プロセスにあります．

正規表現エンジンを実装するアプローチは， VM型（Virtual Machine：仮想マシン）， DFA型（Deterministic Finite Automaton：決定性有限オートマトン） の2種類があります．

VM型は多くのプログラミング言語や環境で採用されており，今回の主役になります．

（それぞれの詳しい内部実装は 技術評論社の 正規表現技術入門 ――最新エンジン実装と理論的背景 で紹介されていますので是非）

バックトラック とは

VM型エンジンでは，バックトラックをしながら一致するかを探索します．イメージを掴むために regex101 という正規表現デバッガツールを用いてバックトラックによる探索の様子を見てみます．

以下の動画は .*a という正規表現に対して 1234567890 という文字列を与えたときの動作です．この正規表現は，任意の文字列に a が連結しているという意味なので，結果としてはマッチしません．たった10文字の入力なので探索は一見すぐに終わりそうですが，ステップ数は77もあります．

https://regex101.com/

よくみると以下のような手順で探索していることがわかります．

  1. i 文字目から末尾までを対象文字列（動画では青マーカーの部分）とする　（ただし i の初期値 = 1）
  2. 末尾から順に a を探す
  3. マッチしなかったので i を +1 する
  4. 1 〜 3 を繰り返す
  5. 対象文字列が0文字になったらマッチしなかったとして終了する

動画中で緑マーカーになっている部分は探索中の正規表現を表しています．これを踏まえると，手順と正規表現の対応付けとしては， 「手順1は .* の探索」，「手順2は a の探索」であると言えます．

ここで，通常は右方向へ進む探索中の正規表現（緑）が，手順3→1の瞬間に左方向へ戻る動きをしています．このような挙動をバックトラックと呼びます．

ReDoS の原因

前置きが長くなってしまいました．ここからが本題です．

バックトラックの増加

結論から言うと，ReDoSの原因は 状態遷移の仕方が膨大になり，バックトラックが増加してしまうことです．

VM型エンジンは複数の状態遷移方法がある場合は一つずつチェックし，マッチしなかったらバックトラックして もう一つの遷移方法をトライする，という方法で探索を行います．このとき，元の正規表現に曖昧さがあると状態遷移の方法が膨大になってしまいます．その結果，バックトラックが増加し 計算量が巨大になることでReDoSが起こってしまいます．

曖昧な表現で状態遷移の分岐が増える具体的な例は後述します．

ReDoS 脆弱になる 3 つの経験則

曖昧な表現は色々ありますが，以下の３つが典型的な脆弱パターンです．（というか個人的にはこれが一番知りたかったやつ）

1. 量指定子がネストされている

前述した実験1で確かめたように指数関数的に計算量が増加するやばいやつです．

  • (a*)*b
  • (a+)+b
  • (a*){9}
2. 選択の両方にサブマッチし得るパターンが繰り返されている

こちらも指数関数的に計算量が増加するやばいパターンですね．

  • (a|.)+
  • (.|\w)*
  • (a|aa)*
3. 繰り返し表現が連結している

こちらは前述した実験3で多項式的に計算量が増加することを確かめたパターンです．上記２つより計算量は小さいですがそれゆえに気づきにくいですね．

  • (a|b)*(a|c)*d
  • .*.*a
  • a.*b.*c

曖昧さ

上記3つのパターンを例にその曖昧さを確かめてみます．

1. 量指定子がネストされている 場合

(a+)+b を例に曖昧さを確認してみます．

下図は，正規表現可視化ツール regexper で (a+)+b を可視化したものです．左の丸から対象文字列が与えられて，いずれかのパスを通って右の丸で受理されればマッチする という意味になります．

対象文字列が a であるときには，内側のループでも外側のループでもマッチできるため複数のパスが生じます．さらに，対象文字列数が増えれば増えるほどパスの組み合わせは増大します．

https://regexper.com/#(a+)+b
2. 選択の両方にサブマッチし得るパターンが繰り返されている 場合

次に，(a|.)+b を例にみてみます．

対象文字列が a であるときには， a という表現にも 任意の文字列 . にもマッチできるため複数のパスが生じます．さらに，対象文字列数が増えれば増えるほどパスの組み合わせは増大します．

https://regexper.com/#(a|.)+b
3. 繰り返し表現が連結している 場合

次に，a.+b.+c を例にみてみます．

対象文字列の2文字目が b のときには，1つ目の . にも1つ目の . にもマッチできるため複数のパスが生じます．さらに，対象文字列数が増えれば増えるほどパスの組み合わせは増大します．

https://regexper.com/#a.+b.+c

このように，曖昧な表現により対象文字列が複数のパスにマッチし得る場合に，文字数が増えるほど組み合わせが爆発し，結果としてReDoSが起こります．

対策

問題のある曖昧な表現を取り除く

ReDoS 脆弱な正規表現をリファクタリングし，曖昧な表現を取り除くことで安全にするという対策がまずは考えられます．

脆弱な表現を見つける

そのためにはまず，任意の正規表現が ReDoS 脆弱かどうかを判断する必要があります．

一つは，前述した 3つの経験則に合う表現がないかを確認する方法があります．ただ，この3つの経験則はあくまで経験則であり，これ以外にも脆弱になるトリッキーなパターンは存在します．

そこで，regexper のような可視化ツールを用いて曖昧な表現がないかを識別したり， regex101 のようなデバッガツールを用いてステップ数を確認したりします ．（他にも「正規表現チェックツールまとめ – Qiita」では便利なツールが紹介されているので是非ご参照ください．）

安全な表現に変える

脆弱性が発見されたら次は曖昧な表現を取り除いていきます．アプローチは色々あると思いますので一部例を紹介します．

  • *? や +? などの控え目な量指定子を使う（欲張り量指定子 * , + は使わない）
    • 例　.+a　→　.+?a
  • {n} などの範囲量指定子を使って繰り返し回数の上限を決める
    • 例　.+a　→　.{5}a
  • 任意の文字を表す . の代わりに文字クラス [] を使う
    • 例　.+a　→　[^a]+a

人の目でチェックするなら重要な対策だと思います．とはいえ，正規表現が複雑になってくると判断が難しかったり，うっかり見落としてしまったりということは避けられませんし，ある程度経験値を必要とする方法です．ということでその他の対策案も紹介します．

ReDoS 脆弱性検出ツール

人力での判断では厳しいのでツールに判定してもらおうという案です．

いくつか調べた中で最も精度が良かったのは recheck という検証ツールでした．Web サイト上でも脆弱性判定ができ，JavaScript と Scala をサポートしたライブラリが提供されているようです．

また，safe-regex を対策として紹介している記事もありました．しかし，このライブラリは，リポジトリの README で紹介されているように「量指定子がネストされている」かどうかのみ判定するため，他の脆弱パターンには対応していないようです．

（他にも優良な検証ツールがありましたら是非ご連絡ください！）

タイムアウトを設定する

正規表現マッチング処理が現実的に終わらなくなり，サーバがダウンしてしまうことがReDoS攻撃の脅威でした．ということで，マッチング処理に一定時間以上かかる場合はタイムアウトしてしまおうという対策です．

DFA型エンジンを使う

VM 型エンジンでは ReDoS 脆弱性が生じ得ますが， DFA 型エンジンではそもそもバックトラックによるマッチングは行わないため，そのような脆弱性もありません． したがって， DFA 型エンジンを用いて防ぐ対策も有効です．

Google/RE2

Google の RE2 というライブラリを用いる対策があります．DFA に基づき，安全で高速にマッチング処理を行うことができます． C++製 のライブラリではありますが，C言語や Python， Node.js ，Ruby などの環境でも利用できるようラッパーライブラリが提供されています．

V8 エンジン

また，JavaScript 環境では，V8 エンジン [※] で付属されている非バックトラッキングエンジンを用いるという対策も考えられます． v8.8 以降の V8 エンジンでは，線形時間での実行を保証する 非バックトラッキング型の正規表現エンジンが付属されました．また， Node.js の v16 では V8 エンジンが v8.6 → v9.0 になったため，オプション指定で非バックトラッキングエンジンでの実行が可能になりました．(詳細は，An additional non-backtracking RegExp engine を参照)

[※] Chrome など Chromiumベースのブラウザや Node.js で使用されている JavaScript 実行エンジン

非対応の機能

しかし，DFA型エンジンでは，VM型エンジンでは提供されている応用的な機能が提供されていないことがあります．

例えば，RE2 は，後方参照や先読み後読みといった，バックトラッキングによる実装が必要な機能はサポートしないと明言されています．

It is also not a goal to implement all of the features offered by Perl, PCRE and other engines. As a matter of principle, RE2 does not support constructs for which only backtracking solutions are known to exist. Thus, backreferences and look-around assertions are not supported.

WhyRE2 · google/re2 Wiki

したがって，DFA型エンジンを採用する場合は，使いたい正規表現演算に対応しているかを確認する必要がありそうです．

おわりに

いつのまにかアドカレに書く文量ではなくなってしまいました．みなさんの正規表現ライフの助けになれば幸いです．

おまけ

開発環境で ReDoS 脆弱性判定ができる VSCode 拡張機能 “ReDoS-Checker-for-VSCode” を作ってみました．内部では，本記事でご紹介した recheck を用いて脆弱性判定をしています．

image/demo.gif

Twitterでフォローしよう

おすすめの記事