Cyber Security Analysis of Power Networks
by Hypergraph Cut Algorithms
Yutaro Yamaguchi1, Anna Ogawa2,
Akiko Takeda1, Satoru Iwata1
1. Department of Mathematical Informatics, University of Tokyo
2. Department of Administration Engineering, Keio University
SmartGridComm 2014 @Venice

November 4, 2014

Cyber Threat to Power Networks
Power network

State

Measurement

Estimate
to control

System administrator

Cyber Threat to Power Networks
Power network

State

False datainjection

Measurement

Misrecognize!!

System administrator

Outline• Model and Problem Definitions— Undetectable (false data injection) attacks— Sparsest attack problem (Global security analysis)— Security index problem (Local security analysis)• Existing Methods vs. Proposed Methods— Approx. by LP-relaxation— Approx. by min-cut in graphs— Exact by min-cut in auxiliary graphs— Exact by min-cut in hypergraphs (Proposed)• Experimental Results

Outline• Model and Problem Definitions— Undetectable (false data injection) attacks— Sparsest attack problem (Global security analysis)— Security index problem (Local security analysis)• Existing Methods vs. Proposed Methods— Approx. by LP-relaxation— Approx. by min-cut in graphs— Exact by min-cut in auxiliary graphs— Exact by min-cut in hypergraphs (Proposed)• Experimental ResultsLinearized State Estimation Model
Power network

StateMeasurement

Estimate

System administrator

Linearized State Estimation Model
Power network

StateMeasurement

Estimate

𝐺 = 𝑉, 𝐴 : directed graph

System administrator

Linearized State Estimation Model
Power network

State: Voltage angle on each node𝜃 ∈ 𝐑𝑉

voltage angle

Measurement

Estimate

𝐺 = 𝑉, 𝐴 : directed graph

System administrator

Linearized State Estimation Model
Power network

State: Voltage angle on each node𝜃 ∈ 𝐑𝑉

power injection
power flow

Measurement: Active power
on arcs & nodes𝑧 ∈ 𝐑𝐴∪𝑉Estimate

𝐺 = 𝑉, 𝐴 : directed graph

System administrator

Linearized State Estimation Model
Power network

State: Voltage angle on each node𝜃 ∈ 𝐑𝑉

Measurement: Active power
on arcs & nodes𝑧 ∈ 𝐑𝐴∪𝑉Estimate𝑧 = 𝐻𝜃
𝐺 = 𝑉, 𝐴 : directed graph𝐻 ∈ 𝐑 𝐴∪𝑉 ×𝑉
System administrator

False Data Injection
Power network

State on each node: 𝜃 ∈ 𝐑𝑉𝑧 = 𝐻𝜃

𝐻 ∈ 𝐑 𝐴∪𝑉 ×𝑉

Measurement on arcs & nodes:𝑧 ∈ 𝐑𝐴∪𝑉𝑧 + Δ𝑧

Estimate
False datainjectionΔ𝑧 ∈ 𝐑𝐴∪𝑉
System administrator

False Data Injection
Power network

State on each node: 𝜃 ∈ 𝐑𝑉𝑧 = 𝐻𝜃

𝐻 ∈ 𝐑 𝐴∪𝑉 ×𝑉

Measurement on arcs & nodes:𝑧 ∈ 𝐑𝐴∪𝑉𝑧 + Δ𝑧

Estimate
False datainjectionΔ𝑧 ∈ 𝐑𝐴∪𝑉
Anything
is OK.

𝑧 + Δ𝑧 = 𝐻𝜃 ??
No such 𝜃 !!
Something wrong!!
Detectable!!

System administrator

False Data Injection
Power network

State on each node: 𝜃 ∈ 𝐑𝑉

𝑧 = 𝐻𝜃

𝐻 ∈ 𝐑 𝐴∪𝑉 ×𝑉

Measurement on arcs & nodes:𝑧 ∈ 𝐑𝐴∪𝑉𝑧 + Δ𝑧

Estimate
False datainjectionΔ𝑧 ∈ 𝐑𝐴∪𝑉Δ𝑧 = 𝐻Δ𝜃Δ𝜃 ∈ 𝐑𝑉𝑧 + Δ𝑧 = 𝐻𝜃 ??
OK, 𝜃 = 𝜃 + Δ𝜃 !!
Misrecognize!!

System administrator

Undetectable (False Data Injection) Attack(Liu, Ning, Reiter 2009)

A difference Δ𝑧 ∈ 𝐑 𝐴∪𝑉 of measurement values
is called an undetectable attack.
def⇔ ∃Δ𝜃 ∈ 𝐑𝑉 s.t. Δ𝑧 = 𝐻Δ𝜃Actual:𝑧 + Δ𝑧 = 𝐻𝜃Attack:𝑧 + Δ𝑧 = 𝐻Δ𝜃Misrecognition:𝑧 + Δ𝑧 = 𝐻(𝜃 + Δ𝜃)Sparsest Attack (Global Security)(Liu, Ning, Reiter 2009)

A nonzero undetectable attack 𝐻Δ𝜃 ∈ 𝐑 𝐴∪𝑉 ∖ 𝟎with the fewest nonzero entries (attacked points)
minimize
𝑉𝐻Δ𝜃 0subject to𝐻Δ𝜃 ≠ 𝟎Δ𝜃∈𝐑Attacking many points→ Easy to preventΔ𝑧 = 𝐻Δ𝜃

Attacking few points→ Hard to preventΔ𝑧 = 𝐻Δ𝜃Security Index (Local Security)(Sandberg, Teixeira, Johansson 2010)

The minimum number of nonzero entries ofan undetectable attack 𝐻Δ𝜃 ∈ 𝐑 𝐴∪𝑉to attack a specified arc or node 𝑘 ∈ 𝐴 ∪ 𝑉
minimize
𝑉Δ𝜃∈𝐑𝐻Δ𝜃 0

subject to 𝐻𝑘 Δ𝜃 ≠ 0
Attacking many points→ Easy to prevent𝑘Δ𝑧 = 𝐻Δ𝜃Attacking few points→ Hard to prevent𝑘Δ𝑧 = 𝐻Δ𝜃

Sparsest Attack and Security Index
Fact

Any sparsest attack attains the security indicesof the arcs and nodes to be attacked.
Δ𝑧 is a sparsest attack.
𝑘Δ𝑧(security index of 𝑘) = Δ𝑧 0

Sparsest Attack and Security Index
Fact

Any sparsest attack attains the security indicesof the arcs and nodes to be attacked.
Δ𝑧 is a sparsest attack.
𝑘Δ𝑧(security index of 𝑘) = Δ𝑧 0

A sparsest attack can be foundby computing the security indices of ALL arcs and nodes!

Sparsest Attack and Security Index
Fact

Any sparsest attack attains the security indicesof the arcs and nodes to be attacked.
Fact

The security index of a node is equal tothe minimum security index among its incident arcs’.
𝑎1𝑣 𝑎2𝑎3(S.I. of 𝑣) = min (S.I. of 𝑎𝑖 )𝑖=1,2,3

A sparsest attack can be foundby computing the security indices of ALL arcs!!!

Outline• Model and Problem Definitions— Undetectable (false data injection) attacks— Sparsest attack problem (Global security analysis)— Security index problem (Local security analysis)• Existing Methods vs. Proposed Methods— Approx. by LP-relaxation— Approx. by min-cut in graphs— Exact by min-cut in auxiliary graphs— Exact by min-cut in hypergraphs (Proposed)• Experimental Results

Solution Methods for Security Index
Approx. by min-cut

Approx. by LP-relax(Sou, Sandberg, Johansson 2011)(Sou, Sandberg, Johansson 2013)

Exact by min-cut
in auxiliary graph(Hendrickx, Johansson, Junger,Sandberg, Sou 2012)

Exact by min-cutin hypergraphSolution Methods for Sparsest attack
Approx. by min-cut

Approx. by LP-relax(Sou, Sandberg, Johansson 2011)(Sou, Sandberg, Johansson 2013)

Security indices of ALL arcs

Exact by min-cut
in auxiliary graph(Hendrickx, Johansson, Junger,Sandberg, Sou 2012)

Exact by min-cut
in hypergraphSingle computation!!

Why min-cut?

Elementary Attack
Δ𝜃 = 0Δ𝜃 = 1

An undetectable attack 𝐻Δ𝜃 ∈ 𝐑 𝐴∪𝑉
defis elementary. ⇔ Δ𝜃 ∈ 0, 1 𝑉Lemma (Sou et al. 2011)

For any arc or node, there exists
an elementary attack attaining the security index.
→ Consider only elementary attacks→ Assign 0 or 1 to each node (Bipartition the node set 𝑉)

Elementary Attack
Δ𝜃 = 0An undetectable attack 𝐻Δ𝜃 ∈ 𝐑
defis elementary. ⇔ Δ𝜃 ∈ 0, 1 𝑉

𝐴∪𝑉𝑢Δ𝜃 = 1𝑣

Fact

An arc 𝑢𝑣 ∈ 𝐴 is attacked in an elementary attack.
⇔ Δ𝜃 𝑢 ≠ Δ𝜃 𝑣
⇔ 𝑢𝑣 is cut off by separating 0-nodes and 1-nodes.
→ # of attacked arcs = # of arcs cut off = cut capacity→ Approx. by min-cut (Sou et al. 2011)

Elementary Attack
Δ𝜃 = 0An undetectable attack 𝐻Δ𝜃 ∈ 𝐑
defis elementary. ⇔ Δ𝜃 ∈ 0, 1 𝑉

𝐴∪𝑉𝑢Δ𝜃 = 1𝑣

Fact

An arc 𝑢𝑣 ∈ 𝐴 is attacked in an elementary attack.
⇔ Δ𝜃 𝑢 ≠ Δ𝜃 𝑣
⇔ 𝑢𝑣 is cut off by separating 0-nodes and 1-nodes.
→ # of attacked arcs = # of arcs cut off = cut capacity→ Approx. by min-cut (Sou et al. 2011) How about attacked nodes?

Counting Attacked Nodes
Construct auxiliary graph(Hendrickx, Johansson, Junger,Sandberg, Sou 2012)

Use hypergraph• Large size

• No additional node

• A sparsest attack requires(# of arcs) min-cut comps.

• A sparsest attack can be foundby single min-cut computation!!

Hypergraphs
Undirected graph

Hypergraphhyperedgeedge ⇔ hyperedgeof size 2

Each edge connects two nodes.

Each hyperedge connects
an arbitrary number of nodes.

Construction of Hypergraph• Start with the input graph (ignoring the direction)

Construction of Hypergraph• Start with the input graph (ignoring the direction)• For each node 𝑣 ∈ 𝑉, add a hyperedge consisting of
the node 𝑣 itself and all neighbors of 𝑣.

𝑣

Construction of Hypergraph• Start with the input graph (ignoring the direction)• For each node 𝑣 ∈ 𝑉, add a hyperedge consisting of
the node 𝑣 itself and all neighbors of 𝑣.

Construction of HypergraphLemma (Y.-O.-T.-I. 2014)

Cut capacity in this hypergraph# of arcs & nodes to be attackedΔ𝜃 = 0Δ𝜃 = 1

Computing Security Index
Computing the security index of an arc 𝑎 = 𝑠𝑡 ∈ 𝐴→ Finding a minimum 𝑠—𝑡 cut in a hypergraphΔ𝜃 = 1Δ𝜃 = 0𝑠𝑎𝑡
Fact
An arc 𝑠𝑡 ∈ 𝐴 is attacked.
⇔ Δ𝜃 𝑠 ≠ Δ𝜃 𝑡
⇔ 𝑠𝑡 is cut off.

Computing Security Index
Computing the security index of an arc 𝑎 = 𝑠𝑡 ∈ 𝐴→ Finding a minimum 𝑠—𝑡 cut in a hypergraph
Theorem (Y.-O.-T.-I. 2014)

For any arc in any directed graph 𝐺 = 𝑉, 𝐴 ,one can compute the security index in O 𝑉 𝐴 time.
• By a hypergraph min 𝒔—𝒕 cut algorithm (Pistorius, Minoux 2003)• The same order as the existing exact method (Hendrickx et al. 2012),
but faster in practice because their auxiliary graph is large.

Finding Sparsest Attack
Finding a sparsest attack in the whole network→ Finding a minimum cut in a hypergraph
Theorem (Y.-O.-T.-I. 2014)

For any directed graph 𝐺 = 𝑉, 𝐴 , one can finda sparsest attack in O 𝑉 𝐴 + 𝑉 2 log 𝑉 time.
• By a hypergraph min-cut algorithm (Klimmek, Wagner 1996)• Essential speeding up!!
Applying the existing exact method (Hendrickx et al. 2012) to all arcs
→ O 𝑉 𝐴 2 timeOutline• Model and Problem Definitions— Undetectable (false data injection) attacks— Sparsest attack problem (Global security analysis)— Security index problem (Local security analysis)• Existing Methods vs. Proposed Methods— Approx. by LP-relaxation— Approx. by min-cut in graphs— Exact by min-cut in auxiliary graphs— Exact by min-cut in hypergraphs (Proposed)• Experimental Results

Problems and Solution Methods• Finding a sparsest attack in the whole network― hyp. global min. cut: exact method by hypergraph min-cut• Computing the security index of an arc 𝑎 ∈ 𝐴

Proposedmethods― hyp. min. s-t cut: exact method by hypergraph min-cut― min. s-t cut exact: exact method by min-cut in auxiliary graph(Hendrickx et al. 2012)― min. s-t cut relax: approx. method by min-cut in input graph(Sou et al. 2011)― L1-relax (LP): approx. method by LP-relaxation (Sou et al. 2013)― L0-exact (MIP): exact method by MIP solver (CPLEX)

minimize𝑉Δ𝜃∈𝐑𝐻Δ𝜃 0

subject to 𝐻𝑎 Δ𝜃 ≠ 0Computational Time for Security Index
Proposed method

Fails to obtain an exact solution
for 10~20% arcs

About 1.8 times faster on averagethan the existing exact method.

IEEE data sets

Tokyo-Tohoku Polish systems(East Japan)

Computational Time for Sparsest Attack
Proposed methods Predominantly fastest!!

IEEE data sets

Tokyo-Tohoku Polish systems(East Japan)

Conclusion• A sparsest attack andthe security index of each measurement point
are significant security criteria for power networks.
• A sparsest attack can be found fast and exactly
by finding a minimum cut in a hypergraph.
• The security index of each measurement point
can be computed fast and exactly
by finding a minimum 𝑠—𝑡 cut in a hypergraph.