KR20070087198A - Network Interfaces and Firewall Devices - Google Patents

Abstract

The network processing device provides a new architecture for performing firewall and other network interface management operations. In another aspect of the invention, an integrated policy management (UPM) structure uses the same memory and processing structure to integrate firewall policy management with routing and switching decisions. In another embodiment, if the reconstruction word processor (RSP) uses a parser to identify different word elements, the identified different word elements are used by one or more word processing units (SPUs) to generate different firewalls. , Network interfaces, routing, switching, and other packet processing operations.

Description

Network interface and firewall device

This application is filed under US Patent Application No. 11 / 187,049, filed July 21, 2005, entitled "Network interface and firewall device," July 22, 2005, entitled "Method and apparatus for detecting semantic elements using a push down automation." Part of U.S. Application No. 10 / 351,030, filed Jan. 24, 2003, which claims priority over U.S. Provisional Application No. 60 / 701,748, filed as title, and U.S. Provisional Application No. 60 / 639,002, filed December 21, 2004. Priority is claimed in US Patent Application No. 11 / 125,956, filed under the title "Intrusion detection system" of May 9, 2005, filed on a continuing application (CIP). All of which are incorporated herein by reference.

The openness of the Internet leads to various attacks on Internet access devices. This attack is effected by sending packet sequences that cause the target device to no longer function properly. These attacks can be categorized into categories such as stopping the target device, Denial of Service (DoS), and Distributed Denial of Service (DDoS), and the device can no longer be used or compromised. Or change files or software on the target device to act as a source of clone attacks in DoS.

Most attacks occur on devices connected to the public Internet and enter the workplace through the company's Internet connection. Some businesses have more than one connection point to the Internet. As such, network devices located at the interface between the two networks, also called firewalls, are used to defend against these attacks. For example, a firewall may be located between the public Internet and a private network, between two Internet Service Provider (ISP) networks, between two Local Area Networks, or some other two networks. If a firewall device is located at all connection points to the Internet, a perimeter firewall is created around the internal network and the devices.

The firewall is responsible for keeping unauthorized attacks out of the private network and, if possible, eliminating unauthorized transmissions that can occur from within the private network. Other uses of the firewall may include modifying information inside the packet. For example, a firewall can be used as a network address translator (NAT) for converting (translating) between public and private Internet protocol (IP) addresses.

Until now, firewall operations have been implemented primarily as embedded processors such as PowerPC®, or as a set of software modules that run on Intel® class x86 processors. The problem is that these hardware structures do not have the processing power to effectively implement such firewall operations. Thus, even if this is not possible, it is difficult to prevent or filter out all the various attacks by applying different rules to inspect each packet as it flows from source to destination to determine the validity of the packets.

The present invention addresses these and other problems associated with the prior art.

One network processing device provides a new architecture for performing firewall and other network interface management operations. In another aspect of the invention, a Unified Policy Management (UPM) structure uses the same memory and processing structure to integrate firewall policy management with routing and switching decisions. In another embodiment, a Reconfigurable Semantic Processor (RSP) uses a parser to identify different syntactic elements, where the elements are configured with different firewalls, network interfaces, routing, switching, and Used by two or more language processing units (SPUs) to perform other packet processing operations.

The above and other objects, features and advantages of the present invention will become more apparent from the following detailed description of the preferred embodiments of the present invention which proceeds with reference to the accompanying drawings.

1 is a block diagram of a network processing apparatus using a reconfigurable language processor (RSP).

2A is a block diagram illustrating RSP in more detail.

2B and 2C are more detailed views showing a parser table and a fabrication rule table used in the RSP.

3 illustrates how a denial of service (DoS) attack can render a network processing device unavailable.

4 shows how a firewall is associated with DoS attacks with different zones.

FIG. 5 is a more detailed view of the firewall shown in FIG. 4.

6 shows how memory in a firewall can be partitioned into different layers.

FIG. 7 is a flow chart showing how a firewall moves between the different layers shown in FIG.

8 is a flowchart illustrating how the firewall of FIG. 5 handles DoS attacks.

FIG. 9 is a block diagram illustrating how the RSP shown in FIG. 2A above is configured to handle DoS attacks.

10 and 11 are flowcharts illustrating how the RSP of FIG. 9 processes DoS candidate packets.

12 is a block diagram showing a firewall and a routing device that operate independently.

FIG. 13 is a diagram of a packet processing structure providing integrated routing and firewall policy management (UPM).

14 shows sample entries of an access control list (ACL) table.

15 is a flowchart illustrating how the packet processor of FIG. 13 provides a UPM.

16 is another example of a UPM table that provides forwarding actions based on higher layer packet characteristics.

17 is a block diagram illustrating an example of how the UPM can be used to route packets according to different URL values.

18 is an example of how uniform policy management is implemented in an RSP in an RSP.

19 is a flowchart illustrating how the RSP of FIG. 18 operates.

20 illustrates how RSP is used for Network Address Translation (NAT) and Port Address Translation (PAT).

FIG. 21 is a more detailed diagram showing how an RSP is configured for NAT / PAT translation and IP packet translation.

22 and 23 are flow charts showing how the RSP performs NAT / PAT translation.

24 shows how the RSP switches packets between IPv4 and IPv6.

25 is a flowchart showing how the RSP switches between IPv4 and IPv6.

26 and 27 show how RSP is used for Virtual Private Network (VPN) integration.

28 and 29 show how a firewall can be used to assign antivirus licenses for different sub-networks.

30 and 31 illustrate how multiple RSPs can be connected to each other for distributed firewall processing.

32A is a block diagram illustrating an intrusion detection system (IDS) implemented in a private network.

32B shows the limitations of a typical intrusion detection system.

32C illustrates one embodiment of the IDS of FIG. 32 that identifies sentence elements in the data stream and uses those sentence elements to identify risk factors.

33 is a block diagram illustrating how IDS is implemented using a resettable word processor (RSP).

34 is a flowchart showing how the IDS of FIG. 33 operates.

35 is a more detailed logic diagram of the IDS shown in FIG. 33.

FIG. 36 is a block diagram of the RSP shown in FIG. 33.

37 and 38 show how the Direct Execution Parser (DXP) in the RSP identifies packets containing email messages.

39 is a flowchart illustrating how the RSP applies risk factor filters to a data stream.

40 is a flowchart showing how an RSP performs a session lookup.

41 is a flowchart showing how the RSP generates tokens from an input stream.

42A is a flow diagram illustrating how the RSP reassembles divided packets before performing intrusion detection operations.

42B is a flow chart showing how the RSP rearranges TCP packets before performing intrusion detection.

43 and 44 show how the central intrusion detector correlates with tokens generated from different network processing devices.

45 shows how IDS is used to change information or to remove information from data streams.

46 shows a PushDown Automaton (PDA) engine.

FIG. 47 is a state diagram showing how the PDA engine of FIG. 46 performs URL search.

48 is a state diagram of a fish showing how the PDA engine uses the same number of fish states to search for a longer character string.

Figure 49 shows how the PDA engine uses only the state of one additional word to find elements of the additional word.

50-54 are detailed views illustrating an exemplary URL search method performed by the PDA engine.

55 shows how the PDA engine is implemented within a Reconfigurable Language Processor (RSP).

1 shows a private Internet Protocol (IP) network 24 connected to a public IP network 12 via a network interface device 25a. The public IP network 12 may be any wide area network (WAN) that supports packet switching. The private network 24 may be a company workplace network, an Internet service provider (ISP) network, a home network, or the like, which requires communication with the public IP network 12.

The network processing devices 25A-25D in the private network 24 may be any type of calculator device that communicates via a packet switched network. For example, network processing devices 25a and 25b may be routers, switches, gateways, firewalls, and the like. The endpoint 25C is a personal computer (PC) and the endpoint 25D is a server such as an internet web server. The PC 25C may be connected to the private network 24 via a wired connection, such as a wired Ethernet connection, or a wireless connection using, for example, the IEEE 802.11 protocol.

Reconfigurable processors (RSPs) 100 operate as any combination of network devices 25A-25D in private network 24. Different RSPs 100 collect and analyze network traffic 22 passing into and through the private network 24. The RSP 100A in the network processing apparatus is configured to operate in this example as a firewall and a general network interface of the private network 24. Although network interfaces and other general firewall operations to be described below are shown to be implemented in RSP 100, it should be understood that some of these operations may be implemented as other conventional computer structures.

In one embodiment, RSP 100A is configured to detect and protect against denial of service (DoS) attacks 16. An external PC 14 connected to the public IP network 12 may generate a DoS attack 16 intended to attack two or more of the network processing devices 25A-25D of the private network 24. RSP 100A monitors all incoming packets 20 received from public IP network 12 and discards any packets in packet stream 20 associated with DoS attack 16. In addition to detecting packets 16, RSP 100A may also perform other network interface operations 26 on packets 22 that are not discarded following DoS attack 16. For example, RSP 100A may be configured to detect and filter viruses and malware, network address translation (NAT), routing, statistical analysis, logging, and / or public IP network 12 and private IP network 24. It can support the packet conversion operations required for packets transmitted in between. All these operations will be described in more detail below.

In another example, RSP 100 may be installed in other network processing devices located internally within private network 24 or at any other primary access point into private network 24. For example, RSP 100B may be located at server 25D to provide operations 26 for similar authentication, routing, statistical analysis, and the like, which will be described in more detail below. Alternatively, some of the packet operations 26 may be performed in the RSP 100B and not in the RSP 100A. For example, the RSP 100B may perform statistical analysis or DoS filtering in addition to any other packet analysis filtering and packet translations performed by the RSP 100A.

Any other network processing devices 25B and 25C in the private network 24 may also include one or more RSPs 100 configured to perform any of the operations described below. A platform using the RSP 100 is a wireless personal digital assistant (PDA) that receives packets or other data streams over a wireless interface such as cellular code division multiplexing access (CDMA) or time division multiplexing access (TDMA), 802.11, Bluetooth, and the like. ), A wireless cell phone, a wireless router, a wireless access point, a wireless client, and so forth.

Reconfigurable Semantic Processor (RSP)

FIG. 2A shows a block diagram of a processor (RSP) 100 of reconfiguration words used in one embodiment for implementing firewall and other network interface operations described below. RSP 100 includes an input buffer 140 for buffering packet data streams received through input port 120 and an output buffer 150 for buffering packet data stream output through output port 152.

Direct Execution Parser (DXP) 180 may process packets or frames (eg, input “stream”) received at input buffer 140, output to output buffer 150 (eg, output “stream”), and Control recycle (eg, recycle "stream") in recycle buffer 160. The input buffer 140, the output buffer 150, and the recycle buffer 160 are preferably first-in-first-out (FIFO) buffers.

DXP 180 also controls the processing of packets by a verbal processing unit (SPU) 200 that handles data transfer between buffers 140, 160 and 160 and memory subsystem 215. Memory subsystem 215 stores packets received from input port 120 and access control list (ACL) to CAM 220 used for Unified Policy Management (UPM) operations and other firewall operations described below. Save the table too.

RSP 100 uses at least three tables to perform a given firewall operation. Codes 178 for retrieving a Production Rule 176 are stored in a Parser Table (PT) 170. The grammatical generation rules 176 are stored in a production rule table 190 (PRT) 190. The code segments 212 executed by the SPU 200 are stored in a Semantic Code Table (SCT) 210. Codes 178 in parser table 170 are stored, for example, in a row-column format or a content-addressed format. In the row-column format, the rows of parser table 170 are indexed by non-terminal code NT 172 provided by inner parser stack 185. The columns of parser table 170 are indexed by input data value DI [N] 174 extracted from the data head of input buffer 140. In the content addressable format, concatenation of the non-terminal code 172 from the parser stack 185 and the input data value 174 from the input buffer 140 defines the input to the parser table 170. do.

The generation rule table 190 is indexed by codes 178 from the parser table 170. Tables 170 and 190 define a generation rule 176 in which a query to parser table 170 may be applied to non-terminal code 172 and input data value 174, as shown in FIG. 2A. Can be linked to return immediately. The DXP 180 replaces the non-terminal code at the top of the parser stack 185 with the generation rule (PR) 176 returned from the PRT 190 and resumes parsing data from the input buffer 140.

The lexical code table 210 is also indexed according to the codes 178 generated by the parser table 170 and / or the generation rules 176 generated by the generation rule table 190. In general, the parsing results cause the DXP 180 to load a semantic entry point (SEP) routine 212 from the fish code table 210 in a predetermined generation rule 176 to load the SPU ( To determine whether or not it should be executed by

SPU 200 has several access paths to memory subsystem 215, which provides a structured memory interface addressable with contextual symbols. The memory subsystem 215, the parser table 170, the generation rule table 190, and the erroneous code table 210 include on-chip memory, synchronous dynamic random access memories (DRAMs) and content (CAM). External memory devices such as addressable memories, or a combination of such resources. Each table or context will only support a contextual interface to the physical shared memory space with one or more of the other tables or contexts.

A Maintenance Central Processing Unit (MCPU) 56 is coupled between the SPU 200 and the memory subsystem 215. The MCPU 56 performs some desired functions for the RSP 100 that can be rationally accomplished as traditional software and hardware. These functions are usually irregular and time-sensitive functions that do not guarantee inclusion in the SPU 200 because of their complexity. It is also desirable for the MCPU 56 to have a function that requests the SPU 200 to perform tasks for the MCPU.

Memory subsystem 215 includes array machine-context data memory (AMCD) 230 that accesses data in DRAM 280 via a hashing function or a content-addressed memory (CAM) lookup. do. The ciphertext block 240 encrypts, decrypts, or authenticates the data, and the context control block cache 250 caches the text control blocks going to or coming from the DRAM 280. The general cache 260 caches the data used for basic operations and the streaming cache 270 caches the data streams as they are written to or read from the DRAM 280. The context control block cache 250 is preferably a software controlled cache, ie the SPU 200 determines when the cache line is used and freed. Each of the circuits 240, 250, 260, and 270 is connected between the DRAM 280 and the SPU 200. TCAM 220 is coupled between AMCD 230 and MCPU 56 to include an Access Control List (ACL) table and other parameters in a manner that substantially enhances firewall functionality.

Detailed design optimizations for the operation blocks of the RSP 100 are described in co-pending application 10 / 351,030 entitled Reconfigurable Semantic Processor, filed Jan. 24, 2003, the content of which is incorporated herein by reference. Included as.

For firewall and network interface operations RSP  use

The firewall and other network interface operations 26 described above in FIG. 1 are implemented via RSP 100 using grammar rules and semantic entry point (SEP) routines 212. The packets arrive at the input port 120 of the RSP device 100, are parsed through grammar table entries in the parser table 170, and semantically processed by the SEP routines 212. SEP routine 212,

1. receive the packet as it is and forward it to the output port 152;

2. Drop the packet from further processing and do not forward it;

3. change the packet and then forward it to output port 152;

4. Hold the packet and wait for further packets in the session to arrive, then determine the final nature of the packet;

5. You will decide to direct the packet to a specific destination or pass it back through the RSP for further processing.

The grammar rules of the parser table 170 are configured to allow acceptable packets to pass through and to warn of any known or suspected anomalies to the SPU 200. An example of a grammar for determining pass or fail is the setting of TCP flags. The TCP flag field contains 8 bits in it and only certain combinations are valid. Grammar rules are coded in parser table 170 to allow all allowable TCP settings and reject unacceptable TCP settings. For example, TCP SYN and FIN messages that are both set in the same packet are not valid combinations and are therefore directly excluded by DXP 180.

Certain unacceptable packets or operations may only be determined by the supporting SEP routines 212. These mostly include the state of the session and protocol. One example would be to send a TP data payload segment before sending it via a corresponding TCP SYN message. In this example, SEP routine 212 will exclude packets from memory 280 during TCP sessions that do not follow a TCP SYN message.

Using parser grammars in conjunction with the SEP code 212 provides excellent performance, which allows the direct execution parser 180 to immediately reject or non-attack packets without consuming additional cycles in the SPUs 200. This is because packets can be redirected around DoS processing. Traditional firewalls have to check each packet against a list of "bad" rules. This increases over time as new attacks are discovered. In contrast, the parser grammar may be written to describe and allow only good packets to pass through the RSP 100. Thus, bad packets are automatically filtered or processed directly by the SPUs 200. This provides better scaling for packet monitoring operations.

RSP  Parser and Generation Rule Tables

RSP 100 operation as a firewall or an integrated policy manager (UPM) will be better understood through specific examples. In the example described below, the RSP 100 supports DoS filtering of TCP packets. However, those skilled in the art will appreciate that the concepts illustrated below are naturally applicable to any type of firewall operation for any data stream transmitted using any communication protocol. Similar concepts can also be readily applied to the integrated policy management (UPM) operations described below.

Firewall and UPM operations include parsing and detecting syntax for an input data stream and will be described with reference to FIGS. 2B and 2C. Referring first to FIG. 2B, codes associated with several different grammars may exist simultaneously in the parser table 170 and the generation rule table 190. For example, the codes 300 are related to media access control (MAC) packet header format parsing, the codes 302 are related to IP packet processing, and another set of codes 304 is a transmission control protocol ( TCP) packet processing. Other codes 306 of the parser table 170 are associated with other firewall or denial of service (DoS) operations, which will be described in more detail below.

PR codes 178 are used to access the corresponding generation rule 176 stored in the generation rule table 190. Input values 308 (eg, non-terminal (NT) symbol 172 combined with current input values DI [n] when n is a match width in any selected byte unit), unless required by a particular lookup configuration. Need not be assigned to the PR table 170 in any particular order.

In one embodiment, parser table 170 also includes an addresser 310 that receives NT symbol 172 and data values DI [n] 174 from DXP 180. The addresser 310 associates the NT symbol 172 with the data value DI [n] 174 and applies the concatenation value 308 to the parser table 170. Conceptually this is useful for viewing the generation rule table 170 as a matrix with one PR code 178 for each unique combination of NT code 172 and data values 174, although the invention is so limited. Does not. Other types of memory and memory schemes may also be suitable for other applications.

In one embodiment, parser table 170 is configured as a content addressable memory (CAM), where addresser 310 uses NT code 172 and input data values DI [n] 174 as one key. To allow the CAM to find the PR code 178. The CAM is preferably a ternary CAM with ternary CAM (TCAM) entries. Each TCAM entry has an NT code 312 and a DI [n] match value 314. Each NT code 312 may include several TCAM entries.

Each bit of the DI [n] match value 314 may be set to "0", "1", or "X" (represents "don't care"). 178 enables the parser table 170 to require that only certain bits / bytes of DI [n] 174 match a coded pattern, so that the parser table 170 can find one match.

For example, one row of TCAM contains NT code NT_TCP_SYN 312A for TCP SYN packets followed by additional bytes 314A indicating the contents that may be present in the TCP SYN packet, such as the destination IP address and TCP message identifier. can do. The remaining bytes of this TCAM row are set to "don't care". Thus, NT_TCP_SYN 312A and DI [N] of certain bytes are provided to the parser table 170, where DI [N] when the first set of bytes of DI [N] contains a TCP SYN message identifier. No matter what the rest of the bytes in] contain, there will be a match.

The TCAM of the parser table 170 provides a PR code 178A corresponding to a TCAM entry that matches NT 172 and DI [N] 174, as described above. In this example, the PR code 178A is associated with a TCP SYN packet. The PR code 178A may be sent back to the DXP 180, directly to the PR table 190, or both. In one embodiment, the PR code 178A is the row index of the TCAM entry that provided the match.

2C illustrates a possible configuration for the generation rule table 190. In this embodiment, addresser 320 receives PR codes 178 from DXP 180 or parser table 170 and NT symbols 172 from DXP 180. The received NT symbol 172 is preferably the same NT symbol 172 sent to the parser table 170, which was used to locate the received PR code 178.

The addresser 320 uses these received PR codes 178 and NT symbols 172 to access the corresponding generation rules 176. The addresser 320 may not necessarily be necessary in some configurations, but may be part of the DXP 180, part of the PRT 190, or an intermediate operation block when used. The addresser may not be needed, for example, if the parser table 170 or the DXP 180 directly generates addresses.

The generation rules 176 stored in the generation rule table 190 include three data segments. These data segments include symbol segment 177A, SPU entry point (SEP) segment 177B, and skip byte segment 177C. These segments may be fixed length segments or variable length segments that are preferably null-terminated. The symbol segment 177A includes terminal and / or non-terminal symbols that are pushed over the parser stack 185 (FIG. 2A) of the DXP. SEP segment 177B includes SPU entry points (SEPs) used by SPU 200 to process segments of data. In one configuration described below, SEP segments 177B may correspond to ACL predicates and other syntax structure elements identified in the currently parsed packet.

The skip byte segment 177C contains the skip byte value used by the input buffer 140, incrementing its buffer pointer to advance the processing of the input stream. Other information useful for processing generation rules may also be stored as part of generation rule 176.

In this example, one or more generation rules 176A indexed as generation rule code 178A match the TCP SYN packet identified in input buffer 140. The SEP segment 177B, when executed by the SPU 200, as described below with reference to Figures 4-11, performs the DoS operation on the identified TCP SYN packet, which is the lexical code table 210 of Figure 2A. C) SPU code 212.

In one embodiment, SPU 200 includes an array of words processing elements that can be operated in parallel. SEP segment 177B of generation rule 176A sets one or more SPUs 200 to perform the same firewall operation on different packets or to perform different firewall operations on the same packet in parallel. It will be apparent that similar operations may be used to detect any other type of packet or data identifier that may be necessary for any of the firewalls, network interfaces, or UPM operations described below.

As discussed above, the parser table 170 may also include other grammars associated with or without TCP SYN packets. For example, the IP grammar 302 included in the parser table 170 is associated with an identified NT_IP destination address in the input buffer 140 that is used in conjunction with the identified TCP SYN message to perform DoS processing. Generation rule codes 178 (see FIGS. 4-11 below).

The matching data values 314 in the generation rule codes 302 may include the destination IP address of the network processing device located in the private network 24 of FIG. 1. If the input data DI [n] 174 associated with the NT_IP code 172 does not have a destination address included in the match values 314 for the PR codes 302, then the generation rule table 190 defaults to the generation rule. Code 178 may be provided. The default generation rule code 178 may point to the generation rule 176 in the generation rule table 190 as long as the DXP 180 and / or SPU 200 commands the packet to be discarded in the input buffer 140. .

Denial of Service (DoS)

3 shows how DoS attack 16 endangers network processing device 406. In general, the purpose of DoS deterrence is to prevent malicious packets from being accessed by network processing devices in private network 24. The following discussion discusses one example of a DoS attack involving flooding a network device with multiple packets. However, there are several other types of hostile attacks involving one or several hostile packets. For example, other hostile attacks may involve one or several packets that interfere with normal operation of the network processing device protocol stack. One of these hostile attacks against a network processing device or network is hereinafter referred to generally as DoS attacks, all within the scope of the system of the present invention.

Referring to FIG. 3, the attacker device 14, which is typically, but not necessarily, external to the private network 24, causes the private network 24 to flood with several packets 16. In one example, by the attacker computer 14, massive Transmission Control Protocol (TCP) Synchronization (SYN) packets 400 are sent to the destination address of the private network 24. In another example, the attacker 14 may send massive packet fragments 402 to the destination address of the private network 24. In either case, the packets 16 allow one or more network devices 406 of the private network 24 to retain the statuses of the TCP SYN packet 400 received differently and for each set of received packet fragments ( To hold states 410 for 402.

TCP SYN attacks 400 and packet fragment attacks 402 are only some examples of the many different types of DoS attacks possible. For example, an attacker may indicate network devices by sending TCP Finish (FIN) packets or duplicate packet fragments. In other port-based DoS attacks, a worm can reside within a device on the private network 24, which is then managed by the attacker 14 to send fake messages from within the private network 24. do. DoS attacks may also occur via Internet Control Message Protocol (ICMP) messages.

Each time a new TCP SYN packet 400 is received by the network processing device 406, a new TCP session state 408 is retained and the corresponding TCP ACK message 404 is sent to the transmitting device (attack 14). Sent again. However, the attacker 14 will ignore the TCP ACK response 404 and continue to send new TCP SYN messages 400 to the private network 24. The attacker 14 also inserts a fake source address into the TCP SYN messages 400, causing the network device 406 to send the TCP SYN ACK messages 404 to another computer feed, which becomes the prey. The subject is then burdened to handle the massive flood of TCP SYN ACK messages 404.

The network processing device 406 is required to hold the TCP states 408 corresponding to each TCP SYN message 400 for some predetermined period of time. Holding such a large number of fake TCP states 408 exhausts resources in network device 406 such that processing of other legitimate IP traffic is severely slowed or the legitimate IP traffic is missed.

Under similar scenarios, the attacker 14 can send packet fragments 402 with associated sequence numbers. The network processing apparatus 406 must retain the states 410 until each packet fragment 402 in the sequence is received, or until some timeout time expires. The attacker 14 may intentionally exclude the packet fragments 402 from the sequence. This requires the network device 406 to maintain states 410 for each set of packet fragments for a duration of timeout time.

The conventional technique for dealing with this type of DoS attacks is to limit the rate of incoming packets 16. For example, the network processing apparatus 406 may identify the destination addresses for all TCP SYN packets. TCP SYN packets for a particular destination address are excluded when the number of received packets increases above a certain rate.

However, continuously monitoring and tracking each DoS attack consumes substantial device resources. The network processing device 406 must monitor all incoming packets for each possible DoS risk factor. For example, the network processing device 406 must identify each TCP SYN packet and each packet fragment. This one is also processing intensive. However, the network processing device 406 must also track the number and rate of similarly received packets and, if necessary, exclude similar types of packets that have reached the DoS rate threshold. One problem is that current computer architectures do not have the capacity to perform these DoS operations at the current network line speed.

Referring to FIG. 4, the firewall 420 more effectively identifies and counters DoS attacks by rate limiting packets in a unique manner. In the description below, any packet that may be part of a DoS attack is called a DoS candidate packet. For example, TCP SYN packets can be used in one DoS attack. Thus, one TCP SYN packet is identified by the firewall 420 as a DoS candidate packet. Fragmented packets can be used for DoS attacks as much as possible, and are therefore also identified as DoS candidate packets by firewall 420.

Firewall 420 rate limits the DoS candidate packets according to the associated destination addresses. Identification and management of destination addresses for each possible DoS attack may require substantial processing resources. However, the architecture used for firewall 420 is more efficient and scalable than previous firewall architectures, allowing for the monitoring and removal of a significant amount of different DoS attacks at high line speeds.

Zones

Policy management can assign different zones to network processing devices or networks. These different areas may be associated with, for example, external network and internal network interfaces in the network processing device. These areas can be determined according to network policy management considerations regardless of DoS operations. However, one aspect of firewall 420 takes into account the different interface areas previously specified by the policy manager when analyzing DoS risk factors.

For example, first region 1 may be associated with public IP traffic received from public network 12 via interface 426. The second zone 2 may be associated with a semi-trusted virtual private network (VPN) that is received over the public network 12 via the VPN tunnel 424. For example, VPN tunnel 424 may be established between private network 24 and home computer 422. Home computer 422 may be operated by an employee of an entity operating private network 24. The third zone 3 may be associated with the highly trusted IP traffic generated internally from the private network 24 and received via the interface 428.

Each zone is associated with a different level of confidence and therefore assigned different DoS rate limits. DoS rate limiting refers to the number of certain types of DoS candidate packets (such as certain types of packets including TCP SYN messages) that have the same destination address and are allowed to pass through firewall 420 during a particular time period. After the rate limit is reached, any additional packets with the same DoS type and destination address are excluded. For example, packets received from zone 1 via interface 426 are associated with the lowest confidence level because they are received from untrusted sources over public network 12. Thus, packets received from region 1 may be assigned a lower DoS rate limit than other regions.

Region 2 has an intermediate confidence level because it is assumed that packets are received from one known source 422. Accordingly, the region 2 may be assigned a higher DoS ratio limit than the region 1. For example, during a given time period, a greater number of TCP SYN packets with the same destination address than area 1 may be allowed to pass through area 2. In this example, area 3 has the highest level of trust since all packets received by interface 428 come from devices located inside private network 24. Accordingly, higher DoS rate limits may be assigned to packets received in region 3.

Areas associated with the received packets can be identified according to source address or port information. For example, RSP 100 or any other processing device in firewall 420 may determine regions associated with incoming packets based on the associated source address VLAN ID and / or interface from which the packet was received. Firewall 420 then manages DoS attacks based in part on the identified packets related areas. For example, packets associated with potential DoS risk factors may be counted, managed, and rate limited according to their related areas. This allows firewall 420 to more effectively allocate DoS resources to different interfaces according to their associated level of trust. This will be explained in more detail below.

Referring to FIG. 5, one embodiment of the firewall 420 shown in FIG. 4 includes a processor 442 that receives an incoming packet stream 440 as long as it can include DoS and non-DoS candidate packets. do. Processor 442 first identifies packets (DoS candidate packets) in packet stream 440 that may be associated with a DoS attack. For example, the processor 442 may identify any incoming packet fragments or packets containing a TCP SYN message as a DoS candidate packet.

Processor 442 accesses table 464 to identify region 468 associated with the identified DoS candidate packets. For example, the processor 442 can match a port value entry 466 in the table 464 with a port value in the identified DoS packet. The processor then identifies the region 468 in the table 464 associated with the matched port number entry 466.

Processor 442 combines the destination address 472 and associated region value 468 for the identified DoS packet as the address into CAM (Content Addressable Memory) 444. CAM 444 includes DoS entries 445 that are a combination of destination address values and area values. Address locations in the CAM are used as pointers to the static random access memory (SRAM) 450.

Memory locations in the SRAM 450 are partitioned into fields that include a DoS attack flag 452, a time stamp 454, a layer value 456, and an offset 458. DoS attack flag 452 is set whenever the number of packets for a particular destination address exceeds a predetermined DoS rate limit. As discussed above, the DoS ratio limit can be customized for different regions 448.

The time stamp 454 is set each time a new entry is added to the TCAM 444 and reset each time the duration of the time stamp extends beyond a certain DoS time period. The layer value 456 is used by the processor 442 to allocate and manage DoS entries of the TCAM 444, the SRAM 450, and the Dynamic Random Access Memory (DRAM) 462. The offset value 458 is used as a pointer to the DRAM 462. DRAM 462 includes a series of counters 460 that track the number of packets for specific destination addresses received by firewall 420 during the DoS period.

Processor 442 identifies to DoS candidate packets 475 that may potentially be part of a DoS attack. The destination address 472 and area value 468 for the newly identified packet 474 are used as the address to the CAM 444. Since the new DoS candidate packet 474 will not match any existing entries, the processor 442 adds a new DoS entry 445 for the packet 474 into the CAM 444.

The corresponding DoS attack flag 452 for the new DoS entry in the CAM 444 is cleared and the time stamp 454 is set to the current time value. The layer value 456 is set to any layer value currently operating in the processor 442 as described in more detail below with reference to FIG. 6. The processor 442 uses the address offset value 458 to increment the corresponding counter 460 in the DRAM 462 to one. Processor 442 then processes the next packet in packet stream 440.

Packets in the packet stream that do not meet the criteria for a possible DoS attack are not identified as DoS candidate packets 441. For example, packets 441 may be generic IP packets that are not packet fragments and that do not contain a TCP SYN message. In this case, processor 442 allows packets 441 to pass through firewall 420 without any further DoS processing.

The next packet in the packet stream 440 may be identified as a possible DoS attack (DoS candidate packet). In this example, the next identified packet may already contain the corresponding DoS entry in the CAM 444. For example, one or more TCP SYN packets or packet fragments with similar destination addresses may have been previously received by firewall 420 during the same DoS period. As such, the destination address 472 and region 468 for that packet will correspond to one of the entries in the CAM 444. The address 449 corresponding to the matching CAM entry 445 is now used as the address to the SRAM 450.

Processor 442 first checks DoS attack flag 452 in SRAM 450. If DoS attack flag 452 is set, processor 442 excludes the packet in packet stream 440. If necessary, the processor 442 may now update the time stamp 454 and layer value 456.

If the DoS attack flag 452 is not set, the processor 442 allows related packets in the packet stream 440 to pass through the firewall 420. Processor 442 now updates DoS state information in SRAM 450 and DRAM 462. For example, processor 442 increments the corresponding counter 460 in DRAM 462 and then compares time stamp 454 with the current time value. If the time stamp 454 is not too old, the corresponding value of the counter 460 in the DRAM 462 is valid and compared with the DoS rate limit. If the counter value 460 is below the DoS rate limit, the processor 442 moves to the next packet processing in the packet stream 440.

If the time stamp 454 is too old when compared to the current time value, the corresponding count value 460 of the DRAM 460 is invalidated and reset to zero. The time stamp 454 is also reset to the current time value. This effectively resets the count 460 during each predetermined time period. If time stamp 454 is valid (not too old) and incremented count 460 in DRAM 462 is greater than or equal to the DoS rate limit, processor 442 sets the corresponding DoS attack flag 452. This causes the processor 442 to exclude similar packets with the same destination address.

Generation

The layer value 456 is used to manage DoS entries in the CAM 444, SRAM 450, and DRAM 462. Referring to the example of FIG. 6, the CAM 444 is logically divided into four different hierarchical sections 480. However, this is merely a configuration, and the system can be configured with any number of hierarchical sections with any configurable size.

The processor 442 of FIG. 5 identifies and manages DoS attacks more efficiently by inserting and removing DoS entries in accordance with layers 480. 5-7, at operation 490, processor 442 begins entering DoS entries into current layer 480. This is shown in FIG. 6 where DoS entries 482 are entered into the current layer 0. At operation 492, processor 442 removes one entry 484 from the next layer 1 for all entries 482 added to current layer 0. This allows the CAM 444 to always have space available when the template processor 442 moves to the next layer.

DoS entry 482 may already exist in CAM 444. In this case, processor 442 switches the layer value 456 currently assigned for the existing DoS entry in operation 494 to the current layer. For example, DoS entry 482 is received while processor 442 is operating at layer zero. DoS entry 482 may match an existing DoS entry 489 currently assigned to Layer 2. At operation 494, processor 442 switches existing DoS entry 489 from layer 2 to layer 0. DoS entry 489 does not physically move to another location within CAM 444, but logically moves to layer 0 when processor 442 reassigns layer value 456 in SRAM 450 from 2 to 0. do.

Moving existing DoS entries to the current layer ensures that active DoS entries that may exist within a relatively long time CAM 444 are not discarded by the processor 442. For example, DoS attacks can last for extended periods of time. Each newly received packet for the same DoS attack will update an existing DoS entry in the CAM 444 with the current layer value. This causes DoS entries that represent an active DoS attack to be removed from the CAM 444 other older DoS entries that have not been completed up to a DoS attack or no longer exhibit an active DoS attack.

In operation 496, processor 442 determines when switching to the next layer 480 should be made. Various events may cause the processor 442 to move to the next layer. Processor 442 will move from operation 498 to the next layer when all entries in the current layer are full. This can happen, for example, when an attacker sends many TCP SYN messages with different destination addresses.

Processor 442 will also move to the next layer in operation 498 when the predetermined time has expired. This ensures that all time stamps 454 (FIG. 5) are in accordance with the current time tracked by the processor 442. For example, time stamps 454 in SRAM 450 combined with associated count values in DRAM 462 determine the rate at which packets are being received for different destination addresses. After the time stamp period expiration, the processor 442 must reset both the time stamp value 454 and the associated count value 460.

However, after the current time value used by processor 442 is rolled over and reset back to zero, old DoS entries may be tentatively left in CAM 444. In this case, the processor 442 may add the count values corresponding to the previous time stamp period to the counter 460 of the DRAM 460 by mistake. This may mislead the counter 460 to count packets over several time stamp periods, which may mislead DoS attack detection. In other words, counting packets over several time stamp periods provides an incorrect indication of the actual packet rate.

To solve this potential rollover problem, processor 442 automatically moves to the next layer after some predetermined time, regardless of the number of entries in the current layer, at operation 496. This predetermined timing is less than the rollover time stamp period used by the processor 442 when multiplied by the total number of layers (in this example, the total number of layers).

For example, processor 442 may have a current timer that rotates once every four seconds. The predetermined time period used to move to the next layer can be set to 0.5 seconds. This allows all stagnant DoS entries in CAM 444 to be removed every two seconds. Thus, processor 442 is confident that all time stamps 454 in SRAM 450 will be associated with the same time stamp period. This also has the unexpected advantage that SRAM 450 makes a smaller number of bits available for time stamps 454. In other words, the time stamp values 454 only need a sufficient number of bits to track the time somewhere around 2 seconds or more.

If neither size limit nor time stamp period is reached in operation 496, processor 442 continues to fill the current layer with new DoS entries and reassign existing DoS entries to the current layer (operations 490-494). When the size or time stamp limit is reached (operation 496), the processor 442 moves to the next layer (operation 498) and begins adding entries to the new layer. For example, processor 9442 begins moving new DoS entries 486 into layer 1 and thus removing existing DoS entries 488 from the next layer 2.

Streamlined DoS attack identification

Referring briefly to FIG. 5, when an incoming packet 440 is identified at the CAM 444, to determine if several similar packets reach a DoS attack threshold within the time traced by the time stamp 454. It is necessary to increment the associated counter 460 of the DRAM 462. However, the amount of time required to access DRAM 462 may delay DoS attack determination and subsequent packet exclusion. This in turn can delay the processing of other packets through the firewall 420. DoS attack flag 452 is used by processor 442 to quickly identify DoS packets that are part of the current DoS attack.

5 and 8, DoS attack flag 452 is used in conjunction with other processing operations to reduce delays in identifying and processing DoS attacks. At operation 540, processor 442 receives the packets. At operation 542, processor 442 determines whether the received packet includes a new destination address and zone that is not currently included as a DoS entry in CAM 444.

If no entry exists in CAM 444 beforehand, the packet is immediately allowed to pass through firewall 420. Since the packet is not currently identified within CAM 444, it cannot be part of the current DoS attack and therefore will not be excluded. After the packet is allowed to pass, the processor 442 performs DoS maintenance operations after the event. This ensures that other packets following the identified packet are not unnecessarily delayed.

Upon repairing "after the event", processor 442 adds a new DoS entry to the current layer at operation 546 and removes a DoS entry from the next layer at operation 548 as described above with reference to FIGS. 6 and 7. In operation 550, processor 442 clears DoS attack flag 452 (if not already cleared), sets new time stamp value 454, sets current layer value 456, and executes DRAM ( Increment the corresponding counter 460 in 462.

If necessary, the processor 442 swaps the current layer at operation 552. For example, as described above, the processor 442 changes the current layer when all entries in the current layer are full, or after a predetermined time stamp period expires. Since the time stamp 454 for the new DoS entry has just been set, the time stamp period will not expire, but the new DoS entry may reach the current DoS entry limit for the current layer.

Referring again to operation 542, processor 442 may receive a packet with a destination address and region corresponding to an existing DoS entry in CAM 444. DoS attack flag 452 in SRAM 450 that matches the matching CAM entry is read by processor 442 immediately at operation 560. If the corresponding DoS attack flag 452 is set, the packet is immediately dropped at operation 580. A packet is not excluded by not outputting it, but ultimately by overwriting it in memory.

If necessary, the processor 442 updates the information in the SRAM 450 in operations 582-586. However, since the DoS attack flag 452 is already set, the processor 442 need not increment the associated counter in the DRAM 462. For example, at operation 582, processor 442 may update the layer value 456 for the DoS entry to the current layer. In operation 584, processor 442 now determines whether time stamp 454 has expired. For example, if the time difference between the current time stamp value tracked by processor 442 and time stamp 454 is greater than some predetermined time (eg, 1 second), time stamp 454 is the current time stamp value. Is reset. Accordingly, the associated counter value 460 and the DoS attack flag 452 may be cleared (operation 586).

Since the time stamp 454 only needs to be reset frequently (eg once per second), the count value of the DRAM 462 will just need to be accessed often (operation 586). This is particularly important because DRAM 462 requires a longer access time than SRAM 450. Therefore, the time required by the processor 442 for DoS maintenance is reduced. Nevertheless, since DoS maintenance operations are performed after the packet is already excluded (operation 580), other incoming packets 440 (FIG. 5) will not be unnecessarily delayed by the processor 442. This allows the firewall 420 to filter packets at gigabit or faster line rates without substantially slowing down processing of other legitimate packets during a DoS attack.

At operation 560, the packet may include an existing DoS entry in CAM 444 but the associated DoS attack flag 452 is not set. At operation 562, the packet is allowed to pass through the firewall. If necessary, the processor 442 updates the hierarchical information for the matching DoS entry in the CAM 444 in operation 564. For example, the existing layer 456 identified in the SRAM 450 is set to the current layer. If necessary, the processor 442 may change the current layer at operation 564, as previously shown in FIGS. 6 and 7, when the layer time period has expired or the maximum number of layer entries in the current layer has reached a certain limit.

The counter 460 for an existing DoS entry is incremented at operation 566 and the processor 442 checks the count value 460 and the age of the associated time stamp 454 (operation 568). If the time stamp value is older than the time stamp period (expired time stamp) (operation 570), count 460 and time stamp 454 are reset (operation 572).

If the time stamp is valid (operation 570), processor 442 determines at operation 574 whether counter 460 exceeds the DoS attack threshold. If not, processor 442 returns to operation 540 and processes the next identified DoS candidate packet for a possible DoS attack. If the counter 460 crosses the DoS attack threshold, the DoS attack flag 452 is set (operation 576).

In one embodiment, the DoS attack flag 452 is set after the associated packet has already passed through the firewall 420. This one additional packet is generally not enough to disturb the target device operation of the private network 24 (FIG. 3). However, the ability to send packets through firewall 420 without having to wait for completion of DoS management operations substantially improves firewall performance. In addition, since the operations described above will be performed only for packets related to possible DoS attacks (DoS candidate packets), the amount of processing required for DoS management and monitoring is another firewall structure that processes all received packets for possible DoS attacks. Substantially less than

RSP  My DoS implementation

5, any processor 442 can be used to implement the firewall system described above. However, to further improve performance, the processor 442 on one embodiment is implemented using the processor (RSP) 100 of the reconstruction word described above in FIGS. 2A-2C. 9 illustrates in more detail how the RSP 100 is used for DoS prevention. For simplicity of explanation, some of the processing elements in RSP 100 described above in FIGS. 2A-2C are not shown in FIG. 9.

Incoming packets 600 are received in input buffer 140. DXP 180 includes a grammar identifying packets 600 (DoS candidate packets) that may be associated with a possible DoS attack in associated parser table 170 (FIG. 2A). For example, the parser grammar may identify any incoming packets 600 including TCP SYN messages, TCP FIN messages, packet fragments, and the like. When one DoS candidate packet is identified, DXP 180 sends DoS identification message 602 to SPU 200. The message 602 launches the DoS SEP code 620 executed by the SPUs 200 from the SCT 210. DoS SEP code 620 causes SPUs 200 to perform the different DoS operations described above with reference to FIGS. 3-8.

Memory subsystem 215 includes DRAM 462, CAM 444, and SRAM 450 shown previously in FIG. 5. In one configuration, Array Machine-Context Data Memory (AMCD) 230 is used to access data in DRAM 462 or SRAM 450 via a hashing function or content-addressable memory (CAM) 444.

AMCD 230 includes a free table 604, each of which includes bits 605 associated with an entry in CAM 444. Any unused entry in CAM 444 is represented by zero bit 605 and any valid DoS entry in CAM 444 is represented by one related bit 605 of free table 604. The AMCD 320 supports a Find First Zero (FFZ) instruction from the SPUs 200 that identify the first zero bits of the free table 604.

When a location of the CAM 444 needs to be identified to load a new DoS entry, the SPUs 200 execute an FFZ instruction against the free table 604. The FFZ instruction returns the position of the first zero bit in free table 604, which is then used as a pointer to that entry in CAM 444. SPU 200 loads the destination address and area for a new packet into the address location identified by CAM 444.

As described above in FIG. 6, DoS entries are added to the current layer of CAM 444 and other DoS entries are concurrently removed at the next layer. SPU 200 uses layer tables 608 to quickly identify which entries of CAM 444 should be removed from the next layer. Each layer in CAM 444 includes an associated layer table 608A-D. Each valid DoS entry in CAM 444, associated with a particular layer, includes a corresponding zero bit set in the associated layer table 608. For example, the third entry of CAM 444 includes a DoS entry associated with layer 0. Accordingly, SPU 200 sets the third bit in layer table 608A to zero.

If DoS entries need to be removed for layer 0, SPU 200 performs an FFZ operation on layer table 608A. The third bit in the hierarchical table 608A is identified and then used by the SPUs 200 to invalidate the corresponding third DoS entry in the CAM 444. For example, the SPU 200 sets the third bit in the hierarchical table 608A to 1 and the third bit in the free table 604 to zero. Of course, this is only one example of how tables 604 and 608 work. Other table settings can also be used.

As discussed above, these DoS maintenance operations that identify the entries available within CAM 444 and which entries to remove from CAM 444 are such that SPUs 200 have already passed relevant packets through RSP 100. It can be done after disabling or allowing it.

The memory subsystem 215 may also include a table 606 used by the SPUs 2000 to identify the areas previously identified by the policy manager, for example, packets may be stored by the DXP 180. The SPU 200 compares the port number with the packet tag 610A in the table 606 to identify the area 610B that receives the packet. It may also include packet rates 610C associated with each zone to identify DoS attacks, generating time stamps for each DoS entry in SRAM 450 and when the time stamp period of each time stamp expired. A timer 612 is used by the SPUs 200 to determine the hierarchy table 614 to identify the current hierarchy.

RSP 100 may also identify and discard any packet with fake IP addresses. For example, a series of IP addresses are reserved as multicast destination addresses. Any packets received with the source address corresponding to the reserved multicast addresses can be detected by the DXP 180 and immediately excluded.

10 and 11 illustrate, at a high technical level, how the RSP 100 implements the above-described DoS operations. Referring specifically to FIGS. 10 and 11 and generally referring to FIG. 9, at operation 650, DXP 180 parses incoming packets 600. The grammar in parsing table 170 is used by DXP 180 to identify any DoS candidate packets (operation 652). At the same time, the DXP 180 may instruct the SPUs 200 to store the incoming packet 600 in the DRAM 462 or temporarily store the packet in the input buffer 140. DXP 180 also identifies the destination address of the packet and the area where the packet was received in operation 654.

When the DoS candidate packet is identified, the DXP 180 sends a signaling 602 to the SPUs 200 in operation 656 to load the DoS SEP code 620 associated with the required DoS operation. For example, SEP code 620 may be associated with a particular type of DoS operation associated with an identified TCP SYN packet or an identified packet fragment.

In operation 658, the SPU compares the identified destination address and related area information with entries in CAM 444. If a corresponding DoS entry is present in the CAM 444 (operation 660), the SPU 200 performs the DoS operations described through FIG. 11 below. If no DoS entry currently exists in the CAM 444, the SPU 200 allows the packets to pass through the firewall in operation 662. This may simply mean that the SPU 200 continues any other required firewall processing for that packet in the DRAM 462 before sending the packet to the output buffer 150. Or, if it is not stored in the DRAM 462, the SPU 200 allows a packet in the input buffer 140 to be stored in the DRAM 462 for further processing.

SPU 200 now performs any necessary DoS maintenance. For example, at operation 664, SPU 200 reads table 614 in AMCD 320 to determine which layer is currently active (active) for the relevant DoS operation. SPU 200 also reads tables 604 and 608 to determine where to add new DoS entries to CAM 444 and which DoS entries to exclude from the next layer. In operation 666, SPU 200 updates CAM 444 with a new DoS entry and reads the contents of the corresponding memory location in SRAM 450. Finally, at operation 668, SPU 200 updates the time stamp and layer information in SRAM 450 and the count information in DRAM 462.

Referring to FIG. 11, when the destination address and area for a packet are already DoS entries of CAM 444, SPU 200 reads the corresponding memory location of SRAM 450 in operation 700. SPU 200 checks to see if the DoS attack flag is set in operation 702. If the DoS attack flag is set, in operation 704 the SPU immediately excludes the packet from DRAM 462 or input buffer 140. For example, SPU 200 may set a drop flag in DRAM 462 indicating that the packet is invalid.

Invalid packets are now never read from DRAM 462 and ultimately overwritten with other data. When not yet stored in DRAM 462, the packet is excluded from input buffer 140. If the DoS attack flag is not set, the SPU immediately releases the packet for further processing in operation 706. For example, this packet may be immediately passed from the input buffer 140 to a specific location in the DRAM 462. If already in DRAM 462, this packet is sent to another SPU 200 for further firewall processing, or to output buffer 150 if no further firewall processing is needed. Alternatively, SPU 200 may send this packet from DRAM 462 to recycle buffer 160 for reparsing by DXP 180. For example, DXP 18 will then identify other content in the packet associated with other firewall operations.

At operation 708, SPU 200 updates the information in SRAM 450 and increments the relevant count 460 in DRAM 462 if necessary. SPU 200 updates some essential information in tables 604, 606, 608, and 614 at operation 710. SPU 200 then waits for new SEP instructions 602 from DXP 180.

Integrated firewall / routing management (integrated policy management)

Referring to FIG. 12, the firewall 804 operates between the first network 800 and the second network 82. Firewall 804 supports various network interface operations. For example, in addition to identifying and filtering DoS attacks as described above, the firewall must convert packets between different network formats, such as between IP version 4 (IPv4) and IP version 6 (IPv6), And packets between private IP addresses (network address translation (NAT)). Firewall 804 may be required to perform other virus detection and security operations.

Another separate network computing device 806, such as a router or switch, must then route or switch packets that have passed through the firewall 804. For example, packets received from router / switch 806 may be forwarded to other routers or switches 808 that further forward those packets to other network processing devices in network 812. Router or switch 806 may route packets to endpoints such as server 810 or personal computer (PC) 814.

The problem with this conventional structure is that the firewall device 804 and the routing device 806 autonomously operate. Thus, separate processing and memory resources are needed for each device 802 and 806. This not only increases the hardware cost of the edge facility, but also limits scalability and can prevent these edge devices from processing packets at the desired line rates.

For example, firewall 804 may need to monitor all incoming packets for possible TCP SYN packets. As mentioned above, this will require the firewall 804 to identify the destination address for each incoming packet. TCP SYN packets that are not part of the DoS attack are now forwarded to the router 806. The router 806 then must again determine the destination addresses of the packets 806 received from the firewall 804 to route the packets to the appropriate destination. Thus, each of the network processing devices 804 and 806 must perform some of the same packet processing operations for the same packets. Eventually, each device 804 and 806 must have separate packet states, packet buffers, and so forth. This limits the overall scalability and processing capacity of the network processing devices, as described above.

Referring to FIG. 13, another aspect of the present invention uses Unified Policy Management (UPM) in the network processing device 820 to process packets more efficiently. In one example, the UPM integrates conventional firewall and edge device operations with packet forwarding operations that have so far been performed by separate, independently operating processors. In one configuration, a unique access control list (ACL) table is used by the processor 822 to provide various various UPM operations.

The processor 822 receives the incoming packet stream 802 and identifies a predicate set 854 associated with the individual packets 821. The set of predicates 854 is described in more detail below with reference to FIG. 14, but may generally be some information in received packets that may be associated with a firewall or a transfer operation. For example, predicate set 854 may include, but is not necessarily limited to, IP addresses, TCP port numbers, IP protocol identifiers, and the like. The predicate set 854 is, on another unique aspect of the present invention, a session initiation protocol (SIP), a pan-resource locator (URL), a simple messaging transport protocol (SMTP), a hypertape transfer protocol (HTTP), a file transfer protocol ( It may include higher open system interconnect (OSI) layer information such as FTP) information and other application layer information such as attachment and other text document identification.

The access control list (ACL) table 840 is organized according to different combinations of predicate entries 850 that may be associated with different UPM or other firewall operations. For example, the first firewall policy ACL set 848 may include different denial of service (DoS) operations that determine whether incoming packets 821 are allowed or disallowed to pass through the network processing device 820. Can be associated. Firewall policy ACLs 848 may also be used for other packet translation, authentication, and filtering operations to be performed by network processing device 820, such as network address translation (NAT), virus detection and filtering, IP version translation, and the like. It can be associated with.

In another particular unique configuration, the ACL table 840 may also include a forward information base (FIB) 842 that associates different destination addresses 844 with different destination port numbers 846. . FIB 842 may reside in a separate section of ACL table 840 and / or may be integrated with a portion of firewall policy ACLs 848 as described in more detail below.

ACL entries in the table 840 also include actions 852 that manage the processor 822 to allow or deny related packets to pass through the network processing device 820. Other ACL actions 852 may direct related packets to a specific destination or back through processor 822 for further processing. Under other circumstances, the firewall policy action 852 may direct the processor 822 to cause the associated packet 821 to be routed to a particular output port 8456.

The combination of the FIB 842 and the firewall policy ACLs 848 of the table 840 supports various different UMP operations that are not normally performed in the same network processing device 820. For example, a small subset of UPM operations includes exclusion packets 838 as described above for DoS or Intrusion Detection. The network processing apparatus 820 may change or tag the packets before being sent towards the destination address. For example, packets 824 may be encapsulated within a particular tunnel 826, titled to a particular QoS level, or the like.

In another UMP action, entries in the ACL table 840 may direct the processor 822 to log statistics to the server 828 for any passed or dropped packets 830. In other UMP operations, as briefly mentioned above, the entries in the ACL table 840 may cause the processor 822 to send packets 834 to different sub-networks 832 or devices 836 according to different firewall policy metrics. Can be delivered as For example, packets 834 containing a particular HTTP session may be routed to server 836 while all other packets are routed to subnet 832.

In the above description of FIG. 13 and the following more detailed description, routing and switching are used interchangeably. Those skilled in the art will appreciate that the UPM system 820 may perform integrated layer-2 switching and / or layer-3 routing operations in combination with other firewall policy metrics, as described in more detail below. will be.

Access control list

FIG. 14 shows typical entries of the ACL table 840 described above in FIG. 13. Any combination of predicates and actions may be combined with each other in the ACL table 840, and FIG. 14 shows only some examples thereof. In one embodiment, processor 822 (FIG. 13) links one or more predicates together and uses the combined set of predicates 854 as an address entry into the CAM that includes ACL table 840. The action associated with the action for the first entry that matches the predicate set 854 provided by the processor 822 in the ACL table 840 is output by the CAM.

Initial entry 860 of ACL table 840 includes destination IP address predicate 860A, source IP address predicate 860B, TCP port number predicate 860C, establishing TCP session predicate 860D, and allow. Action 860E. In this example, ACL 860 is the first entry of ACL table 840. Of course, any sequence or combination of ACL entries may be loaded into the ACL table 840.

The relevant action 860E is output from the ACL table 840 when the set of predicates 854 provided by the processor 822 matches the predicates 860A-860D. In this example, the ACL table 840 shows the allow action 860E when the destination IP address and source IP address for the incoming packet 821 (FIG. 13) match values in the predicates 860A and 860B, respectively. Outputs The IP addresses identified in the predicates 860A and 860B may include only subnet addresses associated with intact IP source and destination addresses. Additional bits in the IP address are masked with "don't care" values, similar to how subnet masks are currently used in routing tables.

To match ACL entry 860, packet 821 (FIG. 13) must also include the associated TCP port number that matches predicate 860C. Note that no source or destination qualifier is associated with the TCP port number predicate 860C. This means that the same source TCP port number C or the same destination TCP port number C in the packet 821 will match the predicate 860C. Finally, to match the ACL entry 860, the incoming packet 821 must be part of an already established TCP session, as requested by the established TCP predicate 860D. Predicate 860D may simply be a flag in predicate set 854 set by processor 822 when it is determined that incoming packet 821 is part of an already established TCP session. Thus, the ACL entry 860 will not match a packet containing a TCP SYN message that attempts to establish a new TCP session.

The next two ACL entries 862 and 864 are tied to firewall policies related to denial of service (DoS) attacks. To match ACL entry 862, the address in incoming packet 821 must match destination and source IP address predicates 862A and 862B, respectively. Incoming packet 821 must also be a TCP packet requested by type TCP predicate 862C. ACL entry 862 associates the specific destination and source IP addresses for a TCP packet with a TCP DoS action 862D that conforms to a particular region as described above in FIG. Thus, action 862D commands processor 822 to perform the DoS operations described above in FIGS. 4-11 using a particular packet rate threshold that matches region 1. FIG.

ACL entry 864 is associated with TCP DoS action 864D and includes the same destination IP address predicate 864A as destination IP address predicate 862A. However, predicate 864B includes a source IP address C that is different from source IP address predicate 862B. This corresponds to packets that can be received from other network interfaces. Thus, ACL action 864D is for a TCP DoS operation with another corresponding region 3. The processor 822 may use different packet rate thresholds for determining DoS attacks when receiving the action 864D.

ACL entry 866 relates to the transition from IPv4 to IPv6. For example, incoming packets 821 may be received over a network operating using IPv6. However, a network operating on the other network processing device 820 may use IPv4. As such, the network processing apparatus 820 may need to convert all IPv6 packets into IPv4 packets.

The IP type field in the IP header of the incoming packet 821 identifies the packet as either IPv4 or IPv6. The processor 822 extracts the IP destination address and IP version identifier in the IP type field from the packet 821, and formats the information into a set of predicates 854 applied to the ACL table 840. When the predicate set 854 matches the predicates 866A and 866B in the ACL entry 866, the processor 822 receives the XLATE IPv6 action 866C. XLATE action 866C instructs processor 822 to convert the incoming IPv6 packet 821 to IPv4 using specific rule 5. For example, IPv6-Rule 5 allows the processor 822 to encapsulate an IPv6 packet into an IPv4 header, or split portions of IPv6 addresses into different company and host codes included in the IPv4 header. The transition between IPv6 and IPv4 will be described in more detail below with reference to FIG. 24.

ACL entries 868 and 870 are associated with policy based routing or switching operations. ACL entry 868 includes forwarding information base (FIB) routing criteria 868A and 868C combined with firewall policy metrics 868B. Similarly, ACL entry 870 includes FIB routing criteria 870A and 870C combined with firewall policy metric 870B. These ACL entries 868 and 870 allow the network processing device 820 to route or switch packets to different ports based on both IP destination addresses and firewall policy metrics.

For example, ACL entry 868 causes forwarding action 868C to direct processor 822 to output incoming packet 821 to port 3 for TCP packet types 868B with destination IP address G. Include. However, ACL entry 870 commands processor 822 to send UDP packet types 870B with the same destination IP address G to another output port 4. Such policy based routing ACLs may be used to route TCP bus risk factors, for example, to a specific processing device for further DoS processing, while UDP packets are routed towards a destination address corresponding to predicate 870A. The entries in the ACL table 840 are, of course, only a small sample of the various ACLs that can be used to perform integrated policy management.

FIG. 15 illustrates in more detail how the network processing apparatus 820 of FIG. 13 performs UPM. At operation 880, processor 822 receives the incoming packets 821 and generates predicate set 854 from the incoming packets at operation 882. For example, processor 822 identifies, extracts, and formats a set of IP packet fields into predicates in a predetermined order. If one of the IP packet fields is not present in the incoming packet 821, the next packet field on the list is extracted and combined with the previously extracted and formatted predicates.

The processor 822 applies the predicate set 854 to the ACL table 840 in operation 884 and receives and executes the action received from the predicate entry that matches in the ACL table 840 in operation 886. For simplicity, only three action categories from the ACL table are described in FIG. 15. However, any number of different actions can be composed of ACL entries. If a drop action 852 is received in the ACL table 840 at operation 892, the processor discards the packet (operation 900). Processor 822 will log some statistical information related to the excluded packet before starting processing for the next input packet 821 (operation 902).

If a pass action 852 is received from the ACL table (operation 890), the processor will route or switch the packet according to FIB 842 (FIG. 13) at operation 898. Pass-through action 890 may include a transport port number, or may direct processor 822 to re-access ACL table 840 to obtain this transport port information.

When a steer ACL action 852 is received from the ACL table (operation 888), the processor performs the firewall operation associated with this ACL action in operation 894. If applicable, processor 822 may send the packet according to the firewall policy metric as it relates (operation 894). For example, as described above with reference to FIG. 14, the steering action 852 may instruct the processor to send TCP packets through a particular port to a network processing device that checks for DoS attacks.

Alternatively, steering action 852, identified at operation 888, may cause processor 822 to perform additional firewall processing on the packet. For example, steering action 852 may also cause processor 822 to perform network address translation (NAT). Accordingly, processor 822 may extract another predicate set 854 from packet 821 if necessary (operation 882) and reapply the new predicate set 854 to ACL table 840 (operation 882). Operation 884). Depending on the next ACL action 852 received in the ACL table 840, the processor 822 may drop, pass, or steer the packet after the NAT operation.

Packet transmission according to higher OSI layers

16 illustrates another example of how routing and switching operations are integrated with firewall policy management. The ACL table 910 is similar to the ACL table 840 of FIG. 13. However, the ACL table 910 combined the forwarding information base (FIB) with layer 4 and layer 7 policy metrics 910D and 910E, respectively.

An important aspect to note is that any combination of policy management metrics can be added to conventional routing and switching forwarding tables by simply adding new predicates to the table 910. Another important feature to note is that routing or switching decisions are usually limited to Layer 2 and Layer 3 of the Open System Interconnect (OSI) Internet model. For example, a switch or router usually determines packet forwarding based on packet port numbers and IP addresses.

In cooperation with the network processing device structure of FIG. 13, the ACL table 910 may cause the forwarding decision to be based on information included in higher OSI layers. For example, some packet forwarding decisions in the ACL table 910 are based on information of the data link (layer 2), network layer (layer 3), transport layer (layer 4) and application layer (layer 7). Of course, the forwarding decision may be based on any of the other OSI layers.

In more detail, ACL table 910 includes destination IP address predicates 910A that are partly used to send packets to other output ports identified in actions 910C. Typical subnet masks within the predicates 910B are used to mask the bits in the destination IP address predicates 910A. For example, in the first ACL entry 912, only the first three subnet fields "10.0.0" of the address are compared with the destination IP address of the incoming packets 821. In ACL entry 916, only the first subnet fields "10" are compared with the destination IP address of input packets 821.

In this example, forwarding decisions are based on destination IP address 910A in addition to layer 4 or layer 7 predicates 910D and 910E, respectively. For example, an incoming TCP packet with the destination IP address "10.0.0.x" (where "x" represents "don't care") will be routed to output port 15. Alternatively, incoming UDP packets with the destination IP address "10.0.0.x" will be routed to output port 5.

TCP and UDP identifiers for the incoming packet 821 are identified by the processor 822 at the same time as the processor 822 identifies the destination IP address during initial packet processing. The destination IP address and the TCP or UDP identifier are then compared with the entries in the ACL table 910 to determine the correct output port for sending the packet. This shows an example of how packets are transmitted based on layer 4 metrics.

ACL entry 914 is a typical forwarding table entry that sends packets to a particular output port 2 when the input packet contains the subnet fields "12.0.x.x" in the destination IP address.

ACL entry 916 is based on routing decisions according to both destination IP address and Layer 7 session initiation protocol (SIP) metrics. For example, a non-SIP packet with IP destination address " 10.x.x.x " is routed to output port 7 of network processing device 820. However, the SIP packet with the IP destination address "10.x.x.x" is routed to output port 4. This is useful for packets containing Voice Over IP (VoIP) SIP signaling that needs to be routed to a particular network processing device, such as a SIP proxy server. Other non-SIP IP traffic is routed in the usual way according to the destination address. The SIP identifier used to compare with the SIP predicate 910E in the ACL entry 916 is a flag generated by the processor 822 when the packet includes SIP messaging.

ACL entry 918 shows another example where routing is based on Layer 7 URL metrics. One application for this kind of routing can be used to access web servers and then route subsequent URL packets to other locations more efficiently. 16 and 17, a business may operate a web server 934 accessible by the various users 930 over the internet 932. The web server 934 can display to the user 930 a web page 936 that supports various different links to various business services. For example, a first URL link 938 can direct a user to customer support, a second URL link 940 can direct a user to a car sales, and a third link 942 can direct a user 930 to a customer. You can go to furniture sales.

Web servers supporting each of these various links 938, 940, and 942 may be located at different Internet locations, and possibly (but not limited to) different geographic locations. For example, customer support server 944 may be located at corporate headquarters in Atlanta, auto sales server 946 may be located in Detroit, and furniture sales server 949 may be located in Paris, France. The ACL table 910 (FIG. 16) is utilized to more effectively connect the user 930 to URL links 938, 940, and 942.

For example, when the user clicks on the customer support link 938, the web server 934 generates packets with the destination IP address "10.10.x.x" including the URL "Http: // DEST1". The router 935 of FIG. 17 compares both the IP destination address and the URL with entries in the ACL table 910. As such, router 935 routes the packets to output port 1 to customer support server 944. Router 935 may also receive packets that have the same destination IP address "10.10.x.x" but whose URL is "fttp; / DEST2". Router 935 accordingly routes these packets through port 2 to automobile server 946. Packets with the destination IP address " 10.10.x.x " and associated URL / DEST3 are routed to the furniture server 948 via port 3. This provides more direct routing to the desired IP destination.

RSP Integrated policy management

As discussed above, Unified Policy Management (UPM) may be implemented within conventional processor and computing system architectures as shown in FIG. However, for additional performance, a UPM may be built into the processor (RSP) of a reconfiguration word similar to the RSP 100 shown earlier in FIGS. 2A-2C.

18 and 19, at operation 1000, the DXP 180 in the RSP 100 identifies any ACL predicates 954 needed to parse packets in the input buffer 140 and perform UPM operations. Run the grammar. The DXP 180 sends instructions to the SPU 200 in operation 1002 to start the SEP code 212. The SEP code 212 causes the SPU 200 to format the ACL predicates 954 into a set of predicates 956 that are then applied to the ACL table 979. In this example, some or all of the ACL table 979 is included in one or more CAMs 220.

According to the DXP 180 and associated SEP code 212 fired by the DXP 180, any number of ACL predicates 954 can be combined into the ACL predicate set 956 by the SPU 200. Can be. For example, the grammar in DXP 180 may identify ACL predicates 954 for packet destination and source address. Other predicates 954 may be identified for IPv6-IPv4 switching or TCP DoS operations. The SEP code 212 fired by the DXP 180 can cause the SPU 200 to combine the destination IP address predicate with an IPv6 packet type predicate when the DXP identifies an IPv6 packet. Similarly, when a TCP packet is identified, the DXP 180 may cause the SPU 200 to combine the destination IP predicate 954 with the TCP packet type predicate 954 and predicate set 956 in the SEP code ( 212) can be started.

At operation 1004, SPU 200 applies ACL predicate set 956 to the ACL table in CAM 220. In operation 1006 the SPU now processes the packet according to the ACL action 952 received back from the CAM 220. At operation 1010, the ACL action 252 may be a simple drop command that causes the SPU 200 to discard a packet currently stored in DRAM 280 (FIG. 2A). At operation 1012, ACL action 952 may be an instruction that causes SPU 200 to send a packet in DRAM 280 to output buffer 150.

In a third situation, the ACL action 952 may cause the SPU 200 to launch additional SEP code 212 that may be associated with a particular firewall operation. For example, a series of ACL entries 980 can be associated with other firewall operations. ACL entry 980A may be associated with an intrusion detection system (IDS) license operation, which will be described in more detail below. Another ACL entry 980B corresponds to the co-pending application disclosed in Serial Number 11 / 125,956 Method and apparatus for intrusion detection in a network processing device, dated May 9, 2005, which is already incorporated in this document in a form of reference. May be associated with an IDS operation.

Other ACL entries 980C-F are already described or described in more detail below, network address translation (NAT), IPv4-IPv6 translation, denial of service for TCP sessions (DoS), and DoS for packet fragments. Like other firewall operations.

For example, the SPU 200 may apply an ACL predicate set 956 to the CAM 220 that matches the ACL entry 880E corresponding to one DoS TCP packet. The action contained in the ACL entry 980E may be a pointer 982 to the language code table 210. In operation 1008 of FIG. 19, SPU 200 starts and executes the SEP code at point location 982. In this example, the SEP code 212 at location 982 allows the SPU 200 to perform some or all of the TCP DoS operations described above with reference to FIGS. 4-11.

After completing the TCP DoS operations initiated by the action of ACL entry 980E, SEP code 212 may cause SPU 200 to do any of a variety of other firewall operations. For example, as indicated by the 1014 path, the SPU 200 is managed to assemble another set of ACL predicates 956 from the ACL predicates 954 identified by the DXP 180. The new predicate set 956 is now reapplied to the ACL table 979 to perform other firewall operations. The SEP code 212 may direct the SPU 200 to either drop the packet as indicated by path 1016 in FIG. 19 or to send the packet as indicated on path 1018 to another output port.

As described above with reference to FIGS. 13-17, the RSP 100 may perform integrated policy management integrating other firewall policy management operations and routing / switching operations. As such, the CAM 220 will also include a forwarding information base 984 that includes entries with destination IP addresses and associated destination port numbers. As shown in FIG. 16 above, the FIB table 984 may include generic FIB entries 987 and other entries 986 for routing packets according to the destination address and other firewall policy metrics 988. have.

The RSP 100 can easily move between firewalls, conventional routers or switches, or a combination of both. For example, in erroneous code table 210 (FIG. 18), path 990 indicates that RSP 100 switches from DoS TCP operation to routing operation. The first set of predicates 956 provided by the SPU 200 to the CAM 220 may match the DoS TCP entry 980E. After completing execution of the SEP code 982 associated with the DoS TCP operation, the SPU 200 is managed to provide another set of predicates 956 to the CAM 220. The new set of predicates 956 will match an entry 986 or 987 in the FIB 984. That entry in the FIB 984 may cause the SPU 200 to go to the SEP code 992 of the SCT 210 to perform a normal or UPM routing operation.

Alternatively, the initial predicate set 956 provided to the CAM 220 may match the FIB entry 986 instead of initially matching the DoS TCP entry 980E. The resulting action contained in entry 986 will direct the SPU 200 to send the relevant packet through the output port to another device that supports TCP DoS operations.

Network Address Switching (NAT) / Port Address Switching (PAT)

Referring to FIG. 20, the RSP 100 may include a public IP address used to transmit a packet through the public network 12 and a private IP address used to transmit a packet through the private network 24. It may be programmed for NAT / PAT operations to switch IP addresses and / or port numbers of packets traveling through firewall 1062.

Typically, there are several unique private IP addresses associated with various network processing devices operating within private network 24. However, only one or a few public IP addresses can be used to represent those private IP addresses. This public-private address translation protects the identity of internal devices in private network 24 and reduces the number of public addresses required for mapping to various private addresses in private network 24.

In another embodiment, the one or more private IP addresses include associated individual public IP addresses. This will not necessarily reduce the number of public IP addresses, but may cause the firewall 1062 to hide its private IP address from the public network 12. This one-to-one mapping also allows the firewall 1062 to reconfigure (reset) public IP addresses for various network devices in the private network 24.

The RSP 100 is configured to translate the public IP address 1058 of the incoming packet 1061 into a private IP address 1074. The private IP address 1074 is now used to route the inner packet 1076 to the associated network processing device 1078 in the private network 24. The RSP 100 also receives a packet 1072 containing the private IP address 1070 from the local device 1078 in the private network 24. When this packet 1072 is directed to an endpoint 1056 in the public network 12, the RSP 100 sends a private IP address 1070 and the packet 1050 via the public network 12 to the endpoint ( 1056 to a public IP address 1052 used for routing.

In more detail, the device 1078 operating in the private network 24 may initially send packets 1072 through the firewall 1062 to the destination of the public network 12. The RSP 100 receives the packet 1072 and translates the private source IP address 1070 into a public IP address 1052 associated with the firewall 1062. Outgoing packets 1050 are also assigned to a specific port number 1054 by the RSP 100. The RSP 100 now updates the lookup table 1064 by adding the private IP address entry 1068 and the corresponding port number entry 1066.

The device 1056 receiving the outgoing packet 1050 may send the packet 1061 back to the local device 1078. Device 1056 sends a public IP address 1052 and port number 1054 in packet 1050 to destination address 1058 and port number 1060 for packet 1061 that is sent back to local device 1078. Use as. RSP 100 maps destination address 1058 and port number 1060 in packet 1061 to port number entries 1066 in lookup table 1064. The RSP 100 identifies the private IP address entry 1070 in the lookup table 1079, corresponding to the matched port number entry 1060.

RSP 100 replaces the public destination IP address 1058 in packet 1061 with the private IP address 1070 identified from lookup table 1064. During the transition between private and public IP addresses, the RSP 100 de-assembles the packet, recreates the checksum value and then reassembles the packet.

21-23 illustrate in detail an example of how the RSP 100 performs the NAT / PAT conversion described above. DXP 180 (FIG. 21) parses incoming packets received from private network 24 at operation 1100 (FIG. 22) to identify private IP source address 1070. DXP 180 signals SPU 200 at operation 1102 to load micro instructions from SCT 210 to convert private IP source address 1070 to a public IP source address.

SPU 200 generates the public IP address and port number for the packet in operation 1104. The public IP address is usually the IP address assigned to the firewall 1062 (FIG. 20). In operation 1106, the SPU 200 loads the port number for the packet 1072 and the corresponding private IP address into the lookup table 1079. 21 shows an example of how the lookup table 1079 is implemented using the CAM 220 and the SRAM 221. The SPU 200 stores the port numbers associated with the output packets 1050 in the CAM location 220A via the AMCD 230 and stores the corresponding private IP address 1070 in the SRAM 221 as an entry 221A. Save it.

In operation 1108, the SPU 200 replaces the private IP source address 1070 of the packet 1072 with a public source IP address 1052 that includes an associated port number 1054 (FIG. 20). SPU 200 may also generate a new checksum for outgoing packets (operation 1110). Finally, the SPU 200 sends a packet 1050 from the DRAM 280 to the output port 152 with a public IP address 1052 and a port number 1054 at operation 1112.

23 shows how the RSP 100 converts the public destination IP address of incoming packets back to private IP addresses. At operation 1120, DXP 180 parses the incoming packet 1061 received from public network 12 and identifies the associated five suit addresses. The DXP 180 signals the SPU 200 at operation 1122 to convert the public IP destination address 1058 and port number 1060 to the corresponding private IP destination address 1074 (FIG. 2A). Load microinstructions from.

SPU 200 compares the public destination IP address 158 and port number 1060 from the incoming packet 1061 with the IP address and port number entries 220A of the lookup table 1079, at operation 1124. For example, SPU 200 uses the destination port number as an address to CAM 220. The section 220A so address that matches the port number is used as a pointer into the address section 221A of the SRAM 221. At operation 1126, SPU 200 reads the identified private destination IP address from SRAM 221 and replaces the public IP destination address 1058 for the packet with the identified private IP address 1074. At operation 1128, the SPU 200 may also generate a new checksum for the switched packet. Finally, the SPU 200 outputs the packet 1076 from the DRAM memory 280 through the output port 152 to the private network 24 in operation 1130.

RSP 100 may be configured to perform other change and monitoring operations on the same packets before or after NAT / PAT operation. In this case, SPU 200 may send a packet with a new private IP address 1074 from DRAM 280 back to recycle buffer 160 (FIG. 2A) for further firewall processing. Other firewall operations are then performed on the packets in recycle buffer 160.

IPv6 / IPv5  transform

Referring to FIG. 24, the firewall 1062 may need to be switched between Internet Protocol Version 4 (IPv4) and IP Version 6 (IPv6), or between other IP Protocol versions. For example, the first network 1150 may use IPv6 and the second network 1160 may use IPv4. Accordingly, firewall 1062 must convert the 128-bit address space for IPv6 packets 1156 into a 32-bit address space for IPv4 packets 1172. Other information and payload in the headers will also have to be switched between IPv4 and IPv6.

In one example, firewall 1062 converts IPv6 packet 1156 into IPv4 packet 1172. In another example, firewall 1062 encapsulates IPv6 packet 1156 into IPv4 tunnel 1164. In connection with the reverse translation, the firewall 1062 may convert IPv4 packets into IPv6 packets or encapsulate IPv4 packets 1172 in IPv6 tunnels. These various transformations depend on the type of IP networks associated with the firewall 1062.

The incoming packet 1158 may include a media access control (MAC) header 1180, an IP header 1182, and a TCP header 1184. The type field 1186 identifies the IP version number for the IP header 1182. Referring now to FIGS. 21, 24 and 25, at operation 1200 (FIG. 25), DXP 180 (FIG. 2) parses an incoming packet 1158 to identify a specific IP version in field 1186. If the type field 1186 indicates IPv4, and the network connected to the opposite end of the RSP 100 also uses IPv4, the DXP 180 will not fire any SEP code in the SPUs 200 for IP version switching.

However, if the type field 1186 points to an IP version that is different from the IP version operating for the opposite end of the RSP 100, the DXP 180 signals the SPU 200 at operation 1202 to direct incoming IP packets to other networks. Micro instructions to load from the SCT 210 (FIG. 2A) to switch to the IP version for. In this example, the SPU 200 converts an IPv6 packet into an IPv4 packet.

In operation 1204, the SPU provides the IPv6 address identified by DXP 180 to section 220B in CAM 220 (FIG. 21) associated with 128-bit IPv6 addresses. CAM 220 addresses the corresponding entry in the section 221B of SRAM 221 that includes the corresponding 32 bit IPv4 address. SPU 200 reads the IPv4 address output from SRAM 221 in operation 1206 and replaces that IPv6 address in the packet with the identified IPv4 address in operation 1208. Alternatively, the SPU 200 may encapsulate an IPv6 packet in an IPv4 tunnel using the IPv4 address identified in the SRAM 221. In operation 1210, the SPU 200 creates a new checksum and sends, in operation 1212, an IPv4 tunnel containing the switched IPv4 packet, or IPv6 packet, from DRAM 280 to output port 152.

A process similar to that shown in FIG. 25 may be used to convert incoming IPv4 packets into IPv6 packets. The same process described above can be used to switch between any other IP packet versions that may appear in the future. The RSP 100 simply identifies the new IP version number that initiates the series of SEP codes used by the SPU 200 to switch packets between the first and second IP versions.

IP version switching may be combined with the integrated policy management operations described above with reference to FIGS. 13-19. For example, RSP 100 may route packets identified with different IP versions to other relevant IP subnets that may support the IP version identified in that packet.

One of the many unique features of the RSP 100 is that additional packet processing operations can be performed without the need for additional hardware and without a substantial increase in software or processing state complexity. For example, in NAT / PAT switching, the same RSP configuration shown in FIG. 21 can also be used for switching between IPv4 and IPv6. IP public and private addresses that are used for NAT / PAT switching within CAM 220, each of IPv6 to IPv4 address mappings 220B and 221B, and vice versa, IPv4 to IPv6 address mappings 220C and 220C, respectively. And can be stored alongside 220A and 220B. Also, processing an increased 128-bit IPv6 header requires only a few additional cycles in the overall packet processing rate of the RSP 100, since only a few additional clock cycles are needed to parse a larger IPv6 packet header. Plus.

Several different firewall operations can be performed more efficiently within the same RSP 100 by leveraging general DXP parsing. For example, the DXP 180 may perform some of the same parsing operations for both NAT / PAT, and IPv6 / IPv4 operations in FIG. 21. For example, the IP address is identified by the DXP 180 for both NAT and IP version transitions. The same DXP address parsing results can thus be used for both NAT and IP version switching. The DXP 180 thus only requires a small amount of grammar in addition to the NAT grammar.

RSP 100 is also not limited to processing any particular data size. Thus, any IPv4 or IPv6 operation, or any other IP version or address size that may be developed later, is easily implemented using the same RSP structure 100. The RSP 100 simply adds minimal new syntax for the DXP 180, additional SEP code to be executed by the SPUs 200, and additional entries to the CAM 220 and the SRAM 221 such different IP versions. And address sizes.

This is different from conventional hardware structures that may require a complete redesign to efficiently handle IPv6 packets instead of IPv4 packets. For example, conventional in-processor data path sizes, register sizes, and logic elements would have to be redesigned for larger 128 bit IPv6 addresses.

Virtual  Private Network (VPN) Integration

FIG. 26 illustrates an example of how a virtual private network (VPN) tunnel 1207 is established over the Internet 1212. Computer 1216 may request a file 1200 from corporate server 1202. Server 1212 accesses file 1200 and sends it back to remote user 1216 via VPN / firewall 1206 as IP packets 1204.

The firewall 1206 may, like the IP Source Guard (IPSG), packetize the packet 1204 to an IP Security Protocol Encapsulating Security Payload (IPSec ESP) trailer 1210 and an IP Security Protocol Authentication Header (IPSec AH); IP Security Protocol Authentication Header). These IPSec headers 1208 and 1210 are located after the IP header and before the upper layer protocol header on the layer 3 protocol in transport mode or before the encapsulated IP header in tunnel mode. IPSec ESP header 1210 and AH header 1208 may be used separately or in combination with each other.

The IPSec ESP header 1210 optionally includes the information needed to decrypt the received packet and the authentication digest required to authenticate the received packet 1204. IPSec AH header 1208 includes an authentication digest required to authenticate the received packet 1204. When the IPsec packet 1218 includes the IPSec AH header 1208, the authentication digest is located in the layer 3 protocol; In the IPSec ESP mode, only the authentication digest is located behind the payload of packets in the ESP trailer 1210.

IPsec packet 1218 is sent to computer 1216 via Internet 1212 as VPN tunnel 1207. The VPN / firewall 1214 decrypts the IPsec packet 1218 according to the information in the AH header 1208 and the ESP header 1210. The decrypted IP packet 1204 is now sent to the computer 1216. The VPN / firewall 1214 may perform any of the other firewall operations on the decrypted packets 1204 as described above.

FIG. 27 shows more detailed operations performed by RSP 100 at VPN / firewalls 1206 and 1214. The RSP 100 first performs preliminary DoS filtering 1220 to filter the received IPsec packets 1218 above the DoS attack rate threshold. DoS filtering 1220 may also filter any non-IPsec packets in a similar manner as described above with reference to FIGS. 4-11.

IP address, packet session identifiers and security parameter indexes (SPIs) for which the Security Association (SA) lookup operation 1222 identifies the necessary decryption and authentication techniques to be used by the RSP 100, from the IPsec packet 1218. Extract (1226). SPIs 1226 and other IP information are provided in a lookup table 1224 that is similar or identical to the lookup and ACL tables described above for DoS, UPM, NAT, and IP version translation. Lookup table 1224 then returns decryption key 1228, decryption algorithm identifier 1230, and authentication algorithm identifier 1232.

Associated decryption algorithms transform the bits of the IPsec packet 1218 from encrypted to decrypted. Examples of decryption algorithms include T-DES mode of Data Encryption Standard (DES), Triple Data Encryption Standard (T-DES), Advanced Encryption Standard (AED), and CBC mode. Authentication algorithms perform a hash operation on the data to verify that the bits in IP packet 1204 are the same as those originally sent from server 1202. Examples for authentication algorithms include MD5 and SHA1.

The results from the SA lookup 1222 are given to the decryption operation 1234, which then decrypts the IPsec packet 1218 back to the original IP packet 1204. Specific details of how the SA lookup 1222 and decryption operation 1234 are performed are disclosed in the following applications that are co-pending and incorporated herein by reference: Serial Number, filed May 11, 2005 11 / 127,445 Multiprocessor architecture with floating decryption / encryption / authentication blocks; Serial number 11 / 127,443, filed May 11, 2005; IP security decryption / encryption / authentication; Serial No. 11 / 127,468, filed May 11, 2005; Pipelined IP Security decryption / encryption / authentication; Serial number 11 / 127,467 DEA Engine with DMA interface, filed May 11, 2005.

DXP 180 parses incoming packets and identifies IPsec packet 1218 according to the identified IP type field. The grammar of the DXP 180 thus identifies the SPIs 1226 used by the DXP 180 to initiate the SEP code 212 (FIG. 2A). SEP code 212 instructs SPUs 200 to apply SPIs 1226 to ACLs in CAM 220 and then performs decryption 1234 according to the results from the CAM lookup. For example, decryption key 1228, decryption algorithm identifier 1230, and authentication algorithm identifier 1232 may be stored in the same CAM / SRAM structure as the same described above in FIG. 21. The results for the CAM lookup are ACL actions that point to an additional SEP code that uses the encryption key 1228 to execute the decryption algorithm associated with the identifier 1230 and the authentication algorithms associated with the identifier 1232.

If non-encrypted packets are received during the same IPsec session, such as the same suit, the corresponding ACL entry in CAM 220 may instruct SPU 200 to exclude the packets. This prevents unauthorized attackers from accepting the VPN session 1207.

Decrypted IP packets are now sent to one or more different post-decryption operations, where possible, which may include a forwarding operation 1236 similar to that described in the UPM application above. For example, the RSP 100 may simply send the decrypted packet 1204 to the destination address at forwarding operation 1236 without any additional firewall operations using the FIB described in FIGS. 13-19.

Alternatively, output from decryption 1234 may pass through secondary DoS filtering 1238. Secondary DoS filtering 1238 may perform DoS detection and filtering for the IP address and other identifiers that are now decrypted in IP packet 1204. For example, some of the predicates used for DoS and other UPM operations are now decrypted. The decrypted predicates are used to perform the next secondary DoS operation 1238, UPM, or other required firewall operations that have been identified.

Additional firewall operations are described in TCP proxy operation 1240 as described in co-pending patent application No. 11 / 181,528, TCP isolation with semantic processor TCP state machine, filed Jul. 14, 2005, incorporated herein by reference. It may also include. In another possible post-decryption operation 1240, the RSP 100 may translate the decrypted IP address into a public or private address as described above via a NAT / PAT application.

Depending on which firewall operations are implemented and the decrypted IP packets 1204, the RSP 100 may perform any combination operation of post decryption operations 1236, 1238, 1240 or 1240. Of course, any of the other firewall operations described above may also be performed.

License to use firewall policy management

Referring to FIG. 28, the ACL table 1506 in conjunction with the RSP 100 may be used to more effectively assign antivirus (AV) licenses. Currently, an AV license is assigned for individual devices 1514. The problem is that such licenses are difficult to manage by a system administrator. For example, for every new device 1514 added to the network, a different license must be obtained and its AV software installed. When the license agreement expires, the network administrator must reinstall or rerun the AV software for each individual device. In addition, any updates to the AV software must be loaded separately on each computer 1514.

The RSP 100 supports centralized license management. For example, AV software 1504 is similar to the method disclosed in US Pat. No. 11 / 125,956 Method and apparatus for intrusion detection in a network processing device, filed May 9, 2005, and which is similar to that disclosed in RSP (firewall 1502). May be operated by 100). Alternatively, AV software 1504 may be executed via a general network processing device.

Nevertheless, the RSP 100 determines which sub-networks 1520, 1522 and 1524 have an AV license and applies the AV software 1504 only to packets destined for the licensed sub-networks accordingly. . Referring to FIGS. 28 and 29, the RSP 100 receives packets 1525 from the public Internet 1500 with a particular destination address 1527. The DXP 180 in the RSP 100 identifies the IP destination address for the SPU 200 and causes the SPU 200 to, among other things, have an AV license for the sub-network corresponding to that destination address 1527. Have the SEP code run checking to see if

For example, SPU 200 provides a destination address 1527 for the packet to CAM 220. The destination address 1527 will match the predicate 1528 of the ACL entry 1526. Action 1530 associated with ACL entry 1526 indicates that there is a license for subnetwork 1522 (FIG. 28) associated with packet destination address 1527 that matches ACL predicate 1528. The action 1530 may be a pointer to an additional SEP code that instructs the SPU 200 to determine whether the number of connections established with the current subnetwork 1522 is less than the number of licenses assigned. If the number of licenses obtained for the sub network 1522 is greater than the number of active connections, the AV software 1504 is applied to the packet 1525.

SPU 200 or other processing elements in firewall 1502 may continue to hold a count 1529 for the number of active connections between the Internet 1500 and each of the subnetworks 1520, 1522, and 1524. The memory 221 stores this activated connection count 1529 and the number 1531 of licenses obtained for each subnetwork connected to the firewall 1502.

SPU 200 may quickly determine whether AV software 1504 should be applied to packet 1525 by applying the already identified packet destination address 1527 to CAM 220. The CAM 220 identifies the location of the SRAM 221 including the number of possible licenses 1531 for the sub-network 1522 and the current connection count 1529. If one or more AV licenses are available, SPU 200 applies AV software 1504 to packet 1525 before or after performing other firewall operations.

Once the subnetwork is in the public network, a tunnel can be established for any packets passing through the AV software 1504. For example, the subnetwork 1524 may be located remote from the firewall 1502. If AV licenses are assigned to the sub-network 1524, the action 1530 in the corresponding ACL entry 1526 that matches the addresses of the sub-network 1524 may also be assigned to the SPU (SPU) before sending the packet to the sub-network 1524. 200 will encapsulate the packet in a secure tunnel 1518.

The AV software 1504 will not apply to sub networks that do not have an AV license. For example, no license key actions 1530 would be set for ACL entries associated with subnetwork 1520. As such, the RSP 100 will not apply the AV 1504 to packets destined for the subnetwork 1520.

RSP  Arrays

30 and 31, several RSPs 100 may be connected to each other to provide serial or parallel firewall operations. For example, in FIG. 30 several RSPs 100A-100D are connected in series, each of which performs a different firewall, routing, or intrusion detection system (IDS) operation. The first RSP 100A can identify and extract IP information from the incoming packets 1598 by extracting the five suite source and destination IP addresses and port numbers.

The second RSP 100B may perform TCP related operations, such as filtering certain TCP packets and managing TCP sessions associated with a DoS attack as described above with respect to FIGS. 4-11. RSP 100C may perform packet processing operations directed at any HTTP sessions that may be delivered over packets. Finally, the RSP 100D may contain a virus or other specific type of information, such as disclosed in May 9, 2005, co-pending application No. 11 / 125,956 Method and apparatus for intrusion detection in a network processing device. Can find any text or executable files in an HTTP session.

Of course, any combination of RSPs 100 may perform any combination operation of different firewall and non-firewall operations, and FIG. 30 is merely illustrative. It is important to note that each additional RSP substantially gives a linear increase in performance. For example, the RSP 100A may include any parsed firewall predicates, IDS tokens, non-terminal (NTs) 312, production codes 178, SEP code 177B (FIG. 2B). And 2c) etc. 1602 to the next RSP 100B. The RSP 100B may send similar state information 1602 to the RSP 100C after completing packet processing.

This prevents each subsequent RSP 100 from repeating some of the same parsing already completed in the previous RSP. In addition, the structure of the DXP 180 (FIG. 2A) allows each RSP 100 to immediately switch to the same state as the previous RSP by simply loading NT 132 into the parser stack 185 (FIG. 2A). To be. For example, RSP 100A can identify an ACL predicate that includes an IP destination address. RSP 100A sends its ACL predicate and associated NT 132 to message RSP 100B, side by side with associated packet 1600 via message 1602. The RSP 100B may now begin performing TCP operations on the packet 1600 with the RSP 100A previously left using the already identified IP address information. Thus, the RSP 100B does not need to reparse the packet 1600, such as having to rediscover the destination IP address.

This is different from conventional processor architectures where packet processor states are not easily communicated. As a result, each additional general processor added to the packet processing system will not necessarily linearly improve overall network processing device performance. In other words, doubling the number of packet processing devices with general computer architecture does not necessarily double overall processing performance. Conversely, doubling the number of RSPs 100 can nearly double the overall performance of the host network processing system.

31 shows another alternative configuration of the RSP 100. In this configuration, one or more RSPs 100 operate in parallel. Based on the IP address and other predicates extracted from the packet, the first RSP 100A may perform an initial UPM operation to determine if other firewall operations need to be performed on the incoming packets 1598, if any. have. RSP 100A routes packets to RSPs 100B-C in accordance with the identified firewall policy metrics.

For example, based on the identified firewall predicates, the packet 1598 may require DoS processing given by the RSP 100B. Accordingly, RSP 100A routes these packets to RSP 100B. If the RSP 100B determines that the destination subnet address for the packet has an associated IDS license as described in Figures 28 and 29, the packet can be routed to the RSP 100C for anti-virus processing. Otherwise, the RSP 100B may send the packets towards the endpoint of the local network 1604.

When UPM routing in RSP 100A determines that a packet should be converted to IPv4 format, the packet is routed to RSP 100D. The packet 1598 is then sent to the RSP 100E for processing according to other higher OSI layer data. For example, the RSP 100E may route the packet according to the HTTP information in the packet as disclosed in FIG. 17. Different packets may be routed to RSPs 100F and 100G, respectively, to perform other NAT and DoS operations.

Command line interface ( CLI ) / Logging (Record) / statistics

Command line interface

Referring again to FIG. 2A, a command line interface (CLI) 282 is coupled with the MCPU 56, allowing a computer 284 operator to enter CLI commands and data 286 into the RSP 100. . MCPU 56 then interprets the CLI command 286 received from computer 284 and operates accordingly. For example, CLI instructions 286 may direct MCPU 56 to load new ACL entries into TCAM 220 in memory subsystem 215. CLI instructions 286 may also direct MCPU 56 to load data into any other memory elements in memory subsystem 215.

CLI commands 286 may also be used to configure other storage elements and tables in RSP 100. For example, CLI commands 286 may command MCPU 56 to load a new parser grammar into parser table 170, or to generate generation rules 176 into generation rule table 190, or A new SEP code 212 can be loaded into the language code table 210. CLI instructions 286 may direct MCPU 56 to read information from any of the storage devices or tables in memory subsystem 215 or other processing elements in RSP 100.

Logging (record)

SEP code 212 may instruct SPU 200 to record certain acknowledged events to MCPU 56 for recording. For example, SPU 200 may send any packet identified to MCPU 56 as part of a DoS attack. When a DoS attack is recognized, SEP code 212 instructs SPU 200 to send a typical dropped packet to MCPU 56. SEP code 212 may also instruct SPU 200 to notify MCP 56 whenever similar packets are excluded.

MCPU 56 formats the statistics identifying the specific information contained in the exclusion packet, and the number of similarly excluded packets, into a log. This log may be formatted into IP packets containing the IP address of a system syslog that receives and records events recognized by the RSP 100. Packets containing logs may be sent by the SPU 200 via the output port 152 to the system recorder device.

Any acknowledgment events may be recorded by the RSP 100 and may include one (but not limited to) one of the events identified through the firewall operations described above. For example, the SEP code 212 can also command the SPUs 200 to send packets to the MCPU 56 that match specific ACL entries in the CAM 220.

statistics

Any statistics needed may be recorded in the RSP 100 and may be stored logically or transmitted to a logging system. For example, the SPU 200 may be programmed to count all packets received, excluded or output. Different SEP codes 212 may include logging instructions along with other related firewall operations. The RSP 100 identifies statistical information related to received or transmitted packets. For example, the number of received packets, the size of received packets, the size and number of transmitted packets, the number of excluded packets, the number of packets with bad checksums, the number of duplicate packets, failed login attempts, and the like. The statistics may be downloaded to the computer 284 via CLI commands 286 or may be sent via packets periodically through the output port 152 by the SPU 200.

guarantee

Any of the above firewall operations can be demonstrated, and different industry acceptance warranties, including Institute for Computer Security Association (ICSA), National Institute of Standards and Technology (NIST), University of New Hampshire (UNH), PLU Fest, etc. You can follow the standards.

summary

The novel use of the RSP structure in conjunction with access control lists allows for more efficient execution of various various firewalls or other packet processing operations through the same hardware and minimal software reset. Several firewall operations may use syntax constructs such as predicates identified by DXP or other early firewall parsing operations. Thus, RSP provides a more scalable firewall architecture.

As mentioned above, any of the operations described above may be implemented on any network processing device and is not limited to operating on edge devices or commonly referred to as firewalls. For example, DoS, UPM, and other operations may be performed at gateways, routers, servers, switches, and any other endpoint device. In addition, the various operations described above do not necessarily need to be implemented using the RSP 100, and may alternatively be implemented through general computer structures.

Intrusion detection

In the description below, the term “virus” refers to an intrusion, unauthorized data, spam, spyware, denial of service (DOS) attack, or any other type of data, signal, or Or sending a message. The term "virus" is also called "malware" and is not limited to any particular type of unauthorized data or message.

32A shows a private IP network 2024 that connects to a public Internet Protocol (IP) network 2012 via an edge device 2025A. The public IP network 2012 may be a wide area network (WAN) that supports packet switching. The private network 2024 may be those that need to be protected from attacks such as viruses or other malware attacks from the public network 2012 such as company enterprise networks, Internet service provider (ISP) networks, home networks, and the like.

The network processing devices 2025A-2025D in the private network 2024 may be any type of computing device that communicates over a packet switched network. For example, network processing devices 2025A and 2025B can be routers, switches, gateways, and the like. In this example, network processing device 2025A operates as a firewall and device 2025B operates as a router or switch. Endpoint 2025C is a personal computer (PC) and endpoint 2025D is a server such as an Internet web server. The PC 2025C may be connected to the private network 2024 via a wired connection such as a wireless connection or a wired Ethernet connection using, for example, the IEEE 802.11 protocol.

Intrusion detection system (IDS) 2018 may be implemented as any combination of network devices 2025A-2025D operating in private network 2024. Each IDS 2018 collects and analyzes network traffic 2022 passing through the host network processing device 2025 and identifies which packets 2016 in the packet stream 2022 containing the virus. In one embodiment, IDS 2018 is implemented using a Reconfigurable Processor (RSP), which will be described in more detail below. However, it should be appreciated that IDS 2018 is not limited to configurations that use RSP, and other processing devices may also be used.

In one example, IDS 2018 is installed within edge router 2025A connecting private network 2024 to an external public network 2012. In one embodiment, IDS 2018 may also be implemented in network processing devices that typically do not perform IDS operations. For example, IDS 2018 may be implemented within a router or switch 2025B. In another embodiment, IDS 2018 may be implemented in one or more endpoint devices, such as PC 2025C or web server 2025D. Implementing an intrusion detection system 2018 within several different network processing devices 2025A-2025D supports more invasive detection and enables private network 2024 through different access points without going through edge router 2025A. Virus 2026 coming in can be removed. For example, a virus that accesses private / internal network 2024 through employee's personal computer 2025C is detected by IDS 2018 running on PC 2025C, router 2025B, or server 2025D. Can be removed.

In another embodiment, IDSs 2018 in network processing devices 2025 are used to find and remove virus 2016A that occurred within private network 2024. For example, an operator of PC 2025C may generate a virus 2016A that is sent to a network device as long as it operates on public IP network 2012. Any combination of IDSs 2018 operating on internal network 2024 may be used to identify and remove virus 2016A before it exits public IP network 2012.

Some processors allow antivirus operations to be embedded and distributed throughout the network 2024. For example, a processor may perform intrusion detection operations at various ports of a network router or switch 2025B. The built-in intrusion detection system (IDS) (2018) is more powerful, supporting intrusion detection much more effective than current peripheral antivirus detection methods. Intrusion detection is done with a network-flowing data flow without having to deal with any suspicious data types such as e-mail attachments offline.

Intrusion Detection using Syntactic Elements

32B shows a way to create a typical intrusion detection system filter. Input data stream 2071 contains several packets 2072. Packets 2082 include one or more headers 2072A and payload 2072B. A typical intrusion detection system compares each byte 2074 of each packet 2072 in the data stream 2071 to the risk signatures 2058 indiscriminately. Any filters 2075 created according to the risk factor symbol comparison are now applied to the entire data stream 2071.

This intrusion detection method unnecessarily wastes computing resources. For example, some information in data stream 2071, such as certain header data 2072A, may never contain a risk factor. Nevertheless, the intrusion detection system of FIG. 32B blindly compares every byte of data stream 2071 with hazard symbol 2058. This unnecessarily burdens computing resources that perform risk detection.

The intrusion detection scheme of FIG. 32B also does not distinguish between the context of packets being searched for viruses. For example, a risk factor symbol 2058 associated with an email virus is applied to all packets 2072 regardless of whether or not the packet 2082 actually contains an email message. Thus, danger signals 2058 associated with an email virus can be compared to packets 2072 containing HTTP messages. This further limits the scalability of the intrusion detection system.

32C illustrates an embodiment of IDS 2018 that identifies sentence structure elements in a data stream to detect viruses more efficiently. IDS 2018 uses a parser to identify session context 2082 associated with packet 2082. For example, one or more of a media access control (MAC) address 2076A, an internet protocol (IP) address 2076B, and a transmission control protocol (TCP) address 2076C may be identified during the initial parsing operation. In this example, the parser may also identify packet 2082 as containing a Simple Mail Transfer Protocol (SMTP) email message. These identifiers 2076A-2076D in session context 2082 are also referred to as sentence structure elements.

Identifying sentence structure elements 2076 allows IDS 2018 to more effectively detect and eliminate viruses or other malware risk factors. For example, IDS 2018 may customize subsequent intrusion detection operations based on session context 2082 found at the beginning of packet 2082. For example, session context 2082 identifies packet 2082 as containing an email message. IDS 2018 may then find and identify additional sentence structure elements 2076E-2076H specifically related to the email messages. More specifically, it identifies the email sentence structure elements that may include a virus.

For example, IDS 2018 identifies sentence structure elements 2076E-2076G that include information related to "To:", "From:", and "Title:" fields in an email message. IDS 2018 may also identify email referral 2076H, which is also included in the email message. In this example, the virus or malware may only be included in sentence structure element 2076H containing an email attachment. Other sentence structures 2076A-2076G may not take intrusion risk factors. Thus, only sentence structure element 2076H containing an email attachment is compared to the risk factor symbol 2058.

The information in other sentence structure elements 2076E-2076G can now be used to help create the filters 2070 used to filter the packet 2072. For example, a filter 2070 may be generated that filters the same "From:" field identified in sentence structure element 2076F or the same IP source address identified in sentence structure element 2076B.

Thus, IDS 2018 may detect intrusion attempts based on IP session context 2082, traffic characteristics and syntax 2076 of the data stream. An intrusion is detected by comparing the identified sentence structure elements 2076 against risk factor preference rules 2058 that describe events that are considered annoying on network traffic. The rules 2058 may include what activities (eg, certain hosts connect to certain services), which activities are alertable (eg, attempts to a certain number of different hosts require a "overhaul"), Or access to known weaknesses or signals indicative of known attacks.

Fixed packet delay

33 shows a delay buffer used in conjunction with IDS 2018. The intrusion monitor operation 2040 may be performed logically within the processor (RSP) 2100 of the reconfiguration word, or in conjunction with other intrusion monitoring circuitry operating in or out of the RSP 200.

33 and 34, in block 2048A the RSP 2100 receives packets 2022 from an input port 2120. The RSP 2100 may perform a risk factor preliminary filtering operation that discards the first category of packets 2032A containing a virus or other type of risk factor at block 2048B. Initial filtering 2048B may be performed, for example, by accessing a table of well-known predetermined risk factor symbols. This initial filtering limits certain data 2032A to be further processed by IDS 2018. For example, a denial of service attack, a known virus attack, or an unauthorized IP session may be detected, and their associated packets excluded without further processing by IDS 2018.

In a 2048C block, the RSP 2100 stores the remaining packets 2022 in a packet delay buffer 2030. In one example, the packet delay buffer 2030 is Dynamic Random Access Memory (DRAM) or some other type of memory sized to temporarily buffer the incoming data stream 2022. In block 2048D, the RSP 2100 further identifies the syntax of the input data stream. For example, the RSP 2100 can identify packets that contain electronic mail (email) messages.

The vast majority of intrusion attacks on Windows-based PCs come from email messages arriving as files or scripts in the messages. In this attack, the data format is either simple binary machine code or ASCII text. Messages must satisfy the syntax and semantics of the delivery mechanism before they are activated. For example, executables in email messages may use the Simple Mail Transfer Protocol / Point of Presence (SMTP / POP) protocol, which uses Multipurpose Internet Mail Extensions (MIME) files as specified in Request For Comment (RFC) (2822). It is sent by writing. Thus, the RSP 2100 may identify packets conforming to the SMTP and / or MIME protocols at block 2048D.

In block 2048E, the RSP 2100 generates tokens 2068 corresponding to the syntax identified for the data stream 2022. For example, these tokens 68 may include the sender of an email message ("From: ___), the recipient of the email message (" To: ___), the subject of the email message ("Subject: ___), and the time the email message was sent (" Sent: ___), attachments included in the email message, and the like, may include certain sub-elements of the identified email message. Since the RSP 2100 examines this session information, risk factor filtering in network processing devices such as routers and switches is not limited to just the elements found in one packet, ie a TCP session abandon attempt. Filtering on the following, or FTP stream conversion, or HTTPS certificate forgery.

Tokens 2068 are used to dynamically generate a second, deeper set of filters 2070 customized for the syntax of the data contained in the packet delay buffer 2030 at block 2048F. For example, tokens 2068 may be used to create filters 2070 associated with viruses included in email messages. This is important for the scale variability of IDS (2018). By creating filters related to the syntax of the data, IDS can more efficiently examine risk factors. For example, IDS 2018 does not have to waste time applying filters that are not applicable to the type of data being processed.

The RSP 2100 applies this customized filter set 2070 to the data stored in the packet delay buffer 2030 in the 2048G block. Any packets 2032B containing the risk factor identified by the filters 2070 are discarded. After the data has been stored in the packet delay buffer 2030 for a certain fixed period of time, the RSP 2100 outputs data to the output port 2152 at block 2048H.

The fixed delay given by the packet delay buffer 2030 determines the risk factor, determines if a new risk factor is in the process of forming, forms a set of syntax related filters 2070, and stores the data 2034. Provides time for monitor operation 2040 to apply the filters before exiting output port 2152. In general, the delay in delay buffer 2030 in 1 Gigabit (Gbps) Ethernet LAN systems per second will be somewhere between about 20 and 50 milliseconds (ms). Of course, other fixed delay times may also be used.

RSP 2100 utilizes a novel parsing technique for processing data stream 2022. This eliminates the need for the RSP 2100 to perform intrusion monitoring operations 2040 offline from other incoming network routing operations that may be performed at the same network processing apparatus, at the IDS 2018 of the network's line transfer rate. ) Can be implemented. This allows the RSP 2100 to handle incoming packets 2022 with a fixed packet delay, making it difficult for an attacker to discern the network processing devices 2025 (FIG. 32A) that operate intrusion detection systems. .

For example, an intruder may monitor network delay while trying to infect private network 2024 (FIG. 32A) with virus 2016. If a longer response is identified through a particular network path in response to repeated virus attacks, the intruder will determine that the path includes an intrusion detection system. If another network path does not take a long time to respond to the attempted attack, the intruder will conclude that the path does not include an intrusion detection system and can transmit viruses through ports or devices in the identified network path.

Regardless of the type of data 2022 or the type of filters 2070 created and applied to the data stream 2022, IDjS is caused by causing a constant packet delay between the input port 2120 and the output port 2152. (2018) prevents intruders from identifying network processing devices 2025 running IDS 2018. Of course, this is just one example, and other IDS configurations 2018 may also be built that use constant packet delay.

In another embodiment, RSP 2100 applies only a fixed delay to certain types of identified data, and other data is processed without that fixed delay being applied. By identifying the syntax of the data streams, IDS 2018 can identify data streams that need to be scanned for viruses and data streams that do not need to be scanned. IDS (2018) now applies to data streams that need to intelligently search for fixed delays. For example, RSP 2100 may apply a fixed delay to packets identified as containing a TCP SYN message. If no anomaly is detected in those SYN packets, then the RSP 2100 will receive and process the subsequent received TCP data packets without applying the fixed delay described in FIG. 34 above. Thus, non-established TCP sessions may be delayed but no other traffic is delayed.

35 is a detailed view of the operations performed by IDS 2018 shown in FIG. 34. Packets from data stream 2022 are received via input port 2120 by packet input buffer (PIB) 2140. The bytes from the packets 2022 are processed by the direct execution parser (DXP) 2180 and the language processing unit (SPU) 2200. In this example, one or more SPUs 2200 can concurrently execute an access control list (ACL) check operation 2050, a session lookup operation 2052, and a token newness operation 2054.

The ACL check operation 2050 checks packets in the incoming data stream 2022 against an initial ACL list 2064 of previously known filters. The ACL check operation 2050 removes packets that match the ACL filters 2064 and then loads the remaining packets 2022 into the delay FIFO 2030.

Session lookup operation 2052 checks packets 2022 for existing valid IP sessions. For example, the DXP 2180 may send information to the session lookup 2052 that identifies the TCP session, port number, and arrival rate for the TCP SYN message. Session lookup 2052 determines whether the TPC session and port number were previously seen or how long ago. If the packets 2022 are satisfied that they are valid TCP / IP sessions, the packets 2022 may be sent directly to the packet output buffer (POB) 2150.

The token generation operation 2054 generates tokens 2068 according to the syntax of the data stream 2022 identified by the DXP 2180. In one example, token generator 2054 includes a set of 5 data sets including a source IP address, a destination IP address, a source port number, a destination port number and a protocol number associated with packets processed in input buffer 2140. Generate tokens 2068 comprising a. Tokens 2068 may also include any variants in TCP packets, such as unknown IP or TCP options.

In the example described below, some of the tokens 2068 also include textural elements associated with email messages. For example, the DXP 2180 may identify packets associated with an SMTP session as disclosed in FIG. 32C. The token generation operation 2054 now extracts specific information, such as SMTS / MIME attachments, from the email session. An example of a token 2068 associated with an email message is generated using the following type, length, and value (TLV) format:

Token # 1

Type: SMTP / MIME attachment (how to send files in email messages)

Length: # of bytes in file

Value: the actual file

In another example, DXP 2180 identifies packets 2022 in input buffer 2140 associated with a Hyper-Text Markup Language (HTML) session. The token generation operation 2054 accordingly generates the tocons that specifically identify and associate with the HTMP session as follows:

Token # 2

Type: HTML Bin Serve (How to transfer files in web pages)

Length: # of bytes in file

Value: the actual file

As described above, the tokens 2068 are formatted by the token generation operation 2054 so that the sentence structure information contained in the tokens 2068 is risked by the risk factor / virus analysis and ACL counter-measurement agent 2056. It can be easily compared with the factor symbols 2058. The counter-measurement agent 2056 is in one example a general purpose CPU (central processing unit) that compares tokens 2068 with certain risk factor symbols 2058 stored in memory. For example, a counter-measure Agent (2056), in order to determine the need for new Intrusion Filters "BRO" - http://ee.Ibl.gov/bro.html or "SNORT" - http; // www . It is possible to build various previously existing algorithms such as snort.org , both of which are hereby incorporated by reference. Risk factor symbols 2058 may be provided by a commercially available intrusion detection database such as those available from SNORT or McAfee.

Counter measurement agent 2056 dynamically generates output ACLS filters 2070 that match the match between tokens 2068 and risk factor symbols 2058. For example, the risk factor symbols 2058 can identify a virus in an email attachment contained in one of the tokens 2068. Counter measurement agent 2056 then dynamically creates a filter 2070 that includes the source IP address of the packet containing the virus infected email attachment. If filter 2070 is output to ACL operation 2062, then ACL operation discards any packets 2016 in delayed FIFO 2030 containing the source IP address identified by filter 2070. The remaining packets are now output to the output buffer 2150.

Reconstruction processor ( RSP )

36 shows a block diagram of a processor (RSP) 2100 of a reconstruction word used in one embodiment for implementing IDS 2018 described above. The RSP 2100 may include an input buffer 2140 for buffering the packet data stream received through the input port 2120, and an output buffer 2150 for buffering the packet data stream output through the output port 2152. Include.

Direct execution parser (DXP) 2180 is received at input buffer 2140 (eg input "stream"), output to output buffer 2150 (eg output "stream"), and recycled at recycle buffer 2160. (Eg, recycling "stream") controls the processing of packets or frames. The input buffer 2140, output buffer 2150, and recycle buffer 2160 are preferably first-in-first-out (FIFO) buffers. DXP 2180 also controls the processing of packets by a fish processing unit (SPU) 2200 that handles data transfer between buffers 2140, 2150 and 2160 and memory subsystem 2215. Memory subsystem 2215 stores packets received from input port 2120 and also stores hazard factor symbols 2058 (FIG. 35) that are used to identify risk factors in the input data stream.

RSP 2100 uses at least three tables to perform a given IDS operation. Codes 2178 for retrieving generation rules 2176 are stored in parser table (PT) 2170. Grammar generation rules 2176 are stored in a generation rule table (PRT) 2190. Code segments executed by the SPU 2200 are stored in a language code table (SCT) 2210. Codes 2178 of parser table 2170 may be stored, for example, in a row-column format or a content-addressed format. In the row-column format, the rows of parser table 2170 are indexed by non-terminal code NT 2172 given by inner parser stack 2185. The columns of parser table 2170 are indexed by input data value DI [N] 2174 extracted from the header of the data in input buffer 2140. In the content-addressed format, the concatenation of the non-terminal code 2172 from the parser stack 2185 and the input data value 2174 from the input buffer 2140 provides the input of the parser table 2170.

The generation rule table 2190 is indexed by codes 2178 from the parser table 2170. Tables 2170 and 2190 are linked as shown in FIG. 36, such that a query to parser table 2170 is applicable to non-terminal code 2172 and input data value 2174. Will return immediately. The DXP 2180 replaces the non-terminal code at the top of the parser stack 2185 with the generation rule (PR) 2176 returned from the PRT 2190 and then parses the data from the input buffer 2140.

The lexical code table 2210 is also indexed according to the codes 2178 generated by the parser table 2170 and / or according to the generation rules 2176 generated by the generation rule table 2190. In general, the parsing results cause the DXP 2180 to detect whether the code segment 2212 from the erroneous code table 2210 should be loaded and executed by the SPU 2200 for a given generation rule 2176. Let's do it.

SPU 2200 has several access paths to memory subsystem 2215, which provides a structured memory interface that can be addressed by symbols on a context. Memory subsystem 2215, parser table 2170, production rules table 2190, and Symantec code table 2210 store external memory such as on-chip memory, synchronous dynamic random memory (DRAM), and content addressable memory (CAM). Use a device or a combination of such resources. Each table or context merely provides a contextual interface to a shared physical memory space with one or more tables or contexts.

A maintenance central processing unit (MCPU) 2056 is coupled between the SPU 2200 and the memory subsystem 2215. The MCPU 2056 executes any function desired by the RSP 2100, which can be used without difficulty with conventional software. These functions are often rare and are not time sensitive and do not guarantee inclusion in the SCT 2210 due to their complexity. Preferably, MCPU 2056 also has the capability to request SPU 2200 to execute tasks on the MCPU side. In one embodiment, MCPU 2056 helps to generate an Access Control List (ACL) used by SPU 2200 to filter viruses from incoming packet streams.

Memory subsystem 2215 includes an Array Machine-Context Data Memory (AMCD) 2230 for accessing data in DRAM 2280 via a hashing function or CAM lookup. The cipher block 2240 encrypts, decrypts, or authenticates the data and the context control block cache 2250 caches the context control blocks going to and from the DRAM 2280. Generic cache 2260 caches data used in basic operations, and streaming cache 2270 caches data streams as they are written to or read from DRAM 2280. The context control block cache 2520 is preferably a software controlled cache, ie the SPU 2200 determines when the cache line is used and emptied. Respective circuits 2240, 2250, 2260 and 2270 are connected between DRAM 2280 and SPU 200. TCAM 2220 is coupled between AMCD 2230 and MCPU 2056.

The detailed optimization design for the functional blocks of the RSP 2100 is not within the scope of the present invention. See also Application No. 10 / 351,030, entitled A Reconfigurable Semantic Processor, filed Jan. 24, 2003, which is hereby filed for an example of a detailed structure of available processor functional blocks.

RSP Intrusion detection

The functionality of the RSP 2100 in the context of intrusion detection can be better understood using specific examples. In the example described below, the RSP 2100 removes a virus or other malware that is located in an email message. Those skilled in the art to which the present invention pertains can easily apply the concepts presented in accordance with the present invention to detect any type of virus or other type of malware and to detect any type of intrusion detection for any data stream transmitted using any communication protocol. You can recognize that even types can be executed.

The initial intrusion detection process involves parsing and detecting the syntax of the input data stream and is described with reference to FIGS. 37 and 38. Referring to FIG. 37, many different grammars exist simultaneously in parser table 2170 and production rule table 2190. For example, codes 2300 relate to MAC packet header format parsing, codes 2302 relate to IP packet processing, other codes 2304 relate to TCP packet processing, and the like. Other codes of reference number 2306 in the parser table 2170 are the intrusions described in FIGS. 32A-35 above and in this example specifically the example of identifying Simple Mail Transport Protocol (SMTP) packets of the data stream 2022 (FIG. 35). Related to detection (2018).

The PR code 2178 is used to access the corresponding production rule 2176 stored in the production rule table 2190. If not requested by a particular lookup implementation, the input value 2308 (e.g., if n is a match width in selected bytes, the non-terminal (NT) symbol 2172 will match the current input value DI [n] 2174). Combined) need not be assigned to any particular order of PR table 2170.

In one embodiment, parser table 2170 also includes an addresser 2310 that receives data symbol DI [n] 2174 from NT symbol 2172 and DZP 2180. The addresser 2310 associates the NT symbol 2172 with the data value DI [n] 2174 and applies the coupled value 2308 to the parser table 2170. Although it is useful to conceptually represent the structure of the production rules table 2710 occasionally as a matrix involving one PR code 2178 for each unique combination of NT code 2172 and data values 2174, The present invention is not limited thereto. Different types of memory and memory organization are suitable for different applications.

In one embodiment, parser table 2170 is implemented as a CAM, where addresser 2310 uses NT code 2172 and input data value DI [n] 2174 as a key so that the CAM uses PR code ( 2178). Preferably, the CAM is a TCAM (Ternary CAM) known as a TCAM entry. Each TCAM entry includes an NT code 2312 and a DI [n] match value 2314. Each NT code 2312 may have multiple TCAM entries.

Each bit of the DI [n] match value 2314 can be set to " 0 ", " 1 " or " X " This capability allows only a specific bit / byte of DI [n] 2174 to request that the PR code 2178 match the coded pattern in order for the parser table 2170 to find a match.

For example, one line of TCAM contains the NT code of NT_SMTP 2312A for one SMTP packet, followed by an additional byte 2314A indicating the specific content type that may be present in the SMTP packet. It is the same as a label for. The remaining bytes of the TCAM row are set to "don't care". Thus some of NT_SMTP 2312A and bytes DI [N] are submitted to the parser table 2170, where the first set of bytes of DI [N] contains an attachment identifier, DI [N]. Matches occur even if the remaining bytes of N] contain anything.

The TCAM of the parser table 2170 generates a PR code 2178A corresponding to the TCAM entry that matches NT 2172 and DI [N] 2174, as described above. In this example, the PR code 2178A is associated with an SMTP packet containing an email message. The PR code 2178A may return to the DXP 2180 or directly back to the PR table 2190, or both. In one embodiment, PR code 2178A is a row index of the TCAM entry that creates a match.

38 illustrates one possible implementation for production rule table 2190. In this embodiment, addresser 2320 receives PR codes 2178 from DXP 2180 or parser table 2170 and NT symbols 2172 from DXP 2180. Preferably the received NT symbol 2172 is identical to the NT symbol 2172 sent to parser table 2170, where the received PR code 2178 was located.

The addresser 2320 uses to access the production rules 2176 corresponding to the PR codes 2178 and NT symbols 2172 thus received. The addresser 2320 may not be necessary in some implementations, but if used may be part of the DXP 2180, part of the PRT 2190, or an intermediate function block. For example, if the parser table 2170 or DXP 2180 directly configures addresses, the addresser may not need to be used.

Production rule 2176 stored in production rule table 2190 includes three data segments. These data segments include: symbol segment 2177A, SPU entry point (SEP) segment 2177B, and skip byte segment 2177C. These segments are either fixed length segments or are preferably either null terminated segments of variable length. The symbol segment 2177A includes terminal and / or non-terminal symbols that are pushed to the parser stack (2185 of FIG. 36) of the DXP. SEP segment 2177B includes SPU entry points (SEPs) used by SPU 2200 to process the data segment. Skip byte segment 2177C includes skip byte values used by input buffer 2140 to increment the buffer point and allow input stream processing to proceed. Other information useful for processing production rules may also be stored as part of production rule 2176.

In this example, one or more production rules 2176A indexed by production rule code 2178A match the identified SMTP packets in input buffer 2140. SEP segment 2177B points to SPU code 2212 in lexical code table 2210 of FIG. 36, and when executed by SPU 2200, the different ACL check 2050 described in FIG. 35 above, session lookup ( 2052) and the token generation 2054 operation. In one embodiment, SPU 2200 includes an array of words processing elements that can operate in parallel. SEP segment 2177B of production rule 2176A may cause one or more SPUs 2200 to execute ACL check 2050, session lookup 2052, and token generation 2054 operations in parallel.

As mentioned above, parser table 2170 may also include a grammar for processing other types of data not associated with SMTP packets. For example, IP grammar 2302 included in parser table 2170 may include production rule codes 2178 associated with the verified NT_IP destination address of input buffer 2140.

The matching data value 2314 in the production rule code 2302 can include the IP address of the network processing device on which the RSP 2100 is present. If the input data DI [I] 2174 associated with the NT_IP code 2172 does not have a destination address included in the match values 2314 for the PR codes 2302, then the default production rule code 2178 is produced. May be supplied to the rules table 2190. The default production rule code 2178 may point to the production rule table 2190 instructing the DXP 2180 and / or the SPU 2200 to discard packets from the input buffer 2140.

Language processing units SPUs )

As described above, the DXP 2180 identifies certain language elements in the input stream, such as IP sessions, TCP sessions, and SMTP email sessions in the present example. This syntactic parsing operation is important to the overall performance of the IDS system 2018. The actual syntax of the input stream is confirmed by the DXP 2180, and the continuous IDS processing described in FIG. 35 can now be executed more efficiently by the SPU 2200.

For example, the SPU 2200 may have to apply ACL filters associated with email messages to the parsed data stream. This offers several advantages. First, not every byte of every packet needs to be compared with all of the threatening signatures 2058 of FIG. 35. Alternatively, only a portion of the threatening signature associated with the email message is authorized to the SMTP packet. This has the real advantage of increasing the size of the IDS 2018 and allows the IDS 2018 to detect more viruses and malware and to operate at higher packet rates.

FIG. 39 illustrates the ACL check operation 2050 and output ACL operation 2062 described previously in FIG. 35 in more detail. In block 2400, the DXP 2180 outputs a signal such that the SPU 2200 performs the appropriate microcontroller from the SCT 2210 where the SPU 2200 performs the ACL check operation 2050 and the output ACL operation 2062 previously described in FIG. Load the command. As described in FIG. 38, the DXP 2180 outputs a signal to the SPU 2200 via SPU (SPU Entry Point) segments included in the production rule 2176A.

In accordance with the SPU code 2212 (FIG. 36) accessed in the SCT 2210 in response to the SEP segments 2177B, the SPU 2200 in the block 2402 is identified by the DXP 2180 in the input data stream. Get specific sentence structure elements For example, the DXP 2180 may identify sentence structure elements consisting of five elements including an IP source address, an IP destination address, a destination port number, a source port number, and a protocol type. Of course, this is just one example, and other syntax elements of the data stream 2022 (FIG. 35) may also be identified by the DXP 2180.

In block 2404, the SPU 2200 compares the syntax structure elements identified by the DXP 2180 with a priori sets of Access Control List (ACL) filters stored in the TCAM 2220. For example, the apriori set of ACL filters of TCAM 2220 may include a different IP address associated with known threats. In one example, SPU 2200 sends sentence structure elements for packets of input buffer 2140 to TCAM 2220 via AMCD 2230, sending sentence structure elements, such as an IP address for the packet, to TCAM ( 2220). The IP address is then used as an address to the TCAM 2220 which returns the results back to the SPU 2200 via the AMCD 2230.

SPU 2200 in block 2406 examines the results from TCAM 2220. The output from the TCAM 2200 may point to a drop packet, a storage packet or perhaps an IP Security (IPSEC) packet. For example, the TCAM 2220 may generate a drop packet flag when an IP address supplied from a packet in the input buffer 2140 matches one of the apriori filter entries in the TCAM 2220. The storage packet flag is output when the IP address for the input data stream 2022 does not match any entry in the TCAM 2220. TCAM 2220 also includes entries corresponding to the encrypted IPSEC packet. If the IP address matches one of the IPSEC entries, the TCAM 2220 outputs an IPSEC flag.

SPU 2200 in block 2408 drops any packet in PIB 2140 that generates a drop packet flag of TCAM 2220. The SPU 2200 may drop the packet simply by instructing the input buffer 2140 to skip another packet. If the storage packet flag is an output from the TCAM 2220, the SPU 2200 in block 2410 stores the packet from the input buffer 2140 into the DRAM 2280. DRAM 2280 operates as delay FIFO 2230 described in FIGS. 34 and 35. When the IPSEC flag is output from the TCAM 2220, the SPU 2200 may send a packet of an input buffer from the memory subsystem 2215 through the cryptographic circuit 2240. The decrypted packet is sent back to the recycle buffer 2160 of FIG. 36 and the ACL check operation described above repeats.

While packets are stored in DRAM 2280 (delay FIFO 2030 in FIG. 35), MCPU 256 (counter measurement agent 2056 in FIG. 35) matches tokens 2068 extracted from the input data stream. ACL filters 2070 are dynamically created. This is explained in more detail in FIG. 41 below. SPU 2200 in block 2412 dynamically generates a packet stored in DRAM 2280 and now compares it with ACL filters 2070 (FIG. 35) stored in TCAM 2220. For example, SPU 2200 may use a set of five elements for the packet identified in block 2402.

SPU 2200 applies a set of five elements for the packet to filters 20780 dynamically generated at TCAM 2220. Then, any packet that produces a drop packet flag result from TCAM 2220 in DRAM 2280 is removed from DRAM 2280 by SPU 2200 at block 2414. If so, after a predetermined fixed delay period, the SPU 2200 in block 2416 outputs the remaining packets to the output port 2152.

It should be understood that the CAM 2220 may include other apriori filters. For example, CAM 2220 may include filters associated with data that may be associated with a different protocol or included in packets. DXP 2180 identifies sentence structure elements to SPU 2200 that need to be applied to the filters of TCAM 2220.

It will not be possible to determine the virus or malware within a fixed time delay provided by the delay FIFO. For example, a virus may be included at the end of a large multi-megabit message. In this case, IDS 2018 will have to receive a packet containing the virus and generate a virus notification message at the same time. The virus notification message informs the received one to discard the packet containing the virus.

FIG. 40 illustrates the operations performed by the SPU 2200 during the session lookup operation 2052 described previously in FIG. 35. In block 2430, the DXP 2180 outputs a signal to the SPU 2200, which transmits associated SEP segments 2177B to execute the session lookup operation, as previously described in FIG. 2210) to load the appropriate microinstruction.

In one example, SPU 2200 of block 2432 receives source and destination addresses and port numbers for input packets from DXP 2180. SPU 2200 then compares its address and port numbers with current session information for packets stored in DRAM 2280. For some IP sessions, at block 2434 the SPU 2200 will need to re-arrange fragmented packets in the delayed FIFO 2030 operated on the DRAM 2280. The SPU 2200 at block 2438 may also drop (drop out) all packets in the input buffer 2140, which are duplicates of previously received packets for the existing IP session.

FIG. 41 illustrates the token generation operation 2054 previously described in FIG. 35. In block 2450, the DXP 2180 parses data from the input stream described in Figures 36-38 above. In block 2452, the DXP 2180 identifies the syntax elements of the data stream in the input buffer 2140 that may be associated with a virus or malware. In the above example, this may include the DXP 2180 checking the packet containing the email message. However, the sentence structure elements identified by the DXP 2180 may be anything, such as IP data flows including IP addresses, source and destination addresses, verified traffic rates for specific data flows, and so forth.

In block 2454, the DXP 2180 outputs a signal to the SPU 2200 to load the microinstruction from the SCT 2210 associated with the specific token generation operation. And more particularly, the microinstruction identified by SEP segment 2177B in FIG. 38 instructs SPU 2200 to generate tokens for the specific syntax elements identified by DXP 2180.

The SPU 2200 of block 2456 then generates tokens 2068 (FIG. 35) from the identified sentence structure elements. For example, the SPU code 2212 (FIG. 36) may instruct the SPU 2200 to extract sentence structure elements located for the confirmed email message. The SPU 2200 may generate tokens that store information from the "From:", "To:" and "Subject" fields in the packet. The SPU 2200 may also exist in the data stream. It may be possible to extract and generate a token for any email attachment, for example, the SPU 2200 could generate TLV token # 1 previously described in FIG.

Token # 1

Type: SMTP / MIME Attachment (method for transferring files in email messgae)

Length: # of bytes in the file

Value: actual file

It should also be understood that DXP 2180 can identify many different types of sentence structure elements associated with threats. DXP 2180 may initiate different SPU code 2212 (FIG. 36) for different sentence structure elements. For example, as described above, the DXP 2180 may also identify elements of the language that match the HTMP message. DXP 2180 sends SEP segment 2177B which instructs SPU 2200 to generate HTML tokens similar to those shown below.

Token # 2

Type: HTML Bin Serve (method for transferring files in web pages)

Length: # of bytes in file

Value: actual file

SPU 2200 at 2457 formats the tokens for easy application to the threat signature 2058 of FIG. 35. For example, the SPU 2200 allows tokens to be in the format of Type, Length, and Value (TLV) data. The SPU at block 2458 then sends the formatted token to the MCPU 2056 of FIG. 36 or to an external threat / virus analysis and ACL counter-measurement agent 2056 as described above in FIG. 35.

In one embodiment, MCPU 2056 applies tokens 2068 to threat signature 2058 included in TCAM 2220 that generates a set of dynamically created ACL filters 2070. The SPU 2200 at the output ACL operation 2062 described above in FIG. 39 then applies the ACL filters 2070 dynamically generated at the TCAM 2220 to the packets stored in the DRAM 2280 delay FIFO. . Any packets in the delay FIFO that match the ACL filters 2070 are dropped.

In this implementation, the TCAM 2220 may include multiple tables that include both a threat signature table and an ACL filter table. The threat signature table of the TCAM 2220 is accessed by the MCPU 2056 and the ACL filters of the TCAM 2220 are accessed by the SPUs 2220 through the AMCD 2230.

In an alternative embodiment, the external threat analysis device operates off chip from the RSP 2100. In this embodiment, the separated TCAM may include a threat signature. SPU 2200 sends tokens 2068 to an external threat analysis device, which then outputs dynamically generated ACL filters 2070 to MCPU 2056. MCPU 2056 then writes the dynamically generated ACL filters 2070 to TCAM 2220. The SPU 2200 then accesses the ACL filters in the TCAM 2220 for the ACL checking operation 2050 and outputs the ACL operation 2062 described in FIG. 35.

The actual creation of ACL filters 2070 is well known to those skilled in the art to which the present invention pertains, and no further detailed description is provided. However, it is not believed that intrusion detection systems have been continuously generating ACL filters dynamically according to tokens associated with identified syntax elements in the data stream.

Fragmented  Intrusion Detection in Packets

Currently existing text scanners look for known patterns in Internet messages. To avoid false detection of a threat, a series of long texts are matched, usually using techniques to match the style pattern of everyday expressions. However, these techniques require contiguous bytes or scan for threats using extensive context memory.

For example, a virus script can be stored as one long line, as shown below.

For all files:

c: ＼; {open (xxx); delete (xxx); close (xxx);} end.

Therefore, the antivirus scanner must search for the full text string:

s / * open (*); delete (*); close (*) * /

However, an attacker could spread the virus between multiple packet fragments as follows.

IP frag # 1: For all files in c: ＼; {open (xxx);

IP frag # 2: delete (xxx); close (xxx);} end;

Conventional virus scanners may not be able to detect viruses in such fragmented IP packets. By the time the TCP / IP protocol finally sends back fragmented messages, the virus has already penetrated the private network. The RSP 2100 detects and reassembles fragmented packets before processing the intrusion detection operation described above. This allows IDS to detect viruses that are spread over multiple fragmented packets.

FIG. 42A includes a flowchart 2500 illustrating how the RSP 2100 in FIG. 36 detects a virus in fragmented packets. 36 and 42A, a packet is received at an input buffer 2140 through an input port 2120 at block 2502. In block 2510 the DXP 2180 begins parsing through the headers of the packet in the input buffer 2140. DXP 2180 stops parsing through the headers of the received packet if it is determined that the packet is an IP-fragmented packet. Preferably, DXP 2180 parses completely through IP headers, but stops parsing through certain headers belonging to subsequent layers (such as TCP, UDP, iSCSI, etc.). DXP 2180 stops parsing when instructed by the grammar on parser stack 2185 or by SPU 2200.

According to the next block 2520, the DXP 2180 signals the SPU 2200 to load the appropriate microinstructions from the SCT 2210 and to read the fragmented packet from the input buffer 2140. According to the next block 2530, the SPU 2200 writes the fragmented packet to the DRAM 2280 via the streaming cache 2270. Although blocks 2520 and 2530 are shown as two separate steps, the blocks may optionally be performed as one step with an SPU 2200 that simultaneously reads and writes packets. Simultaneous reading and writing by this SPU 2200 is known as SPU pipelining, which acts as a pipeline or pipeline for streaming data to be transmitted between two blocks in the semantic processor 2100.

According to the next decision block 2540, the SPU 2200 determines whether a context control block (CCB) has been allocated for the collection and ordering of the correct IP packet fragment. Preferably, a CCB for collecting and ordering fragments corresponding to the IP-fragmented packet is stored in DRAM 2280. The CCB stops waiting for pointers to IP fragments in DRAM 2280, bit masks for IP IP fragment packets that do not arrive, and additional IP fragment fragments after the allotted time period and DRAM 2280. A timer value for forcing the semantic processor 2100 to release the data stored in the CCB within.

Preferably, the SPU 2200 uses the 2205 content-addressable memory (CAM) of the AMCD using the IP source address of the received IP fragmented packet combined with the identification and protocol from the header of the received IP packet fragment as a key. Determine whether the CCB has been assigned by accessing the lookup function. Optionally, IP fragment keys are stored in a separate CCB table in DRAM 2280 and accessed by the CAM by using the identification information from the header of the received IP packet fragment and the IP source address of the received IP fragmented packet combined with the protocol. do. This selective addressing of IP fragment keys avoids key duplication and sizing issues.

If the SPU 2200 determines that the CCB has not been allocated for the collection and ordering of fragments for a particular IP-fragmented packet, execution proceeds to block 2550 where the SPU 2200 allocates the CCB. Preferably, the SPU 2200 may store a key in the AMCD 2230 that includes a key corresponding to the assigned CCB, i.e., the identification information and protocol from the IP source address of the received IP fragment and the header of the received IP fragmented packet. Enter the IP fragment CCB table and start the timer located in the CCB. When the first fragment for a given fragmented packet is received, the IP header is also stored in the CCB for later recycling. For additional fragments, the IP header does not need to be stored.

Once the CCB is allocated for collection and ordering of IP-fragmented packets, according to the next block 2560, the SPU 2200 sends a pointer to an IP-fragment (minus its IP header) packet to the DRAM 2280 in the CCB. Save it. The pointers to the fragments can be arranged in the CCB as a linked list, for example. Preferably, SPU 2200 also updates the bit mask in the newly allocated CCB by marking the portion of the mask corresponding to the received fragment as received.

According to the next decision block 2570, the SPU 2200 determines whether all IP-fragments from the packet have been received. Preferably, this determination is accomplished by using a bit mask in the CCB. Those skilled in the art will appreciate that for use with the present invention, there are a number of techniques or equivalent tracking mechanisms readily available for implementing a bit mask. If all IP-fragments are not received for fragmented packets, the semantic processor 2100 may further delay processing for the fragmented packets until another fragment is received.

 According to the next block 2580, after all IP-fragments have been received, the SPU 2200 reads the IP fragments from the DRAM 2280 in the correct order and recycles them for further parsing and processing, such as the intrusion detection process described above. Write them to buffer 2160. In one embodiment of the invention, the SPU 2200 only writes the specified header and the first portion of the reassembled IP packet (with no fragmentation bits set) to the recycle buffer 2160.

The specified header may cause the DXP 2180 to direct the processing of the reassembled IP-fragmented packet stored in the DRAM 2280 without having to send all IP fragmented packets to the recycle buffer 2160. The specified header may consist of a designated non-terminal symbol that loads a parser grammar containing IDS operations 2018 and a pointer to the CCB. Parser 2180 then parses the IP header normally and proceeds to parse the upper-layer (eg TCP) headers. If a semantic element is identified in the reassembled packet in recycle buffer 2160 that may contain a virus, DXP 2180 performs SCT 2210 to perform intrusion detection operations 2050, 2052, and 2054 described above. Signal the SPU 2200 to load instructions. For example, if the reassembled packet is identified as containing an email message, the DXP 2180 instructs the SPU 2200 to generate tokens corresponding to the other email message fields described above.

42B includes a flow diagram illustrating how IDS 2018 performs intrusion operations on multiple TCP packets. According to block 2592A, a Transmission Control Protocol (TCP) session is established between the initiator and the network processing device hosting the RSP 2100. The RSP 2100 includes a PRT 2190 and microcode in the SCT 2210 and a grammar suitable for the parser table 2170 to establish a TCP session. In one embodiment, one or more SPUs 2200 are configured for a timer to terminate a TCP session if TCP reordering, window sizing constraints and no additional TCP packets arrive from the initiator within the allocated time frame. Configure and maintain a state for the TCP session, including allocating a CCB to DRAM 2280.

According to the next block 2592B, after the TCP session is established with the initiator, the RSP 2100 waits for TCP packets, corresponding to the TCP session established at block 2592A, to arrive at the input buffer 2140. Since the RSP 2100 may have a plurality of SPUs 2200 for processing input data, the RSP 2100 may receive multiple packets in parallel while waiting for the next TCP packet corresponding to the TCP session established at block 2592A. Can be received and processed.

The TCP packet is received at input buffer 2140 through input port 2120 at block 2592C, and DXP 2180 parses through the TCP header of the packet in input buffer 2140. The DXP 2180, when executed, allocates a request to the assigned SPU 2200 to read a packet received from the input buffer 2140 and write the received packet to the DRAM 2280 via the streaming cache 2270. The SPU 2200 microcommands. The assigned SPU 2200 then finds the location of the TCP CCB, stores a pointer to the location of the received packet in the DRAM 2280 for the TCP CCB, and restarts the timer at the TCP CCB. The assigned SPU 2200 may then be released and allocated for other processing when the DXP 2180 determines.

According to the next block 2592D, the received TCP packets are re-ordered if necessary to ensure correct ordering of payload data. As is well known in the art, TCP packets are considered to be in the proper order when all previous packets have arrived. If it is determined that the received packets are in the proper order, the responsible SPU 2200 loads microinstructions from the SCT 2210 for recycling.

According to the next block 2592E, the assigned SPU combines the TCP connection information and the TCP non-terminal from the TCP header to generate the specified TCP header. The allocated SPU 2200 then writes the specified TCP header to the recycle buffer 2160. Optionally, the specified TCP header can be sent to recycling buffer 2160 along with its corresponding TCP payload.

According to the next block 2592F, the specified TCP header and the reassembled TCP payload are parsed by the DXP 2180 to identify additional semantic elements in the TCP data. Any semantic elements, perhaps identified as containing an intrusion, are processed by the SPUs 2200 in accordance with the intrusion operations described above.

Distributed Token Generation

FIG. 43 illustrates one implementation of a distributed IDS system operating in the network 2600. Network 2600 includes different network processing devices 2610 that perform different activities, such as firewall 2610A, email server 2610B, and web server 2610C. Each of the different network devices 2610A-C operate an IDS 2620A-C similar to the IDS 2018 described above. In one embodiment, one or more IDS 2620 is implemented using RSP 2100 similar to that discussed above in FIGS. 36-41. However, in other embodiments, one or more IDS 2620 is implemented using other hardware structures.

Each network processing unit 2610 is connected to a central intrusion detector 2670 that performs centralized intrusion analysis. Each IDS 2620A-2620C parses the input data stream and generates tokens 2640A-C, respectively, similar to the tokens 2068 described above in FIG. 35. Tokens 2640 are sent to a central intrusion detector 2670.

43 and 44, in block 2802 the central intrusion detector 2670 receives tokens 2640 from each IDS 2620. In block 2804 the intrusion detector 2670 analyzes traffic patterns for different data flows according to the tokens 2640. Filters may then be created at block 2806 and threat signatures may be generated at block 2808 in accordance with the analysis. New filters and threat signatures are then distributed to each IDS 2620 at block 2810.

In one example, the firewall 2610B in FIG. 43 may generate tokens 2640B that identify a new data flow received from the public internet 2630. The token 2640B is sent to the central intrusion detector 2670 identifying the new source IP address A. The web server 2610C may also send tokens 2640C to the intrusion detector 2670. The first token 2640C_1 identifies the new source IP address A and the second token 2640C_2 indicates that the new source IP address A was used to access the file in the web server 2610C.

Central intrusion detector 2670 correlates tokens 2640B, 2640C_1 and 2640C_2 to identify possible viruses or malware that cannot normally be detected. For example, intrusion detector 2670 may determine that the new source IP address A received at token 2640B from firewall 2610B is also the same IP address A that opened the file at web server 2610C. External links from the public internet 2630 in this example are not assumed to open internal network files.

Since the token 2640B was received from the firewall 2610B, the central intrusion detector 2670 concludes that IP address A was received externally from the public Internet 2630. Thus, the central intrusion detector 2670 sends a new filter 2750 to the IDS 2620B in the firewall 2610B and possibly to other network devices 2610A and 2610C, which are packets with source IP address A Interfere with entering network 2600.

In another example, IDS 2620A in email server 2610A generates token 2640A_1 indicating that the email was received from unknown source IP address A. IDS 2620A also sends a token 2640A_2 that identifies the MIME / attachment included in the email identified in token 2640A_1.

Central intrusion detector 2670 determines from previously received tokens 2640B, 2640C_1 and 2640C_2 that certain data flows associated with IP source address A may include a virus or malware. Accordingly, the central intrusion detector 2670 dynamically generates a new signature 2660 corresponding to the content and / or name of the MIME / attachment contained in the token 2640A_2. Central intrusion detector 2670 sends a new signature 2660 to IDS 2620A in mail server 2610A and possibly to all other IDS 2620 operating on network 2600. IDS 2620A then adds a new threat signature to threat signatures 58 shown in FIG.

Thus, the IDS system 2600 may generate filters and / or signatures depending on the semantic content of the tokens 2640 and also the type of network processing device 2610 that transmits the tokens. For example, tokens 2640B generated by firewall 2610B may be processed with more suspicion than tokens generated from other network processing devices in the network. In addition, as discussed above, knowledge about new IP addresses (IP packets received from the public Internet) identified by firewall 2610B may be necessary to provide an email server (2610A) or web server (web server) to more thoroughly detect viruses. Correlated with knowledge of other operations detected by 2610C.

In another embodiment, the central intrusion detector 2670 may disable any network processing devices associated with the detected virus or other malware. For example, virus 2660 may be detected by IDS 2662 operating on PC 2662. IDS 2662 notifies central intrusion detector 2670 about virus 2660. The central intrusion detector 2670 may disconnect the PC 2650 from the rest of the network 2600 until the source of the virus 2660 is identified or removed.

Scalability of Tree Search

The IDS 2018 described above improves on existing intrusion detection by scanning within the session context in which threats may appear. For pattern matching, parser trees are used rather than regular expressions. Intrusion detection and other threats in packet data are performed by "scanning" the incoming packet stream for patterns that match those of known threats.

Conventional regular expression scanners have to scan every byte of a packet and do not have the ability to determine what part of the packet can contain a threat. For example, threats in email can only come through email attachments. The defined body of an e-mail message is a string of ASCII characters that some software will not normally operate in unexpected or malicious behavior. Attachments to email messages are defined by specific, published phrases and headers, such as Multipurpose Internet Mail Extensions (MIME).

Moreover, the headers of the IP protocol used to send email messages often cannot cause the email client to take malicious action. Typically, in an email attachment, the execution of a script or program causes an intrusion problem. Therefore, you may only need to scan the MIME parts of an email message to detect a possible virus.

Finding the MIME portion of an email message includes the protocols (TCP / IP) used to send the email messages; And understanding of email MIME formats. The RSP 2100 quickly parses and starts virus scanning only for the MIME sections of the message in an extensible manner. This reduces the number of packets to be scanned and also reduces the number of bytes to be scanned in each packet. RSP 2100 performs a semantic analysis of the input data stream that allows IDS 2018 to understand what type of data needs to be scanned and what type of scanning needs to be performed. This allows IDS 2018 to more efficiently generate tokens 68 that correspond to the syntax of the input stream.

Other features of the DXP 2180 and RSP 2100 have improved performance over regular expression scanners that use optimized and idiomatic hardware structures for this type of threat scanning. For example, in conjunction with the ternary-content-addressable-memory (TCAM) implemented in the parser table 2170 and parser stack 2185 of FIG. 36, the LL (k) parser is faster than regular expression engines. You can search the input stream.

Regular expression scanners require significant and variable length look before determining possible matches. Wildcard matching also requires unique behavior. On the other hand, in conjunction with TCAM, the LL (k) parser can skip past long strings of wildcards, matching all of the specific bytes in one clock cycle.

Session Content  change

Referring to FIG. 45, IDS 2018 may also be used to add or change information in the identified session context 2852. That is, IDS 2018 is not limited to simply discarding packets identified in an intrusion threat. 45 shows a PC 2864 for establishing an IP link 2866 with the network processing apparatus 2856. IDS 2018 operates at device 2856 and identifies a particular IP session context 2852 associated with IP link 2866 as described above. For example, IDS 2018 may identify HTTP messages, FTTP email messages, SMTP email messages, etc., sent by PC 2864 to another endpoint device operating on WAN 2850.

IDS 2018 may be programmed to add or change a particular type of content 2862 associated with the identified session context 2852. In one example, IDS 2018 may be programmed to remove credit card numbers 2858 from documents included in email or FTTP messages. In another example, IDS 2018 may be programmed to add a digital watermark 2860 to certain documents identified in FTTP or email documents. IDS 2018 may add a digital watermark 2860 to documents that include, for example, the IP source address of PC 2864.

DXP 2180 in RSP 2100 identifies another session context 2852 carried over IP link 2864 as described above. SPU 2200 may then generate tokens associated with other types of content 2862 associated with the identified session context 2852. For example, SPU 2200 may generate tokens that include an email attachment as described above in FIG. 35. The RSP 2100 can search for any documents included in the email attachment.

In a first example, DXP 2180 may identify any IP packets destined outwards to WAN 2850. DXP 2180 then instructs SPU 2200 to retrieve any documents contained in packets containing the credit card number. If a credit card number is detected, IDS 2018 replaces the credit card number with a series of "Xs" that erase credit card information. In a second example, SPU 2200 adds a digital watermark 2860 to the document detected in the FTTP or email session. The document with the modified credit card information or watermark is then sent to the destination address corresponding to the FTTP or email session.

Similar changes can be made to any type of content 2862 associated with any identified session context 2852. For example, a particular IP source or destination address may be changed to a different IP address and then sent back out of IP network 2850 according to some identified session context 2852 or session content 2862. .

FIG. 46 illustrates an example of a push down automaton (PDA) engine 3040 that uses Context Free Grammar (CFG) to retrieve data more efficiently. The semantic table 3042 includes non-terminal (NT) symbols 3046 representing other semantic states managed by the PDA engine 3040. Each semantic state 3046 also has one or more corresponding semantic entries 3044 associated with the semantic elements 3015 included in the input data 3014. Any portions 3060 of the input data 3014 are combined with the current non-terminal symbol 3022 and applied to entries in the semantic table 3042.

The index 3054 is output by the semantic table 3042 corresponding to the entries 3046 and 3044 that match the combined symbol 3062 and the input data segment 3060. The semantic state map 3048 identifies the next non-terminal symbol 3054 indicating the next semantic state for the PDA engine 3040. The next non-terminal symbol 3054 is pushed onto the stack 3052 and then exits the stack 3052 to combine with the next segment 3060 of the input data 3014. The PDA engine 3040 continues to parse the input data 3014 until the target search string 3016 is detected.

First, stack 3052 may include terminal and non-terminal (NT) symbols that allow the semantic states for PDA engine 3040 to be maintained inside other semantic states. This allows multiple semantic states to be represented by a single non-terminal symbol and substantially fewer states need to be managed by the PDA engine 3040.

Furthermore, referring to FIGS. 46 and 47, there is usually no semantic state transition until an associated semantic element is detected. For example, the PDA engine 3040 initially operates in the first semantic state (SS) 3070 and does not transition to the second semantic state 3082 until the entire semantic element "WWW." Is detected. Similarly, PDA engine 3040 remains in semantic state 3072 until the next semantic element ".ORG" is detected. The PDA engine 3040 transition is then made from the semantic state 3072 to the semantic state 3074. Thus, one characteristic of the PDA engine 3040 is that the number of semantic states 3070, 3072 and 3074 corresponds to the number of semantic elements that need to be retrieved from the input data 3014.

Conversely, the PDA engine 3040 of FIG. 46 may not require any additional semantic states to retrieve longer character strings. For example, FIG. 48 illustrates an alternative search that requires the PDA engine 3040 to search for the string "WWWW.XXXX.ORGG". In this example, the PDA engine 3040 is required to search for an additional "W" in the first semantic element "WWWW." And to search for an additional "G" character in the second semantic element "ORGG." Additional characters added to the new search string in FIG. 48 do not increase the number of semantic states 3070, 3071 and 3073 previously requested in FIG. 47.

PDA engine 3040 may also reduce or eliminate state branching. The PDA engine 3040 has a second "WWW." In the same semantic state 3082 that retrieves the ".ORG" semantic element. Eliminating additional branch states by maintaining the likelihood of a string. This is indicated by path 3075 in FIG. 47, where PDA engine 3040 remains in the semantic state 3082 while searching for a second possible occurrence of " WWW. " And ".ORG".

Another aspect of the PDA engine 3040 is that additional search strings can be added without affecting or increasing the complexity of the semantic table 3042. Referring to FIG. 49, there is shown a third semantic element ".EXE" added to the search performed by the PDA engine 3040 of FIG. 46. The additional semantic element ".EXE" adds only one additional semantic state 3076 to the semantic table 3042.

Thus, the PDA architecture of FIG. 46 results in more compact and efficient state tables with more predictable and stable linear state expansion when adding additional search criteria. For example, if a new string is added to the data retrieval, the entire semantic table 3042 does not need to be rewritten but only needs incremental additional semantic entries.

Illustrative Embodiment

50-54 illustrate in more detail an exemplary PDA context free grammar previously executed by the PDA engine 3040 shown in FIG. 46. First, referring to FIG. 50, the same search example is used when the PDA engine 3040 searches for the URL string "WWW.XXX.ORG". Of course this is just one example, and any string or combination of characters may be retrieved using the PDA engine 3040.

It should also be noted that the PDA engine 3040 may be implemented in software such that the semantic table 3042, semantic state map 3048 and stack 3052 are at all locations in memory accessed by the central processing unit (CPU). do. The general purpose CPU then implements the operations described below. Another implementation uses a Reconfigurable Semantic Processor (RSP), described in more detail below in FIG. 47.

In this example, a content addressable memory (CAM) is used to implement the semantic table 3042. Alternative embodiments may use static RAM (SRAM) or dynamic RAM (DRAM). The semantic table 3042 is divided into semantic state sections 46, which may include corresponding non-terminal (NT) symbols, as described above. In this example, the semantic table 3042 contains only two semantic states. The first semantic state in section 3046A is identified by non-terminal NT1 and associated with the semantic element "WWW.". The second semantic state in section 3046B is identified by non-terminal NT2 and associated with the semantic element ".ORG".

Second section 3044 of semantic table 3042 includes other semantic entries corresponding to semantic elements in input data 3014. The same semantic entry may exist multiple times in the same semantic state section 3046. For example, semantic entry WWW. May be located at other locations in section 3046A to identify other locations where the semantic element “WWW.” May appear in the input data 3014. This is just one example and is used to further optimize the operation of the PDA engine 3040. In alternative embodiments, only certain semantic entries may be used once and input data 3014 may be sequentially moved to input buffer 3031 to check each other data location.

The second semantic state section 3046B in the semantic table 3042 actually contains two semantic entries. The ".ORG" entry is used to detect the ".ORG" string in the input data 3014 and the "WWW." The entry is made possible by the second " WWW. &Quot; Used to detect a string. Again, many other ".ORG" and "WWW." The entries are optionally loaded into section 3046B of the semantic table 3042 for parsing optimization. One "WWW." It is equally possible to use an entry and one ".ORG" entry, or fewer entries than shown in FIG.

In this example, the semantic state map 3048 includes three different sections. However, fewer sections can also be used. The next state section 3080 maps matching semantic entries in the semantic table 3042 to the next semantic state used by the PDA engine 3040. Semantic Entry Point (SEP) section 3078 is used to initiate microinstructions for the Semantic Processing Unit (SPU), which is described in more detail below. This section is optional and the PDA engine 3040 may alternatively use the non-terminal symbols identified in the next state section 3080 to determine other operations to perform next on the input data 3014.

For example, if the non-terminal symbol NT3 is output from the map 3048, the corresponding processor (not shown) knows that the URL string "WWW.XXX.ORG" was detected in the input data 3014. The processor may then perform any subsequent processing required for the input data 3014 after the PDA engine 3040 identifies the URL. Thus, the SEP section 3078 is just one optimization in the PDA engine 3040 that may or may not be included.

Skip byte section 3076 identifies the number of bytes from input data 3014 for moving to input buffer 3031 in the next operating cycle. If no match exists in the semantic table 3042, a Match All Parser entries Table (MAPT) 3082 is used.

Execution

A specific end-of-operation symbol "$" is first pushed onto stack 3052 along with an initial non-terminal symbol NT1 representing the first semantic state associated with retrieving the URL. First segment 3060 of NT1 symbol and input data 3014 is loaded into input buffer 3031 and applied to CAM 3090. In this example, the contents in input buffer 3021 do not match any entries in CAM 3090. Thus, pointer 3054 generated by CAM 3090 points to the default NT1 entry in MAPT table 3082. The default NT1 entry instructs the PDA engine 3040 to move one additional byte of input data 3014 into the input buffer 3031. PDA engine 3040 then pushes another non-terminal NT1 symbol to stack 3052.

51 illustrates the next PDA cycle after the next byte of input data 3014 has been moved to input buffer 3031. The first URL semantic element 3060A ("WWW.") Is now included in the input buffer 3061. Non-terminal symbol NT1 again comes out of stack 3052 and is coupled with input data 3060 in input buffer 3061. The comparison of the input buffer 3021 with the contents in the semantic table 3042 results in a match in the NT1 entry 3042B. Index 3054B associated with table entry 3042B points to semantic state map entry 3048B. The next state in entry 3048B includes a non-terminal symbol NT2 indicating a transition to the next semantic state.

Map entry 3048B also identifies the number of bytes that PDA engine 3040 needs to move input data 3014 for the next parsing cycle. In this example, "WWW." Because the string was detected in the first four bytes of the input buffer 3041, the skip byte value in entry 3048B instructs the PDA engine 3040 to move the other eight bytes into the input buffer 3041. The skip value is hardware dependent and may vary depending on the size of the semantic table 3042. Of course, other hardware implementations with larger or smaller semantic table widths can also be used.

52 illustrates the next cycle in the PDA engine 3040 after the next eight bytes of the input data 3014 have been moved to the input buffer 3031. In addition, a new semantic state NT2 was pushed onto stack 3052 and then taken out of stack 3052 and joined with the next segment 3060 of input data 3014. The contents in the input buffer 3041 are again applied to the semantic table 3042. In this PDA cycle, the contents in the input buffer 3041 do not match any semantic entries in the semantic table 3042. Thus, the default pointer 3054C for NT2 state points to the corresponding NT2 entry in the MAPT table 3082. The NT2 entry instructs PDA engine 3040 to move one additional byte into input buffer 3031 and push the same semantic state NT2 to stack 3052.

53 shows the next PDA cycle after another byte of input data 3014 has been moved to input buffer 3031. In this example, there is still no match between any of the contents in the input buffer 3041 and any of the NT2 entries in the semantic table 3042. Thus, the default pointer 3054C for semantic state NT2 again points to an NT2 entry in the MAPT table 3082. The default NT2 entry in the table 3082 instructs the PDA engine 3040 to move another byte from the input data 3014 into the input buffer 3031 and push another NT2 symbol to the stack 3052. Note that during the last two PDA cycles there was no change in the semantic state indicated by non-terminal NT2. There was no state transition even though the first three characters ".OR" in the second semantic element ".ORG" were received by the PDA engine 3040.

54 shows the next PDA cycle in which the contents in the input buffer 3041 now match the NT2 entry 3042D in the semantic table 3042. The corresponding pointer 3054D points to entry 3048D in the semantic state map 3048. In this example, entry 3048D indicates that the URL "WWW.XXX.ORG" was detected by mapping to the next semantic state NT3. Note that the "PDA engine 3040 did not transition to the semantic state NT3 until the entire semantic element" .ORG "was detected.

The map entry 3048D is a pointer SEP1 that selectively starts microinstructions executed by the semantic processing unit (SPU) (see FIG. 55) to perform additional operations on the input data 3014 corresponding to the detected URL. It also includes. For example, an SPU was filed on July 21, 2005, co-pending and incorporated herein by reference, application number 11 / 187,049, and application named Network Interface and Firewall Device and May 9, 2005. As described in the application filed, application number 11 / 125,956 and entitled Intrusion Detection System, additional input data 3014 for performing firewall operations, virus detection operations, and the like may be stripped.

Simultaneously with the initiation of the SEP micro instructions for the SPU, the map entry 3048D may also instruct the PDA engine 3040 to push the new semantic state indicated by the non-terminal NT3 to the stack 3052. This may cause the PDA engine 3040 to begin performing another search for other semantic elements in the input data 3014 following the detected URL 3016. For example, as shown in FIG. 49, the PDA engine 3040 may begin searching for the semantic element “.EXE” associated with the executable file that may be included in the input data 3014. Also as described above, the search for a new semantic element ".EXE" simply requires the PDA engine 3040 to add one additional semantic state to the semantic table 3042.

As also described above, the PDA engine 3040 does not need to maintain a separate state for each parsed data item. States are maintained only for transitions between different semantic elements. For example, FIGS. 50, 52, and 53 illustrate data inputs that do not fully match any of the semantic entries in the semantic table 3042. In this situation, the PDA engine 3040 continues to parse the input data without maintaining any state information for the mismatched data strings.

As previously mentioned above in FIGS. 46-48, the semantic states in the PDA engine 3040 are substantially independent of the search string length. For example, the longer search string "WWWW." Replaces "WWW." By simply replacing the semantic entries "WWW." In the semantic table 3042 with the longer semantic entry "WWWW.". Can be retrieved instead.

Reconfigurable Semantic  Processor ( RSP )

45 illustrates a block diagram of a reconfigurable semantic processor (RSP) 3100 used in one embodiment for implementing the pushdown automaton (PDA) engine 3040 described above. RSP 3100 includes an input buffer 3140 for buffering packet data streams received through input port 3120 and an output buffer 3150 for buffering packet data streams output through output port 3152. do.

Direct execution parser (DXP) 3180 implements PDA engine 3040, is received at input buffer 3140 (eg, input “stream”), output to output buffer 3150 (eg, Output "stream"), which controls the processing of packets or frames that are recycled (e.g., recycle "stream") in recycle buffer 3160. Preferably the input buffer 3140, output buffer 3150 and recycle buffer 3160 are first-in first-out (FIFO) buffers.

DXP 3180 also controls the processing of packets by semantic processing unit (SPU) 3200 that handles the transfer of data between buffers 3140, 3150 and 3160 and memory subsystem 3215. Memory subsystem 3215 stores packets received from input port 3120, and is filed on July 21, 2005, co-pending and already incorporated by reference, application number 11 / 187,049, Unified Policy Management (UPM), filed in the application entitled Network Interfaces and Firewall Devices, and filed May 9, 2005, with application number 11 / 125,956, and titled Intrusion Detection System, An Access Control List (ACL) may be stored in the CAM 3220 used for firewall, virus detection, and some other operations.

The RSP 3100 implements a given PDA algorithm using at least three tables. Codes 3178 for retrieving generation rules 3176 are stored in parser table (PT) 3170. In one embodiment, the parser table 3170 includes the semantic table 3042 shown in FIG. 46. Grammar generation rules 3176 are stored in a production rule table (PRT) 3190. The generation rule table 3190 may include, for example, the semantic state map 3048 shown in FIG. 46. Code segments 3212 executed by SPU 3200 are stored in a Semantic Code Table 3210. Code segments 3212 may begin in accordance with SEP pointers 3078 in semantic state map 3048 shown in FIGS. 50-54.

Codes 3178 in parser table 3170 are stored, for example, in a matrix format or in a content-addressable format. In matrix format, the rows of parser table 3170 are indexed by non-terminal code NT 3172 provided by inner parser stack 3170. In one embodiment parser stack 3185 is stack 3052 shown in FIG. 46. The vertical lines of parser table 3170 are indexed by input data values (DI [N]) 3174 extracted from the head of data in input buffer 3140. In the content-addressable format, the concatenation of the non-terminal code 3172 from the parser stack 3185 and the input data value 3174 from the input buffer 3140 to the input buffer 3031 in FIGS. 50-54. Provide input to parser table 3170 as indicated.

The generation rule table 3190 is indexed by the codes 3178 from the parser table 3170. Tables 3170 and 3190 may be linked such that a query to parser table 3170 directly returns a generation rule 3176 that is applicable to non-terminal code 3172 and input data value 3174. The DXP 3180 replaces the non-terminal code on top of the parser stack 3185 with the generation rule (PR) 3176 returned from the PRT 3190 and continues parsing data from the input buffer 3140. .

The semantic code table 3210 is also indexed according to the codes 3178 generated by the parser table 3170 and / or according to the generation rules 3176 generated by the generation rule table 3190. In general, parsing results are determined by the DXP 3180 whether a semantic entry point (SEP) routine 3212 from the semantic code table 3210 should be loaded and executed by the SPU 3200 for a given generation rule 3176. Make it detectable.

SPU 3200 has several access paths to memory subsystem 3215, which provides a structured memory interface addressable by context symbols. The memory subsystem 3215, parser table 3170, generation rule table 3190 and semantic code table 3210 may be external memory devices such as on-chip memory, synchronous dynamic RAM (DRAM) and content addressable memory (CAM) or Combinations of these resources can be used. Each table or context may merely provide a context interface to the physical memory space shared in one or more other tables or contexts.

A maintenance central processing unit (MCPU) 3056 is coupled between the SPU 3200 and the memory subsystem 3215. MCPU 3056 performs some desired functions for RSP 3100 that can be reasonably achieved with traditional software and hardware. These functions are usually rare, time-critical functions that do not guarantee inclusion in the SCT 3210 due to complexity. Preferably, the MCPU 3056 also has the ability to request the SPU 3200 to perform tasks on the MCPU's behavior.

Memory subsystem 3215 is an Array Machine-Context Data Memory (AMCD) 3230 for accessing data in DRAM 3280 via a hashing function or content-addressable memory (CAM) lookup. It includes. The cipher block 3240 encrypts, decrypts or authenticates the data and the context control block cache 3250 caches the context control blocks to and from the DRAM 3280. The general cache 3260 caches data used in basic operations and the streaming cache 3270 caches data streams as data streams are written to and read from the DRAM 3280. Preferably, the context control block cache 3250 is a software controlled cache, ie the SPU 3200 determines when the cache line is used and freed. Each of the circuits 3240, 3250, 3260, and 3270 is connected between the DRAM 3280 and the SPU 3200. TCAM 3220 is connected between AMCD 3230 and MCPU 3056 and includes access control list (ACL) tables and other parameters that can be used to perform firewall, integrated policy management or other intrusion detection operations.

Detailed design optimization for the functional blocks of the RSP 3100, incorporated herein by reference and filed on January 24, 2003, in co-pending application 10 / 351,030, which is a reconfigurable semantic processor It is explained.

Parser table

46-54, the parser table 3170 may be implemented as a content addressable memory (CAM), where NT code and input data values DI [n] are generated rules in the PRT 3190. Is used as the key for the CAM to find the PR code 3176 corresponding to. Preferably, the CAM is a ternary CAM (TCAM) with ternary CAM (TCAM) entries. Each TCAM entry contains an NT code and a DI [n] match value. Each NT code may have multiple TCAM entries. Each bit of the DI [n] match value may be set to "0", "1" or "X" (representing "Don't Care"). This capability allows the parser table 3170 to require PR codes that only certain bits / bytes of DI [n] need to match the coded pattern to find a match. For example, one horizontal line of TCAM may contain the NT code NT_IP for the IP Destination Address field, followed by four bytes representing the IP destination address corresponding to the device incorporating the semantic processor. The remaining four bytes of the TCAM bar are set to "don't care". So when NT_IP and 8 bytes DI [8] are submitted to the parser table 3170, if the first 4 bytes of DI [8] contain the correct IP address, what are the last 4 bytes of DI [8]? If included, a match will occur.

Since the TCAM employs the "doncare" capability and there can be multiple TCAM entries for a single NT, the TCAM can find multiple matching TCAM entries for a given NT code and DI [n] match value. The TCAM prioritizes these matches through its hardware and outputs only the highest priority match. Moreover, when NT code and DI [n] match values are submitted to the TCAM, the TCAM attempts to match all TCAM entries in parallel with the received NT code and DI [n] match codes. Thus, the TCAM has the ability to determine if a match was found in the parser table 3170 in a single clock cycle of the semantic processor 3100.

Another way to look at this structure is like a "variable predictive ability" parser. As with eight bytes, even if a fixed data input segment is applied to the TCAM, the TCAM coding requires that the next generation rule (or a semantic entry as described in FIGS. 46-54) be used to determine which of the current eight bytes of the input. Allow to base on parts. If only one bit or byte anywhere in the current eight bytes at the head of the input stream is of interest for the current rule, the TCAM entry may be coded such that the rest is ignored during the match. Essentially, the current "symbol" can be defined for a given generation rule as any combination of 64 bits at the head of the input stream. By intelligent coding, the number of parsing cycles, NT codes and table entries can generally be reduced for a given parsing task.

The TCAM implementation of the generation rule table 3170 is incorporated herein by reference, filed July 14, 2005, and has application number 11 / 181,527, parser table / generation rule table configuration using CAM and SRAM. The phosphorus, co-pending patent application is described in more detail.

The system described above may use a dedicated processor system, microcontroller, programmable logic device or microprocessor that performs some or all of the above operations. Some of the operations described above may be implemented in software and other operations may be implemented in hardware.

For convenience, the operations are described as various interconnected functional blocks or separate software modules. However, this is not essential and there may be cases where these functional blocks or modules are equally concentrated in a single logic device, program or operation with unclear boundaries. In any case, the features of the functional blocks and software modules or the flexible interface may be implemented on their own or in conjunction with other operations in hardware or software.

Although the principles of the invention have been described and illustrated in the preferred embodiments of the invention, it will be apparent that the invention may be modified in construction and detail without departing from these principles. All changes and modifications that come within the spirit and scope of the following claims are claimed.

Claims (45)

A method of monitoring and filtering denial of service (DoS) attacks, Identifying a packet associated with a DoS attack if possible; Tracking the state of the packet as a DoS entry in one memory; Allowing the passage of a new packet when there is no previous DoS entry in the memory; And Adding a new DoS entry into the memory for the new packet after the new packet has already been allowed to pass. The method of claim 1, Receiving a packet that already has a DoS entry in the memory Dropping the packet when a DoS attack flag is set in the corresponding DoS entry; Updating the time stamp, counter, and DoS attack flag for the corresponding DoS entry when the time stamp is older than a predetermined time. The method of claim 1, Receiving a packet that already has a DoS entry in the memory; Allowing the packet to pass if the DoS attack flag in the DoS entry is not set; Incrementing a counter for a corresponding DoS entry after the packet is allowed to pass; When the counter is a DoS attack threshold and the time stamp for that DoS entry is within a predetermined time period, setting a DoS attack flag. In the network processing apparatus, And a processor configured to use the same memory subsystem as a forwarding information base (FIB) and for firewall policy management. 5. The method of claim 4, wherein the processor determines the destination address and firewall policy metrics contained in the packets of the same access control list (ACL) entries in the memory subsystem to make routing or switching decisions and perform firewall operations. Network processing device, characterized in that compared to the set. 5. The method of claim 4, wherein the ACL entries include predicates that match destination address and firewall policy metrics in packets and actions that indicate firewall or forwarding operations to perform on the packets. Network processing unit. The method of claim 4, wherein the processor, A data parser configured to identify address and firewall metrics in packets; And And one or more semantic processing units (SPUs) for performing both firewall operations and packet forwarding operations on the identified address and firewall metrics. In the processor of the language, A parser for parsing packets to identify sentence structure elements associated with network interface operations, and then launching microinstructions according to the identified syntax structure elements; And And one or more word processing units (SPUs) for performing network interface operations by executing microinstructions initiated by the direct execution parser. The method of claim 8, An input port adapted to receive data symbols; A direct execution parser for stack storing stack symbols, processing the stack symbols in response to received data symbols; A parser table in which there are production rule codes indexable through a combination of at least one received data symbol and a symbol provided by the parser; A generation rule table in which there are generation rules indexable with generation rule codes; And And a code table of words in which machine language instructions that are accessible by SPUs and indexed into the generation rule codes are present. 10. The system of claim 8, wherein the parser identifies DOS packets that may be part of a Denial of Service (DOS) attack and allows the SPUs to monitor the rate at which DoS candidate packets are received. The processor of claim 1, wherein the processor excludes or passes DoS candidate packets according to a rate. 9. The entry of claim 8, wherein the entry has predicates that match the elements of the packet word identified by the parser and actions used by one or more SPUs to determine which firewall operations should be performed on the packets. Word processor comprising an access control list (ACL) that includes data access. 12. The system of claim 11, further comprising a forwarding information base (FIB) comprising a destination address and a corresponding output port, wherein the one or more SPUs use a combination of a predicate from an ACL and a destination address from an FIB. A processor, characterized in that it determines the manner. 13. The method of claim 12, wherein the ACL includes different Uniform Resource Locator (URL) predicates associated with different output ports for the same destination address predicate, and the parser identifies a destination address and a URL value included in the packets. And the SPUs forward (forwarding) the packets to the output port identified in the ACL with a matching destination address predicate and URL predicate. 9. The system of claim 8, comprising a network address translation and / or port address translation (NAT / PAT) lookup table that maps public addresses to private addresses, the parser identifying one or more public or private addresses within the packets. Wherein the SPUs are commanded to replace their private or public address with the corresponding public or private address from the lookup table. 9. The method of claim 8, comprising an Internet Protocol (IP) version translation table that maps a first IP version format to corresponding addresses for a second IP version format, wherein the parser identifies an IP version format used in packets and Command to replace the addresses in the packets with another address for the relative IP version format. 9. The virtual private network (VPN) table of claim 8, wherein the parser comprises a virtual private network (VPN) table that associates a decryption key, a decryption algorithm identifier, and / or an authentication algorithm identifier with associated security parameter indexes (SPIs). To identify and instruct the SPUs to apply the identified SPIs to the VPN table and then decrypt packets according to the decryption key, decryption algorithm identifier, and / or authentication algorithm identifier received from the VPN table. Processor. In intrusion detection system, A data parser that identifies syntactic elements in the data stream; And A risk factor filtering circuit for filtering a risk factor from the data stream according to the sentence structure elements identified by a data parser. 18. The intrusion detection system of claim 17, comprising a delay buffer used by the risk factor filtering circuit to delay the output of the data stream for a substantially constant time while filtering the risk factors. 19. The method of claim 18, wherein the risk factor filtering circuit performs a first preliminary risk factor filtering on a data stream using a first set of preliminary access control list (ACL) filters and is generated according to the identified sentence structure elements. And performing a second risk factor filtering on the data in the delay buffer using a second set of ACL filters. 18. The method of claim 17, wherein the risk factor filtering circuitry is adapted to dynamically generate a set of risk factor filters matching the sentence structure elements from the identified sentence structure elements to be applied to risk signatures. Intrusion detection system, characterized in that for generating tokens. 21. The intrusion detection system of claim 20, wherein the tokens are generated only for syntax elements in the data stream that may be associated with risk factors, and no tokens are generated for other portions of the data stream. 18. The intrusion detection system of claim 17, wherein the data parser parses data according to symbols included in the parser stack. 23. The parser of claim 22, wherein the parser includes a parser table that includes generation rule codes that match different sentence structure elements in the data stream, wherein the generation rule codes are symbols of the parser stack and portions of the data stream. Intrusion detection system, characterized in that indexed by. 24. The method of claim 23, comprising a generation rule table with generation rules indexed by said generation rule codes, wherein some of the generation rules are executed when filtering risk factors from the data stream by a risk factor filtering circuit. An intrusion detection system characterized by addressing micro instructions. 18. The method of claim 17, further comprising receiving tokens identifying different sentence structure elements of different data streams processed by the different network processing devices from risk factor filtering circuits located in different network processing devices. And a central intrusion detector for generating filters in accordance with the different syntax elements and redistributing the filters to the different network processing devices. 27. The intrusion detection system of claim 25, wherein the central intrusion detector generates the filters in accordance with network processing operations performed by network processing devices that send the tokens. 18. The method of claim 17, further comprising a recirculation buffer that reconstructs fragmented packets from the data stream, prior to the risk factor filtering circuit that filters risk factors from the data stream. Intrusion detection system. In the processor of the language, A Direct Execution Parser (DXP) that identifies sentence structure elements in a data stream; And A word processor comprising one or more word processing units (SPUs) that perform intrusion detection operations on a data stream in accordance with the syntax elements identified by the direct execution parser. 29. The apparatus of claim 28, further comprising a parser table comprising sets of generation rule codes indexed by combining non-terminal symbols corresponding to sentence structure elements and portions of data streams. Word processor, characterized in that. 30. The system of claim 29, comprising a generation rule table comprising generation rules indexed by generation rule codes of the parser table, wherein at least some of the generation rules are executed by one or more SPUs to perform intrusion detection operations. A word processor comprising SPU entry point values that index micro instructions to be executed. 29. The processor of claim 28 wherein the one or more SPUs compare the packets in the data stream with a first set of prior ACL filters, and then exclude or store the packets according to the comparison result. 32. The processor of claim 31 wherein the one or more SPUs store packets for a fixed delay time when performing intrusion detection operations. 33. The system of claim 32, wherein the one or more SPUs generate tokens from the syntax elements identified by the DXP and provide the tokens to a risk factor analyzer that dynamically generates an access control list (ACL) that matches the tokens. Characterized by the processor. 34. The processor of claim 33 wherein the one or more SPUs discard a match to the dynamically generated ACL of stored packets. 29. The system of claim 28, further comprising a recycling buffer used by the one or more SPUs to reconstruct fragment packets in the data stream, wherein the direct execution parser identifies sentence structure elements within the reconstructed packets, One or more word processing units (SPUs) for performing intrusion detection operations in accordance with the identified sentence structure elements. 29. The method of claim 28, wherein the direct execution parser identifies Simple Mail Transfer Protocol (SMTP) packets in the data stream, instructs one or more SPUs to extract email elements from the SMTP packets, and uses the extracted email elements to extract SMTP packets. And a processor for generating a set of email risk factor filters to be applied to. In the PDA (PushDown Automaton) engine, A lexicon consisting of different sections corresponding to states of different PDA words, wherein at least some sections contain entries of one or more words that correspond to elements of the multi-character language that may be included in the input data. Contains a table, The word table is indexed by combining segments of input data with symbols identifying the states of the different words. 38. The PDA engine of claim 37, comprising a word state map identifying a state of a next PDA word according to an entry of a word in a current PDA state that matches the symbol and input data segment combination. 39. The stack of claim 38, comprising a stack for popping a symbol for associating with input data segments and for pushing a next symbol corresponding to a state of the next fish identified by the state map of the fish. PDA engine. 40. The PDA engine of claim 39, wherein the stack includes non-terminal symbols representing states of several previous PDA words. 38. The word table of claim 37, wherein the table of words is between different PDA language states depending on the elements of the word identified in the input data, but irrespective of the individual characters that may be included in the elements of the word. PDA engine characterized in that the transition. The word table of claim 37, wherein the word table comprises a content addressable memory (CAM), wherein entry positions of the word in the CAM match elements of the word in the input data to identify a state of the next word. PDA engine. 43. The PDA engine of claim 42, comprising a skip data map indexed by the CAM and identifying a quantity of input data to be moved to the PDA engine for comparison with entries in the language. 38. The processor of claim 37, comprising a reconstruction word processor (RSP) comprising one or more word processing units (SPUs) for performing additional operations on input data in accordance with the states of the word identified by the word table. PDA engine characterized by. 45. The PDA engine of claim 44, comprising a word entry point (SEP) map indexed by a word table to invoke micro instructions to be executed by one or more SPUs.

Images