article

Deterministic high-speed root-hashing automaton matching coprocessor for embedded network processor

Authors:

Tsern-Huei Lee,

Yuan-Cheng LaiAuthors Info & Claims

ACM SIGARCH Computer Architecture News, Volume 35, Issue 3

Pages 36 - 43

https://doi.org/10.1145/1294313.1294314

Published: 01 June 2007 Publication History

Abstract

While string matching plays an important role in deep packet inspection applications, its software algorithms are insufficient to meet the demands of high-speed performance. Accordingly, we were motivated to propose fast and deterministic performance root-hashing automaton matching (RHAM) coprocessor for embedded network processor. Although automaton algorithms are robust with deterministic matching time, there is still plenty of room for improvement of their average-case performance. The proposed RHAM employs novel root-hashing technique to accelerate automaton matching. In our experiment, RHAM is implemented in a prevalent automaton algorithm, Aho-Corasick (AC) which is often used in many packet inspection applications. Compared to the original AC, RHAM only requires extra vector size in 48 Kbytes for root-hashing, and has about 900% and 420% outperformance for 20,000 URLs and 10,000 virus patterns respectively. Implementaion of RHAM FPGA can perform at the rate of 12.6 Gbps with the pattern amount in 34,215 bytes. This is superior to all previous matching hardware in terms of throughput and pattern set.

References

[1]

F. Mike and V. George, "Fast Content-Based. Packet Handling for Intrusion Detection," UCSD. Technical Report CS2001-0670, May 2001.

Digital Library

[2]

S. Antonatos, K. Anagnostakis and E. Markatos, Generating Realistic Workloads for Network Intrusion Detection Systems. ACM WOSP, 2004.

Digital Library

[3]

M. Roesch et al, "Snort: The Open Source Network Intrusion Detection System," http://www.snort.org/.

[4]

T. Kojm et al, "Clam Anti-virus," http://www.clamav.net/.

[5]

J. Mason et al, The Apache SpamAssassin Project. http://spamassassin.apache.org/.

[6]

T. D. Internordia et al, "SquidGuard filter," http://www.squidguard.org/.

[7]

D. Barron et al, "DansGuardian content filter," http://dansguardian.org/.

[8]

G. Navarro and M. Ranot, "Flexible Pattern Matching in Strings," Cambridge University Press, 2002.

Digital Library

[9]

G. Navarro, "A Guided Tour to Approximate String Matching," ACM Computing Surveys, 33(1):31--88. 2001.

Digital Library

[10]

S. Wu and U. Manber, "Fast Text Searching Allowing Errors," Communication of the ACM, 35:83--91.

Digital Library

[11]

R. S. Boyer and J. S. Moore, "A Fast String Searching Algorithm," Communications of the ACM, 20, 10, 762--772.

Digital Library

[12]

A. V. Aho and M. J. Corasick, "Efficient String Matching: An Aid to Bibliographic Search," Communications of the ACM, pp. 333--340.

Digital Library

[13]

N. Tuck, T. Sherwood, B. Calder and G. Varghese, "Deterministic memory-efficient string matching algorithms for intrusion detection," IEEE Infocom, Hong Kong, China, 2004.

[14]

C. Coit, S. Staniford and J. Mcalerney, "Towards Faster String Matching for Intrusion Detection," DARPA Information Survivability Conference and Exhibition, pp. 367--373, 2002.

[15]

N. Desai, "Increasing performance in high speed NIDS," http://www.snort.org/.

[16]

M. Raffinot, "On the Multi Backward Dawg Matching Algorithm (MultiBDM)," Workshop on String Processing, Carleton U. Press, 1997.

[17]

L. Tan and T. Sherwood, "A High Throughput String Matching Architecture for Intrusion Detection And Prevention," ISCA, 2005.

Digital Library

[18]

S. Dharmapurikar and P. Krishnamurthy, T. S. Sproull and J. W. Lockwood, "Deep Packet Inspection Using Parallel Bloom Filters," IEEE Micro, Vol. 24, No. 1, Jan. 2004.

Digital Library

[19]

I. Sourdis, D. Pnevmatikatos, S. Wong, and S. Vassiliadis, "A reconfigurable perfect-hashing scheme for packet inspection," International Conference on Field Programmable Logic and Applications, Aug. 2005.

[20]

M. Aldwairi, T. Conte and P. Franzon, "Configurable String Matching Hardware for Speeding up Intrusion Detection," ACM CAN, 2005.

Digital Library

[21]

J. Lockwood, "An Open Platform for Development of Network Processing Modules in Reconfigurable Hardware," IEC DesignCon, Santa Clara, CA, Jan. 2001.

[22]

J. Moscola, J. Lockwood, R. P. Loui and M. Pachos, "Implementation of a Content-Scanning Module for an Internet Firewall," IEEE FCCM, 2003.

Digital Library

[23]

Z. K. Baker and V. K. Prasanna, "Time And Area Efficient Pattern Matching on FPGAs," ACM/SIGDA FPGA, California, USA, Feb 2004.

Digital Library

[24]

G. Tripp, "A Finite-State-Machine Based String Matching System for Intrusion Detection on High-Speed Network.," EICAR, May 2005.

[25]

L. Bu and J. A. Chandy, "A Keyword Match Processor Architecture Using Content Addressable Memory," ACM VLSI, April 26--28, 2004.

Digital Library

[26]

R. Sidhu and V. Prasanna, "Fast Regular Expression Matching using FPGAs," IEEE FCCM, April 2001.

Digital Library

[27]

R. Franklin, D. Carver and B. L. Hutchings, "Assisting Network Intrusion Detection with Reconfigurable Hardware," IEEE FCCM, Napa, CA, Apr 2002.

Digital Library

[28]

C. R. Clark and D. E. Schimmel, "Scalable Pattern Matching for High Speed Networks," IEEE FCCM, 2004.

Digital Library

[29]

Y. H. Cho and W. H. Mangione, "A Pattern Matching Coprocessor for Network Security," ACM/IEEE DAC, California, USA, Jun 2005.

Digital Library

[30]

I. Sourdis and D. Pnevmatikatos, "Pre-Decoded CAMs for Efficient and High-Speed NIDS Pattern Matching," IEEE FCCM, 2004.

Digital Library

[31]

M. Gokhale, D. Dubois, A. Dubois, M. Boorman, S. Poole and V. Hogsett, "Granidt: Towards Gigabit Rate Network Intrusion Detection Technology," LNCS, Volume 2438, Jan 2002.

Digital Library

[32]

H. M. Blüthgen, T. Noll and R. Aachen, "A Programmable Processor For Approximate String Matching With High Throughput Rate," IEEE ASAP, 2000.

[33]

J. H. Park and K. M. George, "Parallel String Matching Algorithms based on Dataflow," HICSS, Hawaii, 1999.

Digital Library

Cited By

Huang NLee TTseng K(2013)Solution of skip distance constraint on sub-linear time string-matching architecture2013 IEEE International Conference of IEEE Region 10 (TENCON 2013)10.1109/TENCON.2013.6718990(1-4)Online publication date: Oct-2013
https://doi.org/10.1109/TENCON.2013.6718990
Lin Y(2013)Research Roadmap Driven by Network Benchmarking Lab (NBL)Proceedings of the 2013 First International Symposium on Computing and Networking10.1109/CANDAR.2013.7(1-7)Online publication date: 4-Dec-2013
https://dl.acm.org/doi/10.1109/CANDAR.2013.7
Bande Serrano JPalancar J(2012)String alignment pre-detection using unique subsequences for FPGA-based network intrusion detectionComputer Communications10.1016/j.comcom.2011.12.00935:6(720-728)Online publication date: 1-Mar-2012
https://dl.acm.org/doi/10.1016/j.comcom.2011.12.009
Show More Cited By

Index Terms

Deterministic high-speed root-hashing automaton matching coprocessor for embedded network processor

Recommendations

Scalable Automaton Matching for High-Speed Deep Content Inspection
AINAW '07: Proceedings of the 21st International Conference on Advanced Information Networking and Applications Workshops - Volume 01

String matching plays a central role in content inspection applications such as intrusion detection, anti-virus, anti-spam and Web filtering. Because they are computation and memory intensive, software matching algorithms are insufficient in meeting the ...
A high-speed and large-scale dictionary matching engine for Information Extraction systems
ASAP '13: Proceedings of the 2013 IEEE 24th International Conference on Application-specific Systems, Architectures and Processors (ASAP)

Dictionary matching is a commonly used operation in Information Extraction (IE) systems. It involves matching a set of strings in a document against a dictionary of pre-defined patterns. In this paper, we describe a high performance and scalable ...
A CNN accelerator on embedded FPGA using dynamic reconfigurable coprocessor
AIIPCC '19: Proceedings of the International Conference on Artificial Intelligence, Information Processing and Cloud Computing

Convolutional neural network (CNN) has been widely deployed in deep learning networks at present. However, numerous convolution operations are computing intensive and often require powerful accelerator such as FPGA. The existed accelerators usually as ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGARCH Computer Architecture News

ACM SIGARCH Computer Architecture News Volume 35, Issue 3

Special issue on the 2006 reconfigurable and adaptive architecture workshop

June 2007

55 pages

ISSN:0163-5964

DOI:10.1145/1294313

Issue’s Table of Contents

Copyright © 2007 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2007

Published in SIGARCH Volume 35, Issue 3

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
240
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Huang NLee TTseng K(2013)Solution of skip distance constraint on sub-linear time string-matching architecture2013 IEEE International Conference of IEEE Region 10 (TENCON 2013)10.1109/TENCON.2013.6718990(1-4)Online publication date: Oct-2013
https://doi.org/10.1109/TENCON.2013.6718990
Lin Y(2013)Research Roadmap Driven by Network Benchmarking Lab (NBL)Proceedings of the 2013 First International Symposium on Computing and Networking10.1109/CANDAR.2013.7(1-7)Online publication date: 4-Dec-2013
https://dl.acm.org/doi/10.1109/CANDAR.2013.7
Bande Serrano JPalancar J(2012)String alignment pre-detection using unique subsequences for FPGA-based network intrusion detectionComputer Communications10.1016/j.comcom.2011.12.00935:6(720-728)Online publication date: 1-Mar-2012
https://dl.acm.org/doi/10.1016/j.comcom.2011.12.009
Hu YGao QGuo LWang P(2011)Giant complete automaton for uncertain multiple string matching and its high speed construction algorithmScience China Information Sciences10.1007/s11432-011-4363-z54:8(1562-1571)Online publication date: 27-Jul-2011
https://doi.org/10.1007/s11432-011-4363-z
Rejeb JSrinivasan M(2008)Extension of Aho-Corasick Algorithm to Detect Injection AttacksAdvances in Computer and Information Sciences and Engineering10.1007/978-1-4020-8741-7_37(207-212)Online publication date: 2008
https://doi.org/10.1007/978-1-4020-8741-7_37

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents