侵入検出アクセラレータ
ネットワークコンピュータシステム又はそのノードへの侵入若しくは攻撃の可能性、或いは他のセキュリティの穴を示すことのある、文書内の文字記号列の固有特徴は、ハードウェアパーサアクセラレータ杯のハードウェアアクセラレータを用いて高速で検出される。割り込み又は例外は、このため、このようなセキュリティの穴、侵入、或いは攻撃を構成し得るコマンドが文書のパーシングによって実行可能な状態になり得る前に、ホストＣＰＵに対して発行される。ＣＰＵは、侵入を阻止若しくは制限するために、ネットワーク制御処置を開始することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ＸＭＬ（商標）文書のような文書のパーシングに関し、より具体的には、ネットワークのノードに対する侵入の可能性や攻撃を検出するための、文章や、ネットワークデータパケットの他の論理シーケンスのパーシングに関する。
【背景技術】
【０００２】
ネットワークにおけるコンピュータとコンピュータの接続との間のディジタル通信の分野は、近年多様な形態で急速に発達し、ここ数年のパーソナルコンピュータの急増をもたらしている。この、相互連結、および遠隔処理の可能性における増加は、ネットワークシステム等における個々のコンピュータの有効能力および機能を大きく発展させた。それでもやはり、個々のコンピュータやシステムの使用、それらのユーザの好み、並びにコンピュータが用いられる際の技術の状態などの多様性は、個々の装置の能力や構成並びにそれらのオペレーティングシステムに、実質的な程度における多様性を生み出しており、「プラットフォーム」と総称されるこれらは、一般に、ある程度の範囲で、特にオペレーティングシステムとプログラミング言語のレベルにおいて、相互互換性を欠いている。
【０００３】
このプラットフォーム特性の非互換性、および、これと同時に生ずる通信および遠隔処理、並びにそれをサポートするに足る十分程度の互換性に関する要求は、結果として、プログラミングに関する対象と（本質、属性、および関係の基準システムを通して、多少とも一般化されたモジュールのグループとしてアプリケーションやデータを集めようというコンセプトを含む）、それを具現化するための多数のプログラミング言語とを発展させた。エクステンシブル・マークアップ・ランゲージ（ＸＭＬ；商標）は、このような言語であり、広く普及していると共に、任意の構成およびアーキテクチャを有するネットワークを介して文書として送信することができる。
【０００４】
このような言語において、特定の文字記号列は、特定のコマンドや識別に対応しており、特別な文字や他の重要なデータ（制御ワードと総称する）を含み、それらは、データや演算が事実上自身を識別し得るようにして、以後、それらが「オブジェクト」として取り扱われるようにするためのものであり、これにより、結びつけられたデータとコマンドは、言語の異なる相違するアプリケーションで用いられる適当なフォーマットとコマンドに変換されることができ、その結果、接続されたプラットフォームのそれぞれにおいて、特定の機械で所望の処理の実行をサポートするに足る互換性が生み出される。これらの文字記号列の検出は、パーシングとして知られる処理により実行され、センテンス等の表現の系統的配列（syntax）をそれらの構成部分に分解し、また、それらを文法的に表現する従来の手法に類似している。
【０００５】
ＸＭＬ（商標）文書をパーシングする際、中央処理ユニット（ＣＰＵ）の処理時間の大部分、おそらく殆どは、処理されている特定のＸＭＬ（商標）標準に対して定義されている制御ワード、特定文字、および他の重要なデータを探すための文書の通読に費やされる。この処理は、通常は、個々の文字を照会して、それが、例えば以下のような「＜ｃｏｍｍａｎｄ＞」、「＜ｄａｔａ＝ｄａｔａｗｏｒｄ＞」、「＜ｅｎｄｃｏｍｍａｎｄ＞」等を含む所定の興味記号列のセットに属しているかを判断するソフトウェアにより実行される。何れかの対象記号列が検出されると、トークンが、トークンの開始とトークンの長さのために、ポインタと共に文書中のその位置に記録される。これらのトークンは、文書の全てが解析（パース）されるまで蓄積される。
【０００６】
従来のアプローチは、興味の対象であるこれらの記号列を探すために、テーブルを基礎とする有限状態装置（ＦＳＭ）を実現することであった。その状態テーブルは、メモリ内に備わっており、文書内の特定のパターンを探すように設計されている。現在の状態は状態テーブルに対する基礎アドレスとして用いられ、また、入力された文字のアスキー（ＡＳＣＩＩ）表現がそのテーブルにおけるインデックスである。例えば、その状態装置が０（ゼロ）状態にあり、最初の入力文字がアスキー値０２であるとすれば、状態エントリのための絶対アドレスは、基礎アドレス（状態０）とインデックス／アスキー値（０２）の和／連結となる。ＦＳＭは、ＣＰＵが入力文書の最初の文字をメモリから読み取ってくるのに伴って起動する。ＣＰＵは、次に、初期／現在状態および入力文字に従って、メモリ内の状態テーブル中に絶対アドレスを構成し、その状態テーブルから状態データを読み取る。ＣＰＵは、返された状態データに基づいて、現在の状態を新たな値に更新し、もし異なる場合は（その文字が興味記号列の最初の文字に対応することを表示して）、その状態データに示されている他の何らかの動作を行う（例えば、単独文字が特定文字である場合や、現在の文字が、更なる進行の繰り返しに伴い、興味記号列の最後の文字であると判明した場合は、トークンや割り込みを発生する）。
【０００７】
上記の処理は繰り返され、何れかの興味記号列の文字が後に検出される毎にその状態が変更される。つまり、初めの文字が興味記号列の初めの文字として興味の対象である場合は、ＦＳＭの状態が新たな状態に進められる（例えば、初期状態０から状態１）。その文字が興味対象でない場合は、状態装置は（一般に）同じ状態（例えば状態０）を特定することで同一に維持される、若しくは、状態テーブルのアドレスから返された状態テーブルエントリにおいて状態の更新を指示しない。可能性のある動作には、これに限られるものではないが、割り込みの設定、トークンの記録、およびポインタの更新が含まれる。その後、以後に続く文字につき処理が繰り返される。ところで、興味記号列が続けられており、ＦＳＭが状態０以外の状態（若しくは、興味記号列が未だ検出されていない、或いは現在続けられていることを表す他の状態）にある場合には、現在の記号列と一致せず、他の興味記号列の最初の文字と一致する文字が検出されることがある。このような場合に、状態テーブルエントリは、先に継続された記号列の断片または部分を示し、かつ識別するうえで、また、新たな記号列が完全に識別されるか興味記号列でないことが判明するまで、可能性のある新たな記号列を追跡するうえで好適な動作を示す。換言すると、興味記号列は、包み込まれていることがあり、状態装置は、他の興味記号列等の中にある興味記号列を検出できなければならない。このため、ＣＰＵは、ＸＭＬ（商標）文書の部分部分を何度も通読してＸＭＬ（商標）文書の解読（パース）を完了させなければならない。
【０００８】
ＸＭＬ（商標）や他の言語の文書は、上述した手法により１文字ずつ解読（パース）される。可能性のある対象記号列が認識される毎に、興味記号列が完全に識別され、或いは、可能性のある興味記号列と一致しない文字が検出されるまで（例えば、記号列が最後まで／完全に一致し、または文字が対象の記号列から外れたとき）、ＦＳＭは、様々な状態を経由して１文字ずつ処理を進める。後者の場合、一般に、初期状態、或いは他の対象記号列の始めの文字の検出に対応する状態に戻る他は、何ら動作が行われない。前者の場合、トークンが、入力文書内での開始アドレスとトークンの長さと一緒にメモリ内に記憶される。パーシングが完了するまでに、全ての対象が識別され、特定箇所の若しくは所定のプラットフォームに従う処理が開始可能となる。
【０００９】
探索は一般に複数の興味記号列について実行されるため、状態テーブルは、如何なる所定の状態からでも複数の変化を提供することができる。このアプローチによれば、包み込まれた記号列に便利良く適応しつつ、現在の文字を同時に複数の対象記号列に対して分析することができる。
【００１０】
以上のことから、ＸＭＬ（商標）文書のような文書のパーシングは、多数の繰り返しと、個々の繰り返しにおける多数のメモリアクセスとを要求することが判る。このため、一般用ＣＰＵにおける処理時間は、必然的に相当なものとなる。複数の記号列を取り扱うことの更なる主たる複雑さは、大きな状態テーブルを生成する点にあり、また、リアルタイムによるパケット処理からオフラインで取り扱われることである。しかしながら、これにより、入力文字データの取得、状態データの取得、および、文書中の個々の文字に関する種々のポインタおよび状態アドレスの更新のために、多数のＣＰＵサイクルが要求される。このため、ＸＭＬ（商標）文書などの文書のパーシングを行うにあたっては、他の処理に先んじてＣＰＵやプラットフォームが占有され、所望の処理に大きな遅れを生じさせるのが比較的通常である。
【００１１】
従来、一般用のハードウェアは、プログラミングを介して、専用のハードウェアの機能と同等の機能を実現し得ること、および、専用のハードウェアの管理および制御には固定負荷が少ないため、構成とプログラムが互いに正確に一致していたとしても、専用のデータ処理ハードウェアは、プログラムされた一般用ハードウェアよりも高速で機能するのが通常であることが認識されていた。それにもかかわらず、特定の処理のために専用ハードウェアに要求されるハードウェアリソースは、特に処理速度のゲインが最低境界付近にある場合には、法外に大きなものとなり得る。更に、専用ハードウェアは、必然的に機能上の限界を有しており、また、任意の組み合わせに係る任意の数の文字を探索する能力を提供するような特定のアプリケーションに対する十分な柔軟性においても制限がある。このため、専用ハードウェアが適当であるためには、処理速度において大きなゲインを提供しつつ、非常に本質的なハードウェア経済を提供しなければならず、これらの要求は、所望の処理機能において必要とされる機能上の柔軟性やプログラム可能性の程度が高まるに連れて、同時に適応することがより一層困難になっている。
【００１２】
この点に関して、システムセキュリティの問題が、接続可能性と、ＸＭＬ（商標）文書のような文書のパーシングに要求される処理時間の量との双方から生じている。一方では、相対的に高い優先度で非常に大きな処理時間を要求する何らかの処理は、幾つかの点において、システムやそのノードに対するサービス不能（ＤＯＳ）攻撃と似通っており、また、このような攻撃において用いうるツールともなり得る。
【００１３】
ＤＯＳ攻撃は、稼働状態にあるリソースを悪意をもって浪費させ、また、ついには過負荷状態とするために、システムに対してつまらない奇形のサービス要求を頻繁に与える。ハードウェアアクセラレータの適正な構成は、稼働状態にあるリソースが過負荷状態となる可能性を大幅に低減し、または除去することができる。更に、システムは、過負荷状態である場合に、しばしば異常となり、或いはセキュリティの弱点を露出する。このため、過負荷を除去することは、セキュリティ上、重要な考慮事項である。
【００１４】
更に、状態テーブルは、システムパフォーマンスの深刻な低下を伴うこと無しに、保証することが困難若しくは不可能な基礎レベルにおいてＣＰＵのコマンドを含むことができなければならないため、パーシングが終了する以前から、幾つかの処理は開始することが可能でき、また、幾つかのコマンドは実行することができる。つまり、セキュリティの低下の可能性は、ＸＭＬ（商標）パーシングなどを処理するための処理時間の短縮により、必然的に低減されるが、このようなパーシングの処理時間を画期的に短縮する技術は何ら提供されていなかった。
【００１５】
多くのセキュリティシステムは、非常に早い段階では、企てられたセキュリティの穴（security breach）を検出する能力に依拠しており、セキュリティの穴は、一旦開始されると、迅速に、或いはプログラムによる介入により、遮ることが困難若しくは不可能である。例えば、高度な保証システムが提案されており、何れも本出願の譲受人に譲受された米国特許０９／９７３，７６９および０９／９７３，７７６に開示されている。これらの出願は、２つのレベルのノード間通信を有しており、ひとつは、非常に高速であり、これによれば、攻撃の可能性や侵入が検出されたノードは、隔離され、必要であれば、その後、ネットワークに再び接続される前に自動的に修復される。従って、パーシングのアクセラレーションは、ネットワークの適切な制御を、パーシングの出来事として開始することができ、このため、パーシングが画期的に加速されれば早い時点から開始することができることから、攻撃の可能性に対する早期応答を支援するものであり、特に、上記の編入した特許出願中に記載されたシステムにおいて開示されているようなシステムにおいて有効である。検出警報に応じて、適時な方式出開始される適切なネットワーク制御によれば、侵入の検出に加えて侵入の防止を達成することができる。
【発明の開示】
【００１６】
この発明は、リアルタイムによる侵入検出および動作防止を可能とするネットワーク伝送パケット速度で、侵入の可能性、攻撃、或いはコンピュータネットワークシステムにおける他のセキュリティの穴の固有特徴を検出するための文書パーシングの極限の加速を提供するハードウェアパーサアクセラレータを提供する。
本発明のこれらおよび他の事項を達成するため、文書パーサ中に実現することができ、文書の複数バイトのための文字バッファと、割り込み又は例外、および状態テーブルからの次状態データの少なくとも一方にアクセスするために、文書の１バイト及び状態に従ってアドレスを定めることのできる状態テーブルと、次状態データを記憶するレジスタと、状態メモリに対するアドレスを更に形成するためにレジスタの内容を文書の続きのバイトに組み合わせる加算器と、割り込みまたは例外をＣＰＵに通信するためのバスとを備える侵入検出システムを提供する。
【図面の簡単な説明】
【００１７】
以上の、および他の事柄、様相および効果は、以下に続く好ましい実施形態の詳細な説明と、図面の参照により一層理解することができ、図面には以下の事項が記載されている。
【図１】図１は、文書のパーシングに用いられる状態テーブルの一部を表す。
【図２Ａ】図２Ａは、同時に提出した関連のある暫定特許出願に係るパーサアクセラレータを、高度に概要化した図である。
【図２Ｂ】図２Ｂは、本発明に係るパーサアクセラレータを、高度に概要化した図である。
【図２Ｃ】図２Ｃは、本発明の実現を、ホストプロセッサとメインメモリと共に示す。
【図３】図３は、図２Ａに示す文字パレットの好ましいフォーマットを示す。
【図４】図４Ａおよび図４Ｂは、図２Ａに示す発明の好ましい形態における状態テーブルのフォーマットと、これと結合して用いられる状態テーブル制御レジスタとを示す。
【図５Ａ】図５Ａは、図２Ａに示す次状態パレットの好ましいフォーマットを示す。
【図５Ｂ】図５Ｂは、図２Ｂに示す発明と共に用いるうえで好ましい状態テーブルエントリのフォーマットを示す。
【図６】図６は、図５に示すトークンの好ましいフォーマットである。
【発明を実施するための最良の形態】
【００１８】
以下、図面、より具体的には図１を参照して、そこには文書のパーシングに用いられる状態テーブルの一部の表示が示されている。図１に示される状態テーブルは、ＸＭＬ（商標）文書のパーシングに有効な状態テーブルの極小さな一部のみであり得ると共に、本質的に例示を意図したと解されるべきものである。本発明中に、少なくとも表示した形式中には、状態テーブルの全ては物理的に存在しておらず、また、図１は、公知のソフトウェアパーサの動作の理解を容易ならしめるためにも用いることができるが、本発明との関係において、図１の如何なる部分も、従来技術と認められるものではない。
【００１９】
ところで、ＸＭＬ（商標）文書は、ここでは、本発明に係るアクセラレータを利用して処理され得る論理データシーケンスの一つのタイプの例として用いられている。他の論理データシーケンスは、分担されたサーバコンピュータによる実行を意図したユーザ端末命令記号列のようなネットワークデータパケットの内容からも構築することができる。このような記号列は、悪意のユーザによりしばしば生成され、長期の侵入の試みの一部として分担されたサーバコンピュータに送信される。本発明に係るアクセラレータは、このような論理データシーケンスの多くを処理するのに適している。
【００２０】
図１に示された状態テーブルの部分における多くのエントリが重複であることは、有益な注意点であり、図１に表されている状態テーブルの全体を収容するハードウェアが必要でないことも本発明を正しく理解するために重要である。反対に、本発明は、おそらくは専用のプロセッサを用いて、ソフトウェアの内部で実現することが可能であるが、ソフトウェアによるパーシングのために処理時間が増加する不利益は、ハードウェアにおける如何なる経済的可能性によっても正当化はされず、本発明に係るハードウェアの要求は十分に制限されている。
【００２１】
しかしながら、侵入検出システムが、ディジタルファイルの如何なるタイプにも適用可能であるように意図されること、および、一般にセキュリティ攻撃が実行される際に介在するネットワークにおいてリアルタイムによるディジタル伝送に適合しうるパケット伝送速度で、或いはそれ以上の速度で特定のアプリケーションやデータ構造を表すのに用い得るテキストファイルや特定言語に限定されないことは、評価されるべきである。このため、本発明は、侵入検出のみを提供する装置として実現してもよく、その場合は、最低のコストで実質的に理想的なパフォーマンスを得ることを期待することができる。しかしながら、侵入検出を単一の伝送速度で実行するという目的は、更なる加速を提供するために幾つかの処理を省略する、パーサアクセラレータ処理の特別のモードとしても、おそらくは、以下に説明すると共に現時点で好ましいと考えられている選択可能な状態テーブル装置によって増大された状態で、達成することができる。従って、リアルタイムによる高速での侵入検出という本発明が意図した機能に対して必要以上に状況は複雑になるが、完結の興味において、また、本発明により提供される効果の範囲のより完全な理解を伝達するために、本発明は、パーサアクセラレータの状況において説明することとする。
【００２２】
図１において、状態テーブルは、任意数の行に区分されており、それぞれの行は、状態に対応する基礎アドレスを有している。基礎アドレスの行は、解読（パース）される文書中の文字を表すのに用い得るコードの数；この例では、状態テーブルにおけるインデックスとして用いられる文字のための８ビット・バイトに対応する２５６行、に対応する数の列に区分されている。
【００２３】
図示された状態テーブルのエントリの幾つかの様相に注目することは、特に、図１に示された、状態テーブルのほんの小さな部分が、どのようにして多くのワードをサポートしているかの理解を伝えるうえで有効である。
【００２４】
１．図示された状態テーブルでは、状態０の行において、２つのエントリだけが、テストされた文字が如何なる興味記号列の初めの文字とも一致しないときに初期状態を維持する「状態０に残留」以外のエントリを含んでいる。状態１への進行を提供する単一のエントリは、全ての興味記号列が同じ文字で始まる特別な場合に対応している。他の状態への進行を提供する他の文字は、一般に、但し必須ではなく、状態１以外への進行を提供するが、他の文字を介して到達し得る同一の状態を更に参照することは、例えば、包み込まれた記号列を検出するために有効であり得る。｛状態０、ＦＤ｝に示すように「状態０に残留」にコマンド（例えば「特別割り込み」）を含ませることは、特別な単一文字に対する検出および実行に用いられる。
【００２５】
２．状態０より上の状態における「状態ｎに残留」は、普通に遭遇するような、例えば、コマンドの数値引数において遭遇することのあるような一つ以上の文字の潜在的な長期実行を通じて維持されるべき状態に備えたものである。本発明は、以下に詳細に説明するように、十分なアクセラレーションを提供するために、このタイプの文字記号列につき特別な取り扱いを提供する。
【００２６】
３．状態０より上の状態における「状態０へ移動」のエントリは、それまでに、整合する文字がいくつ検出されていたとしても、その記号列を、如何なる興味記号列とも区別する文字が検出されたことを知らせるものであり、また、パーシング処理を、他の興味記号列の探索を始めるためのイニシャル／デフォルト状態に戻すものである。（この理由のため、「状態０へ移動」は、一般に、突出して最も高い頻度で数多く状態テーブル中に表れるエントリである。）状態０への復帰は、パーシング処理を、区別の目安となる文字が検出された時点で追跡されていた記号列を開始していた文字に続いて文書中に存在する文字に復帰させる。
【００２７】
４．コマンドと「状態０へ移動とを含むエントリは、完結した興味記号列の検出の完了を示す。一般に、そのコマンドは、以後、記号列をオブジェクトと取り扱うことを可能とするためのトークンを（トークンのアドレスおよび長さと共に）記憶することである。しかしながら、「状態ｎへ移動」に伴うコマンドは、興味記号列と合致する可能性のある記号列の追跡を継続しながら、中間点において処理を発動するためのものである。
【００２８】
５．探索が２つの興味記号列（例えば、ｎ−１個の同一の始めの文字とｎ番目の異なる文字、或いは、異なる初めの文字を有する記号列）に枝分かれする全ての点で不明確さを回避するためには、一般に、｛状態１，０１｝および｛状態１，ＦＤ｝に示すように、異なる（非連続な）状態に進むことが必要である。任意の長さｎの記号列の識別を完了させるには、特別な文字を含む記号列および共通する初めの文字を有する興味記号列が含まれる特殊な環境を除いて、ｎ−１の状態を必要とする。これらの理由により、興味記号列の数が比較的多くない場合であっても、状態および状態テーブルの行の数は、通常、著しく大きなものとなる。
【００２９】
７．これまでのパラグラフに反して、殆どの状態は、一つか二つの特有なエントリとデフォルトの「状態０に移動」とによって完全に特徴付けられる。図１に示す状態テーブルが有するこの特徴は、本発明において、ハードウェアの高度な経済性と、興味記号列の一般的な場合に対するパーシングプロセスの相当なアクセラレーションとを生み出すために利用される。
【００３０】
以上から判るように、パーシング処理は、従来から実行されていたように、図１において状態０と示されている所定のデフォルト／イニシャル状態にあるシステムで開始され、その後、処理の繰り返しに伴って整合する文字が発見されるに従って、より数の大きな状態に進行する。興味記号列が完全に識別された際、或いは、整合の可能性のある記号列の途中において特別な処理が特定された際に、トークンの記憶や割り込みの発生などの処理が実行される。しかしながら、文書の個々の文字に対する個々の繰り返しにおいて、その文字がＣＰＵメモリから読み出されなければならず、状態テーブルのエントリが（再びＣＰＵメモリから）取り込まれなければならず、また、（例えば、文書の文字および状態テーブルの基礎アドレスに対する）種々のポインタが連続処理の中で更新されなければならない。従って、そのパーシング処理は、多大な処理時間を消費し得るものとして即座に評価し得るものである。
【００３１】
本発明に係るパーサアクセラレータ１００を高度の概要化したブロック図を図２Ａに示す。当業者にとって、そのように評価されるように、図２Ａは、本発明においてパーシングを実行するために実行される工程を示すフローチャートとしても理解することができる。図３、図４Ａ、図４Ｂ、図５Ａおよび図６を参照して以下により詳しく説明するように、本発明は、僅かながら時間的なずれを伴って本質的には並列に作動するような複数のハードウェア経路が達成されるように、状態テーブルを表すにあたり、幾つかのハードウェア経済を利用する。このため、並列で作動させられる高速アクセスのハードウェア、および、状態テーブルと文書との関係でのＣＰＵメモリからの先行取得の双方を通じてメモリアクセスに必要とされる時間を大きく低減しつつ、ポインタおよびレジスタの更新は、ほぼ同時に、かつ、他の処理と同時発生的に行うことができる。
【００３２】
一般的な概観として、ＸＭＬ（商標）文書のような文書は、レジスタ１１２，１１４により索引付けられたＤＲＡＭ１２０中に外部的に記憶され、複数経路のためのマルチプレクサとして機能する入力バッファ１３０に、好ましくは３２ビットのワードで転送される。個々の経路は、文字パレット１４０、状態テーブル１６０、および次状態パレット１７０の写しを有しており、それぞれが、状態テーブルの部分の圧縮形式を収容している。次状態パレット１７０の出力は、状態テーブル１６０におけるエントリを指すアドレスである次状態アドレスの部分と、もし存在すれば、記憶されるべきトークン値との双方が含まれる。文字パレット１４０および次状態パレット１７０における動作は、互いに並列に、かつ、状態テーブル１６０（これもキャッシュとしても実現され得る）を形成する高速外部ＳＲＡＭへの単純なメモリアクセスとも並列に動作することのできる高速内部ＳＲＡＭへの単純なメモリアクセスである。従って、これらのハードウェア要素を始めに制御するＣＰＵのほんの僅かな数クロック周期だけで（しかし、そのハードウェア要素は、一度起動すると、文書データをリフレッシュするため、およびトークンを記憶するためのＣＰＵによる偶発的なＣＰＵ処理の呼び出しのみに対して自律的に作動する）、文書中の個々の文字を評価することができる。ＣＰＵにおける一文字当たりの全メモリ処理の継続の積算における低減と、高速ＳＲＡＭ或いはＤＲＡＭにおいて自律的に行われる単独のメモリ処理の継続に対するＣＰＵの固定負荷との和がアクセラレーションによる基礎ゲインである。
【００３３】
ところで、ここで「外部」と称されるメモリ構成は、メモリ１２０，１４０の構成の暗示を意図したものであり、必要とされる記憶容量、並びに、ハードウェアパーサアクセラレータから、および／またはホストＣＰＵからのアクセスの視点において、現時点で発明者が好ましいと思うものである。換言すると、メモリの分配、或いは、少なくともホストＣＰＵ並びにハードウェアアクセラレータによるメモリへのアクセスを容易ならしめるように本発明に係るパーサアクセラレータのアーキテクチャを提供することは、トークンや他の処理を取り扱ううえで効果的である。この説明の観点より、意図しない他の暗示や、同期ＤＲＡＭ（ＳＤＲＡＭ）のような種々のハードウェアの変形例は、当業者にとって理解可能であると思われる。
【００３４】
以下、図３乃至図６を参照して、文字パレット１４０、状態テーブル１６０、次状態パレット１７０および次状態、並びにトークンのフォーマットを、図２Ａの好適な実現をサポートするハードウェア経済の例示として説明する。他の技術／フォーマットも使用が可能であり、また、示されたフォーマットは、現時点で好ましいものではあるが、あくまで例示として理解されるべきものである。
【００３５】
図３は、興味記号列に含まれ、或いは含まれ得る文字に対応する文字パレットの好適な形式を示す。このフォーマットは、好ましくは、図１に示す状態テーブルの列の数に対応して、０−２５５の数字が付されたエントリを提供する。（「パレット」の用語は、多分に、サポートされている個々の色のデータを含み、総じて全域と称される「色パレット」の用語の場合と同じ感覚で用いられている。パレットの使用により、状態テーブルのエントリ／列が低減される。）例えば、状態を変化させることのない「空文字」と称される文字は、多くの列を要することなく、状態テーブルの一つの列中に表すことができる。１４４において空文字出力をテストすることが望ましく、そのテストによれば、状態テーブルにアクセスするための更なるメモリ処理を必要とすることなく次の文字の即座処理が許可されることから、パーシングの処理を相当に加速することができる。そのフォーマットは、例えば、特定の文字パレット（図２中に、重なり合うメモリ面で図示）に関連付けられた基礎アドレスレジスタ１４２中のデータ等により構成された単一のレジスタ、或いはメモリ中の複数位置により収容することができる。文書（例えばＸＭＬ（商標）文書）から提供された現在の８ビット文字、つまり、外部ＤＲＡＭ１２０からの４バイトのワードとして受け取られてインプットバッファ１３０から提供された４つのうちの一つにより文字パレットのエントリのアドレスが指定され、文字パレットは、次いで、インデックス、若しくは、ポインタの一部として、状態メモリに入るアドレスを出力する。このため、このようなフォーマットをパレットに提供することにより、図１に示す機能の一部を、比較的容量が制限された単一のレジスタの形式中に持たせることができ、その結果、それらを複数形成して、並列に作動させる一方で、本質的なハードウェア経済を維持し、かつ、状態テーブル１６０内の他の要素をサポートすることができる。
【００３６】
図４Ａは、文字パレット（例えば、実質的にはレジスタ）に類似するように構築或いは構成された好ましい状態テーブルのフォーマットを示す。図３に示す文字パレットとの主たる相違は、レジスタの長さが、要求された文字に対する応答の数と、興味記号列の数および長さに依拠している点である。従って、経済的に配置されていた内部メモリの量が特定の場面で不十分である際には、このメモリをＣＰＵまたは他の外部ＤＲＡＭ（おそらくは内部または外部のキャッシュと共に）内に実現するための可能性を準備しておくことが好ましいと考えられる。とはいえ、図１に示す状態テーブルにおける多数の重複エントリが単一エントリに、つまり、図３に示す文字パレットに従って上記のように提供されるデータに収容されるアドレスに低減されていることから、本質的なハードウェア経済が提供されていることは明らかである。状態テーブル１６０の出力は、１、２または４ビットであることが望ましいが、３２ビットまでの変形は、図４Ｂを参照して以下に説明するように、より大きな柔軟性を提供し得るものである。
【００３７】
図４Ｂを参照して、この後者に関する本発明を完成させる特徴として、本発明の好ましい実施形態は、特に状態テーブル１６０が３２ビットの出力を発する場合に、更なる本質的なハードウェア経済を実現する状態テーブル制御レジスタ１６２を含むものである。特に、その状態テーブル制御レジスタは、状態テーブルに、可変長のワードの記憶と読み出しを可能ならしめることにより、状態テーブルの情報の圧縮に備えることができる。
【００３８】
より具体的には、状態テーブル制御レジスタ１６２は、図４Ａに示す状態テーブルにおける個々のエントリの長さを記憶し、また、提供する。図１に示す状態テーブルのエントリは、高度に重複しているため（例えば、「状態０へ移動」、「状態ｎに残留」）、これらのエントリは、状態テーブル１６０中に単一のエントリで、若しくは、少なくとも図１に示すより十分に少ない数で表すことができるのみならず、より少ないビットで、おそらくは、ある種の状態テーブルにおいては便利であることが認められるように、重複エントリの大部分若しくは全てがその状態テーブルに含まれる場合であっても、本質的なハードウェア経済を実現することができる程度に少ないビットで表すことができる。この低減の原理は、当業者にとっては、所謂エントロピーコーディングと類似するものとして理解することができる。
【００３９】
以下、図５Ａを参照して、次状態パレット１７０の好ましいフォーマットを説明する。次状態パレット１７０は、好ましくは、上述した文字パレット１４０とほぼ同様の手法で実現される。しかしながら、状態メモリ１６０の場合と同様に、要求されるエントリの数は、既知でなく、個々のエントリの長さは、好ましくは、より十分に大きなものである（例えば、２つの３２ビットワード）。他方、如何なる所与の時間においても、比較的小さく、かつ、予測可能なアドレスの幅だけが収まれば足りるため、次状態パレット１７０は（例えば、次状態パレット基礎アドレスレジスタ１７２を用いて）キャッシュとして作動させることができる。更に、状態テーブル１６０から３２ビットの出力が提供される際には、それらのデータの幾つかは、次状態パレット１７０のエントリ内のデータを補い、可能であれば後者のエントリの短縮を許容し、或いは、可能であれば、破線１７５で示すように、次状態パレットを完全にバイパスする。
【００４０】
図５Ａに示すように、次状態パレット１７０から出力された下方アドレスの３２ビットワードは、格納されるべきトークンである。このトークンは、好ましくは、８ビットの制御フラグ、並びに、何れも記号列の開始に対するポインタ１９２により提供されたアドレスにおいて、かつ、成功した文字比較のカウントにより蓄積した長さと一緒にトークンバッファ１９０に記憶される、１６ビットのトークン値および８ビットのトークンフラグとして形成される。制御フラグは、ホストＣＰＵ、或いはパーサアクセラレータ中の制御処理に対して割り込みをセットする。後者の制御フラグのうち一つは、好ましくは、既に言及したように、興味記号列内に生じ得る任意の長さの文字と同一または関連する記号列のように、状態０以外の状態において状態を変化させる原因とならない文字のスキップ可能化機能をセットするために用いられる。このような場合においては、次状態テーブルのエントリは、ＳＲＡＭ／ＤＲＡＭから読み取ってくることなく、再び用いることができる。入力バッファアドレス１１２は、追加の処理を伴わずにインクリメントされ、特定の文字記号列に対するパーシングの更なる本質的な加速が実現される。第２の３２ビットワードは、レジスタ１８０および加算器１５０にフィードバックされ、文字パレットから出力されるインデックスと連結されて、次の文字のための状態テーブルに対するポインタを形成するアドレスオフセットである。状態０に対応する初期アドレスは、レジスタ１８２によって供給される。
【００４１】
このため、文字パレット、簡略形式での状態メモリ、および次状態メモリの使用は、従来の状態メモリ処理を、区分された段階に明確化し、それぞれの段階は、相対的に小さく、かつ高速であり、それ故に重複が可能であり、文書中のそれぞれの文字を、他の処理およびトークンの格納と共に、順番に、かつ並列に処理する並列経路を構成し得るメモリを用いて、著しく高速に実行することができる。従って、そのパーシングプロセスは、他の文字の処理が開始される以前にこれらの機能の全てを順番に実行する専用プロセッサとの比較においてさえ相対的に大幅な加速を実現することができる。
【００４２】
要約すると、アクセラレータは、文字データ（場合によってはネットワークへの送信の意味を含んでパケットデータと称される）と状態テーブルが配置されているホストＣＰＵのプログラムメモリにアクセスする。アクセラレータ１００は、メモリマップ化されたレジスタを介してメインＣＰＵにより制御される。アクセラレータは、メインＣＰＵに割り込みをかけて、侵入検出の状況においては一般的にパターンマッチング警報と称することのできる例外、警告、および終了を示すことができる。侵入イベント警報など。パーシングが開始されると、ポインタ（１１２，１１４）が、分析されるべき入力バッファ１３０のデータの最初と終わりにセットされ、使用されるべき状態テーブルが基礎アドレス１８２により示され、更に、他の制御情報（例えば、１４２）がアクセラレータ内に設定される。
【００４３】
アクセラレータの処理を開始するため、ＣＰＵは、アクセラレータのコマンドを発し、アクセラレータは、これに応えてＣＰＵのプログラムメモリ（例えば１２０またはキャッシュ）から最初の３２ビットワードのデータを読み込み、これを入力バッファ１３０に置き、最初のバイト／ＡＳＣＩＩ文字はそこから選択される。アクセラレータは、現在の状態と入力文字に対応する状態情報（つまり、図４Ａは、図１に示す全状態テーブルの単一文字または単一列に対応する）を読み込む。状態情報は次状態アドレスと、ＣＰＵの割り込みや処理の終了などのような実行されるべき特別な情報を含んでいる。
【００４４】
アクセラレータは、次に、入力バッファ１３０から、分析されるべき次のバイトを選択し、加算器１５０に対して既に提供可能となっている新たな状態情報を用いて処理を繰り返す。その処理、またはトークン情報の格納は、同時に実行することができる。この動作は入力ワードの４つの文字の全てが分析されるまで継続される。次いで（或いは、先行取得により４つ目の文字の分析と同時に）、文書バッファ１２０が終わりに達しているかを判断するためにバッファ１１２，１１４が比較され、そうであった場合は、ＣＰＵに割り込みが送り返される。そうでない場合は、新たなワードが取り込まれ、バッファ１１２が更新され、処理が繰り返される。
【００４５】
ポインタとカウンタは専用ハードウェア内に実現されるため、それらは、ソフトウェア内に実現される場合に要求されるような直列的にではなく、並列的に更新することができる。この構成によれば、１バイトのデータの分析時間が、特定部の入力バッファから文字を取り込み、高速の特定部文字パレットメモリから状態テーブルアドレスを生成し、メモリから対応する状態テーブルのエントリを取り込み、再び特定部の高速メモリから次状態情報を取り込むのに要する時間に短縮される。これらの処理の幾つかは、別個の並列経路内で同時に実行することができ、状態テーブル情報の中で特定された他の処理（部分的に或いは全体的に次状態パレットを通じて提供される）は、更なる文字の分析を継続しながら実行することができる。
【００４６】
これより、本発明が、小さく経済的な量の専用ハードウェアを通じてパーシング処理に本質的な加速を提供することが明らかに理解される。パーサアクセラレータがＣＰＵに割り込みをかけ得る一方、パーサアクセラレータに対する初めのコマンドの後に、処理動作は完全にそこから除去される。しかしながら、他のパーシング処理と同時に実行されたとしてもトークンの処理には相当な時間が必要であるため、特に、パーシング処理の過程においてコマンドが発せられることにより、保証することが困難または不可能な処理が開始され得るという観点より、上述したアクセラレーションは、侵入の可能性やセキュリティの穴を検出するものとして理想的なものではない。
【００４７】
ここで、図２Ｂを参照すると、上述した図２Ａに示す装置のそれを超えてパーシングの処理速度を大幅に向上させたハードウェアパーシングアクセラレータ、但し、完全にその装置の互換が可能であるが、その目的が、侵入の可能性又はセキュリティの穴の固有特徴の検出に限定されたもの、が示されている。図２Ｂと図２Ａとを比較すると、図２Ｂに示す装置が、本質的に図２Ａに示す装置のサブセットであり、侵入の固有特徴であり得る全ての記号列（例えば、状態テーブル中にコード化されている完全な表現の整合が取れる前にＣＰＵに対してパターン整合警報を発することができるような、それらの、一つ以上の表現または部分の整合であり、これにより応答速度が改善される）を探索することができるという同じ効果を同時に提供するものであり、処理の結果として発生する必要があるのが、システムを保護するための割り込み又は例外の発生のみであることから、トークン処理の省略を通じて更なるアクセラレーションを提供すものであることは、当業者にとって理解可能である。文書の全体のパーシングを目的とした上記の処理は、可能性のあるセキュリティの穴の固有特徴の包含を完了させるため、文書がスクリーニングされた後に実行され得る。このスクリーニング処理の間はトークン処理が省略されるため、メモリへのアクセス数は大幅に低減される。つまり、本発明に係る（また、上記のハードウェアパーサアクセラレータとの比較に係る）侵入検出アクセラレータにおいては、トークン処理、および文字パレットの使用が省略されており、その結果、メモリリソースに対する要求が低くなっており、また、処理時間にある程度の短縮が生じている。しかしながら、この処理の大部分が並列で行われることから、処理速度の向上は、種々のリソースとして用いられる特定のデバイスのメモリ速度や論理速度等に部分的に依存してはいるが、一般的に２５％若しくはこれ以下である。しかしながら、おそらくは、攻撃の一部分として、セキュリティの穴の可能性に関する固有特徴が検出され、また、対応するコマンドに先立って発行された修復の割り込み又は例外がＣＰＵによって実行され得るという事実の方が、速度より重要である。
【００４８】
図２Ｂに示す装置の全ての機能要素は、図２Ａに存在しており、同一の参照番号は対応する要素に対して用いられている。従って、本発明に係る侵入検出パーサアクセラレータ２００が上記のパーサアクセラレータと完全に互換可能であり、その侵入検出処理が本質的に図２Ａに示すパーサアクセラレータの処理の特別なモードであるように、その装置の変更は、多分にプログラミングによって達成し得ることは明らかである。
【００４９】
特に、入力バッファ１２０および入力ワードバッファ１３０、並びにアドレスレジスタ１１２，１１４、加算器１５０および状態テーブル基礎アドレスレジスタ１８２は、上述した対応要素と同一であり、また、状態テーブル１６０にアクセスするために同一の方式で機能する。その相違は、本質的には、文字パレットおよび次状態パレットメモリと、状態テーブル内のデータおよびその内部フォーマットにおいて存在する。状態テーブルは、本質的に、図２Ａに示す実施形態における場合と同じ幅、つまり２５６文字である。探索が行われた固有特徴は、任意数の文字の記号列の単一文字より複雑であり得る。その固有特徴は、以下にその全体を参照により編入する「So What's a $#!%% Regular Expression Anyway?!」Vikram Vaswani 他著（制作者 Shed）、著作権Melonfire 2000-2002において述べられているように、より一般的には、文字記号列よりも複雑であり得る「規則的表現」として記述される。
【００５０】
規則的表現に対応する状態テーブルは、このため、単純な文字記号列のためのものよりも相当に大きなものとすることができる。加えて、非常に大きな状態テーブルに繋がる同じ状態テーブルを同時に使用することで、多数の規則的表現を探索することができる。しかしながら、現実には、６４の状態で一般には十分である。そうでなければ、しかしながら、状態テーブルのエントリを、８ビットより大きく拡張することが必要となる。従って、上述したような極端な圧縮は一般に必要ではなく、上述した状態テーブル１６０は、要求されるメモリアクセス数を低減するために、攻撃の固有特徴の検出のために要求される状態テーブルの全体ではない実質的部分を提供することができる。
【００５１】
図２Ａに示す実施形態と同様に、状態テーブルにおけるデータのフォーマットは、単一バイトで表すことのできる文字の数に適合するように、ｎ＝２５６のエントリを含むことが望ましい。しかしながら、図２Ｂに示す実施形態の場合においては、状態テーブルへのアクセスは、ワードバッファ１３０内で緩衝された文字ビットから直接実行される。状態テーブルにおける個々のエントリの内容は、図５Ｂに示すように、興味記号列の文字を定義し、かつ、文字記号列の追跡を可能とする、次状態またはロードされるべき状態テーブルの行、及び／又は、その記号列を固有特徴として認識することを支援する記号列の文字（必ずしも、そのような固有特徴を構成し得る記号列の最後の文字である必要はない）に起因して発行されるべき割り込み又は例外のためのフラグ或いは他のコード、だけを含む必要がある。次状態は、通常、上記の８ビットより少ない中で表すことができ、また、興味記号列の検出に対応して生成されるべき例外の割り込みは、単一のビットで表すことができる。
【００５２】
このため、文字は、順番にテストすることができ、興味記号列の最初の文字に当たるまでは、レジスタ１１２，１１４を除いて、他の如何なるレジスタに対しても更新が要求されない。つまり、そのような検出までは、状態ですら変更されず、また、レジスタ１８０内の次状態は更新されない。従って、文書は、著しい速度で、最初の文字に関してスクリーニングされる。興味記号列の最初の文字が出現すると、状態テーブルから次状態データが読み出され、レジスタ１８０が更新され、まだ存在していない場合は新たなテーブルデータが状態メモリにロードされ、また、次の文字が同じ方法で処理に付される。状態テーブルメモリは、上述したＸＭＬ（商標）パーサ用のものに比して大幅に小さいものである。このため、状態テーブルメモリは、図２Ａまたは図２Ｂに示す他の論理および素子と共にチップ上において実現することができ、処理サイクル時間は、おそらくは、外部メモリを用いる設計に対して要求される時間の２５％程度に低減される。しかしながら、アクセラレータが、単純にＸＭＬ（商標）パーサの特別モードとして設計される場合は、状態テーブルは、外部メモリ内に実現され、このような速度の向上は実現されない。従って、このような場合は、状態テーブルの大きさに従って選択的に使用されるべきメモリをチップ上および外部の双方に準備することがコスト的に効果的である。このように、文書を攻撃の固有特徴のためにスクリーニングするためには、個々の文字に対して、僅かに数クロックサイクルが要求されるだけである。興味記号列を識別するために十分な数の文字を処理した時点では、状態テーブルから読み出されたデータに、システムを保護するためのコマンドとしてホストＣＰＵに発せられた割り込み或いは例外が含まれている。
【００５３】
図２Ａまたは図２Ｂに示すように実施化された発明を含むシステムの仕様は、本発明を実現するための唯一のものではないが、図２Ｃに示す仕様は、図２Ｂに示す侵入検出アクセラレータとの関係において好ましいものである。特に、ホストＣＰＵ２３０と、そのメインメモリ２１０は、本発明のハードウェアパーサアクセラレータが、メインメモリ２１０およびホストＣＰＵ２３０と通信するためのバス２２０によって接続されている。ホストＣＰＵ２３０は、メインメモリ２１０とアクセラレータ１００／２００との間の通信をモニタすることができるが、トークンは、未だ定義或いは設立されておらず、好適を実行するためのコードの実行は不可能である。従って、本発明は、攻撃に含まれ得る如何なる動作の実行前に修復の割り込み或いは例外を発行するように備えている。
【００５４】
以上の観点より、本発明が、ＸＭＬ（商標）文書のような文書のパーシングのための時間を、本発明の以前に要求されていた時間の断片に大きく低減するハードウェアパーサアクセラレータの内容や環境の中に、攻撃の企ての可能性を示すことのある固有特徴のために、著しく高速な文書のスクリーニングを提供することが判る。本発明の侵入検出パーサは、本発明に係るパーサアクセラレータが備えるもの以外には何ら追加の要素やハードウェアを要求せず、如何なる侵入処理が実行可能な状態になるより前に、割り込み及び／又は例外を発することができる。
【００５５】
本発明は単一の好ましい実施形態に関して説明されているが、添付のクレームの精神及び範囲の内部で本発明に修正が施せることは当業者にとって理解の範囲である。
【技術分野】
【０００１】
この発明は、ＸＭＬ（商標）文書のような文書のパーシングに関し、より具体的には、ネットワークのノードに対する侵入の可能性や攻撃を検出するための、文章や、ネットワークデータパケットの他の論理シーケンスのパーシングに関する。
【背景技術】
【０００２】
ネットワークにおけるコンピュータとコンピュータの接続との間のディジタル通信の分野は、近年多様な形態で急速に発達し、ここ数年のパーソナルコンピュータの急増をもたらしている。この、相互連結、および遠隔処理の可能性における増加は、ネットワークシステム等における個々のコンピュータの有効能力および機能を大きく発展させた。それでもやはり、個々のコンピュータやシステムの使用、それらのユーザの好み、並びにコンピュータが用いられる際の技術の状態などの多様性は、個々の装置の能力や構成並びにそれらのオペレーティングシステムに、実質的な程度における多様性を生み出しており、「プラットフォーム」と総称されるこれらは、一般に、ある程度の範囲で、特にオペレーティングシステムとプログラミング言語のレベルにおいて、相互互換性を欠いている。
【０００３】
このプラットフォーム特性の非互換性、および、これと同時に生ずる通信および遠隔処理、並びにそれをサポートするに足る十分程度の互換性に関する要求は、結果として、プログラミングに関する対象と（本質、属性、および関係の基準システムを通して、多少とも一般化されたモジュールのグループとしてアプリケーションやデータを集めようというコンセプトを含む）、それを具現化するための多数のプログラミング言語とを発展させた。エクステンシブル・マークアップ・ランゲージ（ＸＭＬ；商標）は、このような言語であり、広く普及していると共に、任意の構成およびアーキテクチャを有するネットワークを介して文書として送信することができる。
【０００４】
このような言語において、特定の文字記号列は、特定のコマンドや識別に対応しており、特別な文字や他の重要なデータ（制御ワードと総称する）を含み、それらは、データや演算が事実上自身を識別し得るようにして、以後、それらが「オブジェクト」として取り扱われるようにするためのものであり、これにより、結びつけられたデータとコマンドは、言語の異なる相違するアプリケーションで用いられる適当なフォーマットとコマンドに変換されることができ、その結果、接続されたプラットフォームのそれぞれにおいて、特定の機械で所望の処理の実行をサポートするに足る互換性が生み出される。これらの文字記号列の検出は、パーシングとして知られる処理により実行され、センテンス等の表現の系統的配列（syntax）をそれらの構成部分に分解し、また、それらを文法的に表現する従来の手法に類似している。
【０００５】
ＸＭＬ（商標）文書をパーシングする際、中央処理ユニット（ＣＰＵ）の処理時間の大部分、おそらく殆どは、処理されている特定のＸＭＬ（商標）標準に対して定義されている制御ワード、特定文字、および他の重要なデータを探すための文書の通読に費やされる。この処理は、通常は、個々の文字を照会して、それが、例えば以下のような「＜ｃｏｍｍａｎｄ＞」、「＜ｄａｔａ＝ｄａｔａｗｏｒｄ＞」、「＜ｅｎｄｃｏｍｍａｎｄ＞」等を含む所定の興味記号列のセットに属しているかを判断するソフトウェアにより実行される。何れかの対象記号列が検出されると、トークンが、トークンの開始とトークンの長さのために、ポインタと共に文書中のその位置に記録される。これらのトークンは、文書の全てが解析（パース）されるまで蓄積される。
【０００６】
従来のアプローチは、興味の対象であるこれらの記号列を探すために、テーブルを基礎とする有限状態装置（ＦＳＭ）を実現することであった。その状態テーブルは、メモリ内に備わっており、文書内の特定のパターンを探すように設計されている。現在の状態は状態テーブルに対する基礎アドレスとして用いられ、また、入力された文字のアスキー（ＡＳＣＩＩ）表現がそのテーブルにおけるインデックスである。例えば、その状態装置が０（ゼロ）状態にあり、最初の入力文字がアスキー値０２であるとすれば、状態エントリのための絶対アドレスは、基礎アドレス（状態０）とインデックス／アスキー値（０２）の和／連結となる。ＦＳＭは、ＣＰＵが入力文書の最初の文字をメモリから読み取ってくるのに伴って起動する。ＣＰＵは、次に、初期／現在状態および入力文字に従って、メモリ内の状態テーブル中に絶対アドレスを構成し、その状態テーブルから状態データを読み取る。ＣＰＵは、返された状態データに基づいて、現在の状態を新たな値に更新し、もし異なる場合は（その文字が興味記号列の最初の文字に対応することを表示して）、その状態データに示されている他の何らかの動作を行う（例えば、単独文字が特定文字である場合や、現在の文字が、更なる進行の繰り返しに伴い、興味記号列の最後の文字であると判明した場合は、トークンや割り込みを発生する）。
【０００７】
上記の処理は繰り返され、何れかの興味記号列の文字が後に検出される毎にその状態が変更される。つまり、初めの文字が興味記号列の初めの文字として興味の対象である場合は、ＦＳＭの状態が新たな状態に進められる（例えば、初期状態０から状態１）。その文字が興味対象でない場合は、状態装置は（一般に）同じ状態（例えば状態０）を特定することで同一に維持される、若しくは、状態テーブルのアドレスから返された状態テーブルエントリにおいて状態の更新を指示しない。可能性のある動作には、これに限られるものではないが、割り込みの設定、トークンの記録、およびポインタの更新が含まれる。その後、以後に続く文字につき処理が繰り返される。ところで、興味記号列が続けられており、ＦＳＭが状態０以外の状態（若しくは、興味記号列が未だ検出されていない、或いは現在続けられていることを表す他の状態）にある場合には、現在の記号列と一致せず、他の興味記号列の最初の文字と一致する文字が検出されることがある。このような場合に、状態テーブルエントリは、先に継続された記号列の断片または部分を示し、かつ識別するうえで、また、新たな記号列が完全に識別されるか興味記号列でないことが判明するまで、可能性のある新たな記号列を追跡するうえで好適な動作を示す。換言すると、興味記号列は、包み込まれていることがあり、状態装置は、他の興味記号列等の中にある興味記号列を検出できなければならない。このため、ＣＰＵは、ＸＭＬ（商標）文書の部分部分を何度も通読してＸＭＬ（商標）文書の解読（パース）を完了させなければならない。
【０００８】
ＸＭＬ（商標）や他の言語の文書は、上述した手法により１文字ずつ解読（パース）される。可能性のある対象記号列が認識される毎に、興味記号列が完全に識別され、或いは、可能性のある興味記号列と一致しない文字が検出されるまで（例えば、記号列が最後まで／完全に一致し、または文字が対象の記号列から外れたとき）、ＦＳＭは、様々な状態を経由して１文字ずつ処理を進める。後者の場合、一般に、初期状態、或いは他の対象記号列の始めの文字の検出に対応する状態に戻る他は、何ら動作が行われない。前者の場合、トークンが、入力文書内での開始アドレスとトークンの長さと一緒にメモリ内に記憶される。パーシングが完了するまでに、全ての対象が識別され、特定箇所の若しくは所定のプラットフォームに従う処理が開始可能となる。
【０００９】
探索は一般に複数の興味記号列について実行されるため、状態テーブルは、如何なる所定の状態からでも複数の変化を提供することができる。このアプローチによれば、包み込まれた記号列に便利良く適応しつつ、現在の文字を同時に複数の対象記号列に対して分析することができる。
【００１０】
以上のことから、ＸＭＬ（商標）文書のような文書のパーシングは、多数の繰り返しと、個々の繰り返しにおける多数のメモリアクセスとを要求することが判る。このため、一般用ＣＰＵにおける処理時間は、必然的に相当なものとなる。複数の記号列を取り扱うことの更なる主たる複雑さは、大きな状態テーブルを生成する点にあり、また、リアルタイムによるパケット処理からオフラインで取り扱われることである。しかしながら、これにより、入力文字データの取得、状態データの取得、および、文書中の個々の文字に関する種々のポインタおよび状態アドレスの更新のために、多数のＣＰＵサイクルが要求される。このため、ＸＭＬ（商標）文書などの文書のパーシングを行うにあたっては、他の処理に先んじてＣＰＵやプラットフォームが占有され、所望の処理に大きな遅れを生じさせるのが比較的通常である。
【００１１】
従来、一般用のハードウェアは、プログラミングを介して、専用のハードウェアの機能と同等の機能を実現し得ること、および、専用のハードウェアの管理および制御には固定負荷が少ないため、構成とプログラムが互いに正確に一致していたとしても、専用のデータ処理ハードウェアは、プログラムされた一般用ハードウェアよりも高速で機能するのが通常であることが認識されていた。それにもかかわらず、特定の処理のために専用ハードウェアに要求されるハードウェアリソースは、特に処理速度のゲインが最低境界付近にある場合には、法外に大きなものとなり得る。更に、専用ハードウェアは、必然的に機能上の限界を有しており、また、任意の組み合わせに係る任意の数の文字を探索する能力を提供するような特定のアプリケーションに対する十分な柔軟性においても制限がある。このため、専用ハードウェアが適当であるためには、処理速度において大きなゲインを提供しつつ、非常に本質的なハードウェア経済を提供しなければならず、これらの要求は、所望の処理機能において必要とされる機能上の柔軟性やプログラム可能性の程度が高まるに連れて、同時に適応することがより一層困難になっている。
【００１２】
この点に関して、システムセキュリティの問題が、接続可能性と、ＸＭＬ（商標）文書のような文書のパーシングに要求される処理時間の量との双方から生じている。一方では、相対的に高い優先度で非常に大きな処理時間を要求する何らかの処理は、幾つかの点において、システムやそのノードに対するサービス不能（ＤＯＳ）攻撃と似通っており、また、このような攻撃において用いうるツールともなり得る。
【００１３】
ＤＯＳ攻撃は、稼働状態にあるリソースを悪意をもって浪費させ、また、ついには過負荷状態とするために、システムに対してつまらない奇形のサービス要求を頻繁に与える。ハードウェアアクセラレータの適正な構成は、稼働状態にあるリソースが過負荷状態となる可能性を大幅に低減し、または除去することができる。更に、システムは、過負荷状態である場合に、しばしば異常となり、或いはセキュリティの弱点を露出する。このため、過負荷を除去することは、セキュリティ上、重要な考慮事項である。
【００１４】
更に、状態テーブルは、システムパフォーマンスの深刻な低下を伴うこと無しに、保証することが困難若しくは不可能な基礎レベルにおいてＣＰＵのコマンドを含むことができなければならないため、パーシングが終了する以前から、幾つかの処理は開始することが可能でき、また、幾つかのコマンドは実行することができる。つまり、セキュリティの低下の可能性は、ＸＭＬ（商標）パーシングなどを処理するための処理時間の短縮により、必然的に低減されるが、このようなパーシングの処理時間を画期的に短縮する技術は何ら提供されていなかった。
【００１５】
多くのセキュリティシステムは、非常に早い段階では、企てられたセキュリティの穴（security breach）を検出する能力に依拠しており、セキュリティの穴は、一旦開始されると、迅速に、或いはプログラムによる介入により、遮ることが困難若しくは不可能である。例えば、高度な保証システムが提案されており、何れも本出願の譲受人に譲受された米国特許０９／９７３，７６９および０９／９７３，７７６に開示されている。これらの出願は、２つのレベルのノード間通信を有しており、ひとつは、非常に高速であり、これによれば、攻撃の可能性や侵入が検出されたノードは、隔離され、必要であれば、その後、ネットワークに再び接続される前に自動的に修復される。従って、パーシングのアクセラレーションは、ネットワークの適切な制御を、パーシングの出来事として開始することができ、このため、パーシングが画期的に加速されれば早い時点から開始することができることから、攻撃の可能性に対する早期応答を支援するものであり、特に、上記の編入した特許出願中に記載されたシステムにおいて開示されているようなシステムにおいて有効である。検出警報に応じて、適時な方式出開始される適切なネットワーク制御によれば、侵入の検出に加えて侵入の防止を達成することができる。
【発明の開示】
【００１６】
この発明は、リアルタイムによる侵入検出および動作防止を可能とするネットワーク伝送パケット速度で、侵入の可能性、攻撃、或いはコンピュータネットワークシステムにおける他のセキュリティの穴の固有特徴を検出するための文書パーシングの極限の加速を提供するハードウェアパーサアクセラレータを提供する。
本発明のこれらおよび他の事項を達成するため、文書パーサ中に実現することができ、文書の複数バイトのための文字バッファと、割り込み又は例外、および状態テーブルからの次状態データの少なくとも一方にアクセスするために、文書の１バイト及び状態に従ってアドレスを定めることのできる状態テーブルと、次状態データを記憶するレジスタと、状態メモリに対するアドレスを更に形成するためにレジスタの内容を文書の続きのバイトに組み合わせる加算器と、割り込みまたは例外をＣＰＵに通信するためのバスとを備える侵入検出システムを提供する。
【図面の簡単な説明】
【００１７】
以上の、および他の事柄、様相および効果は、以下に続く好ましい実施形態の詳細な説明と、図面の参照により一層理解することができ、図面には以下の事項が記載されている。
【図１】図１は、文書のパーシングに用いられる状態テーブルの一部を表す。
【図２Ａ】図２Ａは、同時に提出した関連のある暫定特許出願に係るパーサアクセラレータを、高度に概要化した図である。
【図２Ｂ】図２Ｂは、本発明に係るパーサアクセラレータを、高度に概要化した図である。
【図２Ｃ】図２Ｃは、本発明の実現を、ホストプロセッサとメインメモリと共に示す。
【図３】図３は、図２Ａに示す文字パレットの好ましいフォーマットを示す。
【図４】図４Ａおよび図４Ｂは、図２Ａに示す発明の好ましい形態における状態テーブルのフォーマットと、これと結合して用いられる状態テーブル制御レジスタとを示す。
【図５Ａ】図５Ａは、図２Ａに示す次状態パレットの好ましいフォーマットを示す。
【図５Ｂ】図５Ｂは、図２Ｂに示す発明と共に用いるうえで好ましい状態テーブルエントリのフォーマットを示す。
【図６】図６は、図５に示すトークンの好ましいフォーマットである。
【発明を実施するための最良の形態】
【００１８】
以下、図面、より具体的には図１を参照して、そこには文書のパーシングに用いられる状態テーブルの一部の表示が示されている。図１に示される状態テーブルは、ＸＭＬ（商標）文書のパーシングに有効な状態テーブルの極小さな一部のみであり得ると共に、本質的に例示を意図したと解されるべきものである。本発明中に、少なくとも表示した形式中には、状態テーブルの全ては物理的に存在しておらず、また、図１は、公知のソフトウェアパーサの動作の理解を容易ならしめるためにも用いることができるが、本発明との関係において、図１の如何なる部分も、従来技術と認められるものではない。
【００１９】
ところで、ＸＭＬ（商標）文書は、ここでは、本発明に係るアクセラレータを利用して処理され得る論理データシーケンスの一つのタイプの例として用いられている。他の論理データシーケンスは、分担されたサーバコンピュータによる実行を意図したユーザ端末命令記号列のようなネットワークデータパケットの内容からも構築することができる。このような記号列は、悪意のユーザによりしばしば生成され、長期の侵入の試みの一部として分担されたサーバコンピュータに送信される。本発明に係るアクセラレータは、このような論理データシーケンスの多くを処理するのに適している。
【００２０】
図１に示された状態テーブルの部分における多くのエントリが重複であることは、有益な注意点であり、図１に表されている状態テーブルの全体を収容するハードウェアが必要でないことも本発明を正しく理解するために重要である。反対に、本発明は、おそらくは専用のプロセッサを用いて、ソフトウェアの内部で実現することが可能であるが、ソフトウェアによるパーシングのために処理時間が増加する不利益は、ハードウェアにおける如何なる経済的可能性によっても正当化はされず、本発明に係るハードウェアの要求は十分に制限されている。
【００２１】
しかしながら、侵入検出システムが、ディジタルファイルの如何なるタイプにも適用可能であるように意図されること、および、一般にセキュリティ攻撃が実行される際に介在するネットワークにおいてリアルタイムによるディジタル伝送に適合しうるパケット伝送速度で、或いはそれ以上の速度で特定のアプリケーションやデータ構造を表すのに用い得るテキストファイルや特定言語に限定されないことは、評価されるべきである。このため、本発明は、侵入検出のみを提供する装置として実現してもよく、その場合は、最低のコストで実質的に理想的なパフォーマンスを得ることを期待することができる。しかしながら、侵入検出を単一の伝送速度で実行するという目的は、更なる加速を提供するために幾つかの処理を省略する、パーサアクセラレータ処理の特別のモードとしても、おそらくは、以下に説明すると共に現時点で好ましいと考えられている選択可能な状態テーブル装置によって増大された状態で、達成することができる。従って、リアルタイムによる高速での侵入検出という本発明が意図した機能に対して必要以上に状況は複雑になるが、完結の興味において、また、本発明により提供される効果の範囲のより完全な理解を伝達するために、本発明は、パーサアクセラレータの状況において説明することとする。
【００２２】
図１において、状態テーブルは、任意数の行に区分されており、それぞれの行は、状態に対応する基礎アドレスを有している。基礎アドレスの行は、解読（パース）される文書中の文字を表すのに用い得るコードの数；この例では、状態テーブルにおけるインデックスとして用いられる文字のための８ビット・バイトに対応する２５６行、に対応する数の列に区分されている。
【００２３】
図示された状態テーブルのエントリの幾つかの様相に注目することは、特に、図１に示された、状態テーブルのほんの小さな部分が、どのようにして多くのワードをサポートしているかの理解を伝えるうえで有効である。
【００２４】
１．図示された状態テーブルでは、状態０の行において、２つのエントリだけが、テストされた文字が如何なる興味記号列の初めの文字とも一致しないときに初期状態を維持する「状態０に残留」以外のエントリを含んでいる。状態１への進行を提供する単一のエントリは、全ての興味記号列が同じ文字で始まる特別な場合に対応している。他の状態への進行を提供する他の文字は、一般に、但し必須ではなく、状態１以外への進行を提供するが、他の文字を介して到達し得る同一の状態を更に参照することは、例えば、包み込まれた記号列を検出するために有効であり得る。｛状態０、ＦＤ｝に示すように「状態０に残留」にコマンド（例えば「特別割り込み」）を含ませることは、特別な単一文字に対する検出および実行に用いられる。
【００２５】
２．状態０より上の状態における「状態ｎに残留」は、普通に遭遇するような、例えば、コマンドの数値引数において遭遇することのあるような一つ以上の文字の潜在的な長期実行を通じて維持されるべき状態に備えたものである。本発明は、以下に詳細に説明するように、十分なアクセラレーションを提供するために、このタイプの文字記号列につき特別な取り扱いを提供する。
【００２６】
３．状態０より上の状態における「状態０へ移動」のエントリは、それまでに、整合する文字がいくつ検出されていたとしても、その記号列を、如何なる興味記号列とも区別する文字が検出されたことを知らせるものであり、また、パーシング処理を、他の興味記号列の探索を始めるためのイニシャル／デフォルト状態に戻すものである。（この理由のため、「状態０へ移動」は、一般に、突出して最も高い頻度で数多く状態テーブル中に表れるエントリである。）状態０への復帰は、パーシング処理を、区別の目安となる文字が検出された時点で追跡されていた記号列を開始していた文字に続いて文書中に存在する文字に復帰させる。
【００２７】
４．コマンドと「状態０へ移動とを含むエントリは、完結した興味記号列の検出の完了を示す。一般に、そのコマンドは、以後、記号列をオブジェクトと取り扱うことを可能とするためのトークンを（トークンのアドレスおよび長さと共に）記憶することである。しかしながら、「状態ｎへ移動」に伴うコマンドは、興味記号列と合致する可能性のある記号列の追跡を継続しながら、中間点において処理を発動するためのものである。
【００２８】
５．探索が２つの興味記号列（例えば、ｎ−１個の同一の始めの文字とｎ番目の異なる文字、或いは、異なる初めの文字を有する記号列）に枝分かれする全ての点で不明確さを回避するためには、一般に、｛状態１，０１｝および｛状態１，ＦＤ｝に示すように、異なる（非連続な）状態に進むことが必要である。任意の長さｎの記号列の識別を完了させるには、特別な文字を含む記号列および共通する初めの文字を有する興味記号列が含まれる特殊な環境を除いて、ｎ−１の状態を必要とする。これらの理由により、興味記号列の数が比較的多くない場合であっても、状態および状態テーブルの行の数は、通常、著しく大きなものとなる。
【００２９】
７．これまでのパラグラフに反して、殆どの状態は、一つか二つの特有なエントリとデフォルトの「状態０に移動」とによって完全に特徴付けられる。図１に示す状態テーブルが有するこの特徴は、本発明において、ハードウェアの高度な経済性と、興味記号列の一般的な場合に対するパーシングプロセスの相当なアクセラレーションとを生み出すために利用される。
【００３０】
以上から判るように、パーシング処理は、従来から実行されていたように、図１において状態０と示されている所定のデフォルト／イニシャル状態にあるシステムで開始され、その後、処理の繰り返しに伴って整合する文字が発見されるに従って、より数の大きな状態に進行する。興味記号列が完全に識別された際、或いは、整合の可能性のある記号列の途中において特別な処理が特定された際に、トークンの記憶や割り込みの発生などの処理が実行される。しかしながら、文書の個々の文字に対する個々の繰り返しにおいて、その文字がＣＰＵメモリから読み出されなければならず、状態テーブルのエントリが（再びＣＰＵメモリから）取り込まれなければならず、また、（例えば、文書の文字および状態テーブルの基礎アドレスに対する）種々のポインタが連続処理の中で更新されなければならない。従って、そのパーシング処理は、多大な処理時間を消費し得るものとして即座に評価し得るものである。
【００３１】
本発明に係るパーサアクセラレータ１００を高度の概要化したブロック図を図２Ａに示す。当業者にとって、そのように評価されるように、図２Ａは、本発明においてパーシングを実行するために実行される工程を示すフローチャートとしても理解することができる。図３、図４Ａ、図４Ｂ、図５Ａおよび図６を参照して以下により詳しく説明するように、本発明は、僅かながら時間的なずれを伴って本質的には並列に作動するような複数のハードウェア経路が達成されるように、状態テーブルを表すにあたり、幾つかのハードウェア経済を利用する。このため、並列で作動させられる高速アクセスのハードウェア、および、状態テーブルと文書との関係でのＣＰＵメモリからの先行取得の双方を通じてメモリアクセスに必要とされる時間を大きく低減しつつ、ポインタおよびレジスタの更新は、ほぼ同時に、かつ、他の処理と同時発生的に行うことができる。
【００３２】
一般的な概観として、ＸＭＬ（商標）文書のような文書は、レジスタ１１２，１１４により索引付けられたＤＲＡＭ１２０中に外部的に記憶され、複数経路のためのマルチプレクサとして機能する入力バッファ１３０に、好ましくは３２ビットのワードで転送される。個々の経路は、文字パレット１４０、状態テーブル１６０、および次状態パレット１７０の写しを有しており、それぞれが、状態テーブルの部分の圧縮形式を収容している。次状態パレット１７０の出力は、状態テーブル１６０におけるエントリを指すアドレスである次状態アドレスの部分と、もし存在すれば、記憶されるべきトークン値との双方が含まれる。文字パレット１４０および次状態パレット１７０における動作は、互いに並列に、かつ、状態テーブル１６０（これもキャッシュとしても実現され得る）を形成する高速外部ＳＲＡＭへの単純なメモリアクセスとも並列に動作することのできる高速内部ＳＲＡＭへの単純なメモリアクセスである。従って、これらのハードウェア要素を始めに制御するＣＰＵのほんの僅かな数クロック周期だけで（しかし、そのハードウェア要素は、一度起動すると、文書データをリフレッシュするため、およびトークンを記憶するためのＣＰＵによる偶発的なＣＰＵ処理の呼び出しのみに対して自律的に作動する）、文書中の個々の文字を評価することができる。ＣＰＵにおける一文字当たりの全メモリ処理の継続の積算における低減と、高速ＳＲＡＭ或いはＤＲＡＭにおいて自律的に行われる単独のメモリ処理の継続に対するＣＰＵの固定負荷との和がアクセラレーションによる基礎ゲインである。
【００３３】
ところで、ここで「外部」と称されるメモリ構成は、メモリ１２０，１４０の構成の暗示を意図したものであり、必要とされる記憶容量、並びに、ハードウェアパーサアクセラレータから、および／またはホストＣＰＵからのアクセスの視点において、現時点で発明者が好ましいと思うものである。換言すると、メモリの分配、或いは、少なくともホストＣＰＵ並びにハードウェアアクセラレータによるメモリへのアクセスを容易ならしめるように本発明に係るパーサアクセラレータのアーキテクチャを提供することは、トークンや他の処理を取り扱ううえで効果的である。この説明の観点より、意図しない他の暗示や、同期ＤＲＡＭ（ＳＤＲＡＭ）のような種々のハードウェアの変形例は、当業者にとって理解可能であると思われる。
【００３４】
以下、図３乃至図６を参照して、文字パレット１４０、状態テーブル１６０、次状態パレット１７０および次状態、並びにトークンのフォーマットを、図２Ａの好適な実現をサポートするハードウェア経済の例示として説明する。他の技術／フォーマットも使用が可能であり、また、示されたフォーマットは、現時点で好ましいものではあるが、あくまで例示として理解されるべきものである。
【００３５】
図３は、興味記号列に含まれ、或いは含まれ得る文字に対応する文字パレットの好適な形式を示す。このフォーマットは、好ましくは、図１に示す状態テーブルの列の数に対応して、０−２５５の数字が付されたエントリを提供する。（「パレット」の用語は、多分に、サポートされている個々の色のデータを含み、総じて全域と称される「色パレット」の用語の場合と同じ感覚で用いられている。パレットの使用により、状態テーブルのエントリ／列が低減される。）例えば、状態を変化させることのない「空文字」と称される文字は、多くの列を要することなく、状態テーブルの一つの列中に表すことができる。１４４において空文字出力をテストすることが望ましく、そのテストによれば、状態テーブルにアクセスするための更なるメモリ処理を必要とすることなく次の文字の即座処理が許可されることから、パーシングの処理を相当に加速することができる。そのフォーマットは、例えば、特定の文字パレット（図２中に、重なり合うメモリ面で図示）に関連付けられた基礎アドレスレジスタ１４２中のデータ等により構成された単一のレジスタ、或いはメモリ中の複数位置により収容することができる。文書（例えばＸＭＬ（商標）文書）から提供された現在の８ビット文字、つまり、外部ＤＲＡＭ１２０からの４バイトのワードとして受け取られてインプットバッファ１３０から提供された４つのうちの一つにより文字パレットのエントリのアドレスが指定され、文字パレットは、次いで、インデックス、若しくは、ポインタの一部として、状態メモリに入るアドレスを出力する。このため、このようなフォーマットをパレットに提供することにより、図１に示す機能の一部を、比較的容量が制限された単一のレジスタの形式中に持たせることができ、その結果、それらを複数形成して、並列に作動させる一方で、本質的なハードウェア経済を維持し、かつ、状態テーブル１６０内の他の要素をサポートすることができる。
【００３６】
図４Ａは、文字パレット（例えば、実質的にはレジスタ）に類似するように構築或いは構成された好ましい状態テーブルのフォーマットを示す。図３に示す文字パレットとの主たる相違は、レジスタの長さが、要求された文字に対する応答の数と、興味記号列の数および長さに依拠している点である。従って、経済的に配置されていた内部メモリの量が特定の場面で不十分である際には、このメモリをＣＰＵまたは他の外部ＤＲＡＭ（おそらくは内部または外部のキャッシュと共に）内に実現するための可能性を準備しておくことが好ましいと考えられる。とはいえ、図１に示す状態テーブルにおける多数の重複エントリが単一エントリに、つまり、図３に示す文字パレットに従って上記のように提供されるデータに収容されるアドレスに低減されていることから、本質的なハードウェア経済が提供されていることは明らかである。状態テーブル１６０の出力は、１、２または４ビットであることが望ましいが、３２ビットまでの変形は、図４Ｂを参照して以下に説明するように、より大きな柔軟性を提供し得るものである。
【００３７】
図４Ｂを参照して、この後者に関する本発明を完成させる特徴として、本発明の好ましい実施形態は、特に状態テーブル１６０が３２ビットの出力を発する場合に、更なる本質的なハードウェア経済を実現する状態テーブル制御レジスタ１６２を含むものである。特に、その状態テーブル制御レジスタは、状態テーブルに、可変長のワードの記憶と読み出しを可能ならしめることにより、状態テーブルの情報の圧縮に備えることができる。
【００３８】
より具体的には、状態テーブル制御レジスタ１６２は、図４Ａに示す状態テーブルにおける個々のエントリの長さを記憶し、また、提供する。図１に示す状態テーブルのエントリは、高度に重複しているため（例えば、「状態０へ移動」、「状態ｎに残留」）、これらのエントリは、状態テーブル１６０中に単一のエントリで、若しくは、少なくとも図１に示すより十分に少ない数で表すことができるのみならず、より少ないビットで、おそらくは、ある種の状態テーブルにおいては便利であることが認められるように、重複エントリの大部分若しくは全てがその状態テーブルに含まれる場合であっても、本質的なハードウェア経済を実現することができる程度に少ないビットで表すことができる。この低減の原理は、当業者にとっては、所謂エントロピーコーディングと類似するものとして理解することができる。
【００３９】
以下、図５Ａを参照して、次状態パレット１７０の好ましいフォーマットを説明する。次状態パレット１７０は、好ましくは、上述した文字パレット１４０とほぼ同様の手法で実現される。しかしながら、状態メモリ１６０の場合と同様に、要求されるエントリの数は、既知でなく、個々のエントリの長さは、好ましくは、より十分に大きなものである（例えば、２つの３２ビットワード）。他方、如何なる所与の時間においても、比較的小さく、かつ、予測可能なアドレスの幅だけが収まれば足りるため、次状態パレット１７０は（例えば、次状態パレット基礎アドレスレジスタ１７２を用いて）キャッシュとして作動させることができる。更に、状態テーブル１６０から３２ビットの出力が提供される際には、それらのデータの幾つかは、次状態パレット１７０のエントリ内のデータを補い、可能であれば後者のエントリの短縮を許容し、或いは、可能であれば、破線１７５で示すように、次状態パレットを完全にバイパスする。
【００４０】
図５Ａに示すように、次状態パレット１７０から出力された下方アドレスの３２ビットワードは、格納されるべきトークンである。このトークンは、好ましくは、８ビットの制御フラグ、並びに、何れも記号列の開始に対するポインタ１９２により提供されたアドレスにおいて、かつ、成功した文字比較のカウントにより蓄積した長さと一緒にトークンバッファ１９０に記憶される、１６ビットのトークン値および８ビットのトークンフラグとして形成される。制御フラグは、ホストＣＰＵ、或いはパーサアクセラレータ中の制御処理に対して割り込みをセットする。後者の制御フラグのうち一つは、好ましくは、既に言及したように、興味記号列内に生じ得る任意の長さの文字と同一または関連する記号列のように、状態０以外の状態において状態を変化させる原因とならない文字のスキップ可能化機能をセットするために用いられる。このような場合においては、次状態テーブルのエントリは、ＳＲＡＭ／ＤＲＡＭから読み取ってくることなく、再び用いることができる。入力バッファアドレス１１２は、追加の処理を伴わずにインクリメントされ、特定の文字記号列に対するパーシングの更なる本質的な加速が実現される。第２の３２ビットワードは、レジスタ１８０および加算器１５０にフィードバックされ、文字パレットから出力されるインデックスと連結されて、次の文字のための状態テーブルに対するポインタを形成するアドレスオフセットである。状態０に対応する初期アドレスは、レジスタ１８２によって供給される。
【００４１】
このため、文字パレット、簡略形式での状態メモリ、および次状態メモリの使用は、従来の状態メモリ処理を、区分された段階に明確化し、それぞれの段階は、相対的に小さく、かつ高速であり、それ故に重複が可能であり、文書中のそれぞれの文字を、他の処理およびトークンの格納と共に、順番に、かつ並列に処理する並列経路を構成し得るメモリを用いて、著しく高速に実行することができる。従って、そのパーシングプロセスは、他の文字の処理が開始される以前にこれらの機能の全てを順番に実行する専用プロセッサとの比較においてさえ相対的に大幅な加速を実現することができる。
【００４２】
要約すると、アクセラレータは、文字データ（場合によってはネットワークへの送信の意味を含んでパケットデータと称される）と状態テーブルが配置されているホストＣＰＵのプログラムメモリにアクセスする。アクセラレータ１００は、メモリマップ化されたレジスタを介してメインＣＰＵにより制御される。アクセラレータは、メインＣＰＵに割り込みをかけて、侵入検出の状況においては一般的にパターンマッチング警報と称することのできる例外、警告、および終了を示すことができる。侵入イベント警報など。パーシングが開始されると、ポインタ（１１２，１１４）が、分析されるべき入力バッファ１３０のデータの最初と終わりにセットされ、使用されるべき状態テーブルが基礎アドレス１８２により示され、更に、他の制御情報（例えば、１４２）がアクセラレータ内に設定される。
【００４３】
アクセラレータの処理を開始するため、ＣＰＵは、アクセラレータのコマンドを発し、アクセラレータは、これに応えてＣＰＵのプログラムメモリ（例えば１２０またはキャッシュ）から最初の３２ビットワードのデータを読み込み、これを入力バッファ１３０に置き、最初のバイト／ＡＳＣＩＩ文字はそこから選択される。アクセラレータは、現在の状態と入力文字に対応する状態情報（つまり、図４Ａは、図１に示す全状態テーブルの単一文字または単一列に対応する）を読み込む。状態情報は次状態アドレスと、ＣＰＵの割り込みや処理の終了などのような実行されるべき特別な情報を含んでいる。
【００４４】
アクセラレータは、次に、入力バッファ１３０から、分析されるべき次のバイトを選択し、加算器１５０に対して既に提供可能となっている新たな状態情報を用いて処理を繰り返す。その処理、またはトークン情報の格納は、同時に実行することができる。この動作は入力ワードの４つの文字の全てが分析されるまで継続される。次いで（或いは、先行取得により４つ目の文字の分析と同時に）、文書バッファ１２０が終わりに達しているかを判断するためにバッファ１１２，１１４が比較され、そうであった場合は、ＣＰＵに割り込みが送り返される。そうでない場合は、新たなワードが取り込まれ、バッファ１１２が更新され、処理が繰り返される。
【００４５】
ポインタとカウンタは専用ハードウェア内に実現されるため、それらは、ソフトウェア内に実現される場合に要求されるような直列的にではなく、並列的に更新することができる。この構成によれば、１バイトのデータの分析時間が、特定部の入力バッファから文字を取り込み、高速の特定部文字パレットメモリから状態テーブルアドレスを生成し、メモリから対応する状態テーブルのエントリを取り込み、再び特定部の高速メモリから次状態情報を取り込むのに要する時間に短縮される。これらの処理の幾つかは、別個の並列経路内で同時に実行することができ、状態テーブル情報の中で特定された他の処理（部分的に或いは全体的に次状態パレットを通じて提供される）は、更なる文字の分析を継続しながら実行することができる。
【００４６】
これより、本発明が、小さく経済的な量の専用ハードウェアを通じてパーシング処理に本質的な加速を提供することが明らかに理解される。パーサアクセラレータがＣＰＵに割り込みをかけ得る一方、パーサアクセラレータに対する初めのコマンドの後に、処理動作は完全にそこから除去される。しかしながら、他のパーシング処理と同時に実行されたとしてもトークンの処理には相当な時間が必要であるため、特に、パーシング処理の過程においてコマンドが発せられることにより、保証することが困難または不可能な処理が開始され得るという観点より、上述したアクセラレーションは、侵入の可能性やセキュリティの穴を検出するものとして理想的なものではない。
【００４７】
ここで、図２Ｂを参照すると、上述した図２Ａに示す装置のそれを超えてパーシングの処理速度を大幅に向上させたハードウェアパーシングアクセラレータ、但し、完全にその装置の互換が可能であるが、その目的が、侵入の可能性又はセキュリティの穴の固有特徴の検出に限定されたもの、が示されている。図２Ｂと図２Ａとを比較すると、図２Ｂに示す装置が、本質的に図２Ａに示す装置のサブセットであり、侵入の固有特徴であり得る全ての記号列（例えば、状態テーブル中にコード化されている完全な表現の整合が取れる前にＣＰＵに対してパターン整合警報を発することができるような、それらの、一つ以上の表現または部分の整合であり、これにより応答速度が改善される）を探索することができるという同じ効果を同時に提供するものであり、処理の結果として発生する必要があるのが、システムを保護するための割り込み又は例外の発生のみであることから、トークン処理の省略を通じて更なるアクセラレーションを提供すものであることは、当業者にとって理解可能である。文書の全体のパーシングを目的とした上記の処理は、可能性のあるセキュリティの穴の固有特徴の包含を完了させるため、文書がスクリーニングされた後に実行され得る。このスクリーニング処理の間はトークン処理が省略されるため、メモリへのアクセス数は大幅に低減される。つまり、本発明に係る（また、上記のハードウェアパーサアクセラレータとの比較に係る）侵入検出アクセラレータにおいては、トークン処理、および文字パレットの使用が省略されており、その結果、メモリリソースに対する要求が低くなっており、また、処理時間にある程度の短縮が生じている。しかしながら、この処理の大部分が並列で行われることから、処理速度の向上は、種々のリソースとして用いられる特定のデバイスのメモリ速度や論理速度等に部分的に依存してはいるが、一般的に２５％若しくはこれ以下である。しかしながら、おそらくは、攻撃の一部分として、セキュリティの穴の可能性に関する固有特徴が検出され、また、対応するコマンドに先立って発行された修復の割り込み又は例外がＣＰＵによって実行され得るという事実の方が、速度より重要である。
【００４８】
図２Ｂに示す装置の全ての機能要素は、図２Ａに存在しており、同一の参照番号は対応する要素に対して用いられている。従って、本発明に係る侵入検出パーサアクセラレータ２００が上記のパーサアクセラレータと完全に互換可能であり、その侵入検出処理が本質的に図２Ａに示すパーサアクセラレータの処理の特別なモードであるように、その装置の変更は、多分にプログラミングによって達成し得ることは明らかである。
【００４９】
特に、入力バッファ１２０および入力ワードバッファ１３０、並びにアドレスレジスタ１１２，１１４、加算器１５０および状態テーブル基礎アドレスレジスタ１８２は、上述した対応要素と同一であり、また、状態テーブル１６０にアクセスするために同一の方式で機能する。その相違は、本質的には、文字パレットおよび次状態パレットメモリと、状態テーブル内のデータおよびその内部フォーマットにおいて存在する。状態テーブルは、本質的に、図２Ａに示す実施形態における場合と同じ幅、つまり２５６文字である。探索が行われた固有特徴は、任意数の文字の記号列の単一文字より複雑であり得る。その固有特徴は、以下にその全体を参照により編入する「So What's a $#!%% Regular Expression Anyway?!」Vikram Vaswani 他著（制作者 Shed）、著作権Melonfire 2000-2002において述べられているように、より一般的には、文字記号列よりも複雑であり得る「規則的表現」として記述される。
【００５０】
規則的表現に対応する状態テーブルは、このため、単純な文字記号列のためのものよりも相当に大きなものとすることができる。加えて、非常に大きな状態テーブルに繋がる同じ状態テーブルを同時に使用することで、多数の規則的表現を探索することができる。しかしながら、現実には、６４の状態で一般には十分である。そうでなければ、しかしながら、状態テーブルのエントリを、８ビットより大きく拡張することが必要となる。従って、上述したような極端な圧縮は一般に必要ではなく、上述した状態テーブル１６０は、要求されるメモリアクセス数を低減するために、攻撃の固有特徴の検出のために要求される状態テーブルの全体ではない実質的部分を提供することができる。
【００５１】
図２Ａに示す実施形態と同様に、状態テーブルにおけるデータのフォーマットは、単一バイトで表すことのできる文字の数に適合するように、ｎ＝２５６のエントリを含むことが望ましい。しかしながら、図２Ｂに示す実施形態の場合においては、状態テーブルへのアクセスは、ワードバッファ１３０内で緩衝された文字ビットから直接実行される。状態テーブルにおける個々のエントリの内容は、図５Ｂに示すように、興味記号列の文字を定義し、かつ、文字記号列の追跡を可能とする、次状態またはロードされるべき状態テーブルの行、及び／又は、その記号列を固有特徴として認識することを支援する記号列の文字（必ずしも、そのような固有特徴を構成し得る記号列の最後の文字である必要はない）に起因して発行されるべき割り込み又は例外のためのフラグ或いは他のコード、だけを含む必要がある。次状態は、通常、上記の８ビットより少ない中で表すことができ、また、興味記号列の検出に対応して生成されるべき例外の割り込みは、単一のビットで表すことができる。
【００５２】
このため、文字は、順番にテストすることができ、興味記号列の最初の文字に当たるまでは、レジスタ１１２，１１４を除いて、他の如何なるレジスタに対しても更新が要求されない。つまり、そのような検出までは、状態ですら変更されず、また、レジスタ１８０内の次状態は更新されない。従って、文書は、著しい速度で、最初の文字に関してスクリーニングされる。興味記号列の最初の文字が出現すると、状態テーブルから次状態データが読み出され、レジスタ１８０が更新され、まだ存在していない場合は新たなテーブルデータが状態メモリにロードされ、また、次の文字が同じ方法で処理に付される。状態テーブルメモリは、上述したＸＭＬ（商標）パーサ用のものに比して大幅に小さいものである。このため、状態テーブルメモリは、図２Ａまたは図２Ｂに示す他の論理および素子と共にチップ上において実現することができ、処理サイクル時間は、おそらくは、外部メモリを用いる設計に対して要求される時間の２５％程度に低減される。しかしながら、アクセラレータが、単純にＸＭＬ（商標）パーサの特別モードとして設計される場合は、状態テーブルは、外部メモリ内に実現され、このような速度の向上は実現されない。従って、このような場合は、状態テーブルの大きさに従って選択的に使用されるべきメモリをチップ上および外部の双方に準備することがコスト的に効果的である。このように、文書を攻撃の固有特徴のためにスクリーニングするためには、個々の文字に対して、僅かに数クロックサイクルが要求されるだけである。興味記号列を識別するために十分な数の文字を処理した時点では、状態テーブルから読み出されたデータに、システムを保護するためのコマンドとしてホストＣＰＵに発せられた割り込み或いは例外が含まれている。
【００５３】
図２Ａまたは図２Ｂに示すように実施化された発明を含むシステムの仕様は、本発明を実現するための唯一のものではないが、図２Ｃに示す仕様は、図２Ｂに示す侵入検出アクセラレータとの関係において好ましいものである。特に、ホストＣＰＵ２３０と、そのメインメモリ２１０は、本発明のハードウェアパーサアクセラレータが、メインメモリ２１０およびホストＣＰＵ２３０と通信するためのバス２２０によって接続されている。ホストＣＰＵ２３０は、メインメモリ２１０とアクセラレータ１００／２００との間の通信をモニタすることができるが、トークンは、未だ定義或いは設立されておらず、好適を実行するためのコードの実行は不可能である。従って、本発明は、攻撃に含まれ得る如何なる動作の実行前に修復の割り込み或いは例外を発行するように備えている。
【００５４】
以上の観点より、本発明が、ＸＭＬ（商標）文書のような文書のパーシングのための時間を、本発明の以前に要求されていた時間の断片に大きく低減するハードウェアパーサアクセラレータの内容や環境の中に、攻撃の企ての可能性を示すことのある固有特徴のために、著しく高速な文書のスクリーニングを提供することが判る。本発明の侵入検出パーサは、本発明に係るパーサアクセラレータが備えるもの以外には何ら追加の要素やハードウェアを要求せず、如何なる侵入処理が実行可能な状態になるより前に、割り込み及び／又は例外を発することができる。
【００５５】
本発明は単一の好ましい実施形態に関して説明されているが、添付のクレームの精神及び範囲の内部で本発明に修正が施せることは当業者にとって理解の範囲である。
【特許請求の範囲】
【請求項１】
文書の複数バイトのための文字バッファと、
割り込み又は例外、および状態テーブルからの次状態データのうち少なくとも一つにアクセスするために、文書の単一バイトと状態とに従ってアドレスを指定することができる状態テーブルと、
前記次状態データを記憶するレジスタと、
前記状態メモリに対する更なるアドレスを生成するために、前記レジスタの内容を、文書の続きのバイトに連結するための手段と、
前記割り込み又は例外をホストＣＰＵに通信するバスと、
を備える侵入検出システム。
【請求項２】
前記侵入検出システムは、パーサ内に実現される請求項１記載の侵入検出システム。
【請求項３】
前記状態テーブルは、前記レジスタ、および前記連結するための手段のうち少なくとも１つと同じチップ上のメモリ内に実現される請求項１記載の侵入検出システム。
【請求項４】
前記状態テーブルは、外部メモリ内に実現される請求項２記載の侵入検出システム。
【請求項５】
前記状態テーブルが前記外部メモリ内での実現を要求しない際に前記状態テーブルを記憶するためのメモリを、前記レジスタ、および前記連結するための手段のうち少なくとも１つと同じチップ上に更に備える請求項４記載の侵入検出システム。
【請求項６】
前記状態テーブルは、ネットワークパケット伝送速度より大きな速度でアクセスされる請求項１記載の侵入検出システム。
【請求項７】
前記状態テーブル内にコード化されている一つ以上のシーケンスと整合する入力シーケンスの発生の検出に応えて前記ＣＰＵに与えるべきパターンマッチング警報を発するための手段を更に備え、それにより応答速度を上昇させた請求項１記載の侵入検出システム。
【請求項８】
前記割り込み或いは例外に対応する侵入警報が、侵入の企てを防ぎ、或いは制限する侵入防御動作を起動するために、前記ＣＰＵに通信される請求項７記載の侵入検出システム。
【請求項９】
前記状態テーブルは、ネットワークデータパケット伝送速度と実質的に同じ速度でアクセスされる請求項１記載の侵入検出システム。
【請求項１０】
割り込み又は例外、および状態テーブルからの次状態データのうち少なくとも一つにアクセスするために、文書の単一バイトと状態とに従ってアドレスを指定することができる状態テーブルにアクセスするステップと、
前記次状態データを記憶するステップと、
前記状態メモリに対する更なるアドレスを生成するために、前記記憶された次状態データを、文書の続きのバイトに連結するステップと、
前記割り込み又は例外をホストＣＰＵに通信するステップと、
を備える侵入検出方法。
【請求項１１】
前記侵入検出方法は、パーサ内に実現される請求項１０記載の侵入検出方法。
【請求項１２】
前記状態テーブルは、外部メモリ内に実現される請求項１１記載の侵入検出方法。
【請求項１３】
前記状態テーブルは、ネットワークパケット伝送速度より大きな速度でアクセスされる請求項１０記載の侵入検出方法。
【請求項１４】
前記状態テーブル内にコード化されている一つ以上のシーケンスと整合する入力シーケンスの発生の検出に応えて前記ＣＰＵに与えるべきパターンマッチング警報を発するためのステップを更に備え、それにより応答速度を上昇させた請求項１０記載の侵入検出方法。
【請求項１５】
前記割り込み或いは例外に対応する侵入警報が、侵入の企てを防ぎ、或いは制限する侵入防御動作を起動するために、前記ＣＰＵに通信される請求項１４記載の侵入検出方法。
【請求項１６】
前記状態テーブルは、ネットワークデータパケット伝送速度と実質的に同じ速度でアクセスされる請求項１記載の侵入検出システム。
【請求項１】
文書の複数バイトのための文字バッファと、
割り込み又は例外、および状態テーブルからの次状態データのうち少なくとも一つにアクセスするために、文書の単一バイトと状態とに従ってアドレスを指定することができる状態テーブルと、
前記次状態データを記憶するレジスタと、
前記状態メモリに対する更なるアドレスを生成するために、前記レジスタの内容を、文書の続きのバイトに連結するための手段と、
前記割り込み又は例外をホストＣＰＵに通信するバスと、
を備える侵入検出システム。
【請求項２】
前記侵入検出システムは、パーサ内に実現される請求項１記載の侵入検出システム。
【請求項３】
前記状態テーブルは、前記レジスタ、および前記連結するための手段のうち少なくとも１つと同じチップ上のメモリ内に実現される請求項１記載の侵入検出システム。
【請求項４】
前記状態テーブルは、外部メモリ内に実現される請求項２記載の侵入検出システム。
【請求項５】
前記状態テーブルが前記外部メモリ内での実現を要求しない際に前記状態テーブルを記憶するためのメモリを、前記レジスタ、および前記連結するための手段のうち少なくとも１つと同じチップ上に更に備える請求項４記載の侵入検出システム。
【請求項６】
前記状態テーブルは、ネットワークパケット伝送速度より大きな速度でアクセスされる請求項１記載の侵入検出システム。
【請求項７】
前記状態テーブル内にコード化されている一つ以上のシーケンスと整合する入力シーケンスの発生の検出に応えて前記ＣＰＵに与えるべきパターンマッチング警報を発するための手段を更に備え、それにより応答速度を上昇させた請求項１記載の侵入検出システム。
【請求項８】
前記割り込み或いは例外に対応する侵入警報が、侵入の企てを防ぎ、或いは制限する侵入防御動作を起動するために、前記ＣＰＵに通信される請求項７記載の侵入検出システム。
【請求項９】
前記状態テーブルは、ネットワークデータパケット伝送速度と実質的に同じ速度でアクセスされる請求項１記載の侵入検出システム。
【請求項１０】
割り込み又は例外、および状態テーブルからの次状態データのうち少なくとも一つにアクセスするために、文書の単一バイトと状態とに従ってアドレスを指定することができる状態テーブルにアクセスするステップと、
前記次状態データを記憶するステップと、
前記状態メモリに対する更なるアドレスを生成するために、前記記憶された次状態データを、文書の続きのバイトに連結するステップと、
前記割り込み又は例外をホストＣＰＵに通信するステップと、
を備える侵入検出方法。
【請求項１１】
前記侵入検出方法は、パーサ内に実現される請求項１０記載の侵入検出方法。
【請求項１２】
前記状態テーブルは、外部メモリ内に実現される請求項１１記載の侵入検出方法。
【請求項１３】
前記状態テーブルは、ネットワークパケット伝送速度より大きな速度でアクセスされる請求項１０記載の侵入検出方法。
【請求項１４】
前記状態テーブル内にコード化されている一つ以上のシーケンスと整合する入力シーケンスの発生の検出に応えて前記ＣＰＵに与えるべきパターンマッチング警報を発するためのステップを更に備え、それにより応答速度を上昇させた請求項１０記載の侵入検出方法。
【請求項１５】
前記割り込み或いは例外に対応する侵入警報が、侵入の企てを防ぎ、或いは制限する侵入防御動作を起動するために、前記ＣＰＵに通信される請求項１４記載の侵入検出方法。
【請求項１６】
前記状態テーブルは、ネットワークデータパケット伝送速度と実質的に同じ速度でアクセスされる請求項１記載の侵入検出システム。
【図１】
【図２Ａ】
【図２Ｂ】
【図２Ｃ】
【図３】
【図４】
【図５Ａ】
【図５Ｂ】
【図６】
【図２Ａ】
【図２Ｂ】
【図２Ｃ】
【図３】
【図４】
【図５Ａ】
【図５Ｂ】
【図６】
【公表番号】特表２００６−５０５０４２（Ｐ２００６−５０５０４２Ａ）
【公表日】平成１８年２月９日（２００６．２．９）
【国際特許分類】
【出願番号】特願２００４−５４８３４８（Ｐ２００４−５４８３４８）
【出願日】平成１５年１０月３日（２００３．１０．３）
【国際出願番号】ＰＣＴ／ＵＳ２００３／０３１３１３
【国際公開番号】ＷＯ２００４／０４０４２７
【国際公開日】平成１６年５月１３日（２００４．５．１３）
【出願人】（５０１２６５３３１）ロッキード・マーチン・コーポレイション (5)
【氏名又は名称原語表記】ＬＯＣＫＨＥＥＤ ＭＡＲＴＩＮ ＣＯＲＰＯＲＡＴＩＯＮ
【住所又は居所原語表記】６８０１ ＲＯＣＫＬＥＤＧＥ ＤＲＩＶＥ ＢＥＴＨＥＳＤＡ，ＭＤ ２０８１７ ＵＮＩＴＥＤ ＳＴＡＴＥＳ ＯＦ ＡＭＥＲＩＣＡ
【Ｆターム（参考）】
【公表日】平成１８年２月９日（２００６．２．９）
【国際特許分類】
【出願日】平成１５年１０月３日（２００３．１０．３）
【国際出願番号】ＰＣＴ／ＵＳ２００３／０３１３１３
【国際公開番号】ＷＯ２００４／０４０４２７
【国際公開日】平成１６年５月１３日（２００４．５．１３）
【出願人】（５０１２６５３３１）ロッキード・マーチン・コーポレイション (5)
【氏名又は名称原語表記】ＬＯＣＫＨＥＥＤ ＭＡＲＴＩＮ ＣＯＲＰＯＲＡＴＩＯＮ
【住所又は居所原語表記】６８０１ ＲＯＣＫＬＥＤＧＥ ＤＲＩＶＥ ＢＥＴＨＥＳＤＡ，ＭＤ ２０８１７ ＵＮＩＴＥＤ ＳＴＡＴＥＳ ＯＦ ＡＭＥＲＩＣＡ
【Ｆターム（参考）】
[ Back to top ]