Cloudflare世界障害（2019）— 1本の正規表現

何が起きたか（日時・影響範囲）

2019年7月2日 13:42 UTC、CloudflareがXSS検知を改善するWAFマネージドルールを展開した直後、世界中の全エッジサーバーでHTTP/HTTPSを処理するCPUが100%に張り付きました。新ルールに含まれた1本の正規表現が壊滅的バックトラッキング（catastrophic backtracking）を起こしたためです。Cloudflareを経由するサイトは約27分間502 Bad Gatewayを返し、グローバルのトラフィックは約80%落ち込みました。規模と同時性から当初はDDoS攻撃も疑われましたが、外部要因はなく、自社のダッシュボード・API・社内認証まで巻き込んだ自滅型の障害でした。

タイムライン

公式ポストモーテムが公表した時系列です（すべてUTC）。

決断（14:02）から実行（14:07）までの5分は偶然の遅れではありません。Cloudflareは自社製品を自社で使っており、認証サービスのAccessが障害に巻き込まれて内部管理パネルへログインできず、さらに一部のメンバーは「管理パネルを長期間使わないと資格情報を無効化する」セキュリティ機能でアクセス権を失っていました。緊急停止は「存在」していても、「届く」までに時間を要したのです。

根本原因の技術解説

問題の正規表現は次のとおりです。

(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))

致命部は末尾の .*(?:.*=.*)、本質だけ残せば .*.*=.* です。CloudflareのWAFはNGINX上のLuaで実装され、正規表現は内部でPCREにより評価されていました。PCREはNFAを深さ優先のバックトラッキングで模倣するため、.* が2つ並ぶと「1つ目がどこまで飲み込み、2つ目がどこから引き継ぐか」という分割点の候補が入力長のぶん生まれ、後続の = の照合に失敗するたびに分割点を巻き戻して再試行します。付録の実測では、x=x のマッチに23ステップ、x= の後ろに x を20個並べると555ステップ。さらに末尾に ; を要求する .*.*=.*; は、どう分割しても失敗が確定するまで全候補を試し尽くすため、x=x で90ステップ、x が20個で5,353ステップへ爆発します。試行回数は入力長に対しおおむね二乗で増え、量指定子が入れ子なら指数にもなり得ます。WAFは全リクエストのURIやヘッダへルールを適用するので、攻撃どころか通常トラフィックだけでCPU時間が枯渇し、プロキシ本体が応答不能となって502を返しました。

なぜ防げなかったか

横にスクロール

Cloudflareの通常のソフトウェアリリースは、社員だけが使うDOG PoP、ごく一部の顧客トラフィックを流すPIG PoP、カナリアPoP群を経て全世界へ、という段階的ロールアウトを踏みます。しかしWAFマネージドルールは「新種の攻撃に数分で対処する」ための例外としてこの経路を完全に迂回し、分散KVストアQuicksilverで即時に全世界へ一斉配信されていました（配布のp99は2.29秒）。カナリアで異常を観測する機会は、構造的に存在しなかったのです。

さらに悪条件が重なります。CIのテストはルールの検知精度だけを確認し、CPU消費を測定していませんでした。正規表現の暴走を打ち切る保護機構は、数週間前のリファクタリングで誤って取り除かれていました（皮肉にも、WAFのCPU使用量削減が目的の改修でした）。新ルールはブロックしない「シミュレート」モードでの展開でしたが、判定には正規表現の実行そのものが必要なため、実行コストが欠陥である本件では防波堤になりませんでした。

教訓（原則として一般化）

Cloudflareの再発防止策は、外れていたCPU保護の復活、全3,868本のマネージドルールの点検、テストスイートへの性能プロファイリング追加、そしてRE2またはRustのregexという実行時間を保証するエンジンへの移行でした。線形時間エンジンはThompson構成のNFAの状態集合を入力1文字ごとに同時に進めるため、後方参照などの機能を捨てる代わりに、どんなパターンでも実行時間が入力長に比例します。

• 任意入力に触れる正規表現には線形時間保証か実行上限を課す: エンジンを替えられないなら、PCREのマッチ上限のような打ち切りを必ず設定します。
• 設定もコードと同じ危険物として段階展開する: 数秒で全世界へ届く配信路は、最速で全世界を壊す経路でもあります。緊急用の即時展開は残しつつ、既定はカナリア観測を挟みます。
• 緊急停止は「届くこと」まで設計する: 障害下でも認証・経路・権限が生きているかを訓練で確かめます。Cloudflareもダッシュボード・APIを自社エッジから切り離す緊急手段を整備しました。

カナリアリリースなど段階展開の設計はDevOps、WAFや多層防御の考え方はセキュリティの各トピックも参照してください。