Aho-Corasick法のメッセージ構造解析処理への適用

ごとにハードウェア規模が変化してしまうため，システム設計における回路規 模の見積もり等の取り扱いが容易でなくなるためでもある．状態遷移図が固定 されるまでハードウェア構成を決められないとすると，その他のモジュールと のチップ上の相対配置や接続に関しても決められないことになり，実設計にお いては大きな問題となる．

一方，本方式は，３ファンクションテーブルの内容を変えることで，同一の ハードウェアであっても，異なるメッセージルールを処理することが可能であ る．本方式は，回路規模が小さいだけでなく，その回路規模自体を応用に依存 せずに決定することが可能であるため，実設計において他モジュールとの配置 や接続関係等を早期に決定することが可能であるというメリットをもたらす．

これにより，接続される他モジュールとの並行開発を行うような場合にも都合 が良く，システム設計の短期化にも効果がある．

一方，本研究で提案する方法は，同種のモジュールの繰り返し配置となるた め，レイアウト効率の向上と設計工数の短期化という利点がある．さらに，ハ ードウェア化する際，リソースの数変更や配分変更などにも柔軟に対応できる という利点をもたらす．これは，多様なアプリケーションに対して共通のハー ドウェアモジュールで対応できることを意味し，アプリケーションごとに構造 が異なる機器やシステムを開発しなくてもよいことを示している．予め一定量 の同種モジュールを配置しておいて，それらの利用割り当ては機器開発の遅い 段階に最終決定するといったことが可能となる．

次に，メッセージ構造解析処理に対してAho-Corasickマシンを利用する方法 は，以下のようなものである．メッセージ構造解析処理は，そもそも，構文ル ールにのったトークンのつながりを判定するものである．見方を変えれば，こ れはトークンという塊を一つの文字としてみたてた場合に，トークンという文 字列のパターンとの比較判定に他ならない．よって，先のAho-Corasickマシン を多少変形することにより，構文解析に対しても利用できるようになる．汎用 的に考えると，このような方法は結果的に複数の階層的な構文をサポートする 多階層のAho-Corasickマシン（階層型Aho-Corasickマシン）を構成すること を意味する（図３.５）．

ACM(i) ACM(N-1)

階層型Aho-Corasickマシン

ACM(0)

１階層Aho-Corasickマシン

コード比較器

入力コード パターンコード 現状態

次状態候補 出力生成器

比較ブロック

セレクタ

r r

r

r STL

r : registers 3FT : logic functions

入力 出力

ACM(i) ACM(N-1)

階層型Aho-Corasickマシン

ACM(0)

１階層Aho-Corasickマシン

コード比較器

入力コード パターンコード 現状態

次状態候補 出力生成器

比較ブロック

セレクタ

r r

r

r STL

r : registers 3FT : logic functions

入力 出力

図３．５  ハードウェア階層型Aho-Corasickマシン

３．３  性能-リソース間トレードオフと最適化 ３．３．１  性能-リソース間トレードオフ

ハードウェアを構成する際に，コード比較ブロックの数に応じて方式を分類 することが可能である．そのような分類の両極端のケースが，完全パラレル方 式と完全シリアル方式である．完全パラレル方式は，一つの状態からの遷移分 岐数の最大値の比較ブロックが用意されている場合に相当する．一方，完全シ リアル方式は，比較ブロックは一つだけ用意し，遷移分岐のそれぞれに対応し た比較は逐次的に行うものである．

実際のアプリケーションでは，コストに応じて用意できるリソース数（比較

表３．２  性能-リソース間トレードオフを考慮した３方式

完全シリアル型 完全パラレル型 シリアル・パラ レル併用型 比較

ブロック数

１

状態からの 最大分岐数

コスト制約内 での最大数 目的 リソース削減

の追求

性能の追求 コストパフォー マンスの追求

ブロックの数）が変化するため，両方式の中間的なアプローチとして，シリア ル・パラレル併用方式を取ることも必要となりうる．表３.２は，このような性 能・リソースのトレードオフを考慮して方式を分類したものである．このよう な処理方式による性能の違いについては，第3.5節において実験結果とともに考 察する．

３．３．２  マシン構造を利用した最適化

階層型Aho-Corasickマシンの構築には自由度がある．すなわち，ある状態か

ら次の状態に遷移する場合に，複数の入力に対応して遷移の枝（以下，エッジ）

が複数存在するが，これらをどのような順番で配置するかに関しての自由度が ある．

このようなエッジに関する順番（以下，エッジオーダ）が変化すると，シリ アル型を含む場合の処理性能が変化する．このことを利用して，入力の遷移条 件を調べる際に，遷移確率が高い入力ほど，その枝の優先度を高くすることに より，様々な入力パターンに対して総合的な意味での性能を向上させることが

可能となる．

また，サポートする仕様項目の取捨選択により，マシン構造が変化する．こ のようなマシン構造の変化を利用した最適化については，実験結果を踏まえて 第3.5節で再考する．

３．４  関連するハードウェア技術との比較

ハードウェアを利用するという観点からは，関連する技術が[6]に見られる．

これは，XML処理をハードウェアを使ってオフロード化し，高速化を狙うもの であるが，具体的なハードウェア構成について示すものではない．また，XML 限定の処理であり，本研究の方法のようにテーブル書き換えによって様々なプ ロトコルに対応するといったことができない．

また XML アクセラレータとして[7]がある．これは，汎用のサーバ上で動作 させるWebサーバフレームワーク（例えばIBM社のWebサーバフレームワー

クであるWebSphereなど）と組みあわせて使用するものである．内部方式など

の詳細技術を公開していないため，本技術との正確な比較は困難であるが，同 処理装置の価格が数万ドルであるといったことや，その適用対象がリソースの 非常に大きいWebサーバを対象としていることから，本技術が提供するような 非常に小さいリソースのコンピュータで動作させる高速エンジンとは相当に異 なるものであると予想される．

Aho-Corasick 法に着目したものとしては，[8-9]がある．例えば[8]は，不正 キーワードの発見を行う装置であるが，本提案方式におけるキーワード検索の みを行う機能に対応し，ハードウェア的には一階層分の機能に対応する．しか し，リソース削減に向いた特別なハードウェア構造を与えるものではない．ま た，Webサービス（特にSOAPによるエンベロープ記述等）で使われるような 複雑な構文のルールに対応するためには，階層的なルールで記述されるメッセ ージの処理が不可欠であるが，そのような処理を行うことはできない．必要と

するリソース量も相当に大きい．

[9]は，同様に，不正キーワードの発見を行うものであるが，Aho-Corasick のアルゴリズムをプログラムとして記述した上で，ネットワークプロセッサ上 で動作させるものである．専用の独自構造を持つものではなく，プログラム処 理の形で同アルゴリズムを実行するものである．一方，本提案方式で示すよう な階層的な構造を有する独自構造のハードウェアでは，複雑なルールで記述さ れるメッセージの処理を高速に行うことが可能となるだけでなく，必要とする リソース量を小さくすることも可能となる．

[10]は，やはり不正キーワードの検出を行うものであるが，プログラム処理 が行える汎用プロセッサを利用して検出を行う．ここでは，Boyer-Moore のア ルゴリズムがライブラリの形で実装されており，専用のハードウェアを作る際 にこれを利用することができる．Aho-Corasick法を用いていないため，複数キ ーワードの検出における効率が低いという問題があるが，それ以上に，独自構 造を有するハードウェア実装ではないため，本提案方式に比べると性能やコス トなどの観点で大きく劣るものと思われる．

また，過去には LISP マシンと呼ばれる記号処理のためのコンピュータが提 案され，これをハードウェア化する試みが行われた[11-13]．LISPでは，データ と演算との双方がツリー上のノードのリストとして表現されている．各ノード の値はメモリ上に配置されているが，これらを別途用意された専用のスタック に積み，これらの中から複数の値が取り出されて演算が施された後，再度スタ ックに積まれる形で処理が進行する．このような処理を行うためのハードウェ アは，メモリとスタックとの間で値の頻繁な移動を伴うことや，多くのリスト 操作を必要とすることから，その性能を高めることが困難である．本研究が提 案する方式は，LISPマシンのようなスタック操作やメモリ操作を行う必要はな く，その基本構造から異なるものである． また，LISP マシンのようにプログ ラムを記述して，その処理を行わせるといった必要もない．