1

EXPOSE the Line Failures following
a Cyber-Physical Attack on the Power Grid

S. Soltan is with the Department of Electrical Engineering, Princeton
University, NJ, 08544, and G. Zussman is with the Department of Electrical
Engineering, Columbia University, New York, NY, 10027.
E-mails: ssoltan@princeton.edu, gil@ee.columbia.edu

Power Grid
Physical Infrastructure
Supervisory Control and Data
Acquisition (SCADA) system

Recent cyber attack on the Ukrainian grid in December
2015 [1] demonstrated the vulnerability of power grids to
cyber attacks. As indicated in the aftermath report of the
attack [1], once the attackers obtain access to the grid’s
Supervisory Control And Data Acquisition (SCADA) system,
they can delete, modify, and spoof the data as well as remotely
change the grid’s topology by activating the circuit breakers.
The power grid infrastructure is also vulnerable to physical
attacks. Such an attack occured in April 2014 in San Jose,
California, when snipers tried to shut down a substation simply
by shooting at its transformers [2]. Hence, a physical attack
on the power lines and the measurement devices can have a
similar affect to a cyber attack.
To analyze these vulnerabilities, in this paper, we study
cyber-physical attacks that affect both the power grid physical
infrastructure and its SCADA system. Fig. 1 shows the main
components of the power grids. An adversary can attack the
grid by damaging the power lines and measurement devices
with a physical attack, by remotely disconnecting the lines
and erasing the measurements data with a cyber attack, or by
performing a combination of the both.
Independent of the attack strategy, we assume that an adversary attacks an area by: (i) disconnecting some lines within

IED

IED

Data Conc.

IED

Data Conc.
Command

I. I NTRODUCTION

IED

Data

Index Terms—AC Power Flows, State Estimation, Line Failures
Detection, Cyber Attack, Physical Attack.

IED

Command

Abstract—Recent attacks on power grids demonstrated the
vulnerability of the grids to cyber and physical attacks. To analyze this vulnerability, we study cyber-physical attacks that affect
both the power grid physical infrastructure and its underlying
Supervisory Control And Data Acquisition (SCADA) system. We
assume that an adversary attacks an area by: (i) disconnecting
some lines within that area, and (ii) obstructing the information
(e.g., status of the lines and voltage measurements) from within
the area to reach the control center. We leverage the algebraic
properties of the AC power flows to introduce the efficient
EXPOSE Algorithm for detecting line failures and recovering
voltages inside that attacked area after such an attack. The
EXPOSE Algorithm outperforms the state-of-the-art algorithm
for detecting line failures using partial information under the
AC power flow model in terms of scalability and accuracy. The
main advantages of the EXPOSE Algorithm are that its running
time is independent of the size of the grid and number of line
failures, and that it provides accurate information recovery under
some conditions on the attacked area. Moreover, it approximately
recovers the information and provides the confidence of the
solution when these conditions do not hold.

Data

arXiv:1709.07399v1 [] 21 Sep 2017

Saleh Soltan, Member, IEEE, and Gil Zussman, Senior Member, IEEE

Control Center

Fig. 1: The main components of the power grid. The Intelligent
Electronic Devices (IED) measure voltage magnitudes and phase
angles, and send these information via Data Concentrators to the
Control Center.

that area (failed lines), and (ii) obstructing the information
(e.g., status of the lines and voltage measurements) from
within the area to reach the control center. We call this area,
the attacked zone. Our objective is to detect the failed lines
and recover the voltages inside the attacked zone using the
information available outside of the attacked zone as well
as the information before the attack. An example of such an
attack on the IEEE 300-bus system is depicted in Fig. 2.
We studied a similar attack scenario in [3] using the linearized DC power flows. In a recent extension [4], the methods
in [3] were modified to statistically recover the information
under the AC power flows. However, due to the inaccuracy of
the DC power flows, the methods in [4] could not guarantee
the correct information recovery under the AC power flows.
In this paper, we directly leverage the properties of the nonlinear AC power flows to detect the line failures and recover
the voltages after an attack with guarantee of performance.
In particular, we prove that if there is a matching between
the nodes (buses) inside and outside of the attacked zone that

2

covers all the nodes inside the attacked zone, the voltages can
be accurately recovered by solving a set of linear equations.
Moreover, given the successful recovery of the voltages, we
prove that if the attacked zone is acyclic (i.e., lines in the
attacked zone do not form any cycles), then the failed lines
can be accurately detected by solving a set of linear equations.
We extend these results and show that given the successful
recovery of the voltages, the failed lines can still be accurately
detected by solving a Linear Program (LP), even if the attacked
zone is not acyclic. We further show that even if there is no
matching between the nodes inside and outside of the attacked
zone that covers all the inside nodes and the attacked zone is
not acyclic, one can still approximately recover the voltages
and detect the line failures using convex optimization.
Based on the results, we then introduce the EXPress line
failure detection using partially ObSErved information (EXPOSE) Algorithm. It outperforms the state-of-the-art algorithm
for detecting line failures using partial information under the
AC power flows in terms of scalability and accuracy. The main
advantages of the EXPOSE Algorithm are that its running
time is independent of the size of the grid and number of
line failures, and that it provides accurate information recovery under some conditions on the attacked zone. Moreover,
it approximately recovers the information and provides the
confidence of the solution when these conditions do not hold.
Most of the related work rely on the DC power flows and
deploy brute force search approaches. These approaches do not
scale well, and therefore, are limited only to detecting single
and double line failures using partial measurements [5], [6],
[7], [8], [9]. To represent these approaches and for comparison
purposes only, we also introduce a naive Brute Force Search
(BFS) Algorithm for detecting line failures after the attack.
Finally, while we analytically prove that the EXPOSE
Algorithm guarantees to accurately recover the voltages and
detect line failures under some conditions, we also numerically
evaluate its performance when those conditions do not hold.
In particular, we evaluate the performance of the EXPOSE
Algorithm as the attacked zone becomes topologically more
complex and compare its running time to the BFS Algorithm
by considering all single, double, and triple line failures in
5 nested attacked zones. Based on the simulation results, we
conclude that despite its accuracy, the BFS Algorithm is not
practical for line failures detection in large networks and that
the EXPOSE Algorithm can provide relatively accurate results
exponentially faster. For example, the EXPOSE algorithm
recovers the voltages with less than 15% error and detects
line failures with less than 1 false negative on average, after
all single, double, and triple line failures in an attacked zone
that satisfies none of the conditions for the accuracy of the
EXPOSE Algorithm.
II. R ELATED W ORK
Vulnerability of power grids to failures and attacks has been
widely studied [10], [11], [12], [13], [14], [15], [16], [17], [18],
[19]. In particular false data injection attacks on power grids
and anomaly detection have been studied using the DC power
flows in [20], [21], [22], [23], [24], [25]. These studies focused
on the observability of the failures and attacks in the grid.

The problem studied in this paper is similar to the problem
of line failures detection using phase angle measurements [5],
[6], [7], [26]. Up to two line failures detection, under the
DC power flow model, was studied in [5], [6]. Since the
provided methods in [5], [6] are greedy-based methods that
need to search the entire failure space, the running time of
these methods grows exponentially as the number of failures
increases. Hence, these methods cannot be generalized to
detect higher order failures. Similar greedy approaches with
likelihood detection functions were studied in [8], [9], [27],
[28], [29] to address the PMU placement problem under the
DC power flow model.
The problem of line failures detection in an internal system
using the information from an external system was also studied
in [7] based (again) on the DC power flow model. The
proposed algorithm works for only one and two line failures,
since it depends on the sparsity of line failures.
In a recent work [26], a linear multinomial regression model
was proposed as a classifier for a single line failure detection
using transient voltage phase angles data. Due to the time
complexity of the learning process for multiple line failures,
this method is impractical for detecting higher order failures.
Moreover, the results provided in [26] are empirical with no
performance guarantees.
Finally, in a recent series of works, the vulnerability of
power grids to undetectable cyber-physical attacks is studied [30], [31], [32] using the DC power flows. These studies
are mainly focused on designing attacks that affect the entire
grid and therefore may remain undetected.
To the best of our knowledge, our methods presented in this
paper and [4] are the only methods for line failures detection
under the AC power flows that can be used to detect any
number of line failures and scale well with size of the grid.
However, the EXPOSE Algorithm provided in this paper is
more accurate than the method provided in [4].
III. M ODEL AND D EFINITIONS
A. AC Power Flow Equations
A power grid with n nodes (buses) and m transmission
lines can be represented by an undirected graph G(N , L),
where N = {1, 2, . . . , n} denotes the set of nodes and
L = {l1 , l2 , . . . , lm } denotes the set of lines or edges. In the
steady-state, the status of each node i is represented by its
voltage Vi = |Vi |eiθi in which |Vi | is the voltage magnitude,
θi is the voltage phase angle, and i denotes the imaginary unit.
The goal of the AC power flow analysis is the computation
of the voltage magnitudes and phase angles at each bus in
steady-state conditions [33]. In the steady-state, the AC power
flow equations can be written in matrix form as follows:
YV = I,

(1)

S = diag(V )I ∗ ,

(2)

where ∗ denotes the complex conjugation, V = [V1 , . . . , Vn ]T
is the vector of node voltages, I = [I1 , I2 , . . . , In ]T is the
vector of injected node currents, S = [S1 , S2 , . . . , Sn ]T is the
vector of injected apparent powers, and Y is the admittance
matrix of the graph.

3

𝐻

IEEE 300-Bus

Fig. 2: The attack model. An adversary attacks a zone by disconnecting some of its lines (red dashed lines) and disallowing the information
from within the zone to reach the control center. G is the power grid graph and H is a subgraph of G that represents the attacked zone.

The elements of the admittance matrix Y which depends
on the topology of the grid as well as the admittance values
of the lines, is defined as follows:

P

yii + i6=k yik , if k = i
Yik = −yik ,
if k ∈ N (i)


0,
if k ∈
/ N (i)
where N (i) denotes the direct neighbors of node i, yik is
the equivalent admittance of the lines from node i to k,
and yii is sum of the shunt admittances at node i. In this
paper, we assume that the shunt admittances are negligible,
and therefore, yii = 0 for all i ∈ N . The admittance matrix
can also be written in term of its real and imaginary parts
as Y = G + iB where G and B are real matrices. Using
this and the definition of the apparent power Si = Pi + iQi
in (1-2) results in the equations for the active power Pi and
the reactive power Qi at each node i as well.
B. Incidence Matrix
Under an arbitrary direction assignment to the edges of G,
the incidence matrix of G is denoted by D ∈ {−1, 0, 1}n×m
and defined as,


if lj is not incident to node i,
0
dij = 1
if lj is coming out of node i,


−1 if lj is going into node i.
For each line lj = (i, k), define ylj := yik . It can be verified
that Y = Ddiag([yl1 , yl2 , . . . , ylm ])DT . As we demonstrate
in Section IV, the incidence matrix is a very useful matrix for
detecting line failures in power grids.

C. Basic Graph Theoretical Terms
Matching: A matching in a graph is a set of pairwise
nonadjacent edges. If M is a matching, the two ends of each
edge of M are said to be matched under M, and each vertex
incident with an edge of M is said to be covered by M.
Cycle: A cycle in a graph is a sequence of its distinct nodes
u1 , u2 , . . . , uk such that for all i < k, {ui , ui+1 } ∈ L, and
also {uk , u1 } ∈ L. A graph with no cycle is called acyclic.
D. Attack Model
We assume that an adversary attacks an area by: (i) disconnecting some lines within that area (failed lines), and
(ii) obstructing all the information (e.g., status of the lines
and voltage measurements) from within the area to reach the
control center. We call this area, the attacked zone.
Fig. 2 shows an example of an attack on the area represented
by H = (NH , LH ). We denote the set of failed lines in the
attacked zone H by F ⊆ LH . Upon failure, the failed lines
are removed from the graph and the flows are redistributed
according to the AC power flows. Our objective is to estimate
the voltages and detect the failed lines inside the attacked zone
using the changes in the voltages outside of the zone.
We use the prime symbol (0 ) to denote the values after an
attack (e.g, Y0 denotes the admittance matrix of the grid and
V 0 denotes node voltages after the attack). Using this notation,
if H̄ denotes the set of nodes outside of the attacked zone, then
given VH̄0 and S 0 , we want to recover VH0 and F. Notice that it
0
is reasonable to assume that we know SH
after the attack, since
for the load nodes inside that attacked zone H, we can assume
that P 0 and Q0 remain similar to their values before the attack
and for the generators we can assume that generator operators
can safely report the generated P 0 and Q0 values. Equivalently,

4

we can assume that P and Q do not change much after the
attack and therefore S 0 = S.
Detecting line failures after such an attack is crucial in
maintaining the stability of the grid, since it may result in
further line overloads and failures, if the proper load shedding
mechanism is not applied. An effective load shedding requires
the exact knowledge of the topology of the grid.
Notation. For any complex number x = Re(x) + i Im(x),
real numbers Re(x) and Im(x) denote its real and imaginary
values, respectively. For a vector X, supp(X) denotes the
set of its nonzero entries. If H1 , H2 are two subgraphs of G,
YH1 |H2 denotes the submatrix of Y with rows from VH1 and
columns from VH2 . Moreover, YH1 denotes the submatrix of
Y with all the rows associated with VH1 . For instance, Y can
be written in any of the following forms,




YH|H YH|H̄
YH
Y=
,Y =
.
YH̄|H YH̄|H̄
YH̄
IV. S TATE E STIMATION
In this section, we provide the analytical building blocks
of the EXPOSE Algorithm which can be used to estimate the
state of the grid following a cyber-physical attack. Notice that
the state estimation problem considered here is different from
the classical state estimation problem in power grids. Here,
besides estimating the voltage magnitudes and phase angles in
the attacked area, the algorithm needs to estimate the topology
of the grid as well.
A. Voltage Recovery
Here, we provide a method to recover the voltages inside
that attacked zone after the attack.
Observation 1: The admittance matrix of the grid does not
0
).
change outside of the attacked zone (i.e., YH̄ = YH̄
Proof: Since the line failures only happen inside H, following the definition of the admittance matrix (see Section III),
after the attack only the entries of YH|H change. Hence, YH̄
remains unchanged.
From Observation 1 and using (1), we have:
0
0
0
∗
0∗
YH̄
V 0 = IH̄
⇒ YH̄ V 0 = IH̄
⇒ YH̄
V 0∗ = IH̄
∗
0∗
⇒diag(VH̄0 )YH̄
V 0∗ = diag(VH̄0 )IH̄
∗
0
⇒diag(VH̄0 )YH̄
V 0∗ = SH̄
∗
0∗
0
∗
0∗
⇒diag(VH̄0 )YH̄|
H̄ VH̄ + diag(VH̄ )YH̄|H VH

Lemma 1: If there is matching between the nodes in H̄ and
H that covers the nodes in H, then the following matrix has
full column rank almost surely,


GH̄|H −BH̄|H
M :=
.
BH̄|H GH̄|H
Proof: Suppose U ⊆ NH̄ are the matched nodes which
are in H̄. Since the matching covers H, thus |U| = |NH |. To
show that M has full column rank, we show that


GU |H −BU |H
6= 0,
det(MU |H ) := det
BU |H GU |H
almost surely. det(MU |H ) can be considered as a polynomial
in terms of the entries of MU |H using Leibniz formula. Now
assume U = {u1 , u2 , . . . , u|NH | } are matched to NH =
Q|N |
{v1 , v2 , . . . , v|NH | } in order. It can be seen that i=1H G2ui vi
Q|NH | 2
and i=1 Bui vi are two terms with nonzero coefficient in
det(MU |H ). Therefore, det(MU |H ) is a nonzero polynomial
in terms of its entries. Now since the set of roots of a nonzero
polynomial is a measure zero set in the real space, thus
det(MU |H ) 6= 0 almost surely.
Corollary 1: If there is matching between the nodes in H̄
and H that covers the nodes in H, then VH0 can be recovered
almost surely.
B. Line Failures Detection
Assume VH0 is successfully recovered using (4). In this
subsection, using VH0 , we provide a method to detect the set
of line failures F.
Lemma 2: There exists a complex vector X ∈ C|LH | such
that
0
YH V 0 = IH
+ DH X,
(5)
and supp(X) = F. Moreover, the vector X is unique if, and
only if, DH has full column rank.
Proof: Without loss of generality assume F =
{l1 , l2 , . . . , lk }. It can be seen that Y0 = Y −
Ddiag([yl1 , yl2 , . . . , ylk , 0, 0, . . . , 0])DT . Hence,
Y0 V 0 = YV 0 − Ddiag([yl1 , yl2 , . . . , ylk , 0, 0, . . . , 0])DT V 0
I 0 = YV 0 − Ddiag([yl1 , yl2 , . . . , ylk , 0, 0, . . . , 0])DT V 0 .
Now if we only focus on the rows associated with the nodes
in H, it can been seen that

0
= SH̄
.

(3)

Notice that in (3) all the variables are known after the attack
∗
0
except VH0∗ . Define EH̄ := −YH̄|
V 0∗ +diag(VH̄0−1 )SH̄
which
H̄ H̄
can be computed from the given variables after the attack.
Then, we can separate the real and imaginary parts of (3)
using block matrices as follows:


 

GH̄|H −BH̄|H Re(VH0 )
Re(EH̄ )
=
.
(4)
BH̄|H GH̄|H
Im(VH0 )
−Im(EH̄ )
One can see that Re(VH0 ) and Im(VH0 ) can be uniquely
recovered if the matrix on the left hand side of (4) has full
column rank. The following lemma provides the connection
between the rank of that matrix and the topology of the grid.

0
IH
= YH V 0 − DH diag([yl1 , yl2 , . . . , ylk , 0, 0, . . . , 0])DTH V 0 .

Hence, vector X := diag([yl1 , yl2 , . . . , ylk , 0, 0, . . . , 0])DTH V 0
satisfies (5). It can also be seen that only the entries of X that
are associated with the failed lines are nonzero and therefore
supp(X) = F. In order for (5) to have a unique solution, DH
should have full column rank.
Corollary 2: There exist a real vector X ∈ R|LH | such that
∗
0
Re{YH
V 0∗ } = Re{diag(VH0 )−1 SH
} + DH X,

(6)

and supp(X) = F. Moreover, the vector X is unique if, and
only if, DH has full column rank.
Proof: Using (2) and Lemma 2 gives the result.

5

Corollary 2 indicates that the set of line failures can be
detected by solving a matrix equation, if DH has full column
rank. The following lemma provides the connection between
the rank of that matrix and the topology of the attacked zone.
Lemma 3: The solution vector X to (6) is unique if, and
only if, H is acyclic.
Proof: It is easy to verify that (6) has a unique solution
X if, and only if, DH has linearly independent columns. On
the other hand, it is known in graph theory that rank(DH ) =
|NH |−c in which c is the number of connected components of
H [34, Theorem 2.3]. Therefore, DH has linearly independent
columns if and only if LH = |NH | − c which means that each
connected component of DH is acyclic.
Corollary 3: If H is acyclic, then the set of line failures F
can be detected by solving (6) for X.
Corollary 3 states that the set of line failure can accurately be
detected if H is acyclic. The importance of this result is in
demonstrating that the set of line failures can be efficiently
detected by solving a matrix equation, independent of the
number of line failures.
We can use a similar idea as in [3] to extend this approach
to when H is not acyclic. If we assume that the set of line
failures are sparse compare to the total number of lines in H,
we can detect line failures by finding the solution of following
optimization problem instead:
minimize kXk1 s.t.

X∈R|LH |
∗
Re{YH
V 0∗ }

kX − c1k1 =
=

0
= Re{diag(VH0 )−1 SH
} + DH X.

(7)

≥

i=1

minimize

0 ∈C|NH |
X∈R|LH | ,VH

kXk1 s.t.

GH̄|H Re(VH0 ) − BH̄|H Im(VH0 ) = Re(EH̄ )
BH̄|H Re(VH0 ) + GH̄|H Im(VH0 ) = −Im(EH̄ )
∗
0
Re{YH
V 0∗ } = Re{diag(VH0 )−1 SH
} + DH X.

(8)

However, since VH0 is part of the variables, this optimization
problem is not linear and convex anymore. To resolve this
issue, we need to approximate diag(VH0 )−1 with a linear
function in terms of VH0 . For this, we have:

On the other hand, the voltage magnitudes are almost constant
at each node before and after the failure (|VH0 | ≈ |VH |), hence:

diag(VH0 )−1 ≈ diag(|VH |)−2 diag(Re(VH0 ))−i diag(Im(VH0 )) .
We can use the approximation above in optimization (8) in
order to relax its nonconvexity. Notice that since optimization
(8) is for the cases in which the solution to (4) is not unique
and therefore the voltages cannot be recovered uniquely, some
conditions should be placed on the voltages such that the
recovered voltages are near operable conditions. To do so,
we add a convex constraint on the voltage magnitudes of the
nodes in H after the attack as |VH0 | ≤ 1.11H , in which 1H is
an all ones vector of size |NH |. Hence, the following convex
optimization can be used to detect the set of line failures and
recover the voltages when the solution to (4) is not unique:
minimize

0 ∈C|NH |
X∈R|LH | ,VH

kXk1 s.t.

GH̄|H Re(VH0 ) − BH̄|H Im(VH0 ) = Re(EH̄ )
BH̄|H Re(VH0 ) + GH̄|H Im(VH0 ) = −Im(EH̄ )
|VH0 | ≤ 1.11H
+ diag(|VH |)−2 diag(Im(VH0 ))Q0H + DH X.

(|xi − c| + |c|) + (|LH | − 2k)|c|
|xi | + (|LH | − 2k)|c| >

In order to extend our approach to the cases that (4) does
not have a unique solution, we can solve (4) and (7) at the
same time. Therefore, in order to recover the voltages and
detect the line failures at the same time, one needs to solve
the following optimization problem:

∗
0
Re{YH
V 0∗ } ≈ diag(|VH |)−2 diag(Re(VH0 ))PH

|xi − c| + (|LH | − k)|c|

i=1
k
X

i=1
k
X

C. Simultaneous Recovery and Detection


diag(VH0 )−1 = diag(|VH0 |)−2 diag(Re(VH0 ))−i diag(Im(VH0 )) .

Notice that optimization problem (7) can be solved efficiently
using Linear Programming (LP).
Lemma 4: If H is a cycle and less than half of its edges are
failed, then the solution X to the optimization problem (7) is
unique and supp(X) = F.
Proof: The idea of the proof is similar to the idea used
in the proof in [3, Lemma 4]. Here without loss of generality,
we assume that DH is the incidence matrix of H when edges
of the cycle are directed clockwise. Since H is connected, it
is known that rank(DH ) = |NH | − 1 [34, Theorem 2.2].
Therefore, dim(null(DH )) = 1. Suppose 1 ∈ R|LH | is
the all one vector. It can be seen that DH 1 = 0. Since
dim(null(DH )) = 1, 1 is the basis for the null space of D.
Suppose X is a solution to (7) such that supp(X) = F (from
Lemma 2 we know that such a solution exists). To prove that
X is the unique solution for (7), we prove that ∀c ∈ R\{0},
kXk1 < kX −c1k1 . Without loss of generality we can assume
that x1 , x2 , . . . , xk are the nonzero elements of X, in which
k = |F|. From the assumption, we know that k < |LH |/2.
Hence,
k
X

Thus, the solution to (7) is unique and supp(X) = F.
Lemma 4 can be extended to planar graphs similar to the
result for the DC power flows presented in [3, Theorem 2]. The
proof and the argument in [3] should apply with a very slight
change here as well. To avoid repetition, we do not present a
similar Lemma here.

k
X
i=1

|xi | = kXk1 .

(9)

Notice that to enforce AA ≈ BB for arbitrary vectors AA
and BB, we use convex constraint kAA − BBk2 <  for a
small value . In Section VII, we evaluate the accuracy of the
results obtained by solving the convex optimization problem
(9) as part of the EXPOSE Algorithm.

6

IEEE 118-Bus

Algorithm 1: EXPress line failure detection using partially
ObSErved information (EXPOSE)
Input: A connected graph G, attacked zone H, V , VH̄0 , and S 0
1:
2:
3:
4:
5:
6:
7:
8:

if M is full rank then
Solve (4) to recover VH0
Use the recovered VH0 in (7) to find the solution vector X
else
Find the solution VH0 and X to the optimization (9)
Compute F = supp(X)
Compute the confidence of the solution cP and cQ
return VH0 , F, cP , and cQ

Algorithm 2: Brute Force Search (BFS)
1: for Any F ⊆ LH do
2:
Compute V † after removing the lines in F † from G
3:
Compute eF † = kRe(VH̄† − VH̄0 )k2 +kIm(VH̄† − VH̄0 )k2
4: Select F = arg minF † ⊆LH eF †
5: return F

D. Confidence of the Solution
Once the set of line failures is detected and the voltages
are recovered, one can compute the confidence of the solution
using (1-2). Assume Y† and V † denote the admittance matrix
of the grid after removing the detected lines and the recovered
voltages after the attack, respectively. If the detection and
recovery are done correctly, then Re{diag(V † )∗ YV † } = P 0
and Im{diag(V † )∗ YV † } = Q0 . However, if the detection and
recovery are not done correctly, this equalities do not hold. We
can use the difference between the two sides of these equalities
as a measure for the correctness of the solution.
We define cP and cQ to denote the confidence of the
solution based on P and Q as follows:
cP := (1−kRe{diag(V † )∗ YV † }−P 0 k2 /kP 0 k2 )+ ∗100, (10)
cQ := (1−kIm{diag(V † )∗ YV † }−Q0 k2 /kQ0 k2 )+ ∗100, (11)
in which (x)+ := max(0, x). If cP , cQ ≈ 100%, then it means
that the solution is reliable. If not, depending on the cP or cQ
values, one can see how reliable the solution actually is.
V. EXPOSE A LGORITHM
In this section, using the results provided in Section IV,
we introduce the EXPress line failure detection using partially
ObSErved information (EXPOSE) Algorithm. The EXPOSE
Algorithm is summarized in Algorithm 1.
Notice that for solving (4), (7), and (9) only the voltages of
the nodes that are at most one hop away from the nodes in H
are required. Hence, not only the running time of the EXPOSE
algorithm is independent of the number of line failures, it is
independent of the size of the entire grid as well. This makes
the EXPOSE Algorithm suitable for detecting line failures in
large networks.

Fig. 3: An attacked zone used in [4], shown by red nodes, in the
IEEE 118-bus system.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

1
2
3
4
5

Failed Line

†

Failed Line

Input: A connected graph G, attacked zone H, V , VH̄0 , and S 0

6
7
8
9
10
11
12
13
14
15

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

Detected Lines

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

Detected Lines

(a)
(b)
Fig. 4: Detected line failures after all possible single line failures
using the EXPOSE Algorithm in (a) the zone shown in Fig. 3 in the
IEEE 118-bus system, and (b) the zone shown in Fig. 2 in the IEEE
300-bus system.

Algorithm for detecting line failures after the attack. The BFS
Algorithm considers all possible line failure scenarios and
returns the most likelihood solution. This method is the naive
version of the approaches used in [5], [6], [7], [8], [9] in
similar settings to detect line failures given a partial phase
angle measurements under the DC power flow model.
The idea is to compute the voltages VH̄† for any possible set
of line failures F † ⊆ LH and detect the one that is closest to
VH̄0 as the most likely failure as follows:
F = arg min kRe(VH̄† − VH̄0 )k2 + kIm(VH̄† − VH̄0 )k2 . (12)
F † ⊆LH

The BFS Algrithm is summarized in Algorithm 2. Notice
that the BFS Algorithm is exponentially slower than the
EXPOSE Algorithm, since it requires to solve the AC power
flow solutions 2|LH | times. Moreover, since it requires to solve
the power flow equations for the entire grid, in oppose to the
EXPOSE Algorithm, its running time increases polynomially
with the size of the grid.
The main shortcoming of the BFS Algorithm is its intractability for large networks. One way to speed up the BFS
Algorithm is to stop whenever the eF † (as defined in line 3
of the algorithm) is less than a threshold. This may speed up
the process but does not solve the intractability issue.

VI. B RUTE F ORCE A LGORITHM
In order to compare the performance of the EXPOSE
Algorithm with the previous works that were mostly under the
DC power flows, we introduce the Brute Force Search (BFS)

VII. N UMERICAL R ESULTS
While in Section IV, we analytically proved that the EXPOSE Algorithm guarantees to accurately recover the voltages

7

200

100

0
1

2

3

4

5

6

7

BFS
EXPOSE

Level 1

Level 2

60

40

Level 3
Level 4
Level 5

40

20

0
1

Number of Line Failures

30

Rank Deficit

300

80

BFS
COPSSES
EXPOSE

Running time (sec)

Running time (sec)

400

2

3

4

λH
γH

20

10

5

Attacked Zone Level

(a)
(b)
Fig. 5: Average running times of different line failures detection
algorithms versus (a) the total number of line failures in the attacked
zone shown in Fig. 2, and (b) the size of the attacked zone as shown
in Fig. 6(a) in detecting triple line failures.

and detect line failures under some conditions (i.e., matched
and acyclic attacked zones), in this section, we numerically
confirm those results and also evaluate the EXPOSE Algorithm’s performance when those conditions do not hold (i.e.,
general attacked zones).
A. Matched and acyclic attacked zones
As we mentioned in Section II, to the best of our knowledge,
our work in [4] is the only other method for information
recovery under the AC power flows that can be used to detect
any number of line failures and scales well with the size
of the grid. In [4], we introduced the Convex OPtimization
for Statistical State EStimation (COPSSES) Algorithm and
demonstrated that when the attacked zone is matched and
acyclic (i.e., matrices M and DH have full column rank), it
can detect line failures with few errors. The COPSSES Algorithm uses a relaxation of the methods introduced in [3], which
were based on DC power flow equations, for information
recovery under the AC power flow equations. The advantage
of the COPSSES Algorithm is that similar to the EXPOSE
Algorithm, its running time is independent of the number of
line failures.
In order to demonstrate the superiority of the EXPOSE
Algorithm in this case, here we compare its performance and
running time to the COPSSES Algorithm in addition to the BFS
Algorithm. For comparison purposes, we consider attacks on
the same zones as considered in [4] within the IEEE 118- and
300-bus systems. The zones are depicted in Figs. 3 and 2.
Recall from subsections IV-A and IV-B that when matrices
M and DH have full column rank, as it is the cases here, the
EXPOSE Algorithm can recover the voltages and detect the
line failures accurately. Hence as we expected and can be seen
in Fig. 4, all the single line failures can be exactly detected
using the EXPOSE Algorithm in the selected attacked zones
within the IEEE 118- and 300-bus systems. Notice that the
false positives in failures of lines 6 and 7 as well as 17 and
18 in the IEEE 118-bus system are due to the violation of the
acyclicity of the attacked zone. Lines 6 and 7 (and also 17
and 18) are parallel lines that form a cycle with two nodes.
Moreover, lack of any detections after failures in lines 1
and 15 within that attacked zone in the 300-bus system is due
to the fact that the AC power flows did not have a solution
after those failures. Therefore those cases did not considered
in evaluation of the EXPOSE Algorithm.

0
1

2

3

4

5

Attacked Zone Level

(b)
(a)
Fig. 6: Nested attacked zones in the IEEE 300-bus system. (a) Nodes
corresponding to different levels are shown in different colors, and
(b) the rank deficit in the attacked zones in different levels.

We considered up to 7 line failures in the zone depicted
in Fig. 2. In all the cases, as we expected, the EXPOSE
Algorithm could exactly detect the line failures. The BFS
Algorithm could also detect the line failures exactly in those
scenarios. However, as it was shown in [4], the COPSSES
Algorithm may result in few false positives and negatives in
detecting single line failures, and more false positives and
negatives as the number of line failures increases.
Fig. 5(a) compares the running times of the three Algorithms in detecting line failures versus the number of line
failures. As can be seen since the running times of the
EXPOSE and COPSSES Algorithms are independent of the
number of line failures, they both provide a constant running
time as the number of line failures increases. However, as
can be seen, the running time of the BFS Algorithm increases
exponentially as the total number of line failures increases.
Overall, when the attacked zone is matched and acyclic, the
EXPOSE Algorithm detects line failures as accurately as the
BFS Algorithm, but exponentially faster.
B. General attacked zones
In order to evaluate the performance of the EXPOSE
Algorithm as the attacked zone becomes larger and topologically more complex, in this subsection, we consider 5 nested
attacked zones as depicted in Fig. 6(a). We denote the nodes
that are added to the attacked zone at ith step by the level
i nodes. The level i attacked zone is an attacked zone that
consists of all the nodes in levels 1 to i.
As we proved in Section IV and briefly showed in Subsection VII-A, when matrices M and DH have full column
rank, then the EXPOSE Algorithm can recover the voltages
and detects the line failures accurately. In order to show how
far or close the topological properties of an attacked zone are
to these conditions, we define λH and γH as follows:
λH := 2nH − rank(M),
γH := mH − rank(DH ).
It can be verified that when matrices M and DH have full
column rank, then λH = 0 and γH = 0, respectively. Hence,
λH and γH indicate the rank deficit of matrices M and DH .
Fig. 6(b) shows the λH and γH values for the different
attacked zone levels. As can be seen, both values grow

8

1.5

3

Triple Line Failures
Double Line Failures
Single Line Failures

Number of False Positives

Number of False Negatives

2

1

0.5

0
1

2

3

4

2.5
2
Triple Line Failures
Double Line Failures
Single Line Failures

1.5
1
0.5
0
1

5

Attacked Zone Level

2

3

(a)

30

Triple Line Failures
Double Line Failures
Single Line Failures

20

10

0
1

2

5

(b)
50

Percent Error Phase Ang.

Percent Error Vol. Mag.

40

4

Attacked Zone Level

3

4

Triple Line Failures
Double Line Failures
Single Line Failures

40
30
20
10
0
1

5

Attacked Zone Level

2

3

4

5

Attacked Zone Level

(c)

(d)
100

90

80

80

60

cP

cQ

100

70
60
50
1

40
Triple Line Failures
Double Line Failures
Single Line Failures
2

3

20

4

Attacked Zone Level

(e)

5

0
1

Triple Line Failures
Double Line Failures
Single Line Failures
2

3

4

5

Attacked Zone Level

(f)

Fig. 7: The EXPOSE Algorithm’s performance after all single,
double, and triple line failures versus the size of the attacked zone as
shown in Fig. 6(a). (a) Average number of false negatives, (b) average
number of false positives, (c) average percentage error in recovered
voltage magnitudes, (d) average percentage error in recovered voltage
phase angles, (e) average confidence of the solutions (cP ), and (f)
average confidence of the solutions (cQ ).

significantly in level 4 and 5 attacked zones. This means
that the data outside of the attacked area is very insufficient
to accurately detect the line failures based on the EXPOSE
Algorithm in those levels.
First, in order to show the advantage of the EXPOSE
Algorithm over brute force type algorithms, in Fig. 5(b), we
compare the increase in the running times of the BFS and
the EXPOSE Algorithms in detecting triple line failures as
the number of nodes and lines increases in different levels.
As can be seen in Fig. 5(b), the running time of the BSF
Algorithm exponentially increases with the size of the attacked
zone whereas that of the EXPOSE Algorithm only slightly
increases. This along with Fig. 5(a) clearly indicates that the
BFS Algorithm (and algorithms with similar approaches) do
not scale well with the size of the attacked zone and the
number of line failures.
In order to evaluate the performance of the EXPOSE Algorithm, we consider all single, double, and triple line failures
in the nested zones. The results are presented in Fig. 7.
The average number of false negatives and positives in

detecting line failures in different attacked zone levels for
all single, double, and triple line failures are presented in
Figs. 7(a) and 7(b). It can be seen that as we expected for the
level 1 attacked zone, there are no false negatives or positive.
For the level 2 attacked zone also, although DH does not
have full column rank (see Fig. 6(b)), the EXPOSE Algorithm
can still detect the line failures accurately. However, as the
attacked zone becomes larger in higher levels, and λH and
γH increase, we observe that the EXPOSE Algorithm results
in false positives and negatives. An important observation here
is that the EXPOSE Algorithm results on average in more false
positives than negatives. This is a good characteristic of the
EXPOSE Algorithm, since it means that by having an extra
brute force search step on the detected line failures set, one
can reduce number of false positives significantly.
The average error in recovered voltages in different attacked
zone levels using the EXPOSE Algorithm for all single,
double, and triple line failures are presented in Figs. 7(c) and
7(d). As can be seen, similar to the line failures detection,
the EXPOSE Algorithm recovers the voltages accurately for
the level 1 and 2 attacked zones. Moreover, for the level 3
and 4 attacked zones, the EXPOSE Algorithm recovers the
voltage magnitudes and phase angles with less than 15% and
10% error, respectively. However, for the level 5 attacked zone,
since λH is too high (see Fig. 6(b)), the EXPOSE Algorithm
results in around 30% and 40% error in the recovered voltage
magnitudes and phase angles, respectively.
Finally, as we introduced cP and cQ in subsection IV-D,
these metrics can be used to determine the confidence of
the solutions obtained by the EXPOSE Algorithm. As can
be seen in Figs. 7(e) and 7(f), the cP and cQ values are
directly correlated with the errors in voltages and number of
false negatives. Hence, these values can effectively be used
to compute the confidence of the solution obtained by the
EXPOSE Algorithm. Notice that cQ is more sensitive than
the cP . Therefore, cQ can be used as the upper bound for the
error and cP can be used as the lower bound.
We did not evaluate the performance of the BFS Algorithm
here due to its very high running time (see Fig. 5(b)). However,
we expect that the BFS Algorithm could detect the line failures
and recover the voltages with almost no error. Despite its
accuracy, the BFS Algorithm is not practical for line failures
detection in large networks. As we showed in this section,
the EXPOSE Algorithm can provide relatively accurate results
exponentially faster than the BFS Algorithm.
VIII. C ONCLUSION
We studied cyber-physical attacks on power grids under the
AC power flows. We leveraged the algebraic properties of the
AC power flows to develop the EXPOSE Algorithm for detecting line failures and recovering the voltages after the attack.
We analytically proved that if the attacked zone has certain
topological properties, the EXPOSE Algorithm can accurately
recover the information. We also numerically demonstrated
that in more complex attacked zones, it can still recover the
information approximately well. The main advantages of the
EXPOSE Algorithm are that its running time is independent

9

of the size of the grid and number of line failures, and that it
provides accurate information recovery under some conditions
on the attacked zone. Moreover, it approximately recovers the
information and provides the confidence of the solution when
these conditions do not hold.
The results provided in this paper can be further used in
different context as well. For example, the EXPOSE Algorithm
can be used to detect line failures when measurement devices
are scarce and not ubiquitous. Moreover, the conditions on the
attacked zone such that the EXPOSE Algorithm can accurately
detect the line failures and recover the voltages, can be used
for optimal measurement device placements in the grid.
Despite it strengths, the EXPOSE Algorithm presented in
this paper requires that the power system converges to a stable
state after an attack. However, as the number of line failures
increases, such an assumption may rarely holds. Therefore,
the dynamics of the system after an attack should also be
considered for an effective detection mechanism. Due to their
complexity, study the dynamics of the power system after an
attack is a very challenging task. Hence, exploring this and
other directions is part of our future work.
ACKNOWLEDGEMENT
This work was supported in part by DARPA RADICS under
contract #FA-8750-16-C-0054, funding from the U.S. DOE
OE as part of the DOE Grid Modernization Initiative, and
DTRA grant HDTRA1-13-1-0021.
R EFERENCES
[1] “Analysis of the cyber attack on the Ukrainian power grid,” Mar.
2016, http://www.nerc.com/pa/CI/ESISAC/Documents/E-ISAC SANS
Ukraine DUC 18Mar2016.pdf.
[2] “Assault on California power station raises alarm on potential for
terrorism,” 2014, source: http://goo.gl/RiuhI1.
[3] S. Soltan, M. Yannakakis, and G. Zussman, “Power grid state estimation
following a joint cyber and physical attack,” to appear in IEEE Trans.
Control Netw. Syst., 2017.
[4] S. Soltan and G. Zussman, “Power grid state estimation after a cyberphysical attack under the AC power flow model,” in Proc. IEEE PESGM’17, July 2017.
[5] J. E. Tate and T. J. Overbye, “Line outage detection using phasor angle
measurements,” IEEE Trans. Power Syst., vol. 23, no. 4, pp. 1644–1652,
2008.
[6] ——, “Double line outage detection using phasor angle measurements,”
in Proc. IEEE PES-GM’09, July 2009.
[7] H. Zhu and G. B. Giannakis, “Sparse overcomplete representations for
efficient identification of power line outages,” IEEE Trans. Power Syst.,
vol. 27, no. 4, pp. 2215–2224, 2012.
[8] Y. Zhao, A. Goldsmith, and H. V. Poor, “On PMU location selection
for line outage detection in wide-area transmission networks,” in Proc.
IEEE PES-GM’12, July 2012.
[9] H. Zhu and Y. Shi, “Phasor measurement unit placement for identifying
power line outages in wide-area transmission system monitoring,” in
HICSS’14, 2014, pp. 2483–2492.
[10] A. Ashok, M. Govindarasu, and J. Wang, “Cyber-physical attackresilient wide-area monitoring, protection, and control for the power
grid,” Proc. IEEE, 2017.
[11] A. Pinar, J. Meza, V. Donde, and B. Lesieutre, “Optimization strategies
for the vulnerability analysis of the electric power grid,” SIAM J.
Optimiz., vol. 20, no. 4, pp. 1786–1810, 2010.
[12] T. Kim, S. J. Wright, D. Bienstock, and S. Harnett, “Analyzing vulnerability of power systems with continuous optimization formulations,”
IEEE Trans. Net. Sci. Eng., vol. 3, no. 3, pp. 132–146, 2016.
[13] J. Liu, C. H. Xia, N. B. Shroff, and H. D. Sherali, “Distributed
optimal load shedding for disaster recovery in smart electric power
grids: A second-order approach,” in Proc. ACM SIGMETRICS’14 (poster
description), June 2014.

[14] A. Bernstein, D. Bienstock, D. Hay, M. Uzunoglu, and G. Zussman,
“Sensitivity analysis of the power grid vulnerability to large-scale
cascading failures,” ACM SIGMETRICS Perform. Eval. Rev., vol. 40,
no. 3, pp. 33–37, 2012.
[15] I. Dobson, B. Carreras, V. Lynch, and D. Newman, “Complex systems
analysis of series of blackouts: cascading failure, critical points, and
self-organization,” Chaos, vol. 17, no. 2, p. 026103, 2007.
[16] D. Bienstock, Electrical Transmission System Cascades and Vulnerability: An Operations Research Viewpoint. SIAM, 2016.
[17] S. Soltan, A. Loh, and G. Zussman, “Analyzing and quantifying the
effect of k-line failures in power grids,” to appear in IEEE Trans.
Control Netw. Syst., 2017.
[18] A. Srivastava, T. Morris, T. Ernster, C. Vellaithurai, S. Pan, and U. Adhikari, “Modeling cyber-physical vulnerability of the smart grid with
incomplete information,” IEEE Trans. Smart Grid, vol. 4, no. 1, pp.
235–244, 2013.
[19] F. Pasqualetti, F. Dörfler, and F. Bullo, “Cyber-physical attacks in power
networks: Models, fundamental limitations and monitor design,” in Proc.
IEEE CDC-ECC’11, 2011, pp. 2195–2201.
[20] J. Kim and L. Tong, “On topology attack of a smart grid: undetectable
attacks and countermeasures,” IEEE J. Sel. Areas Commun, vol. 31,
no. 7, pp. 1294–1305, 2013.
[21] Y. Liu, P. Ning, and M. K. Reiter, “False data injection attacks against
state estimation in electric power grids,” ACM Trans. Inf. Syst. Secur.,
vol. 14, no. 1, p. 13, 2011.
[22] G. Dán and H. Sandberg, “Stealth attacks and protection schemes for
state estimators in power systems,” in Proc. IEEE SmartGridComm’10,
2010.
[23] O. Vukovic, K. C. Sou, G. Dán, and H. Sandberg, “Network-layer
protection schemes against stealth attacks on state estimators in power
systems,” in Proc. IEEE SmartGridComm’11, 2011.
[24] S. Li, Y. Yılmaz, and X. Wang, “Quickest detection of false data
injection attack in wide-area smart grids,” IEEE Trans. Smart Grid,
vol. 6, no. 6, pp. 2725–2735, 2015.
[25] J. Kim, L. Tong, and R. J. Thomas, “Subspace methods for data attack on
state estimation: A data driven approach.” IEEE Trans. Signal Process.,
vol. 63, no. 5, pp. 1102–1114, 2015.
[26] M. Garcia, T. Catanach, S. Vander Wiel, R. Bent, and E. Lawrence,
“Line outage localization using phasor measurement data in transient
state,” IEEE Trans. Power Syst., vol. 31, no. 4, pp. 3019–3027, 2016.
[27] N. M. Manousakis, G. N. Korres, and P. S. Georgilakis, “Taxonomy
of PMU placement methodologies,” IEEE Trans. Power Syst., vol. 27,
no. 2, pp. 1070–1077, 2012.
[28] K. Khandeparkar, P. Patre, S. Jain, K. Ramamritham, and R. Gupta,
“Efficient PMU data dissemination in smart grid,” in Proc. ACM eEnergy’14 (poster description), June 2014.
[29] Y. Zhao, J. Chen, A. Goldsmith, and H. V. Poor, “Identification of
outages in power systems with uncertain states and optimal sensor
locations,” IEEE J. Sel. Topics Signal Process., vol. 8, no. 6, pp. 1140–
1153, 2014.
[30] Z. Li, M. Shahidehpour, A. Alabdulwahab, and A. Abusorrah, “Bilevel
model for analyzing coordinated cyber-physical attacks on power systems,” IEEE Trans. Smart Grid, vol. 7, no. 5, pp. 2260–2272, 2016.
[31] R. Deng, P. Zhuang, and H. Liang, “Ccpa: Coordinated cyber-physical
attacks and countermeasures in smart grid,” IEEE Trans. Smart Grid,
2017.
[32] J. Zhang and L. Sankar, “Physical system consequences of unobservable
state-and-topology cyber-physical attacks,” IEEE Trans. Smart Grid,
vol. 7, no. 4, 2016.
[33] J. D. Glover, M. S. Sarma, and T. Overbye, Power System Analysis &
Design, SI Version. Cengage Learning, 2012.
[34] R. Bapat, Graphs and matrices. Springer, 2010.

