Strategic Security and Recovery on Interdependent Network

Modeling critical systems as networks has given rise to many insights about how to prioritize resource allocation for security (for preventing compromise or large-scale disaster events) and recovery in the rare, yet high-consequence, occurrence of catastrophic failure. Topological graph metrics such as betweenness centrality and clustering coefficient have been shown to approximate critical nodes in cascading failure and recovery scenarios on isolated networks. Most complex networks, however, do not exist in isolation, and often have noncooperative actors controlling interdependent subnetworks. This property motivates studying the impact of strategic interactions on networks representative of critical systems. In this dissertation, we examine strategic scenarios of security and recovery on interdependent networks, primarily applying tools from game theory and optimization.;We first investigate security on general interdependent networks, modelling the strategic interaction between defenders, who must protect potential targets in their subnetwork, and an attacker, who wishes to compromise the network, as a Stackelberg (leader-follower) game. Failure cascade models are used to describe the spread of attacks between nodes and, consequently, defenders. We extend traditional models of Stackelberg security games to support equilibria computation for multiple defenders. Since computing such equilibria is intractable for many large networks, we develop a heuristic using distributed optimization and a variant of iterated best response. Finally, we analyze equilibrium results on popular synthetic topologies and those found in real-world power grids, and compare the resulting strategies with common graph metrics for assessing security.;We then apply concepts from the above security framework to digital systems analysis in order to prioritize critical logic nodes in hardware designs for deeper analysis. To calculate probability of failure cascade in logic networks, we use a novel Fourier decomposition method to characterize how single bit failures in the input of a Boolean function affect the correctness of the output. This method is shown to apply to arbitrary distributions of Boolean functions, as well as categorize a Boolean network into either quiescent (dampens out bit flips on average) or chaotic (exponentially spreads the failure throughout the network). Equilibrium strategies from single defender Stackelberg security games are then used to provide a prioritization of critical nodes in academic testbench digital designs.;Finally, we explore decentralization of recovery on interdependent networks. Since computation time is so critical in disaster recovery scenarios, we analyze several game theoretic models for both the the quality of the solution, with respect to the corresponding centralized optimum, as well as time complexity for finding the Nash equilibrium. We then compare an iterated best response heuristic, and prove ?-Nash bounds on approximate solutions. Our model is run on several real-world interdependent utility networks, and results illustrate the tradeoff between slowly computing optimal recovery strategies and quickly computing near optimal strategies; network operators can use such tradeoff points to determine which model is more appropriate for a given scenario. Diving deeper into the recovery process, we also develop a percolation model to mimic the giant component formation and commodity deficit cost satisfaction of the centralized optimization process. We analyze this model on complete and synthetic networks, and discover the component formation and recovery cost curves closely resemble results from the more computationally intensive optimization method.