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


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
Issue number8
StatePublished - 1 Aug 2009


  • 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