Complex symbol evaluation for programmable intelligent search memory

• US 7,827,190 B2
• Filed: 12/06/2007
• Issued: 11/02/2010
• Est. Priority Date: 12/08/2006
• Status: Active Grant

• Current Assignee: Infosil Inc.
• Original Assignee: Ashish A. Pandya
• Inventors: Pandya, Ashish A.
• Primary Examiner(s): Wong; Leslie
• Application Number:
  US11/952,112
• Publication Number:
  US 20080140632A1
• Time in Patent Office: 1,062 Days
• Field of Search: 707/999.003, 707/999.006, 707/999.107, 707/737, 707/758, 707/E17.046, 711/100, 711/103, 711/108
• US Class Current: 707/758
• 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. 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. The PRISM memory provides features for complex regular expression symbols like range detection, complement control, bit masking and the like and enables complex symbols and compact regular expression representation.

Claims

1. The integrated circuit chip comprising programmable intelligent search memory for content search wherein said programmable intelligent search memory performs regular expression based search and wherein said regular expression comprises complex symbols, said programmable intelligent search memory for content search using one or more regular expressions, said one or more regular expressions comprising one or more symbols or characters and further comprising one or more complex symbols, said one or more regular expressions converted into one or more finite state automata representing the functionality of said one or more regular expressions for programming in said programmable intelligent search memory, said one or more finite state automata comprising a plurality of states, said plurality of states derived from said one or more symbols or characters of said one or more regular expressions, said content comprising one or more input symbols provided as input to said programmable intelligent search memory, said programmable intelligent search memory comprising at least one of each of:

a. a symbol memory circuit to store said one or more symbols;

b. a complex symbol memory circuit to store said one or more complex symbols;

c. a complex symbol evaluation circuit coupled to said complex symbol memory circuit to evaluate match of said one or more complex symbols stored in said complex symbol memory circuit with said one or more input symbols of said content;

d. a symbol evaluation circuit coupled to said symbol memory circuit to evaluate match of said one or more symbols stored in said symbol memory circuit with said one or more input symbols of said content;

e. a state dependent vector memory circuit to store state transition controls for said one or more finite state automata;

f. a current state vector memory circuit to store said plurality of states; and

g. a state transition circuit coupled to said symbol evaluation circuit, said complex symbol evaluation circuit, said current state vector memory circuit and said state dependent vector memory circuit to perform state transition from one or more first states to one or more second states of said plurality of states of said one or more finite state automata.

2. The integrated circuit chip of claim 1, wherein the symbol memory circuit, the complex symbol memory circuit, the state dependent vector memory circuit, and the current state vector memory circuit of the programmable intelligent search memory comprises static random access memory circuits.

3. The integrated circuit chip of claim 1, wherein the programmable intelligent search memory further comprises at least one of:

a. a memory circuit to store mask vector coupled to said one or more symbols to enable or disable evaluation of specific bits of said one or more symbols by said symbol evaluation circuit;

b. received symbol vector signals generated by said symbol evaluation circuit to indicate when said content comprises said one or more symbols of said one or more finite state automata;

c. an accept state vector memory circuit to store which of said one or more states are accept states, said accept states used to detect when said one or more regular expressions have matched with said content;

d. a tag state vector memory circuit to store which of said one or more states are tag states, said tag states used to detect when said one or more regular expressions have partially matched with said content;

e. a start state vector memory circuit to store initialization values of said one or more states;

f. a regular expression match detect circuit to detect a match in said content with said one or more regular expressions;

g. a tag match detect circuit to detect a tag match in said content for said one or more finite state automata that are tagged to detect a partial regular expression match or to detect a sub-string match or a combination thereof;

or

h. any combination of a through g above.

4. The integrated circuit chip of claim 3, wherein the programmable intelligent search memory comprises memory circuits that are each independently addressable in a random order.

5. The integrated circuit chip of claim 1, wherein the programmable intelligent search memory further comprises circuits to couple said programmable intelligent search memory to at least one functional block or circuit or a combination.

6. The integrated circuit chip of claim 5, wherein the at least one functional block comprises a microprocessor, multi-core processor, network processor, graphics processor, switch processor, microcontroller, TCP Offload Engine, network packet classification engine, protocol processor, regular expression processor, security processor, content search processor, network attached storage processor, storage area network processor, wireless processor, mainframe computer, grid computer, server, workstation, personal computer, laptop, handheld device, cellular phone, wired or wireless networked device, switch, router, gateway, chipset, unified threat management device, and the like or any derivatives thereof or any combination thereof.

7. The integrated circuit chip of claim 1, wherein the symbol evaluation circuit comprises one or more symbol match signals to indicate a match of said one or more stored symbols with said one or more input symbols of said content.

8. The integrated circuit chip of claim 7, wherein the plurality of one or more symbol match signals coupled together to form a composite match signal.

9. The integrated circuit chip of claim 8, wherein the composite match signal indicates a composite match, said composite match signal asserted only when each of said one or more symbol match signals coupled to form said composite match signal have a match with a plurality of said one or more input symbols of said content.

10. The integrated circuit chip of claim 1, wherein the one or more finite state automata comprises non deterministic finite state automata or tagged non deterministic finite state automata or deterministic finite state automata or a combination thereof.

11. The integrated circuit chip of claim 5, wherein the one or more finite state automata of claim 5, comprising comprises programmable finite state automata comprising said one or more states wherein each state of said one or more states is coupled to at least one said state dependent vector memory circuit to control and program which of said one or more states are coupled to said each state.

12. The integrated circuit chip of claim 1, wherein the one or more finite state automata comprises said one or more states wherein each state of said one or more states is entered from a set of said one or more states coupled to said each state using the same symbol of said content being searched.

13. The integrated circuit chip of claim 1, wherein the one or more finite state automata comprises said one or more states wherein each state of said one or more states is exited to a set of said one or more states coupled to said each state using the same symbol of said content being searched.

14. The integrated circuit chip of claim 1, wherein the one or more finite state automata comprises said one or more states wherein a set of said one or more states are programmed as accept states, said accept states for use to detect when said one or more regular expressions have matched with said content.

15. The integrated circuit chip of claim 1, wherein the one or more finite state automata comprises said one or more states wherein a set of said one or more states are programmed as tag states, said tag states for use to detect when said one or more regular expressions have partially matched with said content.

16. The integrated circuit chip of claim 1, wherein the complex symbols comprises a range detect symbol or a complement symbol or a symbol with some bits masked or a combination of the foregoing.