<?xml-model href='http://www.tei-c.org/release/xml/tei/custom/schema/relaxng/tei_all.rng' schematypens='http://relaxng.org/ns/structure/1.0'?><TEI xmlns="http://www.tei-c.org/ns/1.0">
	<teiHeader>
		<fileDesc>
			<titleStmt><title level='a'>Reinforcement-learning-based dynamic defense strategy of multistage game against dynamic load altering attack</title></titleStmt>
			<publicationStmt>
				<publisher></publisher>
				<date>10/01/2021</date>
			</publicationStmt>
			<sourceDesc>
				<bibl> 
					<idno type="par_id">10303827</idno>
					<idno type="doi">10.1016/j.ijepes.2021.107113</idno>
					<title level='j'>International Journal of Electrical Power &amp; Energy Systems</title>
<idno>0142-0615</idno>
<biblScope unit="volume">131</biblScope>
<biblScope unit="issue">C</biblScope>					

					<author>Youqi Guo</author><author>Lingfeng Wang</author><author>Zhaoxi Liu</author><author>Yitong Shen</author>
				</bibl>
			</sourceDesc>
		</fileDesc>
		<profileDesc>
			<abstract><ab><![CDATA[As the current power grid is highly interconnected and more information and communication technologies (ICTs) are being deployed recently, it could be the target of malicious cyber-physical attacks. Dynamic load altering attacks (D-LAAs), as a special case of load altering attacks, could be performed to interfere the demand response and ultimately force certain generators off-line. Cascading failures due to transmission line overloads may also be triggered. In this paper, we propose a new dynamic defense strategy against D-LAAs through a multistage game between the attacker and the defender which is solved by minimax-q learning. Different from the static game, the multistage game considers the attacker and defender's action sequences and the optimal strategies at each state are learned. After each time step, the cascading failure is measured, and the load shedding is used as the feedback for the attacker to generate the next action strategy. The performance of the proposed model is evaluated on the IEEE 39-bus system. Comparisons between the dynamic defense strategy and the passive defense strategy are conducted, and the results verify the advantage of the proposed dynamic defense strategy. To improve the power system resilience, this defense strategy can be deployed in advance when such cyber-physical attacks are anticipated.]]></ab></abstract>
		</profileDesc>
	</teiHeader>
	<text><body xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink">
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1.">Introduction</head><p>Ensuring cybersecurity of modern power grids has become a national priority with the smart grid initiative. The use of information and communication technologies (ICTs) has not only enhanced the efficiency and reliability of the power grids but also created new vulnerabilities if they are not accompanied by advisable security reinforcements <ref type="bibr">[1,</ref><ref type="bibr">2]</ref>. Various vulnerabilities may leave some sectors of the power system to a wide range of cyber-physical attacks <ref type="bibr">[3]</ref>. As a real example, attackers remotely switched off the breakers in a series of substations by preinstalled malware, resulting in a widespread outage in the Ukrainian power system in late 2015. This blackout is the first publicly acknowledged incident caused by cyber-attack which is even more destructive than natural disasters <ref type="bibr">[4]</ref>. Furthermore, identifying and mitigating such risks are instrumental in improving the resiliency of power grids <ref type="bibr">[5]</ref>. Thus, considering the increasing cyber-physical threats to the modern power system, it is imperative that we understand the risks resulting from cyber-physical attacks and thus implement effective security strategies against them.</p><p>Load Altering Attack (LAA) is a representative cyber-physical attack with the aim to maliciously control and alter a group of remotely accessible yet unsecured controllable loads. A successful LAA can disturb the balance between the power demand and supply, causing frequency and angle instability and consequently system blackout through circuit overflow or generator tripping. The potential vulnerable loads to LAAs can be frequency-responsive loads <ref type="bibr">[6,</ref><ref type="bibr">7]</ref>, data center's computational load <ref type="bibr">[8]</ref>, loads with direct load control (DLC) which is one of the most common demand side management programs <ref type="bibr">[9,</ref><ref type="bibr">10]</ref>, etc.</p><p>LAAs can be categorized into static load altering attack (S-LAA) (which is mainly focused on the amount of vulnerable loads) and dynamic load altering attack (D-LAA) (which is additionally concerned with the trajectory of the changes that are made in the vulnerable loads). Reference <ref type="bibr">[11]</ref> introduces and models S-LAA in smart grids, and the studies in <ref type="bibr">[12]</ref><ref type="bibr">[13]</ref><ref type="bibr">[14]</ref> address the prevention or detection of LAAs. Unlike these investigations, reference <ref type="bibr">[15]</ref> introduces, characterizes and classifies D-LAAs as a new class of cyber-physical attacks against the power grids. In <ref type="bibr">[16]</ref>, the authors present a protection scheme using energy storage systems to improve the power grid's reaction to D-LAAs.</p><p>Game theory is oftentimes used to help people understand the situations in which decision-makers interact, e.g., between attackers and defenders. There is a wide range of situations to which game theory can be applied: political candidates competing, companies competing in business, bidders bidding in an auction, and so on <ref type="bibr">[17]</ref>. Various games are formulated to illuminate different economic, political, engineering phenomena, such as general sum, zero-sum and potential games.</p><p>Recently, researchers recognized the critical role of game-theoretic approaches in power grid security. The security games introduce an analytical framework with a rich mathematical basis for modelling the interactions between intentional attackers whose aim is to disrupt the power grid and operators defending it <ref type="bibr">[18,</ref><ref type="bibr">19]</ref>. The games in power grid security are classified into two categories: static and dynamic games. The static game can be considered as a one-shot process, which means players only take one action. A wealth of research <ref type="bibr">[20]</ref><ref type="bibr">[21]</ref><ref type="bibr">[22]</ref><ref type="bibr">[23]</ref><ref type="bibr">[24]</ref><ref type="bibr">[25]</ref> has emerged on the static defense schemes against malicious attacks in the smart grid.</p><p>In <ref type="bibr">[20]</ref>, the authors present a comprehensive and quantitative static game framework for the power system security problem. Under this framework, a new criterion is derived to seek reliable defense strategies.</p><p>In <ref type="bibr">[21]</ref>, a zero-sum static game model is proposed to provide security policies in the cyber layer with corresponding resilient control in the physical layer. In <ref type="bibr">[22]</ref>, <ref type="bibr">Farraj et al.</ref> analyze the cyber switching attacks and corresponding mitigation method by the zero-determinant strategy in an iterative game. The strategy allows the electric power utility (EPU) to stabilize the power grid in the face of cyber switching attacks. A game equilibrium is obtained by a zero-sum static game between intentional attackers and defenders to provide a reliable fusion-based defense scheme for the communication network of power systems in <ref type="bibr">[23]</ref>. In <ref type="bibr">[24]</ref>, the effect of the compromised active power measurements on the electricity price is quantified. This situation is modeled as a zero-sum game between the defender and the attacker who performs the bad data injection attack on the measurements. For defending against denial-of-service (DoS) attacks, Li et al. <ref type="bibr">[25]</ref> investigate the interaction between the sensor nodes and adversaries. On the other hand, dynamic games have been a largely underexplored domain in the power grid security area. Most existing work mentioned previously are focused on static games or static defenses without considering dynamic processes. In dynamic or multistage games, attackers can compromise multiple components in a time sequence <ref type="bibr">[26]</ref>. For some practical cases, to obtain the maximum profit or achieve the attack objective, attackers have to take offensive actions one by one based on the defender's protection policy and the next steady state of system. Note that full knowledge and observation of the target system are required for the players. In <ref type="bibr">[27]</ref>, the authors propose a stochastic game to protect the power system against coordinated cyberphysical attacks. Although two states are considered, the game proposed in <ref type="bibr">[27]</ref> is more like a one-shot game because the attacker can only target one element at a time. There is no more dynamic evolution in this game. Ma et al. consider a multi-act dynamic game in the electricity market for defending against jamming attacks in <ref type="bibr">[28]</ref>. Dynamic programming is adopted to solve the game. To carry out the recursions, knowing the model of environment is necessary. In <ref type="bibr">[29]</ref>, a q-learning method is devised to solve a multistage game. The attacker's actions are considered while the defender's actions are pre-defined rather than evolving by interacting with the attacker's action and system state.</p><p>Furthermore, machine learning methods are being applied to address cyber-physical security issues in power systems for attack detection, analysis of defense strategy, and fault diagnosis. In <ref type="bibr">[30]</ref>, a deeplearning-based algorithm to detect power theft and false data injection (FDI) attack on real-time measurements is proposed. The authors in <ref type="bibr">[31]</ref> use Q-learning to analyze vulnerabilities of the power system in sequential topological attacks. Wang et al. <ref type="bibr">[32]</ref> develop a deep learning method for fault diagnosis of power plants. A hierarchical deep domain adaptation (HDDA) approach is proposed to apply a classifier with labeled data under one loading condition to detect faults with unlabeled data under another loading condition.</p><p>Thus far, the focus in power grid security against malicious attacks has been mainly on static defense schemes. In contrast, in this paper, we address a new dynamic defense policy against multistage D-LAA, which is concerned with dynamic interactions between the attacker and defender. The attack-defense interaction is modeled by a two-player zerosum multistage game and the solution is obtained based on minimax-q learning. Unlike dynamic programming solution given in <ref type="bibr">[28]</ref> that requires exact knowledge of the model of environment, the proposed minimax-q learning based solution in this paper goes from experience to policies by learning a model rather than needing a model. The main contributions of this paper are summarized as follows:</p><p>&#8226; The one-shot dynamic load altering attacks (D-LAA) in <ref type="bibr">[15]</ref> is extended to a sequence attack. The corresponding cascading failures caused by D-LAA are studied holistically. It allows the attacker takes offensive actions one by one based on the states of system and adversary's protection policy to achieve much higher attack objective. &#8226; A two-player zero-sum multistage game considering both dynamic of the attacker and the defender is proposed.Different from the one-shot games that lack dynamic evolvement of the attack-defense sequence and passive defense strategies where the evolvement of defender's actions is neglected in the existing literature, a minimax-q learning scheme is adopted in this paper to effectively find out the optimal defense sequence against chronological D-LAA considering dynamic interactions between the attacker and the defender. This is also the main difference between the proposed dynamic defense and the existing research. &#8226; This dynamic defense strategy is compared with the static (passive) defense policy. The simulation results show that the power grid with the proposed defense strategy does have lower load loss due to D-LAAs.</p><p>The rest of this paper is organized as follows: Section II presents the related preliminaries and the game model is formulated in Section III. Analysis of the minimax-q learning solution is presented in Section IV. In Section V, simulation setup, results and analysis are presented. Concluding remarks and potential future directions are given in Section VI.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.">Related Preliminaries</head><p>In this section, some related preliminaries are presented including the mathematical model of D-LAAs, optimal load shedding problem and cascading failures.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.1.">Dynamic Load Altering Attack</head></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.1.1.">D-LAA Implementation Principle</head><p>The basic threat model is adopted from reference <ref type="bibr">[15]</ref>. As mentioned, D-LAA is concerned with the volume as well as the trajectory of the changes in the vulnerable load. In a closed-loop D-LAA, referring to Fig. <ref type="figure">1</ref>, the attacker tries to manipulate the vulnerable load (P1) with constant monitoring at the sensor bus for the grid conditions. Although there are various approaches to measure the grid conditions and alter the load, in this paper we limit our scope to the power system frequency obtained from the installed frequency sensors and frequency-responsive loads. A successful D-LAA can be conducted only if there are sufficient potential vulnerable loads to be compromised. The attack objective is to deviate the frequency from the system's nominal value and eventually push one generator off-line. To implement a D-LAA, there are three main steps that the attacker must undertake:</p><p>&#8226; Install the frequency monitor at the sensor bus and constantly send frequency acquisitions to the D-LAA controller. In general, it is not difficult to monitor the frequency of power system using an inexpensive commercial sensor. &#8226; Based on the mechanism of the attack controller and the feedback signal, calculate the amount of vulnerable load which needs to be compromised at the victim bus. &#8226; Remotely control and alter the victim load at the amount that is calculated in the last step. The feasibility of remotely altering the load is discussed in <ref type="bibr">[33]</ref>.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.1.2.">Attack Model</head><p>In power systems, theoretically, the power flow between buses i and j is a nonlinear function of bus voltages and the impedance of transmission lines. The active power flow can be given as follows:</p><p>where V is the voltage magnitude, &#981; is the phase angle in the corresponding bus, and G and B are the real and imaginary parts of the impedance, respectively. Note that G ij can be considered as zero because the resistance of the transmission lines is significantly less than the reactance in practice. Furthermore, the difference of voltage phase angle between two buses is small and the voltage magnitude in each bus is very close to unity in the per-unit system. Thus, further approximation for the power flow equation can be written as:</p><p>Specifically, consider a power system with G generator buses and L load buses. Let then N = G &#8746; L represents the set of all buses in this grid. For a bus i &#8712; N , the total amount of power flow can be separated into the power injection of the generator P G i at bus i &#8712; G and power absorbed by load P L i at bus i &#8712; L . Defining &#948; i as the voltage phase angle of the i-th generator bus, &#952; i as the voltage phase angle at i-th load bus and B ij as the admittance value between buses i and j, the linearized power flow equations based on Eq. ( <ref type="formula">2</ref>) can be written as:</p><p>To model the dynamic behavior of each generator, the swing equations are used for the generator bus:</p><p>where &#969; i is the rotor angular frequency deviation of generator bus i, M i is the rotor inertia of each generator, P M i is the mechanical power input and D G i represents the damping coefficient. Note that P M i and D G i must be positive.</p><p>Specifically, the turbine-governor controller and the load-frequency controller can be integrated together as a proportional-integral (PI) controller, aimed at maintaining the rotor angular frequency at its nominal level to affect the mechanical power input <ref type="bibr">[34]</ref>. The PI controller is represented as:</p><p>where K P i and K I i are the proportional and integral controller coefficients, respectively. As a result, the rotor frequency dynamics in Eq. ( <ref type="formula">6</ref>) can be rewritten by expressing the mechanical power for each generator in terms of frequency deviation &#969; i , as defined in Eq. ( <ref type="formula">7</ref>). It becomes:</p><p>According to Eq. ( <ref type="formula">3</ref>), we obtain:</p><p>In this way, expressions ( <ref type="formula">5</ref>), ( <ref type="formula">4</ref>), ( <ref type="formula">9</ref>) formulate the complete dynamical model and can be written as the following linear state-space descriptor system:</p><p>where B is the imaginary part of the admittance matrix:</p><p>Now, we consider a single-point closed-loop D-LAA that is performed at victim load bus v and the frequency sensor is installed at a generator bus s aiming to push this particular generator off-line. Suppose a proportional-integral controller is used by the attacker, creating a large deviation while less load is needed. Let K L p and K L I denote the attack controller's proportional and integral gains at the generator bus (sensor bus) s, respectively. We can write the compromised power consumption level P L v at victim bus v:</p><p>As a result, the system dynamics subjects to the above D-LAA becomes</p><p>From Eq. ( <ref type="formula">13</ref>), when the system is under attack, the attacker can affect the system dynamics and compromise the system stability by adjusting the attack controller matrices K L p and K L I . In particular, the system becomes unstable if the attacker is capable of moving the system poles to the right-half complex plane assuming the vulnerable load is large enough. Considering generators are generally equipped with various relays in the modern power system <ref type="bibr">[35]</ref>, a single-point closed-loop D-LAA may push the generator off-line and disconnect it from the grid.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.1.3.">Control Scheme of Closed-loop D-LAA</head><p>It is worth mentioning that PI control in <ref type="bibr">(7)</ref> is not the only option to successfully implement D-LAA. In general, the closed-loop D-LAA can be viewed as a frequency controller which makes the compromised loads react to frequency deviants in the opposite direction of the normal demand response for frequency regulation. It has been discussed in <ref type="bibr">[15]</ref> that "the attacker may use a bang-bang, P, PI, or PID controller, or any other more complex feedback control system mechanism" for the closed-loop D-LAA, and a P control model is used in <ref type="bibr">[15]</ref> to formulate the D-LAA. In this work, the P control based D-LAA attack model in <ref type="bibr">[15]</ref> is extended to a more general PI control based model. The models provide effective methods for the modeling of malicious D-LAA actions against the frequency control of the grid. The proposed model keeps the direction of D-LAA actions opposite to the normal frequency control of the grid. Furthermore, the focus of this work is not to design attack controller but rather to develop a dynamic defense framework plan by minimax-q learning against such multistage attacks. This method and idea are not affected by the controller selection and can potentially be extended to other multistage attacks.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.1.4.">D-LAA Implementation</head><p>The D-LLA is launched by altering the remotely controllable demands instead of the outputs of the generation units in the grid. Referring to Fig. <ref type="figure">1</ref> the adversary only needs to hack into the remote load control systems to adjust the power consumption trajectory by constantly monitoring the frequency signals to implement D-LAA. Such remote load control systems extensively exist in demand response programs. Specifically, an attacker may aim to compromise command signals in Direct Load Control (DLC) programs that often involve two-way communications between the power system operator and loads or aggregators <ref type="bibr">[36]</ref>. The adversary may utilize the vulnerability in any of these communications infrastructures to gain direct and remote access and control over the load through the load control mechanism. These loads that are potentially vulnerable to D-LAA attack include air conditioners <ref type="bibr">[37]</ref>, building lighting system <ref type="bibr">[38]</ref>, water heaters <ref type="bibr">[39]</ref> and electric vehicles <ref type="bibr">[40]</ref>. For example, considering the heating, ventilation and air conditioning (HVAC) demand in buildings, after intruding into the communication between the building and grid operator, the attacker could generate desired aggregated load profile by orchestrated periodic on/off signals to each component, e.g., air conditioner and fan.</p><p>To set the parameters in the controller-based model of D-LAA, the attacker needs to know or estimate the system dynamic model including the system frequency control settings and grid topology, which do not change frequently and are considered constant during the attack in this paper. The only signal that needs to be updated in real time by the attacker when implementing the closed-loop D-LAA is the frequency signal. Thus, following the work in <ref type="bibr">[15]</ref>, it is assumed in this paper that the attacker can constantly monitor the frequency signals via the attacker's installed sensors or by hacking into an existing monitoring infrastructure of the grid.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.2.">Optimal Load Shedding</head><p>As mentioned, when a system is attacked and the topological structure of the system is changed, such as a generator being off-line, a transmission line being tripped by relay/man or a system partition being caused, load shedding must be performed to regain stability. Considering a power system with n buses the optimal load shedding problem can be formulated as a constrained optimization problem with the physical constraints of the power flows <ref type="bibr">[27,</ref><ref type="bibr">41,</ref><ref type="bibr">42]</ref>:</p><p>subject to, Fig. <ref type="figure">2</ref>. Root locus plot of power system under a D-LAA attack.</p><p>where w l = [w l1 , w l2 , &#8230;, w ln ] T is the weight vector representing the relative importance of different load buses; vector z = [z g ; z l ], in which vector z g refers to the re-dispatched power at each generation bus; vector z l is the load to be shed at each load bus; vector p = [p g ; p l ], in which vector p g represents the original active power output at each generation bus; vector p l is the demand at each load bus; vector &#981; represents the phase angle at each bus; &#923; is the incidence matrix for the topology of the grid; and B is the diagonal matrix of the transmission-line admittances. Constraint <ref type="bibr">(15)</ref> represents the power balance at each bus; constraint (16) is the power output limit of the generation; constraints <ref type="bibr">(17)</ref> and <ref type="bibr">(18)</ref> are the constraints of the generation redispatch and load shedding respectively; Constraint (19) limits the phase angle difference of the connected buses of each transmission line in the grid.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2.3.">Cascading Failures and D-LAA in Sequence</head><p>A successful single D-LAA with the aim to disconnect a generator may cause cascading failures during the post-attack stage. Due to the excessive load demand after attack, load shedding is an inevitable option for the system operator <ref type="bibr">[11]</ref>. The optimal load shedding technology has been discussed and presented in Section 2.2. After the load shedding is carried out, a DC power flow analysis is performed to check for overloads on the transmission lines. If a transmission line is overloaded by over 50%, it will be tripped by the operator. Then the balance between the generation and demand is checked again and these steps are repeated until entering into the next steady state.</p><p>On the other hand, for causing a more severe damage to the power system such as more load shedding or generation losses, the attacker may perform the D-LAAs in sequence (one-by-one). For example, the attacker may perform a D-LAA to force a generator to be disconnected from the grid and trigger cascading failures. Then, based on the current state and system topology of the post-attack stage, the new proper victim and sensor buses are selected and another D-LAA can be performed. The attacker may repeat this process until the attack goal is achieved.</p><p>There is a main concern for the D-LAA sequence: how to choose the best attack controller gain for each step? For the ease of analysis, it is assumed the frequency sensor is placed at the generator bus, that is, the sensor bus is always one of the generator buses, and all portions of loads are controllable at each vulnerable load bus. As mentioned previously, the attacker may destabilize the system by changing the controller gain matrix K L P . From the control perspective, the locations of system poles change with the increase of K L P and once the pole(s) are moved to righthalf plane the system becomes unstable. Fig. <ref type="figure">2</ref> shows how the root locus analysis helps the attacker find the minimum attack gain.</p><p>The minimum vulnerable load that must be compromised can be calculated by Eq. ( <ref type="formula">12</ref>). If the minimum amount of load is not larger than the total load at this load bus, the selections of victim load bus and sensor bus are feasible. The attacker tries to make the least effort to achieve the attack goal, so for the same sensor bus when there are two feasible victim buses the attacker tends to choose the one with less minimum compromised load. Once a D-LAA is successfully performed and the cascading failures are triggered, the system enters into the next steady state and the attacker may choose the new feasible victim and sensor buses to conduct the next attack. In simulations, we can change the entries of matrix B in Eq. ( <ref type="formula">13</ref>) based on the current system topology because B ij = 0 if the transmission line between buses i and j is tripped.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.">Game-theoretic Analysis of Attack-defense Interactions</head><p>In this section, the behaviors of the attacker and defender are modeled using a two-player zero-sum multistage game. As introduced in Section 1, game theory helps people understand the interactions between the decision-makers. For the analysis of power system security, the attacker and defender are considered as two decision-makers or players. The attacker can be hackers, organized terrorists or other criminals. The defender is the system administrator who monitors the power system network and implements security measures. The attacker intends to cause the maximum damage to power grid while the defender strives to minimize the impact. Thus, the defender's gain is regarded as the opposite of the attacker's gain. In the attack, the adversary may compromise components in sequence instead of at the same time, in order to cause more damage and decrease the risk of being detected. Similarly, the defender has to change defense actions with a dynamic attacker. Thus, both the attacker and defender have to adjust their actions based on the observation of their past actions and current states. In this way, the attack-defense game falls exactly into the category of twoplayer zero-sum games. This game can be considered as a 5-tuple (S S , A A , A D , R A , R D ) Markov game, where.</p><p>&#8226; S S = def {s 1 , &#8230;, s Ns } denotes the system's state space;</p><p>&#8226; A A = def {a 1 , &#8230;, a NA } denotes the attacker's action space; Fig. <ref type="figure">3</ref> illustrates a typical player-system interaction for the twoplayer game. The attacker obtains system state s and takes the attack action a, and will receive reward R A . Meanwhile, the defender will conduct the same process and receive reward R D .</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.1.">Action Spaces</head><p>Attacker's target is to implement D-LAA aiming to disconnect one generator and cause cascading failures. Attacker's action a &#8712; A A means trying to force one generator disconnecting from the main grid at a time step. The defender's action is related to protect a generator bus. However, the defender can restrain this attack on generators by protecting the load on corresponding victim buses. As discussed in Section II-B, a successful D-LAA needs a victim bus and a sensor bus. The defender may follow the same method in Section II-B to obtain all vulnerable loads that can be potentially controlled by the attacker. Thus, protecting the victim load is an effective method against D-LAA. That is, the physical meaning of protection action is to protect the potential victim load rather than protecting these generators. Currently, the load can be protected by implementing reinforced security measures, e.g., adding hardware and software based security components, at both the communication level <ref type="bibr">[43]</ref> and device level <ref type="bibr">[44,</ref><ref type="bibr">45]</ref>. For example, reference <ref type="bibr">[43]</ref> proposes a method in which the administrator can temporarily revoke the certificate of some nodes. In this way, these nodes are excluded from the grid's communication network, that is, the attacker is not able to remotely alter these loads.</p><p>In this paper, it is assumed that when a defense action is performed on a load bus, the load at the protected bus P L v cannot be manipulated by the attacker. Note that not all loads can be targeted by attacker to implement D-LAA because some loads are traditional types which cannot be remotely manipulated.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.2.">System States</head><p>This game is played over a finite state space denoted by S S . States are formulated as a combination of the statuses of all transmission lines of the power grid. For each state s, the status of the transmission lines is represented by a binary number '1' or '0'.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>S t</head><p>( l</p><p>Fig. <ref type="figure">4</ref> shows the transition process from one state to the next steady state through some intermediate states. At state s, attack (D-LAA in this paper) is launched and one generator is pushed to be disconnected from the grid due to instability. The load is shed based on the model in Section 2.2 and the demand is balanced. Then, a DC power flow analysis is applied to decide if any overloads occur on the transmission lines.</p><p>Generally, the transmission line is tripped if the overload exceeds 50%. The system repeats this process until the generation and demand is balanced and there is no overloaded transmission line. Please see Section 2.3 for more details.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.3.">Attacker and Defender's Policies and Rewards</head><p>There are two players in the game: the attacker and the defender. At state s, the players choose their respective actions a &#8712; A A and d &#8712; A D independently, and immediately receive rewards R A a,d (s) and R D a,d (s), respectively. In this zero-sum game, the defender's expected reward is opposite to the attacker's expected reward, denoted by R A a,d (s) = -R D a,d (s). The rewards for players are assigned following the conditions given as:</p><p>and</p><p>where z represents the total load shedding caused by the D-LAA attack and N is the attack objective. Now we have specified the immediate rewards of the attacker and the defender at each state, but have not indicated how these rewards are aggregated into an overall payoff. The most commonly used aggregation method is the discounted-sum reward. For an attack action a and a defense action d, the discounted-sum rewards of the attacker and defender considering deterministic state transition are represented as:</p><p>where Q A and Q D represent game values for the attacker and the defender, respectively; and &#947; &#8712; (0, 1) is the discount factor. A smaller value of &#947; implies the agent emphasizes the immediate reward while a larger value indicates more concerns about future rewards. For a given state s, the attacker's strategy is defined as probability distributions over action space A A , i.e.,</p><p>which satisfies</p><p>Similarly, the defender's strategy is given as:</p><p>and</p><p>When only one entry of the strategies described above is nonzero (and equal to 1), &#960; A and &#960; D are called pure strategy and players always adopt this action at state s(t). Otherwise, they are mixed strategies which are adopted in this paper. Note that in this multi-stage game, the attacker and defender choose their different targets in time sequence until the attack objective is achieved.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3.4.">Nash Equilibrium</head><p>In this game, the defender tries to minimize the discounted sum of expected reward Q D while the attacker aims to maximize it. Nash equilibrium is a common solution to solve the players' optimal strategies for such a Markov game <ref type="bibr">[17,</ref><ref type="bibr">46]</ref>. Nash equilibrium is a state that no player has a unilateral incentive to change actions as that would reduce their rewards, that is, each agent plays best response to their opponents. For the proposed game model, a Nash equilibrium can be mathematically defined as follows: Definition 1. In the proposed zero-sum two-player Markov game, a Nash equilibrium is a pair of mixed optimal strategies (&#960; * A , &#960; * D ) for all mixed strategies &#960; A and &#960; D for all states s &#8712; S</p><p>For such a two-player game, it is proved that unique Nash Equilibrium exists in stationary strategies (for all t) by Shapley <ref type="bibr">[47]</ref>. That is, the mixed optimal attack/defense strategies can be solved for each state instead of each time t. In general, the stationary optimal strategy can be solved recursively by dynamic programming if environment of the model is known such as in <ref type="bibr">[27,</ref><ref type="bibr">28]</ref>.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.">Proposed Solution Approach</head></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.1.">Minimax-q Learning</head><p>In this section, we propose a new dynamic defense solution for the two-player zero-sum Markov game based on the minimax-q learning approach. Our objective is to characterize the attacker's and the defender's Nash equilibrium strategies for each state s &#8712; S S and their attack/defense actions in time sequence, where all players are rational and tend to maximize their own benefits. The attacker and the defender are completely competitive and do not cooperate with each other. Minimax-q learning <ref type="bibr">[48]</ref> is used in conjunction with Markov games. As a modification of q-learning which just considers the opponent as part of the environment, this algorithm treats the Q function not just from the state/action pairs to values, but from the state/action/action to values, i. e., <ref type="figure">Q(s,</ref><ref type="figure">a,</ref><ref type="figure">d</ref>). Thus, both players' actions and their interactions are modeled more explicitly. The minimax-q learning algorithm is adopted to approach real unknown state value function V(s) by interacting with the environment and then players obtain the optimal Nash strategies by the learned state value function. Furthermore, a state-action value function (Q function) is to quantify the performance for a player to apply a particular action following a policy &#960; in a state. From the defender's perspective, the Q function can be defined as:</p><p>and the state value function V(s) is defined as:</p><p>where &#945; t denotes the learning rate for adjusting the step size. To improve the convergence rate of this algorithm, a polynomial learning rate is adopted as 1/t &#946; where &#946; &#8712; (1/2, 1). Note that in Eq. ( <ref type="formula">30</ref>), minmax is adopted to find the best response instead of playing actions with the highest Q in <ref type="bibr">[29]</ref>. Eq. ( <ref type="formula">30</ref>) can be converted to a linear constraint optimization problem to obtain the optimal strategy at state s:</p><p>Similarly, the attacker's state value function and Q function can be dually derived:</p><p>))</p><p>The optimal strategy of the attacker can also be obtained by linear programming in <ref type="bibr">(33)</ref>:</p><p>The procedure to compute the Nash equilibrium at each state and the attack/defense sequence are detailed in Algorithm 1.</p><p>Algorithm 1. Minimax-q Learning Algorithm Update s = s &#8242; 20: end while 21: end for 22: Find optimal strategies and sequences of actions for attacker and defender</p><p>In the proposed algorithm, the game starts with the initialization of Q function, state value function V and attacker/defender's policy. Then the system is evaluated to obtain feasible D-LAA attack discussed in Section 2.3. Note that for simulations, instead of observing the root-locus plot, we can analytically obtain the minimum compromised load by gradually increasing controller K L P until the system is unstable. In the beginning, the initial state is assumed at the normal operation condition, that is, all transmission lines and generators are active and work properly. A &#8714;-greedy strategy is also adopted to balance the exploration and exploitation <ref type="bibr">[49]</ref>. With &#8714;-greedy, the agent plays a random action with a probability 0 &lt; &#8714; &lt; 1, instead of making the best decision given in the Q-function. With the execution of the actions, a certain generator is disconnected from the power grid due to the D-LAA if the corresponding Y. <ref type="bibr">Guo et al.</ref> load is not protected by the defender. Load shedding of the current state is calculated and cascading overloads on the transmission lines may be triggered until the system enters into the next steady state s &#8242; . Instant rewards are assigned to the attacker and the defender by Eqs. ( <ref type="formula">21</ref>) and <ref type="bibr">(22)</ref> and the value of Q-function is updated. Strategies &#960; A (s) and &#960; D (s) and state value V are solved by linear programming. Then, based on the new topology of system and state, feasible targets for the attack/defense's action spaces are decided. The game is repeated until the attack objective is reached. Ideally, if the process above (from step 4 to step 20) repeats for enough times, i.e., Q matrix is updated at each state by enough times, the players will learn the real complex relationships between the actions and outcomes. Thus, such relationships are reinforced in this process and eventually the players find their optimal Nash equilibrium strategies. Note that the optimal attack/defense sequence is not unique and in this study we evaluate the performance by computing the average impact to the system. Furthermore, this defense strategy is not a real-time one but is more like a pre-stipulated plan against low-probability high-impact attacks, such us D-LAA in this paper, to minimize the damage. According to the features of D-LAA attacks, the defender can find an optimal policy for each state against potential vicious attacker if both play rationally. The defense strategy can be deployed in advance when such attacks are anticipated to improve the resilience of the power system.</p><p>In this paper, the proposed work focuses only on the D-LAA scenario. Nevertheless, because the proposed defense method is based on minimax-q learning which works with Markov game, this work can be extended to other multistage attacks, e.g., Load Redistribution (LR) attacks and line switching attacks, as long as the action spaces and cascading failures are redesigned following specific attack mechanisms. The power grid operator may make multiple such stored plans based on different types of attacks and defense actions. ) ,</p><p>where A and D represent the numbers of total possible attack and defense actions, respectively. It can be seen that the computational complexity increases linearly with more attack/defense options. As for S, more possible states will cause relatively quicker increase of the computational complexity.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.">Simulation Results and Analysis</head><p>Now we evaluate the performance of the proposed minimax-q learning for this two-player zero-sum Markov game on the IEEE 39bus system that consists of 46 transmission lines and 10 generators. The results of dynamic defense strategy may provide useful insight for grid operators to improve the resiliency of power systems. Comparisons with the existing passive and dynamic defense strategies are conducted to illustrate the importance of deploying the proposed dynamic strategy against D-LAA.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.1.">System Parameters</head><p>Fig. <ref type="figure">5</ref> shows the IEEE 39-bus system based on a 10-machine New-England power network. There are 10 generators, 46 transmission lines and 19 loads. There are two loops in the simulation: episodes and runs. The episodes loop is the main loop in which the attacker and the defender interact to learn the optimal policy. The attacker and the defender complete a bunch of actions in sequence. As the number of episodes increases, the attacker tends to approach the optimal policy. At the end of the episodes, the attacker and the defender reach the Nash equilibrium point. A number of runs are conducted to deduce different Nash equilibria. Therefore, the whole game simulation is conducted for many runs. Each run includes a number of episodes. The number of episodes is the required number of trials for the agent in the learning process. The initial exploration rate &#8714; is 0.9 and decreases 10% every 20 episodes to ensure the convergence. Other simulation parameters are given in Table <ref type="table">1</ref>.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.2.">Selection of Vulnerable Bus and Attacker/defender's Action Space</head><p>As discussed in Section II, not all loads can be considered vulnerable to D-LAAs. Some loads are traditional ones and may not even have smart meters or any demand response equipment, which the attacker cannot remotely manipulate. In this case, we assume that only eight load buses have vulnerable loads. They can potentially become victim buses, i.e., V = {4, 6, 7, 12, 18, 19, 23, 29}. On the other hand, according to <ref type="bibr">[50]</ref>, generators {31, 35, 37, 38} represent nuclear stations which are fully protected. Thus, frequency sensors are assumed to be placed only at S = {30, 32, 33, 34, 36, 39} that are considered as fossil and hydro stations. Thus, the attacker's action space is A A = {30, 32, 33, 34, 36, 39}. Table <ref type="table">2</ref> shows the minimum portion of the vulnerable load that must be compromised to guarantee a successful D-LAA at the initial state. We assume K L I a pre-tuned parameter and there is no need to change it for simplicity of calculation. The highlighted cells indicate the attacker could launch D-LAA on the corresponding sensor bus and victim bus. For the initial state, the attacker is not able to compromise generator 34 because there are not enough loads to be manipulated for the given vulnerable buses. Therefore, for the initial state, the attacker can perform D-LAA to disconnect generators {30, 32, 33, 36, 39}. Furthermore, at each visited unique state, Table <ref type="table">2</ref> is updated for the next selection of the attack target. Based on the same table, the defender also decides the protection action that should be taken. The defender's action space is denoted as A D = {30, 32, 33, 34, 36, 39}. As mentioned previously, the physical meaning of the protection action is not to protect these generators but to protect the corresponding potential victim load. For example, at the initial state, when the defender selects action "30", it means the load on the corresponding victim bus 7 is protected.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.3.">Game-theoretic Attack/Defense</head><p>Figs. <ref type="figure">6</ref> and<ref type="figure">7</ref> show the convergence curves of the optimal number of attacker/defender's actions. After adequate learning and exploration, we can see that both players reach the optimal number of actions. Among 50 independent runs, the attacker needs three actions in sequence to achieve the objective and the defender also needs the same number of actions to minimize the load shedding caused by D-LAAs. The average computing time per run is about 564s. We need to emphasize again that the defense strategy is not real-time but off-line trained prestipulated plan against the low-probability high-impact D-LAA. The defense plan can be deployed in advance when such attacks are anticipated. Therefore, the proposed strategy can adequately meet the time requirement of practical applications.</p><p>Fig. <ref type="figure">8</ref> depicts the convergence of the total load shedding. The average load shedding converges to around 3400 MW after 50 runs. From the three figures, we can portray how the algorithm works especially in the intermediate process. In the early stage of learning process,  because of the large exploration rate &#8714; and inaccurate Q matrix, both the attacker and defender take actions randomly or wrongly. Thus, they may take more additional steps and the total amounts of load shedding is not stable. With the decrease of &#8714; and the update of Q matrix, the curves gradually converge. At the end of the process, the Q matrix is updated for enough times and the players learn the real relationships between the actions and outcomes. The policies at each state converge to the optimal Nash Equilibrium strategies. Figs. 9 and 10 show the attacker's and defender's optimal policies when Nash Equilibrium is reached at each unique state. For this situation, both the attacker and defender have no unilateral incentive to alter their actions, because they have maximized their profits. The physical meaning of the Nash Equilibrium status for this case is that the defender can minimize the damage (load shedding) if they both play rationally their optimal strategies. The system operators are advised to adopt these strategies for each possible state against the D-LAA. Specifically, there is no need to place any defensive strategies for some states because there are not enough vulnerable loads to alter for disconnecting generators from the power grid. Note that mixed strategy at some states. Regarding the actual implementation in practice, the operator may change the defense plan according to the probabilities of the optimal policy. For instance, at state 9, the probabilities of defender's action on generators <ref type="bibr">(30,</ref><ref type="bibr">32,</ref><ref type="bibr">33,</ref><ref type="bibr">34,</ref><ref type="bibr">36,</ref><ref type="bibr">39)</ref> are (0, 0.165, 0, 0.835, 0, 0), respectively. Thus, the system administrator may plan to take protective actions for bus 34 with a probability of 0.835 and protect bus 32 with a probability of 0.165 at each interval of the actions. The results provide useful information for power system operators to thwart dynamic load altering attacks.  The defensive action sequences are shown in Table <ref type="table">3</ref>. For this game, total 11 unique defense sequences are found and the average load shedding can be calculated as 3398.2 MW. As mentioned in Section 5.2, the defense action sequence indicates the protected generators identified by the defender while the actual actions of the defense strategy are to protect the corresponding victim load buses. For example, for the first run, this action sequence indicates that the defender tries to protect the loads on victim buses <ref type="bibr">(7,</ref><ref type="bibr">19,</ref><ref type="bibr">23)</ref>.   </p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.4.">Comparison with Passive Defense Strategy</head><p>To illustrate the importance of dynamic defense strategy, we compare our results with the passive defense strategy in this section. For a passive strategy, the defensive actions are predefined and the attacker is trained to find the optimal attack strategy in the presence of the passive defender. Considering the limited resources the operator has, we assume only two loads can be protected at a time. In this case study, three different predefined protected load sets are considered: <ref type="bibr">(7,</ref><ref type="bibr">29)</ref>, <ref type="bibr">(4,</ref><ref type="bibr">29)</ref> and <ref type="bibr">(6,</ref><ref type="bibr">7)</ref>. They are denoted as passive defense case I, II and III respectively. We adopt a similar algorithm by calculating the largest value instead of solving minimax in Eq. <ref type="bibr">(33)</ref>. The attack objective is to cause at least 50% load shedding.</p><p>Because the defense strategy is passive and unchangeable, we analyze the performance from the attacker's perspective. Table <ref type="table">4</ref><ref type="table">5</ref><ref type="table">6</ref>show the attack sequences of different runs and the total load shedding. It is found in Table <ref type="table">7</ref> that the attacker's action converges to a sequence of three actions, and the total amounts of load shedding for the passive defense I, II and III are 12.6%, 6.0% and 14.6% more than that obtained by the dynamic defense strategy, respectively. The comparison shows the proposed dynamic defense method is more effective against the single point D-LAA.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.5.">Comparison with Dynamic Defense Strategy</head><p>In this section, the proposed dynamic defense strategy in this paper is compared with the dynamic strategy in <ref type="bibr">[51]</ref>. In <ref type="bibr">[51]</ref>, the dynamic defense strategy is obtained by the pre-calculated worst-case dynamic attack, which ignores the adversarial game between the rational attacker and defender, and their future expected gains. This is the main difference between the proposed models in this paper and <ref type="bibr">[51]</ref>. To compare by same standards, the attack objective is still at least 50% load shedding. The last row of Table <ref type="table">7</ref> shows that the total amount of load shedding by applying the defense plan in <ref type="bibr">[51]</ref> is 9.2% higher than that obtained by the proposed strategy in this paper. One reason of the result is that the outcome of two players' game, i.e., the attacker and defender, is not always the best for one of them but inclines a Nash equilibrium mentioned in Section 3.4. Thus, the defense strategy derived by the worst-case dynamic attack, i.e., unilateral optimal attack, results in the worse outcome because the interaction between two rational players in each state of the Markov game for D-LAA is not considered. In general, the proposed model formulates a more complex and realistic game considering two rational players' game, which leads to better performance for the defense against D-LAA.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="6.">Concluding remarks</head><p>In this paper, we propose a novel reinforcement-learning-based dynamic defense solution against the single point D-LAA in power grid, where considering the attacker/defender's action sequence. We have derived the D-LAA in time sequence considering cascading failures at each state. A two-player zero-sum Markov game is formulated to analyze the complex interactions between the attacker and the defender, in which all players are rational and tend to maximize their own benefits. The proposed minimax-q algorithm is applied to derive the attacker/ defender's Nash equilibrium strategies. The IEEE 39-bus system is used to test the proposed algorithm and evaluate the dynamic defense strategy against D-LAA. Simulation results are compared with the existing passive and dynamic defense strategies, which indicates the proposed dynamic strategy exhibits a better performance. The system operator is informed to enforce the optimal dynamic defense strategy at each state in advance to improve the power system resiliency. In future work, distributed algorithms will be developed to further enhance the effectiveness of the defense strategy, such as the learning automata including linear reward-inaction and linear reward-penalty.</p></div></body>
		</text>
</TEI>
