{'fraction_non_alphanumeric': 0.04438609014888843, 'fraction_numerical': 0.011268611054456455, 'mean_word_length': 3.8642113095238093, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Decentralized Secure State-Tracking in Multi-Agent Systems

This paper addresses the problem of decentralized state-tracking in the presence of sensor attacks. We consider a network of nodes where each node has the objective of tracking the state of a linear dynamical system based on its measurements and messages exchanged with neighboring nodes notwithstanding some measurements being spoofed by an adversary. We propose a novel decentralized attack-resilient state-tracking algorithm based on the simple observation that a compressed version of all the network measurements suffices to reconstruct the state. This motivates a 2-step solution to the decentralized secure state-tracking problem: (1) each node tracks the compressed version of all the network measurements, and (2) each node asymptotically reconstructs the state from the output of step (1). We prove that, under mild technical assumptions, our algorithm enables each node to track the state of the linear system and thus solves the decentralized secure state-tracking problem.


Introduction
Over the past decade the topic of decentralized state-tracking has received considerable attention, due to the increasingly decentralized nature of complex systems such as traffic networks and power grids. In this problem, a group of nodes is required to collectively track the state of a linear dynamical system using measurements from their own sensors and messages exchanged with neighboring nodes via a communication network.
In the absence of attacks, the decentralized state-tracking problem has been well studied [1][2][3][4]. However, reports on cyber-physical systems attacks [5,6] remind us of how vulnerable these systems can be. Motivated by this consideration, in this paper we tackle a more challenging version of the decentralized state-tracking problem where some nodes are subject to sensor attacks spoofing its measurements. We refer to this problem as the Decentralized Secure State-Tracking (DSST) problem.
1.1. Related Work. Closely related to the DSST problem is the Secure State-Reconstruction (SSR) problem whose formal definition can be found in [7]. Roughly speaking, in the SSR problem a central server, which has access to all measurements, is asked to reconstruct the state of a linear system despite an attack on some sensors. A preliminary version of the SSR problem was first considered in [8], and rigorously defined in [9]. Moreover, the solvability of the SSR problem was settled in [9][10][11]. In particular, in [9] and [11] it is pointed out that in order to reconstruct the state in the presence of s attacked sensors, the linear system must remain observable Our solution of the DSST problem is based on the simple observation that instead of processing all measurements from all nodes in the network, a suitably compressed version of the measurements suffices for each node to reconstruct the state. In particular, in Section 6 we will show that reconstructing the state from compressed measurements can be formulated as a special case of the SSR problem and, hence, any algorithm that solves the most general case of the SSR problem can be used to solve the DSST problem. Therefore, a solution of the DSST problem is obtained provided each node can track the compressed version of the measurements. To achieve this goal, we draw inspiration from [24] and design an observer that provides each node with error-free tracking of the compressed measurements.
We make the following contributions in this paper: (1) We propose a necessary and sufficient condition for the DSST problem to be solvable. (2) We provide a solution to the most general case of the DSST problem. Compared with [18], our solution of the DSST problem does not require SD, and the tracking of the state is error-free. Compared with [20], we do no rely on unnecessary assumptions regarding system dynamics or network topology, and we adopt the widely-accepted setting where the communication rate equals the sampling rate. The major disadvantage of our algorithm is its computational complexity. Our algorithm is combinatorial in the most general case. Although our algorithm runs in polynomial time when SD holds, it still requires more computations than the algorithms proposed in [4] and [18]. Moreover, our solution of the DSST problem requires sufficiently fast sampling rates. We summarize the comparison 2 between our solution of the DSST problem and the solutions in [4], [18], and [20], in Table 1.
A preliminary version of this work [25] was accepted for publication at the 60-th IEEE Conference on Decision and Control.
1.3. Paper Organization. The organization of the paper is as follows. We introduce some preliminaries and notations in Section 2 which will be used in later sections. The decentralized secure state-tracking problem is formulated in Section 3, including all the assumptions we made. In Section 4 we discuss how to compress the measurements and state a result regarding the solvability of the DSST problem. Then in Section 5 we relate the DSST problem to the dynamic average consensus problem. We provide our solution to the DSST problem in Section 6. The paper concludes with Section 7.

Preliminaries and Notations
In this section we introduce the notions used throughout the paper.
2.1. Basic Notions. We denote by |S| the cardinality of a set S. For any two sets S and S ′ , the set subtraction S\S ′ is the set defined by S\S ′ = {s ∈ S|s / ∈ S ′ }. Let R, N, and C denote the set of real, natural, and complex numbers, respectively. A complex number z ∈ C is written in the form z = a + bi where i 2 = −1. The support of v ∈ R p , denoted by supp(v), is the set of indices of the non-zero entries of v, i.e., supp(v) = {i ∈ {1, 2, . . . , p}|v i = 0}. For a scalar s ∈ N we say v 2 Note that the computational complexity is measured by the number of additions and multiplications needed by the algorithm during one round of state update. Although the results in [18] are based on a continuous-time representation of the system, computational complexity is assessed for its discrete-time version.   [4], [18], [20], and this paper. is s−sparse if |supp(v)| ≤ s. Also, we define the all-ones vector 1 n = (1, 1, . . . , 1) T and I n to be the identity matrix of order n. When the dimension of the identity matrix is unambiguous, we will write I instead. Moreover, for any p ∈ N, we denote by E p = {e 1 , e 2 , . . . , e p } the standard basis of R p with e i ∈ R p being the vector with all entries equal to zero except the i-th entry which is 1.

Matrix Related Notions.
We denote by A ∈ R m×n a real matrix with m ∈ N rows and n ∈ N columns. We will also refer to matrices where only the number of rows or columns is specified using the notation A ∈ R m× * or A ∈ R * ×n .
For a real square matrix A, we denote by λ max (A) and λ min (A) the eigenvalue with the largest and smallest magnitude, respectively. Also, for a real matrix B, we denote by σ max (B) and σ min (B) the largest and smallest singular values of matrix B, respectively. The range of a real matrix A is denoted by R(A), and its kernel is denoted by ker(A). Moreover, we denote by A ⊗ B the Kronecker product of two real matrices A and B. Consider a set Q of indices and a matrix K, the matrix K Q is obtained by removing any row in K not indexed by Q.

Graph Related Notions.
Here we review some of the basic notions of graph theory. A weighted undirected graph G = (V, E, A) is a triple consisting of a set of vertices V = {v 1 , v 2 , . . . , v p } with cardinality p, a set of edges E ⊆ V × V, and a weighted adjacency matrix A ∈ R p×p which we will define in the coming paragraph. The set of neighbors of a vertex i ∈ V, denoted by N i = {j ∈ V|(i, j) ∈ E}, is the set of vertices that is connected to i by an edge. To clarify, we assume each vertex is not a neighbor of itself, i.e., (i, i) / ∈ E for any i. The weighted adjacency matrix A of the graph G is defined entry-wise. The entry in the i-th row and j-th column, a ij , satisfies a ij > 0 if (i, j) ∈ E and otherwise a ij = 0. Since the graph is undirected, a ij = a ji for any i, j ranging from 1 to p which results in A being a symmetric matrix. The degree matrix D ∈ R p×p of the graph G is a diagonal matrix with its i-th diagonal element defined by d ii = p j=1 a ij . The Laplacian matrix L of the graph G is defined by L = D − A, which is known to be symmetric, if the graph is undirected, positive semi-definite, and having span{1 p } as its kernel.

Problem Formulation and Key Idea
In this section we introduce the decentralized secure state-reconstruction problem.
3.1. System Model. We consider a linear time-invariant system monitored by a network of p nodes whose sensors are subject to attacks: where x[t] ∈ R n is the system state at time t ∈ N, y i [t] ∈ R is the measurement of node i where i ∈ P {1, 2, . . . , p}, which is assumed to be a scalar, and the matrices A, B, and C i have appropriate dimensions.
The vector e i [t] ∈ R models the attack on the sensor at node i (which we will refer to as sensor i for brevity). If sensor i is attacked by an adversary, then e i [t] can be arbitrary, otherwise, e i [t] remains zero for any t, and y i [t] = C i x[t] holds which means node i receives correct measurements from its sensor. We also assume that the adversary is omniscient, i.e., the adversary has knowledge about the system model, the algorithm being executed at each node and, for any time slot t, the adversary knows the system state x[t] and the measurements y i [t] from all nodes. The only assumption we make on the adversary is that it can only attack a fixed set of at most s ∈ N sensors. Note that this set of attacked sensors is unknown to any node in the network.
Collecting n consecutive measurements over time, the output of sensor i can be written in a more compact form: are obtained by stacking vertically over time the measurements of sensor i and the attack vector, respectively, and the matrix O i is the observability matrix of sensor i. These three matrices are defined by: . . .
In a similar way, we stack over nodes the measurements, the observability matrices, and the attack vectors, from which a more concise representation of the linear system is obtained: . . .
We also note that since the adversary can only attack at most s nodes, and since for an attack-free sensor i we have E i [t] = 0 for any t, the vector E[t] is sparse at any t. In the end, we define the matrices We assume that the communication between nodes in the network can be modeled by an undirected graph. Each node is modeled by a vertex i ∈ V, and a communication link from node i to node j is modeled by an edge (i, j) ∈ E from vertex i to j. Since we assume the graph is undirected, (i, j) ∈ E implies (j, i) ∈ E which shows that node j can also send messages to node i. Remark 1. Although the linear system (3) is modelled without inputs, we note that, all results in this paper can be conveniently extended to the case when the input is known to every node in the network.

Assumptions.
Here we list all the assumptions we use in this paper. Some of them have already been discussed when introducing the adversary model.    The Assumptions 1, 2, 3, and 4 are in line with the assumptions in [18] and [20] except that we also assume each node knows the C i matrices of all other nodes throughout the network. We also require the following assumptions: Assumption 5. All the measurements y i are scalars. Assumption 5 is not necessary but we adopt it in the context of this paper for brevity. The authors believe that, with slight modifications, any result or algorithm proposed in this paper can be extended to the case where Assumption 5 is dropped.
Whenever the discrete-time linear system (1) is the time discretization of an underlying continuous-time linear system: Assumption 6 can be interpreted as a requirement on the sampling time τ used to obtain (1) from (4). If τ is small enough, then A = eÃ τ can be made arbitrarily close to the identity matrix. In other words, by increasing the sampling rate, m can be made arbitrary close to 1 and n close to 0, and such a pair of m and n satisfies Assumption 6.
We also note that, Assumption 6 implies for any eigenvalue m + ni of A, the inequality (m − 1) 2 + n 2 < 1 holds.
3.3. The Decentralized Secure State-Tracking Problem. In this section we provide the definition of the decentralized secure state-tracking problem.
In plain words, to solve the DSST problem, each node i must maintain a state estimatex i [t] which converges asymptotically to the true state x[t]. We also refer to this property by saying thatx i [t] tracks x[t]. The rigorous definition of the DSST problem is as follows: Definition 1 (Decentralized Secure State-Tracking Problem). Consider a linear system subject to attacks (1) satisfying Assumptions 2-6 and a communication network satisfying Assumption 1. The decentralized secure state-tracking problem asks for an algorithm running at each node i ∈ P with measurements y i ∈ R and messages from neighboring nodes as its input, and such that its outputx i [t] satisfies: Remark 2. Differently from centralized SSR problem (see for example [7] for its definition), the DSST problem does not require each node to explicitly know which subset of nodes in the network is attacked. For the SSR problem, it has been argued in [12] that knowing the true state x[t] and knowing the set of attacked sensors is equivalent, while this is not the case in the DSST problem setting.

Remark 3.
In the DSST problem setting, it is possible to require all nodes, including attacked nodes and attack-free nodes, to maintain a state estimate which asymptotically tracks the system state x[t]. This follows from Assumption 1 which restricts the adversary to only alter sensor measurements. In particular, nodes with spoofed measurements are still able to correctly execute their algorithms. Therefore, the attacked nodes are still able reconstruct the state x[t] and may even determine that their own measurements have been altered.

Key Idea.
The key idea for solving the DSST problem is based on the simple observation that instead of having access to measurements of all the sensors, a compressed version (D ⊗ I n )Y of the measurements may suffice to reconstruct the state, where the compression matrix D ∈ R v×p reduces the measurements from R p to R v with v ≤ p. Compression is possible, in most cases, and thus v will be strictly smaller than p. We will elaborate on the feasible choices for a compression matrix D in Section 4.
Equipped with the observation that the compressed version of measurements (D ⊗ I n )Y suffices to reconstruct state, it is natural to ask: how can each node have access to the compressed measurements? We show how to reformulate this problem as a dynamic average consensus problem in Section 5 and an algorithm for each node to track (D ⊗ I n )Y is provided in Section 6.
Lastly, in Section 6 we show how to reconstruct the state x from the compressed measurements (D ⊗ I n )Y at each node. We will prove that by suitably introducing a slack variable, this problem can be reduced to an SSR problem. This observation implies that we may employ any algorithm for the SSR problem that does not require additional assumptions, even though the compression slightly changes the attack model. It then follows that, as each sensor's estimate of the compressed measurements converges, so does the state reconstructed from the estimated compressed measurements. These three steps provide a solution to the DSST problem.

Design of the Compression Matrix and Solvability of DSST
There are two considerations involved in the choice of the compression matrix D. On the one hand, in order to reduce communications and storage, we want the D matrix to have the least possible number of rows. On the other hand, the compressed measurements (D ⊗I n )Y must provide enough information for each node to correctly reconstruct the state. We start with the definition of sparse detectability with respect to a matrix, which is a generalization of sparse observability [10,11] as well as sparse detectability [26] but stronger, as we will very soon see.
In other words, if (A, C) is detectable, then for any two trajectories . This property will be used in the proof of Theorem 2.
Definition 3 (Sparse detectability [26]). The sparse detectability index of the system (1) is the largest integer k such that for any K ⊆ P satisfying |K| ≥ p − k the pair (A, C K ) is detectable. When the sparse detectability index is k, we say that system (1) is k-sparse detectable.
In plain words, if we remove any subset of at most s sensors and the remaining system represented by the pair (A, C K ) is still detectable, then we say that the original system is s-sparse detectable. We now present another perspective on sparse observability, paving the way for the definition of sparse detectability with respect to a matrix, which plays a critical role in our study. We first define the set: that we use in the following equivalent definition of sparse detectability: Definition 4 (Sparse detectability). The sparse detectability index of the system (1) is the largest integer k such that the pair (A, LC) is detectable for any L ∈ Q k . When the sparse detectability index is k, we say that system (1) is k-sparse detectable.
Intuitively, by left multiplying C by L we remove the measurements of a subset of s sensors without losing information from any remaining sensors. The equivalence between these two definitions of sparse detectability is trivial and, due to space limitations, we do not provide a proof. We proceed by introducing the new notion of sparse detectability with respect to a matrix: Definition 5 (Sparse detectability with respect to a matrix). Consider the system (1), a matrix D ∈ R v×p , and define the following set: The sparse detectability index of the system (1) with respect to D is the largest integer k such that the pair (A, LDC) is detectable for any L ∈ P k . When the sparse detectability index with respect to D is k, we say that system (1) is k-sparse detectable with respect to D.
Remark 4. We note that, sparse detectability with respect to I coincides with the definition of sparse detectability.
For later use, we formalize the contrapositive of Remark 4 in the next lemma. Lemma 1. Any pair (A, C) that fails to be s-sparse detectable is not s−sparse detectable with respect to any matrix of compatible dimensions.
Equipped with the definition of sparse observability with respect to a matrix, we are ready to present necessary conditions for the compressed measurements (D ⊗ I n )Y to carry enough information to reconstruct the state and thus solves the DSST problem. Proof. For the sake of contradiction, we assume that (A, C) is not 2s−sparse detectable with respect to D. By the definition of sparse detectability with respect to a matrix, there exist two state trajectoriesx   Lemma 2 shows that it is necessary to pick the compression matrix D such that the pair (A, C) is 2s-sparse detectable with respect to D, otherwise it is impossible to track the state from compressed measurements (D ⊗ I n )Y . Later in Lemma 7 we will see that this condition also suffices to solve the DSST problem. Anticipating the results in Section 6 we state here the main contribution of this paper, 2s-sparse detectability with respect to D is both necessary and sufficient to solve the DSST problem: Proof. Necessity comes easily from Lemma 2 by picking D = I p . Sufficiency follows from Lemma 7 in Section 6.

Reduction to Dynamic Average Consensus
One key step of our solution to the DSST problem is to have each node tracking the compressed measurements (D ⊗ I n )Y . To do this, we ask each node i to maintain an estimate vector where d ji is the entry at the j-th row and i-th column of D.
In this section, and in the one that follows, we focus on the problem of tracking (D 1 ⊗ I n )Y , where D 1 is the first row of D, which can also be written as i d 1i Y i , and the tracked value is stored in the block W 1 i . For technical reasons we will use 1 p i d 1i Y i , which serves the same purpose since by Assumption 3 the value of p is known to all nodes. Note that any algorithm that can track 1 p i d 1i Y i can be extended to track 1 p (D ⊗I n )Y but running v concurrent copies, each with a different set of weights {d ji }. We observe that this problem can be seen as an instance of the dynamic average consensus problem [21]. In brief, suppose that each agent in the network has a time-varying local reference signal φ i (t) : [0, ∞) → R n . The dynamic average consensus problem asks for an algorithm that allows individual agents to track the time-varying average of the reference signals, given by: In our problem setting, we pick the external input corresponding to ( and what we want to track is 1 In other words, we may adopt any algorithm that solves the dynamic average consensus algorithm thereby enabling all nodes to track (D ⊗ I n )Y .
However, in the setting of dynamic average consensus problem, no knowledge about reference signals φ i is assumed, whereas in our problem, for an attack-free node i, we have the following: This equality comes from the construction where α 1 , α 2 , . . . , α n−1 are the coefficients of the characteristic polynomial of A. This can be seen by nothing that whenever node i is attack free. Moreover, we note thatÂ is the controller form of A and has the same eigenvalues as A.
Remark 5. Since the state portion corresponding to the stable eigenvalues will decay to zero with the elapse of time, in the remainder of the paper we will only be focusing on the state portion corresponding to unstable eigenvalues.
Based on Equation (7), we define the following local sanity check: In practice, we ask all nodes in the network to constantly run the local sanity check. It is trivially seen that all attack-free nodes would pass the check at any time. On the other hand, if a node fails the local sanity check, then we immediately reach the conclusion that this node is under attack. Therefore, we assume that all the attack vectors e i corresponding to attacked nodes are constructed so that the resulting measurements Y i [t] pass the local sanity check, i.e., The purpose of the local sanity check is to force the dynamics of Y i to be governed by (7), including those from attacked nodes. We will exploit this additional knowledge of d 1i Y i (or φ 1 i ) to achieve better tracking results.

Solving the DSST Problem
We argued in Section 5 that the tracking of the compressed measurements (D ⊗ I n )Y is intrinsically identical to a dynamic average consensus problem. We extend the results in [24] from the scalar-input case to the vector case and present such extension in the discrete-time domain.
6.1. Tracking the Compressed Measurements. We ask each node to update its estimate of 1 p i d 1i Y i [t] according to: for some 0 < α < 1 and β > 0.
Before proving this theorem we present the following two lemmas that will be used in its proof. Proof. The matrix S T BS being symmetric implies it is diagonalizable and positive semi-definite since B is also positive semi-definite. Assume, for the sake of contradiction, that it is not positive definite. Then, there exists x = 0 ∈ R n such that x T S T BSx = 0. Since x T S T BSx = √ BSx 2 2 we conclude that √ BSx = 0, i.e., Sx ∈ ker(B) since any matrix B and its square root √ B have the same kernel, a contradiction with R(S) ∩ ker(B) = {0}.

Lemma 4. Consider a block matrix B =
A − I − 2k 2 I λ 2 I n −2k I k P λI n k I λI n A where A ∈ R n×n and λ is a non-zero eigenvalue of L. There always exist k I , k P ∈ R such that B is stable 4 if A satisfies Assumption 6 in Section 3.
To prove this result, we first invoke the following lemma: Proof. We will only prove the special case when r = 2 since the rest of the proof follows by an induction argument, which we omit for the sake of brevity.
We explicitly write out the matrix H: 4 We recall that a matrix is stable if and only if the magnitude of all its eigenvalues is strictly less than 1.
and compare with another matrixĤ: We observe thatĤ can be obtained from H by a similarity transformation:Ĥ = T −1 HT , where In other words, matrices H andĤ share the same set of eigenvalues. Moreover, we obtain thatĤ is a block diagonal matrix with both of its diagonal blocks a 1 b 1 c 1 d 1 and a 2 b 2 c 2 d 2 being stable. This showsĤ is a stable matrix, which finishes our proof.
With the help of Lemma (5) we are ready to prove that B can be made stable by properly choosing c and λ.
Proof of Lemma 4. We first find the Jordan decomposition of A. Let J = T −1 AT be the Jordan form of A, J is an upper-triangular matrix with entries a 1 , a 2 , . . . , a n on its diagonal. Instead of matrix B, we focus on the following matrix which has the same eigenvalues as B: Now we invoke Lemma (5) and obtain that B is stable if the matrix R(a, λ) = a − 1 − 2k 2 I λ 2 −2k P k I λ k I λ a is stable for any a ∈ {a 1 , a 2 , . . . , a n } being an eigenvalue of A and any λ being a non-zero eigenvalue of L. In the next step we compute the eigenvalues k 1 , k 2 of matrix R(a, λ): The eigenvalues of the matrix R(a, λ) are given by: Lastly, we provide a possible choice of λ and c such that for any aforementioned a and λ, both eigenvalues k 1 and k 2 are stable. We pick k P = 1 and k I = where we recall that λ max (L) is the largest eigenvalue of L. This choice leads to: . By Assumption 6 both k 1 and k 2 are stable 5 for any feasible choice of a and λ, which finishes our proof.
Instead of proving directly Theorem 2, for the sake of simplicity, we prove the convergence result for a broader class of systems in the form of: where k I , k P ∈ R, v, m, ϕ, η ∈ R a for some positive a ∈ N, F, G ∈ R a×a , F = F T is positive semi-definite, and I represents the identity matrix of order a.
We first show that tracking algorithms of the form of (9) can be decoupled into 2 sub-systems and then we analyze the convergence properties for each sub-system. To do this, we introduce a matrix R ∈ R a×dim(kerF ) such that R(R) = ker(F ). Moreover, we pick S ∈ R a×(a−dim(kerF )) such that the matrix R S ∈ R a×a is orthogonal.
We make the following three additional assumptions regarding matrices F and G: • Assumption 1: The external input ϕ[t] satisfies ϕ[t + 1] = Gϕ[t], where G has the following two properties: (1) All eigenvalues of G satisfy Assumption 6 in Section 3.
(2) The equations R T GS = 0 and S T GR = 0 hold. • Assumption 2: All eigenvalues of F coincide with the eigenvalues of L. • Assumption 3: The matrices F and G are simultaneously block diagonalizable and each block in G corresponds to an identity block (possibly scaled by a scalar λ i ) in F . In other words, there exists an invertible matrix P such that P −1 GP = diag{Λ 1 , . . . , Λ r } and P −1 F P = diag{λ 1 I s1 , . . . , λ r I sr } such that Λ i ∈ R si×si with i ranging from 1 to r.
Note that all the additional assumptions are introduced to prove the desired tracking property and any system of the form (8) automatically falls into the broader class of systems described in (9) and the additional Assumptions 1-3, as we will argue at the end of this section. We are now ready to present our decomposition result based on the change of coordinates (z 1 , z 2 ) = (R T , S T )v where z 1 describes the sum of local estimates and z 2 is the difference among local estimates. We see that if z 1 converges to R T ϕ and z 2 converges to 0, then all nodes reach the consensus ϕ which is the target of the tracking algorithm. Proposition 1. The dynamical system in (9) can be decoupled into the following two sub-systems if it satisfies additional Assumption 1: and: where , which in turn means v = R S z, m = R S g, and η = R S f . By substituting these changes of coordinates into (9) and also left multiplying R S T on both sides of Equation (9) we obtain: Recall that R T F = 0, F R = 0, by additional Assumption 1 we have R T GS = 0 and S T GR = 0, and by construction R T S = 0, after some manipulations we obtain: as desired.
The following proposition shows that z 1 converges to R T ϕ as desired.
, we have the following sequence of equations: where the fourth step comes from: since R T GS = 0 by additional Assumption 1, and by construction of R we have R T RR T = R T . Finally, we show that the all eigenvalues of R T (G − I)R are stable, in other words, their magnitudes are strictly less than 1. To do this, we first note that if λ ′ = m − 1 + ni is an eigenvalue of G − I, then λ = m + ni must be an eigenvalue of of G. By additional Assumption 3 and Assumption 6, for any λ = m + ni of G, we have λ ′ 2 2 = (m − 1) 2 + n 2 < 1, which shows that all eigenvalues λ ′ of G − I are stable.
Then we resort to the following similarity transformation: which shows that the eigenvalues of R T (G − I)R are a subset of eigenvalues of G − I. Since all the eigenvalues of G − I are stable, all eigenvalues of R T (G − I)R are also stable and henceẑ 1 converges to 0 exponentially fast, or z 1 converges to R T ϕ exponentially fast.
Similarly, we prove that z 2 converges to 0 in the following proposition.
Proof. By substituting f 2 by k P g 2 + k I S T F Sz 2 we obtain the following dynamics: where G ′ = S T GS and F ′ = S T F S. It is simple to see that, if B is stable, for any two solutions w and w ′ of (17), we have lim In other words, if we can prove: 1. there exists a function g 2 [t] : R → R a−dim(kerF ) such that (0,ĝ 2 ) is a solution of (17), and 2. the matrix B is Hurwitz, then the proposition is proved. First we prove that (0,ĝ 2 [t]) is the solution of (17) for someĝ 2 [t]. By substituting z 2 = 0 into (17) we obtain: By Lemma 3 and the construction of S we obtain that F ′ is an invertible matrix and hence (ẑ 2 = 0,ĝ is a feasible solution. To prove this, we show that if the first equality in (17) holds at time t, then it will also hold at time t + 1. Then a simple induction can be conducted and the proof could thus be obtained. We check that: where in steps (c)(e)(h) we repeatedly used the inequalities S T GSS T = S T G and S T F SS T = S T F which could be obtained by following a similar argument as in the proof of Proposition 2, and step (d) is true since by additional Assumption 2 matrices F and G commute. This finishes the proof that (0,ĝ 2 (t)) is a solution of Equation (17). We now prove that B can be made stable by suitably choosing k I and k P . First of all, we show that G ′ = S T GS and F ′ = S T F S are also simultaneously block diagonalizable and each pair of corresponding blocks has the property described in additional Assumption 2. To see why this is true, consider the invertible matrix P ′ = R T S T P . We observe that P ′ simultaneously block-diagonalizes R T S T G RS and R T S T F RS if P simultaneously block-diagonalizes F and G. Moreover, since R T GS = 0 and S T GR = 0, both R T S T G RS and R T S T F RS are block diagonal matrices which yields that P ′ must also be a block diagonal matrix, with its bottomright block P 2 at the size of S T GS simultaneously diagonalizing S T GS and S T F S.
We then resort to the matrix P 2 to continue our proof. We consider the following similarity transformation: under which the eigenvalues of B are invariant. Simple computations show that . . , k I λ r I}, B 12 = diag{−2k P k I λ l I, . . . , −2k P k I λ r I}, and B 22 = diag{Λ l , . . . , Λ r } for some l < r. The block diagonal structure of each block in B ′ yields the fact that the eigenvalues of both B ′ and B are the eigenvalues of the smaller matrices: where any eigenvalue of any Λ i is an eigenvalue of G, and λ j > 0 is a non-zero eigenvalue of F . Here we invoke Lemma 4 and conclude that if the matrix G satisfy the same constraint on its eigenvalues in Assumption 6, and λ being an eigenvalue of S T LS, both of which are true by additional Assumption (2), then there exists a universal choice of k I and k P such that for any feasible choice of λ, the matrix B is stable.
In conclusion, by properly choosing k I and k P , z 2 [t] converges to 0 exponentially fast.
Lastly, we go back to prove Theorem 2.
Proof. The dynamic average tracking algorithm in (8) can be compactly written in the form: are obtained by concatenating estimates and weighted measurements from all nodes, . . η T p T are similarly defined. Recall that L is the Laplacian of the graph and ⊗ denotes the kronecker product. It is not hard to check that system (20) falls into the class of systems of the form (9) by choosing G = I p ⊗Â all of whose eigenvalues have positive real parts, F = F T = L ⊗ I n 0, and a = np. We also choose ϕ = φ 1 and we note that φ 1 i [t + 1] =Âφ 1 i [t] with i ranging from 1 to p.
Next we show that all the additional Assumptions we made in this section are satisfied.
First of all, we note that G = I p ⊗Â and F = L ⊗ I n , therefore all eigenvalues of G coincide with the eigenvalues of A and all eigenvalues of F coincide with the eigenvalues of L. Moreover, since φ 1 To this end, we only need to check if Assumptions 1(b) and 3 are satisfied, which will be argued in the following.
(1) Checking Additional Assumption 1(b): We pick matrix R = 1 √ p 1 p and a matrix S of suitable dimension such that R S is an orthogonal matrix. We note that the conditions R(R) = kerF and R(S) ∩ kerF = {0} follow from the construction of R and S. Also, recall that L is the Laplacian of the communication graph and the only eigenvector corresponding to the zero eigenvalue is 1 p . This, together with the construction of R, imply that the matrix R S ⊗ I n is an orthogonal matrix with R ⊗ I n lying in the kernel of (L ⊗ I n ). Moreover, we can check by direct computation that the following equalities hold: (2) Checking Additional Assumption 3: Since the graph is undirected, and hence L = L T holds, we can diagonalize L with a matrix T , i.e., T −1 LT is a diagonal matrix with eigenvalues λ 1 , . . . , λ r . To show that the additional Assumption 3 is also satisfied, we directly compute the following two transformations: (T ⊗ I n ) −1 (L ⊗ I n )(T ⊗ I n ) = diag{λ 1 I n , . . . , λ r I n } and (T ⊗I n ) −1 (I p ⊗Â)(T ⊗I n ) = I p ⊗Â = diag{Â, . . . ,Â}. This calculation shows that F and G are simultaneously diagonalizable and each block in G corresponds to an identity block in F , after diagonalization, up to a scalar λ i , hence the additional Assumption 3 is also satisfied.
Since the state observer we designed in (20) falls into the class (9) and satisfies all the additional assumptions, we can apply Propositions 2 and 3 to analyze the trajectory of W 1 i s in Equation (8). By Proposition 2 we conclude that (R T ⊗ By Proposition 3 we conclude that (S T ⊗ I n )W 1 converges to 0 exponentially fast, which shows the difference between any two estimates in two nodes decays to zero exponentially fast. Combining both we obtain that any W i converges to 1 is nothing more than solving a standard SSR problem. Once again, for the sake of simplicity we are not going to provide the rigorous definition of the SSR problem in this paper, which can be found in [7].
In the reconstruction step, each node seeks a statex ∈ R n and a vectorÊ ∈ R pn containing no more than s non-zero blocks that best explain the tracked compressed measurements W i . This problem can be solved in different ways. In this paper we adopt an optimization formulation by requiring each node to minimize W i − (D ⊗ I n )(Ox +Ê) 2 . Note that we dropped the time index t here to simplify notation. In other words, each node solves the following optimization problem: (x,Ê) = argmin (x,Ẽ) W i − (D ⊗ I n )(Ox +Ẽ) 2 , s.t. Ẽ l0/lr ≤ s, where Ẽ l0/lr denotes the number of non-zero blocks of the vectorẼ. The following lemma states that the solutionx of (21) is a good estimate of the system state when the tracking of the compressed measurements is accurate enough. Lemma 6. Let D ∈ R v×p and assume (A, C) is 2s-sparse detectable with respect to D. There exists a constant β ∈ (0, +∞) such that for any α ∈ (0, +∞), x ∈ R n , W i ∈ R vn , and Y ∈ R pn satisfying Y = Ox and W i − (D ⊗ I n )Y 2 ≤ α, the solutionx to the optimization problem (21) satisfies x − x 2 ≤ βα.
Moreover, let K 1 be the index set of non-zero blocks in E, K 2 be the index set of non-zero blocks inÊ, and K = K 1 ∪ K 2 . Note that |K| ≤ 2s. We pick L ∈ P 2s such that 6 ker(L) = span{e i , i ∈ K} and L 2 = 1. We observe that the following inequality holds: By assumption (A, C) is 2s-sparse detectable with respect to D, it follows that the matrix (L ⊗ I n )(D ⊗ I n )O has full column rank. In other words, we can pick β −1 = 1 2 σ min ((L ⊗ I n )(D ⊗ I n )O) > 0 and then Equation (23) directly implies x − x 2 ≤ βα, which finishes our proof.
As a special case, when W i = (D ⊗ I n )Y , the optimization problem in (21) degenerates to the following equality: Solving this equality is equivalent to finding the statex i , a vector T ∈ ker(D ⊗ I n ) and a vectorÊ i containing no more than s non-zero blocks such that: holds. Now we define a matrix N which has np rows and the least possible number of columns such that R(N ) = ker(D ⊗ I n ), and the optimization problem (21) is further reduced into finding the statex i , a vectorr i of appropriate dimension and a vectorÊ i containing no more than s non-zero blocks satisfying: Hereby we conclude that reconstructing the state x from compressed measurements (D ⊗ I n )Y is a special case of the SSR problem, and any algorithmic solution to the SSR problem, for example [17] and [28], can be applied to solve the DSST problem if they do not require additional assumptions. The preceding discussion directly leads to the sufficiency result: Lemma 7. Consider the linear system subject to attacks defined in (1) satisfying Assumptions 2-6 and a communication network satisfying Assumption 1. The tracking algorithm (8) together with a state-reconstruction algorithm enables each node to asymptotically track the state of the system (1) and consequently solves the DSST problem, if the pair (A, C) is 2s-sparse detectable.

Concluding Remarks
In this paper, we studied the problem of tracking the state of a linear system against sensor attacks in a network. Motivated by recent works in the dynamic average consensus literature and the simple observation that a compressed version of measurements suffices to reconstruct the state, we proposed a novel decentralized observer that enables each node in the network to track the state of the linear system 6 The definition of P 2s can be found in the definition of sparse detectability with respect to a matrix in Section 4, and the norm condition can be satisfied by a proper normalization. without making any non-necessary assumptions except one regarding the sampling rate.
Future directions include developing a decentralized state-tracking algorithm robust against other types of adversarial attacks, for example, a byzantine attack which is not only able to alter measurements but also forces attacked nodes to deviate from their prescribed algorithm. One additional problem of interest is the extension of the proposed results to the case where inputs are present but unknown to the nodes.