(57)【要約】【課題】小サイズのデータで大量トラフィックデータ中の端末間通信情報を集約し、その集約データに基づき、端末間の類似度を計算する手法を提供する。【解決手段】端末間通信パターン監視装置はトラヒックデータ取得部とハッシュマトリクス生成／記憶部と端末間通信パターン類似度計算部を備える。ハッシュマトリクス生成／記憶部が、送信端末、受信端末間のトラフィック情報を行列２０１として保持し、トラヒックデータ取得部から得たトラフィックデータ中のパケットまたはフロー毎の送信端末アドレス２０２、受信端末アドレス２０３をハッシュ関数を用いてハッシュ化し、送信端末アドレス２０２のハッシュ値、受信端末アドレス２０３のハッシュ値対に行番号、列番号が対応する行列要素に対して値を更新する。端末間通信パターン類似度計算部は、二つの端末のハッシュ値に対応する行列中の二つのベクトルを用いて端末間通信パターン類似度を計算する。【選択図】図２
2008172401.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク上を転送されるトラフィックデータの送信端末と受信端末ペアの通信パターンを監視する端末間通信パターン監視装置において、送信端末と受信端末ペアの通信パターンを集約する端末間通信パターン集約方法であって、
前記端末間通信パターン監視装置は、トラヒックデータ取得部とハッシュマトリクス生成／記憶部とを備え、
前記トラヒックデータ取得部が、トラヒックデータを取得し、取得したトラヒックデータ中のパケットまたはフロー毎に送信端末アドレスと受信端末アドレスを抽出するステップと、
前記ハッシュマトリクス生成／記憶部が、送信端末、受信端末間のトラフィック情報を行列形式で保持し、前記トラヒックデータ取得部から得たトラフィックデータ中のパケットまたはフロー毎の送信端末アドレス、受信端末アドレスをハッシュ関数を用いてハッシュ化し、送信端末アドレスのハッシュ値、受信端末アドレスのハッシュ値対に行番号、列番号が対応する行列要素に対して値を更新するステップと、
を有することを特徴とする端末間通信パターン集約方法。
【請求項２】
請求項１に記載の端末間通信パターン集約方法であって、
前記ハッシュマトリクス生成／記憶部が、単一もしくは複数のサンプリングレートを用いてサンプリングされたトラフィックデータ中のパケットまたはフローに対して、サンプリングレートに対応する単一もしくは複数の行列の値を更新するステップを有することを特徴とする端末間通信パターン集約方法。
【請求項３】
請求項１に記載の端末間通信パターン集約方法であって、
前記ハッシュマトリクス生成／記憶部が、単一もしくは複数の特定条件に該当するトラフィックデータ中のパケットまたはフローに対して、特定条件に対応する単一もしくは複数の行列の値を更新するステップを有することを特徴とする端末間通信パターン集約方法。
【請求項４】
請求項１に記載の端末間通信パターン集約方法であって、
前記ハッシュマトリクス生成／記憶部が、ハッシュ化する際に、送信端末アドレス、または受信端末アドレスに対して、複数の異なるハッシュ関数によりハッシュ化し、それぞれのハッシュ関数に対応する複数の行列で集約するステップを有することを特徴とする端末間通信パターン集約方法。
【請求項５】
請求項１ないし４のうちいずれか１項に記載の集約方法を用いて集約されたデータを用いて、二つの端末の通信相手端末の通信パターンの類似度を計算する端末間通信パターン分析方法であって、
前記端末間通信パターン監視装置は、端末間通信パターン類似度計算部を備え、
前記端末間通信パターン類似度計算部が、二つの端末のハッシュ値に対応する行列中の二つのベクトルを用いて端末間通信パターン類似度を計算するステップを有することを特徴とする端末間通信パターン分析方法。
【請求項６】
請求項５に記載の端末間通信パターン分析方法であって、
前記端末間通信パターン類似度計算部が、前記二つの端末に対応する二つのベクトルを用いて端末間通信パターン類似度を計算する方法として、ベクトルサイズをＮ、ベクトル内の非０の要素数をＮＡ、ＮＢ、二つのベクトルの要素同士の積を要素とするベクトルにおける非０の要素数をＮＡＢとしたときに、端末間通信パターン類似度Ｓ（Ａ，Ｂ）を式１、式２で計算するステップを有することを特徴とする端末間通信パターン分析方法。
【数１】
2008172401.tif 000004
【請求項７】
請求項５または６に記載の端末間通信パターン分析方法であって、
前記端末間通信パターン類似度計算部が、端末に対応するベクトルとして、単一の行列中のベクトルではなく、複数のハッシュ関数に対応する複数の行列中のベクトルに対して、それらベクトルの要素同士の積を要素とするベクトルを用いて端末間通信パターン類似度を計算するステップを有することを特徴とする分析方法。
【請求項８】
請求項１ないし７のうちのいずれか１項に記載のステップをコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はインターネット上で転送されるトラフィックデータの集約、分析技術に関する。
【背景技術】
【０００２】
インターネットにおける特定サーバに対する攻撃などの異常トラフィックの増加に伴い、トラフィックの監視に対する要求が高まっている。トラフィックの監視対象としては、ＭＩＢ（Management Information Base）などによるパケット数などの総トラフィック流量に基づくものが一般的であるが、総トラフィック量監視では、総トラフィックの変化として現れないようなトラフィックデータ中の一部の変化による異常検出が困難、また異常検出した後の異常原因分析が困難という問題がある。このような異常を検出、分析するために、より詳細に、送信端末毎にトラフィック量や通信相手端末数などの値を監視する手法が提案されている（非特許文献１）。しかしながら一般的に大容量トラフィックに対してこのように詳細な監視を行うことは、計算処理量、監視結果データ蓄積容量的に負荷が高い。蓄積容量を減らすため、大容量トラフィックデータを小サイズのデータに集約する手法が提案されている（非特許文献２）。
【０００３】
【非特許文献１】藤井聖、中村豊、藤川和利、砂原秀樹、“通信先ホスト数の変化に注目した異常トラフィック自動検出手法の提案と評価”、電子情報通信学会、Vol.88-B、No.10、pp.1922-1933、Oct. 2005.
【非特許文献２】S. Venkataraman, D.Song, P.B. Gibbons, and A. Blum,“New Streaming Algorithms for Fast Detection of Superspreaders,”In Proceedings of the 12th ISOC Symposium on Network and Distributed Systems Security (SNDSS), pp.149-166, Feb. 2005.
【０００４】
なお、出願人は、本明細書に記載した先行技術文献情報で特定される先行技術文献以外には、本発明に関連する先行技術文献を出願時までに発見するには至らなかった。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
異常トラフィック送信端末を特定する上では、送信端末毎の通信相手端末数のみならず、どの端末と通信したのかという端末間の通信パターンを監視することが重要である。例えば、複数のワーム感染端末が攻撃指示端末からの指示を受けて、特定サーバを攻撃する事象が近年多発している。この場合、攻撃先サーバの通信端末パターンと類似している通信端末パターンを持つ端末を抽出することで、攻撃指示端末を特定することが可能となる。しかしながら、この通信パターンを記録するためには、送信端末毎に全着信端末情報を保持する必要があるため、端末数の２乗のオーダーの記録容量が必要であり、大容量トラフィックデータをリアルタイムで記録することは困難であった。上記に挙げた既存集約手法は端末毎の送信パケット数や、通信相手端末数を記録するためのものであり、通信相手端末そのものの情報を記録するものではなかった。
【０００６】
本発明は上記の課題を鑑みてなされたもので、小サイズのデータで大量トラフィックデータ中の端末間通信情報を集約する手法を提供することを目的とする。またその集約データに基づき、端末間の類似度を計算する手法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上述の目的を達成するため、本発明で提案した手法では送信端末毎に全着信端末情報を保持することなく、端末間の通信パターンを記録する。
本明細書において開示される発明のうち、代表的なものの概要を簡単に説明すれば、以下のとおりである。
【０００８】
ネットワーク上を転送されるトラフィックデータの送信端末と受信端末ペアの通信パターンを監視する端末間通信パターン監視装置において、送信端末と受信端末ペアの通信パターンを集約する端末間通信パターン集約方法であって、前記端末間通信パターン監視装置は、トラヒックデータ取得部とハッシュマトリクス生成／記憶部とを備え、前記トラヒックデータ取得部が、トラヒックデータを取得し、取得したトラヒックデータ中のパケットまたはフロー毎に送信端末アドレスと受信端末アドレスを抽出するステップと、前記ハッシュマトリクス生成／記憶部が、送信端末、受信端末間のトラフィック情報を行列形式で保持し、前記トラヒックデータ取得部から得たトラフィックデータ中のパケットまたはフロー毎の送信端末アドレス、受信端末アドレスをハッシュ関数を用いてハッシュ化し、送信端末アドレスのハッシュ値、受信端末アドレスのハッシュ値対に行番号、列番号が対応する行列要素に対して値を更新するステップと、を有する端末間通信パターン集約方法である。
【０００９】
また、前記集約方法を用いて集約されたデータを用いて、二つの端末の通信相手端末の通信パターンの類似度を計算する端末間通信パターン分析方法であって、前記端末間通信パターン監視装置は、端末間通信パターン類似度計算部を備え、前記端末間通信パターン類似度計算部が、二つの端末のハッシュ値に対応する行列中の二つのベクトルを用いて端末間通信パターン類似度を計算するステップを有することを特徴とする端末間通信パターン分析方法である。
【発明の効果】
【００１０】
本発明によればハッシュマトリクス形式でトラフィックデータを保持することにより、少ないメモリ容量で効率よくホスト間通信パターンに関する情報を集約することが出来、また分析することが出来る。
【発明を実施するための最良の形態】
【００１１】
以下図面に即して、実施の形態を述べる。
図１は、インターネットのトラフィックデータを対象とする本発明の基本構成の一例を示す図である。１０１は監視対象のネットワークである監視対象網であり、１０２はトラヒック送信端末（以下、単に「送信端末」という。）であり、１０３はトラヒック受信端末（以下、単に「受信端末」という。）であり、１０４〜１０７はルータ等のネットワーク機器である。１１０は本発明の実施例の端末間通信パターン監視装置である。端末間通信パターン監視装置１１０は、トラヒックデータ取得部１１１とハッシュマトリクス生成／記憶部１１２と端末間通信パターン類似度計算部１１３とを有する。
【００１２】
図１では、送信端末１０２と受信端末１０３をそれぞれ１つづつを例示的に示しているが、実際には多数の送信端末と受信端末が存在し、それらの多数の送信端末と受信端末ペアの通信パターン（どの送信端末がどの受信端末と通信したのかという空間的な通信パターン）を、端末間通信パターン監視装置１１０が監視する。端末間通信パターン監視装置１１０は、トラヒックデータ取得部１１１とハッシュマトリクス生成／記憶部１１２とで通信パターンを集約する。そのために、トラヒックデータ取得部１１１は、監視対象網１０１を転送されるトラヒックデータを取得し、取得したトラヒックデータ中のパケットまたはフロー毎に送信端末アドレスと受信端末アドレスを抽出する。そして、ハッシュマトリクス生成／記憶部１１２は、送信端末、受信端末間のトラフィック情報を行列形式で保持し、トラヒックデータ取得部１１１が抽出したトラフィックデータ中のパケットまたはフロー毎の送信端末アドレス、受信端末アドレスをハッシュ関数を用いてハッシュ化し、送信端末アドレスのハッシュ値、受信端末アドレスのハッシュ値対に行番号、列番号が対応する行列要素に対して値を更新する。また、端末間通信パターン監視装置１１０は、端末間通信パターン類似度計算部１１３で端末間通信パターン分析を行う。そのために、端末間通信パターン類似度計算部１１３は、二つの端末のハッシュ値に対応する行列中の二つのベクトルを用いて端末間通信パターン類似度を計算する。
【００１３】
以下、端末間通信パターン監視装置１１０の各部の動作について詳細に説明する。
トラフィックデータ取得部１１１では、リンク上に転送されるパケットデータもしくはルータから出力されるトラフィックフローデータから、送信端末ＩＰアドレス、受信端末ＩＰアドレスを抽出する。
【００１４】
ハッシュマトリクス生成／記憶部１１２では、事前に集約用の行列（サイズはＮ×Ｎ）を準備しておき、全ての要素を０で初期化しておく。図２において、２０１がこの行列の例であり、２０２が送信端末のＩＰアドレスの例であり、２０３が受信端末のＩＰアドレスの例である。行列２０１の列は受信端末アドレスのハッシュ値であり、行は送信端末アドレスのハッシュ値である。トラフィックデータ取得部１１１から得た送信端末、受信端末ＩＰアドレスに対して、図２に示すようにそれぞれハッシュ関数を適用し、１〜Ｎのハッシュ値を得る。先のＮ×Ｎ行列に対して、送信ＩＰアドレスのハッシュ値の行番号、受信ＩＰアドレスのハッシュ値の列番号の行列要素を更新する。図２は、送信端末のＩＰアドレスが１９２．１６８．０．１、そのハッシュ値が２であり、受信端末のＩＰアドレスが１０．０．０．１、そのハッシュ値が４の場合に、行番号２と列番号４で指定される行列要素を１と更新している例である。経過時間、カウントパケット数、もしくは行列内の非０の要素数などが閾値を超えたことをトリガとして、過去ハッシュマトリクスとして記憶し、新たに全要素を０で初期化した更新用行列を用意する。
【００１５】
行列要素の値として、送信端末、受信端末間のパケット数、フロー数を記録する手法や、記録容量を削減するために、０もしくは１の値のみとし、該送信端末、受信端末間にパケットもしくはフローが存在するときは１とする方法もある。
【００１６】
行列の値として、パケット数、フロー数を記録する手法の場合は、トラヒックデータ取得部１１１がパケットデータまたはフローデータを観測し、送信端末ＩＰアドレス、受信端末ＩＰアドレスを抽出するたびに、ハッシュマトリクス生成／記憶部１１２が、その送信端末ＩＰアドレス、受信端末ＩＰアドレスに対応する要素をカウントアップする。
【００１７】
行列の値を０もしくは１の値のみとする場合が、図２に示す行列２０１である。この場合は、トラヒックデータ取得部１１１がパケットデータまたはフローデータを観測し、送信端末ＩＰアドレス、受信端末ＩＰアドレスを抽出すると、ハッシュマトリクス生成／記憶部１１２が、その送信端末ＩＰアドレス、受信端末ＩＰアドレスに対応する要素を１とし、その後、トラヒックデータ取得部１１１が同じ送信端末ＩＰアドレス、受信端末ＩＰアドレスを抽出してもカウントアップはしない。この場合は、端末間のパケット数、フロー数の情報は記録されないため、複数のサンプリングレートでサンプリングされたデータに対して、複数の行列を並列して生成することにより、端末間のパケット数、フロー数をその端末間に対応する要素が１となっている行列に対応するサンプリングレートの逆数などとして推定することも可能である。例えば、サンプリングレートがそれぞれ１／１０、１／１００、１／１０００の複数の行列があり、そのうち、１／１０と１／１００の行列それぞれで１となっている場合は、最も低いサンプリングレート１／１００の行列で１になっているという情報を用いて、パケット数をそのサンプリングレートの逆数の１００と推定する。
【００１８】
このように、ハッシュマトリクス生成／記憶部１１２は、複数のサンプリングレートを用いてサンプリングされたトラフィックデータ中のパケットまたはフローに対して、サンプリングレートに対応する複数の行列の値を更新するようにすることができる。しかし、単一のサンプリングレートを用いてサンプリングされたトラフィックデータ中のパケットまたはフローに対して、サンプリングレートに対応する単一の行列の値を更新するようにしてもよい。
【００１９】
送信端末、受信端末間のトラフィック量情報のみならず、例えばポート番号情報について記録する場合は、ポート番号を特定条件としてフィルタしたデータを対象に行列を生成することにより、特定ポート番号トラフィックの送信、受信端末対情報が得られる。この場合は、ハッシュマトリクス生成／記憶部１１２は、単一もしくは複数の特定条件に該当するトラフィックデータ中のパケットまたはフローに対して、特定条件に対応する単一もしくは複数の行列の値を更新する。
【００２０】
なお、ハッシュ値の範囲サイズＮによっては、複数の端末アドレスが単一のハッシュ値に変換されるため、ある端末間の通信が無いにもかかわらず、それら端末のハッシュ値対に対応する行列要素は非０となっている可能性がある。この可能性を減らすための一方法として、異なる複数のハッシュ関数によって複数のハッシュ値に変換し、ハッシュ関数に対応した複数の異なる行列に対してそれぞれのハッシュ値に対応する行列要素を更新する方法がある。ある端末の通信相手先パターンはそれら複数の行列の対応するベクトルのＡＮＤをとることにより、高精度に推定が可能となる。例えば、二つのハッシュ関数α、βに対応する行列がＡ＝ａ_｛ｉｊ｝とＢ＝ｂ_｛ｉｊ｝であり、ある送信端末のアドレスをαでハッシュ化した数値がｋ、ある送信端末のアドレスをβでハッシュ化した数値がｋ’になったとする。この時ａ_｛ｋｊ｝とｂ_｛ｋ’ｊ｝｛ｊ＝１，．．．，Ｎ｝が、それぞれ行列ＡとＢに対応するベクトルとなる。このａ_｛ｋｊ｝とｂ_｛ｋ’ｊ｝のＡＮＤをとることにより、高精度に推定が可能となる。
【００２１】
このように、ハッシュマトリクス生成／記憶部１１２は、ハッシュ化する際に、送信端末アドレス、または受信端末アドレスに対して、複数の異なるハッシュ関数によりハッシュ化し、それぞれのハッシュ関数に対応する複数の行列で集約するようにしてもよい。
【００２２】
端末間通信パターン類似度計算部１１３では、指定された二つの端末ＩＰアドレスに対して、それら端末の通信相手端末の通信パターンの類似度を計算する。まず入力された二つの端末のＩＰアドレス（それぞれＡ、Ｂとする）のハッシュ値を計算する。それぞれのハッシュ値の列番号に対する列ベクトルを抽出し、両者の類似度を計算する。図２の例において、例えば、入力された二つの受信端末のＩＰアドレスのハッシュ値が１と４であるとすると、列番号１に対する列ベクトル［１  １  １  ０  …  ０］と、列番号４に対する列ベクトル［１  １  ０  ０  …  １］を抽出し、両者の類似度を計算する。このように、端末間通信パターン類似度計算部１１３は、二つの端末のハッシュ値に対応する行列中の二つのベクトルを用いて端末間通信パターン類似度を計算する。
【００２３】
二つの端末に対応する二つのベクトルを用いて端末間通信パターン類似度を計算する方法としては次の方法がある。アドレスＡに対応する列ベクトル中の１の要素数をＮＡ、アドレスＢに対応する列ベクトル中の１の要素数をＮＢ、両方の列ベクトルで１となっている要素数をＮＡＢとする。このとき、端末ＡとＢの端末間通信パターン類似度Ｓ（Ａ，Ｂ）を式３、４で計算する。
【００２４】
【数２】
2008172401.tif 000003
【００２５】
ここで、ｎＣｍは、ｎ個のなかからｍ個取り出す組合わせの数を示し、ｎＣｍ：＝ｎ！／ｍ！（ｎ−ｍ）！である。Ｃ（Ａ，Ｂ）はＮ個の要素から、ＮＡ個、ＮＢ個の要素をそれぞれランダムに選択したとき、共通する要素がＮＡＢ個となる確率であり、超幾何分布を用いて計算される。端末ＡとＢで共通している通信先ホストが類似しているほど、ＮＡＢはランダムに通信先を選択した場合と比較して大きくなる。結果として、ランダム選択を仮定した場合の発生確率の値Ｃ（Ａ，Ｂ）は小さくなり、したがって、Ｓ（Ａ，Ｂ）はより高くなる。
【００２６】
以上の端末間通信パターン類似度の計算方法は、行列の値を０もしくは１の値のみとする場合の計算方法であり、このため、アドレスＡに対応する列ベクトル中の１の要素数をＮＡ、アドレスＢに対応する列ベクトル中の１の要素数をＮＢ、両方の列ベクトルで１となっている要素数をＮＡＢとしている。行列の値としてパケット数、フロー数を記録する手法を用いる場合は行列の要素は２以上の値となることがある。このような場合を含めて、一般的には、アドレスＡに対応する列ベクトル中の非０の要素数をＮＡ、アドレスＢに対応する列ベクトル中の非０の要素数をＮＢ、両方の列ベクトルで非０となっている要素数をＮＡＢとして、同じ計算を行うことになる。
【００２７】
ハッシュマトリクス生成／記憶部１１２が、前述のように、ハッシュ化する際に、送信端末アドレス、または受信端末アドレスに対して、複数の異なるハッシュ関数によりハッシュ化し、それぞれのハッシュ関数に対応する複数の行列で集約した場合は、端末間通信パターン類似度計算部１１３は、その複数の行列を用いて、それぞれのハッシュ値の列番号に対する複数の列ベクトルを抽出し、それら列ベクトルの要素同士の積を要素とするベクトルを類似度計算に用いる。異なる二つの端末のアドレスが、複数のハッシュ関数で、同一ハッシュ値に変換される可能性は、ハッシュ関数の数乗で減少するため、ハッシュ値の衝突による類似度の誤計算を避けることが出来る。
【００２８】
本実施例の端末間通信パターン監視装置１１０のトラヒックデータ取得部１１１、ハッシュマトリックス生成／記録部１１２、端末間通信パターン類似度計算部１１３は、その機能、動作を実現する手段を有しており、それらの手段はコンピュータとプログラムで構成することができる。また、そのプログラムの一部または全部に代えてハードウェアで構成してもよい。
【００２９】
以上、本発明者によってなされた発明を、前記実施形態に基づき具体的に説明したが、本発明は、前記実施形態に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは勿論である。
【図面の簡単な説明】
【００３０】
【図１】本発明における端末間通信パターン監視装置の構成例を示すブロック図である。
【図２】送信、受信ＩＰアドレスから２次元ビットマップを構成する手法を示す図である。
【符号の説明】
【００３１】
１０１…監視対象網、１０２…トラヒック送信端末、１０３…トラヒック受信端末、１０４〜１０７…ルータ等のネットワーク機器、１１０…端末間通信パターン監視装置、１１１…トラヒックデータ取得部、１１２…ハッシュマトリクス生成／記憶部、１１３…端末間通信パターン類似度計算部、２０１…行列、２０２…送信端末のＩＰアドレス、２０３…受信端末のＩＰアドレス
【図１】
2008172401.tif 000005
【図２】
2008172401.tif 000006