<link rel="stylesheet" href="styles.cf390c6bfbe7555f.css">

學術出版;;Publications

Permanent URI for this communityhdl:11536/1

收集所有交通大學研究人員與學生個人或團體所發表之各項學術著作，涵蓋期刊論文、教師專書、學位論文等項。;;Collections of Publications of NCTU Researchers and Students Like Journal Papers and Thesis.

Browse

🏛️國立陽明交通大學機構典藏

Access type: Open accessSubject: search.filters.subject.string matching

Search Results

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item type:Item,
    A platform-based SoC design and implementation of scalable automaton matching for deep packet inspection
    (2007-12-01)
    Lin, Ying-Dar
    ;
    Tseng, Kuo-Kun
    ;
    Lee, Tsern-Huei
    ;
    Lin, Yi-Neng
    ;
    Hung, Chen-Chou
    String matching plays a central role in packet inspection applications such as intrusion detection, anti-virus, anti-sparn and Web filtering. Since they are computation and memory intensive, software matching algorithms are insufficient to meet the high-speed performance. Thus, offloading packet inspection to a dedicated hardware seems inevitable. This paper presents a scalable automaton matching (SAM) coprocessor that uses Aho-Corasick (AC) algorithm with two parallel acceleration techniques, root-indexing and pre-hashing. The root-indexing can match multiple bytes in one single matching, and the pre-hashing can be used to avoid bitmap, AC matching which is a cycle-consuming operation. In the platform-based SoC implementation of the Xilinx ML310 FPGA, the proposed hardware architecture can achieve almost 10.7 Gbps and support over 10,000 patterns for virus, which is the largest pattern set from among the existing works. On the average, the performance of SAM is 7.65 times faster than the original bitmap AC. Furthermore, SAM is feasible for either internal or external memory architecture. The internal memory architecture provides high performance, while the external memory architecture provides high scalability in term of the number of patterns. (C) 2007 Elsevier B.V. All rights reserved.
  • Thumbnail Image
    Item type:Item,
    An efficient pattern matching scheme in LZW compressed sequences
    (2008-07-01)
    Lee, Tsern-Huei
    ;
    Huang, Nai-Lun
    ;
    電信工程研究所
    ;
    Institute of Communications Engineering
    Compressed pattern matching (CPM) is an emerging research field addressing the problem: given a compressed sequence and a pattern, process the sequence with minimal (or no) decompression to find the pattern occurrence(s) in the uncompressed sequence. It can be applied to detect malwares and confidential information leakage in compressed files directly. In this paper, we report our work of CPM in Lempel-Ziv-Welch (LZW) compressed sequences. We propose an efficient bitmap-based realization of the Amir-Benson-Farach algorithm. We also generalize the algorithm to find all pattern occurrences and report their absolute positions in the uncompressed sequence. Experiments are conducted to test the space requirements of our proposed generalization and two related CPM schemes which can also be realized with bitmaps. Results show that our proposed generalization requires the least amount of storage for moderate and long patterns. We also conduct experiments to compare the throughput performance of our proposed generalization with these two related CPM schemes and the decompress-then-search scheme. Results show that our proposed generalization outperforms the decompress-then-search scheme significantly. When scanning a file with pattern occurrences, our proposed generalization performs slightly better than the two related CPM schemes. The difference is significant when scanning a file with no pattern occurrence. Copyright (c) 2008 John Wiley & Sons, Ltd.
  • Thumbnail Image
    Item type:Item,
    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.