Signature search architecture for programmable intelligent search memory

• US 7,831,606 B2
• Filed: 12/06/2007
• Issued: 11/09/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,103
• Publication Number:
  US 20080140662A1
• Time in Patent Office: 1,069 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. Content search rules include of regular expressions which are compiled to finite state automata (FSA) and further include of patterns of strings a first set of which are compiled to a compressed signature database and a second set of which are compiled into FSAs. The finite state automata are then programmed in Programmable Intelligent Search Memory (PRISM) programmable FSA rule blocks and the compressed signature database is programmed in the PRISM signature search engines for evaluating content with the content search rules. A compiler compiles the content search rules for evaluation by PRISM memory. 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.

Claims

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

a. a symbol memory circuit to store said plurality of symbols;

b. a symbol evaluation circuit coupled to the said symbol memory circuit to evaluate match of the said plurality of symbols stored in the said symbol memory circuit with said plurality of input symbols of said content;

c. a state dependent vector (SDV) memory circuit to store state transition controls for said plurality of finite state automata;

d. a current state vector (CSV) memory circuit to store said plurality of states; and

e. a state transition circuit coupled to the said symbol evaluation circuit, 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 plurality of finite state automata.

2. The integrated circuit chip of claim 1, wherein the programmable signature search engines perform content search using said plurality of signature patterns, said plurality of signature patterns comprising a plurality of strings of characters of variable lengths, said plurality of signature patterns compiled into a compressed signature database by performing a plurality of hash operations using a plurality of hash functions, said plurality of hash functions to create a plurality of hash indices from said plurality of signature patterns, said compressed signature database having a memory bit set for each hash index generated from said plurality of signature patterns, said plurality of signature patterns further compiled to a plurality of FSAs into an exact signature match database used for performing exact signature match operations, said programmable signature search engines comprising at least one of each of:

a. a signature search controller to control said programmable signature search engines;

b. a content buffer to store a plurality of characters of said content;

c. a plurality of hash engines coupled to said content buffer to perform said plurality of hash operations on said plurality of characters of said content;

d. a signature hash memory coupled to said plurality of hash engines to store said compressed signature database;

e. a coarse match logic to perform a coarse match on a set of characters of said content using said compressed signature database coupled to said plurality of hash engines and said signature hash memory;

f. an exact match controller to perform exact signature match on said content that has a coarse match on said plurality of characters with said compressed signature database, said exact match controller to confirm a match in said content with at least one of said plurality of signature patterns;

or

g. a combination of any of a through f above.

3. The integrated circuit chip of claim 1, coupled to a programmable intelligent search memory (PRISM) compiler for the programmable intelligent search memory for compiling content search rules comprising a plurality of regular expression rules and a plurality of signature pattern rules for content search wherein said programmable intelligent search memory performs regular expression based and signature pattern based search.

4. The integrated circuit chip of claim 3, wherein the programmable intelligent search memory comprises one or more programmable finite state automata (FSA) rule memory circuit and one or more signature search engines, said PRISM compiler for compiling said regular expression rules into one or more programmable finite state automata data structure for programming into said one or more programmable FSA rule memory circuits and said PRISM compiler for further compiling said signature pattern rules in data structure for programming into said one or more signature search engines.

5. The integrated circuit chip of claim 4, coupled to the PRISM compiler, said PRISM compiler further comprising means to compile a first set of said signature pattern rules in data structure for programming into said one or more signature search engines and further comprising means to compile a second set of said signature pattern rules into a set of programmable finite state automata for programming in the said one or more programmable FSA rule memory circuits, said second set of said signature pattern rules comprising signatures with length less than a predetermined number of characters.

6. The integrated circuit chip of claim 5, wherein the programmable intelligent search memory for content search uses one or more regular expressions, said programmable intelligent search memory comprising a symbol memory circuit for storing symbols;

a state dependent vector memory circuit for storing state transition controls;

an initial vector memory circuit for storing initial vector; and

an accept state vector memory circuit for storing an accept state vector, said PRISM memory further comprising an array of randomly accessible PRISM memory locations to access the said one or more programmable finite state automata memory circuits, said one or more regular expressions comprising one or more symbols or characters, said one or more regular expressions compiled by said PRISM compiler into said one or more programmable finite state automata data structure representing the functionality of the said one or more regular expressions for programming in the said programmable intelligent search memory, said one or more finite state automata comprising a plurality of states, said plurality of states derived from the said one or more symbols of the said one or more regular expressions, said content comprising one or more input symbols provided as input to the said programmable intelligent search memory, said programmable intelligent search memory compiler to generate said one or more programmable finite state automata comprising at least one of each of;

a. a symbol representing at least one of the said one or more symbols for programming in the said symbol memory circuit;

b. a state dependent vector representing state transition controls for programming in said state dependent vector memory circuit;

c. an initial state vector to represent at least one initial state for programming in the said initial state vector memory circuit; and

d. an accept state vector to represent at least one accept state for programming in the said accept state vector memory circuit.

7. The integrated circuit chip of claim 6, coupled to the programmable intelligent search memory compiler, said compiler further comprising:

a. a read mechanism to read said one or more regular expressions;

b. a parse mechanism to parse said one or more regular expressions;

c. a syntax tree generation mechanism to generate syntax tree of said one or more regular expressions;

d. an error handling mechanism to handle errors in said one or more regular expressions;

e. a symbol extraction mechanism to extract said one or more symbols of said one or more regular expressions;

f. a marking mechanism to mark said one or more symbols of said one or more regular expressions;

g. a FSA linearization mechanism to create a linear FSA from said one or more programmable FSA;

h. a mechanism to find and extract first states of said linear FSA from said one or more states of said programmable FSA;

i. a mechanism to find and extract follow states of the said linear FSA from said one or more states of the said programmable FSA;

j. a mechanism to find and extract state transition list of the said linear FSA;

k. a mechanism to find and extract accept states of the said linear FSA from said one or more states of said programmable FSA;

l. a mechanism to create a PRISM programmable FSA data structure for said one or more regular expressions;

m. a mechanism to generate a compiled regular expression rules data base comprising said one or more programmable FSA data structures of said one or more regular expressions;

n. a mechanism to store or distribute said compiled regular expression rules data base;

o. a mechanism to generate a programmable FSA rule ID for programming said linear FSA in one specific memory location of said PRISM memory locations;

p. a mechanism to generate specific actions associated with said one or more regular expression rules when a particular regular expression of said one or more regular expression rules that is programmed in the PRISM FSA rule blocks is matched;

or

q. any combination of the above.

8. The integrated circuit chip of claim 7, wherein the FSA linearization mechanism further comprises marking said one or more symbols of said one or more programmable FSAs with unique integers.

9. The integrated circuit chip of claim 7, wherein the FSA linearization mechanism comprising further comprises a mechanism to create determinants of said linear FSA to detect presence or absence of an empty string in a language defined by said one or more regular expressions.

10. The integrated circuit chip of claim 3, wherein the content search rules comprise rules that are:

a. Application layer rules to detect content from an application layer of an OSI stack;

b. Network layer rules to detect content from a network layer of an OSI stack;

c. Storage area networking rules to detect content in a storage area network;

or

d. a combination of the foregoing.

11. The integrated circuit chip of claim 10, wherein the content search rules further comprise rules that are:

a. Anti-spam rules for detecting spam messages in the said content;

b. Anti-virus rules for detecting viruses in the said content;

c. Anti-spyware rules for detecting spyware in the said content;

d. Digital rights management rules for detecting digital rights compliance or violation in the said content;

e. Anti-phishing rules for detecting information indicating phishing attempts in the said content;

f. Intrusion detection rules for detecting information indicating intrusions from the said content;

g. Extrusion detection rules for detecting information indicating extrusions from the said content;

h. Legal compliance detection rules for detecting information that may violate legal compliance rules from the said content;

i. Worm detection rules for detecting computer worms from the said content;

j. Instant message inspection rules for detecting malware in the said content which is an instant messaging content;

k. XML security rules for detecting security compliance or violation of the said content which is a XML content;

l. VOIP rules for detecting VOIP security violation from the said content;

or

m. a combination of any of the foregoing.

12. The integrated circuit chip of claim 10, wherein the storage area networking rules comprise:

a. Logical unit number (LUN) masking rules for controlling storage area network traffic to allow or deny access to specific LUNs;

b. Zoning rules for enforcing zones in a storage area network;

c. Frame filtering rules to filter frames in a storage area network;

d. Logical block addressing rules for controlling access to specific logical block addresses in a storage area network;

or

e. a combination of any of the foregoing.

13. The integrated circuit chip of claim 10, wherein the network layer rules comprise:

a. Access control rules for controlling access to a network;

b. Network address rules for controlling access to or from specific network addresses of a network;

c. Port specific rules for controlling access to specific network ports of a network;

d. Protocol specific rules for checking protocol violations of a network protocol operating on a network;

or

e. a combination of any of the foregoing.

14. The integrated circuit chip of claim 5, coupled to the programmable intelligent search memory compiler, said compiler further comprising:

a. a read mechanism to read said plurality of signature patterns;

b. a signature length detection mechanism to determine the length of each of the said plurality of signature patterns;

c. said signature length mechanism separating out the said plurality of signature patterns into said first set of signature patterns to be compiled into data structure for programming into said one or more signature search engines and further separating the said plurality of signature patterns into said second set of signature patterns for programming into said one or more finite state automata rule memory;

d. a hash index generation mechanism to generate a plurality of hash indices for each of the said first set of signature patterns using a plurality of hash functions;

e. a compressed signature database generation mechanism coupled to said hash index generation mechanism to set said compressed signature database entries at said hash indices to an active value used to indicate presence of a potential coarse signature match during said content search;

f. a Aho-corasick Finite Automata (ACFA) or Deterministic FSA (DFA) generation mechanism to generate a plurality of composite ACFA or composite DFA from all of said second set of signature patterns wherein each of said plurality of composite ACFA or composite DFA are generated for all signature patterns that have the same first hash index of said plurality of hash indices, said plurality of composite ACFA or composite DFA for use in exact signature match during said content search forming an exact match signature database;

g. a mechanism to generate a compiled signature pattern database comprising said compressed signature database and said exact match signature database;

h. a mechanism to store or distribute the said compiled signature pattern database for programming into said one or more signature search engines;

i. any combination of the above.

15. The integrated circuit chip of claim 2, wherein the programmable intelligent search memory, performs the process of said content search on a stream of content presented to the said programmable intelligent search memory using said plurality of signature patterns, said process comprising:

a. said signature search controller reading or receiving or a combination the said stream of content for said content search;

b. said signature search controller writing said stream of content to said content buffer;

c. said plurality of hash engines retrieving a plurality of characters from said content buffer and generating a plurality of hash indices from said plurality of characters using a plurality of hash functions;

d. said plurality of hash engines retrieving content of memory locations corresponding to said plurality of hash indices from said signature hash memory and providing said content of memory locations to said coarse match logic;

e. said coarse match logic detecting each of said content from memory locations corresponding to said plurality of hash indices are set active and asserting a coarse match signal indicating a coarse match of said content stream with at least one signature of said compressed signature database;

f. said exact match controller coupled to said coarse match signal to detect said coarse match and perform an exact signature match detection using Aho-corasick Finite Automata (ACFA) or Deterministic FSA (DFA) walk of said exact signature match database comprised of said ACFA or DFA data structure to confirm using said exact signature match detection a signature match in said content with at least one of said plurality of signature patterns;

or

g. any combination of the above.

16. The integrated circuit chip of claim 1 embedded in a hardware processor system for accelerating at least one content search application, said hardware processor system comprising at least one integrated circuit microprocessor as a central processing unit to run an operating system comprising kernel layer services and application layer services, said application layer services comprising a application programming interface to couple said content search application to said programmable intelligent search memory, content search operations of said content search application offloaded from said integrated circuit microprocessor to said integrated circuit chip comprising said programmable intelligent search memory, said programmable intelligent search memory further comprising a plurality of regular expression programmable search engines for accelerating regular expression search and further comprising at least one programmable signature search engine to accelerate signature search, said content search application requiring search using a set of variable length signatures or search using a set of regular expressions or a combination thereof.

17. The integrated circuit chip of claim 16, embedded in a hardware processor system for accelerating at least one content search application, wherein the content search application comprises one of the applications from anti-spam, anti-virus, anti-spyware, anti-phishing, intrusion detection, extrusion detection, digital rights management, legal compliance, worm detection, instant message inspection, VOIP security, XML document security and search, genetics, proteomics, XML, XML based protocols like XMPP, web search, database search, bioinformatics, signature recognition, speech recognition, or web indexing application.

18. The integrated circuit chip of claim 17, embedded in a hardware processor system for accelerating at least one content search application, wherein the content search application is adapted for running on said hardware processor to use said regular expression acceleration or said signature pattern acceleration capabilities of said programmable intelligent search memory, said content search application adaptation comprising:

a. Updating application source code by marking said content search operation code in distinct section; and

b. Compiling said updated application source code using a PRISM content search acceleration aware compiler to generate a content search acceleration aware object code;

Said object code for loading on said integrated circuit microprocessor for use by a loader of said operating system, said operating system loader setting up said PRISM with application content search operations like regular expressions or signatures or a combination and said content search application sending content to be searched to said PRISM content search acceleration integration circuit chip to accelerate said content search application.