Variable-Stride Pattern Matching for Network Intrusion Detection

樣式比對是研究如何從文章中找出特定樣式的字串。在網路中，電腦之間的溝通可以視為雙方互相傳遞一些字串，所以樣式比對便可以用來偵測網路之間的溝通內容，而其中一種應用便是網路入侵偵測和預防。網路入侵偵測和預防是試著找出由外面網路進來的惡意封包，為了找到這些封包定義了一些關於惡意封包的規則，在偵測封包時會將這些規則轉為自動狀態機，而自動狀態機的效能通常決定了整個系統的效能。 可變步伐是一個基於Winnowing演算法的方法，這個方法被應用在字串辨識上能在保持和多步伐策略一樣的偵測速度下使用較少的記憶體。使用可變步伐策略下的自動狀態機每一次狀態轉換時都會一次處理不定數量的符號，而不是只有一個符號，如此減少了狀態轉換的次數而增加偵測速度，然而這個方法只被使用在字串辨識，這片論文擴展可變步伐的策略到樣式比對，同時保持其原來的優點。Pattern matching is a research topic that focuses on how to efficiently find strings of expected form in some text. In the network, the communication between the computers can be view as sending string to each other, so the knowledge of pattern matching is used to detect the content of communication in network. The network instruction detection and prevention, one of application used pattern matching in the network, is try to find the malicious data from the incoming data stream which come from outside network. To find malicious data, the rules that present how malicious data look like are converted into automata. The performance of the automata always determines the performance of detecting system. Variable-stride is base on Winnowing algorithm, and this scheme has more memory efficiency than multi-stride method when it has the same throughput improvement. Every transition in the automata applied variable stride may deal with a variable number of symbols, and reduce number of state transition when detecting, so make detecting process faster. However, this scheme is only applied in string matching. Thus this dissertation extends variable-stride to NFA, and keeps its advantage at the same time