James Kelly
Algorithmic complexity attacks seek to specifically invoke an algorithm's worst-case behaviour. In this presentation we will focus on summarizing the content of two papers showcasing these attacks. Crosby and Wallach originally shed light on these attacks in their 2003 paper (Denial of Service via Algorithmic Complexity Attacks) which gives numerous examples of hash table and associative array vulnerabilities. We'll examine their exploits of Perl associative arrays and the Bro intrusion detection system. Gal et al. expand on this style of attack giving some new examples and making the case for a solution through a paradigm shift to focus on algorithms' worst-case complexity as much as the average-case. We present the concept of this paradigm shift and some other possible solutions along with their advantages and disadvantages.