Combating adversaries in network-structured security domains

Game theoretic models of security, and associated computational methods, have emerged as critical components of security posture across a broad array of domains, including airport security and coast guard. However, the network-structured security domains capturing a variety of realistic problems such as preventing the illegal good smuggling, are not paid enough attentions. Many critical challenges and issues exist in those scenarios which, however, remain to be solved, including the cooperation among multiple adversaries, preventing adversarial flows on the network, and the planning and learning in repeated games. Although existing work on target-structured security domains has considered part of those issues, their methodologies fail to deal with the network structure, as the adversarial activity on the network is much more complex. This thesis provides the first models and approaches for several important network-structured security domains: 1) the interdiction of multiple cooperative adversaries connecting on the network from forming powerful coalitions, 2) the interdiction of an adversarial network flow, and 3) the online policy for combating the repeated attacks on the network. First, to address the issue of cooperation among attackers, we introduce a novel coalitional security game (CSG) model. A CSG consists of a set of attackers connected by a (communication or trust) network who can form coalitions as connected subgraphs of this network so as to attack a collection of targets. A defender in a CSG can delete a set of edges, incurring a cost for deleting each edge, with the goal of optimally limiting the attackers' ability to form effective coalitions (in terms of successfully attacking high value targets). We first show that a CSG is, in general, hard to approximate. Nevertheless, we develop a novel branch and price algorithm, leveraging a combination of column generation, relaxation, greedy approximation, and stabilization methods to enable scalable high-quality approximations of CSG solutions on realistic problem instances. Second, focusing on the challenging task of optimally interdicting an illegal network flow, we make several contributions. We propose a new Stackelberg game model for network flow interdiction. To solve this game, we provide a novel Column and Constraint Generation approach for computing the optimal defender strategy. We conduct extensive complexity analysis of the column generation subproblem. We propose compact convex nonlinear programs for solving the subproblems. Novel greedy and heuristic approaches for subproblems with good approximation guarantee are also incorporated. With these novel approaches, our approach can obtain a robust enough solution outperforming the existing methods and heuristic baselines significantly and scale up to realistic-sized problems according to extensive experimental evaluation. Finally, we study repeated network interdiction games with no prior knowledge of the adversary and the environment. We provide the first defender strategy, that enjoys nice theoretical and practical performance guarantees, by applying the adversarial online learning approach. In particular, we model the repeated network interdiction game with no prior knowledge as an online linear optimization problem, for which a novel and efficient online learning algorithm, SBGA, is proposed, which exploits the unique semi-bandit feedback in network security domains. We prove that SBGA achieves sublinear regret against adaptive adversary, compared with both the best fixed strategy on hindsight and a near optimal adaptive strategy. Extensive experiments also show that SBGA significantly outperforms existing approaches with fast convergence rate.Doctor of Philosophy (IGS