@1995__IM__A Coding Approach to Event Correlation

# A Coding Approach to Event Correlation > [!abstract] 概要(abstract の日本語訳) > 本論文は、符号化技術に基づくネットワークにおけるイベント相関への新しい取り組みを述べる。観測可能な症状イベントは、それを引き起こした問題を識別する符号(コード)とみなされ、相関は観測された症状の集合を復号することによって行われる。符号化アプローチはSMARTS Event Management System(SEMS)、すなわちSun Solaris 2.3上で動作するサーバーとして実装された。SEMSの予備的なベンチマークは、符号化アプローチが他の既発表の相関システムに対して少なくとも2桁の高速化を提供することを示す。加えて、症状の高い欠落率および誤警報率に対して頑健である。最後に、符号化アプローチは数千の問題を含む非常に大規模な領域にもうまくスケールする。 ## 論文情報 - タイトル: *A Coding Approach to Event Correlation* - 著者: S. Kliger・S. Yemini([[System Management Arts]](SMARTS)、White Plains, NY)、Y. Yemini・D. Ohsie・S. Stolfo([[Columbia University]] Computer Science Department) - 掲載: *Integrated Network Management IV*(A. S. Sethi et al. 編)、Springer Science+Business Media Dordrecht、1995年、pp. 266-277。第4回 IFIP/IEEE 統合ネットワーク管理国際シンポジウム(ISINM/IM'95)の会議録論文。 - 原本: `.raw/papers/A-Coding-Approach-to-Event-Correlation.pdf`(12ページ、OCRスキャン) ## 概要本論文は、ネットワーク管理におけるアラーム(イベント)相関の問題を、符号理論(コーディング理論)の枠組みで再定式化する。因果グラフに因果尤度を付与した相関モデルから、各「問題」を、それが引き起こす各「症状」への尤度を並べたベクトル(=符号)として導出する。観測されたアラームの集合(=アラームベクトル)を、どの問題の符号に最も一致するかを判定する「復号(decoding)」問題として相関を捉え直す点が中核のアイデアである。手法はコードブック選択(オフラインの前処理段階で監視対象の症状を最小限に絞り込む)と復号(オンラインでアラームベクトルを最近傍の符号に照合する)の二段階からなり、複雑な探索計算をオフライン側に押し込めることでリアルタイム相関を高速化する。SMARTS Event Management System(SEMS)として商用実装され、衛星通信網を模したモデル(約9500問題・6000症状)でのベンチマークにより、当時発表されていた他の相関システム(ECXpert、IMPACT)に対して2〜4桁の速度向上を確認したと報告する。 ## 問題設定 **Figure 1: 一般的なイベント相関システムのアーキテクチャ** ![[_attachments/A-Coding-Approach-to-Event-Correlation/image-002-001.png]] (Figure 1. Configuration Model と Monitors がそれぞれ Event Model と Correlator へ入力し、Monitors はネットワーク要素からアラームを収集して Correlator へ渡す。Correlator は Event Model の知識を用いてアラームから problems を出力する構成。) 従来のアラーム相関システムは、イベントモデルという知識ベースに対する探索によって相関を行うため(Figure 1)、探索の複雑さがスケーラビリティを著しく制限する。探索複雑度を抑えるために特定ドメインの特性を前提としたモデル設計に頼ることが多く、これは汎用性を損なう。さらに、監視すべき最適な症状集合を選ぶ体系的な手法や、観測された症状が問題を決定するのに十分な情報を持つかを判定する手法が存在しない。加えて、アラーム相関システムは入力のノイズに対して頑健でなければならない。ノイズには、症状の欠落や誤警報という観測ノイズと、イベントモデル自体がネットワークの実態と食い違う(設定情報の不備・誤りに起因する)モデルノイズの二種類がある。本論文は、汎用性・スケーラビリティ・ノイズ耐性という3つの目標を同時に満たすアラーム相関手法の設計を課題とする。 ## 提案手法因果関係は、事象をノード、因果関係を有向辺とする因果グラフで表現される(Figure 2)。 **Figure 2: 因果グラフ(a)とそのラベル付け(b)** ![[_attachments/A-Coding-Approach-to-Event-Correlation/image-003-001.png]] (Figure 2. (a) 11個の事象からなる因果グラフの例。(b) 同じグラフのノードを問題(P)・症状(S)として分類したもの。両方に分類されるノードや、いずれにも分類されないノード(事象8)が存在する。) 各辺には、因果の強さ(尤度)を表すラベルが付与される。この尤度のラベル体系を、順序 ≤ と2つの演算(連結 *、結合 +)を持つ**半環(semi-ring)**として一般化し、決定論的モデル D({0,1}、論理積/論理和)・確率モデル P([0,1]、積/確率的OR)・時間モデル T(非負実数、加算/min演算)という複数の尤度モデルを同一の代数構造の特殊ケースとして統一的に扱う(PxTのような合成モデルも構成できる)。因果グラフは、循環(因果的に等価な事象群)の集約や、他の症状のみによって引き起こされ独自の情報を持たない間接症状の除去によって整理され、正規形の「相関グラフ」(問題と症状のみからなる二部グラフ、Figure 3)へと変換される。 **Figure 3: 相関グラフ** ![[_attachments/A-Coding-Approach-to-Event-Correlation/image-005-001.png]] (Figure 3. 問題1・11・2から症状9・3・6への因果関係を表す二部グラフ。問題1と11はいずれも症状9と3を引き起こし、問題2は症状3と6を引き起こす構造。) 各問題pについて、相関グラフ上でpから各症状への尤度を並べたベクトルをpの**符号(コード)**と呼ぶ。観測されたアラームの集合もまた、観測された症状に1、それ以外に0を割り当てたアラームベクトルとして同じ症状空間に埋め込まれる。相関問題は、与えられたアラームベクトルに最もよく一致する問題の符号を見つける**復号**問題として定式化される。Figure 4は、この符号の考え方を決定論的モデルと確率的モデルそれぞれで具体的に例示する。 **Figure 4: 相関尤度モデル** ![[_attachments/A-Coding-Approach-to-Event-Correlation/image-006-001.png]] (Figure 4. (a) 決定論的モデルでは、症状3・6・9に対する問題1・11の符号がいずれも(1,0,1)で一致し区別不能になる。(b) 確率的モデルでは同じ問題対の符号が(0.8,0,0.3)と(0.5,0,0.9)となり区別可能になることを示す。) 符号間の区別能力は、決定論的モデルにおけるハミング距離を一般化した距離測度d(a,b)(半環L上で対称・非負・三角不等式を満たす関数)によって測られ、**コードブックの半径**(コード間の最小距離の半分)が定義される。半径が大きいほど、より多くの症状の欠落・誤警報を検出・訂正できる(半径rであればr-1個までの誤りを訂正し、2(r-1)個までを検出できる)。Figure 5は、6問題・20症状の例において、コードブックのサイズと半径のトレードオフを具体的に示す。 **Figure 5: 決定論的な相関行列とコードブック** ![[_attachments/A-Coding-Approach-to-Event-Correlation/fig05-correlation-matrix-codebooks.png]] (Figure 5. (a) 6問題×20症状の相関行列全体。(b) 症状{1,2,4}からなる半径0.5のコードブック(区別はできるがノイズ耐性がない)。(c) 症状{1,3,4,6,9,18}からなる半径1.5のコードブック(単一症状の誤りを訂正、2症状の誤りを検出できる)。) コードブック(監視対象とする症状の最小部分集合)は、要求される半径を満たしつつ症状数を最小化するように、プルーニングアルゴリズムなどで選択される。復号には、症状の欠落と誤警報を非対称に扱う相関測度μ(1,a)/μ(0,a)を用いる。復号の計算量は、直接復号可能なアラームベクトル数に対して対数的であり(問題数p・コードブックサイズc・訂正すべき誤り症状数kに対しΛ(p,c,k)=lg[(p+1)Σ_{i=0}^{k}C(c,i)]、k≪pのとき近似的に(k+1)lg p)、知識ベース探索型手法の指数的・二重指数的な複雑度と対比される。 ## 新規性 - アラーム相関を、決定論的モデルに限らず任意の因果尤度半環に一般化できる符号化・復号問題として再定式化した点。 - コードブック選択(オフライン)と復号(オンライン)の二段階設計により、組合せ的な探索計算を前処理側に押し込め、リアルタイム相関の計算量を対数オーダーに抑えた点。 - ハミング距離を半環上の任意の距離測度へ一般化し、コードブックの半径という単一の指標で、観測ノイズとモデルノイズの双方への頑健性を定量的に保証する設計原理を与えた点。 - 商用システム(SEMS)として実装し、当時公表されていた他システム(ECXpert、IMPACT)との定量的なベンチマーク比較を提示した点。 ## 実験設定衛星通信網をモデル化した約4000の管理対象オブジェクト・約9500問題・約6000症状からなるドメインを用いてSEMSをベンチマークした。実験シナリオは、9500問題からランダムに一部(例: 100問題)を選び、選ばれた問題に無関係な症状を除外し、残った症状からコードブックを選択するという手順で生成された。このモデルは、監視される症状数が問題数より少ない「計装不足」の系と、1問題あたりが引き起こす症状数が少ない「疎な伝播」の系という、コーディングアプローチにとって不利な(実運用より保守的な)2つの仮定を置いている。SEMSはSun SparcstationのSolaris 2.3上で稼働するサーバーとして実装された。 ## 実験結果 **Figure 6: (a) 症状処理速度 (b) 標準偏差付きの症状処理時間** ![[_attachments/A-Coding-Approach-to-Event-Correlation/fig06-symptom-processing-rate-time.png]] (Figure 6. (a) ドメインサイズ(問題数)に対する症状処理速度(症状/秒)。問題数が小さいほど高速(最大約8500症状/秒)で、ドメインサイズの増加とともに単調に低下し7000問題規模で数百症状/秒程度になる。(b) 症状1件あたりの処理時間(標準偏差の区間つき)。ドメインサイズ200〜2000の範囲でおよそ0.001〜0.0013秒とほぼ安定している。) 図6(a)はECXpert(0.25イベント/秒)やIMPACT(15症状/秒)の公表値に対して2〜4桁高速であることを示す。図6(b)は平均速度の見積もりが実際の相関速度をよく近似することを示す。 **Figure 7: (a) 相関誤り率 (b) コードブック圧縮率** ![[_attachments/A-Coding-Approach-to-Event-Correlation/fig07-error-rate-compression.png]] (Figure 7. (a) 症状損失率(0〜20%)に対する相関誤り率を、コードブック半径0.5〜3.0の各水準で測定。半径0.5では損失率20%で誤り率が約20%まで悪化するのに対し、半径1.5以上では損失率20%でも誤り率5%未満に抑えられる。(b) ドメインサイズに対する圧縮率(監視対象となる全症状数とコードブックサイズの比)。小規模ドメインで約8.5倍、7000問題規模でも約2倍の圧縮を達成する。) ## 考察著者らは、符号化アプローチが導入部で掲げた汎用性・スケーラビリティ・ノイズ耐性の3目標を達成したと総括する。汎用性は因果尤度の抽象的な数学的定式化(半環)によって、スケーラビリティは症状集合の最適化と高速な復号機構によるリアルタイム処理の大幅な削減によって、ノイズ耐性は要求水準のノイズ非感度を保証するようコードブックの症状を選択することによって、それぞれ達成されるとする。精緻な計算量評価は本論文の範囲を超えるとして将来の論文に委ねられ、ベンチマークの詳細も別の技術レポート(Kliger et al. 1994b)に譲られている。また、ベンチマークに用いたモデルは計装不足・疎な伝播という保守的な仮定を置いているため、実運用系(典型的には過剰計装で伝播も複雑)ではより小さなコードブックとより高速な相関が期待できると述べる。 ## 強み / 弱点・課題 - 強み: 決定論的・確率的・時間的モデルを統一的に扱える半環による数学的一般化と、それを実際の商用システム(SEMS/SMARTS)に実装し定量ベンチマークで裏付けた点が明快である。ノイズ耐性をコードブック半径という単一の定量指標に還元し、場当たり的なヒューリスティクスに頼らない設計原理を提供している。 - 弱点・課題(本文に明記された限界): 精緻な計算量評価は「本論文の範囲を超え、将来の論文に委ねる」と明記されており、本論文単独では完結していない。ベンチマークの詳細な手続きも別の社内技術レポート(Kliger et al. 1994b)に依存しており、本論文単独では再現性の検証ができない。コードブック選択自体を行う「プルーニングアルゴリズム」は概略のみが述べられ、その計算量や最適性についての解析は与えられていない。モデルノイズ(イベントモデル自体の誤り)への対処は、相関ログの事後分析による検出・修正に留まり、復号処理そのものに組み込まれた原理的な扱いではない。