Joint Cyber and Physical Attacks on Power Grids: Graph Theoretical Approaches for Information Recovery

• Main Authors: Soltan, Saleh, Yannakakis, Mihalis, Zussman, Gil
• Format: Conference Proceeding
• Language: English
• ISSN: 0163-5999
• DOI: 10.1145/2796314.2745846

Recent events demonstrated the vulnerability of power grids to cyber attacks and to physical attacks. Therefore, we focus on joint cyber and physical attacks and develop methods to retrieve the grid state information following such an attack. We consider a model in which an adversary attacks a zone by physically disconnecting some of its power lines and blocking the information flow from the zone to the grid's control center. We use tools from linear algebra and graph theory and leverage the properties of the power flow DC approximation to develop methods for information recovery. Using information observed outside the attacked zone, these methods recover information about the disconnected lines and the phase angles at the buses. We identify sufficient conditions on the zone structure and constraints on the attack characteristics such that these methods can recover the information. We also show that it is NP-hard to find an approximate solution to the problem of partitioning the power grid into the minimum number of attack-resilient zones. However, since power grids can often be represented by planar graphs, we develop a constant approximation partitioning algorithm for these graphs. Finally, we numerically study the relationships between the grid's resilience and its structural properties, and demonstrate the partitioning algorithm on real power grids. The results can provide insights into the design of a secure control network for the smart grid.