Research On Modeling And Solving Method Of Attack-Defense Adversarial Game Based On Network Structure

Attack-defense adversarial problems have emerged as a long-term and critical issue in military and security fields.In reality,a broad array of adversarial and competitive domains can be modeled by attack-defense adversarial games,including counter-terrorism,the protection of public infrastructures,interdiction of the illegal good smuggling,and so on.Many attack-defense adversarial problems occur in the network-structured domains.The activities of both attacker and defender are related to the network structure,and the competitive and adversarial interactions between them also occur on the network.There are many key problems and challenges to be solved in such network-structured scenarios,including the impact of goal thresholds on game models,uncertainty and probability in attack-defense adversarial 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.Focusing on network-structured domains,we adopt the Stackelberg leader–follower game framework to model and simulate the adversarial interactions between the attacker and the defender,to provide effective resource allocation strategies against potential attacker threats.This thesis provides the models and approaches for several important network-structured adversarial domains with limited resources and uncertainties.The main innovations and contributions of the thesis are represented as follows:(1)We proposed a modeling framework for the Network Attack-Defense Adversarial Game.We firstly expounded the definition of network attack-defense adversarial game from the perspective of network flow.Based on Stackelberg game,we provided the basic framework of network attack-defense adversarial game,including two representations of arc form and path form;then based on the minimax theorem in game theory,we proved the existence and universality of the strong Stackelberg equilibrium in the new game framework,which is used as the core solution concept to solve large-scale network problems.(2)We considered a novel variant of shortest path network interdiction with goal threshold,and proposed algorithms to solve the novel threshold game model and its special cases.Considering cases where interdiction resources are vital and expensive,the optimization of resource allocation must be taken into account.However,known frameworks can hardly address the case where the goal of interdiction is restricted to a specified level.Therefore,based on the Stackelberg network attack-defense adversarial game framework,we proposed an alternative threshold model to balance the utility maximization and the resource consumption.The new threshold model is NP-hard,thus two basic algorithms are proposed based on Benders decomposition and Lagrange duality,respectively.Based on the two basic algorithms,two special cases of complete interdiction and large threshold dominance are further considered,and the corresponding Set Covering algorithm and Lagrange Slack algorithm are given.(3)We proposed a novel stochastic extension of the threshold game model and develop a decomposition based solution framework.The adversarial nature in attack-defense interactions leads to various uncertainties,such as the outcome of a a particular interdiction action.By integrating the uncertainty of interdiction actions into the threshold game model proposed above,the deterministic interdiction model is transformed into a stochastic model.We introduced a decomposition algorithm framework base on mastersub problem iterations,and reformulated the problem as a bi-level mixed-integer problem to help solve the new NP-hard problem.To enhance the efficiency and scalability of the basic decomposition approach,a master problem acceleration algorithm based on dual subgraphs and a better attacker response algorithm based on local search procedure are designed.The enhanced decomposition algorithm framework provides a feasible solution method for solving the attack-defense adversarial game problem of realistic scale.(4)We proposed a novel probabilistic network evasion interdiction model and develop a double oracle algorithm framework.The strategy given by the above models is a deterministic conservative strategy.Based on the research of maximizing reliable path,we proposed a novel model of probabilistic evasion interdiction problems.To solve the new evasion game model,we introduced the solution framework of double oracle,and illustrated the NP-hard complexity of defender and attacker from the reduction of the set covering problem and the 3-SAT problem,respectively.We further enhanced the double oracle algorithm with better response oracle replacement.Based on the submodule characteristics of the defender's resource allocation,we proposed a defender's greedy better response heuristic algorithm;and based on variable neighborhood search procedure,we proposed an attacker's heuristic better response oracle.The convergence of double oracle is guaranteed by minimax theorem,while subproblems can be further accelerated by appropriate optimization methods.Thus we believe that the double oracle approach is a suitable solution framework to solve large-scale network evasion interdiction problem.(5)We validated of the scalability of proposed models and algorithms with real world road networks.Numerical experiments on networks of different sizes and attributes were used to illustrate and validate the proposed algorithms.Furthermore,we performed tests on larger-scale real-world road networks to demonstrate the scalability of our game models and algorithms.The algorithms can provide an order of magnitude acceleration,which extend the application to the real world network domains.In this dissertation,we focus on the application of attack-defense adversarial games in network-structured domains.Many critical challenges and issues exist in those networkstructured scenarios.We adopt the Stackelberg leader-follower game framework to model network attack-defense adversarial games.Considering the impact of scarcity of resources and uncertainty of interdiction actions,more specific and realistic game models are constructed.For different models,we design various innovative techniques based on decomposition and iteration to improve the scalability and robustness of solution algorithms.Experimental results show that the models and algorithms proposed in this dissertation can solve the network problems of real world scale,and thus can provide satisfactory resource allocation strategies for real world network attack-defense adversarial game problems.