JP6679943B2 - 検知プログラム、検知方法および検知装置 - Google Patents

Description

本発明の実施形態は、検知プログラム、検知方法および検知装置に関する。

従来、システムのログや測定データ等のビッグデータ（以下、過去ログと呼ぶ）を解析することによる、システムの動作などの異常検知（アノマリ検知）が提唱されている。このアノマリ検知では、過去ログの異常事象を頂上事象とし、異常事象を原因として波及する他の異常事象を次事象とするとともに、各異常事象のリスク値を示すリスクツリーを格納しておく。そして、システムにおいてリアルタイムに連続する事象が、リスクツリーの順序で実施された場合に、システムにおける現状の異常（アノマリ）を検知する。

特開平７−２１７９６３号公報 特開平９−２３１３２１号公報 特開２０１４−１２６８８２号公報

事象の発生順序（パターン）と、各事象の発生確率を学習し、各事象の発生確率を付与したツリーに反映させる手法として、ＰＳＴ（Probabilistic Suffix Tree）がある。このＰＳＴにおいては、学習結果によるＰＳＴと、現状の事象の発生順序（パターン）とを比較する。そして、現状のパターンが新規（ＰＳＴ上にパスがない）または稀なパターン（発生確率が非常に低いパターン）である場合に、「いつもと違う」異常（アノマリ）と検知できる。

アノマリ検知では、リアルタイムにアノマリを検知できるリアルタイム性が要求されるため、ＰＳＴをアノマリ検知に用いることを検討した場合、ＰＳＴをＲＡＭ（Random Access Memory）などのメモリに格納することが要求される。しかしながら、ＰＳＴの領域長（メモリ使用量）は、ＰＳＴにおけるパターン段数と、各段における要素数の積に比例して急速に増大する。このようにメモリ使用量が増大する場合、ＰＳＴをメモリに格納することは困難なものとなる。

１つの側面では、アノマリ検知におけるメモリ使用量を削減できる検知プログラム、検知方法および検知装置を提供することを目的とする。

第１の案では、検知プログラムは、過去ログに含まれる各事象を示す値を、値に対応する識別値に変換するとともに、値のグループと、グループに属する値に対応する識別値とを示す変換情報に基づいて、変換情報に示されたグループに属する値についてはグループに対応する同一の識別値に変換する処理をコンピュータに実行させる。また、検知プログラムは、事象の発生順に変換された識別値をルートから順次接続し、識別値ごとに、識別値に対応する事象の発生確率を付与した発生確率付き情報を構築する処理をコンピュータに実行させる。また、検知プログラムは、発生した事象に応じて入力されるイベントデータに含まれる各事象を示す値を、値に対応する識別値に変換するとともに、変換情報に基づいて、変換情報に示されたグループに属する値についてはグループに対応する同一の識別値に変換する処理をコンピュータに実行させる。また、検知プログラムは、構築された発生確率付き情報と、イベントデータより変換された識別値との照合結果をもとに異常の検知を行う処理をコンピュータに実行させる。また、変換情報には、グループとして値の並び順が示されており、検知プログラムは、過去ログに含まれる各事象を示す値の並び順にかかる出現頻度を算出し、当該出現頻度が所定値以上の並び順と、当該並び順に対応する識別値とを定めた変換情報を作成する処理をコンピュータに実行させる。また、第１および第２の変換処理は、変換情報に示された並び順の値については当該並び順に対応する同一の識別値に変換する。

本発明の１実施態様によれば、アノマリ検知におけるメモリ使用量を削減できる。

図１は、実施形態にかかる検知装置の構成例を示すブロック図である。 図２は、アノマリ検知の概要を説明する説明図である。 図３は、ＰＳＴの構築にかかる処理の一例を示すフローチャートである。 図４は、定義・ルール情報を説明する説明図である。 図５は、統計処理による学習を説明する説明図である。 図６は、変換表に基づくＰＳＴの構築を説明する説明図である。 図７は、ＰＳＴにおいてルート以下の要素が置き換わる場合を説明する説明図である。 図８は、アノマリ検知にかかる処理の一例を示すフローチャートである。 図９は、ＰＳＴの構築にかかる処理の一例を示すフローチャートである。 図１０は、定義・ルール情報を説明する説明図である。 図１１は、ＰＳＴにおける部分列の置換えを説明する説明図である。 図１２は、ＰＳＴの再構築にかかる処理の一例を示すフローチャートである。 図１３は、ＰＳＴの再構築を説明する説明図である。 図１４は、ＰＳＴの再構築にかかる処理の一例を示すフローチャートである。 図１５は、ＰＳＴの分割／カットにかかる処理の一例を示すフローチャートである。 図１６は、ＰＳＴの分割／カットを説明する説明図である。 図１７は、実施形態にかかる検知装置のハードウエア構成の一例を示すブロック図である。

以下、図面を参照して、実施形態にかかる検知プログラム、検知方法および検知装置を説明する。実施形態において同一の機能を有する構成には同一の符号を付し、重複する説明は省略する。なお、以下の実施形態で説明する検知プログラム、検知方法および検知装置は、一例を示すに過ぎず、実施形態を限定するものではない。また、以下の各実施形態は、矛盾しない範囲内で適宜組合わせてもよい。

図１は、実施形態にかかる検知装置１の構成例を示すブロック図である。図１に示す検知装置１は、例えばＰＣ（パーソナルコンピュータ）等の情報処理装置である。

検知装置１は、大規模コンピュータシステムやネットワークシステム等のログや測定データ等のビッグデータなどであり、過去に発生した事象が時系列順に記述された過去ログ２０を読み込んでＰＳＴ１４を構築する。検知装置１は、監視対象のシステムにおいてリアルタイムに発生した事象に応じて入力されるイベントデータ３０を受け付け、構築されたＰＳＴ１４と、イベントデータ３０との照合結果をもとに監視対象のシステムにおける異常（アノマリ）を検知し、検知結果をユーザへ報知する。例えば、検知装置１は、アノマリ検知の検知結果を他の端末装置２や所定のアプリへ出力し、端末装置２における検知結果の表示やアプリ通知などを介してユーザへの検知結果の報知を行う。

過去ログ２０およびイベントデータ３０における事象については、様々なものがあってよく、特に限定しない。例えば、監視対象のシステムへのサイバー攻撃などをアノマリとして検知する場合には、メール受信、メール操作、ＰＣ操作、Ｗｅｂアクセス、データ通信などの事象がある。また、監視対象のシステムにおける不正入場などをアノマリとして検知する場合には、監視カメラの映像やカードキーの操作などにより検出されたユーザの行動などの事象がある。また、監視対象のシステムにおける環境異常をアノマリとして検知する場合には、センサにより検出された温度、湿度などの事象がある。また、株式市場などの監視を行うシステムでは、銘柄ごとの株価、天気情報、ＳＮＳ（Social Networking Service）などにおけるコメントなどの事象がある。

図２は、アノマリ検知の概要を説明する説明図である。図２に例示した過去ログ２０は、プロキシサーバなどのデータ通信において「ＧＥＴ ｔｅｘｔ／ｈｔｍｌ」から始まる一連の事象の一例である。

図２に示すように、検知装置１は、過去ログ２０において時系列順に記述された事象を識別値に変換する。図示例では、「ＧＥＴ ｔｅｘｔ／ｈｔｍｌ」を「１」、「ＧＥＴ ｉｍａｇｅ／ｊｐｇ」を「９」、「ＰＯＳＴ ｔｅｘｔ／ｈｔｍｌ」を「１１」の識別値に変換している。次いで、検知装置１は事象の発生順序に識別値を並べたパターン２０ａを生成する。

次いで、検知装置１は、根（ルート）から枝に向かって事象の発生順に識別値（１、９、９、９、１１）を接続する。例えば、ルートからの幹（パス）がある識別値（重複する識別値）については、同じパスを通るように接続する。そして、ルートからのパスがない（重複しない）識別値については、新たに枝分かれした木構造とする。次いで、検知装置１は、木構造の各識別値に、識別値に対応した事象の発生確率（遷移確率）を付与してＰＳＴ１４を構築する。具体的には、事象の総数を分母とし、各事象の発生回数（識別値のパスを通る回数）を分子として遷移確率を算出し、算出した遷移確率を各識別値に付与する。なお、ＰＳＴ１４におけるパス段数には、メモリ使用量の増大を抑止するために、制限を設けてもよい。

検知装置１は、過去ログ２０と同様、イベントデータ３０において時系列順に記述された事象を識別値に変換し、発生順序に識別値を並べることで、システムの現状を示すパターン（現状のパターン）を生成する。次いで、検知装置１は、構築されたＰＳＴ１４と、イベントデータ３０より変換した現状のパターンとを照合する。そして、現状のパターンが新規（ＰＳＴ１４上にパスがない）または稀なパターン（発生確率が所定値以下で非常に低いパターン）である場合に、異常（アノマリ）と検知する。

図１に示すように、検知装置１は、前処理部１０ａ、１０ｂ、定義・ルール情報１１、変換表１２、ＰＳＴ構築部１３、ＰＳＴ１４、ＰＳＴ探索部１５、分散・階層化処理部１６およびアノマリ検知部１７を有する。

前処理部１０ａ、１０ｂは、入力されたデータについて、データの整形・加工などの前処理を行う。前処理部１０ａは、監視対象のシステムより入力された過去ログ２０に前処理を行い、処理後のデータをＰＳＴ構築部１３に出力する。前処理部１０ｂは、監視対象のシステムより入力されたイベントデータ３０に前処理を行い、処理後のデータをＰＳＴ探索部１５に出力する。なお、前処理部１０ａ、１０ｂについては、過去ログ２０およびイベントデータ３０で分ける構成とすることなく、１つの前処理部を共有する構成であってもよい。

前処理部１０ａ、１０ｂが行う前処理には、予め定義された規則をもとに、過去ログ２０およびイベントデータ３０に含まれる各事象の値（内容）を対応する識別値へ変換する変換処理がある。この識別値は、内容に対応する数値、文字、シンボルまたは数値、文字およびシンボルの組合わせなどであってよく、特に限定しない。なお、本実施形態では、一例として、事象の値が前処理部１０ａ、１０ｂの前処理により数値化されるものとする。

また、前処理部１０ａ、１０ｂが行う前処理には、各事象の値のグループと、グループに属する値に対応する識別値とを示す変換表１２に基づいて、変換表１２に示されたグループに属する値についてはグループに対応する同一の識別値に変換する変換処理がある。この変換処理により、過去ログ２０およびイベントデータ３０に含まれる各事象の値が変換表１２に示されたグループに属する場合には、一律に同じ識別値に変換し、ＰＳＴ１４の要素数を削減することができる。

また、前処理部１０ａが行う処理には、過去ログ２０に含まれる各事象を示す値の統計分布を定義・ルール情報１１に示された定義・ルールに従って算出し、算出した統計分布に合わせた値の範囲をグループとする。そして、このグループに対応する識別値を定めた変換表１２を作成する処理がある。このように変換表１２を作成することで、前処理部１０ａ、１０ｂが行う前処理においては、各事象を示す値の統計分布に合わせたグループ分けを行うことができる。

また、前処理部１０ａが行う処理には、過去ログ２０に含まれる各事象を示す値について、時系列における並び順の出現頻度を定義・ルール情報１１に示された定義・ルールに従って算出する。そして、算出した出現頻度が所定値以上の並び順をグループとし、このグループに対応する識別値を定めた変換表１２を作成する処理がある。このように変換表１２を作成することで、前処理部１０ａ、１０ｂが行う前処理においては、出現頻度が所定値以上の並び順、すなわち頻出パターンを一律に同じ識別値に変換し、ＰＳＴ１４のパス段数を削減することができる。

定義・ルール情報１１は、定義・ルールを示す情報であり、例えば、上述した統計分布や出現頻度などの算出にかかる定義・ルールが示されている。この定義・ルール情報１１については、ユーザにより予め設定されたものがメモリやＨＤＤ（Hard Disk Drive）などの記憶装置に格納されている。

ＰＳＴ構築部１３は、前処理後の過去ログ２０をもとに、ＰＳＴ１４を構築する。構築されたＰＳＴ１４は、メモリやＨＤＤなどの記憶装置に格納される。ＰＳＴ探索部１５は、過去ログ２０より構築されたＰＳＴ１４と、前処理後のイベントデータ３０とを照合し、イベントデータ３０より変換した現状のパターンに該当するツリーを探索する。ＰＳＴ探索部１５による探索結果は、アノマリ検知部１７に出力される。

分散・階層化処理部１６は、複数のスレッドを用いるなどして検知装置１における各処理を分散・階層化する。例えば、分散・階層化処理部１６は、ＰＳＴ探索部１５におけるＰＳＴ探索やアノマリ検知部１７におけるアノマリ検知にかかる処理を分散・階層化する。このようにＰＳＴ探索部１５やアノマリ検知部１７における処理を分散・階層化することで、アノマリ検知のリアルタイム性を向上することができる。なお、ＰＳＴ探索部１５による処理の分散・階層化は、前処理部１０ａ、１０ｂ、ＰＳＴ構築部１３における各処理に適用してもよい。

アノマリ検知部１７は、ＰＳＴ探索部１５による探索結果をもとに異常（アノマリ）の検知を行う。具体的には、ＰＳＴ探索部１５による探索結果において該当するツリーが無い場合は現状のパターンが新規（ＰＳＴ上にパスがない）なことから、異常と検知する。また、ＰＳＴ探索部１５による探索結果において該当するツリーがある場合は、ツリーに付与された遷移確率が所定値以下で非常に低いパターンである場合に、異常（アノマリ）と検知する。アノマリ検知部１７は、検知結果を端末装置２や所定のアプリなどに出力する。

ここで、ＰＳＴ１４の構築にかかる処理の詳細を説明する。図３は、ＰＳＴ１４の構築にかかる処理の一例を示すフローチャートである。

図３に示すように、処理が開始されると、前処理部１０ａは、メモリなどに格納された定義・ルール情報１１の読込みを行う（Ｓ１）。

図４は、定義・ルール情報１１を説明する説明図である。図４に示すように、定義・ルール情報１１には、過去ログ２０に含まれる事象（要素Ａ〜Ｙ）ごとのグループ分けルールや備考などの定義・ルールが示されている。グループ分けルールには、グループ分けの有無（１又は０）、グループ分け有りの場合に行う統計処理などを示す学習アルゴリズムおよび分割数／閾値設定の値が示されている。

Ｓ１に次いで、前処理部１０ａは、過去ログ２０の読込みを行う（Ｓ２）。次いで、前処理部１０ａは、過去ログ２０に含まれる事象（要素Ａ〜Ｙ）ごとに、Ｓ３〜Ｓ７の処理を行う。

具体的には、Ｓ３において、前処理部１０ａは、定義・ルール情報１１に示された事象（要素Ａ〜Ｙ）ごとのグループ分けルールを参照し、処理対象の要素についてグループ分けの有無を判定する（Ｓ３）。グループ分け無しの場合（Ｓ３：ＮＯ）、前処理部１０ａは、Ｓ４〜Ｓ６の処理をスキップしてＳ７に処理を進める。

グループ分けありの場合（Ｓ３：ＹＥＳ）、前処理部１０ａは、定義・ルール情報１１に示された事象（要素Ａ〜Ｙ）ごとのグループ分けルールを参照し、学習／ルールのいずれでグループ分けを行うかを判定する（Ｓ４）。

例えば、グループ分けルールにおいて「クラスタリング」や「分布／頻度計算」などの統計処理が示されている場合には、学習でグループ分けを行うものと判定する。また、グループ分けルールにおいて「上限／下限設定」などのルールが示されている場合には、ルールでグループ分けを行うものと判定する。

Ｓ４において学習でグループ分けを行う場合、前処理部１０ａは、グループ分けルールにおいて示された統計処理で過去ログ２０に含まれる事象の統計分布を求め、対象要素の学習を行う（Ｓ５）。

図５は、統計処理による学習を説明する説明図である。図５に示すように、ケースＣ１は、株価や品質など、標準偏差（σ）を基準とする一定値（例えば品質における６σ、２σや、株価における＋３０％、−３０％など）以内が意味をもつケースである。このケースＣ１の要素については、グループ分けルールにおいて「分布／頻度計算」などの統計処理が示されており、統計処理によりグループ分けにかかる標準偏差（σ）などを求める。

ケースＣ２は、温度や湿度など、一定範囲（連続値）が意味をもつケースである。このケースＣ２の要素については、グループ分けルールにおいて「上限／下限設定」などのルールが示されており、一定範囲に対応する閾値が設定される。

ケースＣ３は、嗜好など、統計／分析した結果、特定グループ（クラスタ）の分布が現れるケースである。このケースＣ３の要素については、グループ分けルールにおいて「クラスタリング」などの統計処理が示されており、統計処理によりグループ分けにかかるクラスタ変換式を求める。

Ｓ４においてルールでグループ分けを行う場合、前処理部１０ａは、グループ分けルールにおいて示された「１７度Ｃ〜１９度Ｃ」などの範囲に対応する閾値設定を行う（Ｓ６）。

次いで、前処理部１０ａは、対象要素の学習（Ｓ５）または閾値設定（Ｓ６）の結果をもとに、要素のグループ分けの閾値（グループ分けの範囲）を決定する（Ｓ７）。例えば、対象要素の学習において「分布／頻度計算」などの統計処理で標準偏差（σ）を求めた場合には、標準偏差（σ）を用いて３分割する閾値（２σ、６σ）を決定する。なお、グループ分け無しの場合（Ｓ３：ＮＯ）には、閾値は無しと決定する。

次いで、前処理部１０ａは、過去ログ２０に含まれる事象の全要素についてＳ３〜Ｓ７の処理が完了したか否かを判定する（Ｓ８）。全要素について処理が完了していない場合（Ｓ８：ＮＯ）、前処理部１０ａは、次の要素についてＳ３〜Ｓ７の処理を行うため、Ｓ３へ処理を戻す。

全要素について処理が完了した場合（Ｓ８：ＹＥＳ）、前処理部１０ａは、各要素においてグループ分け・閾値決定（Ｓ７）の処理で決定したグループ分けの範囲にユニークな識別値を割り当てた変換表１２を作成する（Ｓ９）。なお、ユーザなどにより変換表１２が事前に設定されている場合には、上記のＳ１〜Ｓ９の処理を省略してもよい。

次いで、前処理部１０ａは、過去ログ２０を読込み（Ｓ１０）、予め定義された規則をもとに、過去ログ２０に含まれる各事象の値（内容）を対応する識別値へ変換する。また、前処理部１０ａは、変換表１２に基づき、変換表１２に示されたグループに属する値についてはグループに対応する同一の識別値に変換する。そして、ＰＳＴ構築部１３は、変換後の過去ログ２０をもとに、ＰＳＴ１４を構築する（Ｓ１１）。

図６は、変換表１２に基づくＰＳＴの構築を説明する説明図である。図６に示すように、変換表１２は、各要素における数値／文字の範囲であるグループと、グループに属する値を変換する識別値とを有する。例えば、変換表１２において、ルートからの最初の要素（Ａ）については、「２〜４」の数値を「１０」の識別値に変換することが示されている。したがって、個別の識別値で構築されたＰＳＴ１４Ａと比べ、変換表１２に基づいて要素Ａにおける「２〜４」の数値を「１０」に置き換えたＰＳＴ１４Ｂでは、要素数を削減し、木構造における横幅をスリムにすることができる。

図７は、ＰＳＴにおいてルート以下の要素が置き換わる場合を説明する説明図である。なお、図７では、ＰＳＴ１４Ａ、１４Ｂにおけるルートから各要素への木構造を、下位要素ポインタによってルートから順次参照されるテーブル形式のデータとして表現している。

図７に示すように、個別の識別値で構築されたＰＳＴ１４Ａでは、ルートから１段目（要素：Ａ）において数値１〜３００に対応する３００要素を有し、２段目（要素：Ｂ）において１つの数値１０００に対応する１要素を有する。これに対し、１段目（要素：Ａ）について上限＝３００、下限＝１を数値５００に置き換える変換表１２に基づきルート以下の要素を置き換えたＰＳＴ１４Ｂでは、１段目（要素：Ａ）が数値５００の１つの要素となっている。したがって、ＰＳＴ１４Ａ、１４Ｂにおけるテーブル数を比較しても明らかなように、変換表１２に基づくＰＳＴ１４Ｂの構築によって、ＰＳＴにかかるメモリ使用量を大幅に削減することができる。

次に、アノマリ検知にかかる処理の詳細を説明する。図８は、アノマリ検知にかかる処理の一例を示すフローチャートである。

図８に示すように、処理が開始されると、前処理部１０ｂは、イベントデータ３０を読込み、イベントデータ３０より現状のパターンを生成する（Ｓ２０）。次いで、前処理部１０ｂは、生成した現状のパターンを、ＰＳＴ１４において探索対象とするツリー部分（対象ツリー）として選択する（Ｓ２１）。次いで、前処理部１０ｂは、対象ツリーを変換表１２で数値変換することで（Ｓ２２）、対象ツリーにおける値が変換表１２に示されたグループに属する場合には、一律に同じ識別値に変換する。

次いで、ＰＳＴ探索部１５は、ＰＳＴ１４と、数値変換後の対象ツリーとを照合し、対象ツリーに該当する該当ツリーを探索する（Ｓ２３）。アノマリ検知部１７は、ＰＳＴ探索部１５の探索結果をもとに、該当ツリーが無い新規／該当ツリーの遷移確率の判定を行う（Ｓ２４）。Ｓ２４の判定結果をもとに、アノマリ検知部１７は、該当ツリーが無い新規の場合および該当ツリーの遷移確率が所定値以下で非常に低い場合には、アノマリと検知する（Ｓ２５）。

次いで、今回の処理における対象ツリーをＰＳＴ１４に接続する場合にはＰＳＴ１４における事象の総数が増えることから、ＰＳＴ構築部１３は、ＰＳＴ１４における遷移確率を更新する（Ｓ２６）。なお、今回の処理における対象ツリーをＰＳＴ１４に接続しない場合には、ＰＳＴ１４における事象の総数に変化がないことから、Ｓ２６の処理をスキップして遷移確率の更新を行わずに処理を終了する。

ここで、ＰＳＴ１４の段数（縦幅）の削減について説明する。段数の削減では、ＰＳＴ１４において連続する複数の段数（並び順）に対してグループ化を行うことで、ＰＳＴ１４の圧縮を行う。

段数の削減には、配列等の組合わせパターン（ソーティング可）を削減する場合と、順序（時系列）パータン（ソーティング不可）を削減する場合とがある。

組合わせパターンの場合には、上述した要素（横幅）の削減と同様の方法でのグループ分けを行う。具体的には、ＰＳＴ１４において関連する「複数の段数」を隣接させ、統計処理（例えば、クラスタリング）等により、グループ分けを行い、各グループを同一の識別値（１要素）に置き換える。なお、クラスタリング等では、段数（縦幅）と要素（横幅）の両方を削減する場合がある。

順序（時系列）パターンの場合には、出現頻度が高い「パターン」（基本：閉塞）を抽出し、「部分列」についての変換表１２に登録する。例えば、「１→２→３」を「Ｎ」に置き換え、「Ｎ」直下に、以降の「ネスト（先）」を全て接続する。なお、パターンの切れ目は頻度（遷移確率）で抽出し、置き換え箇所ごとに「部分列」の遷移確率を保持する。ＰＳＴ１４の検索時には、「Ｎ」の置き換え表示と、変換表１２（「Ｎ」＝「１→２→３」）を認識し、探索を継続する。また、現在パターンをウインドーとし、変換表１２とともにメモリやＨＤＤなどの記憶装置上に保持して比較に用いる。また、記憶装置上に現在パターンのウインドーと、変換表１２とを保持することで、「部分列」の再帰的置き換えや途中分岐にも対応可能とする。

図９は、ＰＳＴ１４の構築にかかる処理の一例を示すフローチャートである。具体的には、図９は、段数（縦幅）の削減にかかるＰＳＴ１４の構築を例示するフローチャートである。図９における前段の処理（Ｓ３０〜Ｓ３３）は、配列等の組合わせパターンの削減にかかる処理を例示している。また、図９における後段の処理（Ｓ３４〜Ｓ３７）は、順序（時系列）パターンの削減にかかる処理を例示している。

図９に示すように、処理が開始されると、前処理部１０ａは、定義・ルール情報１１および過去ログ２０の読込みを行う（Ｓ３０）。図１０は、定義・ルール情報１１を説明する説明図である。図１０に示すように、定義・ルール情報１１には、組合わせパターンにかかる段の組合わせと、グループ分けのルールとが示されている。

Ｓ３０に次いで、前処理部１０ａは、過去ログ２０のツリーより定義・ルール情報１１に示された段組合わせを求める（Ｓ３１）。次いで、前処理部１０ａは、求めた組合わせについて、定義・ルール情報１１に示された統計処理による学習・グループ分けを実施する（Ｓ３２）。

次いで、前処理部１０ａは、定義・ルール情報１１に示された全組み合わせについてＳ３１、Ｓ３２の処理が完了したか否かを判定する（Ｓ３３）。全組み合わせについてＳ３１、Ｓ３２の処理が完了していない場合（Ｓ３３：ＮＯ）、前処理部１０ａは、次の段組み合わせについてＳ３１、Ｓ３２の処理を行うため、Ｓ３１へ処理を戻す。

Ｓ３４において、前処理部１０ａは、ＰＳＴ１４の中で遷移確率が所定値以上の高頻度の部分列（並び順）を抽出する。次いで、前処理部１０ａは、抽出した部分列を、部分列に対応する識別値（置換数）とともに変換表１２に登録する（Ｓ３５）。次いで、前処理部１０ａは、ＰＳＴ１４で変換表１２の部分列に該当する部分列を置換数で置換える（Ｓ３６）。

次いで、前処理部１０ａは、全ての部分列についてＳ３４〜Ｓ３６の処理が完了したか否かを判定する（Ｓ３７）。全ての部分列についてＳ３４〜Ｓ３６の処理が完了していない場合（Ｓ３７：ＮＯ）、前処理部１０ａは、次の部分列についてＳ３４〜Ｓ３６の処理を行うため、Ｓ３４へ処理を戻す。

図１１は、ＰＳＴにおける部分列の置換えを説明する説明図である。図１１に示すように、変換表１２には、「１→２→３」の部分列が高頻度であることから、置換数「Ｎ」として登録されているものとする。前処理部１０ａは、現在パターンをウインドー１２Ａとして保持する。そして、前処理部１０ａは、ウインドー１２Ａの内容（並び順）が変換表１２の部分列とマッチする場合に、その並び順を置換数に置き換える。例えば、ＰＳＴ１４Ａにおける「１→２→３」の部分列は「Ｎ」に置換えられる。これにより、ＰＳＴ１４Ａは、段数が削減されたＰＳＴ１４Ｂとなる。このように、段数を削減することによって、ＰＳＴにかかるメモリ使用量を削減することができる。

ＰＳＴにかかるメモリ使用量が削減されるケースとしては、例えば、株価のケースと、クラスタのケースとがある。株価のケースとしては、一例として、１０００円の株がストップ高の１３００（＋３０％）まで、１円刻みで変動する場合がある。この場合、１円刻みで変動する箇所をグループ化することで、ルートとなる１０００円の事象からの３００の要素（枝）を、１個の要素として扱うことができる。また、クラスタのケースでは、原則、各クラスタ要素が１つの要素に置換えられる。よって、複数の段数（縦幅）と、複数の要素（横幅）とを、クラスタ数分の要素に削減できる場合がある。

ＰＳＴ構築部１３は、ＰＳＴ１４における遷移確率の順番で、ＰＳＴ１４におけるツリーをソーティングして再構築してもよい。このソーティングには、おもに「順序」と「配列」がある。「順序」は、ルートから順次配下の段（枝方向）に向けて、同一段の要素（横幅）を並べ直す。「配列」は、遷移確率の降順に、段（縦）と同一段の要素（横）をセットで並べ直す。

図１２は、ＰＳＴ１４の再構築にかかる処理の一例を示すフローチャートである。図１２に示すように、処理が開始されると、ＰＳＴ構築部１３は、「順序」または「配列」のいずれのソーティングを行うかを判定する（Ｓ４０）。Ｓ４０において「配列」である場合、ＰＳＴ構築部１３は、ＰＳＴ１４を参照し、遷移確率の降順に全段（縦）を並べ直す（Ｓ４１）。次いで、ＰＳＴ構築部１３は、ツリートップから順次、配下の段に向け、各段の要素を例えば降順に並べ直す（Ｓ４２）。Ｓ４０において「順序」である場合、ＰＳＴ構築部１３は、ツリートップから順次、重複を避けて、各段の要素を遷移確率が高い順に並べ替える（Ｓ４３）。

図１３は、ＰＳＴの再構築を説明する説明図である。図１３に示すように、再構築前のＰＳＴ１４Ａは、遷移確率とは無関係に枝が伸びる木構造となっている。これに対し、再構築後のＰＳＴ１４Ｂは、遷移確率が高い枝が近接する木構造となる。遷移確率が高いデータは、アクセス頻度が高くなることから、メモリのキャッシュに保持される確率が高くなる。よって、ソーティングでのＰＳＴ１４の再構築により、ＰＳＴ１４を参照する際のキャッシュヒット率の向上が見込める。

図１４は、ＰＳＴ１４の再構築にかかる処理の一例を示すフローチャートである。具体的には、図１４は、図１２に例示した処理の別例である。この別例では、再構築したＰＳＴ１４を、遷移確率の降順に、（若い）「数字」から割り当て直す。ここで、「順序」については、（若い）「数字」への置換えは、全体で一意とする。また、「配列」については、各段（縦）で数字割当てが独立しており、他の段と「数字」が重複してもよい。

図１４に示すように、処理が開始されると、ＰＳＴ構築部１３は、「順序」または「配列」のいずれのソーティングを行うかを判定する（Ｓ５０）。Ｓ５０において「配列」である場合、ＰＳＴ構築部１３は、ＰＳＴ１４を参照し、ツリートップから順次、段毎に一意の（若い）数字に置換える（Ｓ５１）。Ｓ５０において「順序」である場合、ＰＳＴ構築部１３は、ＰＳＴ１４を参照し、ツリートップから順次、重複を避け、遷移確率の高い順（降順）に若い数字に置換える（Ｓ５２）。Ｓ５１、Ｓ５２に次いで、ＰＳＴ構築部１３は、一定の遷移確率／領域長でＰＳＴ１４を分割／カットする（Ｓ５３）。

図１５は、ＰＳＴ１４の分割／カットにかかる処理の一例を示すフローチャートである。図１６は、ＰＳＴ１４の分割／カットを説明する説明図である。図１５に示すように、処理が開始されると、ＰＳＴ構築部１３は、ＰＳＴ１４を参照し、ツリートップから遷移確率を評価し（Ｓ６０）、所定値と比較して「高」／「中」／「低」の判定を行う（Ｓ６１）。

遷移確率が高い場合（「高」）、ＰＳＴ構築部１３は、遷移確率が高いと評価されたツリーをメモリ常駐とする（Ｓ６２）。また、遷移確率が中程度である場合（「中」）、ＰＳＴ構築部１３は、遷移確率が中程度と評価された該当部をメモリに分散／階層化して配置する（Ｓ６３）。分散は、例えば別サーバ上のメモリへの配置であってもよい。階層化は、例えばディスク装置（外部記憶）上への配置であってもよい。ただし、分割部分については、ポインタをメモリ上に保持する。

また、遷移確率が低い場合（「低」）、ＰＳＴ構築部１３は、遷移確率が低いと評価された部分（下部ツリー）をメモリ上からカットする（Ｓ６４）。図１６に示すように、上述したＰＳＴ１４の分割／カットを行うことで、ＰＳＴ１４にかかるメモリ使用を効率的なものとすることができる。

以上のように、検知装置１の前処理部１０ａは、過去ログ２０に含まれる各事象を示す値を、値に対応する識別値に変換する。また、前処理部１０ａは、値のグループと、このグループに属する値に対応する識別値とを示す変換表１２に基づいて、変換表１２に示されたグループに属する値についてはグループに対応する同一の識別値に変換する処理を行う。また、検知装置１のＰＳＴ構築部１３は、事象の発生順に前処理部１０ａにより変換された識別値をルートから順次接続し、識別値ごとに、識別値に対応する事象の発生確率を付与したＰＳＴ１４を構築する。また、検知装置１の前処理部１０ｂは、イベントデータ３０に含まれる各事象を示す値を、値に対応する識別値に変換する。また、前処理部１０ｂは、変換表１２に基づいて、変換表１２に示されたグループに属する値についてはグループに対応する同一の識別値に変換する処理を行う。検知装置１のアノマリ検知部１７は、構築されたＰＳＴ１４と、前処理部１０ｂにより変換された識別値との照合結果をもとに異常の検知を行う。

したがって、検知装置１では、過去ログ２０に含まれる各事象を示す値を、変換表１２に示されたグループに属する値についてはグループに対応する同一の識別値に変換してからＰＳＴ１４を構築するため、ＰＳＴ１４のメモリ使用量を削減できる。また、グループに対応する同一の識別値に変換することで、ＰＳＴ１４における遷移確率がグループに対応する識別値のところで集約するため、遷移確率における「密・疎」の分布が際立ち、明確化される。このため、ＰＳＴ１４の探索によるアノマリの検知性能（精度）が向上する。

なお、図示した各装置の各構成要素は、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。

例えば、本実施形態では検知装置１単体の装置構成を例示したが、複数のストレージ装置やサーバ装置などをネットワークで接続したクラウドコンピューティングとしてもよい。

また、検知装置１で行われる各種処理機能は、ＣＰＵ（またはＭＰＵ、ＭＣＵ（Micro Controller Unit）等のマイクロ・コンピュータ）上で、その全部または任意の一部を実行するようにしてもよい。また、各種処理機能は、ＣＰＵ（またはＭＰＵ、ＭＣＵ等のマイクロ・コンピュータ）で解析実行されるプログラム上、またはワイヤードロジックによるハードウエア上で、その全部または任意の一部を実行するようにしてもよいことは言うまでもない。

ところで、上記の実施形態で説明した各種の処理は、予め用意されたプログラムをコンピュータで実行することで実現できる。そこで、以下では、上記の実施例と同様の機能を有するプログラムを実行するコンピュータ（ハードウエア）の一例を説明する。図１７は、実施形態にかかる検知装置１のハードウエア構成の一例を示すブロック図である。

図１７に示すように、検知装置１は、各種演算処理を実行するＣＰＵ１０１と、データ入力を受け付ける入力装置１０２と、モニタ１０３と、スピーカ１０４とを有する。また、検知装置１は、記憶媒体からプログラム等を読み取る媒体読取装置１０５と、各種装置と接続するためのインタフェース装置１０６と、有線または無線により外部機器と通信接続するための通信装置１０７とを有する。また、検知装置１は、各種情報を一時記憶するＲＡＭ１０８と、ハードディスク装置１０９とを有する。また、検知装置１内の各部（１０１〜１０９）は、バス１１０に接続される。

ハードディスク装置１０９には、上記の実施形態で説明した前処理部１０ａ、１０ｂ、変換表１２、ＰＳＴ構築部１３、ＰＳＴ探索部１５、分散・階層化処理部１６およびアノマリ検知部１７における各種の処理を実行するためのプログラム１１１が記憶される。また、ハードディスク装置１０９には、プログラム１１１が参照する各種データ１１２（定義・ルール情報１１、変換表１２、ＰＳＴ１４、過去ログ２０およびイベントデータ３０など）が記憶される。入力装置１０２は、例えば、検知装置１の操作者から操作情報の入力を受け付ける。モニタ１０３は、例えば、操作者が操作する各種画面を表示する。インタフェース装置１０６は、例えば印刷装置等が接続される。通信装置１０７は、ＬＡＮ（Local Area Network）等の通信ネットワークと接続され、通信ネットワークを介した外部機器との間で各種情報をやりとりする。

ＣＰＵ１０１は、ハードディスク装置１０９に記憶されたプログラム１１１を読み出して、ＲＡＭ１０８に展開して実行することで、各種の処理を行う。なお、プログラム１１１は、ハードディスク装置１０９に記憶されていなくてもよい。例えば、検知装置１が読み取り可能な記憶媒体に記憶されたプログラム１１１を読み出して実行するようにしてもよい。検知装置１が読み取り可能な記憶媒体は、例えば、ＣＤ−ＲＯＭやＤＶＤディスク、ＵＳＢ（Universal Serial Bus）メモリ等の可搬型記録媒体、フラッシュメモリ等の半導体メモリ、ハードディスクドライブ等が対応する。また、公衆回線、インターネット、ＬＡＮ等に接続された装置にこのプログラム１１１を記憶させておき、検知装置１がこれらからプログラム１１１を読み出して実行するようにしてもよい。

１…検知装置
２…端末装置
１０ａ、１０ｂ…前処理部
１１…定義・ルール情報
１２…変換表
１２Ａ…ウインドー
１３…ＰＳＴ構築部
１４、１４Ａ、１４Ｂ…ＰＳＴ
１５…ＰＳＴ探索部
１６…分散・階層化処理部
１７…アノマリ検知部
２０…過去ログ
２０ａ…パターン
３０…イベントデータ
１０１…ＣＰＵ
１０２…入力装置
１０３…モニタ
１０４…スピーカ
１０５…媒体読取装置
１０６…インタフェース装置
１０７…通信装置
１０８…ＲＡＭ
１０９…ハードディスク装置
１１０…バス
１１１…プログラム
１１２…各種データ
Ｃ１、Ｃ２…ケース

Claims (5)

1. 過去ログに含まれる各事象を示す値を、当該値に対応する識別値に変換するとともに、前記値のグループと、当該グループに属する値に対応する識別値とを示す変換情報に基づいて、前記変換情報に示されたグループに属する値については当該グループに対応する同一の識別値に変換する第１の変換処理を行い、
   前記事象の発生順に前記第１の変換処理により変換された識別値をルートから順次接続し、前記識別値ごとに、当該識別値に対応する事象の発生確率を付与した発生確率付き情報を構築し、
   発生した事象に応じて入力されるイベントデータに含まれる各事象を示す値を、当該値に対応する識別値に変換するとともに、前記変換情報に基づいて、前記変換情報に示されたグループに属する値については当該グループに対応する同一の識別値に変換する第２の変換処理を行い、
   前記構築された発生確率付き情報と、前記第２の変換処理により変換された識別値との照合結果をもとに異常の検知を行い、
   前記変換情報には、前記グループとして値の並び順が示されており、
   前記過去ログに含まれる各事象を示す値の並び順にかかる出現頻度を算出し、当該出現頻度が所定値以上の前記並び順と、当該並び順に対応する識別値とを定めた変換情報を作成する処理をコンピュータに実行させ、
   前記第１および第２の変換処理は、前記変換情報に示された並び順の値については当該並び順に対応する同一の識別値に変換する
   ことを特徴とする検知プログラム。
2. 前記変換情報には、前記グループとして値の範囲が示されており、
   前記第１および第２の変換処理は、前記変換情報に示された範囲内の値については当該範囲に対応する同一の識別値に変換する
   ことを特徴とする請求項１に記載の検知プログラム。
3. 前記過去ログに含まれる各事象を示す値の統計分布を算出し、当該統計分布に合わせた前記値の範囲と、当該範囲に対応する識別値とを定めた変換情報を作成する処理を更に有し、
   前記第１および第２の変換処理は、前記作成された変換情報に基づいた変換処理を行う
   ことを特徴とする請求項２に記載の検知プログラム。
4. 過去ログに含まれる各事象を示す値を、当該値に対応する識別値に変換するとともに、前記値のグループと、当該グループに属する値に対応する識別値とを示す変換情報に基づいて、前記変換情報に示されたグループに属する値については当該グループに対応する同一の識別値に変換する第１の変換処理を行い、
   前記事象の発生順に前記第１の変換処理により変換された識別値をルートから順次接続し、前記識別値ごとに、当該識別値に対応する事象の発生確率を付与した発生確率付き情報を構築し、
   発生した事象に応じて入力されるイベントデータに含まれる各事象を示す値を、当該値に対応する識別値に変換するとともに、前記変換情報に基づいて、前記変換情報に示されたグループに属する値については当該グループに対応する同一の識別値に変換する第２の変換処理を行い、
   前記構築された発生確率付き情報と、前記第２の変換処理により変換された識別値との照合結果をもとに異常の検知を行い、
   前記変換情報には、前記グループとして値の並び順が示されており、
   前記過去ログに含まれる各事象を示す値の並び順にかかる出現頻度を算出し、当該出現頻度が所定値以上の前記並び順と、当該並び順に対応する識別値とを定めた変換情報を作成する処理をコンピュータが実行し、
   前記第１および第２の変換処理は、前記変換情報に示された並び順の値については当該並び順に対応する同一の識別値に変換する
   ことを特徴とする検知方法。
5. プロセッサが、
   過去ログに含まれる各事象を示す値を、当該値に対応する識別値に変換するとともに、前記値のグループと、当該グループに属する値に対応する識別値とを示す変換情報に基づいて、前記変換情報に示されたグループに属する値については当該グループに対応する同一の識別値に変換する第１の変換処理を行い、
   前記事象の発生順に前記第１の変換処理により変換された識別値をルートから順次接続し、前記識別値ごとに、当該識別値に対応する事象の発生確率を付与した発生確率付き情報を構築し、
   発生した事象に応じて入力されるイベントデータに含まれる各事象を示す値を、当該値に対応する識別値に変換するとともに、前記変換情報に基づいて、前記変換情報に示されたグループに属する値については当該グループに対応する同一の識別値に変換する第２の変換処理を行い、
   前記構築された発生確率付き情報と、前記第２の変換処理により変換された識別値との照合結果をもとに異常の検知を行い、
   前記変換情報には、前記グループとして値の並び順が示されており、
   前記過去ログに含まれる各事象を示す値の並び順にかかる出現頻度を算出し、当該出現頻度が所定値以上の前記並び順と、当該並び順に対応する識別値とを定めた変換情報を作成する処理を実行し、
   前記第１および第２の変換処理は、前記変換情報に示された並び順の値については当該並び順に対応する同一の識別値に変換する
   ことを特徴とする検知装置。

Images