> [!abstract] 概要（abstract 和訳） > ネットワークログメッセージ（例: syslog）は、大規模ネットワークにおける予期しない異常挙動を検知するための価値ある有用な情報源として期待されている。しかし、日常運用で収集される膨大なシステムログデータのために、ピンポイントのシステム障害を抽出したり、その原因を特定したりすることは容易ではない。本論文では、ネットワーク syslog データから障害とその原因を抽出する手法を提案する。提案手法は、イベントの時系列集合からネットワークイベントの因果関係を再構成する因果推論に基づく。因果推論は偶発的に相関するイベントを除去できるため、従来の相互相関ベース手法より妥当な因果イベントを出力する。本手法を日本の全国学術ネットワークから取得した 15 ヶ月分のネットワーク syslog データに適用した。提案手法は従来手法と比較して疑似相関イベント数を大幅に削減する。また、3 つのケーススタディとトラブルチケットデータとの比較を通じて、実際のネットワーク運用に対する提案手法の有効性を実証する。 ## 論文情報 - **タイトル**: Mining Causality of Network Events in Log Data - **著者**: Satoru Kobayashi（東京大学）・Kazuki Otomo（東京大学）・Kensuke Fukuda（国立情報学研究所 / SOKENDAI）・Hiroshi Esaki（東京大学） - **掲載誌**: IEEE Transactions on Network and Service Management（TNSM）、Vol. 15、No. 1、March 2018、pp. 53–67 - **DOI**: 10.1109/TNSM.2017.2778096 - **受付/採録/掲載**: 2017-05-15 受付 / 2017-11-04 採録 / 2017-11-28 早期公開 / 2018-03-09 現行版 - **コード**: https://github.com/cpflat/LogCausalAnalysis（[[LogCausalAnalysis]]） - **注記**: IEEE IM 2017 会議論文 [1] の拡張版 ## 概要 大規模ネットワークの syslog から、PC アルゴリズム（Spirtes & Glymour の制約ベース因果探索）を用いてネットワークイベントの因果関係を有向非巡回グラフ（DAG）として抽出する手法を提案する。対象は日本の全国研究教育ネットワーク [[SINET4]]（コアルータ 8・エッジルータ 50・L2 スイッチ 100 から構成）の 456 日分・3,500 万件の syslog。ログテンプレート生成 → 周期イベント除去 → PC アルゴリズム（G-square 検定）→ 頻出エッジ後処理の 4 段パイプラインにより、トラブルチケットの 74% に対応する有用な因果エッジを実用的なネットワーク運用粒度で抽出する。 ## 問題設定 - **入力**: 異機種ネットワーク機器（ルータ・スイッチ）が生成する大量の syslog（syslog プロトコル RFC 5244 準拠） - **出力**: ネットワーク障害イベント間の因果関係を表す DAG、ネットワーク演算子が読める規模（〜5 エッジ/日）に絞り込まれたもの - **課題 3 つ**: ① 多ベンダー機器が多種ログを出力する、② メッセージが離散的・スパース（連続パラメータ前提の従来手法が効かない）、③ すべての検出因果関係が運用上重要なわけではない - **前提条件**: syslog の timestamp は NTP 同期誤差や障害時の信頼性低下のため因果方向決定に使えない → 条件付き独立性のみに基づく因果方向推定が必要 ## 提案手法 ### アーキテクチャ（4 段パイプライン） ``` syslog → [前処理] → PC アルゴリズム（G-square）→ [後処理] → 因果 DAG（演算子向け） ↓ ↓ テンプレート生成 頻出エッジ除去 + 周期フィルタ ``` ### 前処理 1: ログテンプレート生成 生ログのタイムスタンプとソースホスト名を除き、変数（IP アドレス・ポート・プロセス ID 等）をワイルドカード `*` に置換した**ログテンプレート**（標準書式）を生成する。教師あり NLP ベースのテンプレート生成アルゴリズム [35]（マイナーログを正確に分類できない教師なしクラスタリング系より高精度）を使用し、35M 件から **1,789 テンプレート**を生成。テンプレートごとの出現数を非重複タイムビン（サイズ $b$）に集計した**イベント時系列**を PC アルゴリズムの入力とする（機器 × テンプレートを 1 ノードとして扱う）。 ### 前処理 2: 周期イベントフィルタ 定期実行（cron・NTP 同期等）の周期的ログはランダムな障害と相関なく大量に現れ、PC アルゴリズムの偽陽性エッジを増やす。周期性を持つ時系列を除去しつつ、周期的イベント中の**アウトライヤ（重要な例外）を残す**2 段フィルタ: 1. **フーリエ解析**: パワースペクトルに等間隔ピークがあれば周期的と判定（閾値 $th_p=0.1$）。逆フーリエ変換で残差成分 $h(t)$ を取り出しアウトライヤのみ残す（閾値 $th_a=0.4$）。 2. **線形回帰解析**: 累積時系列が線形増加する準周期イベント（短/不等間隔）を補完的に検出（閾値 $th_l=0.5$）。 結果として全メッセージの **7%** のみが PC アルゴリズムの入力となる（System/Service/Network/Management/Monitor の各グループが大幅に削減；Interface/VPN/Routing はほぼ保持）。エッジは前処理で **70〜90% 削減**される。 ### PC アルゴリズム（stable-PC + G-square） 条件付き独立性に基づいてノード（イベント時系列）間の因果関係を DAG として推定する制約ベース因果探索アルゴリズム。4 ステップ: 1. 全連結無向グラフを構築 2. 条件付き独立のエッジを削除（骨格推定） 3. V-structure（V 字構造）でエッジ方向を決定（U → V ← W かつ U-W 間に直接エッジなし） 4. 向き付け規則（DAG の定義によるループ防止） 本論文では order-independent な **stable-PC** 変種 [29] を採用。 **条件付き独立性検定の選択**（重要な設計選択）: | 検定 | 入力 | 特性 | 結論 | |---|---|---|---| | G-square | 二値時系列（$x(t) \geq 1 \to 1$）| 高速・疎データで誤棄却少 | **採用** | | Fisher-Z | 連続時系列 | エッジ多・7% タイムアウト・三角形エッジ多（冗長）| 不採用 | G-square 統計量: $G^2 = \sum_{ijk} 2S_{ijk}\log\frac{S_k S_{ijk}}{S_{ik}S_{jk}}$、有意水準 $p=0.01$。 Fisher-Z は正規分布を仮定するため、スパースな syslog イベントではこの前提が崩れ偽陽性が増加する（クラスタリング係数で評価: Fisher-Z の係数は 1.0 に近い = 三角エッジ多 = 偽陽性）。G-square はクラスタリング係数が小さく（最大でも三角形程度）、最大クリーク規模も小さい（Fisher-Z: 5 以上も発生）。 **ビンサイズパラメータ**: $b=60\text{s}$、重複 $50\text{s}$（非重複 $60\text{s}$ のエッジより多くのエッジを検出しつつ処理可能）。ウィンドウサイズは 1 日長が適切（固有エッジ数はウィンドウサイズによらずほぼ一定）。 **偽陽性率の実験**: Poisson 過程に従うランダムイベント（独立）への適用で、偽陽性比率は 10 イベントで 1.1%、100 で 0.4%、1,000 で 0.06% と低水準。 ### 後処理: 頻出エッジ除去 PC アルゴリズムは因果関係を出力するが重要度を付与しない。同一エッジが複数の DAG（異なる日付）に繰り返し出現する場合、そのエッジは「通常挙動」を表し演算子の注目を分散させる。 エッジの出現頻度を集計し、**上位 5% の頻出エッジを除去**（全 16,196 エッジのうち上位 42 種が全出現の 85% を占める）。残り 2,438 エッジ（5.3 エッジ/日）が演算子向け出力。後処理所要時間: 20 秒（全データセット）。除去後は Monitor（SNMP）関連エッジが相対的に増加する（予期しない機器挙動と同時に出現するため有意）。 ## 新規性 | 先行手法の課題 | 本論文の解決 | |---|---| | 相関ベース手法（クロス相関）: 偽陽性が多い | 条件付き独立性による因果方向推定（PC アルゴリズム）で偽陽性を削減 | | Zheng+ 2012 の HPC 向け手法: 条件付き独立を発見的に探索し一部の因果のみ検出 | 全因果関係を調査し DAG として体系化（演算子のシステム理解を支援） | | 従来の周期フィルタ（自己相関係数+ラグ）: 固定周期候補が必要・アウトライヤも除去・非固定間隔に非対応 | フーリエ + 線形回帰の 2 段で固定間隔/非固定間隔の周期イベントを除去しアウトライヤを保持 | | Fisher-Z 検定: スパース時系列では偽陽性が増加・7% タイムアウト | G-square 検定: 二値データに適合・低偽陽性・高速 | ## 実験設定 - **環境**: Ubuntu 16.04、Intel Xeon X5675（3.07GHz）、48GB メモリ - **データセット**: [[SINET4]]（日本全国研究教育ネットワーク、800 以上の学術機関） - コアルータ 8、エッジルータ 50、L2 スイッチ 100（複数ベンダー） - 2012〜2013 年、456 日間の連続 syslog、35M 件 - 8 サブネット（コアルータ 1 + 付属のエッジ/スイッチ）に分割し各 1 日分を入力 - 計 3,648 DAG を生成 - トラブルチケット: 227 件/年（スパーシャル/テンポラル情報付き、大規模イベントのみ） - **ログテンプレート分類**: System / Network / Interface / Service / Management / Monitor の 6 群 + VPN / Routing 等の外部グループ - **比較対象**: Fisher-Z（PC アルゴリズム別検定）/ 条件付き独立なし（相関のみ） ## 実験結果 ### 前処理効果（Table I） - System グループ: cron 周期イベントが大部分を占め、前処理でほぼ除去 - Service グループ: NTP 同期メッセージを除去 - Interface/VPN/Routing: 状態変化イベントのため周期性なし → ほぼ保持 - 合計: 元メッセージの **7% のみが PC アルゴリズム入力**。エッジは 70〜90% 削減（Figure 6） ### G-square vs Fisher-Z（Table II、Figure 7〜9） - Fisher-Z は G-square より多数のエッジを検出するが、人手確認では余分なエッジが多く troubleshoot 有用性は低い - クラスタリング係数: Fisher-Z ≈ 1.0（完全グラフに近い）vs G-square（低い） - 最大クリークサイズ: Fisher-Z は 5 以上を多発 vs G-square は三角形以下 - Fisher-Z のタイムアウト: 7%（253/3,648 データセット）、処理複雑度に依存（DAG が複雑な障害時に特に遅延） - **結論: G-square が syslog 解析に適切**（疎な時系列には正規分布前提の Fisher-Z が合わない） ### ビンサイズ依存性（Table III） - 大ビンは cross entropy 値が下がりエッジ削減（直感に反するが情報ゲインの低下が原因） - 重複 50s が境界問題を解消しエッジ数を増加させる - 推奨: $b=60\text{s}$、重複 $50\text{s}$ ### ウィンドウサイズ依存性（Table IV） - 固有エッジ数はウィンドウサイズに大きく依存しない → 1 日ウィンドウが妥当 ### 偽陽性分析（Figure 11） - Poisson ランダムイベントへの適用: 偽陽性比率 ≤ 1.1% ### ケーススタディ（3 件） 1. **ログイン失敗（Case 1）**: BGP 接続初期化 → インタフェースエラー → ログイン失敗の因果チェーンを G-square で正確に検出。Fisher-Z は多角形エッジで複雑化 2. **ハードウェアモジュールアラート（Case 2）**: BGP 初期化 → UI 子プロセス異常終了 → ハードウェアモジュール起動の 3 エッジを検出（方向の一部に誤りあり）。Fisher-Z は 70 ノード・270 エッジの複雑な DAG（実用不可） 3. **BGP 状態初期化（Case 3）**: インタフェースエラー → BGP ピアリング断続接続の 2 機器にまたがる複雑障害を検出。G-square は ground truth に近い結果、Fisher-Z は間接因果を示す余分なエッジを含む ### トラブルチケット比較（Table VII） - 188 件の有効チケット（ログあり）のうち **74% に関連エッジを検出** - Routing（BGP 等）・VPN（MPLS 等）で高い検出率（複数デバイスにまたがる多段ログがあるため） - System（ハードウェア）では低い検出率（1〜2 回しか出現しないため統計的因果推定が困難） ## 考察 - **因果方向の不確実性**: PC アルゴリズムは V-structure と向き付け規則のみで方向を決定するため、一部エッジは無向のまま残る。timestamp を補助的に利用（異機種間は通信遅延・時刻同期を考慮して慎重に）する余地がある - **リアルタイム処理の制限**: 平均 50 秒の DAG 生成処理だが、障害発生時は 600 秒超になることがある。障害箇所特定技術との組み合わせが必要 - **G-square は疎データに特化**: アクセスログ等の十分大きなデータでは Fisher-Z が適切に機能する可能性（スパースデータとの対比） - **後処理の単純さ**: 現在の頻出エッジ除去は単純なヒューリスティック。因果推論と異常検知を組み合わせた高度な後処理への発展を予定（著者の将来課題） ## 強み / 弱点・課題 **強み**: - ネットワーク syslog という非常にスパースなデータへの因果推論適用として先駆的 - フーリエ + 線形回帰の組み合わせが互いの欠点を補完する - G-square vs Fisher-Z の定量比較が明確（疎データでは G-square が支配的） - SINET4 という実運用環境での 15 ヶ月長期評価 - 74% のトラブルチケット関連エッジ検出という実用的評価基準 - オープンソース [[LogCausalAnalysis]]（https://github.com/cpflat/LogCausalAnalysis） **弱点・課題**: - 因果方向の一部が不確定（undirected エッジが残る） - System グループ（ハードウェア障害）のような単一出現イベントは統計的因果推定に不向き - 非 Poisson（準周期・線形増加）イベントは前処理後も偽陽性が残りうる - リアルタイム応用には処理時間が問題（障害時に 600 秒超） - 評価が SINET4 のみで他ネットワークへの汎化は未検証（SINET5 への適用が著者の将来課題） ## 関連 - **概念**: [[ログ解析]] / [[因果推論ベースRCA]] / [[根本原因分析]] / [[Fault Localization]] / [[ログパース]] / [[AIOps]] / [[NetOps]] - **著者**: [[Satoru Kobayashi]] / [[Kazuki Otomo]] / [[Kensuke Fukuda]] / [[Hiroshi Esaki]] - **機関**: [[University of Tokyo]] / [[National Institute of Informatics]] - **データ**: [[SINET4]] - **コード**: [[LogCausalAnalysis]] - **関連 MOC**: [[structures/000 Index]] ## 出典 - PDF: `.raw/papers/2018TNSM-Mining-Causality-of-Network-Events-in-Log-Data.pdf` - §III: PC アルゴリズムの 4 ステップと条件付き独立性の定義 - §IV-B: 前処理（テンプレート生成・周期フィルタ）の詳細 - §IV-C: G-square / Fisher-Z の定義式と比較 - §IV-D: 後処理（頻出エッジ除去） - §V: SINET4 データセット詳細、ログテンプレート分類（Table I） - §VI: 前処理効果（Figure 5-6）・G-square vs Fisher-Z（Figure 7-9, Table II）・ビン/ウィンドウサイズ（Table III-IV）・偽陽性（Figure 11） - §VII: 検出エッジ分類（Table V-VI）・後処理効果（Figure 12）・ケーススタディ（Figure 13-18）・トラブルチケット比較（Table VII）