(57)【要約】整合性検査技術を用いてコンピュータウィルスを特定し、その位置を決定する方法を提供する。ファイルブロックのシーケンスを算出するステップと、ホストファイルからのファイルブロックのシーケンスのハッシュを計算し、感染ファイルからの同一または関連するファイルブロックのシーケンスのハッシュを計算するステップと、第１のハッシュと第２とのハッシュのいくつかが一致しない場合にウィルスの位置が出力されるように、同一または関連するファイルブロックのシーケンスから、ホストファイルからのハッシュと感染ファイルからのハッシュとを比較するステップと、を含む、３種類のウィルス感染のそれぞれへのウィルス位置決定方法が提供される。ウィルス感染の種類に基づいてファイルブロックのシーケンスを算出する方法と、衝突困難ハッシュ関数、デジタル署名方式、メッセージ認証コード、または疑似乱数関数を用いてハッシュを計算する方法が提供される。
2010508573.tif 000002
【特許請求の範囲】
【請求項１】
ファイルブロックのシーケンスを算出するステップと、
ホストファイルからの前記ファイルブロックのシーケンスの第１のハッシュを計算するステップと、
感染ファイルからの前記ファイルブロックのシーケンスの第２のハッシュを計算するステップと、
前記ファイルブロックのシーケンスを有する前記第１のハッシュと前記第２のハッシュとを比較するステップと、
を含み、
前記第１のハッシュと前記第２のハッシュとのいくつかが一致しない場合にウィルスの位置を出力する、ウィルス位置決定方法。
【請求項２】
前記第１のハッシュを計算するステップ及び前記第２のハッシュを計算するステップは、衝突困難ハッシュ関数、デジタル署名方式、メッセージ認証コード、及び疑似乱数関数の１つを用いて行われる、請求項１に記載の方法。
【請求項３】
前記ファイルブロックのシーケンスを算出するステップは、出力が、書換え型、追加型または埋め込み型ウィルスの位置をそれぞれ返す、書き換え型アルゴリズム、追加型アルゴリズム及び埋め込み型アルゴリズムの１つ用いて行われる、請求項１に記載の方法。
【請求項４】
前記ウィルスは、ホストファイルからの改変された内容を有する前記ファイルブロックのシーケンスである、請求項１に記載の方法。
【請求項５】
前記ウィルスの前記位置は、小さな乗法量を超える分だけ前記ウィルスよりも大きい量以下である前記ファイルブロックのシーケンスである前記ファイルブロックのシーケンスである、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、ソフトウェアセキュリティに関し、特に、整合性検査(integrity checking)技術を用いてコンピュータウィルスを特定し、その位置を突き止める方法に関する。
【背景技術】
【０００２】
ウィルス検出は、アンチウィルスソフトウェアを購入して動作させるような、ウィルスに対する予防処置をとることを定期的に要求されるあらゆるコンピュータユーザに対して、驚くほど広範な影響を与える問題である。ウィルスとは、テキストあるいは実行可能なコードなどの形態のデータであって、ユーザの承認なく、かつ一般にはユーザが知らない状態で、ユーザのファイルのデータに追加または上書きされたデータのことである。ウィルス検出の分野における研究として、特定クラスのウィルスを対象とする種々の発見的（ヒューリスティックな）方法がある。この問題の解決を試みるいくつかの最も効を奏した現在の技術は、シグネチュア検出及び整合性検査の一般的なパラダイムに分類される。そのようなものとして、例えば、E. Skoudis, "MALWARE:Fighting Malicious Code," Prentice Hall(2004)（非特許文献１）及びP. Szor, "The Art of Computer Virus Research and Defense," Addison Wesley(2005)（非特許文献２）に示されたものがある。前者のパラダイムは、既知のウィルスについてのシグネチュア（痕跡）と呼ばれる感染したコード断片を発見することと、そのシグネチュアを蓄積することと、コンピュータメモリをスキャンしてそのようなシグネチュアを探索するソフトウェアを開発することが必要である。本発明が視点を置く後者のパラダイムは、ファイルへの無承認の変更を検出でき、未知のウィルスの存在を明らかにする可能性を有する、暗号ハッシュ(cryptographic hash)関数を使用することが必要である。後者のパラダイムの成功した重要な例は、ＵＮＩＸ（登録商標）環境において広範に利用可能な整合性検査プログラムであるＴｒｉｐｗｉｒｅである。
【０００３】
例えば、G. Di Crescenzo, A. Ghosh, and R. Talpade, "Towards a Theory of Intrusion Detection"で検討されているように、シグネチュア及び異常検出における侵入検出原理は、ウィルス検出の方法論への洞察を与えている。シグネチュアによるウィルス検出パラダイムは、侵入検出分野におけるシグネチュア検出原理に類似しているが、それとは対照的に、整合性検査パラダイムは、侵入検出分野における異常検出原理に対してより類似している。
【０００４】
通常、利用可能なアンチウィルスソフトウェアは、ウィルスを検出する三つの主な技術であるシグネチュア、ヒューリスティックス及び整合性検証を使用している。シグネチュア技術は、侵入検出システムのシグネチュア検出手法に類似している。まず、既知のウィルスが調べられ、それらのシグネチュアが蓄積され、次に、これらのシグネチュアの存在が候補の実行可能ファイルで探される。これがウィルス検出の最も普及している手法であるが、この手法はベンダーによるシグネチュアデータベースの迅速な更新、及びユーザによるそれらのシグネチュアファイルの迅速な更新に依存しており、ポリモーフィック（多様型：polymorphic）及びメタモーフィック（変成型(metamorphic)）型のウィルス技術によって簡単に破られる。
【０００５】
他の二つの技術であるヒューリスティックス及び整合性検証は、侵入検出システムでの異常検出手法にさらに類似している。ヒューリスティックス技術は、例えば、実行可能ファイルへの書き込み、ブートセクタへのアクセス及びハードドライブの内容の消去の試みなどのようにウィルスが示しそうないくつかの挙動に基づいてウィルスの特定を試みる点で、いくぶん高度な技術であるかもしれない。整合性検証技術は、感染が起こったであるが、おそらくは感染したファイルの実行の前であり、それによって感染はまだ実害を与えないものとなっているときに、ファイルへの予期しない変更を検出しようとするものである。
【０００６】
ヒューリスティックス技術及び整合性検証技術は、両方とも、多様性(polymorphism)及び変成能力(metamorphism)を備えたような、より「賢い」ウィルスを捕捉する潜在的能力を有している。しかしながら、これらの技術は特定のファイルに関してせいぜい警告を発することができる程度である。その特定のファイルは、そののち、潜在的なウィルスの位置、性質及び被害についての結論が導き出される必要のある制御された環境の下でのウィルス診断段階において、慎重にエミュレートして分析される必要がある。エミュレーション用の正確に制御された環境を実現することは困難であるので、導き出された結果の精度は信頼できない可能性がある。さらに、多くの場合、元のファイルへのウィルスによってもたらされる変更は、例えばメモリ以外のどこかの場所にあるプログラムを呼ぶサブルーチンのように、極めて小さいので、ウィルス自体についての付加的な情報を得ることは極めて有用であろう。
【０００７】
また、整合性検証技術または整合性検査原理は、ファイルへの変更を検出するだけであり、ファイル内で変更が発生した位置を突き止めないし、示すこともない。ウィルスについての位置決定情報がないのでは、ウィルスの検出は、非常に資源を消費する割には失敗を起こしやすいものとなる。このことは、ソフトウェアセキュリティの分野における新たな問題である「ウィルス位置決定」を暗に示している。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】E. Skoudis, "MALWARE:Fighting Malicious Code," Prentice Hall(2004)
【非特許文献２】P. Szor, "The Art of Computer Virus Research and Defense," Addison Wesley(2005)
【非特許文献３】G. Di Crescenzo, A. Ghosh, and R. Talpade, "Towards a Theory of Intrusion Detection"
【非特許文献４】B. Schneier, "Applied Cryptography:Protocols,Algorithms and Source Code in C," J. Wiley & Sons(1993)
【非特許文献５】S. Quinlan and S. Dorward, "Venti:a New Approach to Archival Storage," Proc. of USENIX Conference on File and Storage Technologies (FAST), 2002
【非特許文献６】G. H. Kim and E. H. Spafford, "The Design and Implementation of Tripwire: a File System Integrity Checker," Proc. of 2nd ACM Conference on Computer and Communications Security (ACM CCS), 1994
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明者らが知る限り、ウィルスの位置決定の問題はこれまで厳密には研究されておらず、また、これまで問題提起されたことさえなかった。暗号ハッシュのデータへの適用はデータ整合性検証にとっては周知のパラダイムであり、Ｔｒｉｐｗｉｒｅのようなファイルシステムの整合性を検証するプログラムにとっては基本的なものである。ファイルのすべての微小(atomic)ブロックの暗号ハッシュも公知のパラダイムであり、高いレイテンシ（待ち時間）の狭い帯域幅のリンクを介してファイルを遠隔で更新したり、あるいは追記型(write-once)アーカイブデータ記憶装置の目的に対処したりするプログラムにおいて使用されてきた。しかしながら、これらのプログラムのいずれもウィルス位置決定の問題を解決してこなかった。
【課題を解決するための手段】
【００１０】
本発明は、好都合にも、３種類のウィルス感染のそれぞれに対するウィルス位置決定の方法を提供する。一実施態様において、この方法は、ホストファイルからのブロックのシーケンスのハッシュを計算するステップと、疑わしいかまたは損傷したファイルを、各グループが複数のブロックのシーケンスを含んでいる、複数のグループに分割するステップと、疑わしいファイルの複数のブロックのシーケンスのすべてのハッシュを算出するステップと、ホストファイルからのハッシュを疑わしいファイルからのハッシュと比較し、その結果、不一致が見つからない場合、その疑わしいファイルは「損傷していない(uncorrupted)」と宣言され、少なくとも一つの不一致が見つけられた場合、その疑わしいファイルは「損傷している(corrupted)」と宣言され、ファイル内でのウィルスのおおよその位置を決定するステップと、を含む。
【００１１】
ウィルス位置決定方法は、ファイルブロックのシーケンスを算出するステップと、ホストファイルからのファイルブロックのシーケンスのハッシュを算出し、感染ファイルからの同一または関連したファイルブロックのシーケンスのハッシュを算出するステップと、第１のハッシュと第２のハッシュのいくつかが一致しない場合にウィルスの位置が出力されるように、同一または関連するファイルブロックのシーケンスから、ホストファイルからのハッシュを感染ファイルからのハッシュと比較するステップと、を含むことができる。ウィルス感染の種類に応じてファイルブロックのシーケンスを算出する方法と、衝突困難ハッシュ関数、デジタル署名方式、メッセージ認証コード、または疑似乱数関数を用いてハッシュを算出する方法とが提供される。
【図面の簡単な説明】
【００１２】
【図１】図１は概略図である。
【図２】図２は、ウィルスの位置を決定するために後で用いられるファイルブロックのシーケンス及びハッシュを算出する、ハッシュアルゴリズムの一般的な構造を示している。
【図３】図３は、書換え型ウィルス(rewriting-virus)に感染したファイルの場合の、ハッシュアルゴリズムＲｅｗ−ｐＨによって算出されたファイルブロックのシーケンスを示している。
【図４Ａ】図４Ａは、書換え型ウィルス位置決定アルゴリズムＲｅｗ−Ｌｏｃでのステップを示している。
【図４Ｂ】図４Ｂは、（Ｒｅｗ−Ｌｏｃによって用いられる）アルゴリズムＲｅｗ−ＲｅｃＬｏｃでのステップを示している。
【図５】図５は、追加型ウィルス(appending-virus)に感染したファイルの場合の、ハッシュアルゴリズムＡｐｐ−ｐＨによって算出されたファイルブロックのシーケンスを示している。
【図６Ａ】図６Ａは、追加型ウィルス位置決定アルゴリズムＡｐｐ−Ｌｏｃでのステップを示している。
【図６Ｂ】図６Ｂは、（Ａｐｐ−Ｌｏｃによって用いられる）アルゴリズムＡｐｐ−ＲｅｃＬｏｃでのステップを示している。
【図７】図７は、埋め込み型(embedding)ウィルスに感染したファイルの場合の、ハッシュアルゴリズムＥｍｂ−ｐＨによって算出されたファイルブロックのシーケンスを示している。
【図８】図８は、埋め込みウィルス位置決定アルゴリズムＥｍｂ−Ｌｏｃでのステップを示している。
【図９】図９は、種々のウィルス位置決定技術の特徴の要約である。
【図１０】図１０は、種々のウィルス位置決定技術の性能評価である。
【発明を実施するための形態】
【００１３】
本発明は、図面を参照し、図面全体にわたって類似の参照符号が類似の部分を示す本発明の非限定的な例示の実施形態によって、以下の詳細な説明において詳述される。しかしながら、当然に理解されようが、本発明は図示通りの装置及び手段に限定されるものではない。
【００１４】
ウィルス位置決定を用いてソフトウェアのセキュリティを改善する方法が提供される。ファイルに対する変更を検出するだけでなくファイル内でのこれらの変更の位置が突き止められるように、上述した整合性検査原理を拡張することができる。
【００１５】
ウィルス位置の決定を達成する方法を、書換え型(rewriting)手法、追加型(appending)及び先頭追加型(prepending)手法、及び挿入型(insertion)または埋め込み型(embedding)のそれぞれの手法のような、各感染手法に対して考案することができる。本発明に基づく方法は、感染手法に特化したコードによって選択された暗号ハッシュを、ファイルブロック群の種々のシーケンスに対して反復して効率的な適用することに基づいている。すべての場合において、この方法は満足できる位置決定を行う。すなわち、ウィルスより高々２倍大きな領域が損傷ファイル内で特定され、効率、すなわち位置決定ハッシュ関数によって返されるハッシュは、従来の暗号ハッシュ関数によって返されるハッシュよりも最大で対数因子の分だけ長い。出力効率は、位置決定ハッシュ関数の重要な特性である。というのは、下で議論するように、はるかに長いハッシュ、すなわち入力ドキュメントの微小ブロック数における線形因子だけ長いハッシュを返す自明な構造があるからである。
【００１６】
結果的に「損傷したファイル」になる「ターゲットファイル」に対してある改変を行うウィルス（ここで、改変の種類は特有の「感染手法」によって変わる可能性がある）を以下で考察する。（暗号）衝突困難ハッシュの既知の概念及び形式的定義（例えばB. Schneier, "Applied Cryptography:Protocols,Algorithms and Source Code in C," J. Wiley & Sons(1993)）が示され、ウィルスの振る舞いの分類が説明される。
【００１７】
衝突困難ハッシュの概念：
「衝突困難(collision-intractable)」ハッシュ関数、または「衝突なし(collision-free)」、「衝突困難(collision-resistant)」、及び時として「暗号(cryptographic)」関数として知られている、暗号法でしばしば用いられる数学的ツールが、ファイルやメッセージなどの整合性検証を必要とする用途を含むいくつかの用途において非常にしばしば用いられている。これらのツールまたは関数は以下のように定義される：すなわちそれらは、入力として任意の長さの二進（バイナリ）文字列（圧縮されるべきファイルを示す）を受け取り、出力として固定サイズ（例えば１２８または１６０ビット）の二進文字列（元のファイルのハッシュまたはフィンガープリント（指紋）を示す）を返す。ハッシュ関数への入力が１６０ビットよりはるかに長い場合、ハッシュ関数の任意の単一出力の原像(preimage)の数は非常に大きくなる。さらに、これらの関数によって期待される驚くべき特性は、任意のアルゴリズムでもそれを実行に成功するのに実行不可能な時間（例えば、数世紀またはそれ以上）を要するであろうという意味において、同一の出力へマップ（写像）されるたった２つの原像を見つけることすら、いかなる効率的なアルゴリズムにとっても計算困難でありそうだからである。
【００１８】
衝突困難ハッシュ関数の形式的定義：
ｋをセキュリティパラメータとし、Ｈ＝｛Ｈw｝k∈Nを関数
Ｈw：｛０，１｝k×｛０，１｝a→｛０，１｝b
の族(family)とする、ここでａ＞ｂであり、ｗは｜ｗ｜＝ｋを満足する関数インデックスである。以下の条件、
（１）各ｗに対してＨwを算出する（ｋについての）確率的多項式時間アルゴリズムが存在する；
（２）任意の確率的多項式時間アルゴリズムＡに関し、ｗが一様に選択された場合に、Ｈw(ｘ1)＝Ｈw(ｘ2)となるような確率Ａ(ｗ)＝(ｘ1，ｘ2)が最大でε(ｋ)となる、どんな逆多項式よりも漸近的に小さい関数εが存在する；
が成り立つ場合に、Ｈを衝突困難ハッシュ関数(collision-resistant hash function)の族であると言う。
【００１９】
衝突困難ハッシュ関数には以下の特性が認められる：無視できる確率(negligible probability)を除いて、ｘ1及びｘ2が多項式時間アルゴリズムから算出される場合、｜ｘ1｜≧ｋ，｜ｘ2｜≧ｋに対してｘ1≠ｘ2の時、Ｈw(ｘ1)≠Ｈw(ｘ2)となる。それらの入力に対して微小(atomic)衝突困難ハッシュ関数を繰り返し適用する合成衝突困難ハッシュ関数の構造を、任意の２つの入力に基づいた、合成関数の結果として生じた出力が入力の類似性及び／または差異についての情報を明らかにするように、構築することができる。
【００２０】
ウィルスの振る舞いの分類：上書き、先頭追加、追加、埋め込み：
大半のインターネットウィルスをそれらウィルスの感染手法、すなわち以下に詳細に説明する、上書き(Overwriting)、先頭追加(Prepending)、追加(Appending)、及び埋め込み(Embedding)の１つにしたがうように特徴づけることができる。
【００２１】
上書き型感染手法(Overwriting Infection Technique)：
この感染手法では、ウィルスは、ホストのコードの一部を交換することによって、ホストまたはターゲット実行可能ファイルに感染する。ウィルスにとってこれを実現可能な１つの方法は、正規のデータファイルを開くであろうように、書き込みのために簡単にターゲットファイルを開き、その後、ウィルス自身のコピーをファイルにセーブすることである。これによって損傷ファイルが発生することになる。損傷した実行可能ファイルが、そのあとで、その所有者によって実行開始されるとき、オペレーティングシステムは、元のターゲットプログラムの代わりにウィルスコードを実行するだろう。この感染手法は、通常、ターゲットファイルにダメージを与え、それを使用不能にする。
【００２２】
先頭追加型感染手法(Prepending Infection Technique)：
この感染手法では、ウィルスは、どのウィルスが感染したいホストまたはターゲット実行可能ファイルの先頭にそのコードを挿入し、損傷した実行可能ファイルを生成する。この技術は、一般に、上書き技術より精巧であり、例えばウィルスＮｉｍｄａによって使用された。損傷ファイルが、そのあとで、その所有者によって実行開始されるとき、ウィルスコードが実行可能プログラムの先頭に位置し、次に意図されたすなわち元のターゲットプログラムが位置するので、オペレーティングシステムは、最初にウィルスコードを実行するだろう。この感染手法は、ターゲットファイルを破損するようには見せないだけでなく、コードの所有者によって簡単に検出できない、という効果も持っている。事実、そのようなウィルスの存在は容易に検出できない。
【００２３】
追加型感染手法(Appending Infection Technique)：
この感染手法では、ウィルスは、そのウィルスが感染したいホストまたはターゲット実行可能ファイルの終わりにそのコードを挿入し、さらに、通常、ウィルスコードの先頭へのジャンプも感染または損傷したファイルの先頭に挿入する。損傷した実行可能ファイルが、そのあとで、その所有者によって実行開始されるとき、オペレーティングシステムは、まず、ジャンプしてウィルスコードを実行し、次に、意図したプログラム、すなわち元のターゲットプログラムの制御に戻るであろう。先頭追加手法と同様に、この感染手法を用いたウィルスの存在を検出するのは容易ではない。この手法は、例えばウィルスＭｉｃｈｅｌａｎｇｅｌｏで使用された。
【００２４】
埋め込み型感染手法(Embedding Infection Technique)：
この感染手法では、ウィルスは、１個のコードまたは別個のファイル中のコードを指すコマンドを、シェルスクリプト、Ｐｅｒｌのスクリプト、Ｊａｖａ（登録商標）のクラスファイル、または正規の実行可能ファイルに最終的にコンパイルされる１つまたは複数のファイルのソースコードのどこにでも挿入する。この手法が見られた例はほとんどないが、実行可能命令を含んだあらゆるプログラムがウィルスの潜在的なターゲットであるということに注意しなければならない。
【００２５】
暗号ハッシュに基づいた整合性検証：
上述したように、整合性検証技術は、ファイルを実行する前に、そのファイルへの予期しない変更を検出しようとするものである。暗号ハッシュに基づいた整合性検証は以下のように行うことができる。
【００２６】
任意の衝突困難ハッシュ関数の族Ｈ＝｛Ｈw｝k∈N（表記を簡単にするために、Ｈwからインデックスｗを落としている）及びファイルｆが与えられるすると、１６０ビットの値であるｈａｓｈ（ハッシュ）＝Ｈ(ｆ)値は、任意の効率的なアルゴリズム（場合によりｆそのものを生成するアルゴリズム）が整合性検証試験Ｈ(ｇ)＝Ｈ(ｆ)を満足するｆとは異なるｇを実現可能な計算時間で得るまたは既に持つことができないであろう、という根拠を与える。
【００２７】
実行可能またはソースファイルの整合性検証は以下のように行われる。準備段階では、ファイルがその元のソースファイルからダウンロードされる場合のように、ファイルｆが感染していないと考えられる場合、タグｈａｓｈ＝Ｈ(ｆ)がファイルに添付されている。そののち、合法的な変更がファイル上で行われてファイルｆ'になると、新しい値ｈａｓｈ'＝Ｈ(ｆ')が以前のハッシュ値に取って代わる。ファイルを実行する必要がある場合、または実行のためにコンパイルされる必要がある場合、整合性検証試験はファイルの現在のバージョンｆ''上で行われる、すなわち、ｈａｓｈ'＝Ｈ(ｆ'')かどうかがチェックされる。一致が確認されれば、合法的な変更のみがファイルになされたという根拠を持つことになり、一致が確認されない場合には、ある予期しない変更が生じていることになる。この変更は感染によってもたらされ得るので、次に、そのファイルは、安全な環境でファイルの実行をエミュレートすることを含む種々の診断技術を試みるアナライザに送られ、ウィルスについての有用な情報を引き出し、たぶん、ファイルｆ''をその以前の感染していない状態に修復する。
【００２８】
暗号ハッシュを整合性検証に用いるよくあるシステムとして、S. Quinlan and S. Dorward, "Venti:a New Approach to Archival Storage," Proc. of USENIX Conference on File and Storage Technologies (FAST), 2002（非特許文献５）及びG. H. Kim and E. H. Spafford, "The Design and Implementation of Tripwire: a File System Integrity Checker," Proc. of 2nd ACM Conference on Computer and Communications Security (ACM CCS), 1994（非特許文献６）に記載されるＶｅｎｔｉがある。
【００２９】
暗号ハッシュとウィルス位置決定：
上記の技術を拡張して、整合性を検査するだけでなく、２つのファイル間の差異についての付加的情報を明らかにすることもできる。上記の整合性検証技術の基礎的な特性は、以下のように言い直すことができる。ファイルＭ(１)及びＭ(２)、及びそれらのハッシュｈａｓｈ(１)及びｈａｓｈ(２)が与えられると、Ｍ(１)＝Ｍ(２)ならば１であり、そうでなければ０である定義される関数ｐ(Ｍ(１)，Ｍ(２))を決定する効率的なアルゴリズムＤＩＦＦが存在する。アルゴリズムＤＩＦＦは、入力ｐ、ｈａｓｈ(１)及びｈａｓｈ(２)を用いて、単純にｈａｓｈ(１)＝ｈａｓｈ(２)かどうかを検査し、もしそうならば１を返し、そうでない場合には０を返す。この手法はより広範な関数に、特に、例えば書換え型(rewriting)、追加型、先頭追加型及び埋め込み型の感染手法のような上述した感染手法によって引き起こされる、Ｍ(１)とＭ(２)との間の差異に関する情報を検出する関数に、一般化することができる。例えば、p-revealing（ｐ−顕示）衝突困難ハッシュ関数は、２つのファイルＭ(１)，Ｍ(２)を返す任意の効率的な敵対者に対して、入力としてＭ(１)及びＭ(２)の２つのハッシュを受け取る際に関数ｐ(Ｍ(１)，Ｍ(２))を算出できる効率的なアルゴリズムＤｅｔが存在するような、衝突困難ハッシュ関数として形式的に定義される。ここでｐは、通常、２つのファイル間の差異に関する何らかの情報を返す関数である。任意の衝突困難ハッシュ関数はＭ(１)とＭ(２)との間の差異の性質に関する有用な情報を明らかにするのを支援するようには見えないが、従来のものから発展したより複雑な衝突困難ハッシュ関数を考案して有用な情報を得ることができる。
【００３０】
説明した本発明に基づく方法のすべてでは、各ファイルＭはｎ個の微小ブロックＭ(１)，Ｍ(２)，…，Ｍ(ｎ)からなり、ここでブロックサイズは適切に選択することができる。例えば、ファイルを例えばソースファイルの行に分解できるような、最も小さな意味上(semantic)の単位として、ブロックサイズを決定することができるであろう。１つの手法では、非常に単純なハッシュ関数が、入力ファイルの各ブロックの微小ハッシュを返し、次に、以前に算出されたすべてのハッシュの微小ハッシュを返すことによって得られる。ここで微小ハッシュは、任意の衝突困難ハッシュ関数を用いて算出される。この技術をファイルの各ブロック上で上記のアルゴリズムＤＥＦＦとともに用いて、関数ｐによって必要とされるあらゆる興味ある情報を引き出すことができる。しかしながら明らかな欠点は、返されたハッシュが長すぎることであり、それは従来のハッシュの大きさのｎ倍に等しい。このことは、数キロバイトのようなかなり小さなサイズのファイルにとっても既に非実用的になり得る。
【００３１】
しかしながら、例示実施形態では、構造(construction)の「拡張ファクタ(expansion factor)」と呼ばれる、返されたハッシュの大きさは、以下のように定義される。Ｈを衝突困難ハッシュ関数とし、ｃＨをＨへの呼び出しを行うハッシュ関数の構造としよう。すると、ｃＨの拡張ファクタは、ｎビットの入力上のＨにより返された出力の大きさで除算されたｎビットの入力上のｃＨによって返された出力の大きさとなる。できるだけ短い拡張ファクタを有する構造、例えばｎについての対数が非常に望ましい。すべての構造を拡張ファクタに等しいハッシュ関数の適用回数として記述できるので、この構造は、付加された検証及びハッシュの発生に起因する計算上及び記憶上のオーバヘッドを非常に小さくすることを可能にする。
【００３２】
この性能を達成するために、感染手法の各々で例示したように、基礎の衝突困難ハッシュ関数の複数回の適用が、メッセージビットの慎重に選択されたシーケンスに対して算出される。例えば、シーケンスの選択は、後で複数のハッシュのみから２つのメッセージ間の差異に関する所望の情報を「復号する」ことを可能にする、適切な「符号化方式」にしたがって行うことができる。ここで、符号化／復号方式及び所望の情報はともに、感染手法に依存している。
【００３３】
他の興味のあるメトリックは、ウィルスが検出される局在化された領域を最小限にすることであろう。特に、ある「位置決定因子」ρに対して、最大でｍａｘ(ρ・ｂ(Ｖ)，１)となるブロック数を含んだブロックの間隔を返すことが望ましい。ここでｂ(Ｖ)はウィルスＶが構成されるブロック数である。
【００３４】
本発明に基づく方法におけるすべての構造は、位置決定因子ρ＝２（ｎについての対数で表される拡張ファクタ）を達成し、ハッシュについての頻繁でないオフライン計算を必要とするのみであり、その結果、計算オーバヘッドは、システム全体の効率への重要な要因にはならない。
【００３５】
図１は、疑わしいファイル１２になるような処理技術によって変更されるターゲットファイル１０を示す概略図である。図２は、ハッシュアルゴリズム、例えば一般的なp-revealingハッシュ関数の一般的な構造を示している。このハッシュアルゴリズムは、後でウィルスの位置を突き止めるのに用いられるファイルブロックのシーケンス及びハッシュを算出する。ステップＡ１において、ブロックシーケンスが算出される。ステップＡ２において、各ブロックシーケンスに対してハッシュが算出される。このハッシュはステップＡ３において出力される。以下に、各種の感染すなわち書換え型、追加／先頭追加型及び埋め込み型のためのハッシュアルゴリズムをより詳細に説明する。
【００３６】
書換え型感染のウィルス位置決定：
上述のように、書換え型感染手法では、ウィルスは、ターゲットファイルのいくつかのブロックを書き換える。ほとんどの場合、損傷ファイルは、書換えの後でさえ同一サイズのままであり、書き換えられたブロックが隣接して配置されている。本発明に基づく方法は、ファイルからのブロックのシーケンスに対してできるだけ多くのハッシュを算出し、ファイルのいかなる位置でも連続するブロックのセグメントを書き換えるウィルスの位置決定を後でできるようしている。したがって、ファイル中のブロック数をｎとすると、位置決定ハッシュ関数は、ファイルブロックの４(ｌｏｇ2 ｎ−ｌ)個のシーケンスに対してハッシュを算出するので、４(ｌｏｇ ｎ−１)個のハッシュが算出される、すなわち、ｌｏｇ ｎ−１個のグループの各々に対して４つのハッシュが算出される。例えば、ｎ＝１０２４の場合、４×(１０−１)すなわち３６個のハッシュが算出される。図３は、書換え型感染に対するウィルス位置診断ハッシュ計算の例示実施形態において、ハッシュ計算がなされるファイルブロック１４，１６，１８，２０のシーケンスから構成されたグループ２２を示している。なお、ｉ番目のグループ２２では、ｎ／２i+1ブロックだけファイルを巡回的に回転させ、第１のシーケンス１４及び第２のシーケンス１６に分割を再適用することにより、第３のシーケンス１８及び第４のシーケンス２０が得られることに留意されたい。
【００３７】
実施形態では、p-revealing衝突困難ハッシュ関数ｐは、以下のように定義される。ｎ個のブロックを有するファイルＭ１，Ｍ２の入力上で、関数ｐ(Ｍ１，Ｍ２)は次に等しくなる：
Ｍ１＝Ｍ２の場合は０；
（ｂ−ａ）＜（ｎ／４）、かつ、Ｍ１(ａ)，Ｍ１(ａ＋１)，…，Ｍ１(ｂ)及びＭ２(ａ)，Ｍ２(ａ＋１)，…，Ｍ２(ｂ)だけがＭ１とＭ２とが異なるブロックである場合に(ａ，ｂ)；  それ以外の場合には⊥。
【００３８】
したがって、この解析は、最大でｎ／４個のブロックを書き換えるウィルスに限定される。その理由は、より多くのブロックが書き換えられた場合、位置決定ハッシュ関数が従来のハッシュ関数に比べて著しく有用ではなくなるので、位置決定問題は妥当性を失うからである。
【００３９】
したがって各ステップでは、微小衝突困難ハッシュ関数Ｈが、入力ファイルのいくつかのブロックのハッシュを算出するのに用いられる。Ｍ1をＭ2に改変する書換えウィルスのためによって相互に異なっている任意の２つのファイルＭ1，Ｍ2が与えられると、各ステップにおけるハッシュは、Ｍ2における候補ブロックの半分を削除することによって、ウィルスの位置を発見するための支援を行うはずである。削除されたブロックは、ファイル中のまだ削除されていないブロックの前半または後半、またはファイル中のまだ削除されていないブロックの適切な巡回シフトの前半または後半、の４つの中の１つである。これは位置決定因子２を達成するのに十分であり、各ステップで４個のハッシュが算出されるので、出力拡張は高々４・ｌｏｇ ｎとなる。
【００４０】
衝突困難ハッシュ関数の形式的な記述を以下に続ける。Ｒｅｗ−ｐＨとして示す本発明に基づくp-revealing衝突困難ハッシュ関数は、入力としてｎ個のブロックからなるメッセージＭ＝Ｍ(０)，…，Ｍ(ｎ−１)を受け取り、以下のように、元の衝突困難ハッシュ関数Ｈを４・ｌｏｇ ｎ回にわたってＭのｌ個のブロックのシーケンスに適用する（説明を簡単にするために、ｎは２のべき乗であり、対数は底が２であると仮定する）。
【００４１】
ステップ１：
この第１のステップで、Ｍの中のブロックは、各シーケンスがｎ／２個のブロックの連結によって得られる、次のように定義される４つのシーケンスにグループ化される：
Ｓ1,1＝Ｍ(０)｜…｜Ｍ(ｎ／２−１)，
Ｓ1,2＝Ｍ(ｎ／２)｜…｜Ｍ(ｎ−ｌ)，
Ｓ1,3＝Ｍ(ｎ／４)｜…｜Ｍ(３ｎ／４−１)，
Ｓ1,4＝Ｍ(０)｜…｜Ｍ(ｎ／４−１)｜Ｍ(３ｎ／４)｜…｜Ｍ(ｎ−１))。
【００４２】
Ｓ1,3及びＳ1,4のブロックのインデックス（指標）は、それぞれｎ／４だけ、Ｓ1,1及びＳ1,2のブロックのインデックスを巡回的にシフトすることによって得られる。このステップでの４つのハッシュは、ｉ＝１，２，３，４に対してｈ1,i＝Ｈ(Ｓ1,i)として算出される。
【００４３】
ステップｊ、ここでｊ＝２，…，ｌｏｇ ｎ−１：
ステップ１を拡張して、Ｍ中のブロックは、各シーケンスがｎ／２j個のブロックの連結によって得られる、次のように定義される２×２j個のシーケンスにグループ化される：
Ｓj,i＝Ｍ((ｉ−１)＊ｎ／２j)｜…｜Ｍ(ｉ＊ｎ／２j−１)，
Ｓj,i+2j＝Ｍ(((ｉ−１)＊ｎ／２j＋ｎ／２j+1) ｍｏｄ ｎ)｜…｜Ｍ((ｉ＊ｎ／２j＋ｎ／２j+1−ｌ) ｍｏｄ ｎ)，
ここで、ｉ＝１，…，２jである（なお、Ｓj,i+2jでのブロックのインデックスは、ｎ／２j+1だけ巡回的にＳj,iのインデックスをシフトすることによって得られる）。
【００４４】
このステップにおける４つのハッシュは以下のように算出される：
ｉ＝１，２の場合には、
ｈj,i＝Ｈ(Ｓj,i｜Ｓj,i+2｜Ｓj,i+4｜…｜Ｓj,i+2j-2)，
ｉ＝３，４の場合には、
ｈj,i＝Ｈ(Ｓj,i-2+2j｜Ｓj,i+2j｜Ｓj,i+2j+2｜…｜Ｓj,i+2j+2j-4)。
【００４５】
関数の出力は、ｈ＝((ｈ1,i，ｈ2,i，…，ｈlog n-1,i))i=1,2,3,4である。
【００４６】
Ｒｅｗ−ｐＨの微小ハッシュの全体の数はたったの４・ｌｏｇ ｎ−４であり、これは、各ハッシュがウィルス間隔の位置に関する１ビットの情報を明らかにするモデルにおいて、本質的に最適である。
【００４７】
Ｒｅｗ−ｐＨが衝突困難であることを示すために、Ｒｅｗ−ｐＨの出力での衝突を発見するアルゴリズムは、値ｊ＝０，１，…，ｌｏｇ ｎ及び値ｉ＝１，２，３，４の少なくとも１つに対して、Ｈによって同じｈ(ｊ｜ｉ)にマッピングされる２つの異なる入力を見つけることに気づく。このことは、Ｈの衝突を発見するアルゴリズムを暗示している。
【００４８】
Ｒｅｗ−ｐＨがp-revealingであることを示すために、ｐＨとすべてのインデックス(ｊ，ｉ)，ｊ∈｛１，…，ｌｏｇ ｎ−１｝，ｉ∈｛１，２，３，４｝に対するハッシュｈj,iとを用いる効率的なアルゴリズムＬｏｃを構築し、ファイルＭの疑わしいかまたはおそらく損傷したバージョンＭ'における書換え型ウィルスの位置決定を行う。図４Ａに示したアルゴリズムＲｅｗ−Ｌｏｃは、以下のように説明することができる：
１．  Ｍ'の入力に対してＲｅｗ−ｐＨを適用したときの、出力ｈ'＝((ｈ'1,i，ｈ'2,i，…，ｈ'log n-1,i))i=1,2,3,4を算出する（ステップＳ１）；
２．  すべてのインデックス(ｊ，ｉ)，ｊ∈｛１，…，ｌｏｇ ｎ−１｝，ｉ∈｛１，２，３，４｝に対して、ｈj,i≠ｈ'j,iの場合にはｔj,i＝１となり、ｈj,i＝ｈ'j,iの場合にはｔj,i＝０となるｔj,iを算出する（ステップＳ２）；
３．  Ｓ＝｛１，…，ｎ｝，ｊ＝１を設定し、入力ペア(Ｓ，ｊ)についてプロシージャ（手順）Ｒｅｗ−ＲｅｃＬｏｃ（下に定義される）を実行したときに返されるブロックＴのシーケンスを出力する（ステップＳ３）；
ステップＳ４では、プロシージャＲｅｗ−ＲｅｃＬｏｃを実行する。プロシージャＲｅｗ−ＲｅｃＬｏｃ(Ｓ，ｊ)は、以下のように定義され、図４Ｂに示されている：
１．  すべてのインデックスｉ∈｛１，２，３，４｝に対してｔj,i＝１の場合には（ステップＳ５）には、Ｔ＝Ｓを戻り値として返し、停止する；
２．  ｔj,i*＝０となるようにｉ*を定める（ステップＳ６）；
３．  ｉ*＝１または２場合には（ステップＳ７）、群Ｓj,i，Ｓj,i+2，Ｓj,i+4，…，Ｓj,i+2j-2からのブロックを群Ｓからすべて取り除く（ステップＳ８）；
４．  ｉ*＝３または４の場合には（ステップＳ９）、群Ｓj,i-2+2j，Ｓj,i+2j，Ｓj,i+2j+2，…，Ｓj,i+2j+2j-4からのブロックを群Ｓからすべて取り除く（ステップ１０）；
５．  プロシージャＲｅｗ−ＲｅｃＬｏｃ(Ｓ，ｊ＋１)を実行する（ステップＳ１１）。
【００４９】
ｐの定義により、（ｂ−ａ）＜（ｎ／４）の場合を考えるだけで十分とすれば、Ｒｅｗ−ｐＨがp-revealingであるという証明は、次の補助定理の帰結となる。高々ｎ／(２・２j)のサイズの任意のウィルス間隔(ａ'，ｂ')に対し、Ｍ'（ウィルス間隔（ａ'，ｂ'）を有する書き換え型感染にかかったＭのバージョン）の入力と、元のファイルＭの入力上で構造Ｒｅｗ−ｐＨのステップｊまでに得られたハッシュとに対して、アルゴリズムＲｅｗ−Ｌｏｃは、ｎ／２j≧（ｂ−ａ＋１）、（ｂ−ａ＋１）≦ｎ／２jの場合には、ａ≦ａ'≦ｂ'≦ｂとなるような間隔(ａ，ｂ)を返す。
【００５０】
追加型／先頭追加型感染のウィルス位置決定：
追加型感染手法と先頭追加型感染手法とを対称的な方法でを扱うことができる。上述のように、追加型感染手法ではウィルスはターゲットファイル１０の末端に追加されるが、先頭追加型感染手法ではウィルスはターゲットファイル１０の先頭に追加される。結果として、両方の感染手法においては、損傷してしまったまたはその疑いのあるファイル１２のファイルサイズは大きくなり、ウィルスが追加または先頭追加された後、以前のファイルサイズが失われる可能性がある。本発明に基づく方法では、ファイルの末端に連続するブロックのセグメントを追加する（または、先頭にセグメントを先頭追加する）ウィルスの位置決定を行うことをあとで行うために、ホストファイル１０からのブロックのシーケンスについての多くのハッシュを算出する。損傷していないターゲットファイル１０のブロック数がｎであり、損傷しているファイル１２のブロック数がｎ'であると仮定する。すると、ｌ個のブロックからなるメッセージの入力上で、構造は、たかだかｌｏｇ4/3 ｌ／４個のファイルブロックシーケンスを、したがってたかだかｌｏｇ4/3 ｌ／４個のハッシュを返す、すなわち、ｌｏｇ4/3 ｌ／４個のフェーズのおのおのに対して１つのハッシュを返す。例えば、ｌ＝１０２４の場合には２０個のハッシュがある。
【００５１】
図５は、追加型／先頭追加型感染に対するウィルス位置決定ハッシュを行う例示実施形態において、ハッシュされるファイルブロックのシーケンス２４を示している。
【００５２】
本発明に基づくウィルス位置決定方法では、p-revealing衝突困難ハッシュ関数を構築することができ、ここで、ｐは以下のように定義される。必ずしも長さが等しくなくてもよＭ１及びＭ２の入力上で、関数ｐ(Ｍ１，Ｍ２)は次に等しくなる：
Ｍ１＝Ｍ２の場合は０；
｜Ｍ２｜＜２｜Ｍ１｜であり、及びｉ＝１，…，ｘ−１に対してＭ１(ｉ)＝Ｍ２(ｉ)であり、かつｉ＝ｘに対してＭ１(ｉ)≠Ｍ２(ｉ)である場合はｘ；
それ以外の場合には⊥。
【００５３】
上で議論した書換え型感染の場合のように、解析を、最大でｎ個のブロックを追加するウィルスに限定することができる。すなわち、Ｍ２でのブロック数がたかだか２ｎであると仮定する。ここでｎは、Ｍ１中のブロック数である。したがって、各ステップにおいて、微小衝突困難ハッシュ関数Ｈが、入力ファイルのいくつかのブロックの２つのハッシュを算出するのに用いられる。Ｍ1をＭ2に改変する追加型ウィルスのために相互に異なっている任意の２つのファイルＭ1，Ｍ2が与えられると、各ステップにおいて、２つのハッシュは、Ｍ2中での候補ブロックの約半分を削除することによって、ウィルスの位置を発見するための支援を行うはずである。
【００５４】
追加型及び先頭追加型ウィルスに伴う主な１つの困難点は、ファイルＭ2の長さがターゲットファイルＭ1の長さとは異なる可能性があることであり、したがって、上で説明した書換え型ウィルスに対する技術のような「長さ依存の」技術は用いることができない。その代りに、ファイルの先頭からはじめて、候補ブロックは、ターゲットファイルの長さとは無関係なシーケンスのハッシュを慎重に算出することにより、削除される。
【００５５】
Ｈが衝突困難ハッシュ関数を表わすとする。Ａｐｐ−ｐＨとして表わされるp-revealing衝突困難ハッシュ関数は、入力としてｌ個のブロックからなるメッセージＭ＝Ｍ(１)，…，Ｍ(ｌ)を受け取り、元の関数Ｈを最大でｌｏｇ ｌ回にわたってＭのｌ個のブロックのシーケンスに対して以下のように適用する：
１．  ｊ←１及びＭj＝Ｍと設定する；
２．  ２k＜ｌ／２となる最大の正の整数ｋを算出し、Ｍjから、シーケンスＳj,1＝Ｍj(１)，…，Ｍj(２k)を得て、ハッシュｈj＝Ｈ(Ｓj)を算出する；
３．  反復が終わるように新しい入力Ｍj+1が０または１個のブロックを有するようになるまで、ｌ−２k+1＋１≧１場合に、Ｍj+1＝Ｍj(２k+1＋１)｜…｜Ｍj(ｌ)上でステップ２を再帰的に繰り返し、ｊ＝ｊ＋１とする：
４．  ｍ＝ｌｏｇ4/3 ｌ／４に対して、算出されたハッシュ(ｈ1，ｈ2,．…，ｈm)をすべて返す。
【００５６】
ｎがターゲットファイルＭのブロック数を表わし、ｎ'が損傷ファイルＭ'のブロック数を表わすとすると、たかだかｌｏｇ ｌ回の反復ステップがあることになる、したがって、ｎ'≦２ｎと仮定しているので、Ａｐｐ−ｐＨにより返された全ハッシュ数は、全ハッシュ数≦ｌｏｇ4/3 ｌ／４≦ｌｏｇ4/3 ｎ'／４≦ｌｏｇ4/3 ｎ−１となる。この拡張ファクタは（乗法定数を上限として）、各ハッシュがウィルス間隔の位置に関する１ビットの情報を明らかにするモデルにおいて、本質的に最適である。
【００５７】
Ａｐｐ−ｐＨが衝突困難であることを示すために、Ａｐｐ−ｐＨの出力での衝突を発見するアルゴリズムが、値ｊ＝１，…，ｌｏｇ ｎ及び値ｉ＝１，２の少なくとも１つに対して、Ｈによって同じｈ(ｊ｜ｉ)にマッピングされる２つの異なる入力を発見することに気づく。このことは、Ｈの衝突を発見するアルゴリズムを暗示している。
【００５８】
Ａｐｐ−ｐＨがp-revealingであることを示すために、すべてのインデックスｊ∈｛１，…，ｍ｝に対して（ここでｍ＝ｌｏｇ4/3 ｎ／４である）Ａｐｐ−ｐＨ及びハッシュｈjを用いる効率的なアルゴリズムＡｐｐ−Ｌｏｃを構築し、ファイルＭのたぶん損傷しているであろうバージョンＭ'中の追加型ウィルスの位置決定を行う。図６Ａに示したアルゴリズムＡｐｐ−Ｌｏｃは、以下のように説明することができる：
１．  ｊ←１及びＭj＝Ｍを設定する（ステップＳ１２）；
２．  ２k＜ｎ'／２となる最大の正の整数ｋを算出し、Ｍjから次の２つのブロックシーケンス：Ｓj,i＝Ｍj(１)，…，Ｍj(２k-1)及びＳj,2＝Ｍj(１)，…，Ｍj(２k)を得て、ｉ＝１，２に対してハッシュｈ1,j＝Ｈ(Ｓj,i)を算出する（ステップＳ１３）；
３．  反復が終わるように新しい入力Ｍj+1が０または１つのブロックを有するようになるまで、ｌ−２k+1＋１≧１場合に、Ｍj+1＝Ｍj(２k+1＋１)｜…｜Ｍj(ｌ)上でステップ２を再帰的に繰り返し、ｊ＝ｊ＋１とする（ステップＳ１５）；
４．  ｍ'＝ｌｏｇ4/3 ｎ'／４に対して、(ｈ1,i，ｈ2,i，…，ｈm',i)i=1,2がすべての算出されたハッシュを表すものとする（ステップＳ１５）；
５．  ｍ'＝ｍ（ステップＳ１６）の場合、ｉ＝２に設定し（ステップＳ１７）、そうでなければｉ＝１に設定する（ステップＳ１８）；
６．  ｈ'＝(ｈ'1，ｈ'2，…，ｈ'm')＝(ｈ1,i，ｈ2,i，…，ｈm',i)に設定する（ステップＳ１９）；
７．  すべてのインデックスｊ∈｛１，…，ｍ'｝に対して、ｈj≠ｈ'jの場合ｔj＝１とない、ｈj＝ｈ'jの場合にｔj＝０となるｔjを算出する（ステップＳ２０）；
８．  Ｓ＝｛１，…，ｎ｝，ｊ＝１と設定し、入力ペア(Ｓ，ｊ)に対してプロシージャＡｐｐ−ＲｅｃＬｏｃ（下に定義される）を適用したときに返されるペアを出力する（ステップＳ２１）；
ステップＳ２２では、プロシージャＡｐｐ−ＲｅｃＬｏｃを実行するプロシージャＡｐｐ−ＲｅｃＬｏｃ(Ｓ，ｊ)は、以下のように定義され、図６Ｂに示されている：
１．  ｔj,i＝１の場合には、Ｔ＝Ｓを戻り値として返し、停止する（ステップＳ２３）；
２．  ブロックシーケンスＳからブロックシーケンスＳj,iからのブロックをすべて取り除く（ステップＳ２４）；
３．  プロシージャＡｐｐ−ＲｅｃＬｏｃ(Ｓ，ｊ＋１)を実行する（ステップＳ２５）。
【００５９】
Ａｐｐ−ｐＨがp-revealingであるという証明は、次の補助定理の帰結となる。少なくともｌ−ｓj＋１個のブロックを有する任意のウィルス間隔(ｓ，ｌ)に対して、追加された間隔(ｓ，ｌ)を有するターゲットファイルＭに等しい、ｌ個のブロックを有する損傷ファイルＭ'の入力と構造Ａｐｐ−ｐＨの反復での最初の（ｊ−１）ステップ中に得られたハッシュとに対して、アルゴリズムＡｐｐ−Ｌｏｃは、ｘ≦ｓ（すなわち、アルゴリズムはウィルスの所在を決定する）及びｘ≧２ｓ−ｎ−１となるような値ｘを返す。すなわち、Ａｐｐ−ｐＨの位置診断因子は最大２となる。
【００６０】
埋め込み型感染のウィルス位置決定：
上述のように埋め込み型感染手法では、ウィルスは、先頭または末端ではない、ターゲットファイル１０の中間部分のどこかに挿入され、それによりターゲットファイル１０より大きなサイズを有する疑わしいファイル１２が生成される。本発明に基づく方法は、損傷したファイル１２のどこかに連続するブロックのセグメントを埋め込むウィルスの位置決定をあとで行うために、ターゲットファイル１０からのブロックのシーケンスについての多くのハッシュを算出する。ターゲットファイル１０のブロック数がｎであり、損傷しているファイル１２のブロック数がｎ'であると仮定する。すると、ｌ個のブロックを有するメッセージの入力上で、この構造は、ファイルブロックについてのたかだか８・(ｌｏｇ2 ｌ−１)個のシーケンスを、したがって８・(ｌｏｇ ｌ−１)個のハッシュを返す。すなわち、ｌｏｇ ｌ個のフェーズのおのおのに対して８つのハッシュを返す。例えば、ｎ＝１０２４の場合には、８×(１０−１)＝７２のハッシュがあることになる。
【００６１】
図７は、埋め込み型感染に対するウィルス位置決定ハッシュを行う例示実施形態において、ハッシュされるファイルブロック２６，２８，３０，３２のサブセットを示している。ウィルスが、その感染したファイルすなわち損傷したファイル１２内に埋め込まれているので、ウィルスの先頭及び終端の両方を発見することが必要である。
【００６２】
本発明に基づくウィルス位置決定方法では、p-revealing衝突困難ハッシュ関数を構築することができ、ここで、ｐは以下のように定義される。必ずしも長さが等しくなくてもよＭ１及びＭ２の入力上で、関数ｐ(Ｍ１，Ｍ２)は次に等しくなる：
Ｍ１＝Ｍ２の場合は０；
ｂ−ａ＜ｎ／２であって、ｉ＝１，…，ａ−１に対してＭ１(ｉ)＝Ｍ２(ｉ)であり、ｉ1＝ｂ＋１，…，ｎ及びｉ2＝ｉ1＋ｂ−１＋１に対してＭ１(ｉ1)＝Ｍ２(ｉ2)である場合には、(ａ，ｂ)；
それ以外の場合には⊥。
【００６３】
この解析は最大でｎ個のブロックを埋め込むウィルスに限定される、すなわち、Ｍ２でのブロック数はたかだか２ｎであると推定される。ここで、ｎはターゲットファイルＭ１のブロック数である。
【００６４】
埋め込み型感染の場合のp-revealingハッシュ関数の構造は、書換え型及び追加型感染の場合の構造の組み合わせとなる。この組み合わせは、追加型感染の構造におけるような「長さに無関係な」ファイルブロックシーケンスを使用し、書換え型感染の構造におけるようなシーケンス構造を用いるこの技術を利用することから構成される。結果的に得られる構造は、位置決定因子が２、拡張ファクタが８・ｌｏｇ ｌとなる。ここで、ｌは入力ファイルのサイズである。
【００６５】
関数の形式的説明を続ける。Ｈが衝突困難ハッシュ関数を表わすとする。Ｅｍｂ−ｐＨとして表わされる本発明に基づくp-revealing衝突困難ハッシュ関数は、入力としてｎ個のブロックからなるメッセージＭ＝Ｍ(０)，…，Ｍ(ｌ−１)を受け取り、以下のステップを１回は入力Ｍ＝Ｍ(０)，…，Ｍ(ｌ−１)上で実行し、１回は反転ファイル(reverse)ｒＭ＝Ｍ(ｌ−１)，…，Ｍ(０)上で実行することによって、元の関数Ｈを８(ｌｏｇ ｌ−１)回にわたってＭのｌ個のブロックのシーケンスに適用する（説明を簡単にするために、ｌは２のべき乗であり、対数の底は２と仮定する）。
【００６６】
ステップ１：
２k＜ｌ／２となる最大の正の整数ｋを算出する。この第１のステップにおいて、Ｍのブロックは、それぞれがｌ／２個のブロックの連結によって得られる４つのシーケンスにグループ化され、それらは次のように定義される：
Ｓ1,1＝Ｍ(０)｜…｜Ｍ(２k−１)，
Ｓ1,2＝Ｍ(２k)｜…｜Ｍ(ｌ−１)，
Ｓ1,3＝Ｍ(２k-1)｜…｜Ｍ(ｌ−１−２k-1)，
Ｓ1,4＝Ｍ(０)｜…｜Ｍ(２k-1−１)｜Ｍ(ｌ−１−２k-1)｜…｜Ｍ(ｎ−１)。
【００６７】
Ｓ1,3及びＳ1,4中のブロックのインデックスは、それぞれ、Ｓ1,1及びＳ1,2中のブロックのインデックスを２k-1だけ巡回的にシフトすることによって得られる。このステップでの４つのハッシュは、ｉ＝１，２，３，４に対してｈj,i＝Ｈ(Ｓj,i)として算出される。
【００６８】
ステップｊ、ここでｊ＝２，…，ｌｏｇ ｌ−１：
ステップ１を拡張して、Ｍ中のブロックは、各シーケンスがｎ／２j個のブロックの連結によって得られる、次のように定義される２×２j個のシーケンスにグループ化される：
ｃ，ｄ＝１，…，２jに対して、シーケンスＳj,i＝Ｍ((ｃ−１)＊２k／２j)｜…｜Ｍ(ｃ＊２k／２j−１)｜Ｍ(２k＋(ｄ−１)＊(ｌ−２k)／２j)｜…｜Ｍ(２k＋ｄ＊ｌ／２j−１))；及び
そのブロックのインデックスがシーケンスＳj,iのインデックスを２k／２jだけ巡回的にシフトすることによって得られるという点を除いて、シーケンスＳj,iと同様に定義されているシーケンスＳj,i+2j。
【００６９】
このステップにおける４つのハッシュは以下のように算出される：
ｉ＝１，２の場合には、
ｈj,i＝Ｈ(Ｓj,i｜Ｓj,i+2｜Ｓj,i+4｜…｜Ｓj,i+2j-2)；
ｉ＝３，４の場合には、
ｈj,i＝Ｈ(Ｓj,i-2+2j｜Ｓj,i+2j｜Ｓj,i+2j+2｜…｜Ｓj,i+2j+2j-4)。
【００７０】
関数の出力は、ｈ＝((ｈ1,i，ｈ2,i，…，ｈlog n-1,i))i=1,2,3,4,5,6,7,8となる（ここで、ｉ＝１，２，３，４のときｈj,iはＭを参照し、ｉ＝５，６，７，８のときｈj,iはｒＭを参照する）。
【００７１】
Ｅｍｂ−ｐＨの微小ハッシュの全体の数はたった８・ｌｏｇ ｎ−８となり、そしてこれは、各ハッシュがウィルス間隔の位置に関する１ビットの情報を明らかにするモデルにおいて本質的に最適である。
【００７２】
以前に構築されたハッシュ関数同様、Ｅｍｂ−ｐＨが衝突困難であることが分かる。Ｅｍｂ−ｐＨがp-revealingであることを示すために、すべてのインデックス(ｊ，ｉ)，ｊ∈｛１，…，ｌｏｇ ｎ−１｝，ｉ∈｛１，…，８｝に対して、Ｅｍｂ−ｐＨ及びハッシュｈj,iを用いる効率的なアルゴリズムＥｍｂ−Ｌｏｃ（図８において示される）を構築し、ファイルＭのおそらく損傷したバージョンＭ'中の埋め込み型ウィルスの位置決定を行う。このアルゴリズムは、アルゴリズムＲｅｗ−Ｌｏｃを２度実行することから構成される。すなわち一度は、すべてのインデックス(ｊ，ｉ)，ｊ∈｛１，…，ｌｏｇ ｎ−１｝，ｉ∈｛１，…，４｝に対してファイルＭとハッシュｈj,iを用いて実行し（ステップＳ２６）、もう一度は、すべてのインデックス(ｊ，ｉ)，ｊ∈｛１，…，ｌｏｇ ｎ−１｝，ｉ∈｛５，…，８｝に対してファイルｒＭとハッシュｈj,iを用いて実行する（ステップＳ２７）。Ｓ１及びＳ２をこうして得られた出力とする。アルゴリズムＥｍｂ−Ｌｏｃは、集合Ｓ１と集合Ｓ２の共通部分を返す（ステップＳ２８）。
【００７３】
性能解析：
既知の２つの技術と比較した場合における、上で説明した本発明に基づく技術の適用可能性及び性能の概要が、図９及び図１０に示されている。
【００７４】
上述のように、「検出構造(detection construction)」とは、その入力ファイル全体に対する単一のハッシュを単に算出する構造を表わし、「自明な構造(trivial construction)」とは、入力ファイルの各ブロックの単一のハッシュを算出する構造を表わしている。上述の「書換え型感染のウィルス位置決定」の節、「追加型／先頭追加型感染のウィルス位置決定」の節及び「埋め込み型感染のウィルス位置決定」の節における構造が、それぞれＲｅｗ−ｐＨ、Ａｐｐ−ｐＨ及びＥｍｂ−ｐＨとして表わされ、ｎがファイル中のブロック数であることを思い出されたい。検出構造及び自明な構造は、上述した特徴付けにおける任意の感染手法に適用可能であるが、３つのハッシュ関数構造Ｒｅｗ−ｐＨ、Ａｐｐ−ｐＨ及びＥｍｂ−ｐＨの各々は、特定の感染手法に適合するように構成されている。
【００７５】
さらに、これらの構造Ｒｅｗ−ｐＨ、Ａｐｐ−ｐＨ及びＥｍｂ−ｐＨにおけるウィルス長についての制限は、そのような制限が満足させられないときには常にウィルス位置決定問題が重要性を失うので、本質的に、一般性の喪失を伴うものではない。
【００７６】
図１０は、次に述べる性能ファクタを要約したものである。位置決定因子に関して言えば、検出構造は実際には位置決定を行わないが、一方、自明な構造は、それが感染したブロックの全ての位置を決定するので、可能な最良の位置決定能力を有する。構造Ｒｅｗ−ｐＨ、Ａｐｐ−ｐＨ及びＥｍｂ−ｐＨは、感染領域の高々２倍の大きさの領域を位置決定するのみである。拡張ファクタに関して、自明な構造はあまりにも大きい拡張を持っているが一方、検出構造は実際には拡張を持たず、構造Ｒｅｗ−ｐＨ、Ａｐｐ−ｐＨ及びＥｍｂ−ｐＨは、ハッシュに関し、（ｎについての）対数程度の拡張を持っている。
【００７７】
最後に、計算時間性能に関して言えば、自明な構造及び検出構造は、本質的に、単一のハッシュ計算に関して計算時間爆発を持たない。構造Ｒｅｗ−ｐＨ、Ａｐｐ−ｐＨ及びＥｍｂ−ｐＨは、（ｎについて）ハッシュの対数の程度の計算を行う。
【００７８】
本発明を特定の実施形態により説明したが、本発明は、そのような実施形態によって限定されるように解釈されるべきでなく、むしろ添付の特許請求の範囲に従って解釈されるべきであることを理解すべきであろう。
【００７９】
［関連する出願の相互参照］
本発明は、２００６年１０月３１日に出願された米国仮特許出願第６０／８５５，７１０号の利益を主張し、その全内容及び開示は参照によりここに組み込まれる。
【図１】
2010508573.tif 000003
【図２】
2010508573.tif 000004
【図３】
2010508573.tif 000005
【図４Ａ】
2010508573.tif 000006
【図４Ｂ】
2010508573.tif 000007
【図５】
2010508573.tif 000008
【図６Ａ】
2010508573.tif 000009
【図６Ｂ】
2010508573.tif 000010
【図７】
2010508573.tif 000011
【図８】
2010508573.tif 000012
【図９】
2010508573.tif 000013
【図１０】
2010508573.tif 000014
【手続補正書】
【提出日】平成21年6月29日(2009.6.29)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ファイルブロックのシーケンスを算出することと、
ホストファイルからの前記ファイルブロックのシーケンスの第１のハッシュを計算することと、
前記ホストファイルの感染したファイルのバージョンからの前記ファイルブロックのシーケンスの第２のハッシュを計算することと、
前記ファイルブロックのシーケンスの前記第１のハッシュと前記第２のハッシュとを比較することと、
を含み、
いくつかの前記第１のハッシュといくつかの前記第２のハッシュとが一致しない場合に、前記感染したファイルに関するウィルスの位置を出力する、ウィルス位置決定方法。
【請求項２】
前記第１のハッシュを計算すること及び前記第２のハッシュを計算することは、衝突困難ハッシュ関数、デジタル署名方式、メッセージ認証コード、及び疑似乱数関数の１つを用いて行われる、請求項１に記載の方法。
【請求項３】
前記ウィルスは、前記ホストファイルからの改変された内容を有する、請求項１に記載の方法。
【請求項４】
前記ウィルスの前記位置は、小さな乗法量を超える分だけ前記ウィルスよりも大きい量以下であるファイルブロックのシーケンスからなる、請求項１に記載の方法。
【請求項５】
ホストファイルからのファイルブロックのシーケンスの第１のハッシュを計算することと、
改変されたホストファイルからの前記ファイルブロックのシーケンスの第２のハッシュを計算することと、
前記第１のハッシュと前記第２のハッシュとを比較することと、
どの前記第１のハッシュとどの前記第２のハッシュのどれが一致しなかったかに基づいて、前記改変されたホストファイルに関してウィルスの推定された位置を出力することと、
を有するウィルス位置決定方法。
【請求項６】
前記ホストファイルから前記ファイルブロックのシーケンスを決定することは、前記ホストファイルの部分をファイルブロックに分割することと、前記ホストファイルの第２の部分をファイルブロックに分割する前に、ファイルブロック長の小数部分だけ前記ホストファイルを巡回的に回転させることと、を有する、請求項５に記載の方法。
【請求項７】
前記改変されたホストファイルに関してウィルスの推定された位置を出力することは、前記第１のハッシュと前記第２のハッシュとが一致していないファイルブロックを含むファイルブロックの範囲がホストファイルサイズの１／４未満であるときに、前記ファイルブロックの範囲を出力することを含む、請求項５に記載の方法。
【請求項８】
前記ホストファイルから前記ファイルブロックのシーケンスを決定することは、前記ホストファイルに対する順序付け式を決定することと、前記改変されたファイルに再帰的に前記順序付け式を適用することとを含む、請求項５に記載の方法。
【請求項９】
前記改変されたホストファイルに関してウィルスの推定された位置を出力することは、前記改変されたホストファイルについての、前記第２のハッシュが前記第１のハッシュの一致しないシーケンスのサブセットを出力することを含む、請求項５に記載の方法。
【請求項１０】
前記ホストファイルから前記ファイルブロックのシーケンスを決定することは、前記ファイルブロックのシーケンスは少なくともファイルブロックの２つのシーケンスを有するように、シーケンス決定式を前記ホストファイルと前記ホストファイルの反転とに適用することを有する、請求項５に記載の方法。
【請求項１１】
マシンで実行されたときに、ファイル構造におけるコンピュータウィルスの位置を決定する方法を前記マシンに実行させる命令を格納したコンピュータ可読媒体であって。
前記方法は、
ホストファイルからのファイルブロックのシーケンスの第１のハッシュを計算することと、
改変されたホストファイルからの前記ファイルブロックのシーケンスの第２のハッシュを計算することと、
前記第１のハッシュと前記第２のハッシュとを比較することと、
前記第１のハッシュと前記第２のハッシュと不一致に基づくファイルブロックの特定のシーケンスに応じて、前記改変されたホストファイルに関するウィルスの位置を出力することと、
を有する、コンピュータ可読媒体。
【請求項１２】
改変されたファイルの中のコンピュータウィルスを検出して位置を突き止めるように構成されたシステムであって、
メモリに格納された第１のハッシュの集合と、
前記メモリに格納された改変されたファイルと、
前記第１のハッシュを計算するときに用いられたファイルブロックのシーケンスを使用して前記改変されたファイルに対して第２のハッシュを計算するように構成され、前記メモリと通信する少なくとも１つの処理装置と、
を備え、
前記第１のハッシュはホストファイルの処理結果に対応し、
前記少なくとも１つの処理装置は、前記第１のハッシュと前記第２のハッシュとを比較して、前記第１のハッシュと前記第２のハッシュと不一致に基づくファイルブロックの特定のシーケンスに応じて、前記改変されたホストファイルに関するウィルスの推定された位置を出力するように構成されている、システム。
【国際調査報告】
2010508573.tif 000015