Jiefu Zheng

September 2013
Stochastic Network Interdiction Games
Committee Members: Advisor: David Castañon, SE/ECE; Pirooz Vakili, SE/ME; Bobak Nazer, SE/ECE; Ioannis Paschalidis, SE/ECE; Appointed Chair: Michael Caramanis, SE/ME

Abstract: Network interdiction problems consist of games between an attacker and an intelligent network, where the attacker seeks to degrade network operations while the network adapts its operations to counteract the effects of the attacker. This problem has received significant attention in recent years due to its relevance to military problems and network security. When the attacker’s actions achieve uncertain effects, the resulting problems become stochastic network interdiction problems. In this thesis, we develop new algorithms for the solution of different classes of stochastic network interdiction problems.

We first focus on static network interdiction games where the attacker attacks the network once, which will change the network with certain probability, to minimize the expected maximum flow from a given source to its destination. We develop a new solution algorithm, based on parsimonious integration of branch and bound techniques with increasingly accurate lower bounds. Our method obtains solutions significantly faster than previous approaches in the literature.

In the second part, we study a multi-stage interdiction problem where the attacker can attack the network multiple times, and observe the outcomes of its past attacks before selecting a current attack. For this dynamic game, we use a model-predictive approach based on a lower bound approximation. We develop a new set of performance bounds and extend the single stage approach to multiple stages. Our new algorithm is showed faster than other available methods.

Last we study the nested information game between an attacker and a network, where the attacker has partial information about the network, i.e., the initial distribution of availability of arcs. The attacker makes several attacks and observes the flows on the network. These observations will update the attacker’s knowledge of the network and will be used in selecting the next attack actions. The defender can either send flow on an existing arc or refrain from using it to deceive the attacker. For these problems, we develop a faster algorithm, which decomposes this game into a sequence of subgames and solves them to get the equilibrium strategies. As numerical example showed, our method can handle large problems which other methods fail to solve.