Sparse Malicious False Data Injection Attacks and Defense Mechanisms in Smart Grids

This paper discusses malicious false data injection attacks on the wide area measurement and monitoring system in smart grids. First, methods of constructing sparse stealth attacks are developed for two typical scenarios: 1) random attacks in which arbitrary measurements can be compromised; and 2) targeted attacks in which specified state variables are modified. It is already demonstrated that stealth attacks can always exist if the number of compromised measurements exceeds a certain value. In this paper, it is found that random undetectable attacks can be accomplished by modifying only a much smaller number of measurements than this value. It is well known that protecting the system from malicious attacks can be achieved by making a certain subset of measurements immune to attacks. An efficient greedy search algorithm is then proposed to quickly find this subset of measurements to be protected to defend against stealth attacks. It is shown that this greedy algorithm has almost the same performance as the brute-force method, but without the combinatorial complexity. Third, a robust attack detection method is discussed. The detection method is designed based on the robust principal component analysis problem by introducing element-wise constraints. This method is shown to be able to identify the real measurements, as well as attacks even when only partial observations are collected. The simulations are conducted based on IEEE test systems.

SECTION I. Introduction

Compared with the traditional power grids, a smart grid tends to be much more reliable, efficient, and intelligent due to the remarkable advancements in sensing, monitoring, control technologies, and also the tight integration with cyber infrastructure and advanced computing and communication technologies [1]. However, this integration can lead to new vulnerabilities to cyber attacks on the power systems. Cyber attacks are reported as one of the main potential threats to the reliable operation of the power system [2], [3]. In this paper, we consider false data injection attacks (FDIAs) against the supervisory control and data acquisition (SCADA) system in smart grids.

A power grid transmission system is a sophisticated network which connects a number of electric power generators to various consumers through extensive power lines. It is extremely important to monitor the state of this complex system such that various control and planning tasks can be performed and the reliable operation of the power system is guaranteed. In power systems, state estimation [4], [5] is used to estimate system state variables through a number of power measurements and is a useful and necessary function in energy management systems (EMS).

The SCADA system obtains power status information such as transmission line power flows, bus voltages, and also circuit-braker signals through remote terminal units (RTUs). These measurements are then used for the state estimation process in EMS, which builds real-time electricity network models. In smart grids, the complex network connections as well as the Internet make SCADA systems susceptible to potential FDIAs, in which adversaries aim to contaminate the measurements collected from RTUs and bias the state estimation at the transmission level to mislead the operation of the power system. Fig. 1 presents a block diagram of the power grid, communication network, SCADA, and control center. It is critically important to understand the behavior of adversaries so that appropriate countermeasures can be designed to either protect the system from attacks beforehand or identify the malicious false data injections in the measurements.

Recently, the problem of FDIAs as well as countermeasures has attracted a lot of attention among researchers. False data in state estimation were first discussed by Schweppe et al. in their pioneering work about state estimation [6]. It was not well researched until Liu et al. [7] proposed that if adversaries possess the knowledge of power grid topology, they may inject coordinated data attacks, which could evade detection by the bad data detection (BDD) system in state estimator. Based on this strategy, plenty of efforts have been made to design effective attack algorithms and the corresponding countermeasures, such as [8]–​[11].

Adversaries may launch attacks through hacking RTUs such as sensors in substations. In consideration of the accessibility of RTUs and also hacking cost, attackers always tend to control only a few RTUs to implement a successful attack [7]. Kim and Poor [8] developed a general optimization framework-based formulation for constructing sparse attack vectors when a subset of measurements is protected, while Ozay et al. [12] extended the sparse attack construction model to a distributed framework. Sandberg et al. [13] considered sparse attacks with injections into critical measurements, which are essential for the observability of the power grids and sensitive to attacks. In [14], methods of finding both strong stealth attacks and also optimal weak malicious data attacks (when power grid topology is unknown) with the aim of reducing the number of compromised measurements were discussed. It has been proposed that even when the power grid information is unavailable, stealth attacks can still be accomplished [15], [16]. Zhang et al. [17] investigated the attack strategy with consideration of communication rate constraint in cyber–physical systems.

Fig. 1.

Illustration of the power grid, communication network, SCADA, and control center. The warning signs indicate the vulnerabilities to FDIAs.

There are two approaches to defend against the malicious data attacks. The first is to protect the system beforehand from being attacked by adversaries. This can be achieved by either protecting a number of measurements to prevent stealth attacks [18], [19], or monitoring state information directly by the deployment of phasor measurements units (PMU) [8], [20]. In practice, it is not feasible to secure all measurements to prevent attacks due to the high cost. Instead, stealth malicious attacks can be prevented by protecting a carefully selected subset of measurements. A challenge of this approach is to search the effective small measurement subset to make them immune to attacks. Bobba et al. [18] chose the subsets for small power test systems using brute-force search.

The second approach to deal with malicious attacks is to identify the injected false data in measurements and then either abandon the contaminated data or correct them. Traditional false data detection methods are based on residue test [6], [21]. They cannot protect state estimation from carefully designed stealth attacks. Recently, with the advancement of smart grid, new detection methods have been proposed. A survey of the existing detection methods was provided in [22]. In [14], generalized likelihood ratio test is introduced to detect weak FDIAs. The cumulative sum (CUSUM) test-based detection mechanism introduced in [16] is also designed for nonstealth attacks. Esmalifalak et al. [23] discussed stealth false data detection methods using machine learning. Graphical methods are used to design defending mechanisms in [24]. In [11], an effective method capable of detecting false data as well as recovering the real state information was proposed. In [25], both the attack and detection algorithms were discussed, but the subset protection method was not considered. Additionally, only preliminary results regarding the attack strategies were presented in [25]. This paper substantially discusses the methods of sparse attack construction, the strategy of system protection from attacks, and the algorithm of stealth attack detection.

This paper has made three contributions: First, methods of constructing stealth attacks are proposed for two typical scenarios. We consider a general scenario in which adversaries can access arbitrary measurements to change arbitrary state variables in state estimation. To the best of our knowledge, there is no feasible algorithm that can efficiently construct highly sparse undetectable attack vectors in this case. In [7], it is observed that the optimal undetectable attack vector to compromise the minimum number of measurements can be found using brute-force search. However, this is not practical due to the high complexity. We propose an efficient and effective attack vector construction algorithm which can quickly generate highly sparse attack vectors in this scenario.

Liu et al. [7] also have demonstrated that stealth attack vectors always exist when the number of measurements that can be contaminated exceeds a certain value. However, it is shown in this paper that our proposed method can launch stealth attacks by manipulating only a much smaller number of measurements with high probability. Additionally, stealth attacks in a specific scenario are also considered in this paper. An optimization-based algorithm is introduced to generate sparse targeted attack vectors to bias specified state variables with the consideration that a subset of measurements is protected.

A fast greedy search method is then proposed to quickly find a subset of measurements to be protected to defend against stealth attacks. This fast method can find a subset with the same size as brute-force search in nearly all cases. Finally, inspired by Liu et al. [11], we introduce a detection algorithm considering the noise case with partial observations. The proposed algorithm extends the method in [11] to address the problem of detecting stealth attacks as well as recovering true state information with only partially collected contaminated measurements. The performance of the proposed algorithms is investigated using IEEE test systems with software MATPOWER [26].

This paper is organized as follows. Section II introduces power system model and the stealth attack problem in state estimation. In Section III, proposed attack strategies for different scenarios are introduced. Section IV provides the measurement protection algorithm and Section V presents the false data detection method. Simulation results are presented in Section VI. Section VII concludes the paper.

SECTION II. Power Grid and Attack Model

In this paper, we consider a power transmission grid which consists of $n+1$ buses and $l$ transmission lines. The network connectivity of this power grid can be described by the $\left(n+1\right)\times l$ oriented incidence matrix $\mathbf{M}$, of which each column corresponds to the power line $(i,j)$ and consists of all 0s except the $i$th and $j$th elements having value of 1 and $-1,$ respectively [27]. The nonsingular diagonal matrix $\mathbf{D}\in\mathbb{R}^{l\times l}$ describes the physical properties of the transmission grid with diagonal entries equal to admittance of the transmission lines. SCADA collects measurements from RTUs such as bus voltages, bus power injections, and branch power flows from the power grid and sends them to the state estimator to estimate the state of the power system in the control center.

A. State Estimation

The state estimation problem is to use power measurements to timely estimate the state of the power system. Specifically, power system state refers to bus voltage angles $\theta$ and bus voltage magnitudes $V$. In the linearized dc power flow model [4 Ch. 2], bus magnitudes are assumed already known and are all close to unity. Additionally, phase angle at reference bus is set to zero radians; thus, estimation of only $n$ bus voltage angles $\left[\theta_{1},\theta_{2},\ldots,\theta_{n}\right]^{T}$ is required. The measurements have the following relationship with the state variables: $$\begin{equation}{\boldsymbol z}=\mathbf{H\theta+e}\end{equation}$$ where $\boldsymbol{z}=\left[z_{1},z_{2},\ldots,z_{m}\right]^{T}$ denotes measurement vector and $\mathbf{H}\in\mathbb{R}^{m\times n}$ is the measurement Jacobian matrix constructed by $\mathbf{H}=\left[\begin{array}{c}\mathbf{DM}^{T}\\\mathbf{MDM}^{T}\end{array}\right]$. $\mathbf{e}=\left[e_{1},e_{2},\ldots,e_{m}\right]^{T}$ represents the Gaussian measurement noise and it is assumed to be zero-mean for convenience [14]. Measurements include power flows on $l$ transmission lines and power injection at $n$ buses. In the dc power flow model, power from bus $i$ to $j$ can be approximated as $$\begin{equation}P_{ij}=\left(\theta_{i}-\theta_{j}\right)d_{ij}\end{equation}$$ where $d_{ij}$ is the admittance of the transmission line from bus $i$ to $j$. Thus, power flows on transmission lines are computed by $\mathbf{MDM}^{T}\theta$ and power injections at buses are obtained from $\mathbf{DM}^{T}\theta$.

The state vector can be estimated from measurements using the weighted least-square (WLS) method [4]. In particular, system states are estimated as $$\begin{equation}\mathbf{\hat{\theta}=}\left(\mathbf{H}^{T}\mathbf{WH}\right)^{-1}\mathbf{H}^{T}\mathbf{W}{\boldsymbol z}=\mathbf{K}{\boldsymbol z}\end{equation}$$ where diagonal weighting matrix $\mathbf{W}$ has diagonal entries equaling to the inverse of noise variances and $\mathbf{K}=\left(\mathbf{H}^{T}\mathbf{WH}\right)^{-1}\mathbf{H}^{T}\mathbf{W}$.

B. False Data Injection Attacks

Malicious false data can be injected by manipulating the RTU measurements to bias the estimated states. System measurements with malicious data becomes $$\begin{equation}\boldsymbol{z}_{\mathbf{ a}}={\mathbf{ H\theta}}+{\boldsymbol a}+\mathbf{e}\end{equation}$$ where $\boldsymbol{a}=\left[a_{1},a_{2},\ldots,a_{m}\right]^{T}$ denotes the attack vector.

Bad data in measurements can lead to incorrect state estimation and cause severe outcomes. Traditional methods to detect bad data are mostly based on the residue test. The residue vector $\boldsymbol{r}$ refers to the difference between the obtained measurements and the computed value from the estimated state $$\begin{equation}\boldsymbol{r=z}-\mathbf{H}\hat{\theta}.\end{equation}$$ For example, the largest normalized residue (LNR) test identifies bad data if the absolute value of the largest element in $\boldsymbol{r}$ is larger than a certain threshold $\tau$, i.e., $\max_{i}\left\vert r_{i}\right\vert > \tau$.

However, carefully designed malicious data attacks can bypass residue-based BDD. If attackers have knowledge about the power grid topology information, or $\mathbf{H}$, they can inject stealth attacks by constructing the attack vector such that [7] $$\begin{equation}\boldsymbol{a}=\mathbf{Hc}.\end{equation}$$ The measurements can then be written as $$\begin{equation}\boldsymbol{z}_{\mathbf{ a}}=\mathbf{H}\left(\mathbf{\theta}+{\boldsymbol c}\right)+\mathbf{e}\end{equation}$$ where $\boldsymbol{c}\in\mathbb{R}^{n}$ is any arbitrary vector and denotes the errors added to the state variables introduced by $\boldsymbol{a}$. The attack is undetectable as the residue $\boldsymbol{r}$ would not change compared to that without attack $\boldsymbol{a}$ [7]. The system will regard the manipulated state ($\mathbf{\theta}+{\boldsymbol c}$) as the real value in the state estimator.

SECTION III. Stealth Attack Strategies

In order to evade detection in the control center, attack vectors are designed to satisfy (6). Additionally, attackers would tend to compromise as few measurements as possible in effort to launch attacks with least effort. Therefore attack strategies are expected to be able to construct highly sparse attack vectors. The stealth sparse attacks were first discussed in [7], in which the authors proposed that attackers can modify state variables in state estimation without being detected by modifying a small number of carefully chosen RTU measurements. In this paper, two methods are introduced to construct sparse attack vectors for two typical scenarios: random attacks in which arbitrary measurements can be compromised and targeted attacks in which specific state variables need to be biased.

A. Random Attacks

In this scenario, it is assumed that no measurements are protected, and the changes of state variables are not specified. Attackers can hack arbitrary measurements to bias arbitrary state variables. Thus, the aim is solely to find highly sparse vector ${\boldsymbol{a}}$ that satisfies (6). To the best of our knowledge, there is no feasible algorithm that can efficiently construct sparse attack vectors in this case. Since ${\boldsymbol{a}}$ is a linear combination of the columns of $\mathbf{H}$, it is possible to generate sparse vector by column transformation of $\mathbf{H}$. However, this method cannot guarantee sparsity. It is demonstrated by Liu et al. [7] that a $k$-sparse stealth attack vector always exist if $k > m-n$. We propose a novel method that can construct a sparse attack vector with much smaller $k$.

Liu et al. [7] also proposed that a projection matrix $\mathbf{P=H}\left(\mathbf{H}^{T}\mathbf{H}\right)^{-1}\mathbf{H}^{T}$ can lead to an equivalent criterion to generate attack vector ${\boldsymbol{a}}$ satisfying (6) $$\begin{equation*}\begin{split}\mathbf{P}{\boldsymbol a}=\mathbf{H\left(\mathbf{H}^{T}{H}\right)^{-1}{H}^{T}}{\mathbf{ H}}{\boldsymbol c}={\mathbf{ H}}{\boldsymbol c}\\\mathbf{\left(P-I\right)}{\boldsymbol a}=0.\end{split}\end{equation*}$$ Let $\mathbf{B=P}-\mathbf{I}$, then undetectable attack vector $\boldsymbol{a}$ satisfies $$\begin{equation}\mathbf{B}{\boldsymbol a}=0.\end{equation}$$

This criterion can be used to generate attack vectors in certain scenarios such as when a subset of measurements is protected [7]. For random attacks, this criterion can also be utilized. A straightforward way to find sparse attack vectors can be formulated using the following optimization problem: $$\begin{equation}\begin{aligned}\min & \:\left\Vert \boldsymbol{a}\right\Vert _{0}\\ {\rm{ s.t.}} & \:\mathbf{B}{\boldsymbol a}=0,\:\boldsymbol{a}\neq0\end{aligned}\end{equation}$$ where $l_{0}$-norm is the number of the nonzero elements in $\boldsymbol{a}$. This is a nonconvex problem and finding the solution to this problem is highly complex. However, it is obvious that a feasible vector $\boldsymbol{a}$ must be in the null space of matrix $\mathbf{B}$, which is defined as $$\begin{equation}{\rm{ Null}}(\mathbf{B})=\left\{ \mathbf{v}\in\mathbb{R}^{m}\left\vert \mathbf{Bv}=0\right.\right\}.\end{equation}$$ Rather than solving the complex problem in (9), we propose an algorithm taking advantage of null space of $\mathbf{B}$, which can be easily computed.

Proposed algorithm. Measurements are always subject to noise due to the errors in the measuring process and the noise in the communication channels. The noise can be modeled as Gaussian distributed with variance $\Sigma_{e}$. The system is usually designed to be tolerant to measurement deviations within the noise level. Additionally, vectors in the null space of $\mathbf{B}$ usually comprise a small number of relatively large elements and the majority are small value elements. It provides the possibility for attackers to inject attack vectors designed based on vectors in ${\rm{ Null}}(\mathbf{B})$. Those small valued elements can be dealt with as noise if their average energy, denoted as $\Sigma_{B}$, is within the range of the variance of the noise $\Sigma_{e}$, namely $\Sigma_{B}\leq\Sigma_{e}$. Therefore, attackers only need to inject elements of large values in the column vectors of ${\rm{ Null}}(\mathbf{B})$ into the system and the number of measurements to be compromised will be greatly reduced. We define a shrinkage operation $\mathcal{S}_{t}$ as follows: $$\begin{equation}\mathcal{S}_{t}\left(x\right):=\begin{cases}\dfrac{x}{\left\vert x\right\vert -t}\max\left(\left\vert x\right\vert -t,\:0\right), & \left\vert x\right\vert \neq t\\\: x, & \left\vert x\right\vert =t.\end{cases}\end{equation}$$

The attack vector construction procedure can then be designed as follows. Given matrix measurement matrix $\mathbf{H}$, compute matrix $\mathbf{B}$ as well as the standard basis matrix $\mathbf{U}$ of its null space ${\rm{ Null}}(\mathbf{B})$ and choose vector $\boldsymbol{u}$ with the largest variance from all column vector in $\mathbf{U}$ $$\begin{equation}\boldsymbol{u}=\arg\max_{i}\left({\rm{ var}}\left(\mathbf{u}_{i}\right)\right)\end{equation}$$ where $\mathbf{u}_{i}$ denotes the $i$th column in $\mathbf{U}$. Then, scale vector $\boldsymbol{u}$ up, or down, till the maximal element reaches a designed attack value $C.$ The last step is to force the small elements below threshold $t$ to 0 $$\begin{equation}\mathbf{a}=\mathcal{S}_{t}\left(\epsilon\boldsymbol {u}\right)\end{equation}$$ where $\epsilon=\frac{C}{\max(\boldsymbol {u})}$.

Algorithm 1 concludes the whole process of attack vector construction. It is notable that threshold $t$ should be carefully chosen in the consideration of both sparsity and evading BDD. A higher $t$ can generate a sparser attack vector but also increase the possibility of being detected. It is also notable that if the noise is not zero-mean, the threshold $t$ is chosen according to the tolerable noise range. Since the measurement noise follows $\mathcal{N}(0,\,\sigma^{2})$, it is assumed that all noise variables are within the range of $[-3\sigma,\,3\sigma]$ (otherwise it will be identified as bad data). Thus, threshold $t$ should not exceed $3\sigma$. The following proposition can assist in choosing threshold $t$.

Algorithm 1 Sparse stealth attacks construction

Input: $\mathbf{H}\in\mathbb{R}^{m\times n}$, $C > 0$, $t > 0$.

Procedure:

1) Compute $\mathbf{B=\mathbf{H}\left(\mathbf{H}^{T}\mathbf{H}\right)^{-1}\mathbf{H}^{T}-I}$.

2) Get the standard basis matrix $\mathbf{U}$ of $Null(\mathbf{B})$ so that $i$-th column $\mathbf{u}_{i}$: $\mathbf{Bu}_{i}=0$.

3) Find column vector $\mathbf{u}$ in $\mathbf{U}$: $\mathbf{u}=\arg\max_{i}(var(\mathbf{u}_{i}))$.

4) Scale up/down vector $\mathbf{u}$ by $\epsilon$: $\mathbf{u^{\prime}}=\epsilon\mathbf{u}$ and $\epsilon=\frac{C}{\max(\mathbf{u})}$.

5) Shrink the vector using the threshold $t$ to obtain the sparse attack vector $\mathbf{a}$: $\mathbf{a}=\mathcal{S}_{t}\left(\mathbf{u}^{\prime}\right)$.

Output: $\mathbf{a}$.

Proposition 1:

If an attack vector $\boldsymbol {a}$ is constructed using Algorithm 1 with the shrinkage threshold $t$, the probability of successfully evading detection by residue-based detection algorithms in the system is at least $$\begin{equation}P_{l}(t)=\frac{1}{2}\left[1+{\rm{erf}}\left(\frac{3\sigma-t}{\sigma\sqrt{2}}\right)\right]\end{equation}$$ where $\rm{erf}(\cdot)$ refers to the Gauss error function and $\sigma$ is the standard deviation of the Gaussian measurement noise.

Proof:

Since the vector $\boldsymbol {u}$ is selected form $\rm{ Null(\mathbf{B})}$, it satisfies $\boldsymbol {u={\mathbf{ H}}c}$, where $\boldsymbol {c}\in\mathbb{R}^{n}$. Let $\boldsymbol{a}=\mathcal{S}_{t}\left(\epsilon\boldsymbol {u}\right)=\epsilon\boldsymbol {u}-\boldsymbol {u}_{t}$. The residual vector $\boldsymbol {r}^{\prime}$ when attack $\boldsymbol {a}$ is injected into system is calculated as $$\begin{equation}\begin{split}\boldsymbol {r}^{\prime}&= \boldsymbol {z}_{\mathbf{a}}-\mathbf{H\hat{\theta}_{\mathbf{a}}}=\boldsymbol {z+a}+{\mathbf{ e-}}\mathbf{HK}\boldsymbol{(z+a}+{\mathbf{ e)}} \\&= \mathbf{Hx+\epsilon H}{\boldsymbol c}-\boldsymbol {u}_{\mathit{t}}+\mathbf{e-H(KHx{+} K\epsilon H}{\boldsymbol c}{-}\mathbf{K}{\boldsymbol u}_{\mathit{t}}{+}\mathbf{Ke)}\\ &= \mathbf{Hx+\epsilon H}{\boldsymbol c}-{\boldsymbol u}_{\mathit{t}}+\mathbf{e-Hx-\epsilon H}{\boldsymbol c}+\mathbf{HK}{\boldsymbol u}_{\mathit{t}}-\mathbf{HKe}\\ &= \mathbf{(I-HK)(e-u_{\mathit{t}})}.\end{split}\end{equation}$$ Equation (15) indicates that when an attack generated by Algorithm 1 exists, it can be regarded that the random noise is perturbed by small amounts. A very small element comparing to $\sigma$ in $\boldsymbol {u}_{\mathit{t}}$ should not impact the noise level or the residue since the shifted noise variable is still within the tolerable range. To evaluate the probability of having no impact on noise level, we consider the worst case when all elements in vector $\boldsymbol {u}_{\mathit{t}}$ equal the threshold $t$. In this case, it can be viewed as that the noise level is shifted down by an amount of $t$. The shifted noise $\mathbf{e}^{\prime}$ follows $\mathcal{N}(-t,\,\sigma^{2})$. Therefore, the probability when the shifted noise variables are within the normal range of $[-3\sigma,\,3\sigma]$ can be computed by $$\begin{equation}P_{l}(t)=\intop_{-3\sigma}^{3\sigma}\frac{1}{\sigma2\pi}\exp\left(-\frac{\left(k+t\right)^{2}}{2\sigma^{2}}\right)dk.\end{equation}$$ This probability can be evaluated using (14). In fact, as a large number of elements in $\boldsymbol {u}_{\mathit{t}}$ tend to be much smaller than $t$, nondetection probability $P(t) > P_{l}(t)$. Thus, proposition 1 is proved.

B. Targeted Attacks

In practice, adversaries may intend to modify specific state variables. In this case, the amounts in the targeted subset in the vector $\boldsymbol {c}$ are fixed. Sparse attack vector construction methods for targeted attacks have been extensively explored in the literature, e.g., [7], [8], and [12]. Additionally, certain measurements may be protected, and adversaries would not be able to compromise these secured measurements. It is notable that protecting all measurements may not be feasible due to the high cost. Therefore, sparse attack vectors need to be carefully designed to contaminate specific state variables without compromising those protected measurements.

Let $\mathcal{I}$ denote the indices of state variables that are specifically attacked. $\mathcal{\bar{\mathcal{I}}}$ is the complementary set of $\mathcal{I}$ and denotes the indices of state variables that can be arbitrarily chosen to launch targeted attacks. Measurements Jacobian $\mathbf{H}$ is $\left[\mathbf{h}_{1},\mathbf{h}_{2},\ldots,\mathbf{h}_{n}\right]$ where $\mathbf{h}_{i}$ denotes the $i$th column vector of $\mathbf{H}$. A stealth attack vector $\boldsymbol {a}$ can then be written as $$\begin{equation}\boldsymbol {a}={\mathbf{ H}}{\boldsymbol c}=\sum_{i\in\mathcal{I}}\mathbf{h}_{i}c_{i}+\sum_{j\in\bar{\mathcal{I}}}\mathbf{h}_{j}c_{j}.\end{equation}$$ In a targeted attack, the value of $c_{i},\, i\in\mathcal{I}$ is fixed and predesigned to be injected into the state variables. Let $\boldsymbol {b}=\sum_{i\in\mathcal{I}}\mathbf{h}_{i}c_{i}$, which is predesigned by attackers. The attack vector $\boldsymbol {a}$ is then designed based on the fixed vector $\boldsymbol {b}$. As proposed in [7], (17) can be transformed using a projection matrix $\mathbf{P=H}\left(\mathbf{H}^{T}\mathbf{H}\right)^{-1}\mathbf{H}^{T}$. Since $\boldsymbol {a-b}=\mathbf{H}_{\bar{\mathcal{I}}}\boldsymbol {c}_{\bar{\mathcal{I}}}$, where $\mathbf{H}_{\mathcal{\mathcal{\bar{I}}}}$ denotes the submatrix of $\mathbf{H}$ containing columns with index in $\bar{\mathcal{I}}$, i.e., $\mathbf{H}_{\mathcal{\mathcal{\bar{I}}}}=\left[\mathbf{h}_{j_{1}},\mathbf{h}_{j_{2}},\ldots,\mathbf{h}_{j_{\left\vert \mathcal{\bar{I}}\right\vert }}\right],$ where $j_{i}\in\bar{\mathcal{I}}$ for $1\leq i\leq\left\vert \mathcal{\bar{I}}\right\vert$. By left-multiplying both sides with $\mathbf{P_{\bar{\mathcal{I}}}}$, we have $$\begin{equation}\begin{aligned}\mathbf{P_{\bar{\mathcal{I}}}}\boldsymbol {\left(a-b\right)}&= \mathbf{P_{\bar{\mathcal{I}}}}\mathbf{H}_{\bar{\mathcal{I}}}\boldsymbol {c}_{\bar{\mathcal{I}}} \\&= \mathbf{H}_{\bar{\mathcal{I}}}\left(\mathbf{H}_{\bar{\mathcal{I}}}^{T}\mathbf{H}_{\bar{\mathcal{I}}}\right)^{-1}\mathbf{H}_{\bar{\mathcal{I}}}^{T}\mathbf{H}_{\bar{\mathcal{I}}}\boldsymbol {c}_{\bar{\mathcal{I}}} \\&= \mathbf{H}_{\bar{\mathcal{I}}}\boldsymbol {c}_{\bar{\mathcal{I}}}=\boldsymbol {a-b}\end{aligned}\end{equation}$$ where $\mathbf{P_{\bar{\mathcal{I}}}}=\mathbf{H}_{\bar{\mathcal{I}}}\left(\mathbf{H}_{\bar{\mathcal{I}}}^{T}\mathbf{H}_{\bar{\mathcal{I}}}\right)^{-1}\mathbf{H}_{\bar{\mathcal{I}}}^{T}$.

We can then easily obtain that $\mathbf{\left(P_{\bar{\mathcal{I}}}-I\right)}{\boldsymbol a}=\mathbf{\left(P_{\bar{\mathcal{I}}}-I\right)}{\boldsymbol b}$, let $\mathbf{B}=\mathbf{P}-\mathbf{I}$, we have the following equivalent criteria for an attack vector $\boldsymbol {a}$ to be stealth $$\begin{equation}\mathbf{B}_{\bar{\mathcal{I}}}\boldsymbol {a}=\mathbf{B}_{\bar{\mathcal{I}}}\boldsymbol {b}\end{equation}$$ where $\mathbf{B}_{\bar{\mathcal{I}}}=\mathbf{P}_{\bar{\mathcal{I}}}-\mathbf{I}$.

Since a subset of measurements is protected, those elements in attack vector $\boldsymbol {a}$ should be restricted to 0. Let $\mathbf{y}=\mathbf{B}_{\bar{\mathcal{I}}}\boldsymbol {b}$, and assume that the $p$th measurement is secured, e.g., $a_{p}=0$. Applying the $l_{1}$-relaxation, the sparse attack vector can be obtained by solving the following optimization problem: $$\begin{equation}\begin{aligned}\min_{\mathbf{c}} & \left\Vert \mathbf{H}{\boldsymbol c}\right\Vert _{1} \\{\rm{ s.t.}} & \:\mathbf{\mathbf{B}_{\bar{\mathcal{I}}}\mathbf{H}}{\boldsymbol c}={\mathbf{ y}}\\ & \:\mathbf{H}^{p}\boldsymbol {c}=0\end{aligned}\end{equation}$$ where $\mathbf{H}^{p}$ denotes the $p$th row of matrix $\mathbf{H}$ and minimizing $l_{1}$-norm of a vector $\left\Vert \boldsymbol {v}\right\Vert _{1}=\sqrt{\sum_{i}\left\vert v_{i}\right\vert }$ can promote $\boldsymbol {v}$ to be sparse. This problem is well discussed in the field of compressive sensing [28] and can be quickly solved.

SECTION IV. Strategic Protection

Increasing the number of protected measurements can make the stealth attacks more difficult to be accomplished. It is obvious that stealth attacks can be completely prevented by securing all measurements. However, it is not economical or necessary to secure all measurement devices to defend against stealth attacks. Bobba et al. [18] explored the minimal measurement subset that is required to be protected to defend against attacks using brute-force search. This method is time-consuming and only feasible for small-sized power grids. In this section, an efficient algorithm is proposed to quickly find measurement protection subsets, which have the same sizes as that from brute-force method in nearly all cases.

Let the set $\mathcal{P}\subset\left\{ 1,2,\ldots,m\right\}$ be the measurement set that are secured and the complementary set $\bar{\mathcal{P}}$ denotes the index of those measurements that can be contaminated. Similar to (20), adversaries can construct the sparse attack vector $\boldsymbol {a}$ by solving $$\begin{equation}\begin{aligned}\min_{\boldsymbol {c}} & \left\Vert \mathbf{H^{\bar{\mathcal{P}}}}{\boldsymbol c}\right\Vert _{1} \\{\rm s.t.} & \mathbf{\mathbf{B}_{\bar{\mathcal{I}}}\mathbf{H}}{\boldsymbol c}={\mathbf y} \\ & \mathbf{H^{\mathcal{P}}}{\boldsymbol c}=0. \end{aligned}\end{equation}$$

If the protection set $\mathcal{P}$ is properly chosen, specific targeted attack vectors would not exist. Namely, (21) would have no solutions. Giving specified vector $\boldsymbol {c}_{\mathcal{I}}$, which is the targeted subset vector of $\boldsymbol {c}$, the straightforward method is to protect all measurements in the set corresponding to all nonzero elements in $\boldsymbol {a}$ that $\boldsymbol {a}=\mathbf{H_{\mathcal{I}}}{\boldsymbol c}_{\mathcal{I}}$. In this way, it probably requires a large number of measurements to be protected since $\boldsymbol {a}$ may not be desirably sparse. Finding or computing the smallest protection set that can prevent targeted attacks is difficult. The brute-force search method, which is discussed in [18], can guarantee finding the smallest possible sets. However, this method is extremely complex and not feasible in practice.

When a certain measurement is secured, attackers need to compromise more measurements or inject extra errors into the rest of the measurements to launch targeted attacks. From (17), we have $$\begin{equation}\boldsymbol {a=}\mathbf{H}\boldsymbol {c}=\boldsymbol {b+}\mathbf{H}_{\mathcal{\overline{I}}}\boldsymbol {c}_{\mathcal{\bar{I}}}\end{equation}$$ where $\boldsymbol {b}$ represents predesired injections. It is obvious that protecting certain measurements can always be more effective than others. For example, it is more important to secure the measurements corresponding to the nonzero elements in $\boldsymbol {b}$ than others. If a subset $\mathcal{P}$ of the total measurements is protected, we have $$\begin{align}\boldsymbol {a}_{\mathcal{P}} & =\boldsymbol {b}_{\mathcal{P}}+\mathbf{H}_{\mathcal{\bar{I}}}^{\mathcal{P}}\boldsymbol {c}_{\mathcal{\bar{I}}}=0\\-\boldsymbol {b}_{\mathcal{P}} & =\mathbf{H}_{\mathcal{\bar{I}}}^{\mathcal{P}}\boldsymbol {c}_{\mathcal{\bar{I}}}.\end{align}$$ If the rank of $\mathbf{H}_{\mathcal{\bar{I}}}^{\mathcal{P}}$ is smaller than protection size $\left\vert \mathcal{P}\right\vert$, and the augmented matrix with vector $\boldsymbol {b}_{\mathcal{P}}$ can increase the rank, namely ${\rm{ rank}}\left(\left[\mathbf{H}_{\mathcal{\bar{I}}}^{\mathcal{P}}\vert \boldsymbol {b}_{\mathcal{P}}\right]\right)={\rm{ rank}}\left(\mathbf{H}_{\mathcal{\bar{I}}}^{\mathcal{P}}\right)+1$, then $\boldsymbol {c}_{\mathcal{\bar{I}}}$ satisfying (24) does not exist, indicating that the system is successfully protected from targeted attacks with $\boldsymbol {b}$. Otherwise, when vector $\boldsymbol {b}_{\mathcal{P}}$ cannot increase the rank of matrix $\mathbf{H}_{\mathcal{\bar{I}}}^{\mathcal{P}}$, i.e., ${\rm{ rank}}\left(\left[\mathbf{H}_{\mathcal{\bar{I}}}^{\mathcal{P}}\vert \boldsymbol {b}_{\mathcal{P}}\right]\right)={\rm{ rank}}\left(\mathbf{H}_{\bar{\mathcal{I}}}^{\mathcal{P}}\right)$, there exist solutions of $\boldsymbol {c}_{\mathcal{\bar{I}}}$, which means that adversaries can still find attack vectors to launch targeted attacks. The problem is then to find the best solution to obtain highly sparse $\boldsymbol {a}$. It is known from (22) that making a certain subset $\mathcal{P}$ of the measurements immune to attacks can result in an attack vector $\boldsymbol{a}$ which contaminates more state variables. This makes the attacks more difficult to be accomplished. Therefore, it can be deduced that protecting certain measurement would result in a larger $\left\Vert \boldsymbol {a}\right\Vert _{1}$ value than that of protecting another measurement. Protecting these measurements would be more effective than others and these measurements can be regarded as critical measurements to targeted attacks. Based on this idea, giving specified targeted state bias vector $\boldsymbol {c}_{\mathcal{I}}$, we can design a greedy method to search a small subset of these measurements to be protected to defend from targeted attacks.

Algorithm 2 presents the greedy search method to find a small protection subset of measurements with the knowledge of existing protection set and targeted vector $\boldsymbol {c}_{\mathcal{I}}$. At each iteration, the algorithm assume that one more measurement is protected and check the feasibility of constructing attack vector $\boldsymbol {a}$. If the stealth attack vector exists when every measurement is protected one by one, the algorithm increases the protection set by selecting the most important measurement, which leads to the largest value of $\left\Vert \boldsymbol {a}\right\Vert _{1}$ when it is protected. The selection process continues until stealth targeted attack vector does not exist.

SECTION Algorithm 1 Greedy subset searching Algorithm

Input: $\mathbf{H}$, $\mathcal{I}$, $\mathbf{c}_{\mathcal{I}}$, $\mathcal{P}$.

Initialize: $\mathbf{B}_{\bar{\mathcal{I}}}=\mathbf{H}_{\bar{\mathcal{I}}}\left(\mathbf{H}_{\bar{\mathcal{I}}}^{T}\mathbf{H}_{\mathcal{\bar{\mathcal{I}}}}\right)^{-1}\mathbf{H}_{\bar{\mathcal{I}}}^{T}-\mathbf{I}$, $\mathbf{y}=\mathbf{B}_{\bar{\mathcal{I}}}\mathbf{H}_{\mathcal{\mathcal{I}}}\mathbf{c}_{\mathcal{I}}$, $\mathcal{P}^{\prime}=\mathcal{P}$, $k=1$, $\mathcal{P}_{k}=\mathcal{P}^{\prime}$.

Iteration: At the $k$-th iteration:

Compute the complementary set $\mathcal{\bar{P}}$ of $\mathcal{P}^{\prime}$.

$\mathbf{For}$ $i=1:\left\vert \mathcal{\bar{P}}\right\vert$

Put the $i$-th entry in $\mathcal{\bar{P}}$ into $\mathcal{P}_{k}$: $\mathcal{P}_{k}=\mathcal{P}^{\prime}\cup\mathcal{\bar{P}}_{i}$.

Checking the feasibility of finding $\mathbf{c}$ from equation (21).

$\mathbf{If}$ feasible

Compute $\chi_{i}=\left\Vert \mathbf{Hc}\right\Vert _{1}$.

$\mathbf{else}$

$\mathcal{P}^{\prime}=\mathcal{P}_{k}$; Quit the iteration.

$\mathbf{end}$

$\mathbf{end}$

Find index $i$ such that $\chi_{i}$ has the largest value.

Update set $\mathcal{P}^{\prime}=\mathcal{P}^{\prime}\cup\mathcal{\bar{P}}_{i}$.

Output: $\mathcal{P}^{\prime}$.

For a large power grid system, it is not feasible to find the smallest protection subset to prevent any of undetectable attacks that satisfy $\boldsymbol {a=}\mathbf{H}\boldsymbol {c}$ by brute-force search. Instead, we can protect the union set of those subsets selected for protecting every single state variable. Our proposed method can quickly find a small subset that protect the whole system from any stealth attacks satisfying (6). The search procedure can be concluded in Algorithm 3.

SECTION Algorithm 3 Minimal subset selection algorithm

Input: $\mathbf{H}$.

Initialize: $\mathcal{P}=0$.

$\mathbf{For}$ $i=1:n$

Let $\mathcal{I}=\left\{ i\right\}$.

Find $\mathcal{P}_{i}$ using Algorithm 2.

$\mathbf{end}$

$\mathcal{P=P}_{1}\cup\mathcal{P}_{2}\cup\ldots\cup\mathcal{P}_{n}$.

Output: $\mathcal{P}$.

This method cannot guarantee the smallest subset that can be found, but it provides at least a quasi-optimal subset that contains a slightly larger number of elements. Most importantly, this method is fast and feasible in practice. In the worst case, to find a protection set with $k$ elements, the algorithm needs to test the feasibility $\mathcal{K}_{a}$ times $$\begin{equation}\mathcal{K}_{a}=mk-\frac{k\left(k-1\right)}{2}.\end{equation}$$ This figure is much smaller than that using brute-force method, where it needs to test $\sum_{i=1}^{k-1}\binom{m}{i}+1$ combinations in the best case to find the protection set with $k$ elements. Although our proposed algorithm may not find the global optimum solution, it provides some flexibility. When it is not possible to protect certain selected measurement device in practice, the algorithm can find a suboptimal subset instead.

SECTION V. Robust Detection

Traditional residue testing-based false data detection methods cannot provide protection of state estimation from carefully designed stealth attacks. Therefore, new detection methods need to be designed to detect random errors as well as stealth attacks. It is shown that a series of measurement data exhibit low rank and sparse structure, which can be employed in anomaly detection method [11]. In practice, measurements tend to be contaminated with noise. Additionally, it may also happen that some of the measurements are lost due to the measurement device failures or disrupted communication links. In this section, these situations are addressed.

Considering a time interval $T$, the power system obtains a series of measurements $\left[\mathbf{z_{a}}_{1},\mathbf{z_{a}}_{2},\ldots,\mathbf{z_{a}}_{T}\right]$ at the time instants ${t}_{1}, {t}_{2}, \ldots,{t}_{T}$. These measurements can form a matrix $\mathbf{Z_{a}}\in\mathbb{R}^{m\times T}$, which can be decomposed as $$\begin{equation}\mathbf{Z_{a}=Z+A+E}\end{equation}$$ where $\mathbf{Z}\in\mathbb{R}^{m\times T}$ is the block of true measurements with each column $\mathbf{z}_{i}$ representing true measurements at time ${t}_{i}$, $\mathbf{A}\in\mathbb{R}^{m\times T}$ denotes the attack matrix formed by all instant sparse attacks, and $\mathbf{\mathbf{E}}$ represents the noise.

It is known that fast system dynamics are usually well damped in the power system. This implies that the system states would change gradually in a small period $T$, making the matrix $\mathbf{Z}$ typically low rank. Additionally, malicious injection data matrix $\mathbf{A}$ tends to be sparse. This is due to the fact that some of the measurements may be protected and also because attackers would launch attacks with least effort. Given corrupted measurements matrix $\mathbf{Z_{a}}$, it is possible to recover low-rank matrix $\mathbf{Z}$ and sparse-attack matrix ${\mathbf{A}}$ by performing low rank and sparse decomposition, which is well discussed in the robust principle component analysis (PCA) problem [29], which solves $$\begin{equation}\begin{aligned}\min & \left\Vert \mathbf{Z}\right\Vert _{*}+\lambda\left\Vert \mathbf{A}\right\Vert _{1}\\ {\rm{ s.t.}} & \left\Vert \mathbf{Z_{a}}-\mathbf{Z-A}\right\Vert _{F}\leq\delta\end{aligned}\end{equation}$$ where $\left\Vert \cdot\right\Vert _{*}$ denotes the nuclear norm, $\left\Vert \cdot\right\Vert _{F}$ denotes the Frobenius norm, $\delta$ represents a small positive noise bound, and $\lambda$ is the regulation parameter. This problem is also addressed in compressive sensing and matrix completion [30] literature. Thus, true measurements can be recovered and the sparse perturbations including malicious attacks and other false data can also be identified.

Unlike coordinated malicious attacks, the missing data in the measurements can result in residue changes in (5). These incomplete measurement data, as well as the measurements with errors, would be identified as bad data by traditional BDD algorithms. The proposed algorithm can not only detect the missing and inaccurate measurement data but also detect the carefully designed stealth attacks, which is undetectable to traditional methods. More importantly, the proposed algorithm can recover the true measurements from the incomplete measurements.

In order to address the problem that only noise-contaminated partial measurements are collected, the PCA problem can be extended to the following form with element-wise error constraints: $$\begin{equation}\begin{aligned}[b]\min & \left\Vert \mathbf{Z}\right\Vert _{*}+\lambda\left\Vert \mathbf{A}\right\Vert _{1} \\{\rm s.t.} & \left\vert \mathcal{P}_{\Omega}\left(\mathbf{Z_{a}}\right)-\mathcal{P}_{\Omega}\left(\mathbf{Z+A}\right)\right\vert \preceq\epsilon \end{aligned}\end{equation}$$ where $\preceq$ represents element-wise inequality and $\mathcal{P}_{\Omega}\left(\cdot\right)$ denotes a projection operation, in which all elements outside the set $\Omega$ are forced to 0. $\epsilon$ is the matrix of entry-wise error bounds. It is demonstrated in [31] that this problem is equivalent to the following problem: $$\begin{equation}\begin{aligned}\min & \left\Vert \mathbf{Z}\right\Vert _{*}+\lambda\left\Vert \mathcal{T}(\mathbf{A},\tilde{\epsilon})\right\Vert _{1}\\{\rm{ s.t.}} & \mathbf{\, Z_{a}=Z+A} \end{aligned}\end{equation}$$ where $\tilde{\epsilon}$ has the same value as $\epsilon$ in the projection set $\Omega$ and infinite outside set $\Omega$, and the soft thresholding operation $\mathcal{T}_{\epsilon}\left(a_{ij}\right)$ is defined as $$\begin{equation}\mathcal{T}\left(a_{ij},\epsilon\right)={\rm{sign}}\left(a_{ij}\right)\cdot\max\left\{ \left\vert a_{ij}\right\vert -\epsilon,0\right\}.\end{equation}$$

Fig. 2.

Probabilities of successful attack injections (a) under different SNRs for IEEE-57 bus system, SR is 0.4; (b) for different bus systems, SR is 0.4 and $\rm{ SNR=10\,dB}$; (c) for different SRs in IEEE-57 bus system, $\rm{ SNR=10\,dB}$. (c) This figure utilizes random columns in $\rm{ Null(\mathbf{B})}$ rather than that with largest variance.

A variant of the augmented Lagrangian method (ALM), which is also known as the alternating direction method of multipliers (ADMM) algorithm [32], is used to solve the problem defined by (29). The Lagrangian corresponding to this problem is $$\begin{align}\mathcal{L}\left(\mathbf{Z,A,Y,}\mu\right)=\left\Vert \mathbf{Z}\right\Vert _{*}+\lambda\left\Vert \mathbf{\mathcal{T}(\mathbf{A},\tilde{\epsilon})}\right\Vert _{1}+\left\langle \mathbf{Y,H}\right\rangle +\frac{\mu}{2}\left\Vert \mathbf{H}\right\Vert _{2}^{2}\end{align}$$ where $\left\langle \cdot\right\rangle$ denotes the Frobenius product, $\mathbf{H=Z_{a}-Z-A}$ and $\mu > 0$. $\lambda$ can be set to $\sqrt{m/\left\vert \Omega\right\vert }$. We further define the singular-value thresholding operation as $$\begin{equation*}\mathcal{D}\left(\mathbf{X},\tau\right)=\mathbf{U}\mathcal{T}\left(\Sigma,\tau\right)\mathbf{V}^{T}\end{equation*}$$ where $\tau$ is the threshold and $\mathbf{X=U\Sigma V}^{T}$. It is notable that ADMM updates $\mathbf{Z,A,Y}$ separately only once in each iteration, so it is efficient. The convergence of the whole algorithm is analyzed in [32], which states that the condition for convergence requires $\sum_{1}^{\infty}\mu_{k}^{-1}=+\infty$ where $\mu_{k}$ denotes the value of $\mu$ in the $k$th iteration. The whole process of solving (29) is shown in Algorithm 4.

SECTION Algorithm 4 RPCA with entry wise constraints

Input: $\mathbf{Z_{a}^{{\rm{{p}}}}=}\mathcal{P}_{\Omega}\left(\mathbf{Z_{a}}\right)\in\mathbb{R}^{m\times T}$, $\tilde{\epsilon}\in\mathbb{R}^{m\times T}$, $\lambda$.

Initialize $\mathbf{Z}=\mathbf{0}$, $\mathbf{A=0}$, $\mathbf{Y=0}$, $\mu > 0$, $\rho > 1$, $k=0$.

$\mathbf{while}$ not converged

1) Update the value of low rank matrix $\mathbf{Z}_{k+1}$:

$\mathbf{Z}_{k+1}=\mathcal{D}\left(\mathbf{Z_{a}^{{\rm{{p}}}}-A_{{\rm{{k}}}}+\frac{Y_{{\rm{{k}}}}}{\mu_{{\rm{{k}}}}}},\mu_{k}^{-1}\right)$.

2) Compute the value of sparse matrix $\mathbf{A}_{k+1}$ by minimizing:

$F\left(\mathbf{A}\right)=\frac{\lambda}{\mu}\left\Vert \mathcal{T}\left(\mathbf{A},\tilde{\epsilon}\right)\right\Vert _{1}-{\rm{tr}}\left(\frac{\mathbf{Y}_{{\rm{{k}}}}}{\mu_{k}}\left(\mathbf{A-\left(Z_{a}^{{\rm{{p}}}}-Z_{{\rm{{k}}}}\right)}\right)\right)+\frac{1}{2}\left\Vert \mathbf{A-\left(Z_{a}^{{\rm{{p}}}}-Z_{{\rm{{k}}}}\right)}\right\Vert _{F}$.

3) Update the Lagrange multiplier $\mathbf{Y}$:

$\mathbf{Y}_{k+1}=\mathbf{Y}_{k}+\mu_{k}\left(\mathbf{Z_{a}^{{\rm{{p}}}}-Z}_{k+1}\mathbf{-A}_{k+1}\right)$.

4) Update $\mu_{k+1}=\rho\cdot\mu_{k}$.

5) Update $k=k+1$.

$\mathbf{end\; while}$

$\mathbf{Return}$ $\mathbf{Z}$, $\mathbf{A=}\mathcal{T}(\mathbf{A},\tilde{\epsilon})$.

Output $\mathbf{Z}$, $\mathbf{A}$.

It is notable that when incomplete measurements are collected, Algorithm 4 will take the missing data to be sparse anomalies and it can also recover the low-rank true measurement matrix and sparse anomaly matrix. However, the recovery accuracy would be impacted as the sparsity is changed. The recovered sparse attack matrix can ignore those injected data outside the observation set. Thus, it is more difficult to identify all malicious attacks with partial observations.

SECTION VI. Numerical Results

In this section, the algorithms introduced above are evaluated by simulations performed based on the IEEE test systems [33]. The MATLAB package MATPOWER [26] is used to simulate the power system. The convex optimization problems are solved using the convex optimization toolbox CVX [34].

A. Performance of Stealth Attack Construction

The performance of Algorithm 1 which generates highly sparse undetectable attack vectors is tested in different scenarios. Figs. 2 and 6 show the probabilities of successfully generating undetectable attack vectors with different levels of sparsity and different attack level ratios (ALRs), respectively. An attack is regarded as successful when the maximum value in residue vector does not exceed that without attacks. Sparsity ratio (SR) is defined as $k/m$, where $k$ is the number of nonzero elements in $\boldsymbol{a}$ and $m$ is the size of $\boldsymbol{a}$. The ALR is defined as the maximum attack value $C$ to the mean value of the state variables: $\frac{C}{{\rm{ mean}}\left(\theta\right)}$. Generally, these figures reveal that there are high probabilities for Algorithm 1 to successfully generate highly sparse undetectable attacks.

The noise in the simulation is modeled as Gaussian distributed with zero-mean. The signal-to-noise ratio (SNR) indicates the noise level compared with true measurements in the simulation. The noise may be due to measuring devices and process, or due to the communication channel noise. It is clear in Figs. 2(a) and 6(a) that in a relatively noisy case, the probability of a successful attack is extremely high (close to 1). In the low noise case, there is also high probability of injecting a successful highly sparse undetectable malicious attack. The algorithm is also assessed using different power grid system models, which is shown in Figs. 2(b) and 6(b). It is notable that in a larger bus system, Algorithm 1 can provide a better performance even for extremely sparse attacks and high ALRs. For example, the success ratio is around 90% for IEEE 118-bus system to generate stealth attacks with SR lower than 0.1, compared with 75% for IEEE 14-bus system shown in Fig. 2(b). This probability is 100% for IEEE 118-bus system to generate attacks with $\rm{ ALR=1}$ compared to 80% for IEEE 57-bus system shown in Fig. 6(b). Therefore, it can be anticipated that the algorithm would have a better performance in a real power system, which is much larger than the tested systems.

Additionally, it can be seen from Fig. 2 that it is always harder to inject sparser attacks while Fig. 6 reveals that attacks with higher values would be more likely to be detected. Figs. 2(c) and 6(c) display the performance when injecting attacks with different SRs and ALRs. It is notable that in Fig. 6(c), the algorithm utilizes randomly selected columns in a basis matrix of ${\rm{ Null}}(\mathbf{B})$ rather than that with the largest variance. The results imply that using randomly chosen columns can also successfully inject undetectable attacks with high probabilities.

It is known that stealth attacks having $m-n$ nonzero entries can always be found. In IEEE 57-bus system, this figure is 80, for which the SR is about $59\%$. However, by using Algorithm 1, there is still a high probability that attackers can inject undetectable attacks with SRs lower than $59\%$. Even for an attack with SR lower than 0.05, the success rate is still around $80\%$ when the SNR is 10 dB and ALR is 0.5.

Fig. 3.

Sparsity of $\boldsymbol{a}$ under different attack conditions.

TABLE–I Number of Measurements in Protection Sets From Two Methods

Fig. 4.

Number of protected measurements to protect every single state variable from being targeted. (a) IEEE-9 bus system. (b) IEEE-14 bus system.

TABLE–II Number of Testing Times for Two Algorithms to Find Protection Subsets

Fig. 5.

Probability of successful false data detection.

TABLE–III Detection Probability and Measurements Deviation with Partial Observations

Targeted attack construction method in (20) is assessed under different attack conditions in which different percentage of total state variables are assumed to be modified. The targeted set is randomly selected and the protected measurement is also randomly chosen. It can be observed from Fig. 3 that, in order to precisely alter specified state variables, the coordinated attack vectors cannot be highly sparse. Thus, attackers need to compromise a number of measurements to launch targeted attacks. Highly sparse attacks can only be achieved when the percentage of targeted state variables is extremely low for certain test systems. For example, SR can be less than 0.1 for IEEE 39-bus system when a small number of state variables are targeted. The figure also shows that in some cases, SR of attacks are 0. They correspond to the cases that: for certain targeted set of state variables, no feasible attack vectors exist when the $p$th measurement is protected. Therefore, it implies that when certain carefully selected measurements are protected, attackers may not be able to inject targeted attacks.

B. Performance of Strategic Protection

This section evaluates our proposed protection algorithm. To compare the protection subset generated by the proposed algorithm with that from brute-force method, we apply IEEE-9 bus system, which contain 17 total measurements, and IEEE-14 bus system with 33 total measurements. Table I shows the number of measurements in protection subset found by two methods. The results from the proposed algorithm for other larger test systems are also provided. In the first two test systems, the smallest protection sets generated from the proposed algorithm contain only slightly more measurements than that from brute-force method. In IEEE-14 bus system, the difference of this number is quite small compared to the total number of 33 measurements. Thus, Algorithm 2 can find protection subsets with similar number of elements but spend much less time than brute-force method.

Fig. 6.

Probabilities of successful attack injections (a) under different SNRs for IEEE-57 bus system, ALR is 0.5; (b) for different bus systems, ALR is 0.5 and $\rm{ SNR=10\,dB}$; and (c) for different ALRs for IEEE-57 bus system, $\rm{ SNR=10\,dB}$.

Fig. 4 displays the number of elements in the smallest protection subsets to protect every single state variable from being targeted by adversaries. The whole system protection subsets shown in Table I are the unions of the protection subsets for protecting single variables. From both figures, it can be seen that in most cases the proposed algorithm can find a protection subset having the same size as that found by brute-force method. The size differences are only 1 or 2 when the two methods find subsets with different number of elements. This number is quite small compared with the total number of 33 measurements in IEEE-14 bus.

Table II compares the complexities of the two algorithms in terms of the number of feasibility testing times. The results correspond with the simulation shown in Fig. 4 in which measurement protection subsets are searched for protecting every single state variable. It is obvious that when the size of protection subset exceeds 3, the difference of the two methods becomes significant. This difference is more significant when the size of protection subset is bigger as the brute-force search needs to exhaust all subset combinations with smaller sizes. It is also clear that in a larger power system, the difference is much larger for two algorithms to find a subset with same size as that in a smaller system. The testing times of the proposed algorithm will increase only slightly when the size of protection subset and the system scale grow, which is also described by (25). In a real power system, while brute-force method is infeasible because of the combinatorial complexity, the proposed method instead is fast and practical.

C. Performance of Detection

The performance of the detection algorithm is tested on IEEE 14-bus system and IEEE 57-bus system. The malicious attack vectors are constructed using our proposed Algorithm 1. In order to obtain sparsity in the rows of the attack block matrix, different column vectors in the null space in Algorithm 1 are utilized. The SR of the attacks is chosen as 15%. In Fig. 6(c), it is shown that when $\rm{ SR=0.15}$, traditional residual testing-based algorithms will not be able to detect those attacks. Thus, in the simulation, the algorithm is not compared with traditional methods. Additionally, recently proposed algorithms such as [23] do not deal with partial observations. These algorithms do not address the problem of error contaminated measurements as well. The detection method discussed in this paper addresses both problems. Most importantly, it can not only detect anomalies but also recover the true measurements from partial-contaminated observations.

We use the false alarm rate (FAR) which is the probability of positive alarm when there are no attacks. The noise performance of the algorithm compared to RPCA with Frobenius constraints in (27) has been extensively studied in [31]. In this paper, we focus on identifying anomalies in different scenarios when undetectable attacks are injected in power systems.

Fig. 5 shows the error tolerance performance in the IEEE 14-bus system. It is shown that when FAR exceeds 10%, the algorithm can identify attacks with high probabilities which are approaching 100%. This probability is still quite high in the presence of highly dense noise (95%). When FAR decreases, the system will absorb more noise and detection probability decreases. It can be seen that there is still a high chance of detecting anomalies: more than 90% when FAR decreases to an extremely low level (0.025) under $\rm{ SNR=10\,dB}$.

In the case where partial measurements are collected, missing data are regarded as sparse anomalies in Algorithm 4. Additionally, nonzero entries in sparse matrix $\mathbf{A}$ can only be confirmed as attacks when they are located in the observation set. This make identifications of attacks more difficult. Algorithm 4 can circumvent this problem since it also recovers the block of true measurements. We evaluate the attack detection probabilities as well as the deviation rate of the recovered measurement variables, which is defined as $\left\Vert \mathbf{z-z^{\prime}}\right\Vert _{2}/\left\Vert \mathbf{z}\right\Vert _{2}$. Table III shows the results when incomplete measurements are collected based on the IEEE 57-bus system. The FAR equals 0.05 and SNR is set to 8 dB. It can be seen that attack detection probability declines greatly with increasing missing observations. However, the recovered measurement variables experience only small deviations. Therefore, the proposed algorithm can successfully verify the true measurements, even in the situation that only partial measurements are observed (Fig. 6).

SECTION VII. Conclusion

In this paper, we looked into the problem of malicious FDIAs in power grid state estimation. We proposed stealth attack construction strategies for different scenarios and also introduced the countermeasures. It is shown that our proposed random attack construction algorithm can generate extremely sparse attack vectors. These optimal or quasi-optimal attacks can be achieved with high probability of success. The targeted undetectable attacks are obtained based on a optimization framework. The results show that attack vectors in this scenario cannot be extremely sparse, which is also discussed in literature. An efficient protection scheme is proposed in this paper to find an effective measurement protection subset to defend from the stealth attacks. The simulation results reveal that this subset searching algorithm can find a subset with almost the same size as that from the brute-force method. Additionally, a detection algorithm is introduced to detect the stealth attacks as well as other false data. This algorithm considers the case in which only partial measurements are collected in the presence of noise. The performance is demonstrated via the simulation results based on IEEE test power systems.

ACKNOWLEDGMENT

The authors would like to thank their colleagues at Toshiba Research Europe Ltd., for the fruitful discussions and the support of its directors.