Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
2008-04-08
2008-04-08
Ellis, Kevin L. (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C711S122000
Reexamination Certificate
active
10984244
ABSTRACT:
The present invention provides a method and apparatus for searching multiple strings within a packet data using deterministic finite automata. The apparatus includes means for updating memory tables stored in a layered memory architecture comprising a BRAM, an SRAM and a DRAM; a mechanism to strategically store the relevant data structure in the three memories based on the characteristics of data, size/capacity of the data structure, and frequency of access. The apparatus intelligently and efficiently places the associated data in different memories based on the observed fact that density of most rule-sets is around 10% for common data in typical network intrusion prevention systems. The methodology and layered memory architecture enable the apparatus implementing the present invention to achieve data processing line rates over 2 Gbps.
REFERENCES:
patent: 2003/0051043 (2003-03-01), Wyschogrod et al.
patent: 2003/0065800 (2003-04-01), Wyschogrod et al.
patent: 2003/0110208 (2003-06-01), Wyschogrod et al.
patent: 2003/0163803 (2003-08-01), Wyschogrod et al.
patent: 2003/0221013 (2003-11-01), Lockwood et al.
patent: 2004/0049596 (2004-03-01), Schuehler et al.
patent: 2004/0059443 (2004-03-01), Sharangpani
patent: 2004/0162826 (2004-08-01), Wyschogrod et al.
Aho, Alfred V. and Corasick, Margaret J., “Efficient String Matching: An Aid to Bibliographic Search”, 1975, Communications of the ACM, vol. 18, Issue 6, pp. 333-340.
Sidhu, R. and Prasanna, V.K. “Fast Regular Expression Matching using FPGAs”, 2001, IEEE Symposium of Field-Programmalbe Custom Computing Machines (FCCM).
Sidhu, R. et al., “Sring Matching on Multicontext FPGAs using Self-Reconfiguration”, 1999, ACM/SIGDA 7 Intl. Symposium on Field Programmable Gate Arrays, pp. 217-226.
Virtex-E Datasheet, “Virtex(TM)-E 1.8 V Field Programmable Gate Arrays”, Jul. 17, 2002, DS022-1 (v2.3), 6 pages.
M. Fisk and G. Varghese “Applying Fast String Matching to Intrusion Detection” [retrieved from the Internet <<URL: http://public.lanl.gov/mfisk/papers/setmatch-raid.pdf>> on Jul. 13, 2004], 21 pages.
R. Franklin, D. Carver, and B.L. Hutchings “Assisting Network Intrusion Detection with Reconfigurable Hardware,”Proceedings, FCCM 2002, 10 pages.
Z. K. Baker and V. K. Prasanna “Automatic Synthesis of Efficient Intrusion Detection Systems on FPGAs,” FPL 2004, pp. 311-321.
Z. K. Baker and V.K. Prasanna, “A Methodology for Synthesis of Efficient Intrusion Detection Systems on FPGAs”, IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM), 2004, 10 pages.
Y.H. Cho and W.H. Mangione-Smith “Deep Packet Filter with Dedicated Logic and Read Only Memories,” IEEE Symposium of Field Programmable Custom Computing Machines (FCCM), 2004, 10 pages.
S. Dharmapurikar, P. Krishnamurthy, T. Sproull, J. W. Lockwood “Deep Packet Inspection Using Parallel Bloom Filters,” IEEE Computer Society, Jan.-Feb. 2004, pp. 52-61.
N. Tuck, T. Sherwood, B. Calder, G. Varghese “Deterministic Memory-Efficient String Matching Algorithms for Intrusion Detection,”Proceedings, IEEE INFOCOM 2004, 12 pages.
A. V. Aho and M.J. Corasick “Efficient String Matching: An Aid to Bibliographic Search,” Communications of the ACM, vol. 18, Issue 6, Jun. 1975, pp. 333-340.
R. Lippmann, D. Fried, I. Graf, J. Haines, K. Kendall, D. McClung, D. Weber, S. Webster, D. Wyschogrod, R. Cunningham, M. Zissman “Evaluating Intrusion Detection Systems: The 1998 DARPA Off-line Intrusion Detection Evaluation,”Proceedings, DARPA Information Survivability Conference and Exhibition (DISCEX) 2000, IEEE Computer Society Press, Los Alamitos, CA, pp. 12-26.
E.P. Markatos, S. Antonatos, M. Polychronakis and K.G. Anagnostakis “Exclusion-based Signature Matching for Intrusion Detection,”Proceedings, IASTED International Conference on Communications and Computer Networks (CCN), Cambridge, USA, 2002, pp. 146-152.
I. Sourdis and D. Pnevmatikatos “Fast, Large-Scale String Match for a 10Gbps FPGA-based Network Intrusion Detection System,”Proceedings, 13th Intl. Conf. on Field Programmable Logic and Applications (FPL2003), Sep. 2003, Lisbon, Portugal, 10 pages.
R. Sidhu and V.K. Prasanna “Fast Regular Expression Matching using FPGAs,” IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM), Apr. 2001, 12 pages.
M. Gokhale, D. Dubois, A. Dubois, M. Boorman, S. Poole, V. Hogsett “Granidt: Towards Gigabit Rate Network Intrusion Detection Technology,”Proceedings, FPL 2002, 10 pages.
J. Moscola, J. Lockwood, R.P. Loui, M. Pachos “Implementation of a Content-Scanning Module for an Internet Firewall,”Proceedings, FCCM 2003, 8 pages.
I. Sourdis and D. Pnevmatikatos “Pre-decoded CAMs for Efficient and High-Speed NIDS Pattern Matching,”Proceedings, IEEE Symposium on Field Programmable Custom Computing Machines (FCCM), Apr. 2004, Napa, California, USA, 10 pages.
Y.H. Cho, S. Navab, W.H. Mangione-Smith “Specialized Hardware for Deep Network Packet Filtering,”M. Glesner, P. Zipf, and M. Renovell (Eds.), FPL 2002, LNCS 2438, pp. 452-461.
S. Golson “State Machine Design Techniques for Verilog and VHDL,” Synopsys Journal of High-Level Design, Sep. 1994, 11 pages.
R.P.S. Sidhu, A. Mei and V. K. Prasanna “String Matching on Multicontext FPGAs using Self-Reconfiguration,”Proceedings, 1999 ACM/SIGDA 7th Intl. Symposium on Field Programmable Gate Arrays, Feb. 1999, pp. 217-226.
Z.K. Baker, V.K. Prasanna “Time and Area Efficient Pattern Matching on FPGAs,”Proceedings, FPGA '04, Feb. 2004, Monterey, California, USA, 10 pages.
Eland Shawn
Ellis Kevin L.
IntruGuard Devices, Inc.
Lumen Patent Firm, Inc.
LandOfFree
Layered memory architecture for deterministic finite... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Layered memory architecture for deterministic finite..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Layered memory architecture for deterministic finite... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3928644