無線メッシュ及びセンサ・ネットワークにおける回復力のあるパケット逆探知のための方法及びシステム
【課題】 偽データ注入を特定し、防止するために、ネットワークにおいて逆探知するためのシステム及び方法を提供する。
【解決手段】 ネットワークにおけるパケット逆探知のためのシステム及び方法は、ネットワーク内の各々のノードについて識別番号（ＩＤ）を保持することと、転送パス上の各々のノードとシンクとの間で共有される秘密鍵を用いて署名（例えば、メッセージ検証コード（ＭＡＣ））を生成することと、を含む。各々の転送ノードは、決定論的方法又はある確率のいずれかで、パケットにそのＩＤと署名を付加することによってマークを残す。シンクでパケットを受信すると、各々のパケットに含まれた署名の正当性が、これらの署名が付加された順序と逆の順序で検証される。偽データ注入攻撃において共謀する障害ノードの位置を求めるために、転送パス内の最後の有効ＭＡＣが求められる。
【解決手段】 ネットワークにおけるパケット逆探知のためのシステム及び方法は、ネットワーク内の各々のノードについて識別番号（ＩＤ）を保持することと、転送パス上の各々のノードとシンクとの間で共有される秘密鍵を用いて署名（例えば、メッセージ検証コード（ＭＡＣ））を生成することと、を含む。各々の転送ノードは、決定論的方法又はある確率のいずれかで、パケットにそのＩＤと署名を付加することによってマークを残す。シンクでパケットを受信すると、各々のパケットに含まれた署名の正当性が、これらの署名が付加された順序と逆の順序で検証される。偽データ注入攻撃において共謀する障害ノードの位置を求めるために、転送パス内の最後の有効ＭＡＣが求められる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク通信に関し、より詳細には、偽データ注入を特定し、防止するために、ネットワークにおいて逆探知するためのシステム及び方法に関する。
【背景技術】
【０００２】
パケット逆探知は、パケットの真の起点と、ネットワーク内でパケットが横断したパスとを特定する技術である。パケット逆探知は、サービス妨害（ＤｏＳ）攻撃の出現に対抗するために広く用いられており、サービス妨害（ＤｏＳ）攻撃では、一般に攻撃パケットのソース・アドレスが、それらの識別情報を隠すために攻撃者によって「偽造（forge）」される。
【０００３】
有線インターネットのための多くのＩＰパケット逆探知スキームが存在している。例えば、確率的パケット・マーク付け（ＰＰＭ）スキームが提案されている。ＰＰＭスキームにおいては、ルータが、一定の確率で、そのルータが転送するパケット内の或る情報を「マーク付け」する。その情報は、ルータの識別情報又は２つの隣接するルータ間のリンクを伝達する。宛先は、異なるルータからのマークを収集した後で、パケットが横断したパスを再構成することができる。
【０００４】
代数的な手法が提案されており、これは、パス情報が、パスに沿ったルータの識別情報によって係数が決定される多項式ｆ（ｘ）にエンコードされるものである。各々のパケットがサンプルｘを搬送し、パスに沿ったすべてのルータが共同でｆ（ｘ）を計算する。宛先は、十分な（ｘ，ｆ（ｘ））値の対を収集した後で、係数を導出し、最終的にルータの識別情報を推論することができる。
【０００５】
他の技術では、各々のルータが、以前に転送されたパケットを長期間にわたって記憶しておくことが必要である。宛先は、ルータが過去に１つのパケットを転送したかどうかをそれらのルータに問い合わせることによって、転送パスを再構成することができる。ルータは、帯域外逆探知メッセージを低い確率でソース又は宛先に送信することもある。これらのメッセージを収集することにより、宛先がパスを構成することが可能となる。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
これらのスキームは、限られた脅威モデルの下で設計されたものであり、多くの用途で、例えば無線メッシュ及びセンサ・ネットワークでは、不十分なものとなる。これらの従来技術のほとんどは、中間ノード（ルータ）が障害を受けないことを想定している。これは、実際には、特にノードが物理的に取り込まれ障害を受けやすい無線メッシュ又はセンサ・ネットワークにおいては当てはまらないことがある。これらのスキームにおいては、障害を受けた単一の中間ノードでさえ、パケットの真の起点が特定されないようにすることができる。障害ノードは、マークを偽造し、恣意的で不正な起点まで逆探知するように犠牲者を欺くことさえある。
【０００７】
さらに、多くのスキームは、加害者の位置を正確に突き止めるために、多数のパケットが収集されること、又は、中間ノードが大量の監査トレースを格納することを必要とする。これらは、インターネットでは問題とならないかもしれないが、帯域幅、エネルギー、及びストレージ・リソースが逼迫した無線メッシュ及びセンサ・ネットワークにおいては、実用上の厳しい障害に直面する可能性がある。
【課題を解決するための手段】
【０００８】
ネットワークにおけるパケット逆探知のためのシステム及び方法は、ネットワーク内の各々のノードについて識別番号（ＩＤ）を保持することと、転送ノードとシンクとの間で共有される秘密鍵を用いて、決定論的方法又は確率的方法のいずれかで、各々の転送ノードにおいてパケットに加えられる署名、例えばメッセージ検証コード（ＭＡＣ）を生成することとを含む。パケットを受信すると、シンクは、署名（ＭＡＣ）が加えられた順序と逆の順序で、パケットの署名（ＭＡＣ）の正当性を検証する。第１の無効な署名（ＭＡＣ）は、偽造レポートを注入した障害ノード又は正当なパケットを改ざんした障害ノードを、オンザフライで明らかにする。
【０００９】
ネットワークにおけるパケット逆探知のための方法は、ネットワーク内の各々のノードについて識別番号（ＩＤ）を保持することと、このノードとシンクとの間で共有される秘密鍵を用いて、各々の転送ノードにおいて署名を生成することと、シンクでパケットを受信したときに、署名が加えられた順序と逆の順序で、シンクによって各々のパケットの署名の正当性を検証することと、偽データ注入ソース及び／又は共謀する障害ノードの位置を求めるために、転送パスにおける署名有効性を判断することと、を含む。
【００１０】
無線メッシュ又はセンサ・ネットワークにおけるパケット逆探知のための別の方法は、ネットワーク内の各々のノードについて真の識別番号（ＩＤ）を保持することと、現在のノード及びシンクのみに知られている秘密鍵に基づいて、真のＩＤから匿名ＩＤを計算することと、少なくとも２つの確率で各々のパケットをマーク付けするために、転送パス内の各々のノードについて秘密鍵を用いてメッセージ検証コード（ＭＡＣ）を生成することと、偽データ注入ソースを発見するために、ネットワーク内のノードについて匿名ＩＤから真のＩＤを求め、各々のパケットに存在するマークを用いてノード・ルートを再構成し、転送パス内の最後の有効ＭＡＣを求めるために、真のＩＤと秘密鍵とを用いて、転送パスの各々のノードを遡って各々のパケットのＭＡＣの正当性を検証することによって、パスを逆探知することと、を含む。
【００１１】
これらの並びに他の特徴及び利点は、添付図面と併せて読まれることになる例示的な実施形態の以下の詳細な説明から、明らかとなるであろう。
本開示によって、添付図面を参照しながら以下の好ましい実施形態の説明において詳細が提示される。
【図面の簡単な説明】
【００１２】
【図１】一実施形態に係る無線ネットワークにおけるノードの転送パスを示す図である。
【図２】受信したパケットの連続番号が許容限界内にあるかどうかを判断して、パケットが正当なものであること又は再現されたものであることを検証するための、現在未発行の連続番号の有界ウィンドウを示す図である。
【図３】本発明の原理に従って検出される共謀ソース及び転送スパイ（例えば、障害を受けたノード）を有する転送パスを含む例示的なネットワークを示す図である。
【図４】本発明の原理に従ってノード順序を再構成するための例示的な方法を示すブロック／フロー図である。
【図５】本発明の原理に従って検出可能な識別情報スワッピングによって作成されたループを示す図である。
【図６】ノードの３つのカテゴリを示す図である。
【図７】転送パス内の有効ＭＡＣを持つ最後のノードを示す図である。
【図８】シンクがｘ個のパケットを受信した後でｎ個の転送ノードすべてからマークが収集される確率の分析結果を示すグラフである。
【図９】シンクがｘ個のパケットを受信した後でｎ個の転送ノードすべてからマークが収集される確率のシミュレーション結果を示すグラフである。
【図１０】最初のｘ個のパケットでシンクによってマークが収集されたノードの平均数を示すグラフである。
【図１１】４０ノードのパスの場合に、候補ソースの組が時間の経過と共に変化することを示すグラフである。
【図１２】１００回の実行で、何回の実行がソースを明確に特定するのに失敗したかを全パス長の関数として示すグラフであり、２００、４００、６００及び８００の曲線は、各々の実行におけるパケット数に対応する。
【図１３】ソースを明確に特定するのに必要な平均のパケット数を全パス長の関数として示すグラフであり、各々の実行において８００個のパケットがシンクで受信される。
【図１４】例示的な実施形態に係る逆探知及びスパイ位置特定のための例示的なシステム／方法を示すブロック／フロー図である。
【発明を実施するための形態】
【００１３】
本発明の実施形態によれば、多数の共謀する加害者の存在の下で加害者ノードの位置を正確に突き止めることができるシステム及び方法が提供される。本発明の実施形態は、脅威がより深刻でリソースがより逼迫している無線メッシュ及びセンサ・ネットワークに特に適用可能である。従来技術とは対照的に、本発明の実施形態は、障害を受けたノードだけではなく障害を受けた転送ノードが存在する場合でも機能し、それらの位置を突き止める。これは、マークの偽造を防止するためにマークに認証符号を加えることにとどまるものではない。従来技術においては、多数の共謀する障害ノードは、無実のノードを辿るように依然として犠牲者をだます可能性がある。本発明の原理によれば、より少ないリソースを用いて回復力のある逆探知が達成され、単一パケットのみを用いて加害者への逆探知を達成することができる。
【００１４】
多くの無線センサ・ネットワークは、潜在的に悪い環境又は敵意のある環境でも機能することが期待される。それらは無人で動作するため、敵が、センサ・ノードを物理的にピックアップして障害し、秘密鍵を含むそれらの格納データを入手するのは容易である。これらの障害を受けた「スパイ（moles）」は、種々のタイプの攻撃を開始することが可能であり、その重大なものの１つは偽データ注入である。１つの単一スパイが、大量の偽装トラフィック（bogus traffic）を注入してシンクを溢れさせ、アプリケーションの不具合を招き、転送パスに沿ったエネルギー及び帯域幅リソースを浪費する可能性がある。最近の研究によって、そうした偽装メッセージを途中で検出してドロップするための多くのスキームが提案されている。しかしながら、それらは、攻撃のダメージを緩和させるだけであるため、すべて受動的なものである。それらは、攻撃の根本原因に反撃して排除するための能動的な手段を提供するものではない。
【００１５】
以下の説明は、能動的な反撃、すなわち、センサ・ネットワーク内のスパイを探知する方法に対応するものである。スパイの位置を知ることで、ネットワークからスパイを分離又は除去して、攻撃の根本原因を撲滅することができる。スパイを探知することは、重要な研究課題を提示する。第１に、ルータがより良好に保護され、エンド・ホストより相対的に信頼されているインターネットとは対照的に、センサ・ネットワーク内のすべてのセンサ・ノードは、敵によって等しくアクセス可能であり、一様に保護されていない。いずれのノードもパケットを転送することができ、相対的に信頼されている活用可能なルーティング・インフラストラクチャは存在しない。第２に、スパイは共謀することができる。スパイは、それらの秘密鍵を共有するだけでなく、それらの形跡を隠すように協働してパケットを操作することができる。そうした操作攻撃は、単に偽装トラフィックの量を増加させることよりはるかに高度である。インターネットのための既存のインターネット・プロトコル（ＩＰ）逆探知スキームは、そうした共謀するスパイを考慮しておらず、このような攻撃の下では効果のないものとなりつつある。
【００１６】
特に有用な実施形態によれば、偽データ注入攻撃における共謀スパイを探知するための入れ子式マーク付け（nested marking）スキームが提示されている。パケット・マーク付けは、パケットの真の起点を推定するために用いられ、ノードは、転送するパケットに自分の識別情報をマーク付けする。こうしたマークを収集することによって、シンクは、ルートを推論し、したがってトラフィックの起点位置を推論することができる。パケット・マーク付けはインターネットで用いられてきたが、共謀するセンサ・スパイに対するその適用可能性は、本発明者らの知るところではまだ研究されていない。ＩＰ逆探知のための既存のマーク付けスキームは、ソースと自分自身の真の位置を隠すようにマークを改ざんするか又はさらにシンクに無実のノードまで辿らせる中間の共謀スパイによって、容易に破られる可能性がある。
【００１７】
本発明の入れ子式マーク付けスキームは、単一パケットの逆探知をサポートする。各々の転送ノードは、パケットを入れ子式にマーク付けし、そのマークが前のすべての転送ノードのマークを保護するようにする。本発明の入れ子式マーク付けスキームは、共謀スパイがマークをどのように操作しても、マークが、ソースの位置又は自分自身の位置のいずれかを明らかにすることを保証する。
【００１８】
センサ・ネットワーク内のスパイに対する事前対応型のセキュリティの必要性は、パケット・マーク付けの枠組み内で、スパイが開始することができる種々の共謀攻撃について検討される。パケット・マーク付けのセキュリティは、入れ子式マーク付けが必要かつ十分であることを含んでおり、すなわち、前のノードのマークの一部が保護されない場合（一見して明らかな多くの設計のように）には、共謀するスパイがソース及び自分自身の位置を隠すか又は無実のノードまで辿るようにシンクをだますことができる攻撃が存在する。本明細書では、分析的評価を通して入れ子式マーク付けの有効性が示される。
【００１９】
本発明の原理による確率的入れ子式マーク付け（ＰＮＭ）スキームは、２つの技術、すなわち入れ子式マーク付けと確率的マーク付けとを用いて、共謀するスパイに対する安全で効果的な逆探知を達成する。入れ子式マーク付けは、単一パケットの逆探知をサポートする。各々の転送ノードは、パケットを入れ子式にマーク付けして、そのマークがすべての前の転送ノードのマークを保護するようにする。入れ子式マーク付けは、共謀スパイがマークをどのように操作しても、マークが、ソースの位置又は自分自身の位置のいずれかを明らかにすることを保証する。確率的マーク付けは、センサの制約されたリソースに合うようにパケットあたりのオーバーヘッドを低減させる。各々のノードは、一定の確率でマークを残し、したがって、パケットはほんのわずかなマークを搬送する。新しいマークが既存のマークに置き換わるインターネット・マーク付けスキームとは異なり、新しいマークが単にパケットに付加される。
【００２０】
本明細書においては、分析的評価と経験的評価との両方を通じてＰＮＭの有効性及び効率が実証される。ＰＮＭは、約５０パケット以内の高速で逆探知を行い、シンクは、最大で２０ホップ離れたスパイを探知することができる。ＰＮＭは、スパイがかなりの量の攻撃トラフィックを注入することができる前にスパイが捕らえられることになるため、スパイが有効なデータ注入攻撃を開始するのを防止する。
【００２１】
共謀攻撃に対して安全な確率的入れ子式マーク付け（ＰＮＭ）のシステム及び方法が提供される。共謀スパイがマークをいかに操作しようと、ＰＮＭは、スパイを一つずつ探知することができる。入れ子式マーク付けは、共謀攻撃に対抗するのに必要かつ十分なものである。ＰＮＭはまた、例えば約５０パケット以内の速い逆探知を行い、シンクから最大で２０ホップ離れたスパイを見つけ出すことができる。これは、事実上あらゆる有効なデータ注入攻撃を防止するものであり、スパイは、大量の偽装トラフィックを注入する前に捕らえられることになる。
【００２２】
本発明の実施形態は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態、又は、ハードウェア要素とソフトウェア要素の両方を含む実施形態の形態をとることができる。好ましい実施形態においては、本発明は、ソフトウェアの形態で実装され、ソフトウェアは、ファームウェア、常駐ソフトウェア、マイクロコードなどを含む。
【００２３】
さらに、本発明は、コンピュータ若しくはあらゆる命令実行システムによって又はそれらと組み合わせて用いられるプログラム・コードを提供するコンピュータ使用可能媒体又はコンピュータ可読媒体からアクセス可能なコンピュータ・プログラム製品の形態をとることができる。この説明の目的のために、コンピュータ使用可能媒体又はコンピュータ可読媒体は、命令実行システム、装置若しくはデバイスによって又はそれらと組み合わせて用いられるプログラムを含み、格納し、通信し、伝搬し、又は転送することができるあらゆる装置とすることができる。媒体は、電子システム、磁気システム、光学システム、電磁気システム、赤外線システム、若しくは半導体システム（又は装置若しくはデバイス）又は伝搬媒体とすることができる。コンピュータ可読媒体の例として、半導体メモリ又は固体メモリ、磁気テープ、リムーバブル・コンピュータ・ディスケット、ランダム・アクセス・メモリ（ＲＡＭ）、リード・オンリー・メモリ（ＲＯＭ）、剛性磁気ディスク及び光ディスクが挙げられる。光ディスクの現在の例として、コンパクト・ディスク−リード・オンリー・メモリ（ＣＤ−ＲＯＭ）、コンパクト・ディスク−読み取り／書き込み（ＣＤ−Ｒ／Ｗ）及びＤＶＤが揚げられる。
【００２４】
プログラム・コードを格納及び／又は実行するのに適したデータ処理システムは、システム・バスを通じて直接的又は間接的にメモリ要素に結合される少なくとも１つのプロセッサを含むものとすることができる。メモリ要素は、プログラム・コードの実際の実行中に使用されるローカル・メモリと、バルク・ストレージと、実行中にバルク・ストレージからコードを取得する回数を減少させるために少なくとも幾つかのプログラム・コードを一時的に格納するキャッシュ・メモリとを含むことができる。入力／出力又はＩ／Ｏ装置（キーボード、ディスプレイ、ポインティング・デバイス等を含むが、これらに限定されない）は、直接的に又は中間のＩ／Ｏコントローラを通して、システムに結合することができる。
【００２５】
中間のプライベート・ネットワーク又はパブリック・ネットワークを通して、データ処理システムを他のデータ処理システム又は遠隔のプリンタ若しくは記憶装置に結合することができるように、ネットワーク・アダプタをシステムに結合することもできる。モデム、ケーブル・モデム、及びイーサネット・カードは、現在利用可能なタイプのネットワーク・アダプタのうちのほんの一部に過ぎない。
【００２６】
ここで、同様の番号が同じ又は類似の要素を表す図面を参照すると、まず図１において、ネットワーク１０は複数のノード１２を含む。転送パス１４内には幾つかのノード１２を配置することができる。各々のノード１２は、シンク・ノード（シンク）と鍵（Ｋ）を共有し、単調に増加する連続番号を保持することができる。ソース・ノード（ソース）Ａは、メッセージＭを送出するときに、そのＩＤと連続番号を付加し、次に署名（例えばメッセージ検証コード）を計算する。ソースは、パケット全体を次のホップ・ノード１に送信し、自分の連続番号を増加させる。同様に、ノード１は、そのＩＤ及び連続番号、さらに別の署名をパケットに付加し、次にその結果を次のホップに渡し、自分の連続番号を増加させる。最終的に、パケットはシンク・ノード シンクに到着する。到着したパケットは、元のメッセージＭだけでなく、ＩＤ、連続番号、及びパス上のすべてのノードの署名を含む。
【００２７】
シンク・ノード シンクは、パケットのＩＤから、パケットが横断したように見えるクレーム・パス（claimed path）を知る。シンクは、このパスを最後のホップ・ノードから始まる逆の順序で検証する。パス上の各々のノードについて、シンクは、ノードと共有された鍵を用いて署名を再計算し、パケットの署名が正しいかどうかを検証する。シンクは、連続番号が有効であるかどうかも検証する。両方のチェックが成功した場合には、シンクは、前のホップの検証を続ける。最終的に、シンクは、すべての署名／連続番号を正しく検証した場合に停止するか、又は、最初の不正な署名／連続番号で停止する。加害者ノードは、シンクが検証を停止したノードの近傍１ホップ以内にある。
【００２８】
署名を計算し、それらがメッセージを「たまねぎ」のようにレイヤ毎に（一度に一つのレイヤ）保護するため、検出されずに前のホップのメッセージを偽造又は修正することができるノードは無い。各々のパケットがホップ毎の連続番号を搬送するため、加害者は、検出されずに古い正当なトラフィックを再現（replay）することはできない。多数の共謀ノードが存在するときには、最初にパス上の最後の加害者の位置が発見され、次いで最後から２番目の加害者の位置が発見され、以下同様にして発見される。これらのノードが、偽装メッセージを注入し、マーク付けを操作し続ける限り、それらの位置は一つ一つ発見されることになる。対照的に、既存のソリューションは、障害を受けた中間ノードを扱わないか、又は、障害を受けた多数のノードが共謀したときには保護を失う。
【００２９】
本発明の原理によれば、障害を受けた多数のノードによって開始された共謀攻撃に対して防衛するための回復力のある逆探知スキームが提供される。各々の転送ノードは、自分自身のマークとすべての前の転送ノードからのマークとを保護するために、署名を入れ子式で用いる。これによって、共謀ノードが存在する場合であっても、障害を受けた攻撃ノードの位置を逆探知することができる。一実施形態においては、決定論的マーク付けが用いられる。しかしながら、すべての転送ノードがパケットにマークを残すため、ネットワークのサイズが大きくなると、メッセージ及び通信オーバーヘッドが増大することになる。したがって、もう１つの実施形態においては、パケットあたりの通信オーバーヘッドを一定レベルに減少させ、共謀攻撃に対するセキュリティ防御を保つことができる、確率的入れ子式マーク付け（ＰＮＭ）スキームが用いられる。
【００３０】
ＰＮＭの実施形態においては、各々の転送ノードは、小さい確率ｐでパケットをマーク付けする。結果として、もう１つの入れ子式マーク付けスキームにおける単純なｎ個のマークとは対照的に、ノードの転送パス上で、１つのパケットが平均してｎ×ｐ個のマークのみを搬送する。単純な拡張のように見えるが、それは２つの点でより複雑な結果となる。
【００３１】
第１に、入れ子式マーク付けスキームへの上記の単純な確率的拡張によって、新しいセキュリティの抜け穴が開くことがある。それにより、パケットの選択的な組をドロップすることによって障害を受けた転送ノードが自分自身と真のソースとの間のいずれかの無実ノードに罪を被せることが可能な選択的ドロッピング攻撃を受けやすくなる。そうした選択的ドロッピング攻撃に打ち勝つために、匿名化技術を採用して、それらのマークにおけるノード識別情報を隠すことができる。
【００３２】
第２に、各々のパケットは、完全なパスの部分的サンプリングのみを搬送することがある。宛先が少数の攻撃パケットを用いてパスを再構成するためのパス再構成方法が提供される。宛先は、再構成されたパスを用いて加害者ノードを特定することができる。
【００３３】
本発明の原理は、従来のマーク付けスキームより強力な防御をもたらすことができる。本発明の実施形態は、形跡を隠蔽するように共謀する多数の障害ノードによって開始される、巧妙な選択的ドロッピング攻撃を含む種々の共謀攻撃に、耐えることができる。好ましい実施形態においては、通信オーバーヘッドが低減され、拡張性が向上するという利点があり、このことによって、中規模ネットワーク又は大規模のネットワークにも適用できるようになる。
【００３４】
再び図１を参照し、Ａがソースである、パスＡ−１−２．．．−Ｚ−Ｚ＋１−．．．−シンクを考える。各々のノード１２は、鍵Ｋをシンクと共有し、例えば、ＡはＫ＿ａを有し、２はＫ＿２を有し、以下同様である。さらに、各々のノードは、ノードがこれまでに生成又は転送したパケットの数を記録する連続番号を保持する。連続番号は、最初にノード１２が配置されたときにはゼロであり、ノード１２がパケットを送出するたびに１だけ増加する。
【００３５】
各々のノード１２はまた、単調に増加するパケット連続番号を保持する。Ａは、メッセージＭを送信するときに、自分の識別情報及び連続番号を付加し、署名（例えば、鍵付きメッセージ検証コード（ＭＡＣ））を計算し、次にパケットＭ全体を次のホップに送信する。各々のホップは同様に、パケットを次のホップに渡す前に、自分自身の識別情報、連続番号、及び署名を付加する。ノードＡは、メッセージＭを送信するときに、自分の識別情報Ａと現在の連続番号（ｓｅｑｎｕｍ）を付加し、次にメッセージ全体を保護する署名を計算する、すなわち、Ｈ＿ｋａ（ｘ）が鍵Ｋ＿ａを用いるｘの署名の計算を示し、「｜」が連結を示すとすると、
Ａ→Ｂ： Ｍ＿ａ＝Ｍ｜Ａ｜ｓｅｑｎｕｍ｜Ｈ＿ｋａ（Ｍ｜Ａ｜ｓｅｑｎｕｍ）
である。このパケット全体は、Ｍ＿ａと表記することができる。Ａは、Ｍ＿ａを次のホップ１に送信し、次に自分の連続番号ｓｅｑｎｕｍを増加させる。ノード１は、同様の操作を行い、以下のパケット、すなわち、
１→２： Ｍ＿ａ｜２｜ｓｅｑｎｕｍ２｜Ｈ＿ｋ２（Ｍ＿ａ｜２｜ｓｅｑｎｕｍ２）
をノード２に送信し、以下同様である。
【００３６】
一般に、パス上の連続する２つのノードＺ、Ｚ＋１について、Ｚは、ＭＺをＺ＋１に送信した後で、ＭＺ＋１、すなわち、
ＭＺ＋１＝ＭＺ｜Ｚ＋１｜ｓｅｑｎｕｍＺ＋１｜Ｈ＿ｋＺ＋１（ＭＺ｜Ｚ＋１｜ｓｅｑｎｕｍＺ＋１）
を次のホップに送信する。シンクは、このようなメッセージを受信したときに、ノードＩＤから、パケットが横断したように見えるクレーム・パスを取得することができる。シンクは、最後のホップ・ノードから始まってパケットを付加した順序と逆の順序でこのパスを検証する。
【００３７】
一般性を失うことなく、シンクがノードＶを検証するケースを考える。シンクは、ＭＺ｜Ｚ＋１｜ｓｅｑｎｕｍＺ＋１｜Ｈ＿ｋＺ＋１（ＭＺ｜Ｚ＋１｜ｓｅｑｎｕｍＺ＋１）であるメッセージＭＺ＋１を有する。ＩＤ Ｚ＋１を取得した後で、シンクは最初に、Ｋ＿Ｚ＋１の知識を用いて署名が正しいかどうかをチェックする。次に、シンクは、連続番号ｓｅｑｎｕｍ Ｚ＋１が正しいかどうかを検証する。そのために、シンクは、各々のノードについての連続番号のスライディング・ウィンドウを保持する。これが決定論的マーク付けの実施形態である。
【００３８】
図１に続いて図２を参照すると、各々のノード１２について、現在のウィンドウ２２は、上限（最大値）と下限（最小値）を有する。上限（最大値）は、このノードから受信した最大の連続番号であり、下限（最小値）は、このノードについて依然として有効な最小の連続番号である。ウィンドウ２２は、順番どおりでない有効な連続番号のどれがまだ受信されていないかを保持する。各々のパケットは、ネットワーク内で存続する（live）最大の時間を有すると仮定され、この最大寿命（Ｔ＿ｍａｘ）は、ウィンドウ２２を更新するのに用いられる。
【００３９】
最初にノード１２が配置されたときには、最小値及び最大値はいずれも０である。シンクがこのノードから連続番号ｄを有するパケットを受信したときには、以下のような３つの可能性のあるケースが存在する。１）ｄ＜最小値：連続番号は、すでに終了しているため、無効である。２）最小値≦ｄ≦最大値：ｄが以前に受信されていない場合には、ｄは有効であり、それが用いられていることを示すマークがｄについて設定される。シンクはまた、最小値を、受信されていない次の最小の有効な連続番号に更新する。しかしながら、ｄが受信されている場合（例えば、ｄがマークされた場合）、それは再現されたものであり、したがって無効な連続番号である。３）ｄ＞最大値：この場合には、連続番号は有効である。さらに、シンクは、最大値＝ｄに設定し、連続番号ｄに関連するタイマーを開始させる。タイマーは、ネットワーク内部のパケットの最大寿命であるＴ＿ｍａｘの後で終了することになる。このタイマーが終了したときに、シンクは最小値＝ｄに設定し、例えば、ｄより小さい連続番号を持つすべてのパケットは、ネットワークにおいて死んだ（died）ことになる。
【００４０】
パス上のノードは、その署名が正しく、その連続番号が有効である場合に限り、シンク検証を渡す。この場合、シンクは、前のホップのＩＤを取得することによって前のホップを検証し続け、署名及び連続番号を検証する。最終的に、検証は、すべての署名／連続番号が正しく検証されるか、又は、不正な署名／無効な連続番号が見つかったときに、停止する。いずれの場合においても、障害を受けたノードは、シンクが停止した場所の近傍１ホップ以内に位置する。例えば、シンクが、第１のホップＭ｜Ａ｜ｓｅｑｎｕｍａ｜Ｈ（Ｍ｜Ａ｜ｓｅｑｎｕｍａ）を含むすべてのノードを正しく検証したときである。真のソースは、ノードＡの近傍１ホップ以内に位置する。あるいは、いずれかのホップにおいて署名又は連続番号が無効である場合には、障害を受けたノードは、無効なノードの近傍１ホップ以内にある。例えば、ホップＸ：Ｍ＿ｗ｜Ｘ｜Ｃ＿ｘ｜Ｈを検証するときである。シンクは、ＨがＨ（Ｍ＿ｗ｜Ｘ｜Ｃ＿ｘ）と一致しないことを発見し、障害を受けたノードがノードＸの近傍１ホップ以内にあると結論づけることができる。すなわち、Ｘは、加害者である（Ｘが、不要なＨを故意に偽造する）か、又は、Ｙのような、Ｘの近傍のうちの１つである（例えば、Ｙは、Ｘの署名Ｈを修正するが、自分自身のメッセージについての正しい署名を与える）かのいずれかである。
【００４１】
提案されるセキュリティ防御は、多くの特徴を含む。第１に、正当なトラフィックを改ざんする加害者を検出することができる。メッセージは署名によってレイヤ毎に保護されるため、メッセージを修正する加害者は、ソースから始まってその直前のホップまで、前のすべてのホップの署名チェックを失敗させることになる。第２に、ＤｏＳ攻撃パケットを注入しようとする攻撃者は、鍵の知識を持たないため、離れた起点を正しく偽造することができない。シンクは、加害者の後で正常なノードによって残された情報を追い、その位置を見つけ出すことができる。第３に、メッセージがホップ毎の連続番号によって保護され、加害者が、古いパケットにおける増加した連続番号について正しい署名を生成することができないため、加害者は、前の正当なトラフィックを再現することができない。多数の攻撃ノードが同じパス上で共謀するときであっても、正当なトラフィックを修正するか又は偽装トラフィックを注入する最後の加害者の位置は、依然として特定されることになる。シンクはさらに、特定された攻撃ノードと通信しないように他のノードに命令し、残りの加害者ノードを一つずつ発見することができる。
【００４２】
モデル及び仮定：システム及び脅威モデルを説明し、悪意のある攻撃の分類法をパケット・マーク付けフレームワーク内で提示する。
【００４３】
図３を参照すると、静的センサ・ネットワーク３０についてのシステム・モデルが描かれており、このモデルは、センサ・ノード１２が一旦配置されると動かないと考えられる。これらのノード１２は、近くの環境を感知し、イベントの時刻、位置、記述など（例えば、センサの読取値）を含む、対象となるイベントに関するレポートを生成する。レポートは、マルチ−ホップ無線チャネルを通じて中間ノード４１−４７によってシンク３８に転送される。シンク３８は、十分な計算リソース及びエネルギー・リソースを持つ強力なマシンである。ルーティングは、比較的安定していると仮定される。ルートは、短い時間間隔で頻繁に変化することはない。ルートが安定しているときには、各々のノード１２は、転送パス３６において近傍に唯一の次のホップを有し、この近傍のホップを通してすべてのパケットをシンク３８に転送する。このことは、当該技術分野では公知であるいずれかのツリー・ベースのルーティング・プロトコル又は地理的ルーティング・プロトコルにおいて一貫している。
【００４４】
各々のセンサ・ノード１２は、固有のＩＤを有し、固有の秘密鍵（Ｋ）をシンク３８と共有すると仮定する。ＩＤ及び鍵は、ノード１２が配置される前にノード１２に予めロードすることができる。シンク３８は、すべてのノードＩＤ及び鍵についてのルックアップ・テーブルを保持することができる。ノードは、近傍の認証などの目的で他の鍵を定めることもできるが、ＰＮＭは、そうした鍵が機能することを必要としない。
【００４５】
センサ・ノード１２は、リソースが制約され、計算力、記憶容量及びエネルギー供給が制限されることがある。例えば、公知のＭｉｃａ２モートは、バッテリ駆動であり、４ＭＨｚのプロセッサ及び２５６Ｋのメモリのみを装備している。そうしたローエンド・デバイスに公開鍵暗号化技術を実装することもできるが、エネルギー消費の点では極めて不経済である。したがって、ここでは簡単にするために、効率的な対称暗号（例えば、安全なハッシュ関数）のみが考慮される。
【００４６】
図３の本発明の例示的なシナリオにおいては、スパイＳ（ソース３２）及びＸ（転送パス・ノード４４）は、攻撃トラフィックを注入するために自分たちの形跡を隠すように協力し、Ｓは偽装レポートを注入する。Ｘ４４は、ノード１、２、３のマーク（５７）を有するパケットを受信する。Ｘは、これらのマークを１’、２’、３’（５５）に変更するか、又は、ノード１のマークを除去する（５６）などというように、マークを種々の方法で操作することができる。スパイの目的は、自分たちの位置を隠すこと、又は、シンクが無実のノードを辿るように導くことである。
【００４７】
脅威モデル及び攻撃分類法：敵は、物理的捕捉又はソフトウェア・バグを通じてセンサ・ノードを障害し、それらのノードを完全に制御することができる。敵は、秘密鍵を含むすべての格納情報にアクセスし、悪意のある状態で挙動するように再プログラムすることができる。スパイは、損害を最大にするように連係する。シンク３８は、通常は良好に保護される。可能性はあるが、障害を受けるシンクは少なく、簡略化するために考慮されない。
【００４８】
逆探知の背景にあるのは、偽データ注入の脅威である。１つのスパイＳ３２は、ソースとして働き、大量の偽装感知レポートをネットワークに注入する。そうしたレポートは、ユーザ・アプリケーションを混乱させるだけでなく、それらを転送するのに費やされるネットワーク・リソース（例えば、エネルギー、帯域幅）を浪費する。逆探知は、積極的な防御に向けた第１ステップである。逆探知によって、シンクがレポートの真の起点を特定できるようになる。次に、シンクは、そうした場所へタスク・フォースを送り出すか、スパイを物理的に除去するか、又は、それらの近傍にトラフィックを転送しないように通知する。正確な機構は変えることができ、ここでの現在の焦点は逆探知にある。
【００４９】
効果的なマーク付けスキームのための課題は、転送パスに沿った共謀スパイＸ４４がマークを任意に改ざんする場合があることである。スパイＸ４４は、自分の位置とソース・スパイ（３２）の位置をいずれも隠すか、又は、シンクが無実のノードを辿るようにだますことができる。位置を隠すことによって、捕まったり罰せられたりすることなく連続注入が可能となる。大きな損害を生じさせるように注入するためには、このように隠すことが必要となる。それらのいずれかの位置が漏洩することによって、ネットワーク分離又は物理的除去といった処罰につながる。シンクが無実のノードを辿るようにだますことは余分なおまけであり、シンクは、無実のノードを処罰して、汚染されていないリソースを切り捨て、効果的に自分自身を処罰する。偽装レポートを注入するＳ及び転送パス上のＸの２つの共謀スパイによるマーク付けベースの逆探知に対する共謀攻撃の分類法が、以下のように提供される。
【００５０】
１）マークなし攻撃：スパイがレポートをまったくマークしないことがある。２）マーク挿入攻撃：ソース・スパイと転送スパイのいずれも、１つ又は多くの捏造マークをレポートに挿入することがある。３）マーク除去攻撃：転送スパイが、レポートにおいて上流のノードによって残された既存のマークを除去することがある。４）マーク並べ替え攻撃：転送スパイが、レポートの既存のマークを並べ替えることがある。５）マーク変更攻撃：転送スパイが、レポートの既存のマークを変更し、それらを無効にすることがある。６）選択的ドロッピング攻撃：転送スパイが、シンクによって受信された場合に逆探知される可能性のあるパケットを選択的にドロップすることがある。７）識別情報スワッピング攻撃：Ｓ及びＸは、互いの鍵を知り、互いになりすますことができる。
【００５１】
例えば、図３は、ソース・スパイＳ ３２とシンク３８との間の７つの転送ノード（４１−４７）のチェーンを示す。ノードＸ４４は共謀スパイである。ノード４４は、ノードＶ１、Ｖ２、Ｖ３によって残された３つの有効なマーク１、２、３を含むＶ３のメッセージを受信する。ノード４４は、これらを１’、２’、３’に変更して無効にすることができ、したがってシンクは、これらのマークを拒絶する。ノード４４は、マーク１を除去して２，３のみを残すこともあり、したがって逆探知は無実のノードで止まる。
【００５２】
【表１】
【００５３】
説明の助けとなるように、表１には、以下で使用される表記を含む。ソース・スパイＳ３２は、正当なフォーマットに適合した偽装レポートを注入する。各々のレポートＭは、イベントＥ、位置Ｌ及びタイムスタンプＴを含む（すなわち、Ｍ＝Ｅ｜Ｌ｜Ｔであり、「｜」は連結を示す）。レポートはまったく同じ内容を含むことはできず、同じ内容を含む場合には、レポートは冗長であるとみなされて正当な転送ノードによってドロップされる。Ｍは、ｎ個の中間ノードのチェーン｛Ｖｉ｝（ｉ＝１，．．．，ｎ）によってシンク３８に転送される。
【００５４】
各々のノードＶｉは、固有のＩＤｉを有し、固有の鍵ｋｉをシンクと共有する。ノードは、ｋが鍵である効果的で安全な鍵付ハッシュ関数Ｈｋ（ ）を用いてノードが生成又は転送するパケットについてのメッセージ検証コード（ＭＡＣ）又は他の署名を生成するために、その鍵を用いることができる。特に、Ｖｉは、前のホップＶｉ−１から受信したメッセージにマークｍｉを加えて、自分自身のメッセージＭｉを構成する。Ｍｉは、ＶｉのＩＤｉ及びＭＡＣ ＭＡＣｉを含むことができる。次いで、Ｖｉは、Ｍｉを次のホップＶｉ＋１に送信する。
【００５５】
転送ノードＶｘ（１＜ｘ＜ｎ）は、共謀スパイであり、Ｘ（４４）と表記される。Ｘは、Ｖｘ−１から受信したメッセージを任意の方法で操作し、次にそのメッセージをＶｘ＋１に渡すことができる。スパイＸは、前述の攻撃のいずれか１つ又はそれらの組み合わせを用いて、Ｓ（３２）及び自分自身の位置を隠すか、又は、無実のノードまで逆探知させることができる。
【００５６】
従来技術の認証マーク付けスキーム（ＡＭＳ）は、ノードによって加えられたマークが前のノードによって残されたマークとの関係を保護しないため、十分なセキュリティを提供することができない。各々のマークは、他のマークの有効性に影響を及ぼすことなく個別に操作することができる。本発明の原理に係る入れ子式マーク付けは、各々のマークとすべての前のマークとの間の結合を確立し、確率的マーク付けは、選択的ドロッピング攻撃に打ち勝つために、付加的な特徴であるＩＤの匿名性を提供する。
【００５７】
ＰＮＭは、疑わしい単一の近傍ホップ内の精度で、偽データ注入攻撃における共謀スパイを探知することができる。これは、１つのノードとその近傍１ホップとを含む。ソース・スパイ又は転送スパイのいずれかは、それらの範囲内にある。ＰＮＭは、２つの技術、すなわち、入れ子式マーク付けと確率的入れ子式マーク付けとを含む。入れ子式マーク付けは、基本的な機構である。入れ子式マーク付けは、シンクがパケットを１つだけ用いて確実にスパイまで逆探知できるようにする。しかしながら、入れ子式マーク付けは、各々の転送ノードがパケットにマークを付ける必要があるため、メッセージ・オーバーヘッドが大きくなるという欠点を有する。大きなセンサ・ネットワークにおいては、これは非効率となる可能性がある。
【００５８】
その後、メッセージ・オーバーヘッドを多数のパケットにわたって分散させるために、確率的マーク付けが用いられる。各々の転送ノードは、一定の確率でマークを付ける。したがって、パケットは、ほんの僅かなマークのみを搬送し、パケットあたりのオーバーヘッドが大きく低減される。これは、メッセージ・オーバーヘッドをより小さくするために検出力を犠牲にする。シンクは、スパイを特定するために多数のパケットを必要とする場合があり、このことは、スパイが重大な損害を引き起こす前に特定される限り、合理的なことである。
【００５９】
基本的な入れ子式マーク付け：パケット・マーク付け：各々の転送ノードＶｉは、シンクと共有する秘密鍵ｋｉを用いて、そのＩＤｉ及び安全なＭＡＣをパケットに付加する。ＭＡＣは、ＶｉがＶｉ−１から受信したメッセージ全体を保護する。すなわち、ＭＡＣｉ＝Ｈｋｉ（Ｍｉ−１｜ｉ）である。例として、近傍のノードによって送信されるメッセージは、
Ｓ→Ｖ１：Ｍ
Ｖ１→Ｖ２：Ｍ１＝Ｍ｜１｜Ｈｋ１（Ｍ｜１）
Ｖ２→Ｖ３：Ｍ２＝Ｍ１｜２｜Ｈｋ２（Ｍ｜２）．．．
Ｖｉ→Ｖｉ＋１：Ｍｉ＝Ｍｉ｜ｉ｜Ｈｋｉ（Ｍｉ−１｜ｉ）
である。
【００６０】
各々のホップにおいて、ＩＤｉは、ルート上にノードｉが存在することを示し、ＭＡＣ Ｈｋｉ（Ｍｉ−１｜ｉ）は、メッセージＭｉを送信するのが確かにノードｉであり、ノードが受信したのがＭｉ−１であったことを、シンクに対して証明する。Ｖｉによって加えられたＭＡＣは、自分自身のＩＤだけでなく前のホップからのメッセージ全体を保護することが理解できる。これが、入れ子式マーク付けの名前の由来である。ＭＡＣは、前のすべてのノードのＩＤ及びＭＡＣ並びにそれらの相対的順序を保護する。前のＩＤ、ＭＡＣ、又はそれらの順序のいずれかが改ざんされることによって、ＭＡＣが無効になる。
【００６１】
以下では、入れ子式マーク付けが安全な逆探知のために必要かつ十分であることを示すために、形式的セキュリティ分析を用いる。すなわち、入れ子式マーク付けはすべての共謀攻撃に耐えることができるが、より簡単な設計はいずれも耐えることができない。例えば、拡張されたＡＭＳにおいては、元のメッセージＭ及びＶｉのＩＤのみが保護されるが、Ｍｉ−１における前のマークへのマーク結合は保護されない。これが、マークが個別に操作されたときにはＡＭＳが役に立たない理由である。
【００６２】
逆探知：パケットＭｎを受信した後で、シンクは、入れ子式マークの過去を検証する。シンクは、まず最後のホップｎのＩＤを取得し、対応する鍵ｋｎを用いて最後のＭＡＣ ＭＡＣｎを検証する。ＭＡＣｎが正しい場合には、シンクは、前のホップｎ−１のＩＤを取得し、ＭＡＣｎ−１を検証する。シンクは、すべてのＭＡＣが正しいことを検証するか、又は、不正なＭＡＣｘを見つけるまで、このプロセスを続ける。スパイ（ソース又は転送のいずれか）は、検証された最後のＭＡＣを持つノードの近傍１ホップ以内（このノード自身を含む）で探知される。
【００６３】
例えば、図３において、スパイＸがノード４１のマークを変えた場合には、ノード４１、４２及び４３からのマークがすべて無効になる。Ｘがマークを残さなかったとき又は無効なマークを残したときには、逆探知はノード４５で止まり、スパイ（Ｘ）はこの停止ノードの近傍１ホップ以内にあり、Ｘが有効なマークを残したときには、逆探知はノードＸで止まり、スパイはこの停止ノードである。
【００６４】
確率的入れ子式マーク付け：確率的入れ子式マーク付けは、各々の転送ノードが小さい確率ｐでパケットをマークするようにする。したがって、ｎノードの転送パス上で、メッセージは、平均してｎｐ個のマークを搬送する。確率ｐは、ｎｐ個のマークのオーバーヘッドが許容可能となるように調整することができる。
【００６５】
不正な拡張：確率的マーク付けへの拡張は、一見して単純なように見える。しかしながら、それは容易なことではないことが分かる。各々のノードが確率ｐでマークするようにすること（以下参照）だけでは、逆探知を無実のノードに導く可能性がある選択的ドロッピング攻撃を受けやすい。
Ｓ→Ｖ１：Ｍ
Ｖ１→Ｖ２（確率ｐ）：Ｍ１＝Ｍ｜１｜Ｈｋ１（Ｍ｜１）
Ｖ２→Ｖ３（確率１−ｐ）：Ｍ２＝Ｍ１｜２｜Ｈｋ２（Ｍ｜２）．．．
Ｖｉ→Ｖｉ＋１（確率ｐ）：Ｍｉ＝Ｍｉ−１｜ｉ｜Ｈｋｉ（Ｍｉ−１｜ｉ）
Ｖｉ→Ｖｉ＋１（確率１−ｐ）：Ｍｉ＝Ｍｉ−１ （１）
【００６６】
図３の例を考える。ＩＤリストはプレーン・テキストであるため、共謀スパイＸは、Ｖ１、Ｖ２、Ｖ３のうちのどれがパケットをマーク付けしたか知ることができる。スパイＸは、Ｖ１のマークを含むすべてのパケットをドロップし、Ｖ２、Ｖ３からのＳマークを持つものだけを転送することができる。シンクが逆探知したときには、逆探知は、近傍の１ホップがいずれのスパイも含まないＶ２で止まることになる。実際には、Ｘは、逆探知を自分自身とソース・スパイとの間のいずれかの無実ノードに導くことができる。
【００６７】
確率的マーク付けにおいては各々のパケットが転送パス上のノードの部分的な「サンプル」のみを搬送するため、この攻撃が機能する。プレーン・テキストＩＤであるため、スパイは、特定の「サンプル」を選択的に渡して、シンクが、Ｘの上流ノードの１つで終わる部分的なパスのみを知るようにする。本発明の原理に係る基本的な入れ子式マーク付け（決定論的マーク付け）においては、すべてのパケットが完全なパスを構成するマークを搬送するため、この攻撃は適用されない。選択的ドロッピングのための部分的な「サンプル」は存在しない。
【００６８】
選択的ドロッピング攻撃に打ち勝つために、転送ノードは、他のノードのどれがパケットをマーク付けしたか伝えることができないことが望ましい。この方法では、共謀スパイは、どのパケットをドロップするかを知ることができない。しかしながら、シンクは依然として、マークを検証するためにどれがマークを残したかを知る必要がある。以下の説明においては、問題を解決するために、すべての秘密鍵に関する付加的な情報と十分な計算リソースとを与えるシンクの非対称性が利用される。
【００６９】
確率的入れ子式マーク付け：正当なノードＶｉは、自分の真のＩＤｉを用いる代わりに、匿名ＩＤｉ’をパケットに用いる。真のＩＤｉから匿名ＩＤｉ’へのマッピングは、Ｖｉとシンクのみが知っている秘密鍵ｋｉによって決まる。共謀スパイは、障害を受けていないＶｉからのｋｉの知識を所有しておらず、したがって、共謀スパイは、匿名ＩＤから真のＩＤを推論することはできない。
【００７０】
Ｓ→Ｖ１：Ｍ
Ｖ１→Ｖ２（確率ｐ）：Ｍ１＝Ｍ｜１’｜Ｈｋ１（Ｍ｜１’）、１’＝Ｈ’ｋ１（Ｍ｜１）
Ｖ１→Ｖ２（確率１−ｐ）：Ｍ１＝Ｍ．．．
Ｖｉ→Ｖｉ＋１（確率ｐ）：Ｍｉ＝Ｍｉ−１｜ｉ’｜Ｈｋｉ（Ｍｉ−１｜ｉ’）、ｉ’＝Ｈ’ｋｉ（Ｍ｜ｉ）
Ｖｉ→Ｖｉ＋１（確率１−ｐ）：Ｍｉ＝Ｍｉ−１ （２）
【００７１】
上記において、Ｈ’（ ）は、匿名ＩＤを計算する別の安全な一方向関数である。匿名ＩＤ ｉ’は、Ｖｉが転送する各々の個別のメッセージについて変化するように、Ｍに結合される。（冗長なコピーとみなされてドロップされることを防ぐために、ソース・スパイによって偽造されるレポートは、異なる内容を有するべきであることを思い出されたい。） これによって、攻撃者が時間とともに蓄積することができる静的マッピングが防止される。拡張ＡＭＳと比べて、確率的入れ子式マーク付けは、入れ子式マーク付けと匿名ＩＤとの両方を有する。
【００７２】
マーク検証：匿名ＩＤを用いると、シンクにおける検証は異なるものとなる。シンクは、最初に真のＩＤを知ることが必要であり、次に対応する秘密鍵を用いてＭＡＣを検証することができる。シンクの十分な計算力を利用して、真のＩＤを見つけるために全数検索を用いることができる。
【００７３】
ノードＶｎからＭｎを受信した後で、シンクは、最初に、ネットワークにおけるあらゆるノードについてのすべての匿名ＩＤを計算する。Ｍを知っていれば、シンクは、すべてのＩＤ ｉをｉ’にマップするためのテーブルを構築することができる。ｉ’を参照することによって、シンクは、真のＩＤ ｉを知る。次に、シンクは、対応する鍵ｋｉを用いてＭＡＣを検証することができる。このようにして、シンクは、すべてのＭＡＣを一つずつ検証することができる。シンクの計算力と、センサ・ネットワークにおけるデータ速度の低さとを前提とすれば、全数検索は実現可能である。シンクは、各々の個別のメッセージＭについて、参照を行うために異なるテーブルを計算する必要がある。マイクロ秒レベルでハッシュ値の計算を行うことができる（例えば、１．６Ｇ ＣＰＵであれば毎秒２５０万回のハッシュ値計算を行うことができる）とすれば、相当に大きなネットワーク（例えば数千ノード）についてこうしたテーブルを構築することは、数ミリ秒のオーダーで行われるべきである。したがって、シンクは、毎秒数百以上のパケットを検証することができる。シンクは、一度に１つのセンサから受信するため、入力するデータ速度は、センサの無線速度によって制限される。数百パケットというのは、すでに、典型的なセンサ・ハードウェア上の現在の実効データ速度より大きい（例えば、Ｍｉｃａ２ モートについては１２ｋｂｐｓであり、毎秒１００パケットを下回る）。
【００７４】
逆探知：スパイを探知することは、２ステップのプロセスとなる。まず、シンクは、十分な数のパケットからマークを収集することによって、ルートを再構成する必要がある（分析されるノードの数は後述される）。次に、シンクは、どのノードがそれらの近傍１ホップ以内にスパイを有するかを特定する。確率的マーク付けが用いられる場合にシンクがどのようにスパイを探知することができるかを示す例示的な方法１が、以下の擬似コードで提供される。
【００７５】
【表２】
【００７６】
【表３】
【００７７】
図４を参照すると、ブロック／フロー図は、一実施形態によりスパイを探知するためのシステム／方法を示す。ルートは、転送パス内のノードの相対的順序（どのノードがどのノードの上流にあるか）を見つけることによって再構成することができる。ブロック１１０において、ルートは、その上流ノードのすべてを決定することによって再構成される。相対的順序を保持するために、マトリクスＭが用いられる。マトリクスは、最初は空である。新しいノードＶｉについて正しいＭＡＣが検証されたときに、ブロック１１２において、Ｖｉに対応するもう１つの行ともう１つの列とがマトリクスに加えられる。１つのパケット内の連続する２つのＭＡＣであるＭＡＣｉ、ＭＡＣｊが正しいことが検証されたときはいつでも、ＶｉはＶｊの上流であり、ブロック１１４のマトリクスにおいてＭ［ｉ，ｊ］がこの関係を記録する（例えば、ｉ，ｊは１に設定される。−１はＶｊがＶｉの上流にあることを意味し、０は未定である）。転送パス上には２つ以上のノードが存在するため、多数のノードが、コイン投げの要領で確率ｐでパケットをマーク付けすることができる（式２を参照されたい）。これらのノードは、パス上の連続セグメントではない場合があり、転送パス上でバラバラに位置する可能性がある。シンクは、より多くのパケットを受信するのにしたがって、このマトリクスを更新し続ける。十分なパケットを前提とすると、シンクは、すべての転送ノード間の上流の関係、すなわち完全なルートを見つけ出すことができる。
【００７８】
シンクは、２つのタイプのルート、すなわち、ループを有しないルート又はループを有するルートを再構成することができる。第１のタイプは、スパイが識別情報スワッピング以外の攻撃を用いたときに発生し、後者は、スパイがマークを残すために識別情報をスワップしたときに発生する。最初のケースでは、スパイを探知することは、最も上流のノードを見つけることと等価である。ソース・スパイは、自分自身でパケットを生成するため、他からパケットを受信せず、最も上流のノードとなることができる。転送スパイが、その上流のノードによって残されたマークを除去した場合には、転送スパイは、最も上流であるように「見える」ことがある。いずれの場合においても、ソース・スパイ又は転送スパイは、最も上流のノードの近傍１ホップ以内にある。
【００７９】
スパイは、識別情報スワッピングを用いてループを作成することもでき（図５参照）、この場合には「最も」上流のノードは存在しない。
【００８０】
図５を参照すると、Ｓ及びＸは、互いの鍵を用いていくつかのパケットについて有効なマークを残し、シンクがノード間の上流関係を再構成するときにＳとＸ（これらのノードを含む）の間のすべてのノードを含むループを生じさせることができる。シンクは、依然として、ループのリンクが破れた場所まで逆探知し、その近傍内のスパイを特定することができる。
【００８１】
ソース・スパイＳ及び転送スパイＸは、いくつかのパケットについては互いの鍵を用い、他のいくつかのパケットについては自分自身の鍵を用いて、有効なマークを残すことができる。シンクは、いくつかのパケットについてはＸの前にＳが現れ、他のパケットについてはＸの後にＳが現れることを見つけることになる。シンクはまた、ＳとＸの間のすべてのノード（ＳとＸを含む）がループ１３０を形成することも見つけることになる。こうしたループにおけるいずれか２つのノードＵ、Ｖについて、ＵはＶの上流と下流の両方に現れる。
【００８２】
しかしながら、この異常は容易に特定することができ、すなわち、シンクは、残りのノードがループからシンク自体にラインを形成していることを見つけることができる。スパイは、このラインにおける最も上流のノードの近傍１ホップ以内で（すなわち、ループがラインと交差する場所で）探知される。
【００８３】
セキュリティ分析：ＰＮＭのセキュリティ強度を代替的なマーク付けスキームと比較する。この分析によって、入れ子式マーク付けが正確であり必要とされることが示される。ＰＮＭは、共謀攻撃にもかかわらずスパイを近傍領域の１ホップ以内まで突き止めることができるが、より簡単な設計はいずれも特定の攻撃の下では失敗している。シンクが、時間の経過と共に十分な数のパケットを受信するのにしたがって、確率的入れ子式マーク付けは、近傍領域の１ホップ以内のスパイを漸近的に突き止めることができる。
【００８４】
入れ子式マーク付けのセキュリティ：マーク付けスキームについての２つの特性、すなわち、１ホップ精度及び連続トレース可能性を最初に定義し、次に、それらが等価であることを証明する。次に、本発明者らの基本的な入れ子式マーク付けスキームの連続トレース可能性を示すことによって、それが１ホップ精度であることを証明する。
【００８５】
定義１（１ホップ精度）：ソース・ノード又は共謀スパイのいずれかの近傍１ホップまで常に辿ることができる場合には、マーク付けスキームは、逆探知において１ホップ精度を有する。
【００８６】
定義２（連続トレース可能性）：転送パス上の連続する２つの正当ノードＵ及びＶを考える（すなわち、Ｖは、Ｕからメッセージを受け取り、次にそれらを転送する）。連続トレース可能マーク付けスキームを用いれば、シンクがＶまで辿った場合には、シンクは常にさらにＵを辿ることができる。
【００８７】
定理１：マーク付けスキームは、それが連続トレース可能である場合に限り、１ホップ精度である。
【００８８】
十分性の証明：逆探知がノードＶで止まり、ノードＶが有効なＭＡＣを有する（転送の逆の順序の）最後のノードであるとする。Ｖは、転送パス上にはない正当ノードである可能性はなく、これは、そうしたノードはこれらのノードが転送しないメッセージについてＭＡＣを生成せず、攻撃者はそれらの秘密鍵を知らないためである。したがって、Ｖは、スパイであるか、又は、転送パス上の正当ノードであるかのいずれかである。Ｖがスパイである場合には、十分性が保たれる。次に、Ｖが正当な転送ノードである場合を考える。
【００８９】
ＵがＶの前のホップである、すなわち、ＶがＵからメッセージを受信するものとする。以下の２つの可能性、すなわち、Ｕが（ソース又は共謀）スパイであるか又はＵが正当ノードであるかの２つの可能性のみが存在する。第１の場合には、ＶがスパイＵの近傍にあるため、十分性が保たれる。一方、連続トレーサビリティの定義によって、逆探知はＵに進み、Ｖでは止まらない。したがって、第２の場合は発生することはない。これで十分性の証明が終わる。
【００９０】
次に、矛盾によって必要性を証明する。マーク付けスキームは連続トレース可能ではないとする。すなわち、シンクが、正当ノードＶまで辿るが、その前の正当ノードＵに進むことはできない場合が存在する。したがって、逆探知は、Ｖで止まり、必ずしもソース又は共謀スパイの近傍である必要はない。定義によれば、このスキームは１ホップ精度ではない。
【００９１】
図６を参照すると、転送パス上に２つのカテゴリのノードが存在する。カテゴリ１は、スパイと、それらのすぐ次のホップであり、カテゴリ２は、正当な近傍ホップを直前に有する正当ノードである。連続トレース可能性のため、逆探知は、カテゴリ２では止まることができない。カテゴリ３のノード（転送パス上にない正当ノード）については、それらのノードは、自分が転送しないメッセージについてマークを残さない。したがって、逆探知は、カテゴリ１のノード内でのみ止まることができる。
【００９２】
１ホップ精度は、逆探知が第１のカテゴリ内で止まることを意味し、連続トレース可能性は、逆探知が第２のカテゴリ内で止まることができない、すなわち、第１のカテゴリ内で止まらなければならないことを意味する。
【００９３】
定理２：入れ子式マーク付けスキームは、連続トレース可能である。
証明：連続する２つの正当転送ノードＵ及びＶを考える。Ｍｕは、ＵがＶに送信するメッセージであり、Ｖは、Ｍｕ｜Ｖ｜Ｈｋν（Ｍｕ｜Ｖ）を次のホップに送信するものとする。シンクがＶを辿ったと仮定する。これは、Ｖが、メッセージＭ’ｕ｜Ｖ｜ＭＡＣ’Ｖ内に検証されたＭＡＣ’Ｖを有するべきであり、再計算されたＭＡＣ（Ｈｋν（Ｍ’ｕ｜Ｖ））が、含まれるＭＡＣ’Ｖと同一であることを発見したことを意味する。攻撃者はｋｖを知らないため、ＭＡＣ’Ｖは、Ｖによって生成されたＭＡＣＶでなければならない。したがって、Ｍ’ｕ及びＭｕは、同一でなければならず、そうでなければ、再計算されたＭＡＣは、Ｖによって生成されたものと一致しないことになる。Ｍｕは正当ノードＵによって送信されるため、Ｍｕにおける最後のマークは、Ｕから正当なＭＡＣを搬送しなければならない。したがって、このＭＡＣを検証することによって、シンクはさらにＵをトレースすることができる。
【００９４】
結論（corollary）１：入れ子式マーク付けスキームは１ホップ精度である。
【００９５】
入れ子式マーク付けの必要性：
定理３：入れ子式マーク付けより少ないフィールドを保護するマーク付けスキームはいずれも、連続トレース可能ではない。
証明：入れ子式マーク付けにおいては、ノードのＭＡＣは、自分自身のＩＤと、前のホップから受信したメッセージ全体との両方を保護する。ここで、ＭＡＣが入れ子式ＭＡＣより少ないフィールドを保護するもう１つのマーク付けスキームｒを考える。ＩＤ又はＭＡＣが後のすべてのノードによって完全には保護されないノードＡが存在しなければならず、そうでなければ、ｒは入れ子式マーク付けスキームとなる。
【００９６】
図７を参照すると、Ｘは、Ｖによって保護されないＡのマークにおけるビットを変更する。したがって、Ｖのマークは依然として正しいが、Ｕのマークは正しくない。次に、シンクはＶまで逆探知するが、さらにＵを辿ることはできない。Ｕが、ＡのＩＤ及びＭＡＣを完全に保護する最後のノードであり、ＶがＵの次のホップであるとする（図７を参照されたい）。すなわち、ＶのＭＡＣによって保護されないいくつかのビットがＡのマークに存在する。Ｖの後の下流にある１つのスパイを考える。スパイは、レポートを適切にマーク付けし、ＶのＭＡＣによって保護されないＡのマークのビットを変更する。この場合においては、Ｖの後における（Ｖを含む）すべてのノードのＭＡＣは正しく、したがって、シンクは、Ｖを辿ることができる。しかしながら、Ａのマークはスパイによって改ざんされるため、ＵのＭＡＣは無効であるように見え、したがって、シンクはさらにＵを辿ることはできない。言い換えれば、ｒは連続トレース可能ではない。
【００９７】
結論２：入れ子式マーク付けより少ないフィールドを保護するマーク付けスキームはいずれも１ホップ精度ではない。
【００９８】
確率的入れ子式マーク付けのセキュリティ：
定理４：確率的入れ子式マーク付けは漸近的に１ホップ精度である。
証明：シンクがノード間の上流関係を再構成するときに、ループが存在しないか又はループが存在するかのいずれかの２つの可能な場合が存在する。ループが存在しないときには、証明は定理２の証明と同様である。転送パス上の連続する２つの正当ノードＵ、Ｖを考える。確率的マーク付けであるため、これらの２つのノードはいずれも、常にパケットにマークを残すわけではない。しかしながら、十分な数のパケットがあれば、それらがいずれも同じパケットにマークを残さない確率（１−ｐ）２ｎは、パケットの数ｎが増加するにつれて徐々に小さくなる。漸近的に、Ｕ、Ｖがいずれもマークを残すパケットが存在することになる。転送スパイは、そうしたパケットをドロップすることができる場合もある。しかしながら、匿名ＩＤを用いるため、転送スパイは、すべてのそうしたパケットを常に正しく推測し、ドロップすることはできない。漸近的に、シンクは、ＵとＶの両方からマークを持つパケットを受信することになる。定理２の同様の推論によれば、シンクは、Ｖまで辿ると、さらにＵを辿ることができる。したがって、逆探知は、Ｖでは止まらない。そのため、逆探知は最も上流のノードで止まることになり、そのノードは、その近傍１ホップ以内（このノード自体を含む）にスパイを有する。
【００９９】
ループが存在するときに、ループとラインとの接合点（ノードＸ）（図５を参照されたい）が、その近傍１ホップ以内（このノード自体を含む）にスパイを有することを矛盾によって証明する。この近傍１ホップ以内のすべての４つのノード（Ｘ、Ｓ、Ａ、Ｂ）が正当ノードであると仮定する。パケットは、ＸからＡに向かってシンクに到着するため、Ａは、Ｘの転送パス上の次の近傍ホップでなければならない。ループもまたノード間の上流関係を表すため、Ｘは、ループ上のその近傍ホップの１つ（Ｓ又はＢ）にもパケットを転送しなければならない。したがって、Ｘは、その転送パス上に２つの次の近傍ホップを有する。しかしながら、ルートが安定しているときには、正当ノードはいずれも、その転送パス上に唯一の次の近傍ホップを有するべきである。したがって、これらの４つのノードはすべてが正当ノードとなることはできず、それらの１つはスパイでなければならない。
【０１００】
この証明の背景として、ループがラインに接続する場所の辺りでは何らかの異常な挙動が存在するに違いないという洞察がある。正当ノードについて、それらは、ルートが安定であるときにはループを形成しない。したがって、そうした異常な挙動は、スパイの存在によってのみ説明することができる。基本的な入れ子式マーク付けにおいては、スパイは、識別情報スワッピング攻撃を開始することができるが、すべてのノードが各々のパケットにマークを残すため、シンクは、上流関係を通じて逆探知する必要はなく、常に直接スパイまで逆探知できることに注意されたい。
【０１０１】
性能評価：
シンクが各々の転送ノードＶ１、．．．Ｖｎからの少なくとも１つのマークを収集するのに必要なパケットの数Ｎを分析する。これがＬパケット以内で行われる確率Ｐ（Ｎ≦Ｌ）＝（１−１−ｐ）Ｌ）ｎを計算することができる。
【０１０２】
図８を参照すると、グラフは、ｎ個のノードからの少なくとも１つのマークがｘパケット以内で収集される確率を示す。パケットが搬送するマークの平均数ｎｐは３に固定される。１０個のノードを含むパスについて、１３パケットを受信した後でシンクがすべてのマークを収集する確率は約９０％である。２０ホップ及び３０ホップのパスについて９０％の信頼度を達成するためには、それぞれ３３パケット及び５４パケットを要する。この結果は、エネルギー及び帯域幅リソースの消費が少ない比較的少数のパケットの後で、シンクがすべてのノードからマークを収集することを示している。
【０１０３】
シミュレーション結果：
図９を参照すると、分析を検証し、分析するのが難しい指標（metrics）をさらに評価するために、シミュレーションを実行した。パケットが平均で３つのマークを搬送するように、異なるパス長さｎに対して確率ｐが調整されている。分析結果を最初に検証した。ノードの数ｎを１０、２０、３０に設定した。各々の実行においてソースから２００パケットが生成され、５０００回の実行にわって結果を平均した。図９には、シンクがｘパケットを受信した後ですべてのノードからマークが収集される確率が示される。この結果は、図８の分析結果と非常に良く一致する。
【０１０４】
図１０は、ｘパケットの後でシンクによってマークが収集されたノードの割合を示す。１０個のノードが存在するときに、平均して９個のノードのマークを７パケット以内で受信することができる。２０個及び３０個のノードのパスについて、９０％のノードからマークを収集するために約１４パケット及び２２パケットを要する。シンクは、数ダースのパケット以内で、どのノードが転送ノードであるかを知る。
【０１０５】
確率的マーク付け（方法１）におけるルート再構成アルゴリズムの性能も評価した。
図１１は、４０ノードのパスにおいて実行された場合に、より多くのパケットが受信されるにつれて、候補となるソースの組がどのように変化するかを示すものであり、ノード０はソース・スパイである。当初、候補リストにはノードＳがある。より多くのマークが受信されるにつれて、部分的なパスの始めにおける新しいノード８、１１、９、１８が加えられる。それらの上流のノードが後で発見された際には、それらはリストから除外される。真のソース０は、２１番目のパケット上で加えられる。８０番目のパケットの後で、０以外の候補ノードは組に残っていない。候補の組が長時間にわたって変化しないままとなったときに、シンクは、スパイを明確に特定することができる。
【０１０６】
十分な数のパケットがなければ、シンクは、候補となるソースの組を減らして明確に真のスパイのみにすることはできない場合がある。どれほど多くのパケットが必要であるかを試験するために、シンクが受信するパケットの数を２００、４００、６００及び８００に変化させた。各々のトラフィック量について、５から５０まで１０の異なるパス長さの各々にわたって１００回のシミュレーションを実行した。シンクがソースを明確に特定しない回数を得た。
【０１０７】
図１２は、４つの異なるトラフィック量について、失敗した実行の回数を全パス長の関数として示す。パス長が２０個までの場合には２００パケットで十分であることが理解できる。方法１は、各々の実行においてソースをほぼ必ず明確に特定し、パスが３０個までの場合には４００パケットで十分である。非常に長いパス（例えば５０個のノード）の場合のみ、失敗の頻度を５％より低く低減させるのに多数のパケット（例えば８００）が必要である。
【０１０８】
ソースを明確に特定するのにシンクが受信すべきパケット数の平均を測定するために、トラフィック量として８００を選択する。図１３は、ソースを特定するのに成功したすべての実行全体にわたって、全パス長の関数としての結果を示す。２０より小さいパス長の場合には、ソースを明確に特定するために、平均して約５５パケットを要する。これは、図９の結果と概ね一致し、５５パケットがあれば、シンクが、２０個のノードのすべてからマークを収集する確率が９９％以上である。４０個のノードのような長いパスの場合でも、シンクは、約２２０パケットの後でソースを明確に特定することができる。この結果によって、ＰＮＭはスパイが有効な偽データ注入攻撃を開始するのをほぼ防止すること、すなわち、スパイがネットワークに十分な損害を引き起こす前にそれらが突き止められることが実証される。
【０１０９】
逆探知精度：ＰＮＭは、１つのノードとその近傍１ホップとを含む近傍１ホップまでスパイを逆探知することができる。それらの１つは、ソース・スパイ又は転送スパイのいずれかである。ソース・スパイが、レポートを注入するときに異なる識別情報を主張する可能性があるため、精度は単一のノードではない。その次の近傍ホップは、どの識別情報が真であるかを伝えることができない。ＰＮＭは、機能するために近傍ホップ間のペアワイズ鍵を必要としない。しかしながら、ペアワイズ鍵の存在は、逆探知精度の改善に役立つことがある。
【０１１０】
ＰＮＭは、一度に１つのスパイを逆探知する。予想されるのは、いくつかのスパイを分離機構がＰＮＭと一緒に機能することである。その機構は、各ラウンドで特定されたスパイを分離するものである。したがって、時間の経過と共に、これらのスパイはネットワークから一つずつ分離される。
【０１１１】
ルーティング動態の影響：スパイ探知アルゴリズムは、ルートが比較的安定であるときに良好に機能する。スパイは通常、短時間に大量のトラフィックを注入して損害を最大にするため、十分なパケットの収集にはあまり多くの時間を必要としない。例えば、スパイが最大無線速度で注入する場合には、シンクは、１０秒以内で、４０ホップ離れたスパイを探知するのに十分な約３００パケットを収集することができる。ルートは、この短い時間の間は安定なままである可能性が非常に高い。
【０１１２】
レポートの再現：ソース・モールは、同じ内容のレポートを何度も再現することができ、したがって、真のＩＤと匿名ＩＤと間のマッピングは、各々の転送ノードについて固定されたままとなる。共謀スパイは、時間の経過と共にそうしたマッピングを蓄積することができるが、こうした攻撃は、冗長メッセージの局所的抑制によって容易に阻止することができる。転送ノードは、同じ内容のレポートを簡単にドロップすることができる。これは、最近遭遇したメッセージの内容（すなわち、イベント、位置及びタイムスタンプ）の署名（例えば、ハッシュ結果）を保持し、受信した署名をそれらと比較することによって行うことができる。
【０１１３】
ソース・スパイは、レポートする真のソース・ノードからの正当レポートを再現することもできる。レポート内容は、依然として正しい情報を提示する。そうしたメッセージを検出してドロップするために、同じ局所的抑制を用いることができる。他の技術も存在する。それらの１つは、各々のノードが送信又は転送する各々のメッセージについて増加する連続番号を各々のノードに保持させることであり、各々のメッセージは、マークの一部として連続番号を含み、ＭＡＣを用いて連続番号を保護する。シンクは、再現されたパケットが同じ連続番号を有することを検出することができる。この技術は上記で説明されたものである。
【０１１４】
ノードは異なる鍵を用いるため、２つの異なるノードの匿名ＩＤは衝突する場合がある（例えば、Ｈ’ｋｉ（Ｍｕ｜ｉ）＝Ｈ’ｋｊ（Ｍｕ｜ｊ））。暗号化サウンド・ハッシュ関数は、こうした衝突を最小にすることができ、すなわち、衝突が発生したときに、シンクは、そうしたパケットを検証から簡単に除外することができる。ＰＮＭにおいては、スパイは、指示されたよりも多くの偽装マークを挿入するか又は高い確率を用いることによって、より高いパケットあたりのオーバーヘッドを負わせることができる。しかしながら、これは、効率を若干低下させるだけであり、シンクは依然としてスパイまで逆探知することができる。
【０１１５】
すべてが攻撃トラフィックを送信する多数のソース・スパイが存在することもある。基本的な入れ子式マーク付けは、パス上のすべての転送ノードのマーク付けによって、依然としてそれらのソース・スパイを特定することができる。これらの多数のソース・スパイの転送パスがバラバラであるときには、ＰＮＭは、異なるパスを個々に構成し、スパイを探知することができる。これらのスパイはまた、それらの識別情報をスワップしてループを作成するが、この場合もシンクをこれらのループとリンクさせる直線ラインを用いて、これらのスパイを一つずつ特定することができる。
【０１１６】
図１４を参照すると、ブロック／フロー図は、無線ネットワークにおける逆探知のためのシステム／方法を示す。ブロック２０２において、ノードのネットワークにおいて各々のノードが識別番号（ＩＤ）（必要に応じて、図２において前述された連続番号）を付与され、それを保持する。ブロック２０４において、一実施形態として、その（真の）ＩＤは、必要に応じて、現在のノード及びシンクによって知られた鍵を用いて又は他の手段によって、そのＩＤからの匿名ＩＤにマッピングされる。匿名ＩＤのマッピングは、現在のパケットのメッセージを用いて各々の転送されたメッセージについて匿名ＩＤを変えることを含む。マッピングは、パケットの内容を用いて各々のメッセージについてマッピングが変わるようにすべきである。これにより、攻撃者が学習することによって蓄積することができる静的マッピングが防止される。ＰＮＭの実施形態においてはこれが好ましい。ブロック２０６において、ノードとシンクとの間で共有される秘密鍵を用いて、署名を、例えばメッセージ検証コード（ＭＡＣ）を、計算するか又は他の方法で求める。ＭＡＣは、転送パスを通過する各々のパケットについて求められる。ブロック２０８において、ＭＡＣを生成するために、鍵に従って前のノードからのパケット又はメッセージのハッシュ値を計算することができる。ＭＡＣは、パケット内の受信メッセージのハッシュ化バージョンを含むことができる。ＩＤは、転送パス内にノードが存在することを示し、ＭＡＣは、ノードがＩＤと関連付けられたパケットを送信したことを証明する。
【０１１７】
ブロック２０９において、パケットがマーク付けされる。ハッシュ化バージョンは、パケットをマーク付けすることを考慮することができ、マーク付けされたパケットは、転送パスを通してノードの順序を与えるために後で用いられる。パケットあたりのオーバーヘッドを低減させるために、各々の転送ノードにおいて確率的にマーク付けを行うことができる。パケットに常にマークを付ける代わりに、転送ノードは、パケットを確率ｐでマーク付けする。転送ノードは、通常通りその匿名ＩＤ及びＭＡＣを加える。転送ノードは、確率１−ｐで何も行わず、単にパケットを次のホップに転送する。次のホップは、同じ確率ｐを用いて、マークを加えるか又は単にパケットをそのまま渡し続けるかを決定する。マーク付けの変化型として、すべてのノードがマークを付ける基本的な決定論的マーク付けと、すべてのノードが一定の確率でマークを付ける確率的マーク付けがある。
【０１１８】
ブロック２１０において、パケットは、転送パスを通ってシンクで受信される。ブロック２１１において、シンクは、十分な数のパケットについてのマークに基づいて、ノードの順序を再構成する。
【０１１９】
シンクで各々のパケットが受信されると、転送パスの各々のノードを遡ってＭＡＣの正当性が検証される。転送パス内の最後の有効ＭＡＣを用いて、偽データ注入ソースを求めるか、又は、パス全体が検証された（例えば、偽データ注入ソースがない）ことを判断する。これは、ブロック２１４において最後のホップ・ノードについてＩＤを取得し、ブロック２１６において最後のホップ・ノードについてＭＡＣを計算し、ブロック２１８において最後のホップ・ノードについてＭＡＣを検証し、ブロック２２０において最後の有効ＭＡＣが求められるまで繰り返すことを含むことができる。ブロック２１６及び２１８は、連続番号を検証するために、図２で説明されたスライディング・ウィンドウを用いることができる。一実施形態においては、ブロック２１３で、ＭＡＣを検証する前に、転送パス内のノード（又はすべてのノード）について匿名ＩＤから真のＩＤが求められる。
【０１２０】
ブロック２２２において、最後の有効ＭＡＣは、１ホップ以内のスパイの位置を示す。ＰＮＭにおいては、ルート再構成（例えば図４を参照されたい）を実行してスパイを探知することができる。基本的な決定論的マーク付け手法の場合には、図４のルート再構成は不要である。ブロック２２４において、スパイは、転送パスにおいて突き止められ、転送パスから除去される。特に有用な実施形態においては、スパイは、転送パス内に複数の共謀スパイを含む。これらのスパイは、ソース・ノード又は転送ノードである場合があり、攻撃のタイプには、マーク挿入攻撃、マーク除去攻撃、マーク並べ替え攻撃、マーク変更攻撃、選択的ドロッピング攻撃、識別情報スワッピング攻撃又はその他の攻撃がある。本発明の原理によれば、スパイは、そのスパイの１ホップ以内で探知できるという利点がある。
【技術分野】
【０００１】
本発明は、ネットワーク通信に関し、より詳細には、偽データ注入を特定し、防止するために、ネットワークにおいて逆探知するためのシステム及び方法に関する。
【背景技術】
【０００２】
パケット逆探知は、パケットの真の起点と、ネットワーク内でパケットが横断したパスとを特定する技術である。パケット逆探知は、サービス妨害（ＤｏＳ）攻撃の出現に対抗するために広く用いられており、サービス妨害（ＤｏＳ）攻撃では、一般に攻撃パケットのソース・アドレスが、それらの識別情報を隠すために攻撃者によって「偽造（forge）」される。
【０００３】
有線インターネットのための多くのＩＰパケット逆探知スキームが存在している。例えば、確率的パケット・マーク付け（ＰＰＭ）スキームが提案されている。ＰＰＭスキームにおいては、ルータが、一定の確率で、そのルータが転送するパケット内の或る情報を「マーク付け」する。その情報は、ルータの識別情報又は２つの隣接するルータ間のリンクを伝達する。宛先は、異なるルータからのマークを収集した後で、パケットが横断したパスを再構成することができる。
【０００４】
代数的な手法が提案されており、これは、パス情報が、パスに沿ったルータの識別情報によって係数が決定される多項式ｆ（ｘ）にエンコードされるものである。各々のパケットがサンプルｘを搬送し、パスに沿ったすべてのルータが共同でｆ（ｘ）を計算する。宛先は、十分な（ｘ，ｆ（ｘ））値の対を収集した後で、係数を導出し、最終的にルータの識別情報を推論することができる。
【０００５】
他の技術では、各々のルータが、以前に転送されたパケットを長期間にわたって記憶しておくことが必要である。宛先は、ルータが過去に１つのパケットを転送したかどうかをそれらのルータに問い合わせることによって、転送パスを再構成することができる。ルータは、帯域外逆探知メッセージを低い確率でソース又は宛先に送信することもある。これらのメッセージを収集することにより、宛先がパスを構成することが可能となる。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
これらのスキームは、限られた脅威モデルの下で設計されたものであり、多くの用途で、例えば無線メッシュ及びセンサ・ネットワークでは、不十分なものとなる。これらの従来技術のほとんどは、中間ノード（ルータ）が障害を受けないことを想定している。これは、実際には、特にノードが物理的に取り込まれ障害を受けやすい無線メッシュ又はセンサ・ネットワークにおいては当てはまらないことがある。これらのスキームにおいては、障害を受けた単一の中間ノードでさえ、パケットの真の起点が特定されないようにすることができる。障害ノードは、マークを偽造し、恣意的で不正な起点まで逆探知するように犠牲者を欺くことさえある。
【０００７】
さらに、多くのスキームは、加害者の位置を正確に突き止めるために、多数のパケットが収集されること、又は、中間ノードが大量の監査トレースを格納することを必要とする。これらは、インターネットでは問題とならないかもしれないが、帯域幅、エネルギー、及びストレージ・リソースが逼迫した無線メッシュ及びセンサ・ネットワークにおいては、実用上の厳しい障害に直面する可能性がある。
【課題を解決するための手段】
【０００８】
ネットワークにおけるパケット逆探知のためのシステム及び方法は、ネットワーク内の各々のノードについて識別番号（ＩＤ）を保持することと、転送ノードとシンクとの間で共有される秘密鍵を用いて、決定論的方法又は確率的方法のいずれかで、各々の転送ノードにおいてパケットに加えられる署名、例えばメッセージ検証コード（ＭＡＣ）を生成することとを含む。パケットを受信すると、シンクは、署名（ＭＡＣ）が加えられた順序と逆の順序で、パケットの署名（ＭＡＣ）の正当性を検証する。第１の無効な署名（ＭＡＣ）は、偽造レポートを注入した障害ノード又は正当なパケットを改ざんした障害ノードを、オンザフライで明らかにする。
【０００９】
ネットワークにおけるパケット逆探知のための方法は、ネットワーク内の各々のノードについて識別番号（ＩＤ）を保持することと、このノードとシンクとの間で共有される秘密鍵を用いて、各々の転送ノードにおいて署名を生成することと、シンクでパケットを受信したときに、署名が加えられた順序と逆の順序で、シンクによって各々のパケットの署名の正当性を検証することと、偽データ注入ソース及び／又は共謀する障害ノードの位置を求めるために、転送パスにおける署名有効性を判断することと、を含む。
【００１０】
無線メッシュ又はセンサ・ネットワークにおけるパケット逆探知のための別の方法は、ネットワーク内の各々のノードについて真の識別番号（ＩＤ）を保持することと、現在のノード及びシンクのみに知られている秘密鍵に基づいて、真のＩＤから匿名ＩＤを計算することと、少なくとも２つの確率で各々のパケットをマーク付けするために、転送パス内の各々のノードについて秘密鍵を用いてメッセージ検証コード（ＭＡＣ）を生成することと、偽データ注入ソースを発見するために、ネットワーク内のノードについて匿名ＩＤから真のＩＤを求め、各々のパケットに存在するマークを用いてノード・ルートを再構成し、転送パス内の最後の有効ＭＡＣを求めるために、真のＩＤと秘密鍵とを用いて、転送パスの各々のノードを遡って各々のパケットのＭＡＣの正当性を検証することによって、パスを逆探知することと、を含む。
【００１１】
これらの並びに他の特徴及び利点は、添付図面と併せて読まれることになる例示的な実施形態の以下の詳細な説明から、明らかとなるであろう。
本開示によって、添付図面を参照しながら以下の好ましい実施形態の説明において詳細が提示される。
【図面の簡単な説明】
【００１２】
【図１】一実施形態に係る無線ネットワークにおけるノードの転送パスを示す図である。
【図２】受信したパケットの連続番号が許容限界内にあるかどうかを判断して、パケットが正当なものであること又は再現されたものであることを検証するための、現在未発行の連続番号の有界ウィンドウを示す図である。
【図３】本発明の原理に従って検出される共謀ソース及び転送スパイ（例えば、障害を受けたノード）を有する転送パスを含む例示的なネットワークを示す図である。
【図４】本発明の原理に従ってノード順序を再構成するための例示的な方法を示すブロック／フロー図である。
【図５】本発明の原理に従って検出可能な識別情報スワッピングによって作成されたループを示す図である。
【図６】ノードの３つのカテゴリを示す図である。
【図７】転送パス内の有効ＭＡＣを持つ最後のノードを示す図である。
【図８】シンクがｘ個のパケットを受信した後でｎ個の転送ノードすべてからマークが収集される確率の分析結果を示すグラフである。
【図９】シンクがｘ個のパケットを受信した後でｎ個の転送ノードすべてからマークが収集される確率のシミュレーション結果を示すグラフである。
【図１０】最初のｘ個のパケットでシンクによってマークが収集されたノードの平均数を示すグラフである。
【図１１】４０ノードのパスの場合に、候補ソースの組が時間の経過と共に変化することを示すグラフである。
【図１２】１００回の実行で、何回の実行がソースを明確に特定するのに失敗したかを全パス長の関数として示すグラフであり、２００、４００、６００及び８００の曲線は、各々の実行におけるパケット数に対応する。
【図１３】ソースを明確に特定するのに必要な平均のパケット数を全パス長の関数として示すグラフであり、各々の実行において８００個のパケットがシンクで受信される。
【図１４】例示的な実施形態に係る逆探知及びスパイ位置特定のための例示的なシステム／方法を示すブロック／フロー図である。
【発明を実施するための形態】
【００１３】
本発明の実施形態によれば、多数の共謀する加害者の存在の下で加害者ノードの位置を正確に突き止めることができるシステム及び方法が提供される。本発明の実施形態は、脅威がより深刻でリソースがより逼迫している無線メッシュ及びセンサ・ネットワークに特に適用可能である。従来技術とは対照的に、本発明の実施形態は、障害を受けたノードだけではなく障害を受けた転送ノードが存在する場合でも機能し、それらの位置を突き止める。これは、マークの偽造を防止するためにマークに認証符号を加えることにとどまるものではない。従来技術においては、多数の共謀する障害ノードは、無実のノードを辿るように依然として犠牲者をだます可能性がある。本発明の原理によれば、より少ないリソースを用いて回復力のある逆探知が達成され、単一パケットのみを用いて加害者への逆探知を達成することができる。
【００１４】
多くの無線センサ・ネットワークは、潜在的に悪い環境又は敵意のある環境でも機能することが期待される。それらは無人で動作するため、敵が、センサ・ノードを物理的にピックアップして障害し、秘密鍵を含むそれらの格納データを入手するのは容易である。これらの障害を受けた「スパイ（moles）」は、種々のタイプの攻撃を開始することが可能であり、その重大なものの１つは偽データ注入である。１つの単一スパイが、大量の偽装トラフィック（bogus traffic）を注入してシンクを溢れさせ、アプリケーションの不具合を招き、転送パスに沿ったエネルギー及び帯域幅リソースを浪費する可能性がある。最近の研究によって、そうした偽装メッセージを途中で検出してドロップするための多くのスキームが提案されている。しかしながら、それらは、攻撃のダメージを緩和させるだけであるため、すべて受動的なものである。それらは、攻撃の根本原因に反撃して排除するための能動的な手段を提供するものではない。
【００１５】
以下の説明は、能動的な反撃、すなわち、センサ・ネットワーク内のスパイを探知する方法に対応するものである。スパイの位置を知ることで、ネットワークからスパイを分離又は除去して、攻撃の根本原因を撲滅することができる。スパイを探知することは、重要な研究課題を提示する。第１に、ルータがより良好に保護され、エンド・ホストより相対的に信頼されているインターネットとは対照的に、センサ・ネットワーク内のすべてのセンサ・ノードは、敵によって等しくアクセス可能であり、一様に保護されていない。いずれのノードもパケットを転送することができ、相対的に信頼されている活用可能なルーティング・インフラストラクチャは存在しない。第２に、スパイは共謀することができる。スパイは、それらの秘密鍵を共有するだけでなく、それらの形跡を隠すように協働してパケットを操作することができる。そうした操作攻撃は、単に偽装トラフィックの量を増加させることよりはるかに高度である。インターネットのための既存のインターネット・プロトコル（ＩＰ）逆探知スキームは、そうした共謀するスパイを考慮しておらず、このような攻撃の下では効果のないものとなりつつある。
【００１６】
特に有用な実施形態によれば、偽データ注入攻撃における共謀スパイを探知するための入れ子式マーク付け（nested marking）スキームが提示されている。パケット・マーク付けは、パケットの真の起点を推定するために用いられ、ノードは、転送するパケットに自分の識別情報をマーク付けする。こうしたマークを収集することによって、シンクは、ルートを推論し、したがってトラフィックの起点位置を推論することができる。パケット・マーク付けはインターネットで用いられてきたが、共謀するセンサ・スパイに対するその適用可能性は、本発明者らの知るところではまだ研究されていない。ＩＰ逆探知のための既存のマーク付けスキームは、ソースと自分自身の真の位置を隠すようにマークを改ざんするか又はさらにシンクに無実のノードまで辿らせる中間の共謀スパイによって、容易に破られる可能性がある。
【００１７】
本発明の入れ子式マーク付けスキームは、単一パケットの逆探知をサポートする。各々の転送ノードは、パケットを入れ子式にマーク付けし、そのマークが前のすべての転送ノードのマークを保護するようにする。本発明の入れ子式マーク付けスキームは、共謀スパイがマークをどのように操作しても、マークが、ソースの位置又は自分自身の位置のいずれかを明らかにすることを保証する。
【００１８】
センサ・ネットワーク内のスパイに対する事前対応型のセキュリティの必要性は、パケット・マーク付けの枠組み内で、スパイが開始することができる種々の共謀攻撃について検討される。パケット・マーク付けのセキュリティは、入れ子式マーク付けが必要かつ十分であることを含んでおり、すなわち、前のノードのマークの一部が保護されない場合（一見して明らかな多くの設計のように）には、共謀するスパイがソース及び自分自身の位置を隠すか又は無実のノードまで辿るようにシンクをだますことができる攻撃が存在する。本明細書では、分析的評価を通して入れ子式マーク付けの有効性が示される。
【００１９】
本発明の原理による確率的入れ子式マーク付け（ＰＮＭ）スキームは、２つの技術、すなわち入れ子式マーク付けと確率的マーク付けとを用いて、共謀するスパイに対する安全で効果的な逆探知を達成する。入れ子式マーク付けは、単一パケットの逆探知をサポートする。各々の転送ノードは、パケットを入れ子式にマーク付けして、そのマークがすべての前の転送ノードのマークを保護するようにする。入れ子式マーク付けは、共謀スパイがマークをどのように操作しても、マークが、ソースの位置又は自分自身の位置のいずれかを明らかにすることを保証する。確率的マーク付けは、センサの制約されたリソースに合うようにパケットあたりのオーバーヘッドを低減させる。各々のノードは、一定の確率でマークを残し、したがって、パケットはほんのわずかなマークを搬送する。新しいマークが既存のマークに置き換わるインターネット・マーク付けスキームとは異なり、新しいマークが単にパケットに付加される。
【００２０】
本明細書においては、分析的評価と経験的評価との両方を通じてＰＮＭの有効性及び効率が実証される。ＰＮＭは、約５０パケット以内の高速で逆探知を行い、シンクは、最大で２０ホップ離れたスパイを探知することができる。ＰＮＭは、スパイがかなりの量の攻撃トラフィックを注入することができる前にスパイが捕らえられることになるため、スパイが有効なデータ注入攻撃を開始するのを防止する。
【００２１】
共謀攻撃に対して安全な確率的入れ子式マーク付け（ＰＮＭ）のシステム及び方法が提供される。共謀スパイがマークをいかに操作しようと、ＰＮＭは、スパイを一つずつ探知することができる。入れ子式マーク付けは、共謀攻撃に対抗するのに必要かつ十分なものである。ＰＮＭはまた、例えば約５０パケット以内の速い逆探知を行い、シンクから最大で２０ホップ離れたスパイを見つけ出すことができる。これは、事実上あらゆる有効なデータ注入攻撃を防止するものであり、スパイは、大量の偽装トラフィックを注入する前に捕らえられることになる。
【００２２】
本発明の実施形態は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態、又は、ハードウェア要素とソフトウェア要素の両方を含む実施形態の形態をとることができる。好ましい実施形態においては、本発明は、ソフトウェアの形態で実装され、ソフトウェアは、ファームウェア、常駐ソフトウェア、マイクロコードなどを含む。
【００２３】
さらに、本発明は、コンピュータ若しくはあらゆる命令実行システムによって又はそれらと組み合わせて用いられるプログラム・コードを提供するコンピュータ使用可能媒体又はコンピュータ可読媒体からアクセス可能なコンピュータ・プログラム製品の形態をとることができる。この説明の目的のために、コンピュータ使用可能媒体又はコンピュータ可読媒体は、命令実行システム、装置若しくはデバイスによって又はそれらと組み合わせて用いられるプログラムを含み、格納し、通信し、伝搬し、又は転送することができるあらゆる装置とすることができる。媒体は、電子システム、磁気システム、光学システム、電磁気システム、赤外線システム、若しくは半導体システム（又は装置若しくはデバイス）又は伝搬媒体とすることができる。コンピュータ可読媒体の例として、半導体メモリ又は固体メモリ、磁気テープ、リムーバブル・コンピュータ・ディスケット、ランダム・アクセス・メモリ（ＲＡＭ）、リード・オンリー・メモリ（ＲＯＭ）、剛性磁気ディスク及び光ディスクが挙げられる。光ディスクの現在の例として、コンパクト・ディスク−リード・オンリー・メモリ（ＣＤ−ＲＯＭ）、コンパクト・ディスク−読み取り／書き込み（ＣＤ−Ｒ／Ｗ）及びＤＶＤが揚げられる。
【００２４】
プログラム・コードを格納及び／又は実行するのに適したデータ処理システムは、システム・バスを通じて直接的又は間接的にメモリ要素に結合される少なくとも１つのプロセッサを含むものとすることができる。メモリ要素は、プログラム・コードの実際の実行中に使用されるローカル・メモリと、バルク・ストレージと、実行中にバルク・ストレージからコードを取得する回数を減少させるために少なくとも幾つかのプログラム・コードを一時的に格納するキャッシュ・メモリとを含むことができる。入力／出力又はＩ／Ｏ装置（キーボード、ディスプレイ、ポインティング・デバイス等を含むが、これらに限定されない）は、直接的に又は中間のＩ／Ｏコントローラを通して、システムに結合することができる。
【００２５】
中間のプライベート・ネットワーク又はパブリック・ネットワークを通して、データ処理システムを他のデータ処理システム又は遠隔のプリンタ若しくは記憶装置に結合することができるように、ネットワーク・アダプタをシステムに結合することもできる。モデム、ケーブル・モデム、及びイーサネット・カードは、現在利用可能なタイプのネットワーク・アダプタのうちのほんの一部に過ぎない。
【００２６】
ここで、同様の番号が同じ又は類似の要素を表す図面を参照すると、まず図１において、ネットワーク１０は複数のノード１２を含む。転送パス１４内には幾つかのノード１２を配置することができる。各々のノード１２は、シンク・ノード（シンク）と鍵（Ｋ）を共有し、単調に増加する連続番号を保持することができる。ソース・ノード（ソース）Ａは、メッセージＭを送出するときに、そのＩＤと連続番号を付加し、次に署名（例えばメッセージ検証コード）を計算する。ソースは、パケット全体を次のホップ・ノード１に送信し、自分の連続番号を増加させる。同様に、ノード１は、そのＩＤ及び連続番号、さらに別の署名をパケットに付加し、次にその結果を次のホップに渡し、自分の連続番号を増加させる。最終的に、パケットはシンク・ノード シンクに到着する。到着したパケットは、元のメッセージＭだけでなく、ＩＤ、連続番号、及びパス上のすべてのノードの署名を含む。
【００２７】
シンク・ノード シンクは、パケットのＩＤから、パケットが横断したように見えるクレーム・パス（claimed path）を知る。シンクは、このパスを最後のホップ・ノードから始まる逆の順序で検証する。パス上の各々のノードについて、シンクは、ノードと共有された鍵を用いて署名を再計算し、パケットの署名が正しいかどうかを検証する。シンクは、連続番号が有効であるかどうかも検証する。両方のチェックが成功した場合には、シンクは、前のホップの検証を続ける。最終的に、シンクは、すべての署名／連続番号を正しく検証した場合に停止するか、又は、最初の不正な署名／連続番号で停止する。加害者ノードは、シンクが検証を停止したノードの近傍１ホップ以内にある。
【００２８】
署名を計算し、それらがメッセージを「たまねぎ」のようにレイヤ毎に（一度に一つのレイヤ）保護するため、検出されずに前のホップのメッセージを偽造又は修正することができるノードは無い。各々のパケットがホップ毎の連続番号を搬送するため、加害者は、検出されずに古い正当なトラフィックを再現（replay）することはできない。多数の共謀ノードが存在するときには、最初にパス上の最後の加害者の位置が発見され、次いで最後から２番目の加害者の位置が発見され、以下同様にして発見される。これらのノードが、偽装メッセージを注入し、マーク付けを操作し続ける限り、それらの位置は一つ一つ発見されることになる。対照的に、既存のソリューションは、障害を受けた中間ノードを扱わないか、又は、障害を受けた多数のノードが共謀したときには保護を失う。
【００２９】
本発明の原理によれば、障害を受けた多数のノードによって開始された共謀攻撃に対して防衛するための回復力のある逆探知スキームが提供される。各々の転送ノードは、自分自身のマークとすべての前の転送ノードからのマークとを保護するために、署名を入れ子式で用いる。これによって、共謀ノードが存在する場合であっても、障害を受けた攻撃ノードの位置を逆探知することができる。一実施形態においては、決定論的マーク付けが用いられる。しかしながら、すべての転送ノードがパケットにマークを残すため、ネットワークのサイズが大きくなると、メッセージ及び通信オーバーヘッドが増大することになる。したがって、もう１つの実施形態においては、パケットあたりの通信オーバーヘッドを一定レベルに減少させ、共謀攻撃に対するセキュリティ防御を保つことができる、確率的入れ子式マーク付け（ＰＮＭ）スキームが用いられる。
【００３０】
ＰＮＭの実施形態においては、各々の転送ノードは、小さい確率ｐでパケットをマーク付けする。結果として、もう１つの入れ子式マーク付けスキームにおける単純なｎ個のマークとは対照的に、ノードの転送パス上で、１つのパケットが平均してｎ×ｐ個のマークのみを搬送する。単純な拡張のように見えるが、それは２つの点でより複雑な結果となる。
【００３１】
第１に、入れ子式マーク付けスキームへの上記の単純な確率的拡張によって、新しいセキュリティの抜け穴が開くことがある。それにより、パケットの選択的な組をドロップすることによって障害を受けた転送ノードが自分自身と真のソースとの間のいずれかの無実ノードに罪を被せることが可能な選択的ドロッピング攻撃を受けやすくなる。そうした選択的ドロッピング攻撃に打ち勝つために、匿名化技術を採用して、それらのマークにおけるノード識別情報を隠すことができる。
【００３２】
第２に、各々のパケットは、完全なパスの部分的サンプリングのみを搬送することがある。宛先が少数の攻撃パケットを用いてパスを再構成するためのパス再構成方法が提供される。宛先は、再構成されたパスを用いて加害者ノードを特定することができる。
【００３３】
本発明の原理は、従来のマーク付けスキームより強力な防御をもたらすことができる。本発明の実施形態は、形跡を隠蔽するように共謀する多数の障害ノードによって開始される、巧妙な選択的ドロッピング攻撃を含む種々の共謀攻撃に、耐えることができる。好ましい実施形態においては、通信オーバーヘッドが低減され、拡張性が向上するという利点があり、このことによって、中規模ネットワーク又は大規模のネットワークにも適用できるようになる。
【００３４】
再び図１を参照し、Ａがソースである、パスＡ−１−２．．．−Ｚ−Ｚ＋１−．．．−シンクを考える。各々のノード１２は、鍵Ｋをシンクと共有し、例えば、ＡはＫ＿ａを有し、２はＫ＿２を有し、以下同様である。さらに、各々のノードは、ノードがこれまでに生成又は転送したパケットの数を記録する連続番号を保持する。連続番号は、最初にノード１２が配置されたときにはゼロであり、ノード１２がパケットを送出するたびに１だけ増加する。
【００３５】
各々のノード１２はまた、単調に増加するパケット連続番号を保持する。Ａは、メッセージＭを送信するときに、自分の識別情報及び連続番号を付加し、署名（例えば、鍵付きメッセージ検証コード（ＭＡＣ））を計算し、次にパケットＭ全体を次のホップに送信する。各々のホップは同様に、パケットを次のホップに渡す前に、自分自身の識別情報、連続番号、及び署名を付加する。ノードＡは、メッセージＭを送信するときに、自分の識別情報Ａと現在の連続番号（ｓｅｑｎｕｍ）を付加し、次にメッセージ全体を保護する署名を計算する、すなわち、Ｈ＿ｋａ（ｘ）が鍵Ｋ＿ａを用いるｘの署名の計算を示し、「｜」が連結を示すとすると、
Ａ→Ｂ： Ｍ＿ａ＝Ｍ｜Ａ｜ｓｅｑｎｕｍ｜Ｈ＿ｋａ（Ｍ｜Ａ｜ｓｅｑｎｕｍ）
である。このパケット全体は、Ｍ＿ａと表記することができる。Ａは、Ｍ＿ａを次のホップ１に送信し、次に自分の連続番号ｓｅｑｎｕｍを増加させる。ノード１は、同様の操作を行い、以下のパケット、すなわち、
１→２： Ｍ＿ａ｜２｜ｓｅｑｎｕｍ２｜Ｈ＿ｋ２（Ｍ＿ａ｜２｜ｓｅｑｎｕｍ２）
をノード２に送信し、以下同様である。
【００３６】
一般に、パス上の連続する２つのノードＺ、Ｚ＋１について、Ｚは、ＭＺをＺ＋１に送信した後で、ＭＺ＋１、すなわち、
ＭＺ＋１＝ＭＺ｜Ｚ＋１｜ｓｅｑｎｕｍＺ＋１｜Ｈ＿ｋＺ＋１（ＭＺ｜Ｚ＋１｜ｓｅｑｎｕｍＺ＋１）
を次のホップに送信する。シンクは、このようなメッセージを受信したときに、ノードＩＤから、パケットが横断したように見えるクレーム・パスを取得することができる。シンクは、最後のホップ・ノードから始まってパケットを付加した順序と逆の順序でこのパスを検証する。
【００３７】
一般性を失うことなく、シンクがノードＶを検証するケースを考える。シンクは、ＭＺ｜Ｚ＋１｜ｓｅｑｎｕｍＺ＋１｜Ｈ＿ｋＺ＋１（ＭＺ｜Ｚ＋１｜ｓｅｑｎｕｍＺ＋１）であるメッセージＭＺ＋１を有する。ＩＤ Ｚ＋１を取得した後で、シンクは最初に、Ｋ＿Ｚ＋１の知識を用いて署名が正しいかどうかをチェックする。次に、シンクは、連続番号ｓｅｑｎｕｍ Ｚ＋１が正しいかどうかを検証する。そのために、シンクは、各々のノードについての連続番号のスライディング・ウィンドウを保持する。これが決定論的マーク付けの実施形態である。
【００３８】
図１に続いて図２を参照すると、各々のノード１２について、現在のウィンドウ２２は、上限（最大値）と下限（最小値）を有する。上限（最大値）は、このノードから受信した最大の連続番号であり、下限（最小値）は、このノードについて依然として有効な最小の連続番号である。ウィンドウ２２は、順番どおりでない有効な連続番号のどれがまだ受信されていないかを保持する。各々のパケットは、ネットワーク内で存続する（live）最大の時間を有すると仮定され、この最大寿命（Ｔ＿ｍａｘ）は、ウィンドウ２２を更新するのに用いられる。
【００３９】
最初にノード１２が配置されたときには、最小値及び最大値はいずれも０である。シンクがこのノードから連続番号ｄを有するパケットを受信したときには、以下のような３つの可能性のあるケースが存在する。１）ｄ＜最小値：連続番号は、すでに終了しているため、無効である。２）最小値≦ｄ≦最大値：ｄが以前に受信されていない場合には、ｄは有効であり、それが用いられていることを示すマークがｄについて設定される。シンクはまた、最小値を、受信されていない次の最小の有効な連続番号に更新する。しかしながら、ｄが受信されている場合（例えば、ｄがマークされた場合）、それは再現されたものであり、したがって無効な連続番号である。３）ｄ＞最大値：この場合には、連続番号は有効である。さらに、シンクは、最大値＝ｄに設定し、連続番号ｄに関連するタイマーを開始させる。タイマーは、ネットワーク内部のパケットの最大寿命であるＴ＿ｍａｘの後で終了することになる。このタイマーが終了したときに、シンクは最小値＝ｄに設定し、例えば、ｄより小さい連続番号を持つすべてのパケットは、ネットワークにおいて死んだ（died）ことになる。
【００４０】
パス上のノードは、その署名が正しく、その連続番号が有効である場合に限り、シンク検証を渡す。この場合、シンクは、前のホップのＩＤを取得することによって前のホップを検証し続け、署名及び連続番号を検証する。最終的に、検証は、すべての署名／連続番号が正しく検証されるか、又は、不正な署名／無効な連続番号が見つかったときに、停止する。いずれの場合においても、障害を受けたノードは、シンクが停止した場所の近傍１ホップ以内に位置する。例えば、シンクが、第１のホップＭ｜Ａ｜ｓｅｑｎｕｍａ｜Ｈ（Ｍ｜Ａ｜ｓｅｑｎｕｍａ）を含むすべてのノードを正しく検証したときである。真のソースは、ノードＡの近傍１ホップ以内に位置する。あるいは、いずれかのホップにおいて署名又は連続番号が無効である場合には、障害を受けたノードは、無効なノードの近傍１ホップ以内にある。例えば、ホップＸ：Ｍ＿ｗ｜Ｘ｜Ｃ＿ｘ｜Ｈを検証するときである。シンクは、ＨがＨ（Ｍ＿ｗ｜Ｘ｜Ｃ＿ｘ）と一致しないことを発見し、障害を受けたノードがノードＸの近傍１ホップ以内にあると結論づけることができる。すなわち、Ｘは、加害者である（Ｘが、不要なＨを故意に偽造する）か、又は、Ｙのような、Ｘの近傍のうちの１つである（例えば、Ｙは、Ｘの署名Ｈを修正するが、自分自身のメッセージについての正しい署名を与える）かのいずれかである。
【００４１】
提案されるセキュリティ防御は、多くの特徴を含む。第１に、正当なトラフィックを改ざんする加害者を検出することができる。メッセージは署名によってレイヤ毎に保護されるため、メッセージを修正する加害者は、ソースから始まってその直前のホップまで、前のすべてのホップの署名チェックを失敗させることになる。第２に、ＤｏＳ攻撃パケットを注入しようとする攻撃者は、鍵の知識を持たないため、離れた起点を正しく偽造することができない。シンクは、加害者の後で正常なノードによって残された情報を追い、その位置を見つけ出すことができる。第３に、メッセージがホップ毎の連続番号によって保護され、加害者が、古いパケットにおける増加した連続番号について正しい署名を生成することができないため、加害者は、前の正当なトラフィックを再現することができない。多数の攻撃ノードが同じパス上で共謀するときであっても、正当なトラフィックを修正するか又は偽装トラフィックを注入する最後の加害者の位置は、依然として特定されることになる。シンクはさらに、特定された攻撃ノードと通信しないように他のノードに命令し、残りの加害者ノードを一つずつ発見することができる。
【００４２】
モデル及び仮定：システム及び脅威モデルを説明し、悪意のある攻撃の分類法をパケット・マーク付けフレームワーク内で提示する。
【００４３】
図３を参照すると、静的センサ・ネットワーク３０についてのシステム・モデルが描かれており、このモデルは、センサ・ノード１２が一旦配置されると動かないと考えられる。これらのノード１２は、近くの環境を感知し、イベントの時刻、位置、記述など（例えば、センサの読取値）を含む、対象となるイベントに関するレポートを生成する。レポートは、マルチ−ホップ無線チャネルを通じて中間ノード４１−４７によってシンク３８に転送される。シンク３８は、十分な計算リソース及びエネルギー・リソースを持つ強力なマシンである。ルーティングは、比較的安定していると仮定される。ルートは、短い時間間隔で頻繁に変化することはない。ルートが安定しているときには、各々のノード１２は、転送パス３６において近傍に唯一の次のホップを有し、この近傍のホップを通してすべてのパケットをシンク３８に転送する。このことは、当該技術分野では公知であるいずれかのツリー・ベースのルーティング・プロトコル又は地理的ルーティング・プロトコルにおいて一貫している。
【００４４】
各々のセンサ・ノード１２は、固有のＩＤを有し、固有の秘密鍵（Ｋ）をシンク３８と共有すると仮定する。ＩＤ及び鍵は、ノード１２が配置される前にノード１２に予めロードすることができる。シンク３８は、すべてのノードＩＤ及び鍵についてのルックアップ・テーブルを保持することができる。ノードは、近傍の認証などの目的で他の鍵を定めることもできるが、ＰＮＭは、そうした鍵が機能することを必要としない。
【００４５】
センサ・ノード１２は、リソースが制約され、計算力、記憶容量及びエネルギー供給が制限されることがある。例えば、公知のＭｉｃａ２モートは、バッテリ駆動であり、４ＭＨｚのプロセッサ及び２５６Ｋのメモリのみを装備している。そうしたローエンド・デバイスに公開鍵暗号化技術を実装することもできるが、エネルギー消費の点では極めて不経済である。したがって、ここでは簡単にするために、効率的な対称暗号（例えば、安全なハッシュ関数）のみが考慮される。
【００４６】
図３の本発明の例示的なシナリオにおいては、スパイＳ（ソース３２）及びＸ（転送パス・ノード４４）は、攻撃トラフィックを注入するために自分たちの形跡を隠すように協力し、Ｓは偽装レポートを注入する。Ｘ４４は、ノード１、２、３のマーク（５７）を有するパケットを受信する。Ｘは、これらのマークを１’、２’、３’（５５）に変更するか、又は、ノード１のマークを除去する（５６）などというように、マークを種々の方法で操作することができる。スパイの目的は、自分たちの位置を隠すこと、又は、シンクが無実のノードを辿るように導くことである。
【００４７】
脅威モデル及び攻撃分類法：敵は、物理的捕捉又はソフトウェア・バグを通じてセンサ・ノードを障害し、それらのノードを完全に制御することができる。敵は、秘密鍵を含むすべての格納情報にアクセスし、悪意のある状態で挙動するように再プログラムすることができる。スパイは、損害を最大にするように連係する。シンク３８は、通常は良好に保護される。可能性はあるが、障害を受けるシンクは少なく、簡略化するために考慮されない。
【００４８】
逆探知の背景にあるのは、偽データ注入の脅威である。１つのスパイＳ３２は、ソースとして働き、大量の偽装感知レポートをネットワークに注入する。そうしたレポートは、ユーザ・アプリケーションを混乱させるだけでなく、それらを転送するのに費やされるネットワーク・リソース（例えば、エネルギー、帯域幅）を浪費する。逆探知は、積極的な防御に向けた第１ステップである。逆探知によって、シンクがレポートの真の起点を特定できるようになる。次に、シンクは、そうした場所へタスク・フォースを送り出すか、スパイを物理的に除去するか、又は、それらの近傍にトラフィックを転送しないように通知する。正確な機構は変えることができ、ここでの現在の焦点は逆探知にある。
【００４９】
効果的なマーク付けスキームのための課題は、転送パスに沿った共謀スパイＸ４４がマークを任意に改ざんする場合があることである。スパイＸ４４は、自分の位置とソース・スパイ（３２）の位置をいずれも隠すか、又は、シンクが無実のノードを辿るようにだますことができる。位置を隠すことによって、捕まったり罰せられたりすることなく連続注入が可能となる。大きな損害を生じさせるように注入するためには、このように隠すことが必要となる。それらのいずれかの位置が漏洩することによって、ネットワーク分離又は物理的除去といった処罰につながる。シンクが無実のノードを辿るようにだますことは余分なおまけであり、シンクは、無実のノードを処罰して、汚染されていないリソースを切り捨て、効果的に自分自身を処罰する。偽装レポートを注入するＳ及び転送パス上のＸの２つの共謀スパイによるマーク付けベースの逆探知に対する共謀攻撃の分類法が、以下のように提供される。
【００５０】
１）マークなし攻撃：スパイがレポートをまったくマークしないことがある。２）マーク挿入攻撃：ソース・スパイと転送スパイのいずれも、１つ又は多くの捏造マークをレポートに挿入することがある。３）マーク除去攻撃：転送スパイが、レポートにおいて上流のノードによって残された既存のマークを除去することがある。４）マーク並べ替え攻撃：転送スパイが、レポートの既存のマークを並べ替えることがある。５）マーク変更攻撃：転送スパイが、レポートの既存のマークを変更し、それらを無効にすることがある。６）選択的ドロッピング攻撃：転送スパイが、シンクによって受信された場合に逆探知される可能性のあるパケットを選択的にドロップすることがある。７）識別情報スワッピング攻撃：Ｓ及びＸは、互いの鍵を知り、互いになりすますことができる。
【００５１】
例えば、図３は、ソース・スパイＳ ３２とシンク３８との間の７つの転送ノード（４１−４７）のチェーンを示す。ノードＸ４４は共謀スパイである。ノード４４は、ノードＶ１、Ｖ２、Ｖ３によって残された３つの有効なマーク１、２、３を含むＶ３のメッセージを受信する。ノード４４は、これらを１’、２’、３’に変更して無効にすることができ、したがってシンクは、これらのマークを拒絶する。ノード４４は、マーク１を除去して２，３のみを残すこともあり、したがって逆探知は無実のノードで止まる。
【００５２】
【表１】
【００５３】
説明の助けとなるように、表１には、以下で使用される表記を含む。ソース・スパイＳ３２は、正当なフォーマットに適合した偽装レポートを注入する。各々のレポートＭは、イベントＥ、位置Ｌ及びタイムスタンプＴを含む（すなわち、Ｍ＝Ｅ｜Ｌ｜Ｔであり、「｜」は連結を示す）。レポートはまったく同じ内容を含むことはできず、同じ内容を含む場合には、レポートは冗長であるとみなされて正当な転送ノードによってドロップされる。Ｍは、ｎ個の中間ノードのチェーン｛Ｖｉ｝（ｉ＝１，．．．，ｎ）によってシンク３８に転送される。
【００５４】
各々のノードＶｉは、固有のＩＤｉを有し、固有の鍵ｋｉをシンクと共有する。ノードは、ｋが鍵である効果的で安全な鍵付ハッシュ関数Ｈｋ（ ）を用いてノードが生成又は転送するパケットについてのメッセージ検証コード（ＭＡＣ）又は他の署名を生成するために、その鍵を用いることができる。特に、Ｖｉは、前のホップＶｉ−１から受信したメッセージにマークｍｉを加えて、自分自身のメッセージＭｉを構成する。Ｍｉは、ＶｉのＩＤｉ及びＭＡＣ ＭＡＣｉを含むことができる。次いで、Ｖｉは、Ｍｉを次のホップＶｉ＋１に送信する。
【００５５】
転送ノードＶｘ（１＜ｘ＜ｎ）は、共謀スパイであり、Ｘ（４４）と表記される。Ｘは、Ｖｘ−１から受信したメッセージを任意の方法で操作し、次にそのメッセージをＶｘ＋１に渡すことができる。スパイＸは、前述の攻撃のいずれか１つ又はそれらの組み合わせを用いて、Ｓ（３２）及び自分自身の位置を隠すか、又は、無実のノードまで逆探知させることができる。
【００５６】
従来技術の認証マーク付けスキーム（ＡＭＳ）は、ノードによって加えられたマークが前のノードによって残されたマークとの関係を保護しないため、十分なセキュリティを提供することができない。各々のマークは、他のマークの有効性に影響を及ぼすことなく個別に操作することができる。本発明の原理に係る入れ子式マーク付けは、各々のマークとすべての前のマークとの間の結合を確立し、確率的マーク付けは、選択的ドロッピング攻撃に打ち勝つために、付加的な特徴であるＩＤの匿名性を提供する。
【００５７】
ＰＮＭは、疑わしい単一の近傍ホップ内の精度で、偽データ注入攻撃における共謀スパイを探知することができる。これは、１つのノードとその近傍１ホップとを含む。ソース・スパイ又は転送スパイのいずれかは、それらの範囲内にある。ＰＮＭは、２つの技術、すなわち、入れ子式マーク付けと確率的入れ子式マーク付けとを含む。入れ子式マーク付けは、基本的な機構である。入れ子式マーク付けは、シンクがパケットを１つだけ用いて確実にスパイまで逆探知できるようにする。しかしながら、入れ子式マーク付けは、各々の転送ノードがパケットにマークを付ける必要があるため、メッセージ・オーバーヘッドが大きくなるという欠点を有する。大きなセンサ・ネットワークにおいては、これは非効率となる可能性がある。
【００５８】
その後、メッセージ・オーバーヘッドを多数のパケットにわたって分散させるために、確率的マーク付けが用いられる。各々の転送ノードは、一定の確率でマークを付ける。したがって、パケットは、ほんの僅かなマークのみを搬送し、パケットあたりのオーバーヘッドが大きく低減される。これは、メッセージ・オーバーヘッドをより小さくするために検出力を犠牲にする。シンクは、スパイを特定するために多数のパケットを必要とする場合があり、このことは、スパイが重大な損害を引き起こす前に特定される限り、合理的なことである。
【００５９】
基本的な入れ子式マーク付け：パケット・マーク付け：各々の転送ノードＶｉは、シンクと共有する秘密鍵ｋｉを用いて、そのＩＤｉ及び安全なＭＡＣをパケットに付加する。ＭＡＣは、ＶｉがＶｉ−１から受信したメッセージ全体を保護する。すなわち、ＭＡＣｉ＝Ｈｋｉ（Ｍｉ−１｜ｉ）である。例として、近傍のノードによって送信されるメッセージは、
Ｓ→Ｖ１：Ｍ
Ｖ１→Ｖ２：Ｍ１＝Ｍ｜１｜Ｈｋ１（Ｍ｜１）
Ｖ２→Ｖ３：Ｍ２＝Ｍ１｜２｜Ｈｋ２（Ｍ｜２）．．．
Ｖｉ→Ｖｉ＋１：Ｍｉ＝Ｍｉ｜ｉ｜Ｈｋｉ（Ｍｉ−１｜ｉ）
である。
【００６０】
各々のホップにおいて、ＩＤｉは、ルート上にノードｉが存在することを示し、ＭＡＣ Ｈｋｉ（Ｍｉ−１｜ｉ）は、メッセージＭｉを送信するのが確かにノードｉであり、ノードが受信したのがＭｉ−１であったことを、シンクに対して証明する。Ｖｉによって加えられたＭＡＣは、自分自身のＩＤだけでなく前のホップからのメッセージ全体を保護することが理解できる。これが、入れ子式マーク付けの名前の由来である。ＭＡＣは、前のすべてのノードのＩＤ及びＭＡＣ並びにそれらの相対的順序を保護する。前のＩＤ、ＭＡＣ、又はそれらの順序のいずれかが改ざんされることによって、ＭＡＣが無効になる。
【００６１】
以下では、入れ子式マーク付けが安全な逆探知のために必要かつ十分であることを示すために、形式的セキュリティ分析を用いる。すなわち、入れ子式マーク付けはすべての共謀攻撃に耐えることができるが、より簡単な設計はいずれも耐えることができない。例えば、拡張されたＡＭＳにおいては、元のメッセージＭ及びＶｉのＩＤのみが保護されるが、Ｍｉ−１における前のマークへのマーク結合は保護されない。これが、マークが個別に操作されたときにはＡＭＳが役に立たない理由である。
【００６２】
逆探知：パケットＭｎを受信した後で、シンクは、入れ子式マークの過去を検証する。シンクは、まず最後のホップｎのＩＤを取得し、対応する鍵ｋｎを用いて最後のＭＡＣ ＭＡＣｎを検証する。ＭＡＣｎが正しい場合には、シンクは、前のホップｎ−１のＩＤを取得し、ＭＡＣｎ−１を検証する。シンクは、すべてのＭＡＣが正しいことを検証するか、又は、不正なＭＡＣｘを見つけるまで、このプロセスを続ける。スパイ（ソース又は転送のいずれか）は、検証された最後のＭＡＣを持つノードの近傍１ホップ以内（このノード自身を含む）で探知される。
【００６３】
例えば、図３において、スパイＸがノード４１のマークを変えた場合には、ノード４１、４２及び４３からのマークがすべて無効になる。Ｘがマークを残さなかったとき又は無効なマークを残したときには、逆探知はノード４５で止まり、スパイ（Ｘ）はこの停止ノードの近傍１ホップ以内にあり、Ｘが有効なマークを残したときには、逆探知はノードＸで止まり、スパイはこの停止ノードである。
【００６４】
確率的入れ子式マーク付け：確率的入れ子式マーク付けは、各々の転送ノードが小さい確率ｐでパケットをマークするようにする。したがって、ｎノードの転送パス上で、メッセージは、平均してｎｐ個のマークを搬送する。確率ｐは、ｎｐ個のマークのオーバーヘッドが許容可能となるように調整することができる。
【００６５】
不正な拡張：確率的マーク付けへの拡張は、一見して単純なように見える。しかしながら、それは容易なことではないことが分かる。各々のノードが確率ｐでマークするようにすること（以下参照）だけでは、逆探知を無実のノードに導く可能性がある選択的ドロッピング攻撃を受けやすい。
Ｓ→Ｖ１：Ｍ
Ｖ１→Ｖ２（確率ｐ）：Ｍ１＝Ｍ｜１｜Ｈｋ１（Ｍ｜１）
Ｖ２→Ｖ３（確率１−ｐ）：Ｍ２＝Ｍ１｜２｜Ｈｋ２（Ｍ｜２）．．．
Ｖｉ→Ｖｉ＋１（確率ｐ）：Ｍｉ＝Ｍｉ−１｜ｉ｜Ｈｋｉ（Ｍｉ−１｜ｉ）
Ｖｉ→Ｖｉ＋１（確率１−ｐ）：Ｍｉ＝Ｍｉ−１ （１）
【００６６】
図３の例を考える。ＩＤリストはプレーン・テキストであるため、共謀スパイＸは、Ｖ１、Ｖ２、Ｖ３のうちのどれがパケットをマーク付けしたか知ることができる。スパイＸは、Ｖ１のマークを含むすべてのパケットをドロップし、Ｖ２、Ｖ３からのＳマークを持つものだけを転送することができる。シンクが逆探知したときには、逆探知は、近傍の１ホップがいずれのスパイも含まないＶ２で止まることになる。実際には、Ｘは、逆探知を自分自身とソース・スパイとの間のいずれかの無実ノードに導くことができる。
【００６７】
確率的マーク付けにおいては各々のパケットが転送パス上のノードの部分的な「サンプル」のみを搬送するため、この攻撃が機能する。プレーン・テキストＩＤであるため、スパイは、特定の「サンプル」を選択的に渡して、シンクが、Ｘの上流ノードの１つで終わる部分的なパスのみを知るようにする。本発明の原理に係る基本的な入れ子式マーク付け（決定論的マーク付け）においては、すべてのパケットが完全なパスを構成するマークを搬送するため、この攻撃は適用されない。選択的ドロッピングのための部分的な「サンプル」は存在しない。
【００６８】
選択的ドロッピング攻撃に打ち勝つために、転送ノードは、他のノードのどれがパケットをマーク付けしたか伝えることができないことが望ましい。この方法では、共謀スパイは、どのパケットをドロップするかを知ることができない。しかしながら、シンクは依然として、マークを検証するためにどれがマークを残したかを知る必要がある。以下の説明においては、問題を解決するために、すべての秘密鍵に関する付加的な情報と十分な計算リソースとを与えるシンクの非対称性が利用される。
【００６９】
確率的入れ子式マーク付け：正当なノードＶｉは、自分の真のＩＤｉを用いる代わりに、匿名ＩＤｉ’をパケットに用いる。真のＩＤｉから匿名ＩＤｉ’へのマッピングは、Ｖｉとシンクのみが知っている秘密鍵ｋｉによって決まる。共謀スパイは、障害を受けていないＶｉからのｋｉの知識を所有しておらず、したがって、共謀スパイは、匿名ＩＤから真のＩＤを推論することはできない。
【００７０】
Ｓ→Ｖ１：Ｍ
Ｖ１→Ｖ２（確率ｐ）：Ｍ１＝Ｍ｜１’｜Ｈｋ１（Ｍ｜１’）、１’＝Ｈ’ｋ１（Ｍ｜１）
Ｖ１→Ｖ２（確率１−ｐ）：Ｍ１＝Ｍ．．．
Ｖｉ→Ｖｉ＋１（確率ｐ）：Ｍｉ＝Ｍｉ−１｜ｉ’｜Ｈｋｉ（Ｍｉ−１｜ｉ’）、ｉ’＝Ｈ’ｋｉ（Ｍ｜ｉ）
Ｖｉ→Ｖｉ＋１（確率１−ｐ）：Ｍｉ＝Ｍｉ−１ （２）
【００７１】
上記において、Ｈ’（ ）は、匿名ＩＤを計算する別の安全な一方向関数である。匿名ＩＤ ｉ’は、Ｖｉが転送する各々の個別のメッセージについて変化するように、Ｍに結合される。（冗長なコピーとみなされてドロップされることを防ぐために、ソース・スパイによって偽造されるレポートは、異なる内容を有するべきであることを思い出されたい。） これによって、攻撃者が時間とともに蓄積することができる静的マッピングが防止される。拡張ＡＭＳと比べて、確率的入れ子式マーク付けは、入れ子式マーク付けと匿名ＩＤとの両方を有する。
【００７２】
マーク検証：匿名ＩＤを用いると、シンクにおける検証は異なるものとなる。シンクは、最初に真のＩＤを知ることが必要であり、次に対応する秘密鍵を用いてＭＡＣを検証することができる。シンクの十分な計算力を利用して、真のＩＤを見つけるために全数検索を用いることができる。
【００７３】
ノードＶｎからＭｎを受信した後で、シンクは、最初に、ネットワークにおけるあらゆるノードについてのすべての匿名ＩＤを計算する。Ｍを知っていれば、シンクは、すべてのＩＤ ｉをｉ’にマップするためのテーブルを構築することができる。ｉ’を参照することによって、シンクは、真のＩＤ ｉを知る。次に、シンクは、対応する鍵ｋｉを用いてＭＡＣを検証することができる。このようにして、シンクは、すべてのＭＡＣを一つずつ検証することができる。シンクの計算力と、センサ・ネットワークにおけるデータ速度の低さとを前提とすれば、全数検索は実現可能である。シンクは、各々の個別のメッセージＭについて、参照を行うために異なるテーブルを計算する必要がある。マイクロ秒レベルでハッシュ値の計算を行うことができる（例えば、１．６Ｇ ＣＰＵであれば毎秒２５０万回のハッシュ値計算を行うことができる）とすれば、相当に大きなネットワーク（例えば数千ノード）についてこうしたテーブルを構築することは、数ミリ秒のオーダーで行われるべきである。したがって、シンクは、毎秒数百以上のパケットを検証することができる。シンクは、一度に１つのセンサから受信するため、入力するデータ速度は、センサの無線速度によって制限される。数百パケットというのは、すでに、典型的なセンサ・ハードウェア上の現在の実効データ速度より大きい（例えば、Ｍｉｃａ２ モートについては１２ｋｂｐｓであり、毎秒１００パケットを下回る）。
【００７４】
逆探知：スパイを探知することは、２ステップのプロセスとなる。まず、シンクは、十分な数のパケットからマークを収集することによって、ルートを再構成する必要がある（分析されるノードの数は後述される）。次に、シンクは、どのノードがそれらの近傍１ホップ以内にスパイを有するかを特定する。確率的マーク付けが用いられる場合にシンクがどのようにスパイを探知することができるかを示す例示的な方法１が、以下の擬似コードで提供される。
【００７５】
【表２】
【００７６】
【表３】
【００７７】
図４を参照すると、ブロック／フロー図は、一実施形態によりスパイを探知するためのシステム／方法を示す。ルートは、転送パス内のノードの相対的順序（どのノードがどのノードの上流にあるか）を見つけることによって再構成することができる。ブロック１１０において、ルートは、その上流ノードのすべてを決定することによって再構成される。相対的順序を保持するために、マトリクスＭが用いられる。マトリクスは、最初は空である。新しいノードＶｉについて正しいＭＡＣが検証されたときに、ブロック１１２において、Ｖｉに対応するもう１つの行ともう１つの列とがマトリクスに加えられる。１つのパケット内の連続する２つのＭＡＣであるＭＡＣｉ、ＭＡＣｊが正しいことが検証されたときはいつでも、ＶｉはＶｊの上流であり、ブロック１１４のマトリクスにおいてＭ［ｉ，ｊ］がこの関係を記録する（例えば、ｉ，ｊは１に設定される。−１はＶｊがＶｉの上流にあることを意味し、０は未定である）。転送パス上には２つ以上のノードが存在するため、多数のノードが、コイン投げの要領で確率ｐでパケットをマーク付けすることができる（式２を参照されたい）。これらのノードは、パス上の連続セグメントではない場合があり、転送パス上でバラバラに位置する可能性がある。シンクは、より多くのパケットを受信するのにしたがって、このマトリクスを更新し続ける。十分なパケットを前提とすると、シンクは、すべての転送ノード間の上流の関係、すなわち完全なルートを見つけ出すことができる。
【００７８】
シンクは、２つのタイプのルート、すなわち、ループを有しないルート又はループを有するルートを再構成することができる。第１のタイプは、スパイが識別情報スワッピング以外の攻撃を用いたときに発生し、後者は、スパイがマークを残すために識別情報をスワップしたときに発生する。最初のケースでは、スパイを探知することは、最も上流のノードを見つけることと等価である。ソース・スパイは、自分自身でパケットを生成するため、他からパケットを受信せず、最も上流のノードとなることができる。転送スパイが、その上流のノードによって残されたマークを除去した場合には、転送スパイは、最も上流であるように「見える」ことがある。いずれの場合においても、ソース・スパイ又は転送スパイは、最も上流のノードの近傍１ホップ以内にある。
【００７９】
スパイは、識別情報スワッピングを用いてループを作成することもでき（図５参照）、この場合には「最も」上流のノードは存在しない。
【００８０】
図５を参照すると、Ｓ及びＸは、互いの鍵を用いていくつかのパケットについて有効なマークを残し、シンクがノード間の上流関係を再構成するときにＳとＸ（これらのノードを含む）の間のすべてのノードを含むループを生じさせることができる。シンクは、依然として、ループのリンクが破れた場所まで逆探知し、その近傍内のスパイを特定することができる。
【００８１】
ソース・スパイＳ及び転送スパイＸは、いくつかのパケットについては互いの鍵を用い、他のいくつかのパケットについては自分自身の鍵を用いて、有効なマークを残すことができる。シンクは、いくつかのパケットについてはＸの前にＳが現れ、他のパケットについてはＸの後にＳが現れることを見つけることになる。シンクはまた、ＳとＸの間のすべてのノード（ＳとＸを含む）がループ１３０を形成することも見つけることになる。こうしたループにおけるいずれか２つのノードＵ、Ｖについて、ＵはＶの上流と下流の両方に現れる。
【００８２】
しかしながら、この異常は容易に特定することができ、すなわち、シンクは、残りのノードがループからシンク自体にラインを形成していることを見つけることができる。スパイは、このラインにおける最も上流のノードの近傍１ホップ以内で（すなわち、ループがラインと交差する場所で）探知される。
【００８３】
セキュリティ分析：ＰＮＭのセキュリティ強度を代替的なマーク付けスキームと比較する。この分析によって、入れ子式マーク付けが正確であり必要とされることが示される。ＰＮＭは、共謀攻撃にもかかわらずスパイを近傍領域の１ホップ以内まで突き止めることができるが、より簡単な設計はいずれも特定の攻撃の下では失敗している。シンクが、時間の経過と共に十分な数のパケットを受信するのにしたがって、確率的入れ子式マーク付けは、近傍領域の１ホップ以内のスパイを漸近的に突き止めることができる。
【００８４】
入れ子式マーク付けのセキュリティ：マーク付けスキームについての２つの特性、すなわち、１ホップ精度及び連続トレース可能性を最初に定義し、次に、それらが等価であることを証明する。次に、本発明者らの基本的な入れ子式マーク付けスキームの連続トレース可能性を示すことによって、それが１ホップ精度であることを証明する。
【００８５】
定義１（１ホップ精度）：ソース・ノード又は共謀スパイのいずれかの近傍１ホップまで常に辿ることができる場合には、マーク付けスキームは、逆探知において１ホップ精度を有する。
【００８６】
定義２（連続トレース可能性）：転送パス上の連続する２つの正当ノードＵ及びＶを考える（すなわち、Ｖは、Ｕからメッセージを受け取り、次にそれらを転送する）。連続トレース可能マーク付けスキームを用いれば、シンクがＶまで辿った場合には、シンクは常にさらにＵを辿ることができる。
【００８７】
定理１：マーク付けスキームは、それが連続トレース可能である場合に限り、１ホップ精度である。
【００８８】
十分性の証明：逆探知がノードＶで止まり、ノードＶが有効なＭＡＣを有する（転送の逆の順序の）最後のノードであるとする。Ｖは、転送パス上にはない正当ノードである可能性はなく、これは、そうしたノードはこれらのノードが転送しないメッセージについてＭＡＣを生成せず、攻撃者はそれらの秘密鍵を知らないためである。したがって、Ｖは、スパイであるか、又は、転送パス上の正当ノードであるかのいずれかである。Ｖがスパイである場合には、十分性が保たれる。次に、Ｖが正当な転送ノードである場合を考える。
【００８９】
ＵがＶの前のホップである、すなわち、ＶがＵからメッセージを受信するものとする。以下の２つの可能性、すなわち、Ｕが（ソース又は共謀）スパイであるか又はＵが正当ノードであるかの２つの可能性のみが存在する。第１の場合には、ＶがスパイＵの近傍にあるため、十分性が保たれる。一方、連続トレーサビリティの定義によって、逆探知はＵに進み、Ｖでは止まらない。したがって、第２の場合は発生することはない。これで十分性の証明が終わる。
【００９０】
次に、矛盾によって必要性を証明する。マーク付けスキームは連続トレース可能ではないとする。すなわち、シンクが、正当ノードＶまで辿るが、その前の正当ノードＵに進むことはできない場合が存在する。したがって、逆探知は、Ｖで止まり、必ずしもソース又は共謀スパイの近傍である必要はない。定義によれば、このスキームは１ホップ精度ではない。
【００９１】
図６を参照すると、転送パス上に２つのカテゴリのノードが存在する。カテゴリ１は、スパイと、それらのすぐ次のホップであり、カテゴリ２は、正当な近傍ホップを直前に有する正当ノードである。連続トレース可能性のため、逆探知は、カテゴリ２では止まることができない。カテゴリ３のノード（転送パス上にない正当ノード）については、それらのノードは、自分が転送しないメッセージについてマークを残さない。したがって、逆探知は、カテゴリ１のノード内でのみ止まることができる。
【００９２】
１ホップ精度は、逆探知が第１のカテゴリ内で止まることを意味し、連続トレース可能性は、逆探知が第２のカテゴリ内で止まることができない、すなわち、第１のカテゴリ内で止まらなければならないことを意味する。
【００９３】
定理２：入れ子式マーク付けスキームは、連続トレース可能である。
証明：連続する２つの正当転送ノードＵ及びＶを考える。Ｍｕは、ＵがＶに送信するメッセージであり、Ｖは、Ｍｕ｜Ｖ｜Ｈｋν（Ｍｕ｜Ｖ）を次のホップに送信するものとする。シンクがＶを辿ったと仮定する。これは、Ｖが、メッセージＭ’ｕ｜Ｖ｜ＭＡＣ’Ｖ内に検証されたＭＡＣ’Ｖを有するべきであり、再計算されたＭＡＣ（Ｈｋν（Ｍ’ｕ｜Ｖ））が、含まれるＭＡＣ’Ｖと同一であることを発見したことを意味する。攻撃者はｋｖを知らないため、ＭＡＣ’Ｖは、Ｖによって生成されたＭＡＣＶでなければならない。したがって、Ｍ’ｕ及びＭｕは、同一でなければならず、そうでなければ、再計算されたＭＡＣは、Ｖによって生成されたものと一致しないことになる。Ｍｕは正当ノードＵによって送信されるため、Ｍｕにおける最後のマークは、Ｕから正当なＭＡＣを搬送しなければならない。したがって、このＭＡＣを検証することによって、シンクはさらにＵをトレースすることができる。
【００９４】
結論（corollary）１：入れ子式マーク付けスキームは１ホップ精度である。
【００９５】
入れ子式マーク付けの必要性：
定理３：入れ子式マーク付けより少ないフィールドを保護するマーク付けスキームはいずれも、連続トレース可能ではない。
証明：入れ子式マーク付けにおいては、ノードのＭＡＣは、自分自身のＩＤと、前のホップから受信したメッセージ全体との両方を保護する。ここで、ＭＡＣが入れ子式ＭＡＣより少ないフィールドを保護するもう１つのマーク付けスキームｒを考える。ＩＤ又はＭＡＣが後のすべてのノードによって完全には保護されないノードＡが存在しなければならず、そうでなければ、ｒは入れ子式マーク付けスキームとなる。
【００９６】
図７を参照すると、Ｘは、Ｖによって保護されないＡのマークにおけるビットを変更する。したがって、Ｖのマークは依然として正しいが、Ｕのマークは正しくない。次に、シンクはＶまで逆探知するが、さらにＵを辿ることはできない。Ｕが、ＡのＩＤ及びＭＡＣを完全に保護する最後のノードであり、ＶがＵの次のホップであるとする（図７を参照されたい）。すなわち、ＶのＭＡＣによって保護されないいくつかのビットがＡのマークに存在する。Ｖの後の下流にある１つのスパイを考える。スパイは、レポートを適切にマーク付けし、ＶのＭＡＣによって保護されないＡのマークのビットを変更する。この場合においては、Ｖの後における（Ｖを含む）すべてのノードのＭＡＣは正しく、したがって、シンクは、Ｖを辿ることができる。しかしながら、Ａのマークはスパイによって改ざんされるため、ＵのＭＡＣは無効であるように見え、したがって、シンクはさらにＵを辿ることはできない。言い換えれば、ｒは連続トレース可能ではない。
【００９７】
結論２：入れ子式マーク付けより少ないフィールドを保護するマーク付けスキームはいずれも１ホップ精度ではない。
【００９８】
確率的入れ子式マーク付けのセキュリティ：
定理４：確率的入れ子式マーク付けは漸近的に１ホップ精度である。
証明：シンクがノード間の上流関係を再構成するときに、ループが存在しないか又はループが存在するかのいずれかの２つの可能な場合が存在する。ループが存在しないときには、証明は定理２の証明と同様である。転送パス上の連続する２つの正当ノードＵ、Ｖを考える。確率的マーク付けであるため、これらの２つのノードはいずれも、常にパケットにマークを残すわけではない。しかしながら、十分な数のパケットがあれば、それらがいずれも同じパケットにマークを残さない確率（１−ｐ）２ｎは、パケットの数ｎが増加するにつれて徐々に小さくなる。漸近的に、Ｕ、Ｖがいずれもマークを残すパケットが存在することになる。転送スパイは、そうしたパケットをドロップすることができる場合もある。しかしながら、匿名ＩＤを用いるため、転送スパイは、すべてのそうしたパケットを常に正しく推測し、ドロップすることはできない。漸近的に、シンクは、ＵとＶの両方からマークを持つパケットを受信することになる。定理２の同様の推論によれば、シンクは、Ｖまで辿ると、さらにＵを辿ることができる。したがって、逆探知は、Ｖでは止まらない。そのため、逆探知は最も上流のノードで止まることになり、そのノードは、その近傍１ホップ以内（このノード自体を含む）にスパイを有する。
【００９９】
ループが存在するときに、ループとラインとの接合点（ノードＸ）（図５を参照されたい）が、その近傍１ホップ以内（このノード自体を含む）にスパイを有することを矛盾によって証明する。この近傍１ホップ以内のすべての４つのノード（Ｘ、Ｓ、Ａ、Ｂ）が正当ノードであると仮定する。パケットは、ＸからＡに向かってシンクに到着するため、Ａは、Ｘの転送パス上の次の近傍ホップでなければならない。ループもまたノード間の上流関係を表すため、Ｘは、ループ上のその近傍ホップの１つ（Ｓ又はＢ）にもパケットを転送しなければならない。したがって、Ｘは、その転送パス上に２つの次の近傍ホップを有する。しかしながら、ルートが安定しているときには、正当ノードはいずれも、その転送パス上に唯一の次の近傍ホップを有するべきである。したがって、これらの４つのノードはすべてが正当ノードとなることはできず、それらの１つはスパイでなければならない。
【０１００】
この証明の背景として、ループがラインに接続する場所の辺りでは何らかの異常な挙動が存在するに違いないという洞察がある。正当ノードについて、それらは、ルートが安定であるときにはループを形成しない。したがって、そうした異常な挙動は、スパイの存在によってのみ説明することができる。基本的な入れ子式マーク付けにおいては、スパイは、識別情報スワッピング攻撃を開始することができるが、すべてのノードが各々のパケットにマークを残すため、シンクは、上流関係を通じて逆探知する必要はなく、常に直接スパイまで逆探知できることに注意されたい。
【０１０１】
性能評価：
シンクが各々の転送ノードＶ１、．．．Ｖｎからの少なくとも１つのマークを収集するのに必要なパケットの数Ｎを分析する。これがＬパケット以内で行われる確率Ｐ（Ｎ≦Ｌ）＝（１−１−ｐ）Ｌ）ｎを計算することができる。
【０１０２】
図８を参照すると、グラフは、ｎ個のノードからの少なくとも１つのマークがｘパケット以内で収集される確率を示す。パケットが搬送するマークの平均数ｎｐは３に固定される。１０個のノードを含むパスについて、１３パケットを受信した後でシンクがすべてのマークを収集する確率は約９０％である。２０ホップ及び３０ホップのパスについて９０％の信頼度を達成するためには、それぞれ３３パケット及び５４パケットを要する。この結果は、エネルギー及び帯域幅リソースの消費が少ない比較的少数のパケットの後で、シンクがすべてのノードからマークを収集することを示している。
【０１０３】
シミュレーション結果：
図９を参照すると、分析を検証し、分析するのが難しい指標（metrics）をさらに評価するために、シミュレーションを実行した。パケットが平均で３つのマークを搬送するように、異なるパス長さｎに対して確率ｐが調整されている。分析結果を最初に検証した。ノードの数ｎを１０、２０、３０に設定した。各々の実行においてソースから２００パケットが生成され、５０００回の実行にわって結果を平均した。図９には、シンクがｘパケットを受信した後ですべてのノードからマークが収集される確率が示される。この結果は、図８の分析結果と非常に良く一致する。
【０１０４】
図１０は、ｘパケットの後でシンクによってマークが収集されたノードの割合を示す。１０個のノードが存在するときに、平均して９個のノードのマークを７パケット以内で受信することができる。２０個及び３０個のノードのパスについて、９０％のノードからマークを収集するために約１４パケット及び２２パケットを要する。シンクは、数ダースのパケット以内で、どのノードが転送ノードであるかを知る。
【０１０５】
確率的マーク付け（方法１）におけるルート再構成アルゴリズムの性能も評価した。
図１１は、４０ノードのパスにおいて実行された場合に、より多くのパケットが受信されるにつれて、候補となるソースの組がどのように変化するかを示すものであり、ノード０はソース・スパイである。当初、候補リストにはノードＳがある。より多くのマークが受信されるにつれて、部分的なパスの始めにおける新しいノード８、１１、９、１８が加えられる。それらの上流のノードが後で発見された際には、それらはリストから除外される。真のソース０は、２１番目のパケット上で加えられる。８０番目のパケットの後で、０以外の候補ノードは組に残っていない。候補の組が長時間にわたって変化しないままとなったときに、シンクは、スパイを明確に特定することができる。
【０１０６】
十分な数のパケットがなければ、シンクは、候補となるソースの組を減らして明確に真のスパイのみにすることはできない場合がある。どれほど多くのパケットが必要であるかを試験するために、シンクが受信するパケットの数を２００、４００、６００及び８００に変化させた。各々のトラフィック量について、５から５０まで１０の異なるパス長さの各々にわたって１００回のシミュレーションを実行した。シンクがソースを明確に特定しない回数を得た。
【０１０７】
図１２は、４つの異なるトラフィック量について、失敗した実行の回数を全パス長の関数として示す。パス長が２０個までの場合には２００パケットで十分であることが理解できる。方法１は、各々の実行においてソースをほぼ必ず明確に特定し、パスが３０個までの場合には４００パケットで十分である。非常に長いパス（例えば５０個のノード）の場合のみ、失敗の頻度を５％より低く低減させるのに多数のパケット（例えば８００）が必要である。
【０１０８】
ソースを明確に特定するのにシンクが受信すべきパケット数の平均を測定するために、トラフィック量として８００を選択する。図１３は、ソースを特定するのに成功したすべての実行全体にわたって、全パス長の関数としての結果を示す。２０より小さいパス長の場合には、ソースを明確に特定するために、平均して約５５パケットを要する。これは、図９の結果と概ね一致し、５５パケットがあれば、シンクが、２０個のノードのすべてからマークを収集する確率が９９％以上である。４０個のノードのような長いパスの場合でも、シンクは、約２２０パケットの後でソースを明確に特定することができる。この結果によって、ＰＮＭはスパイが有効な偽データ注入攻撃を開始するのをほぼ防止すること、すなわち、スパイがネットワークに十分な損害を引き起こす前にそれらが突き止められることが実証される。
【０１０９】
逆探知精度：ＰＮＭは、１つのノードとその近傍１ホップとを含む近傍１ホップまでスパイを逆探知することができる。それらの１つは、ソース・スパイ又は転送スパイのいずれかである。ソース・スパイが、レポートを注入するときに異なる識別情報を主張する可能性があるため、精度は単一のノードではない。その次の近傍ホップは、どの識別情報が真であるかを伝えることができない。ＰＮＭは、機能するために近傍ホップ間のペアワイズ鍵を必要としない。しかしながら、ペアワイズ鍵の存在は、逆探知精度の改善に役立つことがある。
【０１１０】
ＰＮＭは、一度に１つのスパイを逆探知する。予想されるのは、いくつかのスパイを分離機構がＰＮＭと一緒に機能することである。その機構は、各ラウンドで特定されたスパイを分離するものである。したがって、時間の経過と共に、これらのスパイはネットワークから一つずつ分離される。
【０１１１】
ルーティング動態の影響：スパイ探知アルゴリズムは、ルートが比較的安定であるときに良好に機能する。スパイは通常、短時間に大量のトラフィックを注入して損害を最大にするため、十分なパケットの収集にはあまり多くの時間を必要としない。例えば、スパイが最大無線速度で注入する場合には、シンクは、１０秒以内で、４０ホップ離れたスパイを探知するのに十分な約３００パケットを収集することができる。ルートは、この短い時間の間は安定なままである可能性が非常に高い。
【０１１２】
レポートの再現：ソース・モールは、同じ内容のレポートを何度も再現することができ、したがって、真のＩＤと匿名ＩＤと間のマッピングは、各々の転送ノードについて固定されたままとなる。共謀スパイは、時間の経過と共にそうしたマッピングを蓄積することができるが、こうした攻撃は、冗長メッセージの局所的抑制によって容易に阻止することができる。転送ノードは、同じ内容のレポートを簡単にドロップすることができる。これは、最近遭遇したメッセージの内容（すなわち、イベント、位置及びタイムスタンプ）の署名（例えば、ハッシュ結果）を保持し、受信した署名をそれらと比較することによって行うことができる。
【０１１３】
ソース・スパイは、レポートする真のソース・ノードからの正当レポートを再現することもできる。レポート内容は、依然として正しい情報を提示する。そうしたメッセージを検出してドロップするために、同じ局所的抑制を用いることができる。他の技術も存在する。それらの１つは、各々のノードが送信又は転送する各々のメッセージについて増加する連続番号を各々のノードに保持させることであり、各々のメッセージは、マークの一部として連続番号を含み、ＭＡＣを用いて連続番号を保護する。シンクは、再現されたパケットが同じ連続番号を有することを検出することができる。この技術は上記で説明されたものである。
【０１１４】
ノードは異なる鍵を用いるため、２つの異なるノードの匿名ＩＤは衝突する場合がある（例えば、Ｈ’ｋｉ（Ｍｕ｜ｉ）＝Ｈ’ｋｊ（Ｍｕ｜ｊ））。暗号化サウンド・ハッシュ関数は、こうした衝突を最小にすることができ、すなわち、衝突が発生したときに、シンクは、そうしたパケットを検証から簡単に除外することができる。ＰＮＭにおいては、スパイは、指示されたよりも多くの偽装マークを挿入するか又は高い確率を用いることによって、より高いパケットあたりのオーバーヘッドを負わせることができる。しかしながら、これは、効率を若干低下させるだけであり、シンクは依然としてスパイまで逆探知することができる。
【０１１５】
すべてが攻撃トラフィックを送信する多数のソース・スパイが存在することもある。基本的な入れ子式マーク付けは、パス上のすべての転送ノードのマーク付けによって、依然としてそれらのソース・スパイを特定することができる。これらの多数のソース・スパイの転送パスがバラバラであるときには、ＰＮＭは、異なるパスを個々に構成し、スパイを探知することができる。これらのスパイはまた、それらの識別情報をスワップしてループを作成するが、この場合もシンクをこれらのループとリンクさせる直線ラインを用いて、これらのスパイを一つずつ特定することができる。
【０１１６】
図１４を参照すると、ブロック／フロー図は、無線ネットワークにおける逆探知のためのシステム／方法を示す。ブロック２０２において、ノードのネットワークにおいて各々のノードが識別番号（ＩＤ）（必要に応じて、図２において前述された連続番号）を付与され、それを保持する。ブロック２０４において、一実施形態として、その（真の）ＩＤは、必要に応じて、現在のノード及びシンクによって知られた鍵を用いて又は他の手段によって、そのＩＤからの匿名ＩＤにマッピングされる。匿名ＩＤのマッピングは、現在のパケットのメッセージを用いて各々の転送されたメッセージについて匿名ＩＤを変えることを含む。マッピングは、パケットの内容を用いて各々のメッセージについてマッピングが変わるようにすべきである。これにより、攻撃者が学習することによって蓄積することができる静的マッピングが防止される。ＰＮＭの実施形態においてはこれが好ましい。ブロック２０６において、ノードとシンクとの間で共有される秘密鍵を用いて、署名を、例えばメッセージ検証コード（ＭＡＣ）を、計算するか又は他の方法で求める。ＭＡＣは、転送パスを通過する各々のパケットについて求められる。ブロック２０８において、ＭＡＣを生成するために、鍵に従って前のノードからのパケット又はメッセージのハッシュ値を計算することができる。ＭＡＣは、パケット内の受信メッセージのハッシュ化バージョンを含むことができる。ＩＤは、転送パス内にノードが存在することを示し、ＭＡＣは、ノードがＩＤと関連付けられたパケットを送信したことを証明する。
【０１１７】
ブロック２０９において、パケットがマーク付けされる。ハッシュ化バージョンは、パケットをマーク付けすることを考慮することができ、マーク付けされたパケットは、転送パスを通してノードの順序を与えるために後で用いられる。パケットあたりのオーバーヘッドを低減させるために、各々の転送ノードにおいて確率的にマーク付けを行うことができる。パケットに常にマークを付ける代わりに、転送ノードは、パケットを確率ｐでマーク付けする。転送ノードは、通常通りその匿名ＩＤ及びＭＡＣを加える。転送ノードは、確率１−ｐで何も行わず、単にパケットを次のホップに転送する。次のホップは、同じ確率ｐを用いて、マークを加えるか又は単にパケットをそのまま渡し続けるかを決定する。マーク付けの変化型として、すべてのノードがマークを付ける基本的な決定論的マーク付けと、すべてのノードが一定の確率でマークを付ける確率的マーク付けがある。
【０１１８】
ブロック２１０において、パケットは、転送パスを通ってシンクで受信される。ブロック２１１において、シンクは、十分な数のパケットについてのマークに基づいて、ノードの順序を再構成する。
【０１１９】
シンクで各々のパケットが受信されると、転送パスの各々のノードを遡ってＭＡＣの正当性が検証される。転送パス内の最後の有効ＭＡＣを用いて、偽データ注入ソースを求めるか、又は、パス全体が検証された（例えば、偽データ注入ソースがない）ことを判断する。これは、ブロック２１４において最後のホップ・ノードについてＩＤを取得し、ブロック２１６において最後のホップ・ノードについてＭＡＣを計算し、ブロック２１８において最後のホップ・ノードについてＭＡＣを検証し、ブロック２２０において最後の有効ＭＡＣが求められるまで繰り返すことを含むことができる。ブロック２１６及び２１８は、連続番号を検証するために、図２で説明されたスライディング・ウィンドウを用いることができる。一実施形態においては、ブロック２１３で、ＭＡＣを検証する前に、転送パス内のノード（又はすべてのノード）について匿名ＩＤから真のＩＤが求められる。
【０１２０】
ブロック２２２において、最後の有効ＭＡＣは、１ホップ以内のスパイの位置を示す。ＰＮＭにおいては、ルート再構成（例えば図４を参照されたい）を実行してスパイを探知することができる。基本的な決定論的マーク付け手法の場合には、図４のルート再構成は不要である。ブロック２２４において、スパイは、転送パスにおいて突き止められ、転送パスから除去される。特に有用な実施形態においては、スパイは、転送パス内に複数の共謀スパイを含む。これらのスパイは、ソース・ノード又は転送ノードである場合があり、攻撃のタイプには、マーク挿入攻撃、マーク除去攻撃、マーク並べ替え攻撃、マーク変更攻撃、選択的ドロッピング攻撃、識別情報スワッピング攻撃又はその他の攻撃がある。本発明の原理によれば、スパイは、そのスパイの１ホップ以内で探知できるという利点がある。
【特許請求の範囲】
【請求項１】
ネットワークにおけるパケット逆探知のための方法であって、
ネットワーク内の各々のノードについて識別番号（ＩＤ）を保持することと、
前記ノードとシンクとの間で共有される秘密鍵を用いて、各々の転送ノードにおいて署名を生成することと、
前記シンクでパケットを受信したときに、前記署名が加えられた順序と逆の順序で、前記シンクによって各々のパケットの前記署名の正当性を検証することと、
偽データ注入ソース及び／又は共謀する障害ノードの位置を求めるために、転送パスにおける署名有効性を判断することと、
を含む方法。
【請求項２】
前記ＩＤは、前記転送パス内のノードの存在を示し、前記署名は、前記ノードが前記ＩＤと関連付けられたパケットを送信したことを証明する、請求項１に記載の方法。
【請求項３】
前記署名を生成するために前記鍵に従って前のノードからのパケット全体のハッシュ値を計算することをさらに含む、請求項１に記載の方法。
【請求項４】
署名有効性を判断することは、最後のホップ・ノードについてＩＤを取得し、前記最後のホップ・ノードについて署名を計算し、前記最後のホップ・ノードの前記署名を検証し、最後の有効な署名が求められるまで繰り返すことを含む、請求項１に記載の方法。
【請求項５】
識別番号（ＩＤ）を保持することは、現在のノードと前記シンクとによって知られた前記鍵を用いて前記ＩＤから匿名ＩＤをマッピングすることを含む、請求項１に記載の方法。
【請求項６】
匿名ＩＤをマッピングすることは、現在のパケットのメッセージを用いて、転送された各々のメッセージについての前記匿名ＩＤを変えることを含む、請求項５に記載の方法。
【請求項７】
検証することは、前記転送パス内のノードについての前記匿名ＩＤからＩＤを求めることを含む、請求項６に記載の方法。
【請求項８】
前記転送パスを通してノードの順序を与えるためにパケットをマーク付けすることをさらに含む、請求項１に記載の方法。
【請求項９】
パケットをマーク付けすることは、前記転送ノードの各々において一定の確率で確率的にパケットをマーク付けすることを含む、請求項８に記載の方法。
【請求項１０】
パケットをマーク付けすることは、各々のノードでパケットを決定論的にマーク付けし、各々のパケットについて増加する連続番号を与えることを含む、請求項８に記載の方法。
【請求項１１】
各々のパケットの前記署名の正当性を検証することは、スライディング・ウィンドウを用いて有効な連続番号を求めることを含む、請求項１に記載の方法。
【請求項１２】
前記転送パスからスパイを除去することをさらに含む、請求項１に記載の方法。
【請求項１３】
前記転送パス内の複数の共謀スパイを探知することをさらに含む、請求項１に記載の方法。
【請求項１４】
前記スパイの１ホップ以内のスパイを探知することをさらに含む、請求項１に記載の方法。
【請求項１５】
ネットワークにおけるパケット逆探知のためのコンピュータ可読プログラムを含むコンピュータ・プログラムであって、前記コンピュータ可読プログラムは、コンピュータ上で実行されたときに、前記コンピュータに、
ネットワーク内の各々のノードについて識別番号（ＩＤ）を保持するステップと、
前記ノードとシンクとの間で共有される秘密鍵を用いて、各々の転送ノードにおいて署名を生成するステップと、
前記シンクでパケットを受信したときに、前記署名が加えられた順序と逆の順序で、前記シンクによって各々のパケットの前記署名の正当性を検証するステップと、
偽データ注入ソースを求めるために、転送パスにおける署名有効性を判断するステップと、
を実行させる、コンピュータ・プログラム。
【請求項１６】
無線メッシュ又はセンサ・ネットワークにおけるパケット逆探知のための方法であって、
ネットワーク内の各々のノードについて真の識別番号（ＩＤ）を保持することと、
現在のノード及びシンクのみに知られている秘密鍵に基づいて、前記真のＩＤから匿名ＩＤを計算することと、
少なくとも２つの確率で各々のパケットをマーク付けするために、転送パス内の各々のノードについて前記秘密鍵を用いてメッセージ検証コード（ＭＡＣ）を生成することと、
偽データ注入ソースを発見するために、
前記ネットワーク内のノードについて前記匿名ＩＤから前記真のＩＤを求め、
各々のパケットに存在するマークを用いてノード・ルートを再構成し、
前記転送パス内の最後の有効ＭＡＣを求めるために、前記真のＩＤと前記秘密鍵とを用いて、前記転送パスの各々のノードを遡って各々のパケットの前記ＭＡＣの正当性を検証する、
ことによって、前記パスを逆探知することと、
を含む方法。
【請求項１７】
前記ＩＤは、前記転送パス内のノードの存在を示し、前記ＭＡＣは、前記ノードが前記ＩＤと関連付けられたパケットを送信したことを証明する、請求項１６に記載の方法。
【請求項１８】
前記ＭＡＣを生成するために前記秘密鍵に従って前のノードからのパケットのハッシュ値を計算することをさらに含む、請求項１６に記載の方法。
【請求項１９】
正当性を検証することは、最後のホップ・ノードについて真のＩＤを取得し、前記最後のホップ・ノードについてＭＡＣを計算し、前記最後のホップ・ノードの前記ＭＡＣを検証し、最後の有効なＭＡＣが求められるまで繰り返すことを含む、請求項１６に記載の方法。
【請求項２０】
前記転送パス内の複数の共謀スパイを探知し、前記共謀スパイを除去することをさらに含む、請求項１６に記載の方法。
【請求項２１】
スパイを探知することは、前記スパイの１ホップ以内で実行される、請求項１６に記載の方法。
【請求項２２】
無線メッシュ又はセンサ・ネットワークにおけるパケット逆探知のためのコンピュータ可読プログラムを含むコンピュータ・プログラムであって、前記コンピュータ可読プログラムは、コンピュータ上で実行されたときに、前記コンピュータに、
ネットワーク内の各々のノードについて真の識別番号（ＩＤ）を保持するステップと、
現在のノード及びシンクのみに知られている秘密鍵に基づいて、前記真のＩＤから匿名ＩＤを計算するステップと、
少なくとも２つの確率で各々のパケットをマーク付けするために、転送パス内の各々のノードについて前記秘密鍵を用いてメッセージ検証コード（ＭＡＣ）を生成するステップと、
偽データ注入ソースを発見するために、
前記ネットワーク内のノードについて前記匿名ＩＤから前記真のＩＤを求め、
各々のパケットに存在するマークを用いてノード・ルートを再構成し、
前記転送パス内の最後の有効ＭＡＣを求めるために、前記真のＩＤと前記秘密鍵とを用いて、前記転送パスの各々のノードを遡って各々のパケットの前記ＭＡＣの正当性を検証する、
ことによって、前記パスを逆探知するステップと、
を実行させる、コンピュータ・プログラム。
【請求項１】
ネットワークにおけるパケット逆探知のための方法であって、
ネットワーク内の各々のノードについて識別番号（ＩＤ）を保持することと、
前記ノードとシンクとの間で共有される秘密鍵を用いて、各々の転送ノードにおいて署名を生成することと、
前記シンクでパケットを受信したときに、前記署名が加えられた順序と逆の順序で、前記シンクによって各々のパケットの前記署名の正当性を検証することと、
偽データ注入ソース及び／又は共謀する障害ノードの位置を求めるために、転送パスにおける署名有効性を判断することと、
を含む方法。
【請求項２】
前記ＩＤは、前記転送パス内のノードの存在を示し、前記署名は、前記ノードが前記ＩＤと関連付けられたパケットを送信したことを証明する、請求項１に記載の方法。
【請求項３】
前記署名を生成するために前記鍵に従って前のノードからのパケット全体のハッシュ値を計算することをさらに含む、請求項１に記載の方法。
【請求項４】
署名有効性を判断することは、最後のホップ・ノードについてＩＤを取得し、前記最後のホップ・ノードについて署名を計算し、前記最後のホップ・ノードの前記署名を検証し、最後の有効な署名が求められるまで繰り返すことを含む、請求項１に記載の方法。
【請求項５】
識別番号（ＩＤ）を保持することは、現在のノードと前記シンクとによって知られた前記鍵を用いて前記ＩＤから匿名ＩＤをマッピングすることを含む、請求項１に記載の方法。
【請求項６】
匿名ＩＤをマッピングすることは、現在のパケットのメッセージを用いて、転送された各々のメッセージについての前記匿名ＩＤを変えることを含む、請求項５に記載の方法。
【請求項７】
検証することは、前記転送パス内のノードについての前記匿名ＩＤからＩＤを求めることを含む、請求項６に記載の方法。
【請求項８】
前記転送パスを通してノードの順序を与えるためにパケットをマーク付けすることをさらに含む、請求項１に記載の方法。
【請求項９】
パケットをマーク付けすることは、前記転送ノードの各々において一定の確率で確率的にパケットをマーク付けすることを含む、請求項８に記載の方法。
【請求項１０】
パケットをマーク付けすることは、各々のノードでパケットを決定論的にマーク付けし、各々のパケットについて増加する連続番号を与えることを含む、請求項８に記載の方法。
【請求項１１】
各々のパケットの前記署名の正当性を検証することは、スライディング・ウィンドウを用いて有効な連続番号を求めることを含む、請求項１に記載の方法。
【請求項１２】
前記転送パスからスパイを除去することをさらに含む、請求項１に記載の方法。
【請求項１３】
前記転送パス内の複数の共謀スパイを探知することをさらに含む、請求項１に記載の方法。
【請求項１４】
前記スパイの１ホップ以内のスパイを探知することをさらに含む、請求項１に記載の方法。
【請求項１５】
ネットワークにおけるパケット逆探知のためのコンピュータ可読プログラムを含むコンピュータ・プログラムであって、前記コンピュータ可読プログラムは、コンピュータ上で実行されたときに、前記コンピュータに、
ネットワーク内の各々のノードについて識別番号（ＩＤ）を保持するステップと、
前記ノードとシンクとの間で共有される秘密鍵を用いて、各々の転送ノードにおいて署名を生成するステップと、
前記シンクでパケットを受信したときに、前記署名が加えられた順序と逆の順序で、前記シンクによって各々のパケットの前記署名の正当性を検証するステップと、
偽データ注入ソースを求めるために、転送パスにおける署名有効性を判断するステップと、
を実行させる、コンピュータ・プログラム。
【請求項１６】
無線メッシュ又はセンサ・ネットワークにおけるパケット逆探知のための方法であって、
ネットワーク内の各々のノードについて真の識別番号（ＩＤ）を保持することと、
現在のノード及びシンクのみに知られている秘密鍵に基づいて、前記真のＩＤから匿名ＩＤを計算することと、
少なくとも２つの確率で各々のパケットをマーク付けするために、転送パス内の各々のノードについて前記秘密鍵を用いてメッセージ検証コード（ＭＡＣ）を生成することと、
偽データ注入ソースを発見するために、
前記ネットワーク内のノードについて前記匿名ＩＤから前記真のＩＤを求め、
各々のパケットに存在するマークを用いてノード・ルートを再構成し、
前記転送パス内の最後の有効ＭＡＣを求めるために、前記真のＩＤと前記秘密鍵とを用いて、前記転送パスの各々のノードを遡って各々のパケットの前記ＭＡＣの正当性を検証する、
ことによって、前記パスを逆探知することと、
を含む方法。
【請求項１７】
前記ＩＤは、前記転送パス内のノードの存在を示し、前記ＭＡＣは、前記ノードが前記ＩＤと関連付けられたパケットを送信したことを証明する、請求項１６に記載の方法。
【請求項１８】
前記ＭＡＣを生成するために前記秘密鍵に従って前のノードからのパケットのハッシュ値を計算することをさらに含む、請求項１６に記載の方法。
【請求項１９】
正当性を検証することは、最後のホップ・ノードについて真のＩＤを取得し、前記最後のホップ・ノードについてＭＡＣを計算し、前記最後のホップ・ノードの前記ＭＡＣを検証し、最後の有効なＭＡＣが求められるまで繰り返すことを含む、請求項１６に記載の方法。
【請求項２０】
前記転送パス内の複数の共謀スパイを探知し、前記共謀スパイを除去することをさらに含む、請求項１６に記載の方法。
【請求項２１】
スパイを探知することは、前記スパイの１ホップ以内で実行される、請求項１６に記載の方法。
【請求項２２】
無線メッシュ又はセンサ・ネットワークにおけるパケット逆探知のためのコンピュータ可読プログラムを含むコンピュータ・プログラムであって、前記コンピュータ可読プログラムは、コンピュータ上で実行されたときに、前記コンピュータに、
ネットワーク内の各々のノードについて真の識別番号（ＩＤ）を保持するステップと、
現在のノード及びシンクのみに知られている秘密鍵に基づいて、前記真のＩＤから匿名ＩＤを計算するステップと、
少なくとも２つの確率で各々のパケットをマーク付けするために、転送パス内の各々のノードについて前記秘密鍵を用いてメッセージ検証コード（ＭＡＣ）を生成するステップと、
偽データ注入ソースを発見するために、
前記ネットワーク内のノードについて前記匿名ＩＤから前記真のＩＤを求め、
各々のパケットに存在するマークを用いてノード・ルートを再構成し、
前記転送パス内の最後の有効ＭＡＣを求めるために、前記真のＩＤと前記秘密鍵とを用いて、前記転送パスの各々のノードを遡って各々のパケットの前記ＭＡＣの正当性を検証する、
ことによって、前記パスを逆探知するステップと、
を実行させる、コンピュータ・プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公表番号】特表２０１０−５２８４９６（Ｐ２０１０−５２８４９６Ａ）
【公表日】平成２２年８月１９日（２０１０．８．１９）
【国際特許分類】
【出願番号】特願２０１０−５００２２７（Ｐ２０１０−５００２２７）
【出願日】平成２０年３月１９日（２００８．３．１９）
【国際出願番号】ＰＣＴ／ＥＰ２００８／０５３３２５
【国際公開番号】ＷＯ２００８／１１９６７２
【国際公開日】平成２０年１０月９日（２００８．１０．９）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．イーサネット
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
【公表日】平成２２年８月１９日（２０１０．８．１９）
【国際特許分類】
【出願日】平成２０年３月１９日（２００８．３．１９）
【国際出願番号】ＰＣＴ／ＥＰ２００８／０５３３２５
【国際公開番号】ＷＯ２００８／１１９６７２
【国際公開日】平成２０年１０月９日（２００８．１０．９）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．イーサネット
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
[ Back to top ]