Publications

Conference Publications:

• Anat Bremler-Barr, Eli Brosh‏, Mor Sides, "DDoS Attack on Cloud Auto-scaling Mechanisms". Accepted to INFOCOM 2017
  [pdf][slides][abstract]

  DDoS Attack on Cloud Auto-scaling Mechanisms

  By Anat Bremler-Barr, Eli Brosh‏, Mor Sides

  Auto-scaling mechanisms are an important line of defense against Distributed Denial of Service (DDoS) in the cloud. Using auto-scaling, machines can be added and removed in an on-line manner to respond to fluctuating load. It is commonly believed that the auto-scaling mechanism casts DDoS attacks into Economic Denial of Sustainability (EDoS) attacks. Rather than suffering from performance degradation up to a total denial of service, the victim suffers only from the economic damage incurred by paying for the extra resources required to process the bogus traffic of the attack.
  Contrary to this belief, we present and analyze the Yo-Yo attack, a new attack against the auto-scaling mechanism, that can cause significant performance degradation in addition to economic damage. In the Yo-Yo attack, the attacker sends peri- odic bursts of overload, thus causing the auto-scaling mechanism to oscillate between scale-up and scale-down phases. The Yo- Yo attack is harder to detect and requires less resources from the attacker compared to traditional DDoS. We demonstrate the attack on Amazon EC2 [4], and analyze protection measures the victim can take by reconfiguring the auto-scaling mechanism.

• Yehuda Afek, Anat Bremler-Barr, Lior Shafir, "Network Anti-Spoofing with SDN Data plane". Accepted to INFOCOM 2017
  [pdf][slides][abstract]

  Network Anti-Spoofing with SDN Data plane

  By Yehuda Afek, Anat Bremler-Barr, Lior Shafir

  Traditional DDoS anti-spoofing scrubbers require dedicated middleboxes thus adding CAPEX, latency and complexity in the network. This paper starts by showing that the current SDN match-and-action model is rich enough to implement a collection of anti-spoofing methods. Secondly we develop and utilize advance methods for dynamic resource sharing to distribute the required mitigation resources over a network of switches.
  None of the earlier attempts to implement anti-spoofing in SDN actually directly exploited the match and action power of the switch data plane. They required additional functionalities on top of the match-and-action model, and are not implementable on an SDN switch as is. Our method builds on the premise that an SDN data path is a very fast and efficient engine to perform low level primitive operations at wire speed. The solution requires a number of flow-table rules and switch-controller messages proportional to the legitimate traffic. To scale when protecting multiple large servers the flow tables of multiple switches are harnessed in a distributed and dynamic network based solution.
  We have fully implemented all our methods in either OpenFlow1.5 in Open-vSwitch and in P4. The system mitigates spoofed attacks on either the SDN infrastructure itself or on downstream servers.

• Anat Bremler-Barr, Yotam Harchol, David Hay, "OpenBox: A Software-Defined Framework for Developing, Deploying, and Managing Network Functions", in SIGCOMM, August 2016
  [pdf][slides][abstract]

  OpenBox: A Software-Defined Framework for Developing, Deploying, and Managing Network Functions

  By Anat Bremler-Barr, Yotam Harchol, David Hay

  We present OpenBox — a software-defined framework for network-wide development, deployment, and management of network functions (NFs). OpenBox effectively decouples the control plane of NFs from their data plane, similarly to SDN solutions that only address the network’s forwarding plane.
  OpenBox consists of three logic components. First, user-defined OpenBox applications provide NF specifications through the OpenBox north-bound API. Second, a logically-centralized OpenBox controller is able to merge logic of multiple NFs, possibly from multiple tenants, and to use a network-wide view to efficiently deploy and scale NFs across the network data plane. Finally, OpenBox instances constitute OpenBox’s data plane and are implemented either purely in software or contain specific hardware accelerators (e.g., a TCAM). In practice, different NFs carry out similar processing steps on the same packet, and our experiments indeed show a significant improvement of the network performance when using OpenBox. Moreover, OpenBox readily supports smart NF placement, NF scaling, and multi-tenancy through its controller.

• Anat Bremler-Barr, Yotam Harchol, David Hay, Yacov Hel-Or, "Encoding Short Ranges in TCAM Without Expansion: Efficient Algorithm and Applications", in SPAA, July 2016
  [pdf][slides][technical report][abstract]

  Encoding Short Ranges in TCAM Without Expansion: Efficient Algorithm and Applications

  By Anat Bremler-Barr, Yotam Harchol, David Hay, Yacov Hel-Or

  We present RENE ́ — a novel encoding scheme for short ranges on Ternary content addressable memory (TCAM), which, unlike previous solutions, does not impose row expansion, and uses bits proportionally to the maximal range length. We provide theoretical analysis to show that our encoding is the closest to the lower bound of number of bits used. In addition, we show several applications of our technique in the field of packet classification, and also, how the same technique could be used to efficiently solve other hard problems such as the nearest-neighbor search problem and its variants. We show that using TCAM, one could solve such problems in much higher rates than previously suggested solutions, and outperform known lower bounds in traditional memory models. We show by experiments that the translation process of RENE ́ on switch hardware induces only a negligible 2.5% latency overhead. Our nearest neighbor implementation on a TCAM device provides search rates that are up to four orders of magnitude higher than previous best prior-art solutions.

• Anat Bremler-Barr, David Hay, Daniel Krauthgamer, Shimrit Tzur David, "Scalable URL Matching with Small Memory Footprint", in IFIP Networking, May 2016
  [pdf][slides][abstract]

  Scalable URL Matching with Small Memory Footprint

  By Anat Bremler-Barr, David Hay, Daniel Krauthgamer, Shimrit Tzur David

  URL matching lies at the core of many networking applications and Information Centric Networking architectures. For example, URL matching is extensively used by Layer 7 switches, ICN/NDN routers, load balancers, and security devices. Modern URL matching is done by maintaining a rich database that consists of tens of millions of URL which are classified to dozens of categories (or egress ports). In real-time, any input URL has to be searched in this database to find the corresponding category.
  In this paper, we introduce a generic framework for accurate URL matching (namely, no false positives or miscategorization) that aims to reduce the overall memory footprint, while still having low matching latency. We introduce a dictionary-based compression method that compresses the database by 60%, while having only a slight overhead in time. Our framework is very flexible and it allows hot-updates,
  cloud-based deployments, and can deal with strings that are not URLs.

• Alon Atari, Anat Bremler-Barr, "Efficient Round-Trip Time Monitoring in OpenFlow Networks", in INFOCOM, April 2016
  [pdf][slides][abstract]

  Efficient Round-Trip Time Monitoring in OpenFlow Networks

  By Alon Atari, Anat Bremler-Barr

  Monitoring Round-Trip Time provides important insights for network troubleshooting and traffic engineering. The common monitoring technique is to actively send probe packets from selected vantage points (hosts or middleboxes). In traditional networks, the control over the network routing is limited, making it impossible to monitor every selected path. The emerging concept of Software Defined Networking simplifies network control. However, OpenFlow, the common SDN protocol, does not support RTT monitoring as part of its specification. In this paper, we leverage the ability of OpenFlow to control the routing, and present GRAMI, the Granular RTT Monitoring Infrastructure. GRAMI uses active probing from selected vantage points for efficient RTT monitoring of all the links and any round-trip path between any two switches in the network.
  GRAMI was designed to be resource efficient. It requires only four flow entries installed on every switch in order to enable RTT monitoring of all the links. For every round-trip path selected by the user, it requires a maximum of two additional flow entries installed on every switch along the measured path. Moreover, GRAMI uses a minimal number of probe packets, and does not require the involvement of the controller during online RTT monitoring.

• Netanel Cohen, Anat Bremler-Barr, "Graph-based Cloud Resource Cleanup", in ACM SoCC Poster Session, August 2015
  [poster]
• Mor Sides, Anat Bremler-Barr, Elisha Rosensweig, "Yo-Yo Attack - Vulnerability in auto-scaling mechanism", in ACM SIGCOMM Poster Session, August 2015
  [pdf] [poster]
• Yehuda Afek, Anat Bremler-Barr, Shir Landau Feibish, Liron Schiff, "Sampling and Large Flow Detection in SDN", in ACM SIGCOMM Poster Session, August 2015
  [pdf] [poster]
• Anat Bremler-Barr, Yotam Harchol, David Hay, "OpenBox: Enabling Innovation in Middlebox Applications", in ACM SIGCOMM HotMiddleboxes, August 2015
  [pdf][slides][abstract]

  OpenBox: Enabling Innovation in Middlebox Applications

  By Anat Bremler-Barr, Yotam Harchol, David Hay

  Contemporary networks contain many different kind of middleboxes that perform variety of advanced network functions. Currently, a special box is tailored to provide each such function. These special boxes are usually proprietary, and operators control over them is limited to the set of capabilities defined by the provider of each box. Nonetheless, many middleboxes perform very similar tasks.
  In this paper we present OpenBox: a logically-centralized framework that makes advanced packet processing and monitoring easier, faster, more scalable, flexible, and innovative. OpenBox decouples the control plane of middleboxes from their data plane, and unifies the data plane of multiple middlebox applications using entities called service instances. On top of the centralized control plane everyone can develop box applications. A box application, formerly implemented as a separate middlebox, instructs the data plane how to process packets in order to achieve its intended function. OpenBox service instances reside in data plane and process packets according to policies defined by the control plane. They can be implemented in software or use specialized hardware.

• Anat Bremler-Barr, Yotam Harchol, David Hay, Yacov Hel-Or, "Ultra-Fast Similarity Search Using Ternary Content Addressable Memory", in ACM DaMoN, June 2015
  [pdf][slides][abstract]

  Ultra-Fast Similarity Search Using Ternary Content Addressable Memory

  By Anat Bremler-Barr, Yotam Harchol, David Hay, Yacov Hel-Or

  Similarity search, and specifically the nearest-neighbor search (NN) problem is widely used in many fields of computer science such as machine learning, computer vision and databases. However, in many settings such searches are known to suffer from the notorious curse of dimensionality, where running time grows exponentially with d. This causes severe performance degradation when working in high-dimensional spaces. Approximate techniques such as locality-sensitive hashing improve the performance of the search, but are still computationally intensive.
  In this paper we propose a new way to solve this problem using a special hardware device called ternary content addressable memory (TCAM). TCAM is an associative memory, which is a special type of computer memory that is widely used in switches and routers for very high speed search applications. We show that the TCAM computational model can be leveraged and adjusted to solve NN search problems in a single TCAM lookup cycle, and with linear space. This concept does not suffer from the curse of dimensionality and is shown to improve the best known approaches for NN by more than four orders of magnitude. Simulation results demonstrate dramatic improvement over the best known approaches for NN, and suggest that TCAM devices may play a critical role in future large-scale databases and cloud applications.

• Yehuda Afek, Anat Bremler-Barr, and Liron Schiff, "ORange: Multi field openflow based range classifier", in ACM/IEEE ANCS, May 2015
  [pdf][slides][abstract]

  ORange: Multi field openflow based range classifier

  By Yehuda Afek, Anat Bremler-Barr, and Liron Schiff

  Configuring range based packet classification rules in network switches is crucial to all network core functionalities, such as firewalls and routing. However, OpenFlow, the leading management protocol for SDN switches, lacks the interface to configure range rules directly and only provides mask based rules, named flow entries.
  In this work we present, ORange, the first solution to multi dimensional range classification in OpenFlow. Our solution is based on paradigms used in state of the art non-OpenFlow classifiers and is designed in a modular fashion allowing future extensions and improvements. We consider switch space utilization as well as atomic updates functionality, and in the network context we provide flow consistency even if flows change their entrance point to the network during policy updates, a property we name cross-entrance consistency. Our scheme achieves remarkable results and is easy to deploy.

• Michela Becchi, Anat Bremler-Barr, David Hay, Omer Kochba, Yaron Koral, "Accelerating Regular Expression Matching Over Compressed HTTP". In IEEE INFOCOM, April 2015
  [pdf][slides][abstract]

  Accelerating Regular Expression Matching Over Compressed HTTP

  By Michela Becchi, Anat Bremler-Barr, David Hay, Omer Kochba, Yaron Koral

  This paper focuses on regular expression matching over compressed traffic. The need for such matching arises from two independent trends. First, the volume and share of compressed HTTP traffic is constantly increasing. Second, due to their superior expressibility, current Deep Packet Inspection engines use regular expressions more and more frequently.
  We present an algorithmic framework to accelerate such matching, taking advantage of information gathered when the traffic was initially compressed. HTTP compression is typi- cally performed through the GZIP protocol, which uses back- references to repeated strings. Our algorithm is based on calcu- lating (for every byte) the minimum number of (previous) bytes that can be part of a future regular expression matching. When inspecting a back-reference, only these bytes should be taken into account, thus enabling one to skip repeated strings almost entirely without missing a match. We show that our generic framework works with either NFA-based or DFA-based implementations and gains performance boosts of more than 70%. Moreover, it can be readily adapted to most existing regular expression matching algorithms, which usually are based either on NFA, DFA or combinations of the two. Finally, we discuss other applications in which calculating the number of relevant bytes becomes handy, even when the traffic is not compressed.

• Anat Bremler-Barr, Shimrit Tzur David, Yotam Harchol, David Hay, "Leveraging Traffic Repetitions for High-Speed Deep Packet Inspection". In IEEE INFOCOM, April 2015
  [pdf][slides][abstract]

  Leveraging Traffic Repetitions for High-Speed Deep Packet Inspection

  By Anat Bremler-Barr, Shimrit Tzur David, Yotam Harchol, David Hay

  Deep Packet Inspection (DPI) plays a major role in contemporary networks. Specifically, in datacenters of content providers, the scanned data may be highly repetitive. Most DPI engines are based on identifying signatures in the packet payload. This pattern matching process is expensive both in memory and CPU resources, and thus, often becomes the bottleneck of the entire application.
  In this paper we show how DPI can be accelerated by leveraging repetitions in the inspected traffic. Our new mechanism makes use of these repetitions to allow the repeated data to be skipped rather than scanned again. The mechanism consists of a slow path, in which frequently repeated strings are identified and stored in a dictionary, along with some succinct information for accelerating the DPI process, and a data path, where the traffic is scanned byte by byte but strings from the dictionary, if encountered, are skipped. Upon skipping, the data path recovers to the state it would have been in had the scanning continued byte by byte.
  Our solution achieves a significant performance boost, especially when data is from the same content source (e.g., the same website). Our experiments show that for such cases, our solution achieves a throughput gain of 1.25 − 2.5 times the original throughput, when implemented in software.

• Anat Bremler-Barr, Yotam Harchol, David Hay, Yaron Koral, "Deep Packet Inspection as a Service". in ACM CoNEXT, December 2014
  [pdf][slides][abstract]

  Deep Packet Inspection as a Service

  Anat Bremler-Barr, Yotam Harchol, David Hay, Yaron Koral

  Middleboxes play a major role in contemporary networks, as for- warding packets is often not enough to meet operator demands, and other functionalities (such as security, QoS/QoE provisioning, and load balancing) are required. Traffic is usually routed through a sequence of such middleboxes, which either reside across the net- work or in a single, consolidated location. Although middleboxes provide a vast range of different capabilities, there are components that are shared among many of them.

  A task common to almost all middleboxes that deal with L7 protocols is Deep Packet Inspection (DPI). Today, traffic is inspected from scratch by all the middleboxes on its route. In this paper, we propose to treat DPI as a service to the middleboxes, implying that traffic should be scanned only once, but against the data of all middleboxes that use the service. The DPI service then passes the scan results to the appropriate middleboxes. Having DPI as a service has significant advantages in performance, scalability, robustness, and as a catalyst for innovation in the middlebox domain. Moreover, technologies and solutions for current Software Defined Networks (SDN) (e.g., SIMPLE [42]) make it feasible to implement such a service and route traffic to and from its instances.

• Liron Schiff, Michael Borokhovich, Stefan Schmid, "Reclaiming the Brain: Useful OpenFlow Functions in the Data Plane". in HotNets 2014
  [pdf][slides][abstract]

  Reclaiming the Brain: Useful OpenFlow Functions in the Data Plane

  By Liron Schiff, Michael Borokhovich, Stefan Schmid

  Software-defined networks (SDNs) have the potential to radically simplify the network management by providing a programmatic interface to a logically centralized controller. However, outsourcing the management to the software controller comes at a price, and good tradeoffs have to be found between the benefits of a fine-grained control and its costs.
  In this paper, we show that OpenFlow, the predominant SDN protocol, allows to implement powerful functions “in the south”, i.e., in the data plane. Our approach, called SmartSouth, can be used to reduce interactions with the control plane as well as to make the network more robust. Moreover, while rendering the data plane “smarter”, SmartSouth only relies on the standard OpenFlow match- action paradigm; thus, the data plane functions remain formally verifiable—a key benefit of SDN. To demonstrate the potential of SmartSouth, we discuss four basic applications: (1) topology snapshot, (2) anycast, (3) blackhole- and (4) critical node detection.

• Michael Borokhovich, Liron Schiff, Stefan Schmid. "Provable Data Plane Connectivity with Local Fast Failover: Introducing OpenFlow Graph Algorithms". In HotSDN 2014.
  [pdf][slides][abstract]

  Provable Data Plane Connectivity with Local Fast Failover: Introducing OpenFlow Graph Algorithms

  By Michael Borokhovich, Liron Schiff, Stefan Schmid

  Modern software-defined networks support the implementation of in-network failover mechanisms: mechanisms to quickly re-establish connectivity in the data plane without the interaction of the software controller. Interestingly, however, not much is known today about how to make use of these mechanisms.
  This paper shows a very strong result: there exist failover implementations for OpenFlow that achieve a maximal robustness, in the sense that connectivity is always ensured as long as the underlying physical network is connected. In particular, we show that the problem of computing failover tables is related to graph search, and present three different algorithms achieving different tradeoffs, in terms of the number of required failover rules, the number of tags, as well as the resulting path lengths.
  Our work can also be seen as a first attempt to implement classic graph algorithms in OpenFlow.

• Yehuda Afek, Anat Bremler-Barr, Liron Schiff, "Cross-Entrance Consistent Range Classifier with OpenFlow". in ONS 2014, HotSDN 2014
  [pdf][poster]
• Yehuda Afek, Anat Bremler-Barr, Shir Landau Feibish, "Automated Signature Extraction for High Volume Attacks", in ACM/IEEE ANCS, October 2013
  [pdf][slides][abstract]

  Automated Signature Extraction for High Volume Attacks

  By Y. Afek, A. Bremler-Barr, S. Landau Feibish

  We present a basic tool for zero day attack signature extraction. Given two large sets of messages, P of messages captured in the network at peacetime (i.e., mostly legitimate traffic) and A captured during attack time (i.e., contains many attack messages), we present a tool for extracting a set S of strings, that are frequently found in A and not in P . Therefore, a packet containing one of the strings from S is likely to be an attack packet.
  This is an important tool in protecting sites on the Internet from Worm attacks, and Distributed Denial of Service (DDoS) attacks. It may also be useful for other problems, including command and control identification, DNA-sequences analysis, etc. which are beyond the scope of this work.
  Two contributions of this paper are the system we developed to extract the required signatures together with the problem definition and the string-heavy hitters algorithm. This algorithm finds popular strings of variable length in a set of messages, using, in a tricky way, the classic heavy-hitter algorithm as a building block. This algorithm is then used by our system to extract the desired signatures. Using our system a yet unknown attack can be detected and stopped within minutes from attack start time.

• Yehuda Afek, Anat Bremler-Barr, Liron Schiff, "Recursive Design of Hardware Priority Queues", in ACM SPAA, July 2013
  [pdf][slides][abstract]

  Recursive Design of Hardware Priority Queues

  By Y. Afek, A. Bremler-Barr, L. Schiff

  A recursive and fast construction of an n elements priority queue from exponentially smaller hardware priority queues and size n RAM is presented. All priority queue implementations to date either require O (log n ) instructions per operation or exponential (with key size) space or expensive special hardware whose cost and latency dramatically increases with the priority queue size. Hence constructing a priority queue (PQ) from considerably smaller hardware priority queues (which are also much faster)
  while maintaining the O (1) steps per PQ operation is critical. Here we present such an acceleration technique called the Power Priority Queue (PPQ) technique. Specifically, an n elements PPQ is constructed from 2k −1 primitive priority queues of size k√n ( k = 2 , 3 , ... ) and a RAM of size n , where the throughput of the construct beats that of a single, size n primitive hardware priority queue. For example an n elements PQ can be constructed from either three √n or five 3√n primitive H/W priority queues.
  Applying our technique to a TCAM based priority queue, results in TCAM-PPQ, a scalable perfect line rate fair queuing of millions of concurrent connections at speeds of 100 Gbps. This demonstrates the benefits of our scheme when used with hardware TCAM, we expect similar results with systolic arrays,
  shift-registers and similar technologies.
  As a by product of our technique we present an O(n) time sorting algorithm i n a system equipped with a O(w√n) entries TCAM, where here n is the number of items, and w is the maximum number of bits required to represent an item, improving on a previous result that used an Ω(n) entries TCAM. Finally, we provide a lower bound on the time complexity of sorting n elements with TCAM of size O(n) that matches our TCAM based sorting algorithm.

• Yossi Kanizo, David Hay, Isaac Keslassy, "Palette: Distributing Tables in Software-Defined Networks", in IEEE Infocom Mini-conference, April 2013
  [pdf][abstract]

  Palette: Distributing Tables in Software-Defined Networks

  By Y. Kanizo, D. Hay, I. Keslassy

  In software-defined networks (SDNs), the network controller first formulates abstract network-wide policies, and then implements them in the forwarding tables of network switches. However, fast SDN tables often cannot scale beyond a few hundred entries. This is because they typically include wildcards, and therefore are implemented using either expensive and power-hungry TCAMs, or complex and slow data structures.
  
  This paper presents the Palette distribution framework for decomposing large SDN tables into small ones and then distributing them across the network, while preserving the overall SDN policy semantics. Palette helps balance the sizes of the tables across the network, as well as reduce the total number of entries by sharing resources among different connections. It copes with two NP-hard optimization problems: Decomposing a large SDN table into equivalent subtables, and distributing the subtables such that each connection traverses each type of subtable at least once. To implement the Palette distribution framework, we introduce graph-theoretical formulations and algorithms, and show that they achieve close-to-optimal results in practice.

• Yehuda Afek, Anat Bremler-Barr, Yotam Harchol, David Hay, Yaron Koral, “MCA^2: Multi-Core Architecture for Mitigating Complexity Attacks”, in ACM/IEEE ANCS, 2012
  [pdf][slides][abstract]

  MCA^2: Multi-Core Architecture for Mitigating Complexity Attacks

  By Y. Afek, A. Bremler-Barr, Y. Harchol, D. Hay, Y. Koral

  This paper takes advantage of the emerging multi-core computer architecture to design a general framework for mitigating network-based complexity attacks. In complexity attacks, an attacker carefully crafts "heavy" messages (or packets) such that each heavy message consumes substantially more resources than a normal message. Then, it sends a sufficient number of heavy messages to bring the system to a crawl at best. In our architecture, called MCA^2 - Multi-Core Architecture for Mitigating Complexity Attacks - cores quickly identify such suspicious messages and divert them to a fraction of the cores that are dedicated to handle all the heavy messages. This keeps the rest of the cores relatively unaffected and free to provide the legitimate traffic the same quality of service as if no attack takes place.
  We demonstrate the effectiveness of our architecture by examining cache-miss complexity attacks against Deep Packet Inspection (DPI) engines. For example, for Snort DPI engine, an attack in which 30% of the packets are malicious degrades the system throughput by over 50%, while with MCA^2 the throughput drops by either 20% when no packets are dropped or by 10% in case dropping of heavy packets is allowed. At 60% malicious packets, the corresponding numbers are 70%, 40% and 23%.

• Yossi Kanizo, David Hay, Issac Keslassy, “Access-Efficient Balanced Bloom Filters”, in IEEE ICC, 2012
  [pdf][abstract]

  Access-Efficient Balanced Bloom Filters

  By Y. Kanizo, D. Hay, I. Keslassy

  Bloom Filters should particularly suit network devices, because of their low theoretical memory-access rates. However, in practice, since memory is often divided into blocks and Bloom Filters hash elements into several arbitrary memory blocks, Bloom Filters actually need high memory-access rates. On the other hand, hashing all Bloom Filter elements into a single memory block to solve this problem also yields high false positive rates.
  In this paper, we propose to implement load-balancing schemes for the choice of the memory block, along with an optional overflow list, resulting in improved false positive rates while keeping a high memory-access efficiency. To study this problem, we define, analyze and solve a fundamental access-constrained balancing problem, where incoming elements need to be optimally balanced across resources while satisfying average and instantaneous constraints on the number of memory accesses associated with checking the current load of the resources. We then build on this problem to suggest a new access-efficient Bloom Filter scheme, called the Balanced Bloom Filter. Finally, we show that this scheme can reduce the false positive rate by up to two orders of magnitude, with a worst-case cost of up to 3 memory accesses for each element and an overflow list size of 0 . 5% of the elements.

• Anat Bremler-Barr, Shimrit Tzur-David, David Hay, Yaron Koral,"Decompression-Free Inspection: DPI for Shared Dictionary Compression over HTTP", in IEEE INFOCOM 2012
  [pdf][slides][abstract]

  Decompression-Free Inspection: DPI for Shared Dictionary Compression over HTTP

  By A. Bremler-Barr, S. Tzur-David, D. Hay, Y. Koral

  Deep Packet Inspection (DPI) is the most time and resource consuming procedure in contemporary security tools such as Network Intrusion Detection/Prevention System (NIDS/IPS), Web Application Firewall (WAF), or Content Filtering Proxy. DPI consists of inspecting both the packet header and payload and alerting when signatures of malicious software appear in the traffic. These signatures are identified through pattern matching algorithms.
  The portion of compressed traffic of overall Internet traffic is constantly increasing. This paper focuses on traffic compressed using shared dictionary. Unlike traditional compression algorithms, this compression method takes advantage of the inter-response redundancy (e.g., almost the same data is sent over and over again) as in nowadays dynamic Data. Shared Dictionary Compression over HTTP (SDCH), introduced by Google in 2008, is the first algorithm of this type. SDCH works well with other compression algorithm (as Gzip), making it even more appealing. Performing DPI on any compressed traffic is considered hard, therefore today’s security tools either do not inspect compressed data, alter HTTP headers to avoid compression, or decompress the traffic before inspecting it.
  We present a novel pattern matching algorithm that inspects SDCH-compressed traffic without decompressing it first. Our algorithm relies on offline inspection of the shared dictionary, which is common to all compressed traffic, and marking auxiliary information on it to speed up the online DPI inspection. We show that our algorithm works near the rate of the compressed traffic, implying a speed gain of SDCH’s compression ratio (which is around 40%). We also discuss how to deal with SDCH compression over Gzip compression, and show how to perform regular expression matching with about the same speed gain.

• Anat Bremler-Barr, Yaron Koral and Victor Zigdon, "Shift-Based Pattern Matching for Compressed Web Traffic", in IEEE HPSR, 2011
  [pdf][slides][abstract]

  Shift-Based Pattern Matching for Compressed Web Traffic

  By A. Bremler-Barr, Y. Koral and V. Zigdon

  Compressing web traffic using standard GZIP is becoming both popular and challenging due to the huge increase in wireless web devices, where bandwidth is limited. Security and other content based networking devices are required to decompress the traffic of tens of thousands concurrent connections in order to inspect the content for different signatures. The overhead imposed by the decompression inhibits most devices from handling compressed traffic, which in turn either limits traffic compression or introduces security holes and other disfunctionalities.
  The ACCH algorithm was the first to present a unified approach to pattern matching and decompression, by taking advantage of information gathered in the decompression phase to accelerate the pattern matching. ACCH accelerated the DFA-based Aho-Corasick multi-pattern matching algorithm. In this paper, we present a novel algorithm, SPC (Shift-based Pattern matching for Compressed traffic) that accelerates the commonly used Wu-Manber pattern matching algorithm. SPC is simpler and has higher throughput and lower storage overhead than ACCH. Analysis of real web traffic and real security devices signatures shows that we can skip scanning up to 87 . 5% of the data and gain performance boost of more than 51% as compared to ACCH. Moreover, the additional storage requirement of the technique requires only 4 KB additional information per connection as compared to 8 KB of ACCH.

• Anat Bremler-Barr, Yotam Harchol and David Hay , "Space-time tradeoffs in Software-based Deep Packet Inspection", in IEEE HPSR, 2011
  [pdf][slides][abstract]

  Space-time tradeoffs in Software-based Deep Packet Inspection

  By A. Bremler-Barr, Y. Harchol and D.Hay

  Deep Packet Inspection (DPI) lies at the core of contemporary Network Intrusion Detection/Prevention Systems and Web Application Firewalls. DPI aims to identify various malware (including spam and viruses) by inspecting both the header and the payload of each packet and comparing it to a known set of patterns. DPI is often performed on the critical path of the packet processing, thus the overall performance of the security tools is dominated by the speed of DPI. The seminal algorithm of Aho-Corasick (AC) is the de-facto standard for pattern matching in network intrusion detection systems (NIDS). Basically, the AC algorithm constructs a Deterministic Finite Automaton (DFA) for detecting all occurrences of a given set of patterns by processing the input in a single pass. The input is inspected symbol by symbol (usually each symbol is a byte), such that each symbol results in a state transition. Thus, in principle, the AC algorithm has deterministic performance, which does not depend on specific input and therefore is not vulnerable to algorithmic complexity attacks, making it very attractive to NIDS systems.
  In this paper we show that, when implementing the AC algorithm in software, this property does not hold, due to the fact that contemporary pattern sets induce very large DFAs that cannot be stored entirely in cache. We then propose a novel technique to compress the representation of the Aho-Corasick automaton, so it can fit in modern cache. We compare both the performance and the memory footprint of our technique to previously-proposed implementation, under various settings and pattern sets. Our results reveal the space-time tradeoffs of DPI. Specifically, we show that our compression technique reduces the memory footprint of the best prior-art algorithm by approximately 60% , while achieving comparable throughput.

• Yehuda Afek, Anat Bremler-Barr, Yaron Koral, "Efficient Processing of Multi-Connection Compressed Web Traffic", in NETWOKING, 2011
  [pdf][slides][abstract]

  Efficient Processing of Multi-Connection Compressed Web Traffic

  By Y. Afek, A. Bremler-Barr, Y. Koral

  Compressing web traffic using standard GZIP is becoming both popular and challenging due to the huge increase in wireless web devices, where bandwidth is limited. Security and other content based networking devices are required to decompress the traffic of tens of thousands concurrent connections in order to insp ect the content for different signatures. The major limiting factor in this pro cess is the high memory requirements of 32KB p er connection that leads to hundreds of megabytes to gigabytes of main memory consumption. This requirement inhibits most devices from handling compressed traffic, which in turn either limits traffic compression or intro duces security holes and other dysfunctionalities. In this paper we introduce new algorithms and techniques that drastically reduce this space requirement by over 80%, with only a slight increase in the time overhead, thus making real-time compressed traffic inspection a viable option for network devices.

Journal Publications:

• Liron Schiff, Stefan Schmid, Petr Kuznetsov, "In-Band Synchronization for Distributed SDN Control Planes". In ACM SIGCOMM Computer Communication Review. Vol. 46, Issue 1, January 2016.
  [pdf][abstract]

  In-Band Synchronization for Distributed SDN Control Planes

  By Liron Schiff, Stefan Schmid, Petr Kuznetsov

  Control planes of forthcoming Software-Defined Networks (SDNs) will be distributed: to ensure availability and fault-tolerance, to improve load-balancing, and to reduce overheads, modules of the control plane should be physically distributed. However, in order to guarantee consistency of network operation, actions performed on the data plane by different controllers may need to be synchronized, which is a nontrivial task. In this paper, we propose a synchronization framework for control planes based on atomic transactions, implemented in-band, on the data-plane switches. We argue that this in-band approach is attractive as it keeps the failure scope local and does not require additional out-of-band coordination mechanisms. It allows us to realize fundamental consensus primitives in the presence of controller failures, and we discuss their applications for consistent policy composition and fault-tolerant control-planes. Interestingly, by using part of the data plane configuration space as a shared memory and leveraging the match-action paradigm, we can implement our synchronization framework in today's standard OpenFlow protocol, and we report on our proof-of-concept implementation.

• Yehuda Afek, Anat Bremler-Barr, Yotam Harchol, David Hay, Yaron Koral, "Making DPI Engines Resilient to Algorithmic Complexity Attacks". In IEEE/ACM Transactions on Networking, Volume 24, Issue 6, 2016.
  [pdf][abstract]

  Making DPI Engines Resilient to Algorithmic Complexity Attacks

  By Yehuda Afek, Anat Bremler-Barr, Yotam Harchol, David Hay, Yaron Koral

  This paper starts by demonstrating the vulnerability of Deep Packet Inspection (DPI) mechanisms, which are at the core of security devices, to algorithmic complexity denial of service attacks, thus exposing a weakness in the first line of defense of enterprise networks and clouds. A system and a multi-core architecture to defend from these algorithmic complexity attacks is presented in the second part of the paper. The integration of this system with two different DPI engines is demonstrated and dis- cussed. The vulnerability is exposed by showing how a simple low bandwidth cache-miss attack takes down the Aho-Corasick (AC) pattern matching algorithm that lies at the heart of most DPI engines. As a first step in the mitigation of the attack, we have developed a compressed variant of the AC algorithm that improves the worst case performance (under an attack). Still, under normal traffic its running-time is worse than classical AC implementations. To overcome this problem, we introduce MCA^2 —Multi- Core Architecture to Mitigate Complexity Attacks, which dynamically combines the classical AC algorithm with our compressed implementation, to provide a robust solution to mitigate this cache- miss attack. We demonstrate the effectiveness of our architecture by examining cache-miss algorithmic complexity attacks against DPI engines and show a goodput boost of up to 73%. Finally, we show that our architecture may be generalized to provide a principal solution to a wide variety of algorithmic complexity attacks.

• Yehuda Afek, Anat Bremler-Barr, Liron Schiff, "Recursive design of hardware priority queues". In Computer Networks 66: 52-67, 2014.
  [pdf][abstract]

  Recursive design of hardware priority queues

  By Yehuda Afek, Anat Bremler-Barr, Liron Schiff

• Udi Ben-Porat, Anat Bremler-Barr, Hanoch Levy, "Computer and Network Performance: Graduating from the 'Age of Innocence'". In Computer Networks 66: 68-81, 2014.
  [pdf][abstract]

  Computer and Network Performance: Graduating from the "Age of Innocence"

  By Udi Ben-Porat, Anat Bremler-Barr, Hanoch Levy

  Performance analysis has been used for over half a century for the design and operations of computer systems and communications networks. This methodology, mostly stochastic in nature, has been based on the underlying paradigm that users are innocent and “well behaving”. Following the flourish of the internet and the subsequent rise of malicious incidents, research started investigating the effect of malicious attacks aimed at degrading system performance.

  The objective of this work is to understand how system performance is affected by malicious behavior and how performance evaluation should account for it. We do so by considering an array of “classical” systems taken from the literature and examining their degree of vulnerability. These can also serve in providing some initial insights into what makes a system design vulnerable or resilient.

• Anat Bremler-Barr, Yaron Koral, David Hay, "CompactDFA: Scalable Pattern Matching using Longest Prefix Match Solutions", In IEEE/ACM Transactions on Networking, 2013.
  [pdf][abstract]

  CompactDFA: Scalable Pattern Matching using Longest Prefix Match Solutions

  By A. Bremler-Barr, Y. Koral, D. Hay

  A central component in all contemporary intrusion detection systems (IDSs) is their pattern matching algorithms, which are often based on constructing and traversing a deterministic finite automaton (DFA) that represents the patterns. While this approach ensures deterministic time guarantees, modern IDSs need to deal with hundreds of patterns, thus requiring to store very large DFAs, which usually do not fit in fast memory. This results in a major bottleneck on the throughput of the IDS, as well as its power consumption and cost. We propose a novel method to compress DFAs by observing that the name used by common DFA encoding is meaningless. While regular DFAs store separately each transition between two states, we use this degree of freedom and encode states in such a way that all transitions to a specific state are represented by a single prefix that defines a set of current states. Our technique applies to a large class of automata, which can be categorized by simple properties. Then, the problem of pattern matching is reduced to the well-studied problem of Longest Prefix Match (LPM), which can be solved either in ternary content-addressable memory (TCAM), in commercially available IP-lookup chips, or in software. Specifically, we show that with a TCAM our scheme can reach a throughput of 10 Gb/s with low power consumption.

• Yossi Kanizo, David Hay, Isaac Keslassy, "Access-Efficient Balanced Bloom Filters", In Computer Communication. 36(4), 373-385, January 2013
  [pdf][abstract]

  Access-Efficient Balanced Bloom Filters

  By Y. Kanizo, D. Hay, I. Keslassy

  Bloom Filters particularly suit network devices, because of their low theoretical memory-access rates. However, in practice, since memory is often divided into blocks and Bloom Filters hash elements into several arbitrary memory blocks, Bloom Filters actually need high memory-access rates. Unfortunately, a simple solution of hashing all Bloom Filter elements into a single memory block yields high false positive rates.
  
  In this paper, we propose to implement load-balancing schemes for the choice of the memory block, along with an optional overflow list, resulting in better false positive rates while keeping a high memory-access efficiency. To study this problem, we define, analyze and solve a fundamental access-constrained balancing problem, where incoming elements need to be optimally balanced across resources while satisfying average and instantaneous constraints on the number of memory accesses associated with checking the current load of the resources. We then use these results and suggest a new access-efficient Bloom Filter scheme in networking devices, called the Balanced Bloom Filter. Finally, we show that with a worst-case operation cost of up to 3 memory accesses for each element and an overflow list size of at most 0.5% of the elements, our scheme can reduce the false positive rate by up to two orders of magnitude compared to a filter that hashes all elements into a single memory block.

• Anat Bremler-Barr, David Hay, Danny Hendler, "Layered Interval Codes for TCAM-Based Classification", In Computer Networks. 56(13): 3023-3039, September 2012. Special issue on Challenges in High-Performance Switching and Routing in the Future Internet.
  [pdf][abstract]

  Layered Interval Codes for TCAM-Based Classification

  By A. Bremler-Barr, D. Hay, D. Hendler

  Ternary content-addressable memories (TCAMs) are increasingly used for high-speed packet classification. TCAMs compare packet headers against all rules in a classification database in parallel and thus provide high throughput.
  
  TCAMs are not well-suited, however, for representing rules that contain range fields and previously published algorithms typically represent each such rule by multiple TCAM entries. The resulting range expansion can dramatically reduce TCAM utilization because it introduces a large number of redundant TCAM entries. This redundancy can be mitigated by making use of extra bits, available in each TCAM entry.
  
  We present a scheme for constructing efficient representations of range rules, based on the simple observation that sets of disjoint ranges may be encoded much more efficiently than sets of overlapping ranges. Since the ranges in real-world classification databases are, in general, non-disjoint, the algorithms we present split ranges between multiple layers, each of which consisting of mutually disjoint ranges. Each layer is then coded and assigned its own set of extra bits.
  
  Our layering algorithms are based on approximations for specific variants of interval-graph coloring. We evaluate these algorithms by performing extensive comparative analysis on real-life classification databases. Our analysis establishes that our algorithms reduce the number of redundant TCAM entries caused by range rules by more than 60% as compared with best range-encoding prior work.

• Yossi Kanizo, David Hay, Issac Keslassy, "Hash tables with finite buckets are less resistant to deletions", Computer Communication, 2012
  [pdf][abstract]

  Hash tables with finite buckets are less resistant to deletions

  By Y. Kanizo, D. Hay, I. Keslassy

  We show that when memory is bounded, i.e. buckets are finite, dynamic hash tables that allow insertions and deletions behave significantly worse than their static counterparts that only allow insertions. This behavior differs from previous results in which, when memory is unbounded, the two models behave similarly. We show the decrease in performance in dynamic hash tables using several hash-table schemes. We also provide tight upper and lower bounds on the achievable overflow fractions in these schemes. Finally, we propose an architecture with content-addressable memory (CAM), which mitigates this decrease in performance.

• Yehuda Afek, Anat Bremler-Barr, Yaron Koral, "Space Efficient Deep Packet Inspection of Compressed Web Traffic", Computer Communication, 2012
  [pdf][abstract]

  Space Efficient Deep Packet Inspection of Compressed Web Traffic

  By Y. Afek, A. Bremler-Barr, Y. Koral

  In this paper we focus on the process of deep packet inspection of compressed web traffic. The major limiting factor in this process imposed by the compression, is the high memory requirements of 32KB per connection. This leads to the requirements of hundreds of megabytes to gigabytes of main memory on a multi-connection setting. We introduce new algorithms and techniques that drastically reduce this space requirement for such bump-in-the-wire devices like security and other content based networking tools. Our proposed scheme improves both space and time performance by almost 80% and over 40% respectively, thus making real-time compressed traffic inspection a viable option for networking devices.

• Anat Bremler-Barr, Yaron Koral , "Accelerating Multi-patterns Matching on Compressed HTTP traffic", ACM/IEEE Transactions on Networking, 2011
  [pdf][abstract]

  Accelerating Multi-patterns Matching on Compressed HTTP traffic

  By A. Bremler-Barr, Y. Koral

  Current security tools, using ‘signature-based’ detection, do not handle compressed traffic, whose market-share is constantly increasing. This paper focus on compressed HTTP traffic. HTTP uses GZIP compression and requires some kind of decompression phase before performing a string-matching.
  We present a novel algorithm, Aho-Corasick-based algorithm for Compressed HTTP (ACCH), that takes advantage of information gathered by the decompression phase in order to accelerate the commonly used Aho-Corasick pattern matching algorithm. By analyzing real HTTP traffic and real web application firewall signatures, we show that up to 84% of the data can be skipped in its scan. Surprisingly, we show that it is faster to perform pattern matching on the compressed data, with the penalty of decompression, than on regular traffic. As far as we know, we are the first paper that analyzes the problem of ‘on-the-fly’ multi-pattern matching on compressed HTTP traffic and suggest a solution.

Dissertations:

• Idan Moyal, "Load Balancing Memcached Traffic Using SDN", M.Sc. Dissertation
  [pdf]
• Yotam Harchol, "A Software-Defined Framework for Improved Performance and Security of Network Functions", Ph.D. Dissertation
  [pdf]
• Liron Schiff, "Network Algorithms with Fast Match-Action Modules", Ph.D. Dissertation
  [pdf]
• Omer Kochba, "Accelerating Regular Expression Matching over Compressed HTTP Traffic", M.Sc. Dissertation
  [pdf]
• Alon Atari, "Efficient Round-Trip Time Monitoring in OpenFlow Networks", M.Sc. Dissertation
  [pdf][slides]
• Yaron Koral, "High Performance Deep Packet Inspection", Ph.D. Dissertation
  [pdf]

Talks:

• Yotam Harchol, Making Network Functions Software-Defined - At Stanford University NetSeminar
  [slides][video]
• David Hay, OpenBox: A Software-Defined Framework for Development, Deployment, and Management of Network Functions - At Budapest University of Technology and Economics
  [slides]
• Yotam Harchol, Encoding Short Ranges in TCAM Without Expansion: Efficient Algorithm and Applications - At Israeli Networking Day 2016
  [slides]
• Yotam Harchol, OpenBox: A Software-Defined Framework for Development, Deployment, and Management of Network Functions - Highlight Paper at SYSTOR 2016
  [slides]
• Yotam Harchol, OpenBox: A Software-Defined Framework for Development, Deployment, and Management of Network Functions - At I-Core Day Workshop 2015
  [slides]
• Anat Bremler-Barr, Opportunities in Middlebox Virtualization - Keynote Speech at SYSTOR 2015
  [slides]
• Anat Bremler-Barr, Deep Packet Inspection of Next Generation Network Devices - At I-Core Day Workshop 2015
  [slides][video]
• Anat Bremler-Barr, Deep Packet Inspection as a Service - At Amdocs NFV Conference 2015
  [slides]
• Introduction to DEEPNESS Lab
  [slides]

Code:

The code related to our projects is publicly available on our github.