2012/04/27 by Julien M. Hendrickx, Karl Henrik Johansson, Hendrickx, Julien M. +7 · 3 citations
Computer Science · Engineering · #FOS: Electrical engineering #FOS: Mathematics #Infrastructure Resilience and Vulnerability Analysis #Network Security and Intrusion Detection #Optimization and Control (math.OC) #Security and Verification in Computing #Smart Grid Security and Resilience #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.1204.6174
openalex publication_date 2012/04/27 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28
The resilience of Supervisory Control and Data Acquisition (SCADA) systems\nfor electric power networks for certain cyber-attacks is considered. We analyze\nthe vulnerability of the measurement system to false data attack on\ncommunicated measurements. The vulnerability analysis problem is shown to be\nNP-hard, meaning that unless P = NP there is no polynomial time algorithm to\nanalyze the vulnerability of the system. Nevertheless, we identify situations,\nsuch as the full measurement case, where it can be solved efficiently. In such\ncases, we show indeed that the problem can be cast as a generalization of the\nminimum cut problem involving costly nodes. We further show that it can be\nreformulated as a standard minimum cut problem (without costly nodes) on a\nmodified graph of proportional size. An important consequence of this result is\nthat our approach provides the first exact efficient algorithm for the\nvulnerability analysis problem under the full measurement assumption.\nFurthermore, our approach also provides an efficient heuristic algorithm for\nthe general NP-hard problem. Our results are illustrated by numerical studies\non benchmark systems including the IEEE 118-bus system.\n