Analyzing and improving the resistance of overlays against bandwidth exhaustion attacks

Private overlays, such as Virtual Private Networks (VPN), offer methods for a cheap and yet secure communication over the Internet. However, as our society becomes more and more dependent on it, these structures turn into vital targets for Denial-of-Service (DoS) attacks. As so-called botnets offer an inexpensive way to generate almost arbitrary amounts of traffic, the only effective measure that can be taken by overlay mechanisms is adapting the topology for minimal impact. This article presents novel metrics to estimate the impact of DoS attacks with different strengths. In particular random, greedy, and optimal attacks are considered, whereas for the optimal attacker we show that it involves NP-hard calculations. Based on the attacker models, several prerequisites for resilient overlay topologies, like a low constant node degree and high girth, are derived and validated by a simulation study.