正規表現における実行時間と DoS 攻撃 (ReDoS)

正規表現の処理にかかる負荷で生じる DoS 攻撃の種類である ReDoS についての覚え書き

python-multipart というライブラリで過去に存在した CVE の脆弱性を元に簡単な検証をする

検証環境

Windows 11 Home
Ubuntu 24.04 (WSL)

基礎

ReDoS は正規表現 (Regex) を用いたパターンマッチなどにおいて, 評価に時間がかかるような文字列 (パターンにマッチするかどうかを判断するために非常に多くの組み合わせを調べる必要がある文字列) を送ることで負荷をかけ, サービスを妨害する攻撃
ライブラリなどでチェック機構が用意されておらず自分でチェックしなければいけない場合などに注意しなければいけない (html のエスケープなどと同様原則信頼のおけるライブラリに任せるべきなもの)
ruby を用いた簡単な検証については参考記事を参照のこと

CVE-2024-24762

ReDoS の脆弱性 (既に修正済み)
独自実装の正規表現を使ったことにより脆弱性が生じた例
github advisory database
NVD

python-multipart について

multipart/form-data という複数の情報を扱うための MIME タイプにおけるフォームの解析を行うライブラリ
FastAPI のファイルのアップロードなどの際に使われている
multipart/form-data についての参考サイト

対象となる正規表現

python-multipart のバージョン 0.0.6 では parse_options_header という関数で ctype, options という形で Content-Type (MIME タイプ) とオプションの辞書をパースする関数に脆弱性が存在した
ダウンロード用の URL などで使われる Content-Disposition ヘッダーの値に以下のようなものがある場合に, Content-Type の部分とオプションの部分に分離することがこの関数の主な役割となる

multipart/form-data; boundary=----hogebound; charset=utf-8

処理の結果は以下のようになる

ctype: b'multipart/form-data'
options: {b'boundary': b'----hogebound', b'charset': b'utf-8'}

この関数ではオプションの抽出の際に以下の正規表現が使われていた

# These are regexes for parsing header values.
SPECIAL_CHARS = re.escape(b'()<>@,;:\\"/[]?={} \t')
QUOTED_STR = br'"(?:\\.|[^"])*"'
VALUE_STR = br'(?:[^' + SPECIAL_CHARS + br']+|' + QUOTED_STR + br')'
OPTION_RE_STR = (
    br'(?:;|^)\s*([^' + SPECIAL_CHARS + br']+)\s*=\s*(' + VALUE_STR + br')'
)
OPTION_RE = re.compile(OPTION_RE_STR)

この正規表現では (先頭文字もしくはセミコロン) でオプションの開始を検知し, 特殊文字 (SPECIAL_CHARS) 以外の文字列で構成された key が存在し, = の後の VALUE_STR で許可された文字列までマッチする
VALUE_STR では引用されている文字列について QUOTE_STR で検知している
この QUOTE_STR について, "(?:\\.|[^"])*" ではバックスラッシュ+任意の一文字 (\\.) もしくはダブルクォート以外の任意の一文字 ([^"]) が 0 文字以上続く, という表現がされている
しかし, [^"] はバックスラッシュを含むため, そもそもマッチしない文字列においてバックスラッシュが出てきた場合に, 最初のバックスラッシュ+一文字を \\. として処理し後続の文字列を検証したのちに, マッチしなければ今度は [^"] 側として処理して後続の文字列を検証する, というバックトラックが生じる
今回の場合は以下のような文字列が与えられた場合に負荷が高くなる (実際にはバックスラッシュをもっと増やす)

"\\\\\\\\\\\\\\

ここではダブルクォートが一つあるのにそれが閉じられないため QUOTED_STR にはマッチしないが, 各バックスラッシュごとに先ほど説明した分岐の両方が試されるため, ざっくり $(2^n)$ のオーダーで計算量が増加する

検証

以下では落ちる可能性を考えて Docker 環境で parse_options_header を用いてバックスラッシュの数と実行時間を調べた簡単な検証となる
コードは github で公開

time-backslash image

横軸がバックスラッシュの数を表し, 縦軸が実行時間を表す
バックスラッシュが多い場合に指数的に実行時間が上昇していることが分かる

まとめ

正規表現などはできる限り信頼できるライブラリなどを頼るべき