論 文
ネットワークデータを用いた分散システムにおける異常検出
鹿島

久嗣†

津村

直史†

井手

剛†

平出

涼†

江藤

博明†

福田 剛志††

野ヶ山尊秀†

Network-Based Problem Detection for Distributed Systems
Hisashi KASHIMA† , Tadashi TSUMURA† , Tsuyoshi IDÉ† , Takahide NOGAYAMA† , Ryo
HIRADE† , Hiroaki ETOH† , and Takeshi FUKUDA††

あらまし 本論文で，我々はネットワークデータを用いた分散システムの異常検出システムを提案する．その中で我々は，(1) 対象とするシステムに負荷をかけることなく，ネットワークを流れるデータからトランザクショ
ンの情報を復元する枠組み，(2) 分散したサービスの間の動的な依存関係をトランザクションの実行時間の包含関係を手がかりに，オンライン EM アルゴリズムに基づいて直接的な依存関係を発見することのできる競合モデ
ル，及び，(3) 発見された依存関係情報に基づいた様々な粒度での指標を用いた階層的な異常検出の枠組みを提案する．また，プロトタイプシステムを用いた実験によって，我々の提案するシステムが，実際にシステムに仕組
まれた障害を発見できることを確認する．
キーワード

異常検出，ネットワークデータ，分散システム，EM アルゴリズム

1. は じ め に
今日の典型的な e-ビジネスの基盤は，分散した Web
サーバーやアプリケーションサーバー，データベース，
ストレージサーバー，ネットワークデバイスといった多様なコンポネントから構成されている．そして，各々のコンポネントは各自の持つ様々な機能をサービスとしてお互いに提供している．そして，これらのサービスは自らの機能を果たすために，お互いに強く依存しFig. 1

図 1 分散システムにおける依存関係の例
Example of dependencies in a distributed computer system

あっている．例えば，HTTP サーバーはユーザーに対し，ある URL で指定される Web ページをサービスとして提供しているといえる．もしも，そのページがブレットが EJB を呼ぶ場合には，サーブレットは EJB

サーブレットを含むものであった場合，ユーザー（ブに依存し，さらに EJB がデータベースに対する問い合ラウザー）からのリクエストを受け取った HTTP サー

わせを行う場合には，EJB はデータベースに依存する

バーは，サーブレットを実行するためにアプリケーことになる．図 1 は，このような依存関係を図示した

ションサーバーを呼ぶ．この場合，その URL で指定例である．このように，依存関係の情報は，サービスされる Web ページへのリクエストは，サーブレットにを頂点，それらの間の依存関係を辺とした有向グラフ

依存しているということができる．同様にして，サーとしてみることができる．

†

Gupta et al. [1] らは，多くのコンポネントが持って日本 IBM 株式会社 東京基礎研究所，神奈川県
IBM Tokyo Research Laboratory, 1623-14, Shimotsuruma, Yamato-shi, Kana-††

日本 IBM 株式会社 大和ソフトウェア研究所，神奈川県
IBM Yamato Software Laboratory, 1623-14, Shimotsuruma, Yamato-shi, Kanagawa, 242-8502 Japan

いる共通のパフォーマンス監視用の仕組みを用いて集めたトランザクションの実行期間からサービス間の依gawa, 242-8502 Japan

存関係を自動的に発見する手法を提案した．しかしながら，彼らのアルゴリズムはワークロードが高くなる

電子情報通信学会論文誌 D Vol. J89–D No. 2 pp. 1–16 2006 年 2 月

1電子情報通信学会論文誌 2006/2 Vol. J89–D No. 2と，多くの偽の依存関係を出力してしまうという欠点

異常報告を効果的にフィルタリングすることが可能にがある．加えて，彼らの手法では，直接の依存関係となる．

間接的な依存関係を区別できないという欠点がある．

以下の構成は次のとおりである．まず 2. 章におい

この性質は依存関係のグラフを複雑にしてしまうため，て，システムにおける依存関係の定義を行う．次に，3.

システムの理解や障害箇所の特定が困難になる．一方，章では，依存関係の発見問題と，それに対する我々の図 1 のように直接の依存関係のみによって構成されるアプローチである，ネットワークを流れるデータを対依存関係のグラフはシンプルであり，これらの目的に象とした監視システムのアーキテクチャについて述べより適しているといえる．

る．4. 章では，既存の依存関係発見手法である Gupta

本論文では，我々は 2 つのアイデアに基づき，前述

らのアルゴリズムを説明し，その問題点を指摘する．

した問題を解決する．まず，サービスの到着間隔と実

そして，それらの問題を解決する我々の新しい依存関

行時間から推定される確率モデルを用いて，偽の依存係発見アルゴリズムを提案する．5. 章では，発見され関係の割合を軽減する方法を提案する．そして次に，た依存関係に基づく，システムの異常検出の枠組みを直接の依存関係だけを発見するための競合モデルと呼説明する．6. では，実際のシステムを用いた実験によぶモデルを提案し，EM アルゴリズム [2] に基づきこり，提案手法の有効性を検証する．最後に 7. 章では，のモデルのパラメータ推定を行う方法を提案する．ま

関連研究を紹介し，8. 章にて，結論を述べる．

た，我々のモデルは，あるサービスが他のサービスを直接何回呼び出したかを推定することができ，これは2. 依存関係発見

依存関係の有無のみを推定しようという Gupta らの定

1. 章において，依存関係を用いた分散システムにお式化の一般化となっている．また，我々はトランザク

ける障害の検出と解析を動機付けたが，この章では，ションの実行期間データを収集するための情報源とし稼動中のシステムから依存関係を発見する問題を定義て，ネットワークを流れるデータを用いるため，対象する．

となるシステムのパフォーマンスに殆ど影響を与える

Σ を対象のシステムにおけるサービスの集合とする．

ことなくシステム全体の情報を利用することができる．

それぞれの S ∈ Σ は例えば，URL で指定される Web

依存関係はしばしばシステム管理者ですら気づいてページやサーブレット，あるいは EJB のあるメソッド

いなかったシステムの振る舞いを理解するのに役に立やデータベースへのクエリなど，様々な粒度で提供さつ．また，システムに異常が発生した際には，これられる機能を指す．トランザクション T とは，サービスの情報は異常の検知や，その致命度の解析，あるいはのインスタンスであり，T の属するサービス S と開始

異常個所の特定といった目的にも利用できる．ハード

時刻 s および終了時刻 t の組によって T = (S, [s, t])

ウェアの故障やソフトウェアのバグなどによって，あと定義される．ここで，[s, t] を T の実行期間と呼ぶこるサービスがうまく働かなくなった場合，依存関係のとにする．例えば S が，ある URL で指定される Web

情報から障害の影響を受けたサービスを知ることがでページであった場合，s はそのページに対するリクエ

きる．

ストの時刻，t はリクエストに対して Web ページの送

さらに，本論文では，発見された依存関係を基にし信が終了する時刻というように定義できる．

た異常検出の方法を論じる．個々の依存関係など，特トランザクション履歴 D とは，対象のコンピュータ

定の値の変化に基づいて異常検出を行う方法についシステムに設置された計測機構を用いて得られるトラては，[3], [4] をはじめ，いくつかの研究例が存在する．

ンザクションの集合である．多くの計測手段が D とし

一方，井手ら [5] はサービスやシステム全体といったてモデル化されるデータを提供することができる．場より大きな視点から障害を検出するための手法を提案

合によって D は，含まれるトランザクションの終了時している．そこで，本論文では，システムの微視的な刻順にソートされているとする．

特徴量と巨視的な特徴量を用いることで，異常検出か

トランザクション T1 = (S1 , [s1 , t1 ]) の実行期間が，ら，異常箇所の特定へと結びつける階層的な解析を行

別のトランザクション T2 = (S2 , [s2 , t2 ]) の実行期間

うという階層的な異常検出の枠組みを提案する．このを包含しているとき，T1 は T2 を包含するといい，枠組みによって，障害箇所の絞り込みや，個々の箇所

T1 º T2 と表す．トランザクション T1 が別のトランを独立に監視するだけでは大量に発生してしまう偽のザクション T2 を呼び出すとき，T1 が T2 に直接に依2

論文／ネットワークデータを用いた分散システムにおける異常検出存するという．また，そのような T1 ，T2 があるとき，るアプリケーションがトランザクションごとに ARM

これを S1 ⇒ S2 と表す．そして，T1 は T2 の親トラの API を何度か呼び出す必要があるため，対象のシンザクションであり，T2 は T1 の子トランザクション

ステムに負荷をかけてしまうという問題がある．加えであるという．各トランザクションは，高々1 つの親て，ARM を使用可能にするために，アプリケーション

トランザクションを持つことに注意する．T1 が直接にのソースコードに改変を加えなければならない．従っT2 に依存するか，あるいは，T1 が，T2 に依存する別て，トランザクション間の呼び出し関係を直接計測すのトランザクション T3 に依存するとき，T1 は T2 にるのはコストがかかりすぎ，多くの場合現実的ではな

依存するといい (再帰的な定義となっているところにくなってしまう．

注意する)，T1 → T2 と表す．

一方，各トランザクションの実行期間を計測するこ同様にして，トランザクション T2 = (S2 , [s2 , t2 ])と，すなわちトランザクション履歴 D を得ることは比に 直 接 に 依 存 す る よ う な ト ラ ン ザ ク ション T1 =較的簡単で，対象のシステムにあまり負荷がかからな(S1 , [s1 , t1 ]) が存在するとき，サービス S1 はサービスい場合が多い．そこで，我々はトランザクション履歴

S2 に直接に依存するという．また，T2 = (S2 , [s2 , t2 ])からサービス間の依存関係を推定するというアプローに依存するようなトランザクション T1 = (S1 , [s1 , t1 ])チをとる．

が存在するとき，サービス S1 はサービス S2 に依存すまずは，稼動中の分散システムから如何にしてトるといい，S1 → S2 と表す．サービス S1 がサービス

ランザクション履歴 D を復元するかを考える．Gupta

S2 に依存するとしても，D における全ての S1 に属す

ら [1] は，多くのコンポネントが持っている共通のパ

るトランザクションが S2 に属するトランザクションに

フォーマンス監視用の仕組みを定期的に呼び出すこと依存するとは限らない点に注意する．また，S1 のトラ

で，トランザクションの実行期間を取得するアプロー

ンザクションが S2 のトランザクションを複数回呼びチを提案した．彼らの手法はノード内，すなわち 1 つ

出すこともありうる．後ほど定義するように，我々はのマシン内の依存関係を発見するのには効果的である

直接の依存関係 S1 ⇒ S2 あるいは依存関係 S1 → S2

が，この方法を分散したノード間の依存関係発見に用の強さを S1 のトランザクションが S2 のトランザク

いようとすると，依存関係発見のアルゴリズムを適用

ションを呼び出す確率，あるいは回数の期待値としてするためにデータを一箇所に集めなければならず，ま定義する．G(D) をトランザクション履歴 D から導か

た，ノードの時計を高い精度で同期させねばならない．

れる全ての依存関係の集合とする．依存関係は 2 項関

一般的な企業システムにおいて，各ノードは別々の係の集合であるため，G(D) はグラフとして表現できマシンにインストールされており，コンポネント間のる．これを依存関係グラフと呼ぶ．

通信はネットワークを介して行われる．我々はこの点ここで我々は，次の重要な仮定を行う．我々は全てに着目し，ネットワークを流れるデータをネットワーのトランザクションは同期的，すなわち，T1 が T2 をクデバイスにおいて監視することで，トランザクショ

呼び出すとき，T1 は必ず T2 が終了するのを待ってかンの実行期間を取得するというアプローチをとる．現ら終了するとする．つまり， T1 → T2 ならば T1 º T2

在では，ルーター，スイッチ，ハブなどの多くのネッが成立するとする．

トワークデバイスにおいて殆ど全て (あるいは，定義

3. 依存関係発見問題とネットワークデータ
からのトランザクション履歴の復元されたいくつかの) トラフィックを殆どパフォーマンス
に影響を与えることなく取得することのできるミラー
ポートを備えている．そして，ミラーポートから取ここまでのところでは，我々はどのトランザクショ

得したパケットデータを解析することで，トランザク

ンがどのトランザクションを呼び出していることをションの開始時間，終了時間，およびサービスに関す知っている，すなわちシステムにおける全ての依存関る情報を得ることができる．例えば，HTTP のトラン係は自明にわかるものと仮定してきた．

ザクションの開始時刻は ‘GET’ メソッドを含むパケッ

例 え ば ，ARM (Application Response Measure-

トから，終了時刻は ‘HTTP/1.1 200 OK’ のメッセージment) [6] はアプリケーションの挙動を捉え，トランを含むパケットからそれぞれ取り出すことができる．

ザクション間の真の呼び出し関係を知ることのできる

また，複数のノード間を行き交う情報を，ミラーポー

API の集合である．しかしながら，ARM は対象とな

トに接続された 1 つのノードで取得できるため，デー
3電子情報通信学会論文誌 2006/2 Vol. J89–D No. 2
problem localization

root cause analysis

Application clientsvisualization

impact analysis

きくなるはずである．

protocol analyzer (http)protocol analyzer (drda)…

図2protocol analyzer (ldap)

Server N

dependency discovery
algorithm

包含しているはずであり，従って，p の値が 0 より大transaction detector
protocol analyzer (dns)…

packet capture

network switch

mirrorport

ションが S2 のトランザクションを少なくとも 1 回はnetwork monitor agent
Server 1
Server 2の間に真の依存関係があるならば，S1 のトランザク

プロトタイプシステムの概念図
Fig. 2 A prototype system

また彼らは，S2 のトランザクションが少なくともひ
とつの S1 のトランザクションに包含される確率 r を，

r=](S2 |S1 º S2 )](S2 )(1)のように定義した．ここで，](S2 |S1 º S2 ) は D 中のS2 のトランザクションの中で，少なくとも 1 つの S1のトランザクションに包含されているものの個数であ

タ収集と時刻同期のコストが削減される．さらに，パるとする．

ケットはリクエストの要求元の IP アドレスをも含ん

そして彼らは，これら 2 つの指標を組み合わせてでいるため，これらを用いて親トランザクションの候

max(p, r) + pr を依存関係 S1 → S2 の強さを測る指補を限定するのにも利用することができる．(親トラン

標として提案している．Gupta らのアルゴリズムは全ザクションのサービスは，その IP アドレスで指定さてのサービスの組 (S1 , S2 ) について，依存関係の強されるノードで動いていなければならない．)

をオンラインで計算する．

以上の考えに基づき，我々は図 2 に示されるようなGupta らの手法はシンプルであるが，トランザクショ

プロトタイプシステムを開発した．現在のプロトタイ

ン履歴のみから自動的にサービス間の依存関係を発見

プでは，HTTP，DRDA，DNS，及び LDAP をサポーする強力なツールである．しかしながら，我々は以下トしているが，アーキテクチャ自体は，そのほかのプに示す 3 つの問題点を指摘することができる．

ロトコルに対応したプロトコル解析モジュールを追加（ 1 ） ワークロードの高い状況では，依存関係を過することにより，容易に拡張可能となっている．

大評価，すなわち，偽の依存関係を発見してしまう．

4. 依存関係発見手法

ワークロードが高くなるにしたがって，トランザクション同士の包含が偶然によって起こる確率が高くな

この章では 3. 章で得られたトランザクション履歴

る．つまり，S1 が S2 に依存しない場合でも，S1 のト

D から，トランザクションが同期的であるという仮定

ランザクションは S2 のトランザクションを偶然包含を利用して，依存関係を推定するための手法を考える．

してしまうことが起こる場合がある．

4. 1 従 来 手 法
Gupta らは [1] において，サービス間の依存関係（ 2 ） 直接の依存関係と，間接的な依存関係が区別されていない．

S1 → S2 の強さを，以下で定義する 2 つの確率 p と r

この性質は依存関係のグラフを複雑にし，対象システを用いて定義し，これをオンラインで計算できる依存

ムの挙動の把握や，異常個所の特定を困難にする．

関係発見アルゴリズムを提案した．
まず彼らは，S1 のトランザクションが少なくとも 1
つの S2 のトランザクションを包含する確率 p を

p = ](S1 |S1 º S2 )/](S1 )のように定義した．ここで，](S1 ) は D 中の S1 のト（ 3 ） 依存関係の強さの指標の定義がアドホックである．
依存関係の強さとしては，より定量的な指標のほうが望ましいであろう．
次の章において，我々はこれらの問題に対処する新しい方法を提案する．

ランザクションの回数，](S1 |S1 º S2 ) は D 中の S1

4. 2 偽の依存関係の推定のトランザクションの中で，少なくとも 1 つの S2 の

この節ではまず，前節の最後で述べた，Gupta らのトランザクションを包含しているものの個数であると方法が依存関係を過大評価してしまうという問題を考する．S1 のあるトランザクションが S2 のトランザク

察する．

ションを複数回包含していても，](S1 |S1 º S2 ) への2 つのサービス S1 と S2 の間に依存関係がないとす

寄与は 1 回と数えることに注意する．もしも S1 と S2

る．言い換えれば，S1 のトランザクションが少なく4

論文／ネットワークデータを用いた分散システムにおける異常検出であり，その中のひとつのトランザクションが時刻 t1に始まり，時刻 u1 で終了するとする (図 3 を参照のこと)．すると，u1 は平均 1/µ1 の指数分布に従い，T1
が T2 を包含しない確率は，以下のように書くことができる．

f ail(τ2 ) =図 3 偶然による包含の確率の推定
Fig. 3 Estimation of accidental containmentsZ τ2µ1 e−µ1 u1 du1 = 1 − e−µ1 τ20n 個のトランザクションの終了時刻はお互いに独立でとも 1 回の S2 のトランザクションを呼び出す確率があるから，S1 のトランザクションが n 個存在し，そ0 で，S2 のトランザクションが S1 のトランザクショ

れらの全てが T2 を包含しない確率は，

Z ∞ンに呼び出される確率が 0 であるとする．ワークロー
ドが高くなるに従って，S1 のトランザクションが少な

xn =0

くとも 1 回の S2 のトランザクションを包含してしまう確率と，S2 のトランザクションが少なくとも 1 回

λ
λn
− 1
1
e µ1 f ail(τ2 )n µ2 e−µ2 τ2 dτ2µnn!
1のようになり，最終的に，の S1 のトランザクションに包含されてしまう確率が大きくなり，すなわち，Gupta らの方法が偽の依存関ψ(S1 , S2 ) = 1 −

xn ,

(2)

n=0

係を導いてしまう原因になる．そこで，偶然の包含の影響を抑えるために，まずは，偶然の包含が発生する∞
Xが得られる．ここで，確率を推定することにする．

i = 1, 2 に対し，サービス Si へのリクエストが，ワークロード λi (リクエスト/秒) で到着すると仮定す
る．すると，Si への 2 つの連続するリクエストの到
着間隔 Xi は，平均 E[Xi ] = 1/λi と累積確率分布−λi t
Fi (t) = P r[Xi <をもつ指数分布に従= t] = 1 − eう．同様に，Si の実行時間 τi は，平均 E[τi ] = 1/µi

λ
− 1

µ1
λn
λ1
1e
xn−1
=
nµ1 + µ2
k=1 (kµ1 + µ2 )xn = Qn

であるとする（注 2）．

4. 3 競合モデルによる直接的な依存関係の発見
この節では，前節の結果に基づき，2 番目の課題でをもあった，直接の依存関係の発見問題を考える。既存手つ指数分布に従うとする．これらの仮定は，標準的な法 [1] が間接的な依存関係をも取り出してしまう原因

パフォーマンス解析では，一般的な仮定としてよく用

は，「各トランザクションは高々1 つの親トランザクショ

いられる [7]．

ンしか持ち得ない」という制約を無視しているためでと累積確率分布 Ti (t) = P r[τi <= t] = 1 − e−µi t

これらの仮定のもと，S2 のあるトランザクション T2が少なくとも 1 つの S1 のトランザクションに偶然包含ある。そこで我々は，この制約を明示的にとりいれた競合的なモデル

されてしまう確率 ψ(S1 , S2 ) を推定する（注 1）．簡単のたX

め T2 の開始時間を t = 0 とする．また，t = 0 においiρ(Si , Sj ) = 1(0 <= ρ(Si , Sj ) <
= 1),

(3)

て，実行中の S1 のトランザクションの数を N とする．
すると，N の確率分布はポアソン分布 P o(λ1 /µ1 )，すを採用する。ここで，ρ(Si , Sj ) は，サービス Si がサー

なわち，

ビス Sj のトランザクションにに直接的に依存する確P r[N = n] =

λ
λn
− 1
1
e µ1
n
µ1 n!

率をあらわす（注 3）。
我々はトランザクション履歴 D に対する最尤推定に従う．いま，S1 のトランザクションが n 個実行中
（注 1）
：同様に，S1 のあるトランザクション T1 が少なくとも 1 つのS2 のトランザクションを偶然包含されてしまう確率を計算することも可能であるが，後の議論では用いないため本論文ではその導出は省略す
る．

（注 2）：ψ(S1 , S2 ) は無限の和を含んでいるため厳密な評価は困難であるが，実用的には適当な n まで計算すればよい．
（注 3）：どのサービスにも依存されないサービスを統一的に扱うために，
仮想的なサービス S0 に属する仮想的な T0 = (S0 , [−∞, ∞]) を考える。

5電子情報通信学会論文誌 2006/2 Vol. J89–D No. 2

によってモデル推定を行うというアプローチをとるこ

証明: L に対するヘッセ行列は半負定であるため。詳とにする。まずは例を用いて考える。４つのサービス

細は付録 1. を参照のこと。˜Σ = {S1 , S2 , S3 , S4 } が存在するとし，S1 のあるトラパラメータ推定は以下のように行う。Expectation ス

ンザクション T は，S2 と S3 ，それぞれ少なくともひテップにおいて，現在の ρ に基づき，トランザクショ

とつのトランザクションに包含されており，S4 のトラ

ン T がサービス Si のトランザクションに直接呼び出

ンザクションにはまったく包含されていないとする。

される確率はすると，このような状況が起こる確率は，次の二つのS3 のトランザクションには偶然包含されている。まPr(Si |C(T ), T ) = Pr(Si , C(T )|T )/Pr(C(T )|T ) (5)Q
δ(Si ∈ C(T ))ρ(Si , S(T )) S 0 ∈C(T )\Si ψ(S 0 , S(T ))P
Q=
0S∈C(T ) ρ(S, Sj )S 0 ∈C(T )\S ψ(S , S(T ))た，S4 のトランザクションに偶然包含されることはなのように計算することができる。ここで，δ は引数かった。

が真ならば 1 を，そうでないならば 0 を返すような場合の確率の和である。

••

T は S2 のトランザクションに直接呼び出され，

T は S3 のトランザクションに直接呼び出され，関数であるとする。従って，サービス呼び出し頻度

S2 のトランザクションには偶然包含されている。まˆ](Si ⇒ Sj )，すなわち Si のトランザクションが Sj のた，S4 のトランザクションに偶然包含されることはな

トランザクションを呼び出した回数の期待値はかった。
従って尤度は，ρ(S2 , S1 )ψ(S3 , S1 )(1 − ψ(S4 , S1 )) +ˆ](Si ⇒ Sj ) =ランザクションに偶然包含される確率である。一般的に書くと，トランザクション履歴 D に対する対数尤

L=

T ∈D

log

X

ν(S, C(T )|T ),(4)

S∈C(T )

(6)によって得られる。

Maximization ステップにおいては，パラメータの最尤推定値は，

度の和は，

X

Pr(Si |C(T ), T )T ∈D(Sj )ψ(S2 , S1 )ρ(S3 , S1 )(1 − ψ(S4 , S1 )) となる。ここで，ψ(Si , Sj ) は，Sj のあるトランザクションが Si のトXρ(Si , Sj ) =ˆ](Si ⇒ Sj ).
](Sj )(7)によって更新される。

のように書ける。ここで，C(T )⊂Σ は，トランザク=

ション T が包含されているトランザクションのもつ∂L∂ρ(Si , Sj )サービスの（重複を許さない）集合とし，またY

ν(S, C(T )|T ) = ρ(S, S(T ))·Y

ψ(S 0 , S(T ))S 0 ∈C(T )\S(1 − ψ(S 00 , S(T )))S 00 6∈C(T )で，S(T ) は T のもつサービスとする。
我々の目標は，対数尤度の和 L を (3) の制約のもと=

X

T ∈D(Sj )であることに注意すると，上記のステップを纏めて書くこともでき，ρ(Si , Sj ) の更新則は，

ρ(Si , Sj ) ← ρ(Si , Sj )で最大化することであるが，この最適化問題を解析的に解くことは困難である。従って，我々は ExpectationQ
δ(Si ∈ C(T )) S 0 ∈C(T )\Si ψ(S 0 , Sj )QP0
S 0 ∈C(T )\S ψ(S , Sj )S∈C(T ) ρ(S, Sj )∂L
1](Sj ) ∂ρ(Si , Sj )

(8)

となる。

Maximization (EM) アルゴリズム [2] に基づく反復解

従って，任意の初期パラメータから開始して，(6) と法を提案する。各反復ごとに必ず L が大きくなること(7) を収束するまで交互に適用してやることで，最適が保証され，また，次に示すように L は局所最適解をなパラメータを求めることができる。

もたないため，提案するアルゴリズムは，常に最適解

上記のやりかたは，D 全体を一括処理することを想を求めることができる。

定しているが，実際には D はストリーム形式で与えら

定理: トランザクション履歴 D に対する対数尤度のれ，トランザクションを逐次的にオンライン処理する

和 (4) は局所最適解をもたない。

必要がある場合が考えられる。その場合には，オンラ

6論文／ネットワークデータを用いた分散システムにおける異常検出

イン EM アルゴリズム [8] を用いて，1 回のパラメー

す．システムは正常で，安定状態にあるにもかかわらタ更新には１つのトランザクションを用いるようにすず，この値はワークロードの変化に伴い激しく時間変ることができる。トランザクション T が与えられる化をしており，呼び出し回数そのものを異常検出に用と，親サービスの確率 (5) を現在の ρ に従って計算し，いるのはあまり適当ではないことがわかる．

それを (6) に加えてパラメータを更新するようにすればよい。

従って，システムの異常検出の際には fij をそのまま使うよりも，ワークロードの変化によるサービス呼Gupta らの方法が単に Si が Sj に依存しているかど

び出し頻度の揺らぎを抑えるために，正規化された量うかを考慮しているだけなのに対し，サービス呼び出

hij (fij ) を使うほうが便利である．ここで，hij (·) はし頻度 ˆ](Si ⇒ Sj ) は呼び出し回数の推定値を示して単調なスケーリング関数であるとする．

おり，システムの挙動をより深く理解するための定量的な指標を提供する。各サービス間のサービス呼び出

hij (·) の選び方としては，例えば，hij (·) = 1/](Si )と定義することで，(i, j) 要素がし頻度を行列の形で表したものを F とおく ( 個々の要
素は fij = ˆ](Si ⇒ Sj ) ) ことにする。
次の章では，推定されたサービス呼び出し頻度行列

cij =ˆ](Si ⇒ Sj )](Si )(9)に基づき，分散システムにおける問題検出へのアプで与えられるようなサービス呼び出し割合の行列 C を

ローチを提案する。

用いることが考えられる．cij は，Si の 1 回のトランザクションにつき Sj のトランザクションが直接に呼5. 異 常 検 出

ばれる回数の期待値を表しており，システムの働きを前章では，ネットワークを流れるデータから，分散理解するのには非常に有効である．システムが定常状システムにおける依存関係を高精度で抽出する方法を態のときには，cij は，多少のワークロードの変化に提案した．依存関係はそれだけでもシステムの構造を関わらず一定の値を示すことが期待できる．

理解するために役に立つが，それ以外にも，ひとつのまた，別のスケーリング関数としては，(i, j) 要素

利用方法として，システムの異常検出に用いることがが hij (·) = ln(1 + ·) で与えられるような，対数サー考えられる．依存関係はシステムの振る舞いをよく表

ビス呼び出し頻度の行列 K を用いることが考えられ現しているので，システムに障害が起こった場合，そる．実験的には，対数変換はトラフィックのバースト

れらの多くは依存関係の変化として現れるであろうと的な性質を除去するのに効果的であることが知られて考えられるためである．この章で我々はこの仮説に基いる．このスケーリング関数は (i, j) には依存しない

づき，依存関係に注目した異常検出法を提案する．

ため，サービス間の頻度のバランスが保存されるとい前章で述べた手法により，ある時刻 τ (分) におけるサービス呼び出し頻度行列 F(τ ) を，τ − k 分から τ 分う性質があり，こちらはシステム全体としての異常を発見する尺度として好ましいものとなっている．

までの間のデータから計算するということを，k 分毎に

図 4 で実線で示されているのは，サービス呼び出し

行なうことによって，現時点 t までのサービス呼び出し

割合の行列の要素である．サービス呼び出し頻度が強頻度行列の系列 F(t), F(t − k), F(t − 2k), F(t − 3k), . . .

く時間変動する一方，HTTP サーバーへのリクエストが得られることになる．我々はこの系列から異常を検は，1 回につきアプリケーションサーバーを 1 回呼び出する方法を考えることになる．

出すため，正常時にはサービス呼び出し割合は必ず 1

具体的な手法を考察するにあたり，まずは前章で求になる．このように正常時において，親サービスが子めたサービス呼び出しの行列の性質を調べてみる．まサービスを定数回呼び出す場合 (あるいはある程度のず，サービス呼び出し頻度がどのように振舞うかを調時間で平均すると定数回となるような場合) にはサーべる．図 4 の点線で示されたものは，ある HTTP サー

ビス呼び出し割合は安定した値となる．

バーへのリクエストがあるアプリケーションサーバー

5. 1 個々の依存関係に基づく異常検出を呼び出している部分に対応する部分のサービス呼び

以上の観察から，我々は，個々の正規化されたサー

したものの時間変化を表

ビス呼び出し割合 cij を確率変数と考え統計的検定を（注 4）：後に 6. 章で述べる条件のもと，4. 章で提案したアルゴリズムを用い，システムが正常に動いているときのサービス呼び出し頻度の行列
F を 5 分毎に計算した．

（注 4）

出し頻度を，5 分毎に集計

7

100

Service call ratio

1

80

0.8
0.6

60

0.4

40
20

0.2

service call ratio
service call frequency

0
0

10

20

30

0
40

Service call frequency [calls/min]

電子情報通信学会論文誌 2006/2 Vol. J89–D No. 2

5. 2 サービス活動度に基づくサービス毎の異常検出
前節で述べた異常検出ルールは単純ではあるが，単一のサービス依存関係について起こるような障害について，多くのケースで有効である．しかしながら，この基準だけでは捉えられない障害も数多く存在する．
まず，サービス呼び出し割合のいくつかは正常時でも不安定であり，図 4 のように一定値をとらないものも存在する．この場合，単純な閾値による検出法はうま50Time [min]図 4 サービス呼び出し頻度とサービス呼び出し割合の比較
Fig. 4 Comparison between service call frequency and service
call ratio

行なうことにより，個々の依存関係における異常を検出するためことができると考えられる．ここで用いる確率モデルとしては [9] で用いられているような時系
列モデルや，各時点での値を独立であるとするモデル [10]〜[12] などが考えられるが，前節でみたような
通常の設定では，システムが定常状態にあればサービス呼び出し割合は比較的安定していると考えられるため，ここでは単純に後者のモデルを考えることにする．
なお，提案した cij が 0 以上の値をとるため，理論上はガンマ分布が自然であるが，実用上はガンマ分布の正規近似を行っても十分であり，ここでは単純に正規分布を用いることにする．

く働かず，例えば，サービスの定義の中に定義されていない細かいパラメータが依存関係に影響するような場合，サービス呼び出し割合は不安定になりうる．
また，通常いくつかのサービス依存関係の時間変動は似通っており，互いに相関がある．そのため，仮に個々の依存関係に異常が観測されなくても，何らかのバランスの崩れとして異常が現れる場合がありうる（注 5）．このような異常は個別のサービス依存度を見ていても認識しがたい．
そこで我々は，一段抽象的なレベルで，各々のサービスの異常を検出するために，Idé ら [5] の枠組みを用いる．以下，その概略を説明する．まず，サービス呼び出しの行列に対する特徴ベクトル u を次のように定
義する．

n
o
u(t) ≡ arg max ũT K̃(t)ũ
ũ

(11)

cij に対して，ある時刻 t における平均 wij (t) と標

ただし，ũT ũ = 1．ここで，T は転置を表す．ここで準偏差 σij (t) の値は，よく知られたオンライン最尤推は，マルコフ遷移過程としての解釈の一貫性を保持す定の結果 [11] から，次のように計算できる．

る都合上 [5]，対称化した対数サービス呼び出し頻度

K̃ = K + KT を用いた．K̃ は非負行列なので，たとえwij (t) = (1 − β) · wij (t−k) + βcij (t),(10)

ここで β は忘却率である．
すると，以下の基準に従って，依存関係の異常を判定できる．
基準 1: もし時刻 t におけるサービス呼び出し割合

cij (t) について，|cij − wij (t)| > σij (t)xth

ば k̃2,3 が大きい値をとるならば，最大値の達成のためには，u2 と u3 が正の大きい値をとらねばならない．
すなわち，あるサービス i が他のサービスを活発に呼んでいれば，u において i の重みは大きくなる．この意味で，この特徴ベクトルを，サービス活動度ベクト
ルと呼ぶことができる [5]．
重要な経験的事実として，F における強いランダム
変動が，特徴ベクトル u においては非常に抑制されていることが挙げられる．このことから，個別のサービが満たされた時，依存関係 Si ⇒ Sj には異常がある．

ス活動度に対して，素朴に正規分布で確率モデルを考

ここで，xth はえてみる．もちろん一般にはサービス活動度同士の相Z ∞duN (x) = pc .
xthの解である．ただし，pc は危険域境界 (< 1)，N (x)は標準正規分布である．
8

関は有限の値をとるはずであるが，相関の効果はサービス呼び出し割合の行列に対する異常判定基準 1 によ
（注 5）：典型的には，冗長化構成となっているサーバー同士のバランスの崩れが例として挙げられる．

論文／ネットワークデータを用いた分散システムにおける異常検出

この u の分布から，異常度 z(t) についての分布をり補われていると考えてよい．
ある時刻 t における，各サービス i の活動度 ui (t) に導くために，r を極軸とする球座標系を導入し，特に，ついて，平均 wi (t) と標準偏差 σi (t) の値は，Eq. (10)角度変数 θ ∈ [0, π] を cos θ = r(t)T u で定義する．残と同様の式でオンラインに計算可能である．

りの角度変数を θ2 , θ3 , ..., θN などと書くことにすれ

基準 2: サービス活動度 ui (t) について，

ば，θ についての周辺分布は，

Zp(θ) =|ui (t) − wi (t)| > σi (t)xthp(u|κ, —)J(θ, θ2 , ..., θN )dθ2 · · · dθN (15)が満たされた時，サービス i は異常である．ここで，と表せる．ただし，J は変換のヤコビアンであり，実

xth は
Z ∞

成り立つことより，J は θ N −2 と θ に依存しない部分

験的に |θ| ¿ 1 が成り立つと仮定すると，sin θ ' θ がduN (x) = pc .

との積の形となる．したがって，θ に依存する部分は

xthp(θ) ∝ eκ cos θ θN −2の解である．ただし，pc は危険域境界 (< 1)，N (x)は標準正規分布である．

22のように書ける．これを z(t) ' θ2 , cos θ ' 1 − θ2 を

5. 3 システム全体の異常検出
次に，システムを全体的に見た場合の異常発見について述べる（注 6）．活動度ベクトルの時系列について，
システム全体としての異常度 z(t) を次のように定義する．

介して z に変数変換すると，結局，z についての確率
分布が，

h z i N −1
q(z|N, Σ) ∝ exp −z 2 −12Σ(16)のように求まる．ここで，θdθ = dz という関係を用

z(t) ≡ 1 − r(t)T u(t),(12)

ここで，r(t) は時刻 t における典型的な活動パターンであるとする．z(t) は，活動度ベクトルが時刻 t における典型的なパターンに直交する場合，z(t) は 1 となり，一致する場合 0 となる．

r(t) を計算するために，まず U(t) をU(t) = [u(t − k), u(t − 2k), · · · , u(t − W k)] ,(13)い，また，1/(2κ) を Σ とおいた．この関数は，本質的には，自由度 N − 1 の χ2 分布と同じである．
このモデルは，角分散 Σ に加えて，N というパラメータを含む．我々のモデル化の次の重要なステップ
は，N をフィッティングパラメータとしての「有効次元」n で置き換える，というものである．χ2 分布を含むガンマ分布族では，パラメータ推定にいわゆるモーメント法が有用であることがよく知られている．すな
わち，z の 1 次と 2 次のモーメントは，パラメータ n

とおく．ここで W は考慮する時間枠の大きさ，r(t)は U(t) の最大固有値をもつ左特異ベクトルとする．
この異常度を，危険域境界のような普遍的な数値と関係付けるために，u についてのパラメトリックなモデルを考えてみる．u はいわゆる方向データであるから，エントロピー最大原理の見地からもっとも自然なモデルは次の von Mises-Fisher 分布である [13]．

p(u|κ, —) =

κ

N −1
2

(2π)N/2 I N −1 (κ)“”
exp κ—T u (14)2

ここで Im (·) は m 階の第 1 種の変形ベッセル関数，

1/κ > 0 は角分散と呼ばれる定数，N は方向データ uの形式的な次元である．— は方向ベクトルの平均方向
で，われわれの文脈では r(t) と等値される．
（注 6）：詳細は，[5] を参照されたい．

および Σ とhzi = (n − 1)Σ, hz 2 i = (n2 − 1)Σ2

(17)のように結ばれている．ただし a = 1, 2 に対して

hz a i ≡Rz a q(z|n, Σ)dz である．これらはパラメータn と Σ について逆に解ける：
n−1=

2hzi2
hz 2 i − hzi2

, Σ=

hz 2 i − hzi2
．
2hzi

(18)

右辺のモーメントについては恒等式
t1Xz(t) =
t i=1

„
«
t−1
1
1 X
1
1−
z(i) + z(t)t t − 1 i=1tにおいて，1/t を忘却率 β と読み替えることにより，

hzi(t) = (1 − β)hzi(t−1) + βz(t)(19)
9電子情報通信学会論文誌 2006/2 Vol. J89–D No. 2

whole systemzeach service

service activity

each
dependency

Fig. 5coarse

SCRs

6. 実

験

この章では，提案した異常検出手法の検証を，ベンscale

チマークシステムを用いて検証を行う．実験は大きく
fine

分けて 2 つの部分から構成されている．まず，直接の依存関係を発見する手法の精度を検証し，次に，発見

図 5 階層的な異常検出
Hierarchical view of problem detection

された依存関係に基づく異常検出フレームワークの有効性を検証する．

hz 2 i(t) = (1 − β)hz 2 i(t−1) + βz(t)2

6. 1 実 験 環 境(20)の よ う に 容 易 に オ ン ラ イ ン 化 で き る ．当 然 β は

0 < β < 1 の範囲で選ぶ．これはデータ点の数の逆数に対応するので，興味ある時間スケールと行列生成間隔を元に，値を選択することができる．
われわれの第 3 の異常判定基準は次のようになる．
基準 3: システムは，

z(t) > zth (t)実験環境として，我々は図 6 に示すような 3 層のWeb ベースのシステムを，IBM HTTP Server 1.3.26，
IBM WebSphere Application Server 5.0.2，及 び IBM
DB2 Universal Database Enterprise Server Edition Version 8.1 を用い構築し，この上で Trade3 [14] と呼ばれる，オンラインの株売買サイトをシミュレートする

end-to-end のシステムパフォーマンス・ベンチマークを稼動させた．
システムは概ね以下のように動作する．まず，HTTP
サーバーはユーザーからのリクエストを受け付けると，が満たされた時異常である．ただし zth (t) はZ ∞これをアプリケーションサーバーに転送する．アプリ
ケーションサーバーの上では，サーブレットと JSP がdz q(z|n, Σ) = pc .
zthの解である．パラメータ n と Σ は各時刻 t で計算された値を使う．

動いており，これらがリクエストを処理し，必要に応じて EJB のメソッドを呼び出す．そして，呼ばれた

EJB は，JDBC コールを行うことでデータベースとのやり取りを行う．アプリケーションは，‘login’，‘home’，

5. 4 階層的な異常検出の枠組み‘account’，‘update profile’，‘quote’，‘portfolio’，‘buy’，

以上の手法に基づき，我々は図 5 に示すような階層‘sell’，‘register’ および ‘logout’ の 10 種類の値のうち的な障害検出の枠組みを提案する．この枠組みでは，のどれかの値をパラメータとしてもつ．それぞれの値

システム全体，サービスレベル，依存関係レベルでのはユーザーのとることのできる行動に対応しており，

3 段階の抽象度でシステムを捉え，次のような手続き

例えば，HTTP サーバーに対してパラメータのどれかで，それぞれのレベルでの異常検出を行なう．まず，の値をもつ HTTP リクエストを送ることによってシス最上段ではシステム全体を大まかに捉えるような異常

テムへのログインや，株の購入，価格や自分のポート度を計算する．ここで異常が検出される (基準 3) と，フォリオの照会などを行うことができる．サービスは，一段下がって，それぞれのサービスについての異常度

例えば (ip1 , 80, HTTP, /trade/app?action=login) のようを検証する (基準 2)．問題のあるサービスが特定されに (“IP アドレス”, “TCP ポート番号”, “プロトコル”,

ると，更に一段下がって，そのサービスに関連する依“パラメータ”) によって定義した．我々のアプリケー

存関係を調べ問題箇所を特定する (基準 1)．このようションでは，全部で 23 のサービスが観測された．図 6に，まずは大きな視点から問題の発生を検出し，次第における矢印はこれらのサービスを表している．

に詳細を掘り下げていくという自然な問題解析を自動

全ての実験において，対象の Web アプリケーショ

化することができる．また，この枠組みは，複数の依ンに対して同時に複数のユーザーのアクセスをシミュ

存関係の絡み合いを纏めあげ，適切なレベルでの警告

レートする仮想的なワークロード生成器を用いて，をあげる効果があることに加え，多数の依存関係を個HTTP サーバーへのリクエストを生成した．同時にア

別に監視している際にするだけでは，頻繁に上がってクセスする仮想的なユーザーの人数を変化させるこきてしまう偽の警告を抑える効果も期待できる．

とで，ワークロードを変化させた．また，トランザク

10論文／ネットワークデータを用いた分散システムにおける異常検出
Application
Server1

Database

Clients…

…

Service call ratio

HTTP
Serverindep(Gupta)
indep(prop1)
indep(prop2)
dep(Gupta)
dep(prop1)
dep(prop2)

0.8
0.6
0.4
0.2
0
0

図 6 対象となる 3 層構造 Web システムと，定義される
サービス
Fig. 6 Target 3-tier system and services defined in Trade3 application

1

Probability

2

3

4

5

6

7

Intensity [requests/sec]

図 8 2 つのサービスの間のサービス呼び出し割合
Fig. 8 Service call ratios between two services

度を検証する．図 8 において，‘indep’ とラベル付けさ

r-value (true ψ)estimated ψ

0.8

1

れたグラフは S1 と S2 の間のサービス呼び出し割合の推定値を，‘dep’ とラベル付けされたグラフは S10 =(ip1 ,0.680, HTTP, /trade/app?action=home) と S2 との間のサー0.4

ビス呼び出し割合の推定値を示している．‘Gupta’ と0.2

ラベル付けされたグラフは Gupta ら [1] による r 値から r · ](S2 )/](S1 ) によって計算されるサービス呼び

0
0

1
2
3
4
5
Intensity of S1 [requests/sec]

6

図 7 偶然の包含確率の推定
Fig. 7 Estimated probabilities of accidental containments

出し割合の値を，‘prop1’ とラベル付けされたグラフ
は提案手法によって推定された包含確率 ψ を用いて

r0 = (r − ψ)/(1 − ψ) によって補正された r 値に基づ
くサービス呼び出し割合の値を示している（注 7）．また，ション情報は 3. 章で述べた仕組みを用いて，ネットワークを流れるデータから復元した．

6. 2 依存関係の発見
まずは，異常検出において用いられる直接の依存関係発見手法の精度を検証する．
まず，お互いに依存関係のないサービスの組に対し，(2) によって定義される偶然による包含確率 ψ と，(1) によって定義される，データから計算された包含確率 r を比較する．お互いに依存関係のないサービスの組に関しては，r は真の偶然による包含確率に一致することに注意する．図 7 は，お互いに依存関係がないことがわかっている S1 =(ip1 , 80, HTTP, /trade/app?action=portfolio)
および S2 =(ip2 , 9081, HTTP, /trade/app?action=home)の組に対する比較結果を示す．ワークロードが上昇するに従って偶然による包含確率 (r-value (true ψ) で示された点)，すなわち偽の依存関係が大きくなっていく
ことがわかる．また，我々の推定 (estimated ψ で示された点) はワークロードが上昇しても，よい精度であることが確認できる．
次に，推定された偶然による包含確率を，競合モデ
ルに用いた場合のサービス呼び出し割合の推定値の精‘prop2’ とラベル付けされたグラフは直接の依存関係の制約 (3) を取り入れた競合モデルによるサービス呼び出し割合の値 (9) を示している．S10 ⇒ S2 の真の値は 1 であり，いずれの手法も非常によい精度であることが確認できる．しかしながら，依存関係のない S1と S2 の場合，真のサービス呼び出し割合は 0 であるが，Gupta ら [1] の手法ではワークロードが高くなる
につれ偶然の包含による悪影響が見られる．一方，推定された包含確率 ψ を用いて補正を行うことによって，サービス呼び出し割合の値が大幅に改善されていることが分かるが，さらに競合モデルを導入することによって，さらに改善されることが確認できる．
なお，ここでは，2 つの依存関係の例のみを示したが，他のサービス同士の組に対しても，同様の傾向が確認された．

6. 3 異常検出と異常個所の特定
次に，提案手法の異常検出能力の検証を行う．そのために，我々は Trade3 のアプリケーションに，ある時点でサーブレットに Runtime Exception が発生するという人工的な問題を仕掛けた．サーブレットは（注 7）：真の包含確率を r 0 としたときの関係 r = r 0 + ψ − r 0 ψ より．

11

電子情報通信学会論文誌 2006/2 Vol. J89–D No. 2−4

anomaly metric[×10 ]

1.5
1

10

0.5

5

0
0
50

100

20

図 10 時刻 t = 104 分における γ の値
Fig. 10 The γ value at t = 104

time [min]Fig. 910service index0

図 9 システム全体での異常度と閾値Time dependence of the anomaly metric and its threshold.

Exception を受け取ると，壊れた HTTP ページをユー

weight0.3

0.2

ザーに対して返す．このタイプの問題では，各サービ
スはエラーを返さずログには通常モードでもあまりに50

多くの Runtime Exception が出るため，リターンコー
ドやログを監視する方法では検出するのが困難である．
従って，システム管理者はしばしばユーザーからのクレームを受けてはじめて障害の発生に気づくという事態がしばしば起こる．障害発生によって，サーブレッ
トは Exception を処理するために内部での実行パスを変更し，これは続いて呼び出されるサービスの頻度の変化を引き起こすため，提案手法は，この手の障害をうまく検知できることが期待できる．

100
time [min]図 11 19 番目のサービス活動度の時間変化と異常判定の閾値
Fig. 11 The activity of service 19 and its threshold for anomaly
detection

刻 t = 104 分におけるγi ≡|ui (t) − µi |σi (t)xthの値を示している．上限の閾値か下限の閾値をオー

我々は，図 5 に示されるように，まずはシステム全

バーすると，γi > 1 となり，そうでないときには体を巨視的な特徴量で見ることによって異常の発生を

0 < γi < 1 となることに注意する．19 番目のサービ検出し，次第に細かく見ていくことで，問題の箇所をスにおいてのみ，γ の値が非常に高い値を示しており，特定するというシナリオに従い，リアルタイムで障害

このサービスにおいて何らかの異常が起こっているこを検出する実験を行った．

とが示唆される．また，図 11 は，このサービスの活システムに対しては毎秒平均 8.28 の HTTP サーバー

動度を時間変化で見たものである．図の中には点線でへのリクエストを発生させ，開始から t = 104 分後に上下限の閾値を示しているが，t > 102 において，下障害を発生させた．また，サービス呼び出し割合行列

限の閾値を下回っていることが確認できる．また，トC とサービス頻度行列 F は，2 分毎に，2 分間集計しラフィックのバースト的な性質にも関わらず，正常時た値から計算し，出力させた．また，その中で用いらにおける活動度は比較的安定していることもわかる．

れる偶然の包含確率の推定値 ψ (2) は，最近の 2 分間

この結果からも，個別のガウス分布による仮定の有効のデータから計算した．

性がわかる．19 番目のサービスは (ip2 , 9081, HTTP,

まず，我々はシステム全体としての異常度 z の値と，/trade/app?action=home) で指定されるサービスであり，その閾値をリアルタイムで計算した．パラメータとし

従って，このサービスへの呼び出しか，あるいは，こては，W = 10，β = 0.01，pc = 0.01 のように定めのサービスによる呼び出しに関連する箇所に異常があた．図 9 にその結果を示す．最後の 3 時点で，z の値

るのではないかということが推測される．

が zth の値を超えているのが分かり，ここで何らかの

最後に，サービス呼び出し割合の行列において，異常が発生したことを示している．また，閾値をリア

サービス呼び出し割合の行列においてサービス (ip2 ,ルタイムで計算しているので，z の値が一旦高くなっ

9081, HTTP, /trade/app?action=home) が呼び出していたあとは，zth の値も上昇していることが分かる．

る列（第 19 列）と，呼び出されている行（第 19 行）

次に，異常の発生しているサービスを特定するため，を調べることで，さらに詳細に問題のある箇所を特定基準 2 に従い，サービス活動度を調べた．図 10 は，時する．図 12 にはそのうち二つの要素の時間変化を示

12

service call ratio

論文／ネットワークデータを用いた分散システムにおける異常検出

複数の箇所において異常が検出されるような場合にも0.3

階層的な異常検出法によってさらに候補を絞りこむこ
0.2とができることも示唆される．

0.1

c23,19c2,19

7. 関 連 研 究

0
0

40

80

time [min]図 12 19 番目のサービスに関連するサービス呼び出し割
合の時間変化と異常判定の閾値Fig. 12 The service call ratios related to service 19 and theirthreshold for anomaly detection

依存関係情報は静的な依存関係と動的な依存関係の2 つのカテゴリーに分類することができる．静的な依存関係システムの設定や，インストール時のデータ，
あるいは，コードなどを解析することで発見される．

Kar ら [15] は，ソフトウェア・コンポーネント間の静的な依存関係を，レポジトリから自動的に抽出する方法を提案している．しかしながら，多くのコンポネン
トは実行時に動的にバインドされ，また依存関係は環境の時間とともに変化するため，このような方法は，実行時における動的な依存関係を見つけるためには使うことができない．
動的な依存関係を発見するためには，システムの動作に関する情報を稼動時に集め，解析するような手法

図 13 サービス呼び出し割合のみに基づく異常報告数
Fig. 13 The number of alerts only based on service call ratiosが必要となる．このような目的を達成するために，特殊な計測の仕組みを用いて行うような方法がいくつか存在する [6], [16], [17] が，これらの方法は対象のシしているが，c19,23 要素において，t > 102 で閾値をステムに負荷をかけてしまうという欠点がある．時に

下回っていることがわかる．これは，サービス (ip2 ,は，システムにあまり負荷をかけずに簡単に採取でき

9081, HTTP, /trade/app?action=home) の呼び出しているデータから，依存関係を推定する手法 [1], [18] の方

るサービス (ip3 , 50000, DRDA, TRADE3DB) に対応しが望ましい場合もある．例えば，Ensel [18] は，CPUており，すなわちこの呼び出しの部分に何か問題があ

負荷などの情報からニューラルネットワークを用いて，ることが示唆される．

動的な依存関係を推定する手法を提案している．我々

この章の初めに述べたように，サービス呼び出し頻のアプローチも，まさにこの範疇に属している．

度はサービス間の呼び出し回数そのものであり，ワー

依存関係の応用については，診断や異常個所の特定

クロードとともに増減するため，こういった推論を行などに関して，多くの研究がなされている．例えば，

うことは難しい．また，直接の依存関係でなく，間接イベント相関システム [19]〜[21] では，アラートやイ的な依存関係を用いると，一箇所の障害が，障害箇所

ベント情報を集計し，依存関係における対応箇所にを経由する間接的な依存関係すべてに影響するため，マッピングすることで，問題箇所の特定を行う．また，障害箇所の特定が困難になってしまう．

他にも，依存関係の情報をもとにして，プローブやテ

また，図 13 は，階層的な異常検出によらず，5. 1 節

スト用のトランザクションを設計し，効率よく問題箇のサービス呼び出し割合の行列の要素のみに基づいて所を特定するような試みもある [22], [23]．Hellerstein

異常検出を行った場合に異常が報告される回数を各時

ら [24] は，データマイニング手法を用いることで，対間においてカウントしたものである．各要素のみに注象システムより得られたイベント系列から，特徴的

目するような検出方法では正常時にも偽の異常が検知なパターンを発見する試みを行っている．また，Maされていることがわかる．階層的な異常検出法はこのら [25] はイベントやパターンを視覚化し，ユーザーのような偽情報を排除するという利点があることが示さ

問題解析を助けるシステムを開発している．本論文でれている．一方，実際に異常が起こった t = 104 付近

我々が提案した手法は，相関ルール発見 [26] や系列パ

では，16 番や 21 番のサービスに関連するサービス呼ターン発見 [27] の一種であるという見方もできる．本

び出し割合にも異常が検出されていた．このように，論文では 2 つのサービスの組の依存関係の発見のみに
13電子情報通信学会論文誌 2006/2 Vol. J89–D No. 2

注目して議論したが，この考え方は 3 つ以上のサービの包含関係が失われてしまうこととなるが，パケットスの組にも自然に一般化できる．

ロスに対してよりロバストな推定手法を開発すること

近年，ネットワークのトラフィック解析などにおいも今後の課題といえる．また，本論文では異常検出のて，変化点検出手法の有効性を示す研究がなされてい閾値決定に正規分布を用いたが，これは正常時のシス

る [3], [4]．Hajji [10] は Yamanishi ら [11], [12] と同じテムが安定動作しているときには比較的正しく，1 回

く，確率モデルを用いた LAN における異常検出のアプの異常検出，すなわち異常が検出されるまでモデルがローチを提案しているが，1 観測点のみでの低い層に正しければある程度は目的が達成されるような状況におけるデータを対象としている．これらの研究は主においてはうまく働くことが経験的にわかっているが，ネットワークの低い層における非常に集約されたデーより複雑なシステムや現実のトラフィックにおいて，

タを対象にしているのに対し，我々の手法はより抽象

異常時，特にバースト性やサスペンドなどの現象が起度の高い層，とくに Web ベースのシステムにおけるこっている場合に，どこまで我々の仮定が成立するか

アプリケーション層を対象としている．Thottan ら [9]は明らかではなく，これを見極めることは今後の課題

は，複数観測点におけるデータを AR モデルによってである．

関係付ける興味深い方法を提案している．

8. お わ り に文[1]

lem determination”, Proc. 14th IFIP/IEEE Int. Workshop on Dis-に発見する技術を考察した．また，この目的のためにtributed Systems: Operations and Management, Vol. 2867 of
LNCS, Springer, pp. 221–232 (2003).

(i) 対象のシステムに殆ど負荷をかけることなく採取で[2]Royal Statistical Society, B, 39, pp. 1–38 (1977).
[3]

Workshop on Internet Measurment, pp. 71–82 (2002).
[4]

案した．また，実験システムを用いてこれらの手法の有効性の検証を行った．

Knowledge Discovery and Data Mining (2004).
[6]tific Computing, Academic Press (1990).
[8](2000).
[9](2003).
[11]

ing learning algorithms”, Proc. 6th ACM SIGKDD Int. Conf. on

フィック量が多くなりミラーポートの許容量 (例えば 1の手法では，パケットロス率にほぼ比例した形で本来
14

K. Yamanishi, J. Takeuchi, G. Williams and P. Milne: “On-line
unsupervised outlier detection using finite mixtures with discount-手法などが必要になっていくと思われる．また，トラ取得することができなくなってしまう点である．現在

H. Hajji: “Baselining network traffic and online faults detection”,
Proc. IEEE Int. Conf. on Communications, Vol. 1, pp. 301–308

ある．未知のプロトコルの解析を助けるツールや，未Gb/s) を超えてしまうと，通過するすべてのデータを

M. Thottan and C. Ji: “Anomaly detection in IP networks”, IEEE
Trans. Signal Processing, 51, 8, pp. 2191– 2204 (2003).

[10]

トコルを使用している場合，その作成は非常に困難で知のプロトコルを自動でクラスタリングし，分類する

M. Sato and S. Ishii: “On-line EM algorithm for the normalized gaussian network”, Neural Computation, 12, 2, pp. 407–432

付けるような方法が有効である可能性がある．また，ければならないが，対象となるサービスが未知のプロ

A. O. Allen: “Probability, Statistics, and Queuing Theory with
Computer Science Applications”, Computer Science and Scien-

る．しかしながら，通信の内容をもとに，これらを紐プロトコル解析モジュールはプロトコル毎に準備しな

OpenGroup Technical Standard C807: “Systems management:
Application response measurement” (1998).

[7]

合には，やはり複数の観測データを統合する必要があり，3. 章で述べたような時刻の同期が問題となってく

T. Idé and H. Kashima: “Eigenspace-based anomaly detection
in computer systems”, Proc. 10th ACM SIGKDD Int. Conf. on

アプローチは，複数のノードを同時に監視できるというメリットがあるが，更に広域にわたるシステムの場

H. Wang, D. Zhang and K. G.Shin: “Detecting SYN flooding attacks”, Proc. IEEE INFOCOM 2002, pp. 1530 –1539 (2002).

[5]

今後の研究の方向として，いくつかの可能性を挙げることができる．我々のネットワークデータを用いる

P. Barford, J. Kline, D. Plonka and A. Ron: “A signal analysisof network traffic anomalies”, Proc. Second ACM SIGCOMMを推定する新しい手法，および (iii) 発見された依存関係を基にした，階層的な異常検出の枠組みの 3 つを提A. P. Dempster, N. M. Laird and D. B. Rubin: “Maximum likelihood from incomplete data via EM algorithm”, Journal of the

報を抽出するシステムと，(ii) 得られたトランザクショ
ンの実行期間をもとに，サービス間の直接の依存関係

M. Gupta, A. Neogi, M. K. Agarwal and G. Kar: “Discovering dynamic dependencies in enterprise environments for prob-

本論文で我々は分散システムにおける異常を自動的

きるネットワークデータから，トランザクションの情

献Knowledge Discovery and Data Mining, pp. 320–324 (2000).
[12]

K. Yamanishi and J. Takeuchi: “A unifying framework for detecting outliers and change points from non-stationary time series
data”, Proc. 8th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pp. 676–681 (2002).

論文／ネットワークデータを用いた分散システムにおける異常検出[13]K. Mardia, J. Kent and J. Bibby: “Multivariate Analysis”, Academic Press (1980).

[14]

IBM: “Trade3; http://www-306.ibm.com/software/[15]

G. Kar, A. Keller and S. Calo: “Managing application services

webservers/appserv/benchmark3.html”.

= −T ∈D(Sj )Q

over service provider networks: Architecture and dependency
analysis”, Proc. 5th IFIP/IEEE International Symposium on Integrated Network Management (IM V) (2000).
[16]

workload”, IBM Syst. J., 36, 2, pp. 242–283 (1997).
[17]

M. Y. Chen, E. Kiciman, E. Fratkin, A. Fox and E. Brewer: “Pin-Q

ψ(S 0 , Sm )S 0 ∈P (T )\Si

ψ(S 00 , Sm )S 00 ∈P (T )\Sk

· “PS∈P (T ) ρ(S, Sm )J. Aman, C. K. Eilert, D. Emmes, P. Yocom and D. Dillenberger:“Adaptive algorithms for managing a distributed data processing∂2L∂ρ(Si , Sj )∂ρ(Sk , Sl )X
δ(Si ∈ P (T ))δ(Sk ∈ P (T ))[H](i,j),(k,l) =Q
S 0 ∈P (T )\S”2 ，
ψ(S 0 , Sm )そのほかの場合には [H](i,j),(k,l) = 0 と書ける．
従って，point: Problem determination in large, dynamic internet services”,
Proc. Int. Conf. on Dependable Systems and Networks (2002).
[18]

C. Ensel: “New approach for automated generation of service dependency models”, 2nd Latin American Network Operation and[Hm (T )]j,l := δ(Si ∈ P (T ))δ(Sk ∈ P (T ))YY·
ψ(S 0 , Sm )
ψ(S 00 , Sm ).
S 0 ∈P (T )\Si

Management Symposium, LANOMS (2001).
[19]

S. A. Yemini, S. Kliger, E. Mozes, Y. Yemini and D. Ohsie: “Highで 定 義 さ れ る Hm (T ) が ，∀m = 1, 2, . . . , |Σ| とspeed and robust event correlation”, IEEE Commun. Mag., 34, 5,∀T ∈ D に対し，半正定であることを証明すれば

pp. 82–90 (1996).
[20]

S 00 ∈P (T )\Sk

J. Choi, M. Choi and S. Lee: “An alarm correlation and fault identification schema based on OSI managed object classes”, Proc.

よい．

Hm (T ) は以下のように分解される．

IEEE Int. Conf. on Communications, pp. 1547–1551 (1999).
[21]

B. Gruschke: “Integrated event management: Event correlation using dependency graphs”, Proc. 9th IFIP/IEEE International
Workshop on Distributed Systems Operation and Management(1998).

[22]

Hm (T ) = hm (T )h>m (T ),>
hm (T ) := (h1m (T ), h2m (T ), . . . , h|Σ|m (T )) ,Y
him (T ) := δ(Si ∈ P (T ))ψ(S 0 , Sm ).

J. Gao, G. Kar and P. Kermani: “Approaches to building self heal-

S 0 ∈P (T )\Si

ing systems using dependency analysis”, Proc. IEEE/IFIP Network Operations and Management Symposium (NOMS) (2004).

従って，∀x ∈ R|Σ| に対し，

to appear.
[23]

M. Brodie, I. Rish and S. Ma: “Optimizing probe selection forx> Hm (T )x = (x> hm (T ))2 >=0fault localization”, Proc. 12th IFIP/IEEE International Workshop
on Distributed Systems: Operations and Management (DSOM01)(2001).
[24]

であることから Hm (T ) は半正定であることがわかる．
（平成 17 年 XX 月 XX 日受付，XX 月 XX 日再受付）

J. L. Hellerstein and S. Ma: “Mining event data for actionable patterns”, Proc. 26th Int. Computer Measurement Group Conference,
pp. 307–318 (2000).

[25]

S. Ma, C. Perng and J. L. Hellerstein: “Eventminer: An integrated
mining tool for scalable analysis of event data”, Proc. Visual Data
Mining Workshop, pp. 1–9 (2001).

[26]

[27]

鹿島

久嗣

R. Agrawal, T. Imielinski and A. N. Swami: “Mining asso-

1999 年京都大学工学研究科応用システ

ciation rules between sets of items in large databases”, Proc.

ム科学専攻修士課程修了．同年日本アイ・

1993 ACM SIGMOD International Conference on Management

ビー・エム（株）入社．東京基礎研究所にof Data, ACM Press, pp. 207–216 (1993).

所属．機械学習，データマイニングの研究

R. Agrawal and R. Srikant: “Mining sequential patterns”, Proc.

に従事．

11th Int. Conf. on Data Engineering, IEEE Computer Society, pp.
3–14 (1995).

付

録

津村

直史

2003 年大阪大学大学院工学研究科電気電1. 定理の証明

子情報エネルギー工学専攻修士課程修了．

トランザクション履歴 D に対する対数尤度の和 L

同年日本アイ・ビー・エム（株）入社．東のヘッセ行列 H が，半負定であることを証明する．

京基礎研究所に所属．オートノミックコン

H は， j = l := m に対して

ピューティングの研究に従事．

15

電子情報通信学会論文誌 2006/2 Vol. J89–D No. 2

井手

剛

（正員）

2000 年東京大学大学院理学系研究科物理学専攻修了．博士（理学）．同年日本アイ・
ビー・エム（株）入社．現在，東京基礎研究所にて実数値データに対するマイニング技術の研究に従事．2004 年人工知能学会全国大会優秀賞．電子情報通信学会，情報処
理学会，人工知能学会，日本物理学会，ACM SIGKDD 各会員．

野ヶ山尊秀

（正員）

2004 年電気通信大学工学研究科電子情報学専攻博士前期課程了．同年日本アイ・
ビー・エム（株）入社．東京基礎研究所に所属．オートノミックコンピューティングの研究に従事．

平出

涼2002 年東京工業大学総合理工学研究科

物理情報システム創造専攻修士課程修了．
同年日本アイ・ビー・エム（株）入社．東京基礎研究所に所属．オートノミックコン
ピューティングの研究に従事．

江藤博明

1985 年東京工業大学工学研究科情報工学専攻修士課程修了．同年日本アイ・ビー・
エム（株）入社．東京基礎研究所に所属．
最適化，セキュリティ，オートノミックコ
ンピューティングなどの研究に従事．

福田剛志

1991 年早稲田大学大学院理工学研究科修士課程修了．同年日本アイ・ビー・エム (株)東京基礎研究所入所．データマイニング，
オートノミックコンピューティングなどの研究に従事．現在，大和ソフトウェア開発
研究所情報マネジメント製品開発担当．博士（情報科学）．日本データベース学会，情報処理学会，ACM,
IEEE CS 各会員．

16

Abstract We introduce a network-based problem detection framework for distributed systems, which includes adata-mining method for discovering dynamic dependencies among distributed services from transaction data collectedfrom network, and a novel problem detection method based on the discovered dependencies. From observed containments of transaction execution time periods, we estimate the probabilities of accidental and non-accidental containments,
and build a competitive model for discovering direct dependencies by using a model estimation method based on an
on-line EM algorithm. Utilizing the discovered dependency information, we also propose a hierarchical problem detection framework, where microscopic dependency information is incorporated with a macroscopic anomaly metric thatmonitors the behavior of the system as a whole. This feature is made possible by employing a network-based design
which provides overall information of the system without any impact on the performance.
Key words problem detection, network data, distributed system, EM algorithm