Runtime adaptable search processor

• US 20060136570A1
• Filed: 12/30/2005
• Published: 06/22/2006
• Est. Priority Date: 06/10/2003
• Status: Active Grant

• Current Assignee: Memory Access Technologies LLC
• Original Assignee: Protocol Acquisition LLC
• Inventors: Pandya, Ashish A.
• Granted Patent: US 7,685,254 B2
• Time in Patent Office: Days
• US Class Current: 709/217
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 9/30029 Logical and Boolean instructions, e.g. XOR, NOT
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms
• CPC Class Codes: H04L 63/20 for managing network security; network security policies in general filtering policies H04L63/0227
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 69/12 Protocol engines
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/161 Implementation details of TCP/IP or UDP/IP stack architecture; Specification of modified or new header fields
• CPC Class Codes: H04L 69/32 Architecture of open systems interconnection [OSI] 7-layer type protocol stacks, e.g. the interfaces between the data link level and the physical level

Abstract

A runtime adaptable search processor is disclosed. The search processor provides high speed content search capability to meet the performance need of network line rates growing to 1 Gbps, 10 Gbps and higher. he search processor provides a unique combination of NFA and DFA based search engines that can process incoming data in parallel to perform the search against the specific rules programmed in the search engines. The processor architecture also provides capabilities to transport and process Internet Protocol (IP) packets from Layer 2 through transport protocol layer and may also provide packet inspection through Layer 7. Further, a runtime adaptable processor is coupled to the protocol processing hardware and may be dynamically adapted to perform hardware tasks as per the needs of the network traffic being sent or received and/or the policies programmed or services or applications being supported. A set of engines may perform pass-through packet classification, policy processing and/or security processing enabling packet streaming through the architecture at nearly the full line rate. A high performance content search and rules processing security processor is disclosed which may be used for application layer and network layer security. scheduler schedules packets to packet processors for processing. An internal memory or local session database cache stores a session information database for a certain number of active sessions. The session information that is not in the internal memory is stored and retrieved to/from an additional memory. An application running on an initiator or target can in certain instantiations register a region of memory, which is made available to its peer(s) for access directly without substantial host intervention through RDMA data transfer. A security system is also disclosed that enables a new way of implementing security capabilities inside enterprise networks in a distributed manner using a protocol processing hardware with appropriate security features.

Claims

1. A runtime adaptable search processor operating on information content and having a plurality of hardware configurations, comprising:

a. a control processor and scheduler to control and schedule said information content for processing;

b. an adaptation controller to configure said runtime adaptable search processor configurations at runtime;

c. at least one configuration memory to store at least said plurality of hardware configurations;

d. at least one runtime adaptable NFA search engine for performing search on said information content using at least one NFA;

e. at least one runtime adaptable DFA search engine for performing search on said information content using at least one DFA; and

f. a combination of any of the foregoing.

2. The runtime adaptable search processor of claim 1 further comprising at least one of the following:

a. at least one search cluster comprising at least one search engine for searching information;

b. a global configuration controller for global configuration control;

c. a configuration memory controller for controlling accesses to at least said configuration memory;

d. an inter cluster routing switch for controlling routing between a plurality of said at least one search cluster;

e. a global memory for providing memory storage;

f. a global memory controller for controlling accesses to at least said global memory; and

g. a combination of any of the foregoing.

3. The runtime adaptable search processor of claim 2 wherein said at least one search cluster comprises:

a. a cluster configuration controller for configuring said at least one search cluster;

b. at least one runtime adaptable search engine for searching information; and

c. a configurable cluster interconnect network for connecting a plurality of said at least one runtime adaptable search engine.

4. The runtime adaptable search processor of claim 2 wherein said at least one search cluster further comprises at least one of the following:

a. a cluster memory for providing memory storage;

b. a cluster memory controller for controlling at least said cluster memory;

c. a cluster routing switch for interconnecting said at least one runtime adaptable search engine to said at least one search cluster or said inter cluster routing switch;

d. a cluster flow controller for at least storing and retrieving flow context; and

e. a combination of any of the foregoing.

5. The runtime adaptable search processor of claim 3 wherein said at least one runtime adaptable search engine comprises at least one of the following:

a. a runtime adaptable NFA search engine for performing search using at least one NFA;

b. a runtime adaptable DFA search engine for performing search using at least one DFA;

or

c. a combination of the foregoing.

6. The runtime adaptable search processor of claim 1 wherein said at least one runtime adaptable NFA search engine evaluates at least one said NFA and comprises:

a. at least one state logic block to perform state logic operations for a state;

b. at least one application state memory to store application state information;

c. at least one symbol detection logic to detect a symbol;

d. at least one application state controller to control the operation of said at least one runtime adaptable NFA search engine; and

e. a combination of any of the foregoing.

7. The runtime adaptable search processor of claim 1 wherein said at least one runtime adaptable NFA search engine further comprises at least one of:

a. pattern substitution control to perform pattern substitution;

b. counters to provide counters for various events;

c. match logic to detect a rule match;

d. FSA extension logic to enable said runtime adaptable NFA search engine to support larger FSAs and

e. a combination of any of the foregoing.

8. The runtime adaptable search processor of claim 1 wherein said at least one runtime adaptable DFA search engine comprises:

a. at least one DFA operations engine to perform state logic operations;

b. at least one DFA instruction and state flow memory to store DFA operation instruction and state flow of instructions;

c. at least one DFA state controller to control the operation of said at least one runtime adaptable DFA search engine; and

d. a combination of any of the foregoing.

9. The runtime adaptable search processor of claim 1 wherein said at least one runtime adaptable DFA search engine further comprises at least one of:

a. pattern substitution control to perform pattern substitution;

b. counters to provide counters for various events;

c. a DFA context controller to control the application context of said DFA search engine;

d. DFA extension logic to enable said runtime adaptable DFA search engine to support larger FSAs; and

e. a combination of any of the foregoing.

10. The runtime adaptable search processor of claim 6 wherein said at least one state logic block comprises:

a. a state dependent vector (SDV) used to enable or disable interconnect between said state and one or more states of said NFA;

b. a current state vector (CSV) representing the current state of some of said one or more states of said NFA that said state depends on for its next state;

c. a received symbol vector (RSV) representing the value of said symbol received as input to said symbol detection logic;

d. a left-biased or right-biased signal that indicates the NFA type;

e. a state transition logic that uses at least said SDV, said CSV, said RSV, and said left-biased or right-biased signal to generate the next state value for said state;

f. an init logic block to control the value of the next state for said state;

g. a state memory to store the value of said state;

h. an accept detect logic to detect and signal when said state is an accept state and is activated; and

i. a combination of any of the foregoing.

11. The runtime adaptable search processor of claim 6 wherein said at least one state logic block further comprises at least one of the following:

a. a programmable storage for said SDV to enable runtime configuration of said SDV;

b. a programmable storage for said left-biased (LB) or right-biased (RB) signal to enable runtime configuration of a realized NFA type;

c. a programmable storage for storing a start flag to indicate if said state is a start state of said NFA;

d. a programmable storage for storing an accept flag to indicate if said state is an accept state of said NFA;

e. a programmable storage for storing an action field to indicate the action that should be taken when said state is activated or reached during said NFA evaluation;

f. a programmable storage for storing a tag field to indicate a tag that is issued when said state is activated or reached during said NFA evaluation; and

g. a combination of any of the foregoing.

18. The runtime adaptable search processor of claim 6 wherein said at least one application state memory comprises at least one application state context that represents the context information to be programmed in said NFA search engine when said at least one application state context is selected to be configured in said NFA search engine;

wherein the application state context comprises NFA parameters which are applicable to all states of said NFA, and at least one set of state parameters being applicable to each state of said at least one state of said NFA or a combination of the foregoing.

20. The runtime adaptable search processor of claim 1 embedded in a system for operating on network packets or on local content, said system capable of being coupled to a network, wherein said runtime adaptable search processor processes content embedded within said network packets or within said local content, said runtime adaptable search processor further comprising runtime adaptable search processor array hardware to dynamically select hardware configurations within said runtime adaptable search processor to support application or service processing needs of said network packets or said local content.

12. A runtime adaptable finite state automaton architecture having a plurality of states, comprising:

a. at least one interconnect between any two of said plurality of states;

b. a state dependent vector (SDV) for each of said plurality of states that is used to enable or disable of said at least one interconnect between said two states and other states of said plurality of states;

c. a current state vector (CSV) for each of said plurality of states representing the current state of some of said plurality of states which the state of said plurality of states depends on for its next state evaluation;

d. at least one symbol associated with each of said plurality of state to control the transition into or out of said each of said plurality of states;

e. at least one symbol detection logic for receiving symbols, detecting the value of said symbols and generating a received symbol vector (RSV);

f. at least one application state memory to hold an application context that uses said finite state automaton;

g. a state transition logic for each of said plurality of states that uses at least said state dependent vector, said current state vector, and said received symbol vector to generate the next state for each of said plurality of states; and

h. a combination of any of the foregoing.

13. The runtime adaptable finite state automaton (FSA) of claim 12 further comprises at least one of the following:

a. a programmable storage for SDV to enable runtime configuration of SDV;

b. a programmable storage for a left-biased (LB) or right-biased (RB) signal to enable runtime configuration of the realized FSA type;

c. a programmable storage for storing a start flag to indicate if said state is a start state of said FSA;

d. a programmable storage for storing an accept flag to indicate if said state is an accept state of said FSA;

e. a programmable storage for storing an action field to indicate the action that should be taken when said state is activated or reached during said FSA evaluation;

f. a programmable storage for storing a tag field to indicate a tag that is issued when said state is activated or reached during said FSA evaluation; and

g. a combination of any of the foregoing.

14. A system for operating on network packets or on local content, said system capable of being coupled to a network, said system comprising a runtime adaptable search processor to process content embedded within said network packets or within said local content.

15. The system of claim 14 wherein said runtime adaptable search processor further provides runtime adaptable search processor array hardware to dynamically select hardware configurations within said runtime adaptable search processor to support application or service processing needs of said network packets or said local content.

16. The system of claim 14 comprising a content search API to enable applications to utilize the runtime adaptable search processor hardware to accelerate content search;

wherein the content search API comprises means to initialize said runtime adaptable search processor;

means to communicate content search rules to said runtime adaptable search processor;

means to communicate the content to be searched by said runtime adaptable search processor;

means to communicate the results of said content search by said runtime adaptable search processor to said applications;

means to start and stop said runtime adaptable search processor to start and stop content search; and

a combination of any of the foregoing.

17. The system of claim 14 wherein said runtime adaptable search processor enables email security applications comprising anti-spam;

anti-virus;

anti-spyware;

anti-phishing;

confidential leak prevention;

or regulatory compliance;

or a combination of the foregoing;

or web security applications comprising firewall;

intrusion detection and prevention;

application layer security;

anti-spam;

anti-virus;

anti-spyware;

anti-phishing;

confidential leak prevention;

or regulatory compliance;

or any combination of the foregoing;

wherein said applications can be performed at network line rates;

wherein said network line rates lie within a range of line rates from below 100 Mbps to ₁₀ Gbps and higher.

19. The system of claim 14 wherein said runtime adaptable search processor receives data packets from a network and sends data packets to a network, and further provides capability to select:

a. policy based services, applications or policies or a combination thereof;

b. user selected services, applications or policies or a combination thereof;

c. user defined services, applications or policies or a combination thereof;

d. user configured services, applications or policies or a combination thereof; and

e. a combination of any of the foregoing;

on the data packets received from said network, on the data packets sent to said network, or on a combination of thereof.