Pattern matching technique for high throughput network...

Details Pattern matching technique for high throughput network... Pattern matching technique for high throughput network...

2011-08-30

2011-08-30

Fernandez Rivas, Omar F (Department: 2122)

Data processing: artificial intelligence

Miscellaneous

C706S045000, C706S016000, C706S047000, C706S048000

Reexamination Certificate

active

08010481

ABSTRACT:
A pattern matching technique for high throughput network processing includes a simple yet powerful special purpose architecture and a set of novel string matching algorithms that can work in unison. The novel set of algorithms allow for bit-level partitioning of rules such that may be more easily implemented in hardware or software. The result is a device that maintains tight worst case bounds on performance, can be updated with new rules without interrupting operation, compiles in seconds instead of hours, and is ten times more efficient than the existing best known solutions in this area.

REFERENCES:
patent: 5548775 (1996-08-01), Hershey
patent: 5784298 (1998-07-01), Hershey et al.
patent: 6968291 (2005-11-01), Desai
patent: 7301792 (2007-11-01), Gould et al.
patent: 7356663 (2008-04-01), Jain
patent: 7512531 (2009-03-01), Shia
patent: 7539681 (2009-05-01), Norton et al.
patent: 7890692 (2011-02-01), Pandya
patent: 2002/0099698 (2002-07-01), Abe et al.
patent: 2003/0233600 (2003-12-01), Hartman et al.
patent: 2004/0008701 (2004-01-01), Giacomini
patent: 2005/0273450 (2005-12-01), McMillen et al.
patent: 2006/0020595 (2006-01-01), Norton et al.
patent: 2006/0106773 (2006-05-01), Chang et al.
patent: 2007/0282835 (2007-12-01), Duxbury
patent: 2008/0101371 (2008-05-01), Law et al.
patent: 2008/0263039 (2008-10-01), Van Lunteren
Tan et al., “A High Troughput String Matching Architecture for Intrusion Detection and Prevention”, ISCA 2005, pp. 1-11.
Nishimura et al., “Speed-up of Aho-Corasick Pattern Matching Machines by Rearranging States” IEEE, 2001, pp. 175-185.
Tuck et al., “Deterministic Memory-Efficient String Matching Algorithms for Intrusion Detection”, IEEE, 2004, pp. 2628-2639.
Aldwairi et al., “Configurable String Matching Hardware for Speeding up Intrusion Detection”, ACM SIGARCH Computer Architecture News, 2005, pp. 99-107.
Aldwairi et al., “Configurable String Matching Hardware for Speeding up Intrusion Detection”, ACM 2005, pp. 99-107.
Piyachon et al., “Efficient Memory Utilization on Network Processors for Deep Packet Inspection”, ANCS 2006 pp. 71-80.
Aho, A.V. et al., “Efficient string matching: An aid to bibliographic search,” Communications of the ACM, 1975, 18(6), pp. 333-340.
Aldwairi, M. et al., “Configurable string matching hardware for speedup up intrusion detection,” In Workshop on Architectural Support for Security and Anti-virus (WASSA), held in Cooperation with ASPLOS XI, Oct. 2004.
Baker, Z.K. et al., “A methodology for synthesis of efficient intrusion detection systems on FPGAs,” In Proceedings of the Field-Programmable Custom Computing Machines, 2004, pp. 135-144.
Baker, Z.K. et al., “Time and area efficient pattern matching on FPGAs,” In Proceeding of the 2004 ACM/SIGDA 12th International Symposium on Field Programmable Gate Arrays, 2004, pp. 223-232.
Boyer, R.S. et al., “A fast string searching algorithm,” Communications of the ACM, 1977, 20(10):761-772.
Cho, Y. et al., “Deep packet filter with dedicated logic and read only memories,” In IEEE Symposium on Field-Progammable Custom Computing Machines, Apr. 2004.
Cho, Y.H. et al., “Specialized hardware for deep network packet filtering,” In 12th International Conference on Field-Programmable Logic and Applications, 2002.
Clark, C.R. et al., “Efficient reconfigurable logic circuits for matching complex network intrusion detection patterns,” In Proceedings of the 13th International Conference on Field Programmable Logic and Applications, Sep. 2003.
Crosby, S.A. et al., “Denial of service via algorithmic complexity attacks,” In Proceedings of USENIX Annual Technical Conference, Jun. 2003.
Dharmapurikar, S. et al., “Deep packet inspection using parallel bloom filters,” Micro, IEEE, 2004, 24(1), pp. 52-61.
Fisk, M. et al., “Applying fast string matching to intrusion detection,” Technical Report, in preparation, successor to UCSD TR CS2001-0670, University of California, San Diego.
Gokhale, M. et al., “Granidt: Towards gigabit rate network intrusion detection technology,” In Proceedings of the 12th International Conference on Field-Programmable Logic and Applications, 2002, pp. 404-413.
Hutchings, B.L. et al., “Assisting network intrusion detection with reconfigurable hardware,” In Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, 2002, pp. 1-10.
Mai, K. et al., “Smart memories: A modular reconfigurable architecture,” In Annual International Symposium on Computer Architecture, Jun. 2000.
Roesch, M., “Snort—lightweight intrusion detection for networks,” In Proceedings of LISA '99: 13th Systems Administration Conference, Nov. 1999, pp. 229-238.
Sourdis, I. et al., “Pre-decoded CAMs for efficient and high-speed NIDS pattern matching,” In Proceedings of the Field-Programmable Custom Computing Machines, 2004, pp. 258-267.
Srinivasan, V. et al., “Fast address lookups using controlled prefix expansion,” ACM Transactions on Computer Systems, Feb. 1999, 7(1):1-40.
Swanson, S. et al., “Wavescalar,” In 36th International Symposium on Microarchitecture, Dec. 2003.
Taylor, M.B. et al., “Evaluation of the Raw microprocessor: An exposed-wire-delay architecture for ILP and streams,” In Annual International Symposium on Computer Architecture, Jun. 2004.
Tuck, N. et al., “Deterministic memory-efficient string matching algorithms for intrusion detection,” In the 23rd Conference of the IEEE Communications Society (Infocomm), Mar. 2004.

Affiliated with

Also associated with

Rating

Pattern matching technique for high throughput network... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Pattern matching technique for high throughput network..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pattern matching technique for high throughput network... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2651619