Actuation attacks on constrained linear systems: A set-theoretic analysis

IFAC PapersOnLine 53-2 (2020) 6963–6968 ScienceDirect ScienceDirect Available online at www.sciencedirect.com 2405-8963 Copyright © 2020 The Authors. This is an open access article under the CC BY-NC-ND license . Peer review under responsibility of International Federation of Automatic Control. 10.1016/j.ifacol.2020.12.415 10.1016/j.ifacol.2020.12.415 2405-8963 Copyright © 2020 The Authors. This is an open access article under the CC BY-NC-ND license ( http://creativecommons.org/licenses/by-nc-nd/4.0 ) Actuation attacks on constrained linear systems: a set-theoretic analysis P. A. Trodden ∗J. M. Maestre ∗∗ H. Ishii ∗∗∗ ∗Department of Automatic Control & Systems Engineering, University of Sheffield, Sheffield, UK [email protected] ∗∗ Department of Systems and Automation Engineering, University of Seville, Seville, Spain [email protected] ∗∗∗ Department of Computer Science, Tokyo Institute of Technology, Yokohama, Japan [email protected] Abstract: This paper considers a constrained discrete-time linear system subject to actuation attacks. The attacks are modelled as false data injections to the system, such that the total input (control input plus injection) satisfies hard input constraints. We establish a sufficient condition under which it is not possible to maintain the states of the system within a compact state constraint set for all possible realizations of the actuation attack. The developed condition is a simple function of the spectral radius of the system, the relative sizes of the input and state constraint sets, and the proportion of the input constraint set allowed to the attacker. Keywords: Control problems under conflict or uncertainties; Constrained control; Robustness 1. INTRODUCTION The security of control systems to cyber-attacks has become a pressing issue, owing to the ubiquity of computers and networks and the vulnerabilities that these introduce (Smith, 2015). In the context of feedback control, attention has focused on several salient aspects of the cyber-security problem, including attack detection, synthesis and the analysis of control system stability and performance under different classes of attack, including denial of service (DoS), deception and false data injection (FDI) (Pasqualetti et al., 2013; Teixeira et al., 2015). In this paper, we study a simple instance of an actuation attack problem—a type of data injection attack—and, using set-theoretic methods, develop fundamental conditions under which it is not possible to robustly defend the system. In particular, we consider the problem of maintaining the states of a constrained linear system within a given state target set while it is subject to adversarial input disturbances. We consider that the input constraint set is partitioned, via a scaling factor, into two portions: the control input is selected from one portion, and the attack input from the other, such that the overall input applied is constraint admissible. The main result of the paper is the characterization of a lower bound on the constraint scaling factor such that robust stabilization of the system— and infinite-time robust constraint satisfaction—for all realizations of the attack is not possible. We note that although the state-feedback setting is simpler than that typically considered in the cyber-security literature—and renders certain aspects of the problem, such as stealth and detection, trivial—the results we obtain offer some insights into the relative ease of attacking a system according to its dynamics and constraints. The developed bound on the scaling factor depends, in a natural way, on the open-loop stability of the system, via its spectral radius, and the relative shapes and sizes of the input and state constraint sets. Following intuition, the bound confirms that more unstable systems with smaller target sets are easier to attack, in that the proportion of the input constraint set required by the attacker is smaller, which may have implications for the signal power and energy required for a successful attack. A few other papers have used set-theoretic techniques in the context of cyber-security. Lucia et al. (2016) propose a receding-horizon control law utilizing robust reachability sets in order to mitigate FDI and DoS attacks. Mohajerin Esfahani et al. (2010) and Mo and Sinopoli (2012) use reachability analysis in order to characterize the impact of FDI attacks. The most closely related work, however, appears to be from outside of this literature: Schulze Darup et al. (2017) considered a constrained linear (open-loop stable) autonomous system subject to additive disturbances selected from scaled disturbance set, and developed lower and upper bounds on the critical scaling factor at which robust infinite-time constraint satisfaction is not possible. The present paper considers non-autonomous systems rather than autonomous ones, however, and the techniques employed are necessarily different in order to handle the possibility of open-loop instability. The organization of this paper is as follows. Section 2 gives the problem statement, which is followed by a preliminary analysis in Section 3. In Section 4, we recall some established results on robust constraint admissible and control invariant sets, and develop some new ones that facilitate our developments. The main results of the paper are presented in Section 5, and are subsequently illustrated in Section 6. Section 7 contains a discussion of the results and the conservativeness of the bounds we develop. Conclusions and directions for future work are Actuation attacks on constrained linear systems: a set-theoretic analysis P. A. Trodden ∗J. M. Maestre ∗∗ H. Ishii ∗∗∗ ∗Department of Automatic Control & Systems Engineering, University of Sheffield, Sheffield, UK [email protected] ∗∗ Department of Systems and Automation Engineering, University of Seville, Seville, Spain [email protected] ∗∗∗ Department of Computer Science, Tokyo Institute of Technology, Yokohama, Japan [email protected] Abstract: This paper considers a constrained discrete-time linear system subject to actuation attacks. The attacks are modelled as false data injections to the system, such that the total input (control input plus injection) satisfies hard input constraints. We establish a sufficient condition under which it is not possible to maintain the states of the system within a compact state constraint set for all possible realizations of the actuation attack. The developed condition is a simple function of the spectral radius of the system, the relative sizes of the input and state constraint sets, and the proportion of the input constraint set allowed to the attacker. Keywords: Control problems under conflict or uncertainties; Constrained control; Robustness 1. INTRODUCTION The security of control systems to cyber-attacks has become a pressing issue, owing to the ubiquity of computers and networks and the vulnerabilities that these introduce (Smith, 2015). In the context of feedback control, attention has focused on several salient aspects of the cyber-security problem, including attack detection, synthesis and the analysis of control system stability and performance under different classes of attack, including denial of service (DoS), deception and false data injection (FDI) (Pasqualetti et al., 2013; Teixeira et al., 2015). In this paper, we study a simple instance of an actuation attack problem—a type of data injection attack—and, using set-theoretic methods, develop fundamental conditions under which it is not possible to robustly defend the system. In particular, we consider the problem of maintaining the states of a constrained linear system within a given state target set while it is subject to adversarial input disturbances. We consider that the input constraint set is partitioned, via a scaling factor, into two portions: the control input is selected from one portion, and the attack input from the other, such that the overall input applied is constraint admissible. The main result of the paper is the characterization of a lower bound on the constraint scaling factor such that robust stabilization of the system— and infinite-time robust constraint satisfaction—for all realizations of the attack is not possible. We note that although the state-feedback setting is simpler than that typically considered in the cyber-security literature—and renders certain aspects of the problem, such as stealth and detection, trivial—the results we obtain offer some insights into the relative ease of attacking a system according to its dynamics and constraints. The developed bound on the scaling factor depends, in a natural way, on the open-loop stability of the system, via its spectral radius, and the relative shapes and sizes of the input and state constraint sets. Following intuition, the bound confirms that more unstable systems with smaller target sets are easier to attack, in that the proportion of the input constraint set required by the attacker is smaller, which may have implications for the signal power and energy required for a successful attack. A few other papers have used set-theoretic techniques in the context of cyber-security. Lucia et al. (2016) propose a receding-horizon control law utilizing robust reachability sets in order to mitigate FDI and DoS attacks. Mohajerin Esfahani et al. (2010) and Mo and Sinopoli (2012) use reachability analysis in order to characterize the impact of FDI attacks. The most closely related work, however, appears to be from outside of this literature: Schulze Darup et al. (2017) considered a constrained linear (open-loop stable) autonomous system subject to additive disturbances selected from scaled disturbance set, and developed lower and upper bounds on the critical scaling factor at which robust infinite-time constraint satisfaction is not possible. The present paper considers non-autonomous systems rather than autonomous ones, however, and the techniques employed are necessarily different in order to handle the possibility of open-loop instability. The organization of this paper is as follows. Section 2 gives the problem statement, which is followed by a preliminary analysis in Section 3. In Section 4, we recall some established results on robust constraint admissible and control invariant sets, and develop some new ones that facilitate our developments. The main results of the paper are presented in Section 5, and are subsequently illustrated in Section 6. Section 7 contains a discussion of the results and the conservativeness of the bounds we develop. Conclusions and directions for future work are Actuation attacks on constrained linear systems: a set-theoretic analysis P. A. Trodden ∗J. M. Maestre ∗∗ H. Ishii ∗∗∗ ∗Department of Automatic Control & Systems Engineering, University of Sheffield, Sheffield, UK [email protected] ∗∗ Department of Systems and Automation Engineering, University of Seville, Seville, Spain [email protected] ∗∗∗ Department of Computer Science, Tokyo Institute of Technology, Yokohama, Japan [email protected] Abstract: This paper considers a constrained discrete-time linear system subject to actuation attacks. The attacks are modelled as false data injections to the system, such that the total input (control input plus injection) satisfies hard input constraints. We establish a sufficient condition under which it is not possible to maintain the states of the system within a compact state constraint set for all possible realizations of the actuation attack. The developed condition is a simple function of the spectral radius of the system, the relative sizes of the input and state constraint sets, and the proportion of the input constraint set allowed to the attacker. Keywords: Control problems under conflict or uncertainties; Constrained control; Robustness 1. INTRODUCTION The security of control systems to cyber-attacks has become a pressing issue, owing to the ubiquity of computers and networks and the vulnerabilities that these introduce (Smith, 2015). In the context of feedback control, attention has focused on several salient aspects of the cyber-security problem, including attack detection, synthesis and the analysis of control system stability and performance under different classes of attack, including denial of service (DoS), deception and false data injection (FDI) (Pasqualetti et al., 2013; Teixeira et al., 2015). In this paper, we study a simple instance of an actuation attack problem—a type of data injection attack—and, using set-theoretic methods, develop fundamental conditions under which it is not possible to robustly defend the system. In particular, we consider the problem of maintaining the states of a constrained linear system within a given state target set while it is subject to adversarial input disturbances. We consider that the input constraint set is partitioned, via a scaling factor, into two portions: the control input is selected from one portion, and the attack input from the other, such that the overall input applied is constraint admissible. The main result of the paper is the characterization of a lower bound on the constraint scaling factor such that robust stabilization of the system— and infinite-time robust constraint satisfaction—for all realizations of the attack is not possible. We note that although the state-feedback setting is simpler than that typically considered in the cyber-security literature—and renders certain aspects of the problem, such as stealth and detection, trivial—the results we obtain offer some insights into the relative ease of attacking a system according to its dynamics and constraints. The developed bound on the scaling factor depends, in a natural way, on the open-loop stability of the system, via its spectral radius, and the relative shapes and sizes of the input and state constraint sets. Following intuition, the bound confirms that more unstable systems with smaller target sets are easier to attack, in that the proportion of the input constraint set required by the attacker is smaller, which may have implications for the signal power and energy required for a successful attack. A few other papers have used set-theoretic techniques in the context of cyber-security. Lucia et al. (2016) propose a receding-horizon control law utilizing robust reachability sets in order to mitigate FDI and DoS attacks. Mohajerin Esfahani et al. (2010) and Mo and Sinopoli (2012) use reachability analysis in order to characterize the impact of FDI attacks. The most closely related work, however, appears to be from outside of this literature: Schulze Darup et al. (2017) considered a constrained linear (open-loop stable) autonomous system subject to additive disturbances selected from scaled disturbance set, and developed lower and upper bounds on the critical scaling factor at which robust infinite-time constraint satisfaction is not possible. The present paper considers non-autonomous systems rather than autonomous ones, however, and the techniques employed are necessarily different in order to handle the possibility of open-loop instability. The organization of this paper is as follows. Section 2 gives the problem statement, which is followed by a preliminary analysis in Section 3. In Section 4, we recall some established results on robust constraint admissible and control invariant sets, and develop some new ones that facilitate our developments. The main results of the paper are presented in Section 5, and are subsequently illustrated in Section 6. Section 7 contains a discussion of the results and the conservativeness of the bounds we develop. Conclusions and directions for future work are Actuation attacks on constrained linear systems: a set-theoretic analysis P. A. Trodden ∗J. M. Maestre ∗∗ H. Ishii ∗∗∗ ∗Department of Automatic Control & Systems Engineering, University of Sheffield, Sheffield, UK [email protected] ∗∗ Department of Systems and Automation Engineering, University of Seville, Seville, Spain [email protected] ∗∗∗ Department of Computer Science, Tokyo Institute of Technology, Yokohama, Japan [email protected] Abstract: This paper considers a constrained discrete-time linear system subject to actuation attacks. The attacks are modelled as false data injections to the system, such that the total input (control input plus injection) satisfies hard input constraints. We establish a sufficient condition under which it is not possible to maintain the states of the system within a compact state constraint set for all possible realizations of the actuation attack. The developed condition is a simple function of the spectral radius of the system, the relative sizes of the input and state constraint sets, and the proportion of the input constraint set allowed to the attacker. Keywords: Control problems under conflict or uncertainties; Constrained control; Robustness 1. INTRODUCTION The security of control systems to cyber-attacks has become a pressing issue, owing to the ubiquity of computers and networks and the vulnerabilities that these introduce (Smith, 2015). In the context of feedback control, attention has focused on several salient aspects of the cyber-security problem, including attack detection, synthesis and the analysis of control system stability and performance under different classes of attack, including denial of service (DoS), deception and false data injection (FDI) (Pasqualetti et al., 2013; Teixeira et al., 2015). In this paper, we study a simple instance of an actuation attack problem—a type of data injection attack—and, using set-theoretic methods, develop fundamental conditions under which it is not possible to robustly defend the system. In particular, we consider the problem of maintaining the states of a constrained linear system within a given state target set while it is subject to adversarial input disturbances. We consider that the input constraint set is partitioned, via a scaling factor, into two portions: the control input is selected from one portion, and the attack input from the other, such that the overall input applied is constraint admissible. The main result of the paper is the characterization of a lower bound on the constraint scaling factor such that robust stabilization of the system— and infinite-time robust constraint satisfaction—for all realizations of the attack is not possible. We note that although the state-feedback setting is simpler than that typically considered in the cyber-security literature—and renders certain aspects of the problem, such as stealth and detection, trivial—the results we obtain offer some insights into the relative ease of attacking a system according to its dynamics and constraints. The developed bound on the scaling factor depends, in a natural way, on the open-loop stability of the system, via its spectral radius, and the relative shapes and sizes of the input and state constraint sets. Following intuition, the bound confirms that more unstable systems with smaller target sets are easier to attack, in that the proportion of the input constraint set required by the attacker is smaller, which may have implications for the signal power and energy required for a successful attack. A few other papers have used set-theoretic techniques in the context of cyber-security. Lucia et al. (2016) propose a receding-horizon control law utilizing robust reachability sets in order to mitigate FDI and DoS attacks. Mohajerin Esfahani et al. (2010) and Mo and Sinopoli (2012) use reachability analysis in order to characterize the impact of FDI attacks. The most closely related work, however, appears to be from outside of this literature: Schulze Darup et al. (2017) considered a constrained linear (open-loop stable) autonomous system subject to additive disturbances selected from scaled disturbance set, and developed lower and upper bounds on the critical scaling factor at which robust infinite-time constraint satisfaction is not possible. The present paper considers non-autonomous systems rather than autonomous ones, however, and the techniques employed are necessarily different in order to handle the possibility of open-loop instability. The organization of this paper is as follows. Section 2 gives the problem statement, which is followed by a preliminary analysis in Section 3. In Section 4, we recall some established results on robust constraint admissible and control invariant sets, and develop some new ones that facilitate our developments. The main results of the paper are presented in Section 5, and are subsequently illustrated in Section 6. Section 7 contains a discussion of the results and the conservativeness of the bounds we develop. Conclusions and directions for future work are Actuation attacks on constrained linear systems: a set-theoretic analysis P. A. Trodden ∗J. M. Maestre ∗∗ H. Ishii ∗∗∗ ∗Department of Automatic Control & Systems Engineering, University of Sheffield, Sheffield, UK [email protected] ∗∗ Department of Systems and Automation Engineering, University of Seville, Seville, Spain [email protected] ∗∗∗ Department of Computer Science, Tokyo Institute of Technology, Yokohama, Japan [email protected] Abstract: This paper considers a constrained discrete-time linear system subject to actuation attacks. The attacks are modelled as false data injections to the system, such that the total input (control input plus injection) satisfies hard input constraints. We establish a sufficient condition under which it is not possible to maintain the states of the system within a compact state constraint set for all possible realizations of the actuation attack. The developed condition is a simple function of the spectral radius of the system, the relative sizes of the input and state constraint sets, and the proportion of the input constraint set allowed to the attacker. Keywords: Control problems under conflict or uncertainties; Constrained control; Robustness 1. INTRODUCTION The security of control systems to cyber-attacks has become a pressing issue, owing to the ubiquity of computers and networks and the vulnerabilities that these introduce (Smith, 2015). In the context of feedback control, attention has focused on several salient aspects of the cyber-security problem, including attack detection, synthesis and the analysis of control system stability and performance under different classes of attack, including denial of service (DoS), deception and false data injection (FDI) (Pasqualetti et al., 2013; Teixeira et al., 2015). In this paper, we study a simple instance of an actuation attack problem—a type of data injection attack—and, using set-theoretic methods, develop fundamental conditions under which it is not possible to robustly defend the system. In particular, we consider the problem of maintaining the states of a constrained linear system within a given state target set while it is subject to adversarial input disturbances. We consider that the input constraint set is partitioned, via a scaling factor, into two portions: the control input is selected from one portion, and the attack input from the other, such that the overall input applied is constraint admissible. The main result of the paper is the characterization of a lower bound on the constraint scaling factor such that robust stabilization of the system— and infinite-time robust constraint satisfaction—for all realizations of the attack is not possible. We note that although the state-feedback setting is simpler than that typically considered in the cyber-security literature—and renders certain aspects of the problem, such as stealth and detection, trivial—the results we obtain offer some insights into the relative ease of attacking a system according to its dynamics and constraints. The developed bound on the scaling factor depends, in a natural way, on the open-loop stability of the system, via its spectral radius, and the relative shapes and sizes of the input and state constraint sets. Following intuition, the bound confirms that more unstable systems with smaller target sets are easier to attack, in that the proportion of the input constraint set required by the attacker is smaller, which may have implications for the signal power and energy required for a successful attack. A few other papers have used set-theoretic techniques in the context of cyber-security. Lucia et al. (2016) propose a receding-horizon control law utilizing robust reachability sets in order to mitigate FDI and DoS attacks. Mohajerin Esfahani et al. (2010) and Mo and Sinopoli (2012) use reachability analysis in order to characterize the impact of FDI attacks. The most closely related work, however, appears to be from outside of this literature: Schulze Darup et al. (2017) considered a constrained linear (open-loop stable) autonomous system subject to additive disturbances selected from scaled disturbance set, and developed lower and upper bounds on the critical scaling factor at which robust infinite-time constraint satisfaction is not possible. The present paper considers non-autonomous systems rather than autonomous ones, however, and the techniques employed are necessarily different in order to handle the possibility of open-loop instability. The organization of this paper is as follows. Section 2 gives the problem statement, which is followed by a preliminary analysis in Section 3. In Section 4, we recall some established results on robust constraint admissible and control invariant sets, and develop some new ones that facilitate our developments. The main results of the paper are presented in Section 5, and are subsequently illustrated in Section 6. Section 7 contains a discussion of the results and the conservativeness of the bounds we develop. Conclusions and directions for future work are Actuation attacks on constrained linear systems: a set-theoretic analysis P. A. Trodden ∗J. M. Maestre ∗∗ H. Ishii ∗∗∗ ∗Department of Automatic Control & Systems Engineering, University of Sheffield, Sheffield, UK [email protected] ∗∗ Department of Systems and Automation Engineering, University of Seville, Seville, Spain [email protected] ∗∗∗ Department of Computer Science, Tokyo Institute of Technology, Yokohama, Japan [email protected] Abstract: This paper considers a constrained discrete-time linear system subject to actuation attacks. The attacks are modelled as false data injections to the system, such that the total input (control input plus injection) satisfies hard input constraints. We establish a sufficient condition under which it is not possible to maintain the states of the system within a compact state constraint set for all possible realizations of the actuation attack. The developed condition is a simple function of the spectral radius of the system, the relative sizes of the input and state constraint sets, and the proportion of the input constraint set allowed to the attacker. Keywords: Control problems under conflict or uncertainties; Constrained control; Robustness 1. INTRODUCTION The security of control systems to cyber-attacks has become a pressing issue, owing to the ubiquity of computers and networks and the vulnerabilities that these introduce (Smith, 2015). In the context of feedback control, attention has focused on several salient aspects of the cyber-security problem, including attack detection, synthesis and the analysis of control system stability and performance under different classes of attack, including denial of service (DoS), deception and false data injection (FDI) (Pasqualetti et al., 2013; Teixeira et al., 2015). In this paper, we study a simple instance of an actuation attack problem—a type of data injection attack—and, using set-theoretic methods, develop fundamental conditions under which it is not possible to robustly defend the system. In particular, we consider the problem of maintaining the states of a constrained linear system within a given state target set while it is subject to adversarial input disturbances. We consider that the input constraint set is partitioned, via a scaling factor, into two portions: the control input is selected from one portion, and the attack input from the other, such that the overall input applied is constraint admissible. The main result of the paper is the characterization of a lower bound on the constraint scaling factor such that robust stabilization of the system— and infinite-time robust constraint satisfaction—for all realizations of the attack is not possible. We note that although the state-feedback setting is simpler than that typically considered in the cyber-security literature—and renders certain aspects of the problem, such as stealth and detection, trivial—the results we obtain offer some insights into the relative ease of attacking a system according to its dynamics and constraints. The developed bound on the scaling factor depends, in a natural way, on the open-loop stability of the system, via its spectral radius, and the relative shapes and sizes of the input and state constraint sets. Following intuition, the bound confirms that more unstable systems with smaller target sets are easier to attack, in that the proportion of the input constraint set required by the attacker is smaller, which may have implications for the signal power and energy required for a successful attack. A few other papers have used set-theoretic techniques in the context of cyber-security. Lucia et al. (2016) propose a receding-horizon control law utilizing robust reachability sets in order to mitigate FDI and DoS attacks. Mohajerin Esfahani et al. (2010) and Mo and Sinopoli (2012) use reachability analysis in order to characterize the impact of FDI attacks. The most closely related work, however, appears to be from outside of this literature: Schulze Darup et al. (2017) considered a constrained linear (open-loop stable) autonomous system subject to additive disturbances selected from scaled disturbance set, and developed lower and upper bounds on the critical scaling factor at which robust infinite-time constraint satisfaction is not possible. The present paper considers non-autonomous systems rather than autonomous ones, however, and the techniques employed are necessarily different in order to handle the possibility of open-loop instability. The organization of this paper is as follows. Section 2 gives the problem statement, which is followed by a preliminary analysis in Section 3. In Section 4, we recall some established results on robust constraint admissible and control invariant sets, and develop some new ones that facilitate our developments. The main results of the paper are presented in Section 5, and are subsequently illustrated in Section 6. Section 7 contains a discussion of the results and the conservativeness of the bounds we develop. Conclusions and directions for future work are 6964 P.A. Trodden et al. / IFAC PapersOnLine 53-2 (2020) 6963–6968 presented in Section 8. Proofs of theoretical results are omitted for brevity. Notation: The sets of non-negative and positive reals are denoted, respectively, R0+ and R+ . The set of natural numbers, including zero, is N . For a, b ∈Rn , a≤b applies element by element. For X,Y ⊂Rn , the Minkowski sum is X⊕Y{x + y : x∈X,y ∈Y} ; for Y⊂X , the Minkowski difference is XY{x∈Rn : Y + x⊂X} . For X⊂Rn and a∈Rn , X⊕a means X⊕{a} . AX denotes the image of a set X⊂Rn under the linear mapping A : Rn→Rp , and is given by {Ax : x∈X} . The set −X{−x : x∈X} is the image of X under reflection in the origin. The support function of a non-empty set X⊂Rn is hX ( x ) sup{xz : z∈X} . A C-set is a convex and compact (closed and bounded) set containing the origin; a PC-set is a C-set with the origin in its interior. 2. PROBLEM STATEMENT We consider a discrete-time, linear time-invariant system, xk+1 =Axk+Buk,k∈N,(1) where xk∈Rn and uk∈Rm are the state and input at time k. The states and inputs are constrained as, xk∈Xand uk∈U, k ∈N. Assumption 1. The pair ( A, B )is reachable. X and U are PC-sets; U is symmetrical about the origin, i.e., U = −U . The setting considered in this paper is that the system (1) is subject to attacks on its input. We suppose that these attacks take place via an attacker gaining access to, and injecting data into, the control input signal, u . The system under attack is xk+1 =Axk+B(vk+ak)(2) i.e., the input to the system is uk = vk + ak , where ak∈U is the attack signal, and vk∈U the control signal provided by the system controller (the defender). More specifically, we consider that the attacker is able to use a proportion α∈ [0 , 1) of the input constraint space, while the defender is left with the remaining proportion 1−α. For k∈N, ak∈αU and vk∈(1 −α)U. In this way, the overall input constraint—which typically represents a hard actuation limit—is respected, yet the attacker is able to disturb the system and simultaneously reduce the set of actions available to the defender. The goal of the attacker is to drive the system states out of X . The goal of the defender is, naturally, to keep the state in X , despite the actions of the attacker. Our aim in this paper is to analyse this simple scenario and develop fundamental conditions, in terms of the parameter α , on when an attack is undefendable,i.e., such that there exists no control law able to maintain the state within X. 3. PRELIMINARY ANALYSIS We begin with some definitions relevant to the problem, and then link these to known concepts and results in constrained control. The following refer to the system (2) and constraints (xk,v k,a k)∈X×(1 −α)U×αU. Definition 2. (Attack and defence sets and strategies). The admissible attack {defence} set is αU {(1 −α ) U }, with α∈ [0 , 1). An admissible attack {defence} is an action ak∈αU { vk∈ (1 −α ) U }. An admissible attack {defence} strategy is a policy x→ v∈αU {x→ a∈(1 −α)U}. Definition 3. (Undefendable and defendable attack set). An attack set αU is said to be undefendable for the system (2) if, for all x0∈X , there does not exist an admissible defence strategy that maintains xk∈X for all k≥0. Otherwise, an attack set is said to be defendable. There is a direct link and equivalence between these definitions and established concepts in the literature: infinite reachability, strong reachability and robust control invariance (Bertsekas, 1972; Blanchini, 1999; Kerrigan, 2000). Definition 4. (Bertsekas (1972)). A set Y⊂Rnis: (1) Infinitely reachable if there exists a control law µ ( · )and some x0∈Y such that xk∈Y and vk = µ ( xk ) ∈ (1 − α)Ufor all ak∈αU. (2) Strongly reachable or robust control invariant (RCI) if there exists a control law µ ( · )such that for all x0∈Y , xk∈Yand vk=µ(xk)∈(1 −α)Ufor all ak∈αU. The link to defendability follows trivially. Lemma 5. The attack set αU is defendable if, and only if, X is infinitely reachable. X is infinitely reachable if, and only if, it contains a robust control invariant set C. Remark 6. In establishing a link between these concepts and the results later in the paper, we make a tacit assumption on the information pattern in the problem: the defender selects vk with knowledge of xk but without knowledge of ak , while the attacker may have knowledge of both xk and vk . Moreover, we tacitly assume that both attacker and defender know the value of α. This motivates the remainder of the paper. The question of whether an attack set is defendable or undefendable (as these concepts are defined) amounts exactly to whether or not the state constraint set X contains an RCI set. If it does, then the attack set can be said to be defendable 1 and standard techniques from robust constrained control can be used to keep the state within X . If it does not, then an attack set is undefendable, and there does not exist any defence strategy that keeps the state within X for all time, accounting for all possible actions of the attacker 2 . Our more concrete aim is, therefore, to characterize the relation between the constraint scaling factor α and the existence of an RCI set within X. 4. ROBUST CONSTRAINT-ADMISSIBLE AND CONTROL INVARIANT SETS First we present some known results and new results regarding RCI sets, with respect to a general linear system xk+1 =Axk+Buk+Ewk, (xk,u k,w k)∈X×U×W. (3) 1 Defendability, as it is defined, is a weak notion, in the sense that it does not imply that all x0∈Xcan be kept within X. 2 Undefendability says nothing about how the attacker may determine an admissible attack strategy that achieves the goal of steering x outside X . This is a less standard control problem than that of the defender, and is beyond the scope of the paper. P.A. Trodden et al. / IFAC PapersOnLine 53-2 (2020) 6963–6968 6965 presented in Section 8. Proofs of theoretical results are omitted for brevity. Notation: The sets of non-negative and positive reals are denoted, respectively, R0+ and R+ . The set of natural numbers, including zero, is N . For a, b ∈Rn , a≤b applies element by element. For X,Y ⊂Rn , the Minkowski sum is X⊕Y{x + y : x∈X,y ∈Y} ; for Y⊂X , the Minkowski difference is XY{x∈Rn : Y + x⊂X} . For X⊂Rn and a∈Rn , X⊕a means X⊕{a} . AX denotes the image of a set X⊂Rn under the linear mapping A : Rn→Rp , and is given by {Ax : x∈X} . The set −X{−x : x∈X} is the image of X under reflection in the origin. The support function of a non-empty set X⊂Rn is hX ( x ) sup{xz : z∈X} . A C-set is a convex and compact (closed and bounded) set containing the origin; a PC-set is a C-set with the origin in its interior. 2. PROBLEM STATEMENT We consider a discrete-time, linear time-invariant system, xk+1 =Axk+Buk,k∈N,(1) where xk∈Rn and uk∈Rm are the state and input at time k. The states and inputs are constrained as, xk∈Xand uk∈U, k ∈N. Assumption 1. The pair ( A, B )is reachable. X and U are PC-sets; U is symmetrical about the origin, i.e., U = −U . The setting considered in this paper is that the system (1) is subject to attacks on its input. We suppose that these attacks take place via an attacker gaining access to, and injecting data into, the control input signal, u . The system under attack is xk+1 =Axk+B(vk+ak)(2) i.e., the input to the system is uk = vk + ak , where ak∈U is the attack signal, and vk∈U the control signal provided by the system controller (the defender). More specifically, we consider that the attacker is able to use a proportion α∈ [0 , 1) of the input constraint space, while the defender is left with the remaining proportion 1−α. For k∈N, ak∈αU and vk∈(1 −α)U. In this way, the overall input constraint—which typically represents a hard actuation limit—is respected, yet the attacker is able to disturb the system and simultaneously reduce the set of actions available to the defender. The goal of the attacker is to drive the system states out of X . The goal of the defender is, naturally, to keep the state in X , despite the actions of the attacker. Our aim in this paper is to analyse this simple scenario and develop fundamental conditions, in terms of the parameter α , on when an attack is undefendable,i.e., such that there exists no control law able to maintain the state within X. 3. PRELIMINARY ANALYSIS We begin with some definitions relevant to the problem, and then link these to known concepts and results in constrained control. The following refer to the system (2) and constraints (xk,v k,a k)∈X×(1 −α)U×αU. Definition 2. (Attack and defence sets and strategies). The admissible attack {defence} set is αU {(1 −α ) U }, with α∈ [0 , 1). An admissible attack {defence} is an action ak∈αU { vk∈ (1 −α ) U }. An admissible attack {defence} strategy is a policy x→ v∈αU {x→ a∈(1 −α)U}. Definition 3. (Undefendable and defendable attack set). An attack set αU is said to be undefendable for the system (2) if, for all x0∈X , there does not exist an admissible defence strategy that maintains xk∈X for all k≥0. Otherwise, an attack set is said to be defendable. There is a direct link and equivalence between these definitions and established concepts in the literature: infinite reachability, strong reachability and robust control invariance (Bertsekas, 1972; Blanchini, 1999; Kerrigan, 2000). Definition 4. (Bertsekas (1972)). A set Y⊂Rnis: (1) Infinitely reachable if there exists a control law µ ( · )and some x0∈Y such that xk∈Y and vk = µ ( xk ) ∈ (1 − α)Ufor all ak∈αU. (2) Strongly reachable or robust control invariant (RCI) if there exists a control law µ ( · )such that for all x0∈Y , xk∈Yand vk=µ(xk)∈(1 −α)Ufor all ak∈αU. The link to defendability follows trivially. Lemma 5. The attack set αU is defendable if, and only if, X is infinitely reachable. X is infinitely reachable if, and only if, it contains a robust control invariant set C. Remark 6. In establishing a link between these concepts and the results later in the paper, we make a tacit assumption on the information pattern in the problem: the defender selects vk with knowledge of xk but without knowledge of ak , while the attacker may have knowledge of both xk and vk . Moreover, we tacitly assume that both attacker and defender know the value of α. This motivates the remainder of the paper. The question of whether an attack set is defendable or undefendable (as these concepts are defined) amounts exactly to whether or not the state constraint set X contains an RCI set. If it does, then the attack set can be said to be defendable 1 and standard techniques from robust constrained control can be used to keep the state within X . If it does not, then an attack set is undefendable, and there does not exist any defence strategy that keeps the state within X for all time, accounting for all possible actions of the attacker 2 . Our more concrete aim is, therefore, to characterize the relation between the constraint scaling factor α and the existence of an RCI set within X. 4. ROBUST CONSTRAINT-ADMISSIBLE AND CONTROL INVARIANT SETS First we present some known results and new results regarding RCI sets, with respect to a general linear system xk+1 =Axk+Buk+Ewk, (xk,u k,w k)∈X×U×W. (3) 1 Defendability, as it is defined, is a weak notion, in the sense that it does not imply that all x0∈Xcan be kept within X. 2 Undefendability says nothing about how the attacker may determine an admissible attack strategy that achieves the goal of steering x outside X . This is a less standard control problem than that of the defender, and is beyond the scope of the paper. These are subsequently specialized to the setting described in the previous section. 4.1 Some known results The i -step robust constraint-admissible set is the set of all states that can be kept within X for at least i time steps, for any disturbance, respecting the input constraints: Ci:= x:∃ui∈U isuch that xi∈X ifor all wi∈W i where ui (respectively wi ) is the sequence of i controls {u0,u 1,...,u i−1} (disturbances {w0,w 1,...,w i−1} ), the set UiU×···×U , with a similar definition for W and W . The corresponding sequence xi = {x0,x 1,...,x i} is obtained by, starting from x0 , applying the input sequence uj and disturbance sequence wj . The definition requires xi∈X iX×···×X. We recall some basic facts about Ci and its limit C∞ (Bertsekas, 1972; Blanchini, 1994; Kerrigan, 2000): Lemma 7. Suppose U is a PC-set and W is a C-set. Then (i) C0 = X ; (ii) if X is compact [convex], then each Ci is closed [convex]; (ii) Ci+1 ⊆Ci ; (iii) Ci = i j=0 Cj ; (iv) C∞ := limi→∞ Ci = ∞ i=0 Ci ; (v) if 0 ∈interior(C∞) then every Ci is a PC-set; (vi) if 0 ∈interior(C∞) , then C∞ is a robust control invariant set for the system (3) and constraint set ( X, U, W ); (vii) C∞ , if non-empty, is maximal in the sense that it contains all other robust control invariant sets for the system (3). To compute Ci, the following recursion holds: Ci+1 =Q(Ci)∩X, with C0=X, and where Q(·)is the backwards reachability operation: Q(Y){x:∃u∈Usuch that Ax +Bu ⊕EW ⊆Y}. More specifically, for the linear time invariant system (3), Ci+1 =(A)−1[CiEW]⊕(−BU)∩X, where ( A ) −1 ( · )denotes the pre-image of the linear transformation A ( · ), and exists regardless of whether A is invertible; for shorthand we will write A−iYto denote (Ai)−1(Y). Lemma 8. (1) C∞ is finitely determined if and only if there exists an i∗<∞such that Ci∗+1 =Ci∗. (2) If C∞is a PC-set, then such an i∗exists. 4.2 Some new results The aim of the paper is to characterize the existence of the set C∞ in terms of α . This requires the analysing of the sequence of sets {Ci} , the dynamics of which are characterized by Minkowski additions, subtractions, intersections and preimages, and not readily amenable to analysis. The following result therefore, which appears to be new, gives insight into how Ci (and therefore C∞ ) may be characterized in terms of sets with simpler dynamics that are more amenable to analysis. Proposition 9. The set Ciis bounded as Ci⊆ i  j=0 A−jTj(4) where Ti+1 =(TiAiEW)⊕Ai(−BU) with T0=X. Remark 10. A special case of this result was reported by Schulze Darup et al. (2017), who considered an autonomous system xk+1 = Axk + Ewk subject to a disturbance from a scaled set αW . In that setting, i.e., without a control input, what we refer to here as C∞ is the maximal robust positively invariant set. The authors determine conditions on the scaling constant α under which C∞ exists. Schulze Darup et al. (2017) develop the following relation (5) , which we show now to be a corollary of Proposition 9. Corollary 11. If U={0}then Ti=XRiand Ci= i  j=0 (Aj)−1(XRi)where Ri i  j=0 AjW. (5) Note that in (5) the relation for Ci holds with equality, and not just the inclusion depicted in Proposition 9. The reason for the weakening of the equality to mere inclusion is the behaviour of the Minkowski sum under the intersection: for sets A , B and C ,( A∩B ) ⊕C⊆ ( A⊕C ) ∩ ( B⊕C )and not ( A∩B ) ⊕C =( A⊕C ) ∩ ( B⊕C ). The latter equality does hold if the union of convex sets A and B is convex, which is generally not the case. This, together with the fact that we consider a non-autonomous system and not a stable autonomous one, means that the methodologies and results of Schulze Darup et al. (2017) do not apply. We conclude the section by establishing sufficient conditions for emptiness of the set Ci for some i> 0and subsequently C∞ . The results are central to the developments in the next section, when we specialize to the input-attack setting. Proposition 12. If, for some i>0,Ti=∅then Ci=∅for all i≥i. Proposition 13. If, for some i>0,Si=∅, where SiX⊕  i−2  j=0 AjB(−U)   i−1  j=0 AjEW , then Ti=∅for all i≥i. 5. FOR WHICH VALUES OF αIS AN ATTACK SET UNDEFENDABLE? We now recast some of the results from the previous section in the particular setting of the paper, and develop conditions under which C∞does not exist. Specializing the definitions of Ci and Ti to the system (2) and constraints ( xk,v k,a k ) ∈X× (1 −α ) U×αU , and exploiting the symmetry of U, we obtain Cα i+1 =A−1([Cα iαBU]⊕(1 −α)BU)∩X with Cα 0=X, and Tα i+1 =(Tα iαAiBU)⊕(1 −α)(AiBU) with Tα 0=X, where the sets are super-indexed by α to denote their dependency on this scaling factor. The connection between the two is, following Proposition 9, 6966 P.A. Trodden et al. / IFAC PapersOnLine 53-2 (2020) 6963–6968 Cα i⊆ i  j=0 A−jTα j. In a similar way, the set Si in Proposition 13 may be specialized to the setting and denoted Sα i. Our goal is to determine, for each i∈N , the smallest α for which Cα iis empty: αiinf{α:Cα i=∅,α∈[0,1]}. In our main result, Theorem 16, we establish an upper bound on αi . We achieve this by characterizing, for each i∈N , an ¯αi that renders Sα i empty for all α>¯αi . By Propositions 12 and 13, any α>¯αi≥αi then ensures that Cα i is empty. We find that this bound depends on the relative sizes of the constraint sets X and U , as well as the relative stability or instability (via the spectral radius) of the open-loop system. The following assumption is key to the development and simplicity of the result: Assumption 14. The dominant eigenvalue of A is real and positive. Let ρA denote the spectral radius of A , and Z {z1 A,...,zr A,−z1 A,...,−zr A} be the set of r linearly independent eigenvectors corresponding to the dominant eigenvalue, plus their additive inverses. Define ¯zAarg min z∈Z hX(z)/hBU(z), and HXU ( ¯zA ) hX ( zA ) /hBU ( zA ), the smallest among the ratio of support functions to X and BU evaluated in the directions ±zi A , i =1 ...r . The next assumption ensures this is well defined. Assumption 15. The mapped set BU has non-zero support in at least one of the directions ±zi A,i=1...r. Theorem 16. Suppose Assumptions 1, 14 and 15 hold. If, for some i∈N, α>¯αi       1+HXU(¯zA)[1 −ρA]−ρi−1 A 2−ρi−1 A−ρi A ρA=1 HXU(¯zA)+i−1 2i−1ρA=1 and ¯αi<1then Cα i=∅for all i≥i. Two corollaries of this theorem follow. Corollary 17. If α>¯αi when ¯αi< 1for some i∈N , then the attack set αU is undefendable; moreover, the state is guaranteed to remain in X , for all attack strategies, for at most i−1steps. Corollary 18. If α>¯α∞     1+HXU(¯zA)[1 −ρA] 2ρA<1 1 1+ρA ρA≥1 and ¯α∞<1then Cα ∞=∅. The bounds obtained here provide insight into the relative ease of attacking a system depending on its dynamics and constraints. More specifically, the critical scaling factor depends on the most unstable eigenvalue of the system and the relative sizes of the state and input constraint −1−0.5 0 0.5 1 −1 −0.5 0 0.5 1 x1 x2 3 j=0 A−jTj C3 Fig. 1. Comparison of C3 and its bounding set 3 j=0 A−jTj for system S3with α=0.1. sets in the direction of the corresponding eigenvector. The result implies that unstable systems are easier to attack (for example, if ρA> 1then ¯α∞< 1 / 2, so the attack set does not need to be as large as the defence set to render the system undefendable) and also that (un)defendability depends on the relative sizes of the sets BU (the mapped inputs) and X (for example, even if ρA =0, the system can be rendered undefendable if ¯α∞< 1, which requires HXU(¯zA)<1=⇒hBU(¯zA)>h X(¯zA)). Remark 19. It should be noted that Assumption 14 places restrictions only on the dominant eigenvalues. Under this assumption, the long-term critical evolution of the set AiEW = αAiBU , by which the intermediate sets are restricted, is in the direction ¯zA , which enables the simple result obtained. It is possible to extend the result to more general A matrices, such as those with complex dominant poles. However, because the long-term growth of the set αAiBU is then not in single direction, it is more involved to determine the number of steps after which the set Ti becomes empty. Remark 20. It is interesting to note that the derived bound is consistent with the obvious strategy for attacking an unstable system, namely a ( x, v )= −v ( x )if the information pattern permits it, which guarantees that the state leaves X in finite time. Indeed, since ¯α∞< 1 / 2for all ρA> 1, the attacker can choose α=1/2, permitting this strategy. 6. ILLUSTRATIVE EXAMPLES We illustrate the results via three example systems: S1:A=0.51 00.7S2:A=11 01 S3:A=1.91.1 0.51.5 where, in each case, B = [0.51 ] . The sets X and U are the unit hypercubes. First we illustrate Proposition 9. Fig. 1 compares, for system S3 and a scaling factor of α =0 . 25, the threestep constraint admissible set C3 with the outer bounding set 3 j=0 A−jTj derived in Proposition 9. The inclusion is not tight, as pointed out in Remark 10. Next, we illustrate and investigate the result of Theorem 16 and its corollaries. Figure 2 shows, for the systems S1 to P.A. Trodden et al. / IFAC PapersOnLine 53-2 (2020) 6963–6968 6967 Cα i⊆ i  j=0 A−jTα j. In a similar way, the set Si in Proposition 13 may be specialized to the setting and denoted Sα i. Our goal is to determine, for each i∈N , the smallest α for which Cα iis empty: αiinf{α:Cα i=∅,α∈[0,1]}. In our main result, Theorem 16, we establish an upper bound on αi . We achieve this by characterizing, for each i∈N , an ¯αi that renders Sα i empty for all α>¯αi . By Propositions 12 and 13, any α>¯αi≥αi then ensures that Cα i is empty. We find that this bound depends on the relative sizes of the constraint sets X and U , as well as the relative stability or instability (via the spectral radius) of the open-loop system. The following assumption is key to the development and simplicity of the result: Assumption 14. The dominant eigenvalue of A is real and positive. Let ρA denote the spectral radius of A , and Z {z1 A,...,zr A,−z1 A,...,−zr A} be the set of r linearly independent eigenvectors corresponding to the dominant eigenvalue, plus their additive inverses. Define ¯zAarg min z∈Z hX(z)/hBU(z), and HXU ( ¯zA ) hX ( zA ) /hBU ( zA ), the smallest among the ratio of support functions to X and BU evaluated in the directions ±zi A , i =1 ...r . The next assumption ensures this is well defined. Assumption 15. The mapped set BU has non-zero support in at least one of the directions ±zi A,i=1...r. Theorem 16. Suppose Assumptions 1, 14 and 15 hold. If, for some i∈N, α>¯αi       1+HXU(¯zA)[1 −ρA]−ρi−1 A 2−ρi−1 A−ρi A ρA=1 HXU(¯zA)+i−1 2i−1ρA=1 and ¯αi<1then Cα i=∅for all i≥i. Two corollaries of this theorem follow. Corollary 17. If α>¯αi when ¯αi< 1for some i∈N , then the attack set αU is undefendable; moreover, the state is guaranteed to remain in X , for all attack strategies, for at most i−1steps. Corollary 18. If α>¯α∞     1+HXU(¯zA)[1 −ρA] 2ρA<1 1 1+ρA ρA≥1 and ¯α∞<1then Cα ∞=∅. The bounds obtained here provide insight into the relative ease of attacking a system depending on its dynamics and constraints. More specifically, the critical scaling factor depends on the most unstable eigenvalue of the system and the relative sizes of the state and input constraint −1−0.5 0 0.5 1 −1 −0.5 0 0.5 1 x1 x2 3 j=0 A−jTj C3 Fig. 1. Comparison of C3 and its bounding set 3 j=0 A−jTj for system S3with α=0.1. sets in the direction of the corresponding eigenvector. The result implies that unstable systems are easier to attack (for example, if ρA> 1then ¯α∞< 1 / 2, so the attack set does not need to be as large as the defence set to render the system undefendable) and also that (un)defendability depends on the relative sizes of the sets BU (the mapped inputs) and X (for example, even if ρA =0, the system can be rendered undefendable if ¯α∞< 1, which requires HXU(¯zA)<1=⇒hBU(¯zA)>h X(¯zA)). Remark 19. It should be noted that Assumption 14 places restrictions only on the dominant eigenvalues. Under this assumption, the long-term critical evolution of the set AiEW = αAiBU , by which the intermediate sets are restricted, is in the direction ¯zA , which enables the simple result obtained. It is possible to extend the result to more general A matrices, such as those with complex dominant poles. However, because the long-term growth of the set αAiBU is then not in single direction, it is more involved to determine the number of steps after which the set Ti becomes empty. Remark 20. It is interesting to note that the derived bound is consistent with the obvious strategy for attacking an unstable system, namely a ( x, v )= −v ( x )if the information pattern permits it, which guarantees that the state leaves X in finite time. Indeed, since ¯α∞< 1 / 2for all ρA> 1, the attacker can choose α=1/2, permitting this strategy. 6. ILLUSTRATIVE EXAMPLES We illustrate the results via three example systems: S1:A=0.51 00.7S2:A=11 01 S3:A=1.91.1 0.51.5 where, in each case, B = [0.51 ] . The sets X and U are the unit hypercubes. First we illustrate Proposition 9. Fig. 1 compares, for system S3 and a scaling factor of α =0 . 25, the threestep constraint admissible set C3 with the outer bounding set 3 j=0 A−jTj derived in Proposition 9. The inclusion is not tight, as pointed out in Remark 10. Next, we illustrate and investigate the result of Theorem 16 and its corollaries. Figure 2 shows, for the systems S1 to 0 5 10 15 0 0.5 1 i αior ¯αi ¯αi αi (a) Stable system S1 0 5 10 15 0 0.5 1 i αior ¯αi ¯αi αi (b) Double integrator S2 0 5 10 15 0 0.5 1 i αior ¯αi ¯αi αi (c) Unstable system S3 Fig. 2. Comparison of the bound ¯αi obtained from Theorem 16 with the true bound αi. S3 , the exact critical scaling factors αi and the upper bound ¯αi from Theorem 16. The exact scaling factors were found by trial and error, searching over α∈ (0 , 1) until the smallest value is found for which the reachability recursion Cα i+1 =Q(Cα i)∩Xresults in Cα i=∅for i=i. 7. DISCUSSION The bound on critical α is merely sufficient and, as the numerical results indicate, it is not tight— Cα i may become empty at some smaller i or α than the bound of Theorem 16 suggests. The sources of conservatism are threefold: (1) Proposition 12 is sufficient, but not necessary, to guarantee emptiness of Ci at some i . The lack of necessity arises from the lack of tightness (illustrated in Fig. 1) in the inclusion relation between Ci and Ti established in Proposition 9. This itself is, as explained in Remark 10, because Minkowski addition is not distributive over set intersections. To avoid this, and guarantee equality in the relation of Proposition 9 and necessity of the condition in Proposition 12, strong and unusual assumptions on the system and constraints would be required. (2) Similarly, Proposition 13 is merely sufficient to ensure emptiness of Ti at a given i = i . The source of conservatism again arises from the basic properties of Minkowski addition and subtraction, and in particular that these operations do not commute: Proposition 13 uses the fact that, for sets A , B and C , A⊕C B⊇AB⊕C. (3) Theorem 16 is sufficient, but not necessary, to ensure emptiness of Sα i . The condition was developed by considering the dynamics of Sα i over times i∈N in only one direction in Rn , the eigenvector associated with the dominant (real) eigenvalue. It is possible, but this depends on the system and constraints, that emptiness of Sα i could be concluded at some smaller α than ¯αi by considering other directions. On the other hand, the long-term change in Sα i will tend to be dominated by activity in the direction of the dominant eigenvalue; our numerical results show relatively good agreement between the theoretical bound and the exact bound as igrows. Finally, it is worth remarking that the developed theoretical bounds are simple to determine, requiring only the spectral information about the open-loop system and a couple of support function evaluations on the constraint sets X and U . In comparison, to determine the exact α ( i )requires a search over the space α∈ (0 , 1), computing the sequence {Cα i}i≥0until it is found that Cα iis empty. 8. CONCLUSIONS AND FUTURE WORK We have analysed a simple instance of a constrained linear system subject to actuation attacks and, using set-theoretic methods, derived a lower bound on the sufficient size of the attack set in order that robust infinite-time constraint satisfaction can not be guaranteed. The bound depends, in an intuitive way, on the spectral radius of the system and size and shape of the constraint sets. Future work will investigate lowering conservatism (e.g., by deriving results considering more than one eigenvector direction), consider more general instances of A (e.g., with dominant complex eigenvalues) and a more sophisticated setting (e.g., with outputs and sensor data injection). ACKNOWLEDGEMENTS Financial support from the JSPS fellowship PE16048 and the MINECO-Spain project C3PO (ref: DPI2017-86918-R) is gratefully acknowledged. REFERENCES D. P. Bertsekas. Infinite-time reachability of state-space regions by using feedback control. IEEE Transactions on Automatic Control, 17(5):604–613, 1972. F. Blanchini. Ultimate boundedness control for uncertain discrete-time systems via set-induced Lyapunov functions. IEEE Transactions on Automatic Control, 39(2): 428–433, 1994. F. Blanchini. Set invariance in control. Automatica, 35(11): 1747–1767, 1999. 6968 P.A. Trodden et al. / IFAC PapersOnLine 53-2 (2020) 6963–6968 E. C. Kerrigan. Robust Constraint Satisfaction: Invariant Sets and Predictive Control. PhD thesis, University of Cambridge, 2000. I. Kolmanovsky and E. G. Gilbert. Theory and computation of disturbance invariant sets for discrete-time linear systems. Mathematical Problems in Engineering, 4:317– 367, 1998. W. Lucia, B. Sinopoli, and G. Franze. A set-theoretic approach for secure and resilient control of cyber-physical systems subject to false data injection attacks. In 2016 Science of Security for Cyber-Physical Systems Workshop, pages 1–5, 2016. Y. Mo and B. Sinopoli. Integrity attacks on cyberphysical systems. In Proceedings of the 1st International Conference on High Confidence Networked Systems, pages 47–54, 2012. P. Mohajerin Esfahani, M. Vrakopoulou, K. Margellos, J. Lygeros, and G. Andersson. Cyber attack in a two-area power system: Impact identification using reachability. In Proceedings of the 2010 American Control Conference, pages 962–967, 2010. F. Pasqualetti, F. Dörfler, and F. Bullo. Attack detection and identification in cyber-physical systems. IEEE Transactions on Automatic Control, 58(11):2715–2729, 2013. R. Schneider. Convex Bodies: The Brunn-Minkowski Theory, volume 44 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1993. M. Schulze Darup, R. Schaich, and M. Cannon. How scaling of the disturbance set affects robust positively invariant sets for linear systems. International Journal of Robust and Nonlinear Control, 27(16):3236–3258, 2017. R. S. Smith. Covert misappropriation of networked control systems: Presenting a feedback structure. IEEE Control Systems, 35(1):82–92, 2015. A. Teixeira, K. C. Sou, H. Sandberg, and K. H. Johansson. Secure control systems: A quantitative risk management approach. IEEE Control Systems, 35(1):24–45, 2015.