<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.automaton

Search Results

Now showing 1 - 4 of 4
  • 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,
    A Hybrid Algorithm of Backward Hashing and Automaton Tracking for Virus Scanning
    (2011-04-01)
    Lin, Po-Ching
    ;
    Lin, Ying-Dar
    ;
    Lai, Yuan-Cheng
    ;
    資訊工程學系
    ;
    Department of Computer Science
    Virus scanning involves computationally intensive string matching against a large number of signatures of different characteristics. Matching a variety of signatures challenges the selection of matching algorithms, as each approach has better performance than others for different signature characteristics. We propose a hybrid approach that partitions the signatures into long and short ones in the open-source ClamAV for virus scanning. An algorithm enhanced from the Wu-Manber algorithm, namely the Backward Hashing algorithm, is responsible for only long patterns to lengthen the average skip distance, while the Aho-Corasick algorithm scans for only short patterns to reduce the automaton sizes. The former utilizes the bad-block heuristic to exploit long shift distance and reduce the verification frequency, so it is much faster than the original WM implementation in ClamAV. The latter increases the AC performance by around 50 percent due to better cache locality. We also rank the factors to indicate their importance for the string matching performance.
  • Thumbnail Image
    Item type:Item,
    A Fast Scalable Automaton-Matching Accelerator for Embedded Content Processors
    (2009-04-01)
    Tseng, Kuo-Kun
    ;
    Lai, Yuan-Cheng
    ;
    Lin, Ying-Dar
    ;
    Lee, Tsern-Huei
    ;
    資訊工程學系
    Home and office network gateways often employ a cost-effective embedded network processor to handle their network services. Such network gateways have received strong demand for applications dealing with intrusion detection, keyword blocking, antivirus and antispam. Accordingly, we were motivated to propose an appropriate fast scalable automaton-matching (FSAM) hardware to accelerate the embedded network processors. Although automaton matching algorithms are robust with deterministic matching time, there is still plenty of room for improving their average-case performance. FSAM employs novel prehash and root-index techniques to accelerate the matching for the nonroot states and the root state, respectively, in automation based hardware. The prehash approach uses some hashing functions to pretest the input sub-string for the nonroot states while the root-index approach handles multiple bytes in one single matching for the root state. Also, FSAM is applied in a prevalent automaton algorithm, Aho-Corasick (AC), which is often used in many content-filtering applications. When implemented in FPGA, FSAM can perform at the rate of 11.1Gbps with the pattern set of 32,634 bytes, demonstrating that our proposed approach can use a small logic circuit to achieve a competitive performance, although a larger memory is used. Furthermore, the amount of patterns in FSAM is not limited by the amount of internal circuits and memories. If the high-speed external memories are employed, FSAM can support up to 21,302 patterns while maintaining similar high performance.
  • Thumbnail Image
    Item type:Item,
    On path equivalence of nondeterministic finite automata
    (1996-04-08)
    Tzeng, WG
    ;
    交大名義發表
    ;
    資訊工程學系
    ;
    National Chiao Tung University
    ;
    Department of Computer Science
    Two nondeterministic finite automata (NFAs) are said to be path equivalent if each string is accepted by the two automata via the same number of computation paths. In this paper we show the following. (1) The path equivalence problem for NFAs without lambda-cycles is solvable not only in polynomial sequential time but also in O(log(2)(n)) parallel time using a polynomial number of processors, where n is the total number of states in two NFAs. (2) The path equivalence problem for NFAs with lambda-cycles is PSPACE-complete, hence decidable.