Defending against Contagious Attacks on a Network with Resource Reallocation

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. *Funded by the Science and Technology Development Fund, Macau SAR (File no. SKLIOTSC-2018-2020), the Start-up Research Grant of University of Macau (File no. SRG2020-00020- IOTSC). This work was supported in part by the Science and Technology Development Fund, Macau SAR under File no. 0060/2019/A1, and in part by Research Grant of University of Macau under Grant MYRG2018-00237-FST. † City University of Hong Kong Shenzhen Research Institute, Shenzhen, P. R. China. The work described in this paper was partially sponsored by Project 11771365 supported by NSFC. ‡ BNU-UIC Institute of Artificial Intelligence and Future Networks, Beijing Normal University (Zhuhai), Guangdong, China. The work was partially supported by Chinese National Research Fund (NSFC) Key Project No. 61532013; NSFC grant No. 61872239; and Guangdong Provincial Key Lab of AI and Multimodal Data Processing at BNU-HKBU UIC. Copyright © 2021, Association for the Advancement of Artificial Intelligence (www. aaai. org). All rights reserved.

Authors

• Rufan Bai Southeast University
• Haoxing Lin
• Xinyu Yang Nankai University
• Xiaowei Wu University of Macau
• Minming Li City University of Hong Kong
• Weijia Jia Institute of Artificial Intelligence and Future Networks, Beijing Normal University, Zhuhai BNU-UIC Institute of Artificial Intelligence and Future Networks, Beijing Normal University (Zhuhai), Guangdong Key Lab of AI and Multi-Modal Data Processing, BNU-HKBU United International College, Zhuhai, Guang Dong, PR China.

Keywords

No keywords are indexed for this paper.