第74回　正規表現の脆弱性「ReDoS」徹底解説～原理と対策から、Perlでの最適化まで（2）

本連載では第一線のPerlハッカーが回替わりで執筆していきます。今回のハッカーは藤浪大弥さんで、テーマは「ReDoS徹底解説」（⁠2）です。

＜前回（1）はこちら。＞

ReDoS対策あれこれ

ReDoSの対策として、有効な順に次のものがあります。

セッション単位のタイムアウトの利用
DFA型のマッチ実装の利用
入力の長さの制限
ReDoS検出実装の利用
そもそも正規表現を利用しない
マッチ単位のタイムアウトの利用

これらの対策について解説します。

セッション単位のタイムアウトの利用

ReDoS対策と言うよりは一般的なDoS対策なのですが、最も有効で基本的な対策は、セッション単位でタイムアウトを行うことです。PlackやRackなどのミドルウェアを使って実現できるはずです。

ほとんどのアプリケーションでは、これを徹底することでReDoS、つまりマッチ時間の爆発でサービスがダウンすることは防げます。しかし、マッチ時間の爆発する正規表現があった場合、タイムアウトのせいで本来の処理が実行できなくなります。これは大きな問題のため、ほかの対策も必要になるでしょう。

DFA型のマッチ実装の利用

C++のライブラリre2や、Go言語のregexp、RustのregexなどのDFA型のマッチ実装を利用することで、線形のマッチ時間が保証されます。re2は多くの言語にバインディングが提供されていて、比較的手軽に利用できます。

ただし、DFA型の実装では後方参照など一部の拡張が利用できません。それらが必要な場合は別の対策が必要です。また、依存関係のライブラリの内部で使われる正規表現実装が切り替わらない可能性もあるので注意してください。

入力の長さの制限

短い入力しか受け付けないことで、マッチ時間が爆発する正規表現でも大した時間にはならなくすることができます。よって、入力文字列の長さを制限することも対策になります。ただし、指数的な場合は100文字以下程度の文字列でも数秒のマッチ時間になるので注意が必要です。

ReDoS検出実装の利用

正規表現がReDoSを引き起こすかを判定するReDoS検出実装を利用することで、正規表現を安心して使えます。拙作ですが、recheckをお勧めします。多くの正規表現に対して高速な解析が行えることが特徴です。実装の詳細な解説は筆者のYAPC::Japan::Online2022での発表を参照してください。ESLintプラグイン（eslint-plugin-redos）や、手軽に使えるプレイグラウンドもあるので便利です。

ただ、結果が必ずしも正確とは限らず、現実的な時間で解析できない可能性もあるため、検出結果を確認して過信しすぎないことが重要です。

そもそも正規表現を利用しない

使っている正規表現が単純な場合は、そもそも正規表現を使わないプログラムに書きなおすのも一つの手でしょう。特に、文字列の空白の除去などの基本的な機能は標準ライブラリで提供されていることも多いので、それらを適切に使いましょう。

マッチ単位のタイムアウトの利用

.NETの正規表現実装ではマッチ単位のタイムアウトができます。Rubyでは次バージョンの3.2でタイムアウトの導入が予定されています。このような言語でのサポートがなくても、スレッドやプロセスでタイムアウトは実現できます。

ただし、環境の違いや負荷の状況なども含めると、妥当なタイムアウト時間の設定が難しいことが問題です。そのため、ほかの対策と比べると根本的な対策とはなりにくく、筆者としてはタイムアウトはセッション単位で行うほうが有効だと考えています。

Perlでの実装の工夫

Perlはほかの言語よりも正規表現を頻繁に利用するという事情もあり、マッチの高速化のためにさまざまな工夫がされています。それらの一部をここでは紹介します。

`use re 'debug'`を使う

Perlの正規表現マッチの挙動を確認するために便利なuse re 'debug'プラグマを紹介します。このプラグマを有効にすると、正規表現の内部表現やマッチの過程が標準エラーに出力されます。debugをdebugcolorにすると、出力に色が付いてさらに便利です。

トライ構造の利用

perl -e 'use re debug; /^(fizz|buzz|fizzbuzz)*$/'をためしに実行してみましょう。最初のほうに次の出力が得られます。

$ perl -e 'use re debug; /^(fizz|buzz|fizzbuzz)*$/'
Compiling REx "^(fizz|buzz|fizzbuzz)*$"
Final program:
   1: SBOL /^/ (2)
   2: CURLYX[0]{0,INFTY} (19)
   4:   OPEN1 (6)
   6:     TRIEC-EXACT[bf] (16)
          <fizz>
          <buzz>
          <fizzbuzz>
  16:   CLOSE1 (18)
  18: WHILEM[1/1] (0)
  19: NOTHING (20)
  20: SEOL (21)
  21: END (0)

キャッシュの利用

次にperl -e 'use re debug; ("a" x 10 . "b")=~ /^(a*)*$/'を実行してください。たくさん出力されますが、途中でWHILEM: Detected a super-linearmatch, switching on caching...と表示されます。

この表示は、マッチが明らかに線形ではないと検出したので、キャッシュによる最適化を有効にしたことを意味します。キャッシュでは正規表現のどの繰り返しかと文字列の位置をキーとして、その繰り返しにその位置で到達したことを記録します[1]。再びそこに到達したとしたら、そこからのマッチは失敗するので、実行を省略できます。

ReDoSへの影響

Perlにはこれ以外にも、正規表現中の固定文字列を取り出して、始めにそれが含まれるかを検証するなど、細かな最適化をいくつも行っています。ですが、これらの対策にもかかわらずReDoSは完全には防げていません。もちろん、まったく無意味なわけではなく、指数的な爆発はかなり起こりにくくなっているのですが、2乗的な爆発は簡単に起こり得ます。

爆発の起こる理由の一つは、キャッシュ戦略が適切でないことです。実は正しいキャッシュ戦略を取ることでマッチの計算量を線形にできるのですが[2]、メモリを大量に消費するなど別の問題があるので、今後修正されるかはわかりません。もう一つの理由は、こういった最適化は正規表現が後方参照などの拡張を含まないことを前提としているので、後方参照があると無効になるためです。後方参照はいくつかの正規表現の最適化を無効にするので、パフォーマンスを意識している場合は注意が必要です。

まとめ

ReDoSの起こる原理やその対策、さらにPerlでの実装の工夫について紹介しました。本稿を通じてReDoSがオートマトン理論に基づく理論的な裏付けのある脆弱性だと伝わり、日常の開発やReDoS対策、対応の役に立てば幸いです。

ReDoS検出の研究が盛んになったことで、近年、ReDoSの報告数も増加しています。脆弱性が大きな問題になる前に発見されるのは喜ばしいことですが、脆弱性への対応や依存関係の更新が開発者の大きな負担となっていることも事実です。そこで筆者は、正規表現をReDoSが起こらないように修正する技術や、プログラム上での使われ方も含めて実際に問題になるかを解析する技術など、ReDoSへの対応を容易にする研究に取り組んでいきます。今後の報告にご期待ください。

さて、次回の執筆者は一野瀬翔吾さんで、テーマは「Perlで始める！ AWS Lambda入門」です。お楽しみに。