(57)【要約】【課題】大量フロー生成ホストを特定できる技術を構築する。【解決手段】新規フロー判定装置１０３は測定期間内にサンプルされたフローが新規のフローであるか否かを判定する。ホストテーブル１０４は新規フロー判定装置１０３で新規のフローであると判定された場合に該当ホストのフロー数が更新される。大量フロー生成ホスト特定装置１０５はホストテーブル１０４内のフロー数が予め定めた閾値Ｙ以上となったホストを大量フロー生成ホストとして特定する。フローサンプリング装置１０２はフローサンプリング確率ｆでフローをサンプルする。パラメータ設計装置１０１はフローサンプリング確率ｆと閾値Ｙを設計する。パラメータ設計装置１０１が設計したフローサンプリング確率ｆと閾値Ｙがそれぞれフローサンプリング装置１０２と大量フロー生成ホスト特定装置１０５に設定される。【選択図】図１
2007221412.tif 000002
【特許請求の範囲】
【請求項１】
フローサンプリングによって得られた統計データのみを用いて、測定期間内に生成するフロー数が閾値以上となるホストを大量フロー生成ホストとして特定することを特徴とする大量フロー生成ホスト特定方法。
【請求項２】
請求項１に記載の大量フロー生成ホスト特定方法において、サンプルされたパケットが未カウントのフローに属しているか否かの判定に、Bloom filterを用いることを特徴とする大量フロー生成ホスト特定方法。
【請求項３】
請求項１に記載の大量フロー生成ホスト特定方法において、ホストごとにサンプルされたフロー数を集計し、集計値が予め定めた閾値Ｙ以上となったホストを大量フロー生成ホストとして特定することを特徴とする大量フロー生成ホスト特定方法。
【請求項４】
請求項３に記載の大量フロー生成ホスト特定方法において、測定期間内に着目リンクに到着する総フロー数Ｍと、測定期間内にホストが生成したフロー数を総フロー数Ｍで除したフロー数比率の閾値ｑ＊と、フロー数比率が閾値ｑ＊のホストが特定される確率Ｈ＊と、閾値Ｙとが与えられ、Ｆ＝ｆＭとしたときに、
【数１】
2007221412.tif 000008
よりフローをサンプルする確率であるフローサンプリング確率ｆを導出することを特徴とする大量フロー生成ホスト特定方法。
【請求項５】
請求項３に記載の大量フロー生成ホスト特定方法において、測定期間内に着目リンクに到着する総フロー数Ｍと、測定期間内にホストが生成したフロー数を総フロー数Ｍで除したフロー数比率の閾値ｑ＊と、フロー数比率の閾値ｑ＊のホストが特定される確率Ｈ＊と、フローをサンプルする確率であるフローサンプリング確率ｆが与えられ、Ｆ＝ｆＭとしたときに、
【数２】
2007221412.tif 000009
より閾値Ｙを導出することを特徴とする大量フロー生成ホスト特定方法。
【請求項６】
請求項３に記載の大量フロー生成ホスト特定方法において、測定期間内に着目リンクに到着する総フロー数Ｍ、フローをサンプルする確率であるフローサンプリング確率ｆ、測定期間内にホストが生成したフロー数を総フロー数Ｍで除したフロー数比率の閾値ｑ＊、フロー数比率の閾値ｑ＊のホストが特定される確率Ｈ＊が与えられたときに、任意のフロー数比率ｑを有するホストが特定される確率Ｈを導出し、ｑとＨの関係を表す曲線である特定曲線を得ることを特徴とする大量フロー生成ホスト特定方法。
【請求項７】
請求項３に記載の大量フロー生成ホスト特定方法において、所要メモリ量と所要最大メモリアクセス数を求めることを特徴とする大量フロー生成ホスト特定方法。
【請求項８】
測定期間内にサンプルされたフローが新規のフローであるか否かを判定する新規フロー判定装置と、
前記新規フロー判定装置で新規のフローであると判定された場合に該当ホストのフロー数が更新されるホストテーブルと、
前記ホストテーブル内のフロー数が予め定めた閾値Ｙ以上となったホストを大量フロー生成ホストとして特定する大量フロー生成ホスト特定装置と、
を備えることを特徴とする大量フロー生成ホスト特定システム。
【請求項９】
請求項８に記載の大量フロー生成ホスト特定システムにおいて、
フローサンプリング確率ｆでフローをサンプルするフローサンプリング装置と、
フローサンプリング確率ｆと閾値Ｙを設計するパラメータ設計装置と、
を備え、
前記パラメータ設計装置が設計したフローサンプリング確率ｆと閾値Ｙがそれぞれ前記フローサンプリング装置と前記大量フロー生成ホスト特定装置に設定されることを特徴とする大量フロー生成ホスト特定システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大量フロー生成ホストを特定する方法およびシステムに関する。
【背景技術】
【０００２】
近年、ワーム、ウイルス、ＤＤｏＳ等が引き起こす異常トラヒックが、ネットワークやサーバに深刻な被害をもたらすことが問題となっている。ＤＤｏＳの踏み台にされたホストや、ワームやウイルスに感染したホストは、個々のフローサイズは小さいものの短時間に大量のフローを生成するという特徴がある。そのため、短時間に大量のフローを生成するホストを早急に特定し、特定したホストに対して注意を促したり、ネットワークから切り離すといった対処をとることが重要となる。
【０００３】
フローサイズやフロー時間といったフローの各種統計値を収集するための技術として、パケット流からパケットを一定周期もしくはランダムに抜き出すパケットサンプリングが注目されている。リンクの回線容量が２．５Ｇｂｐｓや１０Ｇｂｐｓと高速化するにつれ、全てのフロー状態を管理することが困難になるため、パケットサンプリングにより一部のフロー状態のみを管理し、各種フロー統計値を得ることは実用上、非常に有用である。そこで、パケットサンプリングによって得られた情報から、測定期間内に送出されたパケット数が閾値以上となる高レートフローを特定する方法が検討されている。しかし大量フロー生成ホストが生成する個々のフローのサイズは小さいため、高レートフローの特定方法ではこのようなホストを効果的に特定することができない。
【０００４】
大量フロー生成ホストを特定するには、パケット単位ではなく、フローを単位にサンプリングを行い、ホストごとに生成フロー数を集計することが有効である。このような観点から、一つ以上のフローがサンプルされたホストを大量フロー生成ホストと見なし、それらホストが測定期間内に生成したフロー数を計測する方法が検討されている。しかしフロー数比率ｑ（測定期間内においてあるホストが生成したフロー数ｍを全フロー数Ｍで除したもの）の特定閾値を明示的に与えることができず、任意のフロー数比率ｑを有するホストが特定される確率である特定曲線も得られない。
以上の技術については、下記非特許文献１〜３を参照されたい。
【０００５】
【非特許文献１】森，川原，上山，石橋，阿部，“通信パターン分析に基づくワーム感染ホスト検出方法”，信学技報ＣＱ、２００５−１１．
【非特許文献２】上山，森，“高レートフロー特定方式の特定精度向上に関する検討”，信学技報ＩＮ，２００５−７．
【非特許文献３】K. Keys, D. Moore, C. Estan、“A Robust System for Accurate Real-time Summaries of Internet Traffic,”ＡＣＭ  ＡＩＧＭＥＴＲＩＣＳ２００５．
【発明の開示】
【発明が解決しようとする課題】
【０００６】
従来の大量フロー生成ホスト特定方法では、フロー数比率に対する特定確率が定式化されておらず、特定されるフロー数比率の閾値の与え方が明らかでない。大量フロー生成ホストの特定を行う際には、大量フローと定義するフロー数比率の閾値ｑ＊とその特定確率Ｈ＊を設計できることが実用上、重要である。さらに、フロー数比率ｑがｑ＜ｑ＊のフローが誤って特定される確率（ＦＰＲ：False Positive Ratio）と、ｑ≧ｑ＊のフローが誤って特定されない確率（ＦＮＲ：False Negative Ratio）を明確にし、特定精度を明らかにすることが重要である。そのためには、ｑ＊とＨ＊を与えたときの任意のｑに対する特定確率Ｈ（ｑとＨの関係を表す曲線を特定曲線という）を明らかにする必要がある。
【０００７】
本発明の目的は、大量フロー生成ホストを特定できる技術を構築することにある。また、測定期間内にホストが生成したフロー数を着目リンクに到着する総フロー数で除したフロー数比率の閾値ｑ＊とフロー数比率の閾値ｑ＊のホストが特定される確率Ｈ＊と大量フロー生成ホストとして特定するためのフロー数の閾値である特定閾値Ｙを与えたときに、フローをサンプルする確率であるフローサンプリング確率ｆを導出する、もしくはｑ＊とＨ＊とｆを与えたときにＹを導出する、ことが可能な、フローサンプリング情報を用いた大量フロー生成ホスト特定技術を構築することにある。
【課題を解決するための手段】
【０００８】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、以下のとおりである。
【０００９】
本発明の大量フロー生成ホスト特定方法は、フローサンプリングによって得られた統計データのみを用いて、測定期間内に生成するフロー数が閾値以上となるホストを大量フロー生成ホストとして特定することを特徴とする。また、サンプルされたパケットが未カウントのフローに属しているか否かの判定に、Bloom filterを用いることを特徴とする。また、ホストごとにサンプルされたフロー数を集計し、集計値が予め定めた閾値Ｙ以上となったホストを大量フロー生成ホストとして特定することを特徴とする。
【００１０】
本発明の大量フロー生成ホスト特定システムは、測定期間内にサンプルされたフローが新規のフローであるか否かを判定する新規フロー判定装置と、前記新規フロー判定装置で新規のフローであると判定された場合に該当ホストのフロー数が更新されるホストテーブルと、前記ホストテーブル内のフロー数が予め定めた閾値Ｙ以上となったホストを大量フロー生成ホストとして特定する大量フロー生成ホスト特定装置と、を備えることを特徴とする。また、フローサンプリング確率ｆでフローをサンプルするフローサンプリング装置と、フローサンプリング確率ｆと閾値Ｙを設計するパラメータ設計装置と、を備え、前記パラメータ設計装置が設計したフローサンプリング確率ｆと閾値Ｙがそれぞれ前記フローサンプリング装置と前記大量フロー生成ホスト特定装置に設定されることを特徴とする。
【発明の効果】
【００１１】
本発明によれば、フロー計測から得られたデータを用いて、測定期間内に生成されるフロー数が閾値を超える大量フロー生成ホストを特定できるという効果がある。
【発明を実施するための最良の形態】
【００１２】
図１は、本発明の大量フロー生成ホスト特定方法で大量フロー生成ホストを特定する大量フロー生成ホスト特定システムの実施の形態の一例を示すシステム構成図である。図１において、１０１はパラメータ設計装置、１０２はフローサンプリング装置、１０３は新規フロー判定装置、１０４はホストテーブル、１０５は大量フロー生成ホスト特定装置、１０６は大量フロー生成ホストリストである。
【００１３】
パラメータ設計装置１０１により任意の特定曲線を実現するフローサンプリング確率ｆ（フローをサンプルする確率）と特定閾値Ｙ（大量フロー生成ホストとして特定するためのフロー数の閾値）が設計され、それぞれフローサンプリング装置１０２と大量フロー生成ホスト特定装置１０５に設定される。測定期間中は、フローサンプリング装置１０２により着目リンクを流れるフローが一定確率（フローサンプリング確率ｆ）でサンプルされ、サンプルされたフローが新規のフロー（未カウント）であるか否かを新規フロー判定装置１０３が判定し、新規フローであった場合にはホストテーブル１０４の該当ホストのフロー数が更新される。大量フロー生成ホスト特定装置１０５はホストテーブル１０４に登録されたホストのフロー数から大量フロー生成ホストを特定し、大量フロー生成ホストリスト１０６に出力する。
【００１４】
すなわち、本実施の形態の大量フロー生成ホスト特定システムは、測定期間内にサンプルされたフローが新規のフローであるか否かを判定する新規フロー判定装置１０３と、新規フロー判定装置１０３で新規のフローであると判定された場合に該当ホストのフロー数が更新されるホストテーブル１０４と、ホストテーブル１０４内のフロー数が予め定めた閾値Ｙ以上となったホストを大量フロー生成ホストとして特定する大量フロー生成ホスト特定装置１０５と、を備えている。また、フローサンプリング確率ｆでフローをサンプルするフローサンプリング装置１０２と、フローサンプリング確率ｆと閾値Ｙを設計するパラメータ設計装置１０１と、を備え、パラメータ設計装置１０１が設計したフローサンプリング確率ｆと閾値Ｙがそれぞれフローサンプリング装置１０２と大量フロー生成ホスト特定装置１０５に設定される。そして、大量フロー生成ホスト特定装置１０５は特定した大量フロー生成ホストのリストを大量フロー生成ホスト１０６に出力する。
【００１５】
次に、本発明の実施の形態に係る大量フロー生成ホスト特定方法について、１．動作原理、２．パラメータ設定方法、３．所要メモリサイズの導出、４．所要最大メモリアクセス数の導出、をそれぞれ説明する。
【００１６】
１．動作原理
フローを、発着ＩＰアドレス、発着ポート番号が共通のパケットの集合と定義する。そして、長さがφ（ｓ）の任意の測定期間Φを定め、Φ内に着目リンクに到着した総フロー数をＭとする。そして各ホストに対して、Φ内に生成したフロー数をｍとするとき、フロー数比率ｑをｑ≡ｍ／Ｍと定義する。任意に定めた閾値ｑ＊に対して、ｑ≧ｑ＊のホストを大量フロー生成ホストと定義し、着目リンクにおいて、大量フロー生成ホストをΦ内で特定する。
【００１７】
着目リンクに到着した各パケットに対して、発着ＩＰアドレスと発着ポート番号の計９６ビットをキーにして、予め用意したハッシュ関数を通して得られるβビットの値をｖするとき、ｖ＜ｗであるときにのみ新規フロー判定装置に入力する。ただしｗはフローサンプリングのための閾値であり、ｆをフローサンプリング確率とするとｆ＝ｗ／２βとなる。同一フローに属するフローは同一のキーを持つため、フローサイズとは無関係に全てのフローが確率ｆでサンプルされることになる。
【００１８】
ｖ＜ｗであった場合、次に到着パケットが属するフローを既にカウントしたかどうかを判定する。最も直感的な方法は、サンプルした全てのフローをフローテーブルにて管理し、フローテーブルに該当フローのエントリが存在するか否かを判定する方法であるが、最大で全エントリをチェックする必要があるため処理時間が大きくなる。そこでここでは、Bloom filterを用いて判定する方法を用いる。Bloom filterはある候補に対してある集合のメンバであるか否かを判定する方法であり、異なるｋ個のハッシュ関数（各々が入力キーに対してｂビットの値を返す）と２ｂ個の２値変数（初期状態では全てゼロにリセットされる）が用意される。この場合、パケットの９６ビットのキーをｋ個のハッシュ関数を通して得られるｋ個のアドレスに該当する２値変数の値を調べ、１つ以上がゼロである場合に該当パケットが属するフローを新規フローと判定する。そしてｋ個の該当する２値変数を全て１にセットする。Bloom filterを用いた場合、既にカウントしたフローを誤って新規フローと見なす可能性はゼロであるが、ハッシュ値の衝突によって新規フローを誤って見逃す可能性がある。
【００１９】
ホストテーブル１０４には発ＩＰアドレスとサンプルフロー数が収容される。新規フローと判定された場合には、該当パケットの発ＩＰアドレスが既にホストテーブル内にエントリされているか否か調べ（例えば発ＩＰアドレスをキーにしてハッシュ値のアドレスを調べる）、既にエントリが存在する場合にはサンプルフロー数を１だけ増加させる。この結果、サンプルフロー数が閾値Ｙに達した場合には、そのホストを大量フロー生成ホストとして特定し、大量フロー生成ホストリストに書き出す。一方、発ＩＰアドレスがホストテーブル内にエントリされていない場合には、新規にエントリを生成する。
【００２０】
図２に、本発明の処理のフローチャートを示す。図２において、パケットが到着すると（ステップ２０１）、ハッシュ値ｖを算出する（ステップ２０２）。算出されたハッシュ値ｖがフローサンプリングのための閾値ｗより小さいかどうかが判断される（ステップ２０３）。ステップ２０３でＮの場合は終了する（サンプルしない）。ステップ２０３でＹの場合は、Bloom filterによる新規フローの判定を行い（ステップ２０４）、新規フローでない場合（ステップ２０５でＮの場合）は終了する。新規フローである場合（ステップ２０５でＹの場合）はホストテーブル１０４内の該当発ホストのサンプルフロー数ｃを１加算し（ステップ２０６）、ｃが閾値Ｙと等しくない場合（ステップ２０７でＮの場合）は終了する。ｃが閾値Ｙと等しい場合は当該発ホストを大量フロー生成ホストとして特定する（ステップ２０８）。ここで、ステップ２０１〜２０３はフローサンプリング装置１０２が処理し、ステップ２０４〜２０６は新規フロー判定装置１０３が処理し、ステップ２０７〜２０８は大量フロー生成ホスト特定装置が処理する。大量フロー生成ホスト特定装置１０５が大量フロー生成ホストリスト１０６に書き出すタイミングとしては、測定期間が終了した時点でまとめて書き出す方法も考えることができるが、その他のタイミングでもよい。
【００２１】
すなわち、本実施の形態の大量フロー生成ホスト特定方法は、フローサンプリングによって得られた統計データのみを用いて、測定期間内に生成するフロー数が閾値以上となるホストを大量フロー生成ホストとして特定するものである。また、サンプルされたパケットが未カウントのフローに属しているか否かの判定に、Bloom filterを用いるものである。また、ホストごとにサンプルされたフロー数を集計し、集計値が予め定めた閾値Ｙ以上となったホストを大量フロー生成ホストとして特定するものである。
【００２２】
２．パラメータ設定方法
フロー数比率がｑのホストからｊ個のフローが測定期間Φ内でサンプルされる確率はＦＣｊ（１−ｑ）Ｆ−ｊｑｊで与えられる（ＦはΦ内の総サンプルフロー数であり、Ｆ＝ｆＭである）。よってこのホストが特定される確率Ｈは、
【００２３】
【数３】
2007221412.tif 000003
となる。フロー数比率の閾値ｑ＊のホストを確率Ｈ＊で特定するためには、
【００２４】
【数４】
2007221412.tif 000004
となるようにＹとＦを設定すればよい。すなわち、ＹとＦのどちらか一方を与えれば、式（２）を数値的に解くことによりもう一方を決めることができる。Ｍの値として例えば前測定期間における実測値を用いれば、Ｙとｆのどちらか一方が自動的に決まると考えることもできる。
【００２５】
Ｙが大きなほど、特定精度が向上する反面、所要メモリ量が増加することが予想される。よってＹを調整することにより特定精度と所要メモリ量の間にトレードオフが得られる。例えば、許容システムコスト（メモリ量）の範囲内で最大のＹを選択し、フローサンプリング確率ｆを設計することが可能である。また同様に、ｆが大きなほど特定精度が向上する反面、所要メモリ量が増加することが予想されるので、許容メモリ量の範囲内で最大のｆを選択し、閾値Ｙを設計するといったことも可能である。
【００２６】
以上のパラメータの設計をパラメータ設計装置１０１が行い、パラメータ設計装置１０１が設計したフローサンプリング確率ｆと閾値Ｙがそれぞれフローサンプリング装置１０２と大量フロー生成ホスト特定装置１０５に設定される。
【００２７】
３．  所要メモリ量の導出
ハッシュ関数には、高性能で知られるＨ３を用いることを想定する。フローサンプリングのハッシュ関数のために必要となるメモリ量は９６β［bits］である。新規フローの判定処理には２値変数の収容のために２ｂ［bits］、ハッシュ関数のために９６ｂｋ［bits］が必要である。最後に、ホストテーブルのためには、エントリされるホスト数の最大値をＥｍａｘとすると、
【００２８】
【数５】
2007221412.tif 000005
が必要になる。ここで、ｌｏｇ２Ｙを挟む記号は、挟んだ数を下まわらない最小の整数を意味する記号であり、例えばｌｏｇ２Ｙが３．６である場合は４になる。これらを合わせ、所要メモリ量［bits］は次式で算出できる。
【００２９】
【数６】
2007221412.tif 000006
４．所要最大メモリアクセス数の導出
１個の到着パケットに対して必要になる最大メモリアクセス数を考える。Ｈ３を用いればハードウェアで容易にハッシュ関数を構築できるためハッシュ値を求める処理は考慮しない。新規フローの判定処理にｋ回のメモリアクセスが必要である。ホストテーブルの更新には、ホストのＩＰアドレスをキーにハッシュ関数を用いてエントリを収容することを想定し、ハッシュ値の衝突による収容アドレスの調整が生じる回数の最大値をＣｍａｘとするとＣｍａｘ＋１となる。よって所要最大メモリアクセス数は次式で求まる。
【００３０】
【数７】
2007221412.tif 000007
以上説明した実施の形態において、ホストテーブルおよび大量フロー生成ホストリストは記憶装置に記憶される。また、各装置はコンピュータと記憶装置に記憶されたプログラムで構成できる。また、そのプログラムの一部または全部に代えてハードウェアで構成してもよい。
【００３１】
以上、本発明者によってなされた発明を、前記実施形態に基づき具体的に説明したが、本発明は、前記実施形態に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは勿論である。
【図面の簡単な説明】
【００３２】
【図１】本発明の実施の形態の一例を示すシステム構成図
【図２】本発明の処理の流れを示すフローチャート
【符号の説明】
【００３３】
１０１…パラメータ設計装置、１０２…フローサンプリング装置、１０３…新規フロー判定装置、１０４…ホストテーブル、１０５…大量フロー生成ホスト特定装置、１０６…大量フロー生成ホストリスト
【図１】
2007221412.tif 000010
【図２】
2007221412.tif 000011