Deep Packet Inspection in Network Intrusion Detection and Prevention Systems

封包內容檢測技術於網路偵測與防禦系統之研究

朱彥銘(Yen-Ming Chu)

指導教授 ： 黃能富

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

摘要

As high-speed networking technology continues to progress, network environments include more and more applications. However, many users still feel uncertain about these network applications due to security issues. To provide a safe application environment, researchers must investigate how to process packets at high speed. Conventional firewalls, which are capable of processing traffic in network Layer-4, have been developed very well and had significant performance both in academia and industry. However, it is hard for these firewalls to fight against various new threats in today’s Internet, such as viruses, spyware, and malicious code. As a result, Network Intrusion Detection and Prevention systems (NIDPs) have been developed to identify and prevent these malicious attacks over the network by performing deep packet inspection (DPI). DPI scans both the headers and payloads of each incoming packet for thousands of attack signatures.
NIDP is an efficient way to provide security protection. However this approach suffers from a performance problem that causes a significant bottleneck due to DPI in heavy-load networks. One of the most common techniques to solve this problem and accelerate DPI is to use a search filter which can filter out innocent packets to speed up the DPI. Another method is to adopt more effective pattern matching algorithms. Pattern matching is the core function of DPI in NIDP, and is the most time-consuming operation. This becomes even more challenging in high-speed networks. Hence, researchers have paid a lot of attention to designing high-speed and cost-effective filters and pattern matching techniques for DPI.
This dissertation first introduces related works about search filters that can filter out normal packets before they are forwarded to a pattern matching algorithm. And the same chapter also introduces several pattern matching algorithms since this is the most computation-intensive task in an NIDP, and ultimately determines NIDP performance. The following chapter proposes an efficient and practical filtering mechanism called Super-Symbol Filter (SSF). The proposed SSF algorithm uses a tiny data structure, and is light-computational and cache-resident. It can be implemented efficiently in a software-based platform. Experimental results show that the speed gain of the proposed scheme is around 100-300 %.
Next, we present a novel scheme, namely, major-state, by observing the deterministic finite automaton (DFA) constructed by given signature patterns. The proposed mechanism is verified to be effective through several well-known routing table lookup algorithms. Also the practicability of the proposed scheme is evaluated by employing realistic attack signatures and traffic traces. The experimental results indicate that a state table can be converted into a prefix table comprising only 1.5% of the original number of entries. Compared with past nondeterministic finite state automaton (NFA) based string matching researches, the proposed scheme achieves more than double throughput rate in hardware implementation.
Afterwards, this dissertation discusses how to optimize the use of major-state by proposing three efficient multiple pattern matching algorithms for NIDP. By employing the characteristics of magic states observed, the first proposed algorithm, named AC with Major State Algorithm (ACMS), significantly reduces the memory requirement without sacrificing high speed no matter it is implemented in software or hardware. The ACMS algorithm also provides high flexibility that it can be tuned to fit specific performance requirement and resource constraints. The experimental results show that the performance of ACMS is over 3.5 times in hardware implementation and 21 times in software implementation better than that of the state-of-the-art studies. Furthermore, another proposed algorithm, called the Major-State-based Heuristic (MSH), constructs a tiny data structure which can be stored into the on-chip memory of modern cost effective FPGA. Prototype and experimental results show the overall efficiency of the proposed MSH is at least 7 times faster than that of the baseline model. The MSH enables the design of cost effective FPGA-based accelerator to furnish over 1Gbps throughput. It can also be scaled to multi-gigabit and realized on various silicon implementations. Finally, this dissertation proposes the third algorithm with major-state, named Aho-Corasick-based Pattern Matching with Major-State algorithm (PMMS). PMMS is a novel memory-efficient string matching algorithm that only requires around 2% of the memory utilized in Aho-Corasick algorithm but has the throughput 5 times faster than that of state-of-the-art algorithm with very limited memory resource. Evaluation results indicate that the proposed PMMS algorithm is applicable to resource-limited embedded systems. In conclusion, the proposed three algorithms are flexible to fit different resource constraints and performance requirements.

關鍵字

字串比對 ； 樣式比對 ； 封包檢測 ； 網路安全

並列摘要

為了因應網際網路的迅速發展，網路入侵偵測與防禦系統藉由封包內容檢測技術來解決傳統網路防火牆所面臨之不足。但封包內容檢測技術卻因計算的複雜度而面臨了效能上的有待改善與加強。
本篇論文乃針對封包內容檢測之技術進行研究。首先，我們提出了一種輕型的前置過濾器：其利用一種精簡的資料結構，有效地過濾大部分的不具攻擊威脅的封包內容，以此加速內容比對之處理速度。
接著，我們根據自動機的特性，提出了一個稱之為多數狀態（major-state）之機制。藉由這樣的機制，我們將傳統應用於路由查找之演算法與技術，轉化成為可提供以自動機為基礎的特徵比對演算法使用，進而大幅地減少記憶體之使用量。
我們根據多數狀態的特性，設計了兩種嶄新的自動機為基礎之特徵比對演算法。第一個演算法，我們稱之為ACMS：其可大量地降低傳統自動機為基礎之特徵比對演算法在資料結構上面臨龐大記憶體耗用的問題，也可以保有自動機基礎的演算法所具有效能保證之優勢。而且其可根據計算資源與計算速度之需求，調整其記憶體使用量，且保證其最糟效能。第二個演算法稱之為MSH：其為一種適合低成本的硬體架構。其有效地利用非常精簡的晶片內置記憶體空間，來使得計算速度可符合現今大多數的網路環境所用。
最後，我們提出了第三個根據多數狀態所設計出來的特徵比對演算法，稱之為PMMS。PMMS是一種特別適合以軟體方式在資源有限的內嵌式系統中運行的演算法。而這三種的演算法，無論在軟體實作，或是以硬體實現之方式，都具備了在有限系統資源中，達成運算時間與記憶體需求均衡的設計。

並列關鍵字

string matching ； pattern matching ； packet inspection ； network security

參考文獻

[1] Firewall-1 Product. Available: http://www.chechpoint.com

[8] Calvin Ko, Manfred Ruschitzka, and Karl N. Levitt, “Execution monitoring of security critical programs in distributed systems: A specification-based approach,” Proceedings of the 1997 IEEE Symposium on Security and Privacy, pp. 175-187, May 1997,.

[10] Harold S. Javitz and Alfonso Valdes, “The SRI statistical anomaly detector,” Proceedings of the 1991 IEEE Symposium on Research in Security and Privacy, pp. 316-215, May 1991.

[12] Y. F. Jou, F. Gong, C. Sargor , X. Wu, S. F. Wu, H. C. Chang, and F. Wang, “Design and implementation of a scalable intrusion detection system for the protection of network infrastructure,” Proceedings of the DARPA Information Survivability Conference and Exposition, vol. 2, pp. 69–83, 2000.

[13] Terry Escamilla, “Intrusion Detection: Network Security Beyond the Firewall,” John Wiley & Sons, New York, 1998.