"Eliminating Algorithmic Complexity Attacks"

Malicious actors often use Denial-of-Service (DoS) attacks to slow down and disrupt network systems. Such attacks attempt to prevent network users from accessing online services by overloading the network with so much data to process that it cannot keep up and is forced to drop users' requests. Researchers at Carnegie Mellon University (CMU) have made significant progress in identifying a new method for eliminating vulnerabilities exposed by Algorithmic Complexity Attacks (ACAs), a particularly dangerous type of DoS attack. Many DoS attacks require a highly skilled attacker commanding thousands of end hosts to generate massive amounts of network traffic. The most significant of such attacks may involve terabits per second of data to overload the victim system. However, ACAs can be triggered by a resource-constrained attacker who sends a small amount of complex network traffic that overloads the victim system and causes traffic to be dropped. An ACA was recently used against Open vSwitch, an open-source system employed by many datacenter networks, to drop over ten thousand bits of innocent data for every bit of attack traffic transmitted by the attacker. According to Justine Sherry, an assistant professor in CMU's School of Computer Science, ACAs have plagued networked systems for years. Developers have had to create one-time patches for ACAs whenever a new vulnerability is discovered. Therefore, Nirav Atre, a Ph.D. student in CMU's School of Computer Science and member of the CyLab Institute for Security and Privacy, developed a new algorithm to protect network systems against ACAs. Atre's algorithm allows systems to make educated guesses about which network packets will be the most costly or difficult to process. These packets are then moved to the back of the service queue, while easy-to-process packets jump ahead, preventing an attacker's complex traffic from overwhelming the system. If the system becomes overloaded, it will discard the most time-consuming and labor-intensive packets, which are likely to contain any attacks. This article continues to discuss ACAs and the new algorithm developed to combat them. 

CyLab reports "Eliminating Algorithmic Complexity Attacks"