在過去幾年，隨著寬頻與無線網路的盛行，越來越多的人們使用低價的網路設備，來將他們的內部網路連接到網際網路上。相對於商業上所使用的高價網路設備而言，這些低價的網路設備使用較低階的處理器與較少的記憶體，也因此有更多的系統資源限制，比如較低處理器的計算能力，較少的記憶體空間與儲存媒體等。所以，當這些低價的網路設備在處理網路上工作負荷大的封包內容過濾與入侵偵測等問題時，如何善用有限的系統資源，顯得更加的重要。
在本篇論文裡，我們首先探討了舊有的字串比對方法應用在系統資源有限的網路設備上的問題。接著我們提出了一個新的多重字串比對方法，稱之為Set-Exclusive Boyer-Moore Horspool(SEBMH)方法。比起傳統的Aho-Corasick方法與最近所提出的Set-Wise Boyer-Moore Horspool方法而言，我們所提出的方法有著較佳的效能並且使用了較少的系統資源。我們所提出的SEBMH方法融合了雜湊表(Hash table)與二層的連結串連(Link-List)架構以節省記憶體資源的使用，同時並加入了Set Exclusive方法以提升效能。我們所提出的新方法將能更有效的幫助那些資源有限的網路設備來解決處理封包內容過濾的問題。

In the past years, due to the popularization of broadband/wireless communication technologies, many SOHO users now construct their Intranet with low-cost embedded network devices to connect to the Internet. These low-cost network devices have low-level CPU and more limitations on system resource (such as the computation power of CPU, memory, static storage, and so on) than traditional expansive network devices. How to save resource is important for these network devices when they are applied to solve the problems of content-based packet filtering and intrusion detection.
In this paper, we show the problems of existing pattern matching methods when they are implemented in a resource-limited network device. We then propose a novel multiple pattern matching method that has better performance than traditional Aho-Corasick(AC) and Boyer-Moore Horspool (BMH) algorithms and uses less resource than Set-Wise Boyer-Moore Horspool algorithm. It adopts hash table to construct an extended Boyer-Moore Hospool approach for multiple pattern matching with Set-Exclusive Shift Table. The HASH-Link-List structure of the proposed approach will have less requirement of memory resource than other Multiple Pattern Matching algorithms. The Set-Exclusive Table also helps to reduce the times of matching. The proposed pattern-matching method has been applied to content-based packet filtering.

[1] Sun Wu and Udi Manber, “A fast algorithm for multi-pattern searching,” Tech. Rep. TR94-17, Department of Computer Science, University of Arizona, May 1994.
[2] D. Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997.
[3] Sun Kim and Yanggon Kim, “A fast multiple string-pattern matching algorithm,” Proceedings of the 17th AoM/IAoM Inernational Conference on Computer Science, May 1999.
[4] C. Charras and T. Lecroq, “Handbook of Exact String-Matching Algorithms”
[5] Pearson, Peter K. Fast Hashing of Variable Length Text Strings. Commun. ACM 33, 6 (Jun 1990), p677.
[6] “RFC 3074 : DHC Load Balancing Algorithm, IETF”, http://www.ietf.org/
[7] Boyer, R.S. and J.S. Moore. “A fast string searching algorithm”, Comm. ACM, 20(10) (1977) 62--72.
[8] Horspool R.N., 1980, Practical fast searching in strings, Software - Practice & Experience, 10(6):501-506.
[9] Mike Fisk, George Varghese. “An Analysis of Fast String Matching Applied to Content-Based Forwarding and Intrusion Detection”, IEEE INFOCOM, 2002.
[10] Aho, A.V. and M.J. Corasick. ``Efficient string matching: an aid to bibliographic search,' Comm. ACM, 18(6) (1975) 333--340.
[11] Knuth D.E., Morris (Jr) J.H., Pratt V.R., 1977, Fast pattern matching in strings, SIAM Journal on Computing 6(1):323-350.
[12] “Unicode.org”, http://www.unicode.org/
[13] “Snort.org”, http://www.snort.org/
[14] “Snort Daily Snapshot”, http://www.snort.org/dl/snapshots/
[15] “DARPA : Defense Advanced Research Projects Agency”, http://www.darpa.mil/
[16] “The Information Systems Technology Group (IST) of MIT Lincoln Laboratory”, http://www.ll.mit.edu/IST/ideval/index.html
[17] Martin Roesch, “Snort - lightweight intrusion detection for networks,” in Proceedings of the 13th Systems Administration Conference. 1999, USENIX.
[18] Vern Paxson, “Bro: A system for detecting network intruders in real-time,” Computer Networks, vol. 31, no. 23-24, pp. 2435–2463, Dec. 1999.
[19] Max Vision, “Advanced reference archive of current heuristics for network intrusion detection systems (arachNIDS),” http://www.whitehats.com/ids/.