Data processing: artificial intelligence – Knowledge processing system – Knowledge representation and reasoning technique
Reexamination Certificate
2011-06-14
2011-06-14
Vincent, David R (Department: 2129)
Data processing: artificial intelligence
Knowledge processing system
Knowledge representation and reasoning technique
Reexamination Certificate
active
07962434
ABSTRACT:
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.
REFERENCES:
patent: 7685254 (2010-03-01), Pandya
patent: 2006/0136570 (2006-06-01), Pandya
patent: 2007/0038798 (2007-02-01), Bouchard et al.
Kumar, et al., Algorithms to Accelerate Multiple Regular Expressions Matching for Deep Packet Inspection, ACM, 2006SIGCOMM'06, Sep. 11-15, 2006, pp. 339-350.
Alfred V. Aho et. al., “Efficient string matching: An aid to bibliographic search”, Communications of the ACM, Jun. 1975.
Fang Yu, et al., “Fast and memory-efficient regular expression matching for deep packet inspection”, Technical Report EECS-2005-8, U.C. Berkeley, 2005.
Michael Spergberg-McQueen, “Notes on finite state automata with counter”, www.w3.org/XML/2004/05/msm-cfa.html, (available at least as early as May 2004).
M. Roesch, “Snort—lightweight intrusion detection for networks”, Proceedings of the 13th Systems Administration Conference, USENIX, 1999.
“Programming techniques: Regular expression search algorithm”, K. Thompson, Commun.ACM, 11(6):419-422, 1968.
M. Fisk et al., “Fast Content-Based Packet Handling for Intrusion Detection”, TR CS 2001-0670, UC San Diego, May 2001.
H. Sengar et al., “VoIP Intrusion Detection Through Interacting Protocol State Machines”, DSN, Jun. 2006.
Fang Yu et al., “Gigabit Rate Packet Pattern-Matching Using Tcam”, ICNP, Oct. 2004.
Estan Cristian
Jha Somesh
Smith Randy David
Boyle Fredrickson , S.C.
Vincent David R
Wisconsin Alumni Research Foundation
LandOfFree
Extended finite state automata and systems and methods for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Extended finite state automata and systems and methods for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extended finite state automata and systems and methods for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2665154