2010 FastRegularExpressionMatchingUs

• (Meiners et al., 2010) ⇒ Chad R. Meiners, Jignesh Patel, Eric Norige, Eric Torng, and Alex X. Liu. (2010). “Fast Regular Expression Matching Using Small TCAMs for Network Intrusion Detection and Prevention Systems.” In: Proceedings of the 19th USENIX conference on Security. ISBN:888-7-6666-5555-4

Subject Headings: Regular Expression Matching Task

Cited By

• http://scholar.google.com/scholar?q=%222010%22+Fast+Regular+Expression+Matching+Using+Small+TCAMs+for+Network+Intrusion+Detection+and+Prevention+Systems
• http://dl.acm.org/citation.cfm?id=1929820.1929831&preflayout=flat#citedby

Quotes

Abstract

Regular expression (RE) matching is a core component of deep packet inspection in modern networking and security devices. In this paper, we propose the first hardware-based RE matching approach that uses Ternary Content Addressable Memories (TCAMs), which are off-the-shelf chips and have been widely deployed in modern networking devices for packet classification. We propose three novel techniques to reduce TCAM space and improve RE matching speed: transition sharing, table consolidation, and variable striding. We tested our techniques on 8 real-world RE sets, and our results show that small TCAMs can be used to store large DFAs and achieve potentially high RE matching throughtput. For space, we were able to store each of the corresponding 8 DFAs with as many as 25,000 states in a 0.59Mb TCAM chip where the number of TCAM bits required per DFA state were 12, 12, 12, 13, 14, 26, 28, and 42. Using a different TCAM encoding scheme that facilitates processing multiple characters per transition, we were able to achieve potential RE matching throughputs of between 10 and 19 Gbps for each of the 8 DFAs using only a single 2.36 Mb TCAM chip.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2010 FastRegularExpressionMatchingUs	Chad R. Meiners Jignesh Patel Eric Norige Eric Torng Alex X. Liu			Fast Regular Expression Matching Using Small TCAMs for Network Intrusion Detection and Prevention Systems						2010