スライド 1

Tokyo Research Laboratory
3F3-05
固有空間における
コンピュータシステムの障害検知
IBM東京基礎研究所
井手剛・鹿島久嗣
© Copyright IBM Corporation 2003
Tokyo Research Laboratory
背景
 コンピュータシステムの障害検知の特徴
複数サーバが連係動作する場合、障害検知が困難
 グラフ時系列からの知識発見とみなせる

 データマイニングの新しい方向性
空間方向への拡張：グラフマイニング
 時間軸方向への拡張：ストリームマイニング

人工知能学会全国大会2004 | 2004/06/04 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
Web系システムのモデル化－定義
 サービス


（要求元、要求相手、ポート番号、アプリ種）
二つのIPアドレスを含んでいることに注意。
HTTP
p1

あるサービスが別のサービスを単位時間に何
度呼んだか
対数変換して対称化
 サービス関連度グラフ


サービスを頂点、サービス関連度を辺の重み
とするグラフ
無向グラフとして定義
p2
DB
p3
i2
 サービス関連度

WAS
i4
i1
HTTP
p1
WAS
p2
s3  (i1 , i2 , p1 , q1 )
s4  (i1 , i3 , p1 , q1 )
i3
s7  (i2 , i3 , p2 , q1 )
s3
s9  (i3 , i2 , p2 , q1 )
s10  (i2 , i4 , p3 , q2 )
s11  (i3 , i4 , p3 , q2 )
s x  (i2 , i2 , p2 , q1 )
s10
sx
s7
s9
s4
s11
sy
s y  (i3 , i3 , p2 , q1 )
人工知能学会全国大会2004 | 2004/06/04 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
Web系システムのモデル化－具体例と特徴
 グラフの辺の重みの時間変動は激しい

サービスの実例
数十分程度の範囲では自己回帰モデルは無理
 グラフの辺の数はそれなりに多い

50種のサービスがあれば1000以上のサービス関
連度。
 グラフの頂点同士の相互関係が現象に本質的

そうやってシステムが動作している。
サービス9から11への呼び出し回数
回/20秒
人工知能学会全国大会2004 | 2004/06/04 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
Web系システムのモデル化－問題設定
 解かれるべき問題
時系列にサービス関連度グラフが与えられる。
 そのグラフ列から、教師データなしで、異常を検出せよ。

実用上の要請
素人可読性
1. ある程度わかりやすい特徴量を使って、
2. 系についての詳細な事前知識を前提とせずに、
3. 従来検知が難しかった障害を見つけたい。
人工知能学会全国大会2004 | 2004/06/04 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
特徴抽出－定義
 「サービス活動度ベクトル」

定義：

すなわち、サービス関連度行列の、最大固有値に属する規格化された固有ベクトル
解釈１「サービスの活動度」
他のサービスを活発に呼び出し
ている（呼び出されている）よう
なサービスにおいて重みが強く
なる
人工知能学会全国大会2004 | 2004/06/04 |
解釈２「コントロールトー
クンの保持確率」
サービス関連度行列に従っ
て時間発展する力学系の
定常状態
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
特徴抽出－数学的に言えること
 活動度ベクトルはトラフィックの一様な変化に不変
 活動度ベクトルは正ベクトルである
 活動度ベクトルに縮退はない
Perron-Frobenius
グラフが非連結の場合
各部分グラフに対して活動度
ベクトルを定義できる
• 活動度に基づく自然なクラスタリング
• サービス数に対するスケーラビリティ
人工知能学会全国大会2004 | 2004/06/04 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
異常の検知
 方向データ（directional data）の外れ値検出問題
「異常度」をどう定義するか
異常の判定をどうするか
コサイン尺度として定義


u(t) : 時刻 t での活動度ベクトル
r(t-1) : 時刻 t-1 の時点での代表パターン
u(t)
r(t-1)
代表パターンはKL展開により抽出
Karhunen-Loeve
人工知能学会全国大会2004 | 2004/06/04 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
手法のまとめ
Web系システム
隣接行列
特徴ベクトル
t
D
t -W
t-1
t -2
t-2 t -1 t
...
...
相違度
の評価
過去の典型
パターン
u (t)

r (t-1)
人工知能学会全国大会2004 | 2004/06/04 |
現在の
パターン
r (t-1)
パターン抽出
u(t )
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
実験－アプリケーションの一方にバグを仕込む
 舞台設定



2つのWASそれぞれの上で２つのアプリケーションを動作させる（花屋と株屋）
20秒おきにサービス関連度行列を出力
主固有クラスターに注目（12個のサービスが存在）
 仕込んだバグ



ある時刻において、花屋の一方がディスク書き込み不能で固まるようにする
プロセス自体は正常に存在しているが、動作自体が妙。
冗長化されているので、トラフィックが小さいうちはユーザも異常を感じないはず。
HTTP
p1
WAS
p2
DB
p3
i2
負荷生成
i4
i1
HTTP
p1
WAS
p2
i3
人工知能学会全国大会2004 | 2004/06/04 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
実験－結果
 計算


関連度グラフから活動度ベクトルを求め、さら
に異常度zを計算
zに対して閾値を更新
 活動度ベクトル


明瞭に異常区間を可視化している
ひとつのアプリケーションの機能不全が、リン
クをたどって他の活動度に影響
time [min]
 異常度


異常度に二つの大きなピーク
• 機能不全の発生（tA）と終了（tB）
• 閾値により自動検出
後者はオンライン学習が機能している証拠
人工知能学会全国大会2004 | 2004/06/04 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
まとめ
 冗長化されたWeb系システムの振る舞いをサービス関連度行列で表現した。
 特徴量として主固有ベクトルを取れば系の動態を要約できることが分かった。
 系の異常検出問題を、方向データの時系列の外れ値検出問題に帰着させた。
 「外れ度」の統計的振る舞いを記述するためのオンライン更新式を導いた。
 従来困難であったアプリケーション層の障害検知に成功した。
省略箇所および詳細はフルペーパー版を参照願います（8月下旬公開）。
T. Ide and H. Kashima, “Eigenspace-based Anomaly Detection in Computer
Systems,” to appear in Proc. 10th ACM SIGKDD, 2004.
人工知能学会全国大会2004 | 2004/06/04 |
© Copyright IBM Corporation 2004

Download Report