(57)【特許請求の範囲】
【請求項１】
特徴的なサブトレースマイニングを使用する、経時的グラフにおける挙動クエリを構築するためのコンピュータによって実行される方法であって、
少なくとも、ターゲット挙動に対応する第１の経時的グラフと、バックグランド挙動の集合に対応する第２の経時的グラフとを含む経時的グラフを提供するために、システムデータログを生成することと、
第１の経時的グラフパターンと第２の経時的グラフパターンとの間に、非反復的なグラフパターンである経時的グラフパターンが存在するか否かを判定するために、前記第１及び第２の経時的グラフの各々について、経時的グラフパターンを生成することと、
少なくとも１つの特徴的な経時的グラフを提供するために、前記経時的グラフパターン同士の間の前記パターンを除去することと、
前記少なくとも１つの特徴的な経時的グラフに基づいて、挙動クエリを生成することと、を含む方法。
【請求項２】
各エッジ同士の間のノードマッピングが１対１になるように、前記第１の経時的グラフパターンにおける各エッジが、前記第２の経時的グラフパターンにおける各エッジに対応する場合に、前記パターンが判定される、請求項１に記載のコンピュータによって実行される方法。
【請求項３】
前記パターンは、線形時間に同一である経時的グラフパターンを含む、請求項１に記載のコンピュータによって実行される方法。
【請求項４】
前記少なくとも１つのターゲット挙動が、前記バックグランド挙動の集合から独立して実行されるように、閉じた環境において前記システムデータログが生成される、請求項１に記載のコンピュータによって実行される方法。
【請求項５】
前記パターンは、連続的な成長パターンを含む、請求項１に記載のコンピュータによって実行される方法。
【請求項６】
前記連続的な成長パターンは、前方成長パターン、後方成長パターン、及び内部成長パターンのうちの少なくとも１つを含む、請求項５に記載のコンピュータによって実行される方法。
【請求項７】
前記経時的グラフは、Ｔ接続された経時的グラフである、請求項１に記載のコンピュータによって実行される方法。
【請求項８】
除去することは、サブグラフ除去及びスーパグラフ除去のうち少なくとも１つを含む、請求項１に記載のコンピュータによって実行される方法。
【請求項９】
サブグラフテスト及び残余グラフ集合等価テストのうちの少なくとも一方からのオーバヘッドを最小化することをさらに含む、請求項１に記載のコンピュータによって実行される方法。
【請求項１０】
特徴的なサブトレースマイニングを使用する、経時的グラフにおける挙動クエリを構築するためのシステムであって、
少なくとも、ターゲット挙動に対応する第１の経時的グラフと、バックグランド挙動の集合に対応する第２の経時的グラフとを含む経時的グラフを提供するために、システムデータログを生成するモニタリングデバイスと、
前記第１及び第２の経時的グラフの各々について、経時的グラフパターンを生成する経時的グラフパターン生成器と、
第１の経時的グラフパターンと第２の経時的グラフパターンとの間に、非反復的なグラフパターンである経時的グラフパターンが存在するか否かを判定するパターン判定器と、
少なくとも１つの特徴的な経時的グラフを提供するために、前記経時的グラフパターン同士の間の前記パターンを除去する、バスに結合されたプロセッサを備えるパターン除去器と、
前記少なくとも１つの特徴的な経時的グラフに基づいて、挙動クエリを生成する、前記バスに結合された挙動クエリ生成器と、を備えるシステム。
【請求項１１】
各エッジ同士の間のノードマッピングが１対１になるように、前記第１の経時的グラフパターンにおける各エッジが、前記第２の経時的グラフパターンにおける各エッジに対応する場合に、前記パターンが判定される、請求項１０に記載のシステム。
【請求項１２】
前記モニタリングデバイスはさらに、前記少なくとも１つのターゲット挙動が、前記バックグランド挙動の集合から独立して実行されるように、閉じた環境において前記システムデータログを生成するように構成された、請求項１０に記載のシステム。
【請求項１３】
前記パターンは、連続的な成長パターンを含む、請求項１０に記載のシステム
【請求項１４】
前記連続的な成長パターンは、前方成長パターン、後方成長パターン、及び内部成長パターンのうちの少なくとも１つを含む、請求項１３に記載のシステム。
【請求項１５】
前記パターン除去器はさらに、サブグラフ除去及びスーパグラフ除去の少なくとも１つを使用して除去するように構成された、請求項１１に記載のシステム。
【請求項１６】
特徴的なサブトレースマイニングを使用する、経時的グラフにおける挙動クエリを構築する方法のために、コンピュータ可読プログラムコードを包含した非一時的なコンピュータ可読記憶媒体であって、前記方法は、
少なくとも、ターゲット挙動に対応する第１の経時的グラフと、バックグランド挙動の集合に対応する第２の経時的グラフとを含む経時的グラフを提供するために、システムデータログを生成することと、
第１の経時的グラフパターンと第２の経時的グラフパターンとの間に、非反復的なグラフパターンである経時的グラフパターンが存在するか否かを判定するために、前記第１及び第２の経時的グラフの各々について、経時的グラフパターンを生成することと、
少なくとも１つの特徴的な経時的グラフを提供するために、前記経時的グラフパターン同士の間の前記パターンを除去することと、
前記少なくとも１つの特徴的な経時的グラフに基づいて、挙動クエリを生成することと、を含む、コンピュータ可読記憶媒体。
【請求項１７】
各エッジ同士の間のノードマッピングが１対１になるように、前記第１の経時的グラフパターンにおける各エッジが、前記第２の経時的グラフパターンにおける各エッジに対応する場合に、前記パターンが判定される、請求項１６に記載のコンピュータ可読記憶媒体。
【請求項１８】
前記少なくとも１つのターゲット挙動が、前記バックグランド挙動の集合から独立して実行されるように、閉じた環境において前記システムデータログが生成される、請求項１６に記載のコンピュータ可読記憶媒体。
【請求項１９】
除去することは、サブグラフ除去及びスーパグラフ除去のうちの少なくとも１つを含む、請求項１６に記載のコンピュータ可読記憶媒体。
【請求項２０】
サブグラフテスト及び残余グラフ集合等価テストのうちの少なくとも一方からのオーバヘッドを最小化することをさらに含む、請求項１９に記載のコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願情報）
本出願は、参照によって本明細書に組み込まれている２０１４年１１月５日に出願された仮出願第６２／０７５，４７８号への優先権を主張する。
【０００２】
本発明は、一般に、経時的グラフにおける挙動クエリ構築のための方法及びシステムに関する。さらに詳しくは、本開示は、特徴的なサブトレースマイニングを使用する、経時的グラフにおける挙動クエリ構築のための方法及びシステムに関する。
【背景技術】
【０００３】
ビジネスを管理するためにコンピュータシステムが広く展開されているので、コンピュータシステムの適切な機能を保証することは、ビジネス実行のための重要な観点である。例えば、システムが、危険に曝されているか、及び／又は、システム故障に遭遇すると、このシステムのセキュリティを保証することができなくなるか、及び／又は、このシステムに提供されたサービスが中断され得る。しかしながら、コンピュータシステムの適切な機能を維持することは、やり甲斐のある任務である。というのも、システムアドミニストレータは、これら複雑なシステムの中を限定的にしか見ることができないからである。
【０００４】
一般に、システムアドミニストレータにとって、システム挙動をモニタリングすることも理解することもなく、キーロガー、スパイウェア、マルウェア等のような、コンピュータシステムに対する脆弱性に対処することは困難である。システム挙動は、プログラムのようなシステムエンティティが実行されたときから、このシステムエンティティが終了するときまでに生成される情報の集合を含んでいてよい。これは一般に、パス及び／又は実行トレースと称される。（例えば、処理、ファイル、ソケット、パイプ等のような）システムエンティティが、オペレーティングシステムレベルにおいて互いにどのように作用し合うのかの実行トレースは、セキュリティ関連の挙動をモニタリングする場合に収集され得る。
【０００５】
しかしながら、コンピュータシステムをモニタリングすることは、典型的には、該システムエンティティ同士の経時的な相互作用のすべてを記録するアプリケーションログに記憶される大量のデータを生成する。例えば、これらログは、どの時間に、どのような種類の相互作用が、どのシステムエンティティ間で発生したのかを各々が記載する、イベントのシーケンスを含んでいる。既存の解決策は、アドミニストレータが、このアプリケーションログ間を探索することを要求する。これは、非効率的で非効果的であり得る。というのも、いくつかのアプリケーションログ（例えば、ファイルアクセスログ、ファイヤフォール、ネットワークモニタリング等）は、システム挙動に関する部分的な情報しか提供しないからである。
【０００６】
したがって、システム挙動のより良い理解と、潜在的なシステムリスク及び悪意のある挙動の識別とは、システムデータのダイナミクス及び異種混合によって、システムアドミニストレータにとってやり甲斐のある任務となった。
【発明の概要】
【０００７】
本原理の１つの実施態様では、特徴的なサブトレースマイニングを使用する、経時的グラフにおける挙動クエリ構築のための方法が提供される。本実施態様では、この方法は、ターゲット挙動に対応する第１の経時的グラフと、バックグランド挙動の集合に対応する第２の経時的グラフとを含む経時的グラフを提供するために、システムデータログを生成することと、第１の経時的グラフパターンと第２の経時的グラフパターンとの間に、非反復的なグラフパターンであるパターンが存在するか否かを判定するために、第１及び第２の経時的グラフとの各々について、経時的グラフパターンを生成することと、特徴的な経時的グラフを提供するために、第１及び第２の経時的グラフパターンとの間のグラフパターンを除去することと、この特徴的な経時的グラフに基づいて、挙動クエリを生成することと、を含んでいてよい。
【０００８】
他の実施態様では、特徴的なサブトレースマイニングを使用する、経時的グラフにおける挙動クエリ構築のためのシステムが提供される。本実施態様では、システムは、少なくとも、ターゲット挙動に対応する第１の経時的グラフと、バックグランド挙動の集合に対応する第２の経時的グラフとを含む経時的グラフを提供するために、システムデータログを生成するモニタリングデバイスと、第１及び第２の経時的グラフの各々について、経時的グラフパターンを生成する経時的グラフパターン生成器と、第１の経時的グラフパターンと第２の経時的グラフパターンとの間に、非反復的なグラフパターンである経時的なグラフパターンが存在するか否かを判定するパターン判定器と、少なくとも１つの特徴的な経時的グラフを提供するために、第１及び第２の経時的グラフパターンの間のパターンを除去する、バスに結合されたパターン除去器と、この少なくとも１つの特徴的な経時的グラフに基づいて、挙動クエリを生成する、このバスに結合された挙動クエリ生成器と、含んでいてよい。
【０００９】
本開示のさらに他の観点では、特徴的なサブトレースマイニングを使用する、経時的グラフにおける挙動クエリ構築のための方法を実行するために、コンピュータ可読プログラムコードを包含したコンピュータ可読記憶媒体が提供される。本実施態様では、この方法は、ターゲット挙動に対応する第１の経時的グラフと、バックグランド挙動の集合に対応する第２の経時的グラフとを含む経時的グラフを提供するために、システムデータログを生成することと、第１の経時的グラフパターンと第２の経時的グラフパターンとの間に、非反復的なグラフパターンであるパターンが存在するか否かを判定するために、第１及び第２の経時的グラフの各々について、経時的グラフパターンを生成することと、特徴的な経時的グラフを提供するために、第１及び第２の経時的グラフパターンの間のパターンを除去することと、この特徴的な経時的グラフに基づいて、挙動クエリを生成することと、を含んでいてよい。
【００１０】
これら及び他の特徴並びに利点は、添付図面に関連して理解されることとなる以下の例示的な実施態様の詳細な説明から明らかになる。
【図面の簡単な説明】
【００１１】
本原理は、以下の図面を参照して、以下の好適な実施態様の説明において詳細を提供する。
【図１】本原理の実施態様にしたがって、特徴的なサブトレースマイニングを使用して、経時的グラフにおける挙動クエリを構築するための典型的なシステム／方法を例示的に描写するブロック／フロー図である。
【図２】本原理の実施態様にしたがう経時的グラフの実例を示す図である。
【図３】本原理の実施態様にしたがう典型的な成長パターンを示す図である。
【図４Ａ】本原理の実施態様にしたがう典型的な成長パターンを示す図である。
【図４Ｂ】本原理の実施態様にしたがう典型的な成長パターンを示す図である。
【図４Ｃ】本原理の実施態様にしたがう典型的な成長パターンを示す図である。
【図５】本原理の実施態様にしたがう典型的な残余グラフを示す図である。
【図６】本原理の実施態様にしたがって、経時的グラフパターン同士の間のパターンを除去するための典型的なシステム／方法を例示的に描写するブロック／フロー図である。
【図７】本原理の実施態様にしたがって、経時的グラフパターン同士の間のパターンを除去するための典型的なシステム／方法を例示的に描写するブロック／フロー図である。
【図８】本原理にしたがって、経時的グラフパターン同士の間のシーケンスベースの表現の実例を示す図である。
【図９】本原理の実施態様にしたがって、本原理が提供されてよい典型的な処理システム／方法を示す図である。
【図１０】本原理の実施態様にしたがって、特徴的なサブトレースマイニングを使用して、経時的グラフにおける挙動クエリを構築するための典型的な処理システム／方法を示す図である。
【発明を実施するための形態】
【００１２】
特徴的なサブトレースマイニングを使用する、経時的グラフにおける挙動クエリ構築のための方法及びシステムが提供される。挙動クエリを使用して潜在的なシステムリスクを識別するために、コンピュータシステムにおけるシステム挙動をモニタリングし理解する際における１つの課題は、システムデータの異種混交及び全体量である。本原理の１つの態様によれば、本明細書に開示した方法、システム、及びコンピュータプログラム製品は、セキュリティ関連挙動のグラフパターンとして、特徴的なサブトレースをマイニングし、ユーザが理解可能な意味論的な意味へマップされ、実行トレースを探索するために有効である挙動クエリを構築するために、経時的グラフへ、特徴的なサブトレースマイニングを適用する。セキュリティ関連挙動は、限定されないが、ファイル圧縮／伸張、ソースコード編集、ファイルダウンロード／アップロード、リモートログイン、及びシステムソフトウェア管理（例えば、ソフトウェアアプリケーションのインストール及び／又は更新）を含んでいてよい。それに加えて、本方法及びシステムは、類似の成長傾向を共有するグラフパターンを除去し、これによって、計算時間が著しく短縮され、データ記憶効率が高まる。なぜなら、反復的な探索が回避され、及び／又は、パターン品質を損なうことなく、冗長的な探索が除去されるからである。
【００１３】
コンピュータシステム企業のセキュリティを保証するために、システムアドミニストレータは、一般に、システムにおける行動がかなり制限されている週末にわたる行動のような、特定のセキュリティ挙動が生じたか否かを判定するために、システムデータログを問い合わせてよい。例示的な目的のために、行動は、システムへのリモートアクセス、いくつかのファイルの圧縮、及び／又は、ファイルのリモートサーバへの転送を含んでいてよい。一般に、このシステムアドミニストレータは、個別の３つのクエリ（例えば、リモートアクセスログイン、ファイルの圧縮、リモートサーバへの転送）を提出し、セキュリティ関連行動を発見するために、システムデータログ全体にわたる探索を実行することが要求される可能性がある。いくつかの事例では、挙動クエリと称されるセキュリティ関連挙動のための、経時的グラフとして表現されるそのようなモニタリングデータを、システムアドミニストレータが直接的にクエリすることは困難であり得る。なぜなら、経時的グラフは、いずれの高レベルの行動（例えば、リモートアクセスログイン、ファイルの圧縮、リモートサーバへの転送）へも直接的にマップされ得ないシステムデータログに記録された、多くの重要ではない低レベルのエンティティ（例えば、処理、ファイル等）を伴い複雑であるからである。そのような事例では、そのようなシステムレベル相互作用と、興味のあるセキュリティ関連挙動との間に意味論的なギャップが存在する。高レベルの行動を発見するために、システムアドミニストレータは、クエリを書き込むために、どの処理又はファイルが、この高レベルの行動に含まれており、時間的にどの順序で、この低レベルの行動がこの高レベルの行動に含まれているのかを知っていなければならない。しかしながら、そのような経時的グラフの複雑さによって、コンピュータシステムにおける異常な行動、攻撃、及び脆弱性を検査するために、システムアドミニストレータが、有用なクエリをマニュアルで作成することは、時間の浪費となる。
【００１４】
この問題を克服するために、本原理は、経時的グラフにおけるターゲット挙動のための最も特徴的なパターンを識別し、最も特徴的なパターンを挙動クエリとして適用することを教示する。したがって、少数のエッジのみからなり得るこれら挙動クエリは、解釈及び修正が容易であるだけでなく、ノイズに対して強い。１つの実施態様にしたがって、以下により詳細に説明するように、経時的グラフの正の集合と負の集合とが決定されてよく、最大の特徴スコアを有する経時的グラフパターンが識別されてよい。したがって、特徴的なパターンは、ターゲット挙動において頻繁に生じるべきであり、他の挙動において滅多に存在するべきではない。
【００１５】
同じ数字は同一又は類似の要素を表す図面のうち、まず、図１を参照すると、図１は、本原理の１つの実施態様にしたがって、特徴的なサブトレースマイニングを使用して、経時的グラフにおける挙動クエリを構築するための典型的な方法／システム１００を例示するブロック／フロー図を示す。
【００１６】
一般に、パターンマイニングは、大きく複雑なデータ集合を、簡潔な形式へ特徴付けてよい。特徴的なグラフパターンマイニングは、データ集合同士の特徴を区別し、相違を識別するために、グラフ分類タスクへ適用され得る特性選択方法である。具体的には、特徴的なパターンマイニングは、パターンの集合と、データ集合内で生じたパターンの頻度とを識別することに関する技法である。１つの実施態様にしたがって、コンピュータシステムにおけるセキュリティ関連挙動に関連するパターンを識別するために、経時的グラフにおける特徴的なパターンマイニングが実行されてもよい。
【００１７】
ブロック１０２では、方法１００は、システムデータをモニタリングすること（例えば、コンピュータシステムにおける挙動トレースの実行）及びシステムデータログを生成することを含んでいてよい。生のシステム挙動、ターゲット挙動、及び／又は、バックグランド挙動を含んでよいシステムデータログが収集されてよく、入力データとして適用されてよい。このシステムデータログは、システムエンティティがオペレーティングシステムにおいて互いにどのように作用するのかに関する情報（例えば、実行トレース及び／又は挙動トレース）を含んでいてよく、タイムスタンプを含んでいてよい。いくつかの実施態様では、処理は、任意の対応するファイル及び／又はタイムスタンプと共にモニタリングされ、及び／又は、収集されてよい。これら処理、ファイル、及び／又は、タイムスタンプは、収集されてよく、及び／又は、システムデータログを生成してよく、対応する経時的グラフを生成するために使用されてよい。
【００１８】
１つの実施態様では、該システムデータログは、１つのターゲット挙動のみが実行される閉じた環境において生成されてよい。例えば、このシステムデータログは、同時に起動している他の挙動（例えば、バックグランド挙動）がなく、独立して起動されるターゲット挙動を含んでいる。それに加えて、このシステムデータログは、同時に起動しているターゲット挙動がなく、独立して起動されるバックグランド挙動を含んでいてよい。
【００１９】
１つの実施態様では、該システムデータログは、システムエンティティであるノードと、タイムスタンプとの作用であるエッジとを用いて、このシステムデータログに対応する経時的グラフとしてモデル化及び／又は提供されてよい。実施態様では、この経時的グラフは、ブロック１０２に図示してあるように、少なくとも、ターゲット挙動に対応する第１の経時的グラフと、バックグランド挙動の集合に対応する第２の経時的グラフとを含んでいてよい。したがって、ターゲット挙動のシステムデータは、高々数千のノード及び／又はエッジからなる経時的グラフを生成してよい。それに加えて、バックグランド挙動の集合のシステムデータは、ノード及び／又はエッジを備える経時的グラフを生成してよい。
【００２０】
経時的グラフは、オブジェクトの集合のグラフ表現であり、ノードと称されるオブジェクトのいくつかのペアが、リンクによって接続され、エッジと称される。一般に、経時的グラフＧは、タプル（Ｖ、Ｅ、Ａ、Ｔ）によって表現される。ここで、Ｖは、ノードの集合であり、Ｅ⊂Ｖ×Ｖ×Ｔは、これらのタイムスタンプによって全体的に順序付けられた指示エッジの集合であり、Ａ：Ｖ→Σは、ラベルをノードに割り当てる関数（Σは、ノードラベルの集合）であり、Ｔは、可能なタイムスタンプの集合であり、エッジにおいて負ではない整数である。いくつかの実施態様では、この方法は、総合エッジ順序を備える経時的グラフを適用する。経時的グラフでは、エッジはタイムスタンプを有していてよい。したがって、エッジは、タイムスタンプによってランク付け、及び／又は、順序付けされてよい。エッジが、全順序を有しているのであれば、任意のエッジｅ１及びｅ２の場合、ｅ１のタイムスタンプがｅ２のタイムスタンプよりも小さくてよいか、又は、ｅ１のタイムスタンプがｅ２のタイムスタンプよりも大きくてよい。言い換えれば、経時的グラフが、総合エッジ順序を含んでいる場合、２つのエッジが同一のタイムスタンプを共有することはない。本原理は、多数のエッジ、ノードラベル、及びエッジタイムスタンプだけでなく、エッジラベルをも備える経時的グラフに適用されてよいことが注目されるべきである。
【００２１】
実施態様では、ターゲット挙動のためのシステムデータログは、正の経時的グラフの集合を含んでいてよく、バックグランド挙動のためのシステムデータログは、負の経時的グラフの集合を含んでいてよい。例えば、ブロック１０２では、ターゲット挙動を含むシステムデータログは、正の経時的グラフＧｐの集合として取り扱われてよく、バックグランド挙動を含むシステムデータログは、負の経時的グラフＧｎの集合として取り扱われてよい。通常及び／又は異常な挙動（例えば、侵入挙動）のためのシステムデータログは、正のデータセットとして使用されてよく、これは、通常及び／又は異常な挙動のためのグラフパターンクエリを生成するために適用されてよいことが注目されるべきである。
【００２２】
さらなる実施態様では、該経時的グラフは、経時的サブグラフを含んでいてよい。したがって、この経時的サブグラフは、ブロック１０２に図示してあるように、少なくとも、ターゲット挙動に対応する第１の経時的サブグラフと、バックグランド挙動の集合に対応する第２の経時的サブグラフとを含んでいてよい。例えば、いくつかの実施態様では、該システムデータログからの生の経時的グラフの全体を挙動クエリとして適用する代わりに、ターゲット挙動の足跡を取得するために、この経時的グラフの特徴的なサブグラフ（以降、「サブグラフ」と称する）を使用することが有利で効率的になる場合がある。
【００２３】
２つの経時的グラフ、すなわち、Ｇ＝（Ｖ，Ｅ，Ａ，Ｔ）及びＧ’＝（Ｖ’，Ｅ’，Ａ’，Ｔ’）が与えられると、ｆ：Ｖ→Ｖ’及びτ：Ｔ→Ｔ’のような２つの単射関数が存在するときかつそのときに限り、経時的グラフＧは、Ｇ’のサブグラフ（例えば、Ｇ⊆ｔＧ’）である。これによって、ノードマッピング、エッジマッピング、及びエッジ順序が保存されるようになる。ノードマッピングは、∀ｕ∈Ｖ、Ａ（ｕ）＝Ａ’（ｆ（ｕ））として定義してよい。ここで、Ｖは、経時的グラフＧにおけるノードの集合であり、ｕは、経時的グラフＧにおけるノードであり、ｆ（ｕ）は、ｕがマップするＧ’におけるノードであり、これによってｕとｆ（ｕ）は、同一のノードラベルを共有できるようになる。エッジマッピングは、∀（ｕ，ｖ，ｔ）∈Ｅ、（ｆ（ｕ），ｆ（ｖ），τ（ｔ））∈Ｅ’として定義され、ここで、Ｅは、経時的グラフＧにおけるエッジの集合であり、（ｕ，ｖ，ｔ）は、タイムスタンプｔを有するノードｕとノードｖとの間のＧにおけるエッジであり、Ｅ’は、Ｇ’におけるエッジの集合であり、（ｆ（ｕ），ｆ（ｖ），τ（ｔ））は、タイムスタンプτ（ｔ）を有するノードｆ（ｕ）とノードｆ（ｖ）との間のＧ’におけるエッジである。したがって、（ｕ，ｖ，ｔ）は、（ｆ（ｕ），ｆ（ｖ），τ（ｔ））へマップし、経時的グラフＧにおけるノードｕ、ノードｖ、及びタイムスタンプｔは、各々、グラフＧ’におけるノードｆ（ｕ）、ノードｆ（ｖ）、及びタイムスタンプτ（ｔ）へマップする。エッジ順序は、∀（ｕ１，ｖ１，ｔ１），（ｕ２，ｖ２，ｔ２）∈Ｅ，ｓｉｇｎ（ｔ１−ｔ２）＝ｓｉｇｎ（τ（ｔ１）−τ（ｔ２））として定義してよく、これによって、Ｇにおけるタイムスタンプｔ１及びｔ２は、各々、Ｇ’におけるタイムスタンプτ（ｔ１）及びτ（ｔ２）へマップする。したがって、ｓｉｇｎ（ｔ１−ｔ２）＝ｓｉｇｎ（τ（ｔ１）−τ（ｔ２））は、（１）ｔ１がｔ２よりも小さいのであれば（例えば、ｔ１−ｔ２のｓｉｇｎが負であれば）、τ（ｔ１）は、τ（ｔ２）よりも小さく（例えば、τ（ｔ１）−τ（ｔ２）のｓｉｇｎが負であり）、（２）ｔ１がｔ２よりも大きいのであれば（例えば、ｔ１−ｔ２のｓｉｇｎが正であれば）、τ（ｔ１）は、τ（ｔ２）よりも大きい（例えば、τ（ｔ１）−τ（ｔ２）のｓｉｇｎが正である）ことを意味する。経時的グラフＧ’は、経時的グラフＧの一致であり、これは、Ｇ’＝ｔＧとして示されてよく、ここで、ｆ及びτは、全単射関数であり、ここでは、１つの集合のすべての要素が、他の集合の１つの要素とペアにされ、他の集合のすべての要素が、ペアでない要素がないように、第１の集合の１つの要素とペアにされる。経時的サブグラフの実例が、図２に例示的に示されている。これは、以下にさらに詳細に説明する。
【００２４】
ブロック１０４では、この方法は、第１及び第２の経時的グラフパターンの間にパターンが存在するか否かを判定するために、第１及び第２の経時的グラフの各々のための経時的グラフパターンを生成することを含んでいてよい。１つの実施態様では、第１及び第２の経時的グラフパターンの間のパターンは、非反復的なグラフパターンである。これは以下にさらに詳細に説明する。経時的グラフパターンｇ＝（Ｖ，Ｅ，Ａ，Ｔ）は、エッジ同士のタイムスタンプのすべてが、∀ｔ∈Ｔ，１≦ｔ≦｜Ｅ｜となるように、１と、この経時的グラフにおけるエッジの総数との間にある経時的グラフパターンである。一般的な経時的グラフとは異なり、タイムスタンプが任意の負ではない整数であり得る場合、経時的グラフパターンにおけるタイムスタンプが（例えば、１から｜Ｅ｜へ）揃えられ、総合エッジ順序のみが維持される。
【００２５】
実施態様では、第１及び第２の経時的グラフの各々に関する経時的グラフパターンのような経時的グラフパターンは、Ｔ接続されたグラフパターンであってよい。経時的グラフは，この経時的グラフ同士の接続のタイプを区別することによって，Ｔ接続された経時的グラフと、Ｔ接続されていない経時的グラフとの間で区別してよい。経時的グラフＧ＝（Ｖ，Ｅ，Ａ，Ｔ）は、∀（ｕ，ｖ，ｔ）∈Ｅであれば、Ｔ接続として定義される。ここで、Ｇは、経時的グラフであり、Ｖは、Ｇにおけるノードの集合であり、Ｅは、Ｇにおけるエッジの集合であり、Ａは、ラベルをＧにおけるノードへ割り当てる関数であり、Ｔは、タイムスタンプをＧにおけるエッジへ割り当てる関数である。したがって、経時的グラフＧは、（ｕ，ｖ，ｔ）であれば、Ｔ接続であり、これは、タイムスタンプｔを有するノードｕとノードｖとの間のＧにおけるエッジであり、これによって、タイムスタンプがｔよりも小さいエッジが、接続されたグラフを形成するようになる。Ｔ接続された経時的グラフと、Ｔ接続されていない経時的グラフとの実例は、図２に示されている。これは以下にさらに詳細に説明する。
【００２６】
引き続き図１を参照すると、この方法は、ブロック１０４に示されているように、パターンが経時的グラフパターン同士の間で形成されているか否かを判定することを含んでいる。実施態様では、第１の経時的グラフパターンと、第２の経時的グラフパターンとの間に、第１及び第２の経時的グラフ各々に対応するパターンが存在するか否かが判定される。好適な実施態様では、このパターンは、非反復的なグラフパターンである。
【００２７】
１つの実施態様では、第１の経時的グラフパターンにおける各エッジが、各エッジ同士の間のノードマッピングが１対１になるように、第２の経時的グラフパターンにおける各エッジに対応する場合、パターンが判定される。例えば、第１の経時的グラフパターンｇ１＝（Ｖ１，Ｅ１，Ａ１，Ｔ１）、第２の経時的グラフパターンｇ２＝（Ｖ２，Ｅ２，Ａ２，Ｔ２）、｜Ｖ１｜＝｜Ｖ２｜、及び第１の経時的グラフパターンにおけるエッジの総数が、第２の経時的グラフパターンにおけるエッジの総数に等しいと仮定すると、｜Ｅ１｜＝｜Ｅ２｜となり、ｇ１におけるエッジに対して、線形スキャンが実施されてよい。第１の経時的グラフパターンにおける各エッジ（ｕ１，ｖ１，ｔ）∈Ｅ１について、エッジは、エッジ（ｕ２，ｖ２，ｔ）∈Ｅ２のように、第２の経時的グラフパターンに配置される。そのようなエッジが存在するのであれば、ｕ１からｕ２へのマッピングと、ｖ１からｖ２へのマッピングとは、そのようなマッピングが１対１であることを保証することが確認される。両マッピングが１対１であれば、（ｕ１，ｖ１，ｔ）は、（ｕ２，ｖ２，ｔ）∈Ｅ２に一致する。したがって、ｇ１におけるすべてのエッジが、ｇ２における一致を発見すると、第１の経時的グラフパターンと第２の経時的グラフパターンとの間のパターンが存在する（例えば、ｇ１＝ｔｇ２）。例えば、ｆ：Ｖ１→Ｖ２及びτ：Ｔ１→Ｔ２のように、２つの全単射関数が発見されると、該線形スキャンは、ｇ１とｇ２との間のエッジタイムスタンプを一致させる一意の方式、及び｜Ｅ１｜＝｜Ｅ２｜に従い、τが発見され全単射である。したがって、｜Ｅ１｜＝｜Ｅ２｜であり、ｇ１及びｇ２におけるすべてのノードがマップされるので、本原理は、ノードマッピングｆが１対１であり、さらに、ｆのフルマッピングが生成されることを保証する。
【００２８】
１つの実施態様では、少なくとも２つの経時的グラフパターンが、線形時間的に同一であるか否かが判定される。パターン成長は、非経時的グラフと比較して、経時的グラフにおいてより効率的であることが注目されるべきである。例えば、経時的グラフの計算利点は、以下の特性から生じる。ｇ１及びｇ２が、経時的グラフパターンであると仮定すると、ｇ１＝ｔｇ２であれば、これらグラフパターン同士の間におけるｆとτのマッピングは一意のものである。これは本明細書では定理１と称する。ｇ１＝（Ｖ１，Ｅ１，Ａ１，Ｔ１）及びｇ２＝（Ｖ２，Ｅ２，Ａ２，Ｔ２）と仮定し得る。ｇ１及びｇ２は、経時的グラフパターンであるので、我々は、∀（ｕ１，ｖ１，ｔ１）∈Ｅ１、１≦ｔ１≦｜Ｅ１｜、及び∀（ｕ２，ｖ２，ｔ２）∈Ｅ２、１≦ｔ２≦｜Ｅ２｜を有する。ｇ１＝ｔｇ２及び｜Ｅ１｜＝｜Ｅ２｜であるので、総合エッジ順序を維持するために、ｔ１＝ｔ２である場合にのみ、（ｕ１，ｖ１，ｔ１）∈Ｅ１は、（ｕ２，ｖ２，ｔ２）∈Ｅ２に一致する。したがって、τ：Ｔ１→Ｔ２になるように、τの一意性が証明される。τは一意であるので、ｇ１とｇ２との間のエッジマッピングは一意である。したがって、ノードマッピングｆもまた、ｆ：Ｖ１→Ｖ２になるように一意である。
【００２９】
それに加えて、非経時的グラフのためにパターン成長を実行することは高くつく。非経時的パターンを特定の大きさのパターンへ成長させるために、異なる方式の組合せが、適用されてよい。しかしながら、繰り返し計算を回避するために、１つのパターンが新たなパターンであるか、又は既に発見されたパターンであるかを確認するための追加の計算が必要とされる。したがって、これは、グラフ同型写像が必然的に含まれるので、結果的に、計算費用が高くなる。オーバヘッドを低減するために、洗練されたパターン成長アルゴリズムと共に様々な正統的なラベリング技術が提案されたが、グラフ同型写像における固有の複雑さによって、費用は未だに非常に高い。非経時的グラフをマイニングすることとは異なり、本原理は、洗練された正統的なラベリング又は複雑なパターン成長アルゴリズムを使用することなく、繰り返されるパターン探索を回避する。
【００３０】
１つの実施態様では、該パターンは、連続的な成長パターンを含んでいてよい。例えば、経時的グラフパターン同士の間のパターンが、パターン空間における探索をガイドし、空パターンで始まり、空パターンを１エッジパターンへ成長させ、１エッジパターンのブランチにおける可能なすべてのパターンを探索する深さ優先探索を実行する場合、連続的なグラフパターンが存在する。１つのブランチが完全に探索された場合、他の１エッジパターンによって開始された追加のブランチが探索されてよい。有利なことに、本原理は、反復がないだけでなく、接続されたすべての可能な経時的グラフパターンを提供する効率的なパターン成長を可能とする。それに加えて、連続的な成長パターンは、接続された経時的グラフパターンが、反復なしで、別の接続された経時的グラフパターンを生成することを保証する。実施態様では、エッジ集合Ｅの接続された経時的グラフパターンｇと、エッジｅ’＝（ｕ’，ｖ’，ｔ’）とが与えられると、エッジｅ’が、ｇと、別の接続された経時的グラフパターンへ追加された場合、パターンは、連続的な成長パターンであり、ｔ’＝｜Ｅ｜＋１という結果になる。連続的な成長パターンの実例は、図３に例示的に示されている。これは以下にさらに詳細に説明する。さらなる実施態様では、この連続的な成長パターンは、前方成長パターン、後方成長パターン、又は内部成長パターンのうちの少なくとも１つを含んでいてよい。これは、以下にさらに詳細に説明する。
【００３１】
引き続き図１を参照すると、該経時的グラフパターン同士の間のパターンが判定された後、この方法は、ブロック１０６に図示してあるように、少なくとも１つの特徴的な経時的グラフを提供するために、判定されたパターンを除去することを含む。１つの実施態様では、これらパターンは、最大頻度及び／又は最大の特徴的なスコアを有するサブ関係のみを選択するように除去される。任意の経時的グラフパターンｇの場合、その特徴的なスコアとしてｇのための真値を返す判別関数Ｆによってその特徴的なスコアが評価されてよい。可能なすべてのパターンのうち、最も大きい特徴的なスコアを有するパターンが、最大特徴スコアを有する。さらなる実施態様では、除去することは、サブグラフ除去及び／又はスーパグラフ除去を含む経時的サブ関係を除去することを含む。これは以下により詳細に説明する。
【００３２】
いくつかの実施態様では、経時的グラフＧの集合及び経時的グラフパターンｇが与えられると、Ｇに関する経時的グラフパターンｇの頻度は、
【００３３】
【数１】
0006488009.tif 000002
として定義してよい。本原理にしたがって、正の経時的グラフＧｐの集合、及び負の経時的グラフＧｎの集合は、最大特徴スコアＦ（ｆｒｅｑ（Ｇｐ，ｇ＊），ｆｒｅｑ（Ｇｎ，ｇ＊））を持つ接続された経時的グラフパターンｇ＊を発見するために生成されてよい。ここで、Ｆ（ｘ，ｙ）は、部分的な反単調性を持つ特徴的なスコア関数であり、これによって、（１）ｘが固定され、ｙがより小さい場合、Ｆ（ｘ，ｙ）はより大きくなり、（２）ｙが固定され、ｘがより大きい場合、Ｆ（ｘ，ｙ）はより大きくなる。Ｆ（ｘ，ｙ）は、２つの変数ｘ及びｙを有する判別関数であり、ここで、ｘはｆｒｅｑ（Ｇｐ，ｇ）（例えば、正のグラフ集合Ｇｐにおける経時的グラフパターンｇの頻度）であり、ｙはｆｒｅｑ（Ｇｎ，ｇ）（例えば、負のグラフ集合Ｇｎにおけるパターンｇの頻度）である。Ｆ（ｘ，ｙ）は、例えば、Ｇテスト、情報利得等のようなスコア関数を含んでいてよいことが注目されるべきである。好適な実施態様では、部分的な反単調性を満足し、クエリ形成タスクに最も良く適合する特徴的なスコア関数が選択されてよい。経時的グラフパターンｇの特徴的なスコアは、Ｆ（ｇ）として示されることもまた注目されるべきである。
【００３４】
１つの実施態様では、該システムデータログにおける最も特徴的な経時的グラフパターンを判定するために、正の経時的グラフＧｐの集合と、負の経時的グラフＧｎの集合とが適用されてよい。さらなる実施態様では、この特徴的な経時的グラフパターンが判定されると、挙動探索の目的を最も良く実現するパターンを識別するために、ノードラベルにおける意味論的／セキュリティ示唆、モニタリングデータ間のノードラベル人気を含むドメイン知識によって、この特徴的な経時的グラフパターンがランク付けされてよい。
【００３５】
探索アルゴリズムは、パターンの特徴スコアの上限の検討のような除去条件を含んでいてよい。経時的グラフパターンｇが与えられると、ｇの上限は、ｇのスーパグラフによって達成され得る最大の可能な特徴スコアを示す。Ｇｐ及びＧｎを、各々正のグラフ集合及び負のグラフ集合とすると、上限は、Ｆ（ｆｒｅｑ（Ｇｐ，ｇ’），ｆｒｅｑ（Ｇｎ，ｇ’））≦Ｆ（ｆｒｅｑ（Ｇｐ，ｇ），０）となってよい。なぜなら、∀ｇ⊆ｔｇ’、ｆｒｅｑ（Ｇｐ，ｇ’）≦ｆｒｅｑ（Ｇｐ，ｇ）及びｆｒｅｑ（Ｇｎ，ｇ’）≧０であるからである。上限は理論的に厳密であるが、実際に、除去するためには非効率的であり得る。
【００３６】
実施態様では、該経時的グラフパターン同士の間のパターンを除去することは、各経時的グラフパターンのための残余グラフの集合を判定することを含んでいてよい。例えば、Ｇ’が、Ｇのサブグラフであれば、タイムスタンプが、Ｇ’における最も大きなエッジタイムスタンプ未満であるＧにおけるエッジは、残余グラフを形成するために除去されてよい。経時的グラフＧ＝（Ｖ，Ｅ，Ａ，Ｔ）及びそのサブグラフＧ’＝（Ｖ’，Ｅ’，Ａ’，Ｔ’）が与えられると、Ｒ（Ｇ，Ｇ’）＝（ＶＲ，ＥＲ，ＡＲ，ＴＲ）は、Ｇ’に関するＧ’の残余グラフであり、（１）ＥＲ⊂Ｅは、∀（ｕ１，ｖ１，ｔ１）∈ＥＲ、（ｕ２，ｖ２，ｔ２）∈Ｅ’、ｔ１＞ｔ２を満足し、（２）ＶＲは、ＥＲにおけるエッジに関連付けられたノードの集合である。残余グラフＲ（Ｇ，Ｇ’）のサイズは、｜Ｒ（Ｇ，Ｇ’）｜＝｜ＥＲ｜（例えば、Ｒ（Ｇ，Ｇ’）におけるエッジの数）として定義してよい。したがって、残余グラフのＲ（Ｇ，Ｇ’）残余ノードラベル集合は、ＬＲ（Ｇ，Ｇ’）＝｛ＡＲ（ｕ）｜∀ｕ∈ＶＲ｝として定義してよい。経時的グラフパターンｇ、経時的グラフＧ、経時的サブグラフＧ’、残余グラフＲ（Ｇ，Ｇ’）、及び残余ノードラベル集合ＬＲ（Ｇ，Ｇ’）＝｛ＡＲ（ｕ）｜∀ｕ∈ＶＲ｝の実例は、図５に例示的に示されている。これは以下にさらに詳細に説明する。
【００３７】
したがって、Ｍ（Ｇ，ｇ）は、経時的グラフパターンｇに一致するＧにおけるすべてのサブグラフを含む集合を表現してよい。Ｇｐ及びｇが与えられると、正の残余グラフ集合Ｒ（Ｇｐ，ｇ）は、
【００３８】
【数２】
0006488009.tif 000003
として定義してよい。Ｒ（Ｇｐ，ｇ）が与えられると、その残余ノードラベル集合Ｌ（Ｇｐ，ｇ）は、
【００３９】
【数３】
0006488009.tif 000004
として定義してよい。同様に、負の残余グラフ集合Ｒ（Ｇｎ，ｇ）とその残余ノードラベル集合Ｌ（Ｇｎ，ｇ）を定義してよい。したがって、経時的グラフ集合Ｇと２つの経時的グラフパターンｇ１⊆ｔｇ２が与えられると、Ｒ（Ｇ，ｇ１）＝Ｒ（Ｇ，ｇ２）であれば、ｇ１とｇ２との間のノードマッピングは一意である。
【００４０】
１つの実施態様では、ブロック１０６において該経時的グラフパターンを除去することは、サブグラフ除去を含んでいてよい。経時的グラフパターンｇの場合、ｇのブランチは、ｇから成長したパターンの空間を称するために適用されてよく、Ｆ＊は、発見された最も大きな特徴スコアを意味することに注目すべきである。サブグラフ除去の際には、ｇ１及びｇ２が、経時的グラフパターンを示し、ｇ１は、ｇ２よりも前に発見される。ｇ２がｇ１の経時的サブグラフであり、ｇ１及びｇ２が、同一の正の残余グラフ集合を共有し、ｇ２におけるいずれのノードにも一致するはずのないｇ１におけるノードのために、それらのラベルが、ｇ２の残余ノードラベル集合において決して現れないのであれば、ｇ２におけるサブグラフ除去が実行されてよい。発見されたパターンｇ１＝（Ｖ１，Ｅ１，Ａ１，Ｔ１）と、ノード集合Ｖ２のパターンｇ２とが与えられると、（１）ｇ２⊆ｔｇ１、（２）Ｒ（Ｇｐ，ｇ２）＝Ｒ（Ｇｐ，ｇ１）、及び（３）
【００４１】
【数４】
0006488009.tif 000005
であり、ここで、φは、空集合であり、
【００４２】
【数５】
0006488009.tif 000006
であり、Ｖ１’⊆Ｖ１が、Ｖ２におけるノードへマップするノードの集合の場合、ｇ１のブランチにおけるパターンのための最も大きな特徴スコアがＦ＊よりも小さいのであれば、ｇ２のブランチにおける探索が除去されてよい。サブグラフ除去は、図６に例示的に示されている。これは以下により詳細に説明する。
【００４３】
したがって、サブグラフ除去は、最も特徴的なパターンのいずれをも見逃すことなく、パターン空間を除去する。これは定理４と称してよい。この定理を証明するために、ｇ１及びｇ２は、経時的グラフパターンであり、ここで、ｇ１は、ｇ２の前に発見され、ｇ１及びｇ２は、サブグラフ除去における条件を満足していると仮定する。サブグラフ除去における条件が満足されるので、以下の事実、すなわち、（１）ｆｒｅｑ（Ｇｐ，ｇ２）＝ｆｒｅｑ（Ｇｐ，ｇ１）、（２）ｇ１のブランチにおけるパターン成長は、ｇ２におけるいずれのノードへも
【００４４】
【数６】
0006488009.tif 000007
としてマップすることができないノードに決して触れないことが導出され得る。特徴スコアがＦ＊以上であり、ｓは、ｇ２をｇ２’へ成長させる連続的な成長のシーケンスである、パターンｇ２’が存在していると仮定する。ｇ１’ブランチにおけるパターン成長は、ｇ２におけるいずれのノードへもマップすることができないノードに触れるので、ｓはその後、ｇ１をｇ１’へ成長させる連続的な成長の有効なシーケンスを（あるタイムスタンプシフトと共に）示す。
【００４５】
ｆｒｅｑ（Ｇｐ，ｇ２）＝ｆｒｅｑ（Ｇｐ，ｇ１）及びＲ（Ｇｐ，ｇ２）＝Ｒ（Ｇｐ，ｇ１）によって、ｆｒｅｑ（Ｇｐ，ｇ２’）＝ｆｒｅｑ（Ｇｐ，ｇ１’）であると推論してよい。したがって、ｇ２’⊆ｔｇ１’及びｆｒｅｑ（Ｇｎ，ｇ２’）≧ｆｒｅｑ（Ｇｎ，ｇ１’）であり、Ｆ（ｇ２’）≦Ｆ（ｇ１’）であると推論してよい。これは、ｇ１’が、ｇ１のブランチにおけるパターンのいずれもが、最も特徴的なものになることはないという条件と矛盾する最も特徴的なパターンのうちの１つであることを意味する。したがって、サブグラフ除去における条件が満足され、ｇ１のブランチにおけるパターンのいずれもが、最も特徴的なものではないのであれば、ｇ２のブランチにおけるパターンのいずれもが、最も特徴的なものになることはない。したがって、我々は、ｇ２のブランチにおけるいずれのパターンもＦ＊未満の特徴スコアを有し、ブランチが安全に除去され得ることを主張し得る。
【００４６】
１つの実施態様では、ブロック１０６において該経時的グラフパターンを除去することは、スーパグラフ除去を含んでいてよい。スーパグラフ除去では、ｇ１及びｇ２が、経時的グラフパターンを示し、ｇ１は、ｇ２の前に発見される。ｇ１がｇ２の経時的サブグラフであり、ｇ１及びｇ２が、同一の正の残余グラフ集合を共有し、ｇ１及びｇ２が、同じ数のノードを有するのであれば、ｇ２におけるスーパグラフ除去が実行されてよい。ｇ１がｇ２の前に発見され、ｇ２がｇ１から成長しない２つのパターンｇ１及びｇ２が与えられると、（１）ｇ２⊇ｔｇ１、（２）Ｒ（Ｇｐ，ｇ２）＝Ｒ（Ｇｐ，ｇ１）、（３）Ｒ（Ｇｎ，ｇ２）＝Ｒ（Ｇｎ，ｇ１）、及び（４）ｇ２及びｇ１が同じ数のノードを有している場合、ｇ１のブランチのための最も大きな特徴スコアが、Ｆ＊よりも小さいのであれば、ｇ２のブランチにおける探索は、安全に除去され得る。スーパグラフ除去は、図７に例示的に示されている。これは以下により詳細に説明する。
【００４７】
したがって、スーパグラフ除去は、最も特徴的なパターンを見逃すことなく、パターン空間を除去する。これは命題２と称してよい。定理４及び命題２は、以下の法則、すなわち、サブグラフ除去及びスーパグラフ除去を実行することは、最も特徴的なパターンが未だに維持されることを保証するに至らせるようにしてもよい。
【００４８】
この法則は、経時的グラフ空間において除去が実施されてよいという一般的なケースを識別する。しかしながら、いくつかの実施態様では、これら除去機会を発見するためのオーバヘッドが小さい場合、サブグラフ除去及び／又はスーパグラフ除去のいずれかを実施することが有利であってよい。サブグラフ除去及びスーパグラフ除去の主要なオーバヘッドは、２つのソース、すなわち、（１）経時的サブグラフテスト（例えば、ｇ２⊆ｔｇ１）、及び（２）残余グラフ集合等価テスト（例えば、Ｒ（Ｇｐ，ｇ２）＝Ｒ（Ｇｐ，ｇ１））に由来してよい。したがって、方法２００はさらに、このオーバヘッドを最小化することを含んでいてよい。
【００４９】
引き続き図１を参照すると、ブロック１０６において、この方法１００は、ブロック１０７に図示してあるように、サブグラフテストからのオーバヘッドを最小化することと、ブロック１０８に図示してあるように、残余グラフ集合等価テストからのオーバヘッドを最小化することとを含んでいてよい。いくつかの実施態様では、除去することが、サブグラフ除去及び／又はスーパグラフ除去の少なくとも一方である場合、この方法は、ブロック１０７及び１０８のいずれか一方又は両方を含んでいてよい。
【００５０】
ブロック１０７では、この方法１００は、サブグラフテストからのオーバヘッドを最小化することを含んでいてよい。実施態様では、サブグラフテストからのオーバヘッドを最小化することは、符号化システムを使用してシーケンスによって経時的グラフを表現することと、シーケンステストに基づいて、軽いアルゴリズムを適用することとを含み得る。２つの経時的グラフｇ及びｇ’が与えられると、それは、ｇ⊆ｔｇ’を決定するためのＮＰ完全である。エッジが、経時的グラフにおいて完全に順序付けられているので、経時的グラフが、シーケンスへ符号化されてよい。それに加えて、経時的グラフがシーケンスとして表現された後、効率的なサブシーケンステストを使用する、より高速な経時的サブグラフテストが適用されてよい。
【００５１】
経時的グラフパターンｇが２つのシーケンス、すなわち、ノードシーケンスとエッジシーケンスとによって表現されてよい。ノードシーケンス、ｎｏｄｅｓｅｑ（ｇ）は、ラベル付けされたノードのシーケンスである。ｇがそのエッジ時間順序によって横送りされていると仮定すると、ｎｏｄｅｓｅｑ（ｇ）におけるノードは、最初にアクセスした時間によって順序付けされてよい。ｇの任意のノードは、ｎｏｄｅｓｅｑ（ｇ）において一度だけ出現してよい。エッジシーケンス、ｅｄｇｅｓｅｑ（ｇ）は、ｇにおけるエッジのシーケンスであり、ここで、エッジは、それらのタイムスタンプによって順序付けられる。シーケンスは、ｓ１＝（ａ１，ａ２，・・・，ａｎ）及びｓ２＝（ｂ１，ｂ２，・・・，ｂｍ）が２つのシーケンスになるように、ｓとして定義してよく、ここで、ａは、シーケンスｓ１における要素であり（ａｉは、シーケンスｓ１におけるｉ番目の要素であり）、ｂは、シーケンスｓ２における要素であり（ｂｉは、シーケンスｓ２におけるｉ番目の要素であり）、ｎは、シーケンスｓ１における要素の総数であり、ｍは、シーケンスｓ２における要素の総数である。∀１≦ｊ≦ｎ、
【００５２】
【数７】
0006488009.tif 000008
になるように、１≦ｉ１＜ｉ２・・・＜ｉｎ≦ｍが存在するのであれば、ｓ１は、ｓ２のサブシーケンスであり、ｓ１⊆ｓ２のように示される。ｉ１、ｉ２、・・・、ｉｎが、１とｍとの間の範囲におけるｎ個の整数変数であり、ｊが、１とｎとの間の範囲における整数変数であることに注目すべきである。例えば、ｎ＝５、ｍ＝７であれば、ｓ１は、ｓ１＝（ａ１，ａ２，ａ３，ａ４，ａ５）のような５つの要素のシーケンスであり、ｓ２は、ｓ２＝（ｂ１，ｂ２，ｂ３，ｂ４，ｂ５，ｂ６，ｂ７）のような７つの要素のシーケンスである。このケースでは、ｉ１、ｉ２、・・・、ｉ５は、１以上、かつ７以下の５つの整数変数である。マッピングの観点において、ｊは、ｉｊへマップする（例えば、ａ２がｂｉ２をマップするように、ｊ＝２は、ｉ２へマップする）。シーケンスベースの経時的グラフ表現と経時的サブグラフテストは、図８に例示的に図示してある。これは以下にさらに詳細に説明する。
【００５３】
実施態様では、サブグラフテストからのオーバヘッドを最小化することは、経時的グラフの強化されたノードシーケンスｅｎｈｓｅｑ（ｇ）を提供することを含む。なぜなら、２つの経時的グラフｇ１及びｇ２が与えられると、ｇ１⊆ｔｇ２であれば、
【００５４】
【数８】
0006488009.tif 000009
であるからである。したがって、ｇが経時的グラフであれば、ｅｎｈｓｅｑ（ｇ）は、ｇにおいてラベル付けされたノードのシーケンスである。経時的グラフパターンｇがそのエッジ時間順序によって横送りされていると仮定すると、ｅｎｈｓｅｑ（ｇ）は、以下のように、各エッジ（ｕ、ｖ、ｔ）を処理することによって構築されてよい。（１）ｕが、現在のｅｎｈｓｅｑ（ｇ）において最後に追加されたノードであるか、又は、ｕが、最後に処理されたエッジのソースノードであれば、ｕは、スキップされてもよく、そうではない場合には、ｕは、ｅｎｈｓｅｑ（ｇ）へ追加される。（２）ノードｖは、常にｅｎｈｓｅｑ（ｇ）へ追加されてよい。ｇにおけるノードは、ｅｎｈｓｅｑ（ｇ）において複数回数現れてよいことが注目されるべきである。
【００５５】
したがって、２つの経時的グラフは、ｎｏｄｅｓｅｑ（ｇ１）⊆ｅｄｇｅｓｅｑ（ｇ２）であり、ここで、根本的な一致が、ｇ１におけるノードからｇ２におけるノードへの単射ノードマッピングｆｓを形成し、また、ｆｓ（ｅｄｇｅｓｅｑ（ｇ１））⊆ｅｄｇｅｓｅｑ（ｇ２）であり、ここで、ｆｓ（ｅｄｇｅｓｅｑ（ｇ１））は、ｇ１におけるノードが、ノードマッピングｆｓによってｇ２におけるノードによって交換される場合におけるエッジシーケンスであるときかつそのときに限り、ｇ１⊆ｔｇ２となる。これは、定理５と称してよい。
【００５６】
ブロック１０８では、方法１００は、残余グラフ集合等価試験からのオーバヘッドを最小化することを含んでいてよい。実施態様では、ｇ１及びｇ２は、経時的グラフパターンを表現する。したがって、Ｇ１’及びＧ２’は、経時的グラフＧにおける経時的グラフパターンｇ１及びｇ２各々の一致であってよい。経時的グラフにおけるエッジは、総合順序を有しているので、以下の結果が導出されてよい。すなわち、Ｇ１’及びＧ２’のための残余グラフのサイズが同じ、例えば、｜Ｒ（Ｇ，Ｇ１’）｜＝｜Ｒ（Ｇ，Ｇ２’）｜であるときかつそのときに限り、残余グラフＲ（Ｇ，Ｇ１’）は、残余グラフＲ（Ｇ，Ｇ２’）と等価になる。したがって、ｇ１⊆ｔｇ２である経時的グラフパターンｇ１及びｇ２と、グラフＧの集合とが与えられると、Ｉ（Ｇ，ｇ１）＝Ｉ（Ｇ，ｇ２）であるときかつそのときに限り、残余グラフＲ（Ｇ，ｇ１）＝Ｒ（Ｇ，ｇ２）となる。ここで、
【００５７】
【数９】
0006488009.tif 000010
である。これは、定理６と称してよい。Ｒ（Ｇ，Ｇ’）は、残余グラフであり、｜Ｒ（Ｇ，Ｇ’）｜は、Ｒ（Ｇ，Ｇ’）のサイズであり、整数である。したがって、Ｉ（Ｇ，ｇｉ）は、２つの変数Ｇ及びｇｉを有する関数であり、グラフ集合Ｒ（Ｇ，ｇｉ）におけるすべての残余グラフのサイズを総和することによって取得される整数を返す。したがって、オーバヘッドは、グラフにおける経時的情報を活用することによって等価残余グラフ集合をテストすることで最小化されてよい。
【００５８】
有利なことに、類似及び／又は同一の成長傾向を共有する経時的グラフパターンの冗長な探索を除去することは、経時的サブグラフテストのオーバヘッドと、除去機会を識別するために使用される残余グラフ集合等価テストとを最小化する。それに加えて、経時的グラフパターンの冗長な探索を除去することは、マイニング処理中、計算時間を増加させ、オーバヘッドを最小化する。なぜなら、根本的なパターン空間は、大きくなり、一般的なナイーブ探索アルゴリズムは、縮尺できないからである。
【００５９】
ブロック１１０では、該特徴的な経時的グラフに基づく挙動クエリが生成されてよい。実施態様では、最高の特徴スコアを有するパターンが、発生している異常及び／又は疑わしい行動（例えば、土曜日の夜に、極めて多数、ターゲット挙動が発生している）が存在しているか否かを判定するために、システムデータログのリポジトリから、ターゲット挙動行動を探索するためのクエリとして選択されてよい。例えば、挙動クエリを構築するために、この特徴的な経時的グラフが使用されてよく、続いて、ターゲット挙動が実行されたか否かを判定するために、システムデータログのような、コンピュータシステムに問い合わせるように適用されてよい。例えば、この特徴的な経時的グラフは、収集されたシステムモニタリングデータにおけるターゲット挙動の存在を探索するためのグラフクエリ（例えば、挙動クエリ）を形成するために使用されてよい。このシステムにおけるターゲット挙動の存在を探索するために、このクエリに一致する大きな経時的グラフのサブグラフを発見するように、このシステムデータの大きな経時的グラフにわたるパターン探索を実行するのに、グラフクエリが使用されてよい。各一致は、このシステムにおけるターゲット挙動の１つの可能な存在を示す可能性がある。実施態様では、本原理は、多数の挙動を伴う挙動クエリへ適用されてよい。例えば、各ターゲット挙動について、その特徴的なパターンは、各々の挙動クエリを生成するために決定され、各々の挙動クエリは、その存在（例えば、一致）を求めてこのシステムモニタリングデータを探索するために適用される。別の実施態様では、これら一致は、多数の挙動に関連付けられた挙動クエリを形成するために組み合わされてよい。有利なことに、本原理は、計算効率を高め、そのような情報の記憶を減少させる。なぜなら、繰り返される探索及び／又はパターンを除去するからである。
【００６０】
方法１００は、高い精度（例えば、９７％）及び高いリコール（例えば、９１％）を有する挙動クエリを用いた、挙動分析のための効果的な方法を提供する。これらは、精度及びリコールが各々８３％及び９１％である非経時的グラフパターンよりも優れている。精度及びリコールは、一般に、本原理の正確さを評価するための判断基準として使用される。ターゲット挙動及びその挙動クエリが与えられると、この挙動クエリの一致は、識別された事例と呼ばれる。一致が生じた時間間隔が、真の挙動事例のうちの１つが実行中であった時間間隔に完全に含まれているのであれば、識別された事例は正しい。この挙動クエリが、この挙動事例に関して少なくとも１つの正しい識別された事例を返し得るのであれば、挙動事例が発見される。したがって、精度は、識別された事例の合計数によって除された正しく識別された事例の数として定義し、リコールは、挙動事例の数によって除された発見事例の数として定義する。これらの利点に加えて、本明細書において提供された本原理は、より効率的であり、経時的グラフにおいて、以前の方法よりも高速なパターンマイニングを可能とし、典型的には、以前に適用された方法よりも約３２倍速いパターンマイニングを提供する。
【００６１】
非経時的グラフを取り扱う特徴的なグラフパターンマイニングは、正確に同じ時間間隔内での同一の行動の発生を必要とすることを注目すべきである。それに加えて、経時的グラフを取り扱うために、特徴的な固定グラフパターンをマイニングする既存のワークを拡張することは困難である。なぜなら、それらの正統なラベリング技術は、同じノードのペア同士の間で多数のエッジを有し、経時的エッジ順序を含み得る経時的グラフを取り扱うことができないからである。さらに、非経時的グラフを取り扱う特徴的なグラフパターンマイニングは、マイニング処理においてタイムスタンプをどのように取り扱うのかを論述していない。タイムスタンプが無視されると、多数のエッジが、単一のエッジへ崩壊されなければならず、この特徴的なマイニングの最終結果は、多数のエッジを有するパターンを除外するので、部分的な結果になる。それに加えて、多数の経時的パターンが、同じ非経時的パターンを共有し得るので、非経時的パターンにおける冗長性は、潜在的な拡張性の問題をもたらし得、特徴的な非経時的パターンは、非特徴的な経時的パターンという結果になり得る。
【００６２】
次に図２を参照すると、いくつかの経時的グラフが、例示的な目的のために示されている。実施態様では、総合エッジ順序を有する経時的グラフを使用することが好適である。図２に図示してあるように、経時的グラフＧ１は、本発明において考慮されるような多数のエッジを例示する。本原理に従って、エッジラベルを有する経時的グラフに加えて、ノードラベル（例えば、Ａ、Ｂ、Ｃ、Ｄ、Ｅ等）及び／又はエッジタイムスタンプ（例えば、１、２、３、４、５、６、７等）を含む経時的グラフが考慮される。１つの実施態様では、該経時的グラフパターンにおけるタイムスタンプが（例えば、１から｜Ｅ｜へ）揃えられてよく、いくつかの実施態様では、タイムスタンプが任意の負ではない整数であり得る一般的な経時的グラフとは異なり、総合エッジ順序のみが維持される。
【００６３】
図２では、経時的サブグラフの例が、例示的に描写してあり、ここでＧ２は、Ｇ１の経時的サブグラフ、すなわちＧ２⊆ｔＧ１である。特に、（例えば、４、５、及び６のような）タイムスタンプのエッジによって形成されてよいＧ１における経時的サブグラフは、Ｇ２の一致である。引き続き図２を参照すると、経時的グラフＧ１及びＧ２は、Ｔ接続された経時的グラフである一方、経時的グラフＧ３は、Ｔ接続されていない（例えば、非Ｔ接続）。なぜなら、５（例えば、５）よりも小さなタイムスタンプを有するエッジによって形成されたグラフは接続されていないからである。好適な実施態様では、Ｔ接続された経時的グラフパターン（以降、「接続された経時的グラフ」と称する）とともに特徴的なマイニングが適用される。パターン成長において、Ｔ接続されたパターンは、接続されたままである一方、Ｔ接続されていないパターンは、成長処理中に切断されてよく、パターン探索空間の著しい成長という結果となる。それに加えて、Ｔ接続されていない任意の経時的グラフは、Ｔ接続された経時的グラフの集合によって形成されてよい。実施態様では、単一のＴ接続されたパターン、又は、Ｔ接続されていないパターンを含むＴ接続されたパターンの集合は、挙動クエリを形成するために使用されてよい。
【００６４】
次に図３を参照すると、経時的グラフパターンのパターンのための連続的な成長パターン３００の例が、典型的な目的のために例示されている。図３において、連続的な成長パターン３００は、経時的グラフパターンｇ１が、連続的な成長による経時的グラフパターンｇ４へ成長した場合に判定されてよい。実施態様では、エッジ集合Ｅ及びエッジｅ’＝（ｕ’，ｖ’，ｔ’）の接続された経時的グラフパターンｇが与えられると、エッジｅ’が、ｇ及び別の接続された経時的グラフパターンへ追加され、ｔ’＝｜Ｅ｜＋１という結果になる場合に、連続的な成長が生じる。
【００６５】
例えば、ｇ１及びｇ２が、ｇ１⊆ｇ２を有する接続された経時的グラフパターンであり、ｇ１をｇ２へ成長させる一意な手法が存在する場合、パターンは、連続的な成長パターンである。あるいは、パターンは、連続的な成長パターンではなく、ｇ１をｇ２へ成長させる手法はない。これは、本明細書において定理３と称してよい。ｇ１及びｇ２のエッジ集合が、各々Ｅ１及びＥ２であれば、ｍ＝｜Ｅ２｜−｜Ｅ１｜個のステップの連続的な成長が、ｇ１を別のパターンｇ２’へ成長させるために実施されてよい。ｇ２’＝ｔｇ２が存在するのであれば、ｇ１をｇ２へ成長させることが可能となり得る。そうではない場合、ｇ１をｇ２へ成長させる手法はない。ｇ１をｇ２へ成長させてよいのであれば、ｍ個のステップの連続的な成長は一意である。
【００６６】
例えば、（１）ｓ’＝＜ｅ１’，ｅ２’，・・・，ｅｍ’＞が、ｇ２’＝ｔｇ２でｇ１をｇ２’へ成長させる連続的な成長のシーケンスであり、（２）ｓ’’＝＜ｅ１’’，ｅ２’’，・・・，ｅｍ’’＞が、ｇ２’’＝ｔｇ２でｇ１をｇ２’’へ成長させる別の連続的な成長のシーケンスであり、（３）∃（ｕ’，ｖ’，ｔ）∈ｓ’は、（ｕ’’，ｖ’’，ｔ）∈ｓ’’と一致しないので、ｓ’はｓ’’から区別できると仮定する。なぜなら、ｇ２’＝ｔｇ２及びｇ２’’＝ｔｇ２、ｇ２’＝ｔｇ２’’は、全単射マッピング関数によって推論してよいからである。連続的な成長パターンの定義によって、定理２からの線形スキャンは、ｇ２’がｇ２’’と一致できないと判断してよい。なぜなら、同じタイムスタンプを共有するｓ’’におけるエッジと一致できないｓ’からの少なくとも１つのエッジが存在するからである。これは、ｇ２’＝ｔｇ２’’と矛盾する。したがって、ｓ’は、ｓ’’と同一であり、ｍ個のステップの連続的な成長は一意である。
【００６７】
次に図４Ａ−図４Ｃを参照すると、連続的な成長パターンは、前方成長パターン、後方成長パターン、又は内部成長パターンのうちの少なくとも１つを含んでいてよい。これは以下にさらに詳細に説明する。図４Ａは、前方成長パターンの実例である。図４Ｂは、後方成長パターンの実例である。図４Ｃは、内部成長パターンの実例である。有利なことに、これらの前方成長パターン、後方成長パターン、及び／又は、内部成長パターンは、発見されるパターンの完全性を達成し、品質を保証するために、この非反復的なグラフパターンが、パターン空間全体をカバーすることを可能にする。
【００６８】
例えば、ｇを、ノード集合Ｖを有する接続された経時的グラフパターンであるとし、経時的グラフパターンｇは、以下のように、連続的な成長によって成長させてよい。この非反復的なグラフパターンが、図４Ａに示されているように、前方成長パターン４００Ａを含んでいる場合、経時的グラフパターンｇは、ｕ∈Ｖ及び
【００６９】
【数１０】
0006488009.tif 000011
であれば、エッジ（ｕ，ｖ，ｔ）によって成長させてよい。この非反復的なグラフパターンが、図４Ｂに図示してあるように、後方成長パターン４００Ｂを含んでいる場合、経時的グラフパターンｇは、
【００７０】
【数１１】
0006488009.tif 000012
及びｖ∈Ｖであれば、エッジ（ｕ，ｖ，ｔ）によって成長させてよい。この非反復的なグラフパターンが、図４Ｃに図示してあるように、内部成長パターン４００Ｃを含んでいる場合、経時的グラフパターンｇは、ｕ∈Ｖ及びｖ∈Ｖであれば、エッジ（ｕ，ｖ，ｔ）によって成長させてよい。内部成長パターン４００Ｃは、ノードペア同士の間の多数のエッジを可能にすることに注目すべきである。したがって、３つの成長パターン、すなわち前方４００Ａ、後方４００Ｂ、及び内部４００Ｃは、該パターン空間にわたる完全な探索を実施するためのガイダンスを提供する。
【００７１】
例えば、Ａが、前方、後方、及び内部成長パターンでの連続的な成長にしたがう短索アルゴリズムを表すのであれば、アルゴリズムＡは、（１）パターン空間にわたる完全な探索と、（２）どのパターンも、複数回探索されないことを保証する。これは、本明細書において法則１と称してよい。経時的グラフパターンｇが、接続された経時的グラフパターンであると仮定すると、定理３は、パターンが、複数回探索されなくてよいことを保証するために、連続的な成長パターンが、空パターンをｇへ成長させる一意の手法を保証することを規定する。したがって、複数回ｇを探索する手法はない。パターン探索に関する完全性のために、ｍが、経時的グラフパターンにおけるエッジの数であると仮定する。この完全性が、ｍ＝ｋに対して成立するのであれば、この完全性は、ｍ＝ｋ＋１に対して成立する。この完全性が、ｍ＝ｋに対して成立するのであれば、ｋ個のエッジの接続された経時的グラフパターンＨ（ｋ）の完全な集合が決定される。さらに、
【００７２】
【数１２】
0006488009.tif 000013
が、ｋ個のエッジのパターンｇ（ｋ）から成長させた、ｋ＋１個のエッジの接続されたパターンであれば、これら３つの成長パターンは、成長中にパターンが接続されていることを維持するすべての可能な手法であるので、ｇ（ｋ＋１）が、Ｈ（ｋ）におけるパターンを成長させることによってカバーされ得ないのであれば、それは、
【００７３】
【数１３】
0006488009.tif 000014
、すなわち、ｇ（ｋ）が接続されていないことを示唆する。これは、ｇ（ｋ＋１）が接続されている（例えば、Ｔ接続されている）という仮定と矛盾する。したがって、この完全性はまた、ｍ＝ｋ＋１に対して成立する。
【００７４】
次に、図５を参照すると、経時的グラフパターンｇ、経時的グラフＧ、経時的サブグラフＧ’、残余グラフＲ（Ｇ，Ｇ’）、及び残余ノードラベル集合ＬＲ（Ｇ，Ｇ’）＝｛ＡＲ（ｕ）｜∀ｕ∈ＶＲ｝の実例が、本原理にしたがって例示されている。図５に示されているように、経時的グラフＧ’は、経時的グラフＧのサブグラフであり、Ｒ（Ｇ，Ｇ’）は、Ｇ’に関するＧの残余グラフを表し、ＬＲ（Ｇ，Ｇ’）は、残余グラフの残余ノード集合である。
【００７５】
次に図６を参照すると、サブグラフ除去６００の実例が、本原理にしたがって例示的に図示されている。マイニング処理では、パターンｇ２が決定されてよく、発見されたパターンｇ１が存在してよい。これは、サブグラフ除去における条件を満足する。したがって、ｇ１のブランチにおけるパターン成長は、ｇ２をどのようにしてより大きなパターンへ成長させるかを提案する（例えば、ｇ１をｇ１’へ成長させることは、ｇ２をｇ２’へ成長させ得ることを示す）。ｇ１のブランチにおけるパターンのいずれも、スコアＦ＊を有していないので、ｇ２のブランチにおけるパターンは、最も特徴的なものにもなることはできず、これは、安全に除去（例えば、削除）され得る。
【００７６】
次に、図７を参照すると、スーパグラフ除去７００の実例が、本原理にしたがって例示的に図示されている。マイニング処理では、経時的グラフパターンｇ２が決定されてよく、別のパターンｇ１が、ｇ２の前に発見されてよい。これは、スーパグラフ除去における条件を満足する。したがって、ｇ１のブランチにおける成長認識は、どのようにしてｇ２をより大きなパターンへ成長させるかを提案する。ｇ１のブランチにおけるパターンのいずれもが最も特徴的なものではないので、ｇ２のブランチにおけるパターンは、同様に見込みがなく、ｇ２のブランチにおける探索が安全に除去（例えば、削除）され得ると推論してよい。
【００７７】
次に、図８を参照すると、シーケンスベースの表現８００の実例が、本原理にしたがって例示的に図示されている。ｇ１及びｇ２では、ノードラベルは、文字によって表現され、同じラベルの複数のノードが、括弧内の整数によって表現されるノードＩＤによって区別される。ｎｏｄｅｓｅｑにおけるノードラベルは、サブスクリプトとしてノードＩＤに関連付けられる。ノードラベルが比較される場合、それらのサブスクリプトは、無視される（例えば、∀ｉ、ｊ、Ｂｉ＝Ｂｊ）ことに注目すべきである。ｅｄｇｅｓｅｑにおける各エッジは、以下のフォーマット（ｉｄ（ｕ），ｉｄ（ｖ））によって表現される。ここで、ｉｄ（ｕ）は、ソースノードＩＤであり、ｉｄ（ｖ）は、宛先ノードＩＤである。
【００７８】
２つの経時的グラフｇ１及びｇ２が与えられると、ｇ１⊆ｔｇ２である場合、ｎｏｄｅｓｅｑ（ｇ１）⊆ｎｏｄｅｓｅｑ（ｇ２）及びｅｄｇｅｓｅｑ（ｇ１）⊆ｅｄｇｅｓｅｑ（ｇ２）であることが期待される。しかしながら、図８に示すように、ｇ１⊆ｔｇ２である場合、ｎｏｄｅｓｅｑ（ｇ１）⊆ｎｏｄｅｓｅｑ（ｇ２）は真ではなくてよい。なぜなら、ラベルＥを付されたノードの第１の訪問された時間は、ｇ１及びｇ２において整合しないからである。実施態様では、上述したように、ｇ１及びｇ２の強化されたノードシーケンスが提供されてよい。図８に示すように、ｇ１及びｇ２は、ｇ１⊆ｔｇ２を満足する２つの経時的グラフである。ｇ１のノードシーケンスは、ｆｓ（ｅｄｇｅｓｅｑ（ｇ１））⊆ｅｄｇｅｓｅｑ（ｇ２）となるようにｆｓ（ｅｄｇｅｓｅｑ（ｇ１））＝＜（１，５），（５，６），（４，６）＞を取得するために、単射ノードマッピングｆｓ（１）＝１、ｆｓ（２）＝５、ｆｓ（３）＝６、及びｆｓ（４）＝４を伴うｇ２の強化されたノードシーケンスのサブシーケンスである。
【００７９】
本明細書に記載した実施態様は、完全にハードウェアであってよいか、又は、ハードウェアと、限定されないが、ファームウェア、常駐ソフトウェア、マイクロコード等を含むソフトウェア要素との両方を含んでいてよいことが理解されるべきである。
【００８０】
実施態様は、コンピュータ又は任意の命令実行システムによる使用、又は、コンピュータ又は任意の命令実行システムと関連する使用のためのプログラムコードを提供するコンピュータ使用可能媒体又はコンピュータ可読媒体からアクセス可能なコンピュータプログラム製品を含んでいてよい。コンピュータ使用可能媒体又はコンピュータ可読媒体は、命令実行システム、装置、又はデバイスによる使用、又は、命令実行システム、装置、又はデバイスと関連する使用のためのプログラムを記憶、通信、伝搬、又は伝送する任意の装置を含んでいてよい。この媒体は、磁気的な、光学的な、電子的な、電磁的な、赤外線の、又は半導体のシステム（又は装置又はデバイス）、又は伝搬媒体であり得る。この媒体は、半導体メモリ又はソリッドステートメモリ、磁気テープ、リムーバブルコンピュータディスケット、ランダムアクセスメモリ（ＲＡＭ）、読取専用メモリ（ＲＯＭ）、リジット磁気ディスク、及び光ディスク等のようなコンピュータ可読記憶媒体を含んでいてよい。
【００８１】
プログラムコードを記憶及び／又は実行するのに適したデータ処理システムは、例えば、ハードウェアプロセッサのように、システムバスを介してメモリ素子へ直接的又は間接的に結合された少なくとも１つのプロセッサを含んでいてよい。このメモリ素子は、該プログラムコードの実際の実行中に適用されるローカルメモリ、バルクストレージ、及び、実行中にバルクストレージからコードが取得される回数を低減させるために少なくともいくつかのプログラムコードの経時的記憶を実現するキャッシュメモリを含み得る。入力／出力又はＩ／Ｏデバイス（限定されないが、キーボード、ディスプレイ、ポインティングデバイス等を含む）は、直接的に、又は、介在するＩ／Ｏコントローラを介してのいずれかによってシステムへ結合されてよい。
【００８２】
次に、図９を参照すると、本原理が適用されてよい典型的な処理システム９００が、本原理の１つの実施態様にしたがって例示的に図示されている。処理システム９００は、システムバス９０２を経由して他の構成要素へ効果的に結合された少なくとも１つのプロセッサ（「ＣＰＵ」）９０４を含んでいる。キャッシュ９０６、読取専用メモリ（「ＲＯＭ」）９０８、ランダムアクセスメモリ（「ＲＡＭ」）９１０、入力／出力（「Ｉ／Ｏ」）アダプタ９２０、サウンドアダプタ９３０、ネットワークアダプタ９４０、ユーザインターフェースアダプタ９５０、及びディスプレイアダプタ９６０は、システムバス９０２へ効果的に結合される。
【００８３】
記憶デバイス９２２及び第２の記憶デバイス９２４は、Ｉ／Ｏアダプタ９２０によってシステムバス９０２へ効果的に結合される。記憶デバイス９２２、９２４は、ディスク記憶デバイス（例えば、磁気ディスク記憶デバイス又は光ディスク記憶デバイス）、ソリッドステート磁気デバイス等のうちのいずれかであり得る。記憶デバイス９２２、９２４は、同じタイプの記憶デバイス、又は、異なるタイプの記憶デバイスであり得る。
【００８４】
スピーカ９３２は、サウンドアダプタ９３０によってシステムバス９０２へ効果的に結合される。トランシーバ９４２は、ネットワークアダプタ９４０によってシステムバス９０２へ効果的に結合される。ディスプレイデバイス９６２は、ディスプレイアダプタ９６０によってシステムバス９０２へ効果的に結合される。
【００８５】
第１のユーザ入力デバイス９５２、第２のユーザ入力デバイス９５４、及び第３のユーザ入力デバイス９５６は、ユーザインターフェースアダプタ９５０によってシステムバス９０２へ効果的に結合される。ユーザ入力デバイス９５２、９５４、及び９５６は、キーボード、マウス、キーパッド、画像キャプチャデバイス、動き感知デバイス、マイクロホン、前述したデバイスのうちの少なくとも２つの機能を組み込んだデバイス等のうちのいずれかであり得る。もちろん、他のタイプの入力デバイスも使用され得る。ユーザ入力デバイス９５２、９５４、及び９５６は、同じタイプのユーザ入力デバイス、又は、異なるタイプのユーザ入力デバイスであり得る。ユーザ入力デバイス９５２、９５４、及び９５６は、情報を、システム９００へ入力するため、及び、システム９００から出力するために使用される。
【００８６】
もちろん、処理システム９００は、また、当業者によって容易に考慮されるように、他の要素（図示せず）を含むだけでなく、いくつかの要素を省略してもよい。例えば、当業者によって容易に理解されるように、処理システム９００の特定の実施に依存して、他の様々な入力デバイス及び／又は出力デバイスが、処理システム９００に含まれ得る。例えば、様々なタイプのワイヤレス及び／又はワイヤードの入力デバイス及び／又は出力デバイスが使用され得る。さらに、様々な構成における追加のプロセッサ、コントローラ、メモリ等もまた、当業者によって容易に認識されるように利用され得る。処理システム９００のこれら及び他の変形は、本明細書で提供した本原理の教示が与えられると、当業者によって容易に考慮される。
【００８７】
さらに、図１０に関して、以下に記載するシステム１０００は、本原理の各々の実施態様を実施するためのシステムであることが認識されるべきである。処理システム９００の一部又はすべては、システム１０００の要素のうちの１つ又は複数において実施されてよい。
【００８８】
さらに、処理システム９００は、例えば、図１の方法１００の少なくとも一部を含む、本明細書に記載した方法の少なくとも一部を実行してよいことが認識されるべきである。同様に、システム１０００の一部又はすべては、図１の方法１００の少なくとも一部を実行するために使用されてよい。
【００８９】
図１０は、本原理の１つの実施態様にしたがって、特徴的なサブトレースマイニングを使用して、経時的グラフにおける挙動クエリを構築するための典型的なシステム１０００を図示している。システム１０００の多くの態様は、説明及び明確化のために、単数形で記載してあるが、システム１０００の記載に関して述べたアイテムのうちの複数へ適用され得る。例えば、パターン除去器１０１０を説明しているが、複数のパターン除去器１０１０が本原理の教示にしたがって使用されてよい。
【００９０】
システム１０００は、モニタリングデバイス１００２、システムデータログデータベース１００４、経時的グラフ生成器１００６、経時的グラフパターン生成器１００８、パターン判定器１０１０、パターン除去器１０１２、挙動クエリ生成器１０１４、及び記憶デバイス１０１６を含んでいてよい。
【００９１】
モニタリングデバイス１００２は、コンピュータシステムのシステムデータをモニタリングするように構成されてよい。例えば、モニタリングデバイス１００２は、このコンピュータシステムにおける挙動トレースの実行をモニタリングしてよい。それに加えて、モニタリングデバイス１００２は、システムデータログを生成するように構成されてよい。このシステムデータログは、システムデータログデータベース１００４に記憶されてよく、システム１０００の様々な構成要素によってアクセスされてよい。上述したように、システムデータログは、生のシステム挙動、ターゲット挙動、及び／又は、バックグランド挙動を含んでいてよく、モニタリングデバイス１００２によってモニタリング及び収集されてよく、入力データとして適用されてよい。それに加えて、このシステムデータログは、システムエンティティが、オペレーティングシステムにおいてどのようにして互いに作用するのかに関する情報を含んでいてよく、タイムスタンプを含んでいてよい。さらなる実施態様では、モニタリングデバイス１００２は、閉じた環境においてシステムデータをモニタリングするように構成されてよく、ターゲット挙動及び／又はバックグランド挙動は、互いに独立して実行される。
【００９２】
経時的グラフ生成器１００６は、該システムデータログに対応する経時的グラフを提供するように構成されてよい。実施態様では、経時的グラフ生成器１００６が、ターゲット挙動に対応する第１の経時的グラフと、バックグランド挙動の集合に対応する第２の経時的グラフとを提供するように構成されてよい。さらなる実施態様では、経時的グラフ生成器１００６は、このシステムデータログに対応する経時的サブグラフを提供するように構成されてよい。
【００９３】
経時的グラフパターン生成器１００８は、経時的グラフの各々のための経時的グラフパターンを生成するように構成されてよい。例えば、経時的グラフパターン生成器１００８は、第１の経時的グラフのための第１の経時的グラフパターンと、第２の経時的グラフのための第２の経時的グラフパターンとを提供してよい。さらなる実施態様では、経時的グラフパターン生成器１００８は、Ｔ接続されたグラフパターンである経時的グラフパターンを生成してよい。
【００９４】
パターン判定器１０１０は、該経時的グラフパターン同士の間にパターンが存在するか否かを判定するように構成されてよい。例えば、パターン判定器１０１０は、第１の経時的グラフパターンと第２の経時的グラフパターンとの間にパターンが存在するか否かを判定してよい。さらなる実施態様では、パターン判定器１０１０は、第１及び第２の経時的グラフパターンの間の非反復的なグラフパターン及び／又は連続的なグラフパターンを判定するように構成されてよい。例えば、パターン判定器１０１０は、各エッジ間のノードマッピングが１対１であるように、第１の経時的グラフパターンにおける各エッジが、第２の経時的グラフパターンにおける各エッジに対応する場合、経時的グラフパターン同士の間のパターンを判定してよい。さらなる実施態様では、上述したように、パターン判定器１０１０は、前方成長パターン、後方成長パターン、又は内部成長パターンのうちの少なくとも１つを判定してよい。有利なことに、パターン判定部１０１０は、正統なラベリング技術を必要とせずに、非反復的なパターンを判定してよい。
【００９５】
パターン除去器１０１２は、特徴的な経時的グラフを提供するために、判定されたパターンを除去するように構成されてよい。１つの実施態様では、パターン除去器１０１２は、最大頻度及び／又は最大特徴スコアを有するサブ関係のみを選択するようにパターンを除去してよい。さらなる実施態様では、パターン除去器１０１２は、上述したように、サブグラフ除去及び／又はスーパグラフ除去を使用して経時的サブ関係を除去してよい。さらなる実施態様では、パターン除去器１０１２は、各経時的グラフパターンのための残余グラフの集合を判定することによって、これら経時的グラフパターン同士の間のパターンを除去するように構成されてよい。さらなる実施態様では、パターン除去器１０１２は、サブグラフテストからのオーバヘッドを最小化し、残余グラフ集合等価テストからのオーバヘッドを最小化するように構成されてよい。
【００９６】
挙動クエリ生成器１０１４は、該特徴的な経時的グラフに基づいて、挙動クエリを生成するように構成されてよい。実施態様では、挙動クエリ生成器１０１４は、コンピュータシステムにおいて発生している異常な及び／又は疑わしい行動があるか否かを判定するために、システムデータログのリポジトリからターゲット挙動行動を探索する挙動クエリとして、最も高い特徴スコアを有するパターンを選択してよい。この挙動クエリは、その後、記憶デバイス１０１６に記憶され得る。
【００９７】
上記構成は例示的に図示してあるが、他の種類の構成もまた、本原理にしたがって適用されてもよいと考慮されることが注目されるべきである。構成同士の間のこれら及び他の変形は、本明細書に提供した本原理の教示が与えられると、本原理を維持しながら、当業者によって容易に判定される。
【００９８】
いくつかの実施態様では、システム１０００のモニタリングデバイス１００２、システムデータログデータベース１００４、経時的グラフ生成器１００６、経時的グラフパターン生成器１００８、パターン判定器１０１０、パターン除去器１０１２、挙動クエリ生成器１０１４、及び／又は記憶デバイス１０１６は、仮想機器（例えば、コンピューティングデバイス、ノード、サーバ等）であってよく、任意の種類の送信媒体（例えば、インターネット、イントラネット、物のインターネット（Internet of Things）等）を経由して制御するために、ネットワークへ直接的に接続されるか、又は、遠隔に配置されてよい。いくつかの実施態様では、モニタリングデバイス１００２、システムデータログデータベース１００４、経時的グラフ生成器１００６、経時的グラフパターン生成器１００８、パターン判定器１０１０、パターン除去器１０１２、挙動クエリ生成器１０１４、及び／又は記憶デバイス１０１６は、ハードウェアデバイスであってよく、本原理にしたがって、ネットワークへ取り付けられるか、又はネットワークへ組み込まれてよい。
【００９９】
図１０に図示している実施態様では、これらの要素は、バス１００１によって相互接続される。しかしながら、他の実施態様では、他のタイプの接続も使用され得る。さらに、１つの実施態様では、システム１０００の要素のうちの少なくとも１つは、プロセッサベースである。さらに、１つ又は複数の要素は、個別の要素として図示している場合があるが、他の実施態様では、これらの要素は、１つの要素として結合され得る。逆もまた適用可能であり、１つ又は複数の要素が、別の要素の一部であってよい一方、他の実施態様では、この１つ又は複数の要素が、スタンドアロン要素として実装されてよい。本明細書によって提供した本原理の教示が与えられると、システム１１００の要素のこれら及び他の変形が、当業者によって容易に判定される。
【０１００】
前述したものは、すべての観点において例示的及び典型的であるが、限定的ではないとして理解されるべきであり、本明細書に開示した発明の範囲は、詳細な説明からではなく、特許法によって認められた全範囲にしたがって解釈されるように特許請求の範囲から決定されるべきである。本明細書において図示及び説明した実施態様は、本発明の原理の単なる例示であり、当業者は、本発明の範囲及び主旨から逸脱することなく様々な変更を実施してよいことが理解されるべきである。当業者は、本発明の範囲及び主旨から逸脱することなく、他の様々な特徴の組合せを実施できる。
【図１】
0006488009.tif 000015
【図２】
0006488009.tif 000016
【図３】
0006488009.tif 000017
【図４Ａ】
0006488009.tif 000018
【図４Ｂ】
0006488009.tif 000019
【図４Ｃ】
0006488009.tif 000020
【図５】
0006488009.tif 000021
【図６】
0006488009.tif 000022
【図７】
0006488009.tif 000023
【図８】
0006488009.tif 000024
【図９】
0006488009.tif 000025
【図１０】
0006488009.tif 000026