ReDoS対策（re2の紹介）

導入

正規表現に対する攻撃として、ReDoSというものがあります。これは正規表現にマッチングさせる入力文字列によって、バックトラッキング^[1]が大量に発生したり、量指定子が入れ子になることで組み合わせ爆発を起こしたりすることにより計算量が爆発する脆弱性を突いた攻撃です。

Webアプリケーションにおいては、外部からの入力に対して正規表現をマッチングさせる場合に問題になり得ます。

対策

メモ化によってマッチングを高速化するなど、自前で実装するのも一つの手段だと思います^[2]。

https://techlife.cookpad.com/entry/2022/12/12/162023

他の選択肢として、Google製のre2というライブラリを紹介します。

https://github.com/google/re2/tree/main

これはマッチ時間が入力文字列に対して線形となるように設計された正規表現エンジン^[3]で、これによってReDoSを防ぐことができます。

C++で実装されたライブラリですが、PythonやNode.js、Rubyなど様々な言語のラッパーが用意されています。以下ではPythonを扱います。

Pythonの場合、使い方は簡単で、まずrye add google-re2やpip install google-re2などでインストールします。正規表現のパターンマッチもreとほとんど同様に使えるようです。

研究レベルでは、脆弱性のある正規表現を自動修正する技術も開発されているようです。

https://www.jstage.jst.go.jp/article/jssmjournal/36/3/36_16_17/_pdf/-char/ja

実験

標準の正規表現エンジンのreとre2でどの程度速度が違うのか実験しました。

次のように、脆弱性のある正規表現に対して攻撃用の入力を与えるコードを実行します。結果は以下のように、re2の方が大幅に高速となりました。

import re
import re2
import time

# 脆弱性のある正規表現
pattern = r"^a*a*$"

# 攻撃用の入力
malicious_input = "a" * 100000 + "!"


def measure_time(regex_module, pattern, input_str):
    """指定した正規表現モジュールとパターン、入力文字列でマッチングを行い、処理時間を計測する"""
    start_time = time.time()
    match = regex_module.match(pattern, input_str)
    end_time = time.time()
    elapsed_time = end_time - start_time

    print(f"\n--- {regex_module.__name__} の結果 ---")
    if match:
        print("Match found!")
    else:
        print("No match.")
    print(f"Elapsed time: {elapsed_time} seconds")


# re と re2 でそれぞれ処理時間を計測
measure_time(re, pattern, malicious_input)
measure_time(re2, pattern, malicious_input)

結果

--- re の結果 ---
No match.
Elapsed time: 35.3548641204834 seconds

--- re2 の結果 ---
No match.
Elapsed time: 0.0004999637603759766 seconds

上記コードの正規表現と入力文字列を以下に変えた場合も、re2の方が高速でした。

pattern = r"^(a+)+$"
malicious_input = "a" * 27 + "!"

結果

--- re の結果 ---
No match.
Elapsed time: 9.513674974441528 seconds

--- re2 の結果 ---
No match.
Elapsed time: 0.00017499923706054688 seconds

ちなみに、以下のようなパターンではre2の方が遅くなります。これはドキュメント^[3:1]記載通り、全ての状況で他のエンジンより高速であることを目指していないためだと思います。

pattern = r"^a*a*$"
malicious_input = "a" * 10000000

結果

--- re の結果 ---
Match found!
Elapsed time: 0.00580596923828125 seconds

--- re2 の結果 ---
Match found!
Elapsed time: 0.06998705863952637 seconds

re2の欠点

バックトラックの解決策しか存在しない、バックリファレンス^[4]や後読みアサーション^[5]に対応していません^[3:2]。

まとめ

正規表現を使用する際は、ReDoS攻撃のリスクを常に意識することが重要です。安全な正規表現パターンを採用し、ユーザー入力を適切にサニタイズするなど、対策を講じることが必要です。

ReDoS対策として、re2のようなReDoS対策が講じられた正規表現エンジンを導入することも有効な手段の一つです。ただし、re2にも機能制限や互換性の問題があるため、状況に応じて最適な対策を選択しましょう。

脚注

1. https://ja.wikipedia.org/wiki/バックトラッキング

2. プログラミング演習の題材としても良さそうだなと思いました。

3. https://github.com/google/re2/wiki/WhyRE2

4. https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Regular_expressions/Backreference

5. https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Regular_expressions/Lookbehind_assertion