(57)【特許請求の範囲】
【請求項１】
攻撃と判定された通信のアクセスログにおけるパラメータ同士の共通した文字列を抽出する抽出部と、
前記抽出部によって抽出された連続する文字列のうち、文字列長が所定の文字列長以上の文字列を基に攻撃パターンを生成する攻撃パターン生成部と
を備え、
前記抽出部は、パラメータ同士で共通する文字列であって、且つ、連続しない文字列間を区切る区切り文字を入れたまま最長共通部分列を算出し、該最長共通部分列を用いて、共通した文字列を抽出することを特徴とする攻撃パターン抽出装置。
【請求項２】
前記攻撃パターン生成部は、文字列長が所定の文字列長以上の文字列が複数ある場合には、複数の文字列と各文字列の出現順序とを基に攻撃パターンを生成することを特徴とする請求項１に記載の攻撃パターン抽出装置。
【請求項３】
前記攻撃パターン生成部は、前記抽出部によって抽出された連続する文字列が既に生成された攻撃パターンに含まれる場合には、抽出された連続する文字列を基に攻撃パターンを生成しないことを特徴とする請求項１に記載の攻撃パターン抽出装置。
【請求項４】
前記抽出部は、抽出した共通の文字列の長さが、抽出前の文字列の長さに対して、所定の比率以下に低下する場合は、当該文字列からの共通した文字列の抽出を抑制することを特徴とする請求項１に記載の攻撃パターン抽出装置。
【請求項５】
攻撃パターン抽出装置で実行される攻撃パターン抽出方法であって、
攻撃と判定された通信のアクセスログにおけるパラメータ同士の共通した文字列を抽出する抽出工程と、
前記抽出工程によって抽出された連続する文字列のうち、文字列長が所定の文字列長以上の文字列を基に攻撃パターンを生成する攻撃パターン生成工程と
を含み、
前記抽出工程は、パラメータ同士で共通する文字列であって、且つ、連続しない文字列間を区切る区切り文字を入れたまま最長共通部分列を算出し、該最長共通部分列を用いて、共通した文字列を抽出することを特徴とする攻撃パターン抽出方法。
【請求項６】
攻撃と判定された通信のアクセスログにおけるパラメータ同士の共通した文字列を抽出する抽出ステップと、
前記抽出ステップによって抽出された連続する文字列のうち、文字列長が所定の文字列長以上の文字列を基に攻撃パターンを生成する攻撃パターン生成ステップと
をコンピュータに実行させ、
前記抽出ステップは、パラメータ同士で共通する文字列であって、且つ、連続しない文字列間を区切る区切り文字を入れたまま最長共通部分列を算出し、該最長共通部分列を用いて、共通した文字列を抽出するための攻撃パターン抽出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、攻撃パターン抽出装置、攻撃パターン抽出方法および攻撃パターン抽出プログラムに関する。
【背景技術】
【０００２】
近年、インターネットの普及に伴い、Ｗｅｂサーバに対する攻撃が急増している。このような攻撃の対策としてＩＤＳ(Intrusion  Detection  System)、ＩＰＳ(Intrusion  Prevention  System)、ＷＡＦ(Web  Application  Firewall)等によるネットワークへの不正侵入検知・防御システムが知られている。これらは主に、攻撃パターンをシグネチャとして覚えておき、シグネチャとマッチした通信を検知するものである。従って、新たな攻撃に対応するには、攻撃パターンに合わせてシグネチャを作成する必要がある。【０００３】
従来、シグネチャ等の攻撃パターンの生成においては、攻撃コードに共通した特徴を元にパラメータの形態素解析を行い、その結果の最長共通部分列（ＬＣＳ：Longest  Common  Subsequence）を算出して生成する手法が知られている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】越智  勇貴、安部  剛、“Exploitに対するWAFシグネチャ自動生成の研究”、Computer  Security  Symposium  2016、pp.958-963.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記した従来の技術では、適切な攻撃パターンを生成することができない場合があるという課題があった。つまり、従来の技術では、既知の攻撃コードの特徴を元にしているため、未知の攻撃には形態素解析が適切に行われず、適切な攻撃パターンを生成できない場合があった。また、ＬＣＳ算出の際に、共通部分の文字列長を考慮していないため、偶然一致した短い文字列を有意な攻撃パターンとして生成してしまう可能性があるという課題があった。
【課題を解決するための手段】
【０００６】
上述した課題を解決し、目的を達成するために、本発明の攻撃パターン抽出装置は、攻撃と判定された通信のアクセスログにおけるパラメータ同士の共通した文字列を抽出する抽出部と、前記抽出部によって抽出された連続する文字列のうち、文字列長が所定の文字列長以上の文字列を基に攻撃パターンを生成する攻撃パターン生成部とを備えたことを特徴とする。【０００７】
また、本発明の攻撃パターン抽出方法は、攻撃パターン抽出装置で実行される攻撃パターン抽出方法であって、攻撃と判定された通信のアクセスログにおけるパラメータ同士の共通した文字列を抽出する抽出工程と、前記抽出工程によって抽出された連続する文字列のうち、文字列長が所定の文字列長以上の文字列を基に攻撃パターンを生成する攻撃パターン生成工程とを含んだことを特徴とする。【０００８】
また、本発明の攻撃パターン抽出プログラムは、攻撃と判定された通信のアクセスログにおけるパラメータ同士の共通した文字列を抽出する抽出ステップと、前記抽出ステップによって抽出された連続する文字列のうち、文字列長が所定の文字列長以上の文字列を基に攻撃パターンを生成する攻撃パターン生成ステップとをコンピュータに実行させることを特徴とする。
【発明の効果】
【０００９】
本発明によれば、適切な攻撃パターンを生成することができるという効果を奏する。
【図面の簡単な説明】
【００１０】
【図１】図１は、第一の実施の形態に係る攻撃パターン抽出装置の概要を示す構成図である。
【図２】図２は、テーブル初期化処理について説明する図である。
【図３】図３は、テーブル更新処理について説明する図である。
【図４】図４は、結果文字列更新処理について説明する図である。
【図５】図５は、通常のＬＣＳを用いた場合について説明する図である。
【図６】図６は、区切り文字入りＬＣＳを用いた場合について説明する図である。
【図７】図７は、第一の実施の形態に係る攻撃パターン抽出装置におけるクラスタリング処理の流れを示すフローチャートである。
【図８】図８は、第一の実施の形態に係る攻撃パターン抽出装置におけるＬＣＳ算出処理の流れを示すフローチャートである。
【図９】図９は、攻撃パターン抽出プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【００１１】
以下に、本願に係る攻撃パターン抽出装置、攻撃パターン抽出方法および攻撃パターン抽出プログラムの実施の形態を図面に基づいて詳細に説明する。なお、この実施の形態により本願に係る攻撃パターン抽出装置、攻撃パターン抽出方法および攻撃パターン抽出プログラムが限定されるものではない。
【００１２】
［第一の実施の形態］
以下の実施の形態では、第一の実施の形態に係る攻撃パターン抽出装置１０の構成、攻撃パターン抽出装置１０の処理の流れを順に説明し、最後に第一の実施の形態による効果を説明する。
【００１３】
［攻撃パターン抽出装置の構成］
まず、図１を用いて、攻撃パターン抽出装置１０の構成を説明する。図１は、第一の実施の形態に係る攻撃パターン抽出装置の概要を示す構成図である。図１に示すように、この攻撃パターン抽出装置１０は、入力部１１、出力部１２、制御部１３および記憶部１４を有する。
【００１４】
入力部１１は、各種情報の入力操作を受け付けるデバイスであり、例えば、攻撃と判定されたＷｅｂサーバへのアクセスログの入力を受け付ける。出力部１２は、各種情報を出力するデバイスであり、例えば、攻撃パターンを出力する。
【００１５】
また、記憶部１４は、制御部１３による各種処理に必要なデータおよびプログラムを格納するが、特に本発明に密接に関連するものとしては、ログ記憶部１４ａを有する。例えば、記憶部１４は、ＲＡＭ（Random  Access  Memory）、フラッシュメモリ（Flash  Memory）等の半導体メモリ素子、又は、ハードディスク、光ディスク等の記憶装置などである。
【００１６】
ログ記憶部１４ａは、攻撃と判定されたＷｅｂサーバへのアクセスログを記憶する。アクセスログは、例えば、データ項目として、「発ＩＰ」、「日時」、「リクエスト」を含むものとする。あるいはアクセスログから、リクエストに含まれるパラメータのみを抽出してデータ項目としても良い。
【００１７】
制御部１３は、各種の処理手順などを規定したプログラムおよび所要データを格納するための内部メモリを有し、これらによって種々の処理を実行するが、特に本発明に密接に関連するものとしては、抽出部１３ａおよび攻撃パターン生成部１３ｂを有する。ここで、制御部１３は、ＣＰＵ（Central  Processing  Unit）やＭＰＵ（Micro  Processing  Unit）などの電子回路やＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ（Field  Programmable  Gate  Array）などの集積回路である。
【００１８】
抽出部１３ａは、攻撃と判定された通信のアクセスログにおけるパラメータ同士の共通した文字列を抽出する。抽出部１３ａは、パラメータ同士で共通する文字列であって、且つ、連続しない文字列間を区切る区切り文字を入れたまま最長共通部分列を算出し、該最長共通部分列を用いて、共通した文字列を抽出する。
【００１９】
抽出部１３ａは、攻撃と判定された通信のアクセスログにおけるパラメータ同士の共通した文字列を抽出するために、以下のクラスタリング処理を行う。以下に、クラスタリング処理について詳しく説明するが、以降の説明では、文字列Ｘの長さを「ｌｅｎ（Ｘ）」と表記し、文字列Ｘのｉ番目の文字（１から数える）を「Ｘ［ｉ］」と表記する。また、複数のパラメータをｐ１,ｐ２，・・・，ｐｎと表記する。最初に、抽出部１３ａは、複数のパラメータｐ１，ｐ２，・・・，ｐｎをクラスタリングする。
【００２０】
まず、抽出部１３ａは、クラスタ集合Ｃを初期化する。クラスタ集合Ｃ（Ｃ＝｛Ｃ１，Ｃ２，．．．，Ｃｎ｝）に含まれるクラスタＣｉ（１≦ｉ≦ｎ）を、｛ｌｃｓ:パラメータｐｉ自身、ｓｔｒｉｎｇｓ：ｐｉのみからなる配列｝からなる連想配列（Ｃｉ＝｛ｌｃｓ：ｐｉ，ｓｔｒｉｎｇｓ：［ｐｉ］｝（１≦ｉ≦ｎ））とする。また、抽出部１３ａは、結果リストＲも空の配列で初期化する。
【００２１】
続いて、抽出部１３ａは、処理対象クラスタ抽出処理を行う。具体的には、抽出部１３ａは、クラスタ集合Ｃから処理対象クラスタ（例えば最後の要素）を１つ抽出し、Ｃｔとする。クラスタ集合ＣをＣ＼｛Ｃｔ｝で更新する。ここで“＼”は差集合を表す。すなわち、クラスタ集合Ｃから要素Ｃｔを取り除いたものでＣを更新する。
【００２２】
そして、抽出部１３ａは、処理対象クラスタと他クラスタのＬＣＳ算出を行う。具体的には、抽出部１３ａは、クラスタ集合Ｃの各要素Ｃｉ（１≦ｉ≦｜Ｃ｜）のｌｃｓ要素と、Ｃｔのｌｃｓ要素とのＬＣＳ（最長共通部分列）を順次算出する。ＬＣＳの算出は、後述の手順で行い、連続しない部分は区切り文字（例：“|”）で区切られた結果が得られる。具体的を挙げて説明すると、抽出部１３ａは、要素Ｃｉのｌｃｓ要素“ａｂＣＤｅＦＧｈ”とＣｔのｌｃｓ要素“ｘｙＣｚＤＦＧ”とのＬＣＳの算出結果として、“Ｃ｜Ｄ｜ＦＧ”が得られる。
【００２３】
そして、抽出部１３ａは、処理対象クラスタとクラスタ集合Ｃの各クラスタとのＬＣＳ算出を行うと、ＬＣＳを区切り文字で分割した文字列の長さのうち、最長のものをＣｉとＣｔのスコアｓ（Ｃｉ,Ｃｔ）とする。
【００２４】
つまり、スコアｓ（Ｃｉ,Ｃｔ）は、クラスタＣｉ,Ｃｔのｌｃｓ要素同士の区切り文字入りＬＣＳを算出し、それを区切り文字で分割した文字列の長さのうち、最長のものである。例えば、クラスタＣｉ「Ｃｉ＝｛ｌｃｓ：“ＡＢ｜ＣＤ”,ｓｔｒｉｎｇｓ：［“ＡＢ１２ＣＤ”,“ＡＢＣＤ”］｝」とクラスタＣｔ「Ｃｔ＝｛ｌｃｓ：“ＡＢ｜Ｃ｜Ｅ”,ｓｔｒｉｎｇｓ：［“ＡＢｘＣＥ”,“ＡＢｙＣｄＥ”］｝」とでは、“ＡＢ｜ＣＤ”と“ＡＢ｜Ｃ｜Ｅ”の区切り文字入りＬＣＳとして、“ＡＢ｜Ｃ”が得られる。そして、“ＡＢ｜Ｃ”を区切り文字で分割し、“ＡＢ”,“Ｃ”の文字列長（２、１）のうち最長の“２”がスコアｓ（Ｃｉ,Ｃｔ）となる。スコアｓ（Ｃｉ,Ｃｔ）が最大となるＣｉ（１≦ｉ≦｜Ｃ｜）をＣｋとする。なお、スコアｓ（Ｃｉ,Ｃｔ）が最大となるＣｉが複数ある場合には、スコアｓ（Ｃｉ,Ｃｔ）が最大となる複数のＣｉのうち任意の一つをＣｋとする。
【００２５】
続いて、抽出部１３ａは、最大スコア確認処理を行う。具体的には、抽出部１３ａは、ＣｋとＣｔのスコアｓ（Ｃｋ,Ｃｔ）（最大スコア）が最小文字列長閾値以上かを確認する。抽出部１３ａは、確認の結果、閾値未満の場合には、処理対象クラスタＣｔを結果リストＲに追加し、処理対象クラスタ抽出処理に戻って、新しい処理対象クラスタを抽出して上記の処理を繰り返す。一方、抽出部１３ａは、確認の結果、閾値以上の場合には、ＣｋとＣｔを以下の通りマージしてＣＮを作成する。ＣＮのｌｃｓ：ＣｋのｌｃｓとＣｔのｌｃｓの区切り文字入りＬＣＳ、ＣＮのｓｔｒｉｎｇｓ：ＣｋのｓｔｒｉｎｇｓとＣｔのｓｔｒｉｎｇｓを配列として連結する。その後、抽出部１３ａは、Ｃを（Ｃ＼｛Ｃｋ｝）∪｛ＣＮ｝で更新し、処理対象クラスタ抽出処理に戻って、新しい処理クラスタを抽出して上記の処理を繰り返す。
【００２６】
そして、抽出部１３ａは、クラスタ集合Ｃのサイズが１になるまで、前述した処理対象クラスタ抽出処理、ＬＣＳ算出処理および最大スコア確認処理を繰り返す。その後、抽出部１３ａは、クラスタ集合のサイズが１になった場合には、最後のクラスタを結果リストＲに追加する。そして、抽出部１３ａは、結果リストＲを攻撃パターン生成部１３ｂに通知する。
【００２７】
ここで、上述したＬＣＳ算出処理について詳しく説明する。抽出部１３ａは、ＬＣＳ算出処理において、２つの文字列ｘ，ｙが与えられた時、これらの最長共通部分列（ＬＣＳ）を算出する。抽出部１３ａは、算出の際、連続しない部分は区切り文字（例えば、“|”）で区切る。なお、区切り文字はｘ，ｙに現れない文字であれば何でもよい。以降の説明では、ｘ＝“ａＢＣｄ”，ｙ＝“ＢｅＣ”を例として説明する。
【００２８】
まず、抽出部１３ａは、ＬＣＳ算出対象の２つの文字列ｘ，ｙを入力として受け取る。そして、抽出部１３ａは、テーブル初期化処理を行う。例えば、抽出部１３ａは、図２に例示するように、（ｌｅｎ（ｙ）＋１）×（ｌｅｎ（ｘ）＋１）の配列ｔを用意し、０行目、０列目の全ての要素を０で初期化する。図２は、テーブル初期化処理について説明する図である。
【００２９】
そして、抽出部１３ａは、テーブル更新処理を行う。具体的には、抽出部１３ａは、ｉ＝１，２，・・・，ｌｅｎ（ｙ）、ｊ＝１，２，・・・，ｌｅｎ（ｘ）とし、以下の（１）、（２）の規則に従って、テーブルを更新する。（１）ｘ［ｊ］＝ｙ［ｉ］の場合には、ｔ［ｉ］［ｊ］＝ｔ［ｉ−１］［ｊ−１］＋１と更新し、（２）ｘ［ｊ］＝ｙ［ｉ］以外の場合には、ｔ［ｉ］［ｊ］＝ｍａｘ（ｔ［ｉ−１］［ｊ］,  ｔ［ｉ］［ｊ−１］）と更新する。
【００３０】
ここで、図３の例を用いて、テーブル更新処理を説明する。図３は、テーブル更新処理について説明する図である。図３の例を挙げて説明すると、例えば、抽出部１３ａは、３列目（ｘ［３］）の文字「Ｃ」と、３行目（ｙ［３］）の文字「Ｃ」とが同じである場合には、２行２列目の要素「ｔ［２，２］＝１」に１を加算した値「２」を、３行目３列目の要素ｔ［３，３］として更新する。また、抽出部１３ａは、４列目（ｘ［４］）の文字「ｄ」と、３行目（ｙ［３］）の文字「Ｃ」とが異なる場合には、３行３列目の要素「ｔ［３，３］＝２」と、２行４列目の要素「ｔ［２，４］＝１」とのうち、最大の「２」を、３行４列目の要素ｔ［３，４］として更新する。
【００３１】
そして、抽出部１３ａは、結果文字列を空文字列“”で初期化する。続いて、抽出部１３ａは、ｉ＞０かつｊ＞０の間、以下の（１）、（２）を繰り返し、結果文字列を更新する。（１）ｘ［ｊ］＝ｙ［ｉ］の場合には、結果文字列にｘ［ｊ］を追記し、ｉ,ｊをともに１減ずる。（２）ｘ［ｊ］＝ｙ［ｉ］以外の場合には、ｔ［ｉ−１］［ｊ］＞ｔ［ｉ］［ｊ−１］ならばｉを１減じ、そうでないならばｊを１減ずる。結果文字列の末尾が区切り文字でなければ区切り文字を追記、末尾が区切り文字ならば何もしない。
【００３２】
ここで、図４の例を用いて、結果文字列更新処理について説明する。図４は、結果文字列更新処理について説明する図である。図４の例を挙げて説明すると、例えば、抽出部１３ａは、４列目（ｘ［４］）の文字「ｄ」と、３行目（ｙ［３］）の文字「Ｃ」とが異なる場合には、２行４列目の要素「ｔ［２，４］＝１」と３行３列目の要素「ｔ［３，３］＝２」とを比較し、３行３列目の要素「ｔ［３，３］＝２」が大きい場合には、ｊを１減ずる。なお、結果文字列の末尾が区切り文字ではないので、結果文字列を“”から“｜”に更新する。
【００３３】
続いて、抽出部１３ａは、３列目（ｘ［３］）の文字「Ｃ」と、３行目（ｙ［３］）の文字「Ｃ」とが同じである場合には、結果文字列を“｜”から“｜Ｃ”に更新し、ｉ，ｊをともに１減ずる。そして、抽出部１３ａは、２列目（ｘ［２］）の文字「Ｂ」と、２行目（ｙ［２］）の文字「ｅ」とが異なる場合には、１行２列目の要素「ｔ［１，２］＝１」と２行１列目の要素「ｔ［２，１］＝０」とを比較し、１行２列目の要素「ｔ［１，２］＝１」が大きい場合には、ｉを１減ずる。また、結果文字列の末尾が区切り文字ではないので、結果文字列を“｜Ｃ”から“｜Ｃ｜”に更新する。
【００３４】
そして、抽出部１３ａは、２列目（ｘ［２］）の文字「Ｂ」と、１行目（ｙ［１］）の文字「Ｂ」とが同じである場合には、結果文字列を“｜Ｃ｜”から“｜Ｃ｜Ｂ”に更新し、ｉ，ｊをともに１減ずる。
【００３５】
その後、抽出部１３ａは、結果文字列を反転する。例えば、抽出部１３ａは、結果文字列が“｜Ｃ｜Ｂ”である場合には、結果文字列を“Ｂ｜Ｃ｜”に反転させる。
【００３６】
図１の説明に戻って、攻撃パターン生成部１３ｂは、抽出部１３ａによって抽出された連続する文字列のうち、文字列長が所定の文字列長以上の文字列を基に攻撃パターンを生成する。また、攻撃パターン生成部１３ｂは、文字列長が所定の文字列長以上の文字列が複数ある場合には、複数の文字列と各文字列の出現順序とを基に攻撃パターンを生成する。また、攻撃パターン生成部１３ｂは、抽出部１３ａによって抽出された連続する文字列が既に生成された攻撃パターンに含まれる場合には、何もしない。
【００３７】
具体的には、攻撃パターン生成部１３ｂは、結果リストＲ＝［Ｃ’１,Ｃ’２，・・・，Ｃ’ｍ］の各要素について、ｓｔｒｉｎｇｓ要素の個数が最小クラスタサイズ閾値以上であるものを抽出する。抽出した要素のｌｃｓ要素が、抽出したい共通部分である。攻撃パターン生成部１３ｂは、共通部分を区切り文字で分割し、最小文字列長閾値以上の長さの文字列を“＊”で連結した正規表現が、最終的に求める攻撃パターンとなる。なお、閾値として最小文字列長閾値とは別の新しい閾値を採用してもよい。
【００３８】
具体例を挙げて説明すると、攻撃パターン生成部１３ｂは、例えば、ｌｃｓ：“ａ｜ＢＣＤ｜ｅｆ｜ｇ｜ＨＩＪＫ”を区切り文字で分割して、“ａ”，“ＢＣＤ”，“ｅｆ”，“ｇ”,“ＨＩＪＫ”とし、閾値（例えば、「３」）以上の長さの文字列を出現順に“＊”で連結して攻撃パターンとして“ＢＣＤ＊ＨＩＪＫ”を生成する。また、“ＢＣＤ＊ＨＩＪＫ”が攻撃パターンとして既に生成されている場合には、何もしない。
【００３９】
このように、攻撃パターン抽出装置１０は、ＬＣＳを算出する際、文字が連続しない箇所に区切り文字を入れながら算出し、閾値以上の長さのものを抽出するため、極端に短い共通部分を攻撃パターンとして抽出することがない。
【００４０】
また、攻撃パターン抽出装置１０は、クラスタをマージする際、区切り文字を入れたままでＬＣＳを算出するため、「共通部が連続している」という情報を失うことなく、３つ以上のパラメータから共通部を効率よく抽出することができる。
【００４１】
ここで、図５および図６の例を用いて、区切り文字列のない通常のＬＣＳを用いた場合と比較することで、区切り文字列入りＬＣＳを用いた場合の効果について説明する。図５は、通常のＬＣＳを用いた場合について説明する図である。図６は、区切り文字入りＬＣＳを用いた場合について説明する図である。図５および図６では、ＡＢ１２ＣＤ，ＡＢＣＤ，ＡＢｘＣＥ，ＡＢｙＣｄＥから、連続する最長の共通部分列を抽出する場合を例示している。
【００４２】
図５に示すように、区切り文字列のない通常のＬＣＳを用いた場合には、４つの文字列のＬＣＳを算出後、元の文字列全てと比較し直さないと、連続する最長の共通部分列“ＡＢ”が分からない。これに対して、図６に示すように、区切り文字入りＬＣＳを用いた場合には、４つの文字列のＬＣＳを算出した時点で、もとの文字列でどこが連続していたかが分かるため、すぐに連続する最長の共通部分列“ＡＢ”が得られる。このため、区切り文字入りＬＣＳを用いた場合には、共通部分列を効率よく抽出することができる。
【００４３】
［攻撃パターン抽出装置の処理の一例］
次に、図７および図８を用いて、攻撃パターン抽出装置１０における処理の流れを説明する。図７は、第一の実施の形態に係る攻撃パターン抽出装置におけるクラスタリング処理の流れを示すフローチャートである。図８は、第一の実施の形態に係る攻撃パターン抽出装置におけるＬＣＳ算出処理の流れを示すフローチャートである。
【００４４】
まず、図７を用いて、攻撃パターン抽出装置１０におけるクラスタリング処理の流れを説明する。図７に示すように、攻撃パターン抽出装置１０の抽出部１３ａは、クラスタ集合Ｃを初期化する（ステップＳ１０１）。そして、抽出部１３ａは、クラスタ集合Ｃのサイズが２以上であるか否かを判定する（ステップＳ１０２）。
【００４５】
この結果、抽出部１３ａは、クラスタ集合のサイズが２以上であると判定した場合には（ステップＳ１０２肯定）、処理対象クラスタ抽出処理を行う（ステップＳ１０３）。具体的には、抽出部１３ａは、クラスタ集合Ｃから処理対象クラスタ（例えば最後の要素）を１つ抽出し、Ｃｔとする。クラスタ集合ＣをＣ＼｛Ｃｔ｝で更新する。ここで“＼”は差集合を表す。すなわち、クラスタ集合Ｃから要素Ｃｔを取り除いたものでＣを更新する。
【００４６】
そして、抽出部１３ａは、処理対象クラスタと他クラスタのＬＣＳ算出を行う（ステップＳ１０４）。具体的には、抽出部１３ａは、クラスタ集合Ｃの各要素Ｃｉ（１≦ｉ≦｜Ｃ｜）のｌｃｓ要素と、Ｃｔのｌｃｓ要素とのＬＣＳ（最長共通部分列）を順次算出する。ＣｔとのＬＣＳの一致部分文字列長が最長となるＣｉをＣｋとする。
【００４７】
そして、抽出部１３ａは、最長一致部分文字列長が最小文字列長閾値以上かを判定する（ステップＳ１０５）。この結果、抽出部１３ａは、最長一致部分文字列長が最小文字列長閾値以上であると判定した場合には（ステップＳ１０５肯定）、クラスタのマージを行って（ステップＳ１０６）、ステップＳ１０２の処理に戻る。具体的には、抽出部１３ａは、ＣｋとＣｔを以下の通りマージしてＣＮを作成する。ＣＮのｌｃｓ：ＣｋのｌｃｓとＣｔのｌｃｓの区切り文字入りＬＣＳ、ＣＮのｓｔｒｉｎｇｓ：ＣｋのｓｔｒｉｎｇｓとＣｔのｓｔｒｉｎｇｓを配列として連結する。
【００４８】
また、抽出部１３ａは、最長一致部分文字列長が最小文字列長閾値未満であると判定した場合には（ステップＳ１０５否定）、処理対象クラスタＣｔを結果リストＲに追加し（ステップＳ１０７）、ステップＳ１０２の処理に戻る。
【００４９】
また、ステップＳ１０２において、抽出部１３ａは、クラスタ集合のサイズが１であると判定した場合には（ステップＳ１０２否定）、最後のクラスタを結果リストに追加する（ステップＳ１０８）。そして、攻撃パターン生成部１３ｂは、クラスタサイズが閾値以上のものを抽出する（ステップＳ１０９）。具体的には、攻撃パターン生成部１３ｂは、結果リストＲ＝［Ｃ’１，Ｃ’２，・・・，Ｃ’ｍ］の各要素について、ｓｔｒｉｎｇｓ要素の個数が最小クラスタサイズ閾値以上であるものを抽出する。抽出した要素のｌｃｓ要素が、抽出したい共通部分である。攻撃パターン生成部１３ｂは、共通部分を区切り文字で分割し、最小文字列長閾値以上の長さの文字列を“＊”で連結した正規表現が、最終的に求める攻撃パターンとなる。
【００５０】
次に、図８を用いて、攻撃パターン抽出装置１０におけるＬＣＳ算出処理の流れを説明する。図８に例示するように、抽出部１３ａは、ＬＣＳ算出対象の２つの文字列ｘ，ｙを入力として受け取る（ステップＳ２０１）。そして、抽出部１３ａは、テーブル初期化処理を行う（ステップＳ２０２）。例えば、抽出部１３ａは、（ｌｅｎ（ｙ）＋１）×（ｌｅｎ（ｘ）＋１）のテーブル（配列）ｔを用意し、０行目、０列目の全ての要素を０で初期化する。
【００５１】
そして、抽出部１３ａは、ｉ＝１，２，・・・，ｌｅｎ（ｙ）、ｊ＝１，２，・・・，ｌｅｎ（ｘ）として、ステップＳ２０３〜ステップＳ２０９のテーブルを更新する処理を繰り返す。ステップＳ２０５において、抽出部１３ａは、ｘ［ｊ］＝ｙ［ｉ］であるか判定し（ステップＳ２０５）、ｘ［ｊ］＝ｙ［ｉ］の場合には（ステップＳ２０５肯定）、ｔ［ｉ］［ｊ］＝ｔ［ｉ−１］［ｊ−１］＋１と更新し（ステップＳ２０７）、ｘ［ｊ］＝ｙ［ｉ］以外の場合には（ステップＳ２０５否定）、ｔ［ｉ］［ｊ］＝ｍａｘ（ｔ［ｉ−１］［ｊ］,ｔ［ｉ］［ｊ−１］）と更新する（ステップＳ２０６）。
【００５２】
続いて、抽出部１３ａは、結果文字列を空文字列“”で初期化する（ステップＳ２１０）。そして、抽出部１３ａは、ｉ＞０かつｊ＞０の間、ステップＳ２１１〜Ｓ２１９の処理を繰り返す。ステップＳ２１２において、抽出部１３ａは、ｘ［ｊ］＝ｙ［ｉ］であるか否かを判定する（ステップＳ２１２）。この結果、抽出部１３ａは、ｘ［ｊ］＝ｙ［ｉ］の場合には（ステップＳ２１２肯定）、結果文字列にｘ［ｊ］を追記し（ステップＳ２１７）、ｉ，ｊをともに１減ずる（ステップＳ２１８）。
【００５３】
また、抽出部１３ａは、ｘ［ｊ］＝ｙ［ｉ］以外の場合には（ステップＳ２１２否定）、ｔ［ｉ−１］［ｊ］＞ｔ［ｉ］［ｊ−１］であるか判定する（ステップＳ２１３）。この結果、抽出部１３ａは、ｔ［ｉ−１］［ｊ］＞ｔ［ｉ］［ｊ−１］である場合には（ステップＳ２１３肯定）、ｉを１減じ（ステップＳ２１４）ｔ［ｉ−１］［ｊ］＞ｔ［ｉ］［ｊ−１］でない場合には（ステップＳ２１３否定）、ｊを１減ずる（ステップＳ２１５）。そして、抽出部１３ａは、結果文字列の末尾が区切り文字でなければ区切り文字を追記する（ステップＳ２１６）。
【００５４】
その後、抽出部１３ａは、結果文字列を反転する（ステップＳ２２０）。例えば、抽出部１３ａは、結果文字列が“｜Ｃ｜Ｂ”である場合には、結果文字列を“Ｂ｜Ｃ｜”に反転させる。
【００５５】
［第一の実施の形態の効果］
このように、第一の実施の形態に係る攻撃パターン抽出装置１０は、攻撃と判定された通信のアクセスログにおけるパラメータ同士の共通した文字列を抽出する。そして、攻撃パターン抽出装置１０は、抽出された連続する文字列のうち、文字列長が所定の文字列長以上の文字列を基に攻撃パターンを生成する。このため、第一の実施の形態に係る攻撃パターン抽出装置１０は、適切な攻撃パターンを生成することが可能である。
【００５６】
また、攻撃パターン抽出装置１０は、ＬＣＳを算出する際、文字が連続しない箇所に区切り文字を入れながら算出し、閾値以上の長さのものを抽出するため、極端に短い共通部分を攻撃パターンとして抽出せずに、適切な攻撃パターンを生成することが可能である。
【００５７】
また、攻撃パターン抽出装置１０は、クラスタをマージする際、区切り文字を入れたままでＬＣＳを算出するため、「共通部が連続している」という情報を失うことなく、３つ以上のパラメータから共通部を効率よく抽出することが可能である。
【００５８】
［第二の実施の形態］
上述した第一の実施の形態では、ＣｋとＣｔのスコアｓ（Ｃｋ,Ｃｔ）（最大スコア）が最小文字列長閾値以上である場合に、クラスタをマージすることを説明したが、クラスタをマージする際、共通部の長さが極端に短くなる（スコアが大きく下がる）場合は、マージを抑制することで、攻撃パターンとして残すべき文字列長の長い共通部分が失われることを防ぐようにしてもよい。
【００５９】
そこで、以下の第二の実施の形態では、クラスタをマージする際、共通部の長さが極端に短くなる（スコアが大きく下がる）場合は、マージを抑制する場合について説明する。なお、第一の実施の形態と同様の構成や処理については説明を省略する。
【００６０】
第二の実施の形態に係る攻撃パターン抽出装置の抽出部１３ａは、共通した文字列の長さが、所定の比率以下に低下する場合は、当該文字列からの共通した文字列の抽出を抑制する。具体的には、抽出部１３ａは、最大スコア確認処理において、ＣｋとＣｔのスコアｓ（Ｃｋ,Ｃｔ）（最大スコア）が最小文字列長閾値以上の場合、マージする前に、Ｃｔのｓｔｒｉｎｇｓの要素数が最小クラスタサイズ閾値以上であり、かつマージ後のスコア低下率がスコア低下率閾値以上となる場合、マージは行わず、Ｃｔを結果リストＲに追加し、処理対象クラスタ抽出処理に戻る。ここで、スコア低下率はＣｔのｌｃｓ要素を区切り文字で分割した文字列の最長文字列長Ｌとスコアｓ（Ｃｋ,Ｃｔ）を比較して算出する。例えば、１−ｓ（Ｃｋ,Ｃｔ）／Ｌをスコア低下率とする。
【００６１】
このため、第二の実施の形態では、既に十分な量のパラメータから十分に長い共通部が得られている場合に、さらにマージを行うことで得られる共通部が短くなってしまうことを防ぐことができる。
【００６２】
例えば、第一の実施の形態では、｛ｌｃｓ：“ＰＡＴＴＥＲＮ”,ｓｔｒｉｎｇｓ：［“ＰＡＴＴＥＲＮ１”,“ＰＡＴＴＥＲＮ２”,“ＰＡＴＴＥＲＮ３”］｝というクラスタが得られている場合に、“ＴＥＲＮ”というパラメータからなるクラスタもマージされて、｛ｌｃｓ：“ＴＥＲＮ”，ｓｔｒｉｎｇｓ：［“ＰＡＴＴＥＲＮ１”，“ＰＡＴＴＥＲＮ２”，“ＰＡＴＴＥＲＮ３”，“ＴＥＲＮ”］｝というクラスタが生成されてしまう。ここで、最小文字列長閾値は「４」とする。
【００６３】
攻撃パターンとしては、できるだけ長い共通部分を抽出したいので、この場合はマージせずに“ＰＡＴＴＥＲＮ”という共通部が得られた時点で、マージを終了してクラスタを確定させたほうが良い。これに対して、第二の実施の形態では、“ＰＡＴＴＥＲＮ”が“ＴＥＲＮ”になるとスコアが大きく低下するので、マージを抑制して、所望の共通部を得ることができる。
【００６４】
［第二の実施の形態の効果］
このように、第二の実施の形態では、クラスタをマージする際、共通部の長さが極端に短くなる場合は、マージを抑制することで、攻撃パターンとして残すべき文字列長の長い共通部分が失われることを防ぐことが可能である。
【００６５】
［システム構成等］
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。例えば、抽出部１３ａと攻撃パターン生成部１３ｂとを統合してもよい。
【００６６】
また、本実施の形態において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともでき、あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００６７】
［プログラム］
また、上記実施形態において説明した攻撃パターン抽出装置が実行する処理をコンピュータが実行可能な言語で記述したプログラムを作成することもできる。例えば、実施形態に係る攻撃パターン抽出装置１０が実行する処理をコンピュータが実行可能な言語で記述した攻撃パターン抽出プログラムを作成することもできる。この場合、コンピュータが攻撃パターン抽出プログラムを実行することにより、上記実施形態と同様の効果を得ることができる。さらに、かかる攻撃パターン抽出プログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録された攻撃パターン抽出プログラムをコンピュータに読み込ませて実行することにより上記実施形態と同様の処理を実現してもよい。
【００６８】
図９は、攻撃パターン抽出プログラムを実行するコンピュータ１０００を示す図である。図９に例示するように、コンピュータ１０００は、例えば、メモリ１０１０と、ＣＰＵ１０２０と、ハードディスクドライブインタフェース１０３０と、ディスクドライブインタフェース１０４０と、シリアルポートインタフェース１０５０と、ビデオアダプタ１０６０と、ネットワークインタフェース１０７０とを有し、これらの各部はバス１０８０によって接続される。
【００６９】
メモリ１０１０は、図９に例示するように、ＲＯＭ（Read  Only  Memory）１０１１及びＲＡＭ１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、図９に例示するように、ハードディスクドライブ１０９０に接続される。ディスクドライブインタフェース１０４０は、図９に例示するように、ディスクドライブ１１００に接続される。例えば磁気ディスクや光ディスク等の着脱可能な記憶媒体が、ディスクドライブ１１００に挿入される。シリアルポートインタフェース１０５０は、図９に例示するように、例えばマウス１１１０、キーボード１１２０に接続される。ビデオアダプタ１０６０は、図９に例示するように、例えばディスプレイ１１３０に接続される。
【００７０】
ここで、図９に例示するように、ハードディスクドライブ１０９０は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、上記の攻撃パターン抽出プログラムは、コンピュータ１０００によって実行される指令が記述されたプログラムモジュールとして、例えばハードディスクドライブ１０９０に記憶される。
【００７１】
また、上記実施形態で説明した各種データは、プログラムデータとして、例えばメモリ１０１０やハードディスクドライブ１０９０に記憶される。そして、ＣＰＵ１０２０が、メモリ１０１０やハードディスクドライブ１０９０に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出し、各種処理手順を実行する。
【００７２】
なお、攻撃パターン抽出プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０９０に記憶される場合に限られず、例えば着脱可能な記憶媒体に記憶され、ディスクドライブ等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、攻撃パターン抽出プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ネットワーク（ＬＡＮ（Local  Area  Network）、ＷＡＮ（Wide  Area  Network）等）を介して接続された他のコンピュータに記憶され、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【符号の説明】
【００７３】
１０  攻撃パターン抽出装置
１１  入力部
１２  出力部
１３  制御部
１３ａ  抽出部
１３ｂ  攻撃パターン生成部
１４  記憶部
１４ａ  ログ記憶部
【図１】
0006714142.tif 000002
【図２】
0006714142.tif 000003
【図３】
0006714142.tif 000004
【図４】
0006714142.tif 000005
【図５】
0006714142.tif 000006
【図６】
0006714142.tif 000007
【図７】
0006714142.tif 000008
【図８】
0006714142.tif 000009
【図９】
0006714142.tif 000010