高パケットレートフロー検出装置及び高パケットレートフロー検出方法
【課題】パケットサンプリング技術を用いることで、パケットレートが所定値以上のトラヒックのフローを検出することを目的とする。
【解決手段】パケットレートが所定値以上のトラヒックのフローを検出する高パケットレートフロー検出装置は、パケットを無作為に抽出するパケット無作為抽出部と、所定の測定期間を部分区間に分割し、部分区間内に抽出されたパケット数をフロー毎に集計するパケット数測定部と、部分区間においてパケット数が閾値以上のフローを、パケットレートが所定値以上のトラヒックフローであるとして検出する高パケットレートフロー検出部とを有する。
【解決手段】パケットレートが所定値以上のトラヒックのフローを検出する高パケットレートフロー検出装置は、パケットを無作為に抽出するパケット無作為抽出部と、所定の測定期間を部分区間に分割し、部分区間内に抽出されたパケット数をフロー毎に集計するパケット数測定部と、部分区間においてパケット数が閾値以上のフローを、パケットレートが所定値以上のトラヒックフローであるとして検出する高パケットレートフロー検出部とを有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、高パケットレートフロー検出装置及び高パケットレートフロー検出方法に関する。
【背景技術】
【０００２】
近年、インターネット上では公的機関や企業のサーバなどを狙った、Ｄｅｎｉａｌ ｏｆ Ｓｅｒｖｉｃｅ（ＤｏＳ）攻撃が深刻な問題となっている。ＤｏＳ攻撃とは、サーバがクライアントに対して供給するサービスを、不正なパケットを送りつけることによって妨害するという、ネットワークを利用した攻撃のことである。ＤｏＳ攻撃の代表的なものとしてＳＹＮ Ｆｌｏｏｄ攻撃とｓｍｕｒｆ攻撃がある。
【０００３】
ＳＹＮ Ｆｌｏｏｄ攻撃とは、攻撃者が攻撃対象のサーバに対してＴＣＰの接続要求であるＳＹＮパケットを、ヘッダを改竄した後に大量に送りつけるというものである。ＳＹＮパケットを受け取ったサーバは送信元に対してＳＹＮ／ＡＣＫを返す。しかしＳＹＮパケットのヘッダに書かれている送信元のＩＰアドレスが実際には存在しないアドレスに書き換えられているため、サーバからのＳＹＮ／ＡＣＫに対してＡＣＫを返すクライアントは存在せず、サーバは返ってこないＡＣＫをタイムアウトになるまで待ち続けなければならない。この状態はｈａｌｆ−ｏｐｅｎと呼ばれ、ｈａｌｆ−ｏｐｅｎ状態のコネクション情報はサーバ内のｂａｃｋｌｏｇ ｑｕｅｕｅに蓄積される。ｂａｃｋｌｏｇ ｑｕｅｕｅのサイズはサーバ毎に決められており、このｂａｃｋｌｏｇ ｑｕｅｕｅが一杯のときは、サーバはクライアントからの接続要求に応えることができない。すなわち、送信元ＩＰアドレスを改竄したＳＹＮパケットが大量に送られてくると、サーバのｂａｃｋｌｏｇ ｑｕｅｕｅは常に一杯の状態になってしまい、正常なクライアントに対してＴＣＰ接続を確立することができず、サービスを供給できなくなる。
【０００４】
一方、ｓｍｕｒｆ攻撃とは、ＩＣＭＰ ｅｃｈｏ ｒｅｑｕｅｓｔを用いたＤｏＳ攻撃であり、攻撃者はＩＣＭＰ ｅｃｈｏ ｒｅｑｕｅｓｔパケットの送信元ＩＰアドレスを攻撃対象のホストのＩＰアドレスに偽装し、そのパケットをネットワークのブロードキャストアドレスに送る。すると、パケットを受け取ったネットワーク内の全てのホストから攻撃対象のホストに向けてＩＣＭＰ ｅｃｈｏ ｒｅｐｌｙパケットが一斉に返される。この大量のＩＣＭＰパケットによって攻撃対象のホストやネットワークに過重負荷がかかるため、サーバなどではサービスの提供が困難になる。
【０００５】
どのようなＤｏＳ攻撃であっても、単一のホストからの攻撃であれば攻撃の規模には限度があるが、複数のホストから一斉にＤｏＳ攻撃を行うＤｉｓｔｒｉｂｕｔｅｄ ＤｏＳ（ＤＤｏＳ）攻撃は、攻撃の規模と攻撃元の分散性から攻撃を受けたサーバでの対処が難しいため、ネットワーク、とりわけバックボーンネットワークの管理者の立場において検出することが、その後の対応を行う上で重要となる。
【０００６】
直接の攻撃とは別に、ＳＹＮ Ｆｌｏｏｄ攻撃が起こった際にその副産物としてバックスキャッタと呼ばれるトラヒックが観測される。これは攻撃を受けたサーバから偽装されたＩＰアドレスに向けて送られるＳＹＮ／ＡＣＫパケット群であり、その多くは実際には使われていないＩＰアドレスが指定されているため、ヘッダのＴＴＬがゼロなるまでネットワーク内を流れつづけることになる。実際には使われていないＩＰアドレスに向けて送られるパケットを観測するシステムとしてＮｅｔｗｏｒｋ ｔｅｌｅｓｃｏｐｅがある。Ｎｅｔｗｏｒｋ ｔｅｌｅｓｃｏｐｅはＩＰｖ４の全アドレス空間のうちのほとんど正常なＩＰアドレスが存在しない部分空間を観測するためのシステムである。その性質から、バックスキャッタのトラヒックやワームによるランダムスキャンのなどの観察に適している。
【０００７】
また、ＤｏＳ攻撃の検出に関連する研究としては以下のようなものがある。Ｖ． Ａ． Ｓｉｒｉｓらはトラヒックに含まれるＳＹＮパケットの数を計測し、２種類のアルゴリズムを用いて動的に閾値を定め、閾値を超えるＳＹＮパケットが計測された場合にＳＹＮ Ｆｌｏｏｄ攻撃の発生を検出するという手法を提案している（非特許文献１参照）。大下らもＳＹＮ Ｆｌｏｏｄ攻撃を検出する手法を提案している。彼らの手法はｂａｃｋｌｏｇ ｑｕｅｕｅのサイズとタイムアウトになる時間を考慮し、サーバがサービス停止状態になる前に検出を行う。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Ｖ． Ａ． Ｓｉｒｉｓ ａｎｄ Ｆ． Ｐａｐａｇａｌｏｕ， "Ａｐｐｌｉｃａｔｉｏｎ ｏｆ ａｎｏｍａｌｙ ｄｅｔｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｄｅｔｅｃｔｉｎｇ ｓｙｎ ｆｌｏｏｄｉｎｇ ａｔｔａｃｋｓ，" Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， ｖｏｌ．２９， ｎｏ．９， ｐｐ．１４３３−１４４２， ２００６．
【発明の概要】
【発明が解決しようとする課題】
【０００９】
Ｖ． Ａ． Ｓｉｒｉｓらはトラヒックに含まれるＳＹＮパケットの数を計測し、２種類のアルゴリズムを用いて動的に閾値を定め、閾値を超えるＳＹＮパケットが計測された場合にＳＹＮ Ｆｌｏｏｄ攻撃の発生を検出するという手法を提案しているが、彼らの手法は、ＳＹＮ Ｆｌｏｏｄ攻撃が発生していることは検知できても、ＳＹＮ Ｆｌｏｏｄ攻撃のフローを特定することができないという問題がある。また大下らもＳＹＮ Ｆｌｏｏｄ攻撃を検出する手法を提案しているが、トラヒックを観測するポイントが、サーバ側のネットワークへのインターフェース部分を想定しており、バックボーンＮＷを対象としたものではない。さらにトラヒックの全パケットを観測しているため、高速な回線を測定対象とした場合のスケール性に問題がある。
【００１０】
本発明は、バックボーンＮＷの任意のルータポートを観測対象とし、パケットサンプリング技術を用いることで、回線レートが高速である場合にも対応可能な、持続的な高パケットレートフロー（パケットレートが所定値以上のトラヒックのフロー）を検出することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の高パケットレートフロー検出装置は、
パケットレートが所定値以上のトラヒックのフローを検出する高パケットレートフロー検出装置であって、
パケットを無作為に抽出するパケット無作為抽出部と、
所定の測定期間を部分区間に分割し、部分区間内に抽出されたパケット数をフロー毎に集計するパケット数測定部と、
部分区間においてパケット数が閾値以上のフローを、パケットレートが所定値以上のトラヒックフローであるとして検出する高パケットレートフロー検出部と、
を有することを特徴とする。
【００１２】
本発明の高パケットレートフロー検出方法は、
パケットレートが所定値以上のトラヒックのフローを検出する高パケットレートフロー検出装置における高パケットレートフロー検出方法であって、
パケットを無作為に抽出するステップと、
所定の測定期間を部分区間に分割し、部分区間内に抽出されたパケット数をフロー毎に集計するステップと、
部分区間においてパケット数が閾値以上のフローを、パケットレートが所定値以上のトラヒックフローであるとして検出するステップと、
を有することを特徴とする。
【発明の効果】
【００１３】
本発明によれば、パケットサンプリング技術を用いることで、パケットレートが所定値以上のトラヒックのフローを検出することが可能になる。
【図面の簡単な説明】
【００１４】
【図１】本発明の実施例に係る高パケットレートフロー検出装置の構成図
【図２】本発明の実施例に係る高パケットレートフロー検出装置のパケット無作為抽出部で実行される処理プロセスのフローチャート
【図３】本発明の実施例に係る高パケットレートフロー検出装置のＩＷ情報の更新部で実行される処理プロセスのフローチャート
【図４】本発明の実施例に係る高パケットレートフロー検出装置の高パケットレートフロー検出部で実行される処理プロセスのフローチャート
【図５】スライディングウィンドウの概要を示す図
【図６】制御パラメータｆが制約条件を満たす領域を示す図
【図７】制御パラメータｆが制約条件を満たす領域を示す図
【図８】スライディングウィンドウの母集団におけるパケット数の説明図
【図９】スライディングウィンドウのサンプルにおけるパケット数の説明図
【図１０】実験に用いたトラヒックデータの概要を示す表
【図１１】実験に用いた規定パラメータを示す表
【図１２】実験で得られた制御パラメータ（ｆ，ｍ）を示す表
【図１３】閾値の候補と検出率の関係を示す図（Ｂａｃｋｓｃａｔｔｅｒ）
【図１４】閾値の候補と検出率の関係を示す図（ＣＥＳＣＡ−Ｉ（Ｒ＝８００））
【図１５】閾値の候補と検出率の関係を示す図（ＣＥＳＣＡ−Ｉ（Ｒ＝１０００））
【図１６】サンプルにおける閾値を示す表
【図１７】実験結果の平均と９５％信頼区間を示す表
【発明を実施するための形態】
【００１５】
以下、図面を参照して本発明の実施例について説明する。
【００１６】
本発明の実施例では、長さＴ秒の測定期間に含まれる長さｔ秒の任意の部分区間において、パケットレートがＲ［ｐａｃｋｅｔｓ／ｓｅｃ］以上のフローを、ランダムパケットサンプリングによって得られた情報からオンラインで検出することを特徴とする持続的な高パケットレートフローのオンライン検出法について説明する。
【００１７】
より具体的には、長さＴＳＷ＝Ｔの測定期間（スライディングウィンドウＳＷ）を自然数ｋとｍに対してｋｍ個のベーシックウィンドウ（ＢＷ）に分割し、さらにｈ≦ｋかつｋとは互いに素な自然数ｈを用いて、連続するｈｍ個のＢＷで構成される検査ウィンドウ（ＩＷ）をＳＷ内に（ｋ−ｈ）ｍ＋１個作成し、ＳＷ内の全てのＩＷにおいてパケットレートがＲ［ｐａｃｋｅｔｓ／ｓｅｃ］以上であるフローを検出する。なお、検査ウィンドウの大きさＴＩＷ＝ｔはｋとｈとにより決まり、ＴＩＷ＝（ｈ／ｋ）ＴＳＷ［ｓｅｃ］となることに注意する。
【００１８】
＜高パケットレートフロー検出装置の構成＞
図１は、持続的な高パケットレートフローのオンライン検出法を実現するための、本発明の実施例に係る高パケットレートフロー検出装置の構成図である。
【００１９】
本実施例に係る高パケットレートフロー検出装置は、パラメータｆとｍの設計部１０１と、パラメータｗ＊の設計部１０２と、パケット無作為抽出部１０３と、ＢＷ情報保存部１０４と、ＩＷ情報の更新部１０５と、ＩＷ情報保存部１０６と、高パケットレートフロー検出部１０７とを有する。
【００２０】
パラメータｆとｍの設計部１０１は、パケットサンプリング確率ｆとＢＷの大きさを定めるパラメータｍとを設計する。パラメータｆとｍの設計部１０１は、目標時間ＴＤ＿ｍａｘ内に検出すること、ＢＷの幅が最大許容値ＴＢＷ＿ｍａｘ以下であること、を制約条件とし、検出対象外のフローの誤検出率を最小化するｆとｍとを設計する。
【００２１】
具体的には以下に説明するように、パラメータｆとｍの設計部１０１は、入力パラメータである、ＳＷの長さＴＳＷ［ｓｅｃ］、１サンプルパケットあたりの処理時間Δ１［ｓｅｃ］、ＳＷの解析に必要なパケット数とは独立な処理時間Δ２［ｓｅｃ］、検出目標時間ＴＤ＿ｍａｘ［ｓｅｃ］、観測する回線の最大パケットレートＣｍａｘ［ｐａｃｋｅｔｓ／ｓｅｃ］、ＢＷの幅の最大許容値ＴＢＷ＿ｍａｘ［ｓｅｃ］、に対して、
【００２２】
【数１】
と定義するとき、
【００２３】
【数２】
の場合には、ｍを
【００２４】
【数３】
に設定し、ｆをｆ＊＝ｍａｘ｛ｆ１（ｍ＋），ｆ２（ｍ−）｝に設定する。一方、
【００２５】
【数４】
の場合には、ｍ＊＝ｍ＋、ｆ＊＝ｆ１（ｍ＋）に設定する。
【００２６】
パラメータｗ＊の設計部１０２は、高パケットレートフローを検出する際のサンプルパケット数に関する閾値ｗ＊を設計する。具体的には、ｆとｍが最適設計された後で、与えられた高レートフローの見逃し許容誤差εに対して、検出対象フローの検出見逃し確率を許容値ε以下に抑えるよう、ＩＷ内のサンプルパケット数の閾値ｗ＊を設計する。
【００２７】
パラメータｗ＊の設計部１０２は、検出確率が最低となる閾値フローの分布Ｘ＊（各ＢＷにおけるパケット数の確率分布）に対して、このようなフローが全てのＩＷにおいてｗ個以上のパケットがサンプルされる確率をＰ（ｗ｜Ｘ＊）、高レートフローの見逃し許容誤差をεとするとき、ｗ＊を、
【００２８】
【数５】
により設計する。ただしＰ（ｗ｜Ｘ＊）はモンテカルトシミュレーションを用いた数値実験により求める。
【００２９】
パケット無作為抽出部１０３は、測定対象となるルータポートを流れる各パケットに対して各々独立に確率ｆでパケットをサンプリングする。
【００３０】
図２に、パケット無作為抽出部１０３で実行される処理プロセスのフローチャートを示す。測定対象のルータポートにパケットが到着するごとに、０から１の値をとる一様乱数ｘを発生させ（Ｓ１０１）、その値がｆより小さい場合には（Ｓ１０２：Ｙ）、到着パケットをサンプリングし（Ｓ１０３）、ＢＷ情報保存部１０４の該当フローのサンプルパケット数を全て１だけ増加させる。
【００３１】
ＢＷ情報保存部１０４は、ＢＷ内でサンプルされたパケット数を各フローに対して保存する。
【００３２】
ＩＷ情報の更新部１０５は、ＢＷの境界時点において、ＢＷ情報保存部１０４のサンプルパケット数情報を、現在のＢＷを含む全てのＩＷに対して、フローごとに足しこむ。また最古のＢＷを含むＩＷを破棄し、連続する最近のｋｍ個のＢＷを用いて新しいＩＷを作成する。このように、ＩＷ情報の更新部は、測定期間ＳＷを任意の部分区間ＩＷに分割し、部分区間内に抽出されたパケット数をフロー毎に集計する。
【００３３】
図３に、ＩＷ情報の更新部１０５で実行される処理プロセスのフローチャートを示す。ＢＷの境界時点において、ＢＷ情報保存部１０４のサンプルパケット数情報を、現在のＢＷを含む全てのＩＷに対して、フローごとに足しこみ（Ｓ２０１）、ＢＷ情報保存装置１０４の全エントリをゼロに初期化する（Ｓ２０２）。またＩＷ情報保存部１０６において、最古のＢＷを含むＩＷを破棄し、連続する最近のｋｍ個のＢＷを用いて新しいＩＷを作成する（Ｓ２０３）。
【００３４】
ＩＷ情報保存部１０６は、ＩＷの情報（（ｋ−ｈ）ｍ＋１の各ＩＷにおける各フローのサンプルパケット数）を保存する。
【００３５】
高パケットレートフロー検出部１０７は、ＳＷに含まれる（ｋ−ｈ）ｍ＋１個の全ＩＷにおいてｗ＊個以上のパケットがサンプルされたフローを高レートフローとして検出する。
【００３６】
図４に、高パケットレートフロー検出部１０７で実行される処理プロセスのフローチャートを示す。ＢＷの境界時点において、ＳＷに含まれる（ｋ−ｈ）ｍ＋１個の全ＩＷにおいてｗ＊個以上のパケットがサンプルされたフローを高レートフローとして検出する（Ｓ３０１）。
【００３７】
＜検出の枠組み＞
次に、本発明の実施例に係る持続的な高パケットレートフローのオンライン検出法の枠組みを説明する。
【００３８】
ＤｏＳ攻撃等の異常トラヒックが発生した際、ネットワークのバックボーンにおいて迅速に検出することは、ネットワーク全体を保守管理する上で非常に重要である。本実施例ではＤＤｏＳ攻撃等、高パケットレートが長時間持続するような異常トラヒックに注目し、パケットレートが予め定められた閾値を一定時間以上超え続けているフローを検出することを試みる。
【００３９】
ネットワークを流れるＩＰトラヒックにおいて、フローとは、共通のＩＰアドレス、ポート番号、ＳＹＮフラグなどの組み合わせをもつパケット群として定義される。例えばＤｏＳ攻撃に用いられているパケット群を一つのフローと見なそうとする場合、一般に攻撃パケットのヘッダに記載されている送信元ＩＰアドレスは改竄されており、確実に共通するのは宛先のＩＰアドレスだけとなる。そのため共通の宛先ＩＰアドレスを持つパケット群をフローと定義するとＤｏＳ攻撃の攻撃フローの検出が可能となる。また、バックスキャッタのトラヒックを観測する場合、ＤｏＳ攻撃を受けたサーバから不特定多数の宛先に向けて送信されるパケットを一つのフローとして見なしたい。この場合は共通の送信元ＩＰアドレスを持つパケット群をフローとして定義するのが適している。このようにフローの定義は検出したい対象や観測地点によって適宜定義を行うと都合が良いため、本実施例ではフローの定義は任意とする。
【００４０】
ここで、検出対象フローの定義を行う。上記のように、本実施例ではパケットレートが予め与えられる閾値を一定時間以上超え続けているフローを検出対象とする。この検出対象をより明確にするために、本実施例では以下のように定義する。
【００４１】
検出対象フローの定義：予め与えられた定数Ｒ［ｐａｃｋｅｔｓ／ｓｅｃ］、Ｔ［ｓｅｃ］、ｔ［ｓｅｃ］（ｔ≦Ｔ）に対して、Ｔ秒間の測定期間に含まれるｔ秒間の任意の区間全てについて、パケットレートがＲ［ｐａｃｋｅｔｓ／ｓｅｃ］以上であるフローを検出対象とする。
【００４２】
この検出対象の定義には、瞬間的に大量のパケットが発生したが、その後すぐに消えてしまうようなバースト的なフローを検出対象から外すという意図がある。バースト的なフローは捉え方によれば高パケットレートフローであるが、検出した時点ですでに消えてしまっているのであれば対応することが出来ない。検出されたフローは管理者が対応するかどうかを判断しなければならないため、バースト的なフローを検出することは管理者のオーバヘッドが増えることになる。
【００４３】
しかし、上記で定義される検出対象フローをネットワークのバックボーンにおいて常時トラヒックを観測しながら検出を行うには大きく三つの問題がある。まず一つ目は、Ｔ秒間の測定期間に含まれる長さｔ秒をもつあらゆる部分区間全てについてパケットレートを調査することは極めて困難である。二つ目は、トラヒックを観測し続ける一方で検出対象のフローをオンラインで検出するためには、観測した解析対象データを更新する仕組みが必要となる。三つ目は、ネットワークのバックボーンのような高速な回線では、回線を流れる全てのパケットを対象に解析することは非現実的でありスケーラビリティを欠く。
【００４４】
そこで本実施例では、スライディングウィンドウ方式を用いて最初の二つの問題の解決を図る。スライディングウィンドウ方式とは、解析対象のデータを保持するスライディングウィンドウをベーシックウィンドウと呼ばれる単位に分割し、ベーシックウィンドウ単位で解析データを更新する、オンラインパケット処理アルゴリズムである。本実施例ではこのスライディングウィンドウ方式に、検査ウィンドウと呼ばれる部分ウィンドウの概念を導入し、上記で定義された検出対象フローを含む新たな検出対象フローの集合を定義することで、一つ目の問題を解決する。
【００４５】
三つ目の問題に関しては、パケットサンプリングを用いることで解決を図る。すなわち、パケットの標本抽出を行い、得られた情報を基にサンプリングの対象となった母集団の統計量を推定することで、処理サイクルやメモリ使用量を抑える。本実施例では、各パケットに対してフローの情報を用いず、独立に一定の確率ｆで無作為標本抽出を行うランダムパケットサンプリングを用いる。これにより、処理サイクルを大幅に抑えることができ、バックボーンなどの高速な回線に対しても適用可能となる。しかし、パケットサンプリングはその性質上、情報の欠如をもたらすため、特にサンプリングをする頻度が少ない場合はサンプリングの対象である母集団の統計量を推定することが困難になる。例えば、パケットが一つもサンプリングされないフローについては、母集団における統計量を推定することは不可能である。しかし、検出対象である高パケットレートのフローであれば、適切なサンプリングレートを用いることによって、母集団を推定できるだけの十分な標本を抽出できると考えられる。
【００４６】
＜スライディングウィンドウ方式による検出とデータ更新＞
バックボーンネットワークを流れているトラヒックを常時、測定管理し、高パケットレートをもつフローの検出を行うにはオンラインアルゴリズムが必要である。すなわち、データの取得、解析、破棄を継続的に行う必要がある。本実施例では、この解析対象データを更新するための手段としてスライディングウィンドウ方式を採用する。スライディングウィンドウ方式とは、解析対象となるデータを保持するスライディングウィンドウをベーシックウィンドウと呼ばれる複数の単位に分割し、解析終了後に最も古いベーシックウィンドウのデータを破棄し、新たに取得された１ベーシックウィンドウ分のデータを加えることによって解析対象のデータを更新する方式である。
【００４７】
スライディングウィンドウ方式には、スライディングウィンドウの大きさをパケット数で規定する方法と測定時間で規定する方法の２種類が存在する。前者は一定数のパケットが回線を通過したとき、あるいは一定数のパケットがサンプリングされたときにベーシックウィンドウを生成し、スライディングウィンドウを更新する。母集団におけるパケット数を一定にすると、トラヒックのフロー毎のパケット数分布などを求めることが容易になり、サンプル数を一定にすると、メモリの使用を一定にすることができるなどの利点がある。一方、後者は一定時間毎にベーシックウィンドウを生成し、スライディングウィンドウを更新する。母集団におけるパケット数およびサンプリングされるパケット数はスライディングウィンドウが更新される度に変わるが、測定時間を一定にすることができる。
【００４８】
本実施例では、パケットレート、すなわち、単位時間当たりに各フローに含まれるパケット数を対象としている。そこで、スライディングウィンドウが保持する解析対象データの測定時間が一定時間ＴＳＷ［ｓｅｃ］になるようにスライディングウィンドウの大きさを定める。さらに自然数ｋとｍを用いて、スライディングウィンドウをＴＳＷ／（ｋｍ）［ｓｅｃ］刻みでｋｍ個のベーシックウィンドウに分割する。すなわち、ＴＳＷ／（ｋｍ）秒毎に取得されるデータで新たなベーシックウィンドウを作成し、スライディングウィンドウに加えると共に、スライディングウィンドウ内の最も古いベーシックウィンドウのデータを破棄することによって解析対象となるデータの更新を行う。
【００４９】
また本実施例では、ｋとは互いに素な自然数ｈ（ｈ≦ｋ）を用いて、連続するｈｍ個のベーシックウィンドウで構成される検査ウィンドウをスライディングウィンドウ内に（ｋ−ｈ）ｍ＋１個作成する。このとき、検査ウィンドウの大きさＴＩＷは（ｈ／ｋ）ＴＳＷ［ｓｅｃ］となることに注意する。図５にｋ＝３、ｍ＝２、ｈ＝２としたときのスライディングウィンドウの概要を示す。
【００５０】
このスライディングウィンドウ方式において検出対象となるフローは下記の通りである。
【００５１】
スライディングウィンドウ方式における検出対象フローの定義：予め与えられた定数Ｒ［ｐａｃｋｅｔｓ／ｓｅｃ］、ＴＳＷ［ｓｅｃ］、自然数ｋ、ｍ、ならびにｋと互いに素な自然数ｈ（ｈ≦ｋ）に対して、ベーシックウィンドウの大きさをＴＢＷ＝ＴＳＷ／（ｋｍ）［ｓｅｃ］とし、連続するｋｍ個のベーシックウィンドウから構成されるスライディングウィンドウを考え、このスライディングウィンドウ内の大きさＴＩＷ＝（ｈ／ｋ）ＴＳＷ［ｓｅｃ］をもつ（ｋ−ｈ）ｍ＋１個全ての検査ウィンドウにおいて、パケットレートがＲ［ｐａｃｋｅｔｓ／ｓｅｃ］以上であるフローを検出対象とする。
【００５２】
ここで、上記の「検出対象フローの定義」で用いたＴおよびｔに対して、ＴＳＷ＝ＴかつＴＩＷ＝（ｈ／ｋ）ＴＳＷ＝ｔを満たす互いに素な自然数ｋおよびｈ（ｈ≦ｋ）が存在すると仮定している。この仮定より、上記の「検出対象フローの定義」を満たす検出対象フローの集合は、スライディングウィンドウ方式で検出対象となっているフローの集合の部分集合になっている。すなわち、「スライディングウィンドウ方式における検出対象フローの定義」の条件を満たすフローを全て検出すれば、「検出対象フローの定義」で定められた検出対象フローは全て検出される。以後、検出対象フローはスライディングウィンドウ方式における「検出対象フローの定義」に基づくものとする。
【００５３】
＜ランダムパケットサンプリングを用いた検出＞
高速回線に対してスケーラビリティを確保するために、本発明の実施例ではランダムパケットサンプリングを用いる。ＴＳＷ秒間に回線を通過したパケット全体を母集団し、そこから確率ｆで無作為標本抽出されたパケットの情報のみを用いて母集団における検出対象フローを検出することを試みる。母集団における検出対象フローは、（ｋ−ｈ）ｍ＋１個の検査ウィンドウ全てにおいてパケットレートが予め与えられる閾値Ｒ［ｐａｃｋｅｔｓ／ｓｅｃ］以上のフローである。検査ウィンドウのパケットレートがＲ以上であることと、検査ウィンドウ内のパケット数が
【００５４】
【数６】
以上であることは等価である。よって、以下では
【００５５】
【数７】
をパケット数の閾値と呼ぶ。すなわち、検出対象フローは母集団の全ての検査ウィンドウにおいて、パケット数がｚ＊個以上のフローである。
【００５６】
もし全てのパケットを対象に解析が行えるのであれば、各検査ウィンドウにおいて、それぞれのフローを構成するパケットがｚ＊個以上あるかどうかを調べれば良いが、本実施例ではパケットサンプリング用いるため、新たに各検査ウィンドウにおけるサンプリングされたパケット数の閾値ｗ＊を設け、スライディングウィンドウ内の全ての検査ウィンドウでｗ＊個以上のパケットがサンプリングされたフローを検出することにする。ここで ｗ＊は、検出対象のフローのうち最低のパケットレート、すなわち母集団の全ての検査ウィンドウにおいてパケット数がｚ＊個であるフロー（これを閾値フローと呼ぶことにする）を十分高い確率で検出できるように定める。これは異常な高パケットレートフローが発生した際には見逃さないようにするためである。しかしサンプリングによって情報が欠如するため、閾値ｗ＊を０にしない限り検出対象を確実に検出することはできない。そこで本実施例では、検出対象フローを見逃してしまう確率が十分小さい値ε以下となるようにｗ＊を定める。具体的なパラメータ設定方法は後述する。
【００５７】
以下に検出の手順をまとめる。ただし、スライディングウィンドウはＳＷ、検査ウィンドウはＩＷ、ベーシックウィンドウはＢＷとそれぞれ略記する。
【００５８】
まず、測定期間ＴＳＷ秒の間に確率ｆで無作為標本抽出されたパケットのデータを保持するＳＷにおいて、ＳＷに含まれる（ｋ−ｈ）ｍ＋１個全てのＩＷにおいてｗ＊個以上サンプリングされているフローがあれば、そのフローを検出する。
【００５９】
次に、ＳＷの解析終了後、最も古いＢＷ、ならびに、このＢＷを含むＩＷを破棄する。
【００６０】
一方、新たにＴＢＷ秒間に転送されたパケットのサンプリング終了後、新しいＢＷを作成し、それをＳＷに加えると共に、連続する最近のｈｍ個のＢＷを用いて新しいＩＷを作成する。
【００６１】
次に、新たに作成されたＩＷを検査し、ｗ＊個以上含まれるフローがあった場合には過去のＩＷの検査結果と照らし合わせ、（ｋ−ｈ）ｍ＋１個のＩＷ全てにおいてサンプルされたパケット数が閾値ｗ＊を超えていれば、そのフローを検出する。
【００６２】
スライディングウィンドウ方式によるデータ更新とランダムパケットサンプリングを用いた本実施例の手法は上記の手順を常時繰り返すものである。
【００６３】
本実施例の手法では、予め与えられるパラメータである、パケットレートの閾値Ｒ［ｐａｃｋｅｔｓ／ｓｅｃ］、測定時間であるスライディングウィンドウの大きさＴＳＷ［ｓｅｃ］、検査ウィンドウの大きさを定める互いに素な自然数ｋおよびｈの他に、制御可能なパラメータとして、サンプリングレートｆ、データ更新単位であるベーシックウィンドウの大きさを定める自然数ｍ、ならびに、サンプリングされたパケット数の閾値ｗ＊がある。よって、制御可能なこれら三つのパラメータ（以後制御パラメータと呼ぶ）の値を適切に決定する必要がある。その際、前述の検出対象のフローを見逃してしまう確率をε以下とするという条件を満たすと同時に、スライディングウィンドウ方式がオンラインアルゴリズムとして正常に機能するために、新しいベーシックウィンドウが生成される前に現在のスライディングウィンドウの解析が終了できるようにしなければならない。
【００６４】
この二つの制約条件下で三つの制御パラメータを設定しようとする場合には自由度が大きく、制御パラメータは一意に決定されない。そこで、以下では、検出対象フローの発生から検出までに要する時間に関する制約条件と、スライディングウィンドウ方式における検出対象フローの集合が、本来の検出対象フローの集合に近いものとなるように検査ウィンドウのスライド幅ＴＢＷ＝ＴＳＷ／（ｋｍ）に関する最大許容値を導入し、各制御パラメータを一意に定める手法を説明する。
【００６５】
そして、サンプリングレートｆ、ベーシックウィンドウの大きさを定める自然数ｍ、並びに、サンプルにおけるパケット数の閾値ｗ＊の三つの制御パラメータを、複数の制約条件を導入することにより、一意に決定する手法を説明する。
【００６６】
＜制御パラメータと制約条件＞
検出対象のフローを定義するパラメータは次の四つである。
【００６７】
・パケットレートの閾値Ｒ［ｐａｃｋｅｔｓ／ｓｅｃ］
・スライディングウィンドウの大きさＴＳＷ［ｓｅｃ］
・検査ウィンドウの大きさを定める互いに素な自然数ｋ及びｈ
一方、制御パラメータは以下の三つである。
【００６８】
・サンプリングレートｆ
・ベーシックウィンドウの大きさを定める自然数ｍ
・サンプルにおけるパケット数の閾値ｗ＊［ｐａｃｋｅｔｓ］
以上七つのパラメータが決定されると、上記の「検出の枠組」みで説明した検出手法を用いることができる。
【００６９】
制御パラメータを設定する際にまず注意しなければならないことは、スライディングウィンドウ方式を用いた本提案手法をオンラインアルゴリズムとして正常に機能させることである。オンラインで検出を行うということは、解析対象のデータが更新される前に、現在のデータの解析処理が完了しなければならないということである。すなわち、スライディングウィンドウの解析を、新たな１ベーシックウィンドウ分のデータを取得する前に終わらせなければならない。よって、スライディングウィンドウの解析時間τ［ｓｅｃ］は
【００７０】
【数８】
を満たさなければならない。
【００７１】
そこで、スライディングウィンドウの解析時間τ［ｓｅｃ］について評価を行う。パケットの情報はサンプリングされた時点でフロー毎に仕分けられ、パケット数はカウントされているものとする。すなわち、ベーシックウィンドウはフロー毎の情報を保持しており、保持するフロー数の上限はサンプリングされるパケット数となる。以下に新しいベーシックウィンドウが生成された直後からのスライディングウィンドウの処理を列挙する。なお、解析を行う際はスライディングウィンドウ内の（ｋ−ｈ）ｍ＋１個の検査ウィンドウのみを対象とするが、データ処理の都合上、まだｈｍ個揃っていない先のスライディングウィンドウで用いる検査ウィンドウも、関係するベーシックウィンドウが到着し次第順次加えながら作成していく。以下に手順を示す。
【００７２】
（１）新しいベーシックウィンドウをスライディングウィンドウ内の関係する全ての検査ウィンドウ（まだｈｍ個そろっていないものも含む）に加える。
【００７３】
（２）最近のｈｍ個のベーシックウィンドウで構成される検査ウィンドウを調査し、閾値ｗ＊を超えるフローを検知する。
【００７４】
（３）以前の検査ウィンドウの検知結果を用いて、全ての検査ウィンドウで検知されたフローを検出する。
【００７５】
（４）最も古い検査ウィンドウおよびベーシックウィンドウを破棄する。
【００７６】
上記手順のうち、（１）はベーシックウィンドウに含まれる各フローについてフロー情報の比較や情報の集約などの複雑な処理を行うため、その処理時間はベーシックウィンドウ内のフロー数に依存する。（２）以降の各手順は、予め確保された空間に渡って単純な比較やデータの廃棄のみを行うため、一定時間内に処理できると考えて良い。そこで、本実施例ではスライディングウィンドウの処理時間τを、ベーシックウィンドウにサンプリングされるパケット数に依存する処理時間と、パケット数とは独立な一定の処理時間の和として考え、次式で処理時間の上界を見積もることにする。
【００７７】
【数９】
ここで、Ｃｍａｘ、Δ１およびΔ２は、それぞれ、観測する回線の最大パケットレート、スライディングウィンドウの解析における１サンプルパケット当りの処理時間、および、サンプルパケット数とは独立な処理時間を表している。
【００７８】
ＤｏＳ攻撃のような異常フローは発生から検出するまでに時間がかかりすぎると、攻撃を受けているサーバが機能を停止してしまう。そこで本実施例では、検出対象のフローが発生してから目標時間ＴＤ＿ｍａｘ［ｓｅｃ］以内に検出できるようにパラメータを定める。検出対象のフローを検出するために必要な時間は、対象フローの測定にかかる時間ＴＳＷとスライディングウィンドウの解析時間τの和で与えられる。しかし、検出対象のフローは多くの場合、ベーシックウィンドウの途中から発生すると考えられ、検出した時点では直前に破棄したベーシックウィンドウの途中から始まっていた可能性が高い。すなわち、最大で１ベーシックウィンドウ分の検出遅れが生じることになる。したがって、検出対象フローを目標時間以内に検出するための条件は次式で与えられる。
【００７９】
【数１０】
上記の「検出対象フローの定義」では、Ｔ（＝ＴＳＷ）秒の測定期間内の任意のｔ（＝ＴＩＷ）秒の区間全てにおいてパケットレートがＲ以上となっているため、検査ウィンドウのスライド幅が大きすぎると、上記の「検出対象フローの定義」を満足しないフローを多数検出することになる。そこで、検査ウィンドウのスライド幅に関する最大許容値ＴＢＷ＿ｍａｘ［ｓｅｃ］を設ける。本実施例において、検査ウィンドウのスライド幅はベーシックウィンドウのサイズＴＢＷとなるため、ＴＢＷは次の条件を満たす必要がある。
【００８０】
【数１１】
上記の「検出の枠組み」で説明した検出手法では、ランダムパケットサンプリングを行い、サンプリングされたパケットの情報のみを用いて検出を行うため、検出対象フローの検出見逃しや検出対象外フローの誤検出が発生する。三つの制御パラメータのうち二つを固定し、残りの一つを変化させた場合、サンプリングレートｆに関しては、ｆを小さくするほど検出見逃しおよび誤検出は発生しやすくなる。ベーシックウィンドウのサイズを規定するｍに関しては、ｍを大きくするほど検査ウィンドウの数が増え、全ての検査ウィンドウでｗ＊以上となる確率が減少するため、検出見逃しは増加するが誤検出は減少する。検査ウィンドウにおけるパケット数の閾値ｗ＊に関しては、ｗ＊が小さいほど検出見逃しは減少するが誤検出は増加する。このようにｍとｗ＊に関してはトレードオフの関係が存在することに注意する。異常フローを見逃してしまうと、その後のネットワークに大きな障害をもたらしかねないため、本実施例では検出対象のフローを見逃してしまう確率を十分小さなε以下に抑えるようにパラメータを設定する。その上で、検出対象外フローを誤検出してしまう確率もなるべく小さくなるように制御パラメータを設定する。
【００８１】
上記のシステムを規定するパラメータを以下にまとめておく。
【００８２】
・見逃し許容誤差ε（検出対象フローを１−ε以上の確率で検出）
・検出目標時間ＴＤ＿ｍａｘ［ｓｅｃ］
・スライド幅の最大許容値ＴＢＷ＿ｍａｘ［ｓｅｃ］
・観測する回線の最大パケットレートＣｍａｘ［ｐａｃｋｅｔｓ／ｓｅｃ］
・１サンプルパケットあたりの処理時間Δ１［ｓｅｃ］
・スライディングウィンドウの解析に必要なパケット数とは独立な処理時間Δ２［ｓｅｃ］
＜誤検出確率の最小化問題＞
上記の制約条件の下、検出対象外の低パケットレートフローを誤検出する確率を最小化するように制御パラメータを設定する問題を考える。すなわち、この問題は次のように定式化される。
【００８３】
目的関数：検出対象外フローの誤検出確率→最小
制約条件：サンプリングレートｆ＞０
ベーシックウィンドウの大きさを定める自然数ｍ
サンプルにおけるパケット数の閾値ｗ＊（自然数）
オンラインのアルゴリズムとして機能すること
目標時間ＴＤ＿ｍａｘ内に検出可能なこと
検査ウィンドウのスライド幅≦最大許容値ＴＢＷ＿ｍａｘ
検出対象フローの検出見逃し確率≦ε以下
なお、対象フローの検出見逃し確率に関する制約条件は、サンプリングレートｆとベーシックウィンドウの大きさを定めるｍが決定した後に、ｗ＊を調整することによって満たすことができるため、上記の問題とは独立な問題として考える。
【００８４】
まず、目的関数について説明する。サンプリングによって得られたパケットの情報を用いて母集団の統計量を推定する場合、サンプリングされたパケット数が多ければ多いほどその統計的精度は高くなる。そのため検出対象外のフローを誤検出してしまう確率を下げるためにはなるべくたくさんのパケットをサンプリングすればよい。スライディングウィンドウのサイズはＴＳＷ秒で固定されているため、サンプリングされるパケット数を多くするにはサンプリングレートｆを大きくする、すなわち、上記の制約条件下でｆを最大化することが検出対象外フローの誤検出確率を最小化することと等価となる。したがって、上記の問題は次のようなサンプリングレートｆの最大化問題となる。
【００８５】
目的関数：サンプリングレートｆ→最大
制約条件：サンプリングレートｆ＞０
ベーシックウィンドウの大きさを定める自然数ｍ
オンラインのアルゴリズムとして機能すること
目標時間ＴＤ＿ｍａｘ内に検出可能なこと
検査ウィンドウのスライド幅≦最大許容値ＴＢＷ＿ｍａｘ
次に、制約条件について説明する。スライディングウィンドウの解析時間τは式（２）に従うと仮定する。さらに上記より、オンラインのアルゴリズムとして機能するための条件は式（１）で、目標時間内の検出の条件は式（３）で、検査ウィンドウのスライド幅に関する条件は式（４）で与えられる。制約条件をこれらで置き換え、ｍに関してｋｍ＝ＴＳＷ／ＴＢＷを加えると、上記の問題は次のように書き換えられる。
【００８６】
目的関数：サンプリングレートｆ→最大
制約条件：ｆ＞０
ｍは自然数
τ≦ＴＢＷ
ＴＳＷ＋ＴＢＷ＋τ≦ＴＤ＿ｍａｘ
ＴＢＷ≦ＴＢＷ＿ｍａｘ
τ＝ｆＣｍａｘＴＢＷΔ１＋Δ２
ｋｍ＝ＴＳＷ／ＴＢＷ
この制約条件下で、サンプリングレートｆを最大にする自然数ｍを求めることが目的となる。τ≦ＴＢＷにτ＝ｆＣｍａｘＴＢＷΔ１＋Δ２を代入し、ＴＳＷ＝ｋｍＴＢＷを用いて変形すると、
【００８７】
【数１２】
となる。同様に、ＴＳＷ＋ＴＢＷ＋τ≦ＴＤ＿ｍａｘは、
【００８８】
【数１３】
となる。また、ＴＢＷ≦ＴＢＷ＿ｍａｘより、
【００８９】
【数１４】
となる。
【００９０】
このとき、本実施例の手法が動作可能であるためには、サンプリングレートｆが正となるようなｍが存在する必要がある。式（５）の右辺が正であるためには、
【００９１】
【数１５】
でなければならない。また、式（６）の右辺が正であるための条件は、
【００９２】
【数１６】
で与えられる。さらに、式（７）より
【００９３】
【数１７】
を得る。すなわち、式（８）、（９）、（１０）より、本実施例の手法が動作可能となるためには、次式が成立する必要がある。
【００９４】
【数１８】
よって、式（１１）が成立しているという条件の下で、以下の最適化問題を考える。
【００９５】
制御パラメータ：ｆ，ｍ
与条件：定数ＴＳＷ，ｋ，ｈ，Ｃｍａｘ，ＴＤ＿ｍａｘ，ＴＢＷ＿ｍａｘ，Δ１，Δ２
ＴＳＷ−ｋΔ２＞０
ｋＴＤ＿ｍａｘ−（ｋ＋１）ＴＳＷ−ｋΔ２＞０
ＴＳＷ≦ｋＴＢＷ＿ｍａｘ
目的関数：ｆ→最大
制約条件：ｆ＞０
ｍは自然数
【００９６】
【数１９】
この混合線形計画問題は以下のようにして解くことができる。まず、自然数ｍを実数ｒで置き換えた以下の緩和問題を考える。
【００９７】
目的関数：ｆ→最大
制約条件：ｆ＞０
【００９８】
【数２０】
２番目と３番目の制約条件で表される領域の境界はそれぞれ次式で与えられる。
【００９９】
【数２１】
【０１００】
【数２２】
ここで、式（１２）がｒに関する減少一次関数に、式（１３）がｒに関する増加一次関数になっていることに注意する。この２直線の交点の座標を
【０１０１】
【数２３】
とおくと、
【０１０２】
【数２４】
である。与条件より、
【０１０３】
【数２５】
は正であることに注意する。一方、最後の制約条件で表される領域の境界を
【０１０４】
【数２６】
とおく。
【０１０５】
【数２７】
以上の準備の下でｆを最大にするようなｒ＊およびｍ＊を、
【０１０６】
【数２８】
に場合分けして求める。
【０１０７】
【数２９】
図６より、
【０１０８】
【数３０】
でｆは最大となる。このとき、
【０１０９】
【数３１】
を求め、
【０１１０】
【数３２】
であればｍ−とｍ＋のうちｆを大きくする方、すなわち
【０１１１】
【数３３】
を採用する。このときのｆ＊はｆ＊＝ｍａｘ｛ｆ１（ｍ＋），ｆ２（ｍ−）｝となる。また、
【０１１２】
【数３４】
のときはｍ＊＝ｍ＋であり、ｆ＊はｆ＊＝ｆ１（ｍ＋）となる。
【０１１３】
【数３５】
図７より、
【０１１４】
【数３６】
でｆは最大となる。このときｍ＊は
【０１１５】
【数３７】
となり、ｆ＊はｆ＊＝ｆ１（ｍ＋）である。
【０１１６】
以上のようにして求めたｍ＊とｆ＊を制御パラメータの値として用いる。
【０１１７】
＜サンプルにおける閾値の導出＞
予め与えられるシステムを規定するパラメータと上記のように設定したサンプリングレートｆおよびベーシックウィンドウの大きさを定めるｍを用いて、検出対象フローを見逃してしまう確率をε以下となるように、検査ウィンドウ内のサンプルパケット数の閾値ｗ＊を設定する。
【０１１８】
ある測定期間において任意のフローに注目する。ＸおよびＹをそれぞれフローを構成するパケット数およびサンプリングされたパケット数を表す確率変数とする。Ｘ＝ｘという条件下で、ｙ個のパケットがサンプリングされる確率ｑ（ｙ｜ｘ）＝Ｐｒ［Ｙ＝ｙ｜Ｘ＝ｘ］は以下の二項分布で与えられる。
【０１１９】
【数３８】
閾値フローを用いた閾値の導出
スライディングウィンドウ内の全ての検査ウィンドウ内のパケット数が
【０１２０】
【数３９】
である閾値フローを１−ε以上の確率で検出できるようにｗ＊を設定すると、全ての検出対象のフローを１−ε以上の確率で検出できることに注意する。
【０１２１】
図８に示すように、スライディングウィンドウ内のｉ番目のベーシックウィンドウの母集団におけるパケット数を確率変数Ｘｉで、ｉ番目の検査ウィンドウの母集団におけるパケット数を確率変数Ｚｉで表すと、ＺｉはＸｉを用いて次のように表される。
【０１２２】
【数４０】
さらに、図９のように、スライディングウィンドウ内のｉ番目のベーシックウィンドウにサンプリングされたパケット数を確率変数Ｙｉで、ｉ番目の検査ウィンドウにサンプリングされたパケット数を確率変数Ｗｉで表すと、ＷｉはＹｉを用いて次のように表される。
【０１２３】
【数４１】
ここで、閾値フローのベーシックウィンドウ毎の母集団におけるパケット数を考える。各検査ウィンドウは母集団においてｚ＊個のパケットで構成されているため、ベーシックウィンドウのパケット数Ｘｉは次の式を満たす。
【０１２４】
【数４２】
上式より、閾値フローの母集団におけるパケット数の分布は１サイクルがｈｍの周期的な分布となることがわかる。そのため、一つ目の検査ウィンドウにおけるパケット数の分布が決定すると、スライディングウィンドウ全体の分布が決定する。
【０１２５】
ベクトルＸをｉ番目の要素がＸｉである、母集団のパケット数を表すｋｍ次元ベクトルとし、閾値フローの母集団におけるパケット数を
【０１２６】
【数４３】
で表すことにする。また、閾値フローがサンプルパケット数の閾値ｗをもって検出される確率、すなわち全ての検査ウィンドウにおいてｗ個以上のパケットがサンプリングされる確率は、
【０１２７】
【数４４】
である。ここで、式（１５）の周辺確率を考える。任意の一つの検査ウィンドウにおいて
【０１２８】
【数４５】
となる確率ｐ（ｗ｜ｚ＊）は、式（１４）の二項分布を用いて次のように求まる。
【０１２９】
【数４６】
このとき、
【０１３０】
【数４７】
となる確率は閾値フローの分布
【０１３１】
【数４８】
とは独立であることに注意する。
【０１３２】
議論を式（１５）の結合確率に戻す。確率変数ＸｉおよびＹｉはｉに関して独立であるが、ＺｉおよびＷｉは前後ｈｍ−１番目まで共通のＸｉおよびＹｉを有し、従属関係にあるため、式（１５）の確率を数値計算によって求めることは困難である。そこで、式（１６）で与えられる周辺確率を用いて、結合確率の上下界値を導く。
【０１３３】
閾値フロー検出確率の上下界値
問題を簡単にするためにｈ＝１の場合、すなわち、スライディングウィンドウの大きさが検査ウィンドウのｋ倍になっている場合を考える。このとき式（１５）で与えられる閾値フローの検出確率は、スライディングウィンドウ内の独立なｋ個の検査ウィンドウにおいてＷｉ≧ｗとなる確率（式（１６））と、その事象が起こったという条件の下で他の検査ウィンドウでもＷｉ≧ｗとなる条件付き確率の積として、
【０１３４】
【数４９】
と変形される。ここで後半部分の条件付き確率は１で上から押さえることができるため、閾値フローの検出確率は、
【０１３５】
【数５０】
として上から押さえられる。ここでｈ≠１の場合にも成り立つように拡張すると、スライディングウィンドウ内の独立な検査ウィンドウの数は
【０１３６】
【数５１】
であるため、
【０１３７】
【数５２】
として閾値フローの検出確率の上界値が得られる。
【０１３８】
次に、下界値について述べる。以下では、サンプリングされたパケット数を表す確率ベクトルをＹ＝（Ｙ１，Ｙ２，...，Ｙｋｍ）とする。このとき、
【０１３９】
【数５３】
が与えられたという条件下では、
【０１４０】
【数５４】
となるため、ベクトルＹ＝（Ｙ１，Ｙ２，...，Ｙｋｍ）は互いに独立な確率変数Ｙｉ（ｉ＝１，２，...，ｋｍ）から構成される確率ベクトルであることに注意する。ただし、
【０１４１】
【数５５】
は
【０１４２】
【数５６】
のｉ番目の要素を表す。よって、確率ベクトルＹは正の関連（ｐｏｓｉｔｉｖｅｌｙ ａｓｓｏｃｉａｔｅｄ）をもつ。ここで正の関連をもつとは、任意の増加関数
【０１４３】
【数５７】
に対して
【０１４４】
【数５８】
すなわち、
【０１４５】
【数５９】
が成立することをいう。
【０１４６】
次に、以下の指示関数を定義する。
【０１４７】
【数６０】
この指示関数は、ｗおよび
【０１４８】
【数６１】
が与えられたとき、あるＹ≧Ｙ'なるベクトルＹとベクトルＹ'に対して、
【０１４９】
【数６２】
を満たす。ただし、Ｙ≧Ｙ'は各ベクトルの成分ＹｊおよびＹｊ'に対して、
【０１５０】
【数６３】
が成り立つこと意味する。式（１８）より、
【０１５１】
【数６４】
は非負の増加関数となっている。以上より、
【０１５２】
【数６５】
が成立する。
【０１５３】
さらに、非負の増加関数の積は非負の増加関数となるので
【０１５４】
【数６６】
とすると、ベクトルＹが正の関連をもつため、
【０１５５】
【数６７】
が成立する。この式の右辺に式（２０）を代入し、式（１９）を適用すると、
【０１５６】
【数６８】
を得る。よって、数学的帰納法により
【０１５７】
【数６９】
を得る。
【０１５８】
式（２１）の左辺はＷｊ＝Ｙｊ＋Ｙｊ＋１＋...＋Ｙｊ＋ｈｍ−１と式（１５）を用いると、
【０１５９】
【数７０】
となる。同様に式（２１）の右辺は、式（１６）を用いると、
【０１６０】
【数７１】
となる。式（２３）と式（２４）を式（２１）に代入することにより、
【０１６１】
【数７２】
の下界を得る。
【０１６２】
【数７３】
閾値フローの分布による検出確率の変化
上記の式（１７）と式（２５）より、閾値フローの検出確率
【０１６３】
【数７４】
が次のように上下界値で押さえられることがわかった。
【０１６４】
【数７５】
しかし、上界値および下界値はｋやｍが大きい場合、あるいはｐ（ｗ｜ｚ＊）が小さな値をとる場合等は両者の差が大きくなり、上下界値を用いて検出確率を推定することは困難になる。
【０１６５】
そこで、閾値フローの母集団におけるパケット数の分布
【０１６６】
【数７６】
に注目する。閾値フローの中でも検出確率が最低になるようなパケット数の分布がわかれば、その分布を基に全ての検出対象フローを検出できるようなパケット数の閾値ｗ＊を決定することができる。ここで、閾値フローのパケット数の分布は一つ目の検査ウィンドウ分の分布が決まると周期性から全ての分布が決定することに注意する。
【０１６７】
複数の条件下での数値計算の結果、ｈ＝１の場合は、一つ目の検査ウィンドウにおいてｚ＊個のパケットをまず
【０１６８】
【数７７】
個ずつ均等にベーシックウィンドウに配置し、余剰が出た場合はそのパケットを検査ウィンドウの中央のベーシックウィンドウから一つずつ前後のベーシックウィンドウに外側に向けて交互に配置したときに、検出確率が最低となることが分かった。このときウィンドウ全体の対称性から、前後のウィンドウのどちらに先に配置するかは問題とならない。反対に、検査ウィンドウ内の一つのベーシックウィンドウにｚ＊個のパケットを全て配置した場合には最も検出確率は高く、その検出確率は上界値と等しくなるため、パケットを均等に配置するときに検出確率が最低になることは直感的な理解とも一致する。
【０１６９】
しかし、ｈ≧２の場合は、一つ目の検査ウィンドウを用いて配置されたベーシックウィンドウ毎のパケット数の、スライディングウィンドウ全体において配置される回数が異なってくるため、ｈ＝１と同じ議論は適用できず、検出確率が最低となる分布は見出すことができない。以降、ｈ≧２の場合は検出確率が最低となる分布が見出されているものと仮定して説明する。
【０１７０】
検出確率が最低となる閾値フローの分布をＸ＊とおく。このとき、先の上下界値を含め、次の式が成り立っていることに注意する。
【０１７１】
【数７８】
分布Ｘ＊が得られた後、検出対象のフローを１−ε以上の確率で検出するためにサンプルにおけるパケット数の閾値ｗ＊を次のように設定する。
【０１７２】
【数７９】
なお、Ｐ（ｗ｜Ｘ＊）はモンテカルロシミュレーションを用いた数値実験によって求める。
【０１７３】
以上で制御パラメータの設定は完了し、上記の「検出の枠組み」で説明した検出手法で用いるパラメータは全て決定した。
【０１７４】
多段階閾値の導入
上記のように、本実施例の検出手法を用いるためのパラメータの決定は完了した。しかし、実験結果が全ての検査ウィンドウでｗ＊以上サンプリングされたかどうかの２通りでの評価では、閾値よりもかなり大きいパケットレートの検出対象フローも、たまたま誤検出された検出対象外フローも全く区別がつかない。そこで、検出されたパケット数の情報をより有効活用することを考え、閾値ｗ＊以外の複数の基準値ω（φ）（ω（φ）＞ｗ＊）を設ける。そして、検出されたフローの中で、全ての検査ウィンドウにおいてω（φ）個以上のパケットがサンプリングされているフローは区別することにする。ここで基準値ω（φ）は次のようにして定める。
【０１７５】
【数８０】
ただし、φは１−ε未満の値を用いる。この基準値の定め方には、パケットレートが閾値フローから僅かに低いだけの検出対象外のフローを誤って検出してしまう確率をφ以下にするという意図がある。複数のφに対するω（φ）を求め、検出されたフローの中でのフローの差別化を図る。
【０１７６】
＜性能評価＞
次に、実際にネットワークで測定された２種類の異なるトレースデータに対して適当な規定パラメータの下でシミュレーション実験を行い、本実施例の検出手法の性能評価を行う。まず実験に用いるトレースデータについて述べる。続いて性能を評価するための指標について述べ、最後に実験の結果を示し、その考察を行う。
【０１７７】
性能評価を行うトレースデータとして、ＣＡＩＤＡによって２００８年２月２０日の８：００から９：００の間に測定されたバックスキャッタのトラヒックを含むＢａｃｋｓｃａｔｔｅｒトレースデータと、ＮＬＡＮＲのＰａｓｓｉｖｅ Ｍｅａｓｕｒｅｍｅｎｔ ａｎｄ Ａｎａｌｙｓｉｓ （ＰＭＡ） Ｐｒｏｊｅｃｔによって２００４年２月１９日の１０：００から１０：０５の間にバックボーンネットワークで測定され、現在はＣＡＩＤＡによって管理されているＣＥＳＣＡ−Ｉトレースデータを用いた。図１０にトレースデータの概要を示す。
【０１７８】
性能評価指標
本実施例の検出手法の性能を評価するため、検出率、誤検出率、最低誤検出パケット数の三つの指標について検証する。ここで次のような二つの指示関数を用意する。
【０１７９】
【数８１】
ここで、ｉはスライディングウィンドウの解析回数のカウンタ値を、ｆｌｏｗ＿ｉｄはフローの識別子をそれぞれ表す。ａ（ｉ，ｆｌｏｗ＿ｉｄ）＝１は母集団において、ｉ回目の解析時点でのｆｌｏｗ＿ｉｄのフローが、全ての検査ウィンドウで
【０１８０】
【数８２】
個以上パケットが存在する検出対象のフローであることを意味し、ｂ（ｉ，ｆｌｏｗ＿ｉｄ）＝１はサンプリング実験において、ｉ回目の解析時点でのｆｌｏｗ＿ｉｄのフローが、全ての検査ウィンドウでｗ＊個以上パケットがサンプリングされ、検出されたフローであることを意味する。
【０１８１】
トレースデータの観測時間をＴＭ［ｓｅｃ］とおくと、ｉのとる値は、ｉ＝１，２，...，ｉｍａｘとなる。ただし、
【０１８２】
【数８３】
である。また、ｉ回目の解析時点における全てのｆｌｏｗ＿ｉｄの集合を
【０１８３】
【数８４】
とする。トラヒックに含まれるフローの集合は解析を行う度に異なるため、ｉの関数になっていることに注意する。
【０１８４】
このとき、検出率を次式で定義する。
【０１８５】
【数８５】
ａ（ｉ，ｆｌｏｗ＿ｉｄ）＝１となるｉとｆｌｏｗ＿ｉｄの組み合わせを検出対象点としたとき、式（２６）は全ての検出対象点のうち本実施例の検出手法により検出できた点の割合を表す。
【０１８６】
一方、誤検出率は次式で定義される。
【０１８７】
【数８６】
ａ（ｉ，ｆｌｏｗ＿ｉｄ）＝０となるｉとｆｌｏｗ＿ｉｄの組み合わせを、検出対象外点としたとき、式（２７）は全ての検出対象外点のうち本実施例の検出手法により誤検出された点の割合を表す。
【０１８８】
最後に、最低誤検出パケット数については、誤検出された全てのフローの母集団における検査ウィンドウ内のパケット数を全て調査し、それらの中で最少パケット数で構成される検査ウィンドウを特定し、そのパケット数を評価する。
【０１８９】
実験結果
予め与えられるパラメータである、Ｒ［ｐａｃｋｅｔｓ／ｓｅｃ］、ＴＳＷ［ｓｅｃ］、ｋ、ｈ、ＴＤ＿ｍａｘ［ｓｅｃ］、ＴＢＷ＿ｍａｘ｝［ｓｅｃ］、Δ１［ｓｅｃ］、Δ２［ｓｅｃ］、Ｃｍａｘ［ｐａｃｋｅｔｓ／ｓｅｃ］、εはそれぞれ図１１のように与えた。また、実験ではフローを、Ｂａｃｋｓｃａｔｔｅｒトレースデータに対しては送信元ＩＰアドレスが共通のパケット群と定義し、ＣＥＳＣＡ−Ｉトレースデータに対しては送信元ＩＰアドレスが共通のパケット群と宛先ＩＰアドレスが共通のパケット群の２種類で定義した。これは、Ｂａｃｋｓｃａｔｔｅｒトレースデータには、ＤｏＳ攻撃を受けたサーバから偽装された様々な宛先へ送られるトラヒックが含まれていることが分かっているため、そのトラヒックを検出することを目的としている。一方、ＣＥＳＣＡ−Ｉトレースデータには異常フローは含まれていないように思われる。そのため２種類の定義により純粋に高パケットレートフローの検出を試みた。
【０１９０】
図１１のパラメータを基に、上記の「制御パラメータと制約条件」で説明した制御パラメータ設定法を用いた。まず、上記の「誤検出確率の最小化問題」を解き、サンプリングレートｆとベーシックウィンドウの大きさを定めるｍが図１２のように得られた。
【０１９１】
図１１のパラメータ群と図１２のｆおよびｍを用いて、上記の「サンプルにおける閾値の導出」の手法を用いたモンテカルロシミュレーションによる数値実験により、検査ウィンドウにおけるパケット数の閾値ｗ＊を決定した。なお数値実験では、各ベーシックウィンドウにパケットを均等に配置した閾値フローを母集団とし、複数の閾値の候補ｗに対して１０６回のサンプリング実験を行い、検出された回数を１０６で割ることによって得られた検出率が１−ε以上となるｗの中で最大のものをｗ＊として採用した。Ｂａｃｋｓｃａｔｔｅｒトレースデータに対する数値実験の結果を図１３に、Ｒ＝８００のときのＣＥＳＣＡ−Ｉトレースデータに対する数値実験の結果を図１４に、Ｒ＝１０００のときのＣＥＳＣＡ−Ｉトレースデータに対する数値実験の結果を図１５にそれぞれ示した。それぞれのグラフから、閾値フローの検出率が下界値と上界値でそれぞれ押さえられていることもわかる。また、数値計算によって求まる下界値と上界値を参考にすることによって、数値実験で試行するｗの範囲を絞ることができる。さらに、ｗ＊と同様に数値実験においてω（φ）の値を、φ＝０．５，１０−１，１０−２，１０−３，１０−４，１０−５，１０−６について求めた結果をｗ＊と共に図１６に示す。
【０１９２】
以上の手順により得られた制御パラメータと予め与えられるパラメータ群を用いてサンプリング実験を行った。ここで検出対象のフローは、サンプリングレートをｆ＝１、サンプルにおけるパケット数の閾値を
【０１９３】
【数８７】
とし、その他のパラメータは実験に用いたものと同じとした場合の検出結果を用いた。
【０１９４】
１００回のサンプリング実験における、三つの評価指標の平均値を９５％信頼区間と共に図１７に示す。図１７より、検出対象はいずれの場合においても１−ε以上の割合で検出されていることがわかる。また、検出対象外フローのうち誤検出されたフローの割合も十分小さく抑えられている。さらに、誤検出されたフローの中で検査ウィンドウに含まれるパケット数が最少のものでも検出対象の半分程度であるため、本実施例の検出手法が誤検出するフローのパケットレートの範囲はそれほど広くないことがわかる。
【０１９５】
＜実施例の効果＞
以上説明したように、本発明の実施例によれば、長さＴ秒の測定期間に含まれる長さｔ秒の任意の部分区間において、パケットレートがＲ［ｐａｃｋｅｔｓ／ｓｅｃ］以上のフローを、ランダムパケットサンプリングによって得られた情報からオンラインで検出できる。
【０１９６】
説明の便宜上、本発明の実施例に係る高パケットレートフロー検出装置は機能的なブロック図を用いて説明しているが、本発明の高パケットレートフロー検出装置は、ハードウェア、ソフトウェア又はそれらの組み合わせで実現されてもよい。例えば、高パケットレートフロー検出装置の各機能部がソフトウェアで実現され、コンピュータ内に実現されてもよい。また、２以上の実施例及び実施例の各構成要素が必要に応じて組み合わせて使用されてもよい。
【０１９７】
以上、本発明の実施例について説明したが、本発明は、上記の実施例に限定されることなく、特許請求の範囲内において、種々の変更・応用が可能である。
【符号の説明】
【０１９８】
１０１ パラメータｆとｍの設計部
１０２ パラメータｗ＊の設計部
１０３ パケット無作為抽出部
１０４ ＢＷ情報保存部
１０５ ＩＷ情報の更新部
１０６ ＩＷ情報保存部
１０７ 高パケットレートフロー検出部
【技術分野】
【０００１】
本発明は、高パケットレートフロー検出装置及び高パケットレートフロー検出方法に関する。
【背景技術】
【０００２】
近年、インターネット上では公的機関や企業のサーバなどを狙った、Ｄｅｎｉａｌ ｏｆ Ｓｅｒｖｉｃｅ（ＤｏＳ）攻撃が深刻な問題となっている。ＤｏＳ攻撃とは、サーバがクライアントに対して供給するサービスを、不正なパケットを送りつけることによって妨害するという、ネットワークを利用した攻撃のことである。ＤｏＳ攻撃の代表的なものとしてＳＹＮ Ｆｌｏｏｄ攻撃とｓｍｕｒｆ攻撃がある。
【０００３】
ＳＹＮ Ｆｌｏｏｄ攻撃とは、攻撃者が攻撃対象のサーバに対してＴＣＰの接続要求であるＳＹＮパケットを、ヘッダを改竄した後に大量に送りつけるというものである。ＳＹＮパケットを受け取ったサーバは送信元に対してＳＹＮ／ＡＣＫを返す。しかしＳＹＮパケットのヘッダに書かれている送信元のＩＰアドレスが実際には存在しないアドレスに書き換えられているため、サーバからのＳＹＮ／ＡＣＫに対してＡＣＫを返すクライアントは存在せず、サーバは返ってこないＡＣＫをタイムアウトになるまで待ち続けなければならない。この状態はｈａｌｆ−ｏｐｅｎと呼ばれ、ｈａｌｆ−ｏｐｅｎ状態のコネクション情報はサーバ内のｂａｃｋｌｏｇ ｑｕｅｕｅに蓄積される。ｂａｃｋｌｏｇ ｑｕｅｕｅのサイズはサーバ毎に決められており、このｂａｃｋｌｏｇ ｑｕｅｕｅが一杯のときは、サーバはクライアントからの接続要求に応えることができない。すなわち、送信元ＩＰアドレスを改竄したＳＹＮパケットが大量に送られてくると、サーバのｂａｃｋｌｏｇ ｑｕｅｕｅは常に一杯の状態になってしまい、正常なクライアントに対してＴＣＰ接続を確立することができず、サービスを供給できなくなる。
【０００４】
一方、ｓｍｕｒｆ攻撃とは、ＩＣＭＰ ｅｃｈｏ ｒｅｑｕｅｓｔを用いたＤｏＳ攻撃であり、攻撃者はＩＣＭＰ ｅｃｈｏ ｒｅｑｕｅｓｔパケットの送信元ＩＰアドレスを攻撃対象のホストのＩＰアドレスに偽装し、そのパケットをネットワークのブロードキャストアドレスに送る。すると、パケットを受け取ったネットワーク内の全てのホストから攻撃対象のホストに向けてＩＣＭＰ ｅｃｈｏ ｒｅｐｌｙパケットが一斉に返される。この大量のＩＣＭＰパケットによって攻撃対象のホストやネットワークに過重負荷がかかるため、サーバなどではサービスの提供が困難になる。
【０００５】
どのようなＤｏＳ攻撃であっても、単一のホストからの攻撃であれば攻撃の規模には限度があるが、複数のホストから一斉にＤｏＳ攻撃を行うＤｉｓｔｒｉｂｕｔｅｄ ＤｏＳ（ＤＤｏＳ）攻撃は、攻撃の規模と攻撃元の分散性から攻撃を受けたサーバでの対処が難しいため、ネットワーク、とりわけバックボーンネットワークの管理者の立場において検出することが、その後の対応を行う上で重要となる。
【０００６】
直接の攻撃とは別に、ＳＹＮ Ｆｌｏｏｄ攻撃が起こった際にその副産物としてバックスキャッタと呼ばれるトラヒックが観測される。これは攻撃を受けたサーバから偽装されたＩＰアドレスに向けて送られるＳＹＮ／ＡＣＫパケット群であり、その多くは実際には使われていないＩＰアドレスが指定されているため、ヘッダのＴＴＬがゼロなるまでネットワーク内を流れつづけることになる。実際には使われていないＩＰアドレスに向けて送られるパケットを観測するシステムとしてＮｅｔｗｏｒｋ ｔｅｌｅｓｃｏｐｅがある。Ｎｅｔｗｏｒｋ ｔｅｌｅｓｃｏｐｅはＩＰｖ４の全アドレス空間のうちのほとんど正常なＩＰアドレスが存在しない部分空間を観測するためのシステムである。その性質から、バックスキャッタのトラヒックやワームによるランダムスキャンのなどの観察に適している。
【０００７】
また、ＤｏＳ攻撃の検出に関連する研究としては以下のようなものがある。Ｖ． Ａ． Ｓｉｒｉｓらはトラヒックに含まれるＳＹＮパケットの数を計測し、２種類のアルゴリズムを用いて動的に閾値を定め、閾値を超えるＳＹＮパケットが計測された場合にＳＹＮ Ｆｌｏｏｄ攻撃の発生を検出するという手法を提案している（非特許文献１参照）。大下らもＳＹＮ Ｆｌｏｏｄ攻撃を検出する手法を提案している。彼らの手法はｂａｃｋｌｏｇ ｑｕｅｕｅのサイズとタイムアウトになる時間を考慮し、サーバがサービス停止状態になる前に検出を行う。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Ｖ． Ａ． Ｓｉｒｉｓ ａｎｄ Ｆ． Ｐａｐａｇａｌｏｕ， "Ａｐｐｌｉｃａｔｉｏｎ ｏｆ ａｎｏｍａｌｙ ｄｅｔｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｄｅｔｅｃｔｉｎｇ ｓｙｎ ｆｌｏｏｄｉｎｇ ａｔｔａｃｋｓ，" Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， ｖｏｌ．２９， ｎｏ．９， ｐｐ．１４３３−１４４２， ２００６．
【発明の概要】
【発明が解決しようとする課題】
【０００９】
Ｖ． Ａ． Ｓｉｒｉｓらはトラヒックに含まれるＳＹＮパケットの数を計測し、２種類のアルゴリズムを用いて動的に閾値を定め、閾値を超えるＳＹＮパケットが計測された場合にＳＹＮ Ｆｌｏｏｄ攻撃の発生を検出するという手法を提案しているが、彼らの手法は、ＳＹＮ Ｆｌｏｏｄ攻撃が発生していることは検知できても、ＳＹＮ Ｆｌｏｏｄ攻撃のフローを特定することができないという問題がある。また大下らもＳＹＮ Ｆｌｏｏｄ攻撃を検出する手法を提案しているが、トラヒックを観測するポイントが、サーバ側のネットワークへのインターフェース部分を想定しており、バックボーンＮＷを対象としたものではない。さらにトラヒックの全パケットを観測しているため、高速な回線を測定対象とした場合のスケール性に問題がある。
【００１０】
本発明は、バックボーンＮＷの任意のルータポートを観測対象とし、パケットサンプリング技術を用いることで、回線レートが高速である場合にも対応可能な、持続的な高パケットレートフロー（パケットレートが所定値以上のトラヒックのフロー）を検出することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の高パケットレートフロー検出装置は、
パケットレートが所定値以上のトラヒックのフローを検出する高パケットレートフロー検出装置であって、
パケットを無作為に抽出するパケット無作為抽出部と、
所定の測定期間を部分区間に分割し、部分区間内に抽出されたパケット数をフロー毎に集計するパケット数測定部と、
部分区間においてパケット数が閾値以上のフローを、パケットレートが所定値以上のトラヒックフローであるとして検出する高パケットレートフロー検出部と、
を有することを特徴とする。
【００１２】
本発明の高パケットレートフロー検出方法は、
パケットレートが所定値以上のトラヒックのフローを検出する高パケットレートフロー検出装置における高パケットレートフロー検出方法であって、
パケットを無作為に抽出するステップと、
所定の測定期間を部分区間に分割し、部分区間内に抽出されたパケット数をフロー毎に集計するステップと、
部分区間においてパケット数が閾値以上のフローを、パケットレートが所定値以上のトラヒックフローであるとして検出するステップと、
を有することを特徴とする。
【発明の効果】
【００１３】
本発明によれば、パケットサンプリング技術を用いることで、パケットレートが所定値以上のトラヒックのフローを検出することが可能になる。
【図面の簡単な説明】
【００１４】
【図１】本発明の実施例に係る高パケットレートフロー検出装置の構成図
【図２】本発明の実施例に係る高パケットレートフロー検出装置のパケット無作為抽出部で実行される処理プロセスのフローチャート
【図３】本発明の実施例に係る高パケットレートフロー検出装置のＩＷ情報の更新部で実行される処理プロセスのフローチャート
【図４】本発明の実施例に係る高パケットレートフロー検出装置の高パケットレートフロー検出部で実行される処理プロセスのフローチャート
【図５】スライディングウィンドウの概要を示す図
【図６】制御パラメータｆが制約条件を満たす領域を示す図
【図７】制御パラメータｆが制約条件を満たす領域を示す図
【図８】スライディングウィンドウの母集団におけるパケット数の説明図
【図９】スライディングウィンドウのサンプルにおけるパケット数の説明図
【図１０】実験に用いたトラヒックデータの概要を示す表
【図１１】実験に用いた規定パラメータを示す表
【図１２】実験で得られた制御パラメータ（ｆ，ｍ）を示す表
【図１３】閾値の候補と検出率の関係を示す図（Ｂａｃｋｓｃａｔｔｅｒ）
【図１４】閾値の候補と検出率の関係を示す図（ＣＥＳＣＡ−Ｉ（Ｒ＝８００））
【図１５】閾値の候補と検出率の関係を示す図（ＣＥＳＣＡ−Ｉ（Ｒ＝１０００））
【図１６】サンプルにおける閾値を示す表
【図１７】実験結果の平均と９５％信頼区間を示す表
【発明を実施するための形態】
【００１５】
以下、図面を参照して本発明の実施例について説明する。
【００１６】
本発明の実施例では、長さＴ秒の測定期間に含まれる長さｔ秒の任意の部分区間において、パケットレートがＲ［ｐａｃｋｅｔｓ／ｓｅｃ］以上のフローを、ランダムパケットサンプリングによって得られた情報からオンラインで検出することを特徴とする持続的な高パケットレートフローのオンライン検出法について説明する。
【００１７】
より具体的には、長さＴＳＷ＝Ｔの測定期間（スライディングウィンドウＳＷ）を自然数ｋとｍに対してｋｍ個のベーシックウィンドウ（ＢＷ）に分割し、さらにｈ≦ｋかつｋとは互いに素な自然数ｈを用いて、連続するｈｍ個のＢＷで構成される検査ウィンドウ（ＩＷ）をＳＷ内に（ｋ−ｈ）ｍ＋１個作成し、ＳＷ内の全てのＩＷにおいてパケットレートがＲ［ｐａｃｋｅｔｓ／ｓｅｃ］以上であるフローを検出する。なお、検査ウィンドウの大きさＴＩＷ＝ｔはｋとｈとにより決まり、ＴＩＷ＝（ｈ／ｋ）ＴＳＷ［ｓｅｃ］となることに注意する。
【００１８】
＜高パケットレートフロー検出装置の構成＞
図１は、持続的な高パケットレートフローのオンライン検出法を実現するための、本発明の実施例に係る高パケットレートフロー検出装置の構成図である。
【００１９】
本実施例に係る高パケットレートフロー検出装置は、パラメータｆとｍの設計部１０１と、パラメータｗ＊の設計部１０２と、パケット無作為抽出部１０３と、ＢＷ情報保存部１０４と、ＩＷ情報の更新部１０５と、ＩＷ情報保存部１０６と、高パケットレートフロー検出部１０７とを有する。
【００２０】
パラメータｆとｍの設計部１０１は、パケットサンプリング確率ｆとＢＷの大きさを定めるパラメータｍとを設計する。パラメータｆとｍの設計部１０１は、目標時間ＴＤ＿ｍａｘ内に検出すること、ＢＷの幅が最大許容値ＴＢＷ＿ｍａｘ以下であること、を制約条件とし、検出対象外のフローの誤検出率を最小化するｆとｍとを設計する。
【００２１】
具体的には以下に説明するように、パラメータｆとｍの設計部１０１は、入力パラメータである、ＳＷの長さＴＳＷ［ｓｅｃ］、１サンプルパケットあたりの処理時間Δ１［ｓｅｃ］、ＳＷの解析に必要なパケット数とは独立な処理時間Δ２［ｓｅｃ］、検出目標時間ＴＤ＿ｍａｘ［ｓｅｃ］、観測する回線の最大パケットレートＣｍａｘ［ｐａｃｋｅｔｓ／ｓｅｃ］、ＢＷの幅の最大許容値ＴＢＷ＿ｍａｘ［ｓｅｃ］、に対して、
【００２２】
【数１】
と定義するとき、
【００２３】
【数２】
の場合には、ｍを
【００２４】
【数３】
に設定し、ｆをｆ＊＝ｍａｘ｛ｆ１（ｍ＋），ｆ２（ｍ−）｝に設定する。一方、
【００２５】
【数４】
の場合には、ｍ＊＝ｍ＋、ｆ＊＝ｆ１（ｍ＋）に設定する。
【００２６】
パラメータｗ＊の設計部１０２は、高パケットレートフローを検出する際のサンプルパケット数に関する閾値ｗ＊を設計する。具体的には、ｆとｍが最適設計された後で、与えられた高レートフローの見逃し許容誤差εに対して、検出対象フローの検出見逃し確率を許容値ε以下に抑えるよう、ＩＷ内のサンプルパケット数の閾値ｗ＊を設計する。
【００２７】
パラメータｗ＊の設計部１０２は、検出確率が最低となる閾値フローの分布Ｘ＊（各ＢＷにおけるパケット数の確率分布）に対して、このようなフローが全てのＩＷにおいてｗ個以上のパケットがサンプルされる確率をＰ（ｗ｜Ｘ＊）、高レートフローの見逃し許容誤差をεとするとき、ｗ＊を、
【００２８】
【数５】
により設計する。ただしＰ（ｗ｜Ｘ＊）はモンテカルトシミュレーションを用いた数値実験により求める。
【００２９】
パケット無作為抽出部１０３は、測定対象となるルータポートを流れる各パケットに対して各々独立に確率ｆでパケットをサンプリングする。
【００３０】
図２に、パケット無作為抽出部１０３で実行される処理プロセスのフローチャートを示す。測定対象のルータポートにパケットが到着するごとに、０から１の値をとる一様乱数ｘを発生させ（Ｓ１０１）、その値がｆより小さい場合には（Ｓ１０２：Ｙ）、到着パケットをサンプリングし（Ｓ１０３）、ＢＷ情報保存部１０４の該当フローのサンプルパケット数を全て１だけ増加させる。
【００３１】
ＢＷ情報保存部１０４は、ＢＷ内でサンプルされたパケット数を各フローに対して保存する。
【００３２】
ＩＷ情報の更新部１０５は、ＢＷの境界時点において、ＢＷ情報保存部１０４のサンプルパケット数情報を、現在のＢＷを含む全てのＩＷに対して、フローごとに足しこむ。また最古のＢＷを含むＩＷを破棄し、連続する最近のｋｍ個のＢＷを用いて新しいＩＷを作成する。このように、ＩＷ情報の更新部は、測定期間ＳＷを任意の部分区間ＩＷに分割し、部分区間内に抽出されたパケット数をフロー毎に集計する。
【００３３】
図３に、ＩＷ情報の更新部１０５で実行される処理プロセスのフローチャートを示す。ＢＷの境界時点において、ＢＷ情報保存部１０４のサンプルパケット数情報を、現在のＢＷを含む全てのＩＷに対して、フローごとに足しこみ（Ｓ２０１）、ＢＷ情報保存装置１０４の全エントリをゼロに初期化する（Ｓ２０２）。またＩＷ情報保存部１０６において、最古のＢＷを含むＩＷを破棄し、連続する最近のｋｍ個のＢＷを用いて新しいＩＷを作成する（Ｓ２０３）。
【００３４】
ＩＷ情報保存部１０６は、ＩＷの情報（（ｋ−ｈ）ｍ＋１の各ＩＷにおける各フローのサンプルパケット数）を保存する。
【００３５】
高パケットレートフロー検出部１０７は、ＳＷに含まれる（ｋ−ｈ）ｍ＋１個の全ＩＷにおいてｗ＊個以上のパケットがサンプルされたフローを高レートフローとして検出する。
【００３６】
図４に、高パケットレートフロー検出部１０７で実行される処理プロセスのフローチャートを示す。ＢＷの境界時点において、ＳＷに含まれる（ｋ−ｈ）ｍ＋１個の全ＩＷにおいてｗ＊個以上のパケットがサンプルされたフローを高レートフローとして検出する（Ｓ３０１）。
【００３７】
＜検出の枠組み＞
次に、本発明の実施例に係る持続的な高パケットレートフローのオンライン検出法の枠組みを説明する。
【００３８】
ＤｏＳ攻撃等の異常トラヒックが発生した際、ネットワークのバックボーンにおいて迅速に検出することは、ネットワーク全体を保守管理する上で非常に重要である。本実施例ではＤＤｏＳ攻撃等、高パケットレートが長時間持続するような異常トラヒックに注目し、パケットレートが予め定められた閾値を一定時間以上超え続けているフローを検出することを試みる。
【００３９】
ネットワークを流れるＩＰトラヒックにおいて、フローとは、共通のＩＰアドレス、ポート番号、ＳＹＮフラグなどの組み合わせをもつパケット群として定義される。例えばＤｏＳ攻撃に用いられているパケット群を一つのフローと見なそうとする場合、一般に攻撃パケットのヘッダに記載されている送信元ＩＰアドレスは改竄されており、確実に共通するのは宛先のＩＰアドレスだけとなる。そのため共通の宛先ＩＰアドレスを持つパケット群をフローと定義するとＤｏＳ攻撃の攻撃フローの検出が可能となる。また、バックスキャッタのトラヒックを観測する場合、ＤｏＳ攻撃を受けたサーバから不特定多数の宛先に向けて送信されるパケットを一つのフローとして見なしたい。この場合は共通の送信元ＩＰアドレスを持つパケット群をフローとして定義するのが適している。このようにフローの定義は検出したい対象や観測地点によって適宜定義を行うと都合が良いため、本実施例ではフローの定義は任意とする。
【００４０】
ここで、検出対象フローの定義を行う。上記のように、本実施例ではパケットレートが予め与えられる閾値を一定時間以上超え続けているフローを検出対象とする。この検出対象をより明確にするために、本実施例では以下のように定義する。
【００４１】
検出対象フローの定義：予め与えられた定数Ｒ［ｐａｃｋｅｔｓ／ｓｅｃ］、Ｔ［ｓｅｃ］、ｔ［ｓｅｃ］（ｔ≦Ｔ）に対して、Ｔ秒間の測定期間に含まれるｔ秒間の任意の区間全てについて、パケットレートがＲ［ｐａｃｋｅｔｓ／ｓｅｃ］以上であるフローを検出対象とする。
【００４２】
この検出対象の定義には、瞬間的に大量のパケットが発生したが、その後すぐに消えてしまうようなバースト的なフローを検出対象から外すという意図がある。バースト的なフローは捉え方によれば高パケットレートフローであるが、検出した時点ですでに消えてしまっているのであれば対応することが出来ない。検出されたフローは管理者が対応するかどうかを判断しなければならないため、バースト的なフローを検出することは管理者のオーバヘッドが増えることになる。
【００４３】
しかし、上記で定義される検出対象フローをネットワークのバックボーンにおいて常時トラヒックを観測しながら検出を行うには大きく三つの問題がある。まず一つ目は、Ｔ秒間の測定期間に含まれる長さｔ秒をもつあらゆる部分区間全てについてパケットレートを調査することは極めて困難である。二つ目は、トラヒックを観測し続ける一方で検出対象のフローをオンラインで検出するためには、観測した解析対象データを更新する仕組みが必要となる。三つ目は、ネットワークのバックボーンのような高速な回線では、回線を流れる全てのパケットを対象に解析することは非現実的でありスケーラビリティを欠く。
【００４４】
そこで本実施例では、スライディングウィンドウ方式を用いて最初の二つの問題の解決を図る。スライディングウィンドウ方式とは、解析対象のデータを保持するスライディングウィンドウをベーシックウィンドウと呼ばれる単位に分割し、ベーシックウィンドウ単位で解析データを更新する、オンラインパケット処理アルゴリズムである。本実施例ではこのスライディングウィンドウ方式に、検査ウィンドウと呼ばれる部分ウィンドウの概念を導入し、上記で定義された検出対象フローを含む新たな検出対象フローの集合を定義することで、一つ目の問題を解決する。
【００４５】
三つ目の問題に関しては、パケットサンプリングを用いることで解決を図る。すなわち、パケットの標本抽出を行い、得られた情報を基にサンプリングの対象となった母集団の統計量を推定することで、処理サイクルやメモリ使用量を抑える。本実施例では、各パケットに対してフローの情報を用いず、独立に一定の確率ｆで無作為標本抽出を行うランダムパケットサンプリングを用いる。これにより、処理サイクルを大幅に抑えることができ、バックボーンなどの高速な回線に対しても適用可能となる。しかし、パケットサンプリングはその性質上、情報の欠如をもたらすため、特にサンプリングをする頻度が少ない場合はサンプリングの対象である母集団の統計量を推定することが困難になる。例えば、パケットが一つもサンプリングされないフローについては、母集団における統計量を推定することは不可能である。しかし、検出対象である高パケットレートのフローであれば、適切なサンプリングレートを用いることによって、母集団を推定できるだけの十分な標本を抽出できると考えられる。
【００４６】
＜スライディングウィンドウ方式による検出とデータ更新＞
バックボーンネットワークを流れているトラヒックを常時、測定管理し、高パケットレートをもつフローの検出を行うにはオンラインアルゴリズムが必要である。すなわち、データの取得、解析、破棄を継続的に行う必要がある。本実施例では、この解析対象データを更新するための手段としてスライディングウィンドウ方式を採用する。スライディングウィンドウ方式とは、解析対象となるデータを保持するスライディングウィンドウをベーシックウィンドウと呼ばれる複数の単位に分割し、解析終了後に最も古いベーシックウィンドウのデータを破棄し、新たに取得された１ベーシックウィンドウ分のデータを加えることによって解析対象のデータを更新する方式である。
【００４７】
スライディングウィンドウ方式には、スライディングウィンドウの大きさをパケット数で規定する方法と測定時間で規定する方法の２種類が存在する。前者は一定数のパケットが回線を通過したとき、あるいは一定数のパケットがサンプリングされたときにベーシックウィンドウを生成し、スライディングウィンドウを更新する。母集団におけるパケット数を一定にすると、トラヒックのフロー毎のパケット数分布などを求めることが容易になり、サンプル数を一定にすると、メモリの使用を一定にすることができるなどの利点がある。一方、後者は一定時間毎にベーシックウィンドウを生成し、スライディングウィンドウを更新する。母集団におけるパケット数およびサンプリングされるパケット数はスライディングウィンドウが更新される度に変わるが、測定時間を一定にすることができる。
【００４８】
本実施例では、パケットレート、すなわち、単位時間当たりに各フローに含まれるパケット数を対象としている。そこで、スライディングウィンドウが保持する解析対象データの測定時間が一定時間ＴＳＷ［ｓｅｃ］になるようにスライディングウィンドウの大きさを定める。さらに自然数ｋとｍを用いて、スライディングウィンドウをＴＳＷ／（ｋｍ）［ｓｅｃ］刻みでｋｍ個のベーシックウィンドウに分割する。すなわち、ＴＳＷ／（ｋｍ）秒毎に取得されるデータで新たなベーシックウィンドウを作成し、スライディングウィンドウに加えると共に、スライディングウィンドウ内の最も古いベーシックウィンドウのデータを破棄することによって解析対象となるデータの更新を行う。
【００４９】
また本実施例では、ｋとは互いに素な自然数ｈ（ｈ≦ｋ）を用いて、連続するｈｍ個のベーシックウィンドウで構成される検査ウィンドウをスライディングウィンドウ内に（ｋ−ｈ）ｍ＋１個作成する。このとき、検査ウィンドウの大きさＴＩＷは（ｈ／ｋ）ＴＳＷ［ｓｅｃ］となることに注意する。図５にｋ＝３、ｍ＝２、ｈ＝２としたときのスライディングウィンドウの概要を示す。
【００５０】
このスライディングウィンドウ方式において検出対象となるフローは下記の通りである。
【００５１】
スライディングウィンドウ方式における検出対象フローの定義：予め与えられた定数Ｒ［ｐａｃｋｅｔｓ／ｓｅｃ］、ＴＳＷ［ｓｅｃ］、自然数ｋ、ｍ、ならびにｋと互いに素な自然数ｈ（ｈ≦ｋ）に対して、ベーシックウィンドウの大きさをＴＢＷ＝ＴＳＷ／（ｋｍ）［ｓｅｃ］とし、連続するｋｍ個のベーシックウィンドウから構成されるスライディングウィンドウを考え、このスライディングウィンドウ内の大きさＴＩＷ＝（ｈ／ｋ）ＴＳＷ［ｓｅｃ］をもつ（ｋ−ｈ）ｍ＋１個全ての検査ウィンドウにおいて、パケットレートがＲ［ｐａｃｋｅｔｓ／ｓｅｃ］以上であるフローを検出対象とする。
【００５２】
ここで、上記の「検出対象フローの定義」で用いたＴおよびｔに対して、ＴＳＷ＝ＴかつＴＩＷ＝（ｈ／ｋ）ＴＳＷ＝ｔを満たす互いに素な自然数ｋおよびｈ（ｈ≦ｋ）が存在すると仮定している。この仮定より、上記の「検出対象フローの定義」を満たす検出対象フローの集合は、スライディングウィンドウ方式で検出対象となっているフローの集合の部分集合になっている。すなわち、「スライディングウィンドウ方式における検出対象フローの定義」の条件を満たすフローを全て検出すれば、「検出対象フローの定義」で定められた検出対象フローは全て検出される。以後、検出対象フローはスライディングウィンドウ方式における「検出対象フローの定義」に基づくものとする。
【００５３】
＜ランダムパケットサンプリングを用いた検出＞
高速回線に対してスケーラビリティを確保するために、本発明の実施例ではランダムパケットサンプリングを用いる。ＴＳＷ秒間に回線を通過したパケット全体を母集団し、そこから確率ｆで無作為標本抽出されたパケットの情報のみを用いて母集団における検出対象フローを検出することを試みる。母集団における検出対象フローは、（ｋ−ｈ）ｍ＋１個の検査ウィンドウ全てにおいてパケットレートが予め与えられる閾値Ｒ［ｐａｃｋｅｔｓ／ｓｅｃ］以上のフローである。検査ウィンドウのパケットレートがＲ以上であることと、検査ウィンドウ内のパケット数が
【００５４】
【数６】
以上であることは等価である。よって、以下では
【００５５】
【数７】
をパケット数の閾値と呼ぶ。すなわち、検出対象フローは母集団の全ての検査ウィンドウにおいて、パケット数がｚ＊個以上のフローである。
【００５６】
もし全てのパケットを対象に解析が行えるのであれば、各検査ウィンドウにおいて、それぞれのフローを構成するパケットがｚ＊個以上あるかどうかを調べれば良いが、本実施例ではパケットサンプリング用いるため、新たに各検査ウィンドウにおけるサンプリングされたパケット数の閾値ｗ＊を設け、スライディングウィンドウ内の全ての検査ウィンドウでｗ＊個以上のパケットがサンプリングされたフローを検出することにする。ここで ｗ＊は、検出対象のフローのうち最低のパケットレート、すなわち母集団の全ての検査ウィンドウにおいてパケット数がｚ＊個であるフロー（これを閾値フローと呼ぶことにする）を十分高い確率で検出できるように定める。これは異常な高パケットレートフローが発生した際には見逃さないようにするためである。しかしサンプリングによって情報が欠如するため、閾値ｗ＊を０にしない限り検出対象を確実に検出することはできない。そこで本実施例では、検出対象フローを見逃してしまう確率が十分小さい値ε以下となるようにｗ＊を定める。具体的なパラメータ設定方法は後述する。
【００５７】
以下に検出の手順をまとめる。ただし、スライディングウィンドウはＳＷ、検査ウィンドウはＩＷ、ベーシックウィンドウはＢＷとそれぞれ略記する。
【００５８】
まず、測定期間ＴＳＷ秒の間に確率ｆで無作為標本抽出されたパケットのデータを保持するＳＷにおいて、ＳＷに含まれる（ｋ−ｈ）ｍ＋１個全てのＩＷにおいてｗ＊個以上サンプリングされているフローがあれば、そのフローを検出する。
【００５９】
次に、ＳＷの解析終了後、最も古いＢＷ、ならびに、このＢＷを含むＩＷを破棄する。
【００６０】
一方、新たにＴＢＷ秒間に転送されたパケットのサンプリング終了後、新しいＢＷを作成し、それをＳＷに加えると共に、連続する最近のｈｍ個のＢＷを用いて新しいＩＷを作成する。
【００６１】
次に、新たに作成されたＩＷを検査し、ｗ＊個以上含まれるフローがあった場合には過去のＩＷの検査結果と照らし合わせ、（ｋ−ｈ）ｍ＋１個のＩＷ全てにおいてサンプルされたパケット数が閾値ｗ＊を超えていれば、そのフローを検出する。
【００６２】
スライディングウィンドウ方式によるデータ更新とランダムパケットサンプリングを用いた本実施例の手法は上記の手順を常時繰り返すものである。
【００６３】
本実施例の手法では、予め与えられるパラメータである、パケットレートの閾値Ｒ［ｐａｃｋｅｔｓ／ｓｅｃ］、測定時間であるスライディングウィンドウの大きさＴＳＷ［ｓｅｃ］、検査ウィンドウの大きさを定める互いに素な自然数ｋおよびｈの他に、制御可能なパラメータとして、サンプリングレートｆ、データ更新単位であるベーシックウィンドウの大きさを定める自然数ｍ、ならびに、サンプリングされたパケット数の閾値ｗ＊がある。よって、制御可能なこれら三つのパラメータ（以後制御パラメータと呼ぶ）の値を適切に決定する必要がある。その際、前述の検出対象のフローを見逃してしまう確率をε以下とするという条件を満たすと同時に、スライディングウィンドウ方式がオンラインアルゴリズムとして正常に機能するために、新しいベーシックウィンドウが生成される前に現在のスライディングウィンドウの解析が終了できるようにしなければならない。
【００６４】
この二つの制約条件下で三つの制御パラメータを設定しようとする場合には自由度が大きく、制御パラメータは一意に決定されない。そこで、以下では、検出対象フローの発生から検出までに要する時間に関する制約条件と、スライディングウィンドウ方式における検出対象フローの集合が、本来の検出対象フローの集合に近いものとなるように検査ウィンドウのスライド幅ＴＢＷ＝ＴＳＷ／（ｋｍ）に関する最大許容値を導入し、各制御パラメータを一意に定める手法を説明する。
【００６５】
そして、サンプリングレートｆ、ベーシックウィンドウの大きさを定める自然数ｍ、並びに、サンプルにおけるパケット数の閾値ｗ＊の三つの制御パラメータを、複数の制約条件を導入することにより、一意に決定する手法を説明する。
【００６６】
＜制御パラメータと制約条件＞
検出対象のフローを定義するパラメータは次の四つである。
【００６７】
・パケットレートの閾値Ｒ［ｐａｃｋｅｔｓ／ｓｅｃ］
・スライディングウィンドウの大きさＴＳＷ［ｓｅｃ］
・検査ウィンドウの大きさを定める互いに素な自然数ｋ及びｈ
一方、制御パラメータは以下の三つである。
【００６８】
・サンプリングレートｆ
・ベーシックウィンドウの大きさを定める自然数ｍ
・サンプルにおけるパケット数の閾値ｗ＊［ｐａｃｋｅｔｓ］
以上七つのパラメータが決定されると、上記の「検出の枠組」みで説明した検出手法を用いることができる。
【００６９】
制御パラメータを設定する際にまず注意しなければならないことは、スライディングウィンドウ方式を用いた本提案手法をオンラインアルゴリズムとして正常に機能させることである。オンラインで検出を行うということは、解析対象のデータが更新される前に、現在のデータの解析処理が完了しなければならないということである。すなわち、スライディングウィンドウの解析を、新たな１ベーシックウィンドウ分のデータを取得する前に終わらせなければならない。よって、スライディングウィンドウの解析時間τ［ｓｅｃ］は
【００７０】
【数８】
を満たさなければならない。
【００７１】
そこで、スライディングウィンドウの解析時間τ［ｓｅｃ］について評価を行う。パケットの情報はサンプリングされた時点でフロー毎に仕分けられ、パケット数はカウントされているものとする。すなわち、ベーシックウィンドウはフロー毎の情報を保持しており、保持するフロー数の上限はサンプリングされるパケット数となる。以下に新しいベーシックウィンドウが生成された直後からのスライディングウィンドウの処理を列挙する。なお、解析を行う際はスライディングウィンドウ内の（ｋ−ｈ）ｍ＋１個の検査ウィンドウのみを対象とするが、データ処理の都合上、まだｈｍ個揃っていない先のスライディングウィンドウで用いる検査ウィンドウも、関係するベーシックウィンドウが到着し次第順次加えながら作成していく。以下に手順を示す。
【００７２】
（１）新しいベーシックウィンドウをスライディングウィンドウ内の関係する全ての検査ウィンドウ（まだｈｍ個そろっていないものも含む）に加える。
【００７３】
（２）最近のｈｍ個のベーシックウィンドウで構成される検査ウィンドウを調査し、閾値ｗ＊を超えるフローを検知する。
【００７４】
（３）以前の検査ウィンドウの検知結果を用いて、全ての検査ウィンドウで検知されたフローを検出する。
【００７５】
（４）最も古い検査ウィンドウおよびベーシックウィンドウを破棄する。
【００７６】
上記手順のうち、（１）はベーシックウィンドウに含まれる各フローについてフロー情報の比較や情報の集約などの複雑な処理を行うため、その処理時間はベーシックウィンドウ内のフロー数に依存する。（２）以降の各手順は、予め確保された空間に渡って単純な比較やデータの廃棄のみを行うため、一定時間内に処理できると考えて良い。そこで、本実施例ではスライディングウィンドウの処理時間τを、ベーシックウィンドウにサンプリングされるパケット数に依存する処理時間と、パケット数とは独立な一定の処理時間の和として考え、次式で処理時間の上界を見積もることにする。
【００７７】
【数９】
ここで、Ｃｍａｘ、Δ１およびΔ２は、それぞれ、観測する回線の最大パケットレート、スライディングウィンドウの解析における１サンプルパケット当りの処理時間、および、サンプルパケット数とは独立な処理時間を表している。
【００７８】
ＤｏＳ攻撃のような異常フローは発生から検出するまでに時間がかかりすぎると、攻撃を受けているサーバが機能を停止してしまう。そこで本実施例では、検出対象のフローが発生してから目標時間ＴＤ＿ｍａｘ［ｓｅｃ］以内に検出できるようにパラメータを定める。検出対象のフローを検出するために必要な時間は、対象フローの測定にかかる時間ＴＳＷとスライディングウィンドウの解析時間τの和で与えられる。しかし、検出対象のフローは多くの場合、ベーシックウィンドウの途中から発生すると考えられ、検出した時点では直前に破棄したベーシックウィンドウの途中から始まっていた可能性が高い。すなわち、最大で１ベーシックウィンドウ分の検出遅れが生じることになる。したがって、検出対象フローを目標時間以内に検出するための条件は次式で与えられる。
【００７９】
【数１０】
上記の「検出対象フローの定義」では、Ｔ（＝ＴＳＷ）秒の測定期間内の任意のｔ（＝ＴＩＷ）秒の区間全てにおいてパケットレートがＲ以上となっているため、検査ウィンドウのスライド幅が大きすぎると、上記の「検出対象フローの定義」を満足しないフローを多数検出することになる。そこで、検査ウィンドウのスライド幅に関する最大許容値ＴＢＷ＿ｍａｘ［ｓｅｃ］を設ける。本実施例において、検査ウィンドウのスライド幅はベーシックウィンドウのサイズＴＢＷとなるため、ＴＢＷは次の条件を満たす必要がある。
【００８０】
【数１１】
上記の「検出の枠組み」で説明した検出手法では、ランダムパケットサンプリングを行い、サンプリングされたパケットの情報のみを用いて検出を行うため、検出対象フローの検出見逃しや検出対象外フローの誤検出が発生する。三つの制御パラメータのうち二つを固定し、残りの一つを変化させた場合、サンプリングレートｆに関しては、ｆを小さくするほど検出見逃しおよび誤検出は発生しやすくなる。ベーシックウィンドウのサイズを規定するｍに関しては、ｍを大きくするほど検査ウィンドウの数が増え、全ての検査ウィンドウでｗ＊以上となる確率が減少するため、検出見逃しは増加するが誤検出は減少する。検査ウィンドウにおけるパケット数の閾値ｗ＊に関しては、ｗ＊が小さいほど検出見逃しは減少するが誤検出は増加する。このようにｍとｗ＊に関してはトレードオフの関係が存在することに注意する。異常フローを見逃してしまうと、その後のネットワークに大きな障害をもたらしかねないため、本実施例では検出対象のフローを見逃してしまう確率を十分小さなε以下に抑えるようにパラメータを設定する。その上で、検出対象外フローを誤検出してしまう確率もなるべく小さくなるように制御パラメータを設定する。
【００８１】
上記のシステムを規定するパラメータを以下にまとめておく。
【００８２】
・見逃し許容誤差ε（検出対象フローを１−ε以上の確率で検出）
・検出目標時間ＴＤ＿ｍａｘ［ｓｅｃ］
・スライド幅の最大許容値ＴＢＷ＿ｍａｘ［ｓｅｃ］
・観測する回線の最大パケットレートＣｍａｘ［ｐａｃｋｅｔｓ／ｓｅｃ］
・１サンプルパケットあたりの処理時間Δ１［ｓｅｃ］
・スライディングウィンドウの解析に必要なパケット数とは独立な処理時間Δ２［ｓｅｃ］
＜誤検出確率の最小化問題＞
上記の制約条件の下、検出対象外の低パケットレートフローを誤検出する確率を最小化するように制御パラメータを設定する問題を考える。すなわち、この問題は次のように定式化される。
【００８３】
目的関数：検出対象外フローの誤検出確率→最小
制約条件：サンプリングレートｆ＞０
ベーシックウィンドウの大きさを定める自然数ｍ
サンプルにおけるパケット数の閾値ｗ＊（自然数）
オンラインのアルゴリズムとして機能すること
目標時間ＴＤ＿ｍａｘ内に検出可能なこと
検査ウィンドウのスライド幅≦最大許容値ＴＢＷ＿ｍａｘ
検出対象フローの検出見逃し確率≦ε以下
なお、対象フローの検出見逃し確率に関する制約条件は、サンプリングレートｆとベーシックウィンドウの大きさを定めるｍが決定した後に、ｗ＊を調整することによって満たすことができるため、上記の問題とは独立な問題として考える。
【００８４】
まず、目的関数について説明する。サンプリングによって得られたパケットの情報を用いて母集団の統計量を推定する場合、サンプリングされたパケット数が多ければ多いほどその統計的精度は高くなる。そのため検出対象外のフローを誤検出してしまう確率を下げるためにはなるべくたくさんのパケットをサンプリングすればよい。スライディングウィンドウのサイズはＴＳＷ秒で固定されているため、サンプリングされるパケット数を多くするにはサンプリングレートｆを大きくする、すなわち、上記の制約条件下でｆを最大化することが検出対象外フローの誤検出確率を最小化することと等価となる。したがって、上記の問題は次のようなサンプリングレートｆの最大化問題となる。
【００８５】
目的関数：サンプリングレートｆ→最大
制約条件：サンプリングレートｆ＞０
ベーシックウィンドウの大きさを定める自然数ｍ
オンラインのアルゴリズムとして機能すること
目標時間ＴＤ＿ｍａｘ内に検出可能なこと
検査ウィンドウのスライド幅≦最大許容値ＴＢＷ＿ｍａｘ
次に、制約条件について説明する。スライディングウィンドウの解析時間τは式（２）に従うと仮定する。さらに上記より、オンラインのアルゴリズムとして機能するための条件は式（１）で、目標時間内の検出の条件は式（３）で、検査ウィンドウのスライド幅に関する条件は式（４）で与えられる。制約条件をこれらで置き換え、ｍに関してｋｍ＝ＴＳＷ／ＴＢＷを加えると、上記の問題は次のように書き換えられる。
【００８６】
目的関数：サンプリングレートｆ→最大
制約条件：ｆ＞０
ｍは自然数
τ≦ＴＢＷ
ＴＳＷ＋ＴＢＷ＋τ≦ＴＤ＿ｍａｘ
ＴＢＷ≦ＴＢＷ＿ｍａｘ
τ＝ｆＣｍａｘＴＢＷΔ１＋Δ２
ｋｍ＝ＴＳＷ／ＴＢＷ
この制約条件下で、サンプリングレートｆを最大にする自然数ｍを求めることが目的となる。τ≦ＴＢＷにτ＝ｆＣｍａｘＴＢＷΔ１＋Δ２を代入し、ＴＳＷ＝ｋｍＴＢＷを用いて変形すると、
【００８７】
【数１２】
となる。同様に、ＴＳＷ＋ＴＢＷ＋τ≦ＴＤ＿ｍａｘは、
【００８８】
【数１３】
となる。また、ＴＢＷ≦ＴＢＷ＿ｍａｘより、
【００８９】
【数１４】
となる。
【００９０】
このとき、本実施例の手法が動作可能であるためには、サンプリングレートｆが正となるようなｍが存在する必要がある。式（５）の右辺が正であるためには、
【００９１】
【数１５】
でなければならない。また、式（６）の右辺が正であるための条件は、
【００９２】
【数１６】
で与えられる。さらに、式（７）より
【００９３】
【数１７】
を得る。すなわち、式（８）、（９）、（１０）より、本実施例の手法が動作可能となるためには、次式が成立する必要がある。
【００９４】
【数１８】
よって、式（１１）が成立しているという条件の下で、以下の最適化問題を考える。
【００９５】
制御パラメータ：ｆ，ｍ
与条件：定数ＴＳＷ，ｋ，ｈ，Ｃｍａｘ，ＴＤ＿ｍａｘ，ＴＢＷ＿ｍａｘ，Δ１，Δ２
ＴＳＷ−ｋΔ２＞０
ｋＴＤ＿ｍａｘ−（ｋ＋１）ＴＳＷ−ｋΔ２＞０
ＴＳＷ≦ｋＴＢＷ＿ｍａｘ
目的関数：ｆ→最大
制約条件：ｆ＞０
ｍは自然数
【００９６】
【数１９】
この混合線形計画問題は以下のようにして解くことができる。まず、自然数ｍを実数ｒで置き換えた以下の緩和問題を考える。
【００９７】
目的関数：ｆ→最大
制約条件：ｆ＞０
【００９８】
【数２０】
２番目と３番目の制約条件で表される領域の境界はそれぞれ次式で与えられる。
【００９９】
【数２１】
【０１００】
【数２２】
ここで、式（１２）がｒに関する減少一次関数に、式（１３）がｒに関する増加一次関数になっていることに注意する。この２直線の交点の座標を
【０１０１】
【数２３】
とおくと、
【０１０２】
【数２４】
である。与条件より、
【０１０３】
【数２５】
は正であることに注意する。一方、最後の制約条件で表される領域の境界を
【０１０４】
【数２６】
とおく。
【０１０５】
【数２７】
以上の準備の下でｆを最大にするようなｒ＊およびｍ＊を、
【０１０６】
【数２８】
に場合分けして求める。
【０１０７】
【数２９】
図６より、
【０１０８】
【数３０】
でｆは最大となる。このとき、
【０１０９】
【数３１】
を求め、
【０１１０】
【数３２】
であればｍ−とｍ＋のうちｆを大きくする方、すなわち
【０１１１】
【数３３】
を採用する。このときのｆ＊はｆ＊＝ｍａｘ｛ｆ１（ｍ＋），ｆ２（ｍ−）｝となる。また、
【０１１２】
【数３４】
のときはｍ＊＝ｍ＋であり、ｆ＊はｆ＊＝ｆ１（ｍ＋）となる。
【０１１３】
【数３５】
図７より、
【０１１４】
【数３６】
でｆは最大となる。このときｍ＊は
【０１１５】
【数３７】
となり、ｆ＊はｆ＊＝ｆ１（ｍ＋）である。
【０１１６】
以上のようにして求めたｍ＊とｆ＊を制御パラメータの値として用いる。
【０１１７】
＜サンプルにおける閾値の導出＞
予め与えられるシステムを規定するパラメータと上記のように設定したサンプリングレートｆおよびベーシックウィンドウの大きさを定めるｍを用いて、検出対象フローを見逃してしまう確率をε以下となるように、検査ウィンドウ内のサンプルパケット数の閾値ｗ＊を設定する。
【０１１８】
ある測定期間において任意のフローに注目する。ＸおよびＹをそれぞれフローを構成するパケット数およびサンプリングされたパケット数を表す確率変数とする。Ｘ＝ｘという条件下で、ｙ個のパケットがサンプリングされる確率ｑ（ｙ｜ｘ）＝Ｐｒ［Ｙ＝ｙ｜Ｘ＝ｘ］は以下の二項分布で与えられる。
【０１１９】
【数３８】
閾値フローを用いた閾値の導出
スライディングウィンドウ内の全ての検査ウィンドウ内のパケット数が
【０１２０】
【数３９】
である閾値フローを１−ε以上の確率で検出できるようにｗ＊を設定すると、全ての検出対象のフローを１−ε以上の確率で検出できることに注意する。
【０１２１】
図８に示すように、スライディングウィンドウ内のｉ番目のベーシックウィンドウの母集団におけるパケット数を確率変数Ｘｉで、ｉ番目の検査ウィンドウの母集団におけるパケット数を確率変数Ｚｉで表すと、ＺｉはＸｉを用いて次のように表される。
【０１２２】
【数４０】
さらに、図９のように、スライディングウィンドウ内のｉ番目のベーシックウィンドウにサンプリングされたパケット数を確率変数Ｙｉで、ｉ番目の検査ウィンドウにサンプリングされたパケット数を確率変数Ｗｉで表すと、ＷｉはＹｉを用いて次のように表される。
【０１２３】
【数４１】
ここで、閾値フローのベーシックウィンドウ毎の母集団におけるパケット数を考える。各検査ウィンドウは母集団においてｚ＊個のパケットで構成されているため、ベーシックウィンドウのパケット数Ｘｉは次の式を満たす。
【０１２４】
【数４２】
上式より、閾値フローの母集団におけるパケット数の分布は１サイクルがｈｍの周期的な分布となることがわかる。そのため、一つ目の検査ウィンドウにおけるパケット数の分布が決定すると、スライディングウィンドウ全体の分布が決定する。
【０１２５】
ベクトルＸをｉ番目の要素がＸｉである、母集団のパケット数を表すｋｍ次元ベクトルとし、閾値フローの母集団におけるパケット数を
【０１２６】
【数４３】
で表すことにする。また、閾値フローがサンプルパケット数の閾値ｗをもって検出される確率、すなわち全ての検査ウィンドウにおいてｗ個以上のパケットがサンプリングされる確率は、
【０１２７】
【数４４】
である。ここで、式（１５）の周辺確率を考える。任意の一つの検査ウィンドウにおいて
【０１２８】
【数４５】
となる確率ｐ（ｗ｜ｚ＊）は、式（１４）の二項分布を用いて次のように求まる。
【０１２９】
【数４６】
このとき、
【０１３０】
【数４７】
となる確率は閾値フローの分布
【０１３１】
【数４８】
とは独立であることに注意する。
【０１３２】
議論を式（１５）の結合確率に戻す。確率変数ＸｉおよびＹｉはｉに関して独立であるが、ＺｉおよびＷｉは前後ｈｍ−１番目まで共通のＸｉおよびＹｉを有し、従属関係にあるため、式（１５）の確率を数値計算によって求めることは困難である。そこで、式（１６）で与えられる周辺確率を用いて、結合確率の上下界値を導く。
【０１３３】
閾値フロー検出確率の上下界値
問題を簡単にするためにｈ＝１の場合、すなわち、スライディングウィンドウの大きさが検査ウィンドウのｋ倍になっている場合を考える。このとき式（１５）で与えられる閾値フローの検出確率は、スライディングウィンドウ内の独立なｋ個の検査ウィンドウにおいてＷｉ≧ｗとなる確率（式（１６））と、その事象が起こったという条件の下で他の検査ウィンドウでもＷｉ≧ｗとなる条件付き確率の積として、
【０１３４】
【数４９】
と変形される。ここで後半部分の条件付き確率は１で上から押さえることができるため、閾値フローの検出確率は、
【０１３５】
【数５０】
として上から押さえられる。ここでｈ≠１の場合にも成り立つように拡張すると、スライディングウィンドウ内の独立な検査ウィンドウの数は
【０１３６】
【数５１】
であるため、
【０１３７】
【数５２】
として閾値フローの検出確率の上界値が得られる。
【０１３８】
次に、下界値について述べる。以下では、サンプリングされたパケット数を表す確率ベクトルをＹ＝（Ｙ１，Ｙ２，...，Ｙｋｍ）とする。このとき、
【０１３９】
【数５３】
が与えられたという条件下では、
【０１４０】
【数５４】
となるため、ベクトルＹ＝（Ｙ１，Ｙ２，...，Ｙｋｍ）は互いに独立な確率変数Ｙｉ（ｉ＝１，２，...，ｋｍ）から構成される確率ベクトルであることに注意する。ただし、
【０１４１】
【数５５】
は
【０１４２】
【数５６】
のｉ番目の要素を表す。よって、確率ベクトルＹは正の関連（ｐｏｓｉｔｉｖｅｌｙ ａｓｓｏｃｉａｔｅｄ）をもつ。ここで正の関連をもつとは、任意の増加関数
【０１４３】
【数５７】
に対して
【０１４４】
【数５８】
すなわち、
【０１４５】
【数５９】
が成立することをいう。
【０１４６】
次に、以下の指示関数を定義する。
【０１４７】
【数６０】
この指示関数は、ｗおよび
【０１４８】
【数６１】
が与えられたとき、あるＹ≧Ｙ'なるベクトルＹとベクトルＹ'に対して、
【０１４９】
【数６２】
を満たす。ただし、Ｙ≧Ｙ'は各ベクトルの成分ＹｊおよびＹｊ'に対して、
【０１５０】
【数６３】
が成り立つこと意味する。式（１８）より、
【０１５１】
【数６４】
は非負の増加関数となっている。以上より、
【０１５２】
【数６５】
が成立する。
【０１５３】
さらに、非負の増加関数の積は非負の増加関数となるので
【０１５４】
【数６６】
とすると、ベクトルＹが正の関連をもつため、
【０１５５】
【数６７】
が成立する。この式の右辺に式（２０）を代入し、式（１９）を適用すると、
【０１５６】
【数６８】
を得る。よって、数学的帰納法により
【０１５７】
【数６９】
を得る。
【０１５８】
式（２１）の左辺はＷｊ＝Ｙｊ＋Ｙｊ＋１＋...＋Ｙｊ＋ｈｍ−１と式（１５）を用いると、
【０１５９】
【数７０】
となる。同様に式（２１）の右辺は、式（１６）を用いると、
【０１６０】
【数７１】
となる。式（２３）と式（２４）を式（２１）に代入することにより、
【０１６１】
【数７２】
の下界を得る。
【０１６２】
【数７３】
閾値フローの分布による検出確率の変化
上記の式（１７）と式（２５）より、閾値フローの検出確率
【０１６３】
【数７４】
が次のように上下界値で押さえられることがわかった。
【０１６４】
【数７５】
しかし、上界値および下界値はｋやｍが大きい場合、あるいはｐ（ｗ｜ｚ＊）が小さな値をとる場合等は両者の差が大きくなり、上下界値を用いて検出確率を推定することは困難になる。
【０１６５】
そこで、閾値フローの母集団におけるパケット数の分布
【０１６６】
【数７６】
に注目する。閾値フローの中でも検出確率が最低になるようなパケット数の分布がわかれば、その分布を基に全ての検出対象フローを検出できるようなパケット数の閾値ｗ＊を決定することができる。ここで、閾値フローのパケット数の分布は一つ目の検査ウィンドウ分の分布が決まると周期性から全ての分布が決定することに注意する。
【０１６７】
複数の条件下での数値計算の結果、ｈ＝１の場合は、一つ目の検査ウィンドウにおいてｚ＊個のパケットをまず
【０１６８】
【数７７】
個ずつ均等にベーシックウィンドウに配置し、余剰が出た場合はそのパケットを検査ウィンドウの中央のベーシックウィンドウから一つずつ前後のベーシックウィンドウに外側に向けて交互に配置したときに、検出確率が最低となることが分かった。このときウィンドウ全体の対称性から、前後のウィンドウのどちらに先に配置するかは問題とならない。反対に、検査ウィンドウ内の一つのベーシックウィンドウにｚ＊個のパケットを全て配置した場合には最も検出確率は高く、その検出確率は上界値と等しくなるため、パケットを均等に配置するときに検出確率が最低になることは直感的な理解とも一致する。
【０１６９】
しかし、ｈ≧２の場合は、一つ目の検査ウィンドウを用いて配置されたベーシックウィンドウ毎のパケット数の、スライディングウィンドウ全体において配置される回数が異なってくるため、ｈ＝１と同じ議論は適用できず、検出確率が最低となる分布は見出すことができない。以降、ｈ≧２の場合は検出確率が最低となる分布が見出されているものと仮定して説明する。
【０１７０】
検出確率が最低となる閾値フローの分布をＸ＊とおく。このとき、先の上下界値を含め、次の式が成り立っていることに注意する。
【０１７１】
【数７８】
分布Ｘ＊が得られた後、検出対象のフローを１−ε以上の確率で検出するためにサンプルにおけるパケット数の閾値ｗ＊を次のように設定する。
【０１７２】
【数７９】
なお、Ｐ（ｗ｜Ｘ＊）はモンテカルロシミュレーションを用いた数値実験によって求める。
【０１７３】
以上で制御パラメータの設定は完了し、上記の「検出の枠組み」で説明した検出手法で用いるパラメータは全て決定した。
【０１７４】
多段階閾値の導入
上記のように、本実施例の検出手法を用いるためのパラメータの決定は完了した。しかし、実験結果が全ての検査ウィンドウでｗ＊以上サンプリングされたかどうかの２通りでの評価では、閾値よりもかなり大きいパケットレートの検出対象フローも、たまたま誤検出された検出対象外フローも全く区別がつかない。そこで、検出されたパケット数の情報をより有効活用することを考え、閾値ｗ＊以外の複数の基準値ω（φ）（ω（φ）＞ｗ＊）を設ける。そして、検出されたフローの中で、全ての検査ウィンドウにおいてω（φ）個以上のパケットがサンプリングされているフローは区別することにする。ここで基準値ω（φ）は次のようにして定める。
【０１７５】
【数８０】
ただし、φは１−ε未満の値を用いる。この基準値の定め方には、パケットレートが閾値フローから僅かに低いだけの検出対象外のフローを誤って検出してしまう確率をφ以下にするという意図がある。複数のφに対するω（φ）を求め、検出されたフローの中でのフローの差別化を図る。
【０１７６】
＜性能評価＞
次に、実際にネットワークで測定された２種類の異なるトレースデータに対して適当な規定パラメータの下でシミュレーション実験を行い、本実施例の検出手法の性能評価を行う。まず実験に用いるトレースデータについて述べる。続いて性能を評価するための指標について述べ、最後に実験の結果を示し、その考察を行う。
【０１７７】
性能評価を行うトレースデータとして、ＣＡＩＤＡによって２００８年２月２０日の８：００から９：００の間に測定されたバックスキャッタのトラヒックを含むＢａｃｋｓｃａｔｔｅｒトレースデータと、ＮＬＡＮＲのＰａｓｓｉｖｅ Ｍｅａｓｕｒｅｍｅｎｔ ａｎｄ Ａｎａｌｙｓｉｓ （ＰＭＡ） Ｐｒｏｊｅｃｔによって２００４年２月１９日の１０：００から１０：０５の間にバックボーンネットワークで測定され、現在はＣＡＩＤＡによって管理されているＣＥＳＣＡ−Ｉトレースデータを用いた。図１０にトレースデータの概要を示す。
【０１７８】
性能評価指標
本実施例の検出手法の性能を評価するため、検出率、誤検出率、最低誤検出パケット数の三つの指標について検証する。ここで次のような二つの指示関数を用意する。
【０１７９】
【数８１】
ここで、ｉはスライディングウィンドウの解析回数のカウンタ値を、ｆｌｏｗ＿ｉｄはフローの識別子をそれぞれ表す。ａ（ｉ，ｆｌｏｗ＿ｉｄ）＝１は母集団において、ｉ回目の解析時点でのｆｌｏｗ＿ｉｄのフローが、全ての検査ウィンドウで
【０１８０】
【数８２】
個以上パケットが存在する検出対象のフローであることを意味し、ｂ（ｉ，ｆｌｏｗ＿ｉｄ）＝１はサンプリング実験において、ｉ回目の解析時点でのｆｌｏｗ＿ｉｄのフローが、全ての検査ウィンドウでｗ＊個以上パケットがサンプリングされ、検出されたフローであることを意味する。
【０１８１】
トレースデータの観測時間をＴＭ［ｓｅｃ］とおくと、ｉのとる値は、ｉ＝１，２，...，ｉｍａｘとなる。ただし、
【０１８２】
【数８３】
である。また、ｉ回目の解析時点における全てのｆｌｏｗ＿ｉｄの集合を
【０１８３】
【数８４】
とする。トラヒックに含まれるフローの集合は解析を行う度に異なるため、ｉの関数になっていることに注意する。
【０１８４】
このとき、検出率を次式で定義する。
【０１８５】
【数８５】
ａ（ｉ，ｆｌｏｗ＿ｉｄ）＝１となるｉとｆｌｏｗ＿ｉｄの組み合わせを検出対象点としたとき、式（２６）は全ての検出対象点のうち本実施例の検出手法により検出できた点の割合を表す。
【０１８６】
一方、誤検出率は次式で定義される。
【０１８７】
【数８６】
ａ（ｉ，ｆｌｏｗ＿ｉｄ）＝０となるｉとｆｌｏｗ＿ｉｄの組み合わせを、検出対象外点としたとき、式（２７）は全ての検出対象外点のうち本実施例の検出手法により誤検出された点の割合を表す。
【０１８８】
最後に、最低誤検出パケット数については、誤検出された全てのフローの母集団における検査ウィンドウ内のパケット数を全て調査し、それらの中で最少パケット数で構成される検査ウィンドウを特定し、そのパケット数を評価する。
【０１８９】
実験結果
予め与えられるパラメータである、Ｒ［ｐａｃｋｅｔｓ／ｓｅｃ］、ＴＳＷ［ｓｅｃ］、ｋ、ｈ、ＴＤ＿ｍａｘ［ｓｅｃ］、ＴＢＷ＿ｍａｘ｝［ｓｅｃ］、Δ１［ｓｅｃ］、Δ２［ｓｅｃ］、Ｃｍａｘ［ｐａｃｋｅｔｓ／ｓｅｃ］、εはそれぞれ図１１のように与えた。また、実験ではフローを、Ｂａｃｋｓｃａｔｔｅｒトレースデータに対しては送信元ＩＰアドレスが共通のパケット群と定義し、ＣＥＳＣＡ−Ｉトレースデータに対しては送信元ＩＰアドレスが共通のパケット群と宛先ＩＰアドレスが共通のパケット群の２種類で定義した。これは、Ｂａｃｋｓｃａｔｔｅｒトレースデータには、ＤｏＳ攻撃を受けたサーバから偽装された様々な宛先へ送られるトラヒックが含まれていることが分かっているため、そのトラヒックを検出することを目的としている。一方、ＣＥＳＣＡ−Ｉトレースデータには異常フローは含まれていないように思われる。そのため２種類の定義により純粋に高パケットレートフローの検出を試みた。
【０１９０】
図１１のパラメータを基に、上記の「制御パラメータと制約条件」で説明した制御パラメータ設定法を用いた。まず、上記の「誤検出確率の最小化問題」を解き、サンプリングレートｆとベーシックウィンドウの大きさを定めるｍが図１２のように得られた。
【０１９１】
図１１のパラメータ群と図１２のｆおよびｍを用いて、上記の「サンプルにおける閾値の導出」の手法を用いたモンテカルロシミュレーションによる数値実験により、検査ウィンドウにおけるパケット数の閾値ｗ＊を決定した。なお数値実験では、各ベーシックウィンドウにパケットを均等に配置した閾値フローを母集団とし、複数の閾値の候補ｗに対して１０６回のサンプリング実験を行い、検出された回数を１０６で割ることによって得られた検出率が１−ε以上となるｗの中で最大のものをｗ＊として採用した。Ｂａｃｋｓｃａｔｔｅｒトレースデータに対する数値実験の結果を図１３に、Ｒ＝８００のときのＣＥＳＣＡ−Ｉトレースデータに対する数値実験の結果を図１４に、Ｒ＝１０００のときのＣＥＳＣＡ−Ｉトレースデータに対する数値実験の結果を図１５にそれぞれ示した。それぞれのグラフから、閾値フローの検出率が下界値と上界値でそれぞれ押さえられていることもわかる。また、数値計算によって求まる下界値と上界値を参考にすることによって、数値実験で試行するｗの範囲を絞ることができる。さらに、ｗ＊と同様に数値実験においてω（φ）の値を、φ＝０．５，１０−１，１０−２，１０−３，１０−４，１０−５，１０−６について求めた結果をｗ＊と共に図１６に示す。
【０１９２】
以上の手順により得られた制御パラメータと予め与えられるパラメータ群を用いてサンプリング実験を行った。ここで検出対象のフローは、サンプリングレートをｆ＝１、サンプルにおけるパケット数の閾値を
【０１９３】
【数８７】
とし、その他のパラメータは実験に用いたものと同じとした場合の検出結果を用いた。
【０１９４】
１００回のサンプリング実験における、三つの評価指標の平均値を９５％信頼区間と共に図１７に示す。図１７より、検出対象はいずれの場合においても１−ε以上の割合で検出されていることがわかる。また、検出対象外フローのうち誤検出されたフローの割合も十分小さく抑えられている。さらに、誤検出されたフローの中で検査ウィンドウに含まれるパケット数が最少のものでも検出対象の半分程度であるため、本実施例の検出手法が誤検出するフローのパケットレートの範囲はそれほど広くないことがわかる。
【０１９５】
＜実施例の効果＞
以上説明したように、本発明の実施例によれば、長さＴ秒の測定期間に含まれる長さｔ秒の任意の部分区間において、パケットレートがＲ［ｐａｃｋｅｔｓ／ｓｅｃ］以上のフローを、ランダムパケットサンプリングによって得られた情報からオンラインで検出できる。
【０１９６】
説明の便宜上、本発明の実施例に係る高パケットレートフロー検出装置は機能的なブロック図を用いて説明しているが、本発明の高パケットレートフロー検出装置は、ハードウェア、ソフトウェア又はそれらの組み合わせで実現されてもよい。例えば、高パケットレートフロー検出装置の各機能部がソフトウェアで実現され、コンピュータ内に実現されてもよい。また、２以上の実施例及び実施例の各構成要素が必要に応じて組み合わせて使用されてもよい。
【０１９７】
以上、本発明の実施例について説明したが、本発明は、上記の実施例に限定されることなく、特許請求の範囲内において、種々の変更・応用が可能である。
【符号の説明】
【０１９８】
１０１ パラメータｆとｍの設計部
１０２ パラメータｗ＊の設計部
１０３ パケット無作為抽出部
１０４ ＢＷ情報保存部
１０５ ＩＷ情報の更新部
１０６ ＩＷ情報保存部
１０７ 高パケットレートフロー検出部
【特許請求の範囲】
【請求項１】
パケットレートが所定値以上のトラヒックのフローを検出する高パケットレートフロー検出装置であって、
パケットを無作為に抽出するパケット無作為抽出部と、
所定の測定期間を部分区間に分割し、部分区間内に抽出されたパケット数をフロー毎に集計するパケット数測定部と、
部分区間においてパケット数が閾値以上のフローを、パケットレートが所定値以上のトラヒックフローであるとして検出する高パケットレートフロー検出部と、
を有する高パケットレートフロー検出装置。
【請求項２】
前記パケット数測定部は、前記所定の測定期間ＴＳＷのスライディングウィンドウを自然数ｋ及びｍを用いてｋｍ個のベーシックウィンドウに分割し、更にｈ≦ｋ且つｋとは互いに素な自然数ｈを用いて、連続するｈｍ個のベーシックウィンドウで構成される検査ウィンドウをスライディングウィンドウ内に（ｋ−ｈ）ｍ＋１個作成し、検査ウィンドウ内に抽出されたパケット数をフロー毎に集計する、請求項１に記載の高パケットレートフロー検出装置。
【請求項３】
前記高パケットレートフロー検出部は、スライディングウィンドウ内の全ての検査ウィンドウにおいてパケット数が閾値ｗ＊以上のフローを検出する、請求項２に記載の高パケットレートフロー検出装置。
【請求項４】
前記高パケットレートフロー検出部は、閾値ｗ＊より大きい複数の基準値ω（φ）を設け、検出されたフローから、全ての検査ウィンドウにおいてパケット数がω（φ）以上のフローを区別する、請求項３に記載の高パケットレートフロー検出装置。
【請求項５】
測定対象の回線のパケットを抽出するサンプリングレートをｆとし、
スライディングウィンドウの大きさをＴＳＷとし、
ベーシックウィンドウの大きさをＴＢＷとし、
検出目標時間をＴＤ＿ｍａｘとし、
測定対象の回線の最大パケットレートをＣｍａｘとし、
１サンプルパケットあたりの処理時間をΔ１とし、
スライディングウィンドウの解析に必要なパケット数とは独立な処理時間をΔ２とし、
ベーシックウィンドウの幅の最大許容値をＴＢＷ＿ｍａｘとし、
スライディングウィンドウの処理時間をτ＝ｆＣｍａｘＴＢＷΔ１＋Δ２としたときに、
ＴＳＷ＋ＴＢＷ＋τ≦ＴＤ＿ｍａｘ且つＴＢＷ≦ＴＢＷ＿ｍａｘを制約条件として、検出対象外のフローの誤検出率を最小化するｆとｍとを設計する第１のパラメータ設計部を更に有する、請求項２乃至４のうちいずれか１項に記載の高パケットレートフロー検出装置。
【請求項６】
パケットレートが所定値以上のトラヒックのフローを見逃す許容誤差をεとしたときに、
設計されたｆとｍとに基づいて、検出対象のフローの検出を見逃す確立をε以下に抑えるよう、検査ウィンドウにおけるパケット数の閾値ｗ＊を設計する第２のパラメータ設計部を更に有する、請求項５に記載の高パケットレートフロー検出装置。
【請求項７】
パケットレートが所定値以上のトラヒックのフローを検出する高パケットレートフロー検出装置における高パケットレートフロー検出方法であって、
パケットを無作為に抽出するステップと、
所定の測定期間を部分区間に分割し、部分区間内に抽出されたパケット数をフロー毎に集計するステップと、
部分区間においてパケット数が閾値以上のフローを、パケットレートが所定値以上のトラヒックフローであるとして検出するステップと、
を有する高パケットレートフロー検出方法。
【請求項１】
パケットレートが所定値以上のトラヒックのフローを検出する高パケットレートフロー検出装置であって、
パケットを無作為に抽出するパケット無作為抽出部と、
所定の測定期間を部分区間に分割し、部分区間内に抽出されたパケット数をフロー毎に集計するパケット数測定部と、
部分区間においてパケット数が閾値以上のフローを、パケットレートが所定値以上のトラヒックフローであるとして検出する高パケットレートフロー検出部と、
を有する高パケットレートフロー検出装置。
【請求項２】
前記パケット数測定部は、前記所定の測定期間ＴＳＷのスライディングウィンドウを自然数ｋ及びｍを用いてｋｍ個のベーシックウィンドウに分割し、更にｈ≦ｋ且つｋとは互いに素な自然数ｈを用いて、連続するｈｍ個のベーシックウィンドウで構成される検査ウィンドウをスライディングウィンドウ内に（ｋ−ｈ）ｍ＋１個作成し、検査ウィンドウ内に抽出されたパケット数をフロー毎に集計する、請求項１に記載の高パケットレートフロー検出装置。
【請求項３】
前記高パケットレートフロー検出部は、スライディングウィンドウ内の全ての検査ウィンドウにおいてパケット数が閾値ｗ＊以上のフローを検出する、請求項２に記載の高パケットレートフロー検出装置。
【請求項４】
前記高パケットレートフロー検出部は、閾値ｗ＊より大きい複数の基準値ω（φ）を設け、検出されたフローから、全ての検査ウィンドウにおいてパケット数がω（φ）以上のフローを区別する、請求項３に記載の高パケットレートフロー検出装置。
【請求項５】
測定対象の回線のパケットを抽出するサンプリングレートをｆとし、
スライディングウィンドウの大きさをＴＳＷとし、
ベーシックウィンドウの大きさをＴＢＷとし、
検出目標時間をＴＤ＿ｍａｘとし、
測定対象の回線の最大パケットレートをＣｍａｘとし、
１サンプルパケットあたりの処理時間をΔ１とし、
スライディングウィンドウの解析に必要なパケット数とは独立な処理時間をΔ２とし、
ベーシックウィンドウの幅の最大許容値をＴＢＷ＿ｍａｘとし、
スライディングウィンドウの処理時間をτ＝ｆＣｍａｘＴＢＷΔ１＋Δ２としたときに、
ＴＳＷ＋ＴＢＷ＋τ≦ＴＤ＿ｍａｘ且つＴＢＷ≦ＴＢＷ＿ｍａｘを制約条件として、検出対象外のフローの誤検出率を最小化するｆとｍとを設計する第１のパラメータ設計部を更に有する、請求項２乃至４のうちいずれか１項に記載の高パケットレートフロー検出装置。
【請求項６】
パケットレートが所定値以上のトラヒックのフローを見逃す許容誤差をεとしたときに、
設計されたｆとｍとに基づいて、検出対象のフローの検出を見逃す確立をε以下に抑えるよう、検査ウィンドウにおけるパケット数の閾値ｗ＊を設計する第２のパラメータ設計部を更に有する、請求項５に記載の高パケットレートフロー検出装置。
【請求項７】
パケットレートが所定値以上のトラヒックのフローを検出する高パケットレートフロー検出装置における高パケットレートフロー検出方法であって、
パケットを無作為に抽出するステップと、
所定の測定期間を部分区間に分割し、部分区間内に抽出されたパケット数をフロー毎に集計するステップと、
部分区間においてパケット数が閾値以上のフローを、パケットレートが所定値以上のトラヒックフローであるとして検出するステップと、
を有する高パケットレートフロー検出方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２０１２−２３６２９（Ｐ２０１２−２３６２９Ａ）
【公開日】平成２４年２月２日（２０１２．２．２）
【国際特許分類】
【出願番号】特願２０１０−１６０９２４（Ｐ２０１０−１６０９２４）
【出願日】平成２２年７月１５日（２０１０．７．１５）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（５０４１７６９１１）国立大学法人大阪大学 (1,536)
【Ｆターム（参考）】
【公開日】平成２４年２月２日（２０１２．２．２）
【国際特許分類】
【出願日】平成２２年７月１５日（２０１０．７．１５）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（５０４１７６９１１）国立大学法人大阪大学 (1,536)
【Ｆターム（参考）】
[ Back to top ]