多型樣式匹配演算法於網路系統之研究

Multi-Pattern Matching Algorithms for Networks

許慈芳(Tzu-Fang Sheu)

指導教授 ： 黃能富

國立清華大學/電機資訊學院/通訊工程研究所/博士(2008年)

摘要

In-depth packet inspection engines, which search the whole packet payload to identify packets of interest that contain certain patterns, are urgently required. The searching results from the inspection engines can be utilized in the network equipment for varied application-oriented management. The most important technology for fast packet inspection is an efficient multi-pattern matching algorithm, which performs exact string matching between packets and a large set of patterns. This study discusses state-of-the-art pattern matching algorithms and proposes three efficient multi-pattern matching algorithms for networks: a hierarchical multi-pattern matching algorithm (HMA), an enhanced hierarchical multi-pattern matching algorithm (EHMA), and an Aho-Corasick with Magic Structures (ACM) algorithm.
HMA and EHMA are built based on hierarchical and cluster-wise matching strategies. The hierarchical matching strategy of HMA and EHMA can efficiently reduce the number of external memory (L2) accesses and the amount of memory space. EHMA contributes modifications to HMA and includes the ideas of Sampling Windows and a Safety Shift Strategy. The Safety Shift Strategy can significantly speed up the scanning process of packet inspection. HMA and EHMA improve the average-case performance of multi-pattern matching, and are useful for the network equipment that locates at the general network environment.
Moreover, the proposed ACM presents a novel Magic Structure based on the Chinese Remainder Theorem. ACM needs only a small amount of memory space and does not increase computational time complexity. ACM has better worst-case performance than state-of-the-art algorithms, and is suitable for the network equipment that usually suffers heavy attacks or requires guaranteed performance.
In this study, the analyses and simulation results show that the proposed algorithms in this study outperform others. HMA and EHMA successfully reduce the average number of L2 memory accesses to about only 0.06–0.37 per code, and improve the performance to about 0.89–1161 times better than the state-of-the-art algorithms. The overall cost of ACM is about 1.1–459 times better than the existing implementations. In particular, HMA, EHMA, and ACM use only simple and easy instructions, and no special hardware is required. Therefore, the proposed multi-pattern matching algorithms are easy to be implemented in both hardware and software. Consequently, the proposed multi-pattern matching algorithms can be efficiently applied to packet inspection engines for network equipment.

關鍵字

樣式匹配 ； 封包檢驗 ； 網路安全

並列摘要

無資料

並列關鍵字

pattern matching ； packet inspection ； network security

參考文獻

[4] Spyros Antonatos, Kostas G. Anagnostakis, and Evangelos P. Markatos, "Generating realistic workloads for network intrusion detection systems," ACM Workshop on Software and Performance, pp. 207–215, 2004.

[5] Martin Roesch, "Snort – Lightweight Intrusion Detection for Networks," Proceedings of the 13th Systems Administration Conference, pp. 229–238, 1999.

[6] Tomoaki Sato and Masa-aki Fukase, "Reconfigurable Hardware Implementation of Host-based IDS," the 9th Asia-Pacific Conference on Communication, Vol. 2, pp. 849–853, Penang, Malaysia, Sept. 2003.

[8] Alfred V. Aho and Margaret J. Corasick, "Efficient string matching: an aid to bibliographic search," Communications of the ACM, Vol. 18, Np. 6, pp. 330–340, June 1975.

[13] Robert S. Boyer and Strother J. Moor, "A Fast String Searching Algorithm," Communications of the ACM, Vol. 20, No. 10, pp. 762–772, October 1977.