Pattern detection

Abstract

Apparatus for detecting a pattern in a data stream comprises a pattern matching device for receiving the data stream. The pattern matching device comprises one or more rule engines, each rule engine operating under a plurality of state transition rules encoding a plurality of patterns, a first state transition rule including a wildcard state component and a wildcard input component, a second state transition rule including a wildcard state component and a specified input component, and a third state transition rule including a specified state component and a specified input component, the first, second and third rules having differing priorities, and at least one state transition rule including an output component indicating a pattern match. The apparatus is arranged to pass the data stream to each rule engine, and is further arranged to output a signal indicating a pattern match when a state transition rule indicates a pattern match.

1 . An apparatus for detecting a pattern in a data stream comprising a pattern matching device for receiving the data stream, the pattern matching device comprising at least one rule engine, said at least one rule engine operating under a plurality of state transition rules encoding a plurality of patterns, a first state transition rule including a wildcard state component and a wildcard input component, a second state transition rule including a wildcard state component and a specified input component, and a third state transition rule including a specified state component and a specified input component, the first, second and third rules having differing priorities, and at least one state transition rule including an output component indicating a pattern match, the apparatus arranged to pass the data stream to said at least one rule engine, and further arranged to output a signal indicating a pattern match when a state transition rule indicates a pattern match.  
   
   
       2 . An apparatus according to  claim 1 , further comprising a pattern distribution device arranged to receive the patterns, to distribute the patterns across a plurality of pattern collections, and to convert each pattern collection into a plurality of state transition rules.  
   
   
       3 . An apparatus according to  claim 2 , wherein the pattern distribution device is arranged to distribute the patterns substantially evenly across the plurality of pattern collections.  
   
   
       4 . An apparatus according to  claim 2 , wherein the pattern distribution device is arranged, when distributing the patterns across the plurality of pattern collections, to distribute the patterns according to commonality and conflict between patterns.  
   
   
       5 . An apparatus according  claim 1 , further comprising a results processor for receiving output from said at least one rule engine, the results processor arranged to determine if a pattern match has occurred.  
   
   
       6 . An apparatus according  claim 1 , wherein at least one of the state transition rules includes a character class component.  
   
   
       7 . An apparatus according  claim 1 , wherein the pattern matching device comprises a plurality of rule engines.  
   
   
       8 . An apparatus according to  claim 7 , wherein the rule engines are arranged in at least one pair of rule engines, with said at least one pair of rule engines processing alternate portions of the data stream.  
   
   
       9 . An apparatus according to  claim 8 , further comprising a results processor for receiving output from said at least one rule engine, the results processor arranged to determine if a pattern match has occurred, wherein the results processor is arranged to combine the outputs of said at least one pair of rule engines.  
   
   
       10 . A method for detecting a pattern in a data stream comprising receiving the data stream, running at least one rule engine, said at least one rule engine operating under a plurality of state transition rules encoding a plurality of patterns, a first state transition rule including a wildcard state component and a wildcard input component, a second state transition rule including a wildcard state component and a specified input component, and a third state transition rule including a specified state component and a specified input component, the first, second and third rules having differing priorities, and at least one state transition rule including an output component indicating a pattern match, passing the data stream to said at least one rule engine, and outputting a signal indicating a pattern match when a state transition rule indicates a pattern match.  
   
   
       11 . A method according to  claim 10 , further comprising receiving the patterns, distributing the patterns across a plurality of pattern collections, and converting each pattern collection into a plurality of state transition rules.  
   
   
       12 . A method according to  claim 11 , wherein the step of distributing the patterns across the plurality of pattern collections distributes the patterns substantially evenly across the plurality of pattern collections.  
   
   
       13 . A method according to  claim 11 , wherein the step of distributing the patterns across the plurality of pattern collections, is executed by an algorithm, which distributes the patterns according to commonality and conflict between patterns.  
   
   
       14 . A method according to  claim 10 , further comprising processing the output from said at least one rule engine to determine if a pattern match has occurred.  
   
   
       15 . A method according to  claim 10 , wherein at least one of the state transition rules includes a character class component.  
   
   
       16 . A method according to  claim 10 , comprising running a plurality of rule engines.  
   
   
       17 . A method according to  claim 16 , wherein the rule engines are arranged in at least one pair of rule engines, with said at least one pair of rule engines processing alternate portions of the data stream.  
   
   
       18 . A method according to  claim 17 , further comprising processing the output from said at least one rule engine to determine if a pattern match has occurred, wherein the processing of the outputs of the rule engines comprises combining the outputs of said at least one pair of rule engines.  
   
   
       19 . A computer program product on a computer readable medium for controlling apparatus for detecting a pattern in a data stream, the computer program product comprising instructions for receiving the data stream, running at least one rule engine, said at least one rule engine operating under a plurality of state transition rules encoding a plurality of patterns, a first state transition rule including a wildcard state component and a wildcard input component, a second state transition rule including a wildcard state component and a specified input component, and a third state transition rule including a specified state component and a specified input component, the first, second and third rules having differing priorities, and at least one state transition rule including an output component indicating a pattern match, passing the data stream to said at least one rule engine, and outputting a signal indicating a pattern match when a state transition rule indicates a pattern match.  
   
   
       20 . A computer program product according to  claim 19 , further comprising instructions for receiving the patterns, distributing the pattern across a plurality of pattern collections, and converting each pattern collection into a plurality of state transition rules.  
   
   
       21 . A computer program product according to  claim 20 , wherein the step of distributing the patterns across the plurality of pattern collections distributes the patterns substantially evenly across the plurality of pattern collections.  
   
   
       22 . A computer program product according to  claim 20 , wherein the step of distributing the patterns across the plurality of pattern collections, is executed by an algorithm, which distributes the patterns according to commonality and conflict between patterns.  
   
   
       23 . A computer program product according to  claim 19 , further comprising instructions for processing the output from said at least one rule engine to determine if a pattern match has occurred.  
   
   
       24 . A computer program product according to  claim 19 , wherein at least one of the state transition rules includes a character class component.  
   
   
       25 . A computer program product according to  claim 19 , comprising instructions for running a plurality of rule engines.  
   
   
       26 . A computer program product according to  claim 25 , wherein the rule engines are arranged in at least one pair of rule engines, with said at least one pair of rule engines processing alternate portions of the data stream.  
   
   
       27 . A computer program product according to  claim 26 , further comprising instructions for processing the output from said at least one rule engine to determine if a pattern match has occurred, wherein the processing of the outputs of the rule engines comprises combining the outputs of said at least one pair of rule engines.