Hardware holds value for classifying packets

Network security has become increasingly important as a way to protect the network, the information that flows through it and the user who accesses it. In applications like intrusion detection and prevention, stateful packet inspection and content filtering consume the largest share of processing bandwidth. While the network processing unit (NPU) is capable of performing the packet-processing functions in some cases, application-level content security and content inspection require a standalone packet classification system comprising a content inspection engine (CIE) and a network search engine (NSE). This article explores the growing value of hardware, including programmable state machines and discrete coprocessors, in developing secure applications.

Traditional implementations of content security are software-based, where the most critical element from the performance-point perspective is the implementation of a pattern-matching algorithm. In this article, the string search represents a reasonable approximation of pattern matching, although it is a simpler subset of a pattern match.

Several algorithms for text search applications exist, including the brute-force algorithm, which compares each text character with the character of each string, and the Boyer-Moore algorithm, which uses a search table that includes an "alphabet" of all symbols used in the policy. The drawback of both methods is that strings are evaluated sequentially resulting in performance that is directly proportional to the number of strings being matched against the text.

The Aho-Corasick algorithm is another type of algorithm that removes the dependency of the search performance from the number of strings by constructing a state graph and using the software implementation of a finite-state machine to locate the strings in the text. In 1998, Feliks Welfeld of Solidum Systems (now IDT Canada) patented the hardware implementation of the PSM for pattern-matching applications using a similar approach.

Programmable state machines
Let's consider the application of PSM to content classification of network traffic. In protocol data unit (PDU) classification, the process begins with the arrival of a bit or a group of bits (an event) that causes a machine state change. The PSM utilizes a state graph with nodes and edges, where a node is the convergence point of several edges and contains the addresses of the next nodes in the graph. Classification results are stored in so-called leafs.

Efficient programming of a PSM can be performed with a high-level programming language such as PAX pattern description language (PDL), an open-source fourth-generation programming language developed by IDT. Since the performance of a PSM-based pattern matcher is independent of the number of patterns or rules in the policy, the time required to evaluate the policy is proportionate to the size of the longest pattern.

Therefore, the device is capable of evaluating a policy containing any number of rules with equal or lower complexity, without incurring a performance penalty. The trade-off becomes the size of the memory used to store the policy graph.

A powerful header-parsing and payload pattern-matching capability is a necessary, but not sufficient, requirement for a comprehensive content security solution. A protocol state-tracking capability is also needed. Stateful content inspection combines both capabilities.

Tricky transitions
Communication protocols often have several states, including a session establishment state, established state and terminated state. When protocols are layered, state transitions become more complex. To track protocol state transitions efficiently, methods are needed to identify an event triggering the state transition (the arrival of a packet), extract state information (flow key) and store the flow key. These three steps must happen in real-time.

At data rates of several gigabits per second, this equates to a few microseconds at most. It is preferable to process all three steps in hardware, since software latency is usually higher and less deterministic. The most efficient solution for these challenges is to use a PSM-based content inspection engine with a network search engine where the CIE is the string matcher and the NSE is the table searcher.

In this scenario, the framer receives a packet and the NPU reads it. While the packet is being transferred over the bus, the CIE snoops the packet data and performs header parsing and matching. If the CIE recognizes an HTTP GET request, it extracts the key in the form of Internet Protocol addresses, and TCP ports in the form of a packet digest. The CIE packs the digest together as a key and transfers the key to the NSE.

A tag (e.g., Tag1) is generated when this packet is identified. The NSE interprets part of Tag1 as a 'learn' command. A field-programmable gate array may be needed to communicate the digest and command part of Tag1 to the NSE.

Let's assume the next packet belongs to the same flow. When it arrives, the CIE recognizes it as a valid TCP packet, generates an appropriate Tag1 and extracts the digest. This time, the command part of the tag will say 'match.' The NSE receives a key and matches it with the content of its table. If there is a positive match, the NSE generates the address of the location where the key was stored (Tag2).

The FPGA combines Tag1 and Tag2 and sends the resulting tag to the NPU, which keeps track of the packets and their associated tags, using that information to determine what to do with each packet and thereby saving valuable processing cycles.

As the need for security continues to grow, the design challenge of determining which functionalities should or should not be embedded increases commensurately.

Security has moved beyond encryption and now requires the incorporation of hardware, such as a PSM-based CIE, to address those demands adequately. The utilization of content specification engines in conjunction with network processing units optimizes network-processing architectures and enables the delivery of secure enhanced services.

Misha Nossik is director of network processing at IDT Inc. (Ottawa, Ontario).

See related chart