Eliminating Algorithmic Complexity Attacks

Assistant Professor Justine Sherry and Ph.D. students Nirav Atre and Hugo Sadok have developed an algorithm that could spell the end of one type of denial of service attack.

Research from Carnegie Mellon University's School of Computer Science and CyLab Institute for Security and Privacy could spell the end of a particularly menacing type of denial of service (DoS) attack.

Nirav Atre, a Ph.D. student in the Computer Science Department and a member of CyLab, has developed a new algorithm guaranteed to protect network systems against algorithmic complexity attacks (ACA), a type of DoS attack that requires fewer resources but can still overwhelm a system. In an ACA attack, a small amount of complex network traffic overloads a network, causing innocent traffic to be dropped. A recent ACA attack on Open vSwitch, an open-source system employed in many data center networks, caused more than ten thousand bits of innocent data to be dropped for every single bit of attack traffic.

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. This naturally prevents 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 limit on the amount of innocent traffic an attacker can cause to be dropped for each bit that they invest in the attack.

Read more about Atre's research on CyLab's website.

For More Information, Contact:

Aaron Aupperlee | 412-268-9068 | aaupperlee@cmu.edu