Embedded programmable intelligent search memory (PRISM) that simultaneously performs regular expression based search and signature pattern based search

• US 8,051,022 B2
• Filed: 12/06/2007
• Issued: 11/01/2011
• Est. Priority Date: 12/08/2006
• Status: Active Grant

• Current Assignee: IP Program Inc.
• Original Assignee: Ashish A. Pandya
• Inventors: Pandya, Ashish A.
• Primary Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US11/952,028
• Publication Number:
  US 20080140661A1
• Time in Patent Office: 1,426 Days
• Field of Search: 706 45- 47, 706/62, 711/100, 711/103, 711/108, 707/706, 707/758, 707/736, 707/769
• US Class Current: 706/45
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 9/4498 Finite state machines
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores
• CPC Class Codes: G11C 15/04 using semiconductor elements
• CPC Class Codes: G11C 15/043 using capacitive charge storage elements
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms

Abstract

Memory architecture provides capabilities for high performance content search. The architecture creates an innovative memory that can be programmed with content search rules which are used by the memory to evaluate presented content for matching with the programmed rules. When the content being searched matches any of the rules programmed in the Programmable Intelligent Search Memory (PRISM) action(s) associated with the matched rule(s) are taken. The PRISM content search memory is embedded in a single core or multi-core processors or in multi-processor systems to perform content search. PRISM accelerates content search by offloading the content search tasks from the processors. Content search rules comprise of regular expressions which are converted to finite state automata and then programmed in PRISM for evaluating content with the search rules.

Claims

1. A hardware processor comprising an integrated circuit chip processor, said integrated circuit chip processor comprising programmable intelligent search memory for content search, wherein said programmable intelligent search memory simultaneously performs regular expression based search and signature pattern based search, said programmable intelligent search memory for content search using a plurality of regular expressions, said regular expressions comprising a plurality of symbols or characters, said plurality of regular expressions further comprising a plurality of interval symbols, said regular expressions converted into a plurality of finite state automata(FSA) representing the functionality of said regular expressions for programming in said programmable intelligent search memory, said finite state automata comprising a plurality of states, said states derived from said symbols or characters of said regular expressions, said content comprising a plurality of input symbols provided as input to said programmable intelligent search memory, said programmable intelligent search memory comprising a plurality of FSA rule blocks to program said plurality of finite state automata and to search said content using said plurality of finite state automata to detect a match of said regular expressions in said content, said FSA rule block of the plurality of FSA rule blocks to program a finite state automata of said plurality of finite state automata and to search said content using said finite state automata to detect a match of a regular expression of said plurality of regular expressions in said content, said regular expression corresponding to said finite state automata, said FSA rule block further comprising:

a) an interval symbol evaluation circuit to store and evaluate said plurality of interval symbols;

b) a plurality of state blocks for evaluating state transitions and to generate a plurality of partial state transition signals;

c) a state control block to store a current state vector, said current state vector to represent the current state of the evaluation of said finite state automata; and

d) a match detect block to detect match of said regular expression with said content.

2. A finite state automata of the claim 1 comprising ‘

n’

states corresponding to ‘

n’

symbols of said regular expression, said ‘

n’

symbols comprising ‘

m’

bits wherein ‘

n’ and

‘

m’

are each integer values greater than one.

3. A state block of the plurality of state blocks of claim 2 coupled to a current state of said current state vector, said state block further comprising:

a) a symbol memory circuit to store said ‘

m’

bit symbol;

b) a symbol evaluation circuit coupled to said symbol memory circuit to evaluate a match of said ‘

m’

bit symbol stored in said symbol memory circuit with said plurality of input symbols of said content;

c) a state dependent vector memory circuit to store a ‘

n’

bit state transition control corresponding to said ‘

n’

states; and

d) a partial state transition control circuit coupled to said symbol evaluation circuit, said current state and said state dependent vector memory circuit to perform partial state transition evaluation and generate a partial state transition signal for transition of said current state from a first state of said ‘

n’

states to a second state of said ‘

n’

states.

4. A state control block of claim 3 further comprising:

a) a state transition control circuit coupled to said plurality of partial state transition signals to perform state transition evaluation for transition of said current state from a first state of said ‘

n’

states to a next state of a second state of said ‘

n’

states;

b) a ‘

n’

bit initialization vector memory circuit to store an initial or start state value for said ‘

n’

states of said finite state automata; and

c) a ‘

n’

bit current state vector memory circuit coupled to said ‘

n’

bit initialization vector memory and said state transition control circuit to load and store a current state value from a set of said ‘

n’

states of said finite state automata.

5. At least one match detect block of claim 1 further comprising:

a) a ‘

n’

bit accept state vector memory circuit to store which of said ‘

n’

states are accept states, said accept states used to detect when said regular expression has matched with said content; and

b) a match detect circuit to detect a match in said content with said regular expression.

6. A match detect block of claim 5 further comprising:

a) a ‘

n’

bit tag state vector memory circuit to store which of said ‘

n’

states are tag states, said tag states used to detect when said regular expression has partially matched with said content; and

b) a tag match detect circuit to detect a tag match in said content with said regular expression to detect;

a partial regular expression match;

or a sub-string match, or a combination thereof.