Optimizing the Maximum Vertex Coverage Attacks Under Knapsack Constraint

Only when we understand how hackers think, can we defend against their attacks. Towards this end, this paper studies the cyber-attacks that aim to remove nodes or links from network topologies. We particularly focus on one type of such attacks called Maximum Vertex Coverage Attacks under Knapsack constraint (MVCAK), in which a hacker has a fixed budget to remove nodes from a network with the nodes involving different costs for removal, and the hacker's goal is to maximize the number of links incident to the nodes removed. Since the MVCAK problem is NP-hard, we firstly propose an optimal solution by Integer Linear Program formulation. Secondly, we give an approximate solution by Linear Programming relaxation that achieves an approximation ratio of 3/4, outperforming the existing 1 - 1/sqrt(e) (about 0.39). Thirdly, since the straightforward implementation of our approximate solution has a high time complexity, we propose two heuristics to significantly reduce its complexity while preserving the approximation ratio. We formally prove the correctness and the effectiveness of these two heuristics. Finally, we conduct extensive experiments on both artificial and real-world networks, showing that our approximate solution produces almost the same results as the optimal solution in practice and has an acceptable running time.

I. Introduction

Infrastructure networks such as Internet backbone and power grids are essential for our everyday lives [2]. Unfortunately, they have become attractive targets for cyber-attacks because (1) they were typically not deployed with security as a major concern initially; (2) undermining them has an enormous impact; and (3) updating/patching them entirely is very difficult due to their large scales. As a result, cyber-attacks on them have occurred frequently in recent years [3]. For example, a DDoS attack on the Domain Name Service provider Dyn Inc. in 2016 made tens of millions of users worldwide lose Internet access for hours [4]; the ’WannaCry’ ransomware attack on UK’s NHS network in 2017 eventually infected about 230,000 computers in 150 countries [5].