# Towards Scalable Critical Alert Mining > [!abstract] 概要(abstract の日本語訳) > データセンター向けのパフォーマンス監視ソフトウェアは、典型的には大量のアラート系列を生成する。これらのアラート系列は異常なネットワークイベントを示す。観測されたアラート系列の集合が与えられたとき、他のアラートの原因である可能性が最も高い重要なアラートを特定することが重要である。大規模なアラート系列にわたって重要アラートをマイニングする必要性は明らかであるにもかかわらず、既存のアラート分析技術の大半は、アラート間の因果関係をモデル化しマイニングする段階で止まっている。 > 本論文は重要アラートマイニング問題(critical alert mining problem)を研究する。アラート系列の集合が与えられたとき、我々は、それらによって潜在的に引き起こされるアラートの数が最大化されるような k 個の重要アラートの集合を見つけることを目指す。この問題が扱いにくい(intractable)ことを示すため、我々は近似アルゴリズムとヒューリスティックアルゴリズムに頼る。第一に、我々は二次時間で近最適なアラート集合を得る近似アルゴリズムを開発し、その実行時間性能を改善する枝刈り手法を提案する。さらに、アラートがある種の因果構造に従う場合には、より高速な近似が存在することを示す。第二に、我々は木サンプリング手法に基づく 2 つの高速なヒューリスティックアルゴリズムを提案する。実データにおいて、これらのアルゴリズムは最大 270,000 件のマイニングされた因果関係から 5 秒で重要アラートを特定する。その一方で、これらは解の質の 80% 以上を保ち、近似アルゴリズムの対応版よりも最大 5,000 倍高速である。 ## 論文情報 - 著者: [[Bo Zong]]([[UC Santa Barbara]])・[[Yinghui Wu]]([[UC Santa Barbara]])・[[Jie Song]]([[LogicMonitor]])・[[Ambuj K. Singh]]([[UC Santa Barbara]])・[[Hasan Cam]]([[Army Research Lab]])・[[Jiawei Han]]([[University of Illinois Urbana-Champaign]])・[[Xifeng Yan]]([[UC Santa Barbara]]) - 発表: KDD 2014(20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining)、2014-08-24 - DOI: 10.1145/2623330.2623729 - 全文版: 参考文献 [1] に `full.pdf`(著者サイト)への言及がある。 ## 概要 データセンターやサイバーセキュリティのシステム監視は大量のアラート系列を生成する。既存のアラート分析技術の多くは、アラート間の因果関係(causal relation)のモデル化・マイニングで止まっており、「観測された膨大なアラートから、修正すれば他の多くのアラートの発生を抑えられる少数の重要アラートを提案する」という次の段階に踏み込んでいない。本論文は、この段階を**重要アラートマイニング問題(critical alert mining problem, CAM)**として定式化し、データセンター運用・侵入検知・ネットワーク性能診断の 3 つの実応用を挙げて動機付ける。 ## 問題設定 - **パフォーマンスメトリクス(performance metric)** `p ∈ P`: システム性能の一側面を測る(CPU 使用率、メモリ使用量、ディスク書き込みのエラー率など)。同種のメトリクスでもホスト・VM・サービスが異なれば別のメトリクスとして扱う。 - **アラート(alert)**: `u = (p_u, t_u, w_u)` の三つ組。`p_u` は対応するパフォーマンスメトリクス、`t_u` はタイムスタンプ、`w_u` は修正された場合の便益を表す重みである。 - **依存規則(dependency rule)** `p --l_pq--> q`: メトリクス `q` に発生したアラートが、時刻 `t' ∈ [t - l_pq, t - 1]` に発生したメトリクス `p` のアラートによって引き起こされることを示す統計的規則。`l_pq` は `p` から `q` へのラグ(遅延)であり、規則には不確実性(確率)`Pr(p --l_pq--> q)` が付与される。依存規則は Granger 因果性などの手法で自動学習されるほか、専門家や既存の知識ベースからも与えられうる。 - **アラートグラフ(alert graph)** `G = (V, E, f_e)`: 頂点集合 `V` はアラート、辺 `(u, v) ∈ E` は依存規則に基づく因果関係、`f_e` は各辺に対する「u が v を引き起こす確率」を割り当てる関数。有向非巡回グラフ(DAG)であり、アラートは(あれば)ただ 1 つの先行アラートによって引き起こされるという因果連鎖(causal chain)モデルの慣習に従う。 - **アラート修復確率(alert-fixed probability)** `P_f(S, u)`: 集合 `S` を修正した場合に `u` が(カスケード的に)修正される確率。`u ∈ S` なら 1、そうでなければ `S` からの因果パスを辿って再帰的に計算される。 - **Gain(S)**: `S` を修正した場合に得られる期待便益の総和 `Σ_u w_u · P_f(S, u)`。 - **CAM の定義**: アラートグラフ `G` と整数 `k` が与えられたとき、`Gain(S)` を最大化する `k` 個の重要アラート集合 `S ⊂ V` を求める問題。 **Theorem 1**: CAM は NP 完全である(最大被覆問題からの帰着で証明)。 ## 提案手法 論文は、オフラインの依存規則マイニング → オンラインのアラートグラフ維持 → オンデマンドの重要アラートマイニング、という 3 段のパイプライン(図1(Figure 1))を提示したうえで、オンデマンド段の 4 種類のアルゴリズムを提案する。 ![[fig01-pipeline.png]] 1. **Naive(貪欲法)**: `Gain` が単調劣モジュラ関数(monotonically submodular function)であることを利用し、各反復で増分利得(incremental gain)が最大のアラートを選ぶ。近似比 `1 - 1/e` を保証するが、`O(k|V||E|)` 時間かかり大規模グラフでは非実用的(2万頂点・20万辺規模で 6 個の重要アラートに 800 秒超)。 2. **BnP(Bound-and-Prune)**: 各反復で候補アラートの上界(SGain)と下界(LGain)を、それぞれ上界・下界の構造を図示した図2(Figure 2)のとおり計算する。SGain は `O(|E|)` 時間で全頂点分を計算可能、LGain は局所 `h` ホップ以内の情報のみで計算する。下界の最大値を `bar` として上界が `bar` を下回るアラートを枝刈りする手続き `Prune`(図3(Figure 3))を導入する。近似比 `1 - 1/e` を保ったまま、Naive に対して最大 30 倍・簡易版 BnPUB に対して最大 17 倍高速化する。`h = 3` で 95% のアラートが枝刈りされ、質を落とさず 30 倍速くなる。 ![[fig02-bnp-bounds.png]] ![[fig03-prune-procedure.png]] 3. **ST(Single-tree approximation)**: アラートグラフから最大有向木(maximum directed tree)`T` を誘導し(各アラートについて最大の `f_e` を持つ入辺だけを残す)、`T` 上で BnP を実行する。木の上では `O(k|V|)` 時間で `1 - 1/e` 近似が可能(Theorem 2(2))。全体で `O(|E| + k|V|)` 時間。木への単純化がバイアスを持ち込む代償として、Naive比で最大 5,000 倍、BnPUB比で最大 3,000 倍高速。 4. **MTS(Multi-tree sampling)**: ST の単一木近似によるバイアスを緩和するため、複数の木をサンプリングして利得推定を平均する(図4(Figure 4))。各反復でアラート修復確率を更新し、`N` 本の木をサンプリングして各アラートの子孫の重み付き和の平均を利得推定として用いる。合計 `O(k·N·|E|)` 時間。実験では 300 サンプルで Naive の 90% の Gain 品質を保ちながら 80 倍高速。 ![[fig04-mts-algorithm.png]] ## 新規性 - 既存の因果マイニング研究([3, 31, 32] 等)がアラート間の因果関係の**発見**で止まっていたのに対し、本論文は発見済みの因果関係(依存規則)を前提として「どのアラートを直せば波及的に最も多くのアラートが解消するか」という**下流の意思決定問題**を初めて計算問題として定式化し、NP 完全性を示した。 - 劣モジュラ関数の貪欲近似という影響最大化(influence maximization)分野の道具立てを、アラート/ネットワーク運用ドメインの因果グラフに適用し、`1 - 1/e` の近似比を保証しながら上下界による枝刈り・木サンプリングという 2 段階のスケーラビリティ改善を組み合わせた。 - ドメイン知識やリッチな意味情報(セマンティクス)を仮定せず、依存規則の確率構造のみからアルゴリズムが動作する汎用フレームワークとして設計されている。 ## 実験設定 - **実データ(LM)**: [[LogicMonitor]] 提供のデータセンター性能データ。122 台のサーバ上の 9,956 サービスにおける 50,772 個のパフォーマンスメトリクスの系列、2013-11-23〜2014-01-14 の 53 日分(各メトリクスは 2 分ごとに報告)。7 日分のデータから依存規則を学習し(Granger 因果性、[31] のツールを p 値 0.01 で使用、[20] で条件付き確率により不確実性を推定)、翌日以降のデータから 46 個のアラートグラフを構築(頂点数 20,248〜25,057、辺数 162,000〜270,370)。 - **合成データ(SYN)**: [18] のランダム有向非巡回グラフモデルを用い、LM から学習した次数・辺重みの経験分布に従って生成。アラート数を 10 万〜100 万の範囲でスケール(平均次数 9)。 - **評価指標**: 損失率(loss ratio)`1 - Gain(S_A)/Gain(S_Naive)`(小さいほど良い)。 - **比較対象**: Naive、BnPUB(上界のみを使う簡易版 BnP)、MaxDeg(出次数の重み付き和が大きい上位 k 個を返す単純戦略)。 - 実装は C++、Intel Core i7-2620M 2.7GHz・8GB RAM・Ubuntu 12.10・GCC 4.7.2 上で、各実験を 10 回実行した平均を報告。 ## 実験結果 - **ケーススタディ(図5(Figure 5))**: LM データ上で、StorageUsed(メモリ不足を示す)が Apache の性能劣化を経て Ping-avgrtt の遅延を引き起こす、また共有メモリ不足が SDA writetime の遅延を引き起こす、という因果パターンをドメインエキスパートが妥当と検証。もう一つの重要アラート DiskReadLatency は I/O ボトルネックを示し、データベースアプリケーションの異常状態や CPU・データベースサーバの性能劣化を波及的に引き起こすパターンが観測された。 ![[fig05-lm-causality-patterns.png]] - **全体性能(図6(Figure 6))**: BnP・MTS・ST は k=1〜6 の全域で Naive・BnPUB より一貫して高速。BnP は質を落とさず Naive比 30 倍・BnPUB比 17 倍高速。ST は Naive比 5,000 倍・BnPUB比 3,000 倍高速(損失率は約 0.2)、MTS は 80 倍・50 倍高速(損失率は約 0.1)。MaxDeg の損失率は k が増えても常に 0.4 超で、提案ヒューリスティクスが明確に上回る。 ![[fig06-mining-performance.png]] - **BnP の探索ホップ数の影響(図7(Figure 7))**: 探索ホップ数 h を 1→3 に増やすと枝刈り率が上がり応答時間が減少するが、h=3→5 では下界計算のコスト増が支配的になり応答時間が増加する。LM データでは h=3 が最良のトレードオフ。 ![[fig07-bnp-performance.png]] - **MTS のサンプル数の影響(図8(Figure 8))**: サンプル木の数 N を 5→100 に増やすと損失率が大きく改善するが、100→500 では改善は限定的。応答時間はサンプル数・要求する重要アラート数の双方に線形。全ケースで 15 秒以内に完了。 ![[fig08-mts-performance.png]] - **スケーラビリティ(図9(Figure 9))**: SYN グラフでアラート数を 10 万〜100 万にスケールしても MTS・ST の応答時間は線形に増加。100 万アラート・9,000 万超の辺を持つグラフでも MTS は 4 分、ST は 13 秒で 3 個の重要アラートを返す。一方 Naive・BnPUB・BnP は 10 万アラート規模でも 1 時間以内に完了しない。 ![[fig09-scalability.png]] ## 考察 著者らは、本研究がデータセンター・侵入検知・ネットワーク診断における大規模重要アラート分析への「第一歩」であると位置づけ、今後の方向性として (1) 分散ネットワーク監視システムへの拡張、(2) アラートグラフと重要アラートの動的維持、(3) 外部の意味情報・知識ベースとの統合による重要アラートの自動解釈、を挙げている。関連研究としては、Granger 因果性・ラグ相関・ベイジアンネットワークによる因果モデリング([3, 31, 32, 29] 等)、侵入検知における根本原因分析(アラートクラスタリング [16]、ルールベースの相関 [17])、ネットワーク性能診断における根本原因特定([23])、影響最大化(influence maximization)分野の劣モジュラ最適化・サンプリング手法([6-9, 11, 13, 14, 19, 21, 22, 28, 30, 36] 等)との違いを整理している。特に影響最大化との対比では、本問題は既知の因果グラフ上での劣モジュラ最適化という共通の道具立てを持ちながら、対象がソーシャルネットワークの拡散ではなくアラートの因果カスケードである点が異なる。 ## 強み / 弱点・課題 - 強み: CAM を NP 完全な最適化問題として定式化したうえで、理論保証(近似比 `1 - 1/e`)を持つ厳密な近似アルゴリズムと、実用的なヒューリスティクスの両方を提示し、実データと合成データの両方でスケーラビリティを裏付けている点。 - 弱点・課題(論文内で明示された限界): (1) 依存規則(因果関係)の学習自体は前提としており、Granger 因果性などの既存手法の精度に依存する。(2) アラートグラフは「1 つのアラートは高々 1 つの先行アラートに引き起こされる」という因果連鎖の慣習を仮定しており、複数原因の合流を直接モデル化していない。(3) 木サンプリング系ヒューリスティクス(ST・MTS)は木構造への単純化に伴うバイアスを内在し、損失率 0.1〜0.2 程度の質の劣化を伴う。(4) アラートグラフの動的維持(オンライン更新)や外部知識ベースとの統合による自動解釈は将来課題として残されている。