近年、インターネットは急速に普及し、生活にとって不可欠なインフラストラクチャの一つとなりつつある。それに伴い、ネットワーク経由の攻撃や情報漏洩等の被害が与える影響は増大しており、これらのセキュリティ脅威を阻止する事の重要性が増している。NIDSはネットワークを流れるデータを検査し、これらのセキュリティ脅威を検知するシステムであり、ネットワークの安全性を守る有効な方法の一つである。実際、攻撃者は対象サイトにNIDSが存在するか否かを調べ、存在する場合は攻撃の対象から外す傾向があるというデータが公開されている。

　NIDSでは、攻撃を確実に発見できる事が重要である。なぜなら、一部の条件下で攻撃が発見できない場合、攻撃者は意図的にその条件を作り出し、NIDSをすり抜けるからである。最低でも、攻撃を発見できない条件を攻撃者が意図的に成立させる事が可能であってはならない。

　収集したネットワークデータの検査方法は、シグネチャ方式とアノーマリ方式に大きく分けられる。シグネチャ方式では、セキュリティ脅威に関わるパケットを、その中に含まれる特定のオクテットパターンを探索する事により発見する。一方、アノーマリ方式では、ネットワークの異常な振る舞いから間接的にセキュリティ脅威を検出する。シグネチャ方式は登録外の攻撃は発見できないが、登録された攻撃は確実に発見可能である。一方、アノーマリ方式は未知の攻撃を発見可能であるが、現状では一部の攻撃は見逃される。前述のようにNIDSでは攻撃を確実に発見できる事が重要である。そのため、snort等の多くの実用NIDSは、シグネチャ方式を単体もしくは他方式との組み合わせで使用している。そのような背景から、本論文ではシグネチャ方式について議論を行う。

　シグネチャ方式では、攻撃を確実に発見するために各パケットではなくTCPストリームのレベルでパターン探索を行う事が重要である。なぜなら、パケット毎に検査を行う場合、パケット分割の手法によりNIDSをすり抜けることが可能になるからである。同時に、NIDSを各ホストではなく、バックボーンネットワークに配置して検査を行う事が求められる。なぜなら、特に大学や大企業等の大規模ネットワークにおいては全てのホストにNIDSを導入・管理する事は実用上困難であるが、バックボーンでの一括管理方式であれば導入・管理を行う事が容易なためである。そのため、パターン探索機構には近年の10Gbpsに達するバックボーンネットワークに対応するスループットが必要である。

　10GbpsでTCPレベルのパターン検査を行う場合、速度の点からソフトウェアではなくハードウェア方式が必要である。しかし、TCPレベルでの検査を行うには(1)TCP毎の照合状態を切り替えるオーバーヘッドを抑え、かつ(2)大部分のパケットはバッファリング無しでパケット落ちと順序交換に対応できる事、が求められる。(2)は、バックボーンネットワークでは多数のTCPストリームを対象に検査を行う必要があり、全てのパケットをバッファリングする事は性能上困難なためである。また、パケットをバッファリングしないため、パケットを到着順に処理する必要があり、ストリーム間の状態切り替えを高速で行う必要があり(1)必要となる。

　本研究では、(1)と(2)の両方を達成可能なFPGAベースのパターン照合方式を提案する。FPGAを用いる理由は、再構成によりルールを変更可能にしつつソフトウェアよりも高いスループットを実現するためである。(1)を満たす照合方式としてSuffix Based Traversing (SBT)法を、(2)に対応する方式としてパケットシグネチャ付き双方向検査方式を提案する。

　SBT法はAho-Corasickアルゴリズム法の拡張である。状態ビット数が従来方式と比較して少なく、結果として軽量のストリーム切り替えが可能である。また、SBT法では複数文字を並列に処理できるため、高いスループットを達成可能である。我々は、与えられたルールからSBT文字列照合機構のVHDL記述を自動的に生成する変換器を実装した。また、出力されたSBT照合機構の評価を行った。Xilinx XC2V6000-6 FPGAを用いた場合、1000文字のルールに対して32Gbps、2000文字のルールに対して14Gbpsを達成した。ステートのビット数は典型的な場合20ビット、最大24ビットであった。その結果、オーバーヘッドクロック無しでのストリーム切り替えを実現した。

　双方向検査方式は、正順SBT機構と逆順SBT機構という2つのSBT機構をパケット検査に用いる。正順SBT機構は元のルール文字列を検出し、逆順SBT機構はルール文字列を反転させたものを検出する。この2つを組み合わせる事により、高々パケットにまたがるパターンはバッファリング無しで発見可能である。そのため、パケットが最長のルール文字列よりも長い限場合はバッファリング不要であり、結果としてバッファリング量を削減できる。また、一回目の送信と異なる内容のパケットを再送して正常な検査を妨げるという攻撃を防ぐためにパケットシグネチャというハッシュを用いる。

　SBT法と双方向検査、パケットシグネチャを組み合わせた方式でTCPストリームレベルでのパターンマッチ機構をXilinx XC2VP70-5 FPGAを用いたNIC向けに製作した。1000文字のルールを使用し、バッファリングが行われない場合について評価を行った。動作クロック速度から計算した結果、順序交換が無い場合で13.1Gbps、パケット落ち、順序交換がある場合で11.2Gbpsを実現できる事が分かった。

インターネットにおける侵入検知システム(Intrusion Detection System, IDS)ではパケットのペイロード解析を必要とする。ペイロード解析法の一つである厳密文字列照合をTCPストリームに対して行う場合、パケット毎の照合と異なり (1)ストリーム毎の照合途中経過の保存、(2)パケット落ちへの対応、(3)一貫性の無い再送への対応、の3つの処理が必要である。本論文ではこれらの処理をFPGAハードウェアで実現するための新しい手法を提案し評価した。

　限られたハードウェア資源下では、ストリーム毎の照合途中経過の保存状態数を少なくする必要がある。このために照合ステートビット数を減らすための文字列照合法として、本論文では、Suffix Based Traversing(SBT)法を提案した。本方式は複数文字並列処理による高速化が可能で、なおかつステートビット数がO(logルール文字列合計長)で抑えられる初めての方式である。合計文字数1000のルールに対してステートビット数が既存方式であるDFA(Deterministic Finite Automaton)法の1/15に抑えられることを示した。ユーザが定義するルール文字列から自動生成器により回路が自動生成される。ユーザは、ルール文字列を記述するだけで本システムを利用することが可能となる。このように単なる手法の提案にとどまらず実用的なシステムを実現した。

　本論文では、さらに、パケット落ちに対応する方式として双方向検査法を提案した。本検査法の特徴は、パケット間にまたがるパターンをパケット到着順に依らず文字列照合を可能としていることである。このために、本手法では、文字列照合のためのオクテット列走査をシーケンス番号の昇順に対し順方向だけではなく逆方向にも行う。

　一貫性の無い再送パケットへの対応方式としてパケットフィンガープリントを提案した。再送パケットに一貫性があるかを厳密にチェックのためには、最初に送信されたパケットデータを全て保存しておく必要があるためメモリ使用量が増大する。パケットフィンガープリント方式では情報理論的に最も精度が高い方式であるハッシュ値を用いた近似検査を行う。

　SBT法の実装では、Xilinx社のXC2V6000FPGA(6Mゲート、RAM324KB)において32オクテットの並列処理を実現し、32Gbpsの照合スループットを達成した。また、本論文で提案している3つの方式をXilinx社のXC2VP50(5Mゲート、RAM 522KB) FPGAを用いて評価した。ルールの合計サイズは約1000、パケットフィンガープリントのハッシュ値を64ビットとし、最大13.1Gbps、最小11.2Gbpsのパケット処理速度を達成できることを実証した。

　本研究では、現在および将来の高速ネットワークに対するTCPレベル文字列照合器を実用的なメモリ量で実装可能にし、かつ、再送一貫性の検査を可能にした。SBT法は既存方式では不可能だった複数文字の並列処理とステートビット数抑制を両立した。双方向検査法はパケット落ちに対処する際に必要なパケットバッファリング量を抑制した。パケットフィンガープリントはハードウェア方式で初めて一貫性の無い再送へ対処し、同時に使用メモリ量を抑えた。このようにインターネットワークにおいて重要性が高まっている侵入検知システムにおいて、その実現における最も重要な要素技術である文字列照合器のハードウェア化に対して、実現課題を体系的にまとめ、かつ、新しい実現手法を提案し評価しており、当該分野に顕著なる貢献を行った。よって本論文は博士（情報理工学）の学位請求論文として合格と認められる。