Detection of Patterns

Abstract

A method of detecting patterns in a plurality of data blocks, comprising generating a first database comprising a first subset of patterns of a set of selected patterns, generating a second database comprising a second subset of remaining patterns of the set of selected patterns, receiving the plurality of data blocks, and, for each data block, using the data, block and a hash function to generate a key, using the key to search the first database, locating an entry of the first database corresponding to the key, reading the content of the entry which comprises zero or a selected pattern that generates the key, if the content of the entry comprises zero, determining that the data block does not comprise a selected pattern, and outputting a first output indicating that the data block does not comprise a selected pattern.

1 . A method of detecting patterns in a plurality of data blocks, comprising generating a first database comprising a first subset of patterns of a set of selected patterns, generating a second database comprising a second subset of remaining patterns of the set of selected patterns, receiving the plurality of data blocks, and, for each data block, using the data block and a hash function to generate a key, using the key to search the first database, locating an entry of the first database corresponding to the key, reading the content of the entry which comprises zero or a selected pattern that generates the key, if the content of the entry comprises zero, determining that the data block does not comprise a selected pattern, and outputting a first output indicating that the data block does not comprise a selected pattern, or if the content of the entry comprises a selected pattern, determining that the data block comprises the selected pattern and outputting a first output indicating that the data block comprises the selected pattern, or determining that the data block does not comprise the selected pattern and outputting a first output indicating that the data block does not comprise the selected pattern, and using a content addressable memory (CAM) to compare the data block with the second database, determining that the data block matches a selected pattern in the second database, and outputting a second output indicating that the data block comprises the selected pattern, or
 determining that the data block does not match a selected pattern in the second database, and outputting a second output indicating that the data block does not comprise a selected pattern, combining the first and second outputs, and if either output indicates that the data block comprises a selected pattern, outputting a flag indicating that the data block comprises the selected pattern.   
   
   
       2 . A method according to  claim 1 , in which generating the first database comprising the first subset of patterns of a set of selected patterns, comprises determining each possible data block, using each possible data block and the hash function to generate a plurality of keys, comparing the or each data block which generates a key with the set of selected patterns, and if the or each data block does not comprise a selected pattern, generating an entry of the first database comprising the key and zero, or if the or any of the data blocks does comprise a selected pattern, generating an entry of the first database comprising the key, the or one of the data blocks which comprises a selected pattern and an identifier (ID) for the data block. 
   
   
       3 . A method according to  claim 1 , in which generating the second database comprising the second subset of remaining patterns of a set of selected patterns, comprises generating an entry of the second database comprising each of the data blocks which comprises a selected pattern not stored in an entry of the first database. 
   
   
       4 . A method according to  claim 1 , in which generating the key comprises generating a key which is compressed with respect to the data block. 
   
   
       5 . A method according to  claim 1 , in which determining that the data block comprises or does not comprise a selected pattern comprises comparing the data block with the selected pattern to determine if a match between them does or does not occur. 
   
   
       6 . A method according to  claim 1 , which is used to detect patterns starting at any position of a data block. 
   
   
       7 . A method according to  claim 1 , which is used to detect selected patterns having various lengths. 
   
   
       8 . A method according to  claim 1 , in which the selected patterns comprise any of whole or partial words or whole or partial strings or whole or partial DNA sequences or signatures or signature segments of malicious content. 
   
   
       9 . A pattern detection circuit for detecting patterns in a plurality of data blocks, comprising a plurality of hash modules, each hash module comprising a first database comprising a first subset of patterns of a set of selected patterns, wherein each hash module receives the plurality of data blocks, and, for each data block, uses the data block and a hash function to generate a key, uses the key to search the first database, locates an entry of the first database corresponding to the key, reads the content of the entry which comprises zero or a selected pattern that generates the key, if the content of the entry comprises zero, determines that the data block does not comprise a selected pattern, and outputs a first output indicating that the data block does not comprise a selected pattern, or if the content of the entry comprises a selected pattern, determines that the data block comprises the selected pattern and outputs a first output indicating that the data block comprises the selected pattern, or determines that the data block does not comprise the selected pattern and outputs a first output indicating that the data block does not comprise the selected pattern, and a plurality of CAM modules, each CAM module comprising a second database comprising a second subset of remaining patterns of the set of selected patterns, wherein each CAM module receives the plurality of data blocks, and, for each data block, compares the data block with the second database, determines that the data block matches a selected pattern in the second database, and outputs a second output indicating that the data block comprises the selected pattern, or determines that the data block does not match a selected pattern in the second database, and outputs a second output indicating that the data block does not comprise a selected pattern, and a combiner module which combines the first and second outputs, and if either output indicates that the data block comprises a selected pattern, outputs a flag indicating that the data block comprises the selected pattern. 
   
   
       10 . A circuit according to  claim 9 , in which each hash module comprises a RAM device. 
   
   
       11 . A circuit according to  claim 10 , in which each RAM device stores the first database. 
   
   
       12 . A circuit according to  claim 11 , in which a key is used to search the first database of a RAM device by using the key as an address to search addresses assigned to a plurality of memory locations of the RAM device. 
   
   
       13 . A circuit according to  claim 9 , in which each hash module comprises a plurality of hash devices each of which uses a data block and the hash function to generate a key. 
   
   
       14 . A circuit according to  claim 9 , in which each CAM module comprises a plurality of CAM cells. 
   
   
       15 . A circuit according to  claim 14 , in which each CAM cell stores a data block comprising a pattern of the second database. 
   
   
       16 . A circuit according to  claim 15 , in which each CAM cell comprises a plurality of comparators each of which compares a received data block with the data block stored in the CAM cell. 
   
   
       17 . A circuit according to  claim 9 , which detects a pattern starting at any position of a data block. 
   
   
       18 . A circuit according to  claim 17 , in which the pattern detection circuit comprises a plurality of hash devices and a plurality of CAM comparators, a first data block is input into a first hash device and into a first CAM comparator, a second data block, shifted with respect to the first data block, is input into a second hash device and into a second CAM comparator and so on. 
   
   
       19 . A circuit according to  claim 18 , in which the second data block is shifted by one or more positions of the block with respect to the first data block. 
   
   
       20 . A circuit according to  claim 19 , in which the first and second data blocks comprise bits or bytes, and the second data block is shifted by one or more positions comprising one or more bits or bytes of the block with respect to the first data block. 
   
   
       21 . A circuit according to  claim 9 , which comprises a plurality of parts, a first part which detects patterns of length n, a second part which detects patterns of length n−1, a third part which detects patterns of length n−2, and so on. 
   
   
       22 . A circuit according to  claim 9 , in which the selected patterns comprise any of whole or partial words or whole or partial strings or whole or partial DNA sequences or signatures or signature segments of malicious content.