The “Power” of Graph Theory: Modeling Weaknesses in the American Electric Grid
After the 2016 shutdown of the Ukrainian power grid by cyberattacks, security analysts and civilians alike wondered if something similar could occur in the US. While the high level of variability in computing systems and inconsistent availability of exploitable materials between power stations may protect the US from such a large scale cyberattack for the time being, more archaic methods of attack are still quite viable. According to a WSJ article covering an information release from a Federal Energy Regulatory Commission study, the American power grid is highly susceptible to physical attacks against certain key locations. To better understand the risks present in the American electric grid and to predict possible vulnerabilities, we can model it as a graph.
At the broadest level, the american electric grid can be represented as 3 weakly-connected nodes, one for each of the major regional power grids, which share only a limited number of connections.
If we take a naive approach, it may seem ideal to simply attack the weak edges between the 3 nodes, creating 3 components of the graph. However, if we unpack these sections further, we quickly discover that each component is perfectly capable of supporting its own power supply. Instead, we need to look for key substations within each of the regional grids. To identify these key substations, we can look for those nodes with low clustering coefficients and lots of edges that act as a hub for local bridges between distant parts of the graph. An additional criterion that may prove useful is to search for nodes whose edges have a low embeddedness. Since the FERC declined to release actual data on connections between critical substations, we can apply this searching technique to the following fictional graph of power substations.
We can start by ignoring nodes with relatively few edges (e<3), since a critical substation must be relied on by many other substations. Already, we can parse out lots of noise to start to see the key regions of the network.
We can dissect the network further by eliminating regions with either a low clustering coefficient or a low embededdness. For the purpose of this analysis, these two metrics should tell us relatively similar information: which substations are part of tightly knit networks (implying they are redundant and not likely targets), and which are not? With this new filter applied, we have a clear winner for the most likely target in our network of power substations, node E.
To double check our analysis, we can refer back to the original graph and check whether or not E acts a hub for local bridges. An easy way to check this is to remove node E from the graph (simulating an attack on the substation), and see how connected the graph remains.
Without node E, the once connected graph breaks down into 4 separate components. The real world implications of such a critical node being removed from the graph could range from a few hours without power in a local region to massive, long-term blackouts.
While the practical applications of graph theory may seem limited at first glance, in reality it provides us with powerful tools for the analysis of essential real-world systems. Techniques such as the ones outlined above were likely utilized in the FERC’s analysis of the American electric grid, and quite possibly played an important role in their identification of the serious security vulnerabilities present therein.
Links:
https://www.wsj.com/articles/u-s-risks-national-blackout-from-small-scale-attack-1394664965?tesla=y
http://www.businessinsider.com/power-grid-hacking-ukraine-2016-6