Realizing a sub-linear time string-matching algorithm with a hardware accelerator using bloom filters

Po Ching Lin*, Ying-Dar Lin, Yuan Cheng Lai, Yi Jun Zheng, Tsern-Huei Lee

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

Abstract

Many network security applications rely on string matching to detect intrusions, viruses, spam, and so on. Since software implementation may not keep pace with the high-speed demand, turning to hardware-based solutions becomes promising. This work presents an innovative architecture to realize string matching in sub-linear time based on algorithmic heuristics, which come from parallel queries to a set of space-efficient Bloom filters. The algorithm allows skipping characters not in a match in the text, and in turn simultaneously inspect multiple characters in effect. The techniques to reduce the impact of certain bad situations on performance are also proposed: the bad-block heuristic, a linear worst-case time method and a non-blocking interface to hand over the verification job to a verification module. This architecture is simulated with both behavior simulation in C and timing simulation in HDL for antivirus applications. The simulation shows that the throughput of scanning Windows executable files for more than 10000 virus signatures can achieve 5.64 Gb/s, while the worst-case performance is 1.2 Gb/s if the signatures are properly specified.

Original languageEnglish
Article number4840440
Pages (from-to)1008-1020
Number of pages13
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume17
Issue number8
DOIs
StatePublished - 1 Aug 2009

Keywords

  • Algorithm
  • Field-programmable gate arrays (FPGAs)
  • String matchings

Fingerprint Dive into the research topics of 'Realizing a sub-linear time string-matching algorithm with a hardware accelerator using bloom filters'. Together they form a unique fingerprint.

Cite this