Paul Chaignon
email: paul.chaignon@orange.com

Diane Adjavon
email: adjavon@eurecom.frkahinalazri

Jérôme François
email: jerome.francois@inria.fr

Olivier Festor
email: olivier.festor@inria.fr

Offloading Security Services to the Cloud Infrastructure

Keywords:

Cloud applications rely on a diverse set of security services from application-layer rate-limiting to TCP SYN cookies and application firewalls. Some of these services are implemented at the infrastructure layer, on the host or in the NIC, to filter attacks closer to their source and free CPU cycles for the tenants' applications. Most security services, however, remain difficult to implement at the infrastructure layer because they are closely tied to the applications they protect.

In this paper, we propose to allow tenants to offload small filtering programs to the infrastructure. We design a mechanism to ensure fairness in resource consumption among tenants and show that, by carefully probing specific points of the infrastructure, all resource consumption can be accounted for.

We prototype our solution over the new high-performance datapath of Linux. Our preliminary experiments show that an offload to the host's CPU can bring a 4-6x performance improvement. In addition, fairness among tenants introduces an overhead of only 14% in the worst case and approximately 3% for realistic applications.

INTRODUCTION

To defend against network threats, cloud applications rely on a diverse set of security services from application-layer rate limiting to TCP SYN cookies and application firewalls. Many of these services are closely tied to the applications they protect; for example, anti-DDoS services often rely on deep knowledge of targeted applications to filter malformed packets. These security services, however, share a common characteristic: they all implement a form of filtering, and as such, they are best executed closer to the wire.

In the past few years, new and faster packet processing frameworks have been developed at the infrastructure layer. Several software switches can now execute arbitrary programs [START_REF]BESS: Berkeley Extensible Software Switch[END_REF][START_REF]Vector Packet Processing (VPP)[END_REF][START_REF] Jackson | SoftFlow: A middlebox architecture for Open vSwitch[END_REF],

the Linux kernel allows userspace processes to execute programs at the lowest point of the networking stack [START_REF] Corbet | Early packet drop-and more-with BPF[END_REF], and some Smart-NICs can execute offloaded programs on their embedded CPUs [START_REF] Kicinski | eBPF/XDP hardware offload to SmartNICs[END_REF]. These frameworks have strong execution constraints inherited from their environment or required to achieve higher performance. For example, several of the above cited examples impose a bounded execution time to ensure programs running in the kernel or in the NIC terminate. In addition, they have a run-to-completion execution model: a single thread processes each packet from reception to transmission, often without interruptions (e.g., context switches).

These high-performance packet processing frameworks are already leveraged to offer security services to cloud tenants [START_REF] Firestone | VFP: A virtual switch platform for host SDN in the public cloud[END_REF]. Nevertheless, because they are tighly coupled to the services they protect, many security services remain difficult to abstract and expose to tenants.

In this paper, we discuss and propose a framework to offload security services from cloud applications to the cloud infrastructure. The benefits of filtering packets at the infrastructure layer, before sending them to VMs or containers, have been noted in previous work [START_REF] Cardigliano | vPF_RING: Towards wire-speed network monitoring using virtual machines[END_REF]. We propose to go a step further and enable tenants to offload near-arbitrary programs to the infrastructure, significantly extending the range of candidate programs for offload compared to stateless filters. As concrete examples, in Section 4, we describe and evaluate two programs we offloaded using our framework: a SYN cookie mechanism similar to that of the Linux kernel and a DNS rate-limiter.

The main challenge to enable the offload of these programs resides in the high-diversity of their resource consumptions. Current security services for tenants (firewalling, stateless filtering, etc.) executed at the infrastructure layer have fairly stable and wellunderstood resource consumptions. For this reason, fairness can be achieved by limiting the number of processing steps taken for each tenant (e.g., the number of rules for firewalls). With our proposal, however, tenants can offload programs with very different resource consumption to the infrastructure. Without a mechanism to ensure fairness, a tenant with a resource-hungry program could starve other tenants.

To achieve fairness among tenants independantly of their own custom offloaded programs, we monitor the CPU time consumed by each packet's processing. We then ensure each tenant does not consume more than its fair share of CPU time, while retaining the run-to-completion model typical of these execution environments. We first describe the design of our framework and the algorithm for our CPU fairness mechanism in Section 2. In Section 3, we detail our implementation over XDP, Linux's high-performance datapath. Section 4 presents our initial evaluation results and shows that our framework provides a 4-6x performance improvement for containerized applications while enforcing fairness with a 14% worst-case overhead. Finally, we discuss related works and conclude this paper in Sections 5 and 6 respectively.

+ + host_α 1 1 0 0 1 0 1 0 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0

DESIGN

In this section, we first describe the different steps executed when tenants decide to offload a security service to the underlying infrastructure. We then elaborate on our mechanism to ensure CPU fairness among tenants while retaining the high-performance runto-completion model. Finally, we discuss the feasibility of the perpacket tracing of CPU consumption.

Offload Workflow

As illustrated in Figure 1, from the implementation of security programs to their actual execution at the infrastructure layer, a number of steps must be executed to ensure a fair, secure offload.

As a first step to any offload, cloud tenants must port their security programs to the infrastructure environment. In our prototype we only support C programs, but support for other languages is possible with the appropriate compiler. Porting programs to the infrastructure environment usually involves changing a few API calls, such as the initial reception of the packet pointer, and replacing data structure to use those exposed by the infrastructure environment.

Once programs are written, tenants can request an offload to the infrastructure through their usual cloud API. They send the source code of the program to offload and the list of containers or virtual machines they want to protect.

New tenant programs are sent to the Compiler agent. For each host, the Compiler agent relies on a template to combine all tenant programs into a single infrastructure program. The template also contains (1) a demultiplexer to execute the code from the appropriate tenant when a packet arrives on the system and (2) a few operations to enforce fairness among tenants. Since programs are attached to a tenant and not to specific applications, the demultiplexer only needs to select the appropriate tenant, not the exact container or virtual machine; for example, demultiplexing can rely on the VLAN identifier or the GRE key. This infrastructure program is then compiled into a bytecode the infrastructure environment can understand (in our case, BPF bytecode to install in the kernel or in the NIC) and sent to all hosts that require an update, i.e., all hosts where the new tenant program should be executed.

On each host, an agent receives the infrastructure program and replaces the currently running program with the new one. We expect the replacement of a program to be an atomic operation, as is the case in the Linux kernel.

Our fairness mechanism relies on an assignment of tokens to tenants. Tenants consume tokens as they process packets and the host agent produces new tokens at regular intervals. The CPU share of each tenant on the host (or in the embedded CPU of the NIC) is a direct function of the number of tokens produced by the host agent for that tenant. By default, all tenants get the same CPU fair share, but the fairness mechanism allows for different CPU shares among tenants.

Run-to-Completion CPU Fairness

Many high-performance execution environments at the infrastructure have a run-to-completion model in which packets are processed from reception to transmission (or end of processing) by a single thread, with as few interruptions as possible. Retaining this model with several programs competing for CPU resources calls for a non-preemptive CPU scheduler as, with a preemptive scheduling policy, programs (or, to be exact, their processes) would be regularly interrupted by the scheduler.

Fine-grained CPU allocation. The usual approach to allocate CPU resources to multiple programs in a run-to-completion environment consists in giving each program its own core. This approach has several drawbacks. First, it requires a prior demultiplexing step, to assign packets to the appropriate core. Not all NICs support programmable demultiplexing policies to cores and, even when they do, they are often limited to a few specific fields (e.g., L4 ports or MAC addresses). Second, this approach doesn't allow for fine-grained allocation of CPU resources. Contrary to pre-emptive scheduling policies, it may not, for example, assign half a core to a first application and the remaining cores to a second application.

Token consumption. As described in the previous section, for each host, all tenants' programs are incorporated into a single infrastructure program. We therefore execute all programs as part of the same process and apply our fairness mechanism on each tenant program. Programs consume tokens in proportion to the time they spend on the CPU.

Fairness is enforced indirectly: instead of limiting the CPU time for each program-which would require a preemptive scheduler-, we limit the packet rate depending on the current CPU consumption (number of tokens remaining).

The fairness mechanism is part of the infrastructure program; it runs after the demultiplexer and before the tenants' programs. It rejects the packet if its tenant's bucket contains a null or negative number of tokens (we explain the negative case below). If the bucket contains a strictly positive number of tokens, the tenant's program is exeuted.

Once the CPU consumption for the packet has been fully accounted for (see Section 2.3 below), an equivalent number of tokens is removed from the bucket. At this point, the bucket may contain a negative number of tokens since we don't know before executing the program if there are enough tokens to process the packet.

Token generation. Whereas the rate-limiting and consumption of tokens is straighforward, the generation of tokens requires more care. Our token generation algorithm, summarized in Algorithm 1, allows for different generation rates among tenants (i.e., different CPU shares). In addition, it implements a work-conserving allocation of CPU time: a tenant that already consumed its fair share may use the fair share of idle tenants, if any.

Algorithm 1 Token generation algorithm

▷ Each tenant i has a bucket b i and a token generation speed v i . Tokens are generated at ∆t intervals. Buckets contain a maximum of B tokens. ▷ Distribute tokens to buckets and count surplus tokens: for all j ∈ J do 11:

1: r i ← v i • ∆t 2: r ′ ← 0 3: for all i ∈ I do 4: r ′ ← r ′ + r i -min(B -b i , r i ) 5: b i ← min(B, b i + r i
r j ← r ′ • v j i ∈ J v i 12: r ′′ ← r ′′ + r -min(B -b i , r i ) 13: b j ← min(B, b j + r j ) 14: end 15: r ′ ← r ′′ 16: end
The generation algorithm runs at ∆t intervals, in two steps. In the first step, each tenant receives a number of tokens proportional to their fair share (lines 1 and 5), expressed as a token generation speed, v i . Each tenant's bucket may contain a maximum of B tokens and surplus tokens are kept for the second step (line 4).

The second step runs as many times as necessary to distribute the surplus tokens fairly among tenants. At each iteration, surplus tokens are distributed among tenants who do not yet have full buckets, as a ratio of their speed compared to other tenants with non-full buckets (lines 11 and 13). This second step stops when there are no more surplus tokens or when all tenants have full buckets. This step makes the allocation of CPU time work-conserving, as it ensures that tokens won't be wasted as long as there are busy tenants.

Per-Packet Tracing of CPU Shares

To properly apply our fairness mechanism, we need to monitor all CPU consumption on the infrastructure, including for tenants that didn't offload security services.

As a toy example, consider a server with only two tenants, the first with an offloaded program that consumes few CPU cycles per packet, the second without any offloaded program. If the first tenant receives and drops a large number of illegitimate packets, she will consume less CPU cycles per packet, on average, than the second tenant. However, if we only accounted for and limited the CPU consumption of tenants with offloaded programs, the second tenant would always receive the same-or a larger-number of packets than the first tenant, who may be rate-limited by our fairness mechanism. The second tenant would therefore receive a larger, undue share of the CPU time.

We therefore need to trace, for each packet and for all tenants, the CPU time consumed in the infrastructure. In particular, we need to monitor all CPU time consumed on the infrastructure, i.e., all CPU time that is not already allocated through traditional preemptive schedulers (be it in operating systems or in hypervisors).

After an offloaded program has been run on a packet, there are three possible actions: the packet may either be dropped, sent up the networking stack to the tenant's domain, or retransmitted back on the interface (as is the case with the TCP SYN proxy for example). We therefore need to account for (1) the CPU time spent to execute the offloaded program and (2) the CPU time spent for any subsequent action. We therefore need to install probes to monitor the CPU time spent for the three possible actions. We detail their implementation in Section 3. In each case, once the packet is fully processed, we remove the CPU time spent on that packet from its tenant's bucket.

IMPLEMENTATION

eXpress Data Path prototype. We prototyped our design on eXpress Data Path (XDP), the recent high-performance datapath for Linux [START_REF] Corbet | Early packet drop-and more-with BPF[END_REF]. XDP allows userspace programs to load BPF bytecode programs in the kernel, to be executed on the reception of packets in the driver, right after packets are DMAed from the NIC to the main memory.

BPF is a bytecode and an infrastructure in the kernel to execute userspace-defined programs at multiple hook points (e.g., in the driver with XDP, but also in the traffic classifier or on functions with kprobes for tracing use cases). A key characteristic of BPF is its verifier, a piece of software in the kernel that verifies programs are safe to execute. For example, it guarantees the absence of infinite loops and the correctness of memory accesses. Of particular interest to our work is the use of BPF by several other high-performance packet processing frameworks [START_REF] Chaignon | Oko: Extending Open vSwitch with stateful filters[END_REF][START_REF] Kicinski | eBPF/XDP hardware offload to SmartNICs[END_REF], which eases porting of our prototype to these frameworks.

In our prototype, buckets are implemented using an array map of counters; buckets are updated by a separate process, running in userspace.

CPU consumption tracing. We also use BPF programs attached to kprobes to trace the CPU consumption at the infrastructure for each packet. Using BPF for tracing allows us to share metadata on packets (e.g., start time of processing and tenant identifier) with the XDP program.

To measure the CPU time for retransmitted packets and packets sent to the tenant's domain, we trace two functions in the network device driver. These two functions are specific to the driver we use, but we expect finding equivalent functions for other drivers to be straightforward; these functions only need to mark the point in time when the packet is retransmitted (respectively, sent to the tenant's domain) and don't need to access any particular information.

EVALUATION

This section aims to evaluate two main aspects of our design and prototype: (1) the cost and benefit of the fairness mechanism and (2) the performance gain from the offload itself.

Evaluation Setup

Our testbed consists of two servers connected with Mellanox 40 Gbps NICs. The Device Under Test (DUT) has an Intel Xeon E5-2640 2.6 Ghz with hyper threading disabled, 20 MB of L3 cache, and 16 GB of DDR4 memory at 2133 MHz. The DUT runs Linux 4.9 without the KPTI patch.

In all experiments, we use a single core at the DUT. To do so, we ensure all packets arrive on the same queue at the NIC, and therefore on the same CPU on the host. Packet processing performance with several cores strongly depends on the efficiency of packet demultiplexing to queues at the NIC (e.g., receive-side scaling).

We configure three tenants on the DUT, each with a single Docker container and their own VLAN. Tenant 1 and 2 offloaded a TCP SYN cookie proxy and a DNS rate-limiter in the host's highperformance datapath respectively, whereas tenant 3 doesn't have any security service offloaded. All tenants receive the same number of tokens at each generation interval and, therefore, have the same CPU share on the host. The second server uses MoonGen [START_REF] Emmerich | Moon-Gen: A scriptable high-speed packet generator[END_REF] to launch a TCP SYN flood against the first tenant, a DNS flood against the second, and replay a CAIDA packet capture against the third.

Each experiment lasts 5 minutes and we report the mean and the standard deviation over 10 runs.

Fairness Mechanism

First, using our probes in the driver, we measure the CPU consumption of each tenant as a percentage of the total CPU time. Figure 2 depicts the results, both with and without our fairness mechanism.

While they all receive the same number of packets, because tenant 3 receives all packets in userspace and does not drop any at the infrastructure, she consumes the majority of the CPU time on the host. In contrast, due to her offloaded program, tenant 2 requires few CPU cycles to drop packets. Nevertheless, without the fairness mechanism, tenant 2 is allowed a smaller share of the CPU time. This result illustrates the need for our fairness mechanism to ensure that one tenant will not starve other colocated tenants.

We next measure the overhead caused by the installation of our probes in the driver. On the DUT, we configure three application, in Docker containers: the first simply drops packets and serves as a baseline to measure the worst possible overhead, the second is an Unbound DNS recursive server, and the last an Apache HTTP server. On the second server, we configure MoonGen to send DNS requests to the first two applications. For the Apache server, we use Apache Benchmark to send a flood of HTTP GET requests. We measure the maximum number of packets (respectively, requests for the Apache server) the application is able to process on a single core, both with and without our probes.

As shown in Figure 3, our probes in the driver only add a slight overhead on the end-to-end performance of applications. Because our probes require a constant number of cycles per packet, the overhead is larger for application that require few cycles to process each packet, as with the baseline application. While for the Apache application we measure 2.6% overhead, we could not measure any perceived overhead for the Unbound DNS server. Because it performs the minimum operations possible on each packet (receive and drop), the baseline application provides a good estimate of the worst possible overhead.

To compare our fairness mechanism to the Linux preemptive scheduler, we ported it to DPDK. Our DPDK application polls packets directly from the NIC, enforces fairness, and sends packets back to the NIC; the offloaded programs are empty for this evaluation. Tokens are generated in a second thread running on the same core as the DPDK process. We compare this setup with a second DPDK-based setup using the Linux schedulers and the cgroups feature: each program runs as a DPDK task and the Linux scheduler preempts tasks to enforce fairness. In both setups, programs are assigned an equal share of the CPU and run on a single core. We vary the number of concurrent programs and measure the throughput at the sink.

As shown in Figure 4, because it breaks the run-to-completion model of DPDK, the Linux scheduler has a severe impact on performance: the frequent context switches between tasks increasingly impede performance as the number of concurrent tasks grows. Conversely, our approach has a lower overhead and its performance only slightly decreases with the number of tasks; in our system, only the complexity of the token generation algorithm depends on the number of programs.

Performance Gain

Finally, we evaluate the performance gain our prototype can bring to applications by allowing them to offload security services to the infrastructure. We port our TCP SYN cookie proxy and our DNS rate-limiter to userspace, on the Linux API, and execute them both in containers. We compare the performance of these two applications to their offloaded counterparts.

Figure 5 shows the packet processing performance in each case for the two applications. The offload to the infrastructure-in this case the host's kernel-brings a 4-6x performance improvement by avoiding unecessary packet copies to userspace and leveraging the higher performance of the infrastructure's datapath. Whereas the rate-limiter drops most packets, the TCP proxy replies to received flood packets with a TCP SYN ACK packet (with a SYN cookie) and therefore requires more cycles per packet. For this reason, the performance gain is lower for the TCP proxy.

Note that this performance improvement is only possible because we can ensure each tenant still receives a fair share of CPU time.

We also note that the performance improvement largely depends on the offload capabilities of the underlying infrastructure. For this reason, we expect a slightly better performance improvement if the infrastructure relies on kernel bypass technologies (in which case, solutions such as [START_REF] Chaignon | Oko: Extending Open vSwitch with stateful filters[END_REF][START_REF] Jackson | SoftFlow: A middlebox architecture for Open vSwitch[END_REF] could be used to execute offloaded programs) and a much stronger improvement if programs can be offloaded to a SmartNIC.

Discussion

Because it takes a few tens of CPU cycles to read a packet in memory, identify its tenant, and free its memory buffer [START_REF] Addanki | Controlling software router resource sharing by fair packet dropping[END_REF], a tenant that does not have any tokens left but still receives a large number of packets may impact the overall performance. Since this weakness affects all CPU-based systems, one approach to mitigate it could leverage upstream hardware devices (e.g., NICs and switches) to install a first, coarse-grained rate-limiter and filter oversized flows before they reach the host's CPU. We leave the design of such a defense to future work.

RELATED WORK

Recent works to accelerate packet processing at the infrastructure layer provided a strong motivation for this work. Packet processing programs can now be executed at the software switch [START_REF]BESS: Berkeley Extensible Software Switch[END_REF][START_REF]Vector Packet Processing (VPP)[END_REF][START_REF] Chaignon | Oko: Extending Open vSwitch with stateful filters[END_REF][START_REF] Jackson | SoftFlow: A middlebox architecture for Open vSwitch[END_REF], at the lowest point of the Linux kernel networking stack [START_REF] Corbet | Early packet drop-and more-with BPF[END_REF], or even in NICs [START_REF] Firestone | VFP: A virtual switch platform for host SDN in the public cloud[END_REF][START_REF] Kicinski | eBPF/XDP hardware offload to SmartNICs[END_REF], in all cases with significant performance gains. Our work allows cloud tenant to benefit from these recent advances to secure their applications with high-performance.

Although they do not allow arbitrary program offload to the infrastructure, both [START_REF] Firestone | VFP: A virtual switch platform for host SDN in the public cloud[END_REF] and [START_REF] Ahmed | InKeV: In-kernel distributed network virtualization for DCN[END_REF] leverage recent packet processing advances to build services for tenants at the infrastructure layer. In particular, Ahmed et al. designed InKeV [START_REF] Ahmed | InKeV: In-kernel distributed network virtualization for DCN[END_REF], a framework to manage network function chains running in the host's kernel. InKeV also relies on BPF to load network functions in the host's kernel, but loads BPF programs higher in the networking stack, at the Linux tc classifier. We execute BPF programs in the device driver using XDP as it avoids unnecessary memory allocations (sk_buff) for dropped packets [START_REF] Corbet | Early packet drop-and more-with BPF[END_REF]. In addition, InKeV targets network services offered by the cloud provider (e.g., routing, switching, and firewalling) and does not provide a viable mechanism to execute tenant's programs concurrently. For example, if the cloud provider was to offer a TCP SYN proxy service to its tenants using InKeV, (1) it would not be customizable by tenants (e.g., to change the cookie generation algorithm) and (2) it would not prevent a tenant that isn't using the service from other tenants (as shown in Section 4.2).

In [START_REF] Cardigliano | vPF_RING: Towards wire-speed network monitoring using virtual machines[END_REF], Cardigliano et al. propose vPF_RING, a framework to accelerate network monitoring in virtualized environments. Similarly to our work, they let tenants define filters that are applied in the host's kernel, using PF_RING. However, with vPF_RING, tenants can only install simple, stateless filters at the infrastructure layer. While these may be enough for packet capture or simple security services such as stateless firewalling, more complex programs are required to implement most security services. In contrast, we allow tenants to offload complex, stateful security services, and we address the associated challenge (that is, ensuring all tenants get their fair share of resources).

A recent trend in networking research discusses outsourcing enterprise network functions to the Cloud and focuses on the associated challenges [START_REF] Gibb | Outsourcing network functionality[END_REF][START_REF] Poddar | SafeBricks: Shielding network functions in the cloud[END_REF][START_REF] Sherry | Making middleboxes someone else's problem: Network processing as a cloud service[END_REF]. In contrast, we consider the offload to the host of network services already deployed in the cloudalthough it may be an on-premise, private cloud. Offloading to the host improves performance without requiring complex traffic redirections; packets are processed on their original path to the applications, albeit closer to the wire. In addition, our approach doesn't require additional protections [START_REF] Poddar | SafeBricks: Shielding network functions in the cloud[END_REF] against the third party executing network services since the host is already trusted to run the tenant's VMs or containers.

In a concurrent work [START_REF] Addanki | Controlling software router resource sharing by fair packet dropping[END_REF], Addanki et al. designed a fair dropping mechanism close to ours, though for a different use case. Their system aims to enforce max-min fairness among different flows inside software switches. Compared to our system, theirs processes packets in batches to improve performance, but it approximates the per-packet CPU consumption from the exact CPU consumption for a whole batch.

Finally, offloading tenant's services to the infrastructure raises evident security concerns. While the frameworks we have discussed have their own security protections-usually to defend the kernel or the NIC against malicious userspace programs [7]-, we note that they could benefit from stronger, formally verified mechanisms. In particular, we could draw inspiration from [START_REF] Necula | Safe kernel extensions without run-time checking[END_REF] and [START_REF] Wang | Jitk: A trustworthy in-kernel interpreter infrastructure[END_REF] to strengthen our current BPF-based prototype. [START_REF] Wang | Jitk: A trustworthy in-kernel interpreter infrastructure[END_REF] is a formally verified compilation toolchain from high-level rules to native code for in-kernel interpreters, whereas [START_REF] Necula | Safe kernel extensions without run-time checking[END_REF] is a mechanism to ensure the safety of programs installed in the kernel, with each program carrying its own proof to be verified by the kernel.

CONCLUSION

Cloud applications rely on a diverse set of security services that are often closely tied to the applications they protect. These services are therefore difficult to abstract and implement at the infrastructure layer and cannot leverage recent advances in packet processing.

In this paper, we proposed a new framework to enable the offload of these services to the infrastructure. We addressed the fairness concerns with a token-based mechanism that ensures each tenant gets their fair share of CPU time, regardless of the program they offloaded. We prototyped our design on Linux's eXpress Data Path and measured a 4-6x performance improvement for offloaded security services.

As our next step, we are working on an extension to our prototype to offload programs directly to the SmartNICs.

Figure 1 :

 1 Figure 1: Offload workflow from the request to the API to the execution on the host or NIC.

) 6 :

 6 end ▷ Distribute surplus tokens fairly until none are left or all buckets are full: 7: while r ′ > 0 and ∃i ∈ I : b i < B do 8: J ← {i ∈ S : b i < B} 9: r ′′ ← 0 10:

Figure 2 :

 2 Figure 2: CPU consumption as a percentage of the total time for a single core, for each tenant, with and without fairness mechanism.

Figure 3 :

 3 Figure 3: Packet processing performance with the probes enabled and disabled. The throughput is measured in requests per seconds for Apache only.

Figure 4 :

 4 Figure 4: Packet processing performance for different fairness mechanisms.

Figure 5 :

 5 Figure 5: Packet processing performance gain from offload.

ACKNOWLEDGMENTS

We thank our shepherd, Alexander von Gernler, and the anonymous reviewer for their valuable comments that helped significantly improve this paper's quality. We also thank Céline Comte for pointing out Addanki et al.'s paper and for the helpful discussion that ensued.


Paul Chaignon
email: paul.chaignon@orange.com

Kahina Lazri
email: kahina.lazri@orange.com

Jerome Francois
email: jerome.francois@inria.fr

Thibault Delmas
email: thibault.delmas@telecom-paristech.fr

Olivier Festor
email: olivier.festor@inria.fr

Jérôme François

Extending Open vSwitch with Stateful Filters

Keywords: CCS CONCEPTS, Networks → Programmable networks, Software-Defined Networking, Programmable Networks, Datacenter Networks

come   L'archive ouverte pluridisciplinaire

INTRODUCTION

Software switches are taking an increasingly important role as the edge of datacenter networks. Not only do they switch packets between virtual machines (VMs) and physical interfaces, but they also often terminate overlay tunnels and enforce ACLs and QoS policies [START_REF] Koponen | Network virtualization in multi-tenant datacenters[END_REF]. The short development cycle of software switches-compared to their hardware counterparts-and their ubiquity in datacenter networks make them an ideal place to implement new network services.

There is, additionally, growing pressure on performance for software switches. Datacenters are moving to 40 Gbps and 100 Gbps physical interfaces, and network IO-bound workloads are becoming more common. Furthermore, software switches must expose programming abstractions simple enough to enable centralized control at the scale of datacenter networks. These abstractions need to express diverse forwarding policies, yet allow for efficient implementation.

Open vSwitch, a software switch widely used in virtualization platforms [START_REF]What is Open vSwitch (OVS)?[END_REF][START_REF] Koponen | Network virtualization in multi-tenant datacenters[END_REF], meets these goals through a careful implementation of the stateless match-action forwarding pipeline of OpenFlow [START_REF] Pfaff | The design and implementation of Open vSwitch[END_REF]. Although this stateless design enables flow caching optimizations, it limits the application scope of Open vSwitch. Open vSwitch cannot, for example, aggregate measurements in the dataplane or maintain persistent information on flows and connections. Even simple arithmetic and logic operations beyond bit matching require control plane applications-possibly with a collocated controller [START_REF] Mekky | Application-aware data plane processing in SDN[END_REF][START_REF] Sonchack | Enabling practical software-defined networking security applications with OFX[END_REF]-or middleboxes and VMs [START_REF] Hwang | NetVM: High performance and flexible networking using virtualization on commodity platforms[END_REF][START_REF] Panda | NetBricks: Taking the V out of NFV[END_REF], at the cost of performance.

Recent advances in programmable hardware motivate the need for new programming languages and abstractions, such as P4 [START_REF] Bosshart | P4: Programming protocol-independent packet processors[END_REF] and Domino [START_REF] Sivaraman | Packet Transactions: High-level programming for line-rate switches[END_REF], which can express complex operations and access persistent memories in the switch. With these new abstractions, network operators can program switches to debug TCP connections [START_REF] Ghasemi | Dapper: Data plane performance diagnosis of TCP[END_REF], aggregate measurements at the switch-level [START_REF] Sivaraman | Heavy-hitter detection entirely in the data plane[END_REF], or mitigate DDoS attacks [START_REF] Puš | FPGA-based 100 Gbps DDoS protector[END_REF].

Despite running on flexible commodity hardware, Open vSwitch did not benefit significantly from this new trend; it still exposes a stateless match-action pipeline. Building a stateful extension to Open vSwitch is difficult because it needs to address the two following design challenges.

1. Prevent switch failures during updates. The pipeline may receive frequent updates in response to attacks, or to debug transient network problems. The pipeline thus needs to be updated without interruption of forwarding, as with classic OpenFlow rules. Without proper verification, however, loading unsafe programs at runtime increases the risk of failure. A fault in the new features, whether it may be an invalid operation or a subtler denial of service (e.g., a memory leak or an infinite loop), may cause the switch to crash, thereby disconnecting virtual machines from the network. The switch must therefore provide a mean to prevent these failures.

2. Preserve caching mechanisms. Open vSwitch implements several flow caching mechanisms, fundamental to its high performance, in particular for the long forwarding pipelines typical of multi-tenant networks [START_REF] Koponen | Network virtualization in multi-tenant datacenters[END_REF][START_REF] Pfaff | Converging approaches in software switches[END_REF][START_REF] Pfaff | The design and implementation of Open vSwitch[END_REF]. These mechanisms are built on the assumption that forwarding rules change infrequently compared to the rate of packet arrival. Therefore, stateless rules stay valid for a long enough time to be worth caching. Conversely, with stateful rules, switches may have to reconstruct cache entries after each state change, thus eliminating any caching benefit.

Berkeley Packet Filter (BPF) [START_REF] Mccanne | The BSD packet filter: A new architecture for user-level packet capture[END_REF] is a known solution to address the first design challenge. In Linux-based operating systems, BPF allows userspace applications to extend the kernel at runtime, without interruption. The kernel relies on a bytecode interpreter and a verifier to execute BPF programs if they are deemed safe. BPF received a lot of attention in the Linux kernel [START_REF] Corbet | BPF: The universal in-kernel virtual machine[END_REF][START_REF] Corbet | Early packet drop-and more-with BPF[END_REF][START_REF] Wang | Jitk: A trustworthy in-kernel interpreter infrastructure[END_REF].

The second design challenge received fewer attention. In [START_REF] Jackson | SoftFlow: A middlebox architecture for Open vSwitch[END_REF], E. J. Jackson et al. propose SoftFlow, an extension of Open vSwitch that can execute arbitrary programs as actions in the OpenFlow pipeline. Program developers can tell Soft-Flow when rule lookups are unnecessary after a program execution to skip them and fully leverage Open vSwitch's caches.

In this paper, we present Oko, an stateful software switch that addresses the above two challenges. Oko is based on Open vSwitch and executes BPF bytecode programs as part of the OpenFlow pipeline. These programs can access persistent data structures to perform stateful operations such as tracking the state of TCP connections or aggregating traffic measurements. Although Oko does not use the in-kernel BPF infrastructure, it relies on BPF's bytecode and security model for its own specialized BPF infrastructure.

Compared to SoftFlow, Oko explores a new point in the design space of Open vSwitch extensions. Oko programs act as filters over packets, in the same manner as conventional OpenFlow match fields. Because its programs never modify packets, Oko always caches them without requiring further information from developers. This design choice effectively limits programs to filtering and monitoring applications. In this sense, Oko is complementary to the SoftFlow approach since programs requiring write access to packets could be implemented as actions.

In summary, we make the following contributions:

• The design of Oko, an software switch based on Open vSwitch that supports stateful filtering and monitoring programs as part of its OpenFlow pipeline. Instead, our implementation relies on a userspace BPF implementation based on uBPF [START_REF] Lane | Userspace eBPF VM[END_REF] (Section 2.2). • An evaluation of our implementation and a comparison to state-of-the-art approaches to extend software switches (Section 4), with three security and network diagnosis programs (Section 3). We show that Oko provides a near 2x improvement of performance compared to a process using shared memory to exchange packets with the switch.

Oko is open source and available at https://github.com/ Orange-OpenSource/oko.

DESIGN

We first describe the overall workflow of Oko. We then elaborate on our specialized BPF infrastructure and our extension to Open vSwitch's caching mechanisms.

Oko Workflow

In this section, we describe our extensions to OpenFlow as well as the Oko workflow, from the compilation of programs at the controller to their execution in switches.

Oko extends match-action tables of OpenFlow with an optional match field referencing a filter program, a stateful packet matching program. If all other fields match the packet headers, the filter program is executed, with the packet as its sole argument. Filter programs have a binary result: if they match, their corresponding action is executed; if they do not match, the lookup continues with rules of lower priority.

Each filter program may read and write to its maps, persistent data structures allocated on the switch, with some restrictions detailed in Section 2.2. Since they are embedded as match fields in flow tables, filter programs only impact whether or not actions of a rule are executed; they cannot define new actions.

Filter programs are written in higher-level languages such as C or Lua and compiled to BPF bytecode. This compilation step happens once, at the controller. The controller then sends the program to switches as an object file embedded into LOAD_FILTER_PROGRAM OpenFlow messages. Oko switches load the filter program into a filter program instance, a memory object that contains both the relocated bytecode and its allocated persistent memory. At this point, the verifier performs a series of checks to ensure that the program is safe (see Section 2.2) and returns an OpenFlow error message if it is not.

Match-action rules may then reference filter program instances. In particular, several rules may share the same filter program instance, allowing different rules to share and update the same maps. A filter program may be instantiated several times to dispose of several different memories. For example, when implementing a stateful firewall, each ACL rule may be associated with its own record of established connections (similar to conntrack zones). In our current implementation, to create a new filter program instance, the controller must send the program to the switch a second time.

We extended the OpenFlow protocol with new messages and fields to load filter programs, retrieve maps, and change OpenFlow rules with filter programs attached. These extensions to the OpenFlow protocol are summarized in Table 1. We used OpenFlow vendor extensions for new messages, but had to modify the OpenFlow protocol itself for the new match field, since such vendor extensions are not available. We added support for these extensions in both Open vSwitch and OpenDaylight [START_REF]OpenDaylight project[END_REF].

The astute reader might notice that Oko does not provide an OpenFlow message for the controller to proactively retrieve the content of maps. To retrieve information collected by filter programs, the controller defines a SEND_MAPS action, which the filter program can then trigger (an example is given in Section 3). While developing Oko filter programs, we have not found a need for such an OpenFlow message. Filter programs are often in a better position to decide when the content of their maps should be sent to the controller: they can trigger the SEND_MAPS action when their maps reach a threshold size, or after a specific network event. Nevertheless, if required, the addition of a controller to switch SEND_MAPS message would be trivial to implement.

Specialized BPF Infrastructure

BPF was originally designed as a minimalist bytecode and an in-kernel infrastructure to filter packets destined to a userspace capture application [START_REF] Mccanne | The BSD packet filter: A new architecture for user-level packet capture[END_REF]. In the Linux kernel, it evolved into a general purpose infrastructure [START_REF] Corbet | BPF: The universal in-kernel virtual machine[END_REF], also referred to as extended BPF or eBPF. Its current applications include tracing [START_REF] Gregg | Linux 4.X tracing tools: Using BPF superpowers[END_REF], firewalling [START_REF] Borkmann | net: add bpfilter[END_REF], and container networking [START_REF]Linux native, HTTP aware network security for containers[END_REF]. In this section, we (1) provide the necessary background on the security model of BPF and (2) describe the design and implementation of our userspace BPF infrastructure.

Background on the BPF security model. In the Linux kernel, the BPF virtual machine consists of a stack and a set of 64-bit registers. The bytecode it recognizes was designed to closely match hardware instruction set architectures. Bytecode programs can call external functions, implemented outside the VM, to perform operations or retrieve information not available within the VM.

In-kernel interpreters2 impose limits on the number of instructions and the size of the stack and reject programs with out-of-bounds memory accesses, jumps to non-existing instructions, or null accesses. In addition, in-kernel interpreters expose a BPF machine abstraction with a computational power equivalent to that of a Decider [START_REF] Sipser | Introduction to the Theory of Computation[END_REF], a type of Turing machine that always halts. In the Linux kernel, this computational power is enforced in a strict way by rejecting all jumps to previously visited instructions. This approach prohibits cycles when interpreting the bytecode and, at a higher level, makes long loops difficult to implement 3 .

The jump restriction, however, does not apply to external functions; data structures are therefore implemented outside the BPF VM. For example, the Linux BPF infrastructure contains a hash table implementation with linked lists for collision resolution. It is exposed to BPF programs through three external functions: bpf_map_lookup_elem, bpf_map_update_elem, and bpf_map_delete_elem to lookup, update, or delete an element respectively.

Although external functions can iterate through dynamic data structures, they do not increase the computational power of the BPF machine abstraction. Indeed, external data structures have a bounded size, fixed by program developers, to ensure termination and limit memory consumption.

Compared to other bytecodes [START_REF]The LuaJIT Project[END_REF][START_REF] Meyer | Java Virtual Machine[END_REF], the BPF bytecode is easier to verify: it has a minimalist instruction set and external functions with well-defined interfaces (expected types, such as potential null pointer or pointer to the packet, for arguments and returned values). Oko's userspace BPF infrastructure. We retain the BPF bytecode and its abstract machine, but we re-implement a set of external functions and a verifier tailored to Oko.

Our BPF infrastructure relies on a userspace implementation of the BPF VM [START_REF] Lane | Userspace eBPF VM[END_REF] and extends it to support maps (allocation and external functions). When Oko receives BPF programs from the control plane, it loads them in BPF VMs.

To this end, it first allocates memory for maps and relocates addresses in the bytecode. A just-in-time compiler then translates the BPF bytecode into machine code.

Oko supports two data structures outside the BPF VM: a hash table and a simple array. The hash table implementation uses Bob Jenkins' lookup3 hash function [START_REF] Jenkins | A hash function for hash table lookup[END_REF] and resolves hash collisions with linked lists.

We implemented five external functions filter programs can call:

• Three functions to lookup, update, and delete elements from data structures. • ubpf_time to read the current time-used to implement traffic policing algorithms and to periodically send measurements to the controller. • ubpf_hash to compute a 32-bit hash of a variablelength input. Together with the array data structure, ubpf_hash can be used to implement probabilistic data structures common in network monitoring applications [START_REF] Yu | Software defined traffic measurement with OpenSketch[END_REF], such as Bloom filters and Count-Min sketches.

For the verifier, we implemented a depth-first traversal of the control flow graph (CFG) of BPF programs, to detect and reject programs with cycles (back-edges in the CFG). In a second traversal of the CFG, the verifier tracks the state of registers to determine if they contain, for example, a constant, a pointer to the packet, or a potential null pointer. This information is then used to reject programs with potential invalid operations such as null memory accesses or writes to the packet.

In summary, our verifier implements the same safety checks as the Linux verifier, except that it only supports the specific needs of Oko. We do not, however, implement some of . . . the optimizations the Linux verifier performs (such as state pruning).

Filter Program Caching

Open vSwitch relies on a hierarchy of caches to achieve high performance without loss of generality [START_REF] Pfaff | The design and implementation of Open vSwitch[END_REF]. In this section, we [START_REF]The LuaJIT Project[END_REF] give the necessary background on Open vSwitch's caching mechanism and (2) elaborate on our design to preserve the performance of Open vSwitch and execute filter programs during the cache lookup.

Open vSwitch's forwarding pipeline. Figure 1 illustrates the caching architecture of Open vSwitch. The full matchaction pipeline of the OpenFlow forwarding model is implemented in the slow path, in userspace. This userspace component hence consists of a collection of match-action tables, where each table contains a number of rules, with match fields, a priority, and corresponding actions. When a packet arrives at the slow path, Open vSwitch executes the action of the matching rule with the highest priority. Processing of the packet may continue with subsequent tables depending on the action applied.

In addition, Open vSwitch includes a number of datapath implementations for different environments: kernel modules for the default Linux and Windows datapaths and an additional userspace implementation based on DPDK (Data Plane Development Kit) for Linux. Our implementation of Oko uses the DPDK userspace datapath as it achieves the highest performance.

Open vSwitch's caching mechanisms. The datapath is sometimes referred to as the fast path of Open vSwitch. It implements a number of flow caching mechanisms and only forwards a packet to the slow path if no cached rules are matched. The DPDK datapath implementation includes two cache levels illustrated in Figure 1: the megaflow cache and the microflow cache.

The megaflow cache is a simplified implementation of the OpenFlow match-action pipeline: it contains a single OpenFlow table with no priority. The slow path component can thus only install disjoint rules into this cache. These megaflow rules are built as an aggregation of rules matched during the slow path lookup. To this end, and in order to build only disjoint megaflow rules, Open vSwitch keeps track of which fields were used during the slow path lookup. The megaflow rule installed afterwards matches only on the field used; other match fields are wildcarded. Open vSwitch uses a number of additional techniques during the construction of megaflow rules to improve the cache hit rate.

Because even the simplified megaflow table has a high lookup cost, Open vSwitch includes a second cache, the microflow cache, implemented as an exact-match table. As any packet header change results in a cache miss, the microflow cache does not perform well with many traffic patterns such as short lived flows, in which case Open vSwitch must fall back to the megaflow cache.

Oko's filter program chains. To maintain the performance of Open vSwitch, filter programs need to be cached and executed in the datapath. The caching mechanisms of Open vSwitch, however, are tailored for its stateless OpenFlow pipeline. Introducing stateful programs in caches raises an important challenge.

The result from the execution of a filter program depends on the full content of the packet and the memory associated with the program. Conversely, in the OpenFlow forwarding model, the actions depend only on the packet's headers. Thus, two packets with the same header will always be processed identically in an OpenFlow pipeline, whereas they may result in different actions taken when processed by Oko.

Open vSwitch relies on this determinism to aggregate a succession of OpenFlow rules into a single megaflow rule. With Oko, the path through the OpenFlow pipeline, and thus the megaflow aggregated rule, depends on the results from executed filter programs, which may change from one execution to the next. To overcome this challenge, we introduce the concept of filter program chains for caches. A filter program chain consists of an ordered list of filter programs, each with an expected result. Each megaflow cache entry contains a filter program chain, assembled during the slow path lookup as the concatenation of executed filter programs with their result. By construction, the filter program chain preserves the order in which filter programs were executed.

Table 3 illustrates a plausible content of the megaflow cache after Oko processed two packets through the slow path table defined in Table 2. Program a matched the first packetand the filter program chain [a:1] was installed in the cachebut not the second packet. The slow path lookup continued for the second packet with rules of lower priority. Program b matched the second packet, resulting in the installation of the filter program chain [a:0, b:1] in the cache.

The datapath executes filter program chains by iterating through them and executing each program until it finds one that does not return the expected value. A filter program chain matches a packet if all its filter programs return their expected results. In the caches' classifiers, several rules with the same stateless match fields but different filter program chains are referenced under the same hash. Oko iterates through them until it finds a matching filter program chain. If none of the cached rules match, the traditional behavior of Open vSwitch is preserved and a slow path lookup is performed.

For a given set of packet headers, the possible paths through the OpenFlow pipeline can be viewed as a binary tree whose nodes are filter programs. Each slow path lookup with this same set of headers results in a new path through the tree being cached, i. 3) in bold.

Although filter programs are still not deterministic from the caches' perspective, encoding their results into cached rules enables the aggregation of several stateful rules into a single disjoint rule.

Filter program chains, however, do not guarantee on their own that a program is not executed twice for the same packet. Two filter program chains may share some filter programs that we do not want executed twice for a same packet. To prevent this, a history of executed filter programs is saved along with their results for each processed packet. This history is then checked before executing any filter program.

If filter programs had write access to packets, our filter program chain extension would not be possible. In this case, the path through the OpenFlow pipeline would also depend on the packet modifications, which would have to be encoded in cache entries as well. Encoding all packet modifications, in addition to the program results, is prohibitively expensive.

Cache Invalidation

Because cached rules depend on their aggregated OpenFlow rules and on higher priority rules, their invalidation is difficult to compute. Therefore, rather than trying to track which cache entries need to be updated after an OpenFlow update, Open vSwitch adopts a brute-force approach and proactively revalidates the whole cache.

To this end, it runs the set of packet headers that generated each cached rule through the slow path again. The new rule generated and its actions are compared against the installed cached rule. Depending on the result, cached rules may be updated, removed from the cache, or kept as they are.

Preserving this cache revalidation mechanism is challenging for filter programs because it presumes that a rule can be matched against several times and give the same result. Unfortunately, executing filter programs during cache revalidation would update their internal state and so may change the expected result of a filter program for future incoming packets. To avoid any execution of filter programs during cache revalidation, we use the filter program chain attached to cached rules. During the slow path lookup for cache revalidation, we compare the identifier of selected filter program with those from the cached filter program chain. A cached rule is deemed valid only if the same filter programs are selected, in the same order.

FILTER PROGRAM EXAMPLES

In this section, we describe three example use cases for Oko: a stateful firewall, a TCP performance diagnosis system, and a stateless filtering application. Each use case requires a single filter program written in C and compiled to BPF bytecode. We evaluate these filter programs in Section 4.

p0f signature filtering. We describe a simple stateless filtering application of Oko, to emphasize its extended matching capabilities. We implemented a TCP SYN DoS mitigation application based on p0f signatures [START_REF] Zalewski | v3[END_REF]. p0f is a passive fingerprinting tool that can identify the system from which a packet originated based on pre-established signatures. p0f also includes signatures to discriminate SYN flood packets from legitimate traffic [START_REF] Bertin | Introducing the p0f BPF compiler[END_REF].

Matching p0f signatures against packets requires a few arithmetic and bitwise operations (e.g., subtractions and bit shifts) on TCP options, and as such, could not be expressed with OpenFlow rules, even if new fields were added. Conversely, with Oko, the filter program extends the OpenFlow table and performs the operations required to match p0f signatures against packets. The first rule in Table 4a illustrates the use of p0f signatures to filter packets at the beginning of the pipeline (with the highest priority). The filter program matches and drops packets that match its p0f signatures.

Our application relies on the OpenDaylight REST API to control the switch. It first generates a p0f signature from sampled TCP packets (mirrored to the controller). The p0f signature is then compiled to BPF and loaded in the switch to block attacks directly in the dataplane.

Stateful firewall. As a descriptive example of Oko's workflow, we implemented a stateful firewall using a filter program as the connection tracker and OpenFlow rules for the ACL rules. As illustrated in Table 4a, the same program, denoted as firewall, tracks connections in both directions in order to protect a web server hosted at 10.0.0. The stateful firewall maintains the state of each connection, identified by their 5-tuple (protocol, source and destination IP addresses and ports), in a hash table. The filter program only needs to implement the TCP state machine and accesses the hash table through the three external functions defined in Section 2.2.

Dapper: TCP performance analysis. Dapper [START_REF] Ghasemi | Dapper: Data plane performance diagnosis of TCP[END_REF] is a system to analyze TCP connections in real-time near end-hosts. Dapper collects a set of information on each TCP connection (e.g., flight size, MSS, sender's reaction time) at the edge switch. A controller can then retrieve this information to determine the limiting factor of a connection among the sender, the receiver, and the network.

An example integration of Dapper in the OpenFlow pipeline is given in Table 4b. Our Dapper implementation analyzes all traffic to and from the server and stores information on TCP connections in a hash table. By default, the Dapper filter program returns false and packets therefore match the last two rules from the OpenFlow table. The program returning true triggers the SEND_MAPS action: statistics on all connections are sent to the controller. This action allows the program to send its collected statistics in batches to the controller when it reaches a given number of connections, after a given amount of time, or when it detects a troubled connection.

EVALUATION

Our evaluations aim to answer the following questions:

• How does Oko compare to other methods to extend software switches? • How much overhead do Oko's extensions introduce in Open vSwitch? In particular, how does it impact traditional stateless forwarding pipelines? • How efficient is our filter program chain extension for Open vSwitch's caching mechanisms?

First, we describe our evaluation environment. Next, through a set of microbenchmarks, we measure the overhead and efficiency of our extensions to Open vSwitch. Finally, we compare, for the three use cases described in Section 3, the performance of Open vSwitch to that of two alternate solutions to extend software switches: (1) a KVM virtual machine using a vhost-user interface and running a DPDK application, and (2) a zero-copy DPDK application running as a process. To avoid Linux's I/O interfaces being the main bottleneck, and to get a clear view of the performance limitations of our own modifications, we based our prototype on the highperformance, userspace datapath of Open vSwitch.

Evaluation Environment

In all experiments, the switch runs on a single core, isolated from the Linux scheduler, with hyper threading disabled. All cores used in experiments are on the same NUMA node, to which the NIC is connected. Unless stated otherwise, we use Open vSwitch 2.5.0, on which Oko is based, with DPDK 2.2 for all comparisons. The switch is configured with a single poll-mode thread and receive checksum offload disabled. The second server runs MoonGen [START_REF] Emmerich | MoonGen: A scriptable high-speed packet generator[END_REF] to send minimum size 64 bytes frames and replay packet captures.

In several of the following evaluations, the packet generator replays a CAIDA packet trace [START_REF]The CAIDA anonymized OC48 Internet traces 2002-2003 dataset[END_REF] of 34 minutes. The trace contains 87 million packets forming 7 million L4 conversations. On average, L4 conversations last 5.6 seconds and contain 11.7 packets. The maximum number of packets in a single conversation is 11k and the median is 4 packets.

Each experiment lasts 5 minutes and we report the mean and the standard deviation over 10 runs.

Microbenchmarks

We first measure the overhead introduced in Open vSwitch by Oko's extensions through a set of microbenchmarks.

Setup. Because Oko extends only the packet classification algorithms of Open vSwitch and does not impact the Open-Flow actions, we configure the switch to drop received packets after classification. The switch therefore acts as a packet classifier in all comparisons to vanilla Open vSwitch. We perform end to end evaluations in Section 4.3.

Because of the two-level caching architecture, the performance of Open vSwitch greatly depends on the traffic patterns and the cache hit rate of both its microflow and megaflow caches. Therefore, in all experiments, we provide results under three switch setups: the first setup is the default switch configuration with all caches; in the second setup, the microflow cache is disabled and packets directly hit the megaflow cache with its single OpenFlow table; in the last setup, both caches are disabled and all packets go through the full OpenFlow pipeline in the slow path.

Scenarios. In the following microbenchmarks, we configure the switch and the MoonGen packet generator according to two scenarios.

In the synthetic scenario, a single OpenFlow rule matching all incoming packets is installed while the packet generator sends a single flow of minimum sized (64 bytes) UDP packets. The rule has a baseline filter program attached, with a single instruction to return 1, and therefore matches all packets. This scenario is an ideal case for Open vSwitch's performance. Once the OpenFlow rule is cached, Open vSwitch requires few cycles to process subsequent packets, and any overhead added by Oko is therefore accentuated.

Conversely, the realistic scenario is designed to stress the switch datapath. It consists of a two-stage pipeline, with an L3 table over 170 IP prefixes and an ACL table consisting of 500 rules over destination ports.

We choose the L3 and ACL tables so as to produce a high number of cached rules at runtime. The L3 table matches the 101 /8 IP prefixes from the trace, as well as the 69 most used /16 IP prefixes, whereas the ACL table matches the 500 most used destination ports. As shown in Figure 3, thanks to this setup, packets are well distributed over all OpenFlow rules. The two ACL rules matching a larger number of packets are the default deny rule and the port 80 rule. After a brief ramp up period, this pipeline results in an average of 170k distinct rules installed in the datapath 4 .

The short duration of conversations and the high distribution of packets over OpenFlow rules significantly stresses the switch caches. Indeed, as can be observed when comparing figures 4a and 4b (OVS bar), the efficiency of the two datapath caches is greatly reduced in the realistic scenario compared to the synthetic scenario (x5 and x3.6 difference 4 We increase the maximum number of rules for the DPDK datapath to 200k. for the microflow and megaflow caches respectively). In particular, because of the short duration of conversations, the microflow cache brings little improvement (3%) over the megaflow cache under the realistic scenario.

Overhead Evaluation. We next measure the performance of Open vSwitch, Oko without filter programs, and Oko with a single baseline filter program. Figure 4a shows the packet classification performance for each cache level under the synthetic scenario.

Without filter programs in the forwarding pipeline, Oko has a small performance overhead over Open vSwitch (no noticeable overhead with all caches, 6% with the microflow cache disabled) largely due to the initialization of several additional packet fields to store the history of executed filter programs. With a baseline filter program, the overhead grows to 12.6% when all cache levels are enabled, and 11.3% when the microflow cache is disabled. This evaluation provides us with an estimated upper bound of the performance overhead. Under the synthetic scenario, because of the single OpenFlow rule, the two caches require very few instructions to classify each packet. Therefore any additional processing (fields initialization, filter program chain iteration, etc.) appears accentuated. Under the realistic scenario, however, Oko adds very little overhead (no noticeable overhead with all caches, 2% with the microflow cache disabled) to Open vSwitch and the overhead added by a baseline filter program decreases to 5.5% with all caches (5.6% with the microflow cache disabled). To obtain a chain of n filter programs in the datapath, we modify the synthetic scenario and create a pipeline of n tables in the slow path. Each table contains a single OpenFlow rule with a baseline filter program attached and forwards packets to the next table. Baseline filter programs match all packets. Figure 5 shows the packet classification performance for these pipelines. Each new filter program results in about 4% additional overhead. The packet classification performance is almost halved (-43.8%) with 10 filter programs in the pipeline. These numbers are in line with what others have reported for similar chains of programs executed in Open vSwitch's datapath [START_REF] Jackson | SoftFlow: A middlebox architecture for Open vSwitch[END_REF]. Filter Programs Evaluation. To provide an estimate of the cost of running filter programs as part of the forwarding pipeline, we integrate and evaluate each filter program example from Section 3 under the realistic scenario.

To evaluate the p0f signature filtering program, an additional table is added at the beginning of the realistic scenario's pipeline. This first table has two rules to (1) drop all packets that match the p0f signature, and (2) forward other packets to the second table. In addition, at the packet generator, we inject both legitimate traffic (from the realistic packet trace) and a flood of TCP SYN packets matching the p0f signature. As in previous tests, the packet trace is replayed with a single core; 3 additional cores participate in the TCP SYN flood, resulting in approximately one on four packets being legitimate.

The results in Figure 6 count all packets successfully classified by Oko. The Baseline bar reports the performance of Oko when there are no filter programs in the pipeline, for comparison. With the p0f filter program, Oko achieves better performance than the baseline case because it drops illegitimate packets at the beginning of the pipeline, before the L3 and ACL lookups. As highlighted by this p0f example, Oko can help filter illegitimate or malformed packets at the beginning of the pipeline to avoid unnecessary processing steps.

To evaluate our Dapper implementation, tables are added at the end of the realistic pipeline with corresponding filter programs. We use the same packet trace as in the realistic scenario.

The initial implementation of Dapper [START_REF] Ghasemi | Dapper: Data plane performance diagnosis of TCP[END_REF] relies on a fixed size data structure to store statistics on TCP connections. For this reason, it can miss some connections if the number of TCP connections grows larger than the size of the data structure. With Oko we have the choice to implement a similar array-based version of Dapper or rely on a hash table to store statistics. We implement both options and compare their performance in Figure 6. Under our test scenario, the hash table implementation has a relatively low cost compared to the array implementation. Oko can therefore benefit from the higher flexibility offered by CPUs to implement algorithms impractical with specialized hardware.

Since its 2.6.1 version, Open vSwitch can act as a stateful firewall thanks to a connection tracking module (conntrack) implemented in the DPDK datapath. We compare this implementation against our Oko stateful firewall under the realistic scenario, with additional rules to distinguish established TCP connections from new connections. The Open vSwitch firewall uses Open vSwitch 2.6.1 and DPDK 16.07.

As shown in Figure 6, the two stateful firewalls perform comparably. Our implementation achieves higher packet classification performance (18% higher with all caches), but contrary to Open vSwitch's connection tracking module, it does not track UDP conversations. With Oko, however, network operators can customize the connection tracking program at runtime to fit a particular application's needs.

In summary, each filter program adds only a small overhead to the baseline pipeline, with the exception of the p0f filtering program that improves performance when the switch is under attack. Notice that Dapper and our stateful firewall implementations achieve very close performance results, despite being completely different applications. An in-depth analysis of the CPU consumption reveals that, in both cases, the hash table lookup dominates the running time with a majority of CPU cycles spent on the 5-tuple hash computation.

End-to-End Comparisons

Setups. For each of the three use case examples, we compare Oko to two existing solutions to extend software switches.

• A DPDK application running inside a KVM virtual machine. The VM is connected to Open vSwitch using the vhost-user virtual NIC. Packets are copied from the switch memory space to the VM memory space through a shared memory. vhost-user is the recommended virtual NIC for use with Open vSwitch-DPDK because it achieves the highest performance by opening a direct channel between the host userspace and the guest memory space. • A DPDK application running as a single process on the host. By using the DPDK Ring Port type, the process shares the memory space of Open vSwitch, enabling zero-copy packet processing.

The switch (both Oko and Open vSwitch), the VM, and the process each have their own dedicated core, isolated from the Linux scheduler. In each setup, the switch has only two rules to send packets through the application.

Even though the VM and the process setups each have two dedicated cores, they use comparable amount of CPU resources. In both cases, the core dedicated to the switch does minimal work: it only forwards packets from the NIC to the virtual port and vice versa.

Figure 7 illustrates our three test setups. When using Oko, a single core receives packets from the NIC, executes the filter program on them and sends them back to the NIC, as per the run-to-completion model of Open vSwitch. Under the Process setup, however, the addition of a second process to run the application breaks the run-to-completion model. Packets are first forwarded by the switch, then processed by the DPDK application, and finally forwarded back to the NIC by the switch. Finally, the VM setup entails two additional packet copies: from the switch to the VM and back.

For the purpose of this comparison, we implemented the three use cases from Section 3 as DPDK applications. The two filtering applications, the stateful firewall and the p0f application, drop filtered packets in the VM and in the process, without requiring an additional transfer to the switch.

The packet generator replays the same CAIDA trace as previously. For the evaluation of the p0f application only, we configure 3 additional cores at the packet generator to send a continuous stream of TCP SYN packets.

Results. Figure 8 presents the results of our comparison evaluation. As expected, Oko outperforms the VM applications by 2-3x. The difference is less pronounced for the p0f filtering application because illegitimate packets (3 out of 4 packets) are dropped at the VM, requiring one less copy.

Although VMs are increasingly considered as potential targets to deploy packet processing application, it is not a fair comparison to Oko as they provide stronger isolation. Contrary to Oko, VMs (1) provide resource isolation between applications, and (2) leverage hardware support for memory isolation. Using our userspace BPF verifier, Oko provides memory isolation between filter programs and between the switch and filter programs, and prevents faults in filter programs from crashing the switch. These guarantees are closer to that of processes, which also isolate faults from the switch and separate each application into its own memory space.

When compared to the Process setup, Oko provides a 1.7-1.9x improvement of performance. Thanks to the run-tocompletion model of Open vSwitch, Oko benefits from fewer cache misses, consolidated processing steps (packet parsing and classification are performed once), and the lack of IPC.

RELATED WORK

There is a large body of work on packet processing in software [START_REF] Han | SoftNIC: A software NIC to augment hardware[END_REF][START_REF] Jackson | SoftFlow: A middlebox architecture for Open vSwitch[END_REF][START_REF] Morris | The Click modular router[END_REF][START_REF] Panda | NetBricks: Taking the V out of NFV[END_REF][START_REF] Rizzo | Netmap: A novel framework for fast packet I/O[END_REF][START_REF] Shahbaz | PISCES: A programmable, protocol-independent software switch[END_REF][START_REF] Sonchack | Enabling practical software-defined networking security applications with OFX[END_REF]. We focus here on (1) propositions to extend software switches, (2) alternatives to BPF for the isolation of packet processing programs, and (3) emerging usages of BPF in software switches.

Extending Software Switches. Several recent works addressed the issue of extending software switches to execute arbitrary packet processing [START_REF] Jackson | SoftFlow: A middlebox architecture for Open vSwitch[END_REF][START_REF] Mekky | Network function virtualization enablement within SDN data plane[END_REF][START_REF] Mekky | Application-aware data plane processing in SDN[END_REF][START_REF] Sonchack | Enabling practical software-defined networking security applications with OFX[END_REF].

OFX [START_REF] Sonchack | Enabling practical software-defined networking security applications with OFX[END_REF] extends the OpenFlow API to allow SDN applications to load programs into a switch agent. This agent acts as a local controller for a few tables at the beginning of the switch's OpenFlow pipeline. [START_REF] Mekky | Application-aware data plane processing in SDN[END_REF] presents the design of a similar extension, except the local controller intercepts packets by modifying table-miss OpenFlow rules. As shown in Section 4.3, because it breaks the switch's run-to-completion model-packets are processed by the local controller in a different execution context than the forwarding pipeline-, this approach cannot offer the same performance as Oko.

With NEWS [START_REF] Mekky | Network function virtualization enablement within SDN data plane[END_REF], the authors of [START_REF] Mekky | Application-aware data plane processing in SDN[END_REF] propose an improvement of their design and integrate the local controller in Open vSwitch. Although NEWS preserves the run-to-completion model of Open vSwitch, it runs in the slow path as the authors do not extend caching mechanisms. As hinted in Section 4.2, extending Open vSwitch's caching mechanisms is a required step to achieve high performance.

SoftFlow [START_REF] Jackson | SoftFlow: A middlebox architecture for Open vSwitch[END_REF] is probably the work closest to ours. Based on Open vSwitch, SoftFlow preserves the run-to-completion model and runs arbitrary programs in the datapath as Open-Flow actions. SoftFlow, however, sacrifices isolation to attain high-performance; as a result, a faulty program may crash the switch. Thanks to BPF, Oko is immune to such failures.

Because SoftFlow supports arbitrary programs, it relies on their developers to tell the switch when a program does not mandate a new rule lookup after its execution. In contrast, in Oko, programs are integrated and act as match fields; in particular, they cannot write to packets. This restriction makes the filter program chain extension possible since new rule lookups are never required after a filter program execution. To support programs that require write access to packets, a future version of Oko could adopt SoftFlow's approach and implement those programs as OpenFlow actions. This design would provide a clear separation between filter programs that can be chained and action programs that require write access to packets. Software Isolation. Besides BPF, several other systems address the issue of providing memory isolation without the significant cost of context switches.

In particular, Singularity [START_REF] Hunt | Singularity: Rethinking the software stack[END_REF] explores the use of type-safe languages and memory-safe runtimes to provide memory isolation in place of the hardware memory management unit. NetBricks [START_REF] Panda | NetBricks: Taking the V out of NFV[END_REF] applies this approach to packet processing and relies on LLVM as the runtime and Rust as the language. In particular, NetBricks leverages a new compile-time mechanism, called Zero-Copy Software Isolation, to ensure packet isolation without the overhead of packet copies.

Closer to BPF, DTrace [START_REF] Cantrill | Dynamic instrumentation of production systems[END_REF] is a dynamic tracing infrastructure for Solaris. DTrace's bytecode is verified by the kernel before execution. Safety checks are similar to that of BPF: invalid operations and forward jumps are prohibited, illegal memory accesses are intercepted at runtime.

With some adjustments, these systems could be used in place of BPF in Oko. We chose to use BPF because it has been tailored for packet processing [START_REF] Mccanne | The BSD packet filter: A new architecture for user-level packet capture[END_REF] and provides the minimum functionalities required for Oko.

BPF for software switching. In a recent work, C.-C. Tu et al. [START_REF] Tu | Building an extensible Open vSwitch datapath[END_REF] detail the design of an BPF-based datapath for Open vSwitch, to replace the Linux kernel module datapath. Their work focuses on implementing the two caches in BPF and does not expose BPF capabilities through the switch API.

S. Jouet et al. propose in [START_REF] Jouet | Programmable dataplane for next generation networks[END_REF] to use stateless BPF programs as OXM match fields to build a protocol independent switch. In [START_REF] Jouet | BPFabric: Data plane programmability for software defined networks[END_REF], they propose a packet processing framework based on BPF, upon which a software switch can be developed. In both [START_REF] Jouet | Programmable dataplane for next generation networks[END_REF] and [START_REF] Jouet | BPFabric: Data plane programmability for software defined networks[END_REF], the prototypes do not implement any flow caching mechanisms, which eases the design but severely limits performance for long forwarding pipelines.

Finally, it is also possible to place BPF hooks in the Linux kernel networking stack (e.g., at the traffic classifier or in the driver). Such programs, however, cannot benefit from the ease and performance of Open vSwitch's forwarding pipeline; they would have to reimplement flow tables and their caching optimizations from scratch. To benefit from both Open vSwitch and the Linux BPF infrastructure, a new hook point and an extended Open vSwitch kernel module would be required. We leave this in-kernel implementation of Oko to our future work.

CONCLUSION

Because of their stateless match-action abstractions, software switches do not leverage the flexibility offered by the commodity hardware on which they run. Due to their unique position at the edge of datacenter networks, software switches are critical pieces of software, difficult to extend.

In this paper, we introduced Oko, a software switch based on Open vSwitch that can be extended at runtime with stateful programs. Oko protects itself against faulty programs using the same security model as the BPF in-kernel interpreter. As our evaluations demonstrate, Oko can preserve the high performance of Open vSwitch, while providing a near 2x improvement over existing approaches to extend software switches. Thanks to Oko, SDN applications can load programs in the dataplane to mitigate attacks, diagnose performance drops, or customize network services at runtime.

Figure 1 :

 1 Figure 1: Open vSwitch caching architecture.

  e. a new result of a filter program of the chain is reached. Filter program chains encode these paths. Figure 2 represents the filter program tree ofTable 2 for flow

Figure 2 :

 2 Figure 2: Tree of filter programs from Table2for flow ip_dst=10.0.0.1,port=80. Only branch a->b->drop has not been cached yet.

  Our testbed consists of two servers directly connected with Mellanox 40 Gbps NICs. The two NICs use firmware 2.40.700 and are configured with a single queue. The Device Under Test (DUT) hosting the switch (Oko or vanilla Open vSwitch) has an Intel Xeon E5-2640 2.6 Ghz with 20 MB of L3 cache and 16 GB of DDR4 memory at 2133 MHz and runs Linux 4.4.0.

Figure 3 :

 3 Figure 3: Cumulative distribution of packets over OpenFlow rules.

  (a) Synthetic scenario, with a standard deviation below 0.30 for all measurements.(b) Realistic scenario, with a standard deviation below 0.06 for all measurements.

Figure 4 :

 4 Figure 4: Packet classification performance between Open vSwitch and Oko.

Figures

  Figures 4a and 4b also highlight the need for our filter program chain extension to Open vSwitch's caching mechanisms. Without filter program chains, the performance of Oko with a filter program would be that of the slow path since the caches would be stateless and all packets would go through the slow path. Filter program chains therefore provide an estimated x5 improvement of performance under the realistic scenario (x18 for the synthetic scenario).

Filter

  program chains. OpenFlow rules are installed in the datapath caches after a packet passed through the full OpenFlow pipeline in the slow path. If filter programs were executed during the slow path lookup, the cached rule has a non-empty filter program chain attached. The size of the filter program chain is equal to the number of filter programs executed during the slow path lookup.

Figure 5 :

 5 Figure 5: Packet classification performance for different filter program chain lengths, with a standard deviation below 0.30 for all measurements.

Figure 6 :

 6 Figure 6: Performance evaluation (on a log scale) for the three Oko use cases, with a standard deviation below 0.08 for all measurements.

Figure 7 :

 7 Figure 7: The three evaluation setups for the end-toend performance comparison. Packet copies are only necessary when crossing memory space boundaries.

Figure 8 :

 8 Figure 8: Comparison of performance for the three use cases, with Oko, a vhost-user KVM virtual machine, and a DPDK Ring Port process. The standard deviation is below 0.10 for all measurements.

  • An implementation of Oko based on Open vSwitch-

DPDK. Thanks to a careful extension, Oko preserves Open vSwitch's cache design despite its original stateless assumption (Section 2.3 and 2.4). Because we leverage the high-performance version of Open vSwitch 1 , we cannot directly reuse the Linux BPF infrastructure.

Table 1 :

 1 Modified to include a new filter_prog field with a filter program ID. Used to add, remove, or modify OpenFlow rules. SEND_MAPS Action Instructs the switch to send the content of data structures given in argument to the controller. The argument is a bit array where each bit corresponds to a data structure referenced in the filter program attached to the rule. Oko's extensions to the OpenFlow protocol.

	Name	Type	Description
	LOAD_FILTER_PROG Controller to switch	Contains an ID and a filter program as an object file. The switch loads the filter program and
		message	assigns it the given ID.
	FLOW_MOD	Controller to switch
		message
	SEND_MAPS	Switch to controller	Contains the binary content of data structures.
		message

Table 0 Table n

 0n

		Slow path
	First packet	Datapath	Megaflow cache Microflow cache

Table 2 :

 2 Example of Oko match-action table. If packets do not match a they will inevitably run against b.

	Priority Source Destination Filter prog. Action
	100	*	10.0.0.1:80	a	drop
	10	*	*:80	b	port 1
	1	*	*	-	drop
	Source Destination Filter program chain Action
	*	10.0.0.1:80	[a:1]		drop
	*	10.0.0.1:80	[a:0, b:1]		port 1

Table 3 :

 3 Example of megaflow cache in Oko after slow path lookups for 2 packets toward 10.0.0.1:80. Only one of the packets matched a, the other matched b.

Table 2 Table 4 :

 24 1. It matches packets if they are part of an established connection. It is only used to filter packets from the server (fourth rule) since only packets from established connections are authorized in that direction. Packets destined to the server are forwarded to the second table (second and third rules), regardless of whether they are from an established connection. OpenFlow tables to illustrate example filter programs.

	Prio. Source Dest. 12 * 10.0.0.1 anti-ddos Filter prog. Actions drop 11 * 10.0.0.1 firewall table 2 10 * 10.0.0.1 -table 2 10 10.0.0.1 * firewall table 2 1 * * -drop (a) Table 1	Prio. Source Dest. 10 10.0.0.1 * 10 * 10.0.0.1 Dapper Filter prog. Actions Dapper send_maps, port 1 send_maps, port 2 1 10.0.0.1 * -port 1 1 * 10.0.0.1 -port 2 (b)

The high-performance Open vSwitch-DPDK helped us uncover several performance bottlenecks in our initial design.

Both the Linux kernel and the BSD kernel have a form of BPF in-kernel interpreter.

Short loops can be unrolled during compilation to bytecode.

ACKNOWLEDGMENTS

We thank our shepherd, Petr Lapukhov, and the anonymous SOSR reviewers for their valuable comments that helped improve the quality of this paper. We also thank Alex Palesandro, Xiao Han, and Diane Adjavon for their helpful input.