> [!abstract] 概要(abstract の日本語訳) > ネットワークサービス間の依存性検知は従来研究で盛んに扱われてきた。依存性検知の試みは能動的アプローチと受動的アプローチの二種類に分類される。受動的アプローチは偽陽性が多く、能動的アプローチは適用可能性の問題を抱える。本論文では、サービス間の依存性を検知するための、新しいアプリケーション非依存の能動的アプローチを設計する。任意に低い偽陽性と容易な適用可能性を持つトラフィックウォーターマーキング手法を提案する。ウォーターマークされたフローを検知するための統計的検定を提供し、これらの検定の偽陽性率と偽陰性率を解析的かつ実験的に算出する。さらに、提案するウォーターマーキングシステム(Rippler)を小規模の大学実験室ネットワークに実装した。システムを 4 ヶ月間運用し、54 サービス間で 38 の依存性を検出した。最後に、この実世界ネットワークデータを用いて 3 つの先行システムとの効率を比較した。 ## 論文情報 - **タイトル**: Rippler: Delay Injection for Service Dependency Detection - **著者・所属**: Ali Zand・Giovanni Vigna・Richard Kemmerer・Christopher Kruegel(UC Santa Barbara) - **媒体**: IEEE INFOCOM 2014(IEEE Conference on Computer Communications) - **発表年**: 2014 - **IEEE DOI**: https://ieeexplore.ieee.org/document/6848158 - **PDF**: `zand, vigna, kemm, [email protected]` ## 概要 Rippler はネットワークサービス間の依存性を、トラフィックに対する選択的遅延注入(delay injection)によって能動的に検出するシステムである。受動的手法が「相関は因果でない」問題から偽陽性を大量生成するのに対し、Rippler はリクエスト到達タイミングにウォーターマークパターンを作りその伝播を観測する。応用非依存で偽陽性を任意に低くできることを統計的に証明し、実ネットワーク実験で既存 3 システム(Sherlock・Orion・NSDMiner)を性能面で上回った。 ## 問題設定 - **入力**: ネットワークフローデータ(NetFlow 等。各接続の開始・終了時刻を含む任意の一般的フォーマット) - **出力**: サービス間の依存性グラフ(S2 → S1 の形で「S2 は S1 に依存する」) - **前提条件**: デレイヤー(遅延器)を対象サービスとクライアントの間に配置できること。研究対象サービスの集合を事前に把握していること - **問題の本質**: 受動的観測手法は「相関≠因果」のために偽陽性が多い。能動的手法は従来アプリケーション依存で未知サービスへ適用不能 ### サービス依存性の定義 ネットワークサービスを「ホスト上で動作しソケット(IP, ポート, プロトコル)宛リクエストに応答するプロセス」と定義する。サービス S2 が S1 に依存する条件は「S1 での遅延・劣化・障害が、直接的または間接的に S2 のサービスに障害・妨害・劣化をもたらす」こと。 依存性の分類(Chen et al. [6] の分類を踏襲): - **ローカルリモート依存**: S1 がクライアントに応答するために S2 を呼ぶ(例: ウェブサーバ → MySQL) - **リモートリモート依存**: クライアントが S2 にアクセスするために先に S1 を参照しなければならない(例: クライアント → DNS → ウェブサーバ) ## 提案手法 ### アーキテクチャ Rippler は「デレイヤー」と「NetFlow コレクタ」の 2 コンポーネントで構成される。デレイヤーは対象サービスへの最初のパケットを指定時間窓では遅延させ、別の時間窓では遅延させない。コレクタは全ネットワーク接続の記録(開始・終了時刻)を収集する。 ### アルゴリズム: トラフィックウォーターマーキング 観測期間を等幅(sw 秒)の時間窓 w1, w2, ..., w2n に分割する。奇数番窓(w1, w3, ...)では S1 へのリクエストを td 秒遅延させ、偶数番窓(w2, w4, ...)では遅延させない。 依存関係 S1 → S2 が存在する場合、S1 への遅延が S2 へのリクエスト到達タイミングに「リップル(さざ波)」を生む: - 奇数窓(アイドル窓 ti): S2 へのリクエスト平均が D1 = D(μ0·(1−ρ), σ0·(1−ρ)) に従う - 偶数窓(ビジー窓 tb): S2 へのリクエスト平均が D2 = D(μ0·(1+ρ), σ0·(1+ρ)) に従う ここで ρ は S2 へのリクエストのうち S1 由来のフラクションで、S2 が S1 に依存する場合は ρ > 0。 ### 統計的検定(3 種) 帰無仮説 H0:「ti と tb のリクエスト到達分布は同一(μi = μb)」を棄却することで依存性の存在を示す。 1. **2 標本独立平均 t 検定**: 2 集団の平均が等しいかを検定。外れ値ノイズに敏感 2. **対応のある t 検定(ペア t 検定)**: 隣接する ti と tb の差 D = X^b − X^i を使い、時間帯による負荷変動を吸収。ペアリングで外れ値の影響を軽減 3. **ウィルコクソン符号順位検定**: ペアリング+順位変換により外れ値の影響をさらに小さくするノンパラメトリック検定 3 検定のいずれかが H0 を棄却すれば S2 → S1 の依存性を報告する。中心極限定理から ρ がどんなに小さくても実験時間を長くすれば任意に小さい p 値を達成できることを解析的に証明。 ### 実装 中央集権型デレイヤー(ブリッジ上)とホストベースデレイヤーの 2 バージョンを開発。プロトタイプは 100ms 遅延(NTP 同期クロック誤差 40ms 以下を考慮)。大学実験室ネットワーク実装では設置制約からホストベースを採用し、クロック誤差(最大 40ms)に対応するため遅延を 500ms に増加。 ## 新規性 先行研究との対比は Table II に整理されており、Rippler が初めて以下のすべてを同時に満たすことを主張する: | 特性 | Rippler | 受動的手法(NSDMiner, Orion 等) | 能動的手法(Pinpoint, X-Trace, ADD) | |------|---------|-------------------------------|-------------------------------------| | ローカルリモート + リモートリモート両対応 | Y | 一部のみ | Y | | センサ配置問題への対応 | Y | N | Y | | ホスト変更不要 | Y | Y | N | | 追加トラフィック不要 | Y | Y | N | | アプリケーション非依存 | Y | Y | N | | 相関≠因果の混同なし | **Y** | **N** | Y | Rippler は「最初のアプリケーション非依存能動的依存性発見システム」であると主張する(§VIII)。 ## 実験設定 - **実験環境**: 大学学科計算機室(主に学生の課題用)。全ホストは cfengine で一元管理、同一構成 - **ネットワーク**: NetFlow フォーマットで 133GB・125 億接続を収集 - **対象サービス**: 最頻 54 サービスを選定して遅延注入 - **遅延パラメータ**: 500ms 遅延、10 秒窓(アイドル)・10 秒窓(ビジー)の交互周期 - **期間**: 4 ヶ月 - **比較対象**: Sherlock [3]、Orion [6]、NSDMiner [14](いずれも受動的依存性発見システム) - **評価指標**: ROC 曲線(真陽性数 vs 偽陽性数)、156 依存候補を管理者インタビューと設定ファイル精査で手動ラベリング(真 68 件・偽 70 件・不明 18 件) ## 実験結果 **Rippler の成果(Table I)**: 検出した真の依存性の一例: - NFS1: LDAP, web, cfengine, dhcp, portmapper, lab shell, DNS - web26: NFS26, portmapper26 - NFS3: MySQL, NFS4 等 合計 38 件の依存性を検出。うち一部は管理者が従来把握していなかったものが含まれる。 **精度**: - p 値 ≤ 10^-6 に設定すると偽陽性ゼロ - アイドルサービス(1000 リクエスト未満)を含めると 7 件の偽陽性が発生 **比較システムとの対比(Figure 4 ROC 曲線)**: - Rippler は任意の真陽性数において偽陽性が最も少ない - Sherlock: 最頻使用サービスをすべて相互依存とみなし大量の偽陽性を生成 - Orion: 1.5 標準偏差(p = 0.1336)より高い確度では依存性を全く検出できなかった - NSDMiner: リモートリモート依存性を検出しないため、本実験では多数の依存性を見逃す(実験ネットワークでの主流依存性タイプが DNS 経由のリモートリモートだったため) ## 考察 「相関は因果でない」という問題が受動的手法の根本的限界であることを実験で確認した。DNS サーバは最頻使用サービスであるため多くのサービスの前に使われるように見え、相関ベース手法(Orion、Sherlock)はほぼすべてのサービスが DNS に依存すると誤検知した。実際にはホスト設定ファイル(/etc/hosts)に内部 IP が記載されているため DNS 照会は不要であり、これが偽陽性だった。 高遅延依存性(Figure 5)については、対象サービスへの遅延期間が長い場合に別サービスの遅延リップルと混同される偽陽性の原因となりうる。これは各サービスへの割り当て時間を長くすることで解決可能と述べている。 ## 強み・弱点 ### 強み - アプリケーション非依存: 未知サービス・暗号化トラフィックでも適用可能 - ホスト変更不要: NetFlow 等の標準フロー記録だけで動作 - 統計的保証: p 値による偽陽性制御、データ量増加で任意精度を達成可能 - 方向性の検出: 遅延の伝播方向でローカルリモート/リモートリモートを区別できる ### 弱点・限界 - 遅延注入のためデレイヤーを対象サービスとクライアントの間に設置する必要がある - 調査対象サービス集合を事前に把握している必要がある(事前のスコープ設定が必要) - 遅延パターンを保存しない依存性タイプ(バックアップ・ロードバランシング)は検出できない - 各サービスへのアクティブな実験時間が必要 → 非常に大規模なシステムでは実験時間が長くなる - 100ms〜500ms の遅延自体がレイテンシ敏感なサービスに影響する可能性 ## 関連 - [[Ali Zand]] — 第一著者 - [[Giovanni Vigna]] — 共著・指導教員 - [[Christopher Kruegel]] — 共著 - [[Richard Kemmerer]] — 共著 - [[UC Santa Barbara]] — 所属機関 - [[ネットワークサービス依存性発見]] — 本論文のドメイン概念 - [[遅延注入]] — 本論文の提案手法の核心 - [[障害注入]] — 上位概念(能動的システム操作一般) - [[@2012__LISA__On the Accurate Identification of Network Service Dependencies in Distributed Systems]] — 比較対象の NSDMiner を提案した直前世代 - [[@2007__SIGCOMM__Towards Highly Reliable Enterprise Network Services via Inference of Multi-level Dependencies]] — 比較対象の Sherlock - [[@2008__OSDI__Automating Network Application Dependency Discovery - Experiences, Limitations, and New Solutions]] — 比較対象の Orion ## 出典 - Zand, Ali, Giovanni Vigna, Richard Kemmerer, Christopher Kruegel. "Rippler: Delay Injection for Service Dependency Detection." *IEEE INFOCOM 2014*, pp. 2157–2165. DOI: 10.1109/INFOCOM.2014.6848158.