P-AC通过精简自动机使多字符串匹配适配硬件

网络安全系统必须实时地将快速数据流与数千个签名进行比对。Aho-Corasick吸引人的地方在于其运行时间与字符串数量无关，但其转换表可能很大。

Pao、Lin和Liu在2010年ACM TACO论文中保留了有用的线性流行为，同时着力解决内存开销问题。通过引入流水线处理，状态图被简化为仅包含前向边的字符trie。

论文报告称，对于从Snort提取的6,166条字符串签名集，每字符约需18比特，控制逻辑开销低，并且通过同时处理两条流，利用双端口FPGA存储器可将吞吐量翻倍。

将自动机流水线化为trie

它将算法的匹配承诺与其自动机的一种笨重实现分离开来。

trie加表的布局用流水线友好的存储器换取了通用转换。

增量式签名变更可以更新查找表，而无需重新配置FPGA电路。

在改变物理表示的同时保留算法不变量。当状态机针对硬件进行布局时，相同的搜索逻辑可以变得实用。

P-AC是来自入侵检测的一个很好的硬件教训：突破不在于新的匹配规则，而在于一种表示方式，使已知规则足够小、可并行且可更新，从而适用于快速数据包流。