Match engine for detection of multi-pattern rules

• US 9,015,102 B2
• Filed: 10/25/2013
• Issued: 04/21/2015
• Est. Priority Date: 07/31/2009
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: van Lunteren, Jan
• Primary Examiner(s): Vincent, David
• Assistant Examiner(s): OLUDE AFOLABI, OLATOYOSI
• Application Number:
  US14/063,554
• Publication Number:
  US 20140052748A1
• Time in Patent Office: 543 Days
• Field of Search: 706/47, 718/100
• US Class Current: 706/47
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 21/561 Virus type analysis
• CPC Class Codes: G06F 2221/034 Test or assess a computer or a system
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: G06N 5/047 Pattern matching networks; Rete networks
• CPC Class Codes: H04L 65/60 Network streaming of media packets

Abstract

Methods, systems and computer program products are disclosed for detecting patterns in a data stream that match multi-pattern rules. One embodiment of the invention provides a method of recognizing a specified group of patterns in a data stream. The method comprises identifying a rule for said specified group of patterns in the data stream, and using a first array of finite state machines to scan the data stream for at least some of the patterns in the specified group. For patterns in the specified group that are found in the data stream by the first array of finite state machines, pattern identifiers are sent to a second array of finite state machines. The second array of finite state machines determines if the specified group of patterns is in the data stream in accordance with the identified rule by, at least in part, using said pattern identifiers.

Claims

1. A method of recognizing a specified group of patterns in a data stream, the method comprising:

identifying a multi-pattern rule for said specified group of patterns in the data stream;

using a first array of finite state machines, in a first, pattern scanner stage, to scan the data stream for at least some of the patterns in the specified group;

for patterns in the specified group that are found in the data stream by the first array of finite state machines, sending pattern identifiers to a second array of finite state machines, in a second, rule processor stage;

using the second array of finite state machines for determining if the specified group of patterns is in the data stream in accordance with the identified multi-pattern rule by, at least in part, using said pattern identifiers; and

using a compiler to distribute a function that matches an individual pattern over the first, pattern scanner stage and the second, rule processor stage; and

wherein;

the method is used to recognize a multitude of specified groups of patterns in the data stream, and the second array of finite state machines determining if the specified group of patterns is in the data stream includes;

running a multitude of threads on the second array of finite state machines; and

using said multitude of threads to determine whether the multitude of specified groups of patterns are in the data stream; and

the sending pattern identifiers to the second array includes;

for each of the multitude of specified groups of patterns, for patterns in said each group that are found in the data stream by the first array of finite state machines, sending pattern identifiers to an associated one of the threads running on the second array of finite state machines.

2. The method according to claim 1, wherein the using said multitude of threads includes using each of the threads to determine whether a respective one of the specified groups of patterns is present in the data stream.

3. The method according to claim 1, wherein the identifying a rule includes identifying a respective one rule for each of the multitude of specified groups of patterns.

4. The method according to claim 3, wherein the using the first array includes using the first array to scan the data stream for at least some of the patterns in each of said multitude of specified groups of patterns.

5. The method according to claim 1, wherein:

each of the threads is used to determine whether a respective one of the specified groups of patterns is in the data stream; and

the sending pattern identifiers to the second array includes, for each of the specified groups of patterns, for patterns in said each group that are found in the data stream by the first array of finite state machines, sending pattern identifiers to the one of the threads used to determine whether said each of the specified groups of patterns is in the data stream.

6. The method according to claim 1, wherein the sending pattern identifiers further includes using an ID distributor to ensure that the only pattern identifiers received by each thread are the pattern identifiers needed by said each thread to determine whether the associated one of the specified groups of patterns is in the data stream.

7. The method according to claim 1, wherein each thread has a respective one thread ID, and wherein the sending pattern identifiers includes, in each pattern identifier, the thread ID of the thread to which said pattern identifier is sent.

8. The method according to claim 1, wherein the using the first array of finite state machines includes using the first array of finite state machines to scan for all of the patterns in the specified group.

9. An article of manufacture comprising:

at least one computer usable hardware medium having computer readable program code logic to execute a machine instruction in a processing unit for using a computer to for recognizing a specified group of patterns in a data stream in accordance with a defined multi-pattern rule, said computer readable program code logic, when executing, performing the following;

using a first array of finite state machines to scan the data stream for at least some of the patterns in the specified group;

for patterns in the specified group that are found in the data stream by the first array of finite state machines, sending pattern identifiers to a second array of finite state machines; and

using the second array of finite state machines for determining if the specified group of patterns is in the data stream in accordance with the identified multi-pattern rule by, at least in part, using said pattern identifiers wherein;

the machine instruction is executed to use the computer for recognizing a multitude of specified groups of patterns in the data stream, and wherein the second array of finite state machines determining if the specified group of patterns is in the data stream includes;

running a multitude of threads on the second array of finite state machines; and

using said multitude of threads to determine whether the multitude of specified groups of patterns are in the data stream.

10. The article of manufacture according to claim 9, wherein:

each of the threads is used to determine whether a respective one of the specified groups of patterns is in the data stream; and

the sending pattern identifiers to the second array includes, for each of the specified groups of patterns, for patterns in said each group that are found in the data stream by the first array of finite state machines, sending pattern identifiers to the one of the threads used to determine whether said each of the specified groups of patterns is in the data stream.

11. The article of manufacture according to claim 10, wherein the sending pattern identifiers further includes using an ID distributor to ensure that the only pattern identifiers received by each thread are the pattern identifiers needed by said each thread to determine whether the associated one of the specified groups of patterns is in the data stream.

12. The article of manufacture according to claim 11, wherein each thread has a respective one thread ID, and wherein the sending pattern identifiers including, in each pattern identifier, the thread ID of the thread to which said pattern identifier is sent.