(57)【特許請求の範囲】
【請求項１】
弁別条件として予め登録されたエントリパターンと、走査対象となる通信ネットワーク上のトラヒックのパケットから抽出したトラヒックパターンとをパターン照合することにより、これらパケットのデータが所定のデータ集合に属するか否かを弁別するトラヒック走査装置で用いられるトラヒック走査方法であって、
ハッシュ演算部が、前記エントリパターンまたは前記トラヒックパターンからなるキーの射像となるハッシュ値を生成するハッシュ演算ステップと、
エントリ登録部が、前記エントリパターンからなるキーをもとにハッシュ値の生成を前記ハッシュ演算ステップに要求し、得られたハッシュ値をパターン照合時に陽性と判定される照合データとして照合データ記憶部に登録するエントリ登録ステップと、
パターン照合部が、前記トラヒックの各パケットから順次抽出した前記トラヒックパターンごとに、当該トラヒックパターンからなるキーをもとにハッシュ値の生成を前記ハッシュ演算ステップに要求し、得られたハッシュ値と前記照合データ記憶部から読み出した前記照合データとを比較することにより前記パターン照合を行うパターン照合ステップと、
照合結果弁別部が、前記パターン照合の結果、前記トラヒックパターンのハッシュ値のうちから前記照合データと一致する被疑パターンが検出された場合に、当該トラヒックパターンにかかるパケットのデータを陽性と弁別し、当該被疑パターンが検出されなかった場合に当該トラヒックパターンにかかるパケットのデータを陰性と弁別する照合結果弁別ステップとを備え、
前記ハッシュ演算部は、特定用途向けプロセッサにより構成されるとともに、当該特定用途向けプロセッサに、特定のハッシュ種別に関するハッシュ値を算出するハッシュ演算用回路を、前記パターン照合に用いる照合ハッシュ種別ごとにそれぞれ内蔵し、
前記ハッシュ演算ステップは、前記照合ハッシュ種別ごとにハッシュ演算専用命令をそれぞれ有し、これらハッシュ演算専用命令を前記特定用途向けプロセッサで実行して、入力パラメータとして指定された検査データ長およびハッシュ種別に基づいて前記ハッシュ演算用回路の動作を制御することにより、当該照合ハッシュ種別のハッシュ値を生成して出力する
ことを特徴とするトラヒック走査方法。
【請求項２】
請求項１に記載のトラヒック走査方法において、
前記ハッシュ演算ステップは、前記ハッシュ演算専用命令で指定された前記キーについて、当該ハッシュ演算専用命令と対応する前記ハッシュ演算用回路によりハッシュ演算手順を複数回繰り返し実行することにより前記ハッシュ値を生成することを特徴とするトラヒック走査方法。
【請求項３】
請求項１または請求項２に記載のトラヒック走査方法において、
前記ハッシュ演算ステップは、前記ハッシュ演算用回路の任意の組合せに対応する前記ハッシュ演算専用命令を有し、当該ハッシュ演算専用命令で指定された前記キーについて、当該ハッシュ演算専用命令と対応する前記各ハッシュ演算用回路によりハッシュ演算手順を組み合わせて実行することにより前記ハッシュ値を生成することを特徴とするトラヒック走査方法。
【請求項４】
弁別条件として予め登録されたエントリパターンと、走査対象となる通信ネットワーク上のトラヒックのパケットから抽出したトラヒックパターンとをパターン照合することにより、これらパケットのデータが所定のデータ集合に属するか否かを弁別するトラヒック走査装置であって、
前記エントリパターンまたは前記トラヒックパターンからなるキーの射像となるハッシュ値を生成するハッシュ演算部と、
前記エントリパターンからなるキーをもとにハッシュ値の生成を前記ハッシュ演算部に要求し、得られたハッシュ値をパターン照合時に陽性と判定される照合データとして照合データ記憶部に登録するエントリ登録部と、
前記トラヒックの各パケットから順次抽出した前記トラヒックパターンごとに、当該トラヒックパターンからなるキーをもとにハッシュ値の生成を前記ハッシュ演算部に要求し、得られたハッシュ値と前記照合データ記憶部から読み出した前記照合データとを比較することにより前記パターン照合を行うパターン照合部と、
前記パターン照合の結果、前記トラヒックパターンのハッシュ値のうちから前記照合データと一致する被疑パターンが検出された場合に、当該トラヒックパターンにかかるパケットのデータを陽性と弁別し、当該被疑パターンが検出されなかった場合に当該トラヒックパターンにかかるパケットのデータを陰性と弁別する照合結果弁別部とを備え、
前記ハッシュ演算部は、特定用途向けプロセッサにより構成されるとともに、当該特定用途向けプロセッサに、特定のハッシュ種別に関するハッシュ値を算出するハッシュ演算用回路を、前記パターン照合に用いる照合ハッシュ種別ごとにそれぞれ内蔵し、前記照合ハッシュ種別ごとに設けたハッシュ演算専用命令を当該特定用途向けプロセッサで実行して、入力パラメータとして指定された検査データ長およびハッシュ種別に基づいて前記ハッシュ演算用回路の動作を制御することにより、当該照合ハッシュ種別のハッシュ値を生成して出力する
ことを特徴とするトラヒック走査装置。
【請求項５】
請求項４に記載のトラヒック走査装置において、
前記ハッシュ演算部は、前記ハッシュ演算専用命令で指定された前記キーについて、当該ハッシュ演算専用命令と対応する前記ハッシュ演算用回路によりハッシュ演算手順を複数回繰り返し実行することにより前記ハッシュ値を生成することを特徴とするトラヒック走査装置。
【請求項６】
請求項４または請求項５に記載のトラヒック走査装置において、
前記ハッシュ演算部は、前記ハッシュ演算用回路の任意の組合せに対応する前記ハッシュ演算専用命令を有し、当該ハッシュ演算専用命令で指定された前記キーについて、当該ハッシュ演算専用命令と対応する前記各ハッシュ演算用回路によりハッシュ演算手順を組み合わせて実行することにより前記ハッシュ値を生成することを特徴とするトラヒック走査装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パターン照合問題、とりわけ通信ネットワーク上で転送されるパケットに含まれるデータが所定のデータ集合に属するか否かを、特定用途向けプロセッサで効率的かつ柔軟に弁別するためのトラヒック走査技術に関する。
【背景技術】
【０００２】
パターン照合問題は、幅広いアプリケーションで生じる重要な問題である。例えば、次に示す応用範囲に限定されるものではないが、インターネットのテキスト検索システムや遺伝子工学、データベース、通信工学などの分野において、種々の技術課題の克服が必要とされている。とりわけ、通信ネットワーク上で転送されるパケットに含まれるデータが所定のデータ集合に属するか否かを効率的に弁別する技術は、異常トラヒックを早期に検出・遮断して安定化を図ることで保安上のリスク低減に繋がるため、安心・安全な通信インフラを支え続けていくにあたって不可欠な要素技術である。
【０００３】
一般に、このようなデータ弁別技術では、予め弁別に用いる条件を登録する機能部と、各パケットから抽出したパターンを照合するための機能部で構成され、直接照合の負担を軽減するためにハッシュ演算が用いられることがある。
【０００４】
具体的には、照合したいパターンのハッシュ値を生成するハッシュ演算部を設けて、予め条件となるハッシュ値をハッシュ演算部で生成し、これを照合データとして照合データ記憶部に格納しておく。そして、実際にパケットデータを弁別する際、弁別対象となるトラヒックからパケットバイパケットに抽出した各トラヒックのパターンについて、同ハッシュ演算部でハッシュ値を生成し、照合データ記憶部から読み出した照合データとパターン照合することになる。
【０００５】
このため、パターン照合問題では、ハッシュ演算部において、いかに効率よくハッシュ値を生成するかが重要となる。
図９は、従来のハッシュ演算部の要部構成を示す説明図である。従来、データ弁別技術で用いるハッシュ演算部について、非特許文献１に示すような、照合するパターンの検査データ長に応じて複数のブルームフィルタ（Ｂｌｏｏｍｆｉｌｔｅｒ）を並列に構成し、トラヒックパターンの弁別をハードウェアで高速に処理する技術が提案されている。
【０００６】
ブルームフィルタは、非特許文献２に示す通り、データベースのようなデータサイエンス分野で考案された古典的なデータ構造であり、実用上問題ない水準において所定の偽陽性確率を許容することで、空間計算量を効率化する工夫がなされている。応用範囲として、データサイエンス分野に限定されるものではないため、通信分野においても、非特許文献１に代表されるような数多くの提案がなされている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特許登録第３８６０５７５号公報
【非特許文献】
【０００８】
【非特許文献１】S. Dharmapurikar, et al., "Deep Packet Inspection Using Parallel Bloom Filters", IEEE Micro, January/February 2004, Volume24, Issue1, p.52-61.
【非特許文献２】Burton H. Bloom, "Space/Time Trade-offs in Hash Coding with Allowable Errors", Communications of the ACM, 1970.
【非特許文献３】S. Dharmapurikar, et al., "Longest Prefix Matching Using Bloom Filters", Proceedings of the 2003 conference on ACM SIGCOMM 2003, p.201-212.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
このような従来技術によれば、ハッシュ演算部において、異なる検査データ長ごとにハッシュ値を一斉並列に生成する構成となっているため、検査データ長１バイトごとに個別のブルームフィルタを備えることになり、回路規模が増大するという問題点があった。また、ブルームフィルタは通常、複数のハッシュ演算の組み合わせで構成されるが、ハードウェアで別種のハッシュ演算アルゴリズムを実装するには複数の回路構成を持たせなければならないため、さらに回路規模が増大することになる。
【００１０】
ハッシュ種別については、一般に約数十種類ほど存在し、トラヒック走査に要求される照合精度（偽陽性確率の高低）に応じて、いずれかのハッシュ種別を複数組み合わせることにより、照合に用いるハッシュ値を生成することになる。
また、データ長については、標準的なパケットでは１５００バイトであるが、９０００バイトや１６０００バイトのデータ長を有する、いわゆるジャンボフレームと呼ばれるパケットも弁別対象となる場合もある。
【００１１】
したがって、従来技術を用いて各種のトラヒック走査を行う場合、ハッシュ種別数をＮｈとしデータ長をＷとすると、ハッシュ演算部に備えるべきブルームフィルタの数は、おおよそＮｈ×Ｗ個（ただし、Ｗ＝通常時〜１５００、最悪の場合１６０００）となり、極めて膨大な数のブルームフィルタを実装する必要がある。このため、ハッシュ演算部において、回路規模および消費電力が大幅に増大するという問題点があった。
【００１２】
本発明はこのような課題を解決するためのものであり、ハッシュ演算部の回路規模および消費電力を削減できるトラヒック走査技術を提供することを目的としている。
【課題を解決するための手段】
【００１３】
このような目的を達成するために、本発明にかかるトラヒック走査方法は、弁別条件として予め登録されたエントリパターンと、走査対象となる通信ネットワーク上のトラヒックのパケットから抽出したトラヒックパターンとをパターン照合することにより、これらパケットのデータが所定のデータ集合に属するか否かを弁別するトラヒック走査装置で用いられるトラヒック走査方法であって、ハッシュ演算部が、前記エントリパターンまたは前記トラヒックパターンからなるキーの射像となるハッシュ値を生成するハッシュ演算ステップと、エントリ登録部が、前記エントリパターンからなるキーをもとにハッシュ値の生成を前記ハッシュ演算ステップに要求し、得られたハッシュ値をパターン照合時に陽性と判定される照合データとして照合データ記憶部に登録するエントリ登録ステップと、パターン照合部が、前記トラヒックの各パケットから順次抽出した前記トラヒックパターンごとに、当該トラヒックパターンからなるキーをもとにハッシュ値の生成を前記ハッシュ演算ステップに要求し、得られたハッシュ値と前記照合データ記憶部から読み出した前記照合データとを比較することにより前記パターン照合を行うパターン照合ステップと、照合結果弁別部が、前記パターン照合の結果、前記トラヒックパターンのハッシュ値のうちから前記照合データと一致する被疑パターンが検出された場合に、当該トラヒックパターンにかかるパケットのデータを陽性と弁別し、当該被疑パターンが検出されなかった場合に当該トラヒックパターンにかかるパケットのデータを陰性と弁別する照合結果弁別ステップとを備え、前記ハッシュ演算部は、特定用途向けプロセッサにより構成されるとともに、当該特定用途向けプロセッサに、特定のハッシュ種別に関するハッシュ値を算出するハッシュ演算用回路を、前記パターン照合に用いる照合ハッシュ種別ごとにそれぞれ内蔵し、前記ハッシュ演算ステップは、前記照合ハッシュ種別ごとにハッシュ演算専用命令をそれぞれ有し、これらハッシュ演算専用命令を前記特定用途向けプロセッサで実行して、入力パラメータとして指定された検査データ長およびハッシュ種別に基づいて前記ハッシュ演算用回路の動作を制御することにより、当該照合ハッシュ種別のハッシュ値を生成して出力するようにしたものである。
【００１４】
また、本発明にかかる上記トラヒック走査方法の一構成例は、前記ハッシュ演算ステップが、前記ハッシュ演算専用命令で指定された前記キーについて、当該ハッシュ演算専用命令と対応する前記ハッシュ演算用回路によりハッシュ演算手順を複数回繰り返し実行することにより前記ハッシュ値を生成するようにしたものである。
【００１５】
また、本発明にかかる上記トラヒック走査方法の一構成例は、前記ハッシュ演算ステップが、前記ハッシュ演算用回路の任意の組合せに対応する前記ハッシュ演算専用命令を有し、当該ハッシュ演算専用命令で指定された前記キーについて、当該ハッシュ演算専用命令と対応する前記各ハッシュ演算用回路によりハッシュ演算手順を組み合わせて実行することにより前記ハッシュ値を生成するようにしたものである。
【００１６】
また、本発明にかかるトラヒック走査装置は、弁別条件として予め登録されたエントリパターンと、走査対象となる通信ネットワーク上のトラヒックのパケットから抽出したトラヒックパターンとをパターン照合することにより、これらパケットのデータが所定のデータ集合に属するか否かを弁別するトラヒック走査装置であって、前記エントリパターンまたは前記トラヒックパターンからなるキーの射像となるハッシュ値を生成するハッシュ演算部と、前記エントリパターンからなるキーをもとにハッシュ値の生成を前記ハッシュ演算部に要求し、得られたハッシュ値をパターン照合時に陽性と判定される照合データとして照合データ記憶部に登録するエントリ登録部と、前記トラヒックの各パケットから順次抽出した前記トラヒックパターンごとに、当該トラヒックパターンからなるキーをもとにハッシュ値の生成を前記ハッシュ演算部に要求し、得られたハッシュ値と前記照合データ記憶部から読み出した前記照合データとを比較することにより前記パターン照合を行うパターン照合部と、前記パターン照合の結果、前記トラヒックパターンのハッシュ値のうちから前記照合データと一致する被疑パターンが検出された場合に、当該トラヒックパターンにかかるパケットのデータを陽性と弁別し、当該被疑パターンが検出されなかった場合に当該トラヒックパターンにかかるパケットのデータを陰性と弁別する照合結果弁別部とを備え、前記ハッシュ演算部は、特定用途向けプロセッサにより構成されるとともに、当該特定用途向けプロセッサに、特定のハッシュ種別に関するハッシュ値を算出するハッシュ演算用回路を、前記パターン照合に用いる照合ハッシュ種別ごとにそれぞれ内蔵し、前記照合ハッシュ種別ごとに設けたハッシュ演算専用命令を当該特定用途向けプロセッサで実行して、入力パラメータとして指定された検査データ長およびハッシュ種別に基づいて前記ハッシュ演算用回路の動作を制御することにより、当該照合ハッシュ種別のハッシュ値を生成して出力するようにしたものである。
【００１７】
また、本発明にかかる上記トラヒック走査装置の一構成例は、前記ハッシュ演算部が、前記ハッシュ演算専用命令で指定された前記キーについて、当該ハッシュ演算専用命令と対応する前記ハッシュ演算用回路によりハッシュ演算手順を複数回繰り返し実行するようにしたものである。
【００１８】
また、本発明にかかる上記トラヒック走査装置の一構成例は、前記ハッシュ演算部が、前記ハッシュ演算用回路の任意の組合せに対応する前記ハッシュ演算専用命令を有し、当該ハッシュ演算専用命令で指定された前記キーについて、当該ハッシュ演算専用命令と対応する前記各ハッシュ演算用回路によりハッシュ演算手順を組み合わせて実行することにより前記ハッシュ値を生成するようにしたものである。
【発明の効果】
【００１９】
本発明によれば、特定用途向けプロセッサからなるハッシュ演算部において、ハッシュ演算専用命令が実行されて、ハッシュ種別ごとに１つずつ設けられているハッシュ演算用回路でハッシュ値が生成される。また、走査データ長やハッシュ種別の指定および組合せは走査パラメータ指定部で柔軟に変更できる。したがって、従来技術のように、ハッシュ種別ごとのブルームフィルタを検査データ長ごとに別個に設ける必要がなくなるため、本実施の形態によれば、ハッシュ演算に要する回路規模を大幅に削減することができる。
【００２０】
このため、９０００バイトや１６０００バイトのデータ長を有する、いわゆるジャンボフレームと呼ばれるパケットを弁別対象とする場合でも、１５００バイトのデータ長を有する標準的なパケットと同様、ハッシュ演算部のハッシュ演算用回路で対応することができ、極めて高い実装効率を実現することが可能となる。
【図面の簡単な説明】
【００２１】
【図１】第１の実施の形態にかかるトラヒック走査装置の構成を示すブロック図である。
【図２】一般的なＲＩＳＣプロセッサの構成を示すブロック図である。
【図３】エントリ登録処理を示すフローチャートである。
【図４】パターン照合処理および照合結果弁別処理を示すフローチャートである。
【図５】第１の実施の形態にかかる全体的なトラヒック走査方法を示す説明図である。
【図６】ハッシュ演算専用命令セットの具体的な構成を示す説明図である。
【図７】第２の実施の形態にかかるトラヒック走査装置の構成を示すブロック図である。
【図８】第２の実施の形態にかかる全体的なトラヒック走査方法を示す説明図である。
【図９】従来のハッシュ演算部の要部構成を示す説明図である。
【発明を実施するための形態】
【００２２】
次に、本発明の実施の形態について図面を参照して説明する。
［第１の実施の形態］
まず、図１を参照して、本発明の第１の実施の形態にかかるトラヒック走査装置１０について説明する。図１は、第１の実施の形態にかかるトラヒック走査装置の構成を示すブロック図である。
【００２３】
このトラヒック走査装置１０は、弁別条件として予め登録されたエントリパターンと、走査対象となる通信ネットワーク上のトラヒックのパケットから抽出したトラヒックパターンとをパターン照合することにより、これらパケットのデータが所定のデータ集合に属するか否かを弁別する機能を有している。本実施の形態では、これらパターン照合に用いるハッシュ値の生成に、ＲＩＳＣ（Reduced Instruction Set Computer：縮小命令セットコンピュータ）プロセッサなどの特定用途向けプロセッサ（ＡＳＩＰ：Application Specific Instruction Processor）を用いる点が特徴になる。
【００２４】
まず、本実施の形態にかかるトラヒック走査方法が前提とする一般的な特定用途向けプロセッサについて説明する。図２は、一般的なＲＩＳＣプロセッサの構成を示すブロック図である。このようなＲＩＳＣプロセッサの構成に対して、例えば特許文献１（構成可能な実行ユニットを有する高性能のハイブリッドプロセッサ）に開示されているＡＳＩＰ設計手法を適用することにより、特定用途向けの専用命令を実行するための演算ユニットないしレジスタを追加できることは、当業者であれば容易に理解することができる。
【００２５】
一般に、プロセッサが備えるロードストア命令はメモリおよびレジスタファイル間のデータ移動を伴うため、高性能な処理を指向する際に支配的なボトルネックとなる。本実施形態によれば、ＲＩＳＣプロセッサのパイプラインにおける実行ステージで結合された、算術論理演算ユニットおよびレジスタファイルを拡張してトラヒック走査専用命令を実行することができるため、一般的なＲＩＳＣプロセッサで多発するようなロードストア命令の発行を抑制することができる。
また、算術論理演算ユニット内部は、アプリケーション設計者が独自に走査処理の効率化を加味した命令および並列化論理を構成できるため、結果としてトラヒック走査に要する処理サイクル数を大幅に削減することができる。
【００２６】
次に、図１を参照して、本実施の形態にかかるトラヒック走査装置１０の構成について詳細に説明する。
図１に示すように、トラヒック走査装置１０には、主な機能部として、ハッシュ演算部１１、エントリ登録部１２、照合データ記憶部１３、走査パラメータ指定部１４、パターン照合部１５、照合結果弁別部１６、信号入出力部１７、および信号制御部１８が設けられている。
【００２７】
ハッシュ演算部１１は、エントリパターンまたはトラヒックパターンからなる検査キーデータの射像となるハッシュ値を生成する機能を有している。本実施の形態は、ハッシュ演算部１１を特定用途向けプロセッサに内蔵する構成をとるものであり、詳細について後述する。
【００２８】
エントリ登録部１２は、エントリパターンからなるキーをもとにハッシュ値の生成をハッシュ演算部１１に要求し、得られたハッシュ値をパターン照合時に陽性と判定される照合データとして照合データ記憶部１３に登録する機能を有している。
照合データ記憶部１３は、エントリ登録部１２により登録された各種照合データを記憶する機能を有している。
【００２９】
走査パラメータ指定部１４は、走査データ長や演算するハッシュ種別などの各種入力パラメータを、信号制御部１８の制御に基づいて予め静的に指定する機能を有している。指定した走査データ長に応じて、エントリ登録部１２およびパターン照合部１５のキー長が変更される。
パターン照合部１５は、走査対象となるトラヒックの各パケットから順次抽出したトラヒックパターンごとに、当該トラヒックパターンからなるキーをもとにハッシュ値の生成をハッシュ演算部１１に要求し、得られたハッシュ値と照合データ記憶部１３から読み出した照合データとを比較してパターン照合を行うことにより、各トラヒックパターンが目的のエントリパターンに合致するか否かを検査する機能とを有している。
【００３０】
照合結果弁別部１６は、パターン照合部１５でのパターン照合の結果、トラヒックパターンのハッシュ値のうちから照合データと一致する被疑パターンが検出された場合に、当該トラヒックパターンにかかるパケットのデータを陽性と弁別し、当該被疑パターンが検出されなかった場合に当該トラヒックパターンにかかるパケットのデータを陰性と弁別する機能を有している。
【００３１】
信号入出力部１７は、信号線Ｌを介して各機能部間においてトラヒックおよび各種値を転送する機能を有している。
信号制御部１８は、信号線Ｌを介して各機能部の値を設定し、動作命令全体を制御する機能を有している。各機能部のパラメータは、信号制御部１８により走査パラメータ指定部が制御され、図２の汎用レジスタにロードされる。
本実施の形態は、これらの機能部を用いて、所定の処理手順により、柔軟かつ高速にトラヒックを走査するようにしたものである。
【００３２】
［第１の実施の形態の動作］
次に、図３〜図５を参照して、本実施の形態にかかるトラヒック走査装置１０の動作について説明する。図３は、エントリ登録処理を示すフローチャートである。図４は、パターン照合処理および照合結果弁別処理を示すフローチャートである。図５は、第１の実施の形態にかかる全体的なトラヒック走査方法を示す説明図である。
【００３３】
トラヒック走査装置１０では、対象となるトラヒックを走査する場合、まず、エントリ登録部１２によりエントリ登録処理を実行して、弁別条件であるエントリパターンの登録を行った後、パターン照合部１５によりパターン照合処理を実行して、登録済のエントリパターンとトラヒックのパケットから抽出したトラヒックパターンとのパターン照合を行うことにより、各パケットのデータが所定のデータ集合に属するか否かを弁別する。なお、照合に先だって、トラヒック走査装置１０の信号制御部１８は、走査データ長や演算するハッシュ種別が走査パラメータ指定部１４により予め静的に指定されているものとし、登録・照合時には、図２に示す一般的な汎用レジスタにそれらをロードした値を用いる構成をとる。
【００３４】
まず、図３を参照して、エントリ登録処理の全体的な流れについて説明する。
エントリ登録部１２は、まず、信号制御部１８の照合設定情報からハッシュ種別および走査データ長を取得するとともに（ステップ１００）、エントリパターンを取得する（ステップ１０１）。図５の例では、エントリパターンとして「１０１０１０１０」、「０１０１０１０１」、および「１１１１１１１１」という３つのエントリパターンが用いられている。
【００３５】
続いて、エントリ登録部１２は、これらエントリパターンに関するハッシュ値の生成をハッシュ演算部１１に要求する（ステップ１０２）。この際、ハッシュ演算部１１には、予めパターン照合に使用されうるハッシュ種別ごとにハッシュ演算専用命令が設けられており、エントリ登録部１２は、走査パラメータ指定部１４が指定するハッシュ種別のハッシュ演算専用命令を用いて、ハッシュ値を生成するよう要求する。
【００３６】
ハッシュ演算部１１は、指定されたハッシュ演算命令を特定用途向けプロセッサの内部に構成した専用の演算器およびレジスタで実行することにより、ハッシュ値ｈentryを生成して出力する。
図５の例では、ｓａｘ、ｓｄｂｍ、およびｂｅｒｎｓｔｅｉｎからなる３種類のハッシュ種別について、それぞれのハッシュ値を生成するためのハッシュ演算専用命令ｓａｘ＿ｈａｓｈ、ｓｄｂｍ＿ｈａｓｈ、およびｂｅｒｎｓｔｅｉｎ＿ｈａｓｈが、ハッシュ種別ごとに個別に設けられている。
【００３７】
したがって、これらハッシュ演算専用命令により、例えばエントリパターン「１０１０１０１０」をｋｅｙとして、照合ハッシュ種別として指定されたｓａｘ、ｓｄｂｍ、およびｂｅｒｎｓｔｅｉｎからなる異なる３種類のハッシュ演算が３回繰り返された後、１つのハッシュ値ｈentryが生成される。
【００３８】
エントリ登録部１２は、このようにしてハッシュ演算部１１で生成されたハッシュ値ｈentryを受け取り、これらハッシュ値ｈentryを、パターン照合時における陽性判定となる被疑パターンを示す照合データ（ｐｏｓｉｔｉｖｅ値）として照合データ記憶部１３にそれぞれ登録し（ステップ１０３）、一連のエントリ登録処理を終了する。
【００３９】
次に、図４を参照して、パターン照合処理の全体的な流れについて説明する。
パターン照合部１５は、まず、エントリ登録処理と同様にして、走査パラメータ指定部１４により信号制御部１８に指定された値からハッシュ種別および走査データ長を取得する（ステップ１１０）。
続いて、パターン照合部１５は、照合データ記憶部１３から前述したエントリ登録処理で予め登録されている照合データを取得する（ステップ１１１）。この照合データは、走査パラメータであるハッシュ種別および走査データ長に基づき生成されたものである。
【００４０】
次に、パターン照合部１５は、信号入出力部１７により、走査対象となるトラヒックからパケットバイパケットにトラヒックパターンを抽出し（ステップ１１２）、このトラヒックパターンに関するハッシュ値の生成をハッシュ演算部１１に要求する（ステップ１１３）。この際、パターン照合部１５は、エントリ登録処理１２と同様にして、ハッシュ演算部１１にハッシュ値の生成を要求する。
【００４１】
これにより、エントリ登録処理と同様にして、ハッシュ演算部１１により、照合ハッシュ種別および検査データ長に応じた１つのハッシュ値ｈcheckが生成される。
パターン照合部１５は、このようにしてハッシュ演算部１１で生成されたハッシュ値ｈcheckを受け取り、これらハッシュ値ｈcheckを、被疑パターンを示す照合データ（ｐｏｓｉｔｉｖｅ値）と照合する（ステップ１１４）。
【００４２】
この照合において、ハッシュ値ｈcheckと照合データとが一致せず、被疑パターンが検出されなかった場合（ステップ１１５：ＮＯ）、照合結果弁別部１６は、当該トラヒックパターンに関する照合結果が陰性であると判定し（ステップ１１６）、ステップ１１２へ移行して新たなパケットに関するパターン照合を開始する。
【００４３】
一方、ハッシュ値ｈcheckと照合データとが一致し、被疑パターンが検出された場合（ステップ１１５：ＹＥＳ）、照合結果弁別部１６は、当該トラヒックパターンに関する照合結果が陽性であると判定し（ステップ１１７）、ステップ１１２へ移行して新たなパケットに関するパターン照合を繰り返す。当該装置の利用者が照合プログラムの停止を指示するとき、一連のパターン照合処理を終了する。
これにより、被疑パターンを検出でき、信号制御部１８を用いて該当トラヒックの分離や遮断、規制、廃棄等の制御を行うことができる。
【００４４】
［ハッシュ演算部の詳細］
次に、図５を参照して、本実施の形態にかかるハッシュ演算部１１の詳細を説明する。
通信トラヒックの走査において目的とするトラヒックパターンを検出するため、弁別条件として、予め検出したいパターンを示すエントリパターンを、エントリ登録部１２により照合データ記憶部１３に登録しておく必要がある。この際、登録できるエントリパターンの数は実装するプロセッサ、論理回路およびシステムによって区々であるが、エントリパターン数ｎと記憶空間上のハッシュテーブルのサイズｍが決定しているとき、偽陽性確率ｐを最小化できるようなハッシュ演算数ｋが定式化され、広く知られている。非特許文献１および非特許文献２に詳述されているため、詳細は割愛するが、関係式は次の式（１）の通りである。また、偽陽性確率ｐは次の式（２）のようになる。
【００４５】
【数１】
0005952239.tif 000002
【００４６】
【数２】
0005952239.tif 000003
【００４７】
ブルームフィルタを用いることにより、照合データ（ｐｏｓｉｔｉｖｅ値）中に偽陽性確率ｐの分だけ、擬陽性（ｆａｌｓｅ  ｐｏｓｉｔｉｖｅ）が生じることを許容することにより、記憶空間の効率（ｍ／ｎ）を高めながらハッシュ演算量ｋを決めることができる。ただし、非特許文献１および非特許文献２に示されているブルームフィルタによれば、エントリパターンの登録はできても削除ができない。このため、エントリパターンの登録数ｎが増えるにしたがってハッシュテーブルサイズｍが大きくなり、偽陽性確率ｐが増えてしまうという課題がある。
【００４８】
このような課題に関する対処手法も広く知られており、ＣＢＦ（Counting Bloom Filter）と呼ばれる。オリジナルのブルームフィルタにおけるハッシュテーブルの最小構成要素が１ビットのメモリであるのに対し、ＣＢＦは数ビットに拡張してカウンタを構成し、カウンタをインクリメントおよびデクリメントすることによりエントリの削除ができるように拡張したデータ構造を有している。非特許文献３は、通信トラヒックのデータ内部の走査とは異なるアプリケーションであるが、パケットのヘッダ部分を最長一致検索する際にＣＢＦを応用している。
【００４９】
説明を簡略化するため、図５に例示したトラヒック走査方法において、ブルームフィルタをＣＢＦにした場合のエントリの削除手段については図示していない。ただし、当業者であれば容易にエントリの削除手段の実装方法を着想することができるため、本実施の形態にかかるエントリ登録部１２および照合データ記憶部１３は、エントリの削除に対応することを含意する。
【００５０】
ハッシュ演算部１１は、エントリ登録部１２から入力されたエントリパターンの値をキーとして、単一種類のハッシュ演算手順をｋ回繰り返す。あるいは、複数種類のハッシュ演算手順を組み合わせてｋ回演算してもよい。いずれにせよ、入力されたエントリパターンに対し、射影関係となるハッシュ値を１つ生成し、エントリ登録部１２に出力する機能を持つ。
【００５１】
一方、パターン照合部１５から入力されたトラヒックパターンについて、エントリパターンに対応する長さのフィールドの値をキーとして、単一種類のハッシュ演算手順をｋ回繰り返す。あるいは、複数種類のハッシュ演算を組み合わせてｋ回演算してもよい。いずれにせよ、入力されたトラヒックパターンに対して射影関係となるハッシュ値を生成し、パターン照合部１５に出力する機能を持つ。
【００５２】
ハッシュ値の演算手順に関しては、アルゴリズム単体でも数十種類の方式があるため、本実施の形態では、図５に示すよう、ｓａｘ＿ｈａｓｈ，ｓｄｂｍ＿ｈａｓｈ，ｂｅｒｎｓｔｅｉｎ＿ｈａｓｈからなる３種類のハッシュ演算アルゴリズムを例として用いる。ハッシュ演算専用の命令セットを構成する際には、もちろん３種類のみに限定されるものではなく、他の方式を採用することによりハッシュ値の分散特性を改善させることができ、偽陽性確率ｐの低減に繋がる。本実施の形態では、例として３種類のハッシュ演算手順を組み合わせてｈentryおよびｈcheckを求めている。
【００５３】
図６は、ハッシュ演算専用命令セットの具体的な構成を示す説明図である。ここでは、専用命令ごとに、当該処理を実現するハッシュ演算用回路の基本構成例が示されている。命令フォーマットのビット幅は一般的には３２ビット長であることが多いが、選択するＡＳＩＰ設計技術によって１６ビットや２４ビットなど複数の実装解があり得る。選択したＡＳＩＰ設計技術が提供する専用言語を用いて図６に示すハッシュ演算回路を記述する。尚、演算ハッシュ種別および走査データ長は、走査パラメータ指定部１４により図２の汎用レジスタにロードされた値が用いられる。
【００５４】
ｓａｘ＿ｈａｓｈ，ｓｄｂｍ＿ｈａｓｈ，ｂｅｒｎｓｔｅｉｎ＿ｈａｓｈは、それぞれのハッシュ演算用回路の構成要素となる演算器が異なる。例えば、ｓａｘ＿ｈａｓｈの場合は加算器２つと３２ビットのＸＯＲが１つ、ｓｄｂｍ＿ｈａｓｈであれば加算器３つ、ｂｅｒｎｓｔｅｉｎ＿ｈａｓｈは加算器２つで構成できる。左右のシフタは、一般的なＲＩＳＣプロセッサであれば基本命令として実装されているため、実施にあたって新たなハードウェアの追加は不要である。尚、各演算器は、図２の算術論理演算ユニットとは別系統のユニットとして設けられ、セレクタ回路と並列に接続する。
【００５５】
専用の演算器およびレジスタを記述するための設計言語は、ツールによって区々であるが、ＨＤＬ（Hardware Description Language）に似た、上位抽象度の言語が様々開発されており、ＡＳＩＰ設計技術においては、ＡＤＬ（Architecture Desctiption Language）と呼ばれる。記述の抽象度が高められているため、Ｖｅｒｉｌｏｇ等のＨＤＬ記述に比べて、数分の１〜数十分の１程度の記述量でＩＳＳ（Instruction Set Simulator）でサイクルシミュレーション可能な命令セットを実装することができる。いずれにせよ、本発明内容をもとに、当業者であれば容易に記述することができるので、詳細を割愛する。
【００５６】
また、専用命令はＣ言語などの高級言語から組み込み関数として呼び出すことができる。ソフトウェアとのインタフェースを備えているため、種々のパラメータを拡張論理ユニットとの間で授受することができ、柔軟なトラヒック走査処理が可能となる。
【００５７】
図６において、機械語へのマッピングを担う命令は、ｓａｘ＿ｈａｓｈ，ｓｄｂｍ＿ｈａｓｈ，ｂｅｒｎｓｔｅｉｎ＿ｈａｓｈである。各ハッシュ演算用回路では、入力レジスタファイルから各々３２ビットのキー（ｋｅｙ）および暫定ハッシュ値（ｈ）を取得し、所定の手順を経て最終的にはｈentryおよびｈcheckとして用いられるハッシュ値をレジスタファイルに出力する。以下に、上記の各命令をプログラムから呼び出してパターンを照合するための具体的な記述例を示す。
【００５８】
void check()
{
if (queue_not_empty()) {
queue_in();
sax_hash();
sdbm_hash();
bernstein_hash();
queue_out();
}
}
【００５９】
各命令はＣ言語等の高級言語プログラムから、上記のように組み込み関数として呼び出すことができる。まず、信号入出力部１７のキューにおいて照合するデータの有無をチェックし、照合データがあればキューからデータを読み出し、順次ハッシュ演算命令を実行する。本例では、bernstein_hash演算が完了した段階でトラヒックパターンに対応するｈｃｈｅｃｋが得られ、信号入出力部１７のキューに出力され、パターン照合部１５でｐｏｓｉｔｉｖｅ値との比較が行われる。
【００６０】
このように、本実施の形態は、ハッシュ種別ごとに１つずつ設けたハッシュ演算用回路で、ハッシュ値を生成している。また、走査データ長やハッシュ種別の指定および組合せは走査パラメータ指定部１４で柔軟に変更できる。したがって、従来技術のように、ハッシュ種別ごとのブルームフィルタを検査データ長ごとに別個に設ける必要がなくなるため、ハッシュ演算に要する回路規模を大幅に削減できる。
【００６１】
以下、本発明のトラヒック走査方法における、エントリ登録部１２以降の処理動作について説明する。
エントリ登録部１２に入力されたｈentryは、エントリパターンがハッシュ値に射影された縮約表現と見なすことができ、トラヒックパターン照合時に陽性を示すための照合データ、すなわちｐｏｓｉｔｉｖｅ値となる。エントリ登録部１２は、この照合データをビット操作により照合データ記憶部１３に登録する。
【００６２】
パターン照合部１５は、走査対象となるトラヒックからパケットバイパケットに抽出したトラヒックパターンのうち、エントリパターンに対応するフィールドの値をキーとして指定してハッシュ演算部１１にハッシュ値の生成を要求し、演算結果としてハッシュ値ｈcheckを得る。
照合結果弁別部１６は、このｈcheckを照合データ記憶部１３から読み出した照合データと比較照合した結果、陽性と判別された場合、被疑パターンの検出を完了し、信号制御部１８を用いてトラヒックの分離や遮断、規制、廃棄等の制御を行うことができる。
【００６３】
エントリパターンに該当列が存在していることから陽性判定は明らかであるが、図５では簡単のため「Ｆｉｅｌｄ  ”１０１０１０１０”  ｉｓ  ｐｒｏｂａｂｌｙ  ａ  ｍｅｍｂｅｒ．」と表記している。実際にそのようなメッセージが出力されるとは限らない。ただし、本実施例では偽陽性無しの真の陽性と判別されているが、ブルームフィルタの原理として、あくまでも該当列が存在している「可能性がある」ことだけが分かる。つまり、偽陽性（ｆａｌｓｅ  ｐｏｓｉｔｉｖｅ）が含まれる可能性もある。
【００６４】
一方、陰性の場合は、被疑パターンの検出無しを意味する「Ｆｉｅｌｄ“１１１０１１１０”ｉｓ  ｄｅｆｉｎｉｔｅｌｙ  ｎｏｔ  ａ  ｍｅｍｂｅｒ．」と表記している。この場合、ブルームフィルタの原理より、被疑パターンはエントリの集合には絶対に存在しないことが分かる。すなわち、偽陰性（ｆａｌｓｅ  ｐｏｓｉｔｉｖｅ）の可能性は一切ない。そのため、陰性のトラヒックは信号制御部１８を用いて透過する等の制御を実施することができる。
【００６５】
［第１の実施の形態の効果］
このように、本実施の形態は、ハッシュ演算部１１を、特定用途向けプロセッサにより構成するとともに、特定用途向けプロセッサに、特定のハッシュ種別に関するハッシュ値を算出するハッシュ演算用回路を、パターン照合に用いる照合ハッシュ種別ごとにそれぞれ内蔵し、照合ハッシュ種別ごとに設けたハッシュ演算専用命令を特定用途向けプロセッサで実行して、走査パラメータ指定部１４で指定した入力パラメータに基づいて当該ハッシュ演算用回路の動作を制御することにより、当該照合ハッシュ種別のハッシュ値を生成して出力するようにしたものである。
【００６６】
これにより、特定用途向けプロセッサからなるハッシュ演算部１１において、ハッシュ演算専用命令が実行されて、ハッシュ種別ごとに１つずつ設けられているハッシュ演算用回路で、任意のハッシュ種別および検査データ長に関するハッシュ値が生成される。
したがって、従来技術のように、ハッシュ種別ごとのブルームフィルタを検査データ長ごとに別個に設ける必要がなくなるため、本実施の形態によれば、ハッシュ演算に要する回路規模を大幅に削減することができる。
【００６７】
このため、ハッシュ種別数をＮｈとしデータ長をＷとするとき、従来のハッシュ演算部に備えるべきブルームフィルタの数は、おおよそＮｈ×Ｗ個（ただし、Ｗ＝通常時〜１５００、最悪の場合１６０００）であったのに対し、本発明によればＮｈ×Ｗ個（ただし、Ｗ＝数個）で構成することができる。したがって、９０００バイトや１６０００バイトのデータ長を有する、いわゆるジャンボフレームと呼ばれるパケットを弁別対象とする場合でも、１５００バイトのデータ長を有する標準的なパケットと同様、ハッシュ種別ごとに１つずつ設けた少数のハッシュ演算用回路で対応することができ、極めて高い実装効率を実現することが可能となる。
【００６８】
また、実際には、各ハッシュ演算用回路で生成されたいずれかのハッシュ値を選択して、エントリ登録部１２やパターン照合部１５へ出力するセレクタ回路が、ハッシュ演算部１１の出力段に必要となる。この際、従来技術のように多くのブルームフィルタが設けられている場合、ブルームフィルタの数に応じてセレクタ回路の回路規模および接続配線による専有面積も極めて大きなものとなる。一方、本実施の形態によれば、高々数個のハッシュ演算用回路からの出力を選択するセレクタ回路で済むため、セレクタ回路の回路規模および接続配線による専有面積をも大幅に削減することが可能となる。
【００６９】
［第２の実施の形態］
次に、図７を参照して、本発明の第２の実施の形態にかかるトラヒック走査装置１０について説明する。図７は、第２の実施の形態にかかるトラヒック走査装置の構成を示すブロック図である。
第１の実施の形態と比較して、本実施の形態にかかるトラヒック走査装置１０には、走査パラメータ指定部１４に代えて、走査ウィンドウ設定部１９が追加されている。
【００７０】
走査ウィンドウ設定部１９は、パターン照合部１５において、トラヒックパターンのハッシュ値と、照合データ記憶部１３から読み出した照合データ（ｐｏｓｉｔｉｖｅ値）とをパターン照合する際、プログラムに従って、演算するハッシュ種別（アルゴリズム）や走査位置（オフセット）および走査データ長（マスク）を動的に変更する機能を有している。
【００７１】
図８は、第２の実施の形態にかかる全体的なトラヒック走査方法を示す説明図である。
走査ウィンドウ設定部１９は、前述したアルゴリズムやオフセットおよびマスクを、対応する各機能部に指定する。
これに応じて、パターン照合部１５は、ハッシュ値および照合データの全ビットをパターン照合するのではなく、プログラムで指定された走査ウィンドウ内のビットについてのみパターン照合する。このため、走査ウィンドウ設定部１９によりマスクされたビット部分については、パターン照合されなくなる。
【００７２】
また、被疑パターンが検出されて、照合結果が陽性であると判定されるまでの一連のパターン照合処理において、処理の途中で走査位置および走査データ長を変更することができる。
したがって、トラヒック走査パラメータを動的に調整することが可能となり、極めて柔軟性の高いトラヒック走査を実現することが可能となる。
【００７３】
また、従来技術のようにハードウェアからなるブルームフィルタを並列に配置する構成では、所望の検査データ長を設定する方法として、対応するレジスタを制御ＣＰＵ等を用いて直接再指定するなどの対応が考えられるが、柔軟性が高い構成とは言い難い。本実施の形態によれば、ハッシュ種別やマスク、オフセット等のパラメータを走査ウィンドウ設定部１９で動的に変更することができ、極めて柔軟性の高い構成を実現することが可能となる。
【００７４】
［実施の形態の拡張］
以上、実施形態を参照して本発明を説明したが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解しうる様々な変更をすることができる。また、各実施形態については、矛盾しない範囲で任意に組み合わせて実施することができる。
【００７５】
以上、実施の形態の説明において「〜部」と記載した各機能部については、「〜手段」、「〜回路」、「〜装置」、「〜機器」であってもよく、また、「〜ステップ」、「〜処理」であってもよい。
【００７６】
また、本実施の形態で示した従来技術に比べて極めてコンパクトな回路構成による走査処理の効率性、およびプログラムによるトラヒック走査設定の柔軟性の両立を可能とするような命令セットを、特定用途向けプロセッサが具備する構成を最良の形態と見なしているものの、「〜部」と記載した各機能部は、ＲＯＭに記憶されたファームウェアおよび再構成型デバイス・素子・基板・配線などのハードウェアで実現されていても構わない。
【００７７】
また、各機能部は、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤ等の記録媒体に記憶される。プログラムはＣＰＵにより読み出されて実行される。すなわち、プログラムは、本実施の形態にかかる各機能部としてコンピュータを機能させるものである。あるいは、各機能部の手順や方法をコンピュータに実行させるものである。
【符号の説明】
【００７８】
１０…トラヒック走査装置、１１…ハッシュ演算部、１２…エントリ登録部、１３…照合データ記憶部、１４…走査パラメータ設定部、１５…パターン照合部、１６…照合結果弁別部、１７…信号入出力部、１８…信号制御部、１９…走査ウィンドウ設定部、Ｌ…信号線。
【図１】
0005952239.tif 000004
【図２】
0005952239.tif 000005
【図３】
0005952239.tif 000006
【図４】
0005952239.tif 000007
【図５】
0005952239.tif 000008
【図６】
0005952239.tif 000009
【図７】
0005952239.tif 000010
【図８】
0005952239.tif 000011
【図９】
0005952239.tif 000012