🔬

テスト時生成オブジェクトを用いた正規表現のReDoS検知

に公開
2025/12/28
2件
Ruby
Security
正規表現
redos
tech

テスト時生成オブジェクトを使ったReDoS検知

2022年の初め頃からしばらくの間、RubyのReDoSについて調査を行っていました。
現在はRuby3.1もEoLとなり危険性もかなり下がったと思われるので手法を公開します。

検知方法

  1. テスト実行時に生成されたRegexpオブジェクトの情報をファイルに出力
  2. ファイルに集めた情報をReDoS判定ツール(recheck)にかける
  3. 判定結果の正誤を手動で確認

RubyではObjectSpace.each_objectによりオブジェクトの一覧を取得できることとObjectSpace::allocation_sourcefileによってオブジェクトの生成箇所を取得できることを利用します。

GCを止めた状態でテストを実行し、最後にRegexpオブジェクトの情報を集めてファイル内の位置などとまとめてJSONファイルとして出力します。

コードの一部.rb
GC.disable

require 'objspace'
ObjectSpace.trace_object_allocations_start

at_exit {
  list = ObjectSpace.each_object(Regexp)
    .select{ |object| Regexp.escape(object.source) != object.source }

  json = list.map do |object|
    file_path = ObjectSpace::allocation_sourcefile(object)
    ...

これをgemごとにテストを実行できる環境を用意して正規表現の情報を集めました。
gemごとにテスト実行方法などの違いがありそこそこ時間がかかるものでしたが、今ならばAIを使って早くできるかもしれません。

集めた情報のReDoS判定には、recheckを使用しました。

https://makenowjust-labs.github.io/recheck/

recheckはRubyには対応されていないので、生成された正規表現をjs向けに調整してから判定にかけています。その状態であっても精度が高く、最初は別の検知ツールを使っていたのですがRecheckに切り替えた結果、検知できるReDoSが多すぎて危険であったためこの記事を公開するのが数年間遅れました。

最後に判定結果を手動で確認します。
テスト側でしか利用されていないものや通常の利用であれば問題ないもの、Ruby側ではReDoSとならないものなどがありました。調査時は完全な自動化を目指していなかったので手動で行っていましたが、工夫次第では可能かもしれません。

手法の特徴

lintと違い動的に検知を行うため、実行時にしか生成されないものやライブラリ内にあるものを検知できるという特徴があります。

検出例として、ActiveModelの以下の場所では内部で使用しているDate内の正規表現を検知しています。

検出例

https://github.com/rails/rails/blob/v6.1.7.3/activemodel/lib/active_model/type/time.rb#L39

なお、DateはCVE-2021-41817の修正時に入力時の長さに制限がかかるようになったので、以前から安全な状態でした。

手法の問題点

正誤を手動で判断していたため、正規表現として同じ形のものが複数の箇所で出てきたものを見逃していた箇所がありました。

複雑な正規表現やjsに置換しきれないものも多く、特にRack::Multipart関連には複雑で問題点の把握が難しかったです。

CVE-2022-44572の修正前の正規表現は下のように人が読んで判断するのは難しいものでした。

❯ bundle exec irb
irb(main):001:0> require 'rack'
=> true
irb(main):002:0> Rack::Multipart::RFC2183
=> /^(?i-mx:Content-Disposition:\s*(?-mix:[^\s()<>,;:\\"\/\[\]?=]+)\s*)((?-mix:;\s*(?:(?-mix:((?-mix:(?-mix:(?-mix:[^ \t\v\n\r)(><@,;:\\"\/\[\]?='*%])+)(?-mix:\*[0-9]+)?))=((?-mix:"(?:\\"|[^"])*"|(?-mix:[^\s()<>,;:\\"\/\[\]?=]+))))|(?-mix:(?-mix:((?-mix:(?-mix:(?-mix:[^ \t\v\n\r)(><@,;:\\"\/\[\]?='*%])+)(?:\*0)?\*))=((?-mix:[a-zA-Z0-9\-]*'[a-zA-Z0-9\-]*'(?-mix:%[0-9a-fA-F]{2}|(?-mix:[^ \t\v\n\r)(><@,;:\\"\/\[\]?='*%]))*)))|(?-mix:((?-mix:(?-mix:(?-mix:[^ \t\v\n\r)(><@,;:\\"\/\[\]?='*%])+)\*[1-9][0-9]*\*))=((?-mix:%[0-9a-fA-F]{2}|(?-mix:[^ \t\v\n\r)(><@,;:\\"\/\[\]?='*%]))*))))\s*))+$/i

また、Rack::Sendfileの事例のようにRegex injectionによるものは検知できません。

ReDoSの報告と危険性

https://zenn.dev/ooooooo_q/articles/ruby_3_3_redos

報告したものは上のページに有るもので、CVEとしては13件、報奨金も10件以上頂きました。

中には危険性が高いものもいくつかあり、Rackの中でReDoSとなるものは、一般的なRailsサーバの殆どに影響を及ぼすものでした。これはCDN側でタイムアウトを設定していてもオリジンサーバ側で処理が継続してしまうため、プロセスが占有され続けるリスクがありました。Unicornなどであればプロセス単位で強制的に落とされますが、それも60秒であるので攻撃側からすると60秒ごとに攻撃すればよいというものでした。 [1]

これらの脆弱性評価はHackerOne上でも一貫しておらず、評価者や時期によってばらつきがあったように感じます。NVD等のCVSS評価も、ネットワーク越しに攻撃可能かといった個別の文脈が十分に反映されていない印象を受けました。

手法を他の言語や脆弱性へ展開可能か

ReDoSの検出自体はRuby以外の言語に対しても応用できそうですが、Rubyが正規表現が強力である分利用箇所が多いため問題となる箇所も多かった印象です。

テストごとの実行ということで、CIに組み込めるかどうかですが、ObjectSpaceを使った方法はメモリ量が多く取られるのであまり便利ではなく、TracePointを使ったほうが良さそうです。一番のハードルとなるのは正誤の判定で、手動ではなく自動化を目指そうとすると工夫が必要です。

ReDoS以外の脆弱性にも適用可能そうに思えるのですが、今のところ活用できていません。自動検出できるのであれば生成時点で例外にしたり、lintツールで検知できるので、自動検出が難しいReDoSではこの手法が有効ということのようです。

RubyのReDoSについて

ReDoSの危険性はもうないのか

現在のRubyはメモ化とtimeoutの両方により、危険性が大幅に下がっていますがゼロとまでは行きません。

複雑な正規表現の中にはメモ化がうまく行かないものもあるということと、Regexp.timeoutがうまく動かないパターンもあるようでした。[2] またtimeoutが設定されていても正規表現の判定自体が複数回実行されるようであれば、DoSに繋がる可能性は残ります。

また、CRuby以外の実装（JRuby等）においては、依然として注意が必要な場合もあります。

ReDoSの報告が増えた理由

Github advisoryを眺めていると数年前からReDoSの報告が増えているように感じます。recheckなどの検知ツールが増えたことがまず一つ、もう一つはhackeroneでReDoSに対して報奨金が支払われるようになったこと、また報奨金自体が増額したこともあります。

https://www.hackerone.com/press-release/hackerone-expands-internet-bug-bounty-improve-collective-security-software-supply
https://hackerone.com/ruby/policy_versions?change=3658667

2021年以前はシステムへ侵入できるような脆弱性にのみ報奨金が支払われていましたが、変更後はCVSSを基準としたためかDoSに対しても報奨金が支払われるようになりました。

12/28 typo修正、Regex injectionについて追加

脚注

  1. https://zenn.dev/ooooooo_q/articles/rack_update_now ↩︎

  2. timeoutの問題に関してはRuby3.4.8では再現しましたが、4.0.0-preview3では再現しなかっため4系では修正されている可能性もあります。 ↩︎

Discussion