A Parallel Automaton string matching with Pre-Hashing and Root-Indexing techniques for content filtering coprocessor

Kuo Kun Tseng*, Ying-Dar Lin, Tsern-Huei Lee, Yuan Cheng Lai

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

10 Scopus citations

Abstract

We propose a new Parallel Automaton string matching approach and its hardware architecture for content filtering coprocessor. This new approach can improve the average matching time of the Parallel Automaton with Pre-Hashing and Root-Indexing techniques. The Pre-Hashing technique uses a hashing function to verify quickly the text against the partial patterns in the Automaton, and the Root-Indexing technique matches multiple bytes for the root state in one single matching. A popular Automaton algorithm, Aho-Corasick (AC) is chosen to be implemented by adding the two techniques; we employ these two techniques in a memory efficient version of AC namely Bitmap AC. For the average-case time, our approach improves Bitmap AC by 494% and 224% speedup for URL and Virus patterns, respectively. Since Pre-Hashing and Root-Indexing techniques can be concurrently executed with Bitmap AC in the hardware, our proposed approach has the same worst-case time as Bitmap AC.

Original languageEnglish
Article number1540374
Pages (from-to)113-118
Number of pages6
JournalProceedings of the International Conference on Application-Specific Systems, Architectures and Processors
DOIs
StatePublished - 23 Jul 2005
EventIEEE 16th International Conference on Application-Specific Systems, Architectures, and Processors, ASAP 2005 - Samos, Greece
Duration: 23 Jul 200525 Jul 2005

Fingerprint

Dive into the research topics of 'A Parallel Automaton string matching with Pre-Hashing and Root-Indexing techniques for content filtering coprocessor'. Together they form a unique fingerprint.

Cite this