标题: | Realizing a Sub-Linear Time String-Matching Algorithm With a Hardware Accelerator Using Bloom Filters |
作者: | Lin, Po-Ching Lin, Yin-Dar Lai, Yuan-Cheng Zheng, Yi-Jun Lee, Tsern-Huei 资讯工程学系 电信工程研究所 Department of Computer Science Institute of Communications Engineering |
关键字: | Algorithms;field-programmable gate arrays (FPGAs);string matching |
公开日期: | 1-八月-2009 |
摘要: | 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 10 000 virus signatures can achieve 5.64 Gb/s, while the worst-case performance is 1.2 Gb/s if the signatures are properly specified. |
URI: | http://dx.doi.org/10.1109/TVLSI.2008.2012011 http://hdl.handle.net/11536/6887 |
ISSN: | 1063-8210 |
DOI: | 10.1109/TVLSI.2008.2012011 |
期刊: | IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS |
Volume: | 17 |
Issue: | 8 |
起始页: | 1008 |
结束页: | 1020 |
显示于类别: | Articles |
文件中的档案:
If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.