# US 8,572,016 B2 · Match engine for detection of multi-pattern rules

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,572,016 B2
- Document ID: US8572016B2
- Status: Granted
- Kind: B2
- Application number: 12/533,616
- Filed: 2009-07-31
- Published: 2011-02-03
- Granted: 2013-10-29
- Earliest claimed: 2009-07-31
- Assignees: International Business Machines Corporation
- Applicants: Jan van Lunteren
- Inventors: Jan van Lunteren
- Web page: https://patentgrep.com/patent/US8572016B2

## CPC

- G06N 5/025: Extracting rules from data
- G06F 16/24: Querying
- G06F 21/561: {Virus type analysis}
- G06N 5/047: Pattern matching networks; Rete networks
- H04L 65/60: Network streaming of media packets
- G06F 2221/034: Test or assess a computer or a system
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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

### Claim 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 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.

### Claim 2 (depends on 1)

The method according to claim 1, wherein the method is used to recognize 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.

### Claim 3 (depends on 2)

The method according to claim 2, 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.

### Claim 4 (depends on 2)

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

### Claim 5 (depends on 4)

The method according to claim 4, 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.

### Claim 6

A method of recognizing a specified group of patterns in a data stream, the method comprising:
identifying a rule for said specified group of patterns in the data stream;
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
the second array of finite state machines determining 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;
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
wherein 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.

### Claim 7 (depends on 2)

The method according to claim 2, 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.

### Claim 8 (depends on 6)

The method according to claim 6, 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.

### Claim 9 (depends on 6)

The method according to claim 6, 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.

### Claim 10 (depends on 1)

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.

### Claim 11

A finite state machine engine for determining whether a multitude of specified groups of patterns are in a data stream, the machine comprising:
a context memory holding a multitude of thread context records;
a transition rule memory holding a multitude of multi-pattern rules for transitioning between different states of the machine;
a rule selector for selecting one or more of the multi-pattern rules from the transition rule memory: and
an array of finite state machines for receiving input data identifying patterns, of the specified groups of patterns, that are in the data stream, and processing said input data and data from the context memory, to determine whether the multitude of specified groups of patterns are in the data stream in accordance with specified multi-pattern rules selected from the transition rule memory.

### Claim 12 (depends on 11)

The finite state machine engine according to claim 11, wherein the context records hold state registers, table registers, and mask registers.

### Claim 13 (depends on 12)

The finite state machine engine according to claim 12, wherein each of the context records is used to determine whether a respective one of the multitude of specified groups of patterns is in the data stream in accordance with an associated one of the specified rules.

### Claim 14 (depends on 13)

The finite state machine engine according to claim 13, wherein the input data includes pattern IDs, and the context records are selected on the basis of information contained in the pattern IDs.

### Claim 15 (depends on 11)

The finite state machine engine according to claim 11, wherein each context record is related to one or multiple multi-pattern rules.