Complex Symbol Evaluation for Programmable Intelligent Search Memory

• US 20080140632A1
• Filed: 12/06/2007
• Published: 06/12/2008
• Est. Priority Date: 12/08/2006
• Status: Active Grant

• Current Assignee: Infosil Inc.
• Original Assignee: Ashish A. Pandya
• Inventors: Pandya, Ashish A.
• Granted Patent: US 7,827,190 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• 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. A memory architecture comprising programmable intelligent search memory for content search wherein said programmable intelligent search memory performs regular expression based search wherein said regular expression comprises complex symbols.

2. An integrated circuit chip comprising programmable intelligent search memory for content search wherein said programmable intelligent search memory performs regular expression based search wherein said regular expression comprises complex symbols.

4. An integrated circuit chip of claim 2 comprising a processor comprising memory, said memory comprising said programmable intelligent search memory for content search, wherein said programmable intelligent search memory performs regular expression based search wherein said regular expression comprises complex symbols.

5. The programmable intelligent search memory of claim 2 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. symbol memory circuit to store said one or more symbols;

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

c. 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. 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. state dependent vector memory circuit to store state transition controls for said one or more finite state automata;

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

g. 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.

6. The symbol memory circuit, the complex symbol memory circuit, the state dependent vector memory circuit, current state vector memory circuit of the programmable intelligent search memory of claim 5 comprises of static random access memory circuits.

7. The programmable intelligent search memory of claim 5 further comprises at least one of:

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. 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. 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. start state vector memory circuit to store initialization values of said one or more states;

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

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

or

h. Any combination of a through g above.

8. Programmable intelligent search memory of claim 7 comprises of memory circuits that are each independently addressable in a random order.

9. The programmable intelligent search memory of claim 5 further comprising circuits to couple said programmable intelligent search memory to at least one functional block or circuit or a combination.

10. The at least one functional block of claim 9 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.

11. The symbol evaluation circuit of claim 5 comprising 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.

12. A plurality of one or more symbol match signals of claim 11 coupled together to form a composite match signal.

13. The composite match signal of claim 12 to indicate 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.

14. The one or more finite state automata of claim 5 are non deterministic finite state automata or tagged non deterministic finite state automata or deterministic finite state automata or a combination thereof.

15. The one or more finite state automata of claim 5 are 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.

16. The one or more finite state automata of claim 5 comprising 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.

17. The one or more finite state automata of claim 5 comprising 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.

18. The one or more finite state automata of claim 5 comprising 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.

19. The one or more finite state automata of claim 5 comprising 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.

20. The complex symbols of claim 5 comprises a range detect symbol or a complement symbol or a symbol with some bits masked or a combination of the foregoing.

3. A hardware processor comprising an integrated circuit chip memory said integrated circuit chip memory comprising programmable intelligent search memory for content search, wherein said programmable intelligent search memory performs regular expression based search wherein said regular expression comprises complex symbols.