(57)【要約】  受信されたデータパケットをフィルタにかける方法および手段が開示される。階層ツリーが維持される。このツリーは、複数のレベルに編成されたノードを含んでいる。ツリーのルートノードの上の各レベルは、１つまたは複数のノードを有し、この１つまたは複数のノードのそれぞれが、インターネットプロトコル（ＩＰ）アドレスのセグメントの特定の値に対応している。セグメントは、ツリーの特定のレベルの各ノードで同じものである。ツリーの特定のレベルの各ノードは、この特定のレベルと関連するＩＰアドレスのセグメントに同じ値を有する受信されたパケットの数を表す数字を格納する。受信されたデータパケットの一部が、階層ツリーに基づいてフィルタにかけられて除去される。
2010520664.tif 000002
【特許請求の範囲】
【請求項１】
あるネットワークアドレスで受信されたデータパケットをフィルタにかけて除去する方法であって、
複数のレベルに編成された複数のノードを含む階層ツリーを維持することであって、ツリーのルートノードの上の各レベルが１つまたは複数のノードを有し、１つまたは複数のノードのそれぞれがインターネットプロトコル（ＩＰ）アドレスのセグメントの特定の値に対応し、セグメントがツリーの特定のレベルの各ノードで同じものであり、ツリーの特定のレベルにある個々の各ノードが、前記特定のレベルと関連する前記ＩＰアドレスのセグメントに同じ値を有する受信されたパケットの数を表す数字を格納することと、
受信されたデータパケットの一部を前記階層ツリーに基づいてフィルタにかけて除去することと
を含む、方法。
【請求項２】
受信されたデータパケットの一部をフィルタにかけて除去することが、発信元のＩＰアドレスの１つのセグメントに特定の値を有する受信されたデータパケットを、その１つのセグメントの特定の値に対応するノードが子ノードしきい値より大きい数の子ノードを有することに応じてフィルタにかけて除去することである、請求項１に記載の方法。
【請求項３】
前記階層ツリーを前記維持することがさらに、
（ａ）発信元のＩＰアドレスの第１のセグメントに第１の値および前記発信元のＩＰアドレスの第２のセグメントに第２の値を含む受信されたデータパケットについて、カレントレベルに位置づけられるカレントレベルのノードを判断することであって、前記カレントレベルのノードが、前記発信元のＩＰアドレスの前記第１のセグメントに前記第１の値を有する前記受信されたデータパケットの数を表す数字を格納する、判断することと、
（ｂ）前記格納された数字が前記カレントレベルのノードのオーバーフローしきい値より小さい場合は前記格納された数字をインクリメントすることと、
（ｃ）格納された数字が前記カレントレベルのノードの前記オーバーフローしきい値より大きい場合はツリーの次のレベルで前記カレントレベルのノードの子ノードを作成することであって、前記子ノードが、前記発信元のＩＰアドレスの前記第１のセグメントについては前記第１の値に、かつ前記第２のセグメントについては前記第２の値に対応する、作成することと
を含む、請求項１に記載の方法。
【請求項４】
（ｄ）前記カレントレベルのノードの作成された子ノードの数が子ノードしきい値より大きくなるまでステップ（ａ）から（ｃ）を繰り返すこと
をさらに含む、請求項３に記載の方法。
【請求項５】
前記フィルタにかけて除去することが、前記カレントレベルのノードの作成された子ノードの前記数が前記子ノードしきい値より大きいとき、前記受信されたデータパケットをフィルタにかけて除去することをさらに含む、請求項４に記載の方法。
【請求項６】
前記ＩＰアドレスのセグメントに前記同じ値を有する受信されたパケットの前記数をデクリメントするために、前記複数のノードの中の各ノードの格納された数字が、リークパラメータによって判断されたレートによりデクリメントされる、請求項１に記載の方法。
【請求項７】
あるネットワークアドレスで受信されたデータパケットをフィルタにかけて除去する装置であって、
複数のレベルに編成された複数のノードを含む階層ツリーを維持する手段であって、ツリーのルートノードの上の各レベルが１つまたは複数のノードを有し、１つまたは複数のノードのそれぞれがインターネットプロトコル（ＩＰ）アドレスのセグメントの特定の値に対応し、セグメントがツリーの特定のレベルの各ノードで同じものであり、ツリーの特定のレベルにある個々の各ノードが、前記特定のレベルと関連する前記ＩＰアドレスのセグメントに同じ値を有する受信されたパケットの数を表す数字を格納する、維持する手段と、
受信されたデータパケットの一部を前記階層ツリーに基づいてフィルタにかけて除去する手段と
を備える、装置。
【請求項８】
受信されたデータパケットの一部をフィルタにかけて除去する手段が、発信元のＩＰアドレスの１つのセグメントに特定の値を有する受信されたデータパケットを、その１つのセグメントの特定の値に対応するノードが子ノードしきい値より大きい数の子ノードを有することに応じてフィルタにかけて除去する手段である、請求項７に記載の装置。
【請求項９】
前記階層ツリーを維持する前記手段がさらに、
（ａ）発信元のＩＰアドレスの第１のセグメントに第１の値を含みかつ前記発信元のＩＰアドレスの第２のセグメントに第２の値を含む受信されたデータパケットについて、カレントレベルに位置づけられたカレントレベルのノードを判断する手段であって、前記カレントレベルのノードが、前記発信元のＩＰアドレスの前記第１のセグメントに前記第１の値を有する前記受信されたデータパケットの数を表す数字を格納する、判断する手段と、
（ｂ）前記格納された数字が前記カレントレベルのノードについてのオーバーフローしきい値より小さい場合、前記格納された数字をインクリメントする手段と、
（ｃ）格納された数字が前記カレントレベルのノードについての前記オーバーフローしきい値より大きい場合、ツリーの次のレベルで前記カレントレベルのノードの子ノードを作成する手段であって、前記子ノードが前記発信元のＩＰアドレスの前記第１のセグメントについては前記第１の値に、かつ前記第２のセグメントについては前記第２の値に対応する、作成する手段と
を備える、請求項７に記載の装置。
【請求項１０】
（ｄ）前記カレントレベルのノードの作成された子ノードの数が子ノードしきい値より大きくなるまでステップ（ａ）から（ｃ）を繰り返す手段
をさらに備える、請求項９に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概してネットワークセキュリティに関し、より詳細にはサービス妨害（Ｄｅｎｉａｌ  ｏｆ  Ｓｅｒｖｉｃｅ、ＤＤｏＳ）攻撃に関する。
【背景技術】
【０００２】
ＤＤｏＳ攻撃中には、障害が起きたいくつかのコンピュータが、受信コンピュータシステム（例えばウェブサーバ、ネットワークリンク、ルータなど）に不要な大量のトラフィック（すなわちデータパケット）を送信することが多い。この不要なトラフィックは一般に受信コンピュータのリソースを使い果たし、受信コンピュータが正規のクライアントにサービスすることを妨害する。
【０００３】
ＤＤｏＳ攻撃を防ぐために、受信コンピュータは一般に望ましくないトラフィックと正規のトラフィックとを見分けなければならない。望ましくないトラフィックが識別されると受信コンピュータは、望ましくないトラフィックが受信コンピュータのリソースを過負荷状態にしないように、望ましくないトラフィックをフィルタにかける（ブロックする）ことができる。
【０００４】
不要なトラフィックは、障害が起きた多くのコンピュータによって送信されていることが多いので、受信コンピュータが望ましくないトラフィックを正規のトラフィックと区別する（およびフィルタにかける）ことは困難であることが多い。一般に受信コンピュータは、受信された各パケットが望ましくないトラフィックの一部であるか、または正規のトラフィックであるかを判断しなければならない。通常この分析には、受信された各パケットの発信元のインターネットプロトコル（ＩＰ）アドレスをコンピュータが調べる必要がある。
【０００５】
すべてのパケットは、発信元のインターネットプロトコル（ＩＰ）アドレスを有する。ＩＰアドレスは一般にａ．ｂ．ｃ．ｄ．の形をしており、ここでａ、ｂ、ｃ、およびｄは０−２５５の範囲の整数である。
【０００６】
ＤＤｏＳ攻撃を阻止するために使用される１つのフィルタリング技術は、受信コンピュータがネットワークに組み込まれる前にどのトラフィックをフィルタにかけるかを判断することである（すなわち静的フィルタリング）。例えば、ある障害が起きたコンピュータがＤＤｏＳ攻撃に加わることがわかっている場合、受信コンピュータはこの障害が起きたコンピュータから受信されるすべてのパケットをフィルタにかける（例えばブロックする）ように構成されることが可能である。
【０００７】
一般に静的フィルタリングでは、受信コンピュータが各パケットの完全なＩＰアドレスを調べ、このＩＰアドレスをＤＤｏＳ攻撃に加わることが疑われるＩＰアドレスのリストにあるＩＰアドレスと比較する必要がある。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
分散型のサービス妨害攻撃を阻止するためにパケットをより効率的にかつ効果的にフィルタにかける技術の必要性が依然としてある。
【課題を解決するための手段】
【０００９】
本発明の一実施形態に従って、受信コンピュータは、受信されたパケットのＩＰアドレスの１つもしくは複数の部分またはセグメントを調べ、受信されたパケットを動的にフィルタにかけて、ＤＤｏＳ攻撃が成功する可能性を小さくする。
【００１０】
本発明の一実施形態に従って、複数のレベルに編成された複数のノードを有する階層ツリーが維持される。ツリーのルートノードの上の各レベルは、１つまたは複数のノードを有し、この１つまたは複数のノードのそれぞれがインターネットプロトコル（ＩＰ）アドレスのセグメントの特定の値に対応している。セグメントは、ツリーの特定のレベルの各ノードで同じものである。ツリーの特定のレベルの各ノードは、この特定のレベルと関連するＩＰアドレスのセグメントに同じ値を有する受信されたパケットの数を表す数字を格納する。受信されたデータパケットの一部が、階層ツリーに基づいてフィルタにかけられて除去される。
【００１１】
一実施形態では、発信元のＩＰアドレスの１つのセグメントに特定の値を有する受信されたデータパケットは、その１つのセグメントの特定の値に対応するノードが子ノードしきい値より大きい数の子ノードを有するときフィルタにかけられる。
【００１２】
１つのセグメントの特定の値に対応するノードの子ノードは、特定のノードに格納されている数字がオーバーフローしきい値（例えばノード、ツリーなどと関連する）より大きいことに応じて生成される。
【００１３】
１つの特定の実施形態では、階層ツリーを維持することは、ＩＰアドレスの第１のセグメントに第１の値、ＩＰアドレスの第２のセグメントに第２の値を有するパケットを受信した後にいくつかのステップを行うことを含む。このステップは、このパケットについてカレントレベルにあるカレントレベルのノードを判断することを含む。カレントレベルのノードは、ＩＰアドレスの第１のセグメントに第１の値を有する受信されたパケットの数を表す数字を格納する。このステップは、格納された数字（オーバーフローカウンタ）が（例えばカレントレベルのノードについての）オーバーフローしきい値より小さい場合、格納された数字（すなわちカレントレベルのノードと関連するオーバーフローカウンタ）をインクリメントすることを含む。次に、ツリーの次のレベルにあるカレントレベルのノードの子ノードについて、格納された数字がカレントレベルのノードのオーバーフローしきい値より大きいかどうか判断される。この子ノードは、ＩＰアドレスの第１のセグメントに第１の値、ＩＰアドレスの第２のセグメントに第２の値を有する受信されたパケットの数を表示する。このステップは、子ノードを作成するステップを行った後にカレントレベルのノードの子ノードの数をインクリメントすることを含む。いくつかの実施形態では、カレントレベルのノードの子ノードの数が子ノードしきい値より大きくなるまで上記ステップが繰り返されることが可能である。
【００１４】
この方法の１つの特定の実施形態では、諸ステップは、カレントレベルのノードの子ノードの数が子ノードしきい値より大きいとき、受信されたパケット（例えばブロックされたパケット）をフィルタにかけることを含む。さらに各ノードはリークパラメータを有することができ、この方法でこれを使用してノードと関連するオーバーフローカウンタを（例えば所定のレートで）デクリメントすることができる。さらに諸ステップは、例えば攻撃のない時間の間はシステムの正常な使用についての統計を用いて、子ノードしきい値およびオーバーフローしきい値を個別に調整することを含むことができる。
【００１５】
本発明のこれらの利点および他の利点は、次の詳細な説明および添付の図面の参照により、当業者には明らかとなるであろう。
【図面の簡単な説明】
【００１６】
【図１】ネットワークを通じて分散型サービス妨害攻撃を受けている第１のコンピュータの例示的なブロック図である。
【図２】一実施形態に従ってパケットをフィルタにかけるためにコンピュータによって行われる諸ステップを示すフローチャートである。
【図３】例えば図２の実施形態のような一実施形態に従ったツリーデータ構造のブロック図である。
【図４】一実施形態に従ったコンピュータのハイレベルブロック図である。
【発明を実施するための形態】
【００１７】
図１は、ネットワーク１０６を通じて分散型サービス妨害攻撃（ＤＤｏＳ）を受けている第１のコンピュータ１０４（例えばウェブサーバ、ルータなど）の例示的なブロック図である。ＤＤｏＳ攻撃中には、第２のコンピュータ１０８、第３のコンピュータ１１２、および第４のコンピュータ１１６のようないくつかの障害が起きたコンピュータが、第１のコンピュータ１０４に不要なトラフィック（すなわちデータパケット）１２０を送信する。この不要なトラフィック１２０は一般に非常に高レートであり、第１のコンピュータのリソースを使い果たして、第１のコンピュータ１０４がその正規のクライアントにサービスできないようにする。このために、ＤＤｏＳ攻撃は第１のコンピュータ１０４をクラッシュさせる可能性がある。
【００１８】
一般にＤＤｏＳ攻撃を防ぐために第１のコンピュータ１０４は、望ましくないトラフィック１２０と、第５のコンピュータ１２８からの正規のトラフィック１２４のような正規のトラフィックとを見分けなければならない。第１のコンピュータ１０４が望ましくないトラフィック１２０を識別すると、第１のコンピュータは、このトラフィックが第１のコンピュータ１０４のリソースを過負荷状態にしないように、望ましくないトラフィック１２０をフィルタにかける（例えばブロックする）ことができる。
【００１９】
ＤＤｏＳ攻撃の際に不要なトラフィック１２０は多くのコンピュータによって送信されているので、望ましくないトラフィック１２０を正規のトラフィック１２４から識別する（およびフィルタにかける）ことは困難である場合がある。一般に第１のコンピュータ１０４は、受信された各パケットが望ましくないトラフィック１２０の一部であるか、または正規のトラフィック１２４であるかを判断しなければならない。このような分析には、第１のコンピュータ１０４が静的フィルタリングを行い、受信された各パケットの完全なインターネットプロトコル（ＩＰ）アドレスを調べることが必要である可能性がある。
【００２０】
図２は、本発明の実施形態に従ってパケットを動的にフィルタにかけるために、第１のコンピュータ（本明細書ではコンピュータと呼ぶこともある）によって行われるステップを示すフローチャートである。図２のフローチャートについてまずハイレベルで説明し、さらなる詳細は下記で一例を説明するときに示す。
【００２１】
コンピュータはまず、ステップ２０５において階層ツリーデータ構造（本明細書ではツリーと呼ぶ）を初期設定する。ツリーは、複数のレベルに編成された複数のノードを有する。各レベルは、ＩＰアドレスのセグメント（例えばＩＰアドレスの１つのバイト）と関連し、特定のレベルの各ノードは、この特定のレベルと関連するＩＰアドレスのセグメントに同じ値を有する受信されたパケットの数を表す数字を格納する。一実施形態ではツリーはルートノードを有するだけで初期設定され、パケットが受信されると、ルートノードのサブノードがツリーに追加される。
【００２２】
その後コンピュータは、ステップ２１０においてパケットを受信する。パケットは、そのＩＰアドレスの第１のセグメントに第１の値を有し、そのＩＰアドレスの第２のセグメントに第２の値を有する。次にステップ２１５においてこのパケットのカレントレベルのノードが判断される。カレントレベルのノードはカレントレベルにあって、ＩＰアドレスの第１のセグメントに第１の値を有する受信されたパケットの数を表す。カレントレベルのノードは、ＩＰアドレスの第１のセグメントに対応するレベルにあるノードである。
【００２３】
カレントレベルのノードを見つけるために、パケットの完全なＩＰアドレスのセグメントが、ツリーの中のノードに照らして分析される。カレントレベルでセグメントと一致するノードが見つかると、ＩＰアドレスの次のセグメントが分析され、次のセグメントと一致するノードがツリーの次のレベルに配置される。これらのステップは繰り返される。カレントレベルのノードは、したがってツリーの中で最深の一致するノードである。このプロセスは、しばしば最長プレフィックス一致と呼ばれる（最長第１セグメント一致と呼ばれることもある）。結果として、第１のセグメント（したがってカレントレベルのノード）は、実際は静的ではなく、むしろ各パケットに対して変わる可能性がある。第１のセグメントは、ノード（すなわちカレントレベルのノード）に一致する、パケットのＩＰアドレスのセグメントに対応する。
【００２４】
その後ステップ２２０においてカレントレベルのノードがオーバーフロー状態であるかどうかを判断する。この判断は、ＩＰアドレスの第１のセグメントに第１の値を有する受信されたパケットの数をオーバーフローしきい値と比較することによって行われることが可能である。一実施形態ではオーバーフローしきい値は、ノードごとに固有のもの（例えばカレントレベルのノードに対する固有のオーバーフローしきい値）である。代替的には、あるレベルのノード、あるいはツリー全体のノードのすべてに対して１つのオーバーフローしきい値がある。ＩＰアドレスの第１のセグメントに第１の値を有する受信されたパケットの数が、（例えばカレントレベルのノードについて）オーバーフローしきい値以下である場合、カレントレベルのノードはオーバーフロー状態ではなく、ＩＰアドレスの第１のセグメントに第１の値を有する受信されたパケットの数を表す格納された数字は、ステップ２２５においてインクリメントされる。その後プロセスはステップ２１０に戻って、繰り返す。
【００２５】
格納された数字（ＩＰアドレスの第１のセグメントに第１の値を有する受信されたパケットの数を表す）がオーバーフローしきい値より大きい場合、カレントレベルのノードはオーバーフロー状態であって、ステップ２３０においてこのパケットのためにカレントレベルのノードの子ノードが形成される。この子ノードは、カレントレベルを数値的に上回るレベル（例えば第２のレベルから第３のレベル）にあり（ただし、ツリーの中ではカレントレベルの下のレベルとして図示されることが可能である）、ＩＰアドレスの第１のセグメントに第１の値を有し、例えばＩＰアドレスの互いに素な第２のセグメントなどＩＰアドレスの第２のセグメントに第２の値を有する受信されたパケットの数を表す。
【００２６】
その後、カレントレベルのノードの子ノードの数に対応するカウンタが、ステップ２３５において形成される、またはインクリメントされる。次にコンピュータは、ステップ２４０において、カレントレベルのノードの子ノードの数のカウンタが子ノードしきい値より大きいかどうかを判断する。大きくない場合、プロセスはステップ２１０に戻って、繰り返す。
【００２７】
カレントレベルのノードの子ノードの数が子ノードしきい値より大きい場合、カレントレベルのノードと関連するパケットはステップ２５０においてフィルタにかけられて除去される。したがってコンピュータは、ＩＰアドレスの第１のセグメントに第１の値を有する受信されたデータパケットをフィルタにかけて除去する。その後プロセスは、ステップ２１０に戻る。
【００２８】
上記のように、ＩＰアドレスの各セグメントは、０と２５５の間の整数である。したがって、一実施形態では４つのレベルがあり、各レベルの子ノードの最大数は２５６である。しかしながら、３２のレベルとレベルにつき２つの子ノード、１６のレベルとレベルにつき２５６の子ノード、１２８のレベルとレベルにつき２つの子ノードを有する実施形態などを含む代替的実施形態が存在するが、これらに限定されず、インターネットプロトコルバージョン４およびバージョン６のアドレスの規則の両方を対象とする。
【００２９】
図３は、本発明の一実施形態に従ったツリー３００の一例を示している。コンピュータは、コンピュータが受信するパケットのいくつかがＤＤｏＳ攻撃の一部であるかどうかを判断する必要がある。コンピュータがこのパケットの一部またはすべてがＤＤｏＳ攻撃の一部であると判断する場合、コンピュータはこのパケットをフィルタにかける。コンピュータは、ツリー３００を使用してこの判断を行う。
【００３０】
コンピュータは、次のＩＰアドレスのそれぞれから多くのパケットを受信していると仮定する：
１００．５０．２０７．１２４、
１００．５１．２０７．９１、
１００．５１．２０８．６、
１００．５１．２０９．１２１、
１００．５１．２１０．１４、
１００．５１．２１１．２５１、
１００．５２．０５．４４、
１００．５３．６８．１４８、
２００．１２５．６５．１８８、および
２００．１８８．２５１．１２。
【００３１】
ツリー３００は、ユニバーサルレベルまたはルートレベル３１０を表すルートノード３０５を有する。ルートレベル３１０は、ツリー３００の最上位レベルである。ルートレベル３１０の下位に、（上記のように）形式ａ．ｂ．ｃ．ｄのＩＰアドレスのａセグメントに対応するａレベル３１５がある。例えば、上に示した１００．５２．０５．４４のＩＰアドレスは、ａ．ｂ．ｃ．ｄ．の形式であり、ここで１００＝ａ、５２＝ｂ、０５＝ｃ、４４＝ｄである。一実施形態ではコンピュータは、２つのａレベルのノード、すなわち第１のａレベルのノード３２０および第２のａレベルのノード３２５を作成する。第１のａレベルのノード３２０は、１００というａレベルのアドレスを有する受信されたパケット（例えば１００．５０．２０７．１２４または１００．５２．０５．４４というＩＰアドレスを有するパケット）の数を表す。第２のａレベルのノード３２５は、２００というａレベルのアドレスを有する受信されたパケット（例えば２００．１２５．６５．１８８または２００．１８８．２５１．１２というＩＰアドレスを有するパケット）の数を表す。
【００３２】
一実施形態において図３に示されるツリー３００の各ノードは、数字が中に入った円で表される。この数字は、オーバーフローカウンタを表す。オーバーフローカウンタは、特定のレベルと関連するＩＰアドレスのセグメントに同じ値を有する受信されたデータパケットの数を表す。各ノードまたはレベルは、対応するオーバーフローしきい値を有することもできる。特定のレベルと関連するＩＰアドレスのセグメントに同じ値を有する受信されたデータパケットの数が、オーバーフローしきい値より大きいときは、コンピュータはカレントレベルのノードの子ノードを作成しなければならない。
【００３３】
例えば、２つのａレベルのノード３２０および３２５のそれぞれの中には、数字５がある。これは、各ａレベルのアドレス１００および２００について少なくとも５つのパケットが受信されたことを意味する。ａレベルのアドレス１００または２００のどちらかまたは両方について、オーバーフローしきい値により、５より多くのパケットが受信された可能性がある。例えば、ツリー３００のａレベルのノードのオーバーフローしきい値が４であると仮定する。ａレベルのノード３２０、３２５は共に、ノードの中に５つのパケットを有するので、このａレベルのノード３２０、３２５はオーバーフロー状態であり、そのオーバーフローカウンタはもはやインクリメントされない。その代わりに、１００または２００というａレベルのアドレスを有する受信されたパケットは、ｂレベル３３０のような次のレベルについて分析される。この次のレベル（例えばｂレベル３３０）は、パケットが受信されるときに作成されるか、または前もって（例えばツリーの作成とともに）作成されていることが可能である。したがってコンピュータが１００（または２００）というａレベルのアドレスを有する別のパケットを受信するとき、コンピュータはまずこのａレベルのノード３２０（または３２５）がオーバーフロー状態であると判断する。次いでコンピュータは、このパケットをｂレベル３３０について分析する。
【００３４】
第１のａレベルのノード３２０の下には、４つのｂレベルのノード３３５、３４０、３４５、３５０がある。第１のｂレベルのノード３３５は、５０というｂレベルのアドレス（すなわち１００．５０）を有するパケットに対応し、１というオーバーフローカウンタを有する。第２のｂレベルのノード３４０は、５１というｂレベルのアドレス（すなわち１００．５１）を有するパケットに対応し、４というオーバーフローカウンタを有する。第３のｂレベルのノード３４５は、５２というｂレベルのアドレス（すなわち１００．５２）を有するパケットに対応し、１というオーバーフローカウンタを有する。第４のｂレベルのノード３５０は、５３というｂレベルのアドレス（すなわち１００．５３）を有するパケットに対応し、１というオーバーフローカウンタを有する。
【００３５】
同様に、第２のａレベルのノード３２５の下には、第５のｂレベルのノード３５５がある。第５のｂレベルのノード３５５は、ｂレベルのアドレス１２５（すなわち２００．１２５）に対応し、１というオーバーフローカウンタを有する。
【００３６】
ｂレベル（すなわちｂレベルの各ノード）は３というオーバーフローしきい値を有すると仮定する。したがって１というオーバーフローカウンタを有するｂレベルのノード（例えばノード３３５、３４５、３５０、および３５５）は、現在オーバーフロー状態ではない。結果として、ツリーの次のレベル（ｃレベル３６０）はこれらのノード３３５、３４５、３５０、３５５について分析される必要はない。
【００３７】
しかしながら、第２のｂレベルのノード３４０は、３というオーバーフローしきい値より大きいオーバーフローカウンタを有する。その結果、第２のｂレベルのノード３４０はオーバーフロー状態であり、コンピュータはもはや第２のｂレベルのノードのカウンタをインクリメントしない。その代わりに、第２のｂレベルのノードがオーバーフロー状態であるときに受信されるパケットには、ｃレベルが使用される。
【００３８】
上述のように、コンピュータは、１００というａレベルのアドレスおよび５１というｂレベルのアドレスのもとにある次の５つのパケットを受信すると仮定する：
１００．５１．２０７．９１、
１００．５１．２０８．６、
１００．５１．２０９．１２１、
１００．５１．２１０．１４、および
１００．５１．２１１．２５１。
【００３９】
ｂレベルのノード３４０はオ―バーフロー状態であるため、パケットは次いでｃレベルで分析される。そこで５つのｃレベルのノード、すなわち２０７というｃレベルのアドレスを有するパケットに対応する第１のｃレベルのノード３６５と、２０８というｃレベルのアドレスを有するパケットに対応する第２のｃレベルのノード３７０と、２０９というｃレベルのアドレスを有するパケットに対応する第３のｃレベルのノード３７５と、２１０というｃレベルのアドレスを有するパケットに対応する第４のｃレベルのノード３８０と、２１１というｃレベルのアドレスを有するパケットに対応する第５のｃレベルのノード３８５とが作成される。それぞれが１というオーバーフローカウンタを有し、ｃレベルのオーバーフローしきい値は２であると仮定すると、オーバーフロー状態であるｃレベルのノードはない。したがって受信されたパケットのいずれにも、ｄレベルのノードが作成される必要はない。
【００４０】
一実施形態では、コンピュータが次のレベルのノードを生成するたびに、カレントノード（すなわち親ノード）と関連する子ノードのカウンタがインクリメントされる。例えば、ｃレベルのノード３６５−３８５が生成されるたびに、（ｃレベルのノード３６５−３８５のすべてが第２のｂレベルのノード３４０の子ノードであるので）ｂレベルのノード３４０と関連する子ノードのカウンタがインクリメントされる。
【００４１】
各レベルは、特定の親ノードと関連するパケットがフィルタにかけられる（例えばブロックされる）前に存在していることが可能である子ノードのしきい値数（すなわち子ノードしきい値）を有することができる。例えば、ｃレベルの子ノードしきい値が４であると仮定する。したがって第２のｂレベルのノード３４０はこれと関連する５つの子ノードを有するとコンピュータが判断するとき、コンピュータは、第２のｂレベルのノード３４０のＩＰアドレス要件を満たすすべてのパケット（すなわち１００というａレベルのＩＰアドレスと５１というｂレベルのＩＰアドレスを有するすべてのパケット）をフィルタにかけることを判断することができる。
【００４２】
一実施形態では、各ノード（または各レベルもしくはツリー３００）についてのリークパラメータが維持される。リークパラメータは、リーキーバケットモデルと関連し、ノードと関連するオーバーフローカウンタをデクリメントすることを制御する。リークパラメータは、トラフィックの通常のフローに対応する。リークパラメータは、レートである（例えば５秒ごとに特定ノードのオーバーフローカウンタをデクリメントする）場合がある。（リークパラメータによって制御された）このデクリメントの結果として、ある期間中にはノードはオーバーフロー状態である可能性があり、その後別の期間中には、リーキーバケットモデルによりオーバーフローカウンタを定期的にデクリメントすることによって、ノードはオーバーフロー状態ではない可能性がある。リークパラメータ、ならびにオーバーフローしきい値および／または子ノードしきい値は、不変のものであることが可能であり、あるいは（例えばシステム管理者またはコンピュータのユーザによって）動的に調整されることが可能である。別の実施形態ではオーバーフローしきい値は、ノードからパケットが自然に排出されるように時間とともに調節される（すなわちオーバーフローカウンタは、例えば所与の時間にデクリメントされる）。
【００４３】
少ないコンピューティングコストでリークパラメータを実現させるためには、循環クロック演算（ｃｉｒｃｕｌａｒ  ｃｌｏｃｋ  ａｒｉｔｈｍｅｔｉｃ）が実施されることが可能であると、当業者は理解するであろう。例えば、１つは、［０．．．Ｔ−１］の値をとる２つのカウンタを各ノードに維持し、ここでＴはノードのしきい値であって、１だけインクリメントされたＴ−１は０をもたらす（循環演算（ｃｉｒｃｕｌａｒ  ａｒｉｔｈｍｅｔｉｃｓ））という規則を有する。１つのカウンタ（ＣＡ）は到着したパケットの実数に対応し、もう１つのカウンタ（ＣＮ）は標準的な経路に対応する。カウンタ（ＣＡ）は、実際の到着によりインクリメントされ、カウンタ（ＣＮ）は、標準的な「リーク」レートによりインクリメントされる。２つの考えられる衝突モード（カウンタの値が一致する事象）があり、１つは（ＣＡ）が（ＣＮ）を上回るように試みることであり、この場合しきい値のオーバーフローが宣言され、もう１つは（ＣＮ）が（ＣＡ）を上回るように試みることであり、これはオーバーフローカウントをゼロまでデクリメントすることに対応する。
【００４４】
さらに、ノードは、そのオーバーフローカウンタが上記のようにリークの実施によりゼロ（または何らかの所定の数）までデクリメントすると、ツリーから削除されることが可能である。その結果ツリーは、トラフィックがほとんどない時間の間、ツリーがより小さくなる、またはルートノードだけを有する空のツリーに戻ることができるように、ツリー自体を削減することができる。さらに、サービス妨害攻撃があるときは、あるサブネットからの攻撃が弱まると、そのサブセットと関連するサブツリーが最終的に消滅し、それによってリソースを解放して攻撃されている他のサブネットに対処する。
【００４５】
様々な実施形態において、実行される、パケットをフィルタにかけて除去することは、様々な形式の階層ツリーに基づくことが可能である。例えば、上記の例はＩＰアドレスのサブセットの中のパケットの数に基づいてフィルタにかけられるが、他の実施形態は、ツリー構造を使用してフロー（例えばＴＣＰセッション）をフィルタにかけることができる。
【００４６】
上記の記述は、本発明の諸実施形態を実施する方法について説明している。これらの方法のステップは、適切にプログラムされたデジタルコンピュータまたはデジタルプロセッサによって行われることが可能であり、このようなコンピュータの構成は当業者にはよく知られている。適切なコンピュータは、例えばよく知られているコンピュータプロセッサ、メモリユニット、記憶装置、コンピュータソフトウェア、および他のコンポーネントを使用して、実装されることが可能である。このようなコンピュータのハイレベルブロック図が、図４に示してある。コンピュータ４０２は、コンピュータ４０２の動作全体を、このような動作を定義するコンピュータプログラム命令を実行することによって制御するプロセッサ４０４を含んでいる。コンピュータプログラム命令は、記憶装置４１２（例えば磁気ディスク）の中に格納され、コンピュータプログラム命令の実行が望まれるときにメモリ４１０にロードされることが可能である。詳細には、例えばメモリ、または光もしくは磁気ディスクなどのデータ記憶媒体に格納されたプログラムは、上述の方法のいずれかのステップを実行するための、コンピュータで実行可能な命令を含むことができる。またコンピュータ４０２は、（例えばローカルにまたはネットワークを通じて）他の装置と通信するための１つまたは複数のインターフェース４０６を含むこともできる。またコンピュータ４０２は、ユーザがコンピュータ４０２と対話できるようにするデバイスを表す入出力４０８（例えばディスプレイ、キーボード、マウス、スピーカ、ボタンなど）を含むこともできる。実際のコンピュータの実装は他の構成要素を同様に含むこと、また図４は説明のためにこのようなコンピュータの構成要素のいくつかをハイレベル表示していることを、当業者は理解するであろう。例えばコンピュータ４０２は、上述のコンピュータを表すことができる。さらに、本明細書に記載した処理のステップは、このような処理のステップを特に実装する目的でその回路を構成された専用のハードウェアを使用して実装されることも可能であると当業者は理解するであろう。あるいはこの処理のステップは、ハードウェアおよびソフトウェアの様々な組合せを用いて実装されることも可能である。またこの処理のステップは、コンピュータの中で行われることが可能であり、またはより大きいマシンの一部であることも可能である。
【００４７】
前述の発明を実施するための形態は、あらゆる点で説明的および例示的であり、限定的ではないと理解されなければならず、本明細書に開示される本発明の範囲は、発明を実施するための形態からではなく、特許法によって認められる最大により解釈される特許請求の範囲から決定されなければならない。本明細書で示されて説明された実施形態は、単に本発明の原理を例示するものであり、本発明の範囲および趣旨から逸脱することなく当業者によって様々な変更が行われることが可能であると理解されたい。当業者は、本発明の範囲および趣旨から逸脱することなく様々な他の特徴の組合せを実施することができる。
【図１】
2010520664.tif 000003
【図２】
2010520664.tif 000004
【図３】
2010520664.tif 000005
【図４】
2010520664.tif 000006
【手続補正書】
【提出日】平成20年9月19日(2008.9.19)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
あるネットワークアドレスで受信されたデータパケットをフィルタにかけて除去する方法であって、
複数のレベルに編成された複数のノードを含む階層ツリーを維持することであって、ツリーのルートノードの上の各レベルが１つまたは複数のノードを有し、１つまたは複数のノードのそれぞれがインターネットプロトコル（ＩＰ）アドレスのセグメントの特定の値に対応し、セグメントがツリーの特定のレベルの各ノードで同じものであり、ツリーの特定のレベルにある個々の各ノードが、前記特定のレベルと関連する前記ＩＰアドレスのセグメントに同じ値を有する受信されたパケットの数を表す数字を格納することと、
受信されたデータパケットの一部を前記階層ツリーに基づいてフィルタにかけて除去することとを含み、
前記フィルタにかけて除去することが、発信元のＩＰアドレスの１つのセグメントに特定の値を有する受信されたデータパケットを、その１つのセグメントの特定の値に対応するノードが子ノードしきい値より大きい数の子ノードを有することに応じてフィルタにかけて除去することである、方法。
【請求項２】
前記階層ツリーを前記維持することがさらに、
（ａ）発信元のＩＰアドレスの第１のセグメントに第１の値および前記発信元のＩＰアドレスの第２のセグメントに第２の値を含む受信されたデータパケットについて、カレントレベルに位置づけられるカレントレベルのノードを判断することであって、前記カレントレベルのノードが、前記発信元のＩＰアドレスの前記第１のセグメントに前記第１の値を有する前記受信されたデータパケットの数を表す数字を格納する、判断することと、
（ｂ）前記格納された数字が前記カレントレベルのノードのオーバーフローしきい値より小さい場合は前記格納された数字をインクリメントすることと、
（ｃ）格納された数字が前記カレントレベルのノードの前記オーバーフローしきい値より大きい場合はツリーの次のレベルで前記カレントレベルのノードの子ノードを作成することであって、前記子ノードが、前記発信元のＩＰアドレスの前記第１のセグメントについては前記第１の値に、かつ前記第２のセグメントについては前記第２の値に対応する、作成することと
を含む、請求項１に記載の方法。
【請求項３】
（ｄ）前記カレントレベルのノードの作成された子ノードの数が子ノードしきい値より大きくなるまでステップ（ａ）から（ｃ）を繰り返すこと
をさらに含む、請求項２に記載の方法。
【請求項４】
前記フィルタにかけて除去することが、前記カレントレベルのノードの作成された子ノードの前記数が前記子ノードしきい値より大きいとき、前記受信されたデータパケットをフィルタにかけて除去することをさらに含む、請求項３に記載の方法。
【請求項５】
前記ＩＰアドレスのセグメントに前記同じ値を有する受信されたパケットの前記数をデクリメントするために、前記複数のノードの中の各ノードの格納された数字が、リークパラメータによって判断されたレートによりデクリメントされる、請求項１に記載の方法。
【請求項６】
あるネットワークアドレスで受信されたデータパケットをフィルタにかけて除去する装置であって、
複数のレベルに編成された複数のノードを含む階層ツリーを維持する手段であって、ツリーのルートノードの上の各レベルが１つまたは複数のノードを有し、１つまたは複数のノードのそれぞれがインターネットプロトコル（ＩＰ）アドレスのセグメントの特定の値に対応し、セグメントがツリーの特定のレベルの各ノードで同じものであり、ツリーの特定のレベルにある個々の各ノードが、前記特定のレベルと関連する前記ＩＰアドレスのセグメントに同じ値を有する受信されたパケットの数を表す数字を格納する、維持する手段と、
受信されたデータパケットの一部を前記階層ツリーに基づいてフィルタにかけて除去する手段とを備え、
前記フィルタにかけて除去する手段が、発信元のＩＰアドレスの１つのセグメントに特定の値を有する受信されたデータパケットを、その１つのセグメントの特定の値に対応するノードが子ノードしきい値より大きい数の子ノードを有することに応じてフィルタにかけて除去する手段である、装置。
【請求項７】
前記階層ツリーを維持する前記手段がさらに、
（ａ）発信元のＩＰアドレスの第１のセグメントに第１の値を含みかつ前記発信元のＩＰアドレスの第２のセグメントに第２の値を含む受信されたデータパケットについて、カレントレベルに位置づけられたカレントレベルのノードを判断する手段であって、前記カレントレベルのノードが、前記発信元のＩＰアドレスの前記第１のセグメントに前記第１の値を有する前記受信されたデータパケットの数を表す数字を格納する手段と、
（ｂ）前記格納された数字が前記カレントレベルのノードについてのオーバーフローしきい値より小さい場合、前記格納された数字をインクリメントする手段と、
（ｃ）格納された数字が前記カレントレベルのノードについての前記オーバーフローしきい値より大きい場合、ツリーの次のレベルで前記カレントレベルのノードの子ノードを作成する手段であって、前記子ノードが前記発信元のＩＰアドレスの前記第１のセグメントについては前記第１の値に、かつ前記第２のセグメントについては前記第２の値に対応する手段と
を備える、請求項６に記載の装置。
【請求項８】
（ｄ）前記カレントレベルのノードの作成された子ノードの数が子ノードしきい値より大きくなるまでステップ（ａ）から（ｃ）を繰り返す手段
をさらに備える、請求項７に記載の装置。
【国際調査報告】
2010520664.tif 000007
2010520664.tif 000008
2010520664.tif 000009