# Defending against Contagious Attacks on a Network with Resource Reallocation

arXiv: https://arxiv.org/abs/2012.01036 · HTML: https://mlsanity.com/paper/2012.01036/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Dec 2020.

## Built on by (most cited first, 2 of 2)

- [Mixed Strategies for Security Games with General Defending Requirements](https://mlsanity.com/paper/2204.12158/) (2022)
- [Security Decisions for Cyber-Physical Systems based on Solving Critical Node Problems with Vulnerable Nodes](https://mlsanity.com/paper/2406.10287/) (2024)

## Abstract (arXiv)

In classic network security games, the defender distributes defending resources to the nodes of the network, and the attacker attacks a node, with the objective to maximize the damage caused. Existing models assume that the attack at node u causes damage only at u. However, in many real-world security scenarios, the attack at a node u spreads to the neighbors of u and can cause damage at multiple nodes, e.g., for the outbreak of a virus. In this paper, we consider the network defending problem against contagious attacks. Existing works that study shared resources assume that the resource allocated to a node can be shared or duplicated between neighboring nodes. However, in real world, sharing resource naturally leads to a decrease in defending power of the source node, especially when defending against contagious attacks. To this end, we study the model in which resources allocated to a node can only be transferred to its neighboring nodes, which we refer to as a reallocation process. We show that this more general model is difficult in two aspects: (1) even for a fixed allocation of resources, we show that computing the optimal reallocation is NP-hard; (2) for the case when reallocation is not allowed, we show that computing the optimal allocation (against contagious attack) is also NP-hard. For positive results, we give a mixed integer linear program formulation for the problem and a bi-criteria approximation algorithm. Our experimental results demonstrate that the allocation and reallocation strategies our algorithm computes perform well in terms of minimizing the damage due to contagious attacks.