Method and apparatus for a pattern matcher using a multiple skip structure

Abstract

A multiple skip structure of a pattern matcher uses a shift engine to read a string and divide the string into a front module and a rear module. The shift engine uses the rear module of the string to index the shift index column of a shift table and retrieves a corresponding shift value and signature value back to the shift engine. The shift engine uses the shift value for the first level of filtering. If the shift value indicates a pattern is contained, it then compares a signature value with a shift hash value for a second level of filtering. The shift hash value is obtained from using the front module of the string via a hash function. If the shift hash value equals to the signature value, then it transmits the position of the string to a trie engine for a full pattern matching.

1 . A multiple skip structure of a pattern matcher, for network intrusion detection system, comprising:
 a string pump capable of reading a string, wherein the string comprises a front module and a rear module;   a shift table comprising a plurality of shift indices, a plurality of shift values and a plurality of signature values, wherein each of the shift indices indicates the corresponding shift value and signature value;   a shift engine connects the string pump and the shift table and is capable of reading and computing the string; and   a trie engine connects to the string pump and a trie table and is capable of a full pattern matching;   wherein the shift engine uses the shift value and the signature value to decide whether to start the trie engine.   
   
   
       2 . The multiple skip structure of a pattern matcher of  claim 1 , further comprising a skip value generator to generate the shift values and store the shift values in the shift table in advance. 
   
   
       3 . The multiple skip structure of a pattern matcher of  claim 1 , wherein the signature values use a hash function to compute and store the result from the has function in the shift table in advance. 
   
   
       4 . The multiple skip structure of a pattern matcher of  claim 1 , wherein a shift generator uses a hash function to compute the front module of the string to generate the shift hash value and compares the shift hash value with the signature value. 
   
   
       5 . A method of multiple skip of a pattern matcher for a network intrusion detection system comprises:
 reading a string at a shift engine from a string pump;   dividing the string into a front module and a rear module;   comparing the rear module with a plurality of shift indices of a shift table;   transmitting a shift value and a signature value corresponds to a shift index equal to the rear module from the shift table to the shift engine;   computing the shift value in the shift engine;   using the front module of the string via a hash function to generate a shift hash value; and   comparing the shift hash value and the signature value to determine whether to start a trie engine.   
   
   
       6 . The method of multiple skip of the pattern matcher of  claim 5 , further comprising a skip value generator to generator the shift value and store the shift value in the shift table in advance. 
   
   
       7 . The method of multiple skip of the pattern matcher of  claim 5 , wherein the signature value use a hash function to compute and store the result from the hash function in the shift table in advance. 
   
   
       8 . The method of multiple skip of the pattern matcher of  claim 5 , wherein the shift engine computes the shift value further comprises the steps of:
 when the shift value does not equal to zero, then a position of the string moves toward right direction of the shift value; and   when the shift value equals to zero, further comprises the steps of:
 when the shift hash value does not equal to the signature value, then the position of the string moves one character toward right direction; and 
 when the shift hash value equals to the signature value, then transmits the position of the string to the trie engine. 
   
   
   
       9 . The method of multiple skip of the pattern matcher of  claim 5 , wherein the shift hash value is compared with the signature value further comprises:
 when the shift hash value does not equal to the signature value, then the position of the string moves one character toward right direction; and   when the shift hash value equals to the signature value, then transmits the position of the string to the trie engine.   
   
   
       10 . A method of multiple skip of a pattern matcher, for network intrusion detection system, comprising:
 receiving a string at a trie engine from a string pump;   generating a trie hash value uses the string via a trie index generator of the trie engine;   indexing the trie hash value with a plurality of trie indices of a trie table;   transmitting a trie node, a current node byte enable, a next node byte enable, a pattern number and a skip value corresponds to a trie index equals to the trie hash value to the trie engine; and   comparing and computing the trie node, the current node byte enable, the next node byte enable, the pattern number and the skip value with the string.   
   
   
       11 . The method of multiple skip of the pattern matcher of  claim 10 , wherein the trie node, the current node byte enable, the next node byte enable, the pattern number and the skip value are computed and then stored in the trie table in advance. 
   
   
       12 . The method of multiple skip of the pattern matcher of  claim 10 , wherein the trie node, the current node byte enable, the next node byte enable, the pattern number and the skip value use a hash function to compute and store in the trie table in advance. 
   
   
       13 . The method of multiple skip of the pattern matcher of  claim 12 , wherein the trie table uses a trie index collision link list method. 
   
   
       14 . The method of multiple skip of the pattern matcher of  claim 10 , wherein the trie node uses a parent node pointer to maintain the relation in a trie tree and stores in the trie table in advance. 
   
   
       15 . The method of multiple skip of the pattern matcher of  claim 10 , wherein the next node byte enable uses the smallest of the current node byte enable of the next node of a trie tree and stores in the trie table in advance. 
   
   
       16 . The method of multiple skip of the pattern matcher of  claim 10 , wherein the trie index generator uses a hash function to generate the trie hash value. 
   
   
       17 . The method of multiple skip of the pattern matcher of  claim 16 , wherein the trie index generator uses the next node byte enable to generate the trie hash value. 
   
   
       18 . The method of multiple skip of the pattern matcher of  claim 10 , wherein the pattern number is generated by the logic of the string contains a longer pattern then certainly contains a shorter pattern, and stores the pattern number in the trie table in advance. 
   
   
       19 . The method of multiple skip of the pattern matcher of  claim 18 , wherein the trie engine compares the trie node and the string uses the pattern number, comprises the steps of:
 when the pattern number indicates another pattern is contained, then the trie engine continues to read the next character of the string; and   when the pattern number indicates another pattern is not contained, then the trie engine continues to read the next string.   
   
   
       20 . The method of multiple skip of the pattern matcher of  claim 10 , wherein the skip value uses the principle of the pattern does not generally contain another start point of the pattern, hence the compared string can be skipped and the amount of characters of the compared string is stored as the skip value in the trie table in advance.