An efficient algorithm for network vulnerability analysis under malicious attacks

Given a communication network, we address the problem of computing a lower bound to the transmission rate between two network nodes notwithstanding the presence of an intelligent malicious attacker with limited destructive power. Formally, we are given a link capacitated network N with source node s and destination node t and a budget B for the attacker. We want to compute the Guaranteed Maximum Flow from s to t when an attacker can remove at most B edges. This problem is known to be NP-hard for general networks. For Internet-like networks we present an efficient ILP-based algorithm coupled with instance transformation techniques that allow us to solve the above problem for networks with more than 200 000 nodes and edges within a few minutes. To the best of our knowledge this is the first time that instances of this size for the above problem have been solved for Internet-like networks.