Resource-Limited Network Security Games with General Contagious Attacks

In classic security games on the graph with contagious attacks, there is a defender and an attacker. The defender first distributes defending resources to the nodes of the graph, and each unit of defending resource incurs a cost. The attacker picks a node to attack to maximize the damage after the transmission of the attack. Generally, the attacker has two attack types—uniform attack and adaptive attack, where the uniform attacker attacks each node with uniform and the adaptive attacker can select one node to attack according to the defender’s strategy. The usual objective in the literature is to minimize the total loss of the defender, including the damage caused by the attacker and the paid cost. However, we notice that in many real-world applications, the defending resources are often limited, and the existing objective fails to capture these scenarios. The paper handles this issue by considering the resource-limited setting of the security game, where there is a given upper bound on the paid resource cost and the defender aims to minimize the caused damage without violating the resource cost constraint. We first discuss the hardness, proving that for both attack types, the problem is NP-hard on general graphs. Then, we focus on bounded treewidth graphs, a well-known graph class that includes many common graphs. We show that given any graph with bounded treewidth and any attack type, a dynamic programming algorithm always exists that solves the problem in polynomial time. Further, the algorithm can be easily extended to more general objective settings. The proposed algorithm is built on an interesting connection to a graph partition problem, which could be intrigued independently.