This work presents a system and a multi-core architecture to defend from complexity attacks. The application of this system to mitigate the complexity attacks on the DPI engines is provided. We show 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 towards mitigating the attack, we have developed a variant of AC algorithm that improves the worst case performance (under an attack). Still, its running-time under normal traffic is worse than classical AC implementations. To overcome this problem, we take advantage of a multi-core architecture. We introduce MCA^2 —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 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 complexity attacks.