(57)【要約】      （修正有）【課題】ファイル全体のエントロピー値が近い値となった場合に、より詳細な類似度評価を機械的に行う。【解決手段】利用者端末２１〜２Ｎは、比較元ファイルと比較先ファイルとを類似度評価装置３へ送信する。類似度評価装置３は、比較元ファイルと比較先ファイルそれぞれを所定の分割方法で複数の区間に分割し、比較元分割ファイルと比較先分割ファイルそれぞれから区間ごとに所定のエントロピー値を算出し、比較元区間特徴量と比較先区間特徴量とに基づいて比較元ファイルと比較先ファイルとが類似するか否かを示す判定結果を求める。利用者端末２１〜２Ｎは、類似度評価装置３から受信した判定結果を表示する。【選択図】図１
2014085854.tif 000002
【特許請求の範囲】
【請求項１】
利用者端末と類似度評価装置とを含み、比較元ファイルと比較先ファイルとが類似するか否かを判定する類似度評価システムであって、
前記利用者端末は、
前記比較元ファイルと前記比較先ファイルとを前記類似度評価装置へ送信する投入部と、
前記類似度評価装置から受信した、前記比較元ファイルと前記比較先ファイルとが類似するか否かを示す判定結果を表示する表示部と、
を含み、
前記類似度評価装置は、
前記比較元ファイルと前記比較先ファイルそれぞれを所定の分割方法で複数の区間に分割し、比較元分割ファイルと比較先分割ファイルを生成する区間分割部と、
前記比較元分割ファイルと前記比較先分割ファイルそれぞれから区間ごとに所定のエントロピー値を算出し、比較元区間特徴量と比較先区間特徴量を生成する区間特徴量算出部と、
前記比較元区間特徴量と前記比較先区間特徴量とに基づいて前記判定結果を求める区間類似度評価部と、
を含む
ことを特徴とする類似度評価システム。
【請求項２】
利用者端末と類似度評価装置とを含み、比較元ファイルと比較先ファイルとが類似するか否かを判定する類似度評価システムであって、
前記利用者端末は、
前記比較元ファイルと前記比較先ファイルそれぞれを所定の分割方法で複数の区間に分割し、比較元分割ファイルと比較先分割ファイルを生成する区間分割部と、
前記比較元分割ファイルと前記比較先分割ファイルそれぞれから区間ごとに所定のエントロピー値を算出し、比較元区間特徴量と比較先区間特徴量を生成する区間特徴量算出部と、
前記比較元区間特徴量と前記比較先区間特徴量とを前記類似度評価装置へ送信する投入部と、
前記類似度評価装置から受信した、前記比較元ファイルと前記比較先ファイルとが類似するか否かを示す判定結果を表示する表示部と、
を含み、
前記類似度評価装置は、
前記比較元区間特徴量と前記比較先区間特徴量とに基づいて前記判定結果を求める区間類似度評価部と、
を含む
ことを特徴とする類似度評価システム。
【請求項３】
請求項１に記載の類似度評価システムであって、
前記類似度評価装置は、
前記比較元ファイルと前記比較先ファイルそれぞれのファイル全体から前記エントロピー値を算出し、比較元全体特徴量と比較先全体特徴量を生成する全体特徴量算出部と、
前記比較元全体特徴量と前記比較先全体特徴量とに基づいて前記比較元ファイルと前記比較先ファイルとが類似するか否かを示す暫定判定結果を求める全体類似度評価部と、
を含み、
前記暫定判定結果が前記比較元ファイルと前記比較先ファイルとが類似することを示す場合には、前記区間分割部と前記区間特徴量算出部と前記区間類似度評価部とを実行する
ことを特徴とする類似度評価システム。
【請求項４】
請求項２に記載の類似度評価システムであって、
前記利用者端末は、
前記比較元ファイルと前記比較先ファイルそれぞれのファイル全体から前記エントロピー値を算出し、比較元全体特徴量と比較先全体特徴量を生成する全体特徴量算出部と、
を含み、
前記類似度評価装置は、
前記比較元全体特徴量と前記比較先全体特徴量とに基づいて前記比較元ファイルと前記比較先ファイルとが類似するか否かを示す暫定判定結果を求める全体類似度評価部と、
を含み、
前記暫定判定結果が前記比較元ファイルと前記比較先ファイルとが類似することを示す場合には、前記区間類似度評価部を実行する
ことを特徴とする類似度評価システム。
【請求項５】
比較元ファイルと比較先ファイルそれぞれを所定の分割方法で複数の区間に分割し、比較元分割ファイルと比較先分割ファイルを生成する区間分割部と、
前記比較元分割ファイルと前記比較先分割ファイルそれぞれから区間ごとに所定のエントロピー値を算出し、比較元区間特徴量と比較先区間特徴量を生成する区間特徴量算出部と、
前記比較元区間特徴量と前記比較先区間特徴量とに基づいて、前記比較元ファイルと前記比較先ファイルとが類似するか否かを示す判定結果を求める区間類似度評価部と、
を含む類似度評価装置。
【請求項６】
比較元ファイルと比較先ファイルとを類似度評価装置へ送信する投入部と、
前記類似度評価装置から受信した、前記比較元ファイルと前記比較先ファイルとが類似するか否かを示す判定結果を表示する表示部と、
を含む利用者端末。
【請求項７】
比較元ファイルを所定の分割方法で複数の区間に分割して区間ごとに所定のエントロピー値を算出した比較元区間特徴量と、比較先ファイルを前記分割方法で複数の区間に分割して区間ごとに前記エントロピー値を算出した比較先区間特徴量と、に基づいて、前記比較元ファイルと前記比較先ファイルとが類似するか否かを示す判定結果を求める区間類似度評価部
を含む類似度評価装置。
【請求項８】
比較元ファイルと比較先ファイルそれぞれを所定の分割方法で複数の区間に分割し、比較元分割ファイルと比較先分割ファイルを生成する区間分割部と、
前記比較元分割ファイルと前記比較先分割ファイルそれぞれから区間ごとに所定のエントロピー値を算出し、比較元区間特徴量と比較先区間特徴量を生成する区間特徴量算出部と、
前記比較元区間特徴量と前記比較先区間特徴量とを類似度評価装置へ送信する投入部と、
前記類似度評価装置から受信した、前記比較元ファイルと前記比較先ファイルとが類似するか否かを示す判定結果を表示する表示部と、
を含む利用者端末。
【請求項９】
比較元ファイルと比較先ファイルとが類似するか否かを判定する類似度評価方法であって、
利用者端末が、前記比較元ファイルと前記比較先ファイルとを類似度評価装置へ送信する投入ステップと、
前記類似度評価装置が、前記比較元ファイルと前記比較先ファイルそれぞれを所定の分割方法で複数の区間に分割し、比較元分割ファイルと比較先分割ファイルを生成する区間分割ステップと、
前記類似度評価装置が、前記比較元分割ファイルと前記比較先分割ファイルそれぞれから区間ごとに所定のエントロピー値を算出し、比較元区間特徴量と比較先区間特徴量を生成する区間特徴量算出ステップと、
前記類似度評価装置が、前記比較元区間特徴量と前記比較先区間特徴量とに基づいて前記比較元ファイルと前記比較先ファイルとが類似するか否かを示す判定結果を求める区間類似度評価部ステップ、
前記利用者端末が、前記類似度評価装置から受信した前記判定結果を表示する表示ステップと、
を含むことを特徴とする類似度評価方法。
【請求項１０】
比較元ファイルと比較先ファイルとが類似するか否かを判定する類似度評価方法であって、
利用者端末が、前記比較元ファイルと前記比較先ファイルそれぞれを所定の分割方法で複数の区間に分割し、比較元分割ファイルと比較先分割ファイルを生成する区間分割ステップと、
前記利用者端末が、前記比較元分割ファイルと前記比較先分割ファイルそれぞれから区間ごとに所定のエントロピー値を算出し、比較元区間特徴量と比較先区間特徴量を生成する区間特徴量算出ステップと、
前記利用者端末が、前記比較元区間特徴量と前記比較先区間特徴量とを類似度評価装置へ送信する投入ステップと、
前記類似度評価装置が、前記比較元区間特徴量と前記比較先区間特徴量とに基づいて、前記比較元ファイルと前記比較先ファイルとが類似するか否かを示す判定結果を求める区間類似度評価ステップと、
前記利用者端末が、前記類似度評価装置から受信した前記判定結果を表示する表示ステップと、
を含むことを特徴とする類似度評価方法。
【請求項１１】
請求項５または７に記載の類似度評価装置もしくは請求項６または８に記載の利用者端末としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、エントロピー値を用いてファイルの類似度を評価する類似度評価技術に関する。
【背景技術】
【０００２】
マルウェアの検出やＤＬＰ(Data Loss Prevention)の分野で、ファイルの類似度を測定する方法として、エントロピー値を求めることが行われている。エントロピー値の計算は順序性を考慮しない場合には式（１）により行われる。順序性を考慮する場合には式（２）により行われる。以下、順序性を考慮したエントロピー値は、M1エントロピーと呼ぶ。式（１）および（２）において、Piは対象ファイルの中で値がiとなる確率である。
【０００３】
【数１】
2014085854.tif 000003
【０００４】
データの状態をエントロピー値で表現することにより、記憶装置に存在する大量の情報を分類したり、特定データ間での近似を検証したりするのに役立つ。特に、原本データに対して意図的に変更を加えて検知を逃れるタイプのマルウェアやアンチフォレンジック手法が存在するため、原本ファイルとの近似を客観的かつ定量的に表現することは、フォレンジック調査にとって意義が大きい。
【０００５】
エントロピー値はデータの状態を表現しており、対象データの一部を変更した場合、原本データからのエントロピー値の変化量には相関関係が存在する。これに対して、フォレンジック分野でデータの識別に用いられるいわゆるハッシュ関数を使用した方法では、データとハッシュ値の変化量に相関関係が存在しないため、原本ファイルにどの程度の変更が加わったかに関して客観的な判断を加えることはできない。この性質は、計算されたハッシュ値への攻撃に対して頑強であるという点においてハッシュ関数の長所でもあるが、ファイルの近似の検証という点においては、エントロピー値の方が有利である。また、エントロピー値の計算は、ハッシュ計算と比べて計算コストが低くてすむため、大量のデータをすばやく検証するのにもエントロピー値を用いた類似度評価の方が向いている。
【０００６】
エントロピー値を用いた類似度評価をより正確に行うため、エントロピー値にファイルサイズで重みを付ける方法が提案されている（例えば、非特許文献１参照）。重み付きエントロピー値は式（３）により計算される。
【０００７】
【数２】
2014085854.tif 000004
【０００８】
重み付きエントロピー値を用いた類似度は、E1を比較元ファイルの重み付きエントロピー値とし、E2を比較先ファイルの重み付きエントロピー値とし、S1を比較元ファイルのファイルサイズとし、S2を比較先ファイルのファイルサイズとして、式（４）により計算される。
【０００９】
【数３】
2014085854.tif 000005
【００１０】
式（４）は計算例であり通常のファイルに適用した場合、有意な値を取らない。このため例えば、式（５）のように類似度を計算することもある。
【００１１】
【数４】
2014085854.tif 000006
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】Guidance Software, “Utilizing Entropy to Identify Undetected Malware”, [online], [平成24年10月15日検索], インターネット<URL:http://www.guidancesoftware.com/DocumentRegistration.aspx?did=1000017288>
【発明の概要】
【発明が解決しようとする課題】
【００１３】
エントロピー値はデータのランダム状態を表現するに過ぎないため、エントロピー値もしくは重み付きエントロピー値を計算しても、偶然的に内容が全く異なるデータが近いエントロピー値をもつことがあり得る。従来はデータの目視確認により補足的な類似度評価を行なっていたが、比較対象のファイルが多い場合には、このようなファイルの目視による類似度評価は困難になる。したがって、近いエントロピー値をとるファイル間の類似度をさらに評価する他の評価手段が必要とされていた。
【００１４】
この発明はこのような点に鑑みてなされたものであり、ファイル全体のエントロピー値が近い値となった場合に、より詳細な類似度評価を機械的に行うことができる類似度評価技術を提供することを目的とする。
【課題を解決するための手段】
【００１５】
上記の課題を解決するために、この発明の一態様による類似度評価システムは、利用者端末と類似度評価装置とを含み、比較元ファイルと比較先ファイルとが類似するか否かを判定する。利用者端末は、比較元ファイルと比較先ファイルとを類似度評価装置へ送信する投入部と、類似度評価装置から受信した、比較元ファイルと比較先ファイルとが類似するか否かを示す判定結果を表示する表示部と、を含む。類似度評価装置は、比較元ファイルと比較先ファイルそれぞれを所定の分割方法で複数の区間に分割し、比較元分割ファイルと比較先分割ファイルを生成する区間分割部と、比較元分割ファイルと比較先分割ファイルそれぞれから区間ごとに所定のエントロピー値を算出し、比較元区間特徴量と比較先区間特徴量を生成する区間特徴量算出部と、比較元区間特徴量と比較先区間特徴量とに基づいて判定結果を求める区間類似度評価部と、を含む。
【００１６】
この発明の他の態様による類似度評価システムは、利用者端末と類似度評価装置とを含み、比較元ファイルと比較先ファイルとが類似するか否かを判定する。利用者端末は、比較元ファイルと比較先ファイルそれぞれを所定の分割方法で複数の区間に分割し、比較元分割ファイルと比較先分割ファイルを生成する区間分割部と、比較元分割ファイルと比較先分割ファイルそれぞれから区間ごとに所定のエントロピー値を算出し、比較元区間特徴量と比較先区間特徴量を生成する区間特徴量算出部と、比較元区間特徴量と比較先区間特徴量とを類似度評価装置へ送信する投入部と、類似度評価装置から受信した、比較元ファイルと比較先ファイルとが類似するか否かを示す判定結果を表示する表示部と、を含む。類似度評価装置は、比較元区間特徴量と比較先区間特徴量とに基づいて判定結果を求める区間類似度評価部を含む。
【発明の効果】
【００１７】
この発明の類似度評価技術によれば、比較対象ファイルを複数の区間に分割し、区間ごとのエントロピー値に基づいてファイルの類似度を評価するため、ファイル全体のエントロピー値が近い値となる場合であっても、より詳細な類似度評価を機械的に行うことができる。これにより、２つのファイルの類似度評価の精度が向上する。
【図面の簡単な説明】
【００１８】
【図１】第一実施形態に係る類似度評価システムの機能構成を例示する図である。
【図２】（Ａ）利用者端末の機能構成を例示する図である。（Ｂ）類似度評価装置の機能構成を例示する図である。
【図３】類似度評価方法の処理フローを例示する図である。
【図４】全体特徴量の算出結果を例示する図である。
【図５】全体類似度の評価結果を例示する図である。
【図６】ローリングハッシュの処理フローを例示する図である。
【図７】区間特徴量の算出結果を例示する図である。
【図８】区間類似度の評価結果を例示する図である。
【図９】第二実施形態に係る類似度評価システムの機能構成を例示する図である。
【図１０】（Ａ）利用者端末の機能構成を例示する図である。（Ｂ）類似度評価装置の機能構成を例示する図である。
【図１１】類似度評価方法の処理フローを例示する図である。
【図１２】類似度評価方法の処理フローを例示する図である。
【発明を実施するための形態】
【００１９】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００２０】
［第一実施形態］
＜構成＞
図１を参照して、この実施形態の類似度評価システム１の構成例を説明する。類似度評価システム１は、N(≧1)台の利用者端末２1，…，２Nと類似度評価装置３を含む。N台の利用者端末２1，…，２Nと類似度評価装置３はネットワーク４に接続される。ネットワーク４は、接続される各装置が相互に通信可能なように構成されていればよく、例えばインターネットやＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）などで構成することができる。なお、各装置は必ずしもネットワークを介してオンラインで通信可能である必要はない。例えば、利用者端末２n(1≦n≦N)の出力する情報を磁気テープやＵＳＢメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体からオフラインで類似度評価装置３へ入力するように構成してもよい。
【００２１】
図２（Ａ）を参照して、類似度評価システム１に含まれる利用者端末２nの構成例を説明する。利用者端末２nは、制御部２０１、メモリ２０２、ファイル記憶部２１、投入部２２、表示部２３を備える。利用者端末２nは、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。利用者端末２nは制御部２０１の制御のもとで各処理を実行する。利用者端末２nに入力されたデータや各処理で得られたデータはメモリ２０２に格納され、メモリ２０２に格納されたデータは必要に応じて読み出されて他の処理に利用される。ファイル記憶部２１は、例えば、ＲＡＭ（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリなどの半導体メモリ素子により構成される補助記憶装置、などにより構成することができる。
【００２２】
図２（Ｂ）を参照して、類似度評価システム１に含まれる類似度評価装置３の構成例を説明する。類似度評価装置３は、制御部３０１、メモリ３０２、入力部３１、全体特徴量算出部３２、全体類似度評価部３３、区間分割部３４、区間特徴量算出部３５、区間類似度評価部３６、出力部３７、特徴量記憶部３８を備える。類似度評価装置３は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。類似度評価装置３は制御部３０１の制御のもとで各処理を実行する。類似度評価装置３に入力されたデータや各処理で得られたデータはメモリ３０２に格納され、メモリ３０２に格納されたデータは必要に応じて読み出されて他の処理に利用される。特徴量記憶部３８は、例えば、ＲＡＭ（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリなどの半導体メモリ素子により構成される補助記憶装置、リレーショナルデータベースやキーバリューストアなどのミドルウェア、などにより構成することができる。
【００２３】
＜処理＞
図３を参照して、この実施形態の類似度評価システム１の動作例を説明する。
【００２４】
利用者端末２n(1≦n≦N)の備えるファイル記憶部２１には類似度を評価する少なくとも２つのファイルが記憶されている。
【００２５】
利用者端末２nの備える投入部２２は、利用者の操作に従って、ファイル記憶部２１に記憶されているファイルから選択した、類似度を評価する比較対象ファイル群を類似度評価装置３へ送信する。比較対象ファイル群に含まれるファイルの数は２つであってもよいし、３つ以上であってもよい。以降の説明では、２つのファイルの類似度を評価する場合について説明し、３つ以上の場合に相違する点があれば適宜説明する。また、比較対象の２つのファイルは、それぞれ比較元ファイル、比較先ファイルと呼ぶ。
【００２６】
利用者端末２nが送信した比較対象ファイル群は、入力部３１を介して類似度評価装置３へ入力される（ステップＳ３１）。類似度評価装置３の備える全体特徴量算出部３２は、比較元ファイルと比較先ファイルそれぞれから所定のエントロピー値を算出する（ステップＳ３２）。比較元ファイルから算出したエントロピー値は比較元全体特徴量、比較先ファイルから算出したエントロピー値は比較先全体特徴量と呼ぶ。算出するエントロピー値は、様々な種類のエントロピー値を適用することができる。例えば、上記の式（１）で算出されるエントロピー値でもよい。上記の式（２）で算出されるM1エントロピー値でもよい。上記の式（３）で算出されるファイルサイズ重み付きエントロピー値でもよい。また例えば、N-gramエントロピーを算出してもよい。N-gramエントロピーとは、決められたバイト数(Nバイト)の単位でファイル中における各ビットパターンの出現数から算出するエントロピー値である。比較対象ファイル群が３つ以上のファイルを含む場合には、すべての２つのファイルの組み合わせについて、所定のエントロピー値を算出すればよい。
【００２７】
図４にファイル全体の特徴量の算出結果の例を示す。「File Name」列は比較対象ファイルの物理的なファイル名である。「No.」列は比較対象ファイルを一意に識別する数値である。「Entropy」列は比較対象ファイルから式（１）で算出したエントロピー値である。「M1Entropy」列は比較対象ファイルから式（２）で算出したM1エントロピー値である。「WEntropy」列は比較対象ファイルから式（３）で算出したファイルサイズ重み付きエントロピー値である。「File size」列は比較対象ファイルのバイト単位のファイルサイズである。この例では、15個の比較対象ファイルが投入されている。例えば、No.1のae.bmpは、エントロピー値が7.36303であり、M1エントロピー値が4.758377であり、ファイルサイズ重み付きエントロピー値が87.8226であり、ファイルサイズが151,374バイトであることを表している。
【００２８】
算出された比較元全体特徴量および比較先全体特徴量は特徴量記憶部３８に記憶される。全体類似度評価部３３は特徴量記憶部３８から読み出した比較元全体特徴量と比較先全体特徴量から全体類似度を算出する（ステップＳ３３１）。全体類似度の算出は、例えば上記の式（５）により計算することができる。比較対象ファイル群が３つ以上のファイルを含む場合には、すべての２つのファイルの組み合わせについて、全体類似度を算出すればよい。
【００２９】
全体類似度評価部３３は算出した全体類似度をあらかじめ定めた閾値と比較し、比較元ファイルと比較先ファイルが類似するか否かを示す暫定判定結果を求める。暫定判定結果には、全体類似度が閾値以上である場合にはファイルが類似することを示す値を設定し、全体類似度が閾値未満の場合にはファイルが類似しないことを示す値を設定する（ステップＳ３３２）。比較対象ファイル群が３つ以上のファイルを含む場合には、全体類似度が閾値以上であるファイルの組み合わせが存在する場合に類似するファイルが存在することを示す値を設定し、全体類似度が閾値以上であるファイルの組み合わせが存在しない場合に類似するファイルが存在しないことを示す値を設定すればよい。
【００３０】
図５にファイル全体の類似度の評価結果の例を示す。「File Name」列は比較対象ファイルの物理的なファイル名である。「No.」列は比較元ファイルを一意に識別する数値である。「1」〜「15」列は比較先ファイルを示している。つまり、図５は比較元ファイルと比較先ファイルの全体類似度のマトリックスとなっている。例えば、No.1のae.bmpとNo.2のaf.bmpとの全体類似度は89である。類似度を判定する閾値を99に設定すると、図５のマトリックス中で値を太字で示したファイルの組み合わせにおいて、ファイルが類似すると判定される。例えば、No.1のae.bmpであれば、No.5のimagesCA6MA9NM.bmpとNo.6のimagesCA83PY61.bmpとNo.8のimagesCAQI7U2A.bmpと類似すると判定される。
【００３１】
暫定判定結果が比較元ファイルと比較先ファイルとが類似しないことを示す場合には、比較元ファイルと比較先ファイルとが類似しないことを示す判定結果を出力し、処理を終了する（ステップＳ３７２）。例えば、図６において、比較対象ファイルとして、No.1のae.bmpとNo.2のaf.bmpが投入された場合であれば、全体類似度が89であり閾値99未満であるため、２つのファイルは類似しないと判定される。この場合には、２つのファイルは類似しないことを出力して処理を終了する。
【００３２】
暫定判定結果が比較元ファイルと比較先ファイルとが類似することを示す場合には、以降の処理を継続する。比較対象ファイル群が３つ以上のファイルを含む場合であって、複数のファイルの組み合わせでファイルが類似すると判定された場合には、類似するファイルの組み合わせすべてについて以降の処理を繰り返し実行する。
【００３３】
比較元ファイルと比較先ファイルが区間分割部３４へ入力される。区間分割部３４は、比較元ファイルと比較先ファイルそれぞれを所定の分割方法で複数の区間に分割する。（ステップＳ３４）。比較元ファイルを分割した後のファイルは比較元分割ファイル、比較先ファイルを分割した後のファイルは比較先分割ファイルと呼ぶ。区間分割の方法は、例えば、あらかじめ定めた固定サイズで分割することができる。例えば、10Kバイトごとに区間を分割すればよい。また例えば、比較対象ファイルのファイルサイズに比例した均等割りにより分割サイズを決定してもよい。ファイルサイズに比例した均等割りであれば、末端の少量サイズの区間が生じることを回避することができる。また例えば、ローリングハッシュにより分割点を決定してもよい。
【００３４】
図６にローリングハッシュによる区間分割の動作例を示す。分割対象のファイルが入力されると、そのファイルのバイナリ列からmバイトを読み取る（ステップＳ３４１）。このmバイト分のバイナリ列をウィンドウと呼ぶ。ウィンドウのサイズを決定するmは任意の値を取ることができる。例えば、m=7などと設定すればよい。次に、読み取ったウィンドウのハッシュ値を計算する（ステップＳ３４２）。ハッシュ関数としては、例えば、文字列を構成する全文字の値を加算する関数、各文字のASCIIコードを全て掛け合わせる関数などが考えられる。続いて、計算したハッシュ値の下位tビットを評価する（ステップＳ３４３）。下位tビットがあらかじめ定めた任意のビットパターンと一致する場合には、そのウィンドウの位置を分割点として記憶する（ステップＳ３４４）。ビットパターンはどのようなものでもよく、例えば、下位tビットがすべて1の場合などでもよいし、すべて0の場合などでもよい。tは、例えば、Lをファイルサイズとし、Nを区間の総数として、下記の式により決定すればよい。
【００３５】
【数５】
2014085854.tif 000007
【００３６】
ここで、
【００３７】
【数６】
2014085854.tif 000008
【００３８】
は床関数であり、xを超えない最大の整数である。
【００３９】
次に、ウィンドウの位置がファイルの終点であるかを確認する（ステップＳ３４５）。ファイルの終点でなければ、ウィンドウの位置を先頭から1バイト後方へ移動させ、ステップＳ３４１からステップＳ３４５の処理を繰り返す。ウィンドウの位置がファイルの終点に至るまで上記の処理を繰り返す。
【００４０】
ローリングハッシュを用いてファイルの区間分割を行うと、比較対象の２つのファイルの相違点を除いて共通の部分を区間として抽出することができる可能性が高い。
【００４１】
比較元分割ファイルと比較先分割ファイルは区間特徴量算出部３５へ入力される。区間特徴量算出部３５は、比較元分割ファイルと比較先分割ファイルそれぞれから区間ごとに所定のエントロピー値を算出する（ステップＳ３５）。比較元分割ファイルの区間ごとのエントロピー値のスペクトルを比較元区間特徴量と呼び、比較先分割ファイルの区間ごとのエントロピー値のスペクトルを比較先区間特徴量と呼ぶ。算出するエントロピー値は、全体特徴量と同様に、様々な種類のエントロピー値を適用することができる。例えば、上記の式（１）で算出されるエントロピー値でもよい。上記の式（２）で算出されるM1エントロピー値でもよい。上記の式（３）で算出されるファイルサイズ重み付きエントロピー値でもよい。また例えば、N-gramエントロピーを算出してもよい。
【００４２】
図７（Ａ）に比較元ファイルの区間特徴量の算出結果の例を示し、図７（Ｂ）に比較先ファイルの区間特徴量の算出結果の例を示す。「File Name」列は区間分割後の比較対象ファイルのファイル名である。「Entropy」列はその分割ファイルから算出したエントロピー値である。「M1Entropy」列はその分割ファイルから算出したM1エントロピー値である。「WEntropy」列はその分割ファイルから算出したファイルサイズ重み付きエントロピー値である。「File Size」列はその分割ファイルのバイト単位のファイルサイズである。この例では、No.1のae.bmpを比較元ファイルとし、No.5のimagesCA6MA9NM.bmpを比較先ファイルとして、それぞれ100,000バイトの固定サイズで分割している。図７（Ａ）では、No.1のae.bmpがae.001〜ae.016の16個に分割され、分割後のae.001〜ae.016それぞれについて、エントロピー値とM1エントロピー値とファイルサイズ重み付きエントロピー値を算出した結果を示している。図７（Ｂ）では、No.5のimagesCA6MA9NM.bmpがIMAGES~1.001〜IMAGES~1.016の16個に分割され、分割後のIMAGES~1.001〜IMAGES~1.016それぞれについて、エントロピー値とM1エントロピー値とファイルサイズ重み付きエントロピー値を算出した結果を示している。
【００４３】
比較元区間特徴量と比較先区間特徴量は区間類似度評価部３６へ入力される。区間類似度評価部３６は、比較元区間特徴量と比較先区間特徴量とに基づいて比較元ファイルと比較先ファイルが類似するか否かを示す判定結果を求める（ステップＳ３６）。判定の方法は、下記の式（６）に示すように、比較元区間特徴量に含まれる区間ごとのエントロピー値と、比較先区間特徴量に含まれる区間ごとのエントロピー値との差をそれぞれ算出し、その平均を計算すればよい。
【００４４】
【数７】
2014085854.tif 000009
【００４５】
ここで、nは区間の総数であり、H1iは比較元ファイルの区間iのエントロピー値であり、H2iは比較先ファイルの区間iのエントロピー値である。
【００４６】
式（６）で求めた差の平均Dがあらかじめ定めた閾値以上であれば、比較元ファイルと比較先ファイルは類似の関係にないと判断する。差の平均により類似するか否かを判定する場合の閾値は、例えば0.25などに設定すればよい。
【００４７】
図８に区間類似度の評価結果の例を示す。図８（Ａ）は比較元区間特徴量と比較先区間特徴量との差の平均を算出した結果である。「区間」列は分割区間の番号を示す数値である。「区間エントロピー値」欄は比較対象ファイルの区間ごとのエントロピー値であり、「No.1」列には比較元ファイルであるNo.1のae.bmpについての区間ごとのエントロピー値が、「No.5」列には比較先ファイルであるNo.5のimagesCA6MA9NM.bmpについての区間ごとのエントロピー値が、それぞれ設定されている。「差」列はNo.1の区間ごとのエントロピー値からNo.5の区間ごとのエントロピー値を減算した値である。例えば、No.1のae.bmpの分割ファイルae.001の区間エントロピー値は7.190017であり、No.5のimagesCA6MA9NM.bmpの分割ファイルIMAGES~1.001の区間エントロピー値は6.508847であり、その差は0.68117であることを表している。図８（Ａ）の最下段の「平均」行は、「差」列の値の平均値、すなわち式（６）における差の平均Dの値である。この例では、差の平均Dが0.472823375であり、上記の例の通り閾値を0.25とすると、No.1のae.bmpとNo.5のimagesCA6MA9NM.bmpは類似の関係にないと判断できる。図８（Ｂ）は比較元区間特徴量と比較先区間特徴量をグラフにプロットした結果である。横軸は区間の番号であり、縦軸は区間エントロピー値の値である。複数の区間で区間エントロピー値が大きく相違していることがわかる。
【００４８】
類似するか否かの判定は、比較元区間特徴量と比較先区間特徴量について各種の統計判定を利用して行なってもよい。統計判定の方法は、例えば、標準偏差により行なってもよい。すなわち、比較元区間特徴量と比較先区間特徴量それぞれの標準偏差を算出し、標準偏差の差が閾値未満であればファイルが類似すると判定する。また例えば、相関係数により判定してもよい。すなわち、比較元区間特徴量と比較先区間特徴量との相関係数を求め、その相関係数が閾値以上であればファイルが類似すると判定する。また例えば、最長一致系列比較により判定を行なってもよい。すなわち、比較元区間特徴量と比較先区間特徴量とで対応する区間エントロピー値が連続して一致する区間の長さを求め、その一致する区間の長さが閾値以上であればファイルが類似すると判定する。また例えば、フーリエ解析により判定を行なってもよい。すなわち、比較元区間特徴量と比較先区間特徴量それぞれをフーリエ変換し、得られたパワースペクトルの系列を比較して一致する要素の数が閾値以上であればファイルが類似すると判定する。また例えば、Χスクエア検定により判定を行なってもよい。すなわち、比較元区間特徴量と比較先区間特徴量をそれぞれ所定の関数に近似させて検定統計量を算出することにより、あらかじめ定めた閾値を有意水準としてファイルが類似するか否かの仮説検定を行う。
【００４９】
判定結果は、類似度評価装置３の備える出力部３７を介して利用者端末２nへ送信される（ステップＳ３７１，Ｓ３７１）。送信する情報は利用者端末２nが表示するために必要な情報である。例えば、比較対象ファイルの全体特徴量、比較対象ファイル間の全体類似度、比較対象ファイルの区間特徴量、比較対象ファイル間の類似度判定結果、および区間エントロピー値の差の平均などの類似度を判定するために算出したすべての値などから任意に選択すればよい。
【００５０】
利用者端末２nの備える表示部２３は、類似度評価装置３から受信した判定結果を表示する。表示の方法はどのような方法であってもよい。例えば、利用者端末２nのディスプレイに整形して表示してもよいし、利用者端末２nに設定された所定のプリンタへあらかじめ定めた書式で出力してもよい。
【００５１】
＜効果＞
従来のエントロピー値を用いた類似度評価技術では、比較対象の２つのファイルの内容が全く異なっているにも関わらず、偶然にファイル全体のエントロピー値が近い値となることがあった。このような場合、従来はデータの目視確認により補足的な類似度評価を行なっていた。
【００５２】
この実施形態の類似度評価システム１は、ファイル全体のエントロピー値が近い値となった場合に、機械的により詳細な類似度評価を行うことができる。したがって、２つのファイルの類似度評価の精度が向上する。なお、この発明の類似度評価技術によっても計算量の増大は大きくなく、実用的なレベルの利便性を維持している。
【００５３】
［第二実施形態］
＜構成＞
図９を参照して、この実施形態の類似度評価システム５の構成例を説明する。類似度評価システム５は、N(≧1)台の利用者端末６1，…，６Nと類似度評価装置７を含む。N台の利用者端末６1，…，６Nと類似度評価装置７はネットワーク４に接続される。ネットワーク４は、接続される各装置が相互に通信可能なように構成されていればよく、例えばインターネットやＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）などで構成することができる。なお、各装置は必ずしもネットワークを介してオンラインで通信可能である必要はない。例えば、利用者端末６n(1≦n≦N)の出力する情報を磁気テープやＵＳＢメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体からオフラインで類似度評価装置７へ入力するように構成してもよい。
【００５４】
図１０（Ａ）を参照して、類似度評価システム５に含まれる利用者端末６nの構成例を説明する。利用者端末６nは、制御部６０１、メモリ６０２、ファイル記憶部２１、投入部２２、表示部２３、全体特徴量算出部３２、区間分割部３４、区間特徴量算出部３５を備える。利用者端末６nは、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。利用者端末６nは制御部６０１の制御のもとで各処理を実行する。利用者端末６nに入力されたデータや各処理で得られたデータはメモリ６０２に格納され、メモリ６０２に格納されたデータは必要に応じて読み出されて他の処理に利用される。ファイル記憶部２１は、例えば、ＲＡＭ（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリなどの半導体メモリ素子により構成される補助記憶装置、などにより構成することができる。
【００５５】
図１０（Ｂ）を参照して、類似度評価システム５に含まれる類似度評価装置７の構成例を説明する。類似度評価装置７は、制御部７０１、メモリ７０２、入力部３１、全体類似度評価部３３、区間類似度評価部３６、出力部３７、特徴量記憶部３８を備える。類似度評価装置７は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。類似度評価装置７は制御部７０１の制御のもとで各処理を実行する。類似度評価装置７に入力されたデータや各処理で得られたデータはメモリ７０２に格納され、メモリ７０２に格納されたデータは必要に応じて読み出されて他の処理に利用される。特徴量記憶部３８は、例えば、ＲＡＭ（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリなどの半導体メモリ素子により構成される補助記憶装置、リレーショナルデータベースやキーバリューストアなどのミドルウェア、などにより構成することができる。
【００５６】
したがって、第一実施形態の類似度評価システム１と第二実施形態の類似度評価システム５との相違点は、類似度評価システム１では類似度評価装置３が備えていた全体特徴量算出部３２、区間分割部３４、区間特徴量算出部３５を利用者端末６nが備えるように構成した点である。
【００５７】
＜処理＞
図１１を参照して、この実施形態の類似度評価システム５に含まれる利用者端末６の動作例を説明する。
【００５８】
利用者端末６n(1≦n≦N)の備えるファイル記憶部２１には類似度を評価する少なくとも２つのファイルを含む比較対象ファイル群が記憶されている。比較対象ファイル群に含まれるファイルの数は２つであってもよいし、３つ以上であってもよい。以降の説明では、２つのファイルの類似度を評価する場合について説明し、３つ以上の場合に相違する点があれば適宜説明する。また、比較対象の２つのファイルは、それぞれ比較元ファイル、比較先ファイルと呼ぶ。
【００５９】
利用者端末６nの備える全体特徴量算出部３２は、比較元ファイルと比較先ファイルそれぞれから所定のエントロピー値を算出する（ステップＳ３２）。比較元ファイルから算出したエントロピー値は比較元全体特徴量、比較先ファイルから算出したエントロピー値は比較先全体特徴量と呼ぶ。算出するエントロピー値は、第一実施形態と同様であるので説明を省略する。比較対象ファイル群が３つ以上のファイルを含む場合には、すべての２つのファイルの組み合わせについて、所定のエントロピー値を算出すればよい。
【００６０】
比較元ファイルと比較先ファイルが区間分割部３４へ入力される。区間分割部３４は、比較元ファイルと比較先ファイルそれぞれを所定の方法で複数の区間に分割する。（ステップＳ３４）。比較元ファイルを分割した後のファイルは比較元分割ファイル、比較先ファイルを分割した後のファイルは比較先分割ファイルと呼ぶ。区間分割の方法は、第一実施形態と同様であるので説明を省略する。
【００６１】
比較元分割ファイルと比較先分割ファイルは区間特徴量算出部３５へ入力される。区間特徴量算出部３５は、比較元分割ファイルと比較先分割ファイルそれぞれから区間ごとに所定のエントロピー値を算出する（ステップＳ３５）。比較元分割ファイルの区間ごとのエントロピー値のスペクトルを比較元区間特徴量と呼び、比較先分割ファイルの区間ごとのエントロピー値のスペクトルを比較先区間特徴量と呼ぶ。算出するエントロピー値は、全体特徴量と同様に、第一実施形態と同様であるので説明を省略する。
【００６２】
利用者端末６nの備える投入部２２は、比較元全体特徴量と比較先全体特徴量と比較元区間特徴量と比較先区間特徴量とを類似度評価装置７へ送信する。
【００６３】
図１２を参照して、この実施形態の類似度評価システム５に含まれる類似度評価装置７の動作例を説明する。
【００６４】
利用者端末６nが送信した比較元全体特徴量と比較先全体特徴量と比較元区間特徴量と比較先区間特徴量とは、入力部３１を介して類似度評価装置７へ入力される（ステップＳ３１）。入力された比較元全体特徴量と比較先全体特徴量と比較元区間特徴量と比較先区間特徴量とは特徴量記憶部３８に記憶される。全体類似度評価部３３は特徴量記憶部３８から読み出した比較元全体特徴量と比較先全体特徴量から全体類似度を算出する（ステップＳ３３１）。全体類似度の算出は、第一実施形態と同様であるので説明を省略する。比較対象ファイル群が３つ以上のファイルを含む場合には、すべての２つのファイルの組み合わせについて、全体類似度を算出すればよい。
【００６５】
全体類似度評価部３３は算出した全体類似度をあらかじめ定めた閾値と比較し、比較元ファイルと比較先ファイルが類似するか否かを示す暫定判定結果を求める。暫定判定結果には、全体類似度が閾値以上である場合にはファイルが類似することを示す値を設定し、全体類似度が閾値未満の場合にはファイルが類似しないことを示す値を設定する（ステップＳ３３２）。比較対象ファイル群が３つ以上のファイルを含む場合には、全体類似度が閾値以上であるファイルの組み合わせが存在する場合に類似するファイルが存在することを示す値を設定し、全体類似度が閾値以上であるファイルの組み合わせが存在しない場合に類似するファイルが存在しないことを示す値を設定すればよい。
【００６６】
暫定判定結果が比較元ファイルと比較先ファイルとが類似しないことを示す場合には、比較元ファイルと比較先ファイルとが類似しないことを示す判定結果を出力し、処理を終了する（ステップＳ３７２）。
【００６７】
暫定判定結果が比較元ファイルと比較先ファイルとが類似することを示す場合には、以降の処理を継続する。複数のファイルの組み合わせでファイルが類似すると判定された場合には、類似するファイルの組み合わせすべてについて以降の処理を繰り返し実行する。
【００６８】
比較元区間特徴量と比較先区間特徴量は区間類似度評価部３６へ入力される。区間類似度評価部３６は、比較元区間特徴量と比較先区間特徴量とに基づいて比較元ファイルと比較先ファイルが類似するか否かを示す判定結果を求める（ステップＳ３６）。判定の方法は、第一実施形態と同様であるので説明を省略する。
【００６９】
判定結果は、類似度評価装置７の備える出力部３７を介して利用者端末６nへ送信される（ステップＳ３７１，Ｓ３７１）。送信する情報は、第一実施形態と同様であるので説明を省略する。
【００７０】
利用者端末６nの備える表示部２３は、類似度評価装置７から受信した判定結果を表示する。表示の方法は、第一実施形態と同様であるので説明を省略する。
【００７１】
＜効果＞
上記のように構成することで、この実施形態の類似度評価システム５は、利用者端末６1，…，６Nから類似度評価装置７へネットワーク４を経由して送信されるデータが、データサイズの大きい評価対象ファイルではなくデータサイズの小さい特徴量のみとすることができる。これにより、ネットワーク４上に流れるトラフィックを抑え、レスポンスを向上することができる。
【００７２】
［プログラム、記録媒体］
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施例において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００７３】
また、上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００７４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００７５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００７７】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００７８】
１，５  類似度評価システム
２，６  利用者端末
３，７  類似度評価装置
４  ネットワーク
２１  ファイル記憶部
２２  投入部
２３  表示部
３１  入力部
３２  全体特徴量算出部
３３  全体類似度評価部
３４  区間分割部
３５  区間特徴量算出部
３６  区間類似度評価部
３７  出力部
３８  特徴量記憶部
２０１，３０１，６０１，７０１  制御部
２０２，３０２，６０２，７０２  メモリ
【図１】
2014085854.tif 000010
【図２】
2014085854.tif 000011
【図３】
2014085854.tif 000012
【図４】
2014085854.tif 000013
【図５】
2014085854.tif 000014
【図６】
2014085854.tif 000015
【図７】
2014085854.tif 000016
【図８】
2014085854.tif 000017
【図９】
2014085854.tif 000018
【図１０】
2014085854.tif 000019
【図１１】
2014085854.tif 000020
【図１２】
2014085854.tif 000021