公开(公告)号：US07962434B2

公开(公告)日：2011-06-14

申请号：US12032380

申请日：2008-02-15

申请人： Cristian Estan ,  Randy David Smith ,  Somesh Jha

发明人： Cristian Estan ,  Randy David Smith ,  Somesh Jha

IPC分类号： G06F17/00

CPC分类号： H04L63/1416 ,  H04L69/22

摘要： Deterministic finite automata (DFAs) are popular solutions to deep packet inspection because they are fast and DFAs corresponding to multiple signatures are combinable into a single DFA. Combining such DFAs causes an explosive increase in memory usage. Extended finite automata (XFAs) are an alternative to DFAs that avoids state-space explosion problems. XFAs extend DFAs with a few bytes of “scratch memory” used to store bits and other data structures that record progress. Simple programs associated with automaton states and/or transitions manipulate this scratch memory. XFAs are deterministic in their operation, are equivalent to DFAs in expressiveness, and require no custom hardware support. Fully functional prototype XFA implementations show that, for most signature sets, XFAs are at least 10,000 times smaller than the DFA matching all signatures. XFAs are 10 times smaller and 5 times faster or 5 times smaller and 20 times faster than systems using multiple DFAs.

摘要翻译： 确定性有限自动机（DFA）是深度分组检测的流行解决方案，因为它们是快速的，并且与多个签名相对应的DFA可以组合成单个DFA。 结合这样的DFA导致内存使用的爆炸性增加。 扩展有限自动机（XFAs）是避免状态空间爆炸问题的替代方案。 XFAs使用几个字节的“暂存内存”来扩展DFA，用于存储记录进度的位和其他数据结构。 与自动机状态和/或转换相关联的简单程序操纵该暂存存储器。 XFAs在运营中是确定性的，相当于表现力的DFA，并且不需要定制硬件支持。 全功能原型XFA实现表明，对于大多数签名集，XFA至少比匹配所有签名的DFA小10,000倍。 XFA比使用多个DFA的系统小10倍，5倍，5倍，20倍。