(57)【要約】      （修正有）【課題】ファイルを構成するバイト列を転置インデックス内で検索し、当該検索結果を用いてシグネチャ及びファジーハッシュを生成する。【解決手段】固定長のバイト列、及び、これらバイト列を含むファイルを関連付ける転置インデックスを検索するため、検索クエリを構成するバイト列を決定して転置インデックス内で検索し、そして、その結果の共通部分を判定して検索クエリに対する応答として返す。さらに、検索ターム及び論理演算子を含む表現形式での検索クエリを、転置インデックス内で検索し、論理演算子に基づいて構築される構文ツリーを用いて評価する。また、ファイルを構成するバイト列を転置インデックス内で検索し、その検索の結果を、シグネチャ及びファジーハッシュを生成するために利用する。【選択図】図１ａ
2018113034.tif 000002
【特許請求の範囲】
【請求項１】
１つ又は複数のプロセッサ、及び、
プログラミング命令であって、
検索クエリを受信するステップと、
前記検索クエリに対応する固定長の複数のバイト列を決定するステップと、
前記固定長のバイト列を特定する転置インデックス内での、前記バイト列のそれぞれと、特定されたバイト列のそれぞれについての、前記特定されたバイト列を含むファイルのファイル識別子と、を検索するステップと、
前記検索するステップの検索結果の共通部分を判定するステップと、
前記検索クエリに応じて、前記共通部分に含まれるファイル識別子に対応付けられたファイルの表示を返すステップと、
を含む動作を行うように、前記１つ又は複数のプロセッサによって実行されるよう構成された、前記プログラミング命令を含む、
システム。
【請求項２】
前記動作は、ファイルのコーパスから前記転置インデックスを生成するステップをさらに含み、
前記生成するステップは、前記ファイルのコーパスの少なくとも１つのファイル内で発見される前記固定長の少なくとも１つのバイト列の部分集合を、そして、バイト列の前記部分集合内のバイト列のそれぞれについて、そのバイト列を含むファイルの前記コーパス内の１つ又は複数のファイルのファイル識別子を特定するステップを含む、
請求項１に記載のシステム。
【請求項３】
ファイルの前記コーパスは、マルウェアファイルのコーパスである
請求項２に記載のシステム。
【請求項４】
前記ファイルは、バイナリファイル又は実行可能ファイルである
請求項１に記載のシステム。
【請求項５】
前記システムは、複数のコンピューティングデバイス、及び前記１つ又は複数のプロセッサを含み、前記プログラミング命令の実行及び転置インデックスは、前記複数のコンピューティングデバイスに分散される
請求項１に記載のシステム。
【請求項６】
前記固定長の前記バイト列は、４バイトの長さを有するＮグラム（n-grams）である
請求項１に記載のシステム。
【請求項７】
前記動作は、前記共通部分に含まれる前記検索の結果が、前記表示を返すステップより前の前記検索クエリを含むことを確認するステップをさらに含む
請求項１に記載のシステム。
【請求項８】
ファイルを構成する固定長のバイト列のそれぞれについて、前記固定長のバイト列を特定する転置インデックスを、そして、特定したバイト列のそれぞれについて、前記特定したバイト列を含むファイルのファイル識別子を検索するステップであって、ファイル識別子のそれぞれはセキュリティステータスに対応付けられる、ステップと、
前記検索の結果に基づいて、候補バイト列のリストを作成するステップであって、前記候補バイト列は、マルウェアステータス又は未知ステータスに対応付けられるファイル識別子を有するファイル内でのみ発見される、ステップと、
最も多くの前記ファイル識別子に対応付けられる前記候補バイト列の１つを選択するステップと、
選択された前記候補バイト列の１つからシグネチャを生成するステップと
を含む、コンピュータ実施方法。
【請求項９】
前記固定長の前記バイト列は、４バイトの長さを有するＮグラム（n-grams）である
請求項８に記載の方法。
【請求項１０】
前記検索するステップは、前記ファイルを構成する前記固定長の前記バイト列を決定するステップをさらに含む
請求項８に記載の方法。
【請求項１１】
ファイル識別子のそれぞれに対応付けられる前記セキュリティステータスは、マルウェアステータス、クリーンステータス、未知ステータス、又は、信頼性のレベルを示す他のステータスのうちの１つである
請求項８に記載の方法。
【請求項１２】
前記検索するステップは、クリーンステータスに対応付けられたファイル識別子を有するファイル内で発見されるものとして知られているバイト列をフィルタリングするステップと、前記ファイルを構成する残りのバイト列を検索するステップと、をさらに含む
請求項８に記載の方法。
【請求項１３】
前記作成するステップは、前記検索から返されるファイル識別子のそれぞれについてセキュリティステータスを判定するステップをさらに含み、前記セキュリティステータスは、前記ファイル識別子についてのメタデータである
請求項８に記載の方法。
【請求項１４】
セキュリティサービスに前記シグネチャを提供するステップをさらに含む
請求項８に記載の方法。
【請求項１５】
検索クエリとして式を受信するステップであって、前記式は、少なくとも１つの論理演算子及び少なくとも２つの検索タームを含む、ステップと、
固定長のバイト列を特定する転置インデックス内で、前記検索タームのそれぞれを構成する固定長のバイト列を、そして、特定したバイト列のそれぞれについて、前記特定したバイト列を含むファイルのファイル識別子を検索するステップと、
前記少なくとも１つの論理演算子で構築される構文ツリーを用いて、前記検索するステップの結果を評価するステップと、
前記評価するステップに基づいて前記検索クエリに対する検索結果を返すステップと
を含む、コンピュータ実施方法。
【請求項１６】
前記固定長の前記バイト列は、４バイトの長さを有するＮグラム（n-grams）である
請求項１５に記載の方法。
【請求項１７】
前記検索するステップは、検索タームのそれぞれに対応する固定長の複数のバイト列を決定するステップをさらに含む
請求項１５に記載の方法。
【請求項１８】
前記少なくとも１つの論理演算子に基づいて前記構文ツリーを構築するステップであって、前記検索タームは、前記構文ツリーのリーフとして評価され、各リーフは、前記検索タームの１つに対応付けられる１つ又は複数のバイト列を構成する、ステップをさらに含む
請求項１５に記載の方法。
【請求項１９】
前記返すステップを実行する前に、前記検索の結果に対応するファイルが前記式に当てはまることを確認するステップをさらに含む
請求項１５に記載の方法。
【請求項２０】
プログラミング命令が格納されている１つ又は複数の非一過性のコンピュータ読み取り可能な記録媒体であって、１つ又は複数のプロセッサによって実行されるとき、前記１つ又は複数のプロセッサに、
ファイルを構成する固定長のバイト列のそれぞれについて、前記固定長のバイト列を特定する転置インデックスを、そして、特定したバイト列のそれぞれについて、前記特定したバイト列を含むファイルのファイル識別子を検索するステップと、
最も少ないファイル識別子に対応付けられる前記検索するステップの検索結果の部分集合を識別するステップと、
前記検索結果の前記部分集合を構成するバイト列からファジーハッシュ（fuzzy hash）を構築するステップと
を含む動作を実行させる、コンピュータ読み取り可能な記録媒体。
【請求項２１】
前記固定長の前記バイト列は、４バイトの長さを有するＮグラム（n-grams）である
請求項２０に記載の１つ又は複数の非一過性のコンピュータ読み取り可能な記録媒体。
【請求項２２】
前記検索するステップは、前記ファイルを構成する固定長のバイト列を決定するステップをさらに含む
請求項２０に記載の１つ又は複数の非一過性のコンピュータ読み取り可能な記録媒体。
【請求項２３】
前記識別するステップは、少なくとも部分的に関連性信頼性閾値に基づく
請求項２０に記載の１つ又は複数の非一過性のコンピュータ読み取り可能な記録媒体。
【請求項２４】
前記動作は、前記ファジーハッシュをセキュリティサービスに提供するステップをさらに含む
請求項２０に記載の１つ又は複数の非一過性のコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、転置インデックスを用いたバイト列のバイナリサーチに関する。
【背景技術】
【０００２】
コンピュータ及びインターネットの利用が日々の生活のより大きな部分を形成するにつれ、コンピュータリソース、データ、プライベート情報を盗み出したり破壊したりするセキュリティエクスプロイトやサイバー攻撃が大きな問題になってきている。例えば、“マルウェア”、又は悪意あるソフトウェア（malicious software）は、様々な敵意ある又は侵入するコンピュータプログラムの形態を称するのに使われる一般用語である。マルウェアは、例えば、コンピュータの動作を混乱させ、コンピュータに格納された又はユーザによってコンピュータに提供されるセンシティブな情報にアクセスして盗み出し、或いは、コンピュータ及び／又はコンピュータのユーザにとって有害な他の活動を実行するサイバー攻撃者によって利用される。マルウェアは、コンピュータウィルス、ワーム、トロイの木馬、ランサムウェア、ルートキット、キーロガー、スパイウェア、アドウェア、ログセキュリティソフトウェア、及び他の悪意あるプログラムを含み得る。そして、マルウェアは、実行可能ファイル、ＤＬＬ（dynamic link libraries）、スクリプト、及び／又は他の種類のコンピュータプログラムの形態をとり得る。
【発明の概要】
【０００３】
マルウェアの著作者又はディストリビュータ（“敵対者（adversaries）”）は、マルウェア検出又は削除ツールによる検出を免れる目的で頻繁にマルウェアを変装させ又はわかりにくくする。その結果、プログラムがマルウェアであるかを判断するために時間を消費してしまう。
【図面の簡単な説明】
【０００４】
【図１ａ】図１ａは、バイナリファイル及び実行ファイルの内容検索、シグネチャ生成、及びファジーハッシュ生成を可能にするバイナリ検索エンジン及び転置インデックスで構成されるコンピューティングデバイスの概観例を示した図である。
【図１ｂ】図１ｂは、バイナリファイル及び実行ファイルの内容検索、シグネチャ生成、及びファジーハッシュ生成を可能にするバイナリ検索エンジン及び転置インデックスで構成されるコンピューティングデバイスの概観例を示した図である。
【図１ｃ】図１ｃは、バイナリファイル及び実行ファイルの内容検索、シグネチャ生成、及びファジーハッシュ生成を可能にするバイナリ検索エンジン及び転置インデックスで構成されるコンピューティングデバイスの概観例を示した図である。
【図１ｄ】図１ｄは、バイナリファイル及び実行ファイルの内容検索、シグネチャ生成、及びファジーハッシュ生成を可能にするバイナリ検索エンジン及び転置インデックスで構成されるコンピューティングデバイスの概観例を示した図である。
【図２】図２は、配布サービス、バイナリ検索エンジン、バイト列を含むファイルを一覧にしたバイト列の転置インデックス、及び他のサポートデータや論理、の全体又は一部を実現するように構成されたコンピューティングデバイスのコンポーネントレベルビューを示した図である。
【図３】図３は、検索クエリを受信すること、その検索クエリに対応するバイト列を転置インデックス内で検索すること、検索結果の共通部分を判定すること、及び共通部分内で特定されるファイルの表示を返すこと、を含む、バイナリ検索エンジンに関連付けられた例示的な動作を示した図である。
【図４】図４は、転置インデックス内で、ファイルを構成するバイト列を検索すること、その結果に関連付けられたファイルのセキュリティステータスに基づいて、検索結果から候補バイト列のリストを作成すること、最多のファイル識別子に関連付けられる候補バイト列を選択すること、及び候補バイト列からシグネチャを生成すること、を含む、バイナリ検索エンジンに関連付けられた例示的な動作を示した図である。
【図５】図５は、検索クエリとして式を受信すること、転置インデックス内で、式の検索タームに対応するバイト列を検索すること、式に含まれる論理演算子から構築される構文ツリーを用いて検索結果を評価すること、及び、評価に基づく検索結果を返すこと、を含む、バイナリ検索エンジンに関連付けられた例示的な操作を示した図である。
【図６】図６は、転置インデックス内で、ファイルを構成するバイト列を検索すること、最少のファイル識別子に関連付けられる検索結果の部分集合を特定すること、及び、部分集合を構成するバイト列からファジーハッシュを構築すること、を含む、バイナリ検索エンジンに関連付けられる例示的な動作を示した図である。
【発明を実施するための形態】
【０００５】
詳細な説明は、関連する図面を参照する形で記載される。図面において、参照番号の最も左側にある桁は、参照番号が最初に現れた図面を識別するものである。異なる図面の同じ参照番号は、類似又は同じアイテム又は特徴を示している。
詳細な説明
【０００６】
この開示は、部分的に、固定長のバイト列と、そのバイト列を含むファイルとを関連付ける転置インデックスを検索するための技術について説明する。検索クエリを構成するバイト列が決定されて転置インデックス内で検索され、そして、結果の共通部分が判定されて検索クエリに対する応答として返される。さらに、検索ターム及び論理演算子を含む式の形式での検索クエリが転置インデックス内で検索され、そして、論理演算子に基づいて構築される構文ツリーを用いて評価される。また、ファイルから抽出されたバイト列が転置インデックス内で検索され、そして、検索の結果がシグネチャ及びファジーハッシュの生成に利用される。
【０００７】
様々な実施例において、１つ又は複数のコンピューティングデバイスは、転置インデックスを、マルウェアファイル、バイナリファイル、実行可能ファイルなどのコーパスのような、ファイルのコーパスから生成してもよい。その生成は、ファイルのコーパスの少なくとも１つのファイル内で見つかる固定長のバイト列の少なくとも１つの部分集合、及び、バイト列の部分集合内の各バイト列についての、そのバイト列を含むファイルのコーパス内での１つ又は複数のファイルのファイル識別子、を特定することを含みうる。いくつかの実施例において、固定長のバイト列は、４バイトの長さを有するＮグラム（n-grams）である。
【０００８】
さらなる実施例において、転置インデックスは、ファイルについてのシグネチャを生成するために利用されうる。ファイルを構成する固定長のバイト列のそれぞれについて、コンピューティングデバイスは、転置インデックスを探索する。また、転置インデックス又は関連するデータは、各ファイル識別子について、そのファイル識別子のファイルに関連付けられたセキュリティステータスを特定してもよい。次に、コンピューティングデバイスは、マルウェアステータス又は未知ステータスに関連付けられたファイル内でのみ候補バイト列が発見されたという、検索の結果に基づいて、候補バイト列のリストを生成する。コンピューティングデバイスは、最多のファイル識別子に関連付けられた候補バイト列を選択し、そして、選択した候補バイト列からシグネチャを生成する。
【０００９】
いくつかの実施例において、上記のように、検索クエリは、少なくとも２つの検索ターム及び少なくとも１つの論理演算子を含む式のような、式を含みうる。式の受信に応じて、コンピューティングデバイスは、各検索タームを構成する固定長のバイト列のそれぞれについて転置インデックスを検索しうる。次に、コンピューティングデバイスは、少なくとも１つの論理演算子から構築される構文ツリーを用いて結果を評価し、そして、その評価に基づいて検索クエリに対する検索結果を返す。
【００１０】
様々な実施例において、コンピューティングデバイスは、ファイルについてのファジーハッシュの作成に転置インデックスを利用してもよい。ファイルを構成する固定長のバイト列のそれぞれについて、コンピューティングデバイスは、転置インデックスを検索する。次に、コンピューティングデバイスは、最少のファイル識別子（しかし、０個より多いファイル識別子を有するもの）に関連付けられた検索結果の部分集合を特定し、そして、その部分集合を構成するバイト列からファジーハッシュを構築する。また、結果的にファジーハッシュを構築するために用いたバイト列は、転置インデックスの固定長バイト列とは異なる長さを有するかもしれない。
実例概要
【００１１】
図１ａー図１ｄは、バイナリファイル及び実行可能ファイルの内容検索、シグネチャ生成、及びファジーハッシュ生成を可能にするバイナリ検索エンジン及び転置インデックスで構成されるコンピューティングデバイスの概観例を示した図である。
【００１２】
図１ａー図１ｄに示したコンピューティングデバイス１０２は、サーバ又はサーバファーム、多重、分散サーバファーム、メインフレーム、ワークステーション、ＰＣ（personal computer）、ラップトップコンピュータ、タブレットコンピュータ、ＰＤＡ（personal digital assistant）、セルラフォン、メディアセンタ、組込みシステム、又は、任意の他の種類のデバイス又はデバイス群でありうるか、又は含みうる。いくつかの実施例において、コンピューティングデバイス１０２は、コンピューティングデバイス上で実現される仮想マシンを表しうる。コンピューティングデバイス１０２の例を図２に示し、その図を参照しながら以下で説明する。
【００１３】
様々な実施例において、コンピューティングデバイス１０２は、セキュリティサービス、調査エンティティに関連付けられてもよいし、或いは、いずれのサービス又はエンティティに関連付けられなくてもよい。図１ａ−図１ｄにブラケットで示したように、コンピューティングデバイス１０２は、バイナリ検索エンジン１０４、及び転置インデックス１０６を含みうる。転置インデックス１０６は、セキュリティサービス又は調査の取り組みによって得られるマルウェアファイルのコーパスのような、ファイルのコーパスから構築されうるし、そして、ファイルのコーパスを特定しうる。しかし、ファイルのコーパスは、バイナリファイル、実行可能ファイル、非構造化ファイルなどの、任意の種類のファイルを含みうる。いくつかの実施例において、転置インデックスは、１つのサービス又はエンティティによって作成されうるし、そして、その後に、他のサービス及び又はエンティティに提供されうる。
【００１４】
また、コンピューティングデバイス１０２は、サービスクラスタ、データセンタ、クラウドサービスなど、又はそれらの一部を含んでもよい。バイナリ検索エンジン１０４及び転置インデックス１０６は、それぞれが、単体の１つのコンピューティングデバイス１０２又は複数のコンピューティングデバイス１０２（例えば、バイナリ検索エンジン１０４又は転置インデックス１０６の多重インスタンスのようなもの）によって実現されてもよいし、コンピューティングデバイス１０２の中に分散されてもよいし（例えば、コンピューティングデバイス１０２の中に分散されるバイナリ検索エンジン１０４のモジュールがある、及び／又は、コンピューティングデバイス１０２の中に分散される転置インデックス１０６のパーツがある）、或いは、それらの任意の組み合わせであってもよい。さらに、転置インデックス１０６は、コンピューティングデバイス１０２のディスクストレージに格納されてもよい。
【００１５】
いくつかの実施例において、図１ａ−図１ｄに示したバイナリ検索エンジン１０４は、テキスト／ストリングクエリ、構造化クエリ（例えば、論理演算子を含む式）、又は、特定のバイト列のような、ユーザからの任意の種類のクエリを受け付けるように構成されうる。次に、バイナリ検索エンジン１０４は、その検索クエリから固定長のバイト列を生成してもよい。例えば、バイナリ検索エンジン１０４は、クエリを構成する、ある長さの、可能な連続したバイト列のそれぞれを特定しうる。逆に、その長さは、転置インデックスによって利用される固定長（例えば、４バイトの固定長）に対応してもよい。例えば、もし、クエリがバイト列"03 62 D1 34 12 00"に対応するならば、バイナリ検索エンジン１０４は、次のような検索される列："03 62 D1 34"、"62 D1 34 12"、及び"D1 34 12 00"を決定しうる。固定長のバイト列を決定するとき、バイナリ検索エンジン１０４は、各バイト列について転置インデックス１０６に問い合わせ、そして、その応答として、ファイル内容としてそれらバイト列を含むファイルのファイル識別子を受信する。次に、バイナリ検索エンジン１０４は、図１ａ−図１ｄを参照しながら説明する更なる任意の数の動作を実行しうる。
【００１６】
さらなる実施例において、バイナリ検索エンジン１０４又はコンピューティングデバイス１０２の他の構成要素のいずれかは、ファイルを受信でき、そして、そのファイルを構成する固定長のバイト列を決定しうる。例えば、もし、ファイルの内容がバイト列"03 62 D1 34 12 00"である場合、バイナリ検索エンジン１０４又は構成要素は、次のような検索される列："03 62 D1 34"、"62 D1 34 12"、及び"D1 34 12 00"を決定しうる。もし、追加の構成要素が上記の受信及び決定を実行するならば、その追加の構成要素は、そのバイト列をバイナリ検索エンジン１０４に提供する。次に、バイナリ検索エンジン１０４は、各バイト列について転置インデックス１０６に問い合わせることができ、そして、上述したように、その応答としてのファイル識別子を受信しうる。次に、バイナリ検索エンジン１０４は、図１ａ−図１ｄを参照しながら説明する任意の数の更なる動作をしうる。
【００１７】
様々な実施例において、転置インデックス１０６は、４バイトの固定長を有するＮグラムバイト列（例えば、4-grams）のような、固定長のバイト列を特定しうる。また、特定したバイト列のそれぞれについて、転置インデックスは、ファイル内容としてその特定したバイト列を含むファイルの１つ又は複数のファイル識別子を特定しうる。図１ａ−図１ｄは、そのような転置インデックス１０６の例を示している。
【００１８】
転置インデックス１０６は、バイナリ検索エンジン１０４によって、コンピューティングデバイス１０２の他の構成要素によって、又は、他のコンピューティングデバイス１０２によって生成されうる。それは、上述したファイルのコーパスから定期的に生成又は更新されうる。それはまた、ファイルのコーパスに対する変更又は追加に応じて生成又は更新されてもよい。転置インデックス１０６を構築するために、ファイルのコーパスについてのファイルの１つで出くわす固定長のバイト列のそれぞれは、転置インデックス１０６によって特定されるバイト列に追加される。バイト列に出くわすとき、生成する構成要素は、バイト列が既に特定されているか否かを判定してもよい。もし、それが特定されているならば、現在処理しているファイルのファイル識別子は、その特定されたバイト列に関連付けられる。もし、それが特定されていないならば、それは追加され、そして、現在処理しているファイルのファイル識別子は、その追加したバイト列に関連付けられる。
【００１９】
図１ａに示すように、コンピューティングデバイス１０２のバイナリ検索エンジン１０４は、ユーザ１０８から、検索クエリ１１０を受信しうる。次に、バイナリ検索エンジン１０４は、転置インデックス１０６内で検索を実行でき、結果を処理し、そして、検索結果１１２をユーザ１０８に応答しうる。検索クエリ１１０は、テキスト／ストリング、構造化クエリ／式、又は上述したバイト列のうちの任意のものでありうる。バイナリ検索エンジン１０４は、検索クエリ１１０に対応する固定長のバイト列を決定でき、決定したバイト列のそれぞれについて転置インデックスに問い合わせでき、そして、その応答として、上述したように、それらバイト列に関連付けられたファイル識別子を取得することができる。
【００２０】
様々な実施例において、検索クエリ１１０についてのバイト列に関連付けられたファイル識別子を取得するとき、バイナリ検索エンジン１０４は、それらの結果の共通部分を判定する。例えば、もし、バイナリ検索エンジン１０４が３つのバイト列を検索し、そして、もし、第１の列がファイル識別子１、３及び４に関連付けられ、第２の列がファイル識別子１、２及び４に関連付けられ、そして、第３の列がファイル識別子１、４及び３０に関連付けられているならば、その結果の共通部分は、ファイル識別子１及び４を含むことになろう。次に、バイナリ検索エンジン１０４は、検索結果１１２として、ファイル識別子１及び４に関連付けられたファイルの表示（indication）を返す。
【００２１】
いくつかの実施例において、バイナリ検索エンジン１０４又は他の構成要素は、結果の共通部分によって特定されるファイルに関する更なる確認動作を実行しうる。例えば、ファイル識別子１及び４に関連付けられるファイルは、検索クエリ１１０に当てはまることを保証するために、それらのファイルの表示が検索結果１１２として返される前に、評価されうる。
【００２２】
図１ｂに示すように、コンピューティングデバイス１０２は、ファイル１１４を構成する固定長のバイト列を決定でき、それらバイト列について転置インデックス１０６を検索するためにバイナリ検索エンジン１０４を利用することができ、検索結果として、それらバイト列を含むファイルのファイル識別子を取得でき、それらファイルについてのセキュリティステータス１１６を決定でき、セキュリティステータス１１６及び検索結果に基づいて検索されたバイト列の部分集合を特定でき、そして、特定されたバイト列に基づくシグネチャ１１８を生成しうる。
【００２３】
いくつかの実施例において、上記のように、バイナリ検索エンジン１０４又はコンピューティングデバイス１０２の他の構成要素は、ファイル１１４を受信でき、そして、そのファイル１１４を構成する固定長のバイト列を決定できる。ファイル１１４は、上述したファイルのコーパスのファイルのような、任意の種類のファイルであってよい。
【００２４】
ファイル１１４を構成するバイト列が決定されると、バイナリ検索エンジン１０４は、各バイト列を転置インデックス１０６内で検索し、そして、検索結果として、転置インデックス１０６内で発見された、検索された各バイト列に関連付けられたファイル識別子を受信する。次に、バイナリ検索エンジン１０４又はコンピューティングデバイス１０２の他の構成要素は、各ファイル識別子に関連付けられるセキュリティステータス１１６を決定する。セキュリティステータス１１６は、ファイル識別子についてのメタデータであってもよく、そして、転置インデックス１０６又は他のデータソース内で発見されうる。各ファイル識別子についてのセキュリティステータス１１６は、ファイル識別子に関連付けられたファイルのセキュリティステータス１１６を識別する。そのようなセキュリティステータス１１６は、マルウェア（malware）ステータス、クリーン（clean）ステータス、未知（unknown）ステータス、信頼性レベルを示す他のステータスのうちの１つでありうる。
【００２５】
さらなる実施例において、ファイル１１４を構成する各バイト列を検索する前に、バイナリ検索エンジン１０４又は他の構成要素は、クリーンセキュリティステータス１１６を有するファイル内でのみ発見されるものとして知られた任意のバイト列が検索されるようにバイト列を、バイト列のリストから取り除くフィルタリングをしてもよい。そのフィルタリングに次いで、バイナリ検索エンジン１０４は、残ったバイト列についての転置インデックス１０６の検索を進めることになろう。
【００２６】
その検索に次いで、バイナリ検索エンジン１０４又は他の構成要素は、また、マルウェアセキュリティステータス１１６又は未知セキュリティステータス１１６に関連付けられたファイル内でのみ見つかる候補バイト列のリストを作成する。もし、所定のバイト列に関連付けられた任意のファイル識別子がクリーンセキュリティステータスに関連付けられるならば、その所定のバイト列は、候補バイト列のリストには含まれないだろう。
【００２７】
次に、例えば、もし、バイト列１が１０個のファイル識別子に関連付けられ、バイト列２が１個のファイル識別子に関連付けられ、バイト列３が８個のファイル識別子に関連付けられ、バイト列４が２個のファイル識別子に関連付けられ、バイト列５が１個のファイル識別子に関連付けられているならば、バイト列１及び３が選択されうる。
【００２８】
次に、バイナリ検索エンジン１０４又はコンピューティングデバイス１０２の他の構成要素は、候補バイト列のうち選択したものからシグネチャ１１８を生成でき、そして、シグネチャ１１８とファイル１１４とを関連付けることができる。いくつかの実施例において、次に、シグネチャ１１８は、マルウェア検出及び解析を支援するためにセキュリティサービスと共有されうる。
【００２９】
図１ｃに示したように、コンピューティングデバイス１０２のバイナリ検索エンジン１０４は、検索クエリとして、ユーザ１０８から式１２０を受信しうる。次に、バイナリ検索エンジン１０４は、転置インデックス１０６内で検索を実行でき、式１２０に含まれる論理演算子から構築される構文ツリー１２２を用いて検索の結果を評価でき、そして、その評価に基づいて検索結果１２４をユーザ１０８に返すことができる。
【００３０】
式１２０は、少なくとも２つの検索ターム及び少なくとも１つの論理演算子を含みうる。例えば、式１２０は、"includes 'hello' AND 'world'"のようなものを含みうる。その式１２０の中で、"hello"及び"world"は検索タームであり、ANDは論理演算子である。式１２０を受信するとき、バイナリ検索エンジン１０４は、各検索タームを構成する固定長のバイト列を決定でき、それらバイト列で転置インデックス１０６に問い合わせしうる。
【００３１】
また、バイナリ検索エンジン１０４又はコンピューティングデバイス１０２の他の構成要素は、式１２０に含まれる論理演算子に基づいて構文ツリー１２２を構築しうる。式１２０の検索タームは、構文ツリー１２２のリーフになる。
【００３２】
様々な実施例において、構文ツリー１２２を構築し、そして、検索タームを構成するバイト列を検索するとき、バイナリ検索エンジン１０４又は他の構成要素は、検索結果１２４を決定するための構文ツリー１２２を用いて、その検索の結果を評価する。次に、それら検索結果１２４は、ユーザ１０８に返される。
【００３３】
いくつかの実施例において、バイナリ検索エンジン１０４又は他の構成要素は、検索結果１２４を返す前に、検索結果１２４として特定された各ファイルが式１２０に当てはまることを保証するための確認動作を実行する。
【００３４】
図１ｄに示すように、コンピューティングデバイスは、ファイル１２６を構成するバイト列を決定でき、バイナリ検索エンジン１０４を用いて、これらバイト列を転置インデックス１０６内で検索でき、最少のファイル識別子に関連付けられたバイト列を特定でき、そして、それらバイト列からファジーハッシュ１２８を構築しうる。
【００３５】
いくつかの実施例において、上記のように、バイナリ検索エンジン１０４又はコンピューティングデバイス１０２の他の構成要素は、ファイル１２６を受信でき、そして、そのファイル１２６を構成する固定長のバイト列を決定しうる。ファイル１２６は、上述したファイルのコーパスのファイルのような、任意の種類のファイルであってよい。
【００３６】
ファイル１２６を構成するバイト列が決定されると、バイナリ検索エンジン１０４は、各バイト列を転置インデックス１０６内で検索し、そして、検索結果として、転置インデックス１０６内で見つかった、検索した各バイト列に関連付けられたファイル識別子を受信する。
【００３７】
様々な実施例において、次に、バイナリ検索エンジン１０４又は他の構成要素は、各バイト列に関連付けられるファイル識別子の数を判定し、そして、最少数のファイル識別子を有する上位ｎ個（例えば、トップ２又はトップ３）のバイト列（但し、０個を超えるファイル識別子を有するもの）を選択する。例えば、バイト列１が１０個のファイル識別子に関連付けられ、バイト列２が１個のファイル識別子に関連付けられ、バイト列３が８個のファイル識別子に関連付けられ、バイト列４が２個のファイル識別子に関連付けられ、そして、バイト列５が１個のファイル識別子に関連付けられているならば、バイト列２及び５が選択されうる。上位ｎ個のバイト列を選択する中で用いられる関連性信頼性閾値は、特定のバイト列が、それが現れるファイルについて相対的にユニークであること、つまりそのファイル及びその僅かに異なるものには現れるが他のファイルには現れないことの、望まれる信頼レベルに基づいて決定されうる。
【００３８】
次に、選択したバイト列は、後にセキュリティサービスに提供されうるファジーハッシュ１２８を構築するために利用される。また、ファジーハッシングに用いるバイト列の長さは、転置インデックスのバイト列の固定長とは異なってもよい。例えば、転置インデックスは、４バイトの固定長を有するバイト列を用いてもよいが、ファジーハッシングに用いるバイト列が１０バイトの長さになることもありうる。
システム例
【００３９】
図２は、分散サービス、バイナリ検索エンジン、その列を含むファイルをリスト化したバイト列の転置インデックス、及び、他のサポートデータ及び論理の全部又は一部を実現するように構成された、コンピューティングデバイスのコンポーネントレベルビューを示した図である。説明したように、コンピューティングデバイス２０２は、バイナリ検索エンジン２０６及び他のモジュール及びデータ２０８を格納するシステムメモリ２０４、そして、転置インデックス２１２を格納するディスクストレージ２１０を含む。また、コンピューティングデバイス２０２は、プロセッサ２１４、リムーバブルストレージ２１６、及び非リブ−バブルストレージ２１８、入力デバイス２２０、出力デバイス２２２、及び、ネットワークインターフェース２２４を含む。
【００４０】
様々な実施形態において、システムメモリ２０４は、揮発性（ＲＡＭのような）、不揮発性（ＲＯＭ、フラッシュメモリなどのような）、又は、それら２つのいくつかの組合せである。バイナリ検索エンジン２０６は、ここでさらに説明する類似名称の構成要素の一例である。他のモジュール及びデータ２０８は、さらに図１−図６に関して説明された機能をサポートする。
【００４１】
ディスクストレージ２１０は、例えば、磁気ディスク、光ディスク、又はテープのようなデータストレージデバイス（リムーバブル及び／又は非リムーバブル）を含みうる。そうしたストレージデバイスは、不揮発性メモリ（ＲＯＭ、フラッシュメモリなどのようなもの）を含みうる。転置インデックス２１２は、ここでさらに説明する類似名称の構成要素の一例である。転置インデックス２１２がディスクストレージ２１０に格納されるように示されているけれど、転置インデックス２１２は、その全体又は一部が、システムメモリ２０４又は任意の他の種類のメモリ又はストレージに格納されてもよいことは理解されよう。
【００４２】
いくつかの実施形態において、プロセッサ２１４は、ＣＰＵ（central processing unit）、ＧＰＵ（graphics processing unit）、又は、ＣＰＵとＧＰＵの両方、又は、当該分野で知られた他のプロセッシングユニット若しくは構成要素を含む。
【００４３】
また、コンピューティングデバイス２０２は、例えば、磁気ディスク、光学ディスク、又はテープのような、追加のデータストレージデバイス（リムーバブル及び／又は非リムーバブル）を含む。そのような追加のストレージは、図２においてリムーバブルストレージ２１６及び非リムーバブルストレージ２１８によって表現されている。非一過性のコンピュータ読み取り可能な媒体は、コンピュータ読み取り可能な命令、データ構造、プログラムモジュール、又は他のデータのような、情報の格納のための任意の方法又は技術で実現される揮発性及び非揮発性の、リムーバブル及び非リムーバブルのメディアを含みうる。システムメモリ２０４、ディスクストレージ２１０、リムーバブルストレージ２１６、及び非リムーバブルストレージ２１８は全て、非一過性のコンピュータ読み取り可能な記録媒体の一例である。非一過性のコンピュータ読み取り可能な記録媒体は、それに限定されるものではないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、又は他のメモリ技術、ＣＤ−ＲＯＭ、ＤＶＤ（digital versatile disks）、又は他の光ストレージ、磁気カセット、磁気テープ、磁気ディスクストレージ、又は他の磁気ストレージデバイス、或いは、望まれる情報を格納するために用いることができ、そして、コンピューティングデバイス２０２によりアクセス可能な任意の他の非一過性の媒体を含む。そのような任意の非一過性のコンピュータ読み取り可能な媒体は、コンピューティングデバイス２０２の一部でありうる。
【００４４】
また、コンピューティングデバイス２０２は、キーボード、マウス、タッチセンサ付きディスプレイ、音声入力デバイスなどのような入力デバイス２２０、及び、ディスプレイ、スピーカ、プリンタなどのような出力デバイス２２２を有する。これらのデバイスは、当該分野で良く知られたものであり、そして、ここでの詳細な議論を必要としない。
【００４５】
また、コンピューティングデバイス２０２は、ここで議論されるような、１つ又は複数のネットワークを介して他のデバイスと通信することを可能にするネットワークインターフェース２２４を含む。
処理例
【００４６】
図３−図６は、処理例を示した図である。これらの処理は、論理フローグラフのように記載され、その各動作は、ハードウェア、ソフトウェア、又はこれらの組合せにより実現されうる動作シーケンスを表す。ソフトウェアの環境において、動作は、１つ又は複数のプロセッサによって実行されるときに、記述された動作を行うようにする、１つ又は複数のコンピュータ読み取り可能な媒体に格納されたコンピュータ実行可能命令を表す。概して、コンピュータ実行可能命令は、特定の機能を実行するか、又は、特定の抽象的なデータタイプを与える、ルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。動作を記述する順序は限定的に解釈されることを意図しておらず、そして、任意の数の記述された動作は、任意の順番で及び／又は並列に、その処理を実施するために結合されうる。
【００４７】
図３は、検索クエリを受信するステップ、転置インデックスにおいて、その検索クエリに対応するバイト列を検索するステップ、検索結果の共通部分を判定するステップ、そして、その共通部分で特定されるファイルの表示を返すステップ、を含む、バイナリ検索エンジンに関連付けられた動作例を示した図である。
【００４８】
３０２において、動作は、１つ又は複数のプロセッサを含むシステムにより、マルウェアファイルのコーパスのような、ファイルのコーパスから転置インデックスを生成するステップを含む。そのファイルは、バイナリファイル又は実行可能ファイルでありうる。上記の生成するステップは、ファイルのコーパスの少なくとも１つのファイルで見つかる固定長のバイト列についての少なくとも１つの部分集合と、バイト列の部分集合内の各バイト列について、そのバイト列を含むファイルのコーパスにおける１つ又は複数のファイルのファイル識別子と、を特定するステップを含みうる。いくつかの実施例において、固定長のバイト列は、４バイトの長さを有するＮグラム（n-grams）である。さらに、１つ又は複数のプロセッサは、図３に示した動作を実行するための実行可能命令及び転置インデックスと共に、複数のコンピューティングデバイスに分散配置されてもよい。
【００４９】
３０４において、システムは、検索クエリを受信しうる。
【００５０】
３０６において、システムは、検索クエリに対応する固定長の複数のバイト列を決定しうる。
【００５１】
３０８において、システムは、固定長のバイト列を特定する転置インデックス内で各バイト列を、そして、特定した各バイト列について、特定したバイト列を含むファイルのファイル識別子を検索しうる。
【００５２】
３１０において、システムは、上記検索の検索結果の共通部分を判定できる。
【００５３】
３１２において、システムは、共通部分に含まれる検索結果が検索クエリを含むことを確認しうる。
【００５４】
３１４において、システムは、検索クエリへの応答として、共通部分に含まれるファイル識別子に関連付けられたファイルの表示を返すことができる。
【００５５】
図４は、転置インデックス内で、ファイルを構成するバイト列を検索するステップ、これらの結果に関連付けられたファイルのセキュリティステータスに基づいて、検索結果から候補バイト列のリストを作成するステップ、最多のファイル識別子に関連付けられた候補バイト列を選択するステップ、及び、その候補バイト列からシグネチャを生成するステップ、を含む、バイナリ検索エンジンに関連付けられた動作例を示した図である。
【００５６】
４０２において、動作は、ファイルを構成する固定長のバイト列それぞれについて、固定長のバイト列を特定する転置インデックスを、そして、特定したバイト列のそれぞれについて、特定したバイト列を含むファイルのファイル識別子を検索するステップを含む。いくつかの実施例において、固定長のバイト列は、４バイトの長さを有するＮグラム（n-grams）である。さらに、各ファイル識別子は、セキュリティステータスに関連付けられていてもよい。例えば、各ファイル識別子に関連付けられたセキュリティステータスは、マルウェアステータス、クリーンステータス、未知ステータス、又は、信頼レベルを示す他のステータスの１つであってもよい。また、４０４において、検索するステップは、ファイルを構成する固定長のバイト列を決定するステップを含む。４０６において、検索するステップは、クリーンステータスに関連付けられたファイル識別子を有するファイルで見つかることが知られているバイト列をフィルタリングするステップ、及び、そのファイルを構成する残りのバイト列を検索するステップ、をさらに含む。
【００５７】
４０８において、動作は、検索の結果に基づいて、候補バイト列を作成するステップをさらに含む。ここでの候補バイト列は、マルウェアステータス又は未知ステータスに関連付けられたファイル識別子を有するファイルだけで発見されるものである。また、４１０において、作成するステップは、検索するステップから返される各ファイル識別子についてのセキュリティステータスを判定するステップを含む。そのセキュリティステータスは、ファイル識別子についてのメタデータである。
【００５８】
４１２において、動作は、最多のファイル識別子に関連付けられた候補バイト列を選択するステップを含む。
【００５９】
４１４において、動作は、候補バイト列のうち選択したものからシグネチャを生成するステップをさらに含む。
【００６０】
４１６において、動作は、シグネチャをセキュリティサービスに提供するステップを含む。
【００６１】
図５は、検索クエリとしての式を受信するステップ、その式の検索タームに対応するバイト列を転置インデックス内で検索するステップ、その式に含まれる論理演算子から構築される構文ツリーを用いて検索結果を評価するステップ、そして、その評価に基づいて検索結果を返すステップ、を含む、バイナリ検索エンジンに関連付けられた動作例を示した図である。
【００６２】
５０２において、動作は、検索クエリとしての式を受信するステップを含む。式は、少なくとも１つの論理演算子及び少なくとも２つの検索タームを含む。
【００６３】
５０４において、動作は、検索タームのそれぞれを構成する固定長のバイト列を転置インデックス内で検索するステップをさらに含む。転置インデックスは、固定長のバイト列を、そして、特定したバイト列のそれぞれについて、特定したバイト列を含むファイルのファイル識別子を特定する。いくつかの実施例において、固定長のバイト列は、４バイトの長さを有するＮグラム（n-grams）である。また、５０６において、検索は、各検索タームに対応する固定長の複数のバイト列を決定するステップを含む。
【００６４】
５０８において、動作は、少なくとも１つの論理演算子に基づいて構文ツリーを構築するステップを含む。検索タームは、構文ツリーのリーフとして評価され、各リーフは、検索タームの１つに関連付けられた１つ又は複数のバイト列を構成する。
【００６５】
５１０において、動作は、少なくとも１つの論理演算子から構築された構文ツリーを用いて検索の結果を評価するステップをさらに含む。
【００６６】
５１２において、動作は、検索結果に対応するファイルが式に当てはまることを確認するステップを含む。
【００６７】
また、５１４において、動作は、少なくとも部分的に上記評価に基づいて、検索クエリに対して検索結果を返すステップを含む。
【００６８】
図６は、ファイルを構成するバイト列を転置インデックス内で検索するステップ、最少のファイル識別子に関連付けられた検索結果の部分集合を特定するステップ、そして、その部分集合を構成するバイト列からファジーハッシュを構築するステップ、を含む、バイナリ検索エンジンに関連付けられた動作例を示した図である。
【００６９】
６０２において、動作は、ファイルを構成する固定長のバイト列のそれぞれについて、固定長のバイト列を特定する転置インデックスを、そして、特定したバイト列のそれぞれについて、特定したバイト列を含むファイルのファイル識別子を１つ又は複数のプロセッサにより検索するステップを含む。いくつかの実施例において、固定長のバイト列は、４バイトの長さを有するＮグラム（n-grams）である。また、６０４において、検索するステップは、ファイルを構成する固定長のバイト列を決定するステップを含む。
【００７０】
６０６において、１つ又は複数のプロセッサは、最少のファイル識別子に関連付けられた上記検索するステップでの検索結果の部分集合を特定する。この特定するステップは、少なくとも部分的に、関連性信頼性閾値に基づいていてもよい。
【００７１】
６０８において、１つ又は複数のプロセッサは、検索結果の部分集合を構成するバイト列からファジーハッシュを構築する。
【００７２】
６１０において、１つ又は複数のプロセッサは、セキュリティサービスにファジーハッシュを提供する。
まとめ
【００７３】
構造的特徴及び／又は方法論的な行為に特化した用語で構成要素が記述されたけれども、添付の特許請求の範囲で定義される構成要素は、説明した特定の特徴又は行為に必ずしも限定されるものでないことは理解されよう。むしろ、特定の特徴及び行為は、特許請求の範囲を実現する例示的な形態として開示される。
【図１ａ】
2018113034.tif 000003
【図１ｂ】
2018113034.tif 000004
【図１ｃ】
2018113034.tif 000005
【図１ｄ】
2018113034.tif 000006
【図２】
2018113034.tif 000007
【図３】
2018113034.tif 000008
【図４】
2018113034.tif 000009
【図５】
2018113034.tif 000010
【図６】
2018113034.tif 000011