High-speed network packet processing is of paramount importance for many aspects of our society. We present HashCache, a new state tracking approach well suited for FPGA implementation. HashCache is a hash-based key-value store which combines high speed state lookup and update rates by utilizing a novel eviction strategy called Not Recently Sequenced. We demonstrate that our FPGA-based HashCache implementation is able to statefully process 200 MPPS of full duplex traffic both with benign data and in an attack scenario.

Today, the most widely distributed type of firewalls are software firewalls, running as applications on standard systems. Dedicated networking hardware like SDN switches has also been used to implement firewall functionality, although their native classification capabilities are restricted to relatively simple checks, such as subnet tests. However, native SDN hardware can satisfy high performance requirements that would be challenging for standard software firewalls. This motivates to build a hybrid combination of fast SDN hardware with a standard software firewall. Our approach directly offloads simple rule policies instead of flows to the SDN switch, in order to exploit the limited storage capacity more efficiently. An effective packet diversion algorithm based on header space analysis avoids expensive communication with the back-end. This way, it can achieve the throughput of a native SDN switch while still being able to resort decisions to the full extent of a software firewall. Our evaluation demonstrates a 23-fold classification performance increase over a standard software firewall.

Packet classification is a core feature needed in firewalls, SDN switches, and QoS routers. Current research to accelerate the classification with hardware employing Field-programmable Gate Arrays (FPGAs) created a variety of approaches, with significant differences in terms of hardware resource requirements, memory usage, configuration update time, and power dissipation. However, there is no optimal, universal method for classification at link rate, due to inherent conflicts between large generic circuits with high resource consumption, and optimized circuits with limited versatility. Thus, current implementations have different trade-offs in terms of memory usage, resource requirements, power consumption, and flexibility. As a new approach to tackle this challenge, we present a hybrid concept that combines an highly optimized configuration-specialized and thus energy- and resource-efficient classification circuit with a generic matching circuit whose configuration can be updated quickly. The combined circuit can thus support reasonably fast configuration updates, has a low power dissipation, and can process network packets at link rate.

Firewalls, key components for secured network infrastructures, are faced with two different kinds of challenges: first, they must be fast enough to classify network packets at line speed, and second, their packet processing capabilities should be versatile in order to support complex filtering policies. Unfortunately, most existing classification systems do not qualify equally well for both requirements: systems built on special-purpose hardware are fast, but limited in their filtering functionality. In contrast, software filters provide powerful matching semantics, but struggle to meet line speed. This motivates the combination of parallel, yet complexity-limited specialized circuitry with a slower, but versatile software firewall. The key challenge in such a design arises from the dependencies between classification rules due to their relative priorities within the rule set: complex rules requiring software-based processing may be interleaved at arbitrary positions between those where hardware processing is feasible. Therefore, we discuss approaches for partitioning and transforming rule sets for hybrid packet processing. As a result, we propose HyPaFilter+, a hybrid classification system consisting of an FPGA-based hardware matcher and a Linux netfilter firewall, which provides a simple, yet effective hardware/software packet shunting algorithm. Our evaluation shows up to 30-fold throughput gains over software packet processing.

With network traffic rates continuously growing, security systems like firewalls are facing increasing challenges to process incoming packets at line speed without sacrificing protection. Accordingly, specialized hardware firewalls are increasingly used in high-speed environments. Hardware solutions, though, are inherently limited in terms of the complexity of the policies they can implement, often forcing users to choose between throughput and comprehensive analysis. On the contrary, complex rules typically constitute only a small fraction of the rule set. This motivates the combination of massively parallel, yet complexity-limited specialized circuitry with a slower, but semantically powerful software firewall. The key challenge in such a design arises from the dependencies between classification rules due to their relative priorities within the rule set: complex rules requiring software-based processing may be interleaved at arbitrary positions between those where hardware processing is feasible. We therefore discuss approaches for partitioning and transforming rule sets for hybrid packet processing, and propose HyPaFilter, a hybrid classification system based on tailored circuitry on an FPGA as an accelerator for a Linux netfilter firewall. Our evaluation demonstrates 30-fold performance gains in comparison to software-only processing.

Network packet classification is a key functionality for packet filters and firewalls, and its performance is crucial for such systems to maintain a high packet throughput under heavy load situations. However, many existing packet filters employ slow classification algorithms which cannot provide the required lookup performance due to slow rule set traversal. In this work, we address this problem by providing a novel rule set transformation strategy called Minflate which combines the advantages of existing orthogonal transformation schemes by first minimizing a source rule set and then encoding decision trees into the minimized rule set. Our results show that the Minflate-generated rule sets are both small and can in many cases be traversed faster than rule sets transformed by existing techniques in isolation.

Packet classification-the matching of packet headers against a predefined rule set-is a crucial functionality of firewalls, intrusion detection systems, and SDN switches. Most existing classification algorithms trade setup time for classification speed-that is, the packet classification is fast, but the transformation of rules set into the corresponding search data structure takes a considerable amount of time. This preprocessing time, however, poses a significant challenge for systems where rule sets can often change. Hence, these systems often use slow classification algorithms that support frequent rule set updates, which drastically limits their achievable throughput. In this work, we present a novel algorithmic technique which is able to "upgrade" an arbitrary existing classification algorithm to support fast updates, while still providing high lookup performance. Our evaluation demonstrates that our proposed technique exceeds the matching performance of existing dynamically updatable algorithms by an order of magnitude while providing the same level of update responsiveness.

Network packet classification plays a pivotal role in packet-switched networks; it is at the heart of many functions including firewalling, QoS routing, and OpenFlow-based switching. However, packet classification is a hard problem, as packets must be classified within a short time frame. Existing classification techniques use sophisticated data structures which are traversed by generic search algorithms - that is, the algorithm is static, while the data structure reflects the configuration of the classifier. In this paper, we propose to break up the strict separation between data structure and algorithm by specializing the algorithm's implementation on the specific classification rules. We demonstrate the feasibility of our approach by introducing JitVector, which builds upon the well-known bit vector classification algorithm, but generates instance-specific machine code at runtime. In our evaluation, which also includes an integration into the OpenFlow Reference Switch, we show that JitVector achieves significant performance gains over an equivalent generic search scheme.

Network packet classification is performed by a wide variety of network devices, like routers or firewalls. Accordingly, researchers have put great efforts in the development of fast packet classification algorithms. However, despite the fact that such approaches have been around for over a decade, most classification systems used in practice still rely on the slow linear search approach. In this work, we propose a methodology that enables linear search-based systems with jump semantics to take advantage of the superior matching performance of decision tree algorithms, without the need to touch the underlying system implementation. By performing source-to-source transformations on packet classification rule sets, we encode decision trees inside of the modified rule sets in order to guide and tweak the originally linear matching process. We implement this in a proof-of-concept tool which transforms Linux iptables firewall rule sets. Our evaluation demonstrates that throughput performance boosts of one order of magnitude and more are possible - without changing the semantics of the rule set, and without any modifications to the matching engine.

Many companies and institutions employ packet filter firewalls in order to effectively regulate network traffic. Unfortunately, the constant growth of network bandwidth makes the task of matching packet headers against potentially large rulesets more difficult, and prohibits the sole use of entirely software-based firewalls which cannot cope with such huge amounts of traffic. Instead, high-speed firewalls are often implemented in ASICs which offer a high degree of parallelism, many opportunities for operation pipelining, and low-latency access to network data. However, due to their static nature, ASICs must provide generic filtering circuitry that is hardly able to take full advantage of firewall ruleset properties, thus leading to a waste of hardware resources.

The process of matching the header fields of network packets against a set of rules is a performance critical task of firewalls. Software-based solutions have no chance to keep pace with the ever-growing data rates in high-speed networks. However, specialized filtering hardware is costly because complex logic is required in order to be able to apply arbitrary rulesets to a packet stream. By adapting the implemented logic to the specific firewall ruleset, FPGAs allow for much more specifically tailored and thus more efficient processing than ruleset-independent circuits in an ASIC. We present MPFC, a method to generate customized firewall circuits in the form of synthesizable VHDL code for FPGA configuration. The highly parallel MPFC circuits achieve a deterministic throughput of one packet per clock cycle, can be operated at high clock frequencies, and provide orders of magnitudes shorter processing latencies than previous work in this direction.