ハイプリッド型ReDoS検出エンジンの実装

摘要

ReDoSとは高い負荷をかけてサービスを妨害するDoS(Denial-of-Service)攻撃の一種で，バックトラック型の正規表現エンジンではパターンによってはマッチに入力文字列に対して非線形な(二乗や指数的な)時間がかかる場合があることを利用したものである。この脆弱性は次の2つの方法で検出できることが知られている。1)パターンに対応する非決定性有限状態オートマトンの遷移関数から，ReDoSの原因となるような構造を探索する方法。2)遺伝的アルゴリズムによって入力文字列をいくつも生成し(ファジング)，ReDoSの原因となるような文字列を発見する方法。オートマトンの解析を用いる場合は原理的に対応の難しい構文があり，ファジングの場合は必ずしもReDoSを検出できるとは限らない。本研究では，パターンに応じて適切な検出手法を選択するハイブリッド型のReDoS検出プログラムを実装し，既存のReDoS検出エンジンとの比較を行なった。その結果，既存のものよりも多くの正規表現をタイムアウトせずに解析することができ，またより多くの脆弱性のある正規表現を正確に検出することができた。