Rapid Searching and Matching of Data to a Dynamic Set of Signatures Facilitating Parallel Processing and Hardware Acceleration

Patent metadata

Field	Value
Publication number	US-2016188751-A1
Application number	US-201514746340-A
Country	US
Kind code	A1
Filing date	Jun 22, 2015
Priority date	Dec 29, 2014
Publication date	Jun 30, 2016
Grant date	—

Abstract

A mechanism is provided in a data processing system for matching data to a dynamic set of signatures. The mechanism creates a state transition, result, and mask (STR&M) table based on a set of signatures. The mechanism executes scanner code in each of a plurality of hardware devices in parallel to form a plurality of matching engines. The mechanism loads the STR&M table into each of the plurality of matching engines. Responsive to receiving a plurality of input records, the mechanism distributes input strings from the plurality of input records among the plurality of matching engines and receiving signature set match results from the plurality of matching engines.

First claim

1 . A method, in a data processing system, for matching data to a dynamic set of signatures, the method comprising:
creating a state transition, result, and mask (STR&M) table based on a set of signatures; executing scanner code in each of a plurality of hardware devices in parallel to form a plurality of matching engines; loading the STR&M table into each of the plurality of matching engines; responsive to receiving a plurality of input records at the plurality of matching engines, extracting input strings from the plurality of input records; submitting the plurality of input strings for scanning by the plurality of matching engines; and receiving signature set match results from the plurality of matching engines.

2 . The method of claim 1 , wherein creating the STR&M table comprises:
receiving a signature set specification; parsing and analyzing the signature set specification; generating a Finite State Machine (FSM) table based on a result of the parsing and analyzing of the signature set specification; and converting the FSM table to the STR&M table.

3 . The method of claim 2 , wherein creating the STR&M table further comprises translating the STR&M table to a binary format.

4 . The method of claim 2 , wherein the signature set specification is ordered to ensure that at any character position in an input string there is at most one prioritized signature match.

5 . The method of claim 1 , wherein a first row of the STR&M table corresponds to an initial state, a at row of the STR&M table corresponds to a persistent final NO_MATCH state, and other rows of the STR&M table correspond to input strings with continuations to a signature.

6 . The method of claim 1 , wherein the STR&M table comprises a state column, a plurality of condition or input character value columns, a result column, and a mask column.

7 . The method of claim 6 , wherein the scanner code uses the mask and result column values to determine a matching result without use of branching logic.

8 . The method of claim 1 , wherein the scanner code in each matching engine receives a given input string, gets an input symbol from the given input string, sets a working result using result and mask columns of the STR&M table, sets a next state based on a current state and the input symbol using the STR&M table, and advances input to a next input symbol until an end of the given input string is reached or a NO_MATCH state is reached.

9 . The method of claim 8 , wherein the scanner code uses the mask and result column values to determine a matching result without use of branching logic.

10 . The method of claim 1 , wherein responsive to a given matching engine receiving a new STR&M table in binary form, the given matching engine loads the new STR&M table.

11 . The method of claim 1 , wherein the plurality of hardware devices comprise a plurality of Single Instruction Multiple Data (SIMD), Graphics Processing Unit (GPU), or Field Programmable Gate Array (FPGA) hardware devices.

12 . The method of claim 11 , wherein extracting the input strings from the plurality of input records comprises communicating through a computing device interface.

13 . The method of claim 12 , wherein the computing device interface comprises an Open Computing Language (OpenCL) application programming interface.

14 . The method of claim 11 , wherein the plurality of hardware devices comprise a Compute Unified Device Architecture (CUDA) parallel computing platform.

15 - 24 . (canceled)

Assignees

• IBM

Inventors

• Agrawal Dakshi
• Bhatti Rashed Z
• Parr Francis N

Classifications

• G06F16/24568

  Data stream processing; Continuous queries · CPC title

• G06F16/9017

  using directory or table look-up (use of a directory or look-up table in file systems G06F16/13) · CPC title

• G06F16/245 Primary

  Query processing · CPC title

• G06F16/951

  Indexing; Web crawling techniques · CPC title

• G06F16/2282

  Tablespace storage structures; Management thereof · CPC title