Graph Reliability in the Presence of an Adversary

Abstract

From ecological food webs to electrical power grids, networks are ubiquitous in the natural and man-made world. They often represent critical infrastructure making it vital to protect their proper functioning. As such, significant research has explored the reliability of graphs when subject to random failures. Far less research, however, has explored non-random graph reliability in the presence of adversary. In this work, we develop a new model that accounts for the presence of an adversary and related non-random failure, and incorporates the reality that the adversary is subject to some constraint (i.e. time, money, manpower). We discuss this with specific interest in modeling threats to electrical power grids.

Using methods including computer scripts to enumerate a large number of possible strategies, using empiric approaches based on the symmetry present in cycles and other graphs, and using the Karush-Kuhn-Tucker (KKT) conditions, we identified the optimal adversarial strategies for a range of specific graphs such as chordless cycles, chorded cycles, and complete graphs. Through subsequent analyses and proofs, we developed a conjecture that implies a complete, comprehensive optimal adversarial approach for any graph that would allow some understanding of the likely behavior of an adversary acting rationally. Finally, after making this conjecture, we proposed an additional iteration of the model that accounts for the severity of disconnection. Thus, we reflect the varying impacts of disconnections in regions within a graph, allowing a more detailed understanding of potential vulnerabilities and weaknesses in real-world networks.

Our model provides a foundation to characterize optimal approaches to adversarial attacks (vulnerabilities) which could allow better allocations of defensive resources, could better inform government offensive efforts when targeting enemy power grids, such as those operated by terrorist organizations, and allows consideration of the most efficiently protected networks designs when new grids are developed. While much work remains to expand this model for real-world applications, these results provide a solid foundation upon which to build.