Snort 是一個開源的網路入侵偵測系統，透過檢查每一個網路封包來判斷惡意攻擊或檔案，因此封包的處理速度非常重要。在 Snort 2.0 版本以後使用了新的偵測引擎取代了三維鏈表來檢查封包內容，但很少有參考文獻完整解釋它的運作流程以及使用的演算法，它們都會影響封包的處理速度。
所以我們直接研究與分析 Snort 2.9.9.0 版本的程式碼，並且利用效能事件分析工具找到封包處理中最大的開銷在於 Fast Pattern Matcher，它是新的偵測引擎採用的封包過濾功能，它是基於 Aho-Corasick (AC) 多字串比對演算法運作的。AC 演算法是一個以自動機為主的演算法，它會利用 Input Text 的每一個字元找出下一個狀態，所以它的搜尋時間取決於 Input Text 的長度。多字元的自動機可以一次利用多個字元找出下一個狀態，能夠有效的提升搜尋速度，但是會遇到 Transition Rule Explosion 的問題，即使只是雙字元的自動機記憶體的使用量就有 256 倍的成長。
在這篇論文中我們提出將 Pattern 分成奇數位置的 Pattern 和偶數位置的 Pattern 來加速 AC 演算法以改善 Snort 系統的效能。我們使用兩階段式的搜尋流程，在第一階段只使用 Input Text 的奇數字元找出 AC 自動機的下一個狀態，藉此快速找出可能匹配 Pattern 的 Sub Input Text，然後在第二階段中才執行完整匹配，以確定 Sub Input Text 是否匹配 Pattern。我們的方法在 Dirtiness 低的情況中可以減少接近一半的 Input Text 長度，並且不用花費大量的記憶體。從實驗的結果顯示在不同的 Snort rules 檔案下，我們的方法的速度比起原本的 AC 演算法可以提升 1.11 倍到 1.80 倍，並且記憶體的使用量約是原本的 0.92 倍到 1.01 倍。

Snort is an open source network intrusion detection system that detects if a specific information associated to a malicious attack is contained in each network packet. The speed of the intrusion detection process on each packet must be fast enough to meet the requirement of high-speed networks. After the release of Snort 2.0, a new detection engine was used to replace the Three-Dimension Linked List for deep packet inspection. However, few references explain Snort’s architecture and algorithm that are the main factors affecting the processing speed of the packets.
We find that the biggest overhead in packet processing in the new Detection Engine is the Fast Pattern Matcher by using the performance event analysis tool to directly trace the source codes of Snort 2.9.9.0. Fast Pattern Matcher is the packet filtering function used by the new Detection Engine based on Aho-Corasick (AC) multi-pattern matching algorithm. AC algorithm is a automata-based algorithm. It uses each character of input text to find the next state. So the search time is limited by the input text length. Multi-character state machine can use multi-character to find the next state. It can speedup the search time effectively, but there will be a problem with transition rule explosion. Even with a dual-character state machine, the memory usage has increased by 256 times.
In this thesis, we propose an Odd-Even AC (OE-AC) structure built from odd and even subpatterns generated from the patterns used in the original AC algorithm to improve the search performance of Snort. We use a two-phase search architecture. In first phase, only odd characters of input text are used to the next state in AC state machine. It can find the sub input text that may match patterns. In second phase, a full match is performed to determine if sub input text matches patterns. Out scheme can reduce the input text length by nearly half in the case of low dirtiness and doesn’t require a lot of memory. The experiment results show that under different Snort rule files, the search performance based on OE-AC is improved 1.11 to 1.80 times compared with original AC, and OE-AC requires about 92% to 101% of the memory needed in original AC.

[1] Snort—a open source network intrusion detection system. [Online]. Available: http://www.snort.org/.
[2] Perf—performance analyzing tool in Linux. [Online]. Available: https://perf.wiki.kernel.org.
[3] DEF CON—one of the world's largest hacker conventions. [Online]. Available: https://www.defcon.org.
[4] V. Aho and M. J. Corasick, "Efficient string matching: An aid to bibliographic search, " Commun. ACM, vol. 18, no. 6, pp. 330-340, 1975
[5] Jay Beale, Andrew R. Baker, Brian Caswell and Mike Poor, "Snort 2.1 Intrusion Detection," Rckland, MA:Syngress Publication, April 2004.
[6] S. Wu and U. Manber, "A fast algorithm for multi-pattern searching", 1994.
[7] M. Norton, "Optimizing Pattern Matching for Intrusion Detection", Columbia, MD, USA:, 2004.
[8] K. Thompson, "Programming techniques: Regular expression search algorithm, " Commun. ACM, vol. 11, no. 6, pp. 419–422, 1968.
[9] J. E. Hopcroft, "An n log n algorithm for minimizing states in a finite automaton, " Stanford Univ., Stanford, CA, USA, Tech. Rep. STAN-CS-71-190, 1971.
[10] Bro—a free and open source network analysis framework. [Online]. Available: https://www.bro.org.
[11] Suricata—a free and open source, mature, fast and robust network threat detection engine. [Online]. Available: https://suricata-ids.org/.
[12] U. Shankar and V. Paxson, "Active mapping: resisting NIDS evasion without altering traffic, " in: Proceedings of the IEEE Symposium on Research in Security and Privacy, Oakland, CA, 2003.
[13] C.-C. Chen and S.-D. Wang, "An efficient multicharacter transition string-matching engine based on the aho-corasick algorithm, " ACM Trans. Archit. Code Optim., vol. 10, no. 4, pp. 25:1–25:22, Dec. 2013.
[14] X. Wang and D. Pao, "Memory-based architecture for multicharacter Aho–Corasick string matching, " IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 26, no. 1, pp. 143–154, Jan. 2017.
[15] Liao, C-Y. and Lin, C.-H.A, "Novel Parallel Dual-Character String Matching Algorithm on Graphical Processing Units, " International Conference on Algorithms and Architectures for Parallel Processing, 2017, 197-210.
[16] Boyer, R.S. and Moore, J.S. "A Fast String Searching Algorithm, " Com. of the ACM, Vol. 20, No. 10, 1977, 262–272.
[17] Yang, Y.H. and Prasanna, V.K. "Robust and scalable string pattern matching for deep packet inspection on multicore processors, " IEEE Trans. Parallel Distrib. Syst. 2013, 24, 2283–2292.
[18] Snort Subscriber Rule Set Categories. [Online]. Available: https://www.snort.org/rules_explanation