ネットワークアプリケーションの依存関係の自動抽出と可視化に関する論文

"Macroscope: End-Point Approach to Networked Application Dependency Discovery" という論文を読んだ内容をここでまとめておく。

Popa, L and Chun, B-G and Stoica, I and Chandrashekar, J and Taft, N, “Macroscope: End-point approach to networked application dependency discovery”, 5th International Conference on Emerging Networking Experiments and Technologies(CoNEXT), 229-240, 2009.

ACM CoNEXTはCORE Rankings(2018)基準でAランクのトップカンファレンスである。

読んだ動機

以下の記事にあるように、サーバにエージェントをインストールするだけで、TCP/UDP層でデータセンター内/データセンター間のサーバ(or ユーザーランドアプリケーション)同士のネットワーク依存関係を過去に渡って自動的に発見できないかを考えている。

TCP接続の追跡による簡略化したネットワーク依存関係グラフの可視化基盤 - ゆううきブログ

自分が調査した限りでは、2009年の論文で古くはあるもの、このMacroscopeが自分のアプローチに最も近い先行研究であるため、細部まで読み込んだ。

概要と感想

本論文では、分散システムの依存関係をTCP/UDPのコネクションテーブルとパケットトレースの結合により自動抽出する、実践的で高精度な手法を提案している。 エンドホスト上のコネクションテーブルとパケットトレースを組み合わせて依存の検出精度を高めている着想がおもしろい。これまで自分はどちらか一方のみを利用する前提で捉えていたこともあり、この着想は参考になった。 アプリケーションの例として、MS Outlookが例に出されていたり、評価環境のホストがWindowsラップトップであることから、社内システム管理者が、オフィスネットワーク内の各クライアントPCとLDAPなどの提供サービスの依存関係を把握するという前提があると解釈している。これをデータセンター内のサーバの依存関係だと思い込んで読むと、細部の記述に違和感を感じてしまう。 とはいっても、データセンター環境を対象としても十分応用できる手法であるように思う。

Introduction

社会の背景

今日の企業ネットワークとデータセンターにおいては、数多くのネットワークアプリケーションが相互に依存し、複雑化している。 企業のITコスト70%までは、メンテナンスとコンフィグレーションコストであると文献[15]により推測されている。

問題意識

アプリケーションとサービスの間の依存関係の発見(またはマッピング)は、以前から重要なタスクとして認識されている。 これらの仕事の多くにおいて、依存関係の発見は、単にネットワークレベルのパケットトレースのデータに頼っている。

先行手法

例えば、Sherlock[5]は、異なるサービス間のパケットの時間相関を利用する。また、Orion[9]はフローペアの遅延分散のスパイクを利用する。 パケットトレースは、各ホストに影響をあたえずに収集できる利点がある。 しかし、アプリケーションとサービスの依存を抽出するという観点では、次のような制約がある。

先行手法の課題

まず、これらのパケットトレースによる手法はかなり正確さに欠けうることが挙げられる。 独立したサービス間の時間相関は、偽陽性につながるような因果関係の幻想をつくりうる。また、バックグラウンドのトラフィックがネットワークパケットのタイミングをかきみだしてしまうか、一時的にパケットをどのように観測するかで大きな変化がある場合、偽陰性が起こりうる。 次に、パケットトレースのみでは、通信パターンが非常に動的または頻繁であるときに依存関係を明らかにできないことが制約としてある。 これは依存関係の抽出手法が多数のサンプルを必要とするからである。 三つ目の制約は、パケットトレースのみを利用するとき、依存関係を正しく抽出するために人間の介入が必要となることである。 これは、抽出された依存関係の精度が人間のオペレーターに完全に依存することになる。

提案手法

そこで、この論文では、アプリケーションの依存関係を自動で抽出するアプローチを提案する。 先行手法と対比すると、提案するアプローチは、特定のアプリケーションについての情報をエンドホストで収集し、ネットワークパケット追跡と結合する。さらに、アプリケーションの依存関係に到達するために、複数のエンドホストからの情報を関連付ける。

システム構成

Macroscopeは、ネットワークレベルとアプリケーションレベルの情報を利用し、ネットワークアプリケーションの依存関係を自動で抽出するシステムである。

Macroscopeは、Tracers、Collector、Analyzerという3つのコンポーネントにより構成される。 Tracerは、各エンドホストで動作し、定期的にTCP/UDPコネクションテーブルをサンプリングしネットワークレベルのパケットトレースと結合することにより、アプリケーションレベルのプロセス情報をログ収集する。 その後、これらの処理済みのトレース結果を中央のCollectorへ転送する。 Analyzerはエンドホストの母集団全体のトレースを相関させて、最終的に様々な属性の依存関係の抽出する。

提案手法の意義

  1. アプリケーションによって使用されるすべての主要サービスを列挙することによって障害診断を支援可能。
  2. 依存関係により、ネットワークオペレータは、障害影響を理解し、効用を最大化するためのリソースを配置可能。
  3. アプリケーションの一時的な依存関係を学習することは、オペレータがサービスを再開するための正しい順序を決定するのを助けることが可能。
  4. アプリケーションの正しい依存関係を知ることにより、アプリケーションまたはサービスの異常を検出可能。

提案手法の貢献

  • サービスレベルの依存関係を特定可能。複数の粒度レベルについて、アプリケーションとサービスの依存関係グラフについてアプリケーション-サービス依存グラフを構築する。
  • 53の企業のエンドホストで収集したトレース結果をもって提案手法を評価した。Macroscpeはパケットトレースのみ利用する最新の手法(Orion[9])と比較し、大幅な差をつけて優位となった。これは、アプリケーションレベルの情報を持ち込んだことによる成果である。
  • アプリケーション-サービスの関係のプロファイルにより、150を超えるアプリケーションで探索的な評価を実行する。像とねずみの現象や驚くほど多くのシングルサービスアプリケーションなどの興味深い発見を明らかにする。最後に、これらの提案手法の特性を活用するサービス管理アプリケーション(障害の局所化、負荷分散/レプリケーション/キャパシティ計画、マルウェア検出)について説明する。

Macroscope Approach

用語定義

  • アプリケーション(application, app): 実行可能なアプリケーション
  • アプリケーションインスタンス(application instance): 特定のエンドホストで動作するアプリケーション。(app, PID, IP) のタプルで表現される。
  • PID: プロセス識別子
  • サービス(services): (protocol, port)のタプルで識別される。DNS, LDAP, HTTPなど。
  • サービスインスタンス(service instance): (IP’, protocol, port)のタプルで表現される。
  • dependency: 任意のアプリケーションと任意のサービス間の関連
  • static dependency: 単にコネクションが確立されるだけでなく、アプリケーションにとって”クリティカル”な依存を示す。
    • (1) ユーザーアクションや他のアプリケーションインスタンスとは独立して、(2) アプリケーションのソースコードと設定ファイルのみを利用して、アプリケーション実行前にサービスSの利用を予測できる状態
    • (app) → (protocol, port)の関係で示せる
  • transient relations: (app) → (protocol, port)の関係を持ちつつもstatic dependencyではない関係性
    • ephemeral portへのコネクションなど。P2Pアプリケーションで利用される。企業ではあまり利用されない。
    • アプリケーションにより確立されたすべてのコネクションからtransient relationsに該当するすべてのコネクションを差し引いたものがstatic dependencies。

Multilevel Dependencies

static dependenciesよりもローレベルの粒度をもつ関係性もよく利用される。 そのために、アプリケーションとサービス間の寛解性の粒度レベルを次のように定義する。

  1. app → (procotol,port) : トップレベルのstatic dependency
  2. app → (IP’,protocol,port) : アプリケーションにより利用される独立したサービスインスタンス
  3. (app,PID,IP)→ (protocol,port) : 特定のアプリケーションインスタンスにより利用される汎用サービス
  4. (app,PID,IP) → (IP’,protocol,port) : 特定のアプリケーションインスタンスにより利用されるサービス
    アプリケーションとサービス間の依存関係の例

Dependency Profiling

依存関係グラフにおいて、各依存は利用頻度もしくはトラフィック量のような重みと関連付けられる 因果順序 を次のように定義する。 “appの依存Aが依存Bよりも前に頻繁にアクセスされ、AとBのアクセスが短時間のタイムウィンドウW以内の発生するとき、依存Bよりもappの依存Aが因果的に依存Bよりも前に並べられる。” MacroscpeはOrion[9]と異なり、フローの方向を常に考慮する。

End-point Tracing vs Network Tracing

エンドポイントトレーシングの利点は、(1) 完全に自動であることと (2) より精度が高いということにある。 反面、エンドホストでの計測とそれらがもたらすオーバーヘッドというコストが発生するが、CPUやメモリ使用量といった統計値を収集するわけではないので、マシンが低速になることに気づくユーザーはいない。

精度の改善については、先行手法であるOrion[9]やSherlock[5]は、完全な依存関係グラフの部分グラフを検出のみとなり、しかも、タイムウィンドウ内での同時発生に頼ることから、かなりノイズがある。 対象的に、提案手法は、同一アプリケーションの接続を識別できることから、より精度が高くなる。

MacroScopeは偽陽性率も削減する。Orionでは、(app) → (A → B)の依存と(app’) → (X → B)の依存があるとき正解シードとしてappがBに依存することを手動で設定するため、appがXに依存すると誤判定してしまう。*1

Macroscope

System Architecture

Tracerは、MS Windows XPが動作するラップトップ向けに実装している。 Tracerは、TCPUDPの接続テーブルをサンプル取得し、ファイルに追加する。サンプルはサンプリング時刻とアプリケーション名、プロセスID、(protocol, ports)などのアプリケーションレベルの情報を含む。 Tracerは5秒ごとに、GetExtendedTcpTableとGetExtendedUdpTableコールを発行する。

TracerはWinPcapを利用しパケットレベルのトレースを取得する。 実装ではエンドホストでパケットキャプチャをしているが、パケットトレーシングの手段は他にもあり、組織ネットワーク内にあるネットワークモニタを利用してもよい。

Collectorは、Bro*2を利用しパケットトレースからフロー(TCP/UDPセッション)を構築し、XMLの接続テーブルと結合する。

Analyzerは、依存関係の抽出、依存関係の問い合わせ、依存関係の可視化のためのツールセット群により構成されており、Pythonで実装されている。 4つの粒度レベルに応じてstatic dependencyを可視化でき、利用頻度やトラフィック量による依存の重み付けもできる。

サンプリング頻度を増加させると、より精度を高められるが、エンドホストのリソース消費も高めてしまう。5秒間隔であれば、オーバーヘッドは無視できるが、サンプリングアプローチにはいくつか注意すべき点がある。 まず、非常に短命なフローを見逃してしまうこと。次に、プロセスのフォークやローカルのプロキシへのコネクションの委譲などにより、実際のアプリケーションの情報を隠してしまう可能性があること。

Algorithm to Identify Static Dependencies

アルゴリズムの入力は、(PID,アプリケーションインスタンスのユーザー識別子、src/dst IPアドレス、src/dst ポート、プロトコル)。 static dependencyを特定する2つのステップがある。

  1. Classifying applications: アプリケーションを2つのタイプ(static dependencyのみを生成する、static dependenciesとtransient relationsの療法を生成する)に分類する。
  2. Identify Static Dependencies: static dependenciesとtransient relationsの両方のコネクションをもつアプリケーションからデータを取り出し、その2つを区別する。これには、同じアプリケーションのインスタンスであればstatic dependenciesは共通し、transientな接続はそうではないという仮定のもとに、コネクションの利用頻度情報を活用する。

Classifying applications

  • N ^a: アプリケーション’a’のインスタンスの個数(aの(PID,IP)のユニークなタプルの個数を計上して計算する)、
  • N _ s ^a: 特定の(port, protocol)ペアを参照するサービスsを利用する[tex:Na]の個数
  • S ^a: サービス、またはすべてのトレース内のaのすべてのインスタンスにより観測された(port, protocol)ペアの合計個数
  • V ^a _ s = N ^a - N ^a _ s: サービスsを利用していないアプリケーションインスタンスの個数
  • M ^a = \sqrt{\sum _ s(V ^a _ s) ^2/S ^a}: メトリック。transientコネクションの度合いを示す。

M^ a0からN^ a-1の間をとるので、M^{a} \lt T (N^{a}-1) (Tはパーセンテージ) を満たせば、アプリケーションはtransient relationsを持たないといえる。本研究では、Tの値として85\%を用いている。

Identify Static Dependencies

次の手法でstatic dependenciesを抽出する。

  1. 1024以下のポートをリスニングしているすべてのサービスをstatic dependenciesと認識する。
  2. 残りのサービスは、利用頻度に2つの条件を満たすとstaticとしてラベル付けする。
  3. U ^{all}: すべてのユーザー集合
  4. U ^{a} \subset U ^{all} : アプリケーションaを利用するユーザー集合
  5. U ^a _ {s} \subset U ^a: アプリケーションaを通してサービスsに接続するユーザー

2つの条件: \displaystyle \frac{|U ^a _ s|}{|U _ a|} \geq U and \displaystyle \frac{N ^a _ s}{N ^a} \geq I UIは2つの閾値である。本実装では、実験データに適合するように実験的に決定した値である10%をそれぞれの相対閾値として採用している。しかし、提案手法はそれほどこのパラメータに対してセンシティブではない。 この条件を設定した理由は、あるユーザーによる特定のpeerに対する頻繁な接続が偽陽性の依存として判定することを避けるためである。

Adjuestments due to sampling

Macroscopeの手法は非常に短命なコネクションを見逃しうるため、実際の利用頻度よりも低く観測されて、transient connectionsとしてミスラベリングしてしまう課題がある。 そのため、検知確率(コネクションテーブル内のTracerによりサンプルされる確率)をもとに値を更新する。 平均コネクション期間をd、Macroscopeのコネクションテーブルサンプリング間隔をW > dとすると、検知確率をp_d = d/Wと定義する。 Wよりも短いコネクションのために、複数の利用頻度サンプルが使用可能なときに、利用頻度に1/p_dを掛け算する。

Evaluation

本論文で使用したトレース結果は、ある大企業の52台の雇用者のラップトップを11週間の間キャプチャしたものである。


依存関係の可視化の例

Figure3は、複数の粒度レベルの依存関係を可視化した様子である。

static dependency検知の精度を確認するために、MSオフィス系アプリケーション、Skypeなどを含む12のアプリケーションを選び、(1) static dependencyを手動検証し、(2) Orion[9]の結果と比較した。

Table2は手動によるground truthとMacroscope、Originの比較結果表である。(tp)はtrue positives、(fp)はfalse positives、(fn)はfalse negativesを示す。 Macroscopeはfpとfnも非常に小さく、tpを95%以上の精度で検出している。fpは18%。Orionは91%の精度で検出するが、315%のfpとなっている。シード選択をfpに最適化すると、fpは80%となるが、tpは57%となってしまう。

Future Work

  • Causal order of dependencies: ****依存の因果順序のアルゴリズムを実装は示したが、ground trueが手に入らないために、評価結果は出せていない
  • Server side dependencies: 本論文では、クライアントサイドのトレースだったが、サーバサイドのトレースがあれば、深さ1よりも大きい複雑な依存関係グラフを作成に拡張できる。
  • Kernel-level tracing: コネクションテーブルのサンプリングをカーネル内のシステムコールのモニタリングに置き換えられる。パケットトレースなしでUDPの依存も検出できる。プロセス間通信をトレースすることにより、OSサービスの利用を通して間接的にアクセスのある依存を検出できる。しかし、ネットワークトラフィックに比例して、トレーシングオーバーヘッドが上がってしまうのが難点である。
  • Identifying applications: 名前衝突を避けるために、実行ファイル名の代わりに、実行ファイルのハッシュを利用し、アプリケーションを特定できる。しかし、コンパイラにより異なる実行ファイルが生成される可能性がある。

手法の制約

論文中には書かれていないが、提案手法では次のようなものはスコープ外であると考えている。

  • 2ホップ以上の依存関係の収集には未対応
  • おそらくephemeral portへ接続するP2Pアプリケーションには未対応。厳密にはP2Pアプリケーションのコネクションを排除することは可能。
  • リアルタイムな依存関係の収集
  • 大量のエンドホストからのトレースの収集
  • 2009年の論文なので当然だがコンテナランタイム上のアプリケーションの依存関係の収集は未対応

*1:おそらくOrionが有向フローを扱えないという前提のもとに

*2:今はZeekという名前になっている