こんにちは！！
株式会社ミラボ 開発部の山口です。
はじめに
さてみなさん、正規表現は使ってますか？文字列の抽出や解析をシンプルに行える上、文法も柔軟で様々なケースに対応することができるので便利ですよね。
最近では生成AIに要件を伝えると瞬時に出力してくれるので、ますます取り扱いやすくなっていると感じます。
しかし便利で簡単に扱える反面、その書き方に関して意識が必要な時があります。その一つが正規表現を悪用した攻撃である「ReDoS」に関してです。
ReDoSとは?
"regular expression denial of service"の略です。
正規表現を用いているアプリケーションコードに対して、計算量を膨大にするような文字列を与えることで、速度低下や機能停止を引き起こすという攻撃です。
実際悪用される場面もあるようで、色々なOSSで修正PRが出ているのを時々見かけます。
以下はいくつかの例です。
意図的な攻撃ではなくても、取り扱うデータによっては想定していなかった文字列によって正規表現の機能が暴走して性能低下を引き起こすことはあり得ると思います。
ReDoSを回避できるように、実際の動作検証や対処法の検討を行いましょう。
動作検証してみる
JavaScriptを用いて、簡易的に検証してみます。
「2文字以上で末尾がbで終わる文字列」をマッチさせるという前提で考えてみましょう。
解として、.+(任意の1文字以上) と b$(最後がbで終わる)という正規表現を組み合わせて、 /.+b$/ を考えました。
これに対してJavaScriptで長い文字列を用意し、マッチする・しないパターンにおける正規表現の処理時間を計測してみます。
// 実験1：マッチするパターン
const start1 = new Date().getTime();
const result1 = `${'a'.repeat(100000)}b`.match(/.+b$/g);
console.log(result1, (new Date().getTime() - start1)); // 末尾bでマッチする
// 実験2：マッチしないパターン
const start2 = new Date().getTime();
const result2 = `${'a'.repeat(100000)}c`.match(/.+b$/g);
console.log(result2, (new Date().getTime() - start2)); // 末尾がcでマッチしない
自分の環境でそれぞれ実験した結果は実験1が0ms、実験2が4466msでした。実験の環境にもよるのですが、マッチしないパターンの方が非常に遅いのがわかると思います。
原因は正規表現の探索の仕方にあります。.+は最初できるだけ長く文字列を取り（最長一致）、一文字ずつ減らして探索するという動きをします。したがって、マッチする文字列が見つからない場合は文字数分探索するので遅くなってしまうのです。
では、これを改善してみましょう。
簡単な解決策の一例としては^(先頭からのマッチング)を加えて、 /^.+b$/とすることです。
// 実験2（改善版）：マッチしないパターン
const start2 = new Date().getTime();
const result2 = `${'a'.repeat(100000)}c`.match(/^.+b$/g);
console.log(result2, (new Date().getTime() - start2)); // 末尾がcでマッチしない
この修正により、自分の環境では処理速度が0msになりました。正規表現の*や+は探索の範囲が広くなりがちなので、^をつけて先頭からの探索を強制して範囲を制限することで解決したわけですね。
簡単な例ですが、その危険性を体感できたと思います。
ReDoSへの対策
ReDoSを引き起こさないためには以下のような対策が挙げられます。
- 危険な正規表現になっていないかを意識的に確認
まずは意識することです。
さまざまな状況があると思いますが、*(0文字以上のマッチ)・+(1文字以上のマッチ)などを使用しているときは特にご注意ください。よく使われる正規表現の一つではありますが、同じ文字列の中で繰り返し探索が行われて時間がかかる危険性を秘めています。
- 正規表現以前で長い文字数を制限
良い正規表現が作れても、長い文字列を捌くのはそもそも時間を要するケースが多いです。正規表現以前で文字数のバリデーションができないかを考えると良さそうです。
- 正規表現に対してReDoS対策用の自動テストを作成
正規表現とセットでReDoSが起きないか検証するテストを書くのも良さそうです。（以下は例です。）
- 生成AIを使う場合はまず確認・可能ならプロンプトにReDoSの検証を追加
生成AIで作成した正規表現に対してはすぐに流用せず、まず安全かを注意深く確認するのが良いでしょう。
また、可能であればプロンプトで生成AIにReDoSの可能性を考慮させるのも良いかもしれません。もちろん、それだけで100%安全になるわけではないですが、可能性を示唆することで事故を回避できるかもしれません。
- 正規表現ツールで可視化・負荷を検証
以下のような、正規表現による計算量を可視化してくれるようなツールを使うのも一つの手です。内部的な動作がわかりづらい場面もあると思うので、有効活用すると良いでしょう。
おわりに
特に最近は生成AIの普及により、難しい文法を覚えていなくても要件に沿った正規表現を簡単に生成できるようになっていますが、一方でこういった危険性があるということも学んだため、ご共有でした。
みなさんも正規表現に出会った時は、ぜひこういった視点からも見てみてください。
参考
株式会社ミラボの社名は「ミライ × labo（ラボ）」に由来します。「いまここにない未来を創造」し「社会に貢献する」ことを基本理念に、主に電子申請サービスや母子保健・福祉・医療・教育に関するDXサービスを展開しており、約300自治体のDX支援を行っております。
Discussion