Time and area efficient pattern matching on FPGAs

ABSTRACT

Pattern matching for network security and intrusion detection demands exceptionally high performance. Much work has been done in this field, and yet there is still significant room for improvement in efficiency, flexibility, and throughput. We develop a novel linear-array string matching architecture using a buffered, two-comparator variation on the Knuth-Morris-Pratt(KMP) algorithm. For small (16 or fewer characters) patterns, it competes favorably with the state-of-the-art while providing better scalability and reconfiguration, and more efficient hardware utilization. The area efficiency compared to other approaches improves further still as the pattern size increases because only the tables increase in size.KMP is a well-known, efficient string matching technique using a single comparator and a precomputed transition table. We add a second comparator and an input buffer, allowing the system to accept at least one character in each cycle and terminate after a number of clock cycles at maximum equal to the length of the input string plus the size of the buffer. The system also provides a clean, modular route to reconfiguring the patterns on-the-fly and scaling the system to support more units, using several rows of linear array elements. In this paper, we prove the bound on the buffer size and running time, and provide performance comparisons against other approaches.

REFERENCES

• 1: Global Velocity, http://www.globalvelocity.info/, 2003.
• 2: Young H. Cho , Shiva Navab , William H. Mangione-Smith, Specialized Hardware for Deep Network Packet Filtering, Proceedings of the Reconfigurable Computing Is Going Mainstream, 12th International Conference on Field-Programmable Logic and Applications, p.452-461, September 02-04, 2002
• 3: S. Dharmapurikar, P. Krishnamurthy, T. Sproull, and J. Lockwood. Implementation of a Deep Packet Inspection Circuit using Parallel Bloom Filters in Reconfigurable Hardware. In Proceedings of HOTi03, 2003.
• 4: Maya Gokhale , Dave Dubois , Andy Dubois , Mike Boorman , Steve Poole , Vic Hogsett, Granidt: Towards Gigabit Rate Network Intrusion Detection Technology, Proceedings of the Reconfigurable Computing Is Going Mainstream, 12th International Conference on Field-Programmable Logic and Applications, p.404-413, September 02-04, 2002
• 5: B. L. Hutchings , R. Franklin , D. Carver, Assisting Network Intrusion Detection with Reconfigurable Hardware, Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.111, September 22-24, 2002
• 6: D.E. Knuth, J. Morris, and V.R. Pratt. Fast Pattern Matching in Strings. In SIAM Journal on Computing, 1977.
• 7: C. E. Leiserson and J. B. Saxe. Retiming Synchronous Circuitry. Technical Report~13, Digital Systems Research Center, 1986.
• 8: James Moscola , John Lockwood , Ronald P. Loui , Michael Pachos, Implementation of a Content-Scanning Module for an Internet Firewall, Proceedings of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.31, April 09-11, 2003
• 9: Reetinder P. S. Sidhu , Alessandro Mei , Viktor K. Prasanna, String matching on multicontext FPGAs using self-reconfiguration, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.217-226, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296463]
• 10: Reetinder Sidhu , Viktor K. Prasanna, Fast Regular Expression Matching Using FPGAs, Proceedings of the the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.227-238, April 29-May 02, 2001 [doi>10.1109/FCCM.2001.22]
• 11: Sourcefire. Snort: The Open Source Network Intrusion Detection System. http://www.snort.org, 2003.
• 12: I. Sourdis and D. Pnevmatikatos. Fast, Large-Scale String Match for a 10Gbps FPGA-Based Network Intrusion Detection System. In Proceedings of FPL2003, 2003.
• 13: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

General Terms:
Algorithms, Design, Security

Keywords:
Knuth-Morris-Pratt, network intrusion detection, string matching