Web系システムからの特徴抽出とオンライン障害検知手

Tokyo Research Laboratory
特別セッション２：システムプラットフォーム・インテリジェンス
Web系システムからの特徴抽出と
オンライン障害検知手法
IBM東京基礎研究所
井手剛・鹿島久嗣
© Copyright IBM Corporation 2003
Tokyo Research Laboratory
話の構成
 研究の背景
 論点の整理
 Web系システムのモデル化
 問題設定
 特徴抽出
 異常の尺度
 閾値の設定
 実験
 まとめ
Page 2
IBIS 2004 | 2004/11/08 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
研究の背景 1/3
アプリケーション層での異常を「オートノミック」なやり方で検知したい
 コンピュータシステムの障害検知、特にアプリ層の障害検知は難しい

HW自体が壊れることは少ないが、SWの不調は頻繁に起こる
 難しさの由来はどこにあるのだろう？
複数の自由度
が強く絡み合う
時間変動
が激しい
Page 3
自由度が
大きい
IBIS 2004 | 2004/11/08 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
研究の背景 2/3
コンピュータシステムの障害検知でありがちな想定
 「各端末にエージェントを仕込んで警報を出させればいい」

局所的に見てわかるのは自明な問題だけ（例：断線、プロセス停止）
 「観測量を閾値と比べて、大小関係を見れば異常がわかる」

たとえばWeb系システムだと、トラフィックの時間的変動は猛烈
自由度が
大きい
 「ポリシーを蓄積してエキスパートシステムを作ればよい」

自由度の絡み合いにより、場合の数はほぼ無限大。
 「応答時間やスループットを監視していれば障害がわかる」

冗長化構成になっているとそれも難しい（次ページ）。
複数の自由度
が強く絡み合う
時間変動
が激しい
Page 4
IBIS 2004 | 2004/11/08 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
研究の背景 3/3
冗長化されたシステム構成では更に問題は難しくなる
 例： 3層構造・2重冗長のWeb系システムの潜在的障害


アプリケーションサーバーの一方が動作不全（プロセス自体は生きている）。
設計時の想定よりもはるかに低いトラフィックでシステムダウンが起こる可能性
HTTP
WAS
DB
i2
応答時間だけで
は異常検知困難
i4
i1
HTTP WAS
Page 5
IBIS 2004 | 2004/11/08 |
i3
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
論点の整理
主要な論点は3つある
 そもそも何を観測すればいいか

部分部分の1点ではなく、何か部分同士の相関を取り込んだ量であるべき。
 全体の振舞いをとらえるために、観測量からどういう特徴を抽出すればいいか


猛烈な時間変動に対し頑強な量であるべき
システム全体の活動の縮図となるような量であるべき
 抽出された特徴に対し、いかなる異常判定基準を課せばいいか


Page 6
オンラインで学習してくれるような仕組みであるべき
熟練者の技のようなものが不要で、普遍的な量が閾値であるべき
IBIS 2004 | 2004/11/08 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
Web系システムのモデル化 1/3
「サービス」の呼び出し回数を基本量として採用する
 サービス


（要求元、要求相手、ポート番号、アプリ種）
二つのIPアドレスを含んでいることに注意。
HTTP
p1

あるサービスが別のサービスを単位時間に何
度呼んだか
対数変換して対称化


一定時間おきに関連度行列が得られると考え
る
行列に対応して、サービスを頂点、サービス関
連度を辺の重みとするグラフを想像できる
DB
p3
i4
i1
HTTP
p1
WAS
p2
s3  (i1 , i2 , p1 , q1 )
 サービス関連度行列とグラフ
p2
i2
 サービス関連度

WAS
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 )
Page 7
IBIS 2004 | 2004/11/08 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
Web系システムのモデル化 2/3
サービス呼び出しの時間変動の具体例と特徴
 サービス呼び出し回数の時間変動は猛烈

サービスの実例
数十分程度の範囲では自己回帰モデルは無理
 サービス同士の相互関係が現象に本質的

各個のサービスを独立に解析することは許されない
 サービス対の数はそれなりに多い

50種のサービスがあれば1000以上のサービス関
連度。サービス関連度行列を眺めているだけでは
何が起きているのか理解しがたい。
サービス9から11への呼び出し回数
回/20秒
Page 8
IBIS 2004 | 2004/11/08 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
Web系システムのモデル化 3/3
サービス呼び出し回数をどう求めるか
 それなりの技が必要だが、詳細省略。サービス関連度行列は所与とする。


IPパケット採取 + 推定アルゴリズム
• H. Kashima et al., “Network-based Problem Determination for Distributed Computer
Systems,” ICDE 2005, to appear.
サーバーのポーリング + 推定アルゴリズム
• M. Gupta et al., “Discovering Dynamic Dependencies in Enterprise Environments for
Problem Determination", Proceedings of 14th IFIP/IEEE Workshop on Distributed Systems:
Operations and Management, 2003.
switch
ミラー
ポート
D(t)
D(t)
D(t)
PC
Host2
Browser
Host1
IHS
WAS
DB2
Dispatcher
IHS
WAS
Host3
Page 9
Host4
IBIS 2004 | 2004/11/08 |
パケット採取によるシステム監視
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
問題設定
解かれるべき3つの問題がある。
 やりたいこと


時系列にサービス関連度グラフが与えられる。
そのグラフ列から、教師データなしで、異常を検出したい
 解かれるべき問題
問1 （特徴抽出）
問2 （異常の尺度）
問3 （閾値設定）
系全体の動態をとらえるこ
とのできる特徴量は何？
異常の尺度はどう定
義すればいい？
その異常度にどう閾値を
設ければいい？
個別の関連度の変化ではなく、システム全体の
「バランスの崩れた」状態を検出したい。
Page 10
IBIS 2004 | 2004/11/08 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
問1（特徴抽出）への解答 1/3
各サービスの「活動度」を表す量を抽出する
 サービス活動度ベクトルの数学的定義：
時刻 t での関連度行列
Dは
非負行列！
「活動度」として解釈できる理由
• 最大化のためには、例えばD12 大なら、u1
と u2 の重みも大きくなければならない。
• 従って、もしs1 が活発に他者を呼んでいる
なら、s1 の重みは大きいはず。
数学的には下記の固有値方程式と同等
特徴量 = 関連度行列Dの主固有ベクトル
Page 11
IBIS 2004 | 2004/11/08 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
問1（特徴抽出）への解答 2/3
サービス活動度ベクトルは、システムの動態の縮図である
 システムのコントロールトークンの遷移強度が、サービス関連度に比例するとする
 活動度ベクトルは、無限に時間が経過した後、行き着く先の状態を表す
サービス関連度行列
 D11 D12  D1N 
D
D22  D2 N 
21

D





D

D
NN
 N1

s1
運動方程式
x(  1)  Dx( )
定常状態
u  x() / || x() ||
u1 
u 
u 2
 
 
u N 
システムが、サービスs2の上にコントロールトークンを持っ
ている確率振幅
サービス活動度ベクトル = システムの動態の要約
s2
Page 12
IBIS 2004 | 2004/11/08 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
問1（特徴抽出）への解答 3/3
数学的にも、Perron-Frobeniusの定理が解釈の一貫性を保障
 活動度ベクトルは、トラフィックの一様な変動に対し
不変である

（正常時の）猛烈なトラフィック変動にある程度頑強
規格化された固有ベ
クトルであるため
 活動度ベクトルは正ベクトルである

負の活動度は出てこない、という意味で解釈の一貫性
が保障される
 活動度ベクトルに縮退はない

Page 13
Perron-Frobenius
の定理のため
準位交差による見かけの不安定性に悩まされることは
ない
IBIS 2004 | 2004/11/08 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
問題は、方向データ（規格化されたベクトル）の時系列からの異常検出問題
に帰着された
computer system
dependency matrix
t
t-1
t -2
activity vector
t -W
D
...
t-2 t -1 t
...
p rin c ip al
e ige nv ec to r
問1 （特徴抽出）
問2 （異常の尺度）
問3 （閾値設定）
系全体の動態をとらえるこ
とのできる特徴量は何？
異常の尺度はどう定
義すればいい？
その異常度にどう閾値を
設ければいい？
Page 14
IBIS 2004 | 2004/11/08 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
問2（異常の尺度）への解答 1/2
方向データについて最も自然な分布はvon Mises-Fisher分布である
 vMF分布＝方向データの世界の「正規」分布


最大エントロピー原理＋全確率保存＋ノルム1の拘束＝ vMF分布
ある極軸まわりの角度の揺らぎを記述
 vMF分布の下での最も自然な類似度尺度＝コサイン尺度

vMF分布のFisher kernel はコサイン尺度と一致
 異常度の定義

u(t)

r(t)
• u (t) : 時刻 t での活動度ベクトル
• r (t) : 時刻 t で定義された代表パターン
Page 15
IBIS 2004 | 2004/11/08 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
問2（異常の尺度）への解答 2/2
過去の代表パターンは特異値分解により計算できる
 過去の活動度の1次結合を考える。
u(t)
r(t)
 係数 v は例えば下記の基準で求められる

これは下記の行列 U(t ) のSVDをすることと同じ
• U = [ u (t -1), u (t -2), …, u (t - W) ]
• W：ウィンドウサイズ
t-1
 結局 r (t ) は U(t ) の左特異ベクトルとして求まる
SVD
t-W
r (t)
Page 16
IBIS 2004 | 2004/11/08 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
残る問題は、異常度に適切な閾値を与えること
問1 （特徴抽出）
問2 （異常の尺度）
問3 （閾値設定）
系全体の動態をとらえるこ
とのできる特徴量は何？
異常の尺度はどう定
義すればいい？
その異常度にどう閾値を
設ければいい？
Page 17
IBIS 2004 | 2004/11/08 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
問3（閾値設定）への解答 1/3
異常度の確率分布モデルを作りたい
 もし異常度zのうまい確率モデルが立てられれば、
閾値は比較的容易に設定できる。

zth
なお、正規分布でフィットできる余地は全然ない。
 活動度ベクトルu がvMF分布に従うと考えるの
はさほど悪くない仮定

正常時は、活動度ベクトルはおおむね安定している


p(u |  , r)  exp rT u
「これらは異常。なぜなら xx % の危険域
を越えているから。」
異常度 z(t )の分布を、vMF分布から導いてみよう
Page 18
IBIS 2004 | 2004/11/08 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
問3（閾値設定）への解答 2/3
変数変換によりzの分布を求め、「有効次元モデル」を導入する
 手順


u から角度変数に変数変換。θに対する周辺分布を出す。
θと z の関係を利用して、zに確率変数を変換
•
2
z (t ) 
u(t)

r(t)
2
 結果

zは、自由度N-1のカイ２乗分布に従う
• N：活動度ベクトルの次元（i.e. サービスの数）
 重要なステップ：形式的な次元 N を「有効次元」 n で置き換え、これをフィッティン
グパラメターとみなす。


Page 19
各自由度の挙動には一般に著しい不均一性が存在
それをならした時、「真の自由度」はいくらになるか、という問いに答えるのが有効次元
IBIS 2004 | 2004/11/08 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
問3（閾値設定）への解答 3/3
確率モデルのオンラインパラメター推定法
 二つの未知パラメターがある
有効次元
「角分散」
 通常の最尤推定は困難：モーメント法でパラメター推定

カイ二乗分布のモーメントは単純な形をしている
z   dzq( z ) z  (n  1) ,
Page 20
z

未知パラメター n と∑ について陽に解ける

モーメントをオンラインで求めるのは容易
IBIS 2004 | 2004/11/08 |
2
  dzq( z ) z  (n  1)
2
2
2
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
問1～問3への解答の要約
サービス関連
度行列
D(t)
u(t)
異常度
z(t)
z の１次と２
次のモーメ
ント
z の確率
分布
活動度
ベクトル
警告発報条件
下記を満たす
閾値 zth を計算

 dzq ( z )  p
c
z th
“0.5%”
異常を定義する（ほぼ唯一の）パラメター
Page 21
IBIS 2004 | 2004/11/08 |
危険域, pc
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
実験 1/3
実験構成。Web系システムでソフトウェア障害を起こす
 設定




3層構造の比較的簡単なWeb系システムで実験
二つあるWASの双方で、二つのアプリケーションが走っている(“Trade” と “Plants”)
サービス関連度行列は20秒おきに生成される
最も活動度の高いクラスターには12個のサービスがある。このクラスターだけに注目。
 ソフトウェア障害


“Trade”が、時刻 tA で機能不全になり、時刻 tBで回復
サーバープロセス自体は正常なので、TCP層以下の挙動は正常。
HTTP
p1
負荷生成
p2
DB
p3
i2
i4
i1
HTTP
p1
Page 22
WAS
IBIS 2004 | 2004/11/08 |
WAS
p2
i3
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
実験 2/3
異常度の確率モデルは実験をよく再現している
 システムの正常動作時に、異常度z を観測

約1時間にわたりz(t)を観測し、その頻度分布を
プロット（下図）。
 得られたz の標本から、確率分布を学習


1次と2次のモーメントを求め、有効次元と、角分
散を計算
• 結果： n = 4.6
サービスの数はN=12であったので、有効次元
はそれよりもずっと小さいことがわかる。
 我々のカイ二乗分布は実験結果をよく再現し
ている


Page 23
分位点プロット（上図）
n の代わりに N を使った場合全然ダメ
IBIS 2004 | 2004/11/08 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
実験 3/3
仕込んだバグをオンラインで検知してみる
 活動度ベクトルの時間変化



正常時はおおむね安定している
明確に異常区間が可視化されている
単一のサービス(#11)に直接関係するバグ
が大規模な変化を引き起こしている
 異常度の時間変化

障害区間の開始と終了に対応して、二つの
明瞭なピークが出ている
• 後者はオンライン学習がうまく行っている証拠

SVDを使った過去パターン抽出はノイズ除
去に効果がある。
 閾値のオンライン計算


動的に状況変化に対応している
この場合、pc=0.5%に設定すれば自動検知
ができる
time [min]
Page 24
IBIS 2004 | 2004/11/08 |
© Copyright IBM Corporation 2004
Tokyo Research Laboratory
まとめ
 コンピュータシステムの障害検知の問題を、高度に動的なグラフ時系列からの異
常検知の問題として考えた。
 いくつかの新しい技術を開発した。
サービス活動度ベクトル
有効次元モデル
コサイン尺度に基づく
異常尺度
モーメント法による
オンライン更新則
 （小さいベンチマークシステムでの話であるが）実システムでの有効性を確認した。
Page 25
IBIS 2004 | 2004/11/08 |
© Copyright IBM Corporation 2004

Download Report