Detecting at least one predetermined pattern in stream of symbols

Patent metadata

Field	Value
Publication number	US-10339141-B2
Application number	US-201615160247-A
Country	US
Kind code	B2
Filing date	May 20, 2016
Priority date	Oct 3, 2014
Publication date	Jul 2, 2019
Grant date	Jul 2, 2019

Abstract

An apparatus comprises pattern matching circuitry for detecting instances of at least one predetermined pattern of symbols within a subject stream of symbols. Encoding circuitry is provided for generating an encoded stream of symbols from an input stream of symbols, where the encoding circuitry maps a number of consecutive repetitions of a same pattern of one or more symbols detected within the input stream to a single instance of a symbol of the encoded stream and a corresponding repetition indicator indicative of the number of consecutive repetitions. Control circuitry controls the pattern matching circuitry to process the encoded stream of symbols generated by the encoding circuitry as the subject stream.

First claim

We claim:

1. An apparatus comprising:
pattern matching circuitry to detect instances of at least one predetermined pattern of symbols within a subject stream of symbols, wherein the pattern matching circuitry comprises:
a plurality of pattern automaton units configured to operate in parallel on corresponding bit portions of a group of one or more adjacent symbols, each pattern automaton unit configured to output a partial match value indicating, based on the corresponding bit portion, which of one or more query conditions representing said at least one predetermined pattern are potentially satisfied by the group of adjacent symbols; and
combining circuitry to combine the partial match values generated by a set of pattern automaton units operating on the same group of adjacent symbols to generate a match value indicating any query condition for which the same query condition is determined as potentially satisfied by all of said set of pattern automaton units;

encoding circuitry to generate an encoded stream of symbols in dependence on an input stream of symbols, wherein the encoding circuitry is configured to map a number of consecutive repetitions of a same pattern of one or more symbols detected within the input stream to a single instance of a symbol of the encoded stream and a corresponding repetition indicator indicative of said number of consecutive repetitions of said same pattern detected in said input stream of symbols; and
control circuitry to control the pattern matching circuitry to process the encoded stream of symbols generated by the encoding circuitry as the subject stream.

2. The apparatus according to claim 1 , wherein the repetition indicator comprises a value indicative of whether the number of consecutive repetitions is 1 or greater than 1.

3. The apparatus according to claim 1 , wherein the repetition indicator comprises a count value indicative of said number of consecutive repetitions.

4. The apparatus according to claim 1 , wherein when processing the encoded stream as the subject stream, the pattern matching circuitry is configured to determine whether the input stream includes one of said at least one predetermined pattern in dependence on whether the repetition indicator corresponding to at least one symbol of the encoded stream satisfies at least one bounding condition.

5. The apparatus according to claim 1 , wherein the control circuitry is configured to control the pattern matching circuitry to process the input stream of symbols as the subject stream of symbols in a first pass of the pattern matching circuitry based on a first set of at least one predetermined pattern; and
the control circuitry is configured to control the pattern matching circuitry to process the encoded stream of components as the subject stream of symbols in a second pass of the pattern matching circuitry based on a second set of at least one predetermined pattern.

6. The apparatus according to claim 5 , wherein the pattern matching circuitry comprises a plurality of pattern matching units;
in the first pass of the pattern matching circuitry, the control circuitry is configured to control a first subset of the pattern matching units to process a current portion of the input stream; and
in the second pass of the pattern matching circuitry, the control circuitry is configured to control a second subset of the pattern matching units to process a portion of the encoded stream corresponding to an earlier portion of the input stream than said current portion, in parallel with processing of said current portion of the input stream by said first subset of the pattern matching units.

7. The apparatus according to claim 5 , wherein the control circuitry has a configuration to control the encoding circuitry to perform further encoding to generate a further stream of symbols in which a number of consecutive repetitions of a pattern of one or more symbols detected in the encoded stream by the pattern matching circuitry in the second pass are mapped to a single symbol representing the pattern and a corresponding repetition indicator indicative of said number of consecutive repetitions, and to control the pattern matching circuitry to process the further stream as the subject stream of symbols in a third pass of the pattern matching circuitry based on a third set of at least one predetermined pattern.

8. The apparatus according to claim 1 , wherein the pattern matching circuitry is configured to process a group of at least two adjacent symbols of the subject stream in parallel to detect whether the group of adjacent symbols satisfies any of a plurality of query conditions including query conditions corresponding to different alignments of the same predetermined pattern with respect to the group of adjacent symbols.

9. The apparatus according to claim 1 , wherein the partial match value comprises a partial match vector indicating which of a plurality of query conditions are potentially satisfied by the group of adjacent symbols, and the match value comprises a match vector indicating which of the plurality of query conditions were determined as potentially satisfied by all of said set of pattern automaton units.

10. The apparatus according to claim 1 , wherein each pattern automaton unit comprises storage circuitry to store programmable data indicative of a state machine comprising a plurality of states, each state associated with a partial match value indicating which of the one or more query conditions are potentially satisfied following a sequence of state transitions leading to that state; and
in response to the corresponding bit portion, each pattern automaton unit is configured to transition from a current state of the state machine to a subsequent state of the state machine selected based on said corresponding bit portion, and to output the partial match value associated with said subsequent state.

11. The apparatus according to claim 1 , wherein the symbols of the input stream comprise at least one of ASCII and UNICODE characters.

12. The apparatus according to claim 1 , wherein the symbols of the input stream comprise portions of data extracted from a network packet.

13. The apparatus according to claim 1 , comprising processing circuitry configured to perform data processing in response to instructions; and
programmable hardware accelerator circuitry comprising the pattern matching circuitry, the encoding circuitry and the control circuitry.

14. The apparatus according to claim 13 , wherein the pattern matching circuitry is configured to process the subject stream of symbols based on query data defining query conditions programmable by compiler software executed by the processing circuitry.

15. A computer-implemented pattern matching method, comprising:
receiving an input stream of symbols;
generating an encoded stream of symbols in dependence on the input stream of symbols, wherein a number of consecutive repetitions of a same pattern of one or more symbols detected within the input stream are mapped to a single instance of a symbol of the encoded stream and a corresponding repetition indicator indicative of said number of consecutive repetitions of said same pattern detected in said input stream of symbols; and
detecting instances of at least one predetermined pattern of symbols within the encoded stream of symbols, using pattern matching circuitry comprising:
a plurality of pattern automaton units configured to operate in parallel on corresponding bit portions of a group of one or more adjacent symbols, each pattern automaton unit configured to output a partial match value indicating, based on the corresponding bit por

Assignees

• Univ Michigan Regents

Inventors

• Cafarella Michael
• GOGTE Vaibhav
• Wenisch Thomas

Classifications

• G06F16/24568 Primary

  Data stream processing; Continuous queries · CPC title

• G06F16/90344

  by using string matching techniques · CPC title