(57)【要約】      （修正有）【課題】ネットワーク・トラフィックにおける変更のスケッチベースの検出方法を提供すること。【解決手段】一定の少量のメモリを使用し、一定のレコードごとの更新／再構成コストを有する、ｋ配列スケッチと呼ばれる、スケッチ・データ構造の一変形を設計した。そうした要約の上で様々な時系列予測モデルが実施され、それらが大きな予測誤差を有するフローを探すことによって有意な変更を検出する。予測モデル・パラメータを自動的に構成するためのヒューリスティックが提示される。実際のインターネット・トラフィック・データを使用して、このスケッチベースの変更検出方法がフローごとの分析に比べて高精度であり、低計算コスト、低メモリ・コストで実施され得ることが実証される。この技法を大規模コンピュータ・ネットワークにおけるネットワーク異常検出およびトラフィック測定のための基本構成単位として使用することの正当性を実証するものである。【選択図】図２
2005065294.tif 000002
【特許請求の範囲】
【請求項１】
異常なトラフィック・フローを検出する方法であって、
着信データ・フローのスケッチを生成するステップと、
対応する予測誤差を含む前記スケッチの時系列予測を計算するステップと、
前記予測誤差が定められた閾値より大きいときに警報条件を指示するステップと
を含む方法。
【請求項２】
前記スケッチが、キー値および更新値によって前記着信データ・フロー中の各データ項目を識別するために前記着信データ・フローのターンスタイル・モデルを使用するｋ配列スケッチを含む請求項１に記載の方法。
【請求項３】
前記キー値が前記データ項目の宛先インターネット・プロトコル（ＩＰ）アドレスを含む請求項２に記載の方法。
【請求項４】
前記キー値が、前記データ項目の発信元ＩＰアドレス、前記データ項目に関連するポート番号、および前記データ項目に関連するネットワーク・プレフィックスのうちの少なくとも１つを含む請求項２に記載の方法。
【請求項５】
前記更新値が前記データ項目のパケット・サイズを含む請求項２に記載の方法。
【請求項６】
前記更新値が前記データ項目に関連するパケット数を含む請求項２に記載の方法。
【請求項７】
前記計算するステップが、
自己回帰パラメータ（ｐ）、差分パス数パラメータ（ｄ）および移動平均パラメータ（ｑ）を含む自己回帰和分移動平均（ＡＲＩＭＡ）時系列予測モデルを使用して前記時系列予測を計算するステップ
をさらに含む請求項１に記載の方法。
【請求項８】
ｐ≦２、ｄ＝０、ｑ≦２である請求項７に記載の方法。
【請求項９】
ｐ≦２、ｄ＝１、ｑ≦２である請求項７に記載の方法。
【請求項１０】
前記計算するステップが、
各データ項目に適用されるハッシュ関数の数を含む第１のパラメータ（Ｈ）、ハッシュ表サイズを含む第２のパラメータ（Ｋ）、および時間間隔サイズを含む第３のパラメータを含むモデルを使用して前記時系列予測を計算するステップ
をさらに含む請求項１に記載の方法。
【請求項１１】
Ｈが1以上２５以下の値からなる請求項１０に記載の方法。
【請求項１２】
Ｋが１０００以上６４０００以下の値からなる請求項１０に記載の方法。
【請求項１３】
前記第３のパラメータが６０秒以上３００秒以下の値からなる請求項１０に記載の方法。
【請求項１４】
前記計算するステップが、
前記予測誤差の総残余エネルギーを最小限に抑える前記第１のパラメータ、前記第２のパラメータおよび前記第３のパラメータの値を選択するステップ
をさらに含む請求項１０に記載の方法。
【請求項１５】
前記計算するステップが、
移動平均モデル、Ｓ型移動平均モデル、指数加重移動平均モデル、非季節調整ホルト−ウィンターズ・モデルのうちの少なくとも１つを使用して前記時系列予測を計算するステップ
をさらに含む請求項１に記載の方法。
【請求項１６】
前記予測誤差が、前記時系列予測モデルによって生成された予測値と各データ・フローごとの観測値との差として計算される請求項１に記載の方法。
【請求項１７】
前記定められた閾値が、前記予測誤差の推定２次モーメントに基づくものである請求項１に記載の方法。
【請求項１８】
前記着信データ・フローが複数の着信データ・フローを含み、前記生成するステップが各着信データ・フローごとに前記スケッチを生成するステップをさらに含み、前記計算するステップが各生成スケッチごとに前記時系列予測および前記予測誤差を計算するステップをさらに含み、前記指示するステップが、任意の予測誤差が前記定められた閾値を超えたときに前記警報条件を指示するステップをさらに含む請求項１に記載の方法。
【請求項１９】
コンピュータによって実行される、異常なトラフィック・フローを検出する方法を実施するためのコンピュータ可読媒体であって、
着信データ・フローのｋ配列スケッチを作成するスケッチ・モジュールであって、前記ｋ配列スケッチはキー値および更新値によって前記着信データ・フロー中の各データ項目を識別するスケッチ・モジュールと、
各データ項目に適用されるハッシュ関数の数を定義する第１のパラメータ、ハッシュ表サイズを定義する第２のパラメータ、および時間間隔を定義する第３のパラメータを含む、予測値をもたらす時系列予測モデルを使用して予測スケッチを生成すると共に、さらに、前記予測値と観測値との差を含む予測誤差も計算する予測モジュールと、
前記予測誤差の推定２次モーメントに基づいて閾値を定め、前記予測誤差が前記閾値を超えたときには警報条件を指示する変更検出モジュールと
を含むコンピュータ可読媒体。
【請求項２０】
異常なトラフィック・フローを検出する装置であって、
プロセッサと、
前記プロセッサとやりとりし、前記プロセッサに、
着信データ・フロー中の各データ項目をキー値および更新値によって識別する前記着信データ・フローのスケッチを生成し、
対応する予測誤差を含む前記スケッチの時系列予測を計算し、
前記予測誤差の推定２次モーメントに基づいて閾値を定め、
前記予測誤差が前記閾値より大きいときには異常トラフィック条件を指示する
ように指図する複数の処理命令を記憶するメモリと
を含む装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、複数のコンピュータまたはプロセスの調整に関し、詳細には、コンピュータ・ネットワークの監視に関する。
【背景技術】
【０００２】
本出願は、参照によりその全体が本明細書に組み込まれている、２００３年８月１４日にＢａｌａｃｈａｎｄｅｒ  Ｋｒｉｓｈｎａｍｕｒｔｈｙ名義で出願された「ＭＥＴＨＯＤ  ＦＯＲ  ＳＫＥＴＣＨ−ＢＡＳＥＤ  ＣＨＡＮＧＥ  ＤＥＴＥＣＴＩＯＮ」という名称の米国仮特許出願第６０／４９５，３１４号の、合衆国法典第３５巻第１１９条（ｅ）に基づく優先権を主張するものである。
【０００３】
障害や攻撃などのトラフィック異常は、今日のネットワークでは当たり前のことであり、それらを迅速かつ正確に識別することは大規模ネットワーク運営者にとって極めて重要である。その検出は、通常、トラフィックを、トラフィック・パターン（容量、接続数など）での有意の変更を調べる必要のあるフローの集合体として扱う。しかし、リンク速度およびフロー数が増大するに従って、フローごとの状態を保持するのでは、あまりに費用または時間がかかりすぎるようになっている。
【０００４】
トラフィック異常は、今日のネットワーク運営者にとって日常生活から切り離せないものである。一部のトラフィック異常は、予期されるもの、または予期されないが許容されるものである。他のトラフィック異常は、しばしば、フラッシュ・クラウド、ネットワーク要素障害、あるいはサービス不能（ＤｏＳ）攻撃やワームなどの悪意ある活動による性能ボトルネックの兆候であることがある。（多様なソースから入手可能な）大量のデータ・ストリームを迅速に処理する際にそれらに異常挙動がないか検査するための尤もな動機付けが存在するのである。ネットワーク異常検出では２つの基本的手法が一般的である。
【０００５】
第１の手法は「シグニチャベースの」手法であり、既知の異常のシグニチャにマッチするパターンを探すことによってトラフィック異常を検出する。例えば、そうした技法は、いくつかのよくあるＤｏＳツールキットに共通する特性であるアドレスの画一性に基づいてＤｏＳ活動を推論し得る。シグニチャベース方法は、文献や多くのソフトウェア・システムおよびツールキットで広範に探究されている。この手法の１つの限界は、異常シグニチャが予め知られている必要があるという要件である。したがって、それは新しい異常の識別には適用し得ない。また、悪意ある攻撃者は、そのシグニチャを変えることによって、シグニチャベースの検出システムを免れることもできる。迷惑メール発信者がその迷惑メール・メッセージにランダム・ハッシュを導入した場合のフィルタベースの迷惑メール対策システムの失敗においてもそれと類似する点が見られる。
【０００６】
第２の手法は、「統計ベースの」手法である。これは異常の性質および特性に関する事前の知識を必要とせず、したがって、新しい異常または既存の異常の変形の場合でも有効であり得る。統計ベースの手法の非常に重要な一構成要素が変更検出である。これは、過去のトラフィック履歴に基づいて正常な挙動のモデルを導出し、そのモデルと一致しない（分単位から時間単位程度の）短期間の挙動での有意の変更を探すことによってトラフィック異常を検出する。
【０００７】
変更検出は時系列予測および異常値分析との関連で広範に研究されている。その標準的技法には、（指数平滑法やスライディング・ウィンドウ平均法などの）様々な平滑化技法、ボックス−ジェンキンズ自己回帰和分移動平均（ＡＲＩＭＡ）モデル化、そして最後に、より最近のウェーブレットベースの技法が含まれる。
【０００８】
従来技術の処理では、これらの技法をネットワーク障害検出および侵入検出に適用している。障害検出の例には、正常なトラフィック挙動からの統計的偏差に基づいて障害を識別するもの、ネットワーク・トラフィックの時系列モデルで閾値を適用することによって異常な挙動を識別する方法、ニューラル・ネットワーク、マルコフ・モデル、およびクラスタリングを含む侵入検出の方法、および様々な種類の異常の特徴付けを提供すると共にウェーブレットベースの変更検出方法を提案するものが含まれる。
【０００９】
残念ながら、既存の変更検出技法は、通常、比較的少数の時系列だけしか処理しない。これは、高度に集約されたトラフィック・データ（例えば、簡易ネットワーク管理プロトコル（ＳＮＭＰ）リンクは、５分のサンプリング間隔でカウントする）での変更検出には十分であると考えられるが、それらの技法は、ネットワーク・インフラストラクチャ（インターネット・サービス提供者（ＩＳＰ））レベルでの必要にまで拡張することができない。ＩＳＰレベルでは、トラフィック異常が集約されたトラフィックの内部に埋もれている可能性があり、それらを露出させるために、ずっと低い集約レベル（インターネット・プロトコル（ＩＰ）アドレス・レベルなど）でのトラフィックの検査が要求される。
【００１０】
今日のトラフィック量およびリンク速度を考えた場合、適切な検出方法は、場合によっては、数百万以上の同時ネットワーク時系列を処理できる必要がある。フローごとに既存の技法を直接適用するのでは、そうした大量のデータ・ストリームの必要にまで拡張することは不可能である。最近の研究成果の中には、会計および異常検出のための拡張可能な「長打者型」検出技法の開発を対象としているものもある。しかし、長打者型技法は、必ずしも、有意の変更が行われているフローに対応するとは限らず、したがって、それらの技法が変更検出をサポートするようにどのようにして適合され得るかは明らかでない。
【００１１】
【特許文献１】米国仮特許出願第６０／４９５，３１４号
【発明の開示】
【発明が解決しようとする課題】
【００１２】
したがって、多数のフローを有する大量のデータ・ストリーム中の有意の変更を検出するための、効率がよく、正確で、拡張可能な変更検出機構が求められている。
【課題を解決するための手段】
【００１３】
したがって、本開示の目的は、スケッチを使用してトラフィック・データのコンパクトな要約が構築される様々な装置上で実施される方法を提示することである。具体的には、スケッチ・データ構造の一変形であるｋ配列スケッチが提示される。ｋ配列スケッチは、一定の少量メモリ使用し、一定のレコード当たりの更新／再構成コストを有する。その線形性は、様々なレベルでのトラフィックの要約を可能にする。次いで、そうした要約の上で、大きな予測誤差を有するフローを探すことによって有意の変更を検出する様々な時系列予測モデル（ＡＲＩＭＡ、ホルト−ウィンターズなど）が実施される。それらのモデル・パラメータを自動的に構成するヒューリスティックも提示される。
【００１４】
稼動中の第１層ＩＳＰからの大量の実際のインターネット・トラフィック・データを使用して、このスケッチベースの変更検出方法が高精度であり、低計算コスト、低メモリ・コストで実施され得ることが示される。その結果は、開示の方法が、ネットワーク異常検出およびトラフィック測定に確実に使用され得ることを示すものである。
【００１５】
以下で述べる本開示の様々な実施形態の詳細な説明を、添付の図面と併せて検討すれば、本開示のさらなる態様がより容易に理解されるであろう。
【発明を実施するための最良の形態】
【００１６】
データベース研究界では、大量のデータ・ストリームに及ぶ計算が過去数年にわたって盛んに研究されている。このデータ・ストリーム計算の新たな分野は、データ・ストリーム中の各タプルに１回（または少数回）だけしか接触できないときに、空間的効率および時間的効率のよい方式で実施され得る様々な計算の態様を扱う。
【００１７】
特に効果的な一技法が、「スケッチ」という、大規模なストリーミング・データセットを分析するために提案された確率的要約技法である。スケッチは、ランダムなベクトルに沿った予測を使用し、次元数削減によってフローごとの状態保持を回避する。スケッチには、データ・ストリーム計算に際して非常に有用であることが証明されているいくつかの興味深い特性がある。スケッチは空間的効率が高く、立証可能な確率的再構成精度保証を提供し、直線的である（すなわち、各スケッチは算術的な意味で結合され得る）。
【００１８】
次に、スケッチベースの変更検出プロセスについて説明する。このプロセスでは、多数のネットワーク時系列を有する大量のデータ・ストリームにおける有意の変更の検出が達成されるように、変更検出にデータ・ストリーム計算技法が組み込まれる。スケッチベースの変更検出では、スケッチを用いてトラフィック・データのコンパクトな要約が生成される。本明細書で説明するスケッチ・データ構造の一変形は、「ｋ配列スケッチ」と呼ばれ、一定の少量のメモリを使用し、一定のレコードごとの更新／再構成コストを有する。そうした要約の上で、様々な時系列予測モデル（ＡＲＩＭＡ、ホルト−ウィンターズなど）を実施することができ、それらは大きな予測誤差を有するフローを探すことによって有意の変更を検出する。上位フローのリスト中の有意の差異を迅速に計算し得るので、潜在的異常を指し示すことが可能になる。予測が計算される時間の長さ、および有意の変更の期間に応じて、このプロセスは、異常の有無を正確に識別することができる。異常には、（フラッシュ・クラウドのような）害のないトラフィックの急上昇も、攻撃もあり得ることに留意されたい。それらのモデル・パラメータを構成するためのヒューリスティックも同様に提示される。
【００１９】
大量の実際のインターネット・トラフィック・データを使用して、このスケッチベースの変更検出方法が、フローごとの分析に比べて高精度であり、より低い計算コスト、メモリ・コストで実施され得ることが実証された。評価は、ある期間における上位フローのリストが効率よく正確に再構築され、フローごとの技法と比べると同様の予測誤差を生じることを示すものである。したがって、この方法は、ネットワーク異常検出の基礎として容易に使用することができる。
【００２０】
次に、図１〜１８を参照すると、本開示の類似の構成要素が類似の方式で参照されており、ネットワーク・トラフィックでの変更のスケッチベースの検出方法および装置の様々な実施形態が開示されている。
【００２１】
図１に、本開示の諸プロセスが実施され得る例示的計算処理環境１００を示す。可能な一実装形態として、一般に、ＩＢＭによって製造される種類の企業ネットワーク・サーバや分散サーバのグループなどのサーバ１０２が、ローカル・エリア・ネットワーク（ＬＡＮ）１０６と、インターネットなどのより広域の計算処理環境との間のゲートウェイとして実装される。このプロセスは、サーバ１０２によって直接実施することも、そうではなく、個人用計算処理端末、コンピュータ・ワークステーション、着信データ・フローの監視タスクを担う別の１つまたは複数の専用サーバなど、別個の計算処理機器１０４上で実施することも可能である。そうした実施形態では、計算処理機器１０４は、サーバ１０２より前、サーバ１０２と同時、あるいはサーバ１０２より後にデータ・フロー入力を受け取ることができる。
【００２２】
ＬＡＮ１０６は企業ネットワーク環境などとすることができ、任意の小サイズから大サイズまでの互いに異なる稼動中の１つまたは複数の計算処理環境、および１つまたは複数のネットワーク・プロトコルを含み得る。具体的な一実施形態では、サーバ１０２、端末１０４およびＬＡＮ１０６は、しばしばＤｏＳ攻撃およびその他のトラフィック異常の対象となることのある、インターネット・サービス提供者などによって運用される。計算処理環境１００の他の実装形態も同様に適応させることが可能である。
【００２３】
サーバ１０２または計算処理機器１０４へのインストール後の、スケッチベースの変更検出プロセス２００の動作を図２の流れ図に要約する。プロセス２００によれば、選択された連続時間間隔での着信データ・フローのｋ配列スケッチが生成される（ステップ２０２）。各ｋ配列スケッチごとに予測スケッチおよび予測誤差を生成するために、時系列予測が実施される（ステップ２０４）。予測誤差のいずれかが定められた閾値を超えた場合（ステップ２０６）には、プロセスは異常フローを識別し、警報条件をトリガする（ステップ２０８）。そうでない場合には、着信データ・フローの監視を続行する。
【００２４】
スケッチベースの変更検出プロセスの使用可能な枠組みの概要を提示する以下の詳細な考察で、ステップ２０２〜２０６の具体的実装形態について説明し、続いて、プロセス２００を実装するための企図されるソフトウェア・モジュール、プロセス２００をテストするための実験的セットアップ、および種々の大規模な実際のデータセット上でのスケッチベースの変更検出のテスト結果について詳細に論じる。
【００２５】
過去数年間に、時系列モデル、キャッシュ・レジスタ・モデル、ターンスタイル・モデルを含めて、データ・ストリームを記述するための様々なモデルが提案されている。以下の考察では、最も一般的なモデルである、ターンスタイル・モデルが想定されているが、他のそうしたモデルも同様に適応させることができる。選択されたモデルに従って、Ｉ＝α１、α２、・・・を、項目別に順次に到着する入力ストリームとする。各項目
【数１】
2005065294.tif 000003
は、キー
【数２】
2005065294.tif 000004
と（おそらく負の）更新
【数３】
2005065294.tif 000005
からなる。各キーａ∈［ｕ］に関連付けられるのは時変信号Ａ［ａ］である。新しいデータ項目（ａｉ，ｕｉ）が到着するたびに、その基礎をなす信号Ａ［ａｉ］が更新される（Ａ［ａｉ］＋＝ｕｉ）。変更検出の目的は、その挙動に有意の変更を有するすべてのそうした信号を識別することである。
【００２６】
ターンスタイル・モデルは、キー値および更新値の具体的定義を用いて様々にインスタンス化され得る。ネットワーク異常検出の状況では、キーは、発信元および宛先ＩＰアドレス、発信元および宛先ポート番号、プロトコル番号など、入力データ・ストリームからのデータ項目のパケット・ヘッダ中の１つまたは複数のフィールドを使用して定義され得る。また、より高度の集約を実現するために、ネットワーク・プレフィックスや自律システム（ＡＳ）数などのパラメータ値を用いてキーを定義することも可能である。
【００２７】
更新値は、１パケットのサイズ、（フロー・レベルのデータが利用可能なときには）１フロー中の合計バイト数またはデータ・パケット数とすることができる。しかし、パラメータ空間を扱いやすいサイズ内に保つためには、キー値、更新値として、それぞれ、宛先ＩＰバージョン４（Ｉｐｖ４）アドレス、バイト数が容易に使用できる。キー値および更新値に他の選択を使用することもでき、その中には、計算処理機器上でのプロセス２００の実行時間に影響を与え得るものもある。
【００２８】
無限のリソースを備える理想的環境では、フローごとに時系列予測および変更検出を実施することができるはずである。具体的には、時間が別個の間隔Ｉ１、Ｉ２・・・に分割され得る。各時間間隔Ｉｔ、および間隔Ｉｔの前またはその間に現れる各信号Ａ［ａ］ごとに、観測値を、間隔Ｉｔ
【数４】
2005065294.tif 000006
の間のＡ［ａ］への全更新として計算することができ、式中、指標セット
【数５】
2005065294.tif 000007
はＩｔの間に到達する。次いで、過去の間隔での観測値に予測モデルを適用することによって予測値ｆａ（ｔ）を求めることができる。次いで、予測誤差ｅａ（ｔ）＝ｏａ（ｔ）−ｆａ（ｔ）を求めることができ、一定の検出基準に従って、ｅａ（ｔ）が有意である場合には常に警報が指示される。
【００２９】
ただし、現実には、前述したように、着信データ・フロー中に存在する信号数が非常に大きくなり得るため、フローごとの分析が無理であることもある。例えば、発信元および宛先ＩＰｖ４アドレスがキーとして使用された場合、キー空間［ｕ］は２６４もの大きさになることがあり、今日のトラフィック量およびリンク速度を考えると、その信号数は、容易に、何千万にも達し得る。したがって、フローごとに変更検出を実施するのでは時間がかかりすぎ、あるいは高く付きすぎることがある。
【００３０】
本明細書に提示する解決法は、入力ストリームを要約するためのスケッチを作成し、次いで、それらのスケッチの上で様々な予測モデルを実施するものである。このスケッチベースの変更検出プロセス２００は、スケッチ・モジュール、予測モジュール、および変更検出モジュールという３つの基本モジュールとして実施され得る。
【００３１】
スケッチ・モジュールは、各時間間隔Ｉｔ中のすべての観測値ｏａ（ｔ）（信号Ａ［ａ］への全更新）を要約する空間的および時間的効率のよいスケッチ（観測スケッチＳｏ（ｔ））を作成する。予測モジュールは、過去の間隔での観測スケッチに基づくいくつかの予測モデルを使用して、予測スケッチＳｆ（ｔ）を生成する。次いで、Ｓｏ（ｔ）とＳｆ（ｔ）との間の差分として、予測誤差スケッチＳｅ（ｔ）を計算する（Ｓｅ（ｔ）＝Ｓｏ（ｔ）−Ｓｆ（ｔ））。スケッチ・データ構造の線形性によって、様々な予測モデルを実施し、予測誤差をスケッチ・レベルで直接計算することが可能になる。変更検出モジュールは、誤差スケッチＳｅ（ｔ）を使用して有意の（すなわち異常な）変更を識別する。次に、これらのモジュールによって実施される機能について説明する。
【００３２】
（ａ１，ｕ１）、（ａ２，ｕ２）・・・を入力ストリーム（例えば，所与の時間間隔の間に観測されるχのサブストリーム）とする。各キーａ∈［ｕ］ごとに、
【数６】
2005065294.tif 000008
とし、式中、
【数７】
2005065294.tif 000009
は指標セットである。
【００３３】
各間隔ごとに、その「２次モーメント」（Ｆ２）が、すべてのキーに関連する値の二乗の合計、すなわち、
【数８】
2005065294.tif 000010
として定義される。この２次モーメントの二乗根
【数９】
2005065294.tif 000011
を「Ｌ２ノルム」と呼ぶ。
【００３４】
スケッチ・モジュールは、スケッチ・データ構造を使用して各時間間隔中のすべてのｖａを要約する。スケッチは、ランダム・予測に基づく確率的要約データ構造である。このスケッチ・データ構造の一変形を設計してあり、それを「ｋ配列スケッチ」と呼ぶ。このｋ配列スケッチは、最近他で提案されたカウント・スケッチ・データ構造に似ている。しかし、ｋ配列スケッチ上での最も一般的な演算は、より単純な演算を使用し、カウント・スケッチ上で定義される対応する演算よりも効率的である。
【００３５】
カウント・スケッチと同様に、ｋ配列スケッチＳは、Ｈ×Ｋのレジスタの表、ＴＳ［ｉ］［ｊ］（ｉ∈［Ｈ］，ｊ∈［Ｋ］）からなる。各行ＴＳ［ｉ］［・］（ｉ∈［Ｈ］）は、［ｕ］から［Ｋ］までのハッシュ関数、ｈｉに関連付けられる。その場合、任意のｋ配列スケッチでのデータ構造は、ハッシュ表の配列として見ることができる。それらのハッシュ関数は、再構成精度の確率的保証を提供するために、４ユニバーサルであることが必要とされる。それらは、高速のタブベースの方法を使用して構築され得る。様々なｈｉが独立のシードを使用して構築され、したがって、それらは独立である。
【００３６】
ｋ配列スケッチでは４つの基本演算が定義される。それらは、（１）スケッチを更新するＵＰＤＡＴＥ、（２）所与のキーａのｖａを再構成するＥＳＴＩＭＡＴＥ、（３）２次モーメントＦ２を推定するＥＳＴＩＭＡＴＥＦ２、および（４）複数のスケッチの線形結合を計算するＣＯＭＢＩＮＥである。これらの演算は、変更検出プロセス２００の様々なモジュールで使用される。スケッチ・モジュールでのＵＰＤＡＴＥは観測スケッチＳｏ（ｔ）を更新し、予測モジュールでのＣＯＭＢＩＮＥは様々な予測モデルを実施すると共に、予測スケッチＳｆ（ｔ）および予測誤差スケッチＳｅ（ｔ）を計算し、変更検出モジュールでのＥＳＴＩＭＡＴＥはＳｅ（ｔ）から予測誤差を再構成し、変更検出モジュールでのＥＳＴＩＭＡＴＥＦ２は予測誤差が有意であるかどうか判断するための閾値を選択する。
【００３７】
これらの演算の１形式仕様を以下に示す。
１．ＵＰＤＡＴＥ（Ｓ，ａ，ｕ）：
【数１０】
2005065294.tif 000012
では、ＴＳ［ｉ］［ｈｉ（ａ）］＋＝ｕである。
【００３８】
２．ＥＳＴＩＭＡＴＥ（Ｓｉ，ａ）：
【数１１】
2005065294.tif 000013
をそのスケッチ中のすべての値の合計とする。これは、任意のＥＳＴＩＭＡＴＥ（Ｓｉ，ａ）が呼び出される前に一度だけ計算すればよい。ｖａの推定値：
【数１２】
2005065294.tif 000014
を返し、式中、
【数１３】
2005065294.tif 000015
である。この考察の最後にある証明に示すように、各
【数１４】
2005065294.tif 000016
は、（Ｋ−１）に反比例する分散を有するｖａの不偏推定量である。ｖｅｓｔａは、極端な推定値を回避することによってさらに精度を向上させる。
【００３９】
３．ＥＳＴＩＭＡＴＥＦ２（Ｓ）：２次モーメントの推定値を返す：
【数１５】
2005065294.tif 000017
式中、
【数１６】
2005065294.tif 000018
である。この考察の最後にある証明に示すように、各
【数１７】
2005065294.tif 000019
は、（Ｋ−１）に反比例する分散を有するＦ２の不偏推定量を形成する。
【数１８】
2005065294.tif 000020
は、極端な推定値を回避することによってさらに精度を向上させる。
【００４０】
４．ＣＯＭＢＩＮＥ（ｃ１，Ｓ１，・・・ｃｌ，Ｓｌ）：スケッチ・データ構造の線形性は、
表
【数１９】
2005065294.tif 000021
中のあらゆるエントリを組み合せることによって、複数のスケッチ
【数２０】
2005065294.tif 000022
を線形的に結合できるようにする。
【００４１】
予測モジュールは、過去の間隔Ｓｏ（ｔ０）（ｔ０＜ｔ）での観測スケッチを使用して予測スケッチＳｆ（ｔ）を計算すると共に、観測スケッチと予測スケッチとの間の誤差をＳｅ（ｔ）として計算する。このために、一変量時系列予測および変更検出に際して、少なくとも６つの公知のモデルが使用され得る。最初の４モデルは単純な平滑化モデルであり、残りの２つはＡＲＩＭＡモデルの系統に属する。６モデルすべてが、スケッチの線形性を利用することによって、スケッチの上で実施され得る。
【００４２】
そうした有用な予測モデルの最初の４つは単純な平滑化モデルであり、その単純さゆえによく用いられる。それらは、移動平均（ＭＡ）、指数加重移動平均（ＥＷＭＡ）、Ｓ型移動平均（ＳＭＡ）、および非季節調整ホルト−ウィンターズ（ＮＳＨＷ）である。
【００４３】
移動平均（ＭＡ）予測モデルは、すべての過去のサンプルに等しい重みを割り当て、時間ｔでの予測を計算するために使用される過去の時間間隔数を指定する単一の整数パラメータＷ≧１を有する。
【数２１】
2005065294.tif 000023
【００４４】
Ｓ型移動平均（ＳＭＡ）予測モデルは、より新しいサンプルにより高い重みを与える加重移動平均モデルの１クラスである。
【数２２】
2005065294.tif 000024
そのウィンドウのうちの新しい方の半分に等しい重みを与え、古い方の半分に直線的に減衰する重みを与えるサブクラスが使用される。
【００４５】
指数加重移動平均（ＥＷＭＡ）予測モデルでは、時間ｔでの予測は、以前の予測と時間ｔ−１において新たに観測されたサンプルの加重平均である。
【数２３】
2005065294.tif 000025
パラメータα∈［０，１］を平滑化定数と呼ぶ。これは、以前の間隔からの履歴データに対して、新しいサンプルにどれほどの重みを与えるかを示す。
【００４６】
非季節調整ホルト−ウィンターズ（ＮＳＨＷ）予測モデルは、異常な挙動の検出に適用され得る、一般に使用されるもう１つの平滑化モデルである。非季節調整ホルト−ウィンターズ・モデルには、別々の平滑化成分Ｓｓ（ｔ）と傾向成分Ｓｔ（ｔ）がある。２つのパラメータα∈［０，１］、β∈［０，１］がある。
【数２４】
2005065294.tif 000026
その場合の予測はＳｆ（ｔ）＝Ｓｓ（ｔ）＋Ｓｔ（ｔ）である。
【００４７】
ボックス−ジェンキンズ法、すなわち自己回帰和分移動平均（ＡＲＩＭＡ）モデル化技法は、未来の値の過去の値に対する線形依存性を捕捉する線形時系列予測技法の１クラスである。それらの技法は幅広い時系列挙動をモデル化することができる。その結果、それらの技法は、広範に研究され、一変量時系列予測および変更検出に広く使用されている。
【００４８】
ＡＲＩＭＡモデルは、自己回帰パラメータ（ｐ）、差分パス数（ｄ）、および移動平均パラメータ（ｑ）の、３つのパラメータを含む。ボックスおよびジェンキンズによって導入された表記法では、各モデルはＡＲＩＭＡ（ｐ，ｄ，ｑ）と要約される。（０，１，２）と記述されるモデルは、それが、１回（ｄ＝１）差分された後にその時系列について計算されたｐ＝０（ゼロ）自己回帰パラメータおよびｑ＝２移動平均パラメータを含むことを意味する。本明細書の考察では、ｐ、ｄ、ｑには整数値のみが使用される。作用−反作用モデルの状況で小数のｄパラメータを有するモデル（自己回帰実数和分移動平均（ＡＲＦＩＭＡ）モデルなど）に関する最近の研究があるが、それらのネットワーク化状況での適用は完全には探究されていない。
【００４９】
次数（ｐ，ｄ，ｑ）の一般的ＡＲＩＭＡモデルを以下のように表すことができる。
【数２５】
2005065294.tif 000027
式中、Ｚｔは元の時系列をｄ回差分することによって得られ、ｅｔは時間ｔにおける予測誤差であり、ＭＡｉ（ｉ＝１，・・・，ｑ）およびＡＲｊ（ｊ＝１，・・・，ｐ）はＭＡおよびＡＲ係数である。実際には、ｐおよびｑが２より大きい必要があることはほとんどない。差分回数（ｄ）は、通常、０または１である。したがって、本明細書でＡＲＩＭＡモデルがスケッチ状況に適用されると述べるときは、以下の２種類のＡＲＩＭＡモデル（それらの名称は差分回数に基づくものである）だけを詳細に論じる。
ＡＲＩＭＡ０：次数（ｐ≦２，ｄ＝０，ｑ≦２）のＡＲＩＭＡモデル
ＡＲＩＭＡ１：次数（ｐ≦２，ｄ＝１，ｑ≦２）のＡＲＩＭＡモデル
【００５０】
ＡＲＩＭＡモデルでは、ＭＡおよびＡＲ係数（ＭＡｉ（ｉ＝１，・・・，ｑ）およびＡＲｊ（ｊ＝１，・・・，ｐ））の選択は、結果として生じるモデルが逆転可能であると共に定常的であることを保証するものである必要がある。１つの必要不十分条件として、ＭＡｉおよびＡＲｊは、ｐ，ｑ≦２のときには［−２，２］の範囲に属する必要がある。
【００５１】
予測誤差スケッチＳｅ（ｔ）を構成した後で、変更検出モジュールは、推定Ｓｅ（ｔ）の２次モーメントに基づいて以下のように警報閾値ＴＡを選択する。
【数２６】
2005065294.tif 000028
式中、Ｔはその用途によって決定されるパラメータである。
【００５２】
これで、任意のキーａについて、変更検出モジュールは、ＥＳＴＩＭＡＴＥ（Ｓｅ（ｔ），ａ）を使用してＳｅ（ｔ）中のその予測誤差を再構成し、推定予測誤差が警報閾値ＴＡを超えるときはいつでも警報を発することができる。
【００５３】
残る問題は、変更検出モジュール用のキーのストリームをどのようにして得るかである。スケッチは、所与のキーに関連する予測誤差の再構成だけをサポートする。それは、入力ストリームにどのキーが出現しているかに関する情報を含まない。
【００５４】
この問題に対するいくつかの可能な解決法がある。総当り的解決を用いると、最近の間隔（Ｓｅ（ｔ）が定義されるのと同じ間隔ｔなど）で出現したすべてのキーを記録し、Ｓｅ（ｔ）が構成された後でそれらを再現することができる。これは、やはり、フローごとの情報を維持することを必要とする。その拡張性は、キー収集用ウィンドウに表示されるキーの最大数によって制限される。第１のパスでＳｅ（ｔ）を構成し、第２のパス上で変更を検出する２パス法を使用すると、フローごとの状態保持を回避することができる。入力ストリーム自体がキーを提供することになるので、フローごとの状態を保持する必要はない。これは、同じ入力ストリームに２回アクセスすることを必要とし、したがって、オフライン状況でのみ有用である。第３の代替方法は、Ｓｅ（ｔ）が構成された後で現れるキーを使用するものである。これはオンライン状況でもオフライン状況でも機能する。
【００５５】
その危険性は、有意な変更を経た後で再度出現しないキーが見落とされることである。これは、キーが再度現れない場合でもその被害が非常にわずかであると考えられるＤｏＳ攻撃検出など多くの用途では、しばしば、許容される。この方法は、あらゆる新着データ項目ごとに行う必要はないことに留意されたい。いくつかの非常にまれなキーを見落とすという危険性が許容される場合には、（将来の）入力ストリームをサンプリングし、キーのサブストリームだけを処理するだけでよい。
【００５６】
別の可能な方法は、組み合わせグループ・テストをスケッチに組み込むものである。これは、別個のキー・ストリームを必要とせずに、（変更された）スケッチ・データ構造からキーを直接推測することを可能にする。しかし、この方式は、同時に、更新／推定コストも増大させるものであり、その効率をより高めるためにさらなる研究が必要とされている。以下の説明では、すべての実験においてオフライン２パス法が想定されている。
【００５７】
この変更検出枠組みは、様々な予測モデルでの制御パラメータだけでなくスケッチ関連パラメータも含む。次に、これらのパラメータを適正に構成するための指針およびヒューリスティックについて説明する。
【００５８】
ＨおよびＫは、２つのスケッチ関連パラメータ、ハッシュ関数の数（Ｈ）およびハッシュ表のサイズ（Ｋ）である。ＨおよびＫの選択に応じて、ｋ配列スケッチは予測誤差およびそれらの総エネルギーの推定精度についての確率的保証を提供し得る（詳細についてはこの考察の最後にある証明を参照されたい）。そうした分析結果を使用して、目標精度を達成するのに十分なＨおよびＫの選択を決定することが可能である。それらの分析結果は、データから独立して適用されるので、結果として生じるＨおよびＫは、実際のデータセットには控えめすぎることがある。したがって、分析結果をさらに使用して、ＨおよびＫのデータから独立の選択を導出し、それらを上限として扱うこともできる。次いで、実際のデータを用いて、実際の用途での最適な（データ依存の）Ｈ値およびＫ値を見つけ出すことができる。
【００５９】
一変量時系列予測の状況では、モデル・パラメータを構成するために一般に使用される単純なヒューリスティックは、総残余エネルギー、すなわち、ある期間にわたる予測誤差の二乗の合計を最小限にするパラメータを選択するものである。前述のヒューリスティックは、時間ΣｔＦ２（Ｓｅ（ｔ））（式中、Ｆ２（Ｓｅ（ｔ））はスケッチＳｅ（ｔ）によって要約されるすべての予測誤差での２次モーメントである）に生じる予測誤差スケッチでの総エネルギーを最小限に抑えるパラメータを探すために、そのスケッチ状況まで拡張することが可能である。
【００６０】
真のＦ２（Ｓｅ（ｔ））は、各パラメータ設定ごとにフローごとの分析が実施されない限り知り得ないものであり、それは不可能である。その代わり、Ｆｅｓｔ２（Ｓｅ（ｔ））がＦ２（Ｓｅ（ｔ））に厳密に近似する限り、推定２次モーメントＦｅｓｔ２（Ｓｅ（ｔ））を使用することが可能である。言い換えると、予測誤差
【数２７】
2005065294.tif 000029
の推定総エネルギーを最小限に抑えるパラメータを見つける必要がある。
【００６１】
連続するパラメータでは、複数パス格子探索法を用いて適切な選択を見つけることができる。例えば、ＥＷＭＡモデルを考察する。第１のパスは、その予測誤差での推定総エネルギーを最小限に抑えるパラメータα∈｛０．１，０．２，…，１．０｝を見つける。ａ０を最適なαとする。第２のパスは、範囲［ａ０−０．１；ａ０＋０．１］をＮ＝１０等分に細分化し、このプロセスを繰り返す。複数パスによって高精度が得られる。移動平均モデルなど、整数パラメータを有するモデルでは、最適値を見つけるために単にパラメータを変動させるだけでよい。格子探索は１ヒューリスティックにすぎないことに留意されたい。これは、予測誤差での推定総エネルギーを最小限にする最適パラメータ組み合わせが見つかることを保証するものではない。しかし、格子探索は、結果として生じるモデルが全体的な時系列挙動を捕捉できるような正確なパラメータを生み出すことがわかっている。
【００６２】
この手法を評価、検証するために大量の実際のインターネット・トラフィック・データが使用された。次に、データセットおよび使用される実験的パラメータ設定について考察を詳細に示す。
【００６３】
入力データ・フローは、第１層ＩＳＰのバックボーン中にある１０個の異なるルータからの４時間分のネットフロー・ダンプとなるように選択された。連続４時間の長さで、最小は８６１，０００レコード、最大は６，０００万を超えるレコードを有するルータを用いて、ほぼ１億９，０００万レコードが処理される。
【００６４】
これらの実験では、許容可能な選択範囲を決定するために様々なパラメータ値が使用された。それらの値は、使用可能な実際のローカル・データに基づくスケッチベースの手法では調整され得る。したがって、それらのパラメータの一部は、スケッチ技法が異なる用途で使用されるときには異なる値を取り得る。
【００６５】
推定および更新のコストは、スケッチに使用されるハッシュ表の数によって決定されるので、Ｈには小さい値を選択すべきである。同時に、Ｈは、極端な推定値をヒットする確率を指数関数的に小さくすることによって精度を向上させ（詳細についてはこの考察の最後にある定理２、３、５を参照されたい）、やはり、Ｈには小さい値を使用すれば十分であることが示唆される。コストに対する推定精度への影響を判定するためにＨを変動させた。Ｈの選択（１、５、９、２５）は、最適化された中間ネットワークを使用すれば入力の性質に関する仮説を立てずに中央値を迅速に見つけられるという事実によって決定された。
【００６６】
ｋ配列スケッチを使用することによって誤差閾値の具体的な程度を提供するのに必要とされる分析的上限がＫの上側の範囲として選択された。上限の対数を取るステップで、０からこの上限までの間の値を経験的に調べることによって下限をゼロからより狭めることが可能である。実験結果は、上限Ｋ＝６４，０００、下限Ｋ＝１，０２４を示した。
【００６７】
もう１つの重要なパラメータが間隔サイズである。スケッチベースのプロセス２００は各間隔の最後に異常を報告するため、間隔が長いと遅延を生じるはずであり、１つの間隔内だけで発生したイベントは見落とされる可能性がある。間隔が短いと、スケッチベースの予測データ構造をより頻繁に更新することが必要とされる。応答性と計算オーバーヘッドとの妥当なトレードオフとして、５分（３００秒）間隔が選択された。そうした間隔は、他のＳＮＭＰベースのネットワーク異常検出システムでも使用される。また、より短い間隔の影響を調べるために、１分（６０秒）間隔も使用する。
【００６８】
これら６つの時系列予測モデルの各々は、様々なパラメータの選択を必要とする。移動平均モデル（ＭＡおよびＳＭＡ）では、最小ウィンドウ・サイズに１つの時間間隔が使用され、５（または１）分間の１間隔サイズでの最大ウィンドウ・サイズが１０（または１２）であった。次いで、各間隔値全体での予測誤差の最小総エネルギーを生じるウィンドウ・サイズがこのパラメータの値として選択された。残りのモデルでは、２パス格子探索法を適用して様々なパラメータが選択された。ＥＷＭＡモデルおよびＮＳＨＷモデルでは、各パス間に、現在の範囲が１０の等間隔に区切られた。しかし、ＡＲＩＭＡモデルでは、パラメータの数がずっと大きく、各パラメータ範囲を１０の部分に区切られた場合には、サーチ空間が大きくなりすぎる。そこで、サーチ空間を制限するために、現在のサーチ範囲が１０ではなく７つの部分に区切られた。格子探索の間、Ｈは１に、Ｋは８０００に固定された。後で実証するように、Ｈ＝１、Ｋ＝８０００では、予測誤差の推定総エネルギーは、フローごとの分析を使用して得られる真のエネルギーに厳密に近似する。
【００６９】
次に、変更検出でのスケッチの評価結果を提示する。様々な実験でのセットアップについて説明し、３つのモデル（ＥＷＭＡ、およびｄ＝０および１でのＡＲＩＭＡ）での結果を詳細に提示し、ＮＳＨＷでの結果も補足的に提示する。ほとんどの場合、これら様々なモデルからの結果は大部分類似しており、それらは簡潔にするために除外する。
【００７０】
評価は３つの部分に分けられる。まず、格子探索によって生成されたパラメータの妥当性が報告される。次に、スケッチの評価がフローレベルで、すなわち、（ｉ）最大絶対予測誤差を有する上位Ｎフロー及び（ii）その絶対予測誤差が閾値を超えるフローとしてスケッチによって報告させるものに焦点を合わせて、スケッチによる報告とフロー毎の方式との比較とともに、提供される。
【００７１】
次に説明する実験は、それらの予測モデルでの適当なパラメータ設定、ＨおよびＫの値の決定、および格子探索関数の有用性の評価に関するものであった。予測モデル・パラメータ設定の選択のためのメトリックとして、（真の総エネルギーの代わりに）推定総エネルギーが使用された。この手法が優れた性能を生み出すには、推定値が真の値を厳密に追随する必要がある。このことが、これらの実験の焦点であった。許容可能な性能をもたらすＨおよびＫの適当な選択を行うために、（Ｈ，Ｋ）値の空間および様々なパラメータ設定が考察された。格子探索関数を使用して最小総エネルギーをもたらすパラメータ設定が選択された。次いで、格子探索によって選択されたパラメータの「適合度」がパラメータのランダム選択に比較された。
【００７２】
図３に、間隔＝３００秒、Ｈ＝１、Ｋ＝１０２４での、相対差の累積分布関数（ＣＤＦ）が全モデルにわたって示されている。１組の実験（ランダムと呼ぶ）が（１億８，９００万を上回るフロー・レコードからなる）１０個のルータ・ファイルを集めたものに対して実施された。各予測モデルごとに、そのモデル・パラメータ空間中でいくつかの点がランダムに選択され、選択された点と（Ｈ，Ｋ）値の組み合わせごとに、各ルータ・トレース上でスケッチベースの検出とフローごとの検出の両方が実行された。ここでの目的は、異なる予測モデル間の差を調べ、ＨおよびＫ（ハッシュ表および範囲サイズ）のパラメータ値選択を評価することであった。この実験は、予測パラメータが慎重に選択されなかったときにスケッチとフローごとがどのように比較されるかの考察も可能にした。その比較メトリックが「相対差」であり、これは、スケッチベースの技法から計算された総エネルギー（各時間間隔ごとの２次モーメントの合計の二乗根）と、フローごとの検出を使用して得られた総エネルギーとの差として定義され、フローごとの検出を使用して得られた総エネルギーに対する比率として表される。個々の予測モデルと（Ｈ，Ｋ）の組み合わせについて、各ルータ・ファイルごとに、複数の相対差の値が、そのモデルのパラメータ空間中の選択された点ごとに１つずつ得られる。
【００７３】
図３〜図５では、各曲線は個々の予測モデルと（Ｈ，Ｋ）の組み合わせに対応し、すべてのルータから集約された相対差の値の経験的ＣＤＦを表す。図３には、Ｈ（１）およびＫ（１０２４）が小さい場合でさえも、すべてのモデルを通じて、大部分の点が、Ｘ軸上の０％点の近隣に集中することが示され、ランダムに選択されたモデル・パラメータの場合でさえも、スケッチベースの手法からの総エネルギーはフローごとでの総エネルギーに非常に近いことがわかる。ＮＳＨＷモデルの場合だけ、ごく一部の点が、対応するフローごとの値と１．５％以上異なるスケッチ値を有する。最悪の場合の差は３．５％である。
【００７４】
次に、Ｈパラメータを変動させることの影響を考察する。図４の、ＥＷＭＡモデルのグラフ４００およびＡＲＩＭＡ０モデルのグラフ４０２には、低い相対差を実現するにはＨを５より大きくする必要がないことが示されている。
【００７５】
図５に、ランダム・パラメータ技法での最後の結果セットを示す。これには、Ｋ＝８１９２とすると、相対差が問題ではなくなり、Ｋをそれ以上増やす必要がなくなることが示されている。パラメータを識別するこの格子探索技法は、６０秒間隔と３００秒間隔（それぞれグラフ５００と５０２に示す）とでの６つのモデル、ルータ・ファイルの代表サンプル（大サイズ、中サイズ、および小サイズのファイルを各１つずつ）、および（Ｈ＝１，Ｋ＝８１９２）の組み合わせを使用する。各（モデル、ルータ、Ｈ、Ｋ）組み合わせごとに、格子探索は、結果として生じる予測誤差での総エネルギーを最小限に抑える、そのモデルでのパラメータ値を出力する。この格子探索によって出力されたパラメータ設定を使用して、対応する総エネルギーを得るためにフローごとの分析が実行された。次いで、同じルータ・ファイルおよびモデルについて、前の技法で生成されたランダム・パラメータのフローごとの推定値に対して、そのフローごとの推定値が比較された。この実験の目的は２つあった。第１は、格子探索の結果が、決してランダム・パラメータのフローごとの値のいずれよりも悪くならないとの保証を得ることであり、第２は、格子探索の結果が、ランダムの場合の結果より著しくよくなり得ることを示すことであった。この実験結果は、すべての場合（すべてのモデル、３つのルータ・ファイル、２つの間隔）において、格子探索が決してランダム・パラメータより悪くならないことを示している。第２には、それらの場合のうち少なくとも２０％において、ランダム・パラメータでの結果が、格子探索の場合での誤差の少なくとも２倍は（大部分でははるかに）悪いことを示している。これは、それらの実験の残りでのパラメータを生成するために格子探索を使用することを正当化するものである。
【００７６】
格子探索方式からのパラメータ・セットを検証した後で、２つの技法、すなわち（ｉ）上位Ｎ個、および（ｉｉ）閾値処理によって、スケッチ方式の精度がフローごとの推定値に比較される。
【００７７】
ＨおよびＫの値は、予測の精度および効率的動作への鍵である。用途ごとに適正な値の範囲を選択する際には注意を払う必要がある。大規模かつ多様なデータセットに基づく実験結果は、選択された値（Ｈ＝１…２５）、（Ｋ＝１，０００…６４，０００）が、実際に、各用途の変更検出クラスに適することを示している。
【００７８】
所与のＮについて、上位Ｎのスケッチ対フローごとの評価が実施されて、フローごとの方式によって検出された（予測誤差の降順に並べられた）上位Ｎフローのうちのいくつが、スケッチベースの方式によってｐ順位付けに関しても検出されたかが判定される。すべてのモデルにわたってスケッチ精度評価を実行するために、３つのＨ値（５、９、２５）およびＫ値（８０００、３２０００、６４０００）、２つの間隔値（６０秒と３００秒）、および大容量（６０００万超）、中容量（１２７０万）、小容量（５３０万）レコードを表す３つのルータ・データ・ファイルが選択された。モデル・パラメータには、格子探索プロセスによって選択されたパラメータ値が使用された。各時間間隔ごとに、最大絶対予測誤差（より大きな絶対予測誤差は、フローの量が、基礎をなすモデルによって予測された量からのより大きい偏差を有することを示すことを想起されたい）を有する上位Ｎフローが、スケッチ技法とフローごとの技法の両方に生成される。Ｎの４つの値（５０、１００、５００、１０００）について、上位Ｎフローのうちのいくつが２つの結果セット間で共通するかを調べ、類似度メトリックＮＡＢ／Ｎ（ＮＡＢは２セット間での共通要素数である）を計算する。
【００７９】
フローごとの技法からの上位Ｎ要素の中には、スケッチ技法によって出力された上位Ｎ要素に厳密には属さないものもあり得るが、それでもなお、それらの要素がスケッチベースの順位付けにおいて上位にあることが期待される。したがって、上位Ｎ個のフローごとのリストを、スケッチベースの順位付けリスト中のさらなる要素と比較することによって精度を上げることは可能である。この可能性を評価するには、第２の比較セットには、上位Ｎ個のフローごとの結果を、スケッチベースの手法からの上位Ｘ＊Ｎ（Ｘ＝１、１．２、１．５、２）個の結果に対して比較することが関与する。
【００８０】
結果は、上位Ｎ（Ｎ＝５０、１００、５００、１０００）フローを比較することによって、フローごとの場合に比べてスケッチがいかに優れているかを示すものである。このメトリックは、本質的に、類似度メトリック、すなわち、Ｎで正規化された２セット間の共通要素数である。適当なＨおよびＫの場合に、このメトリックが全時間間隔にわたって極めて一貫していることが実証されている。４時間のうちの最初の１時間分のデータセットはモデルのウォームアップのためだけに使用され、６０秒時間間隔の場合と３００秒時間間隔の場合とで、それぞれ、１８０間隔と３７間隔が残された。
【００８１】
図６のグラフ６００および６０２には、Ｎが大きい（１０００）場合でさえ、類似度は、Ｈ＝５、Ｋ＝３２Ｋでは、６０秒間隔でも３００秒間隔でも、それぞれ、約０．９５であることが示されている。残りの図７〜９には、１８０間隔と３７間隔全体での平均類似度値を示す。
【００８２】
図７のグラフ７００および７０２は、ＥＷＭＡモデルを使用して（全時間間隔での）平均類似度を示すものであり、３００秒間隔でも６０秒間隔でも、それぞれ、Ｈは５に固定され、Ｋは８Ｋから６４Ｋまでの間で変動する。図からわかるように、Ｋ＝３２０００では、Ｎが大きい場合でも類似度は０．９５を上回る。Ｎがより小さい場合（５０または１００など）には、そのオーバーラップはほぼ１００％である。Ｋの値をより大きくしてもその効果は限られたものである。類似度は、（Ｎが大きい場合）６０秒のより小さい間隔サイズを用いる方が向上することに留意されたい。この精度の向上は、間隔がより小さい場合には、各間隔で要約される必要のあるフローがより少ない可能性があるためであると考えられる。
【００８３】
精度向上の可能性を、上位Ｎ対上位Ｘ＊Ｎ（Ｘ＝１、１．２、１．５、２）の比較を実施することによって探る。図８のグラフ８００および８０２に見られるように、３００秒間隔と６０秒間隔の場合、それぞれ、類似度は、Ｎが大きくても、Ｋ＝８０００では増大する。Ｘ＝１．５では、類似度は、Ｎが大きくても著しく上がっている。考察された各設定では、Ｘ＝１．５では非常に高い精度が達成され、Ｘの値をそれ以上大きくしても、精度はほんのわずかしか増加しない。これは望ましいことである。というのは、Ｘがより大きいと、精度が上がると同時に、フォールス・ポシティブもより多く生じることになるからである。
【００８４】
次に、Ｈを変動させることによる精度への影響について考察する。図９のグラフ９００には、小さいＫ＝８００を用いた場合、特にＮが大きいと、高い類似値を得るためには、Ｈは少なくとも９である必要があることが示されている。Ｈの増加は、計算オーバーヘッド（キー当たりの更新演算数はＨの値に比例する）および（スケッチ用）メモリ・オーバーヘッドの増大に直接対応するため、Ｈが大きいことは望ましくない。
【００８５】
しかし、図９のグラフ９０２に示すように、Ｎが非常に大きい場合でさえ、Ｈが小さい（Ｈ＝５）場合には、Ｋを３２０００まで増加させると、即座に類似度がほぼ１にまで増大する。（スケッチの）Ｋがより大きいことは空間オーバーヘッドが大きいことを意味する。これは、空間／計算オーバーヘッドのトレードオフを示唆するものである。計算オーバーヘッドの方がより重大である多くの用途においては、Ｋ＝３２０００以上にすると、Ｈの値が小さくても精度の高い結果を得ることができる。
【００８６】
中サイズのルータ・ファイルのＥＷＭＡモデルでの類似度メトリックとして、図１０のグラフ１０００（上位Ｎ対上位Ｎの比較結果を示す）およびグラフ１００２（上位Ｎ対上位Ｘ＊Ｎの比較結果を示す）に、すべてのファイルが同様の出力を有する場合の、異なるルータ・ファイルでの結果が示されている。
【００８７】
同様に、ＡＲＩＭＡ０モデル、すなわちｄ＝０のＡＲＩＭＡの影響を示す。図１１のグラフ１１００および１１０２に、それぞれ、３００秒間隔の場合の、大サイズと中サイズのルータ・ファイルでの類似度を示す。
【００８８】
前述の精度検査のように上位Ｎ個の値だけを比較するのではなく、フローは、その絶対予測誤差が、（１時間間隔中のすべてのフローの予測誤差の二乗の合計の二乗根によって得られる）Ｌ２ノルムの一定の割合以上であるものに限られる。閾値レベルは０．０１、０．０２、０．０５、０．０７、０．１の範囲で変動させた。２つの時間間隔（６０秒、３００秒）のそれぞれでの結果が、３つのモデル（ＥＷＭＡ、ＮＳＨＷ、およびｄ＝０のＡＲＩＭＡ）で考察された。スケッチベースとフローごとの変更検出のそれぞれについて、フローが予測誤差の絶対値の降順に並べられた。ここで問題となるメトリックは、フォールス・ネガティブ比、フォールス・ポジティブ比、および警報数である。所与の閾値τについて、Ｎｐｆ（τ）とＮｓｋ（τ）が、それぞれ、フローごとの検出とスケッチベースの検出での閾値を満たすフロー数を指すものとする。その場合、フローごととスケッチでの警報数は、それぞれ、Ｎｐｆ（τ）とＮｓｋ（τ）である。ＮＡＢ（τ）を、スケッチ・リストとフローごとのリストの両方に共通のフロー数とする。フォールス・ネガティブ比は以下のように計算される。
【数２８】
2005065294.tif 000030
フォールス・ポジティブ比は以下のとおりである。
【数２９】
2005065294.tif 000031
【００８９】
この時点で、各メトリックごとに、時間間隔ごとに１つの値を持つ１つの時系列がある。次いで、この時系列全体の平均値が考察された。
【００９０】
また、フローが閾値処理によって選択されたときのスケッチとフローごとの結果の類似度も考察された。ここでの全体の要約は、Ｋを少なくとも３２０００に設定すれば、フォールス・ネガティブとフォールス・ポジティブを低くする確実な保証を提供し得ることである。このことは、大サイズのルータ・データ・ファイルと非季節調整ホルト−ウィンターズ・モデルが６０秒（図１２）と３００秒（図１３）の時間間隔で使用した、図１２と図１３に示されている。図１２のグラフ１２００には、Ｈの値が非常に低い（Ｈ＝１）場合には、警報数が非常に多いことが示されている。警報数を劇的に低減させるには、単にＨを５に増やすだけで十分である。グラフ１２００には、閾値を上げることによって実現され得る警報数の著しい減少も示されている。最終的に、このグラフには、Ｈ≧５かつＫ≧８０００のとき、フローごとの結果とスケッチの結果の間には実質的に差がないことが示されている。
【００９１】
図１２のグラフ１２０２には、Ｋ＝３２０００以上では、閾値が非常に低い場合でさえ、フォールス・ネガティブ比が２％未満にまで急激に低下し、閾値が０．０５では１％を下回ることが示されている。フォールス・ポジティブ比は、図１２のグラフ１２０４に示すように、Ｋ＝３２０００の場合、閾値が０．０２と低い場合でも、非常に低い（１％未満）。全体の結果は、図１３の対応するグラフ１３００、１３０２、１３０４に示す３００秒間隔でも同様である。
【００９２】
図１４〜１７の各グラフは、単一の間隔サイズ（３００秒）で中サイズのルータ・データ・ファイルを使用し、ＥＷＭＡ、非季節調整ホルト−ウィンターズ・モデル、ｄ＝０とｄ＝１のＡＲＩＭＡの４つの間でモデルを変えて行ったものである。フォールス・ネガティブ比とフォールス・ポジティブ比だけが示されている。
【００９３】
図１４のグラフ１４００には、ＥＷＭＡモデルでのフォールス・ネガティブ比が、０．０１より大きい閾値では１％をかなり下回ることが示されている。同様に、図１４のグラフ１４０２には、非季節調整ホルト−ウィンターズ・モデルでのフォールス・ネガティブ比が、ＥＷＭＡモデルよりわずかによいことが示されている。
【００９４】
図１５のグラフ１５００および１５０２に、２つの異なるＡＲＩＭＡモデル（それぞれ、ｄ＝０とｄ＝１）について、閾値が０．０１と低い場合には、フォールス・ネガティブは低いが、ＥＷＭＡモデルおよびＮＳＨＷモデルに比べるとわずかに異なることが示されている。
【００９５】
図１６のグラフ１６００および１６０２には、ＥＷＭＡモデルとＮＳＨＷモデルでのフォールス・ポジティブ比が、それぞれ、Ｋ＝３２０００以上で、閾値が０．０１より大きい場合には、１％をかなり下回ることが示されている。
【００９６】
同様に、図１７のグラフ１７００および１７０２には、それぞれ、ＡＲＩＭＡモデルｄ＝０とｄ＝１での低いフォールス・ポジティブ比が示されている。
【００９７】
スケッチベースの変更検出実装形態には３つの構成要素、４ユニバーサル・ハッシュ関数、スケッチ、および予測がある。４ユニバーサル・ハッシュ関数の実装は、Ｃプログラミング言語で約２００行のプログラミング・コードを用いて実現することができ、スケッチは約２５０行になる。予測コードは、使用される予測モデルによって異なるが、それらのモデルはすべて、それぞれ、８００行未満のコードである。
【００９８】
ハッシュ計算およびスケッチＵＰＤＡＴＥは入力ストリーム中のあらゆるデータ項目に対して行われる必要がある。デフォルトでは、スケッチＥＳＴＩＭＡＴＥも項目ごとに行われる必要がある。しかし、まれにしか出現しない（ほぼ間違いなくごくわずかな被害しか生じ得ない）一部のキーを見落とすことが許容される場合には、着信キーのストリームをサンプリングし、選択されたサブストリームだけに対してＥＳＴＩＭＡＴＥを行うことも可能である。ＥＳＴＩＭＡＴＥＦ２などの演算は、まれにしか行う必要がなく（各間隔ごとに１回）、それらの償却コストは取るに足らないものである。
【００９９】
「コンピュータＡ」（ＩＲＩＸ６４  ６．５を走らせる４００メガヘルツ（ＭＨｚ）のＳＧＩ  Ｒ１２ｋプロセッサ）および「コンピュータＢ」（ＳＯＬＡＲＩＳ５．８を走らせる９００ＭＨｚのＵＬＴＲＡＳＰＡＲＣ−ＩＩＩプロセッサ）で１０００万回のハッシュ計算およびスケッチ演算を実施するための実行時間を図１８の表に示す。各ハッシュ計算は８個の独立の１６ビット・ハッシュ値を生じ、したがって、Ｈ≦８かつＫ≦２１６でのｋ配列スケッチには十分である。ＵＰＤＡＴＥもＥＳＴＩＭＡＴＥも、これらのハッシュ値がすでに計算されている（項目ごとに１回だけ行えばよい）ことを前提とする。使用するスケッチ・パラメータは、Ｈ＝５、Ｋ＝２１６である。表に示すように、これらの演算のオーバーヘッドはあまり大きくない。
【０１００】
スケッチベースの変更検出プロセス２００は、前述のように、フローごとの時系列分析と比べると高精度である。これは、ネットワーク異常検出およびトラフィック測定のための基本構成単位となることが期待される。
【０１０１】
別の実施形態では、スケッチベースの技法は、予測モデル・パラメータをオンラインで取得するように変更することによってほぼリアルタイムの変更検出を行うことができる。１つの可能な方法は、トラフィック挙動全体での変更に遅れをとらないように、履歴データを使用して予測モデル・パラメータを定期的に再計算するものである。
【０１０２】
その他の実施形態では、固定間隔サイズによる境界効果が回避され得る。可能な解決法には、（ｉ）様々な間隔サイズおよび様々な開始点を使用して複数のモデルを同時に走らせること、および（ｉｉ）間隔サイズを（指数関数的に分布する間隔サイズなどを使用して）ランダム化し、間隔サイズによって正規化された合計値の変更を検出することが含まれる。スケッチの線形性がこれら両方の解決法を可能にする。
【０１０３】
正常なトラフィック挙動からの有意の偏差を正確に検出することは１つの大きな目的である。しかし、トラフィック異常の中には害のないものもある。誤警報を減らすという問題は、すべての変更検出に基づくネットワーク異常検出システムにとっての大きな難題である。前述のスケッチベースの変更検出枠組みは調整可能パラメータを含み、フォールス・ポジティブを制限するように調整され得る。例えば、この技法は、上位Ｎ個の大きな変更、または閾値を超える変更だけを報告するようにプログラムされ得る。個々の用途での必要によって、それらの調整可能パラメータの実際の設定が導き出されるであろう。警報条件は、適当なネットワーク管理要員に電子メール、インスタント・メッセージ、または他の任意の通知（電話やポケットベルなどによるものなど）を送るといった、計算処理システムが使用可能な任意の標準的手段によってトリガされ、報告され得る。
【０１０４】
大規模なネットワークで生成された大量のデータを想定して、ＩＳＰネットワーク測定インフラストラクチャでは収集する必要のあるデータ量を減らすためにサンプリングがますます多用されるようになっている。本明細書で提示した手法は、大量のデータセットでの拡張可能な変更検出のために時系列分析をスケッチと組み合せるものである。拡張性を高めるために、サンプリング技法をプロセス２００と組み合せることもできる。
【０１０５】
広範囲のパラメータが使用可能であることを考えると、それらに適正で正当な値を選択するための妥当な指針があれば有用なはずである。統計的実験計画領域における完全な要因加算法は、様々な変数のレベル（または「バージョン」）数を狭めるのに役立つ。そうした技法は、相互に独立で、類似度に基づいて総体的に妥当な値を識別する方向に向かうパラメータを生み出し得る。例えば、Ｈは他のパラメータから独立に全般的影響を与える。複数の実行を有することに伴う単調さも、例えば、イェーツ・アルゴリズムを使用することによって低減され得る。
【０１０６】
次に、先に触れた証明を提示する。注釈：任意の
【数３０】
2005065294.tif 000032
について、ａ〜ｂはｈ（ａ）＝ｈ（ｂ）を表し、
【数３１】
2005065294.tif 000033
はｈ（ａ）≠ｈ（ｂ）を表すものとする。
【０１０７】
ＶＡ推定のための分析（
【数３２】
2005065294.tif 000034
の精度）：以下の定理１は、各
【数３３】
2005065294.tif 000035
が（Ｋ−１）に反比例する分散を有するｖａの不偏推定量であることを表す。
【０１０８】
定理１。
【数３４】
2005065294.tif 000036
【数３５】
2005065294.tif 000037
【０１０９】
証明：任意のｈ∈｛ｈ０，…，ｈＨ−１｝について、
【数３６】
2005065294.tif 000038
である。
【数３７】
2005065294.tif 000039
と定義すると、
【数３８】
2005065294.tif 000040
は、
【数３９】
2005065294.tif 000041
になる。ｈは４ユニバーサルであるので、任意の異なるａ，ｂ∈［ｕ］について、
【数４０】
2005065294.tif 000042
である。また、任意の異なるａ，ｂ，ｃ∈［ｕ］について、
Ｅ［Ｘａ，ｂＸａ，ｃ］＝０
である。以上からこの定理を証明することができる。
【数４１】
2005065294.tif 000043
【０１１０】
【数４２】
2005065294.tif 000044
【数４３】
2005065294.tif 000045
は、極端な推定値を回避することによってさらに精度を向上させる。以下の定理２および３は
【数４４】
2005065294.tif 000046
の精度保証を要約する。
【０１１１】
定理２
任意のａ∈［ｕ］、Ｔ∈（０，１）、およびα∈［１，∞］について、
【数４５】
2005065294.tif 000047
の場合には、
【数４６】
2005065294.tif 000048
である。
【０１１２】
証明：任意のｈ∈｛ｈ０，…，ｈＨ−１｝について、チェビシェフの不等式により、
【数４７】
2005065294.tif 000049
（チェビシェフの不等式）
である。
【数４８】
2005065294.tif 000050
は、チェルノフの不等式により、
【数４９】
2005065294.tif 000051
のＨコピーの中央値を取ることによって得られるので、定理２の結果が直ちに得られる。
【０１１３】
定理３。任意のａ∈［ｕ］、Ｔ∈（０，１）、およびβ∈［０，１］について、
【数５０】
2005065294.tif 000052
の場合には、
【数５１】
2005065294.tif 000053
である。
【０１１４】
証明：この証明はほとんど同一であり、簡潔にするためにここでは省略する。
【０１１５】
一例として、Ｋ＝２１６、α＝２、β＝０．５、Ｔ＝１／３２、Ｈ＝２０とする。
【数５２】
2005065294.tif 000054
であるときには必ず警報を発する場合には、定理２に従って、
【数５３】
2005065294.tif 000055
を見落とす確率は９．０×１０−１３未満である。定理３によれば、
【数５４】
2005065294.tif 000056
に誤って警報を発する確率は、９．５×１０−７未満である。
【０１１６】
Ｆ２推定のための分析（
【数５５】
2005065294.tif 000057
の精度）：以下の定理４は、各
【数５６】
2005065294.tif 000058
が（Ｋ−１）に反比例する分散を有するＦ２の不偏推定量を形成することを示す。カウント・スケッチを使用して同じ分散を実現するためには、より低速となることを受け入れ、またはメモリ所要量を２倍にする必要がある。
【０１１７】
定理４。
【数５７】
2005065294.tif 000059
【数５８】
2005065294.tif 000060
は極端な推定値を回避することによってさらに精度を向上させる。定理５は
【数５９】
2005065294.tif 000061
の精度保証を提供する。
【０１１８】
定理５。任意のλ＞０について、
【数６０】
2005065294.tif 000062
である。
【０１１９】
証明：定理４およびチェビシェフの不等式により、
【数６１】
2005065294.tif 000063
である。
【数６２】
2005065294.tif 000064
は、チェルノフの不等式により、
【数６３】
2005065294.tif 000065
のＨコピーの中央値であるので、定理５での結果が直ちに得られる。
【０１２０】
一例として、Ｋ＝２１６、λ＝０．０５、Ｈ＝２０とすると、定理５は、推定値
【数６４】
2005065294.tif 000066
がその実際の値Ｆ２から５％外れる確率は７．７×１０−１４を下回ることを表す。
【０１２１】
以上の開示においては、本発明の最良の方法を具体的に説明してきたが、それらの説明は例示のために提供したものにすぎず、当分野の技術者によれば、添付の特許請求の範囲によってまず第１に定義される本発明の精神および範囲を逸脱することなく、本発明に関して形と詳細の両方での他の変形形態も実施され得ることを理解すべきである。
【図面の簡単な説明】
【０１２２】
【図１】本明細書で開示するプロセスがその内部で実施され得るコンピュータ・ネットワークを示す構成図である。
【図２】図１のコンピュータ・ネットワークを介して実施される例示的なスケッチベースの異常検出プロセスを示す流れ図である。
【図３】図２のプロセスで使用されるスケッチベースのプロセスとフローごとの分析との間の相対差の累積分布関数（ＣＤＦ）を示すグラフである。
【図４】図２のプロセスと共に使用される時系列予測モデルでのｈパラメータのランダム選択の結果を示すグラフである。
【図５】図２のプロセスと共に使用される時系列予測モデルでのＫパラメータのランダム選択の結果を示すグラフである。
【図６】時系列予測パラメータＨ＝５、Ｋ＝３２０００を用いて、大きなルータ・ファイルに、図２のプロセスと共に使用されるフローごとの測定とスケッチ関数の全般的類似度を示すグラフである。
【図７】時間間隔３００秒と６０秒とで、Ｈが５に固定され、Ｋが８Ｋから６４Ｋまでの間で変動する場合の、図２のプロセスと共に使用されるＥＷＭＡモデルにおける平均類似度を示すグラフである。
【図８】大きなルータ・ファイルに、図２のプロセスと共に使用されるＥＷＭＡモデルでの上位Ｎ対上位Ｘ＊Ｎの精度比較を示すグラフである。
【図９】大きなルータ・ファイルに、図２のプロセスと共に使用されるＥＷＭＡモデルのＨパラメータおよびＫパラメータを変動させることによる影響を示すグラフである。
【図１０】３００秒間隔で、大および中サイズのルータ・ファイルに、図２のプロセスと共に使用されるＥＷＭＡモデルでの類似度メトリックを示すグラフである。
【図１１】３００秒間隔で、大および中サイズのルータ・ファイルに、図２のプロセスと共に使用されるＡＲＩＭＡモデルでの類似度メトリックを示すグラフである。
【図１２】６０秒間隔で、大規模ルータ上で、図２のプロセスと共にＮＳＨＷモデルを使用した場合の、様々な閾値での警報数、フォールス・ポシティブ数、およびフォールス・ネガティブ数を示すグラフである。
【図１３】３００秒間隔で、大規模ルータ上で、図２のプロセスと共にＮＳＨＷモデルを使用した場合の、様々な閾値での警報数、フォールス・ポシティブ数、およびフォールス・ネガティブ数を示すグラフである。
【図１４】３００秒時間間隔で、中サイズのルータ上で実施される図２のプロセスと共に使用されるＥＷＭＡおよびＮＳＨＷモデルでのフォールス・ネガティブ比を示すグラフである。
【図１５】３００秒間隔で、中サイズのルータ上で実施される図２のプロセスと共に使用される様々なＡＲＩＭＡモデルでのフォールス・ネガティブ比を示すグラフである。
【図１６】３００秒間隔で、中サイズのルータ上で実施される図２のプロセスと共に使用されるＥＷＭＡおよびＮＳＨＷモデルでのフォールス・ポシティブ比を示すグラフである。
【図１７】３００秒間隔で、中サイズのルータ上で実施される図２のプロセスと共に使用される様々なＡＲＩＭＡモデルでのフォールス・ポシティブ比を示すグラフである。
【図１８】図１のネットワークで使用され得る別個の計算処理システムでの計算時間に及ぼされるハッシュ計算およびスケッチ関数の影響を要約する表である。
【図１】
2005065294.tif 000067
【図２】
2005065294.tif 000068
【図３】
2005065294.tif 000069
【図４】
2005065294.tif 000070
【図５】
2005065294.tif 000071
【図６】
2005065294.tif 000072
【図７】
2005065294.tif 000073
【図８】
2005065294.tif 000074
【図９】
2005065294.tif 000075
【図１０】
2005065294.tif 000076
【図１１】
2005065294.tif 000077
【図１２】
2005065294.tif 000078
【図１３】
2005065294.tif 000079
【図１４】
2005065294.tif 000080
【図１５】
2005065294.tif 000081
【図１６】
2005065294.tif 000082
【図１７】
2005065294.tif 000083
【図１８】
2005065294.tif 000084