On detectability of cyber-attacks for large-scale interconnected systems ?

The paper deals with the key problem of detecting cyber-attacks in the context of large-scale systems (LSS). As these systems grow in size and complexity, cyber-attacks may target limited parts of the LSS, leading to tackling the problem in a decentralized way. We analyze the properties of distributed detection schemes under both local and interconnection attacks, and show that they are vulnerable to attacks that exploit the structure of the interconnections between subsystems. We also provide conditions and strategies that may be adopted to make the distributed control architecture regulating the LSS robust to this class of cyber-attacks.


INTRODUCTION
Many large-scale critical infrastructure and industrial control systems can be usefully described by the class of largescale dynamic systems (Lunze, 1992), in turn modeled as the interconnection of smaller subsystems. Indeed, this partition into subsystems may be done either to satisfy certain implementation objectives (such as a reduction of computational or communication costs associated with a centralized controller design), or because the plant itself is distributed over a large area. This has lead over the past decades to formulate distributed architectures to operate LSS (Šiljak and Zečević, 2005), where each subsystem is equipped with a local controller.
In order to achieve global objectives, controllers can share information over a communication network, allowing for coordination. In addition, these architectures increasingly rely on the integration of networked sensors and other socalled cyber infrastructure, leading to an increased concern in their cyber-security (Cárdenas et al., 2008). It has been ascertained in the security literature (Teixeira et al. (2015); Dibaji et al. (2019) and references therein) that malicious attackers can detrimentally affect the performance of a system by injecting disruptive signals into the plant's actuator, sensor, or communication channels, as real instances of attacks have proven (see Lee et al. (2016); Sobczak (2019) for recent evidence). Given this risk, together with the critical nature of LSS, it is deemed necessary to ensure their safety and security. Specifically, implementation of distributed monitoring architectures has attracted recent attention in literature (Anguluri et al., 2018;Gallo et al., 2018;Barboni et al., 2019), for which the distributed fault detection and isolation literature has been foundational (see for example Shames et al. (2011); Blanke et al. (2016); Boem et al. (2017a) to name but a few).
In this paper, we address the distributed detection of attacks on the communication network between controllers, named interconnection attacks, and highlight the structural limitations caused by the interconnection between subsystems. Furthermore, we include local attacks in our analysis, as in certain cases they can be modeled as interconnection attacks. The property of detectability of interconnection attacks is shown to be related to that of input observability of neighbors' states through interconnections, which can be seen as input to a subsystem's dynamics. Comprehensive results on input observability can be found in Hou and Patton (1998), or more recently Boukhobza et al. (2009) tackled a similar problem in a distributed context from a graph theoretic point of view.
Other works relevant to detectability of attacks are Pasqualetti et al. (2013) and Weerakkody et al. (2017). In the cited works, attackability is studied from a centralized point of view, and properties are formulated in terms of left-invertibility, which may not hold for subsystems with weakly coupled interconnections in LSS. Hence, we offer the following contributions: a. a generalized model of attacks which are local to one subsystem but target either the local control loop or the communication links;

Notation
Given a matrix A ∈ R p×n , rank A = p, A † is its the Moore-Penrose pseudo-inverse. I is the identity matrix of dimensions appropriate to the context. For a given matrix M , [M ] is used to define its related structural matrix, where specific entries are fixed at zeros, i.e., if [M ] (ij) = 0 then M (ij) = 0 also, while all others are set as free parameters. For some matrix Q, ker Q ⊥ denotes the space orthogonal to ker Q, the null space defined by Q. This decomposition is complete, hence any vector x =x + x ⊥ , wherex ∈ ker Q and x ⊥ ∈ ker Q ⊥ . Throughout the paper the superscripts a and h respectively indicate the attacked and nominal components of some signal x, i.e. in x = x h + x a , x h denotes its healthy component and x a the attacked one. With col[·], row[·], diag[·] we intend column and row concatenation of vectors or matrices, and block-diagonal concatenation of matrices.

Modeling Large-Scale Systems
We consider a large-scale system as a network of N subsystems S i , each of which is interconnected with a set N i ⊆ N {1, . . . , N }, called the set of neighbors of S i . The dynamics of the state of the LSS can be partitioned into N equations, each describing the dynamics of S i as: where x i ∈ R ni , u i ∈ R mi , and y i ∈ R pi are respectively the state, the control input, and the output of S i . The term j∈Ni A ij x j models the interconnection between different subsystems. Matrices A ii , B i , A ij , and C i are of appropriate dimensions. Furthermore, without loss of generality, rank C i = p i . Assumption 1. The pair (A ii , C i ), ∀i ∈ N is observable.
Assumption 2. For some full column rankÃ ij such that Im(Ã ij ) = Im(row[A] ij∈Ni ), there are no zero dynamics fromÃ ij to C i . Remark 3. In this paper we focus on the structural properties of a distributed diagnostic tool. As such no uncertainties are included in (1).
We consider that controllers C i are designed to implement a distributed control algorithm, for which u i , i ∈ N is computed both from locally measured outputs y i , and information received from neighboring controllers C j , j ∈ N i . In order to implement such an algorithm, it is necessary to introduce a peer-to-peer communication network between the controllers, as represented in Figure 1. Assumption 4. The topology of the network of physical interconnections between subsystems is mirrored by that of the communication network, and the networks are undirected.
We consider two scenarios: a) Subsystems share their local measurements y i . b) Subsystems share locally computed state estimatesx i .
The state estimatex i of x i is such that the estimation error i x i −x i → 0 asymptotically as t → ∞. How to compute such an estimate is out of the scope this paper. We introduce the following vector to model the information received by C i : wherex i col[x] j∈Ni is a vector grouping all the states of the neighboring subsystems S j , j ∈ N i , acting as an external input to S i . Notation (2) allows to consider the two information exchange scenarios in a unified way.
In the following, with some abuse of notation, we refer to its j-th block asC i,(j) . Assumption 5. If the following condition does not hold: controllers C i , i ∈ N transmit their local estimatex i . Remark 6. We note here that Assumption 5 is required to allow for the possibility of obtaining a local estimatex i such that i → 0 as t → ∞ without making the estimate independent of the interconnections.
To simplify notation, from (2) we can define an augmented output vector y i , containing both local measurements and transmitted signals:

Modeling cyber-attacks
Definition 7. (Local attack). Attacks between the controller C i and plant S i . These attacks alter the control input signals u i and the output measurements y i . Definition 8. (Interconnection attack). Attacks on information transmitted between controllers C j , or some subset of the neighboring subsystems j ∈ N i ⊆ N i , and C i . The attacker alters the signals contained inỹ i .
These two classes of attacks presuppose different architectures, and different attack resources. Specifically, local attacks presume that the control loop of S i is closed over a communication network, and the attacker is capable of corrupting the signals exchanged between C i and the networked sensors/actuators. On the other hand, in interconnection attacks, it is the communication network over which the controllers exchange information that is compromised. In Figure 1 we show how these different classes of attacks may affect the system. Note that we do not consider the possibility of attacks on the physical interconnections of the LSS.
Following the framework described in Teixeira et al. (2015), we model cyber-attacks in communication networks as additive signals. Specifically, the state dynamics, measurement and received communication outputs in (1) and (2) are defined as: where Moreover φ i models an interconnection attack onỹ i received by C i , µ i a local attack on the actuators, and η i one on the sensor measurements, as represented in Figure 1. We consider both B a i and D a i to be such that Im(B a i ) ⊆ Im(B i ) and Im(D a i ) ⊆ Im(C i ). Note that in (5) we have combined the modeling framework necessary to implement either local or interconnection attacks. Appropriate definition of u a i allows for modeling a number of different attack scenarios (Teixeira et al. (2015)). We denote the starting time of the attack as T a . Assumption 9. For t ≥ T a , an attack input function u a i = 0, for a single i ∈ N . Furthermore, it is defined either as Remark 10. Assumption 9 implies that at any given time either (u i , y i ) orỹ i can be trusted, i.e. are not corrupted by a malicious attacker.

Distributed attack detection architectures
Given the possible vulnerability of the LSS's communication networks, it is necessary to equip it with a monitoring layer. Specifically, as shown in Figure 1, we consider the addition of local model-based diagnostic modules D i capable of detecting local and interconnection attacks.
We choose to consider distributed architectures, as they are capable of integrating properties of scalability, low computational complexity, and privacy amongst subsystems within the diagnosis layer of the LSS. As such, we are interested in the analysis of its properties, and specifically of those limitations that arise following the partition of the LSS into subsystems, while having constraints on the information available to each local diagnoser. Let us define the set of information used in the design of D i : Definition 11. (Information set). The information set I i {M i , γ i , υ i } represents the information available to the diagnoser D i , where M i is a tuple defining the dynamics, and γ i and υ i are output and input signals. Definition 12. (Reduced-information distributed architecture). We define an architecture as "reduced-information" if the information set of D i is When D i is designed according to this definition, it is said to be "reduced-information" itself.
As D i does not have direct access to x i and x j∈Ni , to achieve detection the diagnoser defines an appropriate residual r i given I i . This residual is such that in nominal conditions r i → 0 as t → ∞, while if under attack this is detected once r a i is larger than some suitably chosen threshold.
Differently from other works in literature, we are not here focused on the detectability properties of the diagnoser with respect to local attacks. Rather, we are interested in the analysis of stealthiness of interconnection attacks with respect to the structure of the partitioned LSS. To clarify the explanation throughout the remainder of the paper, let us define the following classes of attacks 1 : Definition 13. (Stealthy attacks). An attack is stealthy if no monitor detects the attack, i.e. for an attack on S k , u a k = 0, r a i = 0, for any k ∈ N and all i ∈ N . Definition 14. (Locally stealthy attack). An attack is locally stealthy if [µ i , η i ] = 0 implies r a i = 0. Definition 15. (Structurally stealthy attacks). An interconnection attack on S i is said to be structurally stealthy to D i if, given I i , φ i = 0 leads to r a i = 0.

DETECTABILITY LIMITATIONS OF REDUCED-INFORMATION D i
In this section, we highlight the limitations of D i with respect to the partitioned structure of the LSS, given a reduced-information distributed architecture. We focus our attention to those attacks that are not locally detectable, namely, interconnection attacks and locally stealthy attacks. The first are analyzed as they influencẽ y i as received by C i , not visible to D j , j ∈ N i , which are transmitting the information. Of the latter, we focus on local covert attacks, inspired by covert attacks in Smith (2015), introduced in a distributed scenario by Barboni 1 The classes of attacks defined here can be seen as subsets of undetectable attacks in Pasqualetti et al. (2013).
Preprints of the 21st IFAC World Congress (Virtual) Berlin, Germany, July 12-17, 2020 et al. (2019), and shown to be locally stealthy to D i , as summarized in the following Lemma: Lemma 16. (Barboni et al. (2019)). Given a local covert attack active for time t ≥ T a , where µ i is freely chosen by the attacker to achieve some objective, and η i is defined as the output of the following linear time invariant system with initial condition x a j (T a ) = 0: a diagnostic module D i is not capable of detecting it.
Although Lemma 16 holds for all local diagnosers D i , in Barboni et al. (2019) it was shown that, through suitable design of the residual generator, it is possible for diagnosers of neighboring subsystems D j to detect local covert attacks. As such, they share similar properties to interconnection attacks. Proposition 17. Given a local covert attack on S j such that Lemma 16 holds, it is equivalent to µ j = η j = 0 and an interconnection attack In (8), with abuse of notation, φ i,(j) are the components of φ i corresponding to the signal received by C i from C j . Remark 18. Although in this paper we limit our analysis to local covert attacks, for both space restrictions and ease of explanation, the method exploited in Proposition 17 can be applied to any locally stealthy attack.
As such in the remainder, we consider that for some unknown j ∈ N i for t ≥ T a , φ i,(j) = 0, modeling both interconnection and local covert attacks on S j . We now introduce the main result of this paper. Theorem 19. Given a subsystem S i with dynamics as in (5), equipped with a detector D i designed with information set I i , suppose that, starting at some time T a > 0, the subsystem is exposed to an interconnection attack φ i,(j) = 0, for some j ∈ N i . Such an attack is structurally stealthy to local diagnoser D i if and only if Proof.
[Sufficiency]: In order to detect an attack, D i must generate a residual such that, given an attack oñ y i,(j) , ifC j x j =ỹ i,(j) , then r i → 0.
As the control input u i is known to D i (given I i in (6)) and as it cannot be altered maliciously (Assumption 9), its effect on y i will be disregarded. An appropriate estimator can be defined such that, nominally, r i → 0 is satisfied. Consider the map from x j to y i : Given that x j and M j are unknown to D i , the neighbor's state must be estimated (statically) in order for r i → 0 to be satisfied in nominal conditions: such a static estimate isx j (ỹ i,(j) ) =C † jỹi,(j) . Since rankC j = p i ≤ n i , this introduces error ε i,(j) (ỹ i,(j) ) x j −C † jỹi,(j) = 0. However, this does not affect the residual generator in nominal behavior, as jC j x j ∈ kerC j ⊆ ker A ij , given Assumption 5, and therefore r i → 0, even though ε i,(j) = 0. Hence,x j (ỹ i,(j) ) is an appropriate estimate of x j . Following the results on input observability in Hou and Patton (1998) any componentx j = 0,x j ∈ ker(A ij ) does not affect y i , as x j is in fact not input observable from y i . To prove sufficiency, suppose that φ i,(j) is designed by the attacker such that (9) holds. Due to linearity, the estimated output affected by the attack,ŷ a i , is: Hence, for t ≥ T a , r a i = 0, asŷ a i = 0, ∀t ≥ T a , and as such the attack is stealthy.
[Necessity]: We prove necessity by contradiction. Let us suppose thatC † j φ i,(j) ∈ ker A ij , but that the attack is indeed structurally stealthy.
The residual generator comparing y i andŷ i (ỹ i,(j) ), as t → ∞: Given thatC † j is full column rank by design, and that condition (9) is assumed not to hold,C † j φ ⊥ i,(j) = 0. Furthermore, following Assumption 2, there are no zero dynamics betweenÃ ij and C i . Hence, r a i = 0, which contradicts the hypothesis.
The result of Theorem 19 shows some similarities with respect to the class of zero-dynamics attacks in literature. Indeed, asx i can be considered as an exogenous input to S i , φ i can in turn be seen as an attack on the measurements of the inputs, and the class of attacks defined in Theorem 19 can be interpreted as a subset of zero-dynamics attacks. However, rather significantly, the attacks satisfying the stealthiness condition in Theorem 19 exploit the fact that A ij is not full column rank, rather than requiring knowledge of the dynamics of S j to exploit its transmission zeros. The above result is also relevant because attacks in this scenario are acting upon S i through the computation of u i by C i , which proves fundamental when considering the design of control architectures robust to such attacks.
If we consider an attacker with knowledge of the structure of the interconnection between subsystems, rather than A ij itself, a special case of Theorem 19 is derived. Such a scenario is relevant as not only said structure might be easier to obtain, but also because, in fact, subsystems in LSS are often described as being weakly coupled (Lunze, 1992). As a consequence, the interconnection matrices are often not structurally full rank, and the following holds. Corollary 20. If rank[A ij ] < n j , it is sufficient that be satisfied for attack to be structurally stealthy.
Note furthermore that, with the appropriate model knowledge and disruption resources, it would be possible for an interconnection attack to satisfy condition (9) even if rank A ij = n j . Indeed, given an attack on a number of interconnections such that j∈ Ni n j > n i is satisfied, and given knowledge of matrices A ij , for j ∈ N i , an attacker would be able to satisfy Theorem 19. A similar result was presented in Boem et al. (2017b), where the properties of a specific distributed detection architecture were analyzed.

CONTROLLER ROBUSTNESS TO STRUCTURALLY STEALTHY ATTACKS
In this section, we are interested in analyzing the interaction between structurally stealthy attacks and distributed control architectures. By affecting only the received measurementsỹ i , interconnection attacks φ i do not have a direct impact on the dynamics of S i . However, through appropriate definition of φ i , the control signals u i may be altered, thus maneuvering the state of S i to an operating point undesired by the operator. It is therefore important to define control laws such that u i is robust to structurally stealthy interconnection attacks. Definition 21. Consider a LSS with an interconnection attack φ i that satisfies Theorem 19, for some φ i,(j) , j ∈ N i . Let C i compute u i κ i (y i ), for some operator κ i 2 . We say that the control architecture is robust if ∀i ∈ N , for all attacks φ i,(j) = 0 stealthy to D i .
In order to ensure control architecture C i is robust, there are two strategies that can be pursued: • ensure κ i ([0 ,ỹ i ] ) = 0 for allỹ i such thatC † jỹi,(j) ∈ ker A ij ; • augment information set I i so that the class of stealthy interconnection attacks is reduced.
This section is dedicated to the former, while Section 5 will address the latter. Before proceeding, we analyze the special case in which φ i,(j) models a local covert attack on S j . Indeed, although in Proposition 17 we have shown that they can be interpreted as interconnection attacks, they affect the state of S j directly, and could therefore have an impact on the behavior of the LSS in two ways: i. by propagating the "attacked state" to other subsystems; ii. by having neighbors' controllers react to behavior that is not nominal. We address these cases separately. Proposition 22. If S j is subject to a local covert attack, controllers C i , i ∈ N , are robust to it.
Proof. In Proposition 17, we assumed the state of a subsystem under a covert attack to be nominal. This can be seen as the definition of a new nominal state and a shift of the attack action entirely onto the information transmission between subsystems. With respect to the actual nominal state from the perspective of C j , however, we have thatỹ i,(j) = y h j , which in fact satisfies (12), as φ i,(j) = 0. Proposition 23. If S j is subject to a local covert attack satisfying (9), the large-scale system composed of subsystems S k , k ∈ N \{j} is not influenced by the attack.
Hence, the dynamics of the large-scale system as a whole is, from (5): where A is a block-matrix where each ik-th entry is j∈N \{j} , and A kj groups the interconnection terms A ij for all S i such that j ∈ N i . We decompose x = x h +x a , where x a is the state affected by all attacks on the LSS. From Proposition 22, u a = 0, as for all i ∈ N j ,ỹ i,(j) = y h j . Hence, to prove x a = 0, i.e. that the state of the LSS once S j is subtracted is not affected by the attack, we must show that A kj x a j = 0. Recall condition (9) and that φ i,(j) = −C j x a j from Proposition 17. Thereforȇ C † jC j x a j ∈ ker A ij , implying that x a j ∈ ker A ij , ∀i ∈ N j . Hence, x a j ∈ ker A kj . As such, x a j will not influence the dynamics of any of its neighbors.
Having established that local covert attacks that are structurally stealthy do not propagate to the rest of the LSS, we evaluate the case in which there is an interconnection attack affectingỹ i . Consequently, the control inputs computed by C i should depend only on measurementsỹ i,(j) associated to those components of x j which directly influence S i through physical interconnection. This translates into ensuring that the arguments of the control function lie in ker(A ijC † ) ⊥ , as shown in the next result. Specifically, we introduce matrix Γ i diag[Γ] ij∈Ni , with Γ ij suitably designed for each j ∈ N i so that the following holds: Proposition 24. If each controller is such that with each Γ ij designed such that C i is robust to all structurally stealthy attacks.
Proof. By setting u i as in (15), it is clear that it is no longer required to detect φ i,(j) , but rather we are restricting the sensitivity of our residual to Γ ij φ i,(j) . As such, rather than (9), we are interested in verifying whether an attack function φ i,(j) such that C † j Γ ij φ i,(j) ∈ ker A ij holds. By setting Γ ij such that (15) holds, no attack function such that Γ ij φ i,(j) = 0 exists such that As such, any attack function such that κ i ([0 , Γ i φ i ] ) = 0 will not be stealthy to D i , and controllers are therefore robust to structurally stealthy attacks.
A possible definition of Γ ij such that Proposition 24 holds is to set it as a basis of ker(A ijC † j ) ⊥ . This is indeed quite conservative, requiring C i to only exploit measurements of neighbors' state components physically coupled with S i .

AUGMENTING I i FOR DETECTABILITY OF D i
A robust control law as presented in the previous section might be infeasible or in contrast with design constraints. As a result, in this section, we show how the addition of information on dynamics of neighboring subsystems S j , j ∈ N i to I i may assist with the design of robust controllers. Indeed, under certain conditions, this permits the estimation of x j directly, and to not rely on the input observability ofx i .
To illustrate the idea, we start by assuming that all of the model information M j , j ∈ N i is available to D i , showing how a residual generator may be capable of detecting structurally stealthy interconnection attacks. Given Assumption 1, it is possible to augment residual generator D i to include additional knowledge of the dynamics of S j .
By extending D i to detect additive attacks onỹ i,(j) , attackers must satisfy further constraints in order to be stealthy. Specifically, the following holds: Proposition 25. Attack φ i,(j) is stealthy to D i if and only if it is both structurally stealthy given A ij , and can be seen as a zero-dynamics attack on S j throughỹ i,(j) .
Proof. If D i is composed of r i and r i,(j) , j ∈ N i , it holds that for an attack φ i,(j) = 0 must satisfy both r a i = 0, r a i,(j) = 0, as if either of these do not hold D i will detect an attack. Following Theorem 19, φ i,(j) must be a structurally stealthy attack for r i → 0. As attack signal φ i,(j) is an additive signal toỹ i,(j) = y j , being a zero-dynamic attack is known to be a necessary and sufficient condition for it to be stealthy to a residual generator exploiting M j (Pasqualetti et al., 2013).
In general, there are conditions on the dynamics of S j that must be satisfied for D i to compute convergent estimates. While out of the scope of this paper to discuss such conditions in a general way, for completeness we refer the reader to Gallo et al. (2018). In that work, distributed diagnosers exploiting model knowledge of neighbors are designed to detect interconnection attacks in islanded DC microgrids.

CONCLUSIONS
Analysis of stealthy attacks in partitioned LSS have been presented, within the framework of interconnection attacks. We have derived conditions under which such attacks are not detectable, and have shown how controllers can be made robust to them, thus preventing the impact to be propagated to the entire LSS. Detectability, furthermore, can be recovered by properly extending the information set locally available to each diagnoser. Future studies will be focused on defining such a set so that it is minimal while ensuring estimation convergence.