Methods and systems for multi-pattern searching

Details Methods and systems for multi-pattern searching Methods and systems for multi-pattern searching

2011-08-09

2011-08-09

Mofiz, Apu M (Department: 2161)

Data processing: database and file management or data structures

Database and file access

Record, file, and data search and comparisons

C707S758000, C707S803000

Reexamination Certificate

active

07996424

ABSTRACT:
Embodiments of the present invention relate to systems and methods for optimizing and reducing the memory requirements of state machine algorithms in pattern matching applications. Memory requirements of an Aho-Corasick algorithm are reduced in an intrusion detection system by representing the state table as three separate data structures. Memory requirements of an Aho-Corasick algorithm are also reduced by applying a banded-row sparse matrix technique to the state transition table of the state table. The pattern matching performance of the intrusion detection system is improved by performing a case insensitive search, where the characters of the test sequence are converted to uppercase as the characters are read. Testing reveals that state transition tables with sixteen bit elements outperform state transition tables with thirty-two bit elements and do not reduce the functionality of intrusion detection system using the Aho-Corasick algorithm.

REFERENCES:
patent: 4550436 (1985-10-01), Freeman
patent: 4570157 (1986-02-01), Kodaira
patent: 4857912 (1989-08-01), Everett et al.
patent: 4912748 (1990-03-01), Horii et al.
patent: 4985863 (1991-01-01), Fujisawa et al.
patent: 5193192 (1993-03-01), Seberger
patent: 5222081 (1993-06-01), Lewis et al.
patent: 5404488 (1995-04-01), Kerrigan et al.
patent: 5430842 (1995-07-01), Thompson et al.
patent: 5459841 (1995-10-01), Flora-Holmquist et al.
patent: 5495409 (1996-02-01), Kanno
patent: 5497463 (1996-03-01), Stein et al.
patent: 5604910 (1997-02-01), Kojima et al.
patent: 5666293 (1997-09-01), Metz et al.
patent: 5796942 (1998-08-01), Esbensen
patent: 5870554 (1999-02-01), Grossman et al.
patent: 5901307 (1999-05-01), Potter et al.
patent: 5917821 (1999-06-01), Gobuyan et al.
patent: 5919257 (1999-07-01), Trostle
patent: 5963942 (1999-10-01), Igata
patent: 5987473 (1999-11-01), Jorgensen
patent: 5995963 (1999-11-01), Nanba et al.
patent: 5999937 (1999-12-01), Ellard
patent: 6002427 (1999-12-01), Kipust
patent: 6141686 (2000-10-01), Jackowski et al.
patent: 6199181 (2001-03-01), Rechef et al.
patent: 6219786 (2001-04-01), Cunningham et al.
patent: 6320848 (2001-11-01), Edwards et al.
patent: 6321338 (2001-11-01), Porras et al.
patent: 6324656 (2001-11-01), Gleichauf et al.
patent: 6334121 (2001-12-01), Primeaux et al.
patent: 6343362 (2002-01-01), Ptacek et al.
patent: 6393474 (2002-05-01), Eichert et al.
patent: 6415321 (2002-07-01), Gleichauf et al.
patent: 6477648 (2002-11-01), Schell et al.
patent: 6487666 (2002-11-01), Shanklin et al.
patent: 6499107 (2002-12-01), Gleichauf et al.
patent: 6539381 (2003-03-01), Prasad et al.
patent: 6546493 (2003-04-01), Magdych et al.
patent: 6587876 (2003-07-01), Mahon et al.
patent: 6590885 (2003-07-01), Jorgensen
patent: 6678734 (2004-01-01), Haatainen et al.
patent: 6678824 (2004-01-01), Cannon et al.
patent: 6684332 (2004-01-01), Douglas
patent: 6711127 (2004-03-01), Gorman et al.
patent: 6754826 (2004-06-01), Challenger et al.
patent: 6766320 (2004-07-01), Wang et al.
patent: 6772196 (2004-08-01), Kirsch et al.
patent: 6789202 (2004-09-01), Ko et al.
patent: 6851061 (2005-02-01), Holland et al.
patent: 6957348 (2005-10-01), Flowers et al.
patent: 6983323 (2006-01-01), Cantrell et al.
patent: 6993706 (2006-01-01), Cook
patent: 6999998 (2006-02-01), Russell
patent: 7032114 (2006-04-01), Moran
patent: 7054930 (2006-05-01), Cheriton
patent: 7058821 (2006-06-01), Parekh et al.
patent: 7065657 (2006-06-01), Moran
patent: 7073198 (2006-07-01), Flowers et al.
patent: 7076803 (2006-07-01), Bruton et al.
patent: 7096503 (2006-08-01), Magdych et al.
patent: 7113789 (2006-09-01), Boehmke
patent: 7133916 (2006-11-01), Schunemann
patent: 7134141 (2006-11-01), Crosbie et al.
patent: 7152105 (2006-12-01), McClure et al.
patent: 7174566 (2007-02-01), Yadav
patent: 7181769 (2007-02-01), Keanini et al.
patent: 7257630 (2007-08-01), Cole et al.
patent: 7305708 (2007-12-01), Norton et al.
patent: 7310688 (2007-12-01), Chin
patent: 7313695 (2007-12-01), Norton et al.
patent: 7315801 (2008-01-01), Dowd et al.
patent: 7317693 (2008-01-01), Roesch et al.
patent: 7346922 (2008-03-01), Miliefsky
patent: 7350077 (2008-03-01), Meier et al.
patent: 7363656 (2008-04-01), Weber et al.
patent: 7596807 (2009-09-01), Ptacek et al.
patent: 7644275 (2010-01-01), Mowers et al.
patent: 2001/0027485 (2001-10-01), Ogishi et al.
patent: 2001/0034847 (2001-10-01), Gaul, Jr.
patent: 2002/0035639 (2002-03-01), Xu
patent: 2002/0066034 (2002-05-01), Schlossberg et al.
patent: 2002/0083344 (2002-06-01), Vairavan
patent: 2002/0087716 (2002-07-01), Mustafa
patent: 2002/0112185 (2002-08-01), Hodges
patent: 2002/0123995 (2002-09-01), Shibuya
patent: 2002/0165707 (2002-11-01), Call
patent: 2003/0009699 (2003-01-01), Gupta et al.
patent: 2003/0014662 (2003-01-01), Gupta et al.
patent: 2003/0046388 (2003-03-01), Milliken
patent: 2003/0065817 (2003-04-01), Benchetrit et al.
patent: 2003/0083847 (2003-05-01), Schertz et al.
patent: 2003/0093517 (2003-05-01), Tarquini
patent: 2003/0101353 (2003-05-01), Tarquini et al.
patent: 2003/0140250 (2003-07-01), Taninaka et al.
patent: 2003/0195874 (2003-10-01), Akaboshi
patent: 2003/0212910 (2003-11-01), Rowland et al.
patent: 2003/0217283 (2003-11-01), Hrastar et al.
patent: 2003/0229726 (2003-12-01), Daseke et al.
patent: 2004/0010684 (2004-01-01), Douglas
patent: 2004/0015728 (2004-01-01), Cole et al.
patent: 2004/0034773 (2004-02-01), Balabine et al.
patent: 2004/0064726 (2004-04-01), Girouard
patent: 2004/0073800 (2004-04-01), Shah et al.
patent: 2004/0093582 (2004-05-01), Segura
patent: 2004/0098618 (2004-05-01), Kim et al.
patent: 2004/0123153 (2004-06-01), Wright et al.
patent: 2004/0172234 (2004-09-01), Dapp et al.
patent: 2004/0179477 (2004-09-01), Lincoln et al.
patent: 2004/0193943 (2004-09-01), Angelino et al.
patent: 2004/0210756 (2004-10-01), Mowers et al.
patent: 2004/0218532 (2004-11-01), Khirman
patent: 2004/0221176 (2004-11-01), Cole
patent: 2004/0250032 (2004-12-01), Ji et al.
patent: 2004/0268358 (2004-12-01), Darling et al.
patent: 2005/0005169 (2005-01-01), Kelekar
patent: 2005/0044422 (2005-02-01), Cantrell et al.
patent: 2005/0076066 (2005-04-01), Stakutis et al.
patent: 2005/0108393 (2005-05-01), Banerjee et al.
patent: 2005/0113941 (2005-05-01), Ii et al.
patent: 2005/0114700 (2005-05-01), Barrie et al.
patent: 2005/0160095 (2005-07-01), Dick et al.
patent: 2005/0172019 (2005-08-01), Williamson et al.
patent: 2005/0188079 (2005-08-01), Motsinger et al.
patent: 2005/0229255 (2005-10-01), Gula et al.
patent: 2005/0240604 (2005-10-01), Corl, Jr. et al.
patent: 2005/0251500 (2005-11-01), Vahalia et al.
patent: 2005/0268331 (2005-12-01), Le et al.
patent: 2005/0268332 (2005-12-01), Le et al.
patent: 2005/0273673 (2005-12-01), Gassoway
patent: 2005/0273857 (2005-12-01), Freund
patent: 2006/0174337 (2006-08-01), Bernoth
patent: 2006/0265748 (2006-11-01), Potok
patent: 2006/0294588 (2006-12-01), Lahann et al.
patent: 2007/0027913 (2007-02-01), Jensen et al.
patent: 2007/0192863 (2007-08-01), Kapoor et al.
patent: 2007/0195797 (2007-08-01), Patel et al.
patent: 2007/0288579 (2007-12-01), Schunemann
patent: 2008/0168561 (2008-07-01), Durie et al.
patent: 2009/0028147 (2009-01-01), Russell
patent: 2009/0041020 (2009-02-01), Gibbons et al.
“Efficient String Matching: An Aid to Bibliographic Search”, By: Aho & Corasick; Published 1975 http://delivery.acm.org/10.1145/370000/360855/p333-aho.pdf?key1=360855&key2=6208390031&coll=DL&dl=ACM&ip=151.207.242.4&CFID=14947222&CFTOKEN=99671516.
M. Norton, “Multi-Pattern Search Engine” source code, released Mar. 2003 (11 pages total).
Office Action issued by the U.S. Patent Office on Oct. 6, 2008 in connection with related U.S. Appl. No. 10/843,374.
Notice of Allowance issued by the U.S. Patent Office on Oct. 15, 2008 in connection with related U.S. Appl. No. 10/951,796.
Notice of Allowance issued by the U.S. Patent Office on Oct. 21, 2008 in connection with related U.S. Appl. No. 10/843,375.
European Office Action issued by the European Patent Office on Nov. 28, 2008 in connection with Europea

Affiliated with

Also associated with

Rating

Methods and systems for multi-pattern searching does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Methods and systems for multi-pattern searching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and systems for multi-pattern searching will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2723417