PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Computations of a Security Index for False Data Attacks in Power Networks

Julien M. Hendrickx, Karl Henrik Johansson, Raphael M. Jungers, Henrik Sandberg, Kin Cheong Sou

arXiv:1204.6174v2math.OCcs.SYeess.SY

TL;DR

False data attacks on communicated measurements threaten the integrity of power-network state estimation, and the general vulnerability-analysis problem is NP-hard. The paper reformulates the fully measured case as a standard minimum cut on a proportional-size auxiliary graph, yielding an exact efficient algorithm, while offering an efficient heuristic for the general problem.

Abstract

from arXiv · show

The resilience of Supervisory Control and Data Acquisition (SCADA) systems for electric power networks for certain cyber-attacks is considered. We analyze the vulnerability of the measurement system to false data attack on communicated measurements. The vulnerability analysis problem is shown to be NP-hard, meaning that unless $P = NP$ there is no polynomial time algorithm to analyze the vulnerability of the system. Nevertheless, we identify situations, such as the full measurement case, where it can be solved efficiently. In such cases, we show indeed that the problem can be cast as a generalization of the minimum cut problem involving costly nodes. We further show that it can be reformulated as a standard minimum cut problem (without costly nodes) on a modified graph of proportional size. An important consequence of this result is that our approach provides the first exact efficient algorithm for the vulnerability analysis problem under the full measurement assumption. Furthermore, our approach also provides an efficient heuristic algorithm for the general NP-hard problem. Our results are illustrated by numerical studies on benchmark systems including the IEEE 118-bus system.

I. INTRODUCTION

SCADA state estimation depends on communicated measurements, which can be manipulated through false data attacks. The paper analyzes this vulnerability and develops exact efficient methods for the fully measured case alongside an efficient approximation for the general problem.

I. INTRODUCTION

  • SCADA systems use RTUs to send measurements to state estimators, whose estimates support monitoring and control; malfunctions can have serious social and economic consequences.The 2003 Northeast US blackout is given as an example.Source: §I · p. 1
  • As SCADA systems connect to office LANs and the Internet, they gain more access points and functions to tamper with, including communicated measurements vulnerable to false data attacks.Prior work studies attacks that evade bad-data detection and sparse attacks that compromise relatively few meters; vulnerability information can help target limited protection resources.Source: §I · p. 1
  • Efficient attack construction matters for timely security analysis, but common polynomial-time approaches may be suboptimal and insufficiently accurate, while the considered problem is more general than some prior formulations.The paper identifies the problem in as its focus and contrasts it with the restrictions in and.Source: §I · pp. 1–2
  • Under full measurement, the vulnerability problem can be formulated as a generalized minimum cut and solved exactly in polynomial time, unlike prior work that supplied only approximate solutions.Full measurement means all bus injections and line power flows are metered; the paper also proposes an efficient heuristic for the general NP-hard problem.Source: §I · p. 2

A. Power Network Model and State Estimation

  • The network model represents buses and transmission lines as graph nodes and edges, with line reactances encoded by a positive-definite diagonal matrix.The DC power-flow model relates measurements to network states through the measurement matrix H.Source: A. Power Network Model and State… · p. 2
  • The measurement system is assumed observable: removing any column of H leaves a matrix of rank n, and one bus is designated as the reference with its phase angle set to zero.Measurement redundancy is assumed; the resulting reduced matrix H2: has full column rank.Source: A. Power Network Model and State… · pp. 2–3

B. Security Index

The security index measures the minimum number of measurements an attacker must compromise to alter a target measurement without detection. It identifies vulnerabilities that the state-estimation hat matrix alone may not reveal.

B. Security Index

  • A coordinated attack of the form H∆θ can produce zero residual, so the bad-data detection test can fail to detect it.The security index αk is defined as a cardinality-minimization objective for attacking measurement k without detection.Source: B. Security Index · p. 3
  • A small security index means the target measurement is relatively easy to compromise undetectably, and indices across measurements can guide protection with limited resources.Reference proposes using the indices to assign limited encryption resources.Source: B. Security Index · p. 3
  • For the example, security indices are 2, 3, 3, 1, and 2; the hat matrix suggests the critical fourth measurement's vulnerability but does not reveal that the first and last are also vulnerable.The specialized problem studied in Sections III–V constrains edge flows; the paper says its results extend to the general case.Source: B. Security Index · pp. 3–4

III. THE SECURITY INDEX PROBLEM IS NP-HARD

The security-index problem is NP-hard even for the power-network matrix structure, via a polynomial reduction from positive one-in-three 3SAT. The construction encodes binary variable assignments and clause satisfaction in the number of nonzero entries of HΔθ.

III. THE SECURITY INDEX PROBLEM IS NP-HARD

  • Unless P = NP, no polynomial-time algorithm solves problem (8) for the specified power-network matrix, even with D as identity and P2 = 0.Source: §III · p. 4
  • The hardness argument reduces from positive one-in-three 3SAT, which asks whether each triple can have exactly one entry equal to 1.Source: §III · p. 4
  • The reduction makes each variable node binary at the minimum count, then requires exactly one of each clause’s three variable values to be 1.A satisfying assignment exists if and only if the construction attains card(HΔθ) = n+1; the construction takes polynomial time.Source: §III · p. 4
  • Problem (5) is also NP-hard because problem (8) is its special case.Source: §III · p. 4

IV. TRACTABLE SPECIAL CASES OF THE SECURITY INDEX PROBLEM

The paper identifies full measurement as a tractable special case of the security-index problem. There, an optimal solution can be found by restricting the decision vector to binary values, a step toward a generalized minimum-cut formulation.

IV. TRACTABLE SPECIAL CASES OF THE SECURITY INDEX PROBLEM

A. The Security Index Problem Under Full Measurement Assumption

B. The Security Index Problem with Binary Decision Vector

The section relates the continuous security-index formulation to a binary restriction and gives conditions under which the two have equal optimal values. Otherwise, the binary formulation can provide an approximate solution with an error bound that may be conservative.

B. The Security Index Problem with Binary Decision Vector

  • When cij ∈ {0,1,2} and pi ∈ {0,1}, the generalized formulations recover the binary security-index problems.Source: B. The Security Index Problem with… · p. 5
  • Under the full measurement assumption, the two formulations have equal optimal values.The full measurement case corresponds to cij = 2 and pi = 1 for all relevant edges and nodes.Source: B. The Security Index Problem with… · p. 6
  • Other stated conditions also suggest equivalence, including a meter on each edge with at most one meter per node, or unmetered edges whose terminal nodes are also unmetered.These cases are expressed through conditions on cij and pi in Theorem 2.Source: B. The Security Index Problem with… · p. 6
  • The binary restriction’s error relative to the general formulation is bounded, but the bound can be conservative and difficult to tighten without solving the general problem.The proof’s tighter bound sums over a subset Vb, while the stated bound sums over all nodes.Source: B. The Security Index Problem with… · pp. 5–7

C. Reformulating the Security Index Problem into Generalized Min Cut Problem with Costly Nodes

The binary security-index problem can be viewed as a generalized minimum cut on the power-network graph, with costs on both edges and nodes. Under symmetric edge weights, the cut cost charges edges crossing the partition and nodes adjacent to a cut edge.

C. Reformulating the Security Index Problem into Generalized Min Cut Problem with Costly Nodes

  • The binary formulation is a generalized minimum cut: it partitions nodes while charging cut edges and nodes incident to at least one cut edge.The power-network graph is treated as undirected for this interpretation.Source: C. Reformulating the Security Index… · p. 7
  • In a directed graph, an edge is charged only when it points from the source-side set to the sink-side set; symmetric edge pairs remove this asymmetry.Source: C. Reformulating the Security Index… · p. 7
  • With symmetric weights cij = cji = 2 and node costs pi = 1, the generalized cut recovers the full-measurement problem.The auxiliary-graph figure depicts dashed vertical edges with weight pi and dotted diagonal edges with weight C > max pi.Source: C. Reformulating the Security Index… · p. 7, Figure 2 · p. 7

V. AN EFFICIENT SOLUTION TO THE TRACTABLE CASES OF THE SECURITY INDEX PROBLEM

The section presents an efficient solution to the minimum cut with costly nodes problem, which also solves the security-index problem under the full measurement assumption.

V. AN EFFICIENT SOLUTION TO THE TRACTABLE CASES OF THE SECURITY INDEX PROBLEM

  • Solving minimum cut with costly nodes efficiently also solves the full-measurement security-index problem, because it is a special case.Source: §V · p. 7

A. Construction of an Auxiliary Graph

The auxiliary graph replaces node costs with weighted edges and represents the original graph’s edge costs while preserving the costly-node cut objective.

A. Construction of an Auxiliary Graph

B. Equivalence with Min Cut on the Auxiliary Graph

The auxiliary-graph construction translates the costly-node cut problem into a standard Min Cut problem while preserving the optimal solution. The modified graph grows proportionally to the original, so standard polynomial-time Min Cut algorithms retain their complexity order.

B. Equivalence with Min Cut on the Auxiliary Graph

  • An optimal Min Cut partition of the modified graph translates directly into an optimal solution of Problem 1 on the original graph.The construction uses 3n nodes and 3|E| + 2n edges, proportional to the original graph’s size.Source: B. Equivalence with Min Cut on the… · p. 8
  • The construction preserves cut costs: each original cut has a matching modified-graph cut of equal cost, and translating an arbitrary modified cut back costs no more.The node weight is charged when an edge entering or leaving that node is cut; the two cases cannot occur simultaneously.Source: B. Equivalence with Min Cut on the… · p. 8
  • Standard polynomial-time Min Cut algorithms therefore solve Problem 1, and problems (9) and (8) in the fully measured case, without changing the algorithm’s polynomial order.Using the algorithm in [31] gives complexity O(n|E| + n^2log(n)) on the modified graph.Source: B. Equivalence with Min Cut on the… · p. 8
  • The method also solves in polynomial time a generalization assigning separate node weights to cut outgoing and incoming edges.This requires a corresponding modification to the auxiliary-graph construction.Source: B. Equivalence with Min Cut on the… · p. 8

VI. THE ORIGINAL SECURITY INDEX PROBLEM TARGETING EDGE AND NODE

The paper relates the original security-index problem to a binary restriction and to the specialized problem in (8). Under full measurement, solving the binary restriction solves the original problem exactly; outside that setting, the stated relationship is approximate with an error bound.

VI. THE ORIGINAL SECURITY INDEX PROBLEM TARGETING EDGE AND NODE

  • When the relevant row of H corresponds to P1DAT and −P2DAT, problem (5) can be restated as (8), and solving (9) either solves (5) exactly or approximately with an error bound.Exactness depends on the full-measurement assumption or similar assumptions; otherwise the error bound is given by (12).Source: §VI · pp. 8–9
  • For a target node corresponding to a row of P3ADAT, the nonzero-injection constraint requires at least one incident edge to have nonzero flow.The text considers instances parameterized by the incident-edge columns of A.Source: §VI · p. 9
  • When the full-measurement assumption does not hold, the approximation error bound may be conservative.The bound is obtained from (12).Source: §VI · p. 9

VII. NUMERICAL EXAMPLES

The numerical examples compare the proposed method with prior graph-based approaches and assess it on benchmark power networks. The examples report exactness and comparable computation time in the full-measurement case, and the strongest accuracy and efficiency among the tested Min Cut methods in the partial-measurement case.

A. Simple Illustrative Example of Problem 1

  • On that instance, methods and select {vs,v1,v2}, which is suboptimal for Problem 1 compared with {vs}, whose objective value is 8 rather than 9.Both earlier methods solve edge-weight-only Min Cut problems, handling node weights differently.Source: A. Simple Illustrative Example of… · p. 9
  • For the illustrative instance, the proposed procedure returns source set {vs} with objective value 8, correctly solving Problem 1.The auxiliary graph’s optimal source set is {vs,w1,w2}, also with objective value 8.Source: A. Simple Illustrative Example of… · p. 9, Figure 4 · p. 10

B. The Security Index Problem on Benchmark Systems

  • The benchmark study includes the IEEE 118-bus and Polish 2383-bus systems, with the 118-bus system also used for partial-measurement tests.The partial-measurement setup randomly selects measurements and verifies observability.Source: B. The Security Index Problem on… · pp. 9–10
  • In the full-measurement tests on the 118-bus and 2383-bus systems, the proposed method guarantees exact solutions, while the compared methods also produced exact solutions experimentally but without a theoretical guarantee.The methods had similar computation times, so the proposed optimality guarantee came at no additional computational cost.Source: B. The Security Index Problem on… · pp. 9–10, Table II · p. 10
  • Among the three Min Cut-based methods tested for partial measurements, the proposed method gives the most accurate suboptimal solutions and is the most efficient in computation time.The comparison uses big-M security indices as the reference; about 50% of injections and flows are measured in the 118-bus test.Source: B. The Security Index Problem on… · p. 10, Table III · p. 10

VIII. CONCLUSIONS

Under full measurement, the security index problem can be solved exactly and efficiently by reducing it to a standard minimum-cut problem on an auxiliary graph of proportional size. For general partially measured systems, the method offers an approximation without a known accuracy guarantee, while efficient design methods remain an open question.

VIII. CONCLUSIONS

  • Under full measurement, the costly-node minimum-cut formulation is equivalent to a standard minimum-cut problem on an auxiliary graph of proportional size, enabling exact, efficient security-index computation.The index gives the minimum number of measurements that must be tampered with to feed incorrect information to SCADA without detection by a BDD method.Source: §VIII · p. 11
  • Figure 8 compares inexact security-index estimates from [18] with big M results, while Figure 9 compares estimates from this paper with big M results for the partially measured 118-bus system.The supplied captions identify circles as inexact estimates and crosses as the corresponding big M estimates, but state no outcome of the comparison.Source: Figure 8 · p. 11, Figure 9 · p. 11
  • For general partially measured systems, the approach provides an approximate solution, but its accuracy guarantee and efficient approximability remain unresolved.The paper also notes an equivalent full-measurement robustness problem concerning observability under measurement failures.Source: §VIII · p. 11
  • Whether efficient design methods can optimize the security index under natural constraints remains an open question.Source: §VIII · p. 11
Loading 1204.6174v2…