Defending on networks : applying game theory to prevent illegal activities in structured security domains
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 wa...
Saved in:
Main Author: | |
---|---|
Other Authors: | |
Format: | Thesis-Doctor of Philosophy |
Language: | English |
Published: |
Nanyang Technological University
2020
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/137024 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
Summary: | 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. |
---|