Review on Energy Resilience

Electrical Power and Energy Systems 82 (2016) 29–36

Contents lists available at ScienceDirect

Electrical Power and Energy Systems

journal homepage: www.elsevier.com/locate/ijepes

A game theory approach to vulnerability analysis: Integrating power flows with topological analysis

http://dx.doi.org/10.1016/j.ijepes.2016.02.045 0142-0615/� 2016 Elsevier Ltd. All rights reserved.

⇑ Corresponding author. E-mail addresses: [email protected] (M.X. Cheng), [email protected] (M. Crow),

[email protected] (Q. Ye).

Maggie X. Cheng a,⇑, Mariesa Crow b, Quanmin Ye c a Department of Computer Science, Missouri University of Science and Technology, Rolla, MO 65409, United States b Department of Electrical and Computer Engineering at Missouri University of Science and Technology, Rolla, MO 65409, United States c Nokia Networks, Mountain View, CA 94043, United States

a r t i c l e i n f o a b s t r a c t

Article history: Received 10 July 2014 Received in revised form 24 December 2015 Accepted 25 February 2016 Available online 17 March 2016

Keywords: Vulnerability analysis Topological analysis Power flow Instability Game theory Linear programming

This paper presents a new framework for vulnerability analysis. Under this framework, we can identify the vulnerable components and the critical components of a power grid. Distinct from previous work, our model considers the interaction between the components of the power system, and models the dynamic evolving process of cascading failures. The impact of a component failure on the system is dynamically changing as the failure propagates. We analyze the vulnerability of a power grid using an optimization model based on game theory, and use linear programming method to solve it. Since insta- bility is the reason of power outage, we use an instability index to measure the negative impact to the system. The results from this optimization problem suggest which component of the system is critical since its failure can most negatively impact the cyber-physical system.

� 2016 Elsevier Ltd. All rights reserved.

Introduction

The electrical power grid nowadays is well connected. As the grid connectivity increases, we will have fewer power outages since the high demand in one region can be satisfied by not only the local generation, but also remote generation from other regions. However, connectivity is a double-edged sword—multiple independent small-scale power outages may be mitigated, fewer but larger-scale power outage is more likely to happen. Large- scale power outage is typically the consequence of cascading failures propagated through a power system. To avoid cascading failure, it is important to identify the critical points or critical lines in the power system and protect them from failure. As the physical system is coupled with the cyber system, additional threats are introduced. Our job is not only to protect the grid from natural fail- ure but also adversarial attacks. This is the scope of vulnerability analysis.

To take preventive action against potential attacks, it is impor- tant to identify the vulnerability as early as possible so that grid operator can enhance the security and robustness of those identified components. In this paper, we present an analytical

framework to identify the security holes of a power grid. It is ana- lytical in the sense it identifies the most vulnerable and the most critical components of the system without deliberately probing the system to discover its weaknesses. Previous work on power grid vulnerability analysis is mainly on the SCADA system [1,2], and/or based on attack graphs or attack trees ([3,4], etc.). The pro- posed method uses a different approach for network vulnerability analysis and can be extended beyond the SCADA system to con- sider the control and monitoring devices and communication links in a smart grid.

To show the cascading failure propagation in a power grid, we study a simple six-bus three-machine system in Fig. 1. Suppose instantaneous high load at bus 2 causes power oscillation at bus 2. If transient instability cannot be dampened timely and it may cause power outage in this area. This ‘‘fault” may be propagated to bus 3 and the extra load may also cause system instability in that area. If the instability is high and it can continue to increase the power flow in more lines and faults may propagate through the whole power grid and cause large-scale power outage. The more the power grid is connected, the more vulnerable it is. An iso- lated area can only have small scale power outage, but will have it more often; a highly connected power grid will have fewer but larger power outage.

To identify the component that is prone to failure is important since failure of one component may cause chain reaction of more

G1

G2

G4

L2

L3

L6

L5

1

2

3 4

5

6

0.443+j0.112

0.433+j0.220

0.2+j0.1

0.3+j0.1 0.433+j0.217

0.4+j0.15

0.4+j0.1

Fig. 1. A six-bus three-machine system.

G1

B6

B1

B5

B4

B3

B2

G2

G4

L6

L2

L3

L5

Fig. 2. The flow network model for the system in Fig. 1.

30 M.X. Cheng et al. / Electrical Power and Energy Systems 82 (2016) 29–36

components, and therefore the robustness or reliability of the vul- nerable component should be improved. On the other hand, to identify the component whose failure can cause the largest degree of damage to the system is also very important in a security con- text since the hacker would target at such components to attack. The identification of the vulnerable components and the critical components help the grid operator in long term planning. The operator can reconfigure the generators, power lines or enhance security protection of some components to keep the grid in a reli- able and secure state.

A purely topological approach that is based on the metrics of network connectivity alone will not do a satisfactory job in power grid vulnerability analysis [5–8]. The reason is that power flow dynamics is not considered, and the interaction between different components of the system is not considered. The cascading propa- gation of failure cannot be captured in such a model. Due to the heterogeneity in load distribution and source capacity, a more sophisticated method is needed than the purely topological approach.

Bompard et al. [9] extended the purely topological approaches to consider the real power flow allocation and line flow limits in transmission grids, and introduced a new metrics called ‘‘net- ability”—the ability of the transmission grid to function properly under normal operating conditions. In [9] critical components are identified according to the relative drop in net-ability caused by the failure of each component. As we will show later, the method in [9] is what we called ‘‘Static Analysis” in this paper by using a different metrics from our work.

The key idea of this paper that distinguishes itself from previous work is to consider the evolving process of system instability after component failure. System vulnerability is quantified in terms of the cost to the power system, which is related to system instability. When system instability is low, power oscillation caused by load disturbance can be quickly stabilized and no further damage will occur; when system instability is high, power oscillation cannot be dampened timely, so it may cause the tripping of a power line. The tripping of a power line will cause power oscillation in other areas so the chain reaction will continue.

The scope of this paper does not include the countermeasures of potential attacks; it only identifies the vulnerable components and the critical components. It is up to the grid operator to decide what to do with the result of vulnerability analysis. Countermeasure or protection is the next step after vulnerability analysis.

Graph model

We can use a multi-source multi-sink flow network to repre- sent a power grid as follows: source nodes represent generators, denoted by set G; sink nodes represent loads, denoted by set L; and intermediate nodes represent buses, denoted by set B. Directed edges are added from generators to buses and from buses to loads; bidirectional edges are added between buses to represent the physical connectivity among them. Let E be the set of bidirectional edges connecting buses. A directed edge from a generator to a bus or from a bus to a load has no capacity limit, and therefore the edge has capacity set to 1. Such edges are not subject to failure. A bidi- rectional edge between two buses represents the power line with a capacity limit, and therefore we set the edge capacity cði; jÞ ¼ T�ij in both directions, 8ði; jÞ 2 E. If the power flow Si;j exceeds T�ij, the line will trip off.

The graph model for the example in Fig. 1 is shown in Fig. 2. If the subgraph induced by the bus nodes is fully connected (i.e.,

there is a path from every node to every other nodes), then every source node has a connected path to every sink node. When there are multiple sources available, a load may be satisfied by drawing power from multiple sources. Intuitively, every sink node would draw power from its nearest (in terms of impedance) source node. If the nearest source cannot satisfy its demand, then the second nearest, and so on. This is because the nearest source has the low- est impedance on the power line; it is also because if there is increase in demand, the power supply can ramp up quickly if it is near the sink node so that the power oscillation can be quickly stabilized.

To compute the power flow on power lines with given load con- dition, we can formulate the problem as a flow network problem. When computing the power flow, we ignore the capacity con- straint since the real power flow does not change its path because of the capacity limit of the power line. The problem can be cast as an optimization problem with the constraints that (1) flow conser- vation is satisfied, (2) the total load demand is satisfied, and (3) the AC version of Ohm’s Law is approximately satisfied.

Let fði; jÞ denote the power flow from bus i to bus j; hi denote the phase on bus i; Xi;j the reactance of the power line between bus i and bus j. We define the cost of a power line as the absolute error of the power flow solution:

costði; jÞ ¼ jhi � hj � Xi;jfði; jÞj; 8ði; jÞ 2 E Then the optimization problem is to find a power flow solution that minimizes the total cost. Xij is given as input; h and fði; jÞ are vari- ables whose values will be solved from the linear program.

Let Nv denote the neighbors of node v connected by undirected edges, N�v denote the neighbors of v connected by out-edges of v, and Nþv denote the neighbors of v connected by in-edges of v. For a power system with n generators (sources) and m loads (sinks), the linear program is given as follows:

M.X. Cheng et al. / Electrical Power and Energy Systems 82 (2016) 29–36 31

Minimize

X ði;jÞ2E

costði; jÞ ð0Þ

Subject to

X u2Nþ

i

fðu; iÞ ¼ Li; 8i ¼ 1 . . . m ð0 - aÞ

X v2N�j

fðj;vÞ ¼ Gj; 8j ¼ 1 . . . n ð0 - bÞ

Gj 6 Gmaxj ; 8j ¼ 1 . . . n ð0 - cÞX u2Nþ

j

fðu; jÞ ¼ X v2N�j

fðj;vÞ þ X k2Nj

fðj; kÞ; 8 j 2 B ð0 - dÞ

�ði; jÞ ¼ hi � hj � Xi;jfði; jÞ; 8ði; jÞ 2 E ð0 - eÞ fði; jÞ ¼ �fðj; iÞ; 8ði; jÞ 2 E ð0 - fÞ costði; jÞ P �ði; jÞ; 8ði; jÞ 2 E ð0 - gÞ costði; jÞ P ��ði; jÞ; 8ði; jÞ 2 E ð0-hÞ

The constraint (0-a) specifies that all demands are satisfied, and (0-b) specifies that all power flow provided to the system is equal to the total generation; (0-c) imposed a maximum generation from a generator; (0-d) states power flows in and out of a bus satisfy flow conservation; (0-e) defines the error of the power flow solu- tion; (0-g) and (0-h) define the cost as the absolute value of error �. The objective function is to minimize the total cost of the power flow solution.

The above linear model is an approximation of the AC model, but it has the advantage of simplicity. It is different from the linear approximation model proposed by Verma [10], which maximizes the throughput (the amount of total demand). Our model mini- mizes the estimation error while delivering the demanded power flow from generators. Although more accurate load-flow methods such as Newton–Raphson method are available to compute the power flow solution, they are in general more complicated. Accu- rate load-flow calculation is not the interest of this paper. Since the scope of this paper is on vulnerability analysis, we try to demonstrate what difference a new vulnerability analysis method can make no matter what load-flow method is used to calculate the power flow solution. The comparison of different vulnerability analysis methods will be based on the same power flow solution. Should the Newton–Raphson method be used to compute power flows, the vulnerability analysis method proposed in Section ‘‘Vulnerability analysis based on power flow dynamics” still applies, as shown in Section ‘‘Test validation”.

Vulnerability analysis based on power flow dynamics

The objective of vulnerability analysis is to provide a quantita- tive measure of system instability, and to identify the vulnerable components that are prone to failure and the critical components whose failure can bring a high cost to the power system [11–13]. A static analysis can be done in one sweep by using the given load and generation configuration, but if the grid operator is actively adjusting his strategy to defend the power grid and the attacker is actively adjusting his strategy to maximize his chance to bring down the system, the defender and the attacker are engaged in a game in which one party aims to maximize a cost function while the other party tries to minimize the same cost function. We will first layout the solution for static analysis, which serves as a build- ing block for the game theory analysis.

Static analysis

What is considered as a cost to the power system is disturbance to the normal operation. To identify the critical components and the vulnerable components, we need to have quantitative mea- sures of disturbance. We first quantify the degree of disturbance by using a cost function. This cost function is different from the indices defined in previous work [11–13].

Every line ði; jÞ in the power system has a security limit, S�ij, which is also called the soft limit. The security margin is the dis- tance between the current operating point and the security limit. Ideally, we would like to have a large security margin. There is also a threshold value T�ij > S

� ij, also known as the hard limit. It is desired

that power system operates below the security limit. If the power flow Sij exceeds the security limit, the system instability increases and a small increase in load may cause some line flow to go beyond its threshold. If the power flow exceeds T�ij, the breaker on the line will open to protect the line, then the line will trip. After the line has tripped, power flow will redistribute and then another line may exceed its threshold and trip, and the fault may continue to propagate.

In Fig. 1, for the given load, the power flows on the lines are all below their security limits. However if the load on bus 2 is increased by 0:2 þ j0:1, the power flow on line ð1; 2Þ will exceeds S�12; if the load on bus 3 is increased by 0:2 þ j0:1, the power flows on lines ð2; 3Þ and ð3; 4Þ will both exceed their security limits, leav- ing no security margins.

Operating the power system with zero security margin is dan- gerous and potentially it can cause fault propagation. The system instability index is then defined to be:

I ¼ X ði;jÞ

maxfSij � S�ij; 0g ð1Þ

Remarks:

(1) If all power lines operate below their security limits, the instability index is zero; if some line goes beyond the secu- rity limit, there is a positive penalty Sij � S�ij added into the instability index. The power grid operator would try to min- imize the system instability index.

(2) In Eq. (1), the maximum value for Sij is T � ij, since if the flow

exceeds the threshold, the line will trip so the maximum penalty for line ði; jÞ is T�ij � S�ij.

The most vulnerable line is the one that has the smallest secu- rity margin

argmin ði;jÞ

ðS�ij � SijÞ; if I ¼ 0

or the one that exceeds the security limit by a farthest distance,

argmax ði;jÞ

ðSij � S�ijÞ; if I > 0

However Sij depends on the load on the system. We will have to confine the load configuration to a few representative cases.

Let IB denote the system instability index for the base case with- out disturbance on the load. Let IDP denote the system instability index when DP amount of load is added into the system. Increasing the load by DP at different locations can cause different degrees of disturbance to the system. We use IDP;i to denote the index calcu- lated when the load at bus i is increased by DP, then

IDP ¼ max i

fIDP;ig ð2Þ

Also notice that when the load is low, adding a DP amount of load will not necessarily cause system instability to increase; However

32 M.X. Cheng et al. / Electrical Power and Energy Systems 82 (2016) 29–36

when the system is already under a high load, adding a DP amount of load will more likely to cause dramatic increase in instability. Therefore it is meaningful to study the system behavior at the peak load. The peak load value can be obtained from historical data. Fig. 3 shows that load oscillates between a low value and a high value with some noises. The expected value at the peak load will be used as the base case. The maximum deviation (instead of the standard deviation) from the expected value is used as DP.

The most critical line is the one whose failure will cause a max- imum degree of disturbance to the system. After a component fail- ure, the system is more prone to fault when the load increases. To measure the system’s sensitivity to increasing load, we define the following metrics, called sensitivity index:

S ¼ IDP � IB DP

ð3Þ

We compare S before and after the component failure. The compo- nent that causes the maximum increase in S is identified as the most critical component. Let Sj represent the sensitivity index after the jth component is taken out of service, and S represents the one with all components in service. Then the change in the sensitivity index is given as:

DSj ¼ Sj � S ð4Þ and the most critical line is given by

jcritical ¼ argmax j

fDSjg ð5Þ

D

line 1

x1=0 x1=1

S1

0.9S+0.1S1

S2

Game-theoretic analysis

Game theory has been used in smart grids for many purposes, such as microgrid systems, demand-side management, and com- munications [14]. It has been used in [15] to minimize communi- cation delay in multiple-hop power line communication when a group of smart meters send data to the common control center. It has also been used in [16] for partition of power grids into dis- joint micro-grid coalitions so that each coalition consists of both supply and demand. In [16] a game theoretic method is used to minimize a utility function that captures the total losses over the distribution power lines. In [17], noncooperative games are used to study the trading strategies of plug-in hybrid electric vehicles (PHEV) seeking to sell stored energy in a power market.

Despite the rich research activities in smart grids, the physical vulnerability of the power grid has never been addressed in a game theory framework. In this paper, we use game theoretic approach to decide the strategies of the attacker and the defender for resource allocation.

When malicious attacks are possible, the defender will try to allocate his resource to protect the critical components so that the system instability index is low. The attacker, with a limited capacity to launch attacks, would also adjust his strategy accord-

Time

L o a d

Fig. 3. Approximate load distribution in a day.

ingly. Initially, the attacker would guess the strategy used by the defender and make the first move. The defender, aiming at mini- mizing system instability, would allocate his resource to protect the most critical components. The attacker, aiming at causing as much power outage as possible, would adjust which components to attack with the objective of maximizing the system instability. Then the defender chooses which components to protect based on what the attacker has chosen and the attacker adjusts its strat- egy based on the decision of the opposite side. This iterative pro- cess continues until both sides reach an equilibrium or a specific stopping criteria is met. When the iteration stops, the results sug- gest the critical components to attack since their failure can cause maximum disruption of the system.

The attacker-defender game can be graphically illustrated in Fig. 4. Using the 6-bus system as an example, we assume the attacker can attack one line at a time, and the defender can make a decision whether to protect a line or not. If the payoff is u for the attacker, it is �u for the defender, so the attacker tries to max- imize u, and the defender tries to minimize u. For the simplicity of drawing the graph, we show xi as a dichotomy decision variable: xi ¼ 1 indicates that the defender decides to defend line i, and xi ¼ 0 otherwise. The actual game used in Section ‘‘Game-theoretic analysis” uses a continuous variable xi such that

P ixi ¼ 1 and

0 6 xi 6 1, where xi indicates the percentage of defender’s resource used for defending line i. Suppose when line j is attacked, the prob- ability to mitigate the attack is 90% when the defender decides to defend the line, then the payoff u ¼ 0:9S þ 0:1Sj, where S is the sen- sitivity index when no line is down, and Sj is the sensitivity index when line j is down. Using the load data in Fig. 1, when all power lines are in service, the value of the sensitivity index is S ¼ 0:0927. When line j is removed, values of Sj are provided in Table 1. If the defender is to make a dichotomy decision, the most critical line that needs to be protected is between bus 1 and bus 6, whose fail- ure will cause the most disturbance to the system sensitivity index.

We discuss the game-theoretic model with the assumption that the attacker can attack one component at a time, and the defender can allocate his resource to protect multiple components. In the following, we demonstrate our model by using a simple example: given a power grid with n power lines, the attacker chooses one of the n power lines to attack, the defender allocate resource to the n power lines subject to a total budget constraint.

Probability pij is the probability of thwarting the attack when the attacker chooses to attack line j while the defender chooses

A

line 7

x7=1

x7=0

0.9S+0.1S2

S7

0.9S+0.1S7

.

.

.

Fig. 4. A game theory graph model for the 6-bus system in Fig. 1. ‘‘A” denotes attacker, ‘‘D” denotes defender.

Table 1 The sensitivity index and payoff for the attacker.

Sj u From bus To bus

1.5019 0.23362 1 2 1.6236 0.24579 2 3 1.9618 0.27961 3 4 2.0463 0.28806 4 5 1.0519 0.18862 5 6 3.2157 0.40500 1 6 0.3553 0.11896 2 5

M.X. Cheng et al. / Electrical Power and Energy Systems 82 (2016) 29–36 33

to protect line i with 100% of resource. pjj is given as input based on how difficult it is to protect line j. Let xi be the proportion of resource allocated to protect line i, so

P ixi ¼ 1. If the defender

chooses a moving target defense strategy, xi can also be understood as the probability that the defender will defend line i. Let yj be the probability that the attacker will attack line j, so

P jyj ¼ 1.

Let C1 be the cost to the system when the attack is thwarted so no line is out of service; C2j be the cost to the system when the defender fails to thwart the attack, so line j is taken out of service. To relate the costs to system transient instability index, we set C1 ¼ S and C2j ¼ Sj.

The objective function is defined as follows:

Z ¼ Xn j¼1

1 � X i

xipij

! C2j þ

X i

xipijC1

! yj ð6Þ

Obviously pij ¼ 0 when i – j. Thus P

ixipij ¼ xjpjj is the actual prob- ability of thwarting the attack on line j under the resource alloca- tion. So the objective function becomes

Z ¼ Xn j¼1

ðð1 � xjpjjÞC2j þ xjpjjC1Þyj ð7Þ

If the attacker has a fixed target, i.e., always attack the same line, then yj is a 0–1 variable, then

Z ¼ max j

fð1 � xjpjjÞC2j þ xjpjjC1g ð8Þ

Otherwise, yj is a real-valued variable between 0 and 1. In this paper we address the general strategy in which the attacker can attack one component at a time but can change the target to attack for each attempt. The vector y = y1; y2; . . . ; yn reveals the best strategy to use for the maximum benefit of the attacker: with probability y1, it should attack line 1, with probability y2, it should attack line 2, and so on.

The attacker would like to maximize Z when x = x1; x2; . . . ; xn is known; the defender would like to minimize Z when y = y1; y2; . . . ; yn is known. We can formulate a minimization linear program for the defender and a maximization linear program for the attacker. The program can start from the attacker: use an initial guess of x, solve vector y, and then the result is fed into the defen- der’s game. The defender uses y as input, solve the minimization problem to get x, and then the result from the minimization pro- gram is fed into the maximization program. When the iterative algorithm terminates, either because the two opponents have reached equilibrium at the objective function Z, or a specific crite- ria has been met, then the values in x suggest the best strategy for the defender, and the values in y suggest the best strategy for the attacker.

The iterative approach seems appealing since each party can use the knowledge of the other party’s strategy to improve his own strategy. However, when an equilibrium is reached, neither the defender nor the attacker should ever need to know the strat- egy of the other party to adjust his own. This is because the linear programs solved by the attacker and the defender are duals of each

other: the attacker tries to maximize his minimum winning no matter what strategy the defender uses, and the defender tries to minimize the maximum damage to the system no matter what strategy the attacker uses. From the strong duality theory, the opti- mal solutions of both programs are the same:

max fy:eT y¼1g

min fx:eT x¼1g

Z ¼ min fx:eT x¼1g

max fy:eT y¼1g

Z ð9Þ

The equilibrium state can be computed without using itera- tions. The optimal solution for either program can be computed by solving a two-player zero-sum problem. Let M be the payoff matrix between the defender and the attacker. Mði; jÞ denotes the cost when defender chooses to defend line i and attacker chooses to attack line j, therefore

Mði; jÞ ¼ ð1 � pjjÞC2j þ pjjC1; if i ¼ j C2j; if i – j

�

Take the defender’s game for example. The objective is to min- imize the maximum winning of the attacker no matter what strat- egy is used by the attacker. We can formulate the defender’s game as follows:

Minimize

maxZ ð10Þ Subject toX

i

xi ¼ 1; ð11aÞ

xjðð1 � pjjÞC2j þ pjjC1Þ þ X i:i–j

xiC2j 6 maxZ; 8j ð11bÞ

Since it is a linear program with n variables, it can be solved in Oðn3Þ time. The solution to the linear program is a vector of fxig, which indicates how much effort the defender should be used to protect a component. The component with the maximum xi is the most critical.

Discussion

Complexity and scalability The proposed game-theoretic analysis framework in Section ‘‘G

ame-theoretic analysis” serves as a modeling method to find the most critical component. However, solving the linear program is in the order of Oðn3Þ for n variables. For very large power systems, direct application of the method is not going to scale well.

To improve the scalability of the method for very large systems, the grid topology can be divided into regions. We can use the pro- posed scheme to conduct vulnerability analysis on two tiers: the first tier is on the power lines connecting different regions, and the second tier is on the power lines inside of a region.

For the first tier analysis, each region is condensed into one node in the graph, and the loads and generations inside the region are replaced by the net difference of them. Using the same model- ing method, we can find out which transmission line is the most critical, whose failure can incur the highest cost to the system. The cost is measured by the sensitivity index computed from all inter-region power lines.

For the second tier analysis, we can zoom-in one region and condense other regions. When we analyze region i, we keep the full details of region i with all loads and generations, as well as all power lines, but we condense other regions and only keep the inter-region power lines. This will significantly reduce the number of variables. The critical line inside a region is identified as the one whose failure will cause the largest increase in system sensitivity index, which is computed over all lines inside region i and all inter-region lines.

34 M.X. Cheng et al. / Electrical Power and Energy Systems 82 (2016) 29–36

If the total number of power lines in the system is n, consisting of ni power lines inside of each region and m power lines between regions, i.e., n ¼ m þ Pini, then the first tier analysis is in the order of Oðm3Þ, and the second tier analysis is in the order of Oðn3i Þ for each region. If n � ni, and n � m, the hierarchical analysis will scale much better.

Extension from attacks on power lines Although the optimization model defined in linear program

(10),(11a),(11b) is for identifying the most critical power line, the game theory model has broader application than power lines. To consider other components in the power grid, the payoff for the attacker will be defined as the cost to the system when that com- ponent is removed or is malfunctioning. For instance, to consider which generator has the most critical role in the system, we can calculate the sensitivity index when the generator is removed from service. Using the same game theory analysis, we can obtain the values of fxig for all generators. The index iH ¼ argmaxixi indicates the generator iH needs to be protected. Other components, such as transformers, can be analyzed using the same analysis.

For other control and monitoring components, although the game theory model still applies, the real challenge comes from the difficulty in quantifying the cost to the system when the com- ponent is not functioning. Similarly, when a communication line or a communication equipment is attacked, the cost to the power sys- tem is not simply a change in power flows, as it impacts the state estimator, controllers, and many others.

Pure topological analysis

Vulnerability analysis in the past has been purely based on the grid structure without considering the power flow dynamics. In this section we show some of them, and in the next section we show the differences between the solutions generated by the pro- posed approach and these topological approaches.

For a given power grid, we can first build the connectivity graph G ¼ ðV; EÞ, where the vertex set V is the set of buses and the edge set E is the set of power lines. We first need a preprocessing proce- dure to ‘‘clean up” the graph. Since some buses have generators attached to it, some have loads on it, and some have both genera- tion and load on it, we need to label a bus either as a source node or a sink node. If a bus i has both generation and load, we calculate the net value Gi � Li as the difference between generation and load; if the difference is positive, then we make bus i a source node; otherwise, label it as a sink node.

The pure topological analysis method addresses this problem as a network partition problem and it studies the community struc- ture, or the clustering structure, of the network. The commonly used approach is to iteratively remove edges from the network until the network is partitioned into clusters. Then the edges that connect different clusters are critical links.

To determine the order that edges are removed, it uses the con- cept of ‘‘betweenness” [18]. Intuitively, we are looking for the edges that are most ‘‘between” other vertices, i.e., these edges are responsible for connecting many pairs of others. Therefore, when we remove these edge the network will most likely split into disconnected communities. These edges are called inter- community edges and the remaining edges are called intra- community edges.

There are several different betweenness measures. We will use two betweenness measures, the Random Walk Betweenness and the Shortest Path Betweenness, to go through the partition proce- dure. The first edge removed is the one that has the highest betweenness value, and is considered the most critical line in the power grid.

Random walk betweenness

Given an undirected graph G, a random walk starts from a speci- fic starting point s and will eventually end at a specific destination t; At each step it randomly makes a decision to move to a neighbor- ing vertex. The decision is uniformly random. For instance, if the walker is at position v, and there are jNvj neighbors, then each neighbor will be selected with probability 1=jNvj. We want to know how often on average random walks starting at vertex s will pass through a particular edge ðv; wÞ (from v to w or from w to v) before finding their way to the destination vertex t. The probability of using edge ðv; wÞ is the betweenness of edge ðv; wÞ.

To calculate the betweenness of edge ðv; wÞ, we first calculate the probability of the random walk visiting vertex v and w respec- tively. If the probability of visiting v is Vv and the probability of vis- iting w is Vw, then the probability of using edge ðv; wÞ is Ptðv; wÞ ¼ jVv � Vwj; which is the absolute difference between two probabilities. The algorithm to find the individual vertex probability is described as follows [18]: we first calculate the adjacent matrix A of G, and the diagonal matrix D of A, which is obtained by setting the diagonal elements as follows:

Dii ¼ X j

Aij; 8i

Since vertex t is an absorbing state, once the walker reaches t, the random walk stops. We remove the tth row and the tth column from matrix A to get At; similarly, remove the tth row and the tth column fromt D to get Dt. Then the probability vector V is calcu- lated as follows:

V ¼ ðDt � AtÞ�1 � S; where S is the source vector, in which Si ¼ 1 if node i is a source node; and Si ¼ 0 otherwise.

For one specific sink node t, assuming the sink node draws one unit of power flow, then the betweenness of edge ðv; wÞ is: betwtðv; wÞ ¼ Ptðv; wÞ

To apply the above algorithm in a power grid with several sink nodes with different load demands, we run the random walk for each sink node t (i.e., for each load). If load t demands Lt units of power flow, then the total betweenness of an edge ðv; wÞ is the weighted sum of the probabilities from each run:

betwðv; wÞ ¼ X t

Ptðv; wÞ � Lt

Shortest path betweenness

When using the Shortest Path Betweenness as a measure, we consider how much flow an edge carries from sources to sinks, assuming all flows take the shortest paths from source nodes to sink nodes. The edge that carries the most flow is the most critical one since its failure will disturb the normal operation to the largest degree.

For each sink node t, we first build a shortest-path tree rooted at t, and assign one unit of flow to each source. The edges are directed towards the sink node t. When the flows move from source nodes to t, flow conservation propert is preserved at relay nodes. If f tðv; wÞ amount of flow is carried on edge ðv; wÞ for sink t, then the betweenness of edge ðv; wÞ is the weighted sum from all sink nodes using loads as weights:

betwðv; wÞ ¼ X t

f tðv; wÞ � Lt

1 .5

M.X. Cheng et al. / Electrical Power and Energy Systems 82 (2016) 29–36 35

For both betweenness measures, the most critical line is identi- fied as:

ðv�; w�Þ ¼ argmax ðv;wÞ

fbetwðv; wÞg

0 .0

0 .5

1 .0

Lines

S j

0 10 20 30

Fig. 6. The sensitivity index of the power lines in the IEEE 30-bus system.

Table 2 Critical lines selected by different analysis methods.

Methods Load 1 Load 2 Load 3

Shortest path betweenness (2,5) (4,12) (4,12) Random walk betweenness (4,12) (27,28) (4,12) Static analysis (15,23) (27,29) (4,12) Game theory, all pjj ¼ 0:9 (15,23) (27,29) (4,12) Game theory, all pjj ¼ 0:8 (15,23) (27,29) (4,12) Game theory, all pjj ¼ 0:7 (15,23) (27,29) (4,12) Game theory, mix 40-30-30 (15,23) (27,29) (4,12) Game theory, mix 20-40-40 (15,23) (27,29) (4,12)

Test validation

The vulnerability analysis uses hypothetical attack scenarios and subsequent disturbance to the system to find out critical com- ponents. Due to the fact that the real-world power grid has not gone through all the failure scenarios, such data can only be obtained from simulation. The IEEE 30-bus test system is used to provide the power grid topology as well as load and generation data. The load bus data is from the table A.2 of [19], and the trans- mission line data is from the table A.4 of [19]. The IEEE 30-bus test system graph is given in Fig. 5.

In the first simulation, we evaluate if a dichotomy decision is to be made by the defender, which line is the most critical to protect, as the failure of this line will cause the maximum disturbance to the system. The power flows are computed by using the New- ton–Raphson method. The picture in Fig. 6 shows that the line between bus 2 and bus 5 is the most critical because its Sj value is the maximum. If the defender has the same probability to miti- gate the attack no matter which line is attacked (i.e., pjj is the same for all j), attacking the line with the maximum Sj also gives the maximum payoff for the attacker.

In the second simulation, we still use the IEEE 30-bus system as the test system to compare the two pure topological approaches and the proposed topology-power integrated approaches. We use three different load settings, and identify the most critical line under each load. For the proposed approach, we use a non- dichotomy decision for the defender. We assume 0 6 xi 6 1, andP

ixi ¼ 1.

Fig. 5. IEEE 30-bus test system.

In Table 2, ‘‘mix 40-30-30” is for having 40% nodes with pij ¼ 0:9, 30% nodes with pij ¼ 0:8, and 30% nodes with pij ¼ 0:7; and ‘‘mix 20-40-40” is for 20%, 40%, and 40% respectively. The Shortest Path Betweenness approach identified the power line between bus 2 and bus 5 as the most critical line under Load 1, and the power line between bus 4 and bus 12 as the most critical line under Load 2 and Load 3. Similarly, the Random Walk Betweenness approach has identified the power line between bus 4 and bus 12 as the most critical line under Load 1 and Load 3, and so on. The observation is that the proposed approach is more sensitive to load change. For three load configurations, both the static analysis and the game theory analysis yield different results for different load settings. The pure topological approaches are less sensitive to load change, since they are largely dependent on the topology structure of the power grid. The weighted versions play up the role of loads, but they still have no instability analysis in them.

In addition, we also tested with Load 2 using a different set of pjj: {0.83, 0.85, 0.89, 0.37, 0.69, 0.82, 0.95, 0.90, 0.92, 0.91, 0.90, 0.92, 0.95, 0.58, 0.98, 0.13, 0.19, 0.96, 0.18, 0.75, 0.82, 0.95, 0.07, 0.02, 0.94, 0.25, 0.95, 0.95, 0.89, 0.89, 0.81, 0.52, 0.78, 0.93, 0.93, 0.12, 0.86, 0.15, 0.93, 0.95, 0.95}. In this test, only the dynamic method using the game theory approach changes with pjj, others do not—the two pure topological approaches and the static analy- sis approach still identified the same line as the most critical line, while the game theory approach has changed from (27,29) to (27,30).

From the tests, the observation is that the topology-power inte- grated approach is more sensitive to load change than the pure topological approach, and the game theory approach also responds to the defender capacity better than the static approach.

36 M.X. Cheng et al. / Electrical Power and Energy Systems 82 (2016) 29–36

Conclusion

This paper addresses how to identify the vulnerable and the critical components of a smart grid. The proposed method quanti- fies vulnerability as a cost to the power system, and considers power flow dynamics and interaction of different components in the cost function. The critical components are identified using opti- mization techniques in a game theory framework. The method is superior to the conventional ‘‘cut” approach that only considers the network topology and ignores the roles of the components in the system.

Acknowledgment

This research work is supported in part by US National Science Foundation under Grants ECCS-1307458, CNS-1537538, CNS- 1545063, and CMMI-1551448. Dr. Crow is supported by multiple NSF – United States and DOE – United States grants.

References

[1] Ten C-W, Liu C-C, Manimaran G. Vulnerability assessment of cybersecurity for scada systems using attack trees. In: Power engineering society general meeting; 24–28 June 2007. p. 1–8.

[2] Ten C-W, Liu C-C, Manimaran G. Vulnerability assessment of cybersecurity for scada systems. IEEE Trans Power Syst 2008;23(4):1836–46.

[3] Vu H, Khaw K, Chen T, Kuo F-C. A new approach for network vulnerability analysis. In: Local computer networks; October 2008. p. 200–6.

[4] Maggi P, Pozza D, Sisto R. Vulnerability modelling for the analysis of network attacks. In: Dependability of computer systems; June 2008. p. 15–22.

[5] Bompard E, Wu D, Xue F. Structural vulnerability of power systems: a topological approach. Electr Power Syst Res 2011;81(July):1334–40.

[6] Xu L et al. Topologic analysis on effect of uhv long connections on energy transmittability of power grid. Eur Trans Electr Power 2011;21:465–74.

[7] Hines P, Cotilla-Sanchez E, Blumsack S. Do topological models provide good information about electricity infrastructure vulnerability? Chaos 2010;20:033 122:1–22:5.

[8] Bompard E, Pons E, Wu D. Analysis of the structural vulnerability of the interconnected power grid of continental Europe with the integrated power system and unified power system based on extended topological approach. Eur Trans Electr Power 2012.

[9] Bompard E, Napoli R, Xue F. Analysis of structural vulnerabilities in power transmission grids. Int J Crit Infrastruct Protect 2009;2(May):5–12.

[10] Verma A. Power grid security analysis: an optimization approach. Ph.D. dissertation, Columbia University; 2009.

[11] Song H, Kezunovic M. Static analysis of vulnerability and security margin of the power system. In: Transmission and distribution conference and exhibition. IEEE PES; 2006. p. 147–52.

[12] Setreus J. Identifying critical components for system reliability in power transmission systems. Ph.D. dissertation, Electrical Systems, KTH Royal Institute of Technology, Sweden; 2011.

[13] Haidar AMA, Mohamed A, Hussain A. Power system vulnerability assessment considering a new index based on power system loss. In: International conference on energy and environment (ICEE 2006); 2006.

[14] Saad W, Han Z, Poor H, Basar T. Game-theoretic methods for the smart grid: an overview of microgrid systems, demand-side management, and smart grid communications. IEEE Signal Process Mag 2012;29(5):86–105.

[15] Saad W, Han Z, Poor HV. A game theoretic approach for multihop power line communications. In: Proc. int. conf. game theory for networks (GameNets), Shanghai, China; April 2011.

[16] Saad W, Han Z, Poor H. Coalitional game theory for cooperative micro-grid distribution networks. In: 2011 IEEE international conference on communications workshops (ICC); June 2011. p. 1–5.

[17] Saad W, Han Z, Poor H, Basar T. A noncooperative game for double auction- based energy trading between phevs and distribution grids. In: 2011 IEEE International Conference on Smart Grid Communications (SmartGridComm); October 2011. p. 267–72.

[18] Newman MEJ, Girvan M. Finding and evaluating community structure in networks. Phys Rev E 2004;69(2):1–15.

[19] http://shodhganga.inflibnet.ac.in/bitstream/10603/1221/18/18_appendix.pdf.