(57)【特許請求の範囲】
【請求項１】
ネットワークのモニタリング方法において、該ネットワークは木構造の形態の連結されたグラフトポロジを持ち、ネットワーク測定データを収集する複数のモニタリングノード、異なるモニタリングノードおよび／または他のメディエータノードから受信したネットワーク測定データを集約するタスクを少なくとも実行する複数のメディエータノード、および該メディエータノードからネットワーク測定データおよび／または集約されたネットワーク測定データを受信する少なくとも一つのルートエンティティを含み、
該ネットワーク測定データの集約が、要約された確率的データ構造へネットワーク測定データを縮約（condense）することによって実行され、
メディエータノードが、パターンチェックが異常なパターンを出力する場合、バックトラッキング処理を始動する
ことを特徴とする、ネットワークのモニタリング方法。
【請求項２】
上記集約されたデータ構造が、ブルームフィルタ（Bloom Filters）、スケッチ（sketches）、またはその組み合わせを含むことを特徴とする請求項１に記載の方法。
【請求項３】
上記メディエータノードの各々が、上記集約されたデータ構造のローカルコピーをキャッシュすることを特徴とする請求項１または２に記載の方法。
【請求項４】
上記メディエータノードの各々が、集約されたデータ構造に対してパターンチェックを実行することを特徴とする請求項１ないし３のいずれかに記載の方法。
【請求項５】
上記バックトラッキング処理が、メディエータノードにより、バックトラッキング要求を子へ発することで始動され、該バックトラッキング要求が、上記異常なパターンに関する情報を含むことを特徴とする請求項１に記載の方法。
【請求項６】
上記メディエータノードの各々が、バックトラッキング要求を受信し、集約されたデータ構造のキャッシュされたコピーを該バックトラッキング要求に対して照合することを特徴とする請求項５に記載の方法。
【請求項７】
メディエータノードが、上記照合の結果メディエータノードの集約されたデータ構造に関与しているいずれかのノードが関連データをログしていることが明らかになった場合、上記バックトラッキング要求をその子へ転送することを特徴とする請求項６に記載の方法。
【請求項８】
上記モニタリングノードによりログされるデータが、バックトラッキング要求が上記モニタリングノードのいずれかに到達した場合、調査されることを特徴とした請求項５ないし７のいずれかに記載の方法。
【請求項９】
上記モニタリングノードが、適切な認証情報を提供するパーティへのみ、収集されたネットワーク測定データに関する情報を開放することを特徴とする請求項１ないし８のいずれかに記載の方法。
【請求項１０】
上記モニタリングノードのログが、タイムアウトに基づいて廃棄されることを特徴とする請求項１ないし９のいずれかに記載の方法。
【請求項１１】
上記モニタリングノードおよび／または上記メディエータノードが、上記確率的データ構造を定期的に生じるよう構成されることを特徴とする請求項１ないし１０のいずれかに記載の方法。
【請求項１２】
モニタリング機能を含むネットワークであって、該ネットワークは木構造の形態の連結されたグラフトポロジを持ち、ネットワーク測定データを収集する複数のモニタリングノード、異なるモニタリングノードおよび／または他のメディエータノードから受信したネットワーク測定データを集約するタスクを少なくとも実行する複数のメディエータノード、および該メディエータノードからネットワーク測定データおよび／または集約されたネットワーク測定データを受信する少なくとも一つのルートエンティティを含み、
該メディエータノードが、該ネットワーク測定データの集約は、要約された確率的データ構造へネットワーク測定データを縮約することによって実行されるよう、構成され、
メディエータノードが、パターンチェックが異常なパターンを出力する場合、バックトラッキング処理を始動する
ことを特徴とするネットワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークのモニタリング方法に関する。該ネットワークは、連結されたグラフトポロジ、特に木構造を持ち、ネットワーク測定データを収集する複数のモニタリングノード、異なるモニタリングノードおよび／または他のメディエータノードから受信したネットワーク測定データを集約するタスクを少なくとも実行する複数のメディエータノード、および該メディエータノードからネットワーク測定データおよび／または集約されたネットワーク測定データを受信する少なくとも１つのルートエンティティを含む。
【０００２】
また、本発明は、モニタリング機能を含むネットワークに関する。該ネットワークは、連結されたグラフトポロジ、特に木構造を持ち、ネットワーク測定データを収集する複数のモニタリングノード、異なるモニタリングノードおよび／または他のメディエータノードから受信したネットワーク測定データを集約するタスクを少なくとも実行する複数のメディエータノード、および該メディエータノードからネットワーク測定データおよび／または集約されたネットワーク測定データを受信する少なくとも１つのルートエンティティを含む。
【背景技術】
【０００３】
モニタリングは、ネットワークの的確な運営およびネットワーク上で動作するサービスの両方に極めて重要である。オペレータは、トラフィックエンジニアリング、サービス品質、セキュリティ、および障害やミスコンフィグレーションの検出を含む様々な目的のためにモニタリングを行う。一般的に、これらのアプリケーションに関するトラフィックは、ネットワークのいくつかのポイントを流れる傾向があるため、それを追跡するために分散モニタリング構造が必要とされる。
【０００４】
残念ながら、リアルタイムおよび分散方法でのトラフィックモニタリングは、さまざまな難しい問題を示している。第一に、スケーラビリティである。モニタされるトラフィック量は、急速に増大し、非特許文献１には、年間グローバルＩＰトラフィック量は２０１２年までにゼタバイトの半分（half a zettabyte, 5x1020 bytes）を超え、その後の各２年で約２倍に達することが記載されている。この増大は、データ収集の集中化を試みているモニタリング基盤を重大なストレス下に置く。他の問題は、プライバシである。モニタリング構造は、エンドユーザのプライバシを侵害することなく、意図された目的を達成することが可能なことを保障すべきだからである。さらに、いくつかのアプリケーション（例えば、法執行、セキュリティ事故レポーティングなど）は、より詳細な情報を取り出すために、元のモニタリングプローブへバックトラックを行う必要がある。この要求は、スケーラビリティやプライバシ保護を実現するために、要約された情報のみをエクスポートする単純なスキームでは解決することができない。
【０００５】
この分野で、いくつかの解決法が存在するが、それらのいずれも上記問題を一度に解決することはできない。
【０００６】
現在、性能およびセキュリティのモニタリング双方に実際使用される多くのモニタリングシステムは、単純化したパラダイムに基づいている。該パラダイムは、いくつかのプローブが異なったポイントを流れるトラフィックをモニタしており、単一のコレクティングデバイスへ観測レポートを送信する。その後、該コレクティングデバイスは、ネットワーク状態のグローバルレポートを発するため、および、場合によってはネットワーク規模の異常を明らかにするために、それぞれのモニタリングノードによって生じたローカルなデータレポートを処理することができる。
【０００７】
残念ながら、このモデルは、モニタされるデータ量の増大に対応しない。上記スケーラビリティ問題を克服するための現在の提案は、収集ポイントに対してモニタされたデータを収集、蓄積、集約、および、さらにエクスポートすることができる中間メディエータノードを使用する。しかしながら、今のところ上記解決法は、相互接続している異なる管理ドメインの問題（つまり、それらは、すべて単一の管理ドメイン用解決法である）を解決していない。残念ながら、ある種の異常（ボットネットアタックがよい例である）を検出するために、異なる管理ドメインで収集されたモニタリングデータの相関が必要とされる。しかしながら、個々のユーザのアイデンティティに関する情報を（間接的にさえ）漏洩する可能性があるデータ開示は、現行法によって一般に妨げられる。
【０００８】
これらの問題の一部に対処するために、いくつかの提案がなされている。ピアツーピアネットワーク技術を活用するモニタリングシステムが設計されている。分散アグリゲーションツリー（distributed aggregation trees, ＤＡＴｓ）に基づく解決法は、システムに対するスケーラビリティを保証するが、今のところ、通常それらは、数個の集約された性能パラメータ（例えば、非特許文献２および非特許文献３を参照されたい）のみのモニタリングに限定されている。さらに、それらは、より高い粒度でネットワークの振舞いをモニタするために必要とされる柔軟性を欠く。いずれのケースでも、それらは、特異な挙動を単一のユーザに帰することを許容せず、またプライバシを考慮しない。さらに、それらは、関連するログの事後監査のためのサポートを提供しない。
【０００９】
一方、特にアラート相関（alert correlation）を対象としたシステム（および、いくつかのケースではアラートの発生元へ折り返しレポートを行うことができるシステム、例えば非特許文献４に記載のシステム）は、いくつかのケースにおいて、異常はグローバルな観点からのみ検出可能であるという事実にもかかわらず、疑わしいイベントを自律的に検出するローカルなプローブの能力に一般的に依存している。さらに悪いことに、それらの多くは、いまだ単一コレクタモデルを適用している。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】"Approaching the zettabyte era"; http://www.cisco.com/en/US/solutions/collateral/ns341/ns525/ns537/ns705/ns827/white_paper_c11-481374.pdf
【非特許文献２】Yalagandula, P. and Dahlin, M. 2004. A scalable distributed information management system. SIGCOMM Comput. Commun. Rev. 34, 4 (Aug. 2004), 379-390. DOI= http://doi.acm.org/10.1145/1030194.1015509
【非特許文献３】2007. WormShield: Fast Worm Signature Generation with Distributed Fingerprint Aggregation. IEEE Trans. Dependable Secur. Comput. 4, 2 (Apr. 2007), 88-104. DOI= http://dx.doi.org/10.1109yTDSC.2007.1000
【非特許文献４】Paul Williams, Kevin Anchor, John Bebo, Gregg Gunsch, and Gary Lamont, CDIS: Towards a Computer Immune System for Detecting Network Intrusions, Proc. 4th Int'l Symp., Recent Advances in Intrusion Detection 2001 , pp. 117-133,Springer-Verlag, Berlin, 2001
【非特許文献５】A. Graham Cormode and A S. Muthukrishnan: "An improved data stream summary: the count-min sketch and its applications." Journal of Algorithms, April 2005, Academic Press, Inc.
【発明の概要】
【発明が解決しようとする課題】
【００１１】
したがって、本発明の目的は、ネットワークのモニタリング方法および冒頭に記載された種類のネットワークの改良およびさらなる展開を行うことである。これは、実装が容易なメカニズムを採用し、異常パターンを検出するための大量のモニタリングデータの効果的な集約がサポートされると同時にユーザプライバシが保護されるように行われる。また、大量のモニタリングノードに対するスケーラビリティは実現されるものとする。
【課題を解決するための手段】
【００１２】
本発明によれば、上記の目的は、請求項１の構成を備えた方法によって達成される。請求項１によれば、本方法は、以下のことを特徴とする。すなわち、ネットワーク測定データの集約は、ネットワーク測定データを要約された確率的データ構造に縮約（condense)することによって実行される。
【００１３】
また、上記目的は、請求項１３の構成を備えたネットワークによって達成される。請求項１３によれば、本ネットワークは、下記のことを特徴とする。すなわち、メディエータノードは、ネットワーク測定データの集約が、要約された確率的データ構造へネットワーク測定データを縮約することによって実行されるよう、構成される。
【００１４】
本発明で認識されたこととして、モニタリングノードによって収集された詳細な情報が縮約される、確率的データ構造の要約を導入することで、バックトラッキングのサポートと共に、効果的であり、プライバシが保護され、およびスケーラブルである集約を実現することができる。この点において、本発明は、関心のあるイベントをログおよびエクスポートしているプローブの位置特定の可能性を維持しながら、各プローブにより生じたネットワーク測定データの集約ができるフレームワークで構成される。測定データは、確率的データ構造を用いる処理に関係するノード間で伝達される。関心のあるイベントを明らかにするため、およびバックトラッキング処理を動作可能とするために、該確率的データ構造の性質が利用されてもよい。
【００１５】
一般的な観点から、本発明の効果は、パターン検出においてマルチドメイン間でやりとりをすることが可能となることである。というのは、モニタされるユーザの匿名性が保護されるからである。これは、従来のマルチドメイン用解決法が実際に適用されることを拒んでいたキーポイントの一つである。また、本発明の効果は、より正確な事後ログを取り出すことができる可能性を依然としてサポートしながら、測定データの集約のためにスケーラブルなネットワークを構築することが可能となることである。ＤＡＴに基づく解決法と比較して、本発明は、高い粒度を保持しながら大量のデータに対応する上でさらなる柔軟性を提供する。バックトラッキング機能により、あるパターンが検出された場合に、完全なデータの記録を確認することが可能となる。従来のアラート相関（例えば、spacedive、またはCids）に関して、本発明は、よりスケーラブルであり、プライバシが保護され、また関連する情報（疑わしい振る舞い）をローカルに検出可能であるプローブには（必ずしも）依存しない。
【００１６】
好ましい実施形態に関して、要約されたデータ構造は、ブルームフィルタ（Bloom Filters）および／またはスケッチ（Sketches）を含んでもよい。それらは、広く配備されている、２つのよく知られた確率的データ構造である。しなしながら、他の実施形態において、他の要約されたデータ構造に同様に対応することができる。ただし、下記の要求を満たす限りにおいてである。第一に、それらは、集約に関して線形でなければならない。すなわち、イベントの２つの集合を要約するデータ構造の集約は、イベントの２つの集合和を要約する類似データ構造と等しくなければならない。第二に、すでに上述の通り、それらは、モニタリングおよび詳細なデータの集約が、プライバシを保護する方法で実行されることを保証するため、非可逆的でなければならない。上記２つの要求に加え、効果的な集約処理に関し、データ構造は、低いメモリ使用量および少ない検索時間であること、すなわち、ログされたキーの数に非依存であることが好ましい。最後に、データ構造は、偽陰性（false negatives）の発生を避けるべきである。一方、偽陽性（false positives）の発生は、基本的に許容される。偽陽性の影響は、ケースバイケースで判断することができる。アプリケーションによって、確率的データ構造の適切な組み合わせを使用することができる。例として、測定データのレポートは、ブルームフィルタと同様にスケッチで構成されてもよい。
【００１７】
効果的なバックトラッキング処理に関して、各メディエータノードは、生じている要約されたデータ構造のローカルコピーをキャッシュしてもよい。
【００１８】
異常なネットワークの振る舞いを検出するために、各メディエータノードは、要約されたデータ構造に対してパターンチェックを実行してもよい。さらに具体的には、メディエータノードは、異常なパターンに対して、集約された要約をチェックするように構成される。これは、モニタしているアプリケーションおよび／または適応したデータ構造に直接依存して異常パターンを定義することによる。異常なパターンの例は、ユーザ（ユーザの集合）に関するイベントカウンタが既定の閾値を超えているという証拠、またはある数のユーザが、明らかに悪意のある活動を実行していると報告された証拠でもよい。また、悪意のあるパターンは、イベントのある種のパターンがネットワークレベルで検出されているという証拠に起因してもよい。さらに、測定データにバリエーションを含むイベントパターンを検出するために、メディエータノードは、過去に受信したレポートのいくつかを、および、適切に現在のレポートと組み合わせることで、ネットワークの振る舞いの変化を追跡するために使用可能なレポートのいくつかを、キャッシュしてもよい。
【００１９】
別の好ましい実施形態に関して、パターンチェックが異常なパターンを出力する場合に、メディエータノードは、バックトラッキング処理を始動してもよい。また、各メディエータノードは、適切に通知するため、対応するネットワーク管理設備へアラームを発してもよい。有利には、バックトラッキング処理の始動に関し、各メディエータノードは、検出された異常パターンに関する詳細を含むバックトラッキング要求を、それぞれの子へ発してもよい。
【００２０】
バックトラッキングの始動指示に基づき、バックトラッキング要求を受信する各メディエータノードは、該バックトラッキング要求に対して、要約されたデータ構造のキャッシュコピーを照合してもよい。照合の結果、メディエータノードの集約されたデータ構造に関与しているいずれかのノードが、関連データをログしていることが明らかになった場合、メディエータノードは、該バックトラッキング要求をその子へ転送する。バックトラッキングの伝搬基準は、アプリケーションおよびデータ構造の両方に依存してもよいことに留意されたい。
【００２１】
バックトラッキング要求が関連するモニタリングノードに到達するたび、ネットワークの異常、起源、および原因の詳細を学ぶため、ログされたデータを広範囲に調査してもよい。この場合、適応したデータ構造の確率的性質に起因して生じる可能性がある偽陽性を廃棄可能とする、より詳細な照合を実行することが有益である。
【００２２】
データのプライバシ保護に関して、モニタリングノードは、必要な認証情報を提示するパーティにのみ詳細な情報を開放するよう構成されてもよい。したがって、個々のユーザの疑わしい振る舞いは、集約で検出することが可能であるが、個々のユーザのアイデンティティに関する情報は、漏洩しない。
【００２３】
集約およびバックトラッキング双方ともにホップ数が限られるため、モニタリングノードは、タイムアウトに基づいて安全にログを廃棄することができる。
【００２４】
習慣的に信頼性のある結果を提供する継続したモニタリング処理に関して、モニタリングノードおよび／またはメディエータノードは、定期的に確率的データ構造を作り出し、ネットワークトポロジ上の親へ転送してもよい。
【００２５】
本発明を好ましい態様で実施するにはいくつもの可能性がある。このためには、一方で請求項１に従属する諸請求項を参照しつつ、他方で図面により例示された本発明の好ましい実施形態についての以下の説明を参照されたい。図面を用いて本発明の好ましい実施形態を説明する際には、本発明の教示による好ましい実施形態一般およびその変形例について説明する。
【図面の簡単な説明】
【００２６】
【図１】ネットワーク変数に関連するカウンタが既定の閾値を超えたか否かを検出する、本発明の第１の実施形態を例示する概略図である。
【図２】異なるモニタリング活動の出力に対して一致するパターンを見つける、本発明の第２の実施形態を例示する概略図である。
【発明を実施するための形態】
【００２７】
本発明の好ましい実施形態に関して、プライバシを保護する集約、およびバックトラッキングという、２つの相補的なメカニズムが認識される。本発明によれば、確率的データ構造が使用され、モニタされるユーザのプライバシを保護しながら両メカニズムを同時に実現することに影響を持つ。
【００２８】
本発明の主要なアプリケーションの一つは、分散化され、クロスドメインに対応したモニタリングアーキテクチャのサポートであろう。このアーキテクチャはスケーラブルであり、モニタされるデータのプライバシを保護し、関連する情報を収集しているプローブの識別によって、事後監査のために元のモニタリングプローブへバックトラッキングすることができるようになる。
【００２９】
図に例示された実施形態を単純化するために、モニタリングノードは、木構造（任意の連結されたグラフでも動作するが）に配置されると仮定される。この木構造において、木の葉は、ネットワークデータを収集しているネットワークプローブ（またはモニタリングノード）を表す。内部のノードは、いわゆるメディエータノード（収集タスクを実行し、最終的には受信したデータの保存、さらには処理およびエクスポートを行う）、またはコレクターノード（最終的にエクスポートを除いたメディエータの全タスクを実行する）のいずれかを表現する。詳細な情報はプローブにより収集され、集約的な、確率的な、およびプライバシ保護的なデータ構造に要約される（ブルームフィルタおよびカウンティング・スケッチ（counting sketches）は、該データ構造の２つの例である）。情報を効果的に集約するほかに、該データ構造は非化逆的である。というのは、特定のユーザに関する情報を漏洩不可能とするためである。したがって、モニタリングおよび詳細なデータの集約は、プライバシを保護する方法（すなわち、発信源のアイデンティティを明らかにすることなしに）で実行される。
【００３０】
木の各メディエータノードで、子から受信している要約された構造が集約され、集約された要約に対してパターンチェック（該情報に関係するアプリケーションに依存する）が実行される。そして、ノードは、バックトラッキングメカニズムをサポートするために該情報をキャッシュし、集約された要約を木の親ノードへ転送する。この処理は、ルート（コレクタ）に達するまで、木の上へ向かって継続する。
【００３１】
実施にあたり、事後監査に関係する情報をログしているプローブは、分散型に配置可能である。これは、パターンチェックが陽性である（例えば、あるホストが生じるトラフィック量によってアラームが発生する）場合、バックトラッキングメカニズムを始動することにより可能となる。
【００３２】
さらに詳細には、ノードは、バックトラッキング伝搬を駆動するために使用されるいくつかの集約された情報とともにバックトラッキング要求を子へ発する。子は、この集約されたデータを自身でキャッシュしたものと相関させ、その結果に基づいて、木の自身の子へバックトラッキング要求を伝搬するかどうか決定する。この手順は、関連する情報をログしている全プローブに達するまで再帰的に継続する。バックトラッキングメカニズムは、使用されているデータ構造の確率的性質に起因する間違った結果（すなわち、関連する情報をエクスポートしていないノードへ発行されるバックトラッキング要求）を無視する廃棄機能をまた含む。データのプライバシを保護するために、モニタリングプローブは、必要な認証情報を提供するパーティへのみ詳細な情報を開放することに留意されたい。
【００３３】
本発明の詳細を説明するために、および現実のシナリオにおける適用性を証明するために、２つの特定の使用事例における実施形態を以下でさらに詳細に説明する。
【００３４】
第１の使用事例において、図１に例示するように、本発明の実施形態は、与えられたネットワーク変数に関するカウンタがネットワークレベルで既定の閾値を超えるかどうか検出するために使用される。この場合、モニタリングノード‐プローブ‐は、閾値を越える可能性があるネットワーク変数の、場合によっては巨大となりうる集合に関する測定結果を収集していることに留意すべきである。個別のカウンタを集約することは、スケーラブルとなり得ない。なぜなら、それは、過度の量のネットワークトラフィックを生み出すからである。しかしながら、バックトラッキング処理により、信頼性のある変数を最終的に識別するために十分な情報を取り出すことが可能となる。
【００３５】
さらに具体的には、図１は、木構造を持つネットワークの一部を例示している。換言すれば、図１の実施形態のフレームワークは、論理的な木トポロジに配置された、モニタリング構造のノードを仮定する。該トポロジにおいて、葉はデータコレクターを表し、中間ノードはデータメディエータノードとして働く。このような抽象化は、ピアツーピアネットワークをベースに築かれる分散アグリゲーションツリー（Distributed Aggregation Trees, ＤＡＴｓ）のように、実際いくつかの種のネットワーク構造を利用していると認識されてもよい。収集およびメディエーション活動は、実際同じ物理ノード上で実行されてもよい。図１で、Ｎ１１、Ｎ１２、Ｎ１３、およびＮ１４で示されるノードは、モニタリングノードとして機能している葉であり、Ｎ２１およびＮ２２で示されるノードは、メディエータノードとして機能している内部ノードである。また、Ｎ３で示されるノードは、集約されたネットワークモニタリングデータすべてがひとつに流れ込むルートである。
【００３６】
一般的な集約およびバックトラッキングメカニズムは、下記のとおり動作する。
・各プローブＮ１１、Ｎ１２、Ｎ１３、およびＮ１４は、トラフィックをログし、集約された確率的データ構造を定期的に作り出し、木の親へ転送する。
・木の各中間ノードＮ２１およびＮ２２は、関連する集約メカニズムを使用して、木の子から受信した情報から、集約された構造を算出し、そして、バックトラッキングを可能とするためローカルコピーをキャッシュする一方で、該情報を木の親へ転送する。中間ノードＮ２１およびＮ２２は、異常なパターンに対して、集約された要約を照合する。
・パターンチェックが陽性の結果を出力した場合は、中間ノードＮ２１およびＮ２２は、関連するネットワーク管理設備へアラームを発し、バックトラッキング処理を始動する。特には、検出したパターンに関するいくつかの詳細を含むバックトラキング要求を各子へ発する。
・バックトラッキング要求を受信する各中間ノードＮ２１およびＮ２２は、バックトラッキング要求に対し、集約されたデータ構造のキャッシュコピーを照合する。照合の結果、集約された要約に関与するノードのいくつかが、関連するデータをログしている可能性を示す場合には、該要求はその子へ転送される。
・バックトラッキング要求が関連プローブのすべてに到達すると、ログされたデータは、広範囲に調査されることができる。
【００３７】
図１に例示された実施形態において、各ネットワーク変数に関連するカウンタを説明するために、カウント-ミン・スケッチ（count-min sketch）データ構造が適応される。該データ構造は、カウンタの大きい配列を要約するために、およびカウンタから異常値を検出するために、文献で広く提案されている（例えば非特許文献５を参照されたい）。
【００３８】
各プローブにより作り出されるスケッチは、木のメディエータノードにより再帰的に集約される。スケッチの集約は、その線形性性質のおかげで、単純にビンワイズ（bin-wise）合計として実行される。図１において、３つの異なる変数Ａ１、Ａ２、およびＡ３が考慮される。例えば、モニタリングプローブＮ１１は、値Ａ１＝３０、Ａ２＝１５、およびＡ３＝１０を検出している。一方、モニタリングプローブＮ１２は、値Ａ１＝４０、Ａ２＝２０、およびＡ３＝１２を検出している。得た結果をメティエータノードＮ２１へ転送した後、該ノードは集約を実行する。
【００３９】
簡単な使用事例において、集約された要約の中からノードが探すパターンは、キーの集約された値を合計したものが、ユーザにより定義された（つまり、オペレータにより定義された）閾値を超えるような、該キーがあるかどうかに基づく。この条件は、スケッチの各行の中で少なくとも１つのビンが閾値を超えるかどうか照合することになる。該照合は、偽陽性（それはバックトラッキング処理で廃棄されるであろう）を生み出す可能性があるが、しかし、確定的に偽陰性を排除する。再度、この段階において、閾値を超える１つのキーが存在するかどうか明らかにできるが、該キーを特定することはできないことが指摘される。それは、バックトラッキングフェーズ後に可能となる。
【００４０】
図１の好ましい構成によれば、変数Ａ１、Ａ２、およびＡ３に関連するカウンタが値１５０を超える場合に、バックトラッキング処理を始動することが意図される。また、関心あるカウンタのローカルな推定値が値４０を超える場合に、バックトラッキングを伝搬することが意図される。メティエータノードＮ２１より得る、集約された要約の中で、既定の閾値を超えるビンは存在しない。よって、該ノードで必要とされる、さらなる活動はない。メティエータノードＮ２２より得る、集約された要約の中で、既定の閾値を超える行（値１５５）が１つ存在する。よって、該ノードで必要とされる、さらなる活動もない。しなしながら、ノードＮ３により得る、集約された要約の中で、両行で既定の閾値を超える（上段は値１６０、下段は値２４７）。したがって、ノードＮ３は、点線の矢印で例示される、バックトラッキング処理を始動する。
【００４１】
バックトラッキングは、下記のとおり実行される。アラームを発するノード（すなわち、本事例ではノードＮ３）は、閾値を越えているビンのインデックスを子へ、すなわちメティエータノードＮ２１およびＮ２２へ、転送する。各子は、ローカルにキャッシュされたスケッチ上の対応するビンを検査する。各子は、それらの最小値を取ることによって、子孫のプローブで観測されたとする、集約されたカウンタ値の推定値を発する。該推定値が既定のバックトラッキング閾値より大きい場合、バックトラッキング要求が次の子へ再帰的に転送される。図１の実施形態において、これは、バックトラッキング要求がさらにモニタリングプローブＮ１２およびＮ１４へ転送される結果となる。モニタリングプローブＮ１１およびＮ１３の場合、カウンタ値の推定値は、既定のバックトラッキング閾値（値＝４０）を超えないため、これらのプローブに対するバックトラキングは、実行されない。
【００４２】
上記のデータ構造の性質、および木トポロジに関する公知の性質を考慮することによって、スケーラビリティおよびプライバシ保護に関し、下記の考察がなされうる。
・各メティエータノードによって処理される状態、処理数、およびメッセージ数は、プローブ数および木の深さに対して一定である。
・集約に関する木の深さ（および、パターンを検出するために必要な照合の最大数）は、プローブ数とともに対数的に増加する。よって、良いスケーラビリティを提供する。
・個々のユーザの疑わしい振る舞いは、集約で検出することが可能であるが、個々のユーザのアイデンティティに関する情報は、漏洩しない。
・集約およびバックトラッキング双方ともにホップ数が限られるため、モニタリングプローブは、タイムアウトに基づいて安全にログを廃棄することができる。
【００４３】
第２の使用事例において、図２に例示するように、アプリケーションの目標は、異なるモニタリング活動の出力に対して一致するパターンを見つけることである。図２では、図１と同様のネットワークトポロジが表現されている。単純化するために、下記が仮定される。すなわち、各プローブは、いくつかのモニタリング活動を実行しているとする。また、各プローブは、それに関して所定の振る舞いが検出される、関連するネットワーク変数のキーの集合を発行するものとする。モニタリング活動のすべてに関連があるとされる、一部のキーを検出するために、モニタリング活動の出力が相関される。
【００４４】
各プローブにおいて、各モニタリング活動は、ブルームフィルタ（Bloom Filters、ＢＦ）を作り出す。該ブルームフィルタは、関連性があるとラベル付けされているネットワークキーの集合を要約する。単純化のため、該ブルームフィルタは、唯一１つのハッシュ関数を使用するよう図２に例示される。すべてのブルームフィルタは、集約のために親ノードへ送信される。メディエータノードは、単純に二進数単位の論理和演算（“or” operation）を実行することで、同じモニタリング活動に関連するすべてのブルームフィルタを集約する。パターンチェックは、集約されたブルームフィルタに対して、ビット単位の論理積（”and”）として実行される。計算結果の配列が、０（ゼロ、zeros）のみで構成される場合は、一致するキーが見つかっていない。そうでなければ、バックトラッキングを始動することができる。
【００４５】
バックトラッキングの照合は、この場合において直接的である。パターンチェック配列の中に組み込まれた二進数のインデックスが、木を伝わっていく（点線の矢印で示されるように）。中間ノードは、自身がキャッシュしたブルームフィルタの中で、一致する二進数を照合する。それらすべてが確定された場合、バックトラッキング要求をその子へ下って伝播する。図２のシナリオでは、バックトラッキング要求は、モニタリングプローブＮ１１およびＮ１３へ伝播されるが、モニタリングプローブＮ１２およびＮ１４へはされない。
【００４６】
上記の説明および添付図面の記載に基づいて、当業者は本発明の多くの変形例および他の実施形態に想到し得るであろう。したがって、本発明は、開示した具体的実施形態に限定されるものではなく、変形例および他の実施形態も、添付の特許請求の範囲内に含まれるものと解すべきである。本明細書では特定の用語を用いているが、それらは総称的・説明的意味でのみ用いられており、限定を目的としたものではない。
【図１】
0005536891.tif 000002
【図２】
0005536891.tif 000003