論文「Towards Efficient Matching of Regexes with Backreferences using Register Set Automata」の技術的サマリー

この論文は、バックレファレンス（後方参照）を含む正規表現（Regex）のマッチングにおいて、従来のバックトラック法が抱える「ReDoS（正規表現によるサービス拒否）攻撃」の脆弱性と、非効率なパフォーマンスを解決するための新しいアプローチを提案しています。著者らは、**レジスタセットオートマトン（Register Set Automata: RSA）**という新しいオートマトンモデルを導入し、これを用いた決定論的マッチングアルゴリズムを開発しました。

以下に、問題定義、手法、主要な貢献、結果、および意義について詳細をまとめます。

1. 問題定義 (Problem)

• バックレファレンスを含む正規表現の課題:
  正規表現はデータ検証、検索、パースなど多くの分野で利用されていますが、バックレファレンス（例：(.).*\1 のように、前にキャプチャした文字列を後で参照する機能）を含む場合、その言語は正規言語を超え、マッチング問題が NP 困難になる可能性があります。
• 現在のマッチャーの限界:
  現在の主要なマッチャー（PCRE2, Python re, Java などの多く）は、バックレファレンスに対してバックトラック（後戻り）アルゴリズムを使用しています。これにより、入力文字列によっては指数関数的な時間がかかる「カタストロフィック・バックトラック」が発生し、サーバーが応答不能になる ReDoS 攻撃のリスクが高まります。
• 決定論的オートマトンの欠如:
  高速なマッチングを実現するには、決定論的有限オートマトン（DFA）のような線形時間のアルゴリズムが望ましいですが、従来の決定論的オートマトンモデル（レジスタオートマトンなど）はバックレファレンスを効率的に扱えず、バックレファレンス対応の決定論的マッチングアルゴリズムが存在しませんでした。

2. 手法と提案モデル (Methodology)

著者らは、**レジスタセットオートマトン（Register Set Automata: RSA）**という新しいモデルを提案しました。

• RSA の特徴:

  • 従来のレジスタオートマトン（RA）では、レジスタは単一のデータ値しか保持できませんでしたが、RSA ではレジスタが**データ値の集合（Set）**を保持できます。
  • 操作として、入力値のレジスタへの追加、レジスタ同士の結合（Union）、レジスタのクリア、および「レジスタに値が含まれているか」のテストがサポートされます。
  • この「集合」を扱う能力により、非決定性（Nondeterminism）を決定論的（Deterministic）にシミュレートすることが可能になります。

• コンパイルとマッチングのフロー:

  1. 正規表現から RA への変換: アンチミロフ導関数（Antimirov derivatives）に基づき、バックレファレンスを含む正規表現を非決定性レジスタオートマトン（NRA）に変換します。
  2. NRA から DRSA への決定化: 提案された半アルゴリズム（Algorithm 1）を用いて、NRA を決定性レジスタセットオートマトン（DRSA）に変換します。
     • この変換は完全ではありません（失敗する場合があります）が、実用的な多くのケース（特に単一文字のキャプチャグループを持つバックレファレンス）で成功します。
     • 変換には「レジスタのサイズクラス（0, 1, 複数）」の追跡や、カルテシアン積による過剰近似の検出などの技術が用いられています。
  3. DRSA によるマッチング: 生成された DRSA を用いて入力文字列を処理します。DRSA は決定論的であるため、バックトラックを必要とせず、入力長に対して線形（有限アルファベットの場合）または二次（無限アルファベットの場合）の時間でマッチングが可能です。

3. 主要な貢献 (Key Contributions)

1. レジスタセットオートマトン（RSA）の導入と理論的解析:

   • RSA の閉包性（和集合、積集合、補集合）や、決定性 RSA（DRSA）との関係を明らかにしました。
   • RSA の空性問題（Emptiness Problem）が決定可能であることを証明し、その計算量クラスが Fω完全（アッカーマン関数的な複雑さ）であることを示しました。これは従来の RA の PSPACE 完全よりも高くなりますが、決定可能であることは重要です。
   • RSA が他のオートマトンモデル（RA, ARA, ペブルオートマトンなど）と比較して、表現力において互いに包含関係にない（incomparable）ことを示しました。

2. NRA から DRSA への決定化アルゴリズム:

   • 単一レジスタを持つ NRA のブール結合（和・積・補）で記述される言語クラスに対して、このアルゴリズムが完全であることを証明しました。
   • 実用的な正規表現（単一文字のバックレファレンス）を効率的に DRSA に変換する手法を確立しました。

3. バックレファレンス付き正規表現のマッチングアルゴリズム:

   • 提案された DRSA ベースのマッチングが、有限アルファベットでは入力長に対して線形時間、無限アルファベットでは二次時間で実行可能であることを示しました。
   • 「コピーフリー（copy-free）」な条件を満たす場合、計算量がさらに改善されることも示しています。

4. 実証実験による性能向上:

   • Python でプロトタイプ実装（rsamatch）を行い、実世界のベンチマーク（Lingua Franca データセット、ReDoS 生成器 Rengar）を用いて評価しました。
   • 既存のマッチャー（PCRE2, grep, Python re など）が ReDoS 攻撃ベクトルに対して数秒から 100 秒以上（タイムアウト）かかるのに対し、rsamatch はほぼすべてのケースで 1 秒未満（平均 0.3 秒）で完了し、予測可能性と堅牢性が劇的に向上しました。

4. 結果 (Results)

• ReDoS 脆弱性の低減:
  実験では、1,335 件の ReDoS 脆弱性を持つ正規表現のうち、97% 以上で決定化アルゴリズムが成功し、DRSA を生成しました。生成された DRSA を用いたマッチングは、既存のバックトラックベースのマッチャーと比較して、実行時間のばらつき（標準偏差）が桁違いに小さく、安定しています。
• 決定化の成功率:
  単一文字のバックレファレンスを持つ正規表現の 91% について、DRSA への変換に成功しました。
• 理論的性質:
  • 空性問題は Fω完全であり、決定可能です。
  • 言語の包含問題（Inclusion Problem）は、DRSA と B(NRA=1) の間では決定可能です。

5. 意義と将来展望 (Significance and Future Work)

• セキュリティへの貢献:
  この研究は、Web アプリケーションやネットワークセキュリティにおいて広く使用されている正規表現マッチングの ReDoS 脆弱性を、理論的に保証された高速な決定論的アルゴリズムによって解決する道筋を示しました。
• 理論的枠組みの拡張:
  バックレファレンスを含む言語を扱うための新しいオートマトンモデル（RSA）を確立し、無限アルファベット上のオートマトン理論に新たな知見をもたらしました。
• 実用性:
  現在の産業用マッチャー（RE2 や HyperScan）はバックレファレンスをサポートしていませんが、このアプローチは「高速かつバックレファレンス対応」を実現する可能性を示唆しており、実用的なマッチングエンジンの開発への応用が期待されます。

結論:
この論文は、バックレファレンスを含む正規表現のマッチングにおいて、バックトラックに依存しない、予測可能で高速な決定論的マッチングを実現するための理論的基盤（RSA）と実用的なアルゴリズムを提供しました。実験結果は、このアプローチが ReDoS 攻撃に対する強力な防御策となり得ることを示しています。