{'fraction_non_alphanumeric': 0.03404230808000806, 'fraction_numerical': 0.013017870771712051, 'mean_word_length': 4.201408134222156, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 22, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Graph-Theoretic Framework for Unified Analysis of Observability and Data Injection Attacks in the Smart Grid

In this paper, a novel graph-theoretic framework is proposed to generalize the analysis of a broad set of security attacks, including observability and data injection attacks, that target the state estimator of a smart grid. First, the notion of observability attacks is defined based on a proposed graph-theoretic construct. In this respect, a structured approach is proposed to characterize critical sets, whose removal renders the system unobservable. It is then shown that, for the system to be observable, these critical sets must be part of a maximum matching over a proposed bipartite graph. In addition, it is shown that stealthy data injection attacks (SDIAs) constitute a special case of these observability attacks. Then, various attack strategies and defense policies, for observability and data injection attacks, are shown to be amenable to analysis using the introduced graph-theoretic framework. The proposed framework is then shown to provide a unified basis for analysis of four key security problems (among others), pertaining to the characterization of: 1) The sparsest SDIA; 2) the sparsest SDIA including a certain measurement; 3) a set of measurements which must be defended to thwart all potential SDIAs; and 4) the set of measurements, which when protected, can thwart any SDIA whose cardinality is below a certain threshold. A case study using the IEEE 14-bus system with a set of 17 measurements is used to support the theoretical findings.


I. INTRODUCTION
With the integration of information and communication technologies in power systems, new security concerns have emerged due to the potential exploitation of this cyber layer to infiltrate and compromise the underlying physical system. Indeed, in recent years, various studies have focused on analyzing the security of emerging cyber-physical power systems [1]- [7] and the effect of potential cyber attacks on the various operational components of the grid, ranging from power system state estimation [2], to electricity markets [3]- [5] and power system dynamics and control [6], [7].
Such attacks can become more pronounced when they target critical power system functions such as state estimation. In this regard, the power system state estimation is an integral smart grid process in which system-wide measurements are collected and processed to estimate the global state of operation of a power system [8]. State estimation is the basis for various grid operational decisions such as congestion management, economic dispatch, contingency analysis, and electricity pricing [9]. As a result, the critical importance of state estimation to the sustainable operation of the grid makes it a primary target of possible cyberphysical attacks [1]. Such attacks may target the availability of the collected measurements as well as their integrity.
In this respect, intercepting a subset of the collected measurement data using availability attacks (such as denial-of-service attacks) can render the power system unobservable (i.e. not fully observable), a state in which the collected measurements do not provide enough independent equations to estimate the states. Such cyber-physical attacks, to which we refer as observability attacks hereinafter, will make the operator partially oblivious to the real state of operation of the system, leading to uninformed operational decisions. Beyond observability attacks, data injection attacks (DIAs) have emerged as a malicious type of integrity attacks which aim at manipulating the collected state estimation data, leading to inaccurate state estimation outcomes that result in misinformed operational decisions with potentially detrimental consequences [1]- [3]. As shown in [2], such DIAs can stealthily target the power system state estimation processmanipulating the collected measurements and altering the state estimation outcome -while being undetectable by the system operator using traditional bad data detection mechanisms. Hence, due to their potential danger to system operation, such stealthy data injection attacks (SDIAs) and observability attacks have been the focus of various recent research efforts [10]- [16].

A. Related Works
In this regard, the works in [10] and [11] focused on computing a security set which comprises the minimum set of measurements which must be attacked in addition to a certain specific measurement in order to make the system unobservable. Moreover, the work in [12] focused on computing the cardinality of the smallest set of meters which when attacked render the system unobservable. The authors in [13]- [15] extended such observability problems to studying SDIAs. In this regard, these works focused on characterizing the sparsest stealthy attack containing a certain specific measurement. In addition, the work in [16] focused on characterizing a set of measurements to defend so that no attack which concurrently manipulates a set of meters whose cardinality is below a certain threshold can be stealthy. Hence, this latter analysis focuses on the defense against resource-limited attackers. As such, these works have focused on formulating and studying mathematical problems whose solutions enable anticipating potential sophisticated attacks -which constitutes a first step towards deriving corresponding defense mechanisms -and designing optimal defense strategies to thwart such attacks and mitigate their potential effect.
The computational complexity of these problems [10]- [16] has led to limiting the analysis of their solutions to special, often approximated, cases or required the use of heuristics and relaxation techniques which led to suboptimal solutions. For example, for characterizing the sparsest observability attacks containing a specific measurement, the work in [10] focused on the special case of measurement sets of low cardinality while the work in [11] derived an approximate solution that is based on the solution of a min-cut problem. In addition, with regard to the analysis of the sparsest SDIAs containing a certain measurement [13]- [15], the work in [13] focused on deriving an upper-bound on this stealthy attack set while the work in [14] used min-cut relaxation techniques to approximate the sought solution. Moreover, the work in [15] proposed a heuristic algorithm which can approximate the solution of the studied problem while an exact solution was found for the special case in which power flows over all the transmission lines and power injections into and out of every bus are assumed to be measured. To defend against a resource-limited data injection attacker, the authors in [16] used an l 1 relaxation method for characterizing the set of meters to defend to thwart SDIAs launched by attackers whose attack space is limited by a certain cardinality threshold. Other related security works are also found in [17]- [22]. Therefore, this rich body of literature [10]- [22] employs heuristics and approximation techniques to numerically approximate the solutions to these fundamental observability attacks and SDIA problems rather than propose new analytical methods for studying these problems and characterizing their solutions. As such, there is a need for an analytical framework which allows modeling and studying such data availability and integrity attacks and enables an analytical characterization of solutions to such widely-studied security problems. In addition, the fact that these works [10]- [16] studied correlated problems but from different perspectives highlights the need for a unified framework using which solutions to such correlated observability attacks and SDIA problems can be studied and derived.

B. Contributions
The main contribution of this paper is a novel unified graphtheoretic framework that enables a global detailed modeling and understanding of observability attacks and SDIAs. As a result, this framework provides a unified tool for analyzing various widely-studied observability attacks and SDIA problems such as those studied in [10]- [16], among others. In addition, the proposed framework enables a graph-theoretic characterization of solutions to such security problems. In this regard, our proposed framework is based on a shift in the modeling of observability attacks and SDIAs from a linear algebra frame of reference to a graph-theoretic perspective. As a result, based on this proposed framework, such attacks can be modeled and analyzed by requiring only power system topological data, namely, the power system 1-line diagram and the location of deployed measurement units without the need for neither line parameters data nor the exact knowledge of power flow levels throughout the system.
To build the proposed framework, we first begin by introducing a graph-theoretic basis of observability attacks and, then, we prove that SDIAs are a special case of such observability attacks. In this respect, we introduce an algorithm providing a step-bystep approach for building critical sets, a set of measurements z ∈ R µ measurement vector with µ measurements x ∈ R ν state vector with ν states H ∈ R µ×ν system's Jacobian matrix G(N , L) set of lines connecting subgraphs G m 1 and G m 2 M m set of measurements on or incident to L m excluding m -containing a certain specific measurement -which, when removed, renders the system unobservable. We then prove that for a DIA to be stealthy, the attacked measurements should strictly result in leaving critical sets unmatched as part of a maximum matching over an introduced bipartite graph. As such, a graph-theoretic model of SDIAs is then introduced based on which we analyze various well-studied SDIA problems. In particular, we show that our developed framework enables a graph-theoretic characterization of solutions to various SDIA problems such as, but not limited to: 1) Finding the stealthy attack of lowest cardinality, 2) Finding the stealthy attack of lowest cardinality, including a specific measurement, 3) Finding a set of measurements which when defended can thwart all possible stealthy attacks, and 4) Finding a set of measurements to defend against a resource-limited attacker, among others. Here, we note that our goal is not to propose tractable algorithms to these problems, but rather to identify graph-theoretic problems whose solutions would lead to the solutions of these problems. A case study using the IEEE 14-bus system, with 17 distributed measurement units, is considered throughout the paper to showcase the developed analytical concepts. The rest of the paper is organized as follows. Section II introduces state estimation and power system observability. Section III introduces our proposed graph-theoretic foundation of observability attacks and shows its impact on modeling and analyzing such data availability attacks. Section IV introduces the proposed graph-theoretic framework for modeling SDIAs, as well as investigates various well-studied SDIA problems. Section V concludes the paper and provides an outlook detailing the impact of the proposed framework on studying future observability and data injection attacks.
A summary of the main notations used in this paper is given in Table I.

II. STATE ESTIMATION AND OBSERVABILITY
We next provide an overview of state estimation and of the algebraic and topological concepts of observability in power systems. This overview provides background material which is useful for the analysis that follows.

A. State Estimation Process
Consider a power system state estimation process which uses various measurements collected from across the system to estimate the voltage magnitudes and phase angles at every bus in the system, known as the system states [8]. Let z ∈ R µ (µ being the number of measurements) be the vector of collected measurements, which includes power flow levels (real and reactive) over transmission lines, power (real and reactive) injected in or withdrawn from certain buses, as well as bus voltage magnitudes. In addition, let x ∈ R ν be the vector of system states. The relationship between the measurements and the states directly follows from the linearized power flow equations [8]: where H ∈ R µ×ν is the measurement Jacobian matrix and e ∈ R µ is the vector of random errors that typically follows a Gaussian distribution, N (0, R), where R is positive definite.
Here µ ≥ ν, that is the dimension of x cannot be larger than the dimension of the measurement vector, z. Further, we assume that H is a full column rank matrix. Using a maximum-likelihood estimator -a weighted least squares estimator (WLS) for a Gaussian error vector e -an estimate of the states,x, will be: This estimate of all the states provides visibility of the steadystate operating conditions of the system, based on which various operational decisions are performed [8].

B. Power System Observability
The observability 1 of the power system consists of the ability to uniquely determine its states based on the collected set of measurements [8]. Observability, hence, requires the collected measurements to provide a sufficient number of independent equations to allow for the estimation of the state vector, x. Otherwise, when this observability condition is not met, the power system is dubbed unobservable. The power system is observable if and only if the measurement matrix H is of full column rank [8], which was our initial assumption. This is known as algebraic observability, as it enables assessment of observability using linear algebra. Due to the P − θ, Q − V decoupling 2 in power systems [9], the observability analysis can be decoupled by separately studying the observability of voltage phase angles, using real power measurements, and the observability of voltage magnitudes, based on reactive power measurements. Since the two analyses are identical, we focus here on phase angle observability. To this end, we consider z ∈ R µ to be a vector of real power measurements (bus injections and line flows), and the state vector x ∈ [−π, π] ν to be the vector of voltage phase angles (in radians). Here, ν = N − 1 for a power system with N buses given that the phase angle of the reference bus is fixed and is taken to be the reference with respect to which all other phase angles are calculated [8].
An alternative measure of observability, which turns out to be equivalent to algebraic observability, has been proposed in [23] and uses graph-theoretic techniques to introduce the concept of topological observability. Topological observability is equivalent to algebraic observability, in the sense that it enables assessment of the observability of the power system using graph-theoretic tools rather than using linear algebra as done for algebraic observability. In this regard, let the power system 1-line diagram be represented as a graph G(N , L) in which the set of vertices N , |N | = N , represents the set of buses of the power system while the set of branches L, |L| = L, represents the set of lines. One key result that was shown in [23] and that will be of relevance to our work is the following: Proposition 1 ( [23] ): A power system is observable if and only if a subset of measurements can be assigned to a subset of edges of the power system graph G(N , L), following a set of assignment rules, in a way to form a spanning tree over G(N , L). A spanning tree over G(N , L) is an acyclic connected subgraph of G(N , L) which contains (i.e. is incident to) the entire set of nodes N of G(N , L). The set of measurement assignment rules are the following: 1) A measurement cannot be simultaneously assigned to two different lines. 2) If m is a measurement over a transmission line l, then m can only be assigned to l. 3) If m is an injection measurement over bus η ∈ N , then m can only be assigned to an unmeasured line l that is incident to η. If a measurement assignment yields a spanning tree over the power network G, then the power system will be observable (and vice versa). Fig. 1 shows an example of measurement assignments over the IEEE 14-bus system. This figure shows the tree edges (marked in solid red lines) to which measurement where assigned as part of the measurement assignment function. The measurements that were assigned to each one of these edges are identified using dashed arrow lines originating from the assigned measurement and pointing to the line to which this measurement is assigned. This tree is formed of edges {1, 2, 4, 6, 8, 9, 10, 12, 13, 15, 16, 17, 19} and spans the whole vertex set N of the power system graph G, and hence, is a spanning tree. As a result, since this measurement assignment yields a spanning tree, then the available set of measurements renders the system observable.
Let M be the set of measurements, and let T (N , B) be a spanning tree formed by an assignment of a subset of measurements, M A ⊆ M, to a subset of lines B ⊆ L following the measurement assignment rules in Proposition 1. The assignment of measurements in M A to lines in B for constructing the spanning tree T (N , B) can be modeled by an assignment function f (.) formally defined [23] as follows: Definition 1: For an assigned set of measurement M A forming a spanning tree T (N , B) over the power system graph G(N , L), the assignment function f (.) : M A → B indicates which measurement m ∈ M A is assigned to which edge b ∈ B of the spanning tree T (N , B).
For example, in Fig. 1, M A is composed of the injection measurements over buses 1, 2, 3, 5, 6, 9, and 13 and the line flow measurements over lines 2, 8, 9, 15, 17, and 19. In addition, B = {1, 2, 4, 6, 8, 9, 10, 12, 13, 15, 16, 17, 19}, where each edge of B in Fig. 1 is colored in red. Moreover, the corresponding assignment function f (.) is visualized in Fig. 1 by dashed red  Here, we note that due to this redundancy, a spanning tree which can be obtained from the measurement set following the measurement assignment rules may not be unique [23]. Hence, when such a redundancy exists, following a different assignment function can result in a different spanning tree and, hence, in different sets of assigned and redundant measurements. Various algorithms of low complexity have been proposed to find and build such a spanning tree [23]- [25]. In this regard, the work in [23] proposes an algorithm to find a spanning tree over G, which will be used in some of the derivations in the following sections. This algorithm starts by processing flow measurements by assigning each flow measurement to its corresponding branch to form disjoint tree components. Then, injection measurements are assigned to lines in a way to connect these tree components to form one spanning tree. Here, we highlight one type of injection measurements, namely, boundary injections, which will play a crucial role in our derivations.
Definition 2: A boundary injection is an injection measurement over a bus incident to lines whose flow is measured and lines whose flow is not measured [23].
Boundary injections play a major role in connecting these tree components. Indeed, for a bus which is not incident to a measured line to be connected to the spanning tree, it has to be reachable from a boundary injection through a series of measurement assignments [23]. As such, boundary injections are considered to be sources and unmeasured buses are considered to be sinks which must be connected to these sources following the set of measurement assignment rules.
We next build on the foundation of topological observability to present a graph-theoretic framework for modeling and studying the security of the smart grid facing observability attacks and SDIAs. This framework is based on our proposed concepts of critical sets and observability sets, which we define and derive in the next section.

III. OBSERVABILITY ATTACKS
The sustainable and efficient operation of the power system requires an accurate observability of all its states [8]. Security attacks that target this observability can cause a limited (or partial) monitoring ability for the operator over the power system which can lead to incorrect operational decisions. Hence, studying and modeling attacks which can target the full observability of the system is indispensable to the sustainable operation of the grid. In this respect, we define a cyber-physical attack, dubbed observability attack, that consists of launching a denialof-service (DoS) attack against a set of measurements to make the system unobservable. We next study this type of attacks by introducing and characterizing what we define as critical sets and observability sets and prove that the well-studied stealthy data injection attack is a subset of our defined observability attacks. This latter finding will provide us with a unified set of tools to characterize solutions to various widely-studied SDIA problems.

A. Critical Sets
Understanding and modeling observability attacks requires an in-depth understanding of the effect of the loss of any bundle of measurements on the observability of the system. In this regard, we next introduce a structured method for identifying, for each measurement m, a minimal set of measurements including m (which we refer to as a critical set of m), which when removed renders the system unobservable. To this end, we first characterize the set of potential measurements to be investigated, for each measurement m, and then provide the necessary discussion and introduce the underlying method for characterizing a critical set of m. Then, a detailed algorithm is introduced to provide a step-by-step method for characterizing such critical sets.
As defined in Section II-B, we let M A ⊆ M be a set of assigned measurements, i.e., a subset of measurements that are assigned to a subset of lines of the power system graph G(N , L), following the measurement assignment rules in Proposition 1, to form a spanning tree, T (N , B), over this graph. As described in Section II-B, T (N , B) is a spanning tree as it includes all the nodes of G(N , L). The set of edges of this tree, i.e. B, represents the set of lines to which measurements in M A were assigned to construct the spanning tree. We refer to measurements that are not part of M A as unassigned measurements. We consider that the system is originally observable. Hence, such a spanning tree and its corresponding set of assigned measurements exist.
In this regard, consider a spanning tree T (N , B) resulting from a measurement assignment and consider an assigned measurement m ∈ M A . Since m is assigned to a line f (m) to build the spanning tree T (N , B), its removal will split the original tree T (N , B) into two trees Here, f (F 2 ) is line 2. Fig. 2 represents the same system shown in Fig. 1 and will be used hereinafter to provide a practical example of the defined concepts and analytical derivations. As can be seen from Fig. 2, since F 2 was assigned to line 2, when the measurement assignment is not modified (i.e. not considering the redundant measurements), the removal of F 2 will split the original tree T (N , B), represented in solid red lines in Fig. 1, into two trees each of which spans a subgraph of G (N , B), namely, subgraphs G F2 1 and G F2 2 in Fig. 2. We let L m be the set of lines connecting a bus in G m 1 to a bus in G m 2 . In addition, let N m 1,2 ⊆ N m 1 and N m 2,1 ⊆ N m 2 be the set of nodes in, respectively, N m 1 and N m 2 which are connected to a node in, respectively, N m 2 and N m 1 . An example of these notations is provided in Fig. 2, for m F 2 . L m is, hence, formally defined as: G m 1 and G m 2 are two disjoint subgraphs of G. Hence, for any tree to potentially span G, it must connect G m 1 and G m 2 (i.e. connect at least one node of G m 1 to a node in G m 2 ), which can only be achieved by assigning a measurement to a line in L m . In this regard, we define M L m to be the set of line measurements over lines in L m and injection measurements over buses incident to L m , i.e., buses in {N m 1,2 ∪ N m 2,1 }. Based on the measurement assignment rules described in Section II-B, also summarized in Proposition 1, only measurements in M L m could be potentially assigned to a line in L m . As a result, removing all of the measurements in M L m will guarantee that the system becomes unobservable, as it guarantees that two subgraphs of G would never be connected by any measurement assignment, making it, thus, impossible to build a spanning tree over G. Hence, the removal of M L m is a sufficient condition for causing the unobservability of the system. However, removing the entire set M L m may be more than required to prevent any possible measurement assignment (or constructed tree) from connecting G m 1 and G m 2 ; a goal which could be achieved by the removal of only a subset of M L m , as we investigate next.
In this regard, for the pair of subgraphs G m 1 and G m 2 , resulting from the spanning tree T , we define a set of measurements, C m ∈ M L m , for each measurement m ∈ M A , to which we refer as a critical set of m, as follows: Definition 3: For a measurement m ∈ M A and the pair of , a critical set of m, denoted by C m ⊆ M L m , is a maximal set of measurements 3 within M L m (i.e., the measurements which could be assigned to lines in L m , following the measurement assignment rules in Proposition 1, to connect a bus in G m 1 to a bus in G m 2 ) containing m, such that a spanning tree can be formed over each of can still be connected while having a spanning tree in each, to form a spanning tree over the entire graph G. Indeed, when m is removed, any m ∈ C m can be assigned to a line in L m to reconnect G m 1 and G m 2 , while a spanning tree can still be formed From an algebraic perspective, C m is such that the Jacobian matrices of G m 1 and G m 2 using only the measurements in M m , are full column rank, i.e., rank(H However, the addition of any additional measurement in M L m to C m would lead to rank(H Hence, finding C m corresponds to finding a maximal set of redundant measurements in M L m \{m}. This maximal set may not be unique (as we will demonstrate in the analysis that ensues). Indeed, any set of measurements that meets Definition 3, is a critical set of m ∈ M A , considering the pair of subgraphs Here, in general, a set of measurements is redundant if its removal does not affect the rank of the Jacobian matrix in the studied graph/subgraph or, equivalently, does not prevent the possibility of building a spanning tree over the studied graph/subgraph. We next introduce a set of rules for building a critical set -which is not necessarily unique -of a certain measurement, following which we provide a step-by-step procedure for building such critical sets. As such, a critical set can be derived for each of the N − 1 measurements in M A , i.e., the measurement assigned as part of the original tree. This set of N − 1 critical sets is then used, analyzed, and  Since the measurements in M m F and the unassigned injection measurements over buses in N m 1,2 ∪ N m 2,1 (which are the first two categories of measurements in M m , as shown in Fig. 3) are redundant, they are part of C m . For example, consider the injection measurement, I 4 , over bus 4 in Fig. 2. I 4 is in M F2 and is a redundant measurement since it was not assigned to any line as part of the original tree T . Thus, I 4 ∈ C F2 . Now, when m ∈ M m is assigned as part of the original assignment function, i.e., m ∈ M m ∩ M A (which corresponds to the third category of measurements in M m , indicated in Fig. 3), then additional investigation is needed to determine whether m is redundant, and hence, whether it can be considered in C m . This process will explore all alternative ways of building a spanning tree in the subgraph in which m is assigned, to determine whether m is a redundant measurement.
In this regard, consider that m ∈ M m is assigned to a line l , i.e., f (m ) = l ∈ B. If m is to be reassigned to a line l ∈ L m , T m 1 and T m 2 will be reconnected, but since m was originally assigned as part of the original tree, another portion of the tree gets disconnected by this reassignment of m to l instead of l . Hence, m would be redundant and can, thus, be part of C m if another measurement can be used to reconnect the subgraph which was disconnected by the reassignment of m from l to l. In other words, m can be part of C m if 4 Such measurements are unassigned measurements. In fact, if m is a line measurement, lines in L m would form a loop with f (m) and hence cannot be part of the original spanning tree. Moreover, if m is an injection measurement, M m F would be an empty set since, otherwise, based on the spanning tree building method described in Section II-B and originally presented in [23], one of the measurements in M m F would have been assigned to a line in L m , and m would not have been part of M A . As a result, measurements in M m F are redundant.
the measurement set within the subgraph that was disconnected by the reassignment of m to l instead of l allows building a spanning tree over this subgraph. This can be assessed by analyzing the redundant measurements within this subgraph to investigate all other possible spanning trees which can be formed, hence, not limiting the analysis to the original spanning tree T . For example, consider the injection measurement over bus 13 in Fig. 2, which we denote by I 13 . I 13 has been assigned to line 12 as part of the original spanning tree. Hence, if I 13 is assigned to line 20 to reconnect T F2 1 and T F2 2 after measurement F 2 is removed, it cannot be assigned to line 12 anymore which will split T F2 1 into two subtrees, one formed by buses {12, 13} and line 19 and the other subtree composed of buses {6, 10, 1, 5} and lines {13, 10, 1}. We denote these two subtrees by T F2 1,1 and T F2 1,2 , respectively. In this respect, if another measurement can replace I 13 in reconnecting T F2 1,1 and T F2 1,2 , then I 13 would be redundant and can be assigned to line 20 and, hence, should be part of C F2 . To this end, consider the injection measurement over bus 12, denoted by I 12 , which was not part of the original spanning tree assignment, i.e., I 12 / ∈ M A . I 12 can be assigned to line 11 to reconnect T F2 1,1 and T F2 1,2 in case I 13 is reassigned to line 20 instead of line 12. Hence, I 13 is indeed redundant, resulting in I 13 ∈ C F2 . Thus, the assignment of I 12 to line 11 will lead to modifications to T F2 1 . However, here, the goal is not to identify the new form of T F2 1 , but rather to merely investigate whether or not a new form of T F2 1 can be constructed using the measurement set in G F2 1 . To generalize the analysis in this example, we next provide a general discussion of measurements in M m ∩ M A (i.e., third category in Fig. 3)  can reconnect T m 1,1 and T m 1,2 . Hence, this corresponds to finding a measurement assignment that connects the two subtrees T m 1,1 and T m 1,2 . As discussed in Section II-B, two subtrees can be connected by using a measurement assignment if the processing of an unassigned boundary injection in one of them reaches a node in the other. We denote such unassigned boundary injections by backup boundary injections, defined as follows: Since the tree building algorithm in [23] is based on connecting subtrees (i.e. tree components) -to build a full spanning tree -by starting from an unassigned boundary injection in a certain subtree (as a source) to reach a node in another subtree (as a sink), this algorithm can be readily employed to identify a backup boundary injection for a measurement m ∈ M m ∩ M A . To this end, to find a backup boundary injection of m , we run the algorithm in [23] by starting from an unassigned boundary injection in either T m 1,1 or T m 1,2 and checking whether the algorithm reaches a bus in T m 1,2 or T m 1,1 , respectively. As such, using the spanning tree building algorithm provided in [23, Fig. 1], one can identify the backup boundary injections for each injection measurement in m ∈ M m ∩ M A . Here, we note that, following our proposed method for constructing C m , a backup boundary injection cannot be an injection measurement in M m , since if m ∈ M m and m is unassigned, m will itself be part of C m , as previously discussed.
Therefore, an assigned injection measurement m ∈ M m ∩ M A is a redundant measurement and is, as a result, part of C m if it has a nonempty boundary injection set I m b−m . However, a boundary injection may be part of multiple backup boundary injection sets. In this regard, based on the measurement assignment rules, an injection measurement can be assigned to only one line at a time. Hence, an unassigned boundary injection can act as a backup boundary injection for only one measurement in M m ∩ M A , at a time. Thus, if two measurements m 1 and m 2 in M m ∩ M A have only one and the same backup boundary injection, only one of them can be concurrently in C m , which indicates that a critical set C m of m may not be unique. As a result, due to this one-to-one assignment requirement between backup boundary injections and injection measurements in M m ∩ M A , finding this assignment can be performed by solving a maximum matching problem over a bipartite graph 5 , as the one shown in Fig. 4. We refer to this graph as the injection measurements -backup boundary injections bipartite graph. for m ∈ M m do 7: if m is a flow measurement then 8: Add m to C m 9: end if 10: if m is an injection measurement then 11: if m / ∈ M A then 12: Add m to C m 13: end if 14: if m ∈ M A then 15: Characterize if m is a matched node as part of the maximum matching then 23: Add m to C m 24: end if 25: end for 26: end for 27: return Critical set C m for all measurements m ∈ M A problem over this bipartite graph 6 . As a result, the matched left-side nodes in a maximum matching over the "injection measurements -backup boundary injections bipartite graph" are the injection measurements in M m ∩ M A which will be part of C m . Here, we note that this leads to the identification of a critical set C m of m, as C m may not be unique given that a maximum matching over a bipartite graph may not be unique. Indeed, each possible maximum matching would lead to a different C m .
Based on these introduced rules for building critical sets, Algorithm 1 provides a structured step-by-step method for building a critical set, C m , for each measurement m ∈ M A .

B. Example and Case Analysis
As an example of characterizing critical sets of the various assigned measurements, as part of a spanning tree, in a power system, we consider the IEEE 14-bus system in Fig. 1. In this example, we denote an injection measurement over bus k by I k and a flow measurement over line k by F k . We first consider the measurement over line 2, F 2 , for which we find a critical set C F2 using Algorithm 1.
From Fig. 2, we can see that removing F 2 will result in splitting the original spanning tree into two trees, T F2 The first measurement in M F2 is F 2 . F 2 is a flow measurement. Hence, F 2 ∈ C F2 . The second and third measurements in M F2 are I 4 and I 11 . I 4 and I 11 are unassigned injection measurements, i.e. I 4 / ∈ M A and I 11 / ∈ M A . Hence, {I 4 , I 11 } ⊆ C F2 . Indeed, I 4 can be assigned to line 7 to reconnect T F2 1 and T F2 2 , while I 11 can be assigned to line 18 for that purpose. I 2 is the fourth measurement in M F2 and the last remaining injection measurement on N m 2,1 to be explored. I 2 is an assigned measurement, originally assigned to line 4 as part of the spanning tree T . As I 2 ∈ M A , assigning I 2 to lines 2 or 3 to reconnect T F2 1 and T F2 2 will disconnect bus 2 from the rest of T F2 2 . Hence, we next characterize the backup boundary injection set of I 2 , i.e. I F2 b−I2 . The only unassigned boundary injection in G F2 2 that is not part of M F2 is I 7 . However, using the algorithm in [23, Fig. 1], we can observe that starting from I 7 , the algorithm does not reach bus 2. Hence, bus 2 cannot be reconnected to the rest of T F2 2 using any unassigned boundary injections over buses in G F2 2 . Hence, I F2 b−I2 = ∅, and as a result F 2 / ∈ C F2 . Similarly, exploring I 1 and I 5 -the fifth and sixth measurements in M F2 -which are both assigned measurements, i.e. {I 1 , I 5 } ⊆ M A , shows that they both have empty backup boundary injection sets 7 , i.e. I F2 b−I1 = ∅ and I F2 b−I5 = ∅. Hence, neither I 1 nor I 5 are part of C F2 . The only remaining measurement in M F2 is I 13 . I 13 is an assigned measurement, I 13 ∈ M A . As previously discussed in Section III-A, when I 13 is reassigned to line 20 to reconnect T F2 1 and T F2 2 , the subtree containing buses 12 and 13 and line 19 gets disconnected from the rest of T F2 1 . Hence, we next characterize the backup boundary injection set of I 13 , i.e. I F2 b−I13 . To this end, I 12 , the only unassigned boundary injection measurement in G F2 1 , can be assigned to line 11 to reconnect the two subtrees, and is the only boundary injection which can do so. Hence, I F2 b−I13 = {I 12 }. As a result, the "injection measurementsbackup boundary injections bipartite graph" is composed of only I 13 on the left-side connected to I F2 b−I13 = {I 12 } on the rightside. Hence, I 13 is matched to the backup boundary injection I 12 . As a result, I 13 ∈ C F2 . The processing of M F2 is thus complete, resulting in C F2 = {F 2 , I 4 , I 11 , I 13 }.
Similarly, Algorithm 1 can be carried out to characterize critical sets of all of the measurements in M A in the IEEE 14-bus system in Fig.1. The results are listed in Table II. We next discuss the value of critical sets with regard to understanding and analyzing observability attacks. We also introduce the concept of observability sets, a generalization of critical sets, which provides a holistic modeling of observability attacks.
Notation: We use the following notation in the derivations that ensue. For the Jacobian matrix H, we let H (−K)+(K ) correspond to H but with the removal of the rows corresponding to measurements in K and the addition of rows corresponding to measurements in K . 7 If I 1 or I 5 are to be reassigned to lines 2 or 3, respectively, to reconnect T F 2 1 and T F 2 2 , each of these reassignments will split T F 2 1 into two subtrees which cannot be reconnected using the unassigned boundary injection I 12 , as can be shown by a run of the algorithm in [23, Fig. 1]. Here, we note that I 12 is the only unassigned boundary injection in G F 2 1 .

C. Critical Sets and Observability
Next, we show that the derived critical sets are indispensable for modeling observability attacks. In this regard, we show that the removal of a critical set renders the system unobservable. The proof is carried out using two approaches: 1) A graph-theoretic approach presented in Theorem 1 and showing that no spanning tree could be build over G when a critical set is removed, and 2) an approach based on linear algebra, presented in Theorem 2, where we will prove that the rank of the Jacobian matrix of the power system graph G, when not considering the measurements in a critical set (i.e. after the removal of a critical set), is strictly less than N − 1 (we, in fact, prove that the rank of the Jacobian matrix becomes N − 2), making the Jacobian matrix not full column rank and leading the system to become unobservable. These two approaches are presented next.
1) Proof by Graph-Theoretic Arguments: Theorem 1: Removing a critical set, C m , renders the system unobservable.
Proof: By topological observability, we know that a system is observable if and only if a spanning tree could be formed using an assignment function. Hence, given that G m 1 and G m 2 are two disjoint subgraphs of G, any spanning tree over G must at least assign one measurement to a line in L m . Otherwise, this tree would not span the whole system.
When m is removed, the original spanning tree T is split into two disjoint trees T m 1 and T m 2 , spanning subgraphs G m 1 and G m 2 , respectively. This makes each of G m 1 and G m 2 observable. However, it does not make the whole system observable as there is a need to connect G m 1 and G m 2 . By definition of C m , removing C m makes it impossible to connect G m 1 and G m 2 , by any measurement assignment, as C m contains all measurements which could be assigned to a line in L m without losing the observability within one of the two subgraphs. In fact, if C m is removed, based on Proposition 1, for any measurement to be assignable to a line in L m it must be in M L m \ C m , in order to either connect T m 1 and T m 2 or interconnect disjoint components of T m 1 and T m 2 (or disjoint tree components within each of G m 1 and G m 2 ) to span the entire G. However, none of these measurements in M L m \ C m can be assigned to a line in L m , as none of these measurements is redundant. In fact, if any of these measurements in M L m \ C m were redundant, this measurement would have been part of C m , as otherwise, it would have contradicted the maximality property of C m . As such, if C m is removed, G would contain no spanning tree that could be built according to the rules of Proposition 1, which makes the system unobservable.

2) Proof by Linear Algebra:
In addition, we prove in the next theorem (Theorem 2) that removing a full critical set decreases the rank of the Jacobian matrix by 1, which as a result makes the system unobservable. However, we first present the following preliminary lemma, which is essential for the proof of Theorem 2. Proof: Since m is assigned, i.e. is part of an original spanning tree measurement assignment, removing it will split the original spanning tree into two subtrees T m 1 and T m 2 . If m existed, m can reconnect T m 1 and T m 2 , as it is a measurement over line l, which is part of L m . Hence, replacing m by m will not affect the connectivity of the spanning tree and, hence, rank(H) = rank(H (−m)+(m ) ). . In this respect, is not full column rank ⇒ the system becomes unobservable after the removal of any critical set C m .
3) Analysis and Discussion: Theorem 2 shows the effect of the removal of a single critical set on the rank of the Jacobian matrix. Theorem 1 and Theorem 2 provide key conditions for observability of the power system under observability attacks. In fact, the contrapositives of these theorems show that if a power system is fully observable, then the investigated observability attack (i.e. the removal of measurements) did not result in removing a full critical set. In addition, using Theorem 1 and Theorem 2, we can also show that a critical set C m is a minimal set of measurements including m which when removed renders the system unobservable. In fact, as shown in Theorem 1 and Theorem 2, removing C m renders the system unobservable while, if all measurements in C m are removed except for one arbitrary measurement m , the system would still remain observable. In fact, by Definition 3, this m can be assigned to a line l ∈ L m to connect G m 1 and G m 2 , while having a spanning tree over each of G m 1 and G m 2 , which leads to a spanning tree over G(N , L) and makes the system observable.
Moreover, based on Theorem 1 and Theorem 2, the critical measurements 8 of a power system can be characterized using the notion of critical sets, as shown in the following corollary.
Corollary 1: m is a critical measurement if and only if its only critical set is C m = {m}.
Proof: By definition, if m is a critical measurement, removing it will render the system unobservable. Hence, if the critical set of m is such that C m ⊃ m, then removing m would not affect the observabilty of the system since any other measurement m ∈ C m \ {m} can be used to replace m and reconnect the tree. As such, C m ⊃ {m} ⇒ m is not a critical measurement, which proves the contrapositive: m is critical ⇒ m is the only element in its critical set, i.e. {m} = C m . Conversely, if m is the only element in its critical set, its removal constitutes removing a complete critical set, which by Theorem 1 and Theorem 2, renders the system unobservable. As a result, C m = {m} ⇒ m is a critical measurement. Thus, m is critical if and only if C m = {m}.
Next, we extend this concept to account for the interconnection between multiple critical sets.

D. Observability Sets
For a measurement m to be in a critical set of a measurement m, i.e. m ∈ C m , a critical set of m , C m , must contain measurements other than m , i.e. C m ⊃ {m }. Otherwise, m would not be redundant. For example, consider injection measurements I 6 and I 9 . Removing I 6 and I 9 will render the system unobservable -even though I 6 and I 9 do not form a critical set -since C I6 = {I 6 , I 11 } and C I9 = {I 9 , I 11 }. As such, if I 6 is removed, I 11 can be used to replace I 6 since I 11 ∈ C I6 . However, if I 9 is also removed, even though I 11 ∈ C I9 , I 11 cannot be used to replace I 9 since I 11 has already been used as a replacement to I 6 . Therefore, removing I 9 and I 6 does render the system unobservable. Indeed, rank(H −(I6)−(I9) ) = 12 < N − 1 = 13. This concept can be extended to the interconnection between multiple critical sets. For example, consider F 2 , I 1 , I 2 , and I 5 and their critical sets shown in Table II. We can see that F 2 , I 1 , and I 2 have critical sets sharing measurements I 4 , I 11 , and I 13 . Hence, if F 2 , I 1 , and I 2 are removed, I 4 , I 11 , and I 13 are assigned, one to each of these measurements, to preserve system observability and, hence, cannot be used as part of further critical sets in case further measurements are removed. Hence, since C I5 = {I 5 , I 11 , I 13 }, removing F 2 , I 1 , I 2 and I 5 will render the system unobservable, even though {F 2 , I 1 , I 2 , I 5 } is not a critical set.
In this respect, the concept of critical sets must be further developed to yield a general graph-theoretic concept of observability attacks. To this end, we define a graph, dubbed "critical sets -system measurements bipartite graph", as follows: Definition 5: A critical sets -system measurements bipartite graph (CS-SMBG) is a bipartite graph in which each left-hand side node represents one of the critical sets of the power system (such that the set of left-hand side nodes include only one critical set C m for each m ∈ M A ), and the right-hand side nodes represent the entire measurement set M such that each righthand side node represents one measurement in the measurement set M. In this respect, an edge between a critical set C i and a measurement j exists if j ∈ C i . An example of this bipartite graph is shown in Fig. 5. Here, we note that since a critical set C m might not be unique, different versions of a CS-SMBG can be constructed for a single power system, depending on the choice of a critical set for each m ∈ M A , which depends on the choice of the assigned measurements M A (associated with the original spanning tree T ). Based on this formulation, a general concept of observability is established in Theorem 3.
Theorem 3: If the system is observable, then any maximum matching over any CS-SMBG must include all of the critical sets of this CS-SMBG.
Proof: We prove this theorem by proving its contrapositive which is the following: if a maximum matching does not include all of the critical sets of a certain CS-SMBG (i.e. at least one critical set is unmatched in a maximum matching over this CS-SMBG), then the system is not observable.
The contrapositive can be proven as follows. As defined in Definition 3, a critical set C m consists of a maximal set of measurements which can be assigned to a line in L m to connect two subgraphs of the power system graph, namely, G m 1 (N m 1 , L m 1 ) and G m 2 (N m 2 , L m 2 ), while preserving the ability to construct spanning trees over each of G m 1 (N m 1 , L m 1 ) and G m 2 (N m 2 , L m 2 ) using measurements in {M m 1 ∪ M m 2 } \ C m . Consider that a number of measurements in the system are unavailable (i.e. attacked) so that the remaining measurements are not enough to include all critical sets in a maximum matching. Without loss of generality, we consider C m to be an unmatched critical set.
When C m is not part of a maximum matching over a CS-SMBG, then either 1) all of the measurements in C m were removed (i.e. attacked and are not available), or 2) other measurements in the system were removed so that not enough measurements remain to match all critical sets (i.e. all measurements in C m are matched to other critical sets). Now, if none of the measurements in C m could be matched to C m ⇒ no measurement in C m could be assigned to a line in L m since a measurement can be assigned to one line at a time ⇒ G m 1 (N m 1 , L m 1 ) and G m 2 (N m 2 , L m 2 ) could not be connected while preserving the observability within each of G m 1 (N m 1 , L m 1 ) and G m 2 (N m 2 , L m 2 ) (i.e., concurrently having a spanning tree over each of G m 1 and G m 2 ) ⇒ a spanning tree over the power system graph G(N , L) could not be constructed through measurement assignments ⇒ the power system is unobservable. This then proves the contrapositive of this theorem and, hence, proves the theorem.
Theorem 3 can be used to fully characterize observability attacks as follows. An observability attack is one in which measurements are removed (i.e. nodes from the right-side of a CS-SMBG) such that any maximum matching over this CS-SMBG would not include at least one critical set (i.e. nodes on the left-side of a CS-SMBG), which renders the system unobservable. This applies to any CS-SMBG, that is built from any set of critical sets (containing a critical set for each assigned measurement), that are derived from any original spanning tree T . This, as a result, provides a general analytical characterization of observability attacks and enables prediction of the effect of the removal of a subset of measurements on the observability of the system. This enables identifying security indices such as the observability attack of lowest cardinality or the minimal set of measurements to remove in addition to a certain measurement to make the system unobservable. In what follows, we focus on stealthy data injection attacks -proving that they are a subset of observability attacks -and we show how our provided analytical characterization of observability attacks enables analysis of various widely-studied stealthy data injection attack problems. To this end, we introduce sets of measurements, dubbed observability sets, as follows, which are valuable for the analysis of data injection attacks which ensues.
Definition 6: For a CS-SMBG, an observability set S ∈ M is a set of measurements such that removing S leads a maximum matching over this CS-SMBG not to include a certain critical set.
In this regard, adding any measurement s ∈ S, which was removed, back to the right-side of this bipartite graph will result in re-including the previously unmatched critical set in this maximum matching. In addition, removing all of S except for one measurement s ∈ S will not lead to excluding any critical set from a maximum matching over the CS-SMBG (resulting in a perfect matching). We note that multiple observability sets may exist for a CS-SMBG, as the removal of a different set of measurements may lead to the exclusion of a different critical set from a maximum matching over this graph. Here, we note that an observability set is associated with the CS-SMBG from which it was derived. A different CS-SMBG (resulting from a different set of critical sets, originating from a different original spanning tree) would result in different observability sets.
A union of observability sets for a CS-SMBG is defined as a set of measurements composed of a number of observability sets such that, when each of these sets is successively removed, each such removal leads to excluding one additional critical set from being part of a maximum matching over the CS-SMBG. Adding back any of the removed measurements to the rightside of the bipartite graph will result in re-including one of the unmatched critical sets in the previously obtained maximum matching. Note that with the successive removal of observability sets, observability sets are defined based on the updated state of the CS-SMBG after the removal of a previous observability set at a previous step. In addition, at each step, multiple observability sets may exist. These observability sets play a crucial role in characterizing stealthy data injection attacks, as shown next.
We next introduce stealthy data injection attacks and prove that they are a variant of our introduced observability attacks. This enables further studying and solving various problems related to SDIAs using our developed analytical tools.

A. Stealthy Data Injection Attacks
Recalling the measurement-state equation in (1), data injection attacks aim at replacing the measurement vector, z by a manipulated measurement vector z a = z + a, where a ∈ R m is the attack vector, resulting in a new state estimatex a . However, typically, the state estimation process is run in conjunction with what is known as a bad data detector and identifier (BDD). The BDD aims at detecting and identifying the presence of outliers in the collected data set, so that such outliers can be removed preventing them from affecting the estimation outcome. Such BDDs rely on the statistical analysis of what is known as measurement residuals, r, defined as [8]: where S = H(H T R −1 H) −1 H T R −1 and W = I n − S. A statistical analysis on the residuals enables analysis of the magnitudes of the errors associated with each measurement, and hence, allows the identification of outliers [8]. Regarding data injection attacks, when data is added to certain measurements, the adversary aims at keeping the residuals unchanged, so that the attack cannot be detected by the BDD. Indeed, as shown in [27], an attack vector that falls in the column-space of the Jacobian matrix H, i.e. a = Hc, cannot be detected by residual statistical analysis. Indeed, for a = Hc, r a = W (z + a) = r + W a = r + Hc − Hc = r.
As such, given the weighted least squares state estimation equation in (2), the attack vector a = Hc generates an arbitrary new state estimatex a =x + c by choosing the constant vector c without inducing any changes to the residual vector, as shown in (5). Such DIAs are, hence, stealthy and are referred to as stealthy DIAs. The ability of SDIAs to stealthily manipulate the state estimates poses various challenges to the operation of the grid. Hence, understanding and modeling such attacks is indispensable to the secure and sustainable operation of power systems. To this end, we next introduce a holistic graph-theoretic modeling of SDIAs that is based on the graph-theoretic modeling of observability attacks introduced in Section III.

B. Graph-Theoretic Modeling of SDIAs
The observability attacks and observability sets introduced in Section III provide the basis for a graph-theoretic interpretation of SDIAs as will be shown in Theorem 4. However, before introducing and proving Theorem 4, we introduce a preliminary lemma which will be used in the proof of Theorem 4.
Lemma 2: If a DIA is stealthy (i.e. a = Hc), then removing the attacked measurements renders the system unobservable.
Proof: Since the attack vector a is stealthy, then a = Hc. Since H is of full rank, then the only solution to Hc = 0 is c = 0. Hence, a = Hc has zero and nonzero elements for c = 0. Now, if all of the rows of H corresponding to nonzero elements of a are removed to form matrix H new , then, this results in a new = H new c = 0 for c = 0. Hence, H new is not of full rank and the power system whose Jacobian matrix is given by H new is unobservable. Therefore, when the attack is stealthy, removing the attacked measurements renders the system unobservable.
Here we note, that the result of Lemma 2, provides a one directional relation stating that if a = Hc, i.e. the attack is stealthy, then the removal of the nonzero elements of a, i.e. the attacked measurements, causes the system to be unobservable. However, the reverse direction does not always hold true. Indeed, the reverse statement of Lemma 2 states that, if removing a set of measurements renders the system unobservable, then this guarantees that a stealthy DIA can be constructed which targets all of these measurements, and only these measurements. We next provide a counter example which proves that this reverse statement does not hold true. In this regard, we consider the Jacobian matrix H to be represented as follows: We let M 0 and M 1 represent the subset of measurements corresponding to the rows of H 0 and H 1 , respectively. Consider Otherwise, this attack must be limited to a strict subset of M 0 and may not target all the measurements in M 0 . As a result, even though removing the measurements in M 0 renders the system unobservable, one cannot necessarily construct a stealthy attack vector that only targets all the measurements in M 0 . Hence, this provides a counter example of the reverse statement of Lemma 2 proving that this reverse statement does not always hold true. Theorem 4: A DIA is stealthy if and only if the attacked measurements constitute a union of observability sets over a certain CS-SMBG.
Proof: We begin by proving that when the attacked measurements (i.e. nonzero elements of the attack vector a) constitute a union of observability sets, then a is stealthy (i.e. a can be represented as a = Hc). As shown in Theorem 3, when an observability set (equivalently, a union of observability sets) is removed, the system is unobservable. Hence, consider an observability set S which has been removed. Let H (−S) be the system's Jacobian matrix without the measurements in S and let C be the critical set which cannot be part of a maximum matching over the CS-SMBG when S is removed. Since the system is unobservable when removing S, H (−S) y = 0 for a y = 0. However, the addition of any measurement s ∈ S will reinclude C in the maximum matching over the CS-SMBG, and hence, reconnect the tree. As such, let H (−S)+(k) correspond to H (−S) with the addition of a row corresponding to a measurement k ∈ S. In this regard, since the system is rendered observable, H (−S)+(k) is of full rank and H (−S)+(k) y will have one nonzero element corresponding to the row of H (−S)+(k) pertaining to the added measurement k. This procedure can be repeated for all k ∈ S. As such, adding the rows corresponding to S back to the Jacobian matrix results in b = Hy in which only the elements of b corresponding to measurements in S are nonzero. As a result, a = b is an attack vector in which only the observability set S is attacked and is proven to be stealthy. Now, we prove that, when an attack is stealthy, i.e. a = Hc, then the nonzero elements of a correspond to a union of observability sets. In this regard, from Lemma 2, we know that removing the nonzero elements of a = Hc will render the system unobservable, which implies that the nonzero elements of a contain at least one observability set. Let S denote this observability set, and let H (−S) be the system's Jacobian matrix without the measurements in S. Removing S will lead to two subsystems each of which is fully observable (i.e. it will split the spanning tree, T , into two subtrees each of which spans its own subgraph). Let H 1 and H 2 be the Jacobian matrices of each of these two subsystems (we denote these subsystems as subsystem 1 and subsystem 2) and let a 1 and a 2 correspond to the portions of a (excluding the measurements of the previously removed observability set) corresponding to the measurements in H 1 and H 2 , respectively. In addition, let c 1 and c 2 correspond to the portions of c pertaining to nodes in subsystem 1 and subsystem 2, respectively. Now, if a i for i ∈ {1, 2} has nonzero elements, this implies that removing these elements will make subsystem i unobservable, which implies that the nonzero elements of a i contain an observability set. Following this same logic, removing this observability set will subsequently split subsystem i into two subsystems, each of which is observable. This process can be continued recursively until no measurement m corresponding to a nonzero element of a remains. Hence, this shows that when Pre-attack Post-attack Fig. 5. Critical sets -system measurements maximum matching and SDIAs. a = Hc, then the nonzero elements of a correspond to a union of observability sets. This proves both directions of the theorem, and hence, concludes the proof.
Theorem 4 provides an analytical graph-theoretic modeling of SDIAs using the fundamentals of observability attacks introduced in Section III. This enables a fundamental understanding of SDIAs since it allows the characterization of the subset of measurements which would be compromised as part of an SDIA and hence enables defense against such attacks. In addition, this analytical characterization of SDIAs enables a more in-depth analysis of such integrity attacks and allows a characterization of analytical solutions to a wide-range of well-studied problems in this field, as will be explored in Section IV-C.
Example 1: As an illustrative example of the result 10 in Theorem 4, we consider the IEEE 14-bus system, shown in Fig. 1, whose line transmission data can be found in [28]. We In this respect, we next verify whether this attack is stealthy, following Theorem 4. To this end, Fig. 5 shows a portion of the CS-SMBG that is relevant to the attacked measurements. The post-attack portion of Fig. 5 marks the nodes corresponding to measurements {F 2 , I 1 , I 2 , I 3 , I 4 , I 5 }, on the right-side of the bipartite graph, as attacked (following the attack vector a). As a result, all the edges connecting these nodes to the critical sets on the left-side of the bipartite graph are removed. Then, building a maximum matching over the post-attack bipartite graph shows that, indeed, not all the critical sets are matched. Hence, the removed measurements lead to a maximum matching that does not include all critical sets. Furthermore, the addition of a node corresponding to any of the attacked measurements, i.e. {F 2 , I 1 , I 2 , I 3 , I 4 , I 5 }, would lead to reincluding one of the unmatched critical sets {C F2 , C I3 , C I5 } in the maximum matching. This implies that the attack consists of a union of observability sets which implies that the attack is stealthy.

C. Unified Analysis of Diverse SDIA Problems
Theorem 4 provides a unified basis for studying various SDIA problems from a graph-theoretic perspective, as show next. 10 In this example, we index the measurements in Fig. 1 from  1 to 17 in an incremental manner based on the following order (F 2 , F 8 , F 9 , F 15 , I 1 , I 2 , I 3 , I 4 , I 5 , I 6 , I 7 , I 9 , I 11 , I 12 , I 13 , F 17 , F 19 ). SDIA analyses can be categorized based on whether the focus is on modeling the attack or the defense strategies. As such, we first present two problems focusing on modeling attack strategies followed by two problems focusing on the derivation of defense strategies to thwart SDIAs.
1) Modeling SDIA Attack Strategies: Modeling SDIA attack strategies enables a vulnerability assessment of the system and allows anticipating sophisticated attack strategies which can target the system. This, in turn, allows the derivation of adequate defense strategies to thwart such attacks. We next focus on two problems which aim at modeling potential attack strategies.
Problem 1: If measurement k ∈ M is attacked, what is a minimal set of measurements which must be attacked along with k for the attack to be stealthy? In other words, Problem 1 seeks a solution to the following optimization problem: min c ||Hc|| 0 , subject to: H(k, :)c = 1.
Problem 1 has been proposed in [13] and studied in [14] and [15]. The derived solution in [14] is based on an approximate relaxation method while the solution in [15] focuses on the special case assuming that the measurement set consists of all injection measurements at all buses and all line flow measurements at all transmission lines. Instead, here, we provide a general graph-theoretic characterization of a solution to this problem using our developed framework. We note that the goal of this analysis here is not to determine and analyze the computational efficiency of deriving a solution to Problem 1 but rather to analytically characterize a solution to this problem using our developed graph-theoretic framework 11 .
An analytical graph-theoretic solution to Problem 1 is characterized in Theorem 5.
Theorem 5: A stealthy attack of smallest cardinality containing measurement k corresponds to attacking the measurements of the critical set of lowest cardinality which contains k.
Proof: First, we show that the attack containing the critical set of lowest cardinality containing k is, indeed, stealthy. Then, we prove that this attack is a stealthy attack containing k that has a minimum cardinality.
By Theorem 4, for the attack to be stealthy, the removal of the attacked measurements must lead a maximum matching over a CS-SMBG not to include all the critical sets (i.e. all the left-side nodes of the bipartite graph). In other words, the attack must be composed of a union of obseravbility sets. In this respect, removing the critical set containing k that is of smallest cardinality is, indeed, stealthy since removing an entire critical set will disconnect the node corresponding to this critical set (on the left-hand side of the CS-SMBG) from the right-side of the bipartite graph, which prevents this critical measurement from being part of any maximum matching.
Next, we prove that there are no stealthy attacks containing k that have a smaller cardinality. In this regard, for an attack containing k to be stealthy, it must prevent a critical set, in which k exists, from being part of a maximum matching over a certain CS-SMBG. A critical set would be excluded from such a maximum matching in two cases: 1) if all the measurements 11 Exact complexity analysis can be an interesting subject for future work. in this critical set are attacked, or 2) if all the measurements in this critical set are matched to other critical sets.
In the first case, considering attacking all the measurements in a critical set, then attacking the critical set that has the fewest number of measurements -as stated in this theoremcorresponds to the minimum cardinality attack for this specific CS-SMBG. As for the second case, if a measurement k in a critical set containing k is matched -as part of a maximum matching -to another critical set (we denote this set by C p ), then measurement p must be attacked since, otherwise, C p would have been matched to p sparing k to be matched to another critical set to maximize the cardinality of the matching. In other words, matching a critical set C p with a measurement k = p while p is not attacked is contradictory to the assumption that this matching is maximum. As a result, for a critical set C, such that k ∈ C, to be discarded from a maximum matching, every measurement in C must be matched to another critical set. This implies that at least one measurement of each of these critical sets is attacked. Thus, the number of attacked measurements will be at least equal to the number of measurements within C for the attack to be stealthy. Consequently, for a certain CS-SMBG, attacking the critical set that has the fewest number of measurements and which contains k is a SDIA containing k having the lowest cardinality. As a result, considering all possible CS-SMBGs, obtained from any set of critical sets that were derived from any original tree, and considering the minimum-cardinality critical set containing k in each one of these CS-SMBGs leads to the following result: a stealthy attack containing k that has the lowest cardinality consists of attacking only the measurements of the critical set containing k that has the lowest cardinality, considering all such critical sets derived from any possible original spanning tree.
Here, one can also conclude that the solution to Problem 1 may not be unique since a critical set containing k of minimum cardinality may not be unique. Thus, any critical set containing k, whose cardinality is less than or equal to any other critical set containing k, is a solution to Problem 1. In addition, a numerical derivation to the solution of Problem 1 requires exploring all possible spanning trees over G. This could be performed, for example, based on a repeated application of the spanning tree building algorithms proposed in [23]- [25], among other techniques. However, our goal here is to provide a graphtheoretic characterization to the solution of Problem 1, rather than proposing algorithms to numerically obtain this solution. This latter end goal would highly complement the results of the current work and is left to be explored in future extensions.
Characterizing the solution to Problem 1 will also facilitate solving another key SDIA problem, referred to as Problem 2, and stated as follows.
Problem 2: What is the SDIA with the lowest cardinality? In other words, which SDIA is a solution to: min a ||a|| 0 , subject to: a = Hc.
A solution to Problem 2 is provided in Proposition 2. Proposition 2: A stealthy attack of lowest cardinality consists of attacking the smallest critical set.