Java正規表現エンジン（NFA）の仕組みと パフォーマンスを維持するための最適化手法

2026/05/30 JJUG CCC 2026 Spring
#jjug_ccc_m

Transcript

1. Java正規表現エンジン（NFA）の仕組みと パフォーマンスを維持するための最適化手法 2026/05/30 JJUG CCC 2026 Spring #jjug_ccc_m 竹内 雅和 (@tm0920.bsky.social)
2. 自己紹介 ・竹内 雅和 ・入社7年目 ・主にバックエンド担当 ・フロント/クラウドもちょっと触る ・Bluesky：@tm0920.bsky.social ▪ 今回の資料 ↓
3. 目次 • はじめに • NFA エンジンの基本とバックトラック （正規表現で文字を検索する仕組み） • Javaの機能を活かした最適化手法 • まとめとレビューの指針
4. はじめに • 背景 • 本セッションの目的 • 正規表現の基本的な説明 • 正規表現による CPU高騰の事例 はじめに
5. 背景 • 正規表現は非常に便利だが気をつけないとシステム不安定化を招く ◦ ReDoS※ など • 生成AIで複雑な正規表現を瞬時に生成できるようになった • 生成したコードをレビューして安全かを判断するのは 依然としてエンジニアの責任 はじめに - 背景 ※ ReDoS (Regular Expression Denial of Service)：正規表現の計算量爆発を悪用し、システムをダウンさせる攻撃
6. 本セッションの目的 • 想定するオーディエンス ◦ 実務で正規表現を「なんとなく」使っている ◦ 正規表現の実行原理や計算量のリスクを 詳しく理解していない中級エンジニア ◦ AIが生成した正規表現をレビューする立場にある開発者 • 持ち帰ってほしいこと ◦ 正規表現のマッチング処理の内部挙動イメージ ◦ 複雑な正規表現を扱う時に抑えておきたい観点 はじめに - 本セッションの目的
7. 正規表現の基本的な説明 • 正規表現とは ◦ 文字列のパターンマッチングを行うための表現言語 ◦ 入力バリデーション、ログ抽出、置換などで日常的に利用 • 本セッションで登場する重要な記号 はじめに - 正規表現の基本的な説明 記号 読み 意味 + 量指定子 直前の要素の1回以上の繰り返し ++ 独占的量指定子 1回以上の繰り返し（※ 後戻りしない） () グループ化 複数の文字をまとめる
8. 正規表現によるCPU高騰の事例 • 2019年7月2日に発生したCloudflare社のサービス障害 ◦ Cloudflareのサービスが27分間ダウン • WAF( Web Application Firewall )を使って、XSS(Cross-Site Scripting)を 検出するためのルールに対する小さな変更 ◦ 正規表現の構造に問題があり、評価処理が暴走してしまった はじめに - 正規表現による CPU高騰の事例 参考：https://blog.cloudflare.com/ja-jp/details-of-the-cloudflare-outage-on-july-2-2019/
9. 正規表現によるCPU高騰の事例 • 問題となった正規表現↓ (?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\ `|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*))) はじめに - 正規表現による CPU高騰の事例 参考：https://blog.cloudflare.com/ja-jp/details-of-the-cloudflare-outage-on-july-2-2019/
10. NFAエンジンの基本とバックトラック • NFAエンジンとは ◦ NFA：非決定性有限オートマトン • バックトラックの動き ◦ バックトラック：マッチ失敗時に「後戻り」して別パターンを探す処理 • ”幾何級数的”マッチ ◦ 幾何級数的：入力が少し増えただけで試行回数が急激に増えること NFAエンジンの基本とバックトラック
11. NFAエンジンとは • NFA（非決定性有限オートマトン）とは、次に進むべき状態の候補が複数あり得る （非決定性を持つ）抽象機械 • NFAエンジンは正規表現の記述通りに 文字列に対して「一歩ずつ」マッチするかを検証していく仕組みのこと • 「バックトラック」を駆使することで 後方参照などの複雑なルールを柔軟に判定する役割がある ※ バックトラックの具体的な動きは次のスライドで図解 • 迷路の分かれ道にパンくずを落としながら進み 行き止まりならパンくずまで戻って別の道を試す探索者のイメージ NFAエンジンの基本とバックトラック - NFAエンジンとは
12. バックトラックの動き(試行1) NFAエンジンの基本とバックトラック - バックトラックの動き
13. バックトラックの動き(試行2) NFAエンジンの基本とバックトラック - バックトラックの動き
14. バックトラックの動き(試行3) NFAエンジンの基本とバックトラック - バックトラックの動き
15. バックトラックの動き(試行4) NFAエンジンの基本とバックトラック - バックトラックの動き
16. ”幾何級数的”マッチ 少しの入力増加で照合パターンが爆発するケース • 以下のような入力と正規表現を考える • 入力：aaaaac • 正規表現：((a+)+)+b NFAエンジンの基本とバックトラック - ”幾何級数的”マッチ
17. ”幾何級数的”マッチ 少しの入力増加で照合パターンが爆発するケース • 評価される組み合わせは 3^(N-1) 通り • ①そのまま繋ぐ 例：[aaaaa] • ② a+ の区切りとする 例：[ (aa)+(aa) ] • ③ (a+)+ の区切りとする 例：[ ( (aa) + (aa) ) ] • N=30の場合、組み合わせは約68兆通りに… • 最終的にマッチしないため 候補を捨てきれずにすべての組み合わせを試すことになる NFAエンジンの基本とバックトラック - ”幾何級数的”マッチ
18. ”幾何級数的”マッチ • 実際に正規表現のマッチにどれくらい掛かるかを計測してみた NFAエンジンの基本とバックトラック - ”幾何級数的”マッチ ※ JMH (Java Microbenchmark Harness) を使って測定 ※ Fork:3, Warmup Iterations:10, Iterations:20 で計測 aの数 平均処理時間(ns/op) ±誤差 誤差の割合(%) 5 3202.387 229.329 7.161 10 122048.020 1784.955 1.463 15 4167584.069 77959.884 1.871 20 128045020.556 2912233.815 2.274
19. ”幾何級数的”マッチ NFAエンジンの基本とバックトラック - ”幾何級数的”マッチ
20. Javaの機能を活かした最適化手法 本章では、以下の3つのケースについて紹介 • バックトラックを抑える書き方 （独占的量指定子による状態保持の抑制） • Java側が自動で助けてくれるケース （Java正規表現ライブラリで行われている内部最適化） • それでも危険なケース （内部最適化が効かないケース） Javaの機能を活かした最適化手法
21. バックトラックを抑える書き方 独占的量指定子による状態保持の抑制 • 量指定子の違いと「ロック」 ◦ 通常の量指定子（+） ▪ 後から戻って別の分け方を試す（バックトラックする。） ◦ 独占的量指定子（++） ▪ 一度マッチした部分を 「ロック」し後から戻らない • 正規表現の改善 ◦ 前回のケース：((a+)+)+b ◦ 改善後：((a++)++)++b • 得られる効果 ◦ ++ を使用することでバックトラックが発生しなくなる ◦ 膨大だった組み合わせの数が1通りに抑えられる Javaの機能を活かした最適化手法 - バックトラックを抑える書き方
22. バックトラックを抑える書き方 • 実際に正規表現のマッチにどれくらい掛かるかを計測してみた Javaの機能を活かした最適化手法 - バックトラックを抑える書き方 ※ JMH (Java Microbenchmark Harness) を使って測定 ※ Fork:3, Warmup Iterations:10, Iterations:20 で計測 aの数 平均処理時間(ns/op) ±誤差 誤差の割合(%) 5 61.266 2.869 4.683 10 96.091 2.660 2.768 15 89.411 2.646 2.959 20 126.486 5.042 3.986
23. バックトラックを抑える書き方 Javaの機能を活かした最適化手法 - バックトラックを抑える書き方
24. Java側が自動で助けてくれるケース Java正規表現ライブラリで行われている内部最適化 Javaの機能を活かした最適化手法 - Java側が自動で助けてくれるケース • 危険そうに見える構造でも 内部最適化により計算量が抑えられるケースがある • 以下のような入力と正規表現を考える • 入力：aaaaac • 正規表現：(a+)+b • ‘a’ の数を Nとした場合、評価される組み合わせは 2^(N-1) 通り • [aaaaa]、[ (aa)+(aa) ]、[ ( (aa) + (aa) ) ] のように ①そのまま繋ぐ、② a+ の区切りとする といった分け方ができるため • 先と同様、照合パターンが爆発的に増えそうだが 内部最適化によって抑えられる時もある
25. Java側が自動で助けてくれるケース • 実際に正規表現のマッチにどれくらい掛かるかを計測してみた Javaの機能を活かした最適化手法 - Java側が自動で助けてくれるケース ※ JMH (Java Microbenchmark Harness) を使って測定 ※ Fork:3, Warmup Iterations:10, Iterations:20 で計測 aの数 平均処理時間(ns/op) ±誤差 誤差の割合(%) 5 511.936 21.849 4.268 10 1332.949 230.082 17.261 15 1468.105 40.783 2.778 20 2363.093 70.242 2.972
26. Java側が自動で助けてくれるケース Javaの機能を活かした最適化手法 - バックトラックを抑える書き方
27. 内部最適化が効かないケース • ”幾何級数的”マッチ のスライドにあった正規表現「((a+)+)+b」 • 先の正規表現「(a+)+b」と比べてネストが1つ増えただけ • それだけでも実行時間は 数万倍程度変わってくる Javaの機能を活かした最適化手法 - 内部最適化が効かないケース
28. まとめとレビューの指針 • 正規表現をレビューする際のチェックポイント • 安全な設計指針 • まとめ まとめとレビューの指針
29. 正規表現をレビューする際のチェックポイント まとめとレビューの指針 - 正規表現をレビューする際のチェックポイント • 見るポイント ◦ 量指定子がネスト（入れ子）になっていないか ◦ 正規表現の選択肢の境界が曖昧になっていないか ▪ マッチの組み合わせが文字数に応じて無数に生じ バックトラックの試行回数が膨大になる ◦ マッチしない入力を与えた時に処理時間が長くなっていないか ▪ マッチしない入力では考え得るすべての照合パターンを テストするためパフォーマンス上の問題が発生しやすい
30. 安全な設計指針 • アトミックグループや独占的量指定子を活用しバックトラックを抑制する • リテラルテキストやアンカーを目立たせる • 選択肢の並べ方を工夫し、重複したマッチが起きないようにする • キャプチャが不要な場合はキャプチャ無しの括弧を使う • 余分な文字クラスを扱わない まとめとレビューの指針 - 安全な設計指針
31. まとめ • 正規表現は非常に便利な反面、実装によってはシステムの不安定化を招く • 生成AIが出力した複雑な正規表現をレビューし、問題無いかを判断するのはエン ジニアの責任 • 正規表現のコードを適切にレビューするために、NFAエンジンの仕組みを理解した 上で、チェックポイントや設計指針を持ち、自信を持ってレビューをする必要がある • AIが出力したものを鵜呑みにしないためにも、基礎や原理に立ち返る必要がある まとめとレビューの指針 - まとめ
32. ご清聴ありがとうございました 質疑応答(例) • AIのコードのどこをまず見る？ • なぜネスト１つで激変する？ など… （アンケートも書いてほしい…🙏→） 今回の資料 ↓ 全体アンケート↓　セッションアンケート↓