Defending on networks : applying game theory to prevent illegal activities in structured security domains

• Main Author: Wang, Xinrun
• Other Authors: Bo An
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2020
• Subjects: Engineering::Computer science and engineering
• Online Access: https://hdl.handle.net/10356/137024
• Institution: Nanyang Technological University

The past decade witnesses the success of applying game theory to address security is- sues in domains such as protecting critical infrastructure and wildlife. However, the structured security domains such as interdicting illegal smuggling on networks, com- bating oil siphoning in international waters and preventing cyber attacks in cyber space are not well investigated. There are many critical challenges in these scenarios such as the scalability of the algorithm to solve realistic-sized problems, the long-term planning ability of the smugglers and the self-interested interdependent behaviors of users in cyber spaces. The previous works cannot be directly applied to solve these problems. Therefore, in this thesis, we provide models and solution approaches to several significant structured security domains. First, we focus on preventing nuclear smuggling on container shipping networks through efficient container inspection. To stop the nuclear smuggling through container shipping networks, the U.S. government launched several initiatives to deploy advanced devices and inspection facilities in ports around the world. However, it is a significant challenge for the government to efficiently allocate the limited inspection resources to combat the nuclear smuggling activities due to the large volume of the containers im- ported to the U.S.. To address this problem, we propose a novel Container Inspection Model (CIM) based on Stackelberg game where the inspector determines her strategy first and the smuggler follows a Markov Decision Process (MDP) to determine his strategy after observing the inspector’s strategy. Several important contributions are made to solve this problem including: i) a linear relaxation approximation which reformulates the problem into a bilinear optimization problem, ii) an algorithm based on the Multi- pleparametric Disaggregation Technique (MDT) to solve the bilinear program, and iii)an iterative algorithm to further improve the scalability. Extensive experiments show that our algorithms outperform existing methods in the scalability significantly and can obtain a solution better than baselines, even under various uncertainties. Second, we focus on preventing oil siphoning in international waters through efficient patrols. Pirate syndicates capturing tankers to siphon oil has become a serious security issue for maritime traffic. In response to the threat, coast guards and navies deploy patrol boats to protect international oil trade. However, given the vast area of the sea and the highly time and space dependent behaviors of both players, it remains a significant challenge to find efficient ways to deploy patrol resources. We provide four key contributions to address this challenge. First, we construct a Stackelberg model of the oil-siphoning problem; Second, we propose a compact formulation and a con- straint generation algorithm to compute efficient strategies of security agencies; Third, to further improve the scalability, we propose an abstraction method to solve extremely large-scale games; Finally, extensive simulations and a detailed case study demonstrate that our approach achieves a dramatic improvement of scalability with modest influence on the solution quality and can scale up to realistic-sized problems. Finally, we focus on preventing cyber attacks on interdependent users through government’s subsidy. Cybersecurity is becoming one of the most critical concerns to the modern society due to the recent cyber attacks. Therefore, governments around the world launch various initiatives to improve the companies’ investments to cybersecurity. However, the government has limited resources and needs to optimally allocate resources to companies. We introduce a game-theoretic model between the government, interdependent users (e.g., companies) and the cyber attacker. We investigate the three cases where the attacker can attack all, single and multiple users and propose a reverse convex formulation, an exact polynomial algorithm and a heuristic algorithm for the three cases, respectively. We extensively evaluate our model and algorithms on synthetic and real data. The results show that our model captures the interdependent behaviors of users and our heuristic algorithm converges efficiently under mild convergence criteria and outperforms the baselines with good robustness.