Scalable automaton matching for high-speed deep content inspection

Ying-Dar Lin*, Kuo Kun Tseng, Chen Chou Hung, Yuan Cheng Lai

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 high-speed performance. Thus, offloading packet content inspection to dedicated hardware seems inevitable. This paper presents a scalable automaton matching (SAM) design, which uses Aho-Corasick (AC) algorithm with two parallel acceleration techniques, root-indexing and pre-hashing. The root-indexing can match multiple bytes in one single matching, and the pre-hashing can be used to avoid bitmap AC matching, which is a cycle-consuming operation. In the implementation of the Xilinx Vertex4P FPGA platform, the proposed hardware architecture can achieve almost 10.7 Gbps and support the largest pattern set, which is 7.65 times faster than the original bitmap AC in the average case. Further, SAM is feasible for either internal or external memory architecture. The internal memory architecture provides high performance, and the external memory architecture provides high scalability of patterns.

Original languageEnglish
Title of host publicationProceedings - 21st International Conference on Advanced Information Networking and ApplicationsWorkshops/Symposia, AINAW'07
Pages858-863
Number of pages6
DOIs
StatePublished - 18 Oct 2007
Event21st International Conference on Advanced Information Networking and ApplicationsWorkshops/Symposia, AINAW'07 - Niagara Falls, ON, Canada
Duration: 21 May 200723 May 2007

Publication series

NameProceedings - 21st International Conference on Advanced Information Networking and Applications Workshops/Symposia, AINAW'07
Volume2

Conference

Conference21st International Conference on Advanced Information Networking and ApplicationsWorkshops/Symposia, AINAW'07
CountryCanada
CityNiagara Falls, ON
Period21/05/0723/05/07

Keywords

  • Content filtering
  • Coprocessor
  • Finite automata
  • Hashing
  • String matching

Fingerprint Dive into the research topics of 'Scalable automaton matching for high-speed deep content inspection'. Together they form a unique fingerprint.

  • Cite this

    Lin, Y-D., Tseng, K. K., Hung, C. C., & Lai, Y. C. (2007). Scalable automaton matching for high-speed deep content inspection. In Proceedings - 21st International Conference on Advanced Information Networking and ApplicationsWorkshops/Symposia, AINAW'07 (pp. 858-863). [4221165] (Proceedings - 21st International Conference on Advanced Information Networking and Applications Workshops/Symposia, AINAW'07; Vol. 2). https://doi.org/10.1109/AINAW.2007.318