Realizing a Sub-Linear Time String-Matching Algorithm With a Hardware Accelerator Using Bloom Filters
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.citation.epage |
1020 | en_US |
dc.citation.issue |
8 | en_US |
dc.citation.spage |
1008 | en_US |
dc.citation.volume |
17 | en_US |
dc.citation.woscount |
8 | |
dc.contributor.author |
Lin, Po-Ching | en_US |
dc.contributor.author |
Lin, Yin-Dar | en_US |
dc.contributor.author |
Lai, Yuan-Cheng | en_US |
dc.contributor.author |
Zheng, Yi-Jun | en_US |
dc.contributor.author |
Lee, Tsern-Huei | en_US |
dc.contributor.department |
資訊工程學系 | zh_TW |
dc.contributor.department |
電信工程研究所 | zh_TW |
dc.contributor.department |
Department of Computer Science | en_US |
dc.contributor.department |
Institute of Communications Engineering | en_US |
dc.date.accessioned |
2014-12-08T15:09:03Z | |
dc.date.available |
2014-12-08T15:09:03Z | |
dc.date.issued |
2009-08-01 | en_US |
dc.description.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 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. | en_US |
dc.identifier.doi |
10.1109/TVLSI.2008.2012011 | en_US |
dc.identifier.issn |
1063-8210 | en_US |
dc.identifier.journal |
IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS | en_US |
dc.identifier.uri |
http://dx.doi.org/10.1109/TVLSI.2008.2012011 | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/6887 | |
dc.identifier.wosnumber |
WOS:000268282700004 | |
dc.language.iso |
en_US | en_US |
dc.subject |
Algorithms | en_US |
dc.subject |
field-programmable gate arrays (FPGAs) | en_US |
dc.subject |
string matching | en_US |
dc.title |
Realizing a Sub-Linear Time String-Matching Algorithm With a Hardware Accelerator Using Bloom Filters | en_US |
dc.type |
Article | en_US |
檔案
- 000268282700004.pdf (1.21 MB, Adobe PDF)
所屬典藏: 期刊論文
引用此條目
Lin, P.-C., Lin, Y.-D., Lai, Y.-C., Zheng, Y.-J., & Lee, T.-H. (2009). Realizing a Sub-Linear Time String-Matching Algorithm With a Hardware Accelerator Using Bloom Filters. IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, 17(8), 1008–1020. https://doi.org/10.1109/TVLSI.2008.2012011
引用文字依 APA 第 7 版格式自動產生,使用前請再核對。
分享
永久網址:https://ir.lib.nycu.edu.tw/handle/11536/6887