Shir Landau Feibish, Yehuda Afek, Anat Bremler-Barr, Edith Cohen, Michal Shagam, "Mitigating DNS random subdomain DDoS attacks by distinct heavy Hitters sketches". HotWeb 2017
[technical report ][abstract]
Mitigating DNS random subdomain DDoS attacks by distinct heavy Hitters sketches
Shir Landau Feibish, Yehuda Afek, Anat Bremler-Barr, Edith Cohen, Michal Shagam
Motivated by a recent new type of randomized Distributed Denial
of Service (DDoS) attacks on the Domain Name Service (DNS),
we develop novel and efficient distinct heavy hitters algorithms and
build an attack identification system that uses our algorithms.
Heavy hitter detection in streams is a fundamental problem with
many applications, including detecting certain DDoS attacks and
anomalies. A (classic) heavy hitter (HH) in a stream of elements is
a key (e.g., the domain of a query) which appears in many elements
(e.g., requests). When stream elements consist of a hkey, subkeyi
pairs, (hdomain, subdomaini) a distinct heavy hitter (dhh) is a
key that is paired with a large number of different subkeys. Our
dHH algorithms are considerably more practical than previous algorithms.
Specifically the new fixed-size algorithms are simple to
code and with asymptotically optimal space accuracy tradeoffs.
In addition we introduce a new measure, a combined heavy hitter
(cHH), which is a key with a large combination of distinct and
classic weights. Efficient algorithms are also presented for cHH
detection.
Finally, we perform extensive experimental evaluation on real
DNS attack traces, demonstrating the effectiveness of both our algorithms
and our DNS malicious queries identification system.
Anat Bremler-Barr, David Hay, Idan Moyal, and Liron Schiff, "Load Balancing Memcached Traffic Using Software Defined Networking". IFIP Networking 2017
[pdf][slides][abstract]
Load Balancing Memcached Traffic Using Software Defined Networking
By Anat Bremler-Barr, David Hay, Idan Moyal, and Liron Schiff
Memcached is an in-memory key-value distributed caching solution, commonly used by web servers for fast content delivery. Keys with their values are distributed between Memcached servers using a consistent hashing technique, resulting in an even distribution (of keys) among the servers. However, as small number of keys are significantly more popular than others (a.k.a., hot keys), even distribution of keys may cause a significantly different request load on the Memcached servers, which, in turn, causes substantial performance degradation.
Previous solutions to this problem require complex application level solutions and extra servers. In this paper, we propose MBalancer–a simple L7 load balancing scheme for Memcached that can be seamlessly integrated into Memcached architectures running over Software-Defined Networks (SDN). In a nutshell, MBalancer runs as an SDN application and duplicates the hot keys to many (or all) Memcached servers. The SDN controller updates the SDN switches forwarding tables and uses SDN readymade load balancing capabilities. Thus, no change is required to Memcached clients or servers.
Our analysis shows that with minimal overhead for storing a few extra keys, the number of requests per server is close to balanced (assuming requests for keys follows a Zipf distribution). Moreover, we have implemented MBalancer on a hardware based OpenFlow switch. As MBalancer offloads requests from bottleneck Memcached servers, our experiments show that it achieves significant throughput boost and latency reduction.
Anat Bremler-Barr, Eli Broshþ, Mor Sides, "DDoS Attack on Cloud Auto-scaling Mechanisms". in 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". in INFOCOM 2017
[pdf][slides][technical report][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.
Y. Afek, A. Bremler-Barr, S. Landau Feibish, "Automated Signature Extraction for High Volume Attacks", in ANCS 2013 [ppt].
Y. Afek, A. Bremler-Barr, L. Schiff, “Space Efficient Priority Queues: The TCAM Case ",in SPAA 2013 [ppt].
Y. Afek, A. Bremler-Barr, D. Hay, Y. Harchol, Y. Koral, “MCA2: Multi Core Architecture for Mitigating Complexity Attacks ", in ANCS 2012 [ppt].
U. Ben-Porat, A. Bremler-Barr, H. Levy and B. Plattner," On the Vulnerability of Hardware Hash Tables to Sophisticated Attacks ", in Networking 2012
A. Bremler-Barr, S. Tzur-David, D. Hay, Y. Koral," Decompression-Free Inspection: DPI for Shared Dictionary Compression over HTTP ", in IEEE INFOCOM 2012 [ppt]
U. Ben-Porat, Anat Bremler-Barr and Hanoch Levy," Network and Computer Performance in Malicious Environments: The Good, the Bad and the Ugly ", in NETGCoop 2011 [ppt]
A. Bremler-Barr, Y. Koral and V. Zigdon, " Shift-Based Pattern Matching for Compressed Web Traffic ", in IEEE HPSR, 2011 [ppt]
A. Bremler-Barr, Y. Harcol and D.Hay , " Space-time tradeoffs in Software-based Deep Packet Inspection ", in IEEE HPSR, 2011 [ppt]
A. Bremler-Barr, O. Dekel, R. Golschmidt, H. Levy, " Controlling P2P applications via Address Harvesting: the Skype story ", in HOTP2P, 2011 [ppt]
Y. Afek, A. Bremler-Barr, Y. Koral, " Efficient Processing of Multi-Connection Compressed Web Traffic ", in NETWOKING, 2011 [ppt]
A. Bremler-Barr, R. Golschmidt , " On the stability of Skype Super Nodes ", in TMA workshop, 2011 [ppt]
U. Ben-Porat, B. Plattner, A. Bremler-Barr, H. Levy, " On the Vulnerability of Proportional Fairness scheduler to retransmission attacks ", in INFOCOM, 2011 [ppt]
A. Bremler-Barr, D.Hay and Y. Koral " CompactDFA: Generic State Machine Compression for Scalable Pattern Matching ", in INFOCOM, 2010 [ppt]
A. Bremler-Barr, Y. Koral " Accelerating Multi-patterns Matching on Compressed HTTP Traffic ", in INFOCOM, 2009 [ppt]
A. Bremler-Barr, D. Hay, D. Hendler, R. Roth, " PEDS: A Parallel Error Detection Scheme for TCAM Devices ", in INFOCOM, 2009. Best paper award runner-up. (Announcement) [ppt]
U. Ben-Porat, Anat Bremler-Barr, Hanoch Levy " On the Exploitation of CDF Based Wireless Scheduling in INFOCOM 2009. [ppt]
A. Bremler-Barr, D. Hay, D. Hendler, B. Ferber, " Layered Interval Codes for TCAM-based Classification ", (poster session) in SIGMERTRICS, 2008; (full paper) in INFOCOM, 2009 [ppt]
U. Ben-Porat, A. Bremler-Barr, H. Levy, " The Vulnerability of Network Mechanisms to Sophisticated DDOS attacks " in INFOCOM 2008 (mini-conference). [ppt]
A. Bremler–Barr , O. Mokryn, J. Kangasharju, N. Chen and Y. Shavitt " Bringing Order To BGP: Decreasing Convergence Message Complexity " in PODC 2007 (brief announcment) [ppt]
A. Bremler-Barr and D. Hendler " Efficient TCAM-based Packet Classification using Gray Code ", Improved BGP Convergence via Ghost Flushing . [ppt]
A. Bremler-Barr, R. Halacmi-Bekel and J. Kangasharju, " Unregister Attacks in SIP ", in NPSec workshop . [ppt]
A. Bremler-Barr, H. Levy and N. Halachmi, " Aggressiveness Protective Fair Queueing for Bursty Applications ", (short paper) in IWQoS , 2006 [ppt]
A. Bremler-Barr and H. Levy " Spoofing Prevention Method ", Brief Announcement in PODC 2004, full paper in INFOCOM 2005 . [ppt]
A. Bremler-Barr and L. Epstein, " Path layout on tree networks: Tight bounds in different label switching model ", in SIROCCO 2004.
Y. Afek, R. Brooks, N. Fischbach, P. Quinn, A. Friedrich, M. Binderberger, A. Bremler-Barr, B. Elgar, R. Hermoni, "MPLS-Based Synchronous Traffic Shunt " , in NANOG, 2003.[abstract]
A. Bremler-Barr, Y. Afek, and S. Schwarts, " Improved BGP convergence via Ghost Flushing. ", in INFOCOM 2003. [ppt]
Y. Afek, A. Bremler-Barr and O. Ben-Shalom, " On the structure and application of BGP Policy Atoms ”, in Internet Measurement Workshop, 2002. [ppt]
A. Bremler-Barr, E. Cohen, H. Kaplan, and Y. Mansour, "On the predictability and by-passability of end to end delays. ", in the Internet Measurement Workshop, 2002. [ppt]
Y. Afek, A. Bremler-Barr, H. Nussbacher, D. Touitou, "Diversion and Sieving Techniques to Defeat DDOS ", in NANOG-23 2001 [abstract]
A. Bremler-Barr, Y. Afek, H. Kaplan, E. Cohen, and M. Merrit , "Restoration by Path Concatenation: Fast recovery of MPLS paths", in SIGMETRIC 2001 (abstract) full paper in PODC, 2001. [ppt]
A. Bremler-Barr, Y. Afek, "Trainet: a new label switching scheme" in INFOCOM, 2000.
A. Bremler-Barr, Y. Afek and S. Har-Peled , "Routing with a Clue", in SIGCOMM, 1999. [ppt]
Y. Afek and A. Bremler, "Self-Stabilizing Unidirectional Network Algorithms by Power Supply", in SODA, 1997.