(57)【特許請求の範囲】
【請求項１】
通信ネットワークを介して伝送されるデータパケット内のシンボルパターンの複数のインスタンスを識別するための機械実装される方法であって、
（ａ）該機械により、２又はそれ以上の異なる長さを有する複数のデータパケットセグメントをもたらすために、可変ストライド型のセグメント化を使用してデータパケットをシンボルの可変サイズのブロックにセグメント化するステップであって、（ｉ）異なるｋグラムに関連するハッシュ値を生成するために、ハッシュ関数をデータパケット内のシンボルの異なるｋグラムに適用し、（ｉｉ）１つまたは複数のハッシュ値に基づいて各データパケットセグメントを区切ることにより、データパケットが複数のデータパケットセグメントに区切られる、該ステップと、
（ｂ）該機械により、複数のデータパケットセグメントのそれぞれを、誤検出なく及び検出漏れなくデータパケット内のシンボルパターンの複数のインスタンスを識別するために決定性有限オートマトン（ＤＦＡ）処理を使用してシンボルパターンのパターンセグメントと比較するステップであって、パターンセグメントがシンボルパターンよりも少ないシンボルを有するステップとを含む、方法。
【請求項２】
ステップ（ａ）が、
（ａ１）データパケット内のｋグラムのシンボルにハッシュ関数を実行して、ｋグラムに関連付けられるハッシュ値を生成するステップであって、（ｋ＞０）であるステップと、
（ａ２）少なくとも１つのｋグラムに関連付けられる少なくとも１つの特別なハッシュ値を識別するために値をフィルタリングするステップと、
（ａ３）データパケットストリームを、少なくとも１つの特別なハッシュ値に関連付けられる少なくとも１つのｋグラムのデータパケット内の位置に基づいて少なくとも２つのデータパケットセグメントに区切るステップとを含む、請求項１に記載の方法。
【請求項３】
ステップ（ａ１）が、サイズｗのウインドウ内の複数のｋグラムに対応する複数のハッシュ値を生成するステップであって、（ｋ＜ｗ）であるステップを含み、
ステップ（ａ２）が、少なくとも１つのｋグラムに関連付けられる少なくとも１つの特別なハッシュ値をウインドウ内の最小ハッシュ値として選択するステップを含む、請求項２に記載の方法。
【請求項４】
ステップ（ａ）が、前記シンボルパターンを少なくともヘッドブロック、コアブロック、およびテイルブロックにセグメント化するステップをさらに含み、前記パターンセグメントが、ヘッドブロック、コアブロック、およびテイルブロックのうちの１つに対応する、請求項１に記載の方法。
【請求項５】
ステップ（ｂ）が、単一の可変ストライド型離散有限オートマトン（ＶＳ−ＤＦＡ）を使用して実行される、請求項１に記載の方法。
【請求項６】
ＶＳ−ＤＦＡが、少なくとも２つのコアブロックを備えるアルファベットを使用して構築される、請求項５に記載の方法。
【請求項７】
ＶＳ−ＤＦＡが少なくとも２つの異なる可能性のあるパターンマッチングのうちの１つに対応する擬似状態を含み、少なくとも２つの異なる可能性のあるパターンマッチング間のパターンマッチングを決定するステップがヘッドおよびテイルブロックの関数である、請求項５に記載の方法。
【請求項８】
前記シンボルパターンが第１のシンボルシーケンスに対応し、
ＶＳ−ＤＦＡが、少なくともパターンセグメントおよび第２のシンボルシーケンスに対応する第２のシンボルパターンのセグメントを含むアルファベットを使用して構築され、第２のシンボルシーケンスが第１のシンボルシーケンスとは異なる、請求項５に記載の方法。
【請求項９】
（ｃ）ｐの連続する単一のシンボルデータパケットセグメントの少なくとも１つのシーケンスを、単一のｐのシンボルデータパケットセグメントに統合するステップであって、（ｐ＞１）であるステップをさらに含む、請求項１に記載の方法。
【請求項１０】
通信ネットワークを介して伝送されるデータパケット内のシンボルパターンの複数のインスタンスを識別するための装置であって、
（ａ）２又はそれ以上の異なる長さを有する複数のデータパケットセグメントをもたらすために、可変ストライド型のセグメント化を使用してデータパケットをシンボルの可変サイズのブロックにセグメント化する手段であって、（ｉ）異なるｋグラムに関連するハッシュ値を生成するために、ハッシュ関数をデータパケット内のシンボルの異なるｋグラムに適用し、（ｉｉ）１つまたは複数のハッシュ値に基づいて各データパケットセグメントを区切ることにより、データパケットが複数のデータパケットセグメントに区切られる、該手段と、
（ｂ）複数のデータパケットセグメントのそれぞれを、誤検出なく及び検出漏れなくデータパケット内のシンボルパターンの複数のインスタンスを識別するために決定性有限オートマトン（ＤＦＡ）処理を使用してシンボルパターンのパターンセグメントと比較する手段であって、パターンセグメントがシンボルパターンよりも少ないシンボルを有する手段とを備える、装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は通信およびコンピュータネットワークに関し、詳細には、コンテンツ検査システムアプリケーションのための、マルチパターンマッチングにおける可変ストライド型ブロック処理の使用に関する。
【背景技術】
【０００２】
このセクションでは、本発明のより良い理解の促進に役立ち得る態様を紹介する。したがって、このセクションの記述はこの観点から読まれるべきであり、従来技術にあるもの、またはないものに関する了承事項と解釈されるべきではない。
【０００３】
マルチパターンマッチングは、シグネチャ型ネットワーク侵入検知および防止システム（ＮＩＤＳ／ＮＩＰＳ、またはＮＩＤＰＳ）などのコンテンツ検査システムによって使用される主要な機能である。このようなシステムは、そのトラフィックがネットワーク、またはホストを含むネットワークのコンポーネントにとって有害である可能性があるかどうかを決定するために、ネットワークトラフィック内の特定のシグネチャまたはパターンの信頼できるリアルタイム検知に依存する。
【０００４】
一般的に、コンテンツ検査システムはこのような多くのシグネチャを同時に検索できる。ラインレートは１０Ｇｂｐｓ以上に増加するので、マルチパターンマッチングを効率的に処理するための方法はますます重要になった。
【０００５】
従来、パターンマッチングは決定性有限オートマトン（ＤＦＡ）を使用して成し遂げられてきた。ＤＦＡは有限状態機械であり、状態および入力シンボルごとに、次の状態への唯一の遷移がある。ＤＦＡについての情報は、Ｇｉｌｌ、Ａの「Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  ｔｈｅ  Ｔｈｅｏｒｙ  ｏｆ  Ｆｉｎｉｔｅ−Ｓｔａｔｅ  Ｍａｃｈｉｎｅｓ」、ＭｃＧｒａｗ−Ｈｉｌｌ、１９６２年から入手でき、その全体を参照により本明細書に組み込む。
【０００６】
基本的なタイプのＤＦＡベースのパターンマッチングでは、ネットワークトラフィックストリームは一度に１バイトまたは１文字処理される。このようなＤＦＡは、ｎ個の１バイトパターンを処理するためにｎ個の状態を必要とし、また状態ごとにｔ個の遷移を必要とし、ｔはパターンアルファベット内のシンボルの数である。しかし、現代のネットワークのラインレートでクロックごとに１バイトを処理するのは遅すぎる。
【０００７】
基本的なＤＦＡのスループットを改善する１つの方法は、それぞれのマッチングステップで、入力データストリームの複数のバイト（たとえば、ブロック）をスキャンすることである。ブロック内のバイト数に比例するバイト指向のＤＦＡと比較して、このブロック指向のＤＦＡ手法はスピードアップを提供するが、他の問題を提示する。特に、パターンはブロック内のどのオフセットでも開始または終了できるので、ブロック指向のＤＦＡは、（１）ｓ回繰り返すことであり、ｓがブロックサイズ、またはＤＦＡの「ストライド」であることか、（２）状態ごとにより多くの遷移を提供することの、どちらかを必要とする場合がある。
【０００８】
たとえば、パターンマッチングのための第１のブロック指向のＤＦＡ手法では、パターンはｓバイトブロックに分割され、ブロックはＤＦＡを構築するために使用される。これにより、同じパターンについて、対応するバイト指向のＤＦＡよりも少ない状態および遷移を有するＤＦＡになる。しかし、ＤＦＡのｓ個のインスタンスはパラレルに実行する必要があり、それぞれは同じ入力データストリームを１バイトオフセットで受け取る（確実にどのパターンも見落とさないようにするために）。入力ストリームが．．．ｂａｂｂａｂａ．．．で、シーケンスが．．．｜ｂａ｜ｂｂ｜ａｂ｜ａ．．．であり、その１バイトシフトされたバージョンが．．．ｂ｜ａｂ｜ｂａ｜ｂａ｜．．．の場合、確実に一致を見逃さないようにするために、両方が処理される必要がある。この手法によって、より高いメモリ帯域幅使用量を使って（マッチングエンジンのｓ個のインスタンスをパラレルに実行する結果）、より高いスループットが実現され、メモリ帯域幅のニーズはブロックのサイズｓに比例して高まる。
【０００９】
あるいは、ストリーム内で発生する可能性がある全ての可能なｓバイトパターンを遷移が考慮する、単一のＤＦＡを構築できる。より大きいＤＦＡを使用することによって、一致を見逃す可能性なしに入力データストリームをスキャンするために、マッチングエンジンの単一のインスタンスを使用できる。この場合のスループットゲインは、より高いメモリ帯域幅ではなく、より高いメモリ使用量を費やす。どのような状態からの遷移の数もｔｓの大きさになる場合があり、ｔはアルファベットのサイズである点にも留意されたい。実際、ｔ＝２６である英語のアルファベットを使用するＮＩＤＳシグネチャのセットでは、２バイトのブロックサイズｓでさえもメモリ使用量は非常に高くなる。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】Ｇｉｌｌ、Ａの「Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  ｔｈｅ  Ｔｈｅｏｒｙ  ｏｆ  Ｆｉｎｉｔｅ−Ｓｔａｔｅ  Ｍａｃｈｉｎｅｓ」、ＭｃＧｒａｗ−Ｈｉｌｌ、１９６２年
【非特許文献２】Ｓ．Ｓｃｈｌｅｉｍｅｒ他の「Ｗｉｎｎｏｗｉｎｇ：  Ｌｏｃａｌ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｄｏｃｕｍｅｎｔ  Ｆｉｎｇｅｒｐｒｉｎｔｉｎｇ」、ＡＣＭ  ＳＩＧＭＯＤ  ２００３年
【非特許文献３】Ａ．Ｖ．  Ａｈｏ  ａｎｄ  Ｍ．Ｊ．  Ｃｏｒａｓｋｉｃの「Ｅｆｆｉｃｉｅｎｔ  ｓｔｒｉｎｇ  ｍａｔｃｈｉｎｇ：  Ａｎ  ａｉｄ  ｔｏ  ｂｉｂｌｉｏｇｒａｐｈｉｃ  ｓｅａｒｃｈ」、Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ、ｖｏｌ．１８、ｎｏ．６、１９７５年
【発明の概要】
【発明が解決しようとする課題】
【００１１】
既存のパターンマッチング手法の基本的な問題は、特に現在のおよび予測されるネットワークインターフェースのラインレートで実行できるシステムにとって、メモリまたはメモリ帯域幅が過度に必要なことである。
【課題を解決するための手段】
【００１２】
一実施形態では、本発明は、入力シンボルストリームのシンボルパターンとの一致を検出するための機械実装される方法である。入力シンボルストリームは、異なる長さの少なくとも２つの入力ストリームセグメントをもたらすために、シンボルの可変サイズのブロックにセグメント化される。少なくとも２つの入力ストリームセグメントのそれぞれはシンボルパターンのパターンセグメントと比較され、パターンセグメントはシンボルパターンよりも少ないシンボルを有する。
【００１３】
他の実施形態では、本発明は入力シンボルストリームをセグメント化するための機械実装される方法である。入力シンボルストリーム内のｋグラムのシンボルが形成され、（ｋ＞０）である。ｋグラムごとに値が計算される。長さｗのスライディングウインドウ内のｋグラム値から１つまたは複数の特別な値が識別され、（ｋ＜ｗ）である。入力シンボルストリームは、入力シンボルストリーム内の１つまたは複数の特別な値の位置に基づいてセグメントに区切られ、少なくとも２つのセグメントは長さが異なる。
【００１４】
本発明の他の態様、特徴、および利点は、以下の詳細な説明、添付の特許請求の範囲、および添付の図面を読めばより十分に明らかになるであろう。添付の図面において、同様の参照番号は類似または同一の要素を識別する。
【図面の簡単な説明】
【００１５】
【図１】本発明の様々な実施形態による、少なくとも２つの自律システムに広がる、ならびにネットワーク侵入検知および防止システムを含む、通信ネットワークのブロック図である。
【図２】図１のネットワーク侵入検知および防止システム１４０のブロック図である。
【図３】図２の可変ストライドマルチパターンマッチング（ＶＳＭＰＭ）システム２３０のブロック図である。
【図４】修正されたｗｉｎｎｏｗｉｎｇ処理に基づく本発明のセグメント化処理の例である。
【図５】本発明の様々な実施形態に関連付けられるトップレベル処理を示す流れ図である。
【図６】本発明の様々な実施形態による、様々なパターンの例示的セグメント化を示す図である。
【図７】本発明の様々な実施形態による、図６の例で使用されるパターンの例示的状態遷移グラフである。
【図８】本発明の様々な実施形態による、図２のＶＳＭＰＭシステム２３０を示す図である。
【図９】本発明の様々な実施形態による、図７の例示的状態遷移グラフをサポートする、例示的状態遷移およびマッチングテーブルを示す図である。
【図１０】本発明の様々な実施形態による、コアレスおよび不可分のパターンについての例示的ＴＣＡＭ記憶テーブルを示す図である。
【図１１】本発明の様々な実施形態による、入力ストリームセグメントについての２つのルールに対応する例示的流れ図である。
【発明を実施するための形態】
【００１６】
図１は、トラフィックフローを共有できる２つの自律システム１１０および１２０を示している。自律システム１１０は、プライベート、コーポレート、またはアクセスネットワークを表し、自律システム１２０は異なるプライベート、コーポレート、またはアクセスネットワーク、あるいはインターネットを表す。それぞれの自律システムは、様々なクライアント、ホスト、サーバ、およびルータを含む。
【００１７】
特に、自律システム１１０は境界ルータ１３０を含む。境界ルータ１３０は、自律システム１１０へ流れる、または自律システム１１０から流れるトラフィックの全てではないがほとんどを経路指定し、特定のトラフィックフローをブロックする能力を有する。境界ルータ１３０は、ネットワーク侵入検知および防止システム（ＮＩＤＰＳ）１４０を含む。ＮＩＤＰＳシステム１４０は、境界ルータ１３０を通じて流れるトラフィックを監視して、どのトラフィックフローが疑わしいまたは悪意のあるデータを含み得るかを境界ルータ１３０に示す働きをする。たとえば、自律システム１２０内のサーバ１９５は、ウイルスまたは他の悪意のあるコードおよび／またはデータを含むストリームを、自律システム１１０内の１つまたは複数のクライアントまたはホスト装置に送信している場合がある。悪意のあるコードおよび／またはデータに関連付けられるパターンは、ＮＩＤＰＳシステム１４０によって検知され得る。ＮＩＤＰＳシステム１４０は、これらのコードおよび／またはデータを直接ブロックするか、境界ルータ１３０に悪意のあるフローを警告し、この場合、境界ルータ１３０は問題となるパケットをドロップすることによって、またはＩＰソースアドレスによってフローをブロックすることなどによって、そのフローをブロックできる。ＮＩＤＰＳシステム１４０は境界ルータ１３０の一部として示されているが、ＮＩＤＰＳシステム１４０は、ルータとともに動作している別のネットワーク装置でもよく、プロキシまたはゲートウェイサーバの一部として実装されてもよい。本発明によるＮＩＤＰＳシステムの他の例が、たとえば内部ルータ１９０、境界ルータ１８０、またはサーバ１７０を含む、他のルータまたはネットワーク装置上に存在する場合もある。
【００１８】
図２は、本発明の一実施形態による、図１のネットワーク侵入検知および防止システム１４０を示している。ＮＩＤＰＳシステム１４０は、プロセッサ２１０、メモリ２２０、および可変ストライド型マルチパターンマッチング（ＶＳＭＰＭ）システム２３０を含む。ＶＳＭＰＭシステム２３０は、ストリーム入力２４０を介して検査および検知するために境界ルータ１３０からネットワークトラフィックを受信し、また、任意でオリジナルのトラフィック、またはトラフィックのサニタイズされたサブセットを、ストリーム出力２５０を介して境界ルータ１３０に返送する。ＶＳＭＰＭシステム２３０は、境界ルータ１３０に、悪意のあるパターン検知警告２６０も出力する。この警告は、提供されたトラフィックは１つまたは複数の悪意のある、または異常なパターンを含むことを境界ルータ１３０に知らせる。様々な実施形態では、ストリーム入力２４０は、ヘッダ、暗号化、およびトラフィックフロー内の悪意のあるパターンを検知するタスクにとって無関係である他の情報を取り除くために、ＶＳＭＰＭシステム２３０の外部で前処理されたデータを含むことになる。このような前処理は、プロトコル分析、プロトコルラッパーの除去、および／またはペイロード再構築を含むことができる。当業者には理解されるように、様々な代替構成が使用され得る。
【００１９】
上述のように、従来技術のブロック指向ＤＦＡに関連付けられる問題の多くは、一致を検出する可能性があるブロックパターンの位置が入力ストリーム内で知られていないという事実から生じる。一致を検出するブロックパターンは、入力ストリーム内の類似の長さのそれぞれのブロックと比較される必要がある場合があり、多量の処理、メモリ、および／またはメモリ帯域幅ペナルティをもたらすことになる。しかし、一致を検出するパターンが入力ストリーム内に存在する場合、それらのパターンに対応するブロックに入力ストリームをセグメント化できれば、パターンマッチングの複雑さを大いに軽減できる。たとえば、テキストストリング「．．．ｃｋｂｒｏｗｎｆｏｘｊｕｍｐｅｄｏｖｅｒｔｈ．．．」内で「ｏｖｅｒ」という単語との一致を見つける問題を考えてみる。人間の視覚システムは、見慣れたパターン「ｏｖｅｒ」の存在をストリングの末端付近に容易に検知できるが、同じタスクは機械にとってはより困難である。特に、従来のブロック指向ＤＦＡは、入力ストリームからの４バイトストリングの「ｏｖｅｒ」をテンプレートと比較して一致が見つかるまで、入力ストリームを１バイトずつ連続的にシフトしながら、まずパターン「ｏｖｅｒ」を「ｃｋｂｒ」と、次いで「ｋｂｒｏ」と、次いで「ｂｒｏｗ」と、以下同様に比較しなければならない。
【００２０】
ともかくまず入力ストリームを適切にセグメント化すれば、問題の複雑さを軽減できることが理解されよう。たとえば、入力ストリーム「．．．ｃｋｂｒｏｗｆｏｘｊｕｍｐｅｄｏｖｅｒｔｈ．．．」がまず「．．．ｃｋ｜ｂｒｏｗｎ｜ｆｏｘ｜ｊｕｍｐｅｄ｜ｏｖｅｒ｜ｔｈ．．．」にセグメント化されれば、マッチングのためのいくつかの異なる手法を行うことができる。たとえば、ある手法では、パターン「ｏｖｅｒ」がストリーム内に発生したかどうかを決定するために、まず、長さが４の何らかのセグメントがストリング内に存在するかどうかを決定して、存在する場合はそれらのストリングだけを一致が検出されるべきパターンと比較することができる。あるいは、セグメントの長さとは無関係に、ｎバイトのパターンをブロックベースで入力ストリームのそれぞれのセグメントの最初のｎバイトと比較できる。たとえば、「ｏｖｅｒ」を「ｂｒｏｗｎ」、「ｆｏｘ」、「ｊｕｍｐｅｄ」、および最後に「ｏｖｅｒ」と、一致が見つかるまで連続で比較できる。これは、「ｏｖｅｒ」を、比較ごとに入力ストリームを１文字ずつシフトすることによって得られるサイズが４の全てのブロックと比較することよりもシンプルである。
【００２１】
したがって、本発明の実施形態では、入力ストリームをバイトごとの方法では処理できないかもしれないが、代わりに位置とは無関係の、および一意のセグメント化処理によって互いに区切られた、より大きな自然単位で処理できる。本発明の実施形態では、入力ストリームおよび一致が検出されるべきパターンは、可変サイズのマルチバイトブロックに一意におよび明確にセグメント化される。次いで、これらの可変サイズのブロック（または原子単位）を状態遷移のためのシンボルの新しいアルファベットとして使用するブロック指向ＤＦＡを使用して、パターンマッチングが実行される。これらの原子単位についての１よりも大きい平均バイトサイズにより、パターンマッチングレートがかなり増すことになる。この方法により、それぞれの状態遷移が複数のバイトに広がることになるので、ＤＦＡ状態および状態遷移の数も減少する。この手法は、以下で図３を参照して説明する。
【００２２】
図３は、本発明の様々な実施形態による図２の可変ストライド型マルチパターンマッチングシステム２３０を示している。ＶＳＭＰＭシステム２３０は、ストリームセグメント化ユニット３１０、可変ストライド型ブロックマッチングユニット３２０、および任意のパケットドロッパー３３０を含む。動作において、ストリームセグメント化ユニット３１０が、ストリーム入力２４０から入力データを受信して、そのストリームをセグメントにセグメント化して、ストリームセグメント３４０を可変ストライド型ブロックマッチングユニット３２０に出力する。可変ストライド型ブロックマッチングユニット３２０は、セグメントをマッチするパターンから得られたセグメントで構成される複数バイトの原子シンボルのアルファベットと比較して、これらの複数バイトの原子シンボルに基づくＤＦＡを使用して、入力ストリーム内に特定のパターンが存在するかどうかを決定する。入力ストリーム内に悪意のあるパターンが検知されると、可変ストライド型ブロックマッチングユニット３２０は警告２６０を出力して、外部ユニットに対応するトラフィックが疑わしい、および／または悪意がある、ならびに／あるいはブロックまたはドロップしなければならないことを示す。ＶＳＭＰＭシステム２３０のいくつかの実施形態では、任意選択で、可変ストライド型ブロックマッチングユニット３２０は代替で、入力ストリームをストリーム出力２５０に転送する前に悪意のあるコンテンツを入力ストリームから削除する働きをする任意のパケットドロッパーユニットにドロップ制御信号３５０を出力できる。いくつかの実装形態では、ＶＳＭＰＭシステム２３０からはストリーム出力が提供されない。明確にするために、図３には単一の可変ストライド型ブロックマッチングユニットが示されているが、当業者には理解されるように、複数のパターンマッチングをサポートするために複数のパラレルインスタンスが提供され得る。あるいは、本発明のいくつかの実施形態では、図３の可変ストライド型ブロックマッチングユニット３２０は、複数のパターンのマッチングを同時にサポートする。
【００２３】
ある実施形態では、本発明は、データの任意のストリームを一意におよび明確にセグメント化する方法である。パターンマッチングおよび曖昧性解消のために、可変サイズのブロックＤＦＡが使用される。このセグメント化と可変ブロックサイズのＤＦＡ処理との組合せを、パターンマッチング問題に適用できる。当業者には理解されるように、本発明に幅広いセグメント化技法を利用できる。一般性を喪失せずに、ある例示的方法を以下で説明する。
【００２４】
セグメント化
本発明の実施形態で利用されるセグメント化スキームは、「ｗｉｎｎｏｗｉｎｇ」アルゴリズムとして知られている一般のドキュメントフィンガープリンティングアルゴリズムに基づく。Ｗｉｎｎｏｗｉｎｇアルゴリズムについてのさらなる情報は、Ｓ．Ｓｃｈｌｅｉｍｅｒ他の「Ｗｉｎｎｏｗｉｎｇ：  Ｌｏｃａｌ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｄｏｃｕｍｅｎｔ  Ｆｉｎｇｅｒｐｒｉｎｔｉｎｇ」、ＡＣＭ  ＳＩＧＭＯＤ  ２００３年で入手でき、その内容を全体として参照により本明細書に組み込む。他のフィンガープリンティングスキームも代替で使用できるが、ｗｉｎｎｏｗｉｎｇスキームは本出願にとって特に望ましいある特性を有する。
【００２５】
Ｗｉｎｎｏｗｉｎｇアルゴリズムは異なる用途のために提示されているので、アルゴリズムは本発明のパターンおよびデータストリームブロック生成発明のために修正される。Ｗｉｎｎｏｗｉｎｇアルゴリズムの良い特徴は、位置非依存なことである。これにより、いくつかの新しいテキストをファイルに追加しても、２つのファイル間の全てのオリジナルな一致が保存されることが確実になる。
【００２６】
アルゴリズムは以下のように働く。第１に、ｓ個の連続する文字の全てのブロックのハッシュ値を計算する。Ｗｉｎｎｏｗｉｎｇの論文では、これらのブロックは「ｋグラム」と呼ばれ、ｋ＝ｓである点に留意されたい。ｒ文字のストリームは（ｒ−ｓ＋１）ハッシュ値を生成する。第２に、サイズｗのスライディングウインドウを使用して、最小ハッシュ値をウインドウ内に位置づける。最右最小値を選択することによって、均衡が破られる。これらの選択されたハッシュ値はｗｉｎｎｏｗｉｎｇスキームにおけるデータストリームのフィンガープリントとして使用されるが、本発明では、入力データストリームのセグメントへのデリミッタ、ならびに一致が検出されるべきパターンのセグメントへのデリミッタを識別するために使用される。
【００２７】
図４は、ハッシュ値が０−２５５の範囲である、セグメント化の例４００を示している。ブロックサイズ、すなわちストライドｓはスライディングウインドウのサイズ、ｗ＝３によって制限される点に留意されたい。図４は、（ｉ）入力ストリーム４１０、（ｉｉ）ブロックハッシュ４２０およびブロックハッシュ４３０などの、ｋ＝２バイトブロックハッシュ、（ｉｉｉ）ブロックハッシュ４３０などの、選択されたブロックハッシュ、ならびに（ｉｖ）セグメント化された出力ストリーム４４０を含む。動作において、入力ストリーム内のあらゆる連続するｋバイトブロックについてハッシュが計算され、ｗバイトウインドウ内の最低ブロックハッシュ値が特別なハッシュ値として識別される。Ｗｉｎｎｏｗｉｎｇアルゴリズムでは、ドキュメントフィンガープリンティングの目的で使用される比較的均等に分散されたハッシュ値のサブセットを表すために、これらの特別なハッシュ値が選択される。本発明では、これらの特別なハッシュ値は、一致が検出されるべきデータのセグメントを区切るために使用される。たとえば、デリミッタ４５０は、バイトストリング「ｒｖｅ」をバイトストリング「ｒ［」から分離させる。ｋ＝２バイトハッシュ法の適用およびｗ＝３ウインドウ内の最小ハッシュ値の選択の結果は、長さが２または３バイトのセグメントを有するセグメント化された出力ストリーム４４０である。
【００２８】
パターンマッチングで使用するために、ｗｉｎｎｏｗｉｎｇアルゴリズムがいくつかの方法で修正される。悪意のあるパターンは短い場合があるので、パターンから有効な数のブロックを取得するために、ブロックサイズｓ（ｗによって制限される）は比較的小さく維持される。様々な実施形態では、パターンは少なくとも３つのブロックにセグメント化される。したがって、ｋおよびｗも小さい（一致が検出されるべきパターンの長さの約３分の１）。一方、スループットにとってはより大きいブロックサイズｓの方が良いので、一致が検出されるべきパターンの長さを考慮すると、ｗをできるだけ大きくすることが望ましい。トレードオフとして、約９−２０バイトの当該のパターンを有する一般的な実施形態では、１か２のどちらかになるようにｋが選択され、ｗは約３−約８に及ぶことができる。
【００２９】
ハッシュウインドウｗは小さいので、結果として得られるセグメントのストライドｓ（ｗによって制限される）も小さくなる。したがって、ｓバイトのＤＦＡを高速ハードウェアで、および上述のｗｉｎｎｏｗｉｎｇの論文に記載されたＲａｂｉｎ高速ハッシュ技法を使用する必要はないが使用できる、高速ハッシュ関数で実装できる。さらに、本発明の目的はマッチングにおいて使用されるべきフィンガープリントを生成することではなく、入力データストリームおよびパターンをセグメント化することなので、大きいハッシュ値は必ずしも好都合ではない。８ビット、またはさらに少ないビット数で十分である。これは効率的で高速のハードウェア実装にとって好都合である。図４に示されるように、ハッシュウインドウのハッシュ値（たとえば、文字「ｓｅ」に関連付けられる２バイトのハッシュウインドウに対応するハッシュ値４２０）は２５６よりも短い。デリミッタは選択された最小ハッシュ値の後に設定される（たとえば、デリミッタ４５０は、文字「ｒｖｅ」に対応するウインドウ内の最低ハッシュ値であるハッシュ値８７の後になるように選択される）点にも留意されたい。これにより、ｋ＜ｗ＋２の場合、どのようなブロックのサイズもｗより決して長くならないことが保証される。
【００３０】
Ｗｉｎｎｏｗｉｎｇアルゴリズムには、入力ストリーム内にパターンが現れる文脈にかかわらず、入力ストリームは常にブロックの同じシーケンスにセグメント化される（以下に説明するように適合され得るいくつかのヘッドおよびテイルパターンを除いて）という点で本発明の実施形態にとって非常に便利な「自己同期化」（すなわち、関連独立性）の特性がある。したがって、本発明のセグメント化処理の成果は、パターンマッチングのためにＤＦＡの構築において原子単位として使用され得る、パターン内の一意のセグメントの決定である。
【００３１】
図５は、本発明の様々な実施形態によるセグメント化およびマッチング処理を示す高レベルの流れ図５００を示している。ステップ５１０で、前処理ステップとして、後のマッチングのための当該のパターンが、本発明によるセグメント化処理を使用して、まずブロックのシーケンスにセグメント化される。これらのセグメントは後の使用のために格納されてもよく、ブロック指向のＤＦＡの構築において使用されてもよい。ステップ５２０で、セグメント化の同様のプロセスが入力ストリームに適用される。最後に、ステップ５３０で、当該のパターンが入力データストリーム内に存在するかどうかを決定するために、一致が検出されるべきパターンから得られたセグメントが、入力データストリームから得られたセグメントと比較される。ステップ５３０の比較は、一致が検出されるべきパターンのセグメントを使用して開発されたブロック指向のＤＦＡを介して行われてよく、そのセグメントはステップ５１０で生成されている。
【００３２】
パターンのセグメント化の間、セグメント化パラメータｋおよびｗに関するパターンのサイズに応じて、複数のセグメントが一般的に生成される。第１セグメントは「ヘッド」ブロックと呼ばれ、最後のセグメントは「テイル」ブロックと呼ばれる。両者間の他の全てのセグメントは「コア」ブロックと呼ばれる。図６は、様々なパターンのセグメント化６００の例を示している。セグメント化６００は、セグメント化されるべきパターン６１０、ならびにパターンのセグメントによって生じるヘッドセグメント６２０、コアセグメント６３０、およびテイルセグメント６４０を含む。例は、見慣れた文字およびストリングを使用して概念を示しているが、本発明はこれらをシンボルおよびセグメントとして広く扱う点に留意されたい。いくつかの短いパターンにはデリミッタが１つしかない（すなわちコアセグメントがなく、パターンは唯一のヘッドおよびテイルセグメントで構成される）、またはデリミッタが全くない場合がある点にも留意されたい。これらの２つのタイプのパターンは、それぞれ「コアレスパターン」および「不可分パターン」と呼ばれる。図６では、「ｅｎｔｉｒｅ」がコアレスパターンであり、「ｓｅｔ」が不可分パターンである。本発明のセグメント化スキームには以下の特性がある：
特性１：どのセグメントブロックのサイズも［１，ｗ］の範囲内である。テイルブロックのサイズは［ｋ−１，ｗ＋ｋ−２］の範囲内であり、不可分パターンのサイズは［１，ｗ＋ｋ−２］の範囲内であり、コアレスパターンのサイズは［ｗ＋ｋ−１，２ｗ＋ｋ−２］の範囲内である。
【００３３】
特性２：データストリーム内にパターンが現れると、データストリームのセグメント化によって、パターンのコアブロックと全く同じデリミッタがもたらされる。
【００３４】
ヘッドブロックは接頭辞によって影響を受ける場合があり、テイルブロックは接尾辞によって影響を受ける場合があるので、データストリーム内に現れるときに、パターンのヘッドおよびテイルブロックには余分なデリミッタがある場合がある点に留意されたい。しかし、コアブロックはパターンに完全に限定され、文脈から分離される。これらの変化しないコアブロックは、パターンマッチングにおける検索を狭めるために使用できる。これは以下によって説明される。
【００３５】
図６のパターンＳ２がデータストリーム内に現れると仮定する。Ｓ２のすぐ前に現れる文字（ｗ−１＝３）に応じて、ヘッドブロック「ａｕｔｈ」は「ａ｜ｕ｜ｔ｜ｈ」、「ａｕ｜ｔｈ」などにセグメント化される可能性がある。同様に、テイルブロック「ｔｅ」のセグメント化は、データストリーム内のＳ２に続く文字（ｗ−１＝３）によって決定される。しかし、決定を行う必要がある全ての文字（すなわち、ａ、ｕ、ｔ、およびｈ）はセグメント化処理の一部なので、文字「ｈ」の後に区切り記号があることが保証される。これは、ストリーム内のパターンＳ２に続く２つの区切り記号にも当てはまるので、セグメント化は常に２つのコアブロック「ｅｎｔ」および「ｉｃａ」をもたらすことになる。
【００３６】
パターンのコアブロックは不変なので、高速パターンマッチングをサポートする。しかし、パターンＳ２を確実に一致を検出するためには、単に２つのブロック「ｅｎｔ」および「ｉｃａ」が連続的に一致を検出したということ以上の情報が必要である。分かっているのは、２つのブロック「ｅｎｔ」および「ｉｃａ」が連続的に一致を検出した場合、Ｓ２と一致を検出する可能性があるということである。一致を検証するために、一旦コアブロックが一致を検出すると、次のステップは、データストリーム内のｗバイトの接頭辞シンボルおよび（ｗ＋ｋ−２）バイトの接尾辞シンボルを取り出して、それぞれをＳ２のヘッドブロックおよびテイルブロックと比較することである。
【００３７】
可変ストライド型マッチング
前処理ステップの間に一旦パターンがセグメント化されて、入力ストリームが同様にセグメント化されると、次のタスクは入力ストリームセグメントをあらかじめ定められたパターンセグメントと比較することを含む。本発明の一実施形態では、この目的のために可変ストライド型離散有限オートマトン（ＶＳ−ＤＦＡ）が使用される。たとえば図３では、以下に説明するように、ＶＳ−ＤＦＡの形式で可変ストライド型ブロックマッチングユニット３２０が実装され得る。
【００３８】
ＶＳ−ＤＦＡ構築は、Ａｈｏ−Ｃｏｒａｓｉｃｋ  ＤＦＡ構築アルゴリズムにおける手順に従う。Ａｈｏ−Ｃｏｒａｓｉｃｋ  ＤＦＡ構築についてのさらなる情報は、Ａ．Ｖ．  Ａｈｏ  ａｎｄ  Ｍ．Ｊ．  Ｃｏｒａｓｋｉｃの「Ｅｆｆｉｃｉｅｎｔ  ｓｔｒｉｎｇ  ｍａｔｃｈｉｎｇ：  Ａｎ  ａｉｄ  ｔｏ  ｂｉｂｌｉｏｇｒａｐｈｉｃ  ｓｅａｒｃｈ」、Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ、ｖｏｌ．１８、ｎｏ．６、１９７５年から得ることができ、その内容を全体として参照により本明細書に組み込む。
【００３９】
パターンのコアブロックは、セグメント化処理を使用して抽出されて、ＤＦＡを構築するためのアルファベット記号として使用される。したがって、ＶＳ−ＤＦＡのある特徴は、状態遷移が個々の文字ではなくコアブロックに基づくことである。コアブロックの一致の後に、ヘッドおよびテイルブロックの一致が続く。ＤＦＡの構築により、ブロックごとに１つの状態遷移で、全てのコアブロックのシーケンスを確実に検知できるようになる。これに続いて、「擬似一致」状態は、ヒットすれば最終的な検証ステップにつながる。
【００４０】
図７は、図６で示されたパターンについての例示的状態遷移グラフ７００を示している。ＤＦＡは７つの状態を含む。ｑ０は最初の状態である。ｑ１１、ｑ１２、ｑ１４、およびｑ１５は擬似一致状態である。図面を乱雑にしないように、最初の状態に戻る失敗遷移は図示されない。ＶＳ−ＤＦＡの正確性はセグメント化処理の第２の特性によって保証され、特に、パターンがデータストリーム内に現れる限りそのコアブロックもセグメント化されたデータストリーム内に現れ、したがって構築されたＤＦＡはコアブロックを正確に捉えて、次いでヘッドおよびテイルブロックを検査することになる。ＶＳ−ＤＦＡの構築の手法は、ブロックシンボルシーケンスを検知するための典型的なＤＦＡ構築と類似している。主な違いは、先験的な知識のために、いくつかのパスを削除できることである。
【００４１】
構築されたＤＦＡは、ヘッドおよびテイルブロックの知識なしにパターンボディ上で直接マッチングが開始するかのように働く。しかし、ＤＦＡを構築する際、不要な状態遷移を削除するためにヘッドおよびテイルブロックの知識が次に使用される。典型的なＤＦＡでは、パスｑｉ→ｑｊがｑ０→ｑｋと同じ文字ストリングを消費する場合、何らかの転送パス上で遷移が既に定義されていない限り、ｑｋから開始する全ての遷移をｑｊにコピーする必要がある。この場合、これはより短いパスによってカバーされたストリングが、より長いパスによってカバーされたストリングの接尾辞であるためであり、より長いパスは、より短いパスがもたらすのと同じパターンとのに一致をもたらす可能性がある。したがって、パターン間の重複を解消するためにジャンプ遷移が構築される。これは図７に示されており、コアブロックシーケンス「｜ｉｄ｜ｅｎｔ｜」がコアブロックシーケンス「｜ｅｎｔ｜ｉｃａ｜」と重複するので、ｑ１５からｑ１２へのジャンプ遷移が使用されている。しかし、ＶＳ−ＤＦＡでは、遷移はパスｑ０→ｑｋ上のヘッドブロックがｑｉの入力パスと一致を検出する場合のみコピーされ得る。この例では、パスｑ０→ｑ１２上のヘッドブロックは「ｉｄ｜」および「ａｕｔｈ｜」を含む。それらのうちの１つがｑ１の入力パス（すなわち「ｉｄ｜」）と一致を検出するので、遷移が必要である。パターン「ｉｄ｜ｅｎｔ｜ｉｃ｜ａｌ」がＤＦＡから削除されると、遷移ｑ１５→ｑ１２は不要になり、安全に削除され得る。
【００４２】
上記の特別な例として、典型的なＤＦＡ構築では、何らかの転送パス上で遷移が定義されない限り、ｑ０からの全ての遷移が他の全ての状態にコピーされるべきである。これらの遷移は再開可能な遷移としても知られている。ＶＳ−ＤＦＡでは、再開可能な遷移は必要なときのみ生成される。
【００４３】
大きなＶＳ−ＤＦＡでは、再開可能な遷移の数が多く、メモリのニーズを増加させる場合がある。幸い、ｑ０からの「開始遷移」の総数は小さい。ある実施形態では、「開始遷移」は別のオンチップ「開始テーブル」に格納され、ＶＳ−ＤＦＡとパラレルに検索される。これらの実施形態では、全ての再開可能遷移が削除され得る。さらに、状態から出て行く遷移（ｏｕｔｇｏｉｎｇ  ｔｒａｎｓｉｔｉｏｎ）を発見できない場合、別のパスを見つけるために開始テーブルからの検索結果が使用される。
【００４４】
システム
ハードウェアの観点からすると、図２および３を再び参照すると、可変ストライド型マルチパターンマッチングシステム２３０は、ストリームセグメント化ユニット（たとえば、ストリームセグメント化ユニット３１０）、および可変ストライド型ブロックマッチングユニット（たとえば、可変ストライド型ブロックマッチングユニット３２０）を含む。様々な実施形態では、ストリームセグメント化ユニット３１０はｗｉｎｎｏｗｉｎｇアルゴリズムの修正に基づくセグメント化スキームを使用して実装され、可変ストライド型ブロックマッチングユニット３２０は専用のＶＳ−ＤＦＡパターンマッチャーを使用して実装される。
【００４５】
図８は、本発明の様々な実施形態による図２のＶＳＭＰＭシステム２３０を示している。ＶＳＭＰＭシステム２３０は、修正されたｗｉｎｎｏｗｉｎｇモジュール８１０、可変ストライド型ブロックキュー８２０、およびＶＳ−ＤＦＡ８３０を含む。動作中、入ってくるデータストリーム（パケットペイロード）２４０が、修正されたｗｉｎｎｏｗｉｎｇモジュール８１０によって可変サイズのブロックにまずセグメント化されて、可変ストライド型ブロックキュー８２０（先入れ先出し（ＦＩＦＯ）キューを使用して実装された）に押し込まれる。次いで、キューからブロックがフェッチされて、可変ストライド型ＤＦＡ８３０に１つずつ送り込まれる。ＶＳ−ＤＦＡ８３０は可変ストライド型ブロックを処理し、まずコアブロックを処理して、次いでヘッドおよびテイルブロックに基づいて一致を精製する。当該のパターンとの一致が見つかったと仮定すると、ＶＳ−ＤＦＡ８３０から「一致発見」警告２６０が出力される。
【００４６】
クロックサイクルごとにｗバイトより多くを処理するために、修正されたｗｉｎｎｏｗｉｎｇモジュールのための回路が実装され得る。状態機械８３０がクロックサイクルごとに消費するのはｗバイトよりも少ない場合があるので、２つのユニット間の小さな短期レート差を適合するために、それらの間でＦＩＦＯキューが使用される。この実装形態では、システムスループットは状態機械によって決定される。
【００４７】
状態機械モジュール８３０の様々な実施形態では、上述の開始テーブルに加えて、さらに２つのテーブルがサポートデータ構造として提供される：状態遷移テーブルとマッチングテーブルである。これらのテーブルの例は、図９に示されている。
【００４８】
図９は、本発明の様々な実施形態によるサポートテーブル９００を示している。サポートテーブル９００は、状態遷移テーブル（ＳＴＴ）９１０、およびマッチングテーブル（ＭＴ）９２０を含む。ＳＴＴテーブル９１０は基本的にハッシュテーブルである。ハッシュ−キーは、開始状態と入力ブロックとの組合せである。ハッシュ値は次の状態のアドレスである。それぞれのサイクルにおいて、問い合わされた組合せが見つかると、ＳＴＴテーブル９１０の対応する行に格納された終了状態が取り出される：見つからない場合は、次の状態が開始テーブルから取得される。
【００４９】
遷移テーブルはハッシュテーブルベースなので、状態番号（およびアドレス）の割当ては一般的に任意である。しかし、擬似一致状態については、特定の範囲があらかじめ割り当てられている。これは、マッチングテーブル内の対応するエントリのアドレスを直接計算することが望ましいためである。たとえば、マッチングテーブル９２０では、範囲ｑ１＊（＊は何らかの１桁を表す）がマッチング状態にあらかじめ割り当てられている。状態ｑ１ｉはｉ番目のＭＴエントリに対応する。特別な場合は、ｑ１２が２つの可能なヘッド／テイルのペアに関連付けられることである。ｑ１２に２つのＭＴエントリが割り当てられているので、状態機械は可能なマッチングについてエントリを直線的に検査する必要がある。第３のＭＴエントリがｑ１２のために保存されるように、ｑ１３は意図的に割り当てられない。
【００５０】
擬似一致状態でのマッチング検証を可能にするために、ある実施形態ではヘッドキュー（ＨＱ）が維持され得る。ヘッドキューは、ブロックマッチング履歴を格納する。ＨＱはＤエントリを有する循環バッファを使用して実装され、ＤはＶＳ−ＤＦＡの最長転送パスの長さである。ヘッドブロックの正確な長さをあらかじめ知ることはできないので、それぞれのキューエントリのサイズはｗバイトに設定される。ブロックがｗバイトよりも短い場合は、残りがパディングされる。したがって、ＨＱのサイズは（Ｄ×ｗ）バイトであり、将来参考にするために十分な履歴が保持されていることを保証する。ＭＴにおける深度フィールドが、ＨＱ内のどのエントリがヘッドとして取り出されるべきかを決定する。深度フィールドは、深度値を備えた現在のＨＱインデックスを引くことによって計算され得る。
【００５１】
短いパターンの処理
長さがｌ＞２ｗ＋ｋ−２のパターンについては、ＤＦＡ構築のための少なくとも１つのコアブロックがあることが保証される。しかし、ｗ＋ｋ−２＜ｌ＜２ｗ＋ｋ−１の場合、パターンはヘッドおよびテイルブロックだけを有するコアレスパターンになる。長さがｌ＜ｗ＋ｋ−１のパターンは、デリミッタが全くなく、不可分パターンになる。コアブロックがないので、これらの短いパターンのためにはＶＳ−ＤＦＡは直接使用されない。代わりに、本発明の様々な実施形態では、これらのパターンは小さな３値連想メモリ（ＴＣＡＭ）によって効率的に処理され得る。
【００５２】
理想的には、ＴＣＡＭメモリは状態機械と同じスループット（すなわち、検索サイクルごとに１ブロック）を有するべきである。この目的を達成するために、従来の方法はパターンを複数回重複させ、それぞれの重複をその前に対して１バイトシフトする。しかし、本発明のセグメント化スキームにより、コアレスパターンごとに１つだけのＴＣＡＭエントリを使用すれば十分になる。ＴＣＡＭエントリは幅が２ｗ＋ｋ−２バイトである。それぞれのエントリは２つのセクションに分割され、それぞれｗバイト、およびｗ＋ｋ−２バイトである。コアレスパターンを格納するために、コアレスパターンのヘッドブロックは第１セクションの右に、およびコアレスパターンのテイルブロックは第２セクションの左に並べられる。エントリ内の使用されないバイトは「ｄｏｎ’ｔ  ｃａｒｅ」とマスキングされる。
【００５３】
不可分のパターンにはこのような最適化は行われない。代わりに、それぞれの不可分のパターンにはｍａｘ｛ｗ，ｗ＋ｋ−２｝ＴＣＡＭエントリが使用される。それぞれのエントリは、データストリーム内にこのパターンが現れる可能性がある、可能なシフトをカバーする。最初のエントリは、ＴＣＡＭエントリと左揃えにされる。それぞれの後続のエントリは、右側に向かって１バイトシフトする。図１０に一例が示されている。この例では、ｗ＝４およびｋ＝２なので、ＴＣＡＭエントリは８バイト幅である。図示されたように、「ｅｎｔ｜ｉｒｅ」にセグメント化されたコアレスパターン「ｅｎｔｉｒｅ」がＴＣＡＭエントリ１に格納される。不可分のパターン「ｓｅｔ」は４つのＴＣＡＭエントリにわたって広がる。
【００５４】
この構成では、一致を実行するために、入力ストリームは上述のようにセグメント化される。バイトストリームの終わりに、１つの追加のデリミッタが追加される。バイトストリーム内のそれぞれのデリミッタで、デリミッタの前にｗバイトが抽出され、デリミッタの後に（ｗ＋ｋ−２）バイトが抽出される。次いで、組み合わされたストリングがＴＣＡＭメモリを問い合わせるためのキーとして使用される。この手法は、あらゆる短いパターンの正確な一致を確実に見つける。幸い、短いパターンは一般的にパターンセットのごく一部分だけである。
【００５５】
１バイトブロックの減少
スループットにおけるＶＳ−ＤＦＡの利点は、ＤＦＡトラバーサルステップ（ｔｒａｖｅｒｓａｌ  ｓｔｅｐ）ごとの比較的大きな平均ストライドによるものである。ランダムデータストリームについて、予想されるブロックサイズは（ｗ＋１）／２である。しかし、上述のようにセグメント化アルゴリズムによって処理されるある入力データストリームは、選択されたハッシュ関数およびウインドウパラメータとは無関係に生成される１バイトセグメントをもたらす場合がある。たとえば、連続的に繰り返される同じ単一の文字を有する入力ストリームを処理することは、一連の１バイトセグメントをもたらす場合がある。これは、システムスループットを減少させ、またシステムが特定のタイプのサービス妨害（ＤｏＳ）攻撃を受けやすくなってしまう場合がある。
【００５６】
低エントロピーのデータストリームも、上述のセグメント化アルゴリズムにとって問題になる場合がある。したがって、本発明の様々な実施形態では、セグメントストリームに現れて、効率的なシステムスループットを減少させてしまう１バイトブロックの問題を軽減するために、ハッシュ値タイブレーカー（ｔｉｅ−ｂｒｅａｋｅｒ）方法の改良版が使用される。これは、１つまたは２つのさらなるセグメント結合規則の適用によって行われる。結果として得られる改良されたセグメント化処理が、本発明の様々な実施形態で使用される：
【００５７】
結合規則１（セグメントストリームに適用される）：データストリーム内に複数の連続する１バイトブロックが現れる場合、第１ブロックから開始して、ｗの１バイトブロックを結合して、新しい統合されたｗバイトブロックを形成する。残りのブロックが複数の場合は、残りのブロックも結合される。たとえば、ｗ＝４と仮定すると、連続する１バイトブロックは｜ｃ１｜ｃ２｜ｃ３｜ｃ４｜ｃ５｜ｃ６｜である（ｃ１以前のブロックおよびｃ６以後のブロックは、１バイトよりも長いと仮定する）。規則を適用すると、２つの結合されたブロック｜ｃ１ｃ２ｃ３ｃ４｜ｃ５ｃ６｜が得られる。
【００５８】
結合規則１は全ての連続する１バイトブロックを除去し、マルチバイトのブロック間に分散した、いくつかの分離された１バイトブロックだけを残す。最悪のケースでは、１バイトブロックおよび２バイトブロックがデータストリーム内で相互にインタリーブされる場合、結合規則１は１．５倍に加速する。類似の結合もパターンに実行される。しかし、パターン内の１バイトブロックをむやみに結合することによって、ストリームおよびパターンのセグメント化が同期を失ってしまう場合がある。いくつかのコアブロックの最初または最後が１ブロックの場合、曖昧性が発生する。異なるコンテキスト（たとえば、異なる接頭辞および接尾辞バイト）があれば、結合規則１は異なる結果になる場合がある。したがって、アルゴリズムの正確性を確実にするために、最初の１つまたは複数のオリジナルコアブロックが１バイトブロックの場合、それらはもはやコアブロックとは見なされない。代わりに、ヘッドブロックの一部として押し出される。同様に、テイルに隣接する１バイトブロックについても特別な処理が必要である。
【００５９】
結合規則１（パターンに適用される）：オリジナルヘッドブロックの直後の全ての連続する１バイトのコアブロックを新しいヘッドブロックに結合する。結合規則１で説明した方法（セグメントストリームに適用される）と同じ方法で、コアブロックの残りを結合する。結合後、最後のコアブロックが結合されたブロックであり、ｗバイトよりも短い場合、テイルブロックに結合する。以下の例は結合規則１（パターンに適用される）を示している。
【００６０】
パターンａａａａａｃｂｄｄｄｄｄａｂｃが、もともとａａａ｜ａ｜ａ｜ｃｂｄ｜ｄ｜ｄ｜ｄ｜ｄ｜ｄ｜ａｂｃとセグメント化され、ｗ＝３と仮定する。最初の２つの１バイトブロック｜ａ｜ａ｜は、ヘッドブロックと結合されるべきである。残りのブロックについて、最初の３つの連続する｜ｄ｜は｜ｄｄｄ｜に結合されて、最後の２つの連続する｜ｄ｜は｜ｄｄ｜に結合される。ブロック｜ｄｄ｜の長さは３よりも短いので、テイルブロックと結合される。
【００６１】
したがって、規則適用後の新しいセグメント化はａａａａａ｜ｃｂｄ｜ｄｄｄ｜ｄｄａｂｃになる。別のケースでは、同じパターンはａａａ｜ａ｜ａ｜ｃｂｄ｜ｄ｜ｄ｜ｄ｜ｄ｜ｄ｜ａｂ｜ｃと異なるようにオリジナルにセグメント化される。結合規則１の適用後、新しいセグメント化はａａａａａ｜ｃｂｄ｜ｄｄｄ｜ｄｄ｜ａｂ｜ｃとなるはずである。最後のコアブロック｜ａｂ｜は結合の結果ではないので、テイルブロックは同じままである。
【００６２】
結合規則１は最悪のケースと予想されるスループットとの両方を改善する。結合の欠点は、パターンがより長いヘッドおよびテイルブロックを有する場合があることである。さらに、規則適用前にそれら全てのコアブロックが１バイトブロックの場合、いくつかのパターンはさらにコアレスパターンになる場合がある。結合後、最大で（ｗ−１）の１バイトブロックがテイルブロックに統合され得るので、最大テイルブロックサイズは（ｗ＋ｋ−２）＋（ｗ−１）＝（２ｗ＋ｋ−３）バイトになることがある。ヘッドブロックについては、サイズに上界はない。
【００６３】
アルゴリズムはデータストリームからの可能性があるヘッドブロックを後のマッチング検証のためにバッファする必要があるで、ヘッドブロックのサイズは制限されなければならない。幸い、ｗバイトよりも長いヘッドブロックを有するパターンの数は少ない。パターンをｗ回複製することによって問題は解決される。それぞれの複製されたパターンは、ヘッドブロックに一意のセグメント化を与えられる。ヘッドブロックセグメント化処理は以下の通りである：
【００６４】
ｉ番目のバイトの後に、最初のデリミッタを設定し、（１≦ｉ≦ｗ）である。最初のデリミッタの後、それぞれのｗバイトの後に新しいデリミッタが設定される。セグメント化が行われると、第１ブロックは新しいヘッドブロックとして維持され、他の全てのブロックはコアブロックに昇格する。次いで、たとえそれぞれの複製されたパターンが依然として同じストリームセグメントパターン発生とのマッチングをもたらしても、それらは新しいパターンとしてＶＳ−ＤＦＡ内にプログラムされる。
【００６５】
たとえば、パターンｃ１ｃ２ｃ３ｃ４ｃ５ｃ６ｃ７ｃ８ｃ９ｃ１０ｃ１１が最初にｃ１｜ｃ２｜ｃ３｜ｃ４｜ｃ５｜ｃ６｜ｃ７｜ｃ８ｃ９ｃ１０｜ｃ１１とセグメント化され、ｗ＝３であると仮定する。結合規則１の適用後、セグメント化されたパターンは｜ｃ１ｃ２ｃ３ｃ４ｃ５ｃ６ｃ７｜ｃ８ｃ９ｃ１０｜ｃ１１になる。新しいヘッドブロックは２ｗバイトよりもさらに長い。ヘッドブロックの長さを制限するために、パターンが３回複製され、それぞれ新しいセグメント化を以下のように受信する：
｜ｃ１ｃ２ｃ３ｃ４｜ｃ５ｃ６ｃ７｜ｃ８ｃ９ｃ１０｜ｃ１１、
｜ｃ１ｃ２ｃ３ｃ４ｃ５｜ｃ６ｃ７｜ｃ８ｃ９ｃ１０｜ｃ１１、および
｜ｃ１ｃ２ｃ３ｃ４ｃ５ｃ６｜ｃ７｜ｃ８ｃ９ｃ１０｜ｃ１１。
【００６６】
これで、入力ストリーム内のどのコンテキストにパターンが現れても、ｗセグメント化のうちの１つによって確実に捉えられる。
【００６７】
要約すると、組合規則１を適用後に大きなヘッドブロックを有するパターンについては、パターンをｗ回複製することによって、ヘッドブロックが２ｗバイト以内になるように制限される。いくつかの実施形態では、ＤＦＡ内の追加の複製されたパターンを使用することによって、最大ヘッドブロックサイズがさらに制限されることがある。
【００６８】
１バイトブロックの除去
結合規則１は、全ての連続する１バイトブロックを除去する。しかし、残りの分離された１バイトブロックによって、依然として処理が遅くなる場合がある。最悪のケースのスループットは、ステップごとに１．５文字である。ほとんど全ての１バイトブロックを除去するために、他の規則、すなわち結合規則２が改良されたセグメント化手法の様々な実施形態に使用され得る。
【００６９】
結合規則２：結合規則１の適用後、全ての残りの１バイトブロックを、先行するブロックに結合する。パターンでは、これはコアブロックだけに適用する。また、テイルブロックの第１バイトはデータストリーム内の１バイトブロックになるので、このケースをカバーするためにパターンを一度複製して新しいセグメント化を作成する。
たとえば、パターン：
｜ｃ１ｃ２ｃ３｜ｃ４ｃ５｜ｃ６｜ｃ７ｃ８｜ｃ９ｃ１０ｃ１１は、結合規則２の適用後、
｜ｃ１ｃ２ｃ３｜ｃ４ｃ５ｃ６｜ｃ７ｃ８｜ｃ９ｃ１０ｃ１１になる。
【００７０】
しかし、データストリーム内で、パターンのテイルブロックは｜ｃ９｜ｃ１０ｃ１１とセグメント化され得るので、結合規則２がデータストリームに適用されると、セグメント化｜ｃ１ｃ２ｃ３｜ｃ４ｃ５ｃ６｜ｃ７ｃ８ｃ９｜ｃ１０ｃ１１という結果になる場合がある。したがって、両方のパターンセグメント化がＶＳ−ＤＦＡに挿入されるべきである。
【００７１】
しかし、場合によっては、この複製は必要ではない、たとえば、上記のパターンについてｋ＝２の場合、ｗｉｎｎｏｗｉｎｇハッシュ値はｃ９およびｃ１０の位置で計算される。第１の値が第２の値よりも大きい場合、パターン後に何の文字が現れるかにかかわらず、ｉとｊとの間には確実にデリミッタがない。この場合、複製は行われない。結合規則２は、ＤｏＳ攻撃問題を防止して、システムスループットを向上させる可能性がある。結合規則２は、システムに他の影響も及ぼす。最大ブロックサイズが（ｗ＋１）バイトになる。したがって、結合規則１の適用後に長いヘッドブロックを有するパターンは、（ｗ＋１）回複製されるべきである。結合規則はいくつかのパターン複製につながる場合があるが、必ずしもＶＳ−ＤＦＡのメモリ消費を増加させない。反対に、１バイト状態遷移が回避されるので、結合規則は実際にメモリ消費を下げるために役立つ場合がある。
【００７２】
図１１に、改良されたセグメントストリームを生成するために入力データセグメントストリームに適用される結合規則が示されている。図１１（ａ）は、改良されないセグメント処理の適用から得られた入力データセグメントストリームに適用された結合規則１を示している。処理はステップ１１１０から開始する。ステップ１１２０で、入力データシステムの予備のセグメント化を担当するシステムの一部から一連のセグメントが受信される。ステップ１１３０で、連続する１バイトセグメント（ブロック）がｗバイトのセグメントに統合され、ステップ１１４０で連続する１バイトセグメントのそれぞれの残りのセットも単一のセグメントに統合される。残りはオーファンの１バイトセグメントであり、少なくとも１つのマルチバイトセグメントによって相互に分離される。処理はステップ１１５０で終了する。
【００７３】
図１１（ｂ）で、図１１（ａ）の処理から得られるストリームに結合規則２が適用される。特に、処理はステップ１１５０から開始し、ステップ１１６０で、結合規則１の適用によって得られるストリームが受信される。ステップ１１７０で、全ての浮遊１バイトセグメントが、先行するマルチバイトのセグメントに統合される。処理はステップ１１８０で終了する。
【００７４】
本発明は、それらの方法を実行するための方法および装置の形式で実施され得る。本発明は、磁気記録メディア、光記録メディア、ソリッドステートメモリ、フロッピー（登録商標）ディスケット、ＣＤ−ＲＯＭ、ハードドライブ、または他の何らかの機械可読記憶メディアなどの有形メディアに実施されたプログラムコードの形式でも実施でき、プログラムコードがロードされて、コンピュータなどの機械によって実行されると、その機械は本発明を実行するための装置になる。本発明は、たとえば記憶メディアに格納された、機械にロードされたおよび／または機械によって実行された、あるいはいくつかの伝送メディアまたはキャリアを介して、たとえば電線またはケーブルを介して、光ファイバーを通じて、または電磁波を介して伝送された、プログラムコードの形式でも実施でき、プログラムコードがロードされて、コンピュータなどの機械によって実行されると、その機械は本発明を実行するための装置になる。汎用プロセッサに実装されると、プログラムコードセグメントはプロセッサを結合して、特定論理回路に類似して動作する一意の装置を提供する。代替でまたは追加で、本発明または本発明の一部を、これに限定されないが、特定用途向け集積回路（ＡＳＩＣ）またはフィールドプログラマブルゲートアレイ（ＦＰＧＡ）を含む、様々な形式で実装できる。上述の実施形態の全ては、プロセッサ、ソフトウェアを有するプロセッサ、ＡＳＩＣ、ＦＰＧＡ、スタンドアロン論理回路、あるいは電子または光回路にかかわらず、本明細書では「機械」という特許請求の範囲の専門用語の範囲内であることが理解されるべきであり、「機械実装された」は、これに限定されないが、上述の実装形態のいずれか、ならびに当業者によってそれらの技法と同等であると理解される他の実装形態技法を含むものと理解されるべきである。
【００７５】
特に明記しない限り、それぞれの数値および範囲は、「約」または「ほぼ」が値か範囲の値に先行するかのように、概算であると解釈されるべきである。
【００７６】
添付の特許請求の範囲に記載した本発明の範囲から逸脱することなしに、本発明の特質を説明するために記載および図示された部品の詳細、材料、および構成における様々な変更が当業者によって行われ得ることがさらに理解されよう。
【００７７】
本明細書で説明した例示的方法のステップは、必ずしも記載の順序で実行される必要はないことが理解されるべきであり、このような方法のステップの順序は例示に過ぎないことが理解されるべきである。同様に、このような方法に追加のステップが含まれてよく、本発明の様々な実施形態と一致する方法において、特定のステップが省略および結合されてもよい。
【００７８】
添付の方法クレーム内の要素は、もしある場合は、対応するラベル付けとともに特定のシーケンスで述べられているが、クレーム記述がそれらの要素のうちのいくつかまたは全てを実装するための特定のシーケンスを含意しない限り、それらの要素はその特定のシーケンスで実装されることに限定されることを必ずしも意図しない。
【００７９】
本明細書における「一実施形態」または「ある実施形態」への言及は、実施形態に関連する特定の特徴、構造、または特性が、本発明の少なくとも１つの実施形態に含まれ得ることを意味する。本明細書の様々な個所における「一実施形態では」というフレーズの出現は、必ずしも全て同じ実施形態を指すものではなく、また必ずしも他の実施形態を相互に除外する別のまたは代替の実施形態を指すものでもない。同じことが、用語「実装形態」にも当てはまる。
【００８０】
上記の説明における例の多くが英語の単語および文字を利用するが、本発明のセグメント化スキームの利点は、あらゆる任意の入力バイトストリーム、および／またはバイトパターンにも適用できることである。したがって本スキームは、セグメント化をサポートするためにストリームの意味コンテキストに依存しない。たとえば、英語文書内に見られる句読点、ホワイトスペース、大文字の使用、および／または他のコンテキスト要素は、このような文書で見られるマルチバイト文字ストリング間の境界を区切るために使用でき、本発明はこのようないかなるコンテキスト依存システムも必要としないので、どのような任意のバイトシステムにも適用可能である。
【００８１】
さらに、本発明はデータのバイトで構成されるデータストリームとの関連で記述したが、バイナリデータのオクテットに限定されるものではない。一例を挙げると、データの８ビット表示の代わりに、データの代替表示では、１０、１２、または他の何らかの数のビットが記号を表すために使用される場合、本発明は代替表示に等しく適用可能である。すなわち、本発明は一般にどのような任意の入力「シンボル」ストリームにも適合するというのが適切である。さらに、同様に、これらのシンボルは特に長さが８ビットである必要はなく、またこれらのシンボルが２進法表示に限定される必要もない。
【００８２】
上述の実施形態の多くが、入力シンボルストリーム内のｋグラムから特別なハッシュ値を選択するためにハッシュ関数および最小値フィルタを組み込む例示的ｗｉｎｎｏｗｉｎｇ関数を使用して示されている。ハッシュ関数自体は、一方向性関数として知られている関数のクラスの一例であり、最小値フィルタは、１つとセットとを区別するための一連の数に適用され得るフィルタまたは基準のクラスの一例である。当業者には理解されるように、一般的に本発明は実施形態の例に限定されるべきではないが、以下に述べる特許請求の範囲の全体的な範囲を保持する。
【図１】
0005373184.tif 000002
【図２】
0005373184.tif 000003
【図３】
0005373184.tif 000004
【図４】
0005373184.tif 000005
【図５】
0005373184.tif 000006
【図６】
0005373184.tif 000007
【図７】
0005373184.tif 000008
【図８】
0005373184.tif 000009
【図９】
0005373184.tif 000010
【図１０】
0005373184.tif 000011
【図１１】
0005373184.tif 000012