(57)【要約】【課題】複数のデータブロック内における或るパターンを検出する方法を提供すること。【解決手段】本発明による、複数のデータブロック内のパターンを検出する方法は、一組の選択されたパターンのうちの複数のパターンからなる第１部分集合を含む第１データベースを生成するステップと、残りのパターンの第２部分集合を含む第２データベースを生成するステップと、複数のデータブロックを受け取り、データブロックごとに処理して第１出力を出力するステップと、データブロックを第２データベースと比較するのに連想メモリ（ＣＡＭ）を使用して処理して第２出力を出力するステップと、第１出力及び第２出力を合成し、いずれかの出力がデータブロックが選択されたパターンを含むことを示す場合に、データブロックが選択されたパターンを含むことを示すフラグを出力するステップとを含む【選択図】図１
2010506322.tif 000002
【特許請求の範囲】
【請求項１】
複数のデータブロック内のパターンを検出する方法であって、
一組の選択されたパターンのうちの複数のパターンからなる第１部分集合を含む第１データベースを生成するステップと、
前記一組の選択されたパターンのうちの残りのパターンからなる第２部分集合を含む第２データベースを生成するステップと、
前記複数のデータブロックを受け取り、前記データブロックごとに、
前記データブロック及びハッシュ関数を使用してキーを生成し、
前記キーを使用して前記第１データベースを検索し、
前記キーに対応する前記第１データベースのエントリを特定し、
前記キーを生成する選択されたパターン若しくは０を含む前記エントリの内容を読み取り、
前記エントリの内容が０を含む場合に、前記データブロックが選択されたパターンを含まないと判定し、前記データブロックが選択されたパターンを含まないことを示す第１出力を出力し、又は、
前記エントリの内容が選択されたパターンを含む場合に、前記データブロックが前記選択されたパターンを含むと判定し、前記データブロックが前記選択されたパターンを含むことを示す第１出力を出力し、又は、
前記データブロックが前記選択されたパターンを含まないと判定し、前記データブロックが前記選択されたパターンを含まないことを示す第１出力を出力する、
ステップと、
連想メモリ（ＣＡＭ）を使用して前記データブロックを前記第２データベースと比較して、
前記データブロックが前記第２データベース内の選択されたパターンと一致すると判定し、前記データブロックが前記選択されたパターンを含むことを示す第２出力を出力し、又は、
前記データブロックが前記第２データベース内の選択されたパターンと一致しないと判定し、前記データブロックが選択されたパターンを含まないことを示す第２出力を出力する、
ステップと
前記第１出力及び第２出力を合成し、いずれかの出力が、前記データブロックが選択されたパターンを含むことを示す場合に、前記データブロックが前記選択されたパターンを含むことを示すフラグを出力するステップと
を含む方法。
【請求項２】
一組の選択されたパターンのうちの複数のパターンからなる第１部分集合のパターンを含む前記第１データベースを生成する前記ステップが、
可能性のある各データブロックを判定する工程と、
可能性のある各データブロック及び前記ハッシュ関数を使用して、複数のキーを生成する工程と、
キーを生成する前記データブロックを、前記一組の選択されたパターンと比較する工程と、
前記データブロックが選択されたパターンを含まない場合に、前記キー及び０を含む前記第１データベースのエントリを生成する工程、又は、前記データブロック又はそのいずれかが選択されたパターンを含む場合に、前記キーと、選択されたパターンを含む前記データブロック又はそのうちの１つと、前記データブロックの識別子（ＩＤ）とを含む前記第１データベースのエントリを生成する工程と
を含む、請求項１に記載の方法。
【請求項３】
一組の選択されたパターンのうちの残りのパターンからなる第２部分集合を含む前記第２データベースを生成する前記ステップが、前記第２データベースのエントリを生成する工程を含み、
前記第２データベースのエントリが、前記第１データベースのエントリに格納されない選択されたパターンを含む前記データブロックのそれぞれを備える、請求項１又は２に記載の方法。
【請求項４】
キーを生成する前記ステップが、前記データブロックに関して圧縮されたキーを生成する工程を含む、請求項１〜３のいずれか一項に記載の方法。
【請求項５】
前記データブロックが選択されたパターンを含むか否かを判定するステップが、前記データブロックを前記選択されたパターンと比較して、前記データブロックと前記選択されたパターンとが一致するか否か判定する工程を含む、請求項１〜４のいずれか一項に記載の方法。
【請求項６】
データブロックの任意の位置から始まるパターンを検出するために使用される、請求項１〜５のいずれか一項に記載の方法。
【請求項７】
様々な長さを有する選択されたパターンを検出するために使用される、請求項１〜６のいずれか一項に記載の方法。
【請求項８】
前記選択されたパターンが、単語全体若しくは部分的な単語、ストリング全体若しくは部分的ストリング、ＤＮＡ配列全体若しくは部分的ＤＮＡ配列、又は悪意のある内容のシグネチャ若しくはシグネチャセグメントのうちのいずれかを含む、請求項１〜７のいずれか一項に記載の方法。
【請求項９】
複数のデータブロック内のパターンを検出するパターン検出回路であって、
複数のハッシュモジュールと、複数のＣＡＭモジュールと、コンバイナモジュールとを備え、
前記ハッシュモジュールの各々が、一組の選択されたパターンのうちの複数のパターンからなる第１部分集合を含む第１データベースを有するものであり、
前記ハッシュモジュールが、前記複数のデータブロックを受け取るものであり、前記データブロックごとに、
前記データブロック及びハッシュ関数を使用してキーを生成し、
前記キーを使用して前記第１データベースを検索し、
前記キーに対応する前記第１データベースのエントリを特定し、
前記キーを生成する選択されたパターン若しくは０を含む前記エントリの内容を読み取り、
前記エントリの内容が０を含む場合に、前記データブロックが選択されたパターンを含まないと判定し、前記データブロックが選択されたパターンを含まないことを示す第１出力を出力し、又は、
前記エントリの内容が選択されたパターンを含む場合に、前記データブロックが前記選択されたパターンを含むと判定し、前記データブロックが前記選択されたパターンを含むことを示す第１出力を出力し、又は、
前記データブロックが前記選択されたパターンを含まないと判定し、前記データブロックが前記選択されたパターンを含まないことを示す第１出力を出力する、
ものであり、
前記ＣＡＭモジュールの各々が、前記一組の選択されたパターンのうちの残りのパターンからなる第２部分集合を含む第２データベースを備え、
前記ＣＡＭモジュールの各々が、前記複数のデータブロックを受け取り、前記データブロックごとに、
前記データブロックを前記第２データベースと比較し、
前記データブロックが前記第２データベース内の選択されたパターンと一致すると判定し、前記データブロックが前記選択されたパターンを含むことを示す第２出力を出力し、又は、
前記データブロックが前記第２データベース内の選択されたパターンと一致しないと判定し、前記データブロックが選択されたパターンを含まないことを示す第２出力を出力する、
ものであり、
前記コンバイナモジュールが、前記第１出力及び前記第２出力を合成し、いずれかの出力が、前記データブロックが選択されたパターンを含むことを示す場合に、前記データブロックが前記選択されたパターンを含むことを示すフラグを出力するものである、回路。
【請求項１０】
前記ハッシュモジュールの各々が、ＲＡＭデバイスを備える、請求項９に記載の回路。
【請求項１１】
前記ＲＡＭデバイスの各々が、前記第１データベースを格納する、請求項１０に記載の回路。
【請求項１２】
前記キーが、前記ＲＡＭデバイスの複数のメモリ位置に割り当てられたアドレスを検索するためのアドレスとして前記キーを使用することによって、前記ＲＡＭデバイスの前記第１データベースを検索するために使用される、請求項１１に記載の回路。
【請求項１３】
前記ハッシュモジュールの各々は、それぞれがキーを生成するためにデータブロック及び前記ハッシュ関数を使用する複数のハッシュデバイスを備える、請求項９〜１２のいずれか一項に記載の回路。
【請求項１４】
前記ＣＡＭモジュールの各々が、複数のＣＡＭセルを備える、請求項９〜１３のいずれか一項に記載の回路。
【請求項１５】
前記ＣＡＭセルの各々が、前記第２データベースのパターンを含むデータブロックを格納する、請求項１４に記載の回路。
【請求項１６】
前記ＣＡＭセルの各々は、それぞれが受け取られたデータブロックを前記ＣＡＭセルに格納された前記データブロックと比較する複数のコンパレータを備える、請求項１５に記載の回路。
【請求項１７】
データブロックの任意の位置から始まるパターンを検出する、請求項９〜１６のいずれか一項に記載の回路。
【請求項１８】
前記パターン検出回路が、複数のハッシュデバイス及び複数のＣＡＭコンパレータを備え、
第１のデータブロックが、第１ハッシュデバイス及び第１ＣＡＭコンパレータに入力され、前記第１のデータブロックに関してシフトされた第２のデータブロックが、第２ハッシュデバイス及び第２ＣＡＭコンパレータに入力され、以下同様である、請求項１７に記載の回路。
【請求項１９】
前記第２のデータブロックが、前記第１のデータブロックに関して前記データブロックの１つ又は複数の位置だけシフトされる、請求項１８に記載の回路。
【請求項２０】
前記第１のデータブロック及び前記第２のデータブロックが、ビット又はバイトを備え、前記第２のデータブロックが、前記第１のデータブロックに関して前記データブロックの１つ又は複数のビット又はバイトを含む１つ又は複数の位置だけシフトされる、請求項１９に記載の回路。
【請求項２１】
長さｎのパターンを検出する第１部分、長さｎ−１のパターンを検出する第２部分、長さｎ−２のパターンを検出する第３部分など、複数の部分を備える、請求項９〜２０のいずれか一項に記載の回路。
【請求項２２】
前記選択されたパターンが、単語全体若しくは部分的単語、ストリング全体若しくは部分的ストリング、ＤＮＡ配列全体若しくは部分的ＤＮＡ配列、又は悪意のある内容のシグネチャ若しくはシグネチャセグメントのうちのいずれかを含む、請求項９〜２１のいずれか一項に記載の回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パターンの検出に関する。
【背景技術】
【０００２】
情報内のパターンを検出する能力が望まれる多数の応用例がある。これには、特定のパターン又はストリングが選択され、情報から、一致するパターン又はストリングが検索される、ストリング照合が含まれる。これは、多数の分野、たとえば、文書検索、レコード検索、セキュリティ（たとえば、データメッセージ又は音声メッセージから、特定の１つ又は複数の単語或いは単語のシーケンスを含むパターンが検索される場合がある）で応用される。パターン検出が使用される他の応用例は、ＤＮＡ塩基配列決定などの生物学応用例と、正規表現処理、ＩＰパケット分類、及びディープパケットインスペクション（ｄｅｅｐ  ｐａｃｋｅｔ  ｉｎｓｐｅｃｔｉｏｎ）などの電気通信産業での様々な応用を含む。後者の応用では、パケットを、たとえば、ウィルス又はワームなどの悪意のある内容に見られるパターンの存在について、点検することができる。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
パターン検出の応用は、非常に広く行きわたっているので、検出の改善、たとえば検出の速度の改善が、常に求められている。
【課題を解決するための手段】
【０００４】
本発明の第１の態様によれば、複数のデータブロック内のパターンを検出する方法であって、
一組の選択されたパターンのうちの複数のパターンからなる第１部分集合を含む第１データベースを生成するステップと、
前記一組の選択されたパターンのうちの残りのパターンからなる第２部分集合を含む第２データベースを生成するステップと、
複数のデータブロックを受け取り、データブロックごとに、
キーを生成するためにデータブロック及びハッシュ関数を使用し、
第１データベースを検索するためにキーを使用し、
キーに対応する第１データベースのエントリを特定し、
キーを生成する選択されたパターン若しくは０を含むエントリの内容を読み取り、
エントリの内容が０を含む場合に、データブロックが選択されたパターンを含まないと判定し、データブロックが選択されたパターンを含まないことを示す第１出力を出力し、又は、
エントリの内容が選択されたパターンを含む場合に、データブロックが選択されたパターンを含むと判定し、データブロックが選択されたパターンを含むことを示す第１出力を出力し、又は、
データブロックが選択されたパターンを含まないと判定し、データブロックが選択されたパターンを含まないことを示す第１出力を出力する、
ステップと、
データブロックを第２データベースと比較するのに連想メモリ（ＣＡＭ）を使用して、
データブロックが第２データベース内の選択されたパターンと一致すると判定し、データブロックが選択されたパターンを含むことを示す第２出力を出力し、又は、
データブロックが第２データベース内の選択されたパターンと一致しないと判定し、データブロックが選択されたパターンを含まないことを示す第２出力を出力する、
ステップと、
第１出力及び第２出力を合成し、いずれかの出力がデータブロックが選択されたパターンを含むことを示す場合に、データブロックが選択されたパターンを含むことを示すフラグを出力するステップと
を含む方法が提供される。
【０００５】
一組の選択されたパターンのうちの複数のパターンからなる第１部分集合を含む第１データベースを生成するステップは、各可能性のあるデータブロックを判定するステップと、複数のキーを生成するために各可能性のあるデータブロック及びハッシュ関数を使用するステップと、キーを生成する又は各データブロックを、一組の選択されたパターンと比較するステップと、又は各データブロックが選択されたパターンを含まない場合に、キー及び０を含む第１データベースのエントリを生成し、或いは、データブロック又はそのいずれかが選択されたパターンを含む場合に、キー、選択されたパターンを含むデータブロック又はそのうちの１つ、及びデータブロックの識別子（ＩＤ）を含む第１データベースのエントリを生成するステップとを含むことができる。
【０００６】
一組の選択されたパターンのうちの残りのパターンからなる第２部分集合を含む第２データベースを生成するステップは、第１データベースのエントリに格納されない選択されたパターンを含むデータブロックのそれぞれを含む第２データベースのエントリを生成するステップを含むことができる。
【０００７】
キーを生成するステップは、データブロックに関して圧縮されたキーを生成するステップを含むことができる。圧縮された鍵の生成は、減らされたメモリ要件をもたらす。
【０００８】
データブロックが選択されたパターンを含む又は含まないと判定するステップは、データブロックと選択されたパターンとの間の一致が発生するのか発生しないのかを判定するためにデータブロックを選択されたパターンと比較するステップを含むことができる。
【０００９】
第１及び第２の出力を合成することは、出力を多重化することを含むことができる。
【００１０】
この方法を、データブロックの任意の位置から始まるパターンを検出するのに使用することができる。この方法を、様々な長さを有する選択されたパターンを検出するのに使用することができる。
【００１１】
本発明の第２の態様によれば、複数のデータブロック内のパターンを検出するパターン検出回路であって、
複数のハッシュモジュールと、複数のＣＡＭモジュールと、コンバイナモジュールとを備え、
ハッシュモジュールの各々が、一組の選択されたパターンのうちの複数のパターンからなる第１部分集合を含む第１データベースを有するものであり、
ハッシュモジュールが、複数のデータブロックを受け取るものであり、データブロックごとに、
データブロック及びハッシュ関数を使用してキーを生成し、
キーを使用して前記第１データベースを検索し、
キーに対応する前記第１データベースのエントリを特定し、
キーを生成する選択されたパターン若しくは０を含む前記エントリの内容を読み取り、
エントリの内容が０を含む場合に、データブロックが選択されたパターンを含まないと判定し、データブロックが選択されたパターンを含まないことを示す第１出力を出力し、又は、
エントリの内容が選択されたパターンを含む場合に、データブロックが選択されたパターンを含むと判定し、データブロックが選択されたパターンを含むことを示す第１出力を出力し、又は、
データブロックが選択されたパターンを含まないと判定し、データブロックが選択されたパターンを含まないことを示す第１出力を出力する、
ものであり、
ＣＡＭモジュールの各々が、一組の選択されたパターンのうちの残りのパターンからなる第２部分集合を含む第２データベースを備え、
ＣＡＭモジュールの各々が、複数のデータブロックを受け取り、データブロックごとに、
データブロックを第２データベースと比較し、
データブロックが第２データベース内の選択されたパターンと一致すると判定し、データブロックが選択されたパターンを含むことを示す第２出力を出力し、又は、
データブロックが第２データベース内の選択されたパターンと一致しないと判定し、データブロックが選択されたパターンを含まないことを示す第２出力を出力する、
ものであり、
コンバイナモジュールが、第１出力及び第２出力を合成し、いずれかの出力が、データブロックが選択されたパターンを含むことを示す場合に、データブロックが選択されたパターンを含むことを示すフラグを出力するものである、回路が提供される。
【００１２】
各ハッシュモジュールは、ＲＡＭデバイスを備えることができる。各ＲＡＭデバイスは、第１データベースを格納することができる。キーを、ＲＡＭデバイスの複数のメモリ位置に割り当てられたアドレスを検索するためのアドレスとしてキーを使用することによってＲＡＭデバイスの第１データベースを検索するのに使用することができる。
【００１３】
各ハッシュモジュールは、それぞれがキーを生成するためにデータブロック及びハッシュ関数を使用する複数のハッシュデバイスを備えることができる。
【００１４】
各ＣＡＭモジュールは、複数のＣＡＭセルを備えることができる。各ＣＡＭセルは、第２データベースのパターンを含むデータブロックを格納することができる。各ＣＡＭセルは、それぞれが受け取られたデータブロックをＣＡＭセルに格納されたデータブロックと比較する複数のコンパレータを備えることができる。
【００１５】
コンバイナモジュールは、マルチプレクサを含むことができる。
【００１６】
このパターン検出回路は、データブロックの任意の位置から始まるパターンを検出することができる。このパターン検出回路は、複数のハッシュデバイス及び複数のＣＡＭコンパレータを備えることができ、第１データブロックを、第１ハッシュデバイス及び第１ＣＡＭコンパレータに入力することができ、第１データブロックに関してシフトされた第２データブロックを、第２ハッシュデバイス及び第２ＣＡＭコンパレータに入力することができ、以下同様である。第２データブロックを、第１データブロックに関してブロックの１つ又は複数の位置だけシフトすることができる。たとえば、第１及び第２のデータブロックは、ビット又はバイトを備えることができ、第２データブロックを、第１データブロックに関してブロックの１つ又は複数のビット又はバイトを含む１つ又は複数の位置だけシフトすることができる。これは、データブロック内の任意の位置から始まるパターンの検出を可能にする。このパターン検出回路は、長さｎのパターンを検出する第１部分、長さｎ−１のパターンを検出する第２部分、長さｎ−２のパターンを検出する第３部分など、複数の部分を備えることができる。
【００１７】
選択されたパターンは、データブロック内のその存在を検出することが望まれる複数のパターンを含む。選択されたパターンは、単語全体若しくは部分的単語、ストリング全体若しくは部分的ストリング、ＤＮＡ配列全体若しくは部分的ＤＮＡ配列、又は悪意のある内容のシグネチャ若しくはシグネチャセグメントのうちのいずれかを含むことができる。
【００１８】
用語パターンが、任意の文字又は複数の文字を記述するのに使用され、反復的性質を有する複数の文字を意味することに限定されないことを理解されたい。
【００１９】
本発明の実施形態を、これから、例としてのみ、添付図面を参照して説明する。
【図面の簡単な説明】
【００２０】
【図１】ハッシュモジュール及びＣＡＭモジュールを備える、本発明によるパターン検出回路を示す概略図である。
【図２】図１のハッシュモジュールの一部を示す概略図である。
【図３】図１のＣＡＭモジュールの一部を示す概略図である。
【図４】本発明のシグネチャ検出回路を備えるディープパケットインスペクションシステムを示す概略図である。
【発明を実施するための形態】
【００２１】
以下の実施形態では、選択されたパターンは、悪意のある内容のシグネチャ又はシグネチャのセグメントを備えるものとする。しかし、これが例にすぎないことと、本発明が、多数のタイプのパターンの検出に適用可能であることとを了解されたい。
【００２２】
図１に、入力レジスタ１０、ハッシュモジュール１２、連想メモリ（ＣＡＭ）モジュール１４、複数のマルチプレクサ１６、及び複数の出力レジスタ１８を備える、パターン検出回路又はシグネチャ検出回路１を示す。この実施形態では、シグネチャ検出回路は、通信ネットワークのディープパケットインスペクション（ＤＰＩ）システムの一部を形成し、複数のエンティティの間で通信されるデータを受信する。データは、パケットにフォーマットされ、各パケットは、ヘッダ及びペイロードを備える。任意のパケットのペイロードが、ウィルス又はワームなど、悪意のある内容を含む場合があることが可能である。シグネチャ検出回路１は、データをチェックし、ＤＰＩシステムに対して、データ内で見つかったすべての悪意のある内容にフラグを立てる。ウィルスなどの悪意のある内容は、一般に、それぞれ、一意の識別子又はシグネチャを備える。現在まで、対応する有限の個数のシグネチャを有する有限の個数のウィルスなどが知られている。本発明のシグネチャ検出回路１は、これらのシグネチャを探すことによって、悪意のある内容についてネットワーク内のデータをチェックする。
【００２３】
ネットワークデータは、シグネチャ検出回路１の入力レジスタ１０に入力され、そこから出力され、この実施形態では、一連の４バイトデータブロックとして、この回路によって処理される。しかし、他のデータブロックサイズ、たとえば、８バイト又は１６バイトのデータブロックを使用できることを了解されたい。悪意のある内容の各シグネチャは、通常、複数のバイト、たとえば、１、２、３、４、６、８、１２、１４、１６、２４などを含む。したがって、各シグネチャが、入力レジスタ１０から出力される１つ又は複数のデータブロックにまたがって広がる可能性がある。検出されるべきシグネチャが、データブロックの長さより短い（すなわち、この実施形態では４バイト未満の）長さを有するときには、シグネチャ検出回路は、完全なシグネチャについて、受け取られたデータブロックを点検する。よりしばしばそうであるように、検出すべきシグネチャが、データブロックの長さより長い（すなわち、この実施形態では４バイトを超える）長さを有するときには、シグネチャ検出回路は、シグネチャのセグメントについて、受け取られたデータブロックを点検する。検出されたシグネチャ又はシグネチャセグメントに関する情報は、シグネチャ検出回路１から出力され、シグネチャセグメントの場合には、照合され得る。
【００２４】
シグネチャ又は第１シグネチャセグメントは、ネットワークデータ内の複数の位置から始まる可能性がある。これは、データの第１ブロックに関してシフトされた（又はオフセットされた）、たとえば１つ又は複数のバイトだけシフトされた、データのブロックを処理するようにシグネチャ検出回路１を構成することによって考慮に入れられる。この実施形態では、シグネチャ検出回路１は、４バイトのデータのブロック、たとえばｘ１、ｘ２、ｘ３、及びｘ４（シフト＝０）をハッシュモジュール１２の第１ハッシュデバイス及びＣＡＭモジュール１４の第１ＣＡＭコンパレータに入力することによってデータを処理する。１バイトだけシフトされた４バイトのデータの次のブロックすなわち、ｘ２、ｘ３、ｘ４、及びｘ５が、ハッシュモジュール１２の第２ハッシュデバイス及びＣＡＭモジュール１４の第２ＣＡＭコンパレータに入力され、ハッシュモジュール１２の各ハッシュデバイス及びＣＡＭモジュール１４の各ＣＡＭコンパレータについて、以下同様である。ハッシュモジュール１２とＣＡＭモジュール１４との両方が、悪意のある内容についてデータブロックをチェックする。これらのモジュールの出力は、複数のマルチプレクサ１６によって受け取られ、データブロック内で見つかったすべての悪意のある内容の詳細が、マルチプレクサ１６によって複数の出力レジスタ１８に出力され、これらから、通信ネットワークに出力される。
【００２５】
シグネチャ検出回路１のこの実施形態のコンポーネントの機能を、これからより詳細に説明する。
【００２６】
図２に、ハッシュモジュール１２の一部を詳細に示す。これは、第１から第４までのハッシュデバイス２０、第１から第４までのレジスタ２２、マルチプレクサ２４、ＲＡＭデバイス２６、第１から第４までのレジスタ２８、及び第１から第４までのコンパレータ３０を含む。悪意のある内容についてチェックされなければならないネットワークデータは、図示のように４バイトのブロックで、ハッシュデバイス２０のそれぞれによって受け取られる。
【００２７】
各ハッシュデバイスは、同一の形で動作し、その基本的なハッシュ関数は、４バイト（３２ビット）のデータブロックを受け取り、キーを生成することであり、このキーの値は、データブロックの値に依存し、このキーは、データブロックに関して圧縮される、すなわち、３２ビット未満を含む。この実施形態では、ハッシュデバイスによって生成される各キーが、１２ビットの長さを有する。しかし、１２以外（ただし、３２未満）のビットサイズを有するキーを生成できることを了解されたい。
【００２８】
ハッシュ関数の使用は、複数の別個のデータブロックが同一のキーを生成する、高い確率を生じる。たとえば、５つの別個のデータブロック（そのうちの３つは悪意のある内容を含み、そのうちの２つは含まない）が、同一のキーを生成する可能性がある。そのような状況を、衝突と称する。
【００２９】
ハッシュデバイス内で使用される特定のハッシュ関数が決定された時に、ソフトウェアモジュールは、そのハッシュ関数を使用して、すべての可能性のある３２ビットデータブロックについて鍵を生成する。これは、キーごとに１エントリを有するテーブルを作成することを可能にし、このエントリは、キーの値と、０又はそのキーを生成する１つ又は複数のデータブロックのいずれかとを含む。キーが、それぞれが悪意のある内容を含まない１つ又は複数のデータブロックによって生成された場合に、そのキーのエントリは、キー値及び０を含む。キーが、それぞれが既知のシグネチャのうちの１つからなるか既知のシグネチャのうちの１つの１セグメントを含む、すなわち、悪意のある内容を含む、１つ又は複数のデータブロックによって生成された場合に、そのキーのエントリは、キー値と、１つ又は複数のデータブロックのそれぞれすなわち、１つ又は複数のシグネチャ又はシグネチャセグメントのそれぞれとを含む。１つ又は複数のデータブロックのそれぞれのシグネチャＩＤ又はシグネチャセグメントＩＤのどちらであれ、適当なものも、キーのエントリに追加され、その使用は、下で説明する。１つ又は複数のデータブロックが既知のシグネチャのうちの１つからなるか既知のシグネチャのうちの１つの１セグメントを含む、すなわち、悪意のある内容を含み、１つ又は複数のデータブロックが悪意のある内容を含まない、複数のデータブロックによってキーが生成された場合に、そのキーのエントリは、キー値と、悪意のある内容を含む１つ又は複数のデータブロックのそれぞれすなわち１つ又は複数のシグネチャ又はシグネチャセグメントのそれぞれと、これらの１つ又は複数のデータブロックのそれぞれのシグネチャＩＤ又はシグネチャセグメントＩＤとを含む。したがって、ハッシュ関数の使用から生じる衝突が、記録される。
【００３０】
次に、このテーブルは、ハッシュモジュール１２のＲＡＭデバイス２６を構成するのに使用される。ＲＡＭデバイス２６は、複数のメモリ位置を備える。各メモリ位置には、次のように、キーのうちの１つと等しい値を有するアドレスと、０又はそのキーを生成する１つのデータブロックのいずれかを含む内容とが割り当てられる。キーが、それぞれが悪意のある内容を含まない１つ又は複数のデータブロックによって生成された場合に、そのキーのメモリ位置の内容は、０を含む。キーが、それぞれが既知のシグネチャのうちの１つからなるか既知のシグネチャのうちの１つの１セグメントを含む、すなわち悪意のある内容を含む１つ又は複数のデータブロックによって生成された場合に、そのキーのメモリ位置の内容は、１つ又は複数のデータブロックのうちの１つすなわち、１つ又は複数のシグネチャ又はシグネチャセグメントのうちの１つと、シグネチャＩＤ又はシグネチャセグメントＩＤとを含む。１つ又は複数のデータブロックが既知のシグネチャのうちの１つからなるか既知のシグネチャのうちの１つの１セグメントを含むすなわち悪意のある内容を含み、１つ又は複数のデータブロックが悪意のある内容を含まない、複数のデータブロックによってキーが生成された場合に、そのキーのメモリ位置の内容は、悪意のある内容を含む１つ又は複数のデータブロックのうちの１つすなわち１つ又は複数のシグネチャ又はシグネチャセグメントのうちの１つと、シグネチャ／シグネチャセグメントＩＤとを含む。後者の２つの状況から、悪意のある内容を含む複数のデータブロックが同一のキーを生成するときに、データブロックすなわちシグネチャ／シグネチャセグメントのうちの１つだけが、ＲＡＭデバイスのメモリ位置への入力のために選択されることに留意されたい。悪意のある内容を含む残りのデータブロックは、下で説明するように、ＣＡＭモジュール１４を構成するのに使用される。
【００３１】
ＲＡＭデバイス２６は、別個のキー値ごとに１つのメモリ位置を有し、したがって、可能性のあるキーの個数と等しい個数のメモリ位置を含む。各キーは、１２ビットを含む。したがって、２１２個の可能性のあるキー値がある。したがって、ＲＡＭデバイス２６は、２１２個のメモリ位置を含む。各キーは、それがそこから生成されたデータブロックに対して圧縮される、すなわち、各キーは、データブロックの３２ビットではなく１２ビットだけを含む。これは、ＲＡＭデバイス２６が、各キーが３２ビットを含む場合に必要になるはずの２３２個のメモリ位置ではなく、２１２個のメモリ位置だけを必要とすることをもたらす。したがって、シグネチャ検出回路１へのデータ入力を圧縮するのにハッシュデバイスを使用することによって、ＲＡＭデバイス２６のメモリ必要量を大幅に減らすことが可能になる。
【００３２】
動作中に、ハッシュデバイスのそれぞれは、データブロックを受け取り、キーを生成する。各ハッシュデバイスは、生成されたキーをレジスタ２２のうちの１つに出力する。次に、各レジスタは、そのキーをマルチプレクサ２４に出力する。マルチプレクサ２４は、その４つの入力のそれぞれでキーを順番に受け取らせるアドレス入力（図示せず）を受け取り、そのキーを順番にＲＡＭデバイス２６に出力する。
【００３３】
ＲＡＭデバイス２６は、キーを順番に受け取る。各キーは、メモリ位置アドレスとして使用される、すなわち、キーの値は、そのアドレス値がキーの値と一致するメモリ位置が見つかるまで、ＲＡＭデバイス２６のメモリ位置のアドレスと比較される。ＲＡＭデバイス２６の一致するメモリ位置が見つかる時に、一致するメモリ位置の内容が読み取られる。メモリ位置の内容は、０を含むか、悪意のある内容を含むデータブロックすなわちシグネチャ又はシグネチャセグメントとシグネチャ／シグネチャセグメントＩＤとを含むかのいずれかになる。この実施形態では、データブロックが３２ビット長なので、シグネチャ又はシグネチャセグメントは、３２ビット長であり、シグネチャ／シグネチャセグメントＩＤは、１２ビットの長さを有するように選択される。
【００３４】
ＲＡＭデバイス２６は、アドレッシングされたメモリ位置の内容を順番に、レジスタ２８の第１、次に第２、次に第３、次に第４のレジスタに出力する。レジスタ２８のそれぞれは、下で説明するように、ＣＡＭモジュール１４の出力との比較のために、シグネチャ検出回路１のマルチプレクサ１６（図１を参照されたい）に、０又はそれが受け取ったメモリ位置内容の１２ビットのシグネチャ／シグネチャセグメントＩＤ部分を出力する。
【００３５】
レジスタ２８のそれぞれは、図示のように、それが受け取ったメモリ位置内容の３２ビットのシグネチャ／シグネチャセグメント部分をもコンパレータ３０のうちの１つに出力する。各コンパレータは、２つの入力すなわち、オリジナルデータブロック（図示のように遅延を介して供給される）と、同一のデータブロックを使用して生成されたキーから生じるメモリ位置の内容の３２ビットシグネチャ／シグネチャセグメント部分とを受け取る。各コンパレータは、オリジナルデータブロックの値と、メモリ位置内容の３２ビットシグネチャ／シグネチャセグメント部分の値とを比較し、一致フラグを出力し、この一致フラグは、これらが同一であるとわかった場合に悪意のある内容が見つかったことを示す。
【００３６】
上で説明したシグネチャ検出回路の動作によれば、データブロックが、悪意のある内容を含まないすなわち、シグネチャを含まず、シグネチャセグメントを含まない場合に、そのデータブロックは、０のメモリ位置内容をもたらす（キーが悪意のある内容を含まない１つ又は複数のデータブロックによって生成されるとき）か、３２ビットシグネチャ／シグネチャセグメントを含むメモリ位置内容をもたらす（キーが、悪意のある内容を含まない１つ又は複数のデータブロック及び悪意のある内容を含む１つ又は複数のデータブロックによって生成されるとき）かのいずれかであるキーを生成する。どちらの場合でも、オリジナルデータブロックとのメモリ位置内容の３２ビットシグネチャ／シグネチャセグメントの比較は、これらが同一でないことがわかることをもたらし、一致フラグは生成されない、すなわち、この回路は、悪意のある内容がそのデータブロック内で見つからなかったことを示す。データブロックが、悪意のある内容を含む、すなわち、シグネチャを含むかシグネチャセグメントを含む場合に、そのデータブロックは、データブロックのシグネチャ／シグネチャセグメントと等しい３２ビットシグネチャ／シグネチャセグメントを含むメモリ位置内容（キーが、悪意のある内容を含む１つ又は複数のデータブロックによって生成され、このデータブロックが、ＲＡＭデバイスへの入力のために選択されたとき）又はデータブロックのシグネチャ／シグネチャセグメントと等しくない３２ビットシグネチャ／シグネチャセグメントを含むメモリ位置内容（キーが、悪意のある内容を含む１つ又は複数のデータブロックによって生成され、このデータブロックが、ＲＡＭデバイスへの入力のために選択されなかったとき）のいずれかをもたらすキーを生成する。第１のケースでは、オリジナルデータブロックとのメモリ位置内容の３２ビットシグネチャ／シグネチャセグメントの比較は、これらが同一であることがわかることをもたらし、一致フラグが生成され、すなわち、このシステムは、悪意のある内容がそのデータブロック内で見つかったことを示す。第２のケースでは、オリジナルデータブロックとのメモリ位置内容の３２ビットシグネチャ／シグネチャセグメントの比較は、これらが同一でないことがわかることをもたらし、一致フラグは生成されず、すなわち、このシステムは、悪意のある内容がそのデータブロック内で見つからなかったことを示す。これは、正しい表示ではないが、このシナリオは、下で説明するように、ＣＡＭモジュール１４を使用することによって考慮される。
【００３７】
図２に示されたハッシュデバイスなどは、シグネチャ検出回路１の実際のハッシュモジュール１２の第１部分だけを含む。ハッシュモジュール１２のこの第１部分は、４バイトの長さのシグネチャ又はシグネチャセグメントを検出することができる。ハッシュモジュール１２は、さらに、第２部分を含み、この第２部分は、４バイトデータブロック内で３つの上位バイトの可能性のあるシグネチャデータ及び残りのバイトの「ワイルドカード」データを有するシグネチャ／シグネチャセグメントを探すことによって、長さ３バイトのシグネチャ又はシグネチャセグメントを検出することができる。ハッシュモジュール１２は、さらに、第３部分を含み、この第３部分は、４バイトデータブロック内で２つの上位バイトの可能性のあるシグネチャデータ及び残りのバイトの「ワイルドカード」データを有するシグネチャ／シグネチャセグメントを探すことによって、長さ２バイトのシグネチャ又はシグネチャセグメントを検出することができる。ハッシュモジュール１２は、さらに、第４部分を含み、この第４部分は、長さ１バイトのシグネチャ又はシグネチャセグメントを検出することができる。ハッシュモジュールの第２部分及び第３部分は、第１部分と同一のコンポーネントを含み、同一の形で機能する。ハッシュモジュールの第４部分は、単純にＲＡＭデバイスを含み、このＲＡＭデバイスは、不相応なハードウェア要件なしで、１バイトの長さのシグネチャ又はシグネチャセグメントを検出するのに十分なメモリを提供することができる。上で説明したように、ハッシュモジュールの第１部分に入力されるデータブロックは、ハッシュモジュールの第２部分、第３部分、及び第４部分にも入力される。ハッシュモジュール１２のそのような配置は、これを使用して、可変長のシグネチャ又はシグネチャセグメントを検出することを可能にする。たとえば、検出すべきシグネチャが、４バイトの長さを有する場合に、このシグネチャは、ハッシュモジュールのすべての部分に供給され、完全なシグネチャを、ハッシュモジュール１２の第１部分によって検出でき、他の部分によって検出はされない。検出すべきシグネチャが、２バイトの長さを有する場合に、このシグネチャは、ハッシュモジュールのすべての部分に供給され、完全なシグネチャを、ハッシュモジュール１２の第３部分によって検出でき、他の部分によって検出はされない。検出すべきシグネチャが、６バイトの長さを有する場合には、ハッシュモジュールの諸部分に供給されるデータブロックが、４バイトの長さを有するので、シグネチャの最初の上位４バイトを含むシグネチャセグメントが、ハッシュモジュールのすべての部分に供給され、このシグネチャセグメントを、ハッシュモジュール１２の第１部分によって検出することができ、他の部分によって検出はされず、シグネチャの残りの２バイト及び入力データの次の２バイトを含むシグネチャセグメントが、ハッシュモジュールのすべての部分に供給され、このシグネチャセグメントを、ハッシュモジュール１２の第３部分によって検出することができ、他の部分によって検出はされない。したがって、シグネチャの両方のセグメントを、ハッシュモジュール１２によって検出し、そこから出力することができる。その後、セグメントを照合して、悪意のある内容が検出されたことを示すフラグを立てることを可能にしてもよい。
【００３８】
上で説明したように、ハッシュ関数が悪意のある内容の検出で使用されているので、衝突が発生するすなわち、複数の異なるデータブロックが同一のキーを生成する可能性が高い。ハッシュデバイス内で使用されるハッシュ関数について発生する衝突が、判定され、ＲＡＭデバイス２６が、それに従って構成される。悪意のある内容を含まないデータブロックと、悪意のある内容を含むデータブロックとが、それぞれ、同一のキーを生じる場合に、これは、シグネチャ検出回路１による悪意のある内容の検出に重要ではない。この場合には、ＲＡＭデバイス２６は、そのアドレスがキーと等しいメモリ位置が、悪意のある内容を含むデータブロックの詳細を含む内容を有するように構成され、一致フラグは、悪意のある内容を含むデータブロックについて生成される。しかし、それぞれが悪意のある内容を含む複数のデータブロックが、それぞれ同一のキーを生じる場合に、これは、シグネチャ検出回路１による悪意のある内容の検出に影響する可能性がある。この場合には、ＲＡＭデバイス２６は、そのアドレスがキーと等しいメモリ位置が、悪意のある内容を含むデータブロックのうちの１つだけを含む内容を有するようになるように構成される。上で詳細に示したように、これは、実際に悪意のある内容を含むデータブロックについて一致フラグが生成されないことをもたらし得る。そのような状況は、ＣＡＭモジュール１４によって考慮される。
【００３９】
ＣＡＭモジュール１４の一部を、図３に示す。これは、複数のＣＡＭセル４０、複数のデコーダ４２、複数のレジスタ４４、マルチプレクサ４６、ＲＡＭデバイス４８、及び複数のレジスタ５０を含む。各ＣＡＭセルは、内容レジスタ及び複数のコンパレータを含む。
【００４０】
ＣＡＭセルは、悪意のある内容を含む複数のデータブロックの衝突を扱うようにカスタマイズされる。上で述べたように、そのような衝突を生じるデータブロックは、ソフトウェアモジュールによって判定される。データブロックのうちの１つが、ハッシュモジュール１２のＲＡＭデバイス２６のメモリ位置への入力のために選択される（したがって、この選択されたデータブロックと等しいデータブロックが、シグネチャ検出回路に入力される場合に、その悪意のある内容が検出される）。残りの１つ又は複数のデータブロックは、ＣＡＭセルのうちの１つ又は複数を使用することによって考慮される。ＣＡＭセルは、１つのそのようなデータブロックを、そのデータブロックをセルの内容レジスタに格納することによって考慮するようにカスタマイズされる。したがって、ＣＡＭモジュール１４は、ｋ個のＣＡＭセルを含み、ここで、ｋは、ハッシュモジュール１２のＲＡＭデバイス２６への格納のために選択されない、悪意のある内容を含むデータブロックの個数と等しい。
【００４１】
各ＣＡＭセルは、４つのコンパレータを含む。ＣＡＭセルごとに、コンパレータのそれぞれは、前に詳細に述べたように第１データブロックに関してシフトされた、ネットワークデータの入力データブロックを受け取る。ＣＡＭセルごとに、各コンパレータは、ＣＡＭセルの内容レジスタに格納されたデータブロックをも受け取る。各コンパレータは、入力データブロックを内容レジスタデータブロックと比較し、これらが同一ではない場合には０と等しい一致を出力し、これらが同一である場合には１と等しい一致を出力する。後者の場合に、これは、入力データブロックが悪意のある内容（すなわち、シグネチャ又はシグネチャセグメント）を含むことを意味し、この入力データブロックは、衝突を生じる悪意のある内容を含むデータブロックのうちの１つと同一である。図示のように、ＣＡＭセルのそれぞれの第１コンパレータの出力は、第１デコーダに入力され、ＣＡＭセルのそれぞれの第２コンパレータの出力は、第２デコーダに入力され、以下同様である。デコーダによって受け取られる１と等しい一致ごとに、デコーダは、ＣＡＭセルのアイデンティティ及び一致を出力したＣＡＭセルのコンパレータのアイデンティティを判定し、一致の起点の位置を示す２進値を出力する。デコーダによって受け取られる０と等しい一致ごとに、デコーダは、０の２進値を出力する。
【００４２】
各デコーダは、図示のように、レジスタ４２のうちの１つに、１つ又は複数の２進位置値及び１つ又は複数の０値を出力する。次に、各レジスタは、その１つ又は複数の２進位置値及び１つ又は複数の０値をマルチプレクサ４４に出力する。マルチプレクサ４４は、その４つの入力のそれぞれで２進位置値又は０値を順番に受け取らせるアドレス入力（図示せず）を受け取り、２進位置値及び０値を順番にＲＡＭデバイス４８に出力する。
【００４３】
ＲＡＭデバイス４８は、２進位置値及び０値を順番に受け取る。各２進位置値及び０値は、メモリ位置アドレスとして使用される。０値が受け取られる時に、これは、そのアドレスが０と等しいＲＡＭデバイス４８のメモリ位置にマッピングされ、このメモリ位置の内容（０と等しい）が、レジスタ５０のうちの１つに出力される。２進位置値が受け取られる時に、この値は、そのアドレスがこの２進位置値と一致するメモリ位置が見つかるまで、ＲＡＭデバイス４８のメモリ位置のアドレスと比較される。ＲＡＭデバイス４８の一致するメモリ位置が見つかった時に、その一致するメモリ位置の内容が、レジスタ５０のうちの１つに出力される。メモリ位置の内容は、２進位置値を生成した一致を生成したデータブロックの１２ビットシグネチャ／シグネチャセグメントＩＤを含む。
【００４４】
ＲＡＭデバイス４８は、０値及び１２ビットシグネチャ／シグネチャセグメントＩＤを順番に、レジスタ５０のうちの第１レジスタ、次に第２レジスタ、次に第３レジスタ、及び次に第４レジスタに出力する。レジスタ５０のそれぞれは、下で説明する、ハッシュモジュール１２の出力との比較のために、０値及び１２ビットシグネチャ／シグネチャセグメントＩＤをマルチプレクサ１６（図１を参照されたい）に出力する。
【００４５】
ハッシュモジュール１２と同様に、図３に示されたＣＡＭデバイスなどは、シグネチャ検出回路１の実際のＣＡＭモジュール１４の第１部分だけを含む。ＣＡＭモジュール１４の第１部分は、長さ４バイトのシグネチャ又はシグネチャセグメントを検出することができる。ＣＡＭモジュール１４は、さらに、第２部分を含み、この第２部分は、４バイトデータブロック内で３つの上位バイトの可能性のあるシグネチャデータ及び残りのバイトの「ワイルドカード」データを有するシグネチャ／シグネチャセグメントを探すことによって、長さ３バイトであるシグネチャ又はシグネチャセグメントを検出することができる。ＣＡＭモジュール１４は、さらに、第３部分を含み、この第３部分は、４バイトデータブロック内で２つの上位バイトの可能性のあるシグネチャデータ及び残りのバイトの「ワイルドカード」データを有するシグネチャ／シグネチャセグメントを探すことによって、長さ２バイトであるシグネチャ又はシグネチャセグメントを検出することができる。ＣＡＭモジュール１４は、さらに、長さ１バイトであるシグネチャ又はシグネチャセグメントを検出することができる第４部分を含む。ＣＡＭモジュールの第２部分及び第３部分は、第１部分と同一のコンポーネントを含み、同一の形で機能する。ＣＡＭモジュールの第４部分は、単純にＲＡＭデバイスを含み、このＲＡＭデバイスは、不相応なハードウェア要件なしで、１バイトの長さのシグネチャ又はシグネチャセグメントを検出するのに十分なメモリを提供することができる。上で説明したように、ＣＡＭモジュールの第１部分に入力されるデータブロックは、ＣＡＭモジュールの第２部分、第３部分、及び第４部分にも入力される。ＣＡＭモジュール１４のそのような配置は、これを使用して、可変長のシグネチャ又はシグネチャセグメントを検出することを可能にする。たとえば、検出すべきシグネチャが、３バイトの長さを有する場合に、このシグネチャは、ＣＡＭモジュールのすべての部分に供給され、完全なシグネチャを、ＣＡＭモジュール１４の第２部分によって検出でき、他の部分によって検出はされない。検出すべきシグネチャが、１バイトの長さを有する場合に、このシグネチャは、ＣＡＭモジュールのすべての部分に供給され、完全なシグネチャを、ＣＡＭモジュール１４の第４部分によって検出でき、他の部分によって検出はされない。検出すべきシグネチャが、７バイトの長さを有する場合には、ＣＡＭモジュールの諸部分に供給されるデータブロックが、４バイトの長さを有するので、シグネチャの最初の上位４バイトを含むシグネチャセグメントが、ＣＡＭモジュールのすべての部分に供給され、このシグネチャセグメントを、ＣＡＭモジュール１４の第１部分によって検出することができ、他の部分によって検出はされず、シグネチャの残りの３バイト及び入力データの次の１バイトを含むシグネチャセグメントが、ＣＡＭモジュールのすべての部分に供給され、このシグネチャセグメントを、ＣＡＭモジュール１４の第２部分によって検出することができ、他の部分によって検出はされない。したがって、シグネチャの両方のセグメントを、ＣＡＭモジュール１４によって検出し、そこから出力することができる。その後、セグメントを照合して、悪意のある内容が検出されたことを示すフラグを立てることを可能にしてもよい。
【００４６】
シグネチャ検出回路１に入力されるデータブロックのそれぞれについて、この回路のマルチプレクサ１６はそれぞれ、図示のように、ハッシュモジュール１２からの０値又は１２ビットシグネチャ／シグネチャセグメントＩＤ、ＣＡＭモジュール１４からの０値又は１２ビットシグネチャ／シグネチャセグメントＩＤ、及びアイドル信号を受け取る。各マルチプレクサ１６は、受け取られた場合にはハッシュ１２ビットシグネチャ／シグネチャセグメントＩＤを出力し、或いは、受け取られた場合にはＣＡＭ１２ビットシグネチャ／シグネチャセグメントＩＤを出力し、或いは、ハッシュモジュール１２とＣＡＭモジュール１４との両方から０値が受け取られた場合にはアイドル信号を出力する。マルチプレクサ１６の出力は、レジスタ１８によって受け取られる。レジスタのそれぞれは、悪意のある内容がネットワークデータのデータブロック内で見つかったことを示すフラグと一緒のハッシュ１２ビットシグネチャ／シグネチャセグメントＩＤ又はＣＡＭ１２ビットシグネチャ／シグネチャセグメントＩＤ、又はアイドル値のいずれかを出力する。これらは、シグネチャ検出回路１からＤＰＩシステムへ、そのＤＰＩシステムでの使用のために出力される。シグネチャ／シグネチャセグメントＩＤが、３２ビットのシグネチャ／シグネチャセグメントではなく１２ビットだけを有するので、ＩＤは、たとえばそれらを格納するのに必要なメモリに関して、シグネチャ／シグネチャセグメントより簡単に使用可能である。
【００４７】
この実施形態では、シグネチャ検出回路１は、図４に示されているようにＤＰＩシステムの一部を構成する。ＤＰＩシステムは、この図の下側部分に示されているように、ＩＰパケットを受け取る。ＤＰＩシステムは、この図の中央部分に示されているように、ＩＰパケットを処理して、それからペイロードを抽出する。シグネチャ検出回路は、この図の上側部分に示されているように、ペイロード内のシグネチャを検出するのに使用される。これは、シグネチャセグメントが検出される時に、それらが、ペイロード内の悪意のある内容の存在を判定するために、完全なシグネチャを形成するために照合されることを示す。
【図１】
2010506322.tif 000003
【図２】
2010506322.tif 000004
【図３】
2010506322.tif 000005
【図４】
2010506322.tif 000006
【国際調査報告】
2010506322.tif 000007
2010506322.tif 000008