Browsing by Author "Zheng, Yi-Jun"

Now showing 1 - 2 of 2

Realizing a Sub-Linear Time String-Matching Algorithm With a Hardware Accelerator Using Bloom Filters
(2009-08-01)
Lin, Po-Ching
;
Lin, Yin-Dar
;
Lai, Yuan-Cheng
;
Zheng, Yi-Jun
;
Lee, Tsern-Huei
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.
String Matching System and Method Using Bloom Filters to Achieve Sub-Linear Computation Time
(2008-05-15)
Lin, Po-Ching
;
Lin, Ying-Dar
;
Zheng, Yi-Jun
;
Lai, Yuan-Cheng
A string matching system includes a text string, a plurality of patterns, an m-byte search window and a plurality of Bloom filters, wherein the m-byte search window stands for an m-byte sub-string in the text string under inspection. Every Bloom filter comprises sub-strings of a plurality of patterns. These Bloom filters are queried for membership of the rightmost block in the search window to determine the shift length. The acceleration efficiency of matching many bytes can be achieved simultaneously by shifting the search window for many bytes. Meanwhile, the patterns are stored into an embedded memory through a memory-efficient mechanism-the Bloom filter.