(57)【要約】  アドホックネットワークにおけるパケット廃棄攻撃において、悪意のあるネットワークノードは転送するものと想定されるパケットを選択的に廃棄することを選択し、これはアプリケーションの良好な出力およびネットワークの安定性に不利な影響をもたらすことになる。アドホックネットワークにおけるパケット廃棄攻撃の検出のための方法およびシステムは、ＩＰフローパケットの発生、受信または近隣ネットワークノードへの転送に関する統計の報告をネットワークノードに要求する。これらの統計を分析し、相関を行い、パケットを廃棄する疑いのあるノードを判断する。
2008523769.tif 000002
【特許請求の範囲】
【請求項１】
アドホックネットワークにおけるパケットを廃棄する疑いのあるノードを判断する方法であって、
前記アドホックネットワークにおけるネットワークノードにおいて、ＩＰフローパケットの発生、受信、または近隣ネットワークノードへの転送に関する統計を作成するステップ、および
前記統計を分析し、パケットを廃棄する疑いのあるネットワークノードを判断するステップ
を含むことを特徴とする方法。
【請求項２】
請求項１に記載の方法において、前記統計を作成するステップが、
ノードにおけるフローデータベースをゼロに初期設定し、
ノードにおいて発生するか、またはノードを通過する各ＩＰパケットに対して、
発信元および宛先ＩＰアドレス対がフローデータベースに存在するか調べ、
フローが存在しなければ、
フローに対する（唯一の発信元および宛先ＩＰアドレス対により
定義する）新たな登録を作成し、
標本化開始時間を現時間に設定し、
受信パケット計数を加算し、
現次ホップＩＰに対する転送パケット計数を加算し、
現次ホップＩＰが次ホップ構成に存在しなければ、登録を作成、更新し、
存在すれば、既存登録を更新し、
フローに対する活性度を再設定し、
次フローのための発信元および宛先ＩＰアドレス対がフローデータベースに存在するか調べるステップに進む
ステップを含むことを特徴とする方法。
【請求項３】
請求項２に記載の方法において、前記統計を調整装置ノードに転送するステップをさらに含むことを特徴とする方法。
【請求項４】
請求項１に記載の方法において、前記統計を作成するステップが、
報告タイムスロットを初期設定し、
現報告タイムスロットが、
データベースにおける全てのフローに対して終了すると、前記フローのデータ
ベース登録から取得する、発信元および宛先ＩＰ、標本化開始時間、受信パケ
ット計数および次ホップ構成の情報を含む報告を調整装置ノードへ送信し、
フローのデータベース登録における活性度を報告時間スロットだけ削減し、
活性度≦セロであれば、データベースからフローを削除し、
そうでなければ、
前記フローのデータベース登録において、標本化開始時間を前記現時間に、受信パケット計数をゼロに、次ホップ構成における全ての次ホップＩＰに対する転送パケット計数をゼロに再設定し、
・      報告時間スロットを初期設定するステップに進む
ステップを含むことを特徴とする方法。
【請求項５】
請求項４に記載の方法において、前記統計を調整装置ノードに転送する、ステップをさらに含むことを特徴とする方法。
【請求項６】
請求項１に記載の方法において、前記統計を前記分析するステップが、
ネットワークノードからの各受信メッセージに対して、
メッセージ内の個々のフローに対する報告を分離し、
メッセージにおけるそれぞれ個々のフローの報告に対して、
調整装置ノードにおいて維持するフローリストにそのフローに対する登録が存在しなければ、
フローに対する（各フローリストの登録は、フローに関する報告を送信したノードのリスト（フロー・ノード・リスト）を含む）新たな登録を作成し、
フローに対するフロータイマーを起動し７０４、
フローリストのフロー・ノード・リストにノードに対する登録が存在しなければ、
ノードに対する（フロー・ノード・リストにおける各登録は、報告継続時間＝（現時間−標本化開始時間）の報告継続時間、受信パケット計数および次ホップ構成を有する）新たな登録を作成し、
そうでなく、ノードに対する登録がフロー・ノード・リストに存在すれば、その場合報告が重複するので（各ノードは各報告時間スロット中にフロー毎に１つの報告を送信する）、報告を無視し、
メッセージ内の個々のフローに対する報告を分離するステップに進む、
ステップを含むことを特徴とする方法。
【請求項７】
請求項６に記載の方法において、
フローに属するフロー・ノード・リストにおける各ノードの登録Ｘに対するフロー
タイマーが時間満了になり、
受信パケット計数が次ホップ構成における全ての次ホップＩＰに対する転
送パケット計数の前記和に等しくなければ、ノードＸに対する疑惑カウンタを差分
／受信パケット計数だけ加算し、
次ホップ構成における各次ホップＩＰに対する
フローに属するフロー・ノード・リストにおける各ノードの登録Ｘに対し
て、次ホップＩＰのフロー・ノード・リストの登録における受信パケット計数をＸ
の次ホップ構成における転送パケット計数だけ減算し、
フローに属するフロー・ノード・リストにおける各ノードの登録Ｘに対し
て｜受信パケット計数｜／（転送パケット計数の和）＞許容パケット損失
であれば、ノードＸに対するネットワーク・ノード・リストの登録における疑惑カ
ウンタを｜受信パケット計数｜／（転送パケット計数の和）だけ加算し、全てのノ
ードのフロー・ノード・リストの登録において次ホップＩＰとしてＸをリストする
全てのノードに対するネットワーク・ノード・リストの登録における疑惑カウンタ
を｜受信パケット計数｜／（転送パケット計数の和）だけ加算し８０６、
そうでなければ、
ノードＸに対するネットワーク・ノード・リストの登録における疑惑カウ
ンタを信頼値だけ減算し、全てのノードのフロー・ノード・リストの登録において次ホップＩＰとしてＸをリストする全てのノードに対するネットワーク・ノード・リストの登録における疑惑カウンタを信頼値だけ減算し、
唯一のフローリストからフローの登録を削除する
ステップをさらに含むことを特徴とする方法。
【請求項８】
請求項７に記載の方法において、
ＬｉＰａＤタイマーを設定し、
ＬｉＰａＤタイマーが時間満了になると、疑惑カウンタ値による「疑惑」ノードの順位リストを生成し、
ＬｉＰａＤタイマーを設定するステップに進む
ステップをさらに含むことを特徴とする方法。
【請求項９】
請求項８に記載の方法において、前記統計を前記分析するステップが、偽りを働くノードの特定に対してネットワークノードを罰し、称える、ステップをさらに含むことを特徴とする方法。
【請求項１０】
軽いパケットの廃棄検出を含むアドホックネットワークにおいて、
ＩＰフローパケットの発生、受信、または近隣ネットワークノードへの転送に関する統計を報告する複数のネットワークノード、および
前記報告を受信し、前記統計を分析して、パケットを廃棄する疑いのあるネットワークノードを判断するための１以上のネットワークノードに連結する少なくとも１つの調整装置ノード
を備えることを特徴とする、アドホックネットワーク。
【請求項１１】
請求項１０に記載のアドホックネットワークにおいて、各ネットワークノードが統計の報告を、
ノードにおけるフローデータベースをゼロに初期設定し、
ノードにおいて発生するか、またはノードを通過する各ＩＰパケットに対して、
発信元および宛先ＩＰアドレス対がフローデータベースに存在するか調べ、
フローが存在しなければ、
フローに対する（唯一の発信元および宛先ＩＰアドレス対により
定義する）新たな登録を作成し、
標本化開始時間を現時間に設定し、
受信パケット計数を加算し、
現次ホップＩＰに対する転送パケット計数を加算し、
現次ホップＩＰが次ホップ構成に存在しなければ、登録を作成、更新し、
存在すれば、既存登録を更新し、
フローに対する活性度を再設定し、
次フローのための発信元および宛先ＩＰアドレス対がフローデータベースに存在するか調べるステップに進む
ことにより行うことを特徴とするアドホックネットワーク。
【請求項１２】
請求項１０に記載のアドホックネットワークにおいて、各ネットワークノードが統計の報告を、
報告タイムスロットを初期設定し、
現報告タイムスロットが、
データベースにおける全てのフローに対して終了すると、前記フローのデータ
ベース登録から取得する、発信元および宛先ＩＰ、標本化開始時間、受信パケット計数および次ホップ構成の情報を含む報告を調整装置ノードへ送信し、
フローのデータベース登録における活性度を報告時間スロットだけ削減し、
活性度≦セロであれば、データベースからフローを削除し、
そうでなければ、
前記フローのデータベース登録において、標本化開始時間を前記現時間に、受信パケット計数をゼロに、次ホップ構成における全ての次ホップＩＰに対する転送パケット計数をゼロに再設定し、
報告時間スロットを初期設定するステップに進む
ことにより行うことを特徴とするアドホックネットワーク。
【請求項１３】
請求項１０に記載のアドホックネットワークにおいて、前記調整装置ノードが前記統計の分析を、
ネットワークノードからの各受信メッセージに対して、
メッセージ内の個々のフローに対する報告を分離し、
メッセージにおけるそれぞれ個々のフローの報告に対して、
調整装置ノードにおいて維持するフローリストにそのフローに対する登録が存在しなければ、
フローに対する（各フローリストの登録は、フローに関する報告を送信したノードのリスト（フローノードリスト）を含む）新たな登録を作成し、
フローに対するフロータイマーを起動し７０４、
フローリストのフロー・ノード・リストにノードに対する登録が存在しなければ、
ノードに対する（フロー・ノード・リストにおける各登録は、報告継続時間＝（現時間−標本化開始時間）の報告継続時間、受信パケット計数および次ホップ構成を有する）新たな登録を作成し、
そうでなく、ノードに対する登録がフロー・ノード・リストに存在すれば、その場合報告が重複するので（各ノードは各報告時間スロット中にフロー毎に１つの報告を送信する）、報告を無視し、
メッセージ内の個々のフローに対する報告を分離するステップに進み、
フローに属するフロー・ノード・リストにおける各ノードの登録Ｘに対するフロータイマーが時間満了になり、
受信パケット計数が次ホップ構成における全ての次ホップＩＰに対する転
送パケット計数の前記和に等しくなければ、ノードＸに対する疑惑カウンタを差分
／受信パケット計数だけ加算し、
次ホップ構成における各次ホップＩＰに対する
フローに属するフロー・ノード・リストにおける各ノードの登録Ｘに対し
て、次ホップＩＰのフロー・ノード・リストの登録における受信パケット計数をＸ
の次ホップ構成における転送パケット計数だけ減算し、
フローに属するフロー・ノード・リストにおける各ノードの登録Ｘに対し
て、｜受信パケット計数｜／（転送パケット計数の和）＞許容パケット損
失であれば、ノードＸに対するネットワーク・ノード・リストの登録における疑惑
カウンタを｜受信パケット計数｜／（転送パケット計数の和）だけ加算し、全ての
ノードのフロー・ノード・リストの登録において次ホップＩＰとしてＸをリストす
る全てのノードに対するネットワーク・ノード・リストの登録における疑惑カウン
タを｜受信パケット計数｜／（転送パケット計数の和）だけ加算し８０６、
そうでなければ、
ノードＸに対するネットワーク・ノード・リストの登録における疑惑カウンタを信頼値だけ減算し、全てのノードのフロー・ノード・リストの登録において次ホップＩＰとしてＸをリストする全てのノードに対するネットワーク・ノード・リストの登録における疑惑カウンタを信頼値だけ減算し、
唯一のフローリストからフローの登録を削除することにより、さらに、
ＩＰフローパケットの発生、受信、または近隣ネットワークノードへの転送に関する統計を報告する複数のネットワークノード、および
前記報告を受信し、パケットを廃棄する疑いのあるネットワークノードを判断するための１以上のネットワークノードに連結する少なくとも１つの調整装置ノード
ことにより行うことを特徴とする、アドホックネットワーク。
【請求項１４】
機械により読み取り可能であり、該機械により実行可能な命令プログラムを実体として実装して、該機械にＩＰフローパケットに関する統計を報告するための方法を実行させる、プログラム格納デバイスにおいて、前記方法は、
ノードにおけるフローデータベースをゼロに初期設定し、
ノードにおいて発生するか、またはノードを通過する各ＩＰパケットに対して、
発信元および宛先ＩＰアドレス対がフローデータベースに存在するか調べ、
フローが存在しなければ、
フローに対する（固有の発信元および宛先ＩＰアドレス対
により定義する）新たな登録を作成し、
標本化開始時間を現時間に設定し、
受信パケット計数を加算し、
現次ホップＩＰに対する転送パケット計数を加算し、
現次ホップＩＰが次ホップ構成に存在しなければ、登録を作成、更新し、
存在すれば、既存登録を更新し、
フローに対する活性度を再設定し、
次フローのための発信元および宛先ＩＰアドレス対がフローデータベースに存在するか調べるステップに進み、
報告タイムスロットを初期設定し、
現報告タイムスロットが、
データベースにおける全てのフローに対して終了すると、
前記フローのデータベース登録から取得する、発信元および宛先ＩＰ、標本化開始時間、受信パケット計数および次ホップ構成の情報を含む報告を調整装置ノードへ送信し、
フローのデータベース登録における活性度を報告時間スロットだけ削減し、
活性度≦セロであれば、データベースからフローを削除し、
そうでなければ、
前記フローのデータベース登録において、標本化開始時間を前記現時間に、受信パケット計数をゼロに、次ホップ構成における全ての次ホップＩＰに対する転送パケット計数をゼロに再設定し、
報告時間スロットを初期設定するステップに進む
ステップを含むことを特徴とするプログラム格納デバイス。
【請求項１５】
機械により読み取り可能であり、該機械により実行可能な命令プログラムを実体として実装して、アドホックネットワークにおいてパケットを廃棄する疑いのあるネットワークノードを判断するために、該機械に統計を分析するための方法を実行させるプログラム格納デバイスにおいて、前記方法は、
ネットワークノードからの各受信メッセージに対して、
メッセージ内の個々のフローに対する報告を分離し、
メッセージにおけるそれぞれ個々のフローの報告に対して、
調整装置ノードにおいて維持するフローリストにそのフローに対する登録が存在しなければ、
フローに対する（各フローリストの登録は、フローに関する報告を送信したノードのリスト（フロー・ノード・リスト）を含む）新たな登録を作成し、
フローに対するフロータイマーを起動し７０４、
フローリストのフロー・ノード・リストにノードに対する登録が存在しなければ、
ノードに対する（フロー・ノード・リストにおける各登録は、報告継続時間＝（現時間−標本化開始時間）の報告継続時間、受信パケット計数および次ホップ構成を有する）新たな登録を作成し、
そうでなく、ノードに対する登録がフロー・ノード・リストに存在すれば、その場合報告が重複するので（各ノードは各報告時間スロット中にフロー毎に１つの報告を送信する）、報告を無視し、
メッセージ内の個々のフローに対する報告を分離するステップに進み、
フローに属するフロー・ノード・リストにおける各ノードの登録Ｘに対するフロータイマーが時間満了になり、
受信パケット計数が次ホップ構成における全ての次ホップＩＰに対する転
送パケット計数の前記和に等しくなければ、ノードＸに対する疑惑カウンタを差分
／受信パケット計数だけ加算し、
次ホップ構成における各次ホップＩＰに対する
フローに属するフロー・ノード・リストにおける各ノードの登録Ｘに対し
て、次ホップＩＰのフロー・ノード・リストの登録における受信パケット計数をＸ
の次ホップ構成における転送パケット計数だけ減算し、
フローに属するフロー・ノード・リストにおける各ノードの登録Ｘに対し
て、
｜受信パケット計数｜／（転送パケット計数の和）＞許容パケット損失で
あれば、ノードＸに対するネットワーク・ノード・リストの登録における疑惑カウ
ンタを｜受信パケット計数｜／（転送パケット計数の和）だけ加算し、全てのノー
ドのフロー・ノード・リストの登録において次ホップＩＰとしてＸをリストする全
てのノードに対するネットワーク・ノード・リストの登録における疑惑カウンタを
｜受信パケット計数｜／（転送パケット計数の和）だけ加算し８０６、
そうでなければ、
ノードＸに対するネットワーク・ノード・リストの登録における疑惑カウンタを信頼値だけ減算し、全てのノードのフロー・ノード・リストの登録において次ホップＩＰとしてＸをリストする全てのノードに対するネットワーク・ノード・リストの登録における疑惑カウンタを信頼値だけ減算し、
唯一のフローリストからフローの登録を削除し、
ＩＰフローパケットの発生、受信、または近隣ネットワークノードへの転送に関する統計を報告する複数のネットワークノード、および
前記報告を受信し、パケットを廃棄する疑いのあるネットワークノードを判断するための１以上のネットワークノードに連結する少なくとも１つの調整装置ノード、
を備える、
ステップを含むことを特徴とするプログラム格納デバイス。
【請求項１６】
請求項１５に記載の、機械により読み取り可能であり、該機械により実行可能な命令プログラムを実体として実施し、アドホックネットワークにおいてパケットを廃棄する疑いのあるネットワークノードを判断するために、該機械に統計を分析するための方法を実行させるプログラム格納デバイスにおいて、前記アドホックネットワークにおけるネットワークノードを罰し、称える、ステップをさらに含むことを特徴とするプログラム格納デバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本願に関係する相互参照
本願は、２００４年１２月１３日出願の米国特許仮出願第６０／６３５，４５１号の出
願日の権益を主張し、その公開内容をここに参照により本明細書に組み込む。
【０００２】
政府認可権
本願は、米国陸軍研究所により与えられた契約ＤＡＡＤ１９−０１−Ｃ−００６２の下に政府の支援によりなされたものである。政府は、この発明において一定の権利を有することができる。
【０００３】
本発明は、アドホックネットワークにおけるパケット廃棄攻撃の検出に関する。特に、ネットワークノードはＩＰフローパケットの発生、受信、または近隣ネットワークノードへの転送に関する統計を報告し、次いで統計を分析し、相関を行い、パケットを廃棄する疑いのあるノードを判断する。
【背景技術】
【０００４】
アドホックネットワークは一般に構成上、移動無線ノードを含むものと記述され、ノードはＩＰパケットを転送することができる。このようなネットワークは最近の数年間に亘って広く研究され、複数のルーティングおよびその他のプロトコルが構成および通信を可能にするために提案されている。ノードが潜在的に全てのネットワークトラフィックを見ることができることと関連するアドホックネットワークの移動および無線の本質は、アドホックネットワークが有線ネットワークより悪意のある攻撃により多く晒されることを意味する。アドホックネットワークへの攻撃の検出、防止、攻撃からの回復のための手法に関してこの数年間に亘ってかなりの努力が費やされた。この仕事の大きな部分をルーティングプロトコルへの攻撃に集中させた、というのはルーティングがアドホック・ネットワーク・インフラストラクチャの重要な構成要素であるからである。研究したが、最終的に提唱されず、ルーティング攻撃のように損害をもたらしうる攻撃は、悪意のあるアドホック・ネットワーク・ノードが、転送されるものと考えられるパケットを選択的に廃棄する場合である。このようにパケットを廃棄する悪意のあるノードの存在は、ＴＣＰなどの信頼できる伝送プロトコルを使用する場合にもネットワークの「良好な出力」に有害でありうる。この理由は、５％以上のパケット損失率に遭遇すると、ＴＣＰフローのスループットがかなり影響を受けるからである。悪意のあるノードは、また重要な制御パケットを廃棄しかねず、これはアドホックネットワークの安定性に不利な影響をもたらす。このような悪意のあるノードを検出する課題は無線の故に複雑であり、従ってこのようなネットワークリンクの「損失のある」特性は悪意と事故とによる廃棄の間の区別を曖昧にする。
【０００５】
従来の解決法は、特別なタイプのネットワークトラフィックに対して立案され、実用に妥当でない仮定を設けている。この課題を解決しようとする従前の試みは、ネットワークリンクの不規則な監視に頼っており、これは実用的仮定ではない。それは、不規則な監視がリソース集中的であり、リンクレイヤ技術に特定し、回避および挿入技術に影響されやすく、また規模に柔軟でないなどの種々の問題に苦しむからである。
【０００６】
不規則モードでは、パケットはインターネットプロトコルの組（internet protocol suit、ＩＰＳ）を通じて流れない。センサーは実転送パケットよりむしろ監視トラフィックのコピーを分析する。不規則モードで動作する利点は、ＩＰＳが転送トラフィックによるパケットフローに影響を与えないことである。とはいえ、不規則モードで動作する欠点は、悪意トラフィックが意図する目標へ到達し、原子的攻撃（単一パケットの攻撃）などの一定のタイプの攻撃を行うのを、ＩＰＳが止めることができないことである。場当たり的なＩＰＳデバイスにより実装する対応動作は事後対応であり、攻撃に対応するのに例えばルータおよびファイアウォールなどの他のネットワーク構成デバイスの支援を必要とすることがよくある。このような対応動作は原子的攻撃のための幾つかのクラスの攻撃を防止することはできるが、単一パケットには目標システムに到着する機会がまずあり、その後に不規則ベースのセンサーがアクセス制御リスト（access control list、ＡＣＬ）の修正を管理デバイス（ファイアウォール、スイッチ、またはルータ）に適用することができる。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、アドホックネットワークにおけるパケット廃棄攻撃の検出に対する規模柔軟性があり、効果的で実用的な手法を提供する。本発明は、ＩＰフローパケットの発生、受信、または近隣ネットワークノードへの転送に関する統計を報告するネットワークノードに頼る。これらの統計を分析し、相関を行い、パケットを廃棄する疑いのあるノードを判断する。
【０００８】
本発明の軽いパケット廃棄（Lightweight Packet Drop、ＬｉＰａＤ）アルゴリズムは、アドホック・ネットワーク・ノードがノードを通過する各ＩＰフローに対してその近隣ネットワークノードから受信し、その近隣ネットワークノードへ転送するＩＰパケットの数を探知することを必要とする。フローをＩＰパケットヘッダにおける発信元ＩＰアドレスおよび宛先ＩＰアドレスを要素とする集合により定義する。フローの統計をネットワークノードにより調整装置ノードに定期的に報告し、調整装置ノードが統計を分析して、パケットを廃棄しようとするネットワークノードを特定する。ネットワークノードをその「悪さの」レベルに従い定期的に順位付けするので、リンクレイヤの問題による「自然な」パケット損失はアルゴリズムにより説明が付く。アルゴリズムは統計を正確に報告せず、調整装置に意図的に虚偽の報告をする、悪意のあるノードを検出することができる。さらに、ノードが移動し、ルーティングプロトコルが新たな経路を決定すると、トラフィックフローの再ルーティングを行う動的アドホックネットワークの場合にも、アルゴリズムは効果的である。アルゴリズムは、複数のパケットを廃棄するノードを検出することができ、暗号化されたトラフィックに関しても動作できるが、それは暗号化トラフィックがＩＰレベルのパケットヘッダ情報にアクセスする必要があるからである。アルゴリズムにより課す不規則リンク監視に対する要求条件はない。
アルゴリズムは以下の仮定に頼る。
【０００９】
攻撃者により物理的に、または論理的に乗っ取られる恐れは、１以上のネットワークノードにより仕掛けられる。悪意のあるノードは、悪意のあるノードにより転送するものと想定されるＩＰパケットを選択的に廃棄しうる。悪意のあるノードは、またその受信および／または転送パケット数に関する不正確な情報を提供することもある。
【００１０】
不規則なリンクレベル監視をアルゴリズムにより必要とすることはない。不規則な監視の実行性はリンクレイヤ特性およびリンクレイヤ暗号化手法に依存する。従って、パケット廃棄検出アルゴリズムに必要な情報を提供するために、不規則な監視に頼ることはできない。
【００１１】
ノードはＩＰパケットのヘッダを見ることができ、ノードを通過するトラフィックフローに関する統計を収集することができる。少なくともＩＰパケットのヘッダは正しい転送を可能にするために中間ノードに取り可視である必要があるので、この仮定はトラフィックフローのエンド・ツー・エンド暗号化に問題を課すことはない。
【００１２】
ＩＤＳメッセージはエンド・ツー・エンドに暗号化され、従って、中間ノードにより一般のネットワークトラフィックと区別することはできない。この仮定は悪意のあるノードがＩＤＳメッセージを特に廃棄するのを防止する。
【００１３】
ノードは、幾つかの保証された配信機構（信頼性のあるＵＤＰ、またはアプリケーションレベルの信頼性など）を使用して、ＩＤＳメッセージを調整装置ノードに送信する。
【００１４】
ノードは緩やかに時間同期し、最大数秒変動する。
【００１５】
本発明の主目的は、それ故アドホックネットワークにおけるパケット廃棄攻撃の検出方法の提供である。
【００１６】
本発明の別の目的は、ネットワークノードがＩＰフローパケットの発生、受信、または近隣ネットワークノードへの転送に関する統計を報告し、次いで統計の分析、相関を行い、パケットを廃棄する疑いのあるノードを判断する方法の提供である。
【００１７】
本発明のさらなる目的は、添付の図面とともに以下の記述を読めば、より明確に明らかになろう。
【発明を実施するための最良の形態】
【００１８】
ネットワークノードはＬｉＰａＤアルゴリズムを実行し、ネットワークノードを通過するトラフィックフローについて報告する。図１を参照して、アドホックネットワーク１００におけるフローの経路上の各ネットワークノード１０２は、連結する調整装置ノード１０４へフローに関する要約情報を定期的に送信する。調整装置ノードは受信情報の相関を行い、パケットを廃棄するネットワークノードを判断する。
【００１９】
以下の用語をＬｉＰａＤアルゴリズムの記述において使用する。
【００２０】
調整装置ノード：ノードはネットワークノードから定期的に報告を受信し、報告を分析し、パケットを廃棄する悪意のあるノードを判断する。
【００２１】
報告時間スロット：ノードがフローに関する報告を調整装置へ送信する適合可能な期間。ネットワークにおける全てのノードにおいて同じ値に設定する。
【００２２】
唯一のフローＩＤ：ネットワークにおける各フローをフローに対する発信元および宛先ＩＰアドレスの連鎖により唯一に特定する。
【００２３】
標本化開始時間：現報告時間スロット中に、ノードがノードを通過するフローの探知を開始する時間。
【００２４】
活性度：動作しないフローを探知し、動作しないフローをデータベースから削除するためにネットワークノードにおいて使用するタイマー。ネットワークにおける全てのノードにおいて同じ値に設定する。
【００２５】
受信パケット計数：現報告時間スロット中にフローに対するノードにより受信するパケット数の計数。
【００２６】
転送パケット計数：現報告時間スロット中にフローに対するノードによる近隣ネットワークノードへの転送パケット数の計数。
【００２７】
次ホップ構成：２要素のそれぞれが、次ホップ近隣ネットワークノードのＩＰアドレス（次ホップＩＰ）および現報告時間スロット中に次ホップ近隣ネットワークノードに転送するフローパケット数（転送パケット計数）を示す、２要素集合のリストである。
【００２８】
疑惑カウンタ：ネットワークノードの「悪意度」を表すために調整装置において使用する値。値が高いほど、ノードはより悪意があると考えられる。
【００２９】
ネットワーク・ノード・リスト：ノードに対する疑惑カウンタを含む調整装置ノードにより維持するネットワークノードのリストである。
【００３０】
フローリスト：調整装置ノードにより維持するフローのリストおよびネットワークノードにより報告するフローの統計。
【００３１】
フロー・ノード・リスト：調整装置ノードのフローリストにおけるフローについて報告するネットワークノードのリスト。ネットワークノードに対する各登録は報告継続時間、受信パケット計数、次ホップ構成を含む。
【００３２】
報告継続時間：現報告時間スロット中にフローをノードにより探知する時間。
【００３３】
フロータイマー：受信情報の処理以前に、全てのネットワークノードが特定のフローについて報告できるように調整装置ノードにおいて使用するタイマー。
【００３４】
許容パケット損失：「自然な」リンクレイヤ損失を受容し、従って誤りを積極的に削減するための調整装置における適合可能な閾。
【００３５】
ＬｉＰａＤタイマー：疑惑カウンタ値を削減することによりネットワーク・ノード・リストにおける全てのネットワークノードを定期的に順位付けするために調整装置ノードにおいて使用するタイマー。
【００３６】
信頼値：パケットを正確に転送するノードを称えるために調整装置において使用する値。転送動作の悪い場合にノードを罰するために使用する最終値に設定。
【００３７】
基本概念は図２を参照して記述することができ、図２はアドホックネットワーク２００の一部である６ノードＡ、Ｂ、Ｃ、Ｄ、ＥおよびＸを示す。フロー１はノードＡ、ＸおよびＢを通過し、一方フロー２はノードＣ、ＸおよびＤを通過する。フロー１に対して、ノードＡ、ＸおよびＢはＩＰパケットを受信し、そのそれぞれのＩＰレベル次ホップ（Ａに対する次ホップはＸ；Ｘに対してはＢ）へ転送するＩＰパケットに関する報告を生成し、フロー２に対してノードＣ、ＸおよびＤが同様に（Ｃに対する次ホップはＸ；Ｘに対してはＤ）報告を生成する。報告を定期的に（報告時間スロット）現在単一ノードであると仮定する調整装置ノードへ送信する。とはいえ、ネットワークにおいて複数の動作する調整装置ノードが存在し、各調整装置ノードが所定の１以上のネットワークノードに連結することは可能である。受信報告における情報に基づいて、調整装置ノードは動作の良いノードを称え、動作のよくないノードを罰する。調整装置は全てのネットワークノードの「疑惑」値に基づいてその順位リストを定期的に生成する。ネットワークノードおよび調整装置ノードにおけるアルゴリズムの詳細を以下に記述する。
アドホック・ネットワーク・ノードにおけるアルゴリズム
【００３８】
各ネットワークノードはノードを通過するか、またはノードから発生するフローのデータベース（発信元および宛先ＩＰアドレスにより定義する）を維持する。データベースは図３に示す各フローに対する情報を含む。唯一のフローＩＤ（８バイト）は、フローの発信元および宛先ＩＰアドレスから導出する。標本化開始時間（４バイト）は、ノードが現報告時間スロット中にフローに関するデータの収集を開始した時間を示す。活性度（４バイト）はデータベースからフローを削除するための残存時間量を示し、新たなパケットをフローに対して受信するたびごとに再設定する。受信パケット計数（４バイト）は現報告時間スロット中のノードによるフローに対する受信パケット数を示す。次ホップ構成（集合要素当り８バイト）は、２集合要素のそれぞれが次ホップ近隣ネットワークノードのＩＰアドレス（次ホップＩＰ）および現報告時間スロット中の次ホップ近隣ネットワークノードのＩＰアドレスへの転送フローパケット数を示す、２要素の集合リストである。
各ネットワークノードにおけるフローのデータベース構成
【００３９】
各ネットワークノードにおけるアルゴリズムは並列に実行する２つの部分を含む。図４に示すアルゴリズムの第１の部分は以下のステップに従いノードにおいて発生するか、またはノードを通過する各ＩＰパケットについて動作する。
１．    ノードにおけるフローデータベースをゼロに初期設定する４００。
２．    ノードにおいて発生するか、またはノードを通過する各ＩＰパケットに対し、
・      発信元および宛先ＩＰアドレス対がフローデータベースに存在するか調べる４０２。
・      フローが存在しなければ、
ｏフローに対して（唯一の発信元および宛先ＩＰアドレス対により定義する）新たな登録を作成し、標本化開始時間を現時間に設定する４０４。
・      受信パケット計数を加算する４０６。
・      現次ホップＩＰに対する転送パケット計数を加算する４０８。
ｏ現次ホップＩＰが次ホップ構成に存在しなければ、登録を作成、更新する４１２。
ｏ存在すれば、既存登録を更新する４１４。
・      フローに対する活性度を再設定する４１６。
・      ステップ４０２に進む。
【００４０】
上記の次ホップ構成の概念は、ネットワーク・ルーティング・テーブルが報告時間スロット中に変化し、ノードがフローのパケットを異なる次ホップ近隣ネットワークノードへ転送する原因となることがあるというものである。図５で、フロー１は最初ノードＦ−Ｃ−Ｘを通じて流れるものとして示し、次にノードＦ−Ｃ−Ｂを通じて流れるように変化する。次ホップ構成は、ノードが報告時間スロット中の各次ホップ近隣ネットワークノードへの転送パケット数を探知し、ローカルなルーティング／転送テーブルにおける情報を使用して、現次ホップ近隣ネットワークノードを特定することを保証する。ノードＣはＸに対する次ホップ構成における転送パケット計数を探知し、次いでルートの変化後Ｂに対して同じことを継続することになろう。次ホップ構成は、また次ホップ近隣ネットワークノードが同じ報告時間スロット中に異なる前位ホップから同じフローに対するパケットを受信する場合にも対処する。
【００４１】
図６に示すアルゴリズムの第２の部分は、全てのネットワークノードに亘って一様な予め構成した値を有する各報告時間スロットの終了時に起動する。
１．    報告時間スロットを初期設定する６００。
２．    現報告時間スロットが終了すると
・      データベースにおける全てのフローに対し、
ｏフローのデータベース登録から取得する、発信元および宛先ＩＰ、標本化開始時間、受信パケット計数、次ホップ構成の情報を含む報告を調整装置ノードに送信する６０２。
ｏフローのデータベース登録における活性度を報告時間スロットだけ削減する６０４。
ｏ活性度≦ゼロであれば６０６、データベースからフローを削除する６０８。
ｏそうでなければ、
・フローのデータベース登録において、標本化開始時間を現時間に、受信パケット計数をゼロに、次ホップ構成における全ての次ホップＩＰに対する転送パケット計数をゼロに再設定する６１０。
・      ステップ６００に進む。
【００４２】
複数のフローに対する報告を集めて、可能な限り少ないＩＰパケットで送信し、個々のフローの報告を分離パケットで送信する場合のパケット当りのヘッダオーバヘッドを回避することができる。フローの報告によるネットワーク帯域幅の消費は、その送信前の報告の圧縮によりさらに削減することができる。調整装置ノードはそのような受信報告をさらに処理する前に圧縮解除することができる。
調整装置ノードにおけるアルゴリズム
【００４３】
調整装置ノードは各ネットワークノードから報告を定期的に受信する。調整装置ノードは、唯一のＩＰアドレスにより特定する各ノードを有するネットワークにおけるノードに関する情報（ネットワーク・ノード・リスト）を維持する。各ネットワーク・ノード・リストの登録は、最初はゼロに設定するノードに対する疑惑カウンタを含む。さらに、調整装置はまたネットワークノードにより報告する各フローに関する情報（フローリスト）も維持する。調整装置のアルゴリズムは３つの部分を含む。図７に示す第１の部分は、フローの報告をネットワークノードから受信するとその報告を処理する。
１．    ネットワークノードからの各受信メッセージに対して、
ｏ      メッセージ内の個々のフローに対する報告を分離する７００。
・メッセージのそれぞれ個々のフローの報告に対して、
ｏ調整装置ノードにおいて維持するフローリストにそのフローに対する登録が存在しなければ、
・フローに対する（各フローリストの登録はフローに関する報告を送信したノードリスト（フロー・ノード・リスト）を含む）新たな登録を作成する７０２。
・フローに対するフロータイマーを起動する７０４。
ｏフローリストのフロー・ノード・リストにノードに対する登録が存在しなければ７０６、
・ノードに対する（フロー・ノード・リストにおける各登録は報告継続時間＝（現時間−標本化開始時間）の報告継続時間、受信パケット計数、次ホップ構成を有する）新たな登録を作成する７０８。
ｏそうでなくフロー・ノード・リストにノードに対する登録が存在すれば、その場合登録が重複するので、報告を無視する（各ノードは各報告時間スロット中にフロー当り１つの報告を送信する）７１０。
ｏ      ステップ７００に進む。
【００４４】
図８に示す調整装置ノードのアルゴリズムの第２の部分はフロータイマーの時間満了により起動し、フロータイマーは、上記のように現報告時間スロットにおけるフローに関する第１の報告を受信して、起動する。フロータイマーを持つ概念は、全てのノードがその特定のフローについて報告する機会を持つまで待機することであり、従ってフロータイマー値はアドホックネットワークに亘る最大メッセージ遅延により影響を受けることがある。以上の第１の部分におけるフローに対するフロー・ノード・リストにおいて利用可能な情報に基づいて、調整装置は受信パケット数とノードによるその次ホップ近隣ネットワークノードにより示すノードへの送信パケット数を比較する。以下のステップ１は、ノードが受信する全てのフローパケットを転送せず、受信および転送パケット数について正しく報告する「正直な」ノードの場合を取り扱う。従ってノードにより報告するように受信パケット数と全ての次ホップ近隣ネットワークノードへの転送パケット数との間には不一致がある。ネットワーク・ノード・リストにおけるノードに対する疑惑カウンタはこの動作を反映するように加算する。
【００４５】
以下のステップ２は、ノードによる送信報告フローパケット数とその次ホップ近隣ネットワークノードによる受信報告フローパケット数との間に不一致がある場合を取り扱う。この不一致は、適合可能な閾（許容パケット損失）を使用して考慮する「自然な」パケット損失に帰することができる。その他の可能性は、ノードまたはその次ホップ近隣ネットワークノードの１つのいずれかがそれぞれ転送、または受信フローパケット実数を報告しないことにより虚偽を働くことである。この可能性を次に以下のステップ２および３に従い記述することにする。
【００４６】
フロータイマーが時間満了になる場合；
１．    フローに属するフロー・ノード・リストにおける各ノードの登録Ｘに対して、
・      受信パケット計数が次ホップ構成における全ての次ホップＩＰに対する転送パケット計数の和に等しくなければ、ノードＸに対する疑惑カウンタを差分／受信パケット計数だけ加算する８００。
２．    次ホップ構成における各次ホップＩＰに対する
・      フローに属するフロー・ノード・リストにおける各ノードの登録Ｘに対して、次ホップＩＰのフロー・ノード・リストの登録における受信パケット計数をＸの次ホップ構成における転送パケット計数だけ減算する８０２。
３．    フローに属するフロー・ノード・リストにおける各ノードの登録Ｘに対して、
・      ｜受信パケット計数｜／（転送パケット計数の和）＞許容パケット損失であれば８０４、
−ノードＸに対するネットワーク・ノード・リストの登録における疑惑カウンタを｜受信パケット計数｜／（転送パケット計数の和）だけ加算し、
−全てのノードのフロー・ノード・リストの登録において次ホップＩＰとしてＸをリストする全てのノードに対するネットワーク・ノード・リストの登録における疑惑カウンタを｜受信パケット計数｜／（転送パケット計数の和）だけ加算する８０６。
・      そうでなければ、
−ノードＸに対するネットワーク・ノード・リストの登録における疑惑カウンタを信頼値だけ減算し、
−全てのノードのフロー・ノード・リストの登録において次ホップＩＰとしてＸをリストする全てのノードに対するネットワーク・ノード・リストの登録における疑惑カウンタを信頼値だけ減算する８０８。
４．    唯一のフローリストからフローの登録を削除する８１０。
【００４７】
図９に示す調整装置ノードのアルゴリズムの第３の部分は、ＬｉＰａＤタイマーにより起動し、ＬｉＰａＤタイマーはネットワーク・ノード・リストを定期的に調べ、ノードをその疑惑カウンタ値により順位付けする。疑惑カウンタ値が大きいほど、ノードはパケットを廃棄した見込みが高い。
１．    ＬｉＰａＤタイマーを設定する９００。
・      ＬｉＰａＤタイマーが時間満了になると、疑惑カウンタ値により「疑いのある」ノードの順位リストを生成する９０２。
−ステップ９００に進む。
虚偽を働くノード
【００４８】
ネットワークノードの肩代わりを行った巧妙な攻撃者はパケットの廃棄に加えて、調整装置ノードへの報告情報を改竄するための管理を行うことがありうる。ＬｉＰａＤアルゴリズムは図１０に示す、虚偽を働くノードに関する全ての場合を取り扱うことができる。ノードＸは悪意の有るノードであり、フロー１からパケットを廃棄しようとする。ノードＸはＡから受信し、Ｂへ転送するパケット数について９つの別個の組み合わせの虚偽を働きうる。記号ｖ（注．チェック記号）は、Ｘが統計的に正しく報告していることを示し、記号↓は、Ｘが実際に受信／転送するより少ないパケットを報告していることを示し、記号↑は、Ｘが実際に受信／転送するより多いパケットを報告していることを示し、黒丸に白抜きの矢印の記号は、Ｘが受信したのと正確に同じ数の転送すべきパケットを報告していることを表す。９つの場合を図１０に示す。
【００４９】
９つの場合において、ノードＸは悪意の有るノードであり、ノードＸを通過する全てのフローのパケットを廃棄している。ノードＸはノードＡから受信するフロー１のパケット数については正確に報告しているが、フロー１のパケットと同数をノードＸによりノードＢへ転送していると報告している。Ｘは実際には幾つかのフロー１のパケットを廃棄している、すなわちＸは虚偽を働いているので、これは正しくない。調整装置ノードがＸおよびＢからのデータを分析して、調整装置ノードはＸによる転送報告パケット数とＢによる受信報告パケット数との間の相違を注目することになる。この場合、実際に転送したより多くのパケットを報告することにより、Ｘが虚偽を働いているか、または実際に受信したより少ないパケットを報告することにより、Ｂが虚偽を働いているかを判断することはできない。ＬｉＰａＤアルゴリズムは、ＸおよびＢ双方を罰することによりこのような場合を処理する。１つのフローのみを考えれば、この手法はＢに不利に働くことになる。とはいえ、ＸまたはＢを通過するその他のフローがあり、Ｂはこれらのフローに属するパケットを正しく転送すると期待することができるので、Ｂはその前位ホップとしてＸを持たないフローに対して罰せられることはない。従って、Ｂの総合疑惑カウンタは改善し、一方Ｘの疑惑カウンタはＸを通過する全てのフローに対して悪化する。事実、ＬｉＰａＤアルゴリズムは動作の良いノードを積極的に称え、さらにＸに対する疑惑カウンタ値と比較してＢに対する疑惑カウンタ値を改善する。
【００５０】
ＬｉＰａＤアルゴリズムは、アドホックネットワークにおけるパケット廃棄攻撃の検出に対して規模柔軟性があり、効果的で、実用的アルゴリズムである。本手法は、ＩＰフローパケットの発信、受信または近隣ネットワークノードへの転送に関する統計の報告をノードに要求する。これらの統計を分析し、相関を行い、パケットを廃棄する疑いの有るノードを判断する。悪意の有るパケット廃棄に匹敵する、悪意のない「自然な」リンク損失が存在し、悪意の有るノードが不正な統計を報告することにより虚偽を働く場合にも、ＬｉＰａＤアルゴリズムは複数の悪意の有るパケット廃棄ノードの検出に正確である。ＬｉＰａＤアルゴリズムはより大きなネットワークおよびノード移動性に対して良好な検出確度を維持する。
【００５１】
アドホックネットワークに対する軽いパケット廃棄検出を記述し、図示したが、本発明の広範な原理および技術から離反することなく、変更および修正が可能であることは、当業者には明らかであろうし、本発明は本明細書に添付する特許請求の範囲によってのみ制限されるであろう。
【図面の簡単な説明】
【００５２】
【図１】システムノードおよび調整装置を示すアドホックネットワークの概要図である。
【図２】アドホックネットワークにおけるトラフィックフローの概要図である。
【図３】各ネットワークノードにおけるフローデータベースの構成を示す。
【図４】アドホック・ネットワーク・ノードにおけるアルゴリズムの第１の部分のフローチャートである。
【図５】軽いパケット廃棄により処理する経路変更の概要図である。
【図６】アドホック・ネットワーク・ノードにおけるアルゴリズムの第２の部分のフローチャートである。
【図７】フローの報告をネットワークノードから受信する場合のフロー報告を処理するための調整装置ノードにおけるアルゴリズムの第１の部分のフローチャートである。
【図８】現行フローに関する第１の報告を受信すると起動する、フロータイマーの時間満了により起動される調整装置ノードにおけるアルゴリズムの第２の部分のフローチャートである。
【図９】ＬｉＰａＤタイマーにより起動する調整装置ノードにおけるアルゴリズムの第３の部分のフローチャートである。
【図１０】悪意のあるノードを有するアドホックネットワークにおけるトラフィックフローの概要図および悪意のあるノードにより行うことのできる動作テーブルである。
【図１】
2008523769.tif 000003
【図２】
2008523769.tif 000004
【図３】
2008523769.tif 000005
【図４】
2008523769.tif 000006
【図５】
2008523769.tif 000007
【図６】
2008523769.tif 000008
【図７】
2008523769.tif 000009
【図８】
2008523769.tif 000010
【図９】
2008523769.tif 000011
【図１０】
2008523769.tif 000012
【国際調査報告】
2008523769.tif 000013