(57)【要約】  本発明は、特にデータ集合及び／又は信号を有するデータストリーム中の異常オブジェクトを自動的にオンライン検出及びクラス分類するための方法に関する。a）正常及び異常オブジェクトを有する少なくとも１つの流入データストリーム（１０００）の検出、b）少なくとも１つの所定の最適化条件に従う時刻t１におけるデータストリーム（１０００）の流入オブジェクトの正常性の幾何学表現（２２００）の自動的構築（２１００）であって、特に有限数の正常オブジェクトを囲む超曲面の構築、c）時刻t２＞t１における少なくとも１つの受信オブジェクトに対して正常性の幾何学表現（２２００）の、少なくとも１つの所定の最適化条件に従うオンライン適合、d）正常性の幾何学表現（２２００）に対する時刻t２における受信オブジェクトに対する正常性／異常性クラス分類のオンライン決定（２３００）、e）生成された正常性クラス分類（２３００）に基づいて、さらなる処理のための異常データを記述するデータ集合、特に視覚的表現、を生成する正常オブジェクト及び異常オブジェクトの自動的クラス分類、を特徴とする。
2007503034.tif 000002
【特許請求の範囲】
【請求項１】
特にデータ集合及び／又は信号を有するデータストリーム中の異常オブジェクトを自動的にオンライン検出及びクラス分類するための方法であって、
a）正常及び異常オブジェクトを有する少なくとも１つの流入データストリーム（１０００）の検出、
b）少なくとも１つの所定の最適化条件に従う時刻t１におけるデータストリーム（１０００）の流入オブジェクトの正常性の幾何学表現（２２００）の自動的構築（２１００）であって、特に有限数の正常オブジェクトを囲む超曲面の構築、
c）時刻t２＞t１における少なくとも１つの受信オブジェクトに対する正常性の幾何学表現（２２００）の、少なくとも１つの所定の最適化条件に従うオンライン適合、
d）正常性の幾何学表現（２２００）に対する時刻t２における受信オブジェクトに対する正常性／異常性クラス分類のオンライン決定（２３００）、
e）生成された正常性クラス分類（２３００）に基づいて、さらなる処理のための異常データを記述するデータ集合、特に視覚的表現、を生成する正常オブジェクト及び異常オブジェクトの自動的クラス分類、
を特徴とする方法。
【請求項２】
請求項１に記載の方法であって、正常性の幾何学表現（２２００）は、全ての可能な曲面中の最小体積又は最小体積推定の閉空間を最適化条件として使用するパラメトリック境界超曲面である方法。
【請求項３】
超曲面は、少なくとも１つの流入データストリーム（１０００）のオリジナル測定値空間内又はその非線形変換によって得られる空間内に構築される請求項２に記載の方法。
【請求項４】
パラメトリック境界超曲面を構築するために使用される最適化条件は、所定の条件、特に異常オブジェクトの予測割合ηに基づいた条件、又はデータストリームに動的に適合可能な条件である請求項１〜３の少なくとも１項に記載の方法。
【請求項５】
異常オブジェクトは、正常性の幾何学表現（２２００）、特に正常オブジェクトを囲むパラメトリック境界超曲面、の外部にあるオブジェクトとして決定される請求項１〜４の少なくとも１項に記載の方法。
【請求項６】
正常性の幾何学表現（２２００）の動的適合は、正常性の幾何学表現（２２００）のパラメータxiの自動的調整を有し、少なくとも１つの新しいオブジェクトを組み入れる一方、正常性の幾何学表現（２２００）の最適化を維持する請求項１〜５の少なくとも１項に記載の方法。
【請求項７】
正常性の幾何学表現（２２００）の動的適合は、正常性の幾何学表現（２２００）のパラメータxiの自動的調整を有し、最も関連性のないオブジェクトを除去する一方、正常性の幾何学表現（２２００）の最適化を維持する請求項１〜６の少なくとも１項に記載の方法。
【請求項８】
正常性の最小体積幾何学表現（２２００）はインスタンスtiから維持されており、その後に正常性の幾何学表現（２２００）の構築は最適化条件に実行可能に従う請求項１〜７の少なくとも１項に記載の方法。
【請求項９】
正常性の幾何学表現（２２００）は、表現を記述するためのパラメトリックなベクトルxを生成するサポートベクターマシン法を用いて生成される請求項１〜８の少なくとも１項に記載の方法。
【請求項１０】
正常性の幾何学表現（２２００）の一時的な変化、特に正常性の幾何学表現（２２００）のパラメータベクトルxの一時的な変化は、一時的トレンドの評価のためにデータストリーム（１０００）中に格納される請求項１〜９の少なくとも１項に記載の方法。
【請求項１１】
正常性の幾何学表現（２２００）は球又はその任意の部分である請求項１〜１０の少なくとも１項に記載の方法。
【請求項１２】
流入データストリーム（１０００）は通信ネットワーク中のデータパケット又はその表現を有する請求項１〜１１の少なくとも１項に記載の方法。
【請求項１３】
データオブジェクトは、少なくとも１つのコンピュータの処理時のロギングから発生するエントリ又はその代表を有する請求項１〜１２の少なくとも１項に記載の方法。
【請求項１４】
受信したデータパケットの正常性の決定は、正常な流入データストリームを異常データ、特にスニフィング攻撃及び／又はサービス拒否攻撃、と区別し、それによって正常及び異常データを自動的に決定するための手段が警告メッセージを生成する請求項１２又は１３に記載の方法。
【請求項１５】
正常性の幾何学表現（２２００）の構築及び更新のための方法においては、表現が構築される座標系がデータ空間中の又は特徴空間中の所定の点に固定されている請求項１〜１４の少なくとも１項に記載の方法。
【請求項１６】
座標系の中心は、（オリジナルの又は特徴空間の）データ空間の質量中心に一致する請求項１５に記載の方法。
【請求項１７】
オブジェクトの正常性又は異常性の決定は、データ中心の（又は特徴空間中心の）座標系におけるそのノルムに基づいて、又は前記座標系の原点に中心を置いて所定のオブジェクトを囲む超球面の半径によって決定される請求項１５又は１６に記載の方法。
【請求項１８】
表現の更新は座標系の更新を有する請求項１５〜１７の１項に記載の方法。
【請求項１９】
座標系の更新は座標系の中心の更新を有する請求項１５〜１８の１項に記載の方法。
【請求項２０】
新しいオブジェクトのインポートは、作業集合内の全てのオブジェクトのノルムの更新を一部として有し、拡張した作業集合（「ノルム拡張」）に対応する新しい座標系にそれらをもたらす請求項１５〜１９の１項に記載の方法。
【請求項２１】
オブジェクトの除去は、作業集合内の全てのオブジェクトのノルムの更新を一部として有し、収縮した作業集合（「ノルム収縮」）に対応する新しい座標系にそれらをもたらす請求項１５〜２０の１項に記載の方法。
【請求項２２】
特にデータ集合及び／又は信号を有するデータストリーム中の異常オブジェクトを自動的オンライン検出及びクラス分類するためのシステムであって、
a）正常及び異常オブジェクトを有する少なくとも１つの流入データストリーム（１０００）を検出するための手段、
b）以下を有する自動的オンライン異常性検出エンジン、
−少なくとも１つの所定の最適化条件に従う時刻t１におけるデータストリーム（１０００）の流入オブジェクトの正常性の幾何学表現（２２００）の、特に有限数の正常オブジェクトを囲む超曲面の構築のために、時刻t２＞t１における少なくとも１つの受信オブジェクトに対して正常性の幾何学表現（２２００）のための、少なくとも１つの所定の最適化条件に従う自動的オンライン適合手段を備える自動的構築手段（２１００）、及び
−正常性の幾何学表現（２２００）に対する時刻t２における受信オブジェクトに対する正常性クラス分類の自動的オンライン決定手段、
c）生成された正常性クラス分類（２３００）に基づいて、さらなる処理のための異常データを記述するデータ集合、特に視覚的表現、を生成する正常オブジェクト及び異常オブジェクトの自動的クラス分類手段（４０００）、
を特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は請求項１に係る、データストリーム中の異常オブジェクトを自動的にオンラインで検出及びクラス分類するための方法、並びに請求項２２にかかるその目的のシステムに関する。
【背景技術】
【０００２】
実用アプリケーションのデータ分析においては、データ集合の内容を、その内容が所定のクラスに属するように評価することが必要な場合が多い。
【０００３】
一例として、測定値を正常及び異常クラスにクラス分類することがある。「正常」と「異常」との間の数学的境界は通常、満たされるか満たされないかのどちらかの数学的条件である。
【０００４】
従来技術（例えば米国特許第5,640,492、5,649,492、6,327,581号明細書、及び以下の学会誌記事：Cortes,  C.  and  Vapnik,  V.  "Support  Vector  Networks".  Machine  Learning,  1995,  20:  273−297  K.R.  Muller  and  S.  Mika  and  G.  Ratsch  and  K.  Tsuda  and  B.  Scholkopf："An  Introduction  to  Kernel−Based  Learning  Algorithms",  IEEE  Transactions  on  Neural  Networks,  2001,  12：  181−201）によると、オフライン（バッチ）訓練プロセスの結果として適合可能なクラス分類を作る方法が知られている。また、適合可能なクラス分類を、連続的データストリームから得られた訓練データのバッチに繰り返し適用することも可能である（例えば米国特許出願公開第2003／0078683号明細書）。
【０００５】
従来技術（例えば記事：P.A.  Porras,  and  P.G.  Neumann,,  "Emerald：  event  monitoring  enabling  responses  to  anomalous  live  disturbances",  Proc.  National  Information  Systems  Security  Conference,  1997,  pp.353−365、及びC.  Warrender,  S.  Forrest  and  B.  Perlmutter,  "Detecting  intrusions  using  system  calls：  alternative  data  methods",  Proc.  IEEE  Symposium  on  Security  and  Privacy,  1999,  pp.133−145）によると、正常性の概念があらかじめモデルとして定められている場合に、外れ値をオンラインで、すなわち１つの例を一度に、検出する方法が知られている。
【０００６】
しかし、データの連続的なストリーム中の外れ値を検出し、同時に正常性の表現を構築して、新しいデータの到着又は以前のデータの除去に伴いその表現を動的に調整する方法は知られていない。このような形態のデータ処理が本発明の範囲を構成する。
【０００７】
リアルタイムなアプリケーションの問題は、オフライン分析がしばしば実行可能でなく又は望ましくないということにある。
【０００８】
このようなアプリケーションの１つの例としては、コンピュータネットワークを介してのハッカーによるコンピュータシステムへの攻撃を検出することがある。
【０００９】
「正常」な特徴がわかっていても、攻撃がデータストリーム中にどのように表されるのかを事前に定義することはできない。
【００１０】
事前にわかっているのは、正常な状態からの所定の逸脱が生じるということだけである。
【００１１】
本発明は、そのような状態において、分析に使用されるクラス分類の基準についての明確な知識なしにデータ集合がリアルタイムで分析されることに関する。
【特許文献１】米国特許第５,６４０,４９２号明細書
【特許文献２】米国特許第５,６４９,４９２号明細書
【特許文献３】米国特許第６,３２７,５８１号明細書
【特許文献４】米国特許出願公開第２００３／００７８６８３号明細書
【非特許文献１】Cortes,  C.  and  Vapnik,  V.  "Support  Vector  Networks"  Machine  Learning,1995,20:273−297
【非特許文献２】K.R.  Muller  and  S.  Mika  and  G.  Ratsch  and  K.  Tsuda  and  B.  Scholkopf:  "An  Introduction  to  Kernel−Based  Learning  Algorithms"  IEEE  Transactions  on  Neural  Networks,  2001,12:181−201
【非特許文献３】P.A.  Porras,  and  P.G.  Neumann:  "Emerald:  event  monitoring  enabling  responses  to  anomalous  live  disturbances"  Proc.  National  Information  Systems  Security  Conference,  1997,  pp.353−365
【非特許文献４】C.  Warrender,  S.  Forrest  and  B.  Perlmutter,  "Detecting  intrusions  using  system  calls：  alternative  data  methods",  Proc.  IEEE  Symposium  on  Security  and  Privacy,  1999,  pp.133−145
【非特許文献５】G.  Cauwenberghs  and  T.  Poggio："Incremental  and  Decremental  Support  Vector  Learning"  Advances  in  Neural  Information  Processing  Systems  NIPS  2000,  vol.13,  pages409−415,  （2001）
【非特許文献６】D.M.J.  Tax  and  R.P.W.  Duin："Support  Vector  Data  Description"  Pattern  Recognition  Letters,vol.20,  pages1191−1199,（1999）
【非特許文献７】SCHOLKOPF  B.  AND  SMOLA  A.J.:  "Learning  with  Kernels,  Support  Vector  Machines,  Regularization,  Optimization,  and  Beyond"  2002,  MIT  PRESS,  CAMBRIDGE,  MASS,  USA,  XP002316053,  page227−page250,  page312−page329
【非特許文献８】MUKKAMALA  S.,  JANOSKI  G.  AND  SUNG  A.:  "Intrusion  Detection  Using  Neural  Netwarks  and  Support  Vector  Machines"  PROCEEDINGS  OF  THE  2002  INTERNATIONAL  JOINT  CONFERENCE  ON  NEURAL  NETWORKS,  vol.2,  2002,  pages1702−1707,  XP002316051,  sectionsIIIandIV
【非特許文献９】NGUYEN  B.V.:"Application  of  Support  Vector  Machines  to  Anomaly  Detection"  FINAL  PROJECT  FOR  CS681RESEARCH  IN  COMPUTER  SCIENCE−SUPPORT  VECTOR  MACHINES−FALL  2002,  September  2002  (2002−09),  XP002316052,  whole  document
【非特許文献１０】DESOBRY  F.  AND  DAVY  M.:"Support  Vector−Based  Online  Detection  of  Abrupt  Changes"  2003  IEEE  INTERNATIONAL  CONFERENCE  ON  ACOUSTICS,  SPEECH,  AND  SIGNAL  PROCESSING  ICASSP  2003,  6  April  2003  (2003−04−06),  −10  April  2003  (2003−04−10)  pagesIV872−IV875,  XP010641299  sections1−3
【発明の開示】
【００１２】
本発明は、図面を例として以下に説明される。
【００１３】
連続的なデータストリーム中の異常オブジェクトのオンラインでの検出及びクラス分類のためのシステム及び方法が開示されている。
【００１４】
図１には、１つの実施例のデータフローが示されている。
【００１５】
システム及び方法の実施例の全体的な構成が図１に示されている。システムの入力は、所定のアプリケーションに関する正常及び異常オブジェクトを含むデータストリーム１０００である。以下では、データストリーム１０００は、コンピュータネットワークの流入データであるものと仮定する。本発明に係るシステムは、ハッカー攻撃を示し得る前記データストリーム１０００中の異常オブジェクトを検出するために使用される。
【００１６】
データストリーム１０００は、通信ネットワーク中のデータパケットである。
【００１７】
または、データストリーム１０００は、アクティビティログのエントリ、操作機械装置の物理的特性の測定値、化学プロセスのパラメータの測定値、生物学的活動の測定値等でもよい。
【００１８】
本発明に係る方法及びシステムの中心的特徴は、それがオンライン状態で連続的なデータストリーム１０００を扱い得ることにある。本文脈において「連続的な」という語は、データ集合が、システムによって規則的又は不規則的に受信されて（例えばランダムバースト）、一度に１つ処理されることを意味する。
【００１９】
本文脈において「オンライン」という語は、システムが大々的なセットアップ及びチューニングの段階なしのデプロイ直後に流入データを処理開始可能であることを意味する。システムのチューニングは、その操作のプロセスにおいて自動的に実行される。これは、チューニング段階が（ニューラルネットワーク及びサポートベクターマシンに基づくシステムとのような）大々的な訓練又は（エキスパートシステムとのような）手動相互作用を有するオフラインモードと対照的である。
【００２０】
システムはまた、オフラインモードで操作することもできる。これにより、データストリーム１０００から取得されたデータは、さらなる処理段階で使用される前にデータベース１１００に格納される。かかるモードは、流入データのボリュームが処理システムの全範囲を越え、データベース中の中間的バッファリングが要求される状態において使用される。
【００２１】
アプリケーションを混合モードで（例えばデータの不規則性が強い場合において）操作することも可能である。この場合、全データストリームの少なくとも一部は、連続的な流入データストリーム１０００である。
【００２２】
この場合、システムは、新しいデータが入手可能な限りデータストリーム１０００からデータを読み取る。入手される新しいデータがない場合は、システムはその入力をデータベースに切り替えて以前にバッファされたデータを処理する。一方、データストリーム１０００中のデータの到着速度がシステムの処理能力を越えている場合は、データはデータベースに転向されて後に処理される。このようにして、コンピューティング資源の最適利用が達成される。
【００２３】
流入オブジェクトの各々は特徴抽出ユニット１２００に供給される。特徴抽出ユニット１２００は、所定のアプリケーションに関連する特徴１３００を取得するために要する事前処理を実行する。
【００２４】
特徴抽出ユニットの目的は、データの内容に基づいて、オンライン異常性検出エンジン２０００におけるその後の分析に適した特性（「特徴」）の集合を計算することである。こうした特性は以下の要求のいずれかを満たす必要がある：
a）各特性は数値量（実数又は複素数）、又は
b）特性集合は、内積空間においてベクトルを形成する（すなわちコンピュータプログラムが、前記特性集合を引数とみなして前記特性集合に関する定数又はスカラー積による加算、乗算の操作を実行する）、又は
c）非線形写像が与えられて、特性集合がいわゆる再生核ヒルベルト空間（Reproducing  Kernel  Hilbert  Space（RKHS））に変換される。後者の要求は、前記特性集合を引数とみなして２つ特性集合間のkernel関数を計算するコンピュータプログラムを与えることによって満たされる。このプログラムによって実現される関数は「Mercer条件」として知られる条件を（正確に又は近似的に）満たす必要がある。
【００２５】
システムの実施例において、特徴は以下のようにできる（がそれに限られるわけではない）。
−IP送信元アドレス
−IP宛先アドレス
−TCP送信元ポート
−TCP宛先ポート
−TCPシーケンス番号
−TCP肯定応答番号
−TCP  URGフラグ
−TCP  ACKフラグ
−TCP  PSHフラグ
−TCP  RSTフラグ
−TCP  SYNフラグ
−TCP  FINフラグ
−TCP  TTLフィールド
−TCP接続の開始
−TCP接続の持続時間
−送信元から宛先へ伝送されたバイト数
−宛先から送信元へ伝送されたバイト数
【００２６】
特性の全集合は、課された要求を総じて満たさない場合は、特性部分集合に分割され得る。この場合、部分集合は別々のオンライン異常性検出エンジンによって処理される。
【００２７】
データと同様に、特徴は、何らかの理由により特徴の中間的なストレージが所望される場合は、特徴データベース１４００にバッファすることが可能である。
【００２８】
または、流入オブジェクトが検出／クラス分類方法に直接使用されるようになっている場合は、特徴抽出ユニット１２００は不要である。
【００２９】
次に、特徴１３００はオンライン異常性検出エンジン２０００に送られる。
【００３０】
オンライン異常性検出エンジン２０００の主要ステップ２１００は、正常性概念の幾何学表現を構築及び更新することを有する。
【００３１】
オンライン異常性検出２０００は本発明の核心を構成する。その動作の主要原理は正常性の幾何学表現２２００の構築及び維持にある。幾何学表現は、超曲面（すなわち高次元空間内の多様体）の形で構築される。超曲面は、データストリーム中に含まれる選択された例、及び超曲面の形状を制御するパラメータに依存する。かかる超曲面の例は以下のようにできる（がそれに限られるわけではない）。
−超平面
−超球面
−超楕円面。
【００３２】
オンライン異常性検出エンジンは以下のコンポーネントからなる：
−幾何学表現の構築及び更新用ユニット２１００
−ユニット２１００によって生成された幾何学表現用ストレージ２２００、及び
−異常性検出ユニット２３００。
【００３３】
オンライン異常性検出エンジン２０００の出力は異常性警告３１００である。異常性警告３１００は、グラフィカルユーザインターフェイス、異常性ロギングユーティリティ、又は異常性への自動応答用コンポーネントにおいて使用することができる。ハッカー攻撃識別の実施例において、異常性警告のコンシューマは各々、セキュリティ監視システム、セキュリティ監査ソフトウェア、又はネットワーク設定ソフトウェアである。
【００３４】
または、オンライン異常性検出エンジンの出力は、さらに異常性のクラス分類に使用することができる。かかるクラス分類は、クラス分類ユニット４０００によって実行される。クラス分類ユニット４０００は、例えばニューラルネットワーク、サポートベクターマシン、フィッシャー判別クラス分類器などの周知のクラス分類方法のいずれかを利用してよい。異常性クラス分類メッセージ４１００は、同じセキュリティ管理コンポーネントにおいて異常性警告として使用することができる。
【００３５】
１つの実施例においては、正常性の幾何学表現２２００は、異常オブジェクトの所定の割合に一致する全ての可能な曲面における最小体積を囲むパラメトリックな超曲面である（図４及び５の例を参照）。
【００３６】
または、正常性の幾何学表現２２００は、異常オブジェクトの動的に適合された割合に一致する全ての可能な曲面における最小体積を囲むパラメトリックな超曲面である。図６に例を示す。
【００３７】
前記超曲面は、データオブジェクト（「kernel関数」）間の適切に定義される類似関数によってもたらされる特徴空間内に構築される。データオブジェクト（「kernel関数」）は、前記関数が前記特徴空間内の内積として振る舞うための条件（「Mercer条件」）を満たす。前記正常性の幾何学表現２２００の更新には、流入データストリーム１０００からの最新のオブジェクトを組み込むための調整、及び正常性の幾何学表現２２００（すなわち超曲面）によって囲まれた最小体積のカプセル化を維持するための最も関連性のないオブジェクトを除去するための調整が含まれる。これには、システムによって自動的に解決される最小化問題が含まれる。
【００３８】
正常性の幾何学表現２２００の構築及び更新は図２に関連してより詳細に説明される。
【００３９】
ひとたび正常性の幾何学表現が自動的に更新されると、オンライン異常性検出エンジン２０００によって異常性検出２３００が自動的に実行され、オブジェクトに以下に割り当てる。
−オブジェクトが正常性の幾何学表現２２００によって包含された体積に該当する場合は、正常オブジェクトの状態、又は
−エントリが正常性の幾何学表現２２００によって包含された体積から外れている場合は、異常オブジェクトの状態。
【００４０】
オンライン異常性検出エンジン２０００の出力は、異常性警告３１００を発するために、及び／又はクラス分類コンポーネント４０００をトリガーするために使用される。クラス分類コンポーネント４０００は、決定木、ニューラルネットワーク、サポートベクターマシン（SVM）、フィッシャー判別等のような周知のクラス分類方法を利用することができる。
【００４１】
本発明に関連するサポートベクターマシンの使用は付録Aに記載されている。
【００４２】
正常性の幾何学表現２２００は、これが本方法によって要求される場合にはクラス分類コンポーネントに与えることもできる。
【００４３】
正常性の幾何学表現２１００の構築及び更新の実施例において、正常イベントのクラスを表す超曲面は、パラメータx１,...,xn（i＝l...n）の集合によって表現され、１つのパラメータは作業集合内の各オブジェクトに対応する。
【００４４】
作業集合のサイズnは、ユーザによって事前に選択される。この理由は以下の２つである：
１．データ集合が極めて大きく（何万もの例）、全ての点を平衡状態に維持することがコンピュータ計算上実現不可能（必要なメモリが多大すぎる、又は長時間かかりすぎる）であること。この場合、最も関連性があるとみなされた例のみが保たれる。例の重みはクラス分類に対する例の関連性に依存するため、その重みは、除外される例を決定するために関連性ユニットにおいて使用される。
２．データが一時的な構造を有しており、最新の要素のみが関連すると考えられること。この場合、最も古い例までやり通さなければならず、これは、一時的な構造が示された場合に関連性ユニットが行うことである。
【００４５】
パラメータはさらに非負に制限されており、C＝l／（nν）以下の値を有するように制限される。ここで、νは、ユーザによって設定される、データストリーム中の異常イベント予測割合（例えば２５％の予測外れ値に対しては０.２５）である。この推定は、システムに与えられるアプリオリな知識にすぎない。システムには、他に、kernel依存のパラメータがあってもよい。こうしたパラメータは、オブジェクトの幾何学形状に関する（入手可能であれば）所定の事前知識を反映する。
【００４６】
これは非常に弱い制限である。というのは、かかる推定は容易に入手可能であるためである。
【００４７】
作業集合は以下に区切られる。
パラメータxkがゼロに等しいオブジェクトの「集合０」、
パラメータxkがCに等しいオブジェクトの「集合E」、
残りのオブジェクトの「集合S」。
【００４８】
正常性の幾何学表現の構築及び更新２１００の操作は図２に示されている。
【００４９】
データオブジェクトkの到着に際し、以下の３つの主要な動作がループ内で実行される：
ステップA２.５において、データエントリは作業集合の中に「インポート」される。
ステップA２.６において、作業集合で最も関連性のないデータオブジェクト１が求められる。そして、
ステップA２.７において、データエントリ１が作業集合から除去される。
【００５０】
インポート及び除去の操作により、超曲面に囲まれて、異常オブジェクトの所定の予測割合に一致する最小体積が維持される。
【００５１】
さらに複雑な幾何学形状に対しては、体積推定は最適化基準として使用されてもよい。というのは、超楕円面のようなさらに複雑な曲面に対しては、体積の正確な知識が入手不可能かもしれないためである。
【００５２】
こうした操作は、付録Cにさらに詳細に説明されている。データオブジェクトの関連性は、オブジェクト上のタイムスタンプによって又はオブジェクトに割り当てられたパラメータxiの値によって判断することができる。
【００５３】
ステップA２.１からステップA２.４までは、システムを平衡状態にするほどの十分なデータオブジェクトが観測されていない（すなわち超曲面を構築するほど十分なデータがない）場合に実行される初期化操作である。
【００５４】
最小体積を囲み、異常オブジェクトの所定の予測割合に一致する超曲面の構築は、"Support  Vector  Data  Description"  by  D.M.J.  Tax  and  R.P.W.  Duin,  Pattern  Recognition  Letters,  vol.  20,  pages1191−1.199,（1999）という記事に示されているように、以下の数学的プログラミング問題を解決することを意味する：
2007503034.tif 000003
ここで、Kを、作業集合の全てのデータ点に対する所定のkernel関数の評価からなるn×n行列：Ki,j＝kernel（pi,pj）とする。
【００５５】
例えば、オブジェクトがn次元空間のベクトルであり、線形特徴空間で解を求めると、kernel関数は以下のように評価される：
2007503034.tif 000004
【００５６】
別の例として、解が、（n無限次元空間である）ラジアル基底関数の特徴空間内の空間であれば、kernel関数は以下のように計算される：
2007503034.tif 000005
ここで、γはkernelパラメータである。
【００５７】
式（１）において、cはKの主対角の数のベクトルであり、aはn個の１のベクトルであり、b＝−１である。
【００５８】
パラメータCは、異常オブジェクトの予測割合に関連する。
【００５９】
問題（１）の解によって得られる表現を最適化するための必要十分条件は、周知のKarush−Kuhn−Tucker条件によって与えられる。
【００６０】
作業集合の全ての点が前記条件を満たす場合、作業集合は平衡状態にあるという。
【００６１】
新しいデータオブジェクトを作業集合の中にインポート又は既存のデータオブジェクトを作業集合から除去することは、前記条件の違反を生じ得る。かかる場合においては、作業集合を平衡状態に戻すためにパラメータx１,...,xnの調整が必要となる。
【００６２】
異なる数学的プログラミング問題に対し、かかる調整をKarush−Kuhn−Tucker条件に基づいて実行するためのフレームワークは、"Incremental  and  Decremental  Support  Vector  Learning"  by  G.  Cauwenberghs  and  T.  Poggio,  Advances  in  Neural  Information  Processing  Systems  13,  pages409−415,  （2001）という記事に提示されている。
【００６３】
幾何学表現の調整を実行するためのアルゴリズムは付録Cに、より詳細に記載されている。
【００６４】
図２に記載されているオンライン異常性検出エンジンの操作の初期段階においては特別な注意が必要である。作業集合内のデータオブジェクトの数が１／Ｃ以下（１／Ｃ以下の最大整数）である場合は、平衡状態は達成できずにインポート方法は適用されない。本発明の初期化ステップA２.１〜A２.４は、この特別の場合を扱うように設計されており、できるだけ少数のデータオブジェクトが見出された後に作業集合を平衡状態にするように設計されている。
【００６５】
コンピュータ侵入を検出及びクラス分類するための、システム内のオンライン異常性検出方法の実施例は図３に示されている。
【００６６】
オンライン異常性検出エンジン２０００は、ネットワークパケット及びコンピュータの監査ログの記録を含むデータストリーム１０００（監査ストリーム）を分析するために使用される。パケット及び記録は分析対象のオブジェクトとなる。
【００６７】
監査ストリーム１０００は、関連性のある特徴を抽出する一式のフィルタを有する特徴抽出コンポーネント１２００に入力される。
【００６８】
抽出された特徴は、オンライン異常性検出エンジン２０００によって読み取られる。オンライン異常性検出エンジン２０００は異常オブジェクト（パケット又はログエントリ）を識別し、イベントが異常であると発見した場合はイベント警告を発する。検知された異常イベントのクラス分類は、イベントデータベース内に収集及び格納された異常イベントをクラス分類するように事前に訓練されたクラス分類コンポーネント４０００によって実行される。
【００６９】
オンライン異常性検出エンジンは、流入データ、有限の作業集合、及びパラメトリックな超曲面による正常（非異常）データオブジェクトの幾何学表現を格納するためのメモリを備える処理ユニット；流入データの処理用プログラムを有する格納されたプログラム；並びに格納されたプログラムによって制御されるプロセッサを有する。プロセッサは、正常データオブジェクトの幾何学表現を構築及び更新するための、並びに格納された正常データオブジェクトの表現に基づいて異常オブジェクトを検出するためのコンポーネントを有する。
【００７０】
幾何学表現を構築及び更新するためのコンポーネントは、データオブジェクトを受信して表現の中にインポートし、超曲面によって囲まれて異常オブジェクトの所定の予測割合に一致する最小体積が維持される。コンポーネントはさらに、作業集合中の最も関連性のないエントリを識別し、超曲面によって囲まれた最小体積を維持している間にそれを除去する。異常オブジェクトの検出は、オブジェクトが正常性を表す超曲面の内部に該当するか又は外部に該当するかをチェックすることによって実行される。
【００７１】
本発明の実施例として、コンピュータ侵入の検出及びクラス分類のためのシステムアーキテクチャが開示される。システムは、監査ストリームからデータを受信する特徴抽出コンポーネント；オンライン異常性検出エンジン；並びに所定のイベントのデータベースに基づいて訓練されたイベント学習エンジンによって生成されるクラス分類コンポーネントからなる。
【００７２】
図４及び図５に、正常性の幾何学表現２２００の構築が、特に初期化に関連して記載されている。
【００７３】
最適化基準に対するデータ集合の最適な正常性の幾何学表現２２００を見出すためには、所定最小数のオブジェクトが必要である。上記例（すなわち図３）を参照すると、これはコンピュータネットワークの何らかの流入データを集める必要があるということである。
【００７４】
各オブジェクトは、パラメータCによって拘束される個別重みα１を有する。最適な表現に対しては、α１の合計は１になる必要がある。オブジェクトの集合が非常に小さければ、最適化基準を満たすことはできない。
【００７５】
７つのオブジェクトの最小数が必要となるような単純な例を考える（図４A〜図４C参照）。図４Aにおいて星印でプロットされた第１の６個のオブジェクトには最大重みCが与えられており、最適化基準は満たされていない。
【００７６】
ウィンドウサイズ（window  size）が１００例であり、予測外れ値割合は７％であると仮定する。C＝１／７という値が計算できる。システムを平衡状態にするためには、全ての制約が満たされなければならない。すなわち、全てのa_iが＜＝１／７である必要があるが、それらの合計は１に等しい必要がある。これらの２つの制約が、少なくとも７点を観測した後に満たされることは容易にわかる。
【００７７】
図４Bにマル印で示された７番目のオブジェクトを追加した後に、その重み、及び他のオブジェクトの重みが最適化可能となる（すなわち、幾何学表現を見出す最小化ルーチンに従うことができる。この２次元のデータ集合においては、最小領域を囲むオブジェクトのまわりの閉曲線）。
【００７８】
新しいオブジェクトはその重みαを増加させる一方、その他のオブジェクトはその重みαを減少させて重みの総計を維持する。これらの２つのオブジェクトは図４Bにおいて「x」印で示されている。
【００７９】
最適化の最終ステップでは、追加されたオブジェクトは上側重み境界に到達する。これは、図４Cにおいて、マーカが星印に変化することで示されている。
【００８０】
この図の曲線は、その後の全ての図と同様に、正常性の表現の形を意味する。なお、正常性領域内に点がないことがやや奇妙に思われるかもしれないが、数の異常性の上側境界に関する保証は、少なくともn＝window_sizeとなる点が見出された後になって初めて満たすことができる。それまでは、実行可能な解が存在しても、この解の統計的特徴を強制することはできない。
【００８１】
図５A〜図５Gに、新しいオブジェクトを既存のクラス分類器（すなわち、既に存在ｓている正常性の幾何学表現２２００）に組み込むプロセスが示されている。例えば図５Aに示されているように、閉曲線２２００の外部にいくつかのオブジェクトがあり、これらのオブジェクトが「異常」と考えられることが示されている。
【００８２】
図５Aは２０個のオブジェクトの散乱プロットを示す。このデータ集合については、クラス分類器が訓練され（すなわち上記のような最小化）、決定境界としての正常性の幾何学表現２２００がプロットされている。
【００８３】
以下の３つのタイプのデータオブジェクトが示されている：
−点状のオブジェクトは、ターゲットオブジェクトとしてクラス分類される（すなわち「正常な」）オブジェクトである。これらのオブジェクトは、「残り」集合すなわち集合Rに属するといえる。これらのオブジェクトは重み０を有する。
−星状のオブジェクトは、クラス分類器によって拒否される（すなわち「異常な」）オブジェクトであり、このため、エラー集合Eに属する。これらの重みは最大値Cを有する。
−最後に、「x」で示される正常性の幾何学表現２２００の曲線上のオブジェクトは、サポートベクトル（集合Sに属する）であり、非ゼロの重みを有しているが、拘束はされていない。
【００８４】
図５Bでは、新しいオブジェクトが位置（２,０）に追加されている。このオブジェクトは、この時点でサポート集合Sに追加されているが、クラス分類器はこの時点では平衡状態から外れている。以下のステップ（図１におけるステップ２１００、２２００、２３００参照）において、その他のオブジェクトの重み及び集合メンバーシップは自動的に適合される。システムが平衡状態に到達するまで、かかる幾何学的解釈は不可能であり、それが図５bから始まることは明確にわかる。新しいオブジェクトを集合Sに追加し、その重みを変化させることができるが、曲線はすぐには新しいオブジェクトを通過させる力になれない。さらに、新たしいオブジェクトのインポートの始まりにおいては、それが新しいオブジェクトを通過するかどうかはわからない。図５c及び全てのその後の図において、マル印はその状態が変化したオブジェクトを示す。最後の図においては、新しいオブジェクトがその最終状態を受信しており、幾何学表現が再び一貫していることがわかる。曲線はバツ印を通過して星印（異常性）を点印（正常点）と分けている。
【００８５】
上記からわかるように、オンライン（リアルタイム）アプリケーションには必須の正常性の幾何学表現は順次更新される。クラス分類に関する事前の仮定はない。クラス分類（すなわち集合に対するメンバーシップ）は、データが受信されている間に自動的に発達する。
【００８６】
次のステップ（図５D）において、同じ変化が別のオブジェクトによってなされる。３つのさらなるステップの後、新しい平衡状態が得られる。このクラス分類器を有して、新しいオブジェクトはこの時点で処理することが可能になる。
【００８７】
図５D〜図５Gは、例が受け得る、アルゴリズムの進展及び様々な可能な状態変化を示す（上述も参照）。図５Dにおいて、オブジェクトは集合Sから集合Oの中に除去される。図５Eにおいて、オブジェクトは集合Eから集合Sに追加される。図５Fにおいて、オブジェクトは集合Sから集合Eの中に除去される。最後に、図５Gにおいて、現在のオブジェクトは集合Eに割り当てられて平衡状態が達成される。
【００８８】
図６A〜図６Dは、外れ値割合パラメータνがデータから自動的に選択される場合を示す。図６A及び図６Bにおいて、全てのデータ点に対してランキング尺度が計算されているのがわかる。この関数の局所的最小値は、「第１選択」（最も小さな最小値）及び「第２選択」（次に小さな最小値）と称する矢印で示されている。これらの最小値は外れ値割合パラメータに対する候補値、約５％又は１５％を与える。これらの値に対応する決定関数は図６C及び図６Dに示されている。
【００８９】
付録Bの、特にセクション２.４には、正常性の幾何学表現（２２００）の具体的な有利な定式化、すなわち四半球、が記載されている。正常性の幾何学表現（２２００）の非対称性は侵入問題のデータストリームに対して十分適合している。
【００９０】
簡単のため、本発明の方法及びシステムは２次元データ集合に関連して記載されている。明らかなことだが、方法及びシステムは任意の次元を伴うデータ集合に対して一般化することも可能である。曲線は、より高次の体積を囲む超曲面でもよい。
【００９１】
本発明はまた、機械装置を操作する物理的パラメータの測定値、化学プロセスの測定値、及び生物学的活動の測定値を監視することに適用することも可能である。一般的には、本発明は、連続的データが受信されてもデータの送信元に関するアプリオリなクラス分類又は知識が入手できない状況に特に適合する。
【００９２】
かかるアプリケーションには、例えば、異なる色や放射線パターンによって異常オブジェクトが区別され得る医学的標本の画像分析がある。別の可能性のある医学的アプリケーションには、EEG又はECG装置から得られる電気信号を表すデータストリームがある。この場合、異常波パターンが自動的に検出可能である。EEGデータを使用して、てんかん発作の差し迫った発生が検知できる。
【００９３】
さらに、機械的又は地球物理学的システムからオンラインで収集されるデータは、本発明の方法及びシステムを使用して分析可能である。機械的応力及びその結果生じる破損を、データから認識することができる。「異常な」データ（すなわち「正常な」データからの逸脱）が受信されるとすぐに、これが顕著な条件確率を示す。
【００９４】
本発明の方法及びシステムはまた、よくあることであるが、パターンがアプリオリにわかっていないパターン認識に応用することも可能である。「異常な」オブジェクトはパターンに属しないオブジェクトである。
【００９５】
また、本発明の方法及びシステムの可能なアプリケーションは金融データに関連する。取引データにおける望ましくないリスクを示す変化を識別するために使用することができる。クレジットカードデータが分析されて、リスク又は詐欺でさえも識別可能である。
【００９６】
付録AにはオンラインSVMの概略が記載されている。付録Bには、四半球法（quarter−sphere  method）を使用する特別なアプリケーションが記載されている。付録Cには、追加の図C２、C３、C５、C６、C７、C１０、C１１、C１２の説明が含まれている。図C２は全体的概略を与える。付録Dは、公式のいくつかを説明する。
【００９７】
［付録A］
2007503034.tif 000006
2007503034.tif 000007
2007503034.tif 000008
2007503034.tif 000009
2007503034.tif 000010
2007503034.tif 000011
2007503034.tif 000012
2007503034.tif 000013
2007503034.tif 000014
2007503034.tif 000015
【００９８】
［付録B］
2007503034.tif 000016
2007503034.tif 000017
2007503034.tif 000018
2007503034.tif 000019
2007503034.tif 000020
2007503034.tif 000021
2007503034.tif 000022
2007503034.tif 000023
2007503034.tif 000024
2007503034.tif 000025
2007503034.tif 000026
2007503034.tif 000027
【００９９】
［付録C］
図C３  −平面／球エージェントのフロー制御ユニットの操作
フロー制御ユニットは以下のデータを引数として読み取る：
−特徴（１３００）のストリームから例「Ｘ」
−ユーザによって設定される操作パラメータ（２１１６）からウィンドウサイズ「Ｗ」
−内部ストレージから平面／球オブジェクト（PSObj）「obj」。このオブジェクトは、平面／球エージェントの初期化ユニット（２１１１）によって生成され、フロー制御ユニットの操作の間中維持される。
【０１００】
以下のアクションシーケンスが、各流入例「Ｘ」に対してループで実行される。
１．オブジェクト「obj」に格納されたデータの現在のサイズがウィンドウサイズ「Ｗ」を越えた場合は、所定の例は新しい例がインポートされる前に除去される必要がある。
２．所定の例を除去するために、最も関連性のない例のインデックス「ind」は、関連性ユニット（２１１４）にリクエストを発することによって計算される。その後、このインデックスを有する例は、「ind」を引数として有する除去ユニット（２１１５）にリクエストを発することによって除去される。オブジェクトの更新された状態は「obj」に格納される。
３．例「Ｘ」のインポートは、「Ｘ」を引数として有するインポートユニット（２１１３）にリクエストを発することによって実行される。オブジェクトの更新された状態は「obj」に格納される。
【０１０１】
結果として生じるオブジェクト「obj」は、フロー制御ユニットの出力データであり、オンライン異常性検出エンジンのその他の部分へ平面／球表現として送られる。
【０１０２】
−平面／球エージェントの初期化ユニットの操作
システム操作のはじめに、システムが平衡状態に入るまでは初期化ユニットがフロー制御ユニットから制御を引継ぐ。それは、floor（１／C）の例が見出されるまで、特徴ストリーム（１３００）から例を読み取り、それらにCの重みを課し、及びそれらを集合Eに入れる。次の例が１−floor（１／C）の重みを得て、集合Ｓに入れられる。その後、制御はフロー制御ユニットに返される。
【０１０３】
図C５  −平面／球エージェントのインポートユニットの操作
インポートユニットは以下のデータを引数として読み取る：
−特徴（１３００）のストリームから例「Ｘ」
−内部ストレージから平面／球オブジェクト（PSObj)。このオブジェクトは、フロー制御ユニットの操作の間中維持される。
【０１０４】
新しい例を読み取る際、インポートユニットは、いくつかの内部データ構造の初期化（内部データ及びkernelストレージの拡張、勾配（gradient）及び感度（sensitivity）のパラメータのためのメモリのアロケーション等）を実行する。
【０１０５】
新しい例を有するシステムの平衡状態のチェックが実行される（すなわち、現在の重みの割り当てがKarush−Kuhn−Tucker条件を満たすかどうかが検証される）。システムが平衡状態に到達した場合は、インポートユニットは終了して、オブジェクト「obj」の現在の状態を出力する。システムが平衡状態にない場合は、かかる状態に到達するまで処理が続行される。
【０１０６】
オブジェクトの状態の最新の更新を構成するために、すなわち、新しい例が追加されたオブジェクトの初期状態に対応する値を計算するために、感度パラメータが更新される。感度パラメータは、流入する例の重みの微小変化に対して作業集合中の全ての例の重み及び勾配の感度を反映する。
【０１０７】
（内部ストレージ中に維持される）集合Ｓが空か否かによって、以下の処理経路の１つがとられる。
【０１０８】
集合Ｓが空の場合、オブジェクトのフリーパラメータ（free parameter）のみがしきい値「b」となる。「b」を更新するために、しきい値「b」の可能な増分が、集合E及びO中の全ての点に対して計算されて、これらの点の勾配がゼロに強制される。勾配感度パラメータは、この操作を効果的に実行するために使用される。かかる増分のうち最小のものが選択され、この増分によってその勾配がゼロになった例が集合Ｓに追加される（及び対応するインデックス集合E又はOから除去される）。
【０１０９】
集合Ｓが空でない場合は、４つの可能な増分が計算されてそれらの中での選択が行われる必要がある。増分「inc_a」は、現在の例の重みの最小増分であり、集合S中の例の重みの誘発変化（induced  change）は、これらの例の重みにボックスの境界をもたらす（すなわち、それがゼロ又はCの値になるように強制する）。この増分は個々に、集合Sの各例に対するかかる可能な全ての増分の最小値として決定され、重み感度パラメータを用いて計算される。増分「ind_g」は、現在の例の重みの最小増分であり、集合E及びO中の例の勾配の誘発変化がこれらの勾配をゼロにする。この増分は個々に、集合E及びOの各例に対するかかる可能な全ての増分の最小値として決定され、勾配感度パラメータを用いて計算される。増分「inc_ac」は、新しい例の重みの可能な増分である。それは、例の重みの上側境界Cと、新しい例の現在の重みa_cとの差として計算される。増分「inc_ag」は新しい例の重みの可能な増分であり、新しい例の勾配はゼロになる。この増分は、新しい例の勾配感度を使用して計算される。
【０１１０】
４つの可能な増分が計算された後、それらのうち最小のもの、及び最小の各増分に関連する例のインデックス「ind」が計算される。前述に従って４つの増分は最小値を与え、以下の処理ステップが行われる：
最小値が増分「inc_a」によって与えられる場合は、インデックス「ind」によって参照される例は集合Sから除去される。
最小値が増分「inc_ac」によって与えられる場合は、インデックス「ind」によって参照される例（この場合それは新しい例）は集合Eに追加される。
その他の残りの場合（「inc_g」及び「inc_gc」)には、インデックス「ind」によって参照される例は集合Sに追加される。
【０１１１】
インデックス集合の組成が更新された後、オブジェクトの状態は更新される。この操作は、計算された増分を、作業集合中の全ての例の重みに及びしきい値「b」に適用することからなる。
【０１１２】
結果として生じるオブジェクト「obj」は、インポートユニットの出力データであり、フロー制御ユニット(２１１２)に送られる。
【０１１３】
図C６  −平面／球エージェントの関連性ユニットの操作
関連性ユニットは以下のデータを引数として読み取る：
−内部ストレージ（２１１７）から平面／球オブジェクト（PSObj）「obj」。このオブジェクトはフロー制御ユニットの操作の間中維持される。
−操作パラメータ（２１１６）からフラグ「TCFlag」。このフラグは、データが一時的構造かどうかを示す。
【０１１４】
「TSFlag」が設定されている場合は、作業集合の最も古い例が最も関連性のない例である。
そうでなければ、以下の選択が行われる：
オブジェクトの集合On（集合Oからのキャッシュされていない例）が空でない場合は、例は集合Onからランダムに選択され、そうでなければ
オブジェクトの集合Oc（集合からのキャッシュされた例）が空でない場合は、例は集合Ocからランダムに選択され、そうでなければ
集合Ｓが空でない場合は、最小重みを有する例が集合Ｓから選択され、そうでなければ
例は集合Eからランダムに選択される。
【０１１５】
関連性ユニットの出力は、選択された例のインデックス「ind」である。それはフロー制御ユニット（２１１２）に送られる。
【０１１６】
図C７  −平面／球エージェントの除去ユニットの操作
除去ユニットは以下のデータを引数として読み取る：
−フロー制御ユニット（２１１２）からインデックス「ind」
−内部ストレージ（２１１７）から平面／球オブジェクト（PSObj）「obj」。このオブジェクトは、フロー制御ユニットの操作の間中維持される。
【０１１７】
入力引数を読み取る際、除去ユニットは、いくつかの内部データ構造の初期化（内部データ及びkernelストレージの収縮、勾配及び感度のパラメータの収縮等）を実行する。
【０１１８】
例「ind」の重みのチェックが実行される。この例の重みがゼロに等しい場合は、制御がフロー制御ユニット（２１１２）に返され、そうでなければ操作が続行されて例「ind」の重みはゼロに到達する。
【０１１９】
オブジェクトの状態の最新の更新を構成するために、すなわち、例「ind」が除去されたオブジェクトの初期状態に対応する値を計算するために、感度パラメータが更新される。感度パラメータは、流出する例の重みの微小変化に対して作業集合中の全ての例の重み及び勾配の感度を反映する。
【０１２０】
（内部ストレージ中に維持される）集合Ｓが空か否かによって、以下の処理経路の１つがとられる。
【０１２１】
集合Ｓが空の場合、オブジェクトのフリーパラメータのみがしきい値「b」となる。「b」を更新するために、しきい値「b」の可能な増分が、集合E及びO中の全ての点に対して計算されて、これらの点の勾配がゼロに強制される。勾配感度パラメータは、この操作を効果的に実行するために使用される。かかる増分のうち最小のものが選択され、この増分によってその勾配がゼロになった例が集合Ｓに追加される（及び対応するインデックス集合E又はOから除去される）。
【０１２２】
集合Ｓが空でない場合は、３つの可能な増分が計算されてそれらの中での選択が行われる必要がある。増分「inc_a」は、例「ind」の重みの最小増分であり、集合S中の例の重みの誘発変化は、これらの例の重みにボックスの境界をもたらす（すなわち、それがゼロ又はCの値になるように強制する）。この増分は個々に、集合Sの各例に対するかかる可能な全ての増分の最小値として決定され、重み感度パラメータを用いて計算される。増分「ind_g」は、現在の例の重みの最小増分であり、集合E及びO中の例の勾配の誘発変化がこれらの勾配をゼロにする。この増分は個々に、集合E及びOの各例に対するかかる可能な全ての増分の最小値として決定され、勾配感度パラメータを用いて計算される。増分「inc_ac」は、例「ind」の重みの可能な増分である。それは、例「ind」の現在の重みa_cとゼロとのマイナスの差として計算される。
【０１２３】
３つの可能な増分が計算された後、それらのうち最小の絶対値を有するもの、及び最小の各増分に関連する例のインデックス「ind」が計算される。前述に従って３つの増分は最小値を与え、以下の処理ステップが行われる：
最小値が増分「inc_a」によって与えられる場合は、インデックス「ind」によって参照される例は集合Sから除去される。
最小値が増分「inca_c」によって与えられる場合は、何も行われない（これは次の反復で検出される終了条件である）。
その他の残りの場合（「inc_g」)には、インデックス「ind」によって参照される例は集合Sに追加される。
【０１２４】
インデックス集合の組成が更新された後、オブジェクトの状態は更新される。この操作は、計算された増分を、作業集合中の全ての例の重みに及びしきい値「b」に適用することからなる。
【０１２５】
ループの終了後、除去された例はパージされる、すなわち、それに関連する全てのデータ構造（kernelキャッシュ、インデックス集合等）は永久にクリアされる。
【０１２６】
結果として生じるオブジェクト「obj」は、インポートユニットの出力データであり、フロー制御ユニット(２１１２)に送られる。
【０１２７】
図C１０  −四半球エージェントのフロー制御ユニットの操作
フロー制御ユニットは以下のデータを引数として読み取る：
−特徴（１３００）のストリームから例「Ｘ」
−ユーザによって設定される操作パラメータ（２１１６）からウィンドウサイズ「Ｗ」
−内部ストレージから四半球オブジェクト（QSObj）「obj」。このオブジェクトは、フロー制御ユニットの操作の間中維持される。
【０１２８】
以下のアクションシーケンスが、各流入例「Ｘ」に対してループで実行される。
１．オブジェクト「obj」に格納されたデータの現在のサイズがウィンドウサイズ「Ｗ」を越えた場合は、所定の例は新しい例がインポートされる前に除去される必要がある。
２．所定の例を除去するために、最小のノルムを有する例のインデックス「ind」が計算される。その後、このインデックスを有する例は、「ind」を引数として有するセンタリングユニット（２１２３）にリクエスト「収縮」を発することによって除去される。オブジェクトの更新された状態は「obj」に格納される。
３．例「Ｘ」のインポートは、「Ｘ」を引数として有するセンタリングユニット（２１２３）にリクエスト「拡張」を発することによって実行される。オブジェクトの更新された状態は「obj」に格納される。
４．オブジェクトの状態は、全ての例のノルムの必要な順序付けを維持するソーティングユニット（２１２４）にリクエストを発することによってさらに更新される。
【０１２９】
結果として生じるオブジェクト「obj」は、フロー制御ユニットの出力データであり、オンライン異常性検出エンジンのその他の部分へ平面／球表現として送られる。
【０１３０】
図C１１  −四半球エージェントのセンタリングユニットの操作
センタリングユニットは、以下のデータを引数として読み取る：
−特徴（１３００）のストリームから例「Ｘ」
−内部ストレージから四半球オブジェクト（QSObj）「obj」。このオブジェクトは、フロー制御ユニット（２１２２）の操作の間中維持される。
−リクエストされた操作「拡張」か「収縮」かを示す２値フラグ「OPFlag」。
【０１３１】
例「X」を読み取る際、センタリングユニットは、この例に対するkernel行、すなわち、作業集合中のこの例及びその他の全ての例に対するkernel値の行ベクトル、を計算する。
【０１３２】
「OPFlag」の値に従って、以下の操作が実行される：
「拡張」操作がリクエストされた場合、
−例「Ｘ」のノルム（「現在のノルム」）の拡張が実行される（添付の技術レポート中の公式参照）
−作業集合中のその他の例のノルムの拡張が実行される
−補助ターム（auxiliary terms）が更新される。
【０１３３】
「収縮」操作がリクエストされた場合、
−作業集合中のその他の例のノルムの収縮が実行される（添付の技術レポート中の公式参照）
−補助タームが更新される。
【０１３４】
結果として生じるオブジェクト「obj」は、センタリングユニットの出力データであり、フロー制御ユニット(２２１２)に送られる。
【０１３５】
図C１２  −四半球エージェントのソーティングユニットの操作
ソーティングユニットは以下のデータを引数として読み取る：
−内部ストレージから四半球オブジェクト（QSObj）「obj」。このオブジェクトは、フロー制御ユニット（２１２２）の操作の間中維持される。
−異常性検出のモードを示す２値フラグ「ModeFlag」：固定された異常性割合に関する検出に対しては「固定」、及び異常性割合がデータから適合的に決定されるモードに対しては「適合」。
【０１３６】
「ModeFlag」の値に従い、ソーティングユニットは、適合モードが示されている場合は通常ソーティング操作（例えばQuickSort）を、固定モードが示されている場合は（ソーティングよりも手軽な）メジアン検索操作を呼び出す。
【０１３７】
ソーティングユニットの出力は、作業集合中の例のノルムの順序付けされたベクトルであり、ここで、順序付けはリクエストされたモードに従う。このベクトルはフロー制御ユニット（２１２２）に送られる。
【０１３８】
［付録D］
2007503034.tif 000028
2007503034.tif 000029
2007503034.tif 000030
2007503034.tif 000031
【図面の簡単な説明】
【０１３９】
【図１】本発明の１つの実施例のフローチャートである。
【図２】正常性の幾何学表現を構築及び更新するための詳細なフローチャートである。
【図３】コンピュータネットワークに関連して異常オブジェクトを検出するための、本発明のシステムの実施例の概略図である。
【図４Ａ】本発明の実施例の初期化の例を示す図である。
【図４Ｂ】本発明の実施例の初期化の例を示す図である。
【図４Ｃ】本発明の実施例の初期化の例を示す図である。
【図５Ａ】本発明の実施例のさらなる処理の例を示す図である。
【図５Ｂ】本発明の実施例のさらなる処理の例を示す図である。
【図５Ｃ】本発明の実施例のさらなる処理の例を示す図である。
【図５Ｄ】本発明の実施例のさらなる処理の例を示す図である。
【図５Ｅ】本発明の実施例のさらなる処理の例を示す図である。
【図５Ｆ】本発明の実施例のさらなる処理の例を示す図である。
【図５Ｇ】本発明の実施例のさらなる処理の例を示す図である。
【図６Ａ】２つの自動的に選択された異常性割合から生じる決定境界を示す図である。
【図６Ｂ】２つの自動的に選択された異常性割合から生じる決定境界を示す図である。
【図６Ｃ】２つの自動的に選択された異常性割合から生じる決定境界を示す図である。
【図６Ｄ】２つの自動的に選択された異常性割合から生じる決定境界を示す図である。
【図１】
2007503034.tif 000032
【図２】
2007503034.tif 000033
【図３】
2007503034.tif 000034
【図４Ａ】
2007503034.tif 000035
【図４Ｂ】
2007503034.tif 000036
【図４Ｃ】
2007503034.tif 000037
【図５Ａ】
2007503034.tif 000038
【図５Ｂ】
2007503034.tif 000039
【図５Ｃ】
2007503034.tif 000040
【図５Ｄ】
2007503034.tif 000041
【図５Ｅ】
2007503034.tif 000042
【図５Ｆ】
2007503034.tif 000043
【図５Ｇ】
2007503034.tif 000044
【図６Ａ】
2007503034.tif 000045
【図６Ｂ】
2007503034.tif 000046
【図６Ｃ】
2007503034.tif 000047
【図６Ｄ】
2007503034.tif 000048
【図Ｃ２】
2007503034.tif 000049
【図Ｃ３】
2007503034.tif 000050
【図Ｃ５】
2007503034.tif 000051
【図Ｃ６】
2007503034.tif 000052
【図Ｃ７】
2007503034.tif 000053
【図Ｃ１０】
2007503034.tif 000054
【図Ｃ１１】
2007503034.tif 000055
【図Ｃ１２】
2007503034.tif 000056
【手続補正書】
【提出日】平成17年6月20日(2005.6.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
特にデータ集合及び／又は信号を有するデータストリーム中の異常オブジェクトを自動的にオンライン検出及びクラス分類するための方法であって、
a）正常及び異常オブジェクトを有する少なくとも１つの流入データストリーム（１０００）の検出、
b）少なくとも１つの所定の最適化条件に従う時刻t1におけるデータストリーム（１０００）の流入オブジェクトの正常性の幾何学表現（２２００）の自動的構築（２１００）であって、特に有限数の正常オブジェクトを囲む超曲面の構築、
c）正常性の最適幾何学表現、特に正常性の最小体積幾何学表現（２２００）はインスタンスtiから維持されており、その後に正常性の幾何学表現（２２００）の構築は最適化条件に実行可能に従うこと、
d）時刻t2＞t1における少なくとも１つの受信オブジェクトに対する正常性の幾何学表現（２２００）の、少なくとも１つの所定の最適化条件に従うオンライン適合、
e）正常性の幾何学表現（２２００）に対する時刻t2における受信オブジェクトに対する正常性／異常性クラス分類のオンライン決定（２３００）、
f）生成された正常性クラス分類（２３００）に基づいて、さらなる処理のための異常データを記述するデータ集合、特に視覚的表現、を生成する正常オブジェクト及び異常オブジェクトの自動的クラス分類、
を特徴とする方法。
【請求項２】
請求項１に記載の方法であって、正常性の幾何学表現（２２００）は、全ての可能な曲面中の最小体積又は最小体積推定の閉空間を最適化条件として使用するパラメトリック境界超曲面である方法。
【請求項３】
超曲面は、少なくとも１つの流入データストリーム（１０００）のオリジナル測定値空間内又はその非線形変換によって得られる空間内に構築される請求項２に記載の方法。
【請求項４】
パラメトリック境界超曲面を構築するために使用される最適化条件は、所定の条件、特に異常オブジェクトの予測割合ηに基づいた条件、又はデータストリームに動的に適合可能な条件である請求項１〜３の少なくとも１項に記載の方法。
【請求項５】
異常オブジェクトは、正常性の幾何学表現（２２００）、特に正常オブジェクトを囲むパラメトリック境界超曲面、の外部にあるオブジェクトとして決定される請求項１〜４の少なくとも１項に記載の方法。
【請求項６】
正常性の幾何学表現（２２００）の動的適合は、正常性の幾何学表現（２２００）のパラメータxiの自動的調整を有し、少なくとも１つの新しいオブジェクトを組み入れる一方、正常性の幾何学表現（２２００）の最適化を維持する請求項１〜５の少なくとも１項に記載の方法。
【請求項７】
正常性の幾何学表現（２２００）の動的適合は、正常性の幾何学表現（２２００）のパラメータxiの自動的調整を有し、最も関連性のないオブジェクトを除去する一方、正常性の幾何学表現（２２００）の最適化を維持する請求項１〜６の少なくとも１項に記載の方法。
【請求項８】
正常性の幾何学表現（２２００）は、表現を記述するためのパラメトリックなベクトルxを生成するサポートベクターマシン法を用いて生成される請求項１〜７の少なくとも１項に記載の方法。
【請求項９】
正常性の幾何学表現（２２００）の一時的な変化、特に正常性の幾何学表現（２２００）のパラメータベクトルxの一時的な変化は、一時的トレンドの評価のためにデータストリーム（１０００）中に格納される請求項１〜８の少なくとも１項に記載の方法。
【請求項１０】
正常性の幾何学表現（２２００）は球又はその任意の部分である請求項１〜９の少なくとも１項に記載の方法。
【請求項１１】
流入データストリーム（１０００）は通信ネットワーク中のデータパケット又はその表現を有する請求項１〜１０の少なくとも１項に記載の方法。
【請求項１２】
データオブジェクトは、少なくとも１つのコンピュータの処理時のロギングから発生するエントリ又はその代表を有する請求項１〜１１の少なくとも１項に記載の方法。
【請求項１３】
受信したデータパケットの正常性の決定は、正常な流入データストリームを異常データ、特にスニフィング攻撃及び／又はサービス拒否攻撃、と区別し、それによって正常及び異常データを自動的に決定するための手段が警告メッセージを生成する請求項１１又は１２に記載の方法。
【請求項１４】
正常性の幾何学表現（２２００）の構築及び更新のための方法においては、表現が構築される座標系がデータ空間中の又は特徴空間中の所定の点に固定されている請求項１〜１３の少なくとも１項に記載の方法。
【請求項１５】
座標系の中心は、（オリジナルの又は特徴空間の）データ空間の質量中心に一致する請求項１４に記載の方法。
【請求項１６】
オブジェクトの正常性又は異常性の決定は、データ中心の（又は特徴空間中心の）座標系におけるそのノルムに基づいて、又は前記座標系の原点に中心を置いて所定のオブジェクトを囲む超球面の半径によって決定される請求項１４又は１５に記載の方法。
【請求項１７】
表現の更新は座標系の更新を有する請求項１４〜１６の１項に記載の方法。
【請求項１８】
座標系の更新は座標系の中心の更新を有する請求項１４〜１７の１項に記載の方法。
【請求項１９】
新しいオブジェクトのインポートは、作業集合内の全てのオブジェクトのノルムの更新を一部として有し、拡張した作業集合（「ノルム拡張」）に対応する新しい座標系にそれらをもたらす請求項１４〜１８の１項に記載の方法。
【請求項２０】
オブジェクトの除去は、作業集合内の全てのオブジェクトのノルムの更新を一部として有し、収縮した作業集合（「ノルム収縮」）に対応する新しい座標系にそれらをもたらす請求項１５〜１９の１項に記載の方法。
【請求項２１】
特にデータ集合及び／又は信号を有するデータストリーム中の異常オブジェクトを自動的オンライン検出及びクラス分類するためのシステムであって、
a）正常及び異常オブジェクトを有する少なくとも１つの流入データストリーム（１０００）を検出するための手段、
b）以下を有する自動的オンライン異常性検出エンジン、
−少なくとも１つの所定の最適化条件に従う時刻t1におけるデータストリーム（１０００）の流入オブジェクトの正常性の幾何学表現（２２００）の、特に有限数の正常オブジェクトを囲む超曲面の構築のために、時刻t2＞t1における少なくとも１つの受信オブジェクトに対して正常性の幾何学表現（２２００）のための、少なくとも１つの所定の最適化条件に従う自動的オンライン適合手段を備える自動的構築手段（２１００）、及び
−正常性の最適幾何学表現、特に正常性の最小体積幾何学表現（２２００）はインスタンスtiから維持されており、その後に正常性の幾何学表現（２２００）の構築は最適化条件に実行可能に従うこと、
−正常性の幾何学表現（２２００）に対する時刻t2における受信オブジェクトに対する正常性クラス分類の自動的オンライン決定手段、
c）生成された正常性クラス分類（２３００）に基づいて、さらなる処理のための異常データを記述するデータ集合、特に視覚的表現、を生成する正常オブジェクト及び異常オブジェクトの自動的クラス分類手段（４０００）、
を特徴とするシステム。
【国際調査報告】
2007503034.tif 000057
2007503034.tif 000058