On the Computational Complexity of the Secure State-Reconstruction
Problem111This work was funded in part by the Army Research Laboratory under
Cooperative Agreement W911NF-17-2-0196, by the UC-NL grant LFR-18-548554, by
the NSF award 1740047, and by the NSF CAREER award 1653648.

Yanwen Mao1, Aritra Mitra2, Shreyas Sundaram2 and Paulo Tabuada1

1Department of Electrical and Computer Engineering,

University of California, Los Angeles

Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
2Department of Electrical Engineering, Purdue University, West Lafayette

Email<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract.

In this paper, we discuss the computational complexity of reconstructing the
state of a linear system from sensor measurements that have been corrupted by
an adversary. The first result establishes that the problem is, in general,
NP-hard. We then introduce the notion of eigenvalue observability and show
that the state can be reconstructed in polynomial time when each eigenvalue is
observable by at least $2s+1$ sensors and at most $s$ sensors are corrupted by
an adversary. However, there is a gap between eigenvalue observability and the
possibility of reconstructing the state despite attacks - this gap has been
characterized in the literature by the notion of sparse observability. To
better understand this, we show that when the $\mathbf{A}$ matrix of the
linear system has unitary geometric multiplicity, the gap disappears, i.e.,
eigenvalue observability coincides with sparse observability, and there exists
a polynomial time algorithm to reconstruct the state provided the state can be
reconstructed.

##  1\. INTRODUCTION

This paper is concerned with the detection of attacks on Cyber-Physical
Systems (CPSs). The distributed nature of these large-scale systems often
leads to increased vulnerabilities. Of particular concern are adversaries that
exploit the distributed nature of CPSs to gain access to sensors and launch
attacks by modifying their measurements [1, 2, 3]. The most notorious example
is the Stuxnet malware [4], which attacked numerous industrial control
systems.

Over the last decade, a significant amount of research has focused on
reconstructing the state in the presence of sensor attacks - we will refer to
this as the Secure State-Reconstruction (SSR) problem throughout the paper.
The first experimental demonstration of a stealthy attack on a control system
was reported in [5] and it was followed by the first theoretical results
developed for special classes of systems [6, 7]. Stealthy attacks were then
formalized in [8, 9]. An important step in the conceptual understanding of
these attacks was given in [10, 11, 12], where the existence of such attacks
was characterized by the system theoretic notion of zero-dynamics.

In addition to detecting and identifying attacks, it is important to mitigate
their effect by continuing to control the plant. Hence, researchers have
invested a significant effort in developing algorithms to reconstruct the
state since the papers [13, 14]. However, the SSR problem is intrinsically an
NP-hard problem (as we show in this paper). Based on how the NP-hardness is
tackled, we classify the existing work in two classes: 1) brute force search
[15, 16], and 2) computationally efficient relaxations. The methods reported
in the first class are better suited for small systems as the computational
complexity grows combinatorially with the number of sensors. Noteworthy
examples of the second class include: convex relaxations [14, 17], distributed
detection filters [11], specialized observers under sparsity constraints [18],
satisfiability modulo theory techniques [19], and safety envelopes [20].

The distributed version of the SSR problem has also attracted a substantial
amount of interest given the distributed nature of CPSs. Several authors have
studied the problem of estimating a static vector from a set of corrupted
measurements, either over a distributed sensor network [21, 22], or over a
connected-on-average network [23]. A control-theoretic approach to distributed
function calculation was developed in [12]. Follow-up works have analyzed the
resilient consensus problem, both for discrete [24], and continuous-time [25]
systems. The work in [26] also evaluates this method in various network
topologies. The problem of guaranteeing resilience in the context of
distributed state estimation, when the state of the system evolves over time
(based on potentially unstable dynamics) has been recently explored in [27],
[28], and [29]. In particular, the authors in [29] develop a fully-distributed
algorithm that reconstructs the evolving state despite attacks on certain
sensors in the network.

Despite the wealth of literature on the security of CPSs, to the best of the
authors’ knowledge, a detailed characterization of the complexity of the SSR
problem is still lacking. On the one hand, the papers [14, 17, 11, 18, 19, 20]
suggest that the SSR problem is computationally hard since they propose
efficient relaxations to the problem. On the other hand, the paper [29]
implicitly proposes a polynomial-time solution to the SSR poblem for certain
cases. These observations naturally call for a better understanding of the
complexity of the SSR problem, which is precisely the goal of this paper.

As we shall soon see, two alternate notions of observability, namely “sparse
observability” introduced in [14, 18] (see also [12] for an equivalent notion
in continuous time), and “eigenvalue observability” [30], [31], will play key
roles in our characterization of the SSR problem complexity. Our contributions
are the following:

  1. (1)

We show that the SSR problem is NP-hard.

  2. (2)

redWe provide a decomposition that identifies portions of the state that can
be reconstructed in polynomial time and portions that are NP-hard to
reconstruct.

  3. (3)

We offer a polynomial-time solution for the SSR problem under an eigenvalue
observability assumption.

  4. (4)

We show that checking sparse observability is coNP-complete.

  5. (5)

We show that the notions of sparse observability and eigenvalue observability
are equivalent when the geometric multiplicity of each eigenvalue of the
system matrix $\mathbf{A}$ is 1.

These results can be understood as follows. Although the SSR problem is NP-
hard, in general, there may be portions of the state that can be reconstructed
in polynomial time. We perform a system decomposition to identify these
different portions of the state. In particular, when all the eigenvalues of
the system matrix $\mathbf{A}$ have unitary geometric multiplicity, the
decomposition results in scalar SSR problems. This establishes the equivalence
between sparse observability, a necessary and sufficient condition for the SSR
problem to be solvable, and eigenvalue observability, a sufficient condition
for the existence of a polynomial time algorithm. Interestingly, even if the
unitary geometric multiplicity condition is not satisfied, we may still check
eigenvalue observability and, if successful, solve the SSR problem in
polynomial time. When the system does not satisfy the eigenvalue observability
condition, we conjecture that the SSR problem is intractable since even
checking sparse observability is coNP-complete. This paper improves upon the
preliminary results in [32] by introducing a decomposition technique that is
key to the aforementioned contributions 1 and 2.

The rest of the paper is organized as follows. In Section 2, we define the
notation used throughout the paper. In Section 3, we introduce the system
model and give a formal definition of the SSR problem, sparse observability,
and eigenvalue observability. We prove that the SSR problem is NP-hard in
Section 4. This is then followed by a result on breaking the overall SSR
problem into several smaller independent SSR problems. As a special case, we
show in Section 6 that under an eigenvalue observability assumption, the SSR
problem can be solved in polynomial time. While checking eigenvalue
observability can be done in polynomial time, in Section 7 we show that
checking sparse observability is coNP-complete. We connect these two notions
in Section 8 by showing that they are equivalent when the geometric
multiplicity of each eigenvalue of the system matrix $\mathbf{A}$ is $1$.
Finally, we conclude the paper in Section 9.

##  2\. PRELIMINARIES AND NOTATIONS

The cardinality of a finite set
$\mathcal{I}=\\{\mathbf{i}_{1},\dots,\mathbf{i}_{p}\\}$ is denoted by
$|\mathcal{I}|=p$. For matrices $\mathbf{Q}_{i_{1}},\dots,\mathbf{Q}_{i_{p}}$
over the same field and with the same number of columns, we define the matrix
$\mathbf{Q}_{\mathcal{I}}=\begin{bmatrix}\mathbf{Q}_{i_{1}}^{T}|\mathbf{Q}_{i_{2}}^{T}|\dots|\mathbf{Q}_{i_{p}}^{T}\end{bmatrix}^{T}$
by stacking the individual matrices vertically.

We use $\mathbb{R}$ to denote the field of real numbers, $\mathbb{Q}$ to
denote the field of rational numbers, and $\mathbb{C}$ to denote the field of
complex numbers. For a matrix $\mathbf{A}\in\mathbb{R}^{n\times n}$, we use
$\mathrm{ker}~{}\mathbf{A}$ to denote the kernel of $\mathbf{A}$,
$\mathrm{Im}(\mathbf{A})$ to denote the image of $\mathbf{A}$ and
$\mathbf{A}|_{V}$ to denote the restriction of the linear map defined by
$\mathbf{A}$ to the subspace $V$. We also denote by $\mathbf{A}(V)$ the set
$\\{y\in\mathbb{R}^{n}|y=\mathbf{A}x,x\in V\\}$.

Let $V$ be a vector space. The collection of vector spaces
$\\{V^{j}\\}_{j=1,\ldots,r}$, with $V^{j}\subseteq V$, is said to be an
internal direct sum of $V$, denoted by $V=\bigoplus_{j=1,\ldots,r}V^{j}$, if
any vector $v\in V$ can be uniquely written as $v=v_{1}+\ldots+v_{r}$ with
$v_{j}\in V^{j}$. The direct sum comes equipped with canonical inclusions
$\imath_{j}:V^{j}\to V$ taking $v_{j}\in V^{j}$ to $\imath_{j}(v_{j})=v_{j}\in
V$, and canonical projections $\pi_{j}:V\to V^{j}$ taking $v\in V$ to
$\pi_{j}(v)=v_{j}\in V^{j}$.

As an example, consider $V=\mathbb{R}^{4}$ and let
$V^{1}=\mathrm{Im}(\mathbf{M}_{1})$, $V^{2}=\mathrm{Im}(\mathbf{M}_{2})$, and
$V^{3}=\mathrm{Im}(\mathbf{M}_{3})$ where $\mathbf{M}_{1}$, $\mathbf{M}_{2}$,
and $\mathbf{M}_{3}$ are the following linear transformations:

(2.1) $\mathbf{M}_{1}=\begin{bmatrix}\phantom{-}2&0\\\ -1&1\\\
\phantom{-}1&1\\\
\phantom{-}0&0\end{bmatrix},\quad\mathbf{M}_{2}=\begin{bmatrix}\phantom{-}0\\\
\phantom{-}1\\\ -1\\\
\phantom{-}0\end{bmatrix},\quad\mathbf{M}_{3}=\begin{bmatrix}-1\\\
\phantom{-}1\\\ \phantom{-}0\\\ \phantom{-}1\end{bmatrix}.$

The collection $\\{V^{1},V^{2},V^{3}\\}$ is an internal direct sum of $V$
since all the column vectors are linearly independent. The canonical
inclusions $\imath_{j}$ can be represented by $\mathbf{I}_{4}|_{V^{j}}$, the
identity matrix $\mathbf{I}_{4}$ of order 4 restricted to the subspace
$V^{j}$, since $\imath_{j}$ maps any vector $v\in V^{j}$ to $v\in V$.
Conversely, the canonical projections $\pi_{j}$ are represented by the
matrices
$\mathbf{P}_{j}=\mathbf{M}_{j}(\mathbf{M}_{1}^{T}\mathbf{M}_{j})^{-1}\mathbf{M}_{j}^{T}$.

Let $V=\bigoplus_{j=1,\ldots,r}V^{j}$, $W=\bigoplus_{j=1,\ldots,r}W^{j}$, and
consider a linear map $F:V\to W$ satisfying $F(V^{j})\subseteq W^{j}$. Then,
the linear map $F^{(j)}:V^{j}\to W^{j}$ defined by $F^{(j)}=\pi_{j}\circ
F\circ\imath_{j}$ satisfies:

(2.2) $\displaystyle F^{(j)}\circ\pi_{j}$ $\displaystyle=$
$\displaystyle\pi_{j}\circ F$ (2.3) $\displaystyle\imath_{j}\circ F^{(j)}$
$\displaystyle=$ $\displaystyle F\circ\imath_{j}.$

Continuing with our example, let $\mathbf{F}$ be represented by the matrix:

(2.4)
$\mathbf{F}=\frac{1}{2}\begin{bmatrix}\phantom{-}2&\phantom{-}0&\phantom{-}0&-4\\\
\phantom{-}1&\phantom{-}3&-1&\phantom{-}4\\\
-1&-1&\phantom{-}3&\phantom{-}0\\\
\phantom{-}0&\phantom{-}0&\phantom{-}0&\phantom{-}3\end{bmatrix},$

and note that $\mathbf{F}(V^{j})\subseteq V^{j}$. The maps $\mathbf{F}^{(j)}$
are then given by
$\mathbf{F}^{(1)}=\mathbf{P}_{1}\mathbf{F}\circ\imath_{1}=\mathbf{P}_{1}\mathbf{F}|_{V^{1}}=\mathbf{I}_{4}|_{V^{1}},\mathbf{F}^{(2)}=\mathbf{P}_{2}\mathbf{F}\circ\imath_{2}=\mathbf{P}_{2}\mathbf{F}|_{V^{2}}=2\mathbf{I}_{4}|_{V^{2}}$,
as well as
$\mathbf{F}^{(3)}=\mathbf{P}_{3}\mathbf{F}\circ\imath_{3}=\mathbf{P}_{3}\mathbf{F}|_{V^{3}}=3\mathbf{I}_{4}|_{V^{3}}$.
Since the vector subspaces $V^{j}$ are the generalized eigenspaces of
$\mathbf{F}$ corresponding to each different eigenvalue, the matrices
$\mathbf{F}^{(j)}$ are simply the identity matrix restricted to $V^{j}$
multiplied by the corresponding eigenvalue.

We denote by $\lambda_{1},\ldots,\lambda_{r}\in\mathbb{C}$ the (counted
without repetition) eigenvalues of $\mathbf{A}$ and by
$sp(\mathbf{A})=\\{\lambda_{1},\ldots,\lambda_{r}\\}$ its spectrum. The
algebraic multiplicity of an eigenvalue $\lambda_{j}$, denoted by
$\alpha(\lambda_{j})$, is the number of times (counted with repetition) that
$\lambda_{j}$ is a solution of $\det(\mathbf{A}-\lambda_{j}\mathbf{I}_{n})=0$.
The geometric multiplicity of an eigenvalue $\lambda_{j}$, denoted by
$\gamma(\lambda_{j})$, is the dimension of the vector space
$\ker(\mathbf{A}-\lambda_{j}\mathbf{I}_{n})$. We denote the space of
generalized eigenvectors associated with $\lambda_{j}$,
$\ker(\mathbf{A}-\lambda_{j}\mathbf{I}_{n})^{\alpha(\lambda_{j})}$, by
$V_{j}$. Note that $V_{j}$ has dimension $\alpha(\lambda_{j})$ and
$\gamma(\lambda_{j})$ Jordan chains.

Given a vector $\mathbf{b}\in\mathbb{R}^{n}$, we denote by
$\|\mathbf{b}\|_{0}$ the number of non-zero entries in $\mathbf{b}$.

##  3\. PROBLEM FORMULATION

###  3.1. System Model

Consider a discrete-time linear time-invariant system under sensor attacks of
the following form:

(3.1) $\displaystyle\mathbf{x}[k+1]$ $\displaystyle=$
$\displaystyle\mathbf{Ax}[k]$ (3.2) $\displaystyle\mathbf{y}_{i}[k]$
$\displaystyle=$ $\displaystyle\mathbf{C}_{i}\mathbf{x}[k]+\mathbf{e}_{i}[k],$

where $\mathbf{x}[k]\in\mathbb{R}^{n}$,
$\mathbf{y}_{i}[k]\in{\mathbb{R}}^{p_{i}}$ and
$\mathbf{e}_{i}[k]\in{\mathbb{R}}^{p_{i}}$ represent the state of the system,
the measurement acquired by sensor $i$, and the attack vector for sensor $i$
at time-step $k\in\mathbb{N}$, respectively. Let $\mathcal{V}$ denote the set
of sensors, and let $N=|\mathcal{V}|$. We use
$\mathbf{C}={\begin{bmatrix}\mathbf{C}^{T}_{1}|\mathbf{C}^{T}_{2}|\cdots|\mathbf{C}^{T}_{N}\end{bmatrix}}^{T}$
to denote the collection of the sensor observation matrices,
$\mathbf{y}[k]={\begin{bmatrix}\mathbf{y}^{T}_{1}[k]&\cdots&\mathbf{y}^{T}_{N}[k]\end{bmatrix}}^{T}$
and
$\mathbf{e}[k]={\begin{bmatrix}\mathbf{e}^{T}_{1}[k]&\cdots&\mathbf{e}^{T}_{N}[k]\end{bmatrix}}^{T}$
to represent the collective measurement vector and the collective attack
vector, respectively.

We define
$\mathcal{O}_{i}=\begin{bmatrix}\mathbf{C}_{i}^{T}|(\mathbf{C}_{i}\mathbf{A})^{T}|\dots|(\mathbf{C}_{i}\mathbf{A}^{\tau_{i}-1})^{T}\end{bmatrix}^{T}$
to be the observability matrix of sensor $i$ with $\tau_{i}$ being the
observability index of the pair $(\mathbf{A},\mathbf{C}_{i})$. We also define
$\mathbf{Y}_{i}=\begin{bmatrix}\mathbf{y}_{i}^{T}[0]&\dots&\mathbf{y}_{i}^{T}[\tau_{i}-1]\end{bmatrix}^{T}$
and
$\mathbf{E}_{i}=\begin{bmatrix}\mathbf{e}_{i}^{T}[0]&\dots&\mathbf{e}_{i}^{T}[\tau_{i}-1]\end{bmatrix}^{T}$
to be the collection of measurements and attacks of sensor $i$ over the time
horizon $[0,\tau_{i}-1]$, respectively. An equivalent expression for the
measurements is:

(3.3) $\mathbf{Y}_{i}=\mathcal{O}_{i}\mathbf{x}[0]+\mathbf{E}_{i}.$

In the remainder of the paper, we drop the time indices to simplify notation.

###  3.2. The Secure State-Reconstruction Problem

######  Problem 1.

(Secure state-reconstruction)
Input: Matrices $\mathbf{A}\in\mathbb{R}^{n\times n}$,
$\mathbf{C}_{i}\in\mathbb{R}^{p_{i}\times n},~{}i=1,\dots,N,$ and a set of
vectors ${\mathbf{Y}_{i}\in\mathbb{R}^{p_{i}\tau_{i}}},~{}i=1,\dots,N.$
Question: Find a vector $\mathbf{x}\in\mathbb{R}^{n}$ and a set $\mathcal{I}$
of minimal cardinality such that $\mathbf{Y}_{j}=\mathcal{O}_{j}\mathbf{x}$
for all $j\notin\mathcal{I}$.

In other words, the SSR problem requires the reconstruction of a state
$\mathbf{x}$ and the simplest attack explanation in the form of the least
number of attacked sensors. Note that when the solution $\mathbf{x}$ is
unique, we have found the state of the linear system. Although uniqueness of
solutions is essential when handling attacks, we can study the complexity of
the SSR problem independently of the number of solutions. To make this clear,
we will explicitly state the uniqueness requirements when needed.

###  3.3. Sparse Observability and Eigenvalue Observability

The notions of sparse observability and eigenvalue observability are
instrumental to the results in this paper.

######  Definition 1 (Sparse observability index).

The sparse observability index of the pair $(\mathbf{A},\mathbf{C})$ in system
(3.1)-(3.2) is the largest integer $k$ such that
$\mathrm{ker}~{}\mathcal{O}_{\mathcal{V}\backslash\mathcal{K}}=\\{0\\}$ for
any $\mathcal{K}\subseteq\mathcal{V},~{}|\mathcal{K}|\leq k$. When the sparse
observability index is $r$, we say that system (3.1)-(3.2) is $r-$sparse
observable.

It is proved in [14, 18] (see also [15] for a similar notion in continuous
time) that if at most $s$ sensors have been attacked in a system, the initial
state $\mathbf{x}[0]$ can be uniquely reconstructed if and only if the system
is at least $2s-$sparse observable. In view of this result, computing the
sparse observability index of a system is of great interest since it
characterizes the maximum number of arbitrary sensor attacks that can be
tolerated without compromising the ability to uniquely reconstruct the state.

In addition to sparse observability, we will require the notion of eigenvalue
observability [30, 31].

######  Definition 2 (Eigenvalue observability index).

We say that an eigenvalue $\lambda\in sp(\mathbf{A})$ is observable w.r.t.
sensor $i$ if the linear map defined by
$\begin{bmatrix}\mathbf{A}-\lambda\mathbf{I}_{n}\\\
\mathbf{C}_{i}\end{bmatrix}$ is injective.

If the above condition is satisfied, we equivalently say that “sensor $i$ can
observe eigenvalue $\lambda$”. Let the set of all sensors that can observe an
eigenvalue $\lambda$ be denoted $\mathcal{S}_{\lambda}$. The eigenvalue
observability index of system (3.1)-(3.2) is the largest integer $k$ such that
each eigenvalue of the matrix $\mathbf{A}$ is observable by at least $k+1$
distinct sensors. When the eigenvalue observability index is $k$, we say that
system (3.1)-(3.2) is $k$-eigenvalue observable.

We study the SSR problem under the following assumptions.

Assumption 1: For each sensor $i\in\\{1,\ldots,N\\}$ under attack, the
adversary can only manipulate sensor $i$’s measurements through the signal
$\mathbf{e}_{i}[k]$ in (3.2).

Assumption 2: The adversary is omniscient, i.e., we assume the adversary has
full knowledge of the system state, measurements, and plant model. Moreover,
all the attacked sensors are allowed to work cooperatively.

##  4\. SSR IS HARD

Fawzi _et al._ established in [14] a connection between the SSR problem and
compressed sensing by drawing inspiration from the ideas of Candes and Tao in
[33]. We take this approach further by also using the ideas in [33] to
establish that the SSR problem is NP-hard. To do so, we first define the
compressed sensing problem.

######  Problem 2.

(Compressed sensing)
Input: A full row rank matrix $\mathbf{F}\in\mathbb{Q}^{m\times n}$, a vector
$\mathbf{b}\in\mathbb{Q}^{m}$.
Question: Find the sparsest solution of $\mathbf{Fx}=\mathbf{b}$.

The compressed sensing problem yields the solution to the minimization
problem:

$\displaystyle\min_{\mathbf{x}}$
$\displaystyle\left\lVert\mathbf{x}\right\rVert_{0}$ s.t.
$\displaystyle\mathbf{Fx}=\mathbf{b}.$

######  Theorem 4.1.

The SSR problem is NP-hard.

###### Proof.

Given an instance of the compressed sensing problem, we generate an instance
of the SSR problem as follows. Let the system matrix be of the form
$\mathbf{A}=\mathbf{I}_{n}$, and the collective observation matrix
$\mathbf{C}$ satisfy $\mathrm{Im}\mathbf{C}=\mathrm{ker}~{}\mathbf{F}$. Let
the measurements of the sensors be scalar-valued, i.e., let $\mathbf{C}_{i}$
be the $i$-th row of $\mathbf{C}$. Note that based on the above $\mathbf{A}$
matrix, the observability index for each sensor $i\in\\{1,\ldots,N\\}$ is
given by $\tau_{i}=1$, and thus $\mathcal{O}_{i}=\mathbf{C}_{i}$. Finally, let
$\mathbf{Y}$ be any solution to the equation
$\mathbf{F}\mathbf{Y}=\mathbf{b}$. Since the linear equation
$\mathbf{F}{\mathbf{Y}}=\mathbf{b}$ is underdetermined, finding a solution
${\mathbf{Y}}$ can be done in polynomial time [34]. For each
$i\in\\{1,\ldots,N\\}$, set $\mathbf{Y}_{i}$ to be the $i$-th row of
$\mathbf{Y}$. Thus, given an instance of the compressed sensing problem, the
instance of the SSR problem described above can be constructed in polynomial
time.

The SSR problem for the constructed instance degenerates to:

(4.1) $\displaystyle\min_{\mathbf{x,e}}$
$\displaystyle\left\lVert\mathbf{e}\right\rVert_{0}$ s.t.
$\displaystyle\mathbf{Cx}+\mathbf{e}=\mathbf{Y}.$

We now show these two problems have the same solution. It is simple to see
that any solution $(\mathbf{x,e})$ of $\mathbf{Cx}+\mathbf{e}=\mathbf{Y}$
provides a solution to $\mathbf{Fe}=\mathbf{b}$, since by applying
$\mathbf{F}$ we obtain:

$\displaystyle\mathbf{F}(\mathbf{Cx}+\mathbf{e})$ $\displaystyle=$
$\displaystyle\mathbf{F}{\mathbf{Y}}$
$\displaystyle\Leftrightarrow\mathbf{Fe}$ $\displaystyle=$
$\displaystyle\mathbf{b}.$

To prove the converse, we show that for every $\mathbf{e}$ such that
$\mathbf{Fe}=\mathbf{b}$, there exists some $\mathbf{x}$ satisfying
$\mathbf{Cx}+\mathbf{e}=\mathbf{Y}$. Recalling that
$\mathbf{F}{\mathbf{Y}}=\mathbf{b}$, we obtain
$\mathbf{F}(\mathbf{Y}-\mathbf{e})=\mathbf{0}$, i.e.,
${\mathbf{Y}}-\mathbf{e}\in\mathrm{ker}~{}\mathbf{F}$. Since
$\mathrm{ker}~{}\mathbf{F}=\mathrm{Im}\mathbf{C}$, there exists an
$\mathbf{x}$ such that $\mathbf{Cx}=\mathbf{Y}-\mathbf{e}$, as desired.

Noting that the equations $\mathbf{Fe}=\mathbf{b}$ and
$\mathbf{Cx}+\mathbf{e}=\mathbf{Y}$ have the same solutions for $\mathbf{e}$,
we conclude that they also have the same sparsest solution. In other words, if
there exists an algorithm $\mathcal{A}$ that solves the SSR problem for the
specific instance constructed by us, such an algorithm will also yield a
solution to the given instance of the compressed sensing problem. It then
follows that since the compressed sensing problem is NP-hard [35], the secure
state reconstruction problem is also NP-hard. ∎

##  5\. SYSTEM DECOMPOSITION

In the previous section, we proved that the SSR problem is in general NP-hard.
This means there does not exist a polynomial-time solution unless $P=NP$.
Despite this fact, we show in this section how to decompose the SSR problem
into smaller instances. In the next section, we identify which of these
smaller instances are NP-hard, and which ones are solvable in polynomial time.

######  Lemma 5.1.

Assume the existence of a collection of vector spaces
$\\{X^{j}\\}_{j=1,\ldots,r}$ satisfying:

  1. (1)

$\mathbb{C}^{n}=\bigoplus_{j=1,\ldots,r}X^{j}$;

  2. (2)

$\mathbf{A}(X^{j})\subseteq X^{j}$ for $j=1,\ldots,r$;

  3. (3)

$\mathcal{O}_{i}(\mathbb{C}^{n})=\bigoplus_{j=1,\ldots,r}\mathcal{O}_{i}^{j}(X^{j})\quad\text{for~{}}i=1,\ldots,p,$

then for any $\mathbf{Y}_{i}$, a solution $\mathbf{x}$ of the equation:

(5.1) $\mathbf{Y}_{i}=\mathcal{O}_{i}\mathbf{x},$

whenever it exists, can be written as
$\mathbf{x}=\mathbf{x}_{1}+\mathbf{x}_{2}+\ldots+\mathbf{x}_{r}$ with
$\mathbf{x}_{j}=\pi_{j}(\mathbf{x})\in X^{j}$ given by the solution of:

(5.2) $\mathbf{Y}_{i}^{j}=\mathcal{O}_{i}^{j}\mathbf{x}_{j},$

for $\mathbf{Y}_{i}^{j}=\pi_{j}(\mathbf{Y}_{i})\in\mathcal{O}_{i}^{j}(X^{j})$
and $\mathcal{O}_{i}^{j}=\pi_{j}\circ\mathcal{O}_{i}\circ\imath_{j}$.

###### Proof.

Let $\mathbf{x}_{j}$ be the solution of (5.2) and note that:

$\mathbf{Y}_{i}^{j}=\mathcal{O}_{i}^{j}\mathbf{x}_{j}\Rightarrow\imath_{j}(\mathbf{Y}_{i}^{j})=\imath_{j}\circ\mathcal{O}_{i}^{j}(\mathbf{x}_{j})=\mathcal{O}_{i}\circ\imath_{j}(\mathbf{x}_{j})=\mathcal{O}_{i}\mathbf{x}_{j},$

where the third equality follows from (2.3). By summing over $j$ we obtain:

$\mathbf{Y}_{i}=\sum_{j=1}^{r}\imath_{j}(\mathbf{Y}_{i}^{j})=\sum_{j=1}^{r}\mathcal{O}_{i}\mathbf{x}_{j}=\mathcal{O}_{i}\sum_{j=1}^{r}\mathbf{x}_{j}=\mathcal{O}_{i}\mathbf{x}.$

Hence, the solutions to (5.2) provide a solution to (5.1). Consider now (5.1):

$\displaystyle\mathbf{Y}_{i}=$
$\displaystyle\mathcal{O}_{i}\mathbf{x}\Rightarrow\pi_{j}(\mathbf{Y}_{i})=\pi_{j}\circ\mathcal{O}_{i}(\mathbf{x})$
$\displaystyle\Rightarrow$
$\displaystyle\mathbf{Y}_{i}^{j}=\mathcal{O}_{i}^{j}\circ\pi_{j}(\mathbf{x})=\mathcal{O}_{i}^{j}\mathbf{x}_{j}.$

where the third equality follows from (2.2). Hence, if $\mathbf{x}$ is a
solution to (5.1), then $\mathbf{x}_{i}$ is a solution to (5.2). ∎

Intuitively, we treat the state-space $\mathbb{R}^{n}$ as the direct sum of
multiple subspaces. If the images of these subspaces under the linear map
$\mathcal{O}_{i}$ are pairwise non-overlapping, we are able to project the
state vector $\mathbf{x}$ onto these subspaces, project the measurement
$\mathbf{Y}_{i}$ onto the image under the linear map $\mathcal{O}_{i}$ of
these subspaces, and then establish a one-to-one correspondence between the
projected state vector and the projected measurement. This effectively
decomposes the original problem into $r$ sub-problems, each of dimension
$\mathrm{dim}(X^{j})$. As formalized in the next result, the spaces $X^{j}$
can always be taken to be the generalized eigenspaces of $\mathbf{A}$.

######  Proposition 1.

The generalized eigenspaces $V^{1},V^{2},\dots,V^{r}$ of $\mathbf{A}$ satisfy
properties (1)-(3) in Lemma 5.1.

###### Proof.

Properties (1) and (2) in Lemma (5.1) follow directly from the definition of
generalized eigenspace. To simplify notation, we will drop the sensor index
$i$ in this proof.

It also follows from the definition of generalized eigenspace that
$\cup_{j=1,\ldots,r}V^{j}$ spans $\mathbb{C}^{n}$. Therefore, the set
$\cup_{j=1,\ldots,r}\mathcal{O}(V^{j})$ spans $\mathcal{O}(\mathbb{C}^{n})$.
Given this, to conclude property (3) we only need to show:

$\mathcal{O}(V^{j})\cap\mathcal{O}(V^{k})=\\{0\\},\qquad\forall j\neq k.$

Moreover, it suffices to show that for any $\mathbf{x}_{j}\in V^{j}$ and
$\mathbf{x}_{k}\in V^{k}$, with $j\neq k$, the equality
$\mathcal{O}(\mathbf{x}_{j}+\mathbf{x}_{k})=0$ can only be satisfied if
$\mathcal{O}\mathbf{x}_{j}=0=\mathcal{O}\mathbf{x}_{k}$.

We have the following sequence of equalities that is explained thereafter:

$\displaystyle 0$ $\displaystyle=$
$\displaystyle\mathcal{O}(\mathbf{x}_{j}+\mathbf{x}_{k})$ $\displaystyle=$
$\displaystyle\mathcal{O}(\mathbf{A}-\lambda_{k}\mathbf{I}_{n})^{\alpha(\lambda_{k})}(\mathbf{x}_{j}+\mathbf{x}_{k})$
$\displaystyle=$
$\displaystyle\mathcal{O}(\mathbf{A}-\lambda_{k}\mathbf{I}_{n})^{\alpha(\lambda_{k})}(\mathbf{x}_{j})$
$\displaystyle=$ $\displaystyle\mathcal{O}\mathbf{x}_{j}.$

The second step follows from
$\ker\mathcal{O}\subseteq\ker\mathcal{O}(\mathbf{A}-\lambda_{k}\mathbf{I}_{n})^{\alpha(\lambda_{k})}$,
the third step follows from $\mathbf{x}_{k}\in
V^{k}=\ker(\mathbf{A}-\lambda_{k}\mathbf{I}_{n})^{\alpha(\lambda_{k})}$, and
the fourth from the following sequence of steps:

$\displaystyle\dim\ker\mathcal{O}\big{|}_{V^{j}}$ $\displaystyle\leq$
$\displaystyle\dim\ker\mathcal{O}(\mathbf{A}-\lambda_{k}\mathbf{I}_{n})^{\alpha(\lambda_{k})}\big{|}_{V^{j}}$
$\displaystyle=$
$\displaystyle\dim\ker(\mathbf{A}-\lambda_{k}\mathbf{I}_{n})^{\alpha(\lambda_{k})}\big{|}_{V^{j}}$
$\displaystyle+$
$\displaystyle\dim\ker\mathcal{O}\big{|}_{(\mathbf{A}-\lambda_{k}\mathbf{I}_{n})^{\alpha(\lambda_{k})}{V^{j}}}$
$\displaystyle=$
$\displaystyle\dim\ker\mathcal{O}\big{|}_{(\mathbf{A}-\lambda_{k}\mathbf{I}_{n})^{\alpha(\lambda_{k})}{V^{j}}}$
$\displaystyle\leq$ $\displaystyle\dim\ker\mathcal{O}\big{|}_{V^{j}}.$

The first step comes from
$\ker\mathcal{O}\subseteq\ker\mathcal{O}(\mathbf{A}-\lambda_{k}\mathbf{I}_{n})$.
To show that the second step is true, we observe that
$\mathrm{dim~{}}\mathrm{ker}~{}\mathbf{MN}=\mathrm{dim~{}}\mathrm{ker}~{}\mathbf{N}+\mathrm{dim~{}}\mathrm{ker}(\mathbf{M}\big{|}_{\mathbf{N}(\mathbb{C}^{n})})$
for any matrices $\mathbf{M},\mathbf{N}\in\mathbb{C}^{n\times n}$. The third
step comes from the map
$(\mathbf{A}-\lambda_{j}\mathbf{I}_{n})^{\alpha(\lambda_{j})}\big{|}_{V^{j}}$
being injective if $j\neq k$, as the generalized eigenspaces $V^{j}$ and
$V^{k}$ intersect only at the origin, and
$\ker(\mathbf{A}-\lambda_{j}\mathbf{I}_{n})^{\alpha(\lambda_{j})}=V^{j}$. The
fourth step follows by the $\mathbf{A}-$invariant nature of eigenspace
$V^{j}$. This shows
$\dim\ker\mathcal{O}\big{|}_{V^{j}}=\dim\ker\mathcal{O}(\mathbf{A}-\lambda_{k}\mathbf{I}_{n})^{\alpha(\lambda_{k})}\big{|}_{V^{j}}$
which, combined with
$\ker\mathcal{O}\big{|}_{V^{j}}\subseteq\ker\mathcal{O}(\mathbf{A}-\lambda_{k}\mathbf{I}_{n})^{\alpha(\lambda_{k})}\big{|}_{V^{j}}$,
can only hold when
$\ker\mathcal{O}\big{|}_{V^{j}}=\ker\mathcal{O}(\mathbf{A}-\lambda_{k}\mathbf{I}_{n})^{\alpha(\lambda_{k})}\big{|}_{V^{j}}$.
A symmetric argument can be used to show that $\mathcal{O}\mathbf{x}_{k}=0$
and the claim is thus proved. ∎

Combining Lemma (5.1) and Proposition (1) results in a decomposition of the
sensor measurements in (3.3):

(5.3) $\displaystyle\mathbf{Y}_{i}^{j}=\mathcal{O}_{i}^{j}\mathbf{x}_{j},\quad
j=1,2,\dots,r,$

where $\mathbf{Y}_{i}^{j}=\pi_{j}(Y_{i})$ is the projection of measurement
$\mathbf{Y}_{i}$ onto the vector space $\mathcal{O}_{i}(V^{j})$, the linear
transformation $\mathcal{O}_{i}^{j}$ is defined by
$\mathcal{O}_{i}^{j}=\pi_{j}\circ\mathcal{O}_{i}\circ\imath_{j}$,
$\mathbf{x}_{j}$ is given by $\mathbf{x}_{j}=\pi_{j}(\mathbf{x})$,
$\pi_{j}:\mathbb{R}^{n}\rightarrow V^{j}$ is the canonical projection and
$\imath_{j}:V^{j}\rightarrow\mathbb{R}^{n}$ is the canonical inclusion.

######  Theorem 5.2.

A solution $\mathbf{x}$ of the SSR problem with inputs
$\mathbf{A},\mathbf{C}_{i},\mathbf{Y}_{i}$ is given by
$\mathbf{x}=\mathbf{x}_{1}+\mathbf{x}_{2}+\dots+\mathbf{x}_{j}$ where
$\mathbf{x}_{i}$ is the solution to the SSR problem with inputs
$\mathbf{A}^{(j)}=\pi_{j}\circ\mathbf{A}\circ\imath_{j}$,
$\mathbf{C}_{i}^{j}=\mathbf{C}_{i}\circ\imath_{j}$, $\mathbf{Y}_{i}^{j}$.

###### Proof.

Follows directly from Lemma 5.1, Proposition 1, and the properties of
generalized eigenspaces. ∎

Theorem (5.2) lays the theoretical foundation for decomposing the SSR problem
with $n$ states into $r$ sub-problems of the form:

(5.4) $\displaystyle\mathbf{x}_{j}[k+1]$
$\displaystyle=\mathbf{A}^{(j)}\mathbf{x}_{j}[k],$
$\displaystyle\mathbf{Y}_{i}^{j}[k]$
$\displaystyle=\mathcal{O}_{i}^{j}\mathbf{x}_{j}[k]+\mathbf{E}_{i}^{j}[k],$

each with $\alpha(\lambda_{1}),\alpha(\lambda_{2}),\dots,\alpha(\lambda_{r})$
states. The attack vector $\mathbf{E}_{i}^{j}$ is identically zero when sensor
$i$ is not under attack. The state of the original problem can be
reconstructed by summing up the state reconstructions of each sub-problem.

We now illustrate the decomposition of (3.1)-(3.2) into (5.4) through an
example. The matrix $\mathbf{A}$ is the same as the matrix $\mathbf{F}$
defined in (2.4) and the matrices $\mathbf{C}_{i}$ are given by:

$\displaystyle\mathbf{C}_{1}=\begin{bmatrix}3&2&0&2\end{bmatrix},$
$\displaystyle\mathbf{C}_{2}=\begin{bmatrix}2&3&1&-1\end{bmatrix},$
$\displaystyle\mathbf{C}_{3}=\begin{bmatrix}2&2&0&0\end{bmatrix},$
$\displaystyle\mathbf{C}_{4}=\begin{bmatrix}2&3&-1&0\end{bmatrix}.$

As we discussed below (2.4), the generalized eigenspaces of $\mathbf{A}$ are
$V^{1}=\mathrm{Im}(\mathbf{M}_{1}),V^{2}=\mathrm{Im}(\mathbf{M}_{2}),$ and
$V^{3}=\mathrm{Im}(\mathbf{M}_{3})$ corresponding to eigenvalues $1,2,$ and
$3$ respectively, where $\mathbf{M}_{j}$ are defined in (2.1) for $j=1,2,3$.
Also, recall that the projections $\pi_{1},\pi_{2},$ and $\pi_{3}$ are
$\mathbf{P}_{j}=\mathbf{M}_{j}(\mathbf{M}_{j}^{T}\mathbf{M}_{j})^{-1}\mathbf{M}_{j}^{T}$
for $j=1,2,3$. By definition, we have
$\mathbf{x}_{1}=\mathbf{P}_{1}\mathbf{x}$,
$\mathbf{x}_{2}=\mathbf{P}_{2}\mathbf{x}$,
$\mathbf{x}_{3}=\mathbf{P}_{3}\mathbf{x}$, and
$\mathbf{A}^{(1)}=\mathbf{P}_{1}\mathbf{A}|_{V^{1}}$,
$\mathbf{A}^{(2)}=\mathbf{P}_{2}\mathbf{A}|_{V^{2}}$,
$\mathbf{A}^{(3)}=\mathbf{P}_{3}\mathbf{A}|_{V^{3}}$. Hence the decomposition
of $\mathbf{x}[k+1]=\mathbf{A}\mathbf{x}[k]$ is given by:

$\mathbf{P}_{j}\mathbf{x}[k+1]=(\mathbf{P}_{j}\mathbf{A}|_{V^{j}})(\mathbf{P}_{j}\mathbf{x}[k]),\quad
j=1,2,3.$

We now illustrate how to decompose the measurement equation
$\mathbf{Y}_{1}[k]=\mathcal{O}_{1}\mathbf{x}[k]+\mathbf{E}_{1}[k]$ for sensor
1. The observability matrix $\mathcal{O}_{1}$ of sensor $1$ is given by:

$\mathcal{O}_{1}=\begin{bmatrix}3&2&\phantom{-}0&2\\\ 4&3&-1&4\\\ 6&5&-3&10\\\
10&9&-7&28\end{bmatrix}.$

We first compute the projections
$\widetilde{\pi}_{1}^{1},\widetilde{\pi}_{1}^{2}$ and
$\widetilde{\pi}_{1}^{3}$ that map $\mathcal{O}_{1}(\mathbb{R}^{4})$ to
$\mathcal{O}_{1}(V^{1}),\mathcal{O}_{1}(V^{2}),$ and $\mathcal{O}_{1}(V^{3})$,
respectively. To do this, we define the matrices:

$\widetilde{\mathbf{M}}_{1}=\begin{bmatrix}1\\\ 1\\\ 1\\\
1\end{bmatrix},~{}\widetilde{\mathbf{M}}_{2}=\begin{bmatrix}1\\\ 2\\\ 4\\\
8\end{bmatrix},~{}\text{and}~{}\widetilde{\mathbf{M}}_{3}=\begin{bmatrix}1\\\
3\\\ 9\\\ 27\end{bmatrix},$

which satisfy
$\mathcal{O}_{1}(V^{1})=\mathrm{Im}(\widetilde{\mathbf{M}}_{1})$,
$\mathcal{O}_{1}(V^{2})=\mathrm{Im}(\widetilde{\mathbf{M}}_{2})$, and
$\mathcal{O}_{1}(V^{3})=\mathrm{Im}(\widetilde{\mathbf{M}}_{3})$. We also
remark that the collection
$\\{\mathcal{O}_{1}(V^{1}),\mathcal{O}_{1}(V^{2}),\mathcal{O}_{1}(V^{3})\\}$
is an internal direct sum of the vector space
$\mathcal{O}_{1}(\mathbb{R}^{4})$. Therefore, each projection
$\widetilde{\pi}_{1}^{i}$ can be represented by the projection matrix:

$\widetilde{\mathbf{P}}_{1}^{i}=\widetilde{\mathbf{M}}_{i}(\widetilde{\mathbf{M}}_{i}^{T}\widetilde{\mathbf{M}}_{i})^{-1}\widetilde{\mathbf{M}}_{i}^{T},~{}i=1,2,3.$

By definition,
$\mathbf{Y}_{1}^{j}=\widetilde{\mathbf{P}}_{1}^{j}\mathbf{Y}_{1}$,
$\mathbf{E}_{1}^{j}=\widetilde{\mathbf{P}}_{1}^{j}\mathbf{E}_{1}$ and
$\mathcal{O}_{1}^{j}=\widetilde{\mathbf{P}}_{1}^{j}\mathcal{O}_{1}|_{V^{j}}$
for $j=1,2,3$. In summary, the decomposition of measurement
$\mathbf{Y}_{1}[k]=\mathcal{O}_{1}\mathbf{x}[k]+\mathbf{E}_{1}[k]$ is given
by:

$\widetilde{\mathbf{P}}_{1}^{j}\mathbf{Y}_{1}[k]=(\widetilde{\mathbf{P}}_{1}^{j}\mathcal{O}_{1}|_{V^{j}})(\mathbf{P}_{1}^{j}\mathbf{x}[k])+\widetilde{\mathbf{P}}_{1}^{j}\mathbf{E}_{1}[k],\quad
j=1,2,3.$

##  6\. CLASSES OF SSR PROBLEMS SOLVABLE IN POLYNOMIAL TIME

While in the previous section we established that the SSR problem is NP-hard,
in this section we leverage the results in Section 5 to answer a simple but
important question: when can we solve the SSR problem in polynomial time? Our
answer relies heavily on the system decomposition technique introduced in
Section 5. The first result establishes that the decomposition can be done in
polynomial time.

######  Proposition 2.

The computational complexity of decomposing the system (3.1)-(3.2) into sub-
systems (5.4) is within $O(pn^{3})$.

###### Proof.

To prove this result, we list all the steps involved in the decomposition from
(3.1)-(3.2) to (5.4) and list the computational complexity of each step.

Offline preparation 1: compute the observability matrix of each sensor
$\mathcal{O}_{i}$. The computational complexity of this step is $O(pn^{2})$.

Offline preparation 2: find the eigenvalues of the matrix $\mathbf{A}$ as well
as its generalized eigenspaces $V^{j}$. This can be done by finding the Jordan
form of $\mathbf{A}$. The computational complexity of this step is $O(n^{3})$.

Offline preparation 3: determine the image of each generalized eigenspace
$V^{j}$ under the observability matrix $\mathcal{O}_{i}$, i.e.,
$\mathcal{O}_{i}(V^{j})$. In this step, we perform $p$ times two $n\times n$
matrix multiplications and thus the complexity of this step is $O(pn^{3})$.

Offline preparation 4: find the projection matrix for each generalized
eigenspace and each sensor. The computational complexity of this step is
$O(pn^{3})$.

Online task: at each time instance, project the measurements
$\mathbf{Y}_{i}[k]$ of each sensor $i$ onto each generalized eigenspace. In
this step, for each sensor we multiply a $n\times n$ matrix by a $n\times 1$
vector $r$ times. This requires $O(pn^{2}r)$ time.

We thus conclude that we can decompose the system (3.1)-(3.2) into sub-systems
(5.4) within $O(pn^{3})$ and finish the proof. ∎

Before giving an answer to the question we stated at the beginning of this
section, we relate the sparse observability index defined for the system
(3.1)-(3.2) and the sparse observability index for each subsystem (5.4) with
$j$ ranging from $1$ to $r$. In the following two results we refer to
$k$-sparse observability and $k$-eigenvalue observability of subsystem (5.4).
Note that, since the state space of (5.4) is $V^{j}$, sparse observability is
characterized by the injectivity of $\mathcal{O}_{i}^{j}|_{V^{j}}$ whereas
eigenvalue observability is characterized by injectivity of the linear map
$\begin{bmatrix}\mathbf{A}^{(j)}-\lambda_{j}\mathbf{I}_{n}^{(j)}\\\
\mathbf{C}_{i}^{j}\end{bmatrix}$, where we define
$\mathbf{I}_{n}^{(j)}=\pi_{j}\circ\mathbf{I}_{n}\circ\imath_{j}$. We now have
the following results.

######  Theorem 6.1.

The system (3.1)-(3.2) is $k$-sparse observable if and only if for each
$j\in\\{1,2,\ldots,r\\}$, the system (5.4) is $k$-sparse observable.

###### Proof.

This result can be easily established by observing that
$\mathrm{ker}~{}\mathcal{O}_{i}=\oplus_{j=1}^{r}\mathrm{ker}~{}\mathcal{O}_{i}^{j}$
holds for any sensor $i$. We omit the proof here in the interest of space. ∎

Similarly, to relate the eigenvalue observability index defined for the
overall system and the eigenvalue observability index for each subsystem, we
have the following result.

######  Theorem 6.2.

The system (3.1)-(3.2) is $k$-eigenvalue observable if and only if for each
$j\in\\{1,2,\ldots,r\\}$, the system (5.4) is $k$-eigenvalue observable.

###### Proof.

By the definition of eigenvalue observability, it suffices to show the matrix
$\begin{bmatrix}\mathbf{A}-\lambda_{j}\mathbf{I}_{n}\\\
\mathbf{C}_{i}\end{bmatrix}$ has full column rank if and only if each matrix
$\begin{bmatrix}\mathbf{A}^{(j)}-\lambda_{j}\mathbf{I}_{n}^{(j)}\\\
\mathbf{C}_{i}^{j}\end{bmatrix}$ defines an injective map with domain $V^{j}$,
for $j$ ranging from $1$ to $r$.

Consider the map $F:V\rightarrow V\times\mathbb{R}^{p_{i}}$ defined by the
matrix $\begin{bmatrix}\mathbf{A}-\lambda_{j}\mathbf{I}_{n}\\\
\mathbf{C}_{i}\end{bmatrix}$ and note that $F$ being injective is equivalent
to $\ker F=\\{0\\}$. Note also that the result immediately follows if we
establish that $\ker F\subseteq V^{j}$. This can be seen by noting that
$F\mathbf{x}=0$ for $\mathbf{x}\in\mathbb{R}^{n}$ degenerates to
$F\mathbf{x}=0$ for $\mathbf{x}\in V^{j}$ and (given
$\mathbf{x}=\imath_{j}\mathbf{x}$) can be written as
$F\imath_{j}\mathbf{x}=0$:

(6.1) $\begin{bmatrix}\mathbf{A}\circ\imath_{j}-\lambda_{j}\imath_{j}\\\
\mathbf{C}_{i}\circ\imath_{j}\end{bmatrix}\mathbf{x}=0.$

Moreover, since $(\mathbf{A}-\lambda_{j}\mathbf{I}_{n})(V^{j})\subseteq V^{j}$
we have the equality
$\pi_{j}(\mathbf{A}-\lambda_{j}\mathbf{I}_{n})\imath_{j}\mathbf{x}=(\mathbf{A}-\lambda_{j}\mathbf{I}_{n})\imath_{j}\mathbf{x}$.
Therefore, (6.1) degenerates into:

(6.2)
$\begin{bmatrix}\pi_{j}\circ\mathbf{A}\circ\imath_{j}-\lambda_{j}\pi_{j}\circ\imath_{j}\\\
\mathbf{C}_{i}\circ\imath_{j}\end{bmatrix}\mathbf{x}=\begin{bmatrix}\mathbf{A}^{(j)}-\lambda_{j}\mathbf{I}_{n}^{(j)}\\\
\mathbf{C}_{i}^{j}\end{bmatrix}\mathbf{x}=0.$

Therefore, we proceed by showing that $\ker F\subseteq V^{j}$. The equality
$F\mathbf{x}=0$ implies $(\mathbf{A}-\lambda_{j}\mathbf{I}_{n})\mathbf{x}=0$.
If we write $\mathbf{x}$ as $\mathbf{x}_{j}+\mathbf{x}_{\overline{j}}$ with
$\mathbf{x}_{j}=\pi_{j}(\mathbf{x})$ and
$\mathbf{x}_{\overline{j}}=\sum_{k=1,k\neq j}^{r}\pi_{k}(\mathbf{x})$ we have
$(\mathbf{A}-\lambda_{j}\mathbf{I}_{n})(\mathbf{x}_{j}+\mathbf{x}_{\overline{j}})=0$.
We now make two observations. The first is that
$(\mathbf{A}-\lambda_{j}\mathbf{I}_{n})\mathbf{x}_{\overline{j}}=0$ implies
$\mathbf{x}_{\overline{j}}=0$ since $\mathbf{x}_{\overline{j}}\neq 0$ would
imply that $\mathbf{x}_{\overline{j}}\in V^{j}$, by definition of $V^{j}$. The
second observation is that
$(\mathbf{A}-\lambda_{j}\mathbf{I}_{n})(V^{\ell})\subseteq V^{\ell}$, for
$\ell\in\\{1,\ldots,r\\}$, implies that
$(\mathbf{A}-\lambda_{j}\mathbf{I}_{n})(\mathbf{x}_{j}+\mathbf{x}_{\overline{j}})=0$
iff $(\mathbf{A}-\lambda_{j}\mathbf{I}_{n})\mathbf{x}_{j}=0$ and
$(\mathbf{A}-\lambda_{j}\mathbf{I}_{n})\mathbf{x}_{\overline{j}}=0$. From the
first observation we have $\mathbf{x}_{\overline{j}}=0$ which implies that
$\mathbf{x}\in V^{j}$ and concludes the proof. ∎

Based on the above decomposition and the assumption that at most $s$ sensors
are attacked, we partition the set of eigenvalues
$\\{\lambda_{1},\lambda_{2},\ldots,\lambda_{r}\\}$ as follows:

  * •

We define
$\mathcal{J}_{1}\subseteq\\{\lambda_{1},\lambda_{2},\ldots,\lambda_{r}\\}$ to
be the set of eigenvalues whose corresponding subsystems (5.4) are not
$2s$-sparse observable.

  * •

We define
$\mathcal{J}_{2}\subseteq\\{\lambda_{1},\lambda_{2},\ldots,\lambda_{r}\\}\setminus\mathcal{J}_{1}$
to be the set of eigenvalues whose corresponding subsystems (5.4) are
$2s$-eigenvalue observable.

  * •

We define
$\mathcal{J}_{3}=\\{\lambda_{1},\lambda_{2},\ldots,\lambda_{r}\\}\setminus\\{\mathcal{J}_{1}\cup\mathcal{J}_{2}\\}$
to be the set of eigenvalues whose corresponding subsystems (5.4) are
$2s$-sparse observable but not $2s-$eigenvalue observable.

###  6.1. Impossibility of Reconstructing Substates Corresponding to
Eigenvalues in the Set $\mathcal{J}_{1}$

It is established in Section (3) that the SSR problem does not admit a unique
solution if it is not $2s-$sparse observable. Therefore, it is impossible to
reconstruct the substates corresponding to eigenvalues in $\mathcal{J}_{1}$.
Furthermore, by Theorem (6.1) if $\mathcal{J}_{1}$ is not empty, the overall
system defined in (3.1)-(3.2) is not $2s-$sparse observable, which in turn
means the solution is not unique.

###  6.2. Reconstructing the Substates Corresponding to Eigenvalues in the Set
$\mathcal{J}_{2}$

We learned from Theorem (6.2) that if $\lambda_{j}$ is observable w.r.t.
sensor $i$, then after decomposing the system, $\lambda_{j}$ is also
observable w.r.t. to sensor $i$ in the $j$-th sub-system corresponding to this
sensor. By the Popov-Belevitch-Hautus (PBH) test, the $j$-th sub-system
($\mathbf{A}^{(j)},\mathbf{C}_{i}^{j}$) is observable, which shows that
$\mathbf{x}_{j}$ can be reconstructed using only measurements from sensor $i$.

We now explain how to reconstruct the substates corresponding to eigenvalues
in $\mathcal{J}_{2}$ based on majority voting. Consider any eigenvalue
$\lambda_{j}\in\mathcal{J}_{2}$. Let $S_{\lambda_{j}}$ represent the set of
sensors w.r.t. which $\lambda_{j}$ is observable. The result of the PBH test
implies that $\mathbf{x}_{j}$ can be recovered using the measurements of each
of the sensors in the set $\mathcal{S}_{\lambda_{j}}$. We denote by
$x_{j}^{(l)}$ the $l$th component of $\mathbf{x}_{j}$. Based on the definition
of the set $\mathcal{J}_{2}$, we have $|\mathcal{S}_{\lambda_{j}}|\geq(2s+1)$.
Consequently, since at most $s$ sensors have been compromised, we are
guaranteed at least $s+1$ consistent copies of the state $x_{j}^{(l)}$. Thus,
each component of the vector $x_{j}^{(l)}$ can be recovered via majority
voting and therefore all the substates corresponding to eigenvalues in
$\mathcal{J}_{2}$ can be reconstructed in polynomial time.

###  6.3. Computational Complexity of Reconstructing Substates Corresponding
to Eigenvalues in the Set $\mathcal{J}_{3}$

The NP-hardness of solving the SSR problem has been established in Section 4.
In this subsection, we argue that with the prescribed decomposition technique,
the computational complexity of solving the SSR problem for substates
corresponding to eigenvalues in $\mathcal{J}_{3}$ could be reduced whenever we
only need to work with substates whose dimension is smaller than $n$. Assuming
$s$ is the upper bound of the number of attacked sensors, we have the
following theorem.

######  Theorem 6.3.

By applying the decomposition (5.4), the SSR problem can be solved in time
$\sum_{\lambda_{j}\in\mathcal{J}_{3}}\mathcal{C}(p,n_{j})+O(pn^{3})$ if the
system (3.1)-(3.2) is $2s-$sparse observable, where $\mathcal{C}(p,n)$ is the
time complexity of solving an instance of the SSR problem with $n$ states and
$p$ sensors whose corresponding system is $2s-$sparse observable.

Before providing a proof we first discuss how this result may reduce the
computational complexity of solving the SSR problem. For a large-scale CPS,
it’s not uncommon for the number of sensors to greatly exceed the number of
states, i.e., $p\gg n$. We note that the computational complexity of brute
force search grows exponentially with $p$. Also, the computational complexity
of some brute force search algorithms (such as [15]) to determine whether a
set of sensors is attacked is at least $O(n^{2})$ . In other words, for such
algorithms $\mathcal{C}(p,n)\geq O(p^{2}n^{2})$. By assuming $p\gg n$ we make
the following observations:

  1. (1)

$O(p^{2}n^{2})\geq\sum_{j=1}^{r}O(p^{2}n_{j}^{2})$, and equality holds only
when $r=1$.

  2. (2)

$O(pn^{3})\ll\sum_{j=1}^{r}O(p^{2}n_{j}^{2})$.

The first observation shows that the computation required to solve all the
sub-problems is smaller than what is required to solve the original problem.
The second observation shows that, compared with the computational complexity
of solving the SSR problem, the computation required for decomposition of the
original system is negligible. These two facts indicate that by decomposing
the SSR problem into simpler instances, we reduce the computational complexity
of solving the SSR problem.

Proof of Theorem 6.3: We already established that reconstructing the state of
each decomposed system is also an SSR problem and the solution $\mathbf{x}$ of
the original problem is obtained by summing over all the projections, i.e.,
$\mathbf{x}=\mathbf{x}_{1}+\mathbf{x}_{2}+\dots+\mathbf{x}_{r}$. Therefore any
algorithm that solves the SSR problem can be applied to solve each subproblem,
i.e., we may solve each subproblem corresponding to
$\lambda_{j}\in\mathcal{J}_{3}$ within time complexity $\mathcal{C}(p,n_{j})$
since there are $p$ sensors and $n_{j}$ states. By the assumption that the
system (3.1)-(3.2) is $2s-$sparse observable as well as Theorem (6.1), all
sub-systems are $2s-$sparse observable and hence $\mathcal{J}_{1}=\\{\phi\\}$,
and for each subproblem corresponding to $\lambda_{j}\in\mathcal{J}_{2}$ the
time complexity of the majority voting algorithm is within $O(pn^{2})$. In
summary, the total computational complexity is:

$\displaystyle\sum_{\lambda_{j}\in\mathcal{J}_{2}}O(pn_{j}^{2})+\sum_{\lambda_{j}\in\mathcal{J}_{3}}\mathcal{C}(p,n_{j})+O(pn^{3})$
$\displaystyle=$
$\displaystyle\sum_{\lambda_{j}\in\mathcal{J}_{3}}\mathcal{C}(p,n_{j})+O(pn^{3}),$

which finishes the proof.

∎

######  Remark 6.4.

The actual complexity might be even smaller than
$\sum_{\lambda_{j}\in\mathcal{J}_{3}}\mathcal{C}(p,n_{j})+O(pn^{3})$. This can
be seen by noting that we solve each smaller SSR problem sequentially, and
thus we can remove measurements from sensors that have been identified as
being attacked when solving subsequent problems.

###  6.4. Polynomial-Time Solvable SSR Problem Instances

To conclude, we have the following result which answers the question at the
beginning of this section by pointing out when the SSR problem can be solved
in polynomial time, which actually is a corollary of Theorem (6.3).

######  Corollary 1.

Consider the system (3.1)-(3.2), and suppose at most $s$ sensors are attacked.
Let the eigenvalue observability index of system (3.1)-(3.2) be at least $2s$.
Then, the SSR problem can be solved in polynomial time.

######  Remark 6.5.

We point out that the majority voting algorithm can be extended to solve more
general SSR problem instances where noise with bounded second moments appears
in (3.1)- (3.2), if the eigenvalue observability index is at least $2s$. To
see this, notice that under the above noise model, each copy of $x_{j}^{(l)}$
recovered from an attack-free sensor is the true value of that component of
the state perturbed by noise with bounded second moments. Now suppose that for
estimating each component $x_{j}^{(l)}$ of $\mathbf{x}_{j}$, the highest $s$
and the lowest $s$ estimates of $x_{j}^{(l)}$ from the set
$\mathcal{S}_{\lambda_{j}}$ are rejected, and a convex combination is taken of
the remaining estimates. Given that at most $s$ sensors are under attack, it
is not hard to see that this scheme leads to a bounded error in the estimation
of $x_{j}^{(l)}$.

######  Remark 6.6.

Another understanding of this classification of eigenvalues into
$\mathcal{J}_{1}$, $\mathcal{J}_{2},$ and $\mathcal{J}_{3}$ is provided by the
vulnerability of the corresponding substates. Substates in $\mathcal{J}_{1}$
are the most vulnerable to attack since the defender may not even be able to
identify the attacked set of sensors. Substates in $\mathcal{J}_{2}$ are
robust against attacks since attacked sensors can be easily determined. For
substates $\mathcal{J}_{3}$, the defender is able to identify the attacked
sensors, but this task requires a substantially higher computational effort.

In other words, in the view of the adversary, a wise attacking strategy is to
attack the substates corresponding to eigenvalues in $\mathcal{J}_{1}$, and it
should avoid attacking states in $\mathcal{J}_{2}$ since majority voting will
allow the defender to easily identify the compromised sensors.

###  6.5. Example - Continued

In this subsection we continue the example in Section 2 and Section 5 and show
how to classify each subsystem under the assumption that the adversary can
attack at most $s=1$ sensor. We recall that $V^{1},V^{2},V^{3}$ are the
eigenspaces corresponding to eigenvalues 1, 2, and 3, respectively. Also,
after decomposition, we have
$\mathbf{A}^{(j)}=\mathbf{P}_{j}\mathbf{A}|_{V^{j}}$ as well as
$\mathcal{O}_{i}^{j}=\widetilde{\mathbf{P}}_{i}^{j}\mathcal{O}_{i}|_{V^{j}}$
for $i=1,2,3,4$ and $j=1,2,3.$

We first claim that $\lambda_{3}=3$ belongs to $\mathcal{J}_{1}$. To see why
this is true, we remove $2s=2$ sensors, sensor 1 and sensor 4, and explicitly
compute $\mathcal{O}_{2}^{3}$ and $\mathcal{O}_{3}^{3}$. We have:

$\mathcal{O}_{2}=\begin{bmatrix}2&3&\phantom{-}1&-1\\\ 3&4&\phantom{-}0&-1\\\
5&6&-2&-1\\\
9&10&-6&-1\end{bmatrix},\mathcal{O}_{3}=\begin{bmatrix}2&2&\phantom{-}0&\phantom{-}0\\\
3&3&-1&\phantom{-}0\\\ 5&5&-3&-0\\\ 9&9&-7&\phantom{-}0\end{bmatrix},$

and $\mathcal{O}_{2}(V^{3})=\mathcal{O}_{3}(V^{3})=\\{0\\}$ which yields
$(\widetilde{\mathbf{P}}_{2}^{3}\mathcal{O}_{2})\mathbf{x}^{\prime}_{3}=0$ and
$(\widetilde{\mathbf{P}}_{3}^{3}\mathcal{O}_{3})\mathbf{x}^{\prime\prime}_{3}=0$
for any $\mathbf{x}^{\prime}_{3}$ and $\mathbf{x}^{\prime\prime}_{3}$ in
$V^{3}$. Therefore, we have $\mathcal{O}_{2}^{3}=\mathcal{O}_{3}^{3}=0.$ By
the definition of sparse observability, we have
$\mathrm{ker}~{}\mathcal{O}_{\\{2,3\\}}^{3}=V^{3}$ and hence the subsystems
corresponding to eigenvalue $3$ are not $2s-$sparse observable. Also, a
similar analysis reveals that subsystems corresponding to eigenvalues
$\lambda_{1}$ and $\lambda_{2}$ are both $2s-$sparse observable, hence
$1\notin\mathcal{J}_{1}$ and $2\notin\mathcal{J}_{1}$.

Next we argue that $\lambda_{2}=2$ belongs to $\mathcal{J}_{2}$. To see why
this is true, we first recall that
$\mathbf{A}^{(2)}=\mathbf{P}_{2}\mathbf{A}|_{V^{2}}$,
$\mathbf{I}_{4}^{(2)}=\mathbf{I}_{4}|_{V^{2}}$,
$\mathbf{C}_{i}^{2}=\mathbf{C}_{i}|_{V^{2}}$, and then check that for sensor
1, the matrix:

$\begin{bmatrix}\mathbf{A}^{(2)}-2\mathbf{I}_{4}^{(2)}\\\
\mathbf{C}_{1}^{2}\end{bmatrix}=\frac{1}{2}\left.\begin{bmatrix}0&\phantom{-}0&\phantom{-}0&0\\\
1&-2&-2&2\\\ 1&-2&-2&2\\\ 0&\phantom{-}0&\phantom{-}0&0\\\
6&\phantom{-}4&\phantom{-}0&4\end{bmatrix}\right|_{V^{2}},$

defines an injective map. We also run the same check on sensor $2,3,$ and $4$
to conclude that eigenvalue $\lambda_{2}$ is observable by all $4$ sensors.
Hence the subsystems corresponding to $\lambda_{2}$ are $2s-$eigenvalue
observable. Proceeding in the same fashion we conclude that subsystems
corresponding to eigenvalue $\lambda_{1}$ are not $2s-$eigenvalue observable.
Therefore, the eigenvalue $\lambda_{1}=1$ belongs to $\mathcal{J}_{3}$.

In summary, the substates in $V^{3}$ cannot be securely reconstructed, the
substates in $V^{1}$ can be securely reconstructed in the presence of at most
$1$ attacked sensor, and the substates in $V^{2}$ can be securely
reconstructed and the reconstruction can be done efficiently.

##  7\. COMPLEXITY OF CHECKING SPARSE OBSERVABILITY

In the previous two sections, we studied the complexity of the SSR problem,
and in particular, identified instances of the problem that can be solved in
polynomial time. Recall that under at most $s$ sensor attacks on the system
(3.1)-(3.2), $2s$-sparse observability is necessary and sufficient for the SSR
problem to yield a unique solution, namely the true initial state vector
$\mathbf{x}[0]$. Given this result, we now take a step back and ask: what is
the complexity of deciding whether a given system is $2s$-sparse observable?
As explained in Section 3.3, the above question is highly relevant since it
aims to identify the maximum number of sensor attacks that can be tolerated by
a given system of the form (3.1)-(3.2). In what follows, we show that
determining the sparse-observability index (see Definition 1) of a system is
computationally hard; we will focus on the case of scalar-valued sensors
throughout, as it suffices to establish the computational complexity of the
problem.

######  Problem 3.

($r$-sparse observability)
Input: A matrix $\mathbf{A}\in\mathbb{Q}^{n\times n}$, a matrix
$\mathbf{C}\in\mathbb{Q}^{p\times n}$ and a positive integer $r$.
Question: Is the pair $(\mathbf{A},\mathbf{C})$ $r$-sparse observable?

Note that if the answer to an instance of the $r$-sparse observability problem
is “no”, then there is a simple proof: one can provide a set of $r$ rows of
$\mathbf{C}$ that, if removed, result in a system that is no longer
observable. However, it is not clear whether there is a similarly simple proof
for “yes” instances. Thus, the $r$-sparse observability problem is in the
class coNP.222See, e.g., [36] for additional details on the complexity classes
NP and coNP.

The complement of a decision problem is the problem obtained by switching the
“yes” and “no” answers to all instances of that problem. If a problem is in
the class coNP, then its complement is in the class NP, and vice versa.

We will show that the $r$-sparse observability problem is coNP-hard by showing
that its complement is NP-hard. Specifically, we define the following
complement problem to $r$-sparse observability.

######  Problem 4.

($r$-sparse unobservability)
Input:  A matrix $\mathbf{A}\in\mathbb{Q}^{n\times n}$, a matrix
$\mathbf{C}\in\mathbb{Q}^{p\times n}$ and a positive integer $r$.
Question: Is there a set of $r$ rows that can be removed from $\mathbf{C}$ in
order to yield a matrix $\bar{\mathbf{C}}$ such that
$(\mathbf{A},\bar{\mathbf{C}})$ is unobservable?

Note that the answer to an instance of $r$-sparse unobservability is “yes” if
and only if the answer to the corresponding instance of $r$-sparse
observability is “no” and vice versa. Further note that $r$-sparse
unobservability is in the class NP.

We show that $r$-sparse unobservability is NP-complete by providing a
reduction from the following Linear Degeneracy problem. This problem was shown
to be NP-complete in [37].

######  Problem 5.

(Linear Degeneracy [37])
Input: A full column rank matrix $\mathbf{F}\in\mathbb{Q}^{p\times n}$.
Question: Does $\mathbf{F}$ contain a degenerate (i.e., noninvertible)
$n\times n$ submatrix?

In other words, the linear degeneracy problem asks whether it is possible to
remove $p-n$ rows from matrix $\mathbf{F}$ so that the resulting (square)
matrix is not full rank. We are now ready to prove the following result.

######  Theorem 7.1.

The $r$-sparse unobservability problem is NP-complete. Thus, the $r$-sparse
observability problem is coNP-complete.

###### Proof.

Given an instance of the linear degeneracy problem (with matrix
$\mathbf{F}\in\mathbb{Q}^{p\times n}$), we construct an instance of the
$r$-sparse unobservability problem as follows: set
$\mathbf{A}=\mathbf{I}_{n}$, $\mathbf{C}=\mathbf{F}$, and $r=p-n$.

We now show that the answer to the constructed instance of $r$-sparse
unobservability is “yes” if and only if the answer to the given instance of
linear degeneracy is “yes”.

First, suppose that the answer to the constructed instance of $r$-sparse
unobservability is “yes.” Then there exists a set of $r$ rows of $\mathbf{C}$
that can be removed such that the remaining rows are not sufficient to yield
observability. However, since $\mathbf{A}=\mathbf{I}_{n}$, the above implies
that there is a set of $r$ rows of $\mathbf{C}$ that can be removed such that
the remaining rows are not full column rank. Since $\mathbf{C}=\mathbf{F}$ and
$r=p-n$, this means that there is an $n\times n$ submatrix of $\mathbf{F}$
that loses rank, and thus the answer to the linear degeneracy problem is
“yes.”

Next, we show that if the answer to the given instance of linear degeneracy is
“yes,” then the answer to the constructed instance of $r$-sparse
unobservability is “yes.” We will do this by showing the contrapositive: if
the answer to the constructed instance of $r$-sparse unobservability is “no”,
then the answer to the given instance of linear degeneracy is “no.” Suppose
the answer to the constructed instance of $r$-sparse unobservability is “no.”
Then, by definition, the pair $(\mathbf{A},\mathbf{C})$ is observable even
after removing any arbitrary $r$ rows from $\mathbf{C}$. However, since
$\mathbf{A}=\mathbf{I}_{n}$, in order for the system to remain observable
after removing $r$ rows from $\mathbf{C}$, it must be the case that the
remaining rows of $\mathbf{C}$ have full column rank. Thus, if the answer to
the constructed instance of $r$-sparse unobserability is “no”, then
$\mathbf{C}$ has full column rank after removing any arbitrary $r=p-n$ rows.
This means that every $n\times n$ submatrix of $\mathbf{C}$ is invertible.
Since $\mathbf{C}=\mathbf{F}$, the answer to the given instance of linear
degeneracy is “no” (i.e., there is no $n\times n$ submatrix of $\mathbf{F}$
that is degenerate).

Thus, we have shown that the answer to the constructed instance of $r$-sparse
unobservability is “yes” if and only if the answer to the given instance of
linear degeneracy is “yes.” Since linear degeneracy is NP-complete, so is
$r$-sparse unobservability.

Finally, since $r$-sparse observability is the complement of $r$-sparse
unobservability (and since $r$-sparse observability is in coNP), we have that
$r$-sparse observability is coNP-complete. ∎

######  Remark 7.2.

In [29], certain necessary conditions were presented for estimating the state
of a plant despite attacks in a distributed setting, i.e., where measurements
of the plant are dispersed over a network of sensors. Specifically, these
conditions impose certain requirements on the observation model (in addition
to requirements on the communication structure), the complexity of checking
which was left open. Interestingly, Theorem 7.1 resolves this question, and
establishes that checking the necessary conditions in [29] is computationally
hard; since the focus of our paper is on centralized systems, we do not
present details of this result here.

##  8\. CONNECTIONS BETWEEN SPARSE OBSERVABILITY AND EIGENVALUE OBSERVABILITY

$2s$-sparse observability $2s$-eigenvalue observability
$g_{\mathbf{A}}(\lambda)=1,\forall\lambda\in sp(\mathbf{A})$ Figure 1. Figure
illustrating the hierarchy of relationships between different notions of
observability.

In Sections 4 and 7, we showed that the SSR problem and the problem of
determining the sparse observability index of a system are each
computationally hard. At the same time, Section 6 gave us the positive result
that certain instances of the SSR problem can be efficiently solved. In line
with this finding, we are now motivated to ask: Can the sparse observability
index of a system be computed in polynomial time for certain specific
instances? In this section, we show that this is indeed the case by
identifying instances of the problem where the notions of sparse observability
and eigenvalue observability coincide. Given that the eigenvalue observability
index of a system can always be computed in polynomial time based on simple
rank tests, an equivalence between the two notions of observability
immediately yields instances of the problem where the sparse observability
index of the system can also be computed in polynomial time. With this in
mind, in this section we will prove each of the implications indicated in
Figure 1. We begin with the following simple result.

######  Proposition 3.

Consider the linear system (3.1)-(3.2), and suppose its eigenvalue
observability index is $2s$. Then, the pair $(\mathbf{A},\mathbf{C})$ is at
least $2s$-sparse observable.

###### Proof.

Consider any subset of sensors $\mathcal{F}\subset\mathcal{V}$, such that
$|\mathcal{F}|\leq 2s$. To establish that the pair $(\mathbf{A},\mathbf{C})$
is at least $2s$-sparse observable, we need to show that the pair
$(\mathbf{A},\mathbf{C}_{\mathcal{V}\setminus\mathcal{F}})$ is observable.
Based on the PBH test, this amounts to checking that each eigenvalue
$\lambda\in sp(\mathbf{A})$ is observable w.r.t. the observation matrix
$\mathbf{C}_{\mathcal{V}\setminus\mathcal{F}}$. Let $S_{\lambda}$ represent
the set of sensors w.r.t. which $\lambda$ is observable. A sufficient
condition for this to happen is
$|(\mathcal{V}\setminus\mathcal{F})\cap\mathcal{S}_{\lambda}|\geq 1$, which is
indeed true given that an eigenvalue observability index of $2s$ implies
$|\mathcal{S}_{\lambda}|\geq(2f+1),\forall\lambda\in sp(\mathbf{A})$, and the
fact that $|\mathcal{F}|\leq 2s$. ∎

To see that the reverse implication does not hold in general, consider the
following example.

######  Example 1.

Consider an LTI system of the form (3.1)-(3.2) monitored by 6 sensors, with
parameters as follows:

(8.1) $\mathbf{A}=\begin{bmatrix}\lambda&0\\\
0&\lambda\end{bmatrix},\mathbf{C}_{i}=\begin{cases}\begin{bmatrix}1&0\end{bmatrix},&\text{if
}i\in\\{1,2,3\\},\\\ \\\ \begin{bmatrix}0&1\end{bmatrix},&\text{if
}i\in\\{4,5,6\\}.\end{cases}$

Here $\lambda\in\mathbb{R},|\lambda|\geq 1$. Suppose $s=1$. Then, the removal
of at most $2$ sensors will ensure that at least one sensor from each of the
sets $\\{1,2,3\\}$ and $\\{4,5,6\\}$ remains unattacked; given the measurement
model in (8.1), this is sufficient to preserve observability w.r.t. the
remaining sensors. In other words, the system is 2-sparse observable. However,
it is easy to verify that the eigenvalue $\lambda$ is not observable w.r.t.
any sensor.

In view of Proposition 3 and Example 8.1, we conclude that $2s$-sparse
observability of a system is in general less restrictive than the condition
that the eigenvalue observability index of the system is $2s$. In what
follows, we establish that the two aforementioned notions coincide when
additional structure is imposed on the spectrum of $\mathbf{A}$.

######  Proposition 4.

Consider the linear system model given by (3.1)-(3.2), and suppose $\lambda\in
sp(\mathbf{A})$ has geometric multiplicity $1$. Consider any non-empty subset
of sensors
$\mathcal{S}=\\{i_{1},i_{2},\ldots,i_{|\mathcal{S}|}\\}\subseteq\mathcal{V}$.
Then, the eigenvalue $\lambda$ is observable w.r.t. the pair
$(\mathbf{A},\mathbf{C}_{\mathcal{S}})$ if and only if there exists a sensor
$i_{p}\in\mathcal{S}$ such that $\lambda$ is observable w.r.t. sensor $i_{p}$,
i.e., $\lambda$ is observable w.r.t. the pair
$(\mathbf{A},\mathbf{C}_{i_{p}})$.

###### Proof.

Consider a similarity transformation that maps $\mathbf{A}$ to its Jordan
canonical form $\mathbf{J}$. Let this transformation map
$\mathbf{C}_{\mathcal{S}}$ to $\bar{\mathbf{C}}_{\mathcal{S}}$, and
${\mathbf{C}}_{i_{j}}$ to $\bar{\mathbf{C}}_{i_{j}}$, for each
$i_{j}\in\mathcal{S}$. Since $\lambda$ has geometric multiplicity $1$, there
exists a single Jordan block corresponding to $\lambda$ in $\mathbf{J}$. Let
this Jordan block be denoted $\mathbf{J}_{\lambda}$. Without loss of
generality, suppose $\mathbf{J}$ is of the following form:

(8.2) $\mathbf{J}=\begin{bmatrix}\mathbf{J}_{\lambda}&\mathbf{0}\\\
\mathbf{0}&\bar{\mathbf{J}}\end{bmatrix},$

where $\bar{\mathbf{J}}$ is the collection of the Jordan blocks corresponding
to eigenvalues in $sp(\mathbf{A})\backslash\\{\lambda\\}$. Based on the PBH
test, $\lambda$ is observable w.r.t. the pair
$(\mathbf{J},\bar{\mathbf{C}}_{\mathcal{S}})$ if and only if the following
condition holds:

(8.3) $\textrm{rank}\begin{bmatrix}\mathbf{J}-\lambda\mathbf{I}_{n}\\\
\bar{\mathbf{C}}_{\mathcal{S}}\end{bmatrix}=n.$

Given the structure of $\mathbf{J}$ in (8.2), and the fact that $\lambda$ has
geometric multiplicity $1$, it is easy to see that (8.3) holds if and only if
there is at least one non-zero entry in the first column of
$\bar{\mathbf{C}}_{\mathcal{S}}$. However, the preceding condition holds if
and only if there exists some sensor $i_{p}\in\mathcal{S}$ with at least one
non-zero entry in the first column of $\bar{\mathbf{C}}_{i_{p}}$; the latter
is precisely the condition for observability of $\lambda$ w.r.t. the sensor
$i_{p}$, given that $g_{\mathbf{A}}(\lambda)=1.$ To complete the proof, it
suffices to notice that a similarity transformation preserves the
observability of an eigenvalue. ∎

We now make use of the previous result to establish an equivalence between
sparse observability and eigenvalue observability.

######  Proposition 5.

Consider the linear system model (3.1)-(3.2), and suppose every eigenvalue of
$\mathbf{A}$ has geometric multiplicity $1$. Then, the pair
$(\mathbf{A},\mathbf{C})$ is $2s$-sparse observable if and only if the
eigenvalue observability of the system is $2s$.

###### Proof.

For necessity, we proceed via contradiction. Suppose the pair
$(\mathbf{A},\mathbf{C})$ is $2s$-sparse observable, but there exists some
$\lambda\in sp(\mathbf{A})$ that is observable w.r.t. at most $2s$ distinct
sensors. Recall that the set of sensors w.r.t. which $\lambda$ is observable
is denoted $\mathcal{S}_{\lambda}$. Based on our hypothesis,
$|\mathcal{S}_{\lambda}|\leq 2s$. Suppose $|\mathcal{S}_{\lambda}|=2s$ (since
an identical argument can be sketched when $|\mathcal{S}_{\lambda}|<2s$).
Since $(\mathbf{A},\mathbf{C})$ is $2s$-sparse observable, the pair
$(\mathbf{A},\mathbf{C}_{\mathcal{V}\setminus\mathcal{S}_{\lambda}})$ is
observable. However, based on Proposition 4, this requires $\lambda$ to be
observable w.r.t. at least one sensor in
$\mathcal{V}\setminus\mathcal{S}_{\lambda}$, leading to the desired
contradiction. This completes the proof of necessity. For sufficiency, note
from Proposition 3 that the pair $(\mathbf{A},\mathbf{C})$ is at least
$2s$-sparse observable whenever its eigenvalue observability index is $2s$;
the fact that the observability index is no more than $2s$ follows from the
additional assumption on the geometric multiplicity of eigenvalues, and
arguments similar to those used for establishing necessity. ∎

It directly follows from the definition of eigenvalue observability that the
eigenvalue observability index of a system can be computed in polynomial time.
Hence, we have the following corollaries of Proposition 5.

######  Corollary 2.

When all the eigenvalues of the matrix $\mathbf{A}$ have geometric
multiplicity 1, the sparse observability index of the system can be computed
in polynomial time.

######  Corollary 3.

For a 2s-sparse observable system (3.1)-(3.2), when all the eigenvalues of the
matrix $\mathbf{A}$ have geometric multiplicity 1, the SSR problem can be
solved in polynomial time.

###### Proof.

It is shown in Proposition 5 that under the unitary geometric multiplicity
assumption, a $2s$-sparse observable system is also $2s$-eigenvalue
observable. Thus, such a system satisfies the hypotheses in the statement of
Theorem 1, and we immediately obtain the existence of a polynomial-time
solution for the SSR problem. ∎

##  9\. CONCLUSION

In this paper, we showed that when the eigenvalues of the system matrix
$\mathbf{A}$ have unitary geometric multiplicity, the SSR problem is tractable
since both checking the sparse observability (see Corollary 2) as well as
solving the SSR problem (see Theorem 1) can be performed in polynomial time.
When at least one of the eigenvalues has geometric multiplicity greater than
one, we can still compute the eigenvalue observability index and, if it is at
least $2s$, solve the SSR problem in polynomial time if at most $s$ sensors
are attacked. However, in this case, eigenvalue observability is no longer
necessary for the SSR problem to be solvable. Since even checking sparse
observability is coNP-complete, we conjecture that the SSR problem may be
intractable in this case. The authors are currently investigating this
conjecture. However, even in this case, the computational complexity of
solving the SSR problem can be reduced, when the system matrix $\mathbf{A}$
has at least 2 distinct eigenvalues.

##  10\. ACKNOWLEDGMENTS

Shreyas Sundaram thanks Lintao Ye for helpful discussions pertaining to the
Linear Degeneracy problem.

## References

  * [1] Alvaro A Cárdenas, Saurabh Amin, and Shankar Sastry.  Research challenges for the security of control systems.  In HotSec, 2008.
  * [2] Special issue on secure control of cyber physical systems.  4, 2017.
  * [3] Jairo Giraldo, David Urbina, Alvaro Cardenas, Junia Valente, Mustafa Faisal, Justin Ruths, Nils Ole Tippenhauer, Henrik Sandberg, and Richard Candell.  A survey of physics-based attack detection in cyber-physical systems.  ACM Computing Surveys (CSUR), 51(4):1–36, 2018.
  * [4] Ralph Langner.  Stuxnet: Dissecting a cyberwarfare weapon.  IEEE Security & Privacy, 9(3):49–51, 2011.
  * [5] Saurabh Amin, Xavier Litrico, S Shankar Sastry, and Alexandre M Bayen.  Stealthy deception attacks on water scada systems.  In Proc. of the 13th ACM Int. Conference on Hybrid Systems: Computation and Control, pages 161–170, 2010.
  * [6] Henrik Sandberg, André Teixeira, and Karl H Johansson.  On security indices for state estimators in power networks.  In First Workshop on Secure Control Systems, 2010.
  * [7] Abhishek Gupta, Cédric Langbort, and Tamer Başar.  Optimal control in the presence of an intelligent jammer with limited actions.  In Proc. of the 49th IEEE Conference on Decision and Control, pages 1096–1101, 2010.
  * [8] Roy S Smith.  A decoupled feedback structure for covertly appropriating networked control systems.  IFAC Proceedings Volumes, 44(1):90–95, 2011.
  * [9] Roy S Smith.  Covert misappropriation of networked control systems: Presenting a feedback structure.  IEEE Control Systems Magazine, 35(1):82–92, 2015.
  * [10] Fabio Pasqualetti, Florian Dörfler, and Francesco Bullo.  Cyber-physical security via geometric control: Distributed monitoring and malicious attacks.  Proc. of the 51st IEEE Conference on Decision and Control, pages 3418–3425, 2012.
  * [11] Fabio Pasqualetti, Florian Dörfler, and Francesco Bullo.  Attack detection and identification in cyber-physical systems.  IEEE Transactions on Automatic Control, 58(11):2715–2729, 2013\.
  * [12] Shreyas Sundaram and Christoforos N Hadjicostis.  Distributed function calculation via linear iterative strategies in the presence of malicious agents.  IEEE Transactions on Automatic Control, 56(7):1495–1508, 2010.
  * [13] Hamza Fawzi, Paulo Tabuada, and Suhas Diggavi.  Secure state-estimation for dynamical systems under active adversaries.  In Proc. of the 49th Annual Allerton Conference on Communication, Control, and Computing, pages 337–344, 2011.
  * [14] Hamza Fawzi, Paulo Tabuada, and Suhas Diggavi.  Secure estimation and control for cyber-physical systems under adversarial attacks.  IEEE Transactions on Automatic control, 59(6):1454–1467, 2014.
  * [15] Michelle S Chong, Masashi Wakaiki, and Joao P Hespanha.  Observability of linear systems under adversarial attacks.  In Proc. of the American Control Conference, pages 2439–2444. IEEE, 2015.
  * [16] An-Yang Lu and Guang-Hong Yang.  Secure state estimation for cyber-physical systems under sparse sensor attacks via a switched Luenberger observer.  Information sciences, 417:454–464, 2017.
  * [17] Sze Zheng Yong, Ming Qing Foo, and Emilio Frazzoli.  Robust and resilient estimation for cyber-physical systems under adversarial attacks.  In Proc. of the American Control Conference, pages 308–315. IEEE, 2016.
  * [18] Yasser Shoukry and Paulo Tabuada.  Event-triggered state observers for sparse sensor noise/attacks.  IEEE Transactions on Automatic Control, 61(8):2079–2091, 2015.
  * [19] Yasser Shoukry, Pierluigi Nuzzo, Alberto L Sangiovanni-Vincentelli, Sanjit A Seshia, George J Pappas, and Paulo Tabuada.  Smc: Satisfiability modulo convex programming.  Proc. of the IEEE, 106(9):1655–1679, 2018.
  * [20] Ashish Tiwari, Bruno Dutertre, Dejan Jovanović, Thomas de Candia, Patrick D Lincoln, John Rushby, Dorsa Sadigh, and Sanjit Seshia.  Safety envelope for security.  In Proc. of the 3rd International Conference on High Confidence Networked Systems, pages 85–94. ACM, 2014.
  * [21] Yuan Chen, Soummya Kar, and Jose MF Moura.  Resilient distributed estimation through adversary detection.  IEEE Transactions on Signal Processing, 66(9):2455–2469, 2018.
  * [22] Lili Su and Shahin Shahrampour.  Finite-time guarantees for byzantine-resilient distributed state estimation with noisy measurements.  IEEE Transactions on Automatic Control, 2019.
  * [23] Yuan Chen, Soummya Kar, and José MF Moura.  Topology free resilient distributed estimation.  arXiv: 1812.08902, 2018.
  * [24] Heath J LeBlanc, Haotian Zhang, Xenofon Koutsoukos, and Shreyas Sundaram.  Resilient asymptotic consensus in robust networks.  IEEE Journal on Selected Areas in Communications, 31(4):766–781, 2013.
  * [25] Heath J LeBlanc, Haotian Zhang, Shreyas Sundaram, and Xenofon Koutsoukos.  Resilient continuous-time consensus in fractional robust networks.  In Proc. of the American Control Conference, pages 1237–1242. IEEE, 2013.
  * [26] Lewis Tseng and Nitin H Vaidya.  Fault-tolerant consensus in directed graphs.  In Proc. of the 2015 ACM Symposium on Principles of Distributed Computing, pages 451–460, 2015.
  * [27] Mohammad Deghat, Valery Ugrinovskii, Iman Shames, and Cedric Langbort.  Detection and mitigation of biasing attacks on distributed estimation networks.  Automatica, 99:369–381, 2019.
  * [28] Aritra Mitra and Shreyas Sundaram.  Secure distributed observers for a class of linear time invariant systems in the presence of Byzantine adversaries.  In Proc. of the 55th IEEE Conference on Decision and Control, pages 2709–2714, 2016.
  * [29] Aritra Mitra and Shreyas Sundaram.  Byzantine-resilient distributed observers for LTI systems.  Automatica, 108:108487, 2019.
  * [30] Chi-Tsong Chen.  Linear system theory and design.  Oxford University Press, Inc., 1998.
  * [31] Aritra Mitra and Shreyas Sundaram.  Distributed observers for LTI systems.  IEEE Transactions on Automatic Control, 63(11):3689–3704, 2018\.
  * [32] Yanwen Mao, Aritra Mitra, Shreyas Sundaram, and Paulo Tabuada.  When is the secure state-reconstruction problem hard?  In Proc. of the 58th IEEE Conference on Decision and Control, pages 5368–5373. IEEE, 2019.
  * [33] Emmanuel J Candes and Terence Tao.  Decoding by linear programming.  IEEE Transactions on Information Theory, 51(12):4203–4215, 2005\.
  * [34] Alan J. Laub.  Matrix Analysis for Scientists and Engineers.  SIAM, 2004.
  * [35] Balas K. Natarajan.  Sparse approximate solutions to linear systems.  SIAM journal on computing, 24(2):227–234, 1995.
  * [36] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein.  Introduction to algorithms.  MIT press, 2009.
  * [37] Leonid Khachiyan.  On the complexity of approximating extremal determinants in matrices.  Journal of Complexity, 11(1):138–153, 1995.