Transcription
Fundamental Limits of Cyber-Physical Security in Smart Power GridsYue Zhao, Andrea Goldsmith, and H. Vincent PoorAbstract— Cyber-physical security of power systems underpower injection attacks that alter generation and loads isstudied. The system operator employs Phasor MeasurementUnits (PMUs) for detecting such attacks, while attackers deviseattacks that are unobservable by such PMU networks. Forthe NP-hard problem of finding the sparsest unobservableattacks, it is shown that the solution has a simple form withprobability one, namely, min κ(G M ), M 1, where κ(G M )is the vertex connectivity of an augmented graph, and Mis the number of PMUs. The constructive proof allows oneto find the entire set of the sparsest unobservable attacks inpolynomial time. Furthermore, the geometric interpretation ofunobservable attacks leads to a natural characterization oftheir potential impacts. With optimized PMU deployment, thesparsest unobservable attacks and their potential impact asfunctions of the number of PMUs are evaluated numerically forIEEE 30, 57, 118, 300-bus systems and Polish 2383, 2737, 3012bus systems. It is observed that, as more PMUs are added, themaximum potential impact among all the sparsest unobservableattacks drops quickly until it reaches the minimum sparsity.I. I NTRODUCTIONModern power networks are increasingly dependent oninformation technology in order to achieve higher efficiency,flexibility and adaptability. The development of more advanced sensing, communications and control capabilities forpower grids enables better situational awareness and smartercontrol. However, security issues also arise as more complexinformation systems become prominent targets of cyberphysical attacks: not only can there be data attacks onmeasurements that disrupt situation awareness [1], but alsocontrol signals of many power grid components includinggeneration and loads can be hijacked, directly leading tophysical misbehavior of power systems [2]. Therefore, toachieve reliable and secure operation of a smart power grid,it is essential for the system operator to minimize (if noteliminate) the feasibility and impact of such cyber-physicalattacks.Recently, there has been considerable research concerningdata injection attacks on sensor measurements, particularlyfrom supervisory control and data acquisition (SCADA)systems. A common and important goal among these worksThis research was supported in part by the DTRA under Grant HDTRA108-1-0010, in part by the Air Force Office of Scientific Research underMURI Grant FA9550-09-1-0643, and in part by the Office of Naval Researchunder Grant N00014-12-1-0767.Y. Zhao is with the Dept. of Electrical Engineering, Princeton University, Princeton, NJ, 08544 USA, and with the Dept. of ElectricalEngineering, Stanford University, Stanford, CA, 94305 USA (e-mail:yuez@princeton.edu).A. Goldsmith is with the Dept. of Electrical Engineering, StanfordUniversity, Stanford, CA 94305 USA (e-mail: andrea@stanford.edu).H. V. Poor is with the Dept. of Electrical Engineering, Princeton University, Princeton, NJ 08544 USA (e-mail: poor@princeton.edu).is to pursue the integrity of network state estimation, thatis, to successfully detect the injected data attack and recoverthe correct system states. The feasibility of constructing falsedata injection attacks to pass bad data detection schemes andalter estimated system states was first shown in [1]. There, anatural question arises as to how to find the sparsest unobservable data injection attack, as sparsity is used to model thecomplexity of an attack, as well as the resources needed foran attacker to implement it. However, finding such an optimalattack requires solving an NP-hard l0 minimization problem.While efficiently finding the sparsest unobservable attacks ingeneral remains an open problem, many interesting solutionsunder special problem settings have been developed (see, e.g.[3] and [4]). Furthermore, as PMUs become increasinglydeployed in power systems, network situational awarenessfor grid operators is significantly improved compared tousing legacy SCADA systems only. However, the high installation costs of PMUs still prohibit large-scale deployment.Thus, the problem of how to economically deploy PMUsto best facilitate the state estimator to detect data injectionattacks becomes an interesting problem that many studieshave addressed (see, e.g. [5] and [6] among others.)Compared to data attacks that target state estimators,cyber-physical attacks that directly disrupt power networkphysical processes can have a much faster (and oftenstronger) impact on power grids. In addition to physicalattacks implemented by hacking control signals or directlyintruding upon grid components, several types of load altering attacks have been shown to be practically implementablevia Internet-based message attacks [2]. Topological attacksare another type of physical attack which have been considered in [7]. Furthermore, there have been studies of dynamicpower injection attacks [8], [9].In this paper, we investigate a general type of cyberphysical attacks in power systems, namely, power injectionattacks that alter generation and loads in the network. Weconsider a grid operator that employs PMUs to (partially)monitor the network for detecting power injection attacks.Since power injection attacks disrupt the power system statesimmediately, the timeliness of PMU measurement feedbackis essential. We study the open l0 minimization problemof finding the sparsest unobservable attacks given any setof PMU locations. We prove that this in general NP-hardproblem has a simple solution with probability one, namely, the sparsity of the optimal solution is min κ(G M ), M 1,where κ(G M ) is the vertex connectivity of an augmentedgraph of the original power network, and M is the numberof PMUs. Furthermore, the geometric interpretation of thesesparsest unobservable attacks leads to a natural characteri-
zation of their potential impact. Accordingly, among all thesparsest unobservable attacks, an attacker can easily find theone with the greatest potential impact. Finally, for all possiblenumbers of PMUs with optimized placement, we evaluate thesparsest unobservable attacks in terms of their sparsity andpotential impact in IEEE 30, 57, 118, 300-bus and Polish2383, 2737, 3012-bus systems.The remainder of the paper is organized as follows. InSection II, models of the power network, power injectionattacks and PMUs are established. We then formulate theminimum sparsity problem of unobservable attacks. In Section III, we prove that the minimum sparsity of unobservableattacks can be found in polynomial time with probabilityone. The potential impact of unobservable attacks is characterized based on a geometric interpretation. In Section IV,numerical evaluation of the sparsest unobservable attacks inIEEE benchmark test cases and Polish power systems areprovided. Conclusions are drawn in Section V. Due to spacelimitations, proof details (except for Theorem 2) are omittedhere, and can be found in [10].II. P ROBLEM FORMULATIONA. Power network modelWe consider a power network with N buses, and denotethe set of buses and the set of transmission lines by N {1, . . . , N } and L {1, . . . , L} respectively. For a line l L that connects buses n and m, denote its reactance by xl aswell as xnm , and define its incidence vector ml as follows: if i n, 1, 1, if i m,ml (i) 0,otherwise.Based on the power network topology and line reactances, weconstruct a weighted graph G {N , L, w} where the edgeweight wl , x1l , l 1, . . . , L. We employ the DC powerflow model in this paper, and the real power injections P RN and the voltageθ RN satisfy P Bθ,PL 1phase anglesTwhere B l 1 xl ml ml RN N is the Laplacian ofthe weighted graph G. Furthermore, the power flow on line1(θn θm ).l from bus n to bus m equals Pnm xnmWe consider attackers inflicting power injection attacksthat alter the generation and loads in the power network. Wedenote the power injections under normal conditions by P ,and denote a power injection attack by P RN . Thus thepost-attack power injections are P P .B. Sensor model and unobservable attacksWe consider the use of PMUs by the system operatorfor monitoring the power network in order to detect powerinjection attacks. With PMUs installed at the buses, weconsider the following two different sensor models:1) A PMU securely measures the voltage phasor of thebus at which it is installed.2) A PMU securely measures the voltage phasor of thebus at which it is installed, as well as the currentphasors on all the lines connected to this bus1 .We denote the set of buses with PMUs by M ( N ), and letM , M be the total number of PMUs, where · denotesthe cardinality of a set. We say that a power injection attack P is unobservable if it leads to zero changes in all thequantities measured by the PMUs. With the first PMU modeldescribed above, we have the following definition:Definition 1 (unobservability condition): An attack Pis unobservable if and only if θ, such that P B θ and θM 0,(1)where θM denotes the M 1 sub-vector of θ obtainedby keeping its M entries whose indices are in M.With the second PMU model described above, for anybus n N , it is immediate to verify that the following threeconditions are equivalent:1) There are no changes of the voltage phasor at n andof the current phasors on all the lines connected to n.2) There are no changes of the voltage phasor at n andof the power flows on all the lines connected to n.3) n′ N [n], there is no change of the voltage phasor atn′ , where N [n] is the closed neighborhood of n whichincludes n and its neighboring buses N (n).Thus, for forming unobservable attacks, the following twosituations are equivalent to the attacker: The system operator monitors the set of buses M withthe second PMU model; The system operator monitors the set of buses N [M]with the first PMU model,where N [M] is the closed neighborhood of M whichincludes all the buses in M and their neighboring busesN (M). Thus, the unobservability condition with the secondPMU model is obtained by replacing M with N [M] in (1).Without loss of generality (WLOG), we employ the firstPMU model in the following analysis, and all the resultscan be directly translated to the second PMU model.C. Sparsest unobservable attacksIn forming an unobservable attack, an attacker generallyhas two objectives: minimize execution complexity and maximize its impact on the grid. Note that these two objectives can be competing interests that are not simultaneouslyachievable. For an attack vector P , we use its zero normk P k0 to model its complexity. For minimizing attackcomplexity, an attacker is interested in finding the sparsestattacks that satisfy the unobservability condition (1):min k P k0(2) θs.t. P B θ, θM 0, θ 6 0.Equivalently, a more compact form of (2) is as follows:(2) min θMc 6 0kBN Mc θMc k0 ,(3)1 In practice, the second PMU measurement model is achieved by installing PMUs on all the lines connected to a bus.
Because of the non-convexity of the l0 norm, problem (3) isin general NP-hard. Instead of applying existing heuristics(e.g., l1 relaxation), in Section III, we will solve (3) byanalyzing the network topology and the structure of theLaplacian matrix B. We will then characterize the potentialimpact associated with unobservable attacks.III. S OLVING FOR THE SPARSEST UNOBSERVABLEATTACKSIn this section, we study the problem of finding the sparsest unobservable attacks given any set of PMUs M (cf. (3)).We first show an important role of the vertex connectivityof the grid in lower bounding the optimum of (3). Wethen derive an upper bound of (3). By further exploitingthe geometric insights behind the upper bound, we closethe gap between the lower and upper bounds, and providea complete solution to the minimum sparsity problem (3).Finally, we characterize the potential impact of unobservableattacks based on their geometric interpretations.A. The role of vertex connectivity in lower bounding thesparsity of unobservable attacksWe first make the following definitions:Definition 2 (Vertex cut): A vertex cut of a connectedgraph G is a set of vertices whose removal renders Gdisconnected.Definition 3 (Vertex connectivity): The vertex connectivity of a graph G, denoted by κ(G), is the size of the minimumvertex cut of G, i.e., it is the minimum number of verticesthat need to be removed to disconnect the remaining graph.We now state the following theorem.Theorem 1: For a connected power grid G {N , L, w},assume that the line reactances xl (l L) are independentcontinuous random variables strictly bounded away fromzero from below. M κ(G), for any set of buses M N , M M , in order to have θM 0, one of thefollowing must be true with probability one: There is no power injection attack at any bus in the grid,i.e., P 0; or There must be at least M 1 buses with non-zero powerinjections from an attack, i.e., k P k0 M 1.Theorem 1 provides a lower bound on the optimum of (3)which holds with probability one, i.e., no matter which setof M buses’ phase angles are monitored by PMUs, if M κ(G), there must be at least M 1 powerinjections in any non-zero unobservable attack; if M κ(G), there must be at least κ(G) 1 powerinjections in any non-zero unobservable attack.In sum, the minimum sparsity of unobservable attacks islower bounded almost surely by min (κ(G), M ) 1. We willsee in the following that while this lower bound is not alwaystight, a modification of it will render the optimum of (3).B. An upper bound on the minimum sparsity of unobservableattacksTo derive an upper bound on the minimum sparsity ofunobservable attacks, we exploit the fact that solving (3) isequivalent to finding the sparsest non-zero vector in the rangespace of BN Mc . We have the following theorem:Theorem 2: For a connected grid, the optimum of (3) isupper bounded by N (Mc ) 1( M 1), 1 M N 1.Proof: By re-indexing the buses, WLOG, i) let Mc {1, 2, . . . , N M }, and ii) let BN Mc have the followingpartition as depicted in Figure 1(a):1) The top submatrix BMc Mc is an (N M ) (N M )full-rank matrix.2) The middle submatrix (which will be shown to beBN (Mc )Mc ) consists of all the remaining rows eachof which has at least one non-zero entry.3) The bottom submatrix is an all-zero matrix.In particular, from the definition of the Laplacian, themiddle submatrix of BN Mc as described above is exactlyBN (Mc )Mc as its row indices correspond to those buses notin Mc but connected to at least one bus in Mc . Note thatthe middle and the bottom sub-matrices can be degenerate.Now, we let 1 θMc BMc Mc e1 ,(4)where e1 R(N M ) 1 is the natural basis [1, 0, . . . , 0]T .Then, we construct an attack vector P BN Mc θMc :it has a 1 at its index 1, and some possibly non-zero valuesat the indices that correspond to N (Mc ), but has zero valuesat all other indices. Thus,k P k0 N (Mc ) 1 M 1.(5)From Theorem 1 and 2, we have closed the gap betweenthe lower and upper bounds on the optimum of (3) for thecase of M κ(G), and proved that the optimum in this caseequals M 1. To further solve the case of M κ(G), wewould like to improve the upper bound N (Mc ) 1.We observe that, by selecting a subset of the columnsof BN Mc to form a new submatrix BN S , S Mc , andpartitioning BN S into three submatrices in the same wayas BN Mc is partitioned in Figure 1(a), it is possible thatthe resulting middle submatrix BN (S)S has fewer rows thanBN (Mc )Mc , leading to even sparser unobservable attackswith sparsity N (S) 1. By further developing this ideabased on the geometric insights behind the proof of Theorem2, we provide a complete solution of (3) next.C. Closing the gap between lower and upper bounds on theminimum sparsity of unobservable attacksWe start by providing a geometric interpretation of Theorem 2. As shown in Figure 1(a), if M\N (Mc ) 6 , allthe buses can be partitioned into three subsets Mc , N (Mc )and M\N (Mc ), corresponding to the row indices of thetop, middle and bottom submatrices of BN Mc respectively.Moreover, N (Mc ) is a vertex cut of G that separates Mcfrom M\N (Mc ). The N (Mc ) 1-sparse attack P (cf.(5)) is formed by injecting power at one of the buses amongMc (i.e., bus 1), and extracting power at and only at thebuses in the vertex cut N (Mc ), such that the phase anglechanges at M are all zero.
30N ( S2 )Minimum sparsity of unobservable attacksMaximum potential impact of 2 sparse attacksMaximum potential impact of 3 sparse attacksMaximum potential impact of 4 sparse attacksMaximum potential impact of 5 sparse attacksN [ S2 ]V2cNumber of buses under power injection attack25«V2BV2A«««««N [ S1 ]««V1BV1AN ( S1 )««15105.0Fig. 2. An illustration of two minimum vertex cuts with the same size butdifferent potential impacts.always cancel out the effects of anything that happens withinS on the measurements by the set of PMUs M ( N \S).From Corollary 1, by taking control of the buses in a cutN (S), an attacker is able to hide from the system operatora power injection attack with a zero norm as large as N [S] N (S) S ( N (S) 1).20(6)Accordingly, we define the potential impact of unobservableattacks as follows:Definition 5: For any vertex cut N (S) for some S Mc ,the potential impact of unobservable attacks by controllingpower injections at N (S) is N [S] .Employing Definition 5, we can differentiate the potentialimpacts of multiple sparsest unobservable attacks with thesame sparsity. In particular, multiple minimum vertex cutscan exist for the same augmented graph G M . Then, each ofthese cuts leads to a different sparsest unobservable attackof the same size (constructed by controlling the buses in thiscut as well as one other bus disconnected from M by it).However, different cuts may disconnect different portions ofthe network from M, leading to vastly different potentialimpacts of unobservable attacks. An illustration is depictedin Figure 2. In this example, two vertex cuts both of size two,N (S1 ) {V1A , V1B } and N (S2 ) {V2A , V2B }, are notedas enclosed by solid ovals. Accordingly, both cuts enable 3sparse unobservable attacks. However, their potential impactsare significantly different. Cut N (S2 ) only disconnects oneother bus, namely S2 {V2C } from the set of PMUs M, andhence its potential impact equals N [S2 ] 3; in comparison,cut N (S1 ) disconnects all the vertices above N (S1 ) fromM, and hence its potential impact equals N [S1 ] 3. Withthis definition of potential impact, it is then natural for anattacker to seek the sparsest unobservable attack with thegreatest potential impact.Finally, we conclude this section by noting the followingfact: the minimum sparsity and the potential impacts of12345Number of PMUs6789Fig. 3. Minimum sparsity of unobservable attacks and maximum potentialimpact of 2, 3, 4, 5-sparse attacks as functions of M ; IEEE 30-bus system.unobservable attacks are fully determined with probabilityone by the network topology and the locations of the PMUs.IV. N UMERICAL EVALUATIONIn this section, we evaluate the sparsest unobservableattacks and their potential impacts when the system operatordeploys PMUs at optimized locations. We have seen inSection III that the minimum sparsity and potential impactsof unobservable attacks are determined fully by the networktopology and the PMU placement. Unlike network states andnetwork parameters which can vary over short and mediumtime scales, the transmission network topology (or the set ofpossible topologies) typically stays the same over long timescales. The above motivates the system operator to optimizethe PMU placement according to the network topology. Forthe best performance in countering power injection attacks,the system operator wants to raise the minimum sparsityof unobservable attacks, as well as mitigate the maximumpotential impact of unobservable attacks. The geometricinterpretations of the sparsest unobservable attacks and theirpotential impacts allow us to develop an efficient PMUplacement algorithm for the system operator to pursue bothobjectives. The details of the algorithm are omitted here dueto space limitations, and can be found in [10].We evaluate our results in IEEE 30-bus, IEEE 57-bus,IEEE 118-bus, IEEE 300-bus, Polish 2383-bus, Polish 2737bus, and Polish 3012-bus systems. The evaluation is performed based on the software toolbox MATPOWER [11]. Ineach of these systems, we generate a set of PMUs basedon the developed placement algorithm, with the numberof PMUs increasing from one until all attacks becomeobservable. For all numbers of PMUs, the minimum sparsityof unobservable attacks as well as the maximum potentialimpact among the sparsest unobservable attacks are found.Specifically, the minimum sparsity of unobservable attacksand the maximum potential impact among these sparsest attacks both as functions of the number of PMUs M are plotted
16Minimum sparsity of unobservable attacksMaximum potential impact of 2 sparse attacksMaximum potential impact of 3 sparse attacksMaximum potential impact of 4 sparse attacksMaximum potential impact of 5 sparse attacksNumber of buses under power injection attack14121086420100200300400500600Number of PMUs700800900Fig. 4.Minimum sparsity of unobservable attacks and the maximumpotential impact of the sparsest attacks as functions of M ; Polish 3012bus system.for the IEEE 30-bus power system and the Polish 3012-bussystem in Figure 3 and 4 respectively. In addition, for theIEEE 30-bus system, the maximum potential impacts amongall 2-sparse, 3-sparse, 4-sparse and 5-sparse unobservableattacks for the entire range of M are plotted. (Note that theminimum sparsity of unobservable attacks does not exceed3 for all M .)We make the following observations which appear in allseven of the evaluated systems: In all seven systems, all the attacks become observablewith less than a third of the buses installed withPMUs (assuming the second PMU model). The averagepercentage of the number of PMUs needed to havefull network observability equals 31.1%. This numberresembles a well-known estimate of such percentage tobe one third [12]. The topologies of the tested power systems tend toallow sparse power injection attacks. In other words,the vertex connectivity of these power networks isoften small. Furthermore, there are often many tieswhen finding unobservable attacks with the minimumsparsity: this is why even after adding a lot more PMUsinto the network, with each addition eliminating theprevious sparsest attack, the minimum sparsity can stillremain the same. While there are many ties of unobservable attacks withthe same sparsity, the potential impacts among them canvary significantly. Moreover, as more PMUs are added,the maximum potential impact among all the sparsestunobservable attacks drops quickly until it reaches theminimum sparsity.V. C ONCLUSIONWe have studied cyber-physical attacks that alter powergeneration and loads in power networks while remainingunobservable under the surveillance of system operatorsusing PMUs. We have provided an explicit solution to theopen problem of finding the sparsest unobservable attacks;the minimum sparsityamong all unobservable attacks equals min κ(G M ), M 1. In deriving this minimum sparsity, alower bound on it based on the vertex connectivity of thenetwork was shown to hold with probability one. We havethen provided a constructive upper bound that successfullycloses the gap to the lower bound. This constructive upperbound enables us to find all the sparsest unobservable attacksin polynomial time by finding the minimum vertex cuts ofan augmented graph G M . As a result, min κ(G M ), M 1is a fundamental limit of this minimum sparsity that is notonly explicitly attainable, but also unbeatable by all possible unobservable attacks. We have further shown that thegeometric interpretation of the unobservable attacks allowsa natural characterization of their potential impacts. Withoptimized PMU deployment, we have evaluated the sparsestunobservable attacks and their potential impacts in IEEE 30,57, 118, 300-bus systems and Polish 2383, 2737, 3012-bussystems. Finally, while this work has studied a static systemmodel and power injection attacks, extension to dynamicsystems, measurements and power injection attacks remainsan interesting future direction, for which we expect thatsimilar insights on fundamental limits will apply.R EFERENCES[1] Y. Liu, P. Ning, and M. Reiter, “False data injection attacks againststate estimation in electric power grids,” ACM Transactions on Information and System Security, vol. 14, no. 1, Article 13, May 2011.[2] A.-H. Mohsenian-Rad and A. Leon-Garcia, “Distributed internet-basedload altering attacks against smart power grids,” IEEE Transactions onSmart Grid, vol. 2, no. 4, pp. 667–674, December 2011.[3] K. C. Sou, H. Sandberg, and K. H. Johansson, “On the exactsolution to a smart grid cyber-security analysis problem,” eprintarXiv:1201.5019v2.[4] J. Hendrickx, K. H. Johansson, R. Jungers, H. Sandberg, and K. C.Sou, “An exact solution to the power networks security index problemand its generalized min cut formulation,” eprint arXiv:1204.6174.[5] A. Giani, E. Bitar, M. Garcia, M. McQueen, P. Khargonekar, andK. Poolla, “Smart grid data integrity attacks: characterizations andcountermeasures,” Proc. of IEEE International Conference on SmartGrid Communications (SmartGridComm), pp. 232–237, October 2011.[6] T. T. Kim and H. V. Poor, “Strategic protection against data injectionattacks on power grids,” IEEE Transactions on Smart Grid, vol. 2,no. 2, pp. 326–333, June 2011.[7] J. Weimer, S. Kar, and K. H. Johansson, “Distributed detection andisolation of topology attacks in power networks,” Proc. of the 1st Int.Conf. on High Confidence Networked Systems, pp. 65–72, July 2012.[8] F. Pasqualetti, F. Dorfler, and F. Bullo, “Attack detection and identification in cyber-physical systems,” IEEE Transactions on AutomaticControl, to appear.[9] H. Fawzi, P. Tabuada, and S. Diggavi, “Secure estimation andcontrol for cyber-physical systems under adversarial attacks,” eprintarXiv:1205.5073.[10] Y. Zhao, A. Goldsmith, and H. V. Poor, “Fundamental limits ofcyber-physical security in smart power grids,” IEEE Transactionson Automatic Control, Special Issue on Control of Cyber-PhysicalSystems, 2013, under review.[11] R. D. Zimmerman, C. E. Murillo-Sanchez, and R. J. Thomas, “MATPOWER steady-state operations, planning and analysis tools for powersystems research and education,” IEEE Transactions on Power Systems, vol. 26, no. 1, pp. 12 – 19, Feb. 2011.[12] T. Baldwin, L. Mili, J. M.B. Boisen, and R. Adapa, “Power systemobservability with minimal phasor measurement placement,” IEEETransactions on Power Systems, vol. 8, no. 2, pp. 707–715, May 1993.
Fundamental Limits of Cyber -Ph ysical Security in Smart P ower Grids Y ue Zhao, Andrea Goldsmith, and H. V incent Poor . IN T R ODU C T ION Modern po wer netw orks are increasingly dependent on information technology in order to achie ve higher efcienc y, e xibility and adaptability . The de velopment of more ad-
