正規表現の脆弱性を自動修正するアルゴリズムを開発 NTTと早稲田大学：理論的に「ReDoS脆弱性がないこと」を保証

NTTと早稲田大学は、正規表現の脆弱性に対する実用的な自動修正技術を開発した。論理モデルを定義し、脆弱性がないことを保証した正規表現を出力するアルゴリズムを考案した。

[＠IT]

　NTTと早稲田大学は2022年3月23日、正規表現の脆弱（ぜいじゃく）性に対する実用的な自動修正技術を開発したと発表した。専門知識を持たない開発者でも正規表現の脆弱性の修正が可能になるとしている。

早稲田大学のWebページから引用

脆弱性がないことを論理的に保証する

　正規表現の脆弱性の一つに「ReDoS脆弱性」（ReDoS：Regular Expression Denial of Service）がある。これは、正規表現を用いた文字列のパターンマッチ機能に対して、「処理時間が長くなる特殊な入力」を与えることで計算リソースを消費してサービスの運用妨害を引き起こすもの。早稲田大学によると「ReDoS脆弱性によって商用サービスが停止するインシデントはたびたび発生しており、大きな脅威として認識されている」という。

　NTTと早稲田大学が開発した技術のポイントは2つ。1つ目は「ReDoS脆弱性」「ReDoS脆弱性がないことを保証する条件」「ReDoS脆弱性の修正問題」の3点を論理モデルとして明確に定義したこと。もう1つは、ReDoS脆弱性がないことを保証した正規表現を出力するアルゴリズムを考案したことだ。

　このアルゴリズムは、利用者が望む正規表現に対してポジティブな例（受理される文字列）とネガティブな例（拒否される文字列）を与えると、それらの例を正しく分類して出力する。ReDoS脆弱性がないことを保証するため、正規表現の書き方から曖昧さを排除し、任意の文字列に対してパターンマッチの方法を一意に定める条件を定義。その定義に合う「修正正規表現」を出力させるため、「理論的にReDoS脆弱性がないことを保証できる」という。