Eliminating algorithmic complexity attacks

Attackers constantly look to bog down and interrupt network systems through Denial-of-Service (DoS) attacks. DoS attacks aim to prevent innocent network users from accessing online services (such as a particular website or their email), often by overloading the network with so much data to process that they cannot keep up and are forced to drop innocent users’ requests.

Now, researchers at Carnegie Mellon University are making headway, discovering a new way to eliminate vulnerabilities exposed by algorithmic complexity attacks (ACAs), a particularly menacing type of DoS attack. Many DoS attacks require an attacker to be very powerful, controlling thousands of end hosts to generate a large amount of network traffic – the largest such attacks might involve terabits per second of data – in order to overload the victim system.

ACAs, on the other hand, can be triggered by a resource-strapped attacker who sends a small amount of complex network traffic, which nonetheless manages to overload the victim system and cause innocent traffic to be dropped. A recent attack on Open vSwitch, an open-source system employed in many datacenter networks, used an ACA to drop over ten thousand bits of innocent data for every single bit of attack traffic the attacker transmitted.

“ACAs have plagued networked systems for years,” says Justine Sherry, an assistant professor in CMU's School of Computer Science.

"Typically, developers have had to develop one-off patches for ACAs every time a new vulnerability is discovered.”

However, ACAs may be on their way to extinction thanks to a new approach to mitigating ACAs proposed by Nirav Atre, a Ph.D. student in CMU’s School of Computer Science and member of the CyLab Institute for Security and Privacy. Atre has developed a new algorithm guaranteed to protect network systems against these types of attacks.

Atre’s algorithm enables systems to make educated predictions about which network packets will be the most expensive or difficult to process. These packets are then moved to the back of the queue for service, while easy-to-process packets jump the line, naturally preventing an attacker’s complex traffic from overwhelming the system. If the system does become overloaded, it will drop the most time-consuming and labor-intensive packets, which are likely to include any attacks. Overall, this approach guarantees a mathematical upper-bound on the amount of innocent traffic an attacker can cause to be dropped for each bit that they invest into the attack.

We’re raising the bar for how powerful an attacker has to be to overpower the system.

Nirav Atre, Ph.D. Student, Carnegie Mellon School of Computer Science

Atre’s system, SurgeProtector, has already been deployed in practice as part of Pigasus, an open-sourced networked system for intrusion detection developed within CyLab. Prior to integrating SurgeProtector, Atre’s study reports, an attacker could use ACAs to slow down one of Pigasus’s components by 8.3 Gbps using only 0.3 Gbps of attack traffic. Now with SurgeProtector, an attacker must invest over 8 Gbps (a 27X higher bandwidth investment) to achieve the same slowdown.

Paper References

SurgeProtector: mitigating temporal algorithmic complexity attacks using adversarial scheduling

• Nirav Atre, Carnegie Mellon University
  Computer Science Department
• Hugo Sadok, Carnegie Mellon University
  Computer Science Department
• Erica Chiang, Carnegie Mellon University
  Computer Science Department
• Weina Wang, Carnegie Mellon University
  Computer Science Departmentt
• Justine Sherry, Carnegie Mellon University
  Computer Science Department

This study was presented at ACM SIGCOMM 2022 and is available on the conference’s website.