Parallel pattern detection engine

• US 7,444,434 B2
• Filed: 03/06/2007
• Issued: 10/28/2008
• Est. Priority Date: 01/14/2004
• Status: Expired due to Fees

• Current Assignee: Trend Micro Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Kravec, Kerry A., Saidi, Ali G., Slyfield, Jan M., Tannhof, Pascal R.
• Primary Examiner(s): Kindred, Alford
• Assistant Examiner(s): Martinez, David
• Application Number:
  US11/682,547
• Publication Number:
  US 20070150621A1
• Time in Patent Office: 602 Days
• Field of Search: None
• US Class Current: 710/1
• CPC Class Codes: G06V 10/751 Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching
• CPC Class Codes: G06V 10/955 using specific electronic processors

Abstract

A parallel pattern detection engine (PPDE) comprise multiple processing units (PUs) customized to do various modes of pattern recognition. The PUs are loaded with different patterns and the input data to be matched is provided to the PUs in parallel. Each pattern has an Opcode that defines what action to take when a particular data in the input data stream either matches or does not match the corresponding data being compared during a clock cycle. Each of the PUs communicate selected information so that PUs may be cascaded to enable longer patterns to be matched or to allow more patterns to be processed in parallel for a particular input data stream.

Claims

1. A method of determining if any of N sequences of pattern occurs within a sequence of input data using a parallel pattern detection engine (PPDE) comprising the steps of:

a) loading the N sequences of pattern into M processing units (PUs), each of the M PUs having compare circuitry for comparing each of the sequence of input data, in parallel, to a selected pattern in each of the N sequences of pattern stored in the M PUs;

b) loading identification (ID) data into each of the M PUs, wherein the ID data determines an ID for each of the M PUs;

c) loading match mode data into each of the M PUs setting criteria for determining when conditions have been met for indicating that one of the N sequences of pattern has been detected in the sequence of input data;

d) coupling a first input data in parallel to each of the M PUs;

e) comparing the first input data to the selected pattern determined by an address pointer in each of the M PUs and generating a compare output in each of the M PUs within a same clock cycle;

f) modifying the value of the address pointer in each of the M PUs in response to a logic state of the corresponding compare output and an operation code stored with the selected pattern in each of the M PUs;

g) selecting a match ID from the ID data in response to a pattern match signal indicating one of the N sequences of pattern has been detected;

h) storing the match ID and match data corresponding to the match ID; and

i) repeating steps (e-h) until a last input data of the sequence of input data has been compared.

2. The method of claim 1, wherein cascade circuitry is coupled from each of the M PUs to one or more adjacent PUs within the M PUs for selectively coupling chain data between two or more adjacent PUs selected from the M PUs in response to control data loaded into the two or more adjacent PUs.

3. The method of claim 2, wherein the cascade circuitry enables the stored patterns of two or more PUs to be chained together as a single pattern using the chain data.

4. The method of claim 3, wherein the chain data inhibits indexing the pointer of one PU until an adjacent PU coupled with the cascade circuitry has compared a last pattern to an input data.

5. The method of claim 1, one of the N sequences of pattern are partitioned and loaded into the two or more M PUs.

6. The method of claim 1, wherein each of M processing units (PUs) has a control register for storing the match mode data, wherein the match mode data determines criteria for generating the match signal and the match data.

7. The method of claim 6, wherein each of the M PUs has a memory register array for storing a sequence of the pattern and corresponding operation codes addressed by an address register indexed by the address pointer.

8. The method of claim 7, wherein the operation codes are selected from a set of operation codes comprising:

a match operation code indicating that the address pointer is incremented if the compare output is a logic one and the address pointer is reloaded to its initial value if the compare output is a logic zero;

an inverse operation code indicating that the address pointer is to be incremented if the compare output is a logic zero and the address pointer is reloaded to its initial value if the compare output is a logic one;

a wildcard operation code indicating that the address pointer is incremented if the compare output is a logic zero or a logic one;

a multiple wildcard operation code indicating that the address pointer is to be held if the compare output is a logic zero otherwise the address pointer is incremented; and

a last operation code indicating that the address pointer is frozen until the matching process receives a reset if the compare output is a logic one and the address pointer is reloaded to its initial value if the compare output is a logic zero.

9. The method of claim 1, wherein compare circuitry in each of the M PUs completes a compare of an input data to a selected pattern and generates a compare output and modifies the address pointer in the same cycle of a clock signal.

10. The method of claim 1, wherein the match mode data for each of the M PUs sets a match mode comprising:

an exact match mode, wherein a pattern match indicates that the sequence of pattern matches a sequence of input data exactly;

a longest match mode wherein a pattern match indicates that a particular sequence of pattern corresponding to the match ID has the largest number of data in a sequence that compared to a sequence of data in the sequence of input data wherein the match data indicates the value of the largest number;

a maximum match mode, wherein a pattern match indicates that a particular sequence of pattern corresponding to the match ID has the largest number of data that compared to a broken sequence of input data, wherein the match data indicates the value of the largest number;

a fuzzy match mode, wherein a pattern match indicates that a particular sequence of pattern corresponding to the match ID has the closet match to the sequence of input data as determined by a distance value, wherein the match data indicates the distance value.