用加權式自動狀態機做特徵碼比對

Signature Matching with Weighted Automata

張家銘(Chia-Ming Chang)

指導教授 ： 顏嗣鈞

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2010年)

https://doi.org/10.6342/NTU.2010.00872

摘要

網際網路在世界上已經普及化且容易使用。為了保護來自網際網路的攻擊，我們需要網路入侵偵測系統。在網路入侵偵測系統的特徵碼比對中，使用自動狀態機為基礎的方法是一個有用的解決辦法。將網路入侵偵測系統的特徵碼表示成決定性的有限自動狀態機可達到非常快速的特徵碼比對，但其需要的記憶體空間卻非常巨大。另一方面，使用非決定性的有限自動狀態機將造成特徵碼比對的速度過慢，雖然它需要的記憶體空間非常小。
在某些論文中，使用變種的有限自動狀態機做網路入侵偵測系統的特徵碼比對已經被提出。舉例來說，使用延展的有限自動狀態機做特徵碼比對是快速的，且記憶體空間的需求也不高，但它需要一個人工設定的步驟且建構一個延展的有限自動狀態機需要花相當多的時間。另一個例子是複合決定性的有限自動狀態機，它提供了一個可以在使用的記憶體空間和特徵碼比對的時間上做調整的機制。在這篇論文中，我們提出了一個使用加權式自動狀態機做網路入侵偵測系統的特徵碼比對的方法，此方法快速且完全自動化。透過使用不同的半環來建構加權式自動狀態機，我們可以調校加權式自動狀態機的效率以及其記憶體使用空間。我們也提出了一些在建構加權式自動狀態機做特徵碼比對時需要用到的演算法。

關鍵字

網路安全 ； 網路入侵偵測系統 ； 加權式自動狀態機

並列摘要

The Internet has become popular and easy to use for everyone in the world. Network Intrusion Detection Systems (NIDS) are useful for preventing attacks from malicious users. The automata-based solutions are useful for signature matching in NIDS. Representing NIDS signatures as deterministic finite state automata results in very fast matching speed but the memory usage would blowup, on the other hand, using nondeterministic finite state automata to match signatures results in very small memory usage but slow signature matching.
Variant finite state automata have been introduced for signature matching in NIDS in several papers. For example, extended finite automata (XFA) is fast and small memory usage but it needs a manual configuration and large construction time. Another example is multiple-DFA, it provide a mechanism to trade memory usage for time by enforcing an upper bound on the available memory. In this thesis, we introduce another method to match signatures in NIDS by using weighted automata, which is fast and fully automatic. By controlling the semiring of weighted automata we could tune performance and memory usage of the weighted automata. We also provide several algorithms for constructing weighted automata to match signatures.

並列關鍵字

Network Security ； Network Intrusion Detection System ； Weighted Automata

參考文獻

[21] F. Yu, Z. Chen, Y. Diao, T. Lakshman, and R. Katz, “Fast and memory-efficient regular expression matching for deep packet inspection,” Proceedings of Architectures for Networking and Communications Systems, pp. 93-102, 2006.

[2] V. Paxson, “Bro: a system for detecting network intruders in real-time,” Computer Networks, volume 31, pp. 2435-3463, 1999.

[3] A. Aho and M. Corasick, “Efficient string matching: An aid to bibliographic search,” Communications of the ACM, June 1975.

[4] R. Boyer and J. Moore, “A fast string searching algorithm,” Communications of the ACM, volume 20, October 1977.

[5] C. Coit, S. Staniford, and J. McAlerney, “Towards faster pattern matching for intrusion detection or exceeding the speed of Snort,” 2nd DARPA Information Survivability Conference and Exposition, June 2001.