A Tale of Frozen Clouds: Quantifying the Impact of Algorithmic Complexity Vulnerabilities in Popular Web Servers

Algorithmic complexity vulnerabilities are a class of security problems that enables attackers to trigger the worst-case complexity of certain algorithms. Such vulnerabilities can be leveraged to deploy low-volume, asymmetric, CPU-based denial-of-service (DoS) attacks. Previous work speculates that these vulnerabilities are more dangerous in certain web servers, like Node.js, than in traditional ones, like Apache. We believe it is of utmost importance to understand if this is indeed the case or if there are ways to compensate against such problems using various deployment strategies. To this end, we study the resilience of popular web servers against CPU-based DoS attacks in four major cloud platforms under realistic deployment conditions. We find that there are indeed significant differences in how various web servers react to an attack. However, our results suggest a more nuanced landscape than previously believed: while event-based systems tend to recover faster from DoS in certain scenarios, they also suffer the worst performance degradation overall. Nevertheless, in some setups, Apache performs worse than event-based systems, and there are cloud platforms in which all the considered servers are seriously exposed to the attack. We also find that developers can harden their servers against CPU-based DoS attacks by increasing the number of server instances running in parallel. This, in turn, can lead to an increased cost of operation or a slight degradation of performance in non-DoS conditions.