Complexity DDoS Prevention with Multicore Processors

By sending just a few carefully crafted packets, an attacker could launch an algorithmic complexity denial of service attack on a Deep Packet Inspection (DPI) engine. Such engines are at the core of security devices, thus, they expose a weakness in the first line of defense of enterprise networks and clouds. We present a system and a multi-core architecture to defend from these algorithmic complexity attacks, and discuss the integration of this system with three popular DPI engines. The vulnerability of the first engine 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 a multi-core architecture for mitigating 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.

This work was published in IEEE HPSR 2011, ACM/IEEE ANCS 2012, IEEE/ACM Transactions on Networking (Preprint 2016)