Deep packet inspection (DPI) has become one of the key components of a Network Intrusion Detection System (NIDS) and it compares packet content to a set of rules written in regular expression. The need to keep up with ever-increasing line speed has forced NIDS designers to move to hardware or high-speed memory where memory resources are limited. In this paper, we present LBM, a novel accelerating scheme for regular expression matching which converts the original byte stream into much shorter integer stream and then matches it with a variant of DFA, called StriD2FA. In the instance of LBM that we realize, 10 to 15 speedup is reasonable while the memory is much smaller than traditional DFA.

Today's file sharing networks are creating potential security problems to enterprise networks, i.e., the leakage of confidential documents. In order to prevent such leakage, we propose the Data Leakage Prevention System (DLPS) which is applied at the entrance of the enterprise network to filter out the outgoing sensitive information. The DLPS is based on a content scanning engine which defines a new type of matching problem, called longest overlap matching which also exits in many other applications as a basic problem where contents are delivered by small blocks. We study the problem by comparing it with the traditional pattern matching problem in Deep Packet Inspection (DPI) of Network Intrusion Detection Systems (NIDS) whose solutions are based on finite automata. We develop a new finite automata representation called Skip-Finite Automata (Skip-FA) which detects the packets carrying sensitive information by using default transitions to implicitly track the overlapping parts between packets' payloads and sensitive files. The simulation results shows that our system achieves a matching speed of about 10B+ per memory access for small file set (>;20KB) and 100B+ per memory access for large file set (>;2500KB). We also find that the memory consumption of Skip-FA is almost the same to that of the original files.

Multi-string matching is a key technique for implementing network security applications like Network Intrusion Detection Systems (NIDS). Existing DFA-based approaches always tradeoff between memory and throughput, and fail to has the best of both worlds. This paper extends the classic longest prefix principle from single-character to multi-character string matching and proposes a multi-string matching acceleration scheme named Independent Parallel Compact Finite Automata (PC-FA). In the scheme, DFA is divided into k PC-FAs, each of which can process one character from the input stream, achieving a speedup up to k with reduced memory occupation. Theoretical proof is given for the equivalency between traditional DFA and PC-FA approach. Experimental evaluations show that seven times of speedup can be practically achieved with a reduced memory size than up-to-date DFA-based compression approaches.

Regular expression (Regex) becomes the standard signature language for security and application detection. Deterministic finite automata (DFAs) are widely used to perform regex matching in linear time. Previously researches mostly focus on how to compress DFA to reduce memory requirements in recent years. However, memory requirement is not the only problem caused by DFA explosion when implementation DFA matching system. In this paper, we propose a new issue in DFA matching procedure. We notice that the DFA produced from regex never considers the physical locality of logical neighbor, which results in a low cache hit rate when using cache as matching accelerator. This problem becomes severe for current increasingly complex security regex which producing huge DFA with nearly no locality in physical location. We propose to solve this problem through reordering the state number of existing DFA and further put forward two methods on reordering DFA from different viewpoints. In our algorithms, we achieve more than twice cache hit rate compared with traditional method. Moreover, our methods will not affect the existing matching system. Hence, all the cache hit rate improvement is achieved without any cost in wire speed matching.

In Network Intrusion Detection System, De-terministic Finite Automaton (DFA) is widely used to compare packet content at a constant speed against a set of patterns specified in regular expressions (regex patterns). However, combining many regex patterns into a single DFA causes a serious state explosion. Partitioning the pat-tern set into several subsets, each of which produces a small DFA, is a practical way to deflate the state explosion. In this paper, we propose a regex pattern grouping scheme based on a new DFA model called Pattern-Based DFA (P-DFA) which supports efficient pattern-based op-erations, such as insertion, deletion, and etc. By using these basic operations, one can easily measure the state explo-sion when combining a set of regex patterns into a single DFA. Based on the privilege, we develop regex grouping algorithms for mitigating the state explosion in parallel and sequential matching environments, respectively. The evaluation shows that under the same constraints, our ap-proach requires only half the number of groups compared with the most well-known algorithms.

There is an increasing demand for network devices to perform deep packet inspection (DPI) to enhance network security. In DPI the packet payload is compared against a set of predefined patterns which can be specified using regular expressions (regexes). It is well-known that mapping regexes to deterministic finite automata (DFA) will suffer from the state explosion problem. Through observation, we attribute DFA explosion to the necessity of remembering matching history. In this paper, we investigate how to record the matching history efficiently and propose an extended DFA approach for regex matching called fcq-FA, which can make a memory size reduction of about 1000 times with a fully automated approach. In fcq-FA, we use pipeline queues and counters to help recording the matching history. Hence, state explosion caused by Kleene closure and repetitions can be definitely avoided. Further, it achieves a fully automated signature compilation with polynomial running time and space.

Accuracy and speed are the two most important metrics for Network Intrusion Detection/Prevention Systems (NIDS/NIPSes). Due to emerging polymorphic attacks and the fact that in many cases regular expressions (regexes) cannot capture the vulnerability conditions accurately, the accuracy of existing regex-based NIDS/NIPS systems has become a serious problem. In contrast, the recently-proposed vulnerability signatures (a.k.a data patches) can exactly describe the vulnerability conditions and achieve better accuracy. However, how to efficiently apply vulnerability signatures to high speed NIDS/NIPS with a large ruleset remains an untouched but challenging issue.

Deterministic Finite Automaton (DFA) is well-known for its constant matching speed in worst case, and widely used in multi-string matching, which is a critical technique in high performance Network Intrusion Detection System (NIDS) design. Existing DFA-based researches achieve high throughput at the expense of extremely high memory cost, so they fail to be used in situations like embedded systems where very tight memory resource is available. In this paper, we propose a memory-efficient multi-string matching acceleration scheme named Synergic Parallel Compact (SPC) Match Engine, which can provide a high matching speedup with no extra memory cost than the traditional DFA. Our scheme can be understood as consisting of k SPC-FAs, each of which can process one character from the input stream, causing achieving a constant speedup factor k with reduced memory occupation. Experimental evaluations with Snort and ClamAV rulesets show that a speedup of 9X can be practically achieved by a single SPC Match Engine instance with a reduced memory size than the up-to-date DFA-based compression approaches.

New applications such as real-time deep packet inspection require high-speed regular expression (regex) matcher, and the number of regexes in pattern store is increasing to several thousands, which requires a memory efficient solution. In this paper, a kind of hardware based compact DFA structure for multiple regexes matching called CPDFA is presented. According to statistics of regexes in Snort and L7-filter rules, transitions from each state to its next states are not evenly distributed. The summation of transitions from each state to its top three most popular next states takes about 90% of all the transitions. Therefore, CPDFA employs an indirect index table to represent transitions to top three most popular next states more efficiently. The remaining transitions which take about 10% of all the transitions are stored in direct transition table or K parallel SRAMs according to the number of remaining transitions from the same state is more than K or not. Simulation shows that CPDFA structure can save about 90% of memory storage comparing with the original DFA structure. By using pipelined architecture in FPGA, CPDFA can advance one character in one memory access cycle.

SYN flood attacks still dominate distributed denial of service attacks. It is a great challenge to accurately detect the SYN flood attacks in high speed networks. An intelligent attacker would evade the public detection methods by suitably spoofing the attack to pretend to be benign. Keeping per-flow or per-connection state could eliminate such a spoofing, but meanwhile, it also consumes extremely huge resources. We propose a more accurate and fast SYN flood detection method, named SACK2, which could detect all kinds of SYN flood attacks with limited implementation costs. SACK2exploits the behavior of the SYN/ACK-CliACK pair to identify the victim server and the TCP port being attacked, where a SYN/ACK packet is sent by a server when receiving a connection request and a CliACK packet is the ACK packet sent by the client to complete the three-way handshake. We utilize the space efficient data structure, counting Bloom filter, to recognize the CliACK packet. Comprehensive experiments demonstrate that, SACK2is the fastest and most accurate detection method compared with related methods which also leverage the packet pair's behavior. The memory cost of SACK2for a 10 Gbps link is 364 KB and can be easily accommodated in modern routers.

Per-flow queuing is believed to be able to guarantee advanced Quality of Service (QoS) for each flow. With the dramatic increase of link speed and number of traffic flows, per-flow queuing faces a great challenge since millions of queues need to be maintained for implementation in a traditional sense. In this paper, by setting only a small number of physical queues, we propose a Dynamic Queue Sharing (DQS) mechanism to achieve an equal performance to the pure per-flow queuing with a lower cost. The proposed mechanism is based on an interesting fact that the number of simultaneous active flows in the router buffer is far less than that of in-progress flows. In DQS, a physical queue is dynamically created on-demand when a new flow comes and then dynamically released when the flow temporarily pauses. Hashing and binary sorting tree (or linked list) are combined to manage the mapping between flows and queues, so as to isolate flows in different queues. Theoretical analysis and traces experiments are conducted to evaluate DQS. The results demonstrate that when the parameters are well set, the operation delay is less than two time cycles in average with an extra memory of 16k bits.

In order to reduce network congestion and fully use link bandwidth, when there are equal-cost-multi-paths (ECMPs) between a forwarding node and a destination subnet, traffic load should be balanced among ECMPs and packets of the same TCP flow should reach destination host in the same order. An algorithm called LRU-based caching with counting (LCC) is proposed. Packet length differentiation is considered to achieve load balance by adapting a counter for each ECMP, and counter overflow is solved by relative counting and restrictions. UDP packets only need to be concerned to achieve load balance. Furthermore, flow delay differentiation forwarding to different hosts of the same destination subnet is transformed to entries in cache invalided time period difference. Simulation shows that when delay differentiation among ECMPs is not significant, storage requirement is small, only one cycle is needed for each cache lookup, load balance is near optimal, and only 2% of packets are out of order