{'fraction_non_alphanumeric': 0.033754085427702016, 'fraction_numerical': 0.007776400315564071, 'mean_word_length': 4.300776583034647, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Likelihood of Cyber Data Injection Attacks to Power Systems

Cyber data attacks are the worst-case interacting bad data to power system state estimation and cannot be detected by existing bad data detectors. In this paper, we for the first time analyze the likelihood of cyber data attacks by characterizing the actions of a malicious intruder. We propose to use Markov decision process to model an intruder's strategy, where the objective is to maximize the cumulative reward across time. Linear programming method is employed to find the optimal attack policy from the intruder's perspective. Numerical experiments are conducted to study the intruder's attack strategy in test power systems.


I. INTRODUCTION
State estimation [1] solves for power system states from obtained measurements. The correct estimation of systems states is vital for the reliable operation of power systems. Since bad data can result in significant errors in the outcome of state estimation and potentially lead to catastrophic consequences, the detection and identification of bad data has been extensively studied [3], [6], [13], [14], [21] in state estimation.
The integration of cyber infrastructures in future smart grids inevitably increases the possibility of cyber attacks. Cyber data attacks, firstly studied in [12], means that a malicious intruder with system configuration information simultaneously manipulates multiple measurements and the injected errors cannot be detected by any bad data detector.
State estimation in the presence of cyber data attacks has attracted much research attention recently [2], [4], [9], [11], [12], [16]- [18]. Some work focused on the identification of a small number of key measurement units such that if those units are protected from an intruder, the intruder cannot launch a successful cyber data attack [2], [4], [8]. A few recent work [11], [17], [19] considered the detection of cyber data attacks in a power system with Supervisory Control and Data Acquisition (SCADA) systems or phasor measurement units (PMUs) and various detection methods have been proposed.
What is missing in the literature of cyber data attacks is the analysis of the frequency of data attacks in smart grids and the likelihood of attacks at a given system state. This paper takes the first step to analyze the likelihood of data attacks from the intruder's perspective. We consider a scenario that if a cyber data attack is detected by the operator, the affected measurement units will be protected for some time. Thus, the intruder's current action affects its future available actions.
To address such challenge in developing an attack strategy, we propose to use Markov Decision Process (MDP) [15] to model the intruder's attack decision across time. The solution to the resulting MDP is a mapping from system states to the intruder's actions (attack or not, which bus to attack and how much error to inject). Numerical experiments are carried on PJM 5-bus system to verify the proposed approach and study the likelihood of cyber attacks in such systems.
The rest of the paper is organized as follows. We motivate the problem and introduce cyber data attacks and MDP in Section II. We formulate the intruder's attack strategy as an MDP and introduce its solution method in Section III. Section IV records our numerical study on an example network. We conclude the paper in Section V.

II. PROBLEM MOTIVATION AND BACKGROUND
We first introduce the definition and existing work on cyber data attacks in Section II-A. We then motivate and introduce the problem of likelihood analysis of cyber data attacks in Section II-B. One main contribution of our paper is to model this problem as a Markov Decision Process (MDP). MDPs are introduced in Section II-C.

A. Cyber Data Attacks in Power Systems
In a power system, the state is usually represented by bus voltage magnitudes V ∈ R n and angles θ ∈ [−π, π] n , where n is the number of buses. State estimation [1] solves for system states from the obtained measurements. Under the AC measurement model, the measurements z can be expressed as a nonlinear function of state variables x = (V ,θ): where ω represents the random measurement noise. In the AC state estimation, the state variables are determined from the weighted least square optimization problem: where R is the covariance matrix of measurement noise ω.
Malicious intruders can hack the measuring devices and inject interacting errors to the measurements. If they have sufficient system information and choose the errors e z satisfying where e V and e θ represent the resulting errors on state variables V and θ respectively, the manipulated measurements cannot be detected by existing bad data detectors. In this case, instead of correctly estimating state variables (V , θ), the operator would obtain a wrong estimate (V + e V , θ + e θ ).
Since such cyber data attacks cannot be identified by bad data detectors, many efforts have been devoted to identify and protect a small number of key measurement units such that an intruder cannot inject unobservable attacks without hacking protected units [2], [4], [8]. A few recent work [11], [17], [19] considered the detection of data attacks and various detection methods have been proposed.
The potential financial risks of cyber data attacks are studied in [20] and [7], where the congestion pattern is defined as the set of congested lines. By injecting false data without being detected, the intruders could change the congestion pattern and thus change the locational marginal price (LMP). The intruders can obtain financial reward from the resulting change in LMP.
In this paper, we restrict our attention to attacks that satisfy (3) and result in a change of the system congestion pattern. By launching a data attack, if a line's real power is wrongly estimated to exceed its capacity while it actually is not, or the power is wrongly estimated to below its limit while the line is actually congested, then the intruder can gain a reward from the attack.

B. Likelihood of Cyber Data Attacks
One important question that has not been considered before is the analysis of the likelihood of cyber data attacks at a given operating state of power systems.
In this paper, we act as an intruder and aim to find the optimal attack strategy from an intruder's perspective. We assume that an intruder can obtain a reward from a change of the congestion pattern by injecting false data without being detected. The intruder aims to maximize the cumulative reward. If a cyber data attack, however, is detected by detection methods such as [11], [17], [19], we assume the intruded measuring devices will be protected for some time so that an intruder cannot change the measurements of these devices during the period. A detected attack, therefore, can limit the intruder's future actions and thus reduce the future reward. Since the state of a power system changes across time, and the future state is unknown to the intruder, it needs to decide when and which buses to attack to maximize the total rewards based on its current estimate. We employ Markov Chains [15] to model the evolution of power system states and formulate the intruder's decision process as a Markov Decision Process [15]. The solution of resulting MDP is a mapping from system states to the intruder's actions.

C. Markov Decision Processes (MDPs)
An MDP is a mathematical framework employed to model the decision-making process in stochastic environments. In this framework, the system is modeled via a series of states S. Each state s ∈ S has an associated set of actions A(s). In time step t, a decision is made based on the system's current state s t ∈ S, and an action a t ∈ A(s t ) is chosen to conduct. The cost of taking action a t at state s t is G(s t , a t ). Then following the state transition probability distribution, the system transits to a new state s t+1 with a probability of P (s t+1 |s t , a t ). A reward R(s t+1 |s t , a t ) is received from the state transition. As the system evolves, a sequence of rewards is obtained. The aim for decision-makers is to choose sequential actions that yield maximal expected rewards over the total decision-making horizon. The MDP problem can be solved by numerous methods, like value iteration, policy iteration and linear programming approaches discussed in [15].

III. PROBLEM FORMULATION AND SOLUTION
In Section III-A, the problem is formulated from the perspective of attackers and the strategy of cyber data attacks is modeled as an infinite-horizon MDP. The solution method of resulting MDP is discussed in Section III-B.

A. Problem Formulation 1) States and Time Steps:
Here we employ bus voltage magnitudes, angles and the states of measuring devices together as system states in an MDP. Because the measurements contain noise and an intruder may have limited knowledge of the states of a power system, we use discrete states to model the intruder's estimate of actual power system states.
. n V denotes the number of discrete states in the range. We define the state of the voltage magnitude of bus i as We say the state of the voltage angle of bus i is The state of the jth measuring device is denoted by a variableŪ j : If a measuring device is protected, then an intruder cannot change any measurements of that device. Otherwise, an intruder can change partial or all measurements of that device. We consider a discrete-time system, and the time step is set as the duration between two consecutive instants of state estimation. The sampling rate of measuring devices can be higher than the state estimation frequency, as shown in Fig. 1. Attacks can happen during either device sampling or data transmission to control center. We assume if intruders decide to attack a device during step t, they need to change all the measurements of that device in the time step. Otherwise, the attack can be easily detected by comparing consecutive measurements. If a power system has M buses and N devices, the state s t at time step t is whereV i (t),θ i (t) andŪ j (t) represent the states of voltage magnitude and angle of bus i and the state of jth device at time step t respectively.

2) Actions, Rewards and Costs:
Since the reward results from a change in the congestion pattern, in order to change the line power, the intruder needs to inject errors to the estimate of voltage phasors of incident buses. Let e Vi and e θi denote the injected errors to the voltage magnitude and angle of bus i respectively. To make the problem tractable, we assume e Vi and e θi can only be multiples of ∆Vi nV −1 and ∆θi n θ −1 respectively, and the resulting estimates of system variables still lie in individual allowable range. In this case, there are totally n V × n θ available ways to inject errors to one bus voltage phasor. Note that in order to pass the bad data detection, given e V and e θ , an intruder needs to choose the injected errors e z to measurements according to (3).
We call a set of buses and lines as target buses and target lines respectively if the intruder attempts to change the congestion pattern of these lines by injecting errors on the target buses. Since an intruder may have limited resources to launch attacks, we assume at each time step the intruder can manipulate the states of at most d bus voltages. The intruder, therefore, has at most d i=0 M i ways to select target buses. The launched attacks can be detected by some recently developed methods, as presented in section II-B. Here we use p d (s, a) to denote the probability that an action a at state s is detected by the network operator. We suppose it is a function of injected errors on the bus voltage magnitudes and angles: where C is a positive constant. Intuitively, a larger C means a higher probability with which the launched attack can be detected.
Since the bus voltage magnitudes and angles are in discretized states, instead of computing the power flow of line ij directly from one specific state (V ,θ), we can obtain the lower and upper bound of its absolute value, denoted as P min ij (V ,θ) and P max ij (V ,θ) respectively. Since the reward results from a change in the congestion pattern, we define the reward as a function proportional to the gap between the line's flow limit and the power bounds with injected errors: where K ij is the given reward weight of line ij, P M ij is the power flow limit of line ij, (V ′ ,θ ′ ) is the resulting estimate of system states by injecting errors (e V , e θ ) to (V ,θ).
The expected immediate reward from action a at state s is: where Φ(s, a) is the set of target lines. We assume the cost to intrude an accessible measuring device is fixed and known to an intruder, denoted by g u . Let f (Φ(s, a)) denote the number of intruded measuring devices in attack a, the attack cost at state s is: s, a)).

3) State Transition Probabilities:
We assume all measuring devices that are currently open to attack will stay open without attack. An action a at state s is detected with probability p d (s, a), and the intruded devices will be protected as a whole in the next time step. Each protected device will change to open in the next time step with a fixed probability p T . Intuitively, a smaller p T indicates that once protected, a device is more likely to stay inaccessible to intruders for a longer period of time. When p T = 0, it means the protected devices will no longer be accessible to intruders.
To model the dynamics of a power system, we assume each load in the system evolves independently as a Markov Chain [15] and the system state is determined from economic dispatch. We assume each load has n L states and a load can transit from state q 1 to state q 2 with a fixed and known probability p q1,q2 . In practice, one can learn these transition probabilities from historical data. In this case, in a power network with M buses and N devices, if M L loads evolve as Markov Chains, the total number of system state is n ML L ×2 N .

B. MDP Solutions
A linear programming approach [5], [15] is applied to solve MDP. A stationary policy π for an MDP is a mapping π : S → A, where π(s) is the action taken in state s. We define W π (s) as the cumulative expected net reward by starting from state s and following policy π, W π (s) = E ∞ t=0 γ t (R(s t , π(s t )) − G(s t , π(s t ))|s 0 = s) , where γ ∈ [0, 1) is the discount factor for future reward. The value of state s is the maximal cumulative reward, where Π is the set of all available policies. The policy that achieves the maximum in (13) is the optimal policy π * . It is shown in [5] that W * (s) is the optimal solution to the following optimization problem: Therefore, we can find W * (s) by solving (14) and compute π * (s) defined as arg max The optimal attack strategy is a mapping between system state s and the corresponding optimal action π * (s). An intruder can solve the MDP to obtain the strategy offline and then inject attacks accordingly in real-time operations.

IV. SIMULATION
We test our proposed method on the PJM 5-bus system. The basic system configuration and the generation bids, generation MW limits and MW loads are shown in Fig. 2. More details can be found in [10].    Fig. 2 are the base case loads. Another state for each load is half of its base case. The transition probability from one state to another is 0.5. 2) Measuring device transition probability. p T is set 0.5. The attack detection probability is calculated from (8).
3) Costs. The number of target buses at each time step is at most one. The reward weight of each line is 1. The cost g u is set as 0.05. 4) Discount factor. The discount factor γ = 0.95.
We solve the economic dispatch in MATPOWER toolbox in MATLAB. The power flow limit of each line is set 300 MW. We relax the constraint in economic dispatch from P ij ≤ P M ij to P ij ≤ 1.2P M ij . We set V max = 1.1 p.u. (per unit), V min = 1.0 p.u., n V = 5; ∆θ = 5 • , n θ = 10, θ max i and θ min i are determined from the actual values of bus i in eight load states. For each discretized state, we calculate the lower and upper bounds of each line power flow. One line can be an available target line if the upper bound of its power flow is below the power limit or the lower bound is over the limit.
We solve (14) and (15) to obtain the optimal actions for 2 3 × 2 3 = 64 states and compute the static distribution probabilities of all states. The attack probability of one line is computed as the sum of the distribution probabilities of the states under which the optimal action is to change the congestion pattern of that line. The intrusion probability of one device is the sum of the distribution probabilities of the states under which the optimal action requires manipulating partial or all measurement of that device. The results of the likelihood of data attacks are shown in Figs. 3 and 4. Generally, as C increases, the attack probability of each line and each measuring device decreases. When C = 0, it means the launched attack cannot be detected by network operators. In this case, the intruders always choose the action that brings about the maximal immediate net reward. When C ≥ 4, the net expected reward for each action is negative, hence the optimal action for all states is no attack.

V. CONCLUSION AND DISCUSSIONS
We for the first time analyze the likelihood of cyber data attacks to power systems. We model an intruder's attack strategy as a Markov Decision Process (MDP). We compute the optimal attack action at a given power system state from an intruder's perspective. We study the likelihood of cyber data attacks on a small system through simulation. One ongoing work is to apply the method to likelihood analysis of cyber data attacks on larger power systems.