P-ACはオートマトンを削減することでマルチストリングマッチングをハードウェアに適合させた

ネットワークセキュリティシステムは、高速なデータストリームを数千のシグネチャとリアルタイムで比較しなければならない。Aho-Corasickの魅力的な点は、その実行時間が文字列の数に依存しないことだが、その遷移テーブルは大きくなり得る。

Pao、Lin、Liuによる2010年のACM TACO論文は、有用な線形ストリーム動作を維持しながら、メモリコストに取り組んだ。パイプライン処理を組み込むことで、状態グラフは前方エッジのみを含む文字トライに削減される。

論文は、Snortから抽出した6,166文字列のシグネチャセットに対して1文字あたり約18ビット、低い制御ロジックコスト、そしてデュアルポートFPGAメモリを用いて2つのストリームを同時に処理することでスループットを2倍にできることを報告している。

オートマトンをトライにパイプライン化する

アルゴリズムのマッチングの約束を、そのオートマトンの一つの肥大化した実装から切り離す。

トライとテーブルのレイアウトは、一般的な遷移をパイプラインに適したメモリと引き換えにする。

シグネチャの増分変更は、FPGA回路を再構成することなくルックアップテーブルを更新できる。

物理的な表現を変えながら、アルゴリズムの不変条件を保つ。同じ検索ロジックは、状態機械がハードウェア向けに配置されると実用的になり得る。

P-ACは侵入検知からの優れたハードウェアの教訓である。画期的だったのは新しいマッチング規則ではなく、既知の規則を高速なパケットストリームに十分対応できるほど小さく、並列化可能で、更新可能にする表現だった。