ちょっと待って！そのAIに作ってもらった正規表現、危険かも！

こんにちは！アルダグラムでレポートチームのエンジニアをしている志茂です。

レポートチームでは、お客様が利用されているExcelファイルをKANNA上にアップロードし、
Webから編集できるような機能を開発しております。

正規表現についてやってしまったなという話です。
エンジニアなりたての頃は何も見ずに、正規表現をささっと書いてしまう先輩が職人っぽくてかっこよく思いましたが、最近はclaudeなり、GPTがあるので、判定したい文字列を渡して、複雑なものでもサクッと生成してしまうことが多いかなと思います。

そんな正規表現ですが、合致するものをベースに生成した場合に、セキュリティ的にちょっと危険なものはちょっと出ちゃうかもというのが、今日の本題になります。

経緯

複雑な正規表現で正確に把握できてないけど、テストちゃんとしてるし大丈夫だよね！という実装箇所がありました。
ある日、レポートのアプリケーションサーバーのCPUが突如として CPU 使用率 100% に張りついて、元に戻らないという事情が発生しました。

調査した結果、正規表現の判定が動き続けている事象が発生しており、シート名を判定するのような長い正規表現が根本原因でした。

// シート名の正規表現.
private val sheetNameRegex = """[a-zA-Zａ-ｚＡ-Ｚ0-9０-９_ぁ-んァ-ン一-龥ー（） ]+""".toRegex()

// シングルクォートでエスケープされたシート名の正規表現
private val quotedSheetNameRegex = """'(?:[^'\\\\]|''|\\\\.|\\(|\\)|${sheetNameRegex.pattern})*'""".toRegex()
private val cellLabelRegex = """\$?[A-Z]+\$?[0-9]+""".toRegex()
private val sheetNameAndCellLabelRegex =
        """(?:(${quotedSheetNameRegex.pattern}|${sheetNameRegex.pattern})!)?(${cellLabelRegex.pattern})(?::(?:(${quotedSheetNameRegex.pattern}|${sheetNameRegex.pattern})!)?(${cellLabelRegex.pattern}))?""".toRegex()

これが原因で、破壊的バックトラック(Catastrophic backtracking)を引き起こして、計算量が爆発的に増加して、CPUが張りつき続けてしまいました。
悪意がある利用でないにも関わらず、正規表現を使ったDoS攻撃のような状態が発生してしまいました。
再デプロイし、実行中の処理を中断することで一旦ことなきをえました。

正規表現の利用時に発生する破壊的バックトラック

先ほどの例では、正規表現が複雑すぎて読む気が起きない方もいたかもしれません。
なので、もっと簡単な例を使って破壊的バックトラックがどう起きるのかを説明します。

ケース：シート名を判定する処理
例えば、Excel の数式に出てくる「シート名!セル番地」のうち、シート名を抽出するような処理があるのですが、次のようなシンプルな正規表現を使ったとしましょう。

val sheetNameRegex = """^(Sheet[0-9]+)+!""".toRegex()

これは、Sheet1! や Sheet23! のような形式にマッチさせるものです。
ここでは必ずSheetの後に、数値が続くものだけを判定したいとしましょう。
合致するものだった場合はいいのですが、次のような途中までは正しくて、最後に合致しない文字の入力がきた場合どうなるでしょうか。

Sheet111111111X

この文字列は一見すると Sheet から始まっているため、途中まで正しくマッチしてしまいますが、最後の X でマッチが失敗してしまいます。
Javaの正規表現エンジン（Regexエンジン）ではバックトラック法で合致する文字列を探索していきます。

そのため、Sheet11111111Xではうまくいかなかったが、Sheet11111111 + Xで分けたらマッチするか、Sheet1+ 111111 + 1Xなどはマッチするかなど、分割できる全てのパターンを試し続けます。
この全て試すパターンが大量になって、計算量が指数関数的に増加することを破壊的バックトラックと呼びます。

+などの量指定子（quantifiers）をネストして、使用することで発生するのですが、例えば上記の1の文字が100文字続いた後にXがあった場合、パターンマッチの計算量は、各文字の間の数は99なので、2 ^ 99になってしまいます。

GPTにこの数を for ループするとどれぐらいかかるの？と聞いたところ、
とても私が生きている間に終わるような処理じゃないことがわかりました。

仮に 2^99 通りのパターンを for 文で1個ずつ試したらどうなるか？
秒数：約 1.4 × 10²³ 秒（＝140,537,626,530,200,650,000,000,000 秒）
分：約 2.3 × 10²¹ 分
時間：約 3.9 × 10¹⁹ 時間
日数：約 1.6 × 10¹⁸ 日
年数：約 4,456兆年（4,456,418,903,164,658 年）

ということで、(Sheet[0-9]+)+! のように量指定子がネストされた正規表現入りの正規表現を使うと、ただの数百文字のStringのデータしか受けていないのにも関わらず、簡単にシステムがクラッシュすることがわかりました。

解決策

そもそも量指定子をネストさせないようにするとか、正規表現のライブラリ変えるとか、タイムアウト設定するとか、色々やり方はあるようでしたが、結局最初の辛めな正規表現を利用しないといけなさそうでしたので、根本対策としてはちょっと不十分でした。

ただ、レポートチームにはすでに ANTLR という強力なライブラリが利用できる状態だったので、
複雑なシート名判定をするパーサーをジェネレイトして、探索アルゴリズム自体を変更することで、解決しました。
詳細割愛しますが、文字列をトークンとして認識して、ツリーを作成してReactのように探索していくので、今回のように合致しないパターンが発生しても問題なく処理できます。

以前のANTLRの記事
https://zenn.dev/aldagram_tech/articles/8d712209c13973

興味のある方が少ない気もするので簡単に説明すると
目的のパーサーを生成するANTLRの定義ファイルを書いて、buildして、生成されたパーサーのメソッドをオーバライドして使用します。
ANTLR では文法ルール単位で構文を設計できるため、保守性と拡張性の観点で大きな利点があります。

Excel 関連の構文（シート名やセル座標など）を判定対象ごとで切り出すことで、後続のロジックやテストもしやすくなりました。ANTLRを利用したことで、処理時間は大幅に短縮され、CPU 負荷も劇的に改善しました。めでたし、めでたし！

最後に

生成された複雑な正規表現がある場合、合致パターンだけではなく、合致しないパターンも網羅的に確認しましょうという学びと、これ長すぎて運用辛いなーと思ったら、ANTLRというストロングな手段もあることを覚えていただけると嬉しいです！

Kotlin + ANTLR4 の組み合わせは、Visitor パターンを使うことで構文処理もロジックも明快に設計できるので、おすすめです。

もし似たような正規表現を日々の業務で使っている方がいれば、その一行が、将来のトラブルの火種になっていないか、ぜひ見直してみてください。

参考リンク
https://ja.javascript.info/regexp-catastrophic-backtracking

もっとアルダグラムエンジニア組織を知りたい人、ぜひ下記の情報をチェックしてみてください！