(57)【要約】  ネットワーク異常検出装置は、ネットワークの状態を階層構造の行列変数で表したデータを入力とし、上記ネットワークの状態を上記行列変数の確率分布として学習するデータ分布学習部（２、３、４、５）と、上記データ分布学習部による学習の結果に基づいて、上記確率分布が上記ネットワークの通常の状態を示す分布から他の状態を示す分布に遷移した状態を上記ネットワークの異常として検出する異常検出部（６、７）と、を有する。
2009090939.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークの状態を階層構造の行列変数で表したデータを入力とし、前記ネットワークの状態を前記行列変数の確率分布として学習するデータ分布学習部と、
前記データ分布学習部による学習の結果に基づいて、前記確率分布が前記ネットワークの通常の状態を示す分布から他の状態を示す分布に遷移した状態を前記ネットワークの異常として検出する異常検出部と、を有する、ネットワーク異常検出装置。
【請求項２】
前記データ分布学習部は、
入力される前記データの階層構造に対応する候補として複数の異なる構造を列挙する構造候補列挙手段と、
前記構造候補列挙手段にて列挙された構造のそれぞれについて、当該構造と同じ階層構造の行列変数を持つ確率モデルを生成するモデル生成手段と、
前記モデル生成手段で生成した確率モデルのそれぞれについて、該確率モデルの行列変数として与えられているパラメータを、入力される前記データに基づいて更新する分布学習手段と、
前記分布学習手段にてパラメータの更新がなされた確率モデルのそれぞれについて、モデル選択の指標である情報量規準の値を計算し、該情報量規準の値が最も小さな確率モデルを最適なモデルとして選択するモデル選択手段と、を有し、
前記異常検出部は、前記モデル選択手段にて選択した最適なモデルの行列変数の確率分布に関する学習の結果に基づいて前記ネットワークの異常を検出する、請求の範囲第１項に記載のネットワーク異常検出装置。
【請求項３】
前記構造候補列挙手段は、前記モデル選択手段にて最適なモデルの選択がなされると、該選択された最適なモデルの階層構造に類似した複数の異なる構造を前記候補として列挙する、請求の範囲第２項に記載のネットワーク異常検出装置。
【請求項４】
前記異常検出部は、前記モデル選択手段にて選択された最適なモデルにより与えられる入力データの、前記ネットワークが通常の状態における入力データとの差を示す異常度スコアを計算する異常度スコア計算手段を有する、請求の範囲第２項または第３項に記載のネットワーク異常検出装置。
【請求項５】
前記異常度スコア計算手段は、前記異常度スコアが閾値を越えるか否かを判定し、その判定結果を出力する、請求の範囲第４項に記載のネットワーク異常検出装置。
【請求項６】
前記異常検出部は、前記モデル選択手段にて選択された最適なモデルに基づいて前記ネットワークの階層構造の変化を検出する構造変化検出手段を有する、請求の範囲第２項または第３項に記載のネットワーク異常検出装置。
【請求項７】
ネットワークの状態を階層構造の行列変数で表したデータを入力するコンピュータシステムにおいて行われるネットワーク異常検出方法であって、
データ分布学習部が、入力される前記データに基づいて、前記ネットワークの状態を前記行列変数の確率分布として学習し、
異常検出部が、前記データ分布学習部による学習の結果に基づいて、前記確率分布が前記ネットワークの通常の状態を示す分布から他の状態を示す分布に遷移した状態を前記ネットワークの異常として検出する、ネットワーク異常検出方法。
【請求項８】
前記データ分布学習部による学習のステップは、
入力される前記データの階層構造に対応する候補として複数の異なる構造を列挙する第１のステップと、
前記第１のステップで列挙された構造のそれぞれについて、当該構造と同じ階層構造の行列変数を持つ確率モデルを生成する第２のステップと、
前記第２のステップで生成した確率モデルのそれぞれについて、該確率モデルの行列変数として与えられているパラメータを、入力される前記データに基づいて更新する第３のステップと、
前記第３のステップでパラメータの更新がなされた確率モデルのそれぞれについて、モデル選択の指標である情報量規準の値を計算し、該情報量規準の値が最も小さな確率モデルを最適なモデルとして選択する第４のステップを含み、
前記異常検出部による異常検出のステップは、前記第４のステップで選択した前記最適なモデルの行列変数の確率分布に関する学習の結果に基づいて前記ネットワークの異常を検出するステップである、請求の範囲第７項に記載のネットワーク異常検出方法。
【請求項９】
前記第１のステップは、前記第４のステップで選択された最適なモデルの階層構造に類似した複数の異なる構造を前記候補として列挙するステップである、請求の範囲第８項に記載のネットワーク異常検出方法。
【請求項１０】
前記異常検出部による異常検出のステップは、前記第４のステップで選択された最適なモデルにより与えられる入力データの、前記ネットワークが通常の状態における入力データとの差を示す異常度スコアを計算し、該異常度スコアの計算結果に基づいて前記ネットワークの異常を検出するステップを含む、請求の範囲第８項または第９項に記載のネットワーク異常検出方法。
【請求項１１】
前記異常検出部による異常検出のステップは、前記第４のステップで選択された最適なモデルに基づいて前記ネットワークの階層構造の変化を検出し、該構造変化の検出結果に基づいて前記ネットワークの異常を検出するステップを含む、請求の範囲第８項または第９項に記載のネットワーク異常検出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークの異常を検出する技術に関する。
【背景技術】
【０００２】
ネットワークの異常を検出する上で考慮すべき点として、以下のようなネットワークの性質がある。【０００３】
第一の性質は、ネットワーク上では頂点毎に相互作用がある点である。この相互作用の下でネットワークがどのような状態にあるか、もしくは、どのように働いているか、といった、ネットワークの全体的な構造(グラフ構造)を考慮する必要がある。ここでいう全体的な構造とは、例えば、どの頂点も均一に働いていること、重点的に稼動している重要な頂点が少数存在することなどを示す構造である。【０００４】
この第一の性質があるため、個別の要素を調べるだけでは、ネットワークの異常を検出することは難しい。例えば、ネットワークの或る部分のトラフィック量が多くなるだけでは、ネットワークの異常とは言えないが、他のある部分のトラフィック量と同時に多くなる場合は、ネットワークの異常であると言える。ネットワークの全体的な構造を考慮することで、例えば、ネットワークが通常の状態にあり、トラフィック量が均一であったものが、全体的にウィルスに感染してあるサーバを攻撃し始めたために、トラフィック量が一極集中するようになる、といったネットワークの異常を検出することができる。【０００５】
第二の性質は、ネットワーク上のトラフィック量は時刻と共に変化し、どの頂点とどの頂点が繋がっているかというネットワークの構造も時間と共に変化する点である。この第二の性質があるため、ネットワークの異常を検出するためには、ネットワークの通常の状態がどういう状態であるかを学習する必要がある。例えば、深夜の時間帯においては、トラフィック量が異常に多くなったとしても、昼の時間帯においては、トラフィック量は通常の量となる、といったような状況が、第二の性質に対応する。【０００６】
上記の性質を考慮したネットワークの異常検出方法として、特開２００５−２１６０６６号公報（以下、特許文献１と記す。）に記載の方法がある。特許文献１に記載の方法では、ネットワークの特徴量を成分に持つ行列の最大固有ベクトルを入力として、ベクトルの通常の状態を学習し、通常のベクトルと大きく異なる場合を異常として検出する。【０００７】
ネットワークの持つ特徴的な構造としては、以下の非特許文献１乃至３に記載のものがある。【０００８】
１．A.  L.  Barabasi,  and  R.  Albert,  ‘Emergence  of  Scaling  in  Random  Networks  ’,  Science  vol.  286,  pp509-512  (1999).）
２．（C.  Song,  S.  Havlin  and  H.  Makse,  ‘Self-similarity  of  complex  networks’,  Nature  vol.  433,  pp.392-395  (2005).）
３．（Jure  Leskovec  and  Christos  Faloutsos,  ‘Scalable  Modeling  of  Real  Graphs  using  Kronecker  Multiplication’,  ICML2007
非特許文献１には、ネットワークの構造について、多くの現実のネットワークがスケールフリー性を持つことが示されている。ここで、スケールフリー性とは、ネットワークの多くの頂点が少ないリンク数を持つ一方、膨大なリンクを持つ頂点も少数ながら存在するという性質のことをいう。Ｗｅｂページを例に挙げると、人気のページは、膨大な数のページから参照されるが、他の大多数のページは、少数の参照元しか持たない。このような性質をスケールフリー性と呼ぶ。【０００９】
非特許文献２には、スケールフリー性を持つネットワークが自己相似性を持つことが報告されている。自己相似性とは、全体を相似的に縮小した際に、元と同じ形が現れるという性質である。具体的には、遠くからぼんやりと眺めた場合も、近くに寄って細かい構造を見た場合も、同じ形に見えるという性質を、自己相似性という。【００１０】
スケールフリー性を持つネットワークを、行列を用いて表現する方法として、非特許文献３には、行列を行列の直積として表すという方法が示されている。ｎ×ｍ行列Ｕとｐ×ｑ行列Ｖとの直積は、以下のｐｎ×ｑｍ行列で定義される。【００１１】
【数１】
2009090939.tif 000003
特開２００５−１４１６０１号公報（以下、特許文献２と記す。）には、ネットワークの構造についての技術ではないが、複数の構造があった場合に、その中から最適な構造を選択する技術が記載されている。この技術によれば、予め用意された構造の中から情報量規準を最小にするものを最適な構造として逐次的に選択することで、構造の時間的な変化に対応する。
【発明の開示】
【００１２】
ネットワーク上のトラフィックにおいて、ある区域において重要な働きをするハブがあり、更に広い区域で見ると、それらをまとめるハブがある、というような階層構造が、各所で現れる場合がある。このような階層構造を有するネットワークにおいて、ワームの発生等の異常が発生した場合、全体が同じようなトラフィックになったり、一部だけがおかしくなったりする。このような異常を検出するためには、ネットワークの階層構造を考慮する必要がある。
【００１３】
特許文献１に記載の手法では、入力を固有ベクトルに変換するため、ネットワークの構造に関する情報が出力に含まれない。このため、どのような変化が起こったために(全体的な構造がどのように変化したために)、ネットワークの異常と判断されたのかを知ることはできない。
【００１４】
非特許文献１、２には、現実のネットワークの特徴的な構造としてスケールフリー構造や自己相似構造があることが開示されている。しかし、自己相似性やスケールフリー性といった階層構造の変化をどのようにして検出するかについては、これら非特許文献１、２には示されていない。
【００１５】
特許文献２には、入力データの確率分布の構造の変化を捉える異常検出手法が記載されている。しかし、特許文献２に記載の手法は、候補となる構造を全て用意し、その中から最適な構造を選択するという手法である。階層構造を考慮したネットワークの異常検出に関する技術思想については、特許文献２には何も開示されていない。
【００１６】
本発明の目的は、上記の課題を解決し、ネットワークの全体的な構造を考慮して異常の検出を行うことのできる、ネットワーク異常検出装置および方法を提供することにある。
【００１７】
上記の目的を達成するため、本発明のネットワーク異常検出装置は、ネットワークの状態を階層構造の行列変数で表したデータを入力とし、前記ネットワークの状態を前記行列変数の確率分布として学習するデータ分布学習部と、前記データ分布学習部による学習の結果に基づいて、前記確率分布が前記ネットワークの通常の状態を示す分布から他の状態を示す分布に遷移した状態を前記ネットワークの異常として検出する異常検出部と、を有する。
【００１８】
また、本発明のネットワーク異常検出方法は、ネットワークの状態を階層構造の行列変数で表したデータを入力するコンピュータシステムにおいて行われるネットワーク異常検出方法であって、データ分布学習部が、入力される前記データに基づいて、前記ネットワークの状態を前記行列変数の確率分布として学習し、異常検出部が、前記データ分布学習部による学習の結果に基づいて、前記確率分布が前記ネットワークの通常の状態を示す分布から他の状態を示す分布に遷移した状態を前記ネットワークの異常として検出する。
【図面の簡単な説明】
【００１９】
【図１】図１は、本発明の一実施形態であるネットワーク異常検出装置の構成を示すブロック図である。
【図２】図２は、図１に示すネットワーク異常検出装置において行われる異常検出処理を説明するためのフローチャートである。
【符号の説明】
【００２０】
１  データ入力装置
２  構造候補列挙手段
３  モデル生成手段
４  分布学習手段
５  モデル選択手段
６  異常スコア計算手段
７  構造変化検出手段
８  出力装置
【発明を実施するための最良の形態】
【００２１】
以下、本発明における一実施形態を、図面を参照して説明する。【００２２】
次に、本発明の実施形態について図面を参照して説明する。【００２３】
図１は、本発明の一実施形態であるネットワーク異常検出装置の構成を示すブロック図である。図１を参照すると、ネットワーク異常検出装置は、データ入力装置１、構造候補列挙手段２、モデル生成手段３、分布学習手段４、モデル選択手段５、異常度スコア計算手段６、構造変化検出手段７および出力装置８を有する。【００２４】
データ入力装置１は、ネットワークの状態を階層構造のパラメータで表したデータ、より具体的には、ネットワークの特徴量を成分に持つテンソル型データを入力するためのものである。入力データは、時刻と共に逐次的に入力される、もしくは、そのデータが発生した時刻に関する情報が付与されている。ここで、ネットワークの特徴量とは、例えば、ノード間のトラフィック量(もしくはその関数)や、ノード間の接続の有無を０、１の２値の情報で表したものである。入力データは、一般の階数のテンソル型であってもよく、また、行列型であってもよい。【００２５】
行列型データは、例えばＤ（ｉ，ｊ）のような、データを指定する自由度が二つ（ｉとｊ）あるデータを表す。例えば、Ｗｅｂページ間のリンクを表すデータＤ（ｉ，ｊ）の場合、Ｄ（ｉ，ｊ）はページ間のリンクの有無を表し、ｉ、ｊはそれぞれ一つのＷｅｂページを表す。ページｉからページｊへリンクが張られている場合は、Ｄ（ｉ，ｊ）＝１となる。ページｉからページｊへリンクが張られていない場合は、Ｄ（ｉ，ｊ）＝０となる。【００２６】
テンソル型データは、Ｅ（ｉ，ｊ，ｋ）やＦ（ｉ，ｊ，ｋ，ｌ）のように、データを指定する自由度が二つ以上あるデータである。Ｅ（ｉ，ｊ，ｋ）のように自由度が３つあるものは、三階のテンソルと言う。Ｆ（ｉ，ｊ，ｋ，ｌ）のように自由度が４つあるものは、四階のテンソルと言う。行列型は、二階のテンソルと言うことができる。【００２７】
例えば、ネットワークの通信の種類と容量を記録したデータＥ（ｉ，ｊ，ｋ）において、ｉ，ｊはそれぞれ一つのサーバを表し、ｋは通信の種類（ftp,smtp,ssh…）を表す。Ｅ（ｉ，ｊ，ｋ）はネットワーク上の通信量を表す。この通信量は、サーバｉからサーバｊへの通信における、通信の種類がｋであったものがどれくらいの量あったかを示す。【００２８】
以下では、行列型の入力データを例にとって、本実施形態のネットワーク異常検出装置の各部の動作を説明する。【００２９】
構造候補列挙手段２は、現時点で最適な構造として選ばれている階層構造の近傍の構造を列挙する。ただし、計算量を節約しなくても良い場合は、構造候補列挙手段２は、可能な全ての構造を列挙しても良い。【００３０】
構造候補列挙手段２の主要部は、最適構造記憶部２１および近傍構造生成部２２からなる。最適構造記憶部２１には、現時点で最適な構造として選ばれている階層構造の情報が格納される。近傍構造生成部２２は、最適構造記憶部２１に記憶されている最適な構造をもとに、最適な構造の近傍の構造を列挙し、その情報をモデル生成手段３に供給する。【００３１】
なお、最適な構造が決まっていない場合、すなわち初めてデータが入力された場合は、近傍構造生成部２２は、可能な構造のうちの一つをランダムに選び、それを最適な構造とする。ここで、階層構造とは、一般のグラフ的な階層構造を指すものであり、例えば、ツリー構造、自己相似構造、スケールフリー構造などを含む。【００３２】
構造は、例えば行列の直積構造である。行列の直積構造は、一般に、【００３３】
【数２】
2009090939.tif 000004
で示されるものであり、各要素（σ）が階層構造に対応する。可能な構造とは、このΣを分割してつくることが可能な階層構造である。可能な階層構造は、Σを幾つのσの掛け算で表すか、および、各σの次元が幾つであるか、といったことにより決まる。例えば、【００３４】
【数３】
2009090939.tif 000005
で表される構造の場合、Σは３０次元（入力データの次元に対応する）となる。入力データの次元が分かれば、可能な構造を列挙することができる。ネットワーク異常検出装置の起動時には、入力データの次元に関する情報がデータ入力装置１から近傍構造生成部２２に供給される。【００３５】
以下では、データ入力装置１からの入力データ(ネットワークの特徴量)が直積構造を持つ場合を例にとって説明する。【００３６】
入力データをＴとするとき、Ｔが直積構造を持つとは、以下の式のように、Ｔが二つ以上の行列または二つ以上の一般の階数のテンソルの直積で表されることを指す。【００３７】
【数４】
2009090939.tif 000006
この式によれば、Ｕという階層の値とＶという階層の値の積で入力データＴが表される、という階層構造をＴが持っている。非特許文献３に記載されているとおり、直積構造は、スケールフリー構造と対応しており、現実のネットワークが持つ構造の一つである。【００３８】
以下、近傍の構造の列挙の方法について説明する。【００３９】
Ｋ番目のモデルのパラメータ行列ＭＫが、【００４０】
【数５】
2009090939.tif 000007
で表される直積構造の場合は、階層構造は、幾つの行列の直積で書かれているかを示す(dk)と、それぞれの階層の行列μ１〜μdkの各次元とで表される。各階層の行列の次元を並べた【００４１】
【数６】
2009090939.tif 000008
といったもので構造を表すことができる。【００４２】
最適な構造の近傍の構造とは、最適な階層構造と類似する構造のことである。直積構造を考える場合、最適な構造と類似する直積構造を持つ構造が近傍の構造とされる。例えば、最適な構造が(s_1,s_2,…,s_d)のように表されるとき、その近傍の構造とは、以下のような構造である。
（１）隣接する二つの階層の次元を交換した構造【００４３】
【数７】
2009090939.tif 000009
（２）隣接する二つの階層を一つにまとめた構造【００４４】
【数８】
2009090939.tif 000010
（３）一つの階層を二つに分割した構造【００４５】
【数９】
2009090939.tif 000011
モデル生成手段３は、入力データの確率分布のモデルを複数生成する。入力データをＸと表す。データの分布のモデルとして、直積構造を持つ行列型パラメータを持つ行列変数の確率分布を用いる。分布として、例えば、行列変数の正規分布を用いることができる。【００４６】
【数１０】
2009090939.tif 000012
データの分布のモデルは、階層構造を持つ行列型パラメータを持つ行列変数の確率分布であれば良い。ここでは、データ分布モデルを、パラメータ行列が直積構造を持った行列変数の正規分布とする。【００４７】
生成された複数のモデルのうち、ｋ番目のモデルは、【００４８】
【数１１】
2009090939.tif 000013
で与えられる。【００４９】
各モデルのパラメータに、構造候補列挙手段２にて列挙された構造と対応する直積構造を持たせる。ｋ番目のモデルの階層の深さをｄｋとする。この深さｄｋは、幾つの直積でパラメータを表すかを示す。【００５０】
【数１２】
2009090939.tif 000014
モデル生成手段３は、モデル生成部３１および確率モデル記憶部３２からなる。分布学習手段４は、複数のモデルパラメータ更新部４１および複数の確率モデル記憶部４２からなる。【００５１】
モデル生成部３１は、一段階前のモデルのパラメータと構造の情報を確率モデル記憶部３２から取得し、新たに生成されたモデルの構造の情報を近傍構造生成部２２から受け取り、複数のモデルのパラメータと構造の情報を各モデルパラメータ更新部４１に供給する。【００５２】
近傍構造生成部２２から得られた構造が、確率モデル記憶部３２から送られた一段階前の時刻における複数のモデルの中に含まれる場合は、一段階前の時刻のパラメータをそのまま引き継ぐ。近傍構造生成部２２から得られた構造が、一段階前の時刻における複数のモデルの中に含まれない場合、すなわち、最適な構造の変化によって構造候補列挙手段２で新たに生成された構造に対応したモデルである場合は、最適な構造に対応するモデルのパラメータに近くなるようにパラメータを決める。例えば、最適なモデルのパラメータがσであって、新たに生成した構造に対応するモデルのパラメータがσ’１×σ’２という形である場合、フロベニウスノルム【００５３】
【数１３】
2009090939.tif 000015
を最小にするσ’１とσ’２を求め、それを新たなモデルのパラメータの値とする。【００５４】
モデル学習手段４は、モデル生成手段３で用意された複数のモデルのパラメータを更新する。モデルパラメータ更新部４１は、一段階前の時刻におけるモデルの情報をモデル生成部３１から受け取り、入力データを入力装置１から受け取り、モデルのパラメータの更新を行う。時刻ｔでのパラメータの算出方法としては、時刻ｊの入力データをＸｊとして、例えば以下の式で与えられる対数尤度が最大になるようにパラメータを決める、という方法がある。【００５５】
【数１４】
2009090939.tif 000016
また、以下の式で与えられる時間幅Ｌの中での対数尤度が最大になるようにパラメータを決めてもよい。【００５６】
【数１５】
2009090939.tif 000017
また、過去のものの重みを小さくした以下の対数尤度が最大になるようにパラメータを決めてもよい。ただし、0＜r＜１である。このパラメータの決定方法は、一般に、忘却型学習と呼ばれる。【００５７】
【数１６】
2009090939.tif 000018
上記の例のような、パラメータを決める方式を、学習方式と呼ぶ。【００５８】
更新されたパラメータと構造の情報は確率モデル記憶部４２に格納される。確率モデル記憶部４２に格納されている情報は、情報が更新される度に、確率モデル記憶部３２に送られる。【００５９】
モデル選択手段５は、モデル学習手段４にて学習された各モデルについて情報量規準を計算し、その値が最小になるモデルを最適なモデルとして選択する。モデル選択手段５は、最適モデル選択部５１および最適モデル記憶部５２からなる。最適モデル選択部５１は、各確率モデル記憶部４２から供給された複数のモデルの情報から、最適なモデルを一つ選択する。最適なモデルの選択方法について、以下に説明する。【００６０】
時刻ｊでのｋ番目のモデルのパラメータをまとめて【００６１】
【数１７】
2009090939.tif 000019
と表し、時刻ｊでのｋ番目のモデルの直積構造を【００６２】
【数１８】
2009090939.tif 000020
と表す。【００６３】
時刻ｊでの最適なモデルを【００６４】
【数１９】
2009090939.tif 000021
と表す。【００６５】
情報量規準を用いて最適なモデルを選択する方法の例として、以下のものが挙げられる。【００６６】
学習方式として忘却型学習を用いている場合に、以下の予測的確率的コンプレキシティとして知られる量(Universal  coding,  information,  prediction,  and  estimation,  IEEE  Transactions  on  Information  Theory,  30,  pp:629-636,  1984)をモデル選択の為の情報量規準として用い、この値を最小にするモデルｋを最適なモデルとして選択するという方法を用いることが出来る。【００６７】
【数２０】
2009090939.tif 000022
学習方式に依らず、ある範囲のモデルの推移を一括して求める場合には、時刻ｊ−１までのモデルの系列【００６８】
【数２１】
2009090939.tif 000023
とモデルの遷移確率【００６９】
【数２２】
2009090939.tif 000024
とを用いて表される、以下の一括型動的モデル選択基準(特許文献２参照)【００７０】
【数２３】
2009090939.tif 000025
を最小にするように最適なモデルの系列【００７１】
【数２４】
2009090939.tif 000026
を決めるという方法を用いることが出来る。【００７２】
また、忘却型でない学習方式を用いる場合や、計算量を小さくしたい場合には、ある時間幅Ｗの中で、パラメータの数とデータの数とデータの尤度等を引数とする関数の値を計算して、それを最小にするモデルを最適なモデルとして選択するという方法を用いることができる。【００７３】
パラメータの数とデータの数とデータの尤度等を引数とする関数としては、MDL,  AIC,  BIC等の情報量規準を用いることができる。例えば、情報量規準としてMDLを用いる場合には、以下の量を最小にするモデルを最適なモデルとして選択すればよい。【００７４】
【数２５】
2009090939.tif 000027
異常度スコア計算手段６は、モデル選択手段５にて選択された最適なモデルを用いて、データの異常度スコアを算出する。異常度スコアは、入力データが通常のデータとどれだけ異なっているかを表す量で、値が大きい程、通常は、現れない異常なデータであることに対応する。異常度スコアが突然高くなったところを調べることで、突発的な異常を検出することができる。【００７５】
異常度スコアとして、例えば以下の量を用いることが出来る。【００７６】
【数２６】
2009090939.tif 000028
例えば、入力をネットワークのノード間の通信量とする場合、異常度スコアが高いことは、通常同時に通信量が多くならない二箇所で同時通信量が多くなる場合や、通常の通信量よりも全体的に通信量が多くなる場合など、通常の状態とは異なった状態にネットワークが置かれていることに対応する。したがって、この例では、異常度スコアを監視することで、ネットワーク上の通信の状態の異常を検出することが出来る。計算された異常度スコアは、出力装置８に送られる。【００７７】
スコアに対して予め閾値を設定できる場合は、スコアがその値を超えたか否か(異常か否か)の情報を出力装置８に送っても良い。【００７８】
構造変化検出手段７では、データの背後にある階層構造の変化を検出する。最適なモデルのパラメータが持つ階層構造【００７９】
【数２７】
2009090939.tif 000029
が変化した場合、これを階層構造の変化として検出する。構造の変化として、階層構造そのものは変化していないが、何れかの階層の中の構造が変化している、という変化も検出する。このような何れかの階層の中の構造変化の検出方法として、各階層のパラメータ行列の一時刻前からの変化量を計算し、その量の急激な変化を検出する、という方法を用いることが出来る。【００８０】
パラメータ行列の一時刻前からの変化量として、以下のような量を用いることが出来る。【００８１】
【数２８】
2009090939.tif 000030
例えば、入力がネットワーク上の通信量である場合に、構造の変化が起こるということは、ある区域において重要な働きをするハブがあり、更に、広い区域で見た場合に、それらをまとめるハブがある、といった、似たような構造を持つネットワークにおいて、ワームの発生等の異常が発生して、全体が同じようなトラフィックになったり、一部だけがおかしくなったりする、といった一時的ではない通信の全体的な異常が発生していることに対応する。したがって、この例では、構造の変化を監視することで、一時的ではない全体的な通信の構造の異常を検出することが出来る。【００８２】
上記の二つの変化が検出されたか否かを出力装置８に送る。【００８３】
その他、最適な構造に関する情報なども出力装置８に送っても良い。【００８４】
出力装置８は、異常度スコア計算手段６と構造変化検出手段７で得られた結果を受け取り、それを出力または表示する。【００８５】
図２は、図１に示すネットワーク異常検出装置において行われる異常検出処理を説明するためのフローチャートである。【００８６】
図２を参照すると、異常検出処理は、ネットワークの状態を階層構造の行列変数で表したデータを入力とし、該入力データの分布を行列変数の確率分布として学習するステップＳ１０と、その確率分布が通常の状態から他の状態に遷移した場合にネットワークの異常と判定するステップＳ２０とを含む。【００８７】
ステップＳ１０の処理では、まず、近傍構造生成部２２が、最適構造記憶部２１に最適な構造の情報が格納されているか否かを確認する（ステップＳ１１）。最適構造記憶部２１に最適な構造の情報が格納されていない場合（起動直後の状態）、近傍構造生成部２２は、入力装置１から予め与えられた入力データの次元に関する情報に基づいて、候補として可能な構造を列挙し、その中からランダムに選択した構造を最適な構造として用いる（ステップＳ１２）。【００８８】
ステップＳ１２の後、または、最適構造記憶部２１に最適な構造の情報が格納されると、近傍構造生成部２２が、最適な構造に類似の構造（近傍の構造）を列挙する。次に、モデル生成部３１が、近傍構造生成部２２にて列挙した近傍の構造のそれぞれについて、近傍の構造に対応する直積構造のパラメータよりなるモデルを生成する（ステップＳ１４）。このモデル生成において、モデル生成部３１は、生成するモデルのパラメータとして、最適な構造におけるパラメータおよび確率モデル記憶部３２に格納されたモデルのパラメータを参照する。モデル生成部３１にて生成された各モデルは、各モデルパレメータ更新部４１に供給される。【００８９】
次に、モデルパレメータ更新部４１のそれぞれが、学習方式により、モデル生成部３１から供給されたモデルのパラメータを更新する（ステップＳ１５）。各モデルパレメータ更新部４１でパラメータの更新がなされたモデルはそれぞれ、対応する確率モデル記憶部４２に格納される。確率モデル記憶部４２に格納された、パラメータの更新がなされたモデルの情報は、モデル生成主だ３の確率モデル記憶部に供給される。【００９０】
次に、最適モデル選択部５１が、各確率モデル記憶部４２に格納されたモデルについて、情報量規準の値を計算し、この値が最も小さなモデルを最適モデルとする（ステップＳ１６）。最適モデルは、最適モデル記憶部５２に格納される。最適モデル記憶部５２に格納された最適モデルの情報は、構造候補列挙手段２の最適構造記憶部２１に供給される。【００９１】
上述のステップＳ１１〜Ｓ１６が、データ入力装置１からデータが供給される度に繰り返し実行される。【００９２】
ステップＳ２０では、ステップＳ１１〜Ｓ１６の繰り返しの処理において、ステップＳ１６で得られる最適モデルの分布（行列変数の確率分布）を監視し、その分布が通常の状態から他の状態に遷移した場合にネットワークの異常と判定する。この異常判定の処理は、異常度スコア計算手段６による計算結果に基づく第１の異常判定処理と、構造変化検出手段７による検出結果に基づく第２の異常判定処理とを含む。ステップＳ２０において、第１および第２の異常判定処理のいずれかが一方が行われるようにしてもよい。【００９３】
以上説明したネットワーク異常検出装置は、本発明の一例であり、その構成および動作は発明の趣旨を逸脱しない範囲で適宜に変更することができる。例えば、図１に示した構成において、異常度スコア計算手段６および構造変化検出手段７の一方のみを有するように構成してもよい。【００９４】
また、ネットワーク異常検出装置は、プログラムより動作するコンピュータシステムにより構成することができる。コンピュータシステムの主要部は、プログラムやデータなどを蓄積する記憶装置、キーボードやマウスなどの入力装置、ＣＲＴやＬＣＤなどの表示装置、外部との通信を行うモデムなどの通信装置、プリンタなどの出力装置および入力装置からの入力を受け付けて通信装置、出力装置、表示装置の動作を制御する制御装置から構成される。【００９５】
上記のコンピュータシステムにおいて、制御部が、記憶部に格納されたプログラムを実行することで実現される機能ブロックとして、ネットワークの状態を階層構造の行列変数で表したデータを入力とし、上記ネットワークの状態を上記行列変数の確率分布として学習するデータ分布学習部と、該データ分布学習部による学習の結果に基づいて、上記確率分布が上記ネットワークの通常の状態を示す分布から他の状態を示す分布に遷移した状態を上記ネットワークの異常として検出する異常検出部と、を有していてもよい。【００９６】
上記の構成において、上記データ分布学習部が、入力される上記データの階層構造に対応する候補として複数の異なる構造を列挙する構造候補列挙手段と、上記構造候補列挙手段にて列挙された構造のそれぞれについて、当該構造と同じ階層構造の行列変数を持つ確率モデルを生成するモデル生成手段と、上記モデル生成手段で生成した確率モデルのそれぞれについて、該確率モデルの行列変数として与えられているパラメータを、入力される上記データに基づいて更新する分布学習手段と、上記分布学習手段にてパラメータの更新がなされた確率モデルのそれぞれについて、モデル選択の指標である情報量規準の値を計算し、該情報量規準の値が最も小さな確率モデルを最適なモデルとして選択するモデル選択手段と、を有し、上記異常検出部が、上記モデル選択手段にて選択した最適なモデルの行列変数の確率分布に関する学習の結果に基づいて上記ネットワークの異常の判定を行うように構成してもよい。この場合、上記構造候補列挙手段は、上記モデル選択手段にて最適なモデルの選択がなされると、該選択された最適なモデルの階層構造に類似した複数の異なる構造を上記候補として列挙してもよい。【００９７】
また、図１に示した構成において、上記のデータ分布学習部は、近傍構造生成部２２、モデル生成部３１、モデルパラメータ更新部３１および最適モデル選択部５１に対応する機能ブロックにより構成され、異常検出部は、異常度スコア計算手段６および構造変化検出手段に対応する機能ブロックにより構成される。【００９８】
以上説明した本発明によれば、以下のような効果を奏する。【００９９】
例えば、ネットワーク上のトラフィックにおいて、ある区域において重要な働きをするハブがあり、更に広い区域で見ると、それらをまとめるハブがある、というような階層構造が、各所で現れる場合がある。このような構造のネットワークにおいて、ワームの発生等の異常が発生した場合、全体が同じようなトラフィックになったり、一部だけがおかしくなったりする。【０１００】
本発明では、ネットワークの状態を階層構造（一般のグラフ的な階層構造、例えば、ツリー構造や自己相似構造などを含む）の行列変数で表したデータを入力とし、ネットワークの状態をその行列変数の確率分布として学習し、その学習の結果に基づいて、その確率分布がネットワークの通常の状態を示す分布から他の状態を示す分布に遷移した状態をネットワークの異常として検出する。これにより、ネットワークの構造の変化を監視することができ、ワームの発生等の異常の発生を検出することができる。このようにネットワークの構造を考慮して異常の検出を行うことで、異常検出の精度を向上させることができる。【０１０１】
また、ネットワークの状態を表す階層構造を持つ行列をパラメータとして持つ確率分布を学習し、そのパラメータ行列のどの階層が激しく変化するかを検出することができる。したがって、ネットワークの構造の変化を見る際に、部分的な構造の変化についても検出することができる。加えて、どのような構造の変化から異常が発生したのかということも提示することができ、その結果、検出結果の可読性を向上することができる。【０１０２】
非特許文献１、２で示されているように、現実のネットワークに特徴的な構造としてスケールフリー構造や自己相似構造が存在する。スケールフリー構造は、多数の頂点が繋がっているハブとなる少数の頂点があり、それら少数のハブが繋がっている更に少数のハブがある、という構造になっているので、階層構造の一種であると言える。また、自己相似構造も、どの階層も同じ形をしているという階層構造である。本発明によれば、ネットワークの階層構造を考慮した異常検出を行うようになっているので、現実のネットワークへの適用を容易に行うことができる。【０１０３】
以上説明した本発明のネットワーク異常検出装置は、要素同士が相関を持つネットワーク全般に適用することができる。【０１０４】
以上、実施形態を参照して本発明を説明したが、本発明は上述した実施形態に限定されるものではない。本発明の構成および動作については、本発明の趣旨を逸脱しない範囲において、当業者が理解し得る様々な変更を行うことができる。【０１０５】
この出願は、２００８年１月１５日に出願された日本出願特願２００８−５６０３を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
2009090939.tif 000031
【図２】
2009090939.tif 000032
【国際調査報告】
2009090939.tif 000033
2009090939.tif 000034
2009090939.tif 000035
2009090939.tif 000036