# A Timing-Based Framework for Designing Resilient Cyber-Physical Systems
under Safety Constraint

Abdullah Al Maruf<EMAIL_ADDRESS>Network Security Lab, Department of
Electrical and Computer Engineering, University of WashingtonP.O. Box
1212SeattleWashingtonUSA98195-2500 1234-5678-9012 ,  Luyao Niu
<EMAIL_ADDRESS>Network Security Lab, Department of Electrical and Computer
Engineering, University of WashingtonSeattleWashingtonUSA98195-2500 ,  Andrew
Clark<EMAIL_ADDRESS>Electrical and Systems Engineering Department,
McKelvey School of Engineering, Washington University in St.
LouisMissouriUSA63130 ,  J. Sukarno Mertoguno<EMAIL_ADDRESS>School of
Cybersecurity and Privacy, Georgia Institute of
TechnologyAtlantaGeorgiaUSA30332 and  Radha Poovendran<EMAIL_ADDRESS>Network
Security Lab, Department of Electrical and Computer Engineering, University of
WashingtonSeattleWashingtonUSA98195-2500

(2018)

###### Abstract.

Cyber-physical systems (CPS) are required to satisfy safety constraints in
various application domains such as robotics, industrial manufacturing
systems, and power systems. Faults and cyber attacks have been shown to cause
safety violations, which can damage the system and endanger human lives.
Resilient architectures have been proposed to ensure safety of CPS under such
faults and attacks via methodologies including redundancy and restarting from
safe operating conditions. The existing resilient architectures for CPS
utilize different mechanisms to guarantee safety, and currently there is no
approach to compare them. Moreover, the analysis and design undertaken for CPS
employing one architecture is not readily extendable to another. In this
paper, we propose a timing-based framework for CPS employing various resilient
architectures and develop a common methodology for safety analysis and
computation of control policies and design parameters. Using the insight that
the cyber subsystem operates in one out of a finite number of statuses, we
first develop a hybrid system model that captures CPS adopting any of these
architectures. Based on the hybrid system, we formulate the problem of joint
computation of control policies and associated timing parameters for CPS to
satisfy a given safety constraint and derive sufficient conditions for the
solution. Utilizing the derived conditions, we provide an algorithm to compute
control policies and timing parameters relevant to the employed architecture.
We also note that our solution can be applied to a wide class of CPS with
polynomial dynamics and also allows incorporation of new architectures. We
verify our proposed framework by performing a case study on adaptive cruise
control of vehicles.

cyber-physical systems (CPS), safety-critical system, cyber resilient
architecture, barrier certificate

††copyright: acmcopyright††journalyear: 2018††doi: XXXXXXX.XXXXXXX††journal:
JACM††journalvolume: 37††journalnumber: 4††article: 111††publicationmonth: 8

##  1\. Introduction

The coupling between cyber and physical subsystems of Cyber-Physical Systems
(CPS) creates an opportunity for faults and attacks on cyber components to
impact the physical performance and safety (Alemzadeh et al., 2016; Koscher et
al., 2010). Cyber attacks causing severe safety violations have been reported
in many application domains such as transportation (Greenberg, 2015), medical
devices (Halperin et al., 2008), and power system (Lee et al., 2016).

A variety of fault tolerant architectures (Sha, 2001; Bak et al., 2009; Mohan
et al., 2013) have been proposed to mitigate the impact of failures in CPS.
These architectures primarily use redundancies and require at least one of the
redundant components to be verified as fault-free at any time instant.
However, when CPS are under cyber attacks, these architectures become sub-
optimal or even not applicable since an intelligent adversary can exploit the
same vulnerabilities common to all the components and cause system failure.

To address cyber attacks against CPS, cyber resilient architectures (CRAs)
(Mertoguno et al., 2019; Arroyo et al., 2019; Abdi et al., 2017, 2018;
Romagnoli et al., 2020a, 2019; Niu et al., 2022b) have been proposed to ensure
the safety of CPS during attacks and recover the system to its nominal
operation after attacks. One class of architectures mitigates cyber attacks by
restarting the cyber subsystem to an uncompromised (‘clean’) state. This
restart can either be proactive (periodic) or reactive by engineering the
controller to crash when the adversary attempts to exploit the
vulnerabilities. These restart-based mechanisms limit the adversary’s
capabilities of compromising the cyber component, but also render the
controller inoperative during restart, potentially leading to safety
violations.

The existing CRAs (Mertoguno et al., 2019; Arroyo et al., 2019; Abdi et al.,
2018; Romagnoli et al., 2019; Niu et al., 2022b; Gamarra et al., 2019) employ
different mechanisms that achieve different levels of resilience, safety, and
system performance. At present, there is no common analysis methodology to
evaluate them or compute the associated design parameters and control policies
for CPS safety. Such a methodology should be based on a framework to model CPS
employing all possible CRAs, which currently does not exist.

In this paper, we propose and develop a hybrid system framework to provide
guarantee on safe operation of a CPS that uses different classes of CRAs. Our
insight is that the cyber subsystem operates in one out of a finite number of
statuses, such as _normal_ (following nominal control policy), _corrupted_
(controller compromised by the adversary), and _restoration_ (recovering the
controller). These statuses comprise the discrete location set of the hybrid
system, whereas the physical dynamics of the CPS are captured by a nonlinear
dynamical state space model. Based on the hybrid system, we develop a common
analysis methodology to compute control policies and associated design
parameters for different classes of CRAs. Our approach is based on computing
the duration of time that the CPS can remain in each status to guarantee CPS
safety. These time durations, which we denote as _timing parameters_ , provide
a common method to quantify the resilience of CPS when employing distinct
CRAs, and thus allow us to evaluate the CRAs. Our approach is sufficiently
general to enable analysis and design for future CRAs. Our main contributions
in this paper are summarized as follows.

  * •

We develop a hybrid system model to capture CPS employing at least ten state-
of-the-art architectures of six different classes (Sha, 2001; Bak et al.,
2009; Mohan et al., 2013; Mertoguno et al., 2019; Arroyo et al., 2019, 2017;
Abdi et al., 2018; Romagnoli et al., 2019; Niu et al., 2022b; Gamarra et al.,
2019). The discrete transitions of the hybrid system model how cyber statuses
evolve over time following cyber attacks.

  * •

Using the hybrid system, we quantify how fast CPS approaches the boundary of a
given safety region at each cyber status. Using this quantification, we derive
sufficient conditions for a control policy and timing parameters so that the
system remains within the safety region.

  * •

We present an algorithm to jointly compute the control policy and timing
parameters by mapping the derived conditions to a sum-of-squares program that
is applicable to any CPS with polynomial dynamics. We analyze our proposed
algorithm and prove that it converges to a safe control policy, provided that
one exists.

  * •

We validate our algorithm by using a case study on adaptive cruise control of
vehicles. We show that our proposed approach guarantees safety of the system
implementing any of the CRAs.

A preliminary version of this work was presented in (Niu et al., 2022a).
Compared with (Niu et al., 2022a), this article differs in the following
aspects. First, our hybrid model incorporates more CRAs than (Niu et al.,
2022a), including proactive restart (Abdi et al., 2018; Romagnoli et al.,
2019), reactive restart (Niu et al., 2022b), and dual redundant architectures
(Gamarra et al., 2019). Moreover, the conditions and algorithm derived in this
paper are applicable to CPS with a broader class of physical dynamics. Our
proposed approach is also more flexible since it can be mapped to new
architectures, allowing future resilient designs to be incorporated in the
framework. We present a new case study for which the solution method given in
(Niu et al., 2022a) is not applicable.

The remainder of this paper is organized as follows. Section 2 presents the
related works in the context of our paper. Section 3 presents the system and
threat models. Our proposed analytic framework and problem statement are
presented in Section 4. Section 5 provides our solution approach including
proposed algorithm and its analysis. A case study is presented in Section 6.
We conclude the paper in Section 7.

##  2\. Related Works

There has been extensive study on verification (Prajna et al., 2007; Pajic et
al., 2014a) and control synthesis (Ames et al., 2019; Cohen and Belta, 2020;
Qin et al., 2021; Herbert et al., 2017) for safety-critical CPS, assuming that
the systems are operated under benign environments without any fault or
attack. Barrier certificate based approaches, where safety constraint is
encoded as a linear inequality on the control input, have been widely used in
this context (Ames et al., 2016; Xu, 2018; Prajna et al., 2007).

To address faults occurring in CPS, many fault tolerant controls (Zhang and
Jiang, 2008; Sharifi et al., 2010; Xu et al., 2020) and architectures (Castro
and Liskov, 2002; Sha, 2001; Bak et al., 2009; Mohan et al., 2013; Niu et al.,
2019) have been proposed. Fault tolerant controls usually consist of fault
detection scheme accompanied with resynthesis of controllers using methods
like robust $H_{\infty}$ control and model predictive control (Zhang and
Jiang, 2008). Fault tolerant architectures are primarily redundancy based and
designed to deal with known failures which occur randomly.

One of the widely adopted fault tolerant designs is Simplex architecture (Sha,
2001). This architecture consists of a main controller and a safety
controller. The main controller is a high performance controller which is
vulnerable to random failure whereas safety controller is verifiable and
fault-free. Both controllers run in parallel and a decision module monitors
the system states and decides which controller to be used to actuate the
physical subsystem. The main controller operates the system unless the
decision module instantly switches to safety controller under certain
conditions, e.g., main controller is faulty. After recovering the main
controller from fault, the decision module switches back to the main
controller again. System-level Simplex (Bak et al., 2009) requires the safety
controller and decision module to be located in a dedicated trusted processing
unit such as FPGA. Secure System Simplex (S3A) (Mohan et al., 2013) is an
enhancement of system-level Simplex as the decision module also monitors the
side channels of main controller for faster detection of certain cyber attacks
that cannot replicate the monitored side channels. These fault tolerant
architectures rely on the assumption that there is no common mode failure for
all the controllers. However, this assumption may not hold in the presence of
cyber attack (Mertoguno et al., 2019).

In the existing literature, two different directions have been taken to
address cyber attacks in CPS. In the first direction, control- and game-
theoretic approaches have been proposed to protect CPS from cyber attacks
(Pajic et al., 2014b; Fawzi et al., 2014; Mo and Sinopoli, 2010; Manshaei et
al., 2013; Zhu and Başar, 2015; Cárdenas et al., 2008). The idea is to detect
the attack and then prevent the impact from the attack by making necessary
corrections for the detected attack. The second direction focuses on designing
resilient systems that can tolerate and then recover from attack. The CRAs
(Mertoguno et al., 2019; Arroyo et al., 2019, 2017; Abdi et al., 2018;
Romagnoli et al., 2019; Niu et al., 2022b; Gamarra et al., 2019) including
BFT++ (Byzantine fault tolerant++) (Mertoguno et al., 2019) and YOLO (You Only
Live Once) (Arroyo et al., 2019) follow this approach.

BFT++ (Mertoguno et al., 2019) relies upon redundancies of the controller. In
particular, BFT++ uses multiple redundant controllers where one of the them is
designated as backup. Other non-backup controllers are employed with
artificial software diversity via different implementations of software or
randomization of the memory or instruction set (Larsen et al., 2014; Kc et
al., 2003). Due to this diversity, one of the non-backup controller
deliberately crashes when an attacker attempts to intrude the system by
exploiting the cyber vulnerabilities. This crash signal triggers restoration
of non-backup controllers from the backup one.

YOLO and its variant use periodic restart and does not have any redundant
controller (Arroyo et al., 2019, 2017). During each restart, the controller is
reset to its ‘clean’ state by loading its software from a read only module and
clearing out all the volatile memory. YOLO also implements software diversity
after each restart to ensure that the attacker cannot exploit same
vulnerabilities. YOLO requires proper tuning of controller availability based
on the natural resilience of the physical subsystem. Dual redundant scheme
adopts same strategy as YOLO, but instead of restarting CPS, it periodically
switches between two identical controllers (Gamarra et al., 2019). After
switching to the standby controller, the other controller restarts to ensure
its integrity. This scheme is extendable to multiple controllers where CPS
switches among them periodically. However this redundant scheme is useful over
YOLO only when the restart time of controllers is relatively high.

Proactive restart based scheme also uses restart to recover the compromised
controller (Abdi et al., 2018; Romagnoli et al., 2019). Unlike YOLO, a secured
execution interval (SEI) program is executed following a restart. During this
interval, all the external interfaces of the system are disabled while a
safety controller takes over the system. After scheduling the next restart
time, the main controller program takes over from the safety controller and
CPS resumes its normal operation by enabling the external interfaces. In (Abdi
et al., 2018) online reachability analysis was used to determine the time for
next restart and then it was scheduled in an external hardware timer which can
only be programmed once before the next restart. Reference (Romagnoli et al.,
2019) provided a method to compute these timing parameters using offline
reachability analysis over linearized dynamics of the physical subsystem.
These results has been extended for networked systems as well as noisy
settings (Griffioen et al., 2019; Romagnoli et al., 2020b).

Reactive restart based mechanism uses crash signals as triggers to restart
(Niu et al., 2022b). It assumed that the adversary needs certain amount of
time (referred as exploitation window) to exploit the vulnerabilities to own
the controller. The controller will then crash after some time (referred as
vulnerability window) due to erroneous inputs coming from the adversary.
Reference (Niu et al., 2022b) provides an analysis using barrier certificate
based approach to compute the control policy and bounds on these timing
windows. However, this analysis does not hold for a system whose barrier
certificate is of higher relative degree with respect to the dynamics of the
physical subsystem.

##  3\. System and Threat Model

In this section we first give some notations and then describe the system
model. We then present the threat model.

###  3.1. System Model

Throughout this paper, we use $\mathbb{R}$, $\mathbb{R}_{\geq 0}$,
$\mathbb{R}_{>0}$, $\mathbb{Z}$, $\mathbb{Z}_{\geq 0}$, and $\mathbb{Z}_{>0}$
to denote the sets of real numbers, non-negative real numbers, positive real
numbers, integers, non-negative integers, and positive integers, respectively.
Given a vector $x\in\mathbb{R}^{n}$, we denote its $i$-th entry as $[x]_{i}$,
where $i=1,\ldots,n$.

We consider a CPS comprised of a cyber subsystem and a physical subsystem. The
physical subsystem is modeled by a plant that has the dynamics

(1) $\dot{x}_{t}=f(x_{t})+g(x_{t})u_{t},$

where $x_{t}\in\mathcal{X}\subset\mathbb{R}^{n}$ is the system state and
$u_{t}\in\mathcal{U}\subset\mathbb{R}^{m}$ is the control input. Functions
$f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ and
$g:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n\times m}$ are assumed to be
Lipschitz continuous. We also assume that the input set satisfies
$\mathcal{U}=\prod_{i=1}^{m}[u_{i}^{min},u_{i}^{max}]$ with $u_{i}^{min}\leq
u_{i}^{max}$. A control policy $\mu:\mathcal{X}\rightarrow\mathcal{U}$
determines the actuator signal $u_{t}$ given the system state $x_{t}$, so that
$u_{t}=\mu(x_{t})\in\mathcal{U}$ for $x_{t}\in\mathcal{X}$.

Although the physical plant evolves in continuous time, the cyber subsystem
interacts with the physical subsystem at discrete instants of time. That is,
the cyber subsystem reads the measurements of the physical subsystem’s state
and issues control command at discrete time $k\delta$, where
$k\in\mathbb{Z}_{\geq 0}$ and $\delta\in\mathbb{R}_{>0}$. We refer to each
discrete time interval of duration $\delta$ as an _epoch_. The duration
$\delta$ of each epoch is dependent on the controller’s sampling period.

Safety-critical CPS are required to operate within a certain range called as
_safety set_. Here we assume that the safety set of our considered CPS is
given as $\mathcal{C}=\\{x\in\mathcal{X}:h(x)\geq 0\\}$, where
$h:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is a $r$-th order continuously
differentiable function with $r\in\mathbb{Z}_{>0}$.

###  3.2. Threat Model

We consider that there exists an intelligent adversary in the CPS with the
goal of driving the system into unsafe region of operations. The intelligent
adversary can initiate cyber attacks by exploiting vulnerabilities in the
cyber subsystem so as to intrude into the system. Once the adversary completes
intrusion, it then gains access to software, actuator, and other peripherals.
The adversary can then corrupt the actuator signal and arbitrarily manipulate
the control input to be $\tilde{u}_{k\delta}\in\mathcal{U}$ for epoch
$k\in\mathbb{Z}_{\geq 0}$. As a consequence, the system will deviate from the
desired trajectories and may violate the safety constraint. Throughout this
paper, we assume that the adversary cannot physically access the components in
CPS, e.g., physically damage the sensors and plant. We also assume that the
system is not susceptible to external sensor spoofing or jamming attacks.

##  4\. Proposed Cyber Resilient Framework

In this section we first introduce the timing behaviors of the CRAs which will
be incorporated in our framework. Then we propose a hybrid system model to
capture CPS employing different CRAs. Finally we state the problem that we
seek to solve in this paper.

###  4.1. Timing Behaviors

In this subsection, we discuss the timing behaviors of the CPS employing
different CRAs. We first identify a set of statuses of the cyber subsystem. We
then discuss how the system evolves with time by specifying its timing
behavior, which will help us to develop a hybrid system model for CPS that
implements any of these architectures.

Based on the behavior of the cyber subsystem, we identify the statuses of the
system as follows: $normal,corrupted,restart,$
$restoration,safety~{}controller~{}driven(SC)$, $switching$ and $unsafe$. When
the nominal controller is being used and the system is in the safety set
$\mathcal{C}$, the corresponding status is $normal$. In this status the
control input $u$ follows the control policy $\mu(x)$. Status $corrupted$
models the scenario where an adversary successfully intrudes into the system
and corrupts the control input to $\tilde{u}\neq\mu(x)$. Status $restart$
models the system when the controller is in the process of restart and thus
the controller input will be zero during this status. When the CPS restores
the compromised controller using the backup controller of BFT++ in order to
recover from the attack, we model such status as $restoration$. At this
status, the control input will not be accurate since the controller is not
fully recovered from attack, and thus it will deviate from the desired control
signal. Status $SC$ models the system when the safety controller drives the
system. Switching process in dual redundant scheme is modeled as $switching$.
The controller input will also be zero during $switching$. When the system is
in the unsafe region, we model that as $unsafe$. We explicitly include
$unsafe$ status in our model to capture the safety-critical nature of CPS. We
remark that unlike other status in the hybrid model, the status $unsafe$ is
solely based upon the physical states of the system, i.e., whether
$x_{t}\notin\mathcal{C}$.

Now we discuss the evolution of these statuses under attack. Suppose that an
attacker intrudes the system at epoch index $j$ which causes the system status
to change from $normal$ to $corrupted$. The timing behavior of the system
following the intrusion depends upon the employed architecture. When the
system adopts BFT++ (Mertoguno et al., 2019), the CPS will spend $N_{1}$
epochs in the $corrupted$ status until one of the redundant controllers
crashes due to diversity implemented in the controllers, e.g., diversified
software implementation and randomized instruction set. This crash signal will
initiate controller restoration. The system elapses $N_{2}$ epochs in
$restoration$ status during which the compromised controller are restored by
using the backup controller. After restoration, the system will return to the
$normal$ status. In practice, for BFT++ implementation we observe that
$N_{1}=2$ and $N_{2}=2$ in the worst-case scenario (Mertoguno et al., 2019).
Therefore if the physical subsystem can tolerate four epochs of disruption
caused by a cyber attack, the system will remain safe. To withstand
consecutive cyber attacks, the system needs to operate in the $normal$ status
for at least $N_{3}$ epochs.

In the case of YOLO (Arroyo et al., 2019, 2017), it is possible for an
attacker to exploit the vulnerabilities without causing any software crash. We
suppose that the attacker can corrupt the system for at most $N_{4}$ epochs
which is the up-time of the controller. During this $corrupted$ status, the
attacker manipulates the control signal issued by the controller. The
controller will recover by the periodic restart triggered by a timer. The
system will then elapse $N_{5}$ epochs in the $restart$ status in order to
reboot and reinitialize the controller. Note that at the $restart$ status, the
controller does not produce any control input and thus $u=0$. The value of
$N_{5}$ depends on multiple factors including operating system and controller,
but in general $N_{5}>N_{2}$. If the intrusion causes a software crash, then
the system restarts automatically without a trigger coming from the timer. The
restart period for YOLO is given by $N_{4}+N_{5}$ epochs. The timing behavior
of dual redundant scheme (Gamarra et al., 2019) is identical to YOLO except
that the system periodically switches back to the other controller instead of
periodic restart.

Proactive restart mechanism (Abdi et al., 2018; Romagnoli et al., 2019)
utilizes a timer to trigger the $restart$ irrespective of whether the CPS is
corrupted or not. Therefore at the worst case, the system spends $N_{6}$
epochs in the $corrupted$ status which is same as the up-time of the main
controller. The CPS elapses $N_{7}$ epochs in $restart$ status during which a
trusted image of software is loaded from read only memory unit. Unlike YOLO, a
secured execution interval program, modeled as $SC$, is invoked for $N_{8}$
epochs after the restart. During this time all the external interfaces are
disabled, safety controller program is activated, and an external hardware
timer is scheduled for next restart. After the end of this interval, the
system returns to the $normal$ status where the main controller program is
activated and the external interfaces are enabled. Reference (Abdi et al.,
2018) uses online reachability analysis that determines the values of $N_{6}$
and $N_{8}$, whereas (Romagnoli et al., 2019) provides an offline method to
compute these timing parameters.

Unlike proactive restart, reactive restart mechanism does not have any timer
for restart (Niu et al., 2022b). Instead, it relies upon crash signal as the
trigger for restart. The system will remain in the $corrupted$ status for
$N_{9}$ epochs until crash causes the system to restart. During the $restart$
status, the controller will be rebooted and reinitialized, which takes
$N_{10}$ epochs. Then the CPS will resume the $normal$ operation. It is
assumed that there is an exploitation window of $N_{11}$ epochs before which
the adversary cannot intrude the system again (Niu et al., 2022b).

The class of Simplex architectures (Sha, 2001; Bak et al., 2009; Mohan et al.,
2013) relies upon a verified controller which is assumed to be fault- and
attack-free. A trusted decision module decides when the system switches to the
safety controller by monitoring the system states or side channels. Decision
module also decides when the main controller needs to be switched back from
$SC$ to $normal$ where the main controller is active.

###  4.2. Proposed Framework

In this subsection, we first construct a hybrid system to model the CPS
implementing the aforementioned CRAs. Our hybrid system is given by
$H=(\mathcal{X},\mathcal{U},\mathcal{L},\mathcal{Y},\mathcal{Y}_{0},Inv_{x},Inv_{u},\mathcal{F},\allowbreak\Sigma,\Gamma)$
where

  * •

$\mathcal{X}\subseteq\mathbb{R}^{n}$ is the continuous state space that
represents the states of the physical subsystem.

  * •

$\mathcal{U}\subseteq\mathbb{R}^{m}$ is the set of admissible control inputs
of the physical subsystem.

  * •

$\mathcal{L}=\\{normal,corrupted,restart,\allowbreak
restoration,SC,switching,\allowbreak unsafe\\}$ is a set of discrete locations
which corresponds to the statuses of the system. At each epoch, the system
must be at some location $l\in\mathcal{L}$.

  * •

$\mathcal{Y}=\mathcal{X}\times\mathcal{L}$ is the state space of the hybrid
system $H$.

  * •

$\mathcal{Y}_{0}$ is the set of initial states of the hybrid system $H$ where
$\mathcal{Y}_{0}\subset\mathcal{Y}$.

  * •

$Inv_{x}:\mathcal{L}\rightarrow 2^{\mathcal{X}}$ is the invariant that maps
from the set of locations to the power set of $\mathcal{X}$. Function
$Inv_{x}(l)$ specifies the set of possible continuous states when the system
is at $l\in\mathcal{L}$.

  * •

$Inv_{u}:\mathcal{L}\rightarrow 2^{\mathcal{U}}$ is the invariant that maps
from the set of locations to the power set of $\mathcal{U}$. Function
$Inv_{u}(l)$ specifies the set of admissible inputs when the system is at
$l\in\mathcal{L}$.

  * •

$\mathcal{F}$ is the set of vector fields. For each $F\in\mathcal{F}$, the
continuous system state evolves as $\dot{x}=F(x,u,l)$, where $x\in
Inv_{x}(l)$, $u\in Inv_{u}(l)$, and $\dot{x}$ is the time derivative of
continuous state $x$. Here $F$ is jointly determined by the system dynamics
and the status of the cyber subsystem.

  * •

$\Sigma\subseteq\mathcal{Y}\times\mathcal{Y}$ is the set of transitions
between the states of the hybrid system $H$. A transition
$\sigma=((x,l),(x^{\prime},l^{\prime}))$ models the state transition from
$(x,l)$ to $(x^{\prime},l^{\prime})$.

  * •

$\Gamma$ is a finite alphabet set. Each $\gamma\in\Gamma$ is labeled on some
transition $\sigma\in\Sigma$ representing the events that triggers the
transition.

Fig. 1 presents our proposed hybrid model $H$. In the figure, each node
(depicted by circles) represents a location $l\in\mathcal{L}$ and each
directed edge (denoted by arrow) represents a transition $\sigma\in\Sigma$. We
remark that in our setting there is no discontinuity in the physical states
and epoch indices for any of the transitions.

Figure 1. An illustration of the proposed hybrid system model $H$. The
statuses are depicted as circles, and transitions among the statuses are
captured by arrows. This hybrid model captures the evolution of cyber statuses
of the CPS that employ resilient architectures.

Hence for simplicity we will denote a transition
$\sigma=((x,l),(x^{\prime},l^{\prime}))\in\Sigma$ as $(l,l^{\prime})$. Note
that some transitions are valid for specific architectures employed by the
CPS. For example, transition $(corrupted,restoration)$ is valid for BFT++
while the transition from $(corrupted,restart)$ is not. A run (i.e., a
sequence of successive transitions) in the model $H$ determines the evolution
of the CPS statuses with time. Tracking successive transitions in the model
$H$ provides a means to analyze CPS safety.

Transition | Label | Valid Architecture(s)
---|---|---
$(normal,corrupted)$ | $cyber~{}intrusion$ |  | Any CRA
---
(Sha, 2001; Bak et al., 2009; Mohan et al., 2013; Mertoguno et al., 2019;
Arroyo et al., 2019, 2017; Abdi et al., 2018; Romagnoli et al., 2019; Niu et
al., 2022b; Gamarra et al., 2019)
$(corrupted,restoration)$ | $controller~{}crash$ | BFT++ (Mertoguno et al., 2019)
$(restoration,normal)$ | $controller~{}restored$ | BFT++ (Mertoguno et al., 2019)
$(corrupted,restart)$ | $controller~{}crash$ | YOLO (Arroyo et al., 2019, 2017), Reactive Restart (Niu et al., 2022b)
$(corrupted,restart)$ | $restart~{}timer$ | YOLO (Arroyo et al., 2019, 2017), Proactive Restart (Abdi et al., 2018; Romagnoli et al., 2019)
$(normal,restart)$ | $restart~{}timer$ | YOLO (Arroyo et al., 2019, 2017), Proactive Restart (Abdi et al., 2018; Romagnoli et al., 2019)
$(restart,normal)$ | $controller~{}restarted$ | YOLO (Arroyo et al., 2019, 2017), Reactive Restart (Niu et al., 2022b)
$(restart,SC)$ | $controller~{}restarted$ | Proactive Restart (Abdi et al., 2018; Romagnoli et al., 2019)
$(SC,normal)$ | $SEI~{}ended$ | Proactive Restart (Abdi et al., 2018; Romagnoli et al., 2019)
$(normal,switching)$ | $switching~{}timer$ | Dual Redundant (Gamarra et al., 2019)
$(corrupted,switching)$ | $switching~{}timer$ | Dual Redundant (Gamarra et al., 2019)
$(switching,normal)$ | $switching~{}completed$ | Dual Redundant (Gamarra et al., 2019)
$(corrupted,SC)$ | $safety~{}controller~{}invoked$ | Simplex/S3A (Sha, 2001; Bak et al., 2009; Mohan et al., 2013)
$(SC,normal)$ | $main~{}controller~{}invoked$ | Simplex/S3A (Sha, 2001; Bak et al., 2009; Mohan et al., 2013)
$(l,unsafe)_{l\neq unsafe}$ | $safety~{}region~{}crossed$ |  | Any CRA
---
(Sha, 2001; Bak et al., 2009; Mohan et al., 2013; Mertoguno et al., 2019;
Arroyo et al., 2019, 2017; Abdi et al., 2018; Romagnoli et al., 2019; Niu et
al., 2022b; Gamarra et al., 2019)
Table 1. Transitions in the hybrid system model $H$. For each transition in
the first column, the corresponding label and the corresponding architectures
for which the transition is valid are listed in the second and third column
respectively.

Each transition is labeled with an alphabet set $\gamma\in\Gamma$ where
$\gamma$ represents the event that triggers the transition. For example, the
transition $(normal,corrupted)$ is triggered by a cyber intrusion whereas the
transition $(corrupted,restoration)$ is triggered by a controller crash. The
details of all labels and corresponding transitions are given in Table 1.

In Fig. 1, we observe that location $l=unsafe$ is absorbing since it has an
incoming edge from each other node and does not have any outgoing edge. It
implies that if the CPS ever transits to $l=unsafe$, it will remain there
since safety constraint has been violated. Thus our focus in this study is to
avoid any run on the hybrid model $H$ that reaches $l=unsafe$.

###  4.3. Problem Formulation

This subsection states the problem of interest. We consider the hybrid system
$H$ that represents the CPS employing any of the CRAs. Let $t_{1}$ be the time
instant when the system transits to $corrupted$ status triggered by a cyber
intrusion. The CRAs employed by the system tries to recover the system so that
the system goes back to $normal$ status at some time instant
$\tilde{t}>t_{1}$. Let $t_{2}$ be the first time when the system again
transits to $corrupted$ status following a new cyber intrusion where
$t_{2}\geq\tilde{t}$. We define the time interval $[t_{1},t_{2}]$ as an
_attack cycle_. The length $A=t_{2}-t_{1}$ of each attack cycle varies and is
dependent on the capabilities of the adversary and the vulnerability of cyber
subsystem. Here we focus on guaranteeing the system safety for an arbitrary
attack cycle and thus for all time $t\geq 0$. Our problem in this paper is
formalized as follows:

###### Problem 4.1.

Synthesize a control policy
$\mu:\mathcal{X}\times\\{normal,SC\\}\rightarrow\mathcal{U}$ and design the
timing parameters for the CPS such that the system never reaches the location
$l=unsafe$ during an attack cycle.

Here the timing parameters quantify how many epochs the system can remain at
each status. The above problem is equivalent to computing a control policy and
the timing parameters such that
$x_{t}\in\mathcal{C}~{}~{}\forall[t_{1},t_{2}]$. Our method for computation of
the control policy and timing parameters is detailed in Section 5.

##  5\. Proposed Solution Approach

In this section, we first provide some preliminary background on barrier
certificates and sum-of-squares polynomials. Then we present our proposed
solution to the Problem 4.1.

###  5.1. Preliminaries

In this subsection, we present necessary preliminaries which will be useful in
deriving our solution to the formulated problem. A continuous function
$\alpha:[-b,a)\rightarrow(-\infty,\infty)$ belongs to the extended class
$\mathcal{K}$ if it is strictly increasing and $\alpha(0)=0$ for some $a,b>0$.
A set $\mathcal{C}$ is called forward invariant if
$x_{t}\in\mathcal{C}~{}~{}\forall t\geq t_{0}$ given that
$x_{t_{0}}\in\mathcal{C}$.

The Lie derivative of function $h(x)$ with respect to dynamics (1) is given by
$L_{f}h(x)+L_{g}h(x)u$ where $L_{f}h(x)=\frac{\partial h}{\partial x}(x)f(x)$
and $L_{g}h(x)=\frac{\partial h}{\partial x}(x)g(x)$ denote the Lie
derivatives along $f(x)$ and $g(x)$ respectively. The higher order Lie
derivatives of $h(x)$ along $f(x)$ are obtained inductively via
$L_{f}^{i}h(x)=L_{f}L_{f}^{i-1}h(x)$ where $i\in\mathbb{Z}_{>0}$ and
$L_{f}^{0}h(x)=h(x)$. _Relative degree_ of a continuously differentiable
function on a set with respect to a dynamics is defined by the minimum number
of times Lie derivatives of the function needs to be taken along the dynamics
such that control input explicitly appears in the expression (Khalil, 1996;
Wang et al., 2021). This is formally defined as follows:

###### Definition 5.1 ((Khalil, 1996; Wang et al., 2021)).

The relative degree of a function $h(x)$ is $r\in\mathbb{Z}_{>0}$ on the set
$\mathcal{X}$ with respect to dynamics (1) if $h(x)$ is $r$-th order
continuously differentiable on $\mathcal{X}$ and $L_{g}L_{f}^{r-1}h(x)\neq 0$
and $L_{g}L_{f}^{i}h(x)=0$ for all $i\in\\{0,1,\cdots,r-2\\}$ and for all
$x\in\mathcal{X}$.

In this paper, we denote the $i$-th order Lie derivative of $h(x)$ as
$h^{i}(x)$. We abuse this notation by assuming $h^{i}(x)=h(x)$ when $i=0$.
Note that we can write $h^{i}(x)=L_{f}^{i}h(x),~{}~{}\forall i=\\{0,1,\cdots
r-1\\}$ and $h^{r}(x)=L_{f}^{r}h(x)+L_{g}L_{f}^{r-1}h(x)\mu(x)$ given that the
relative degree of $h(x)$ is $r$ and $u$ follows some control policy $\mu(x)$.

A multivariate polynomial $p(x)$ is a sum-of-squares (SOS) polynomial if there
exists a set of polynomials $q_{1}(x),q_{2}(x),\cdots,q_{l}(x)$ such that
$p(x)=\sum_{i=1}^{l}(q_{i}(x))^{2}$. If $p(x)$ is a SOS polynomial then we
have that $p(x)\geq 0$. SOS and non-negativity are equivalent when the
polynomial is quadratic or univariate (Powers, 2011). In this paper, we denote
the set of SOS polynomials over $x\in\mathbb{R}^{n}$ as $\mathcal{S}(x)$.

###  5.2. Control Synthesis and Timing Parameters Design for Safety

In this subsection, we present our proposed solution approach to control
synthesis and timing parameters design for the system’s safety. We first
derive a set of sufficient conditions for a control policy along with timing
parameters so that safety of the CPS is guaranteed. Next we encode the derived
conditions as a set of sum-of-squares (SOS) constraints under certain
assumptions. Using the SOS formulation, we propose an algorithm to compute the
control policy and associated timing parameters. We also analyze convergence
of our proposed algorithm.

Recall that safety of the CPS is defined over a set
$\mathcal{C}=\\{x\in\mathcal{X}:h(x)\geq 0\\}$. We suppose that the relative
degree of the function $h(x)$ on set $\mathcal{C}$ with respect to dynamics
(1) is $r$. When $r>1$, the control input $u$ does not appear in the first
order Lie derivative of $h(x)$ since $L_{g}h(x)=0$. In that case, solution
methods based on first order Lie derivative of $h(x)$ (Niu et al., 2022a, b)
are not applicable to guarantee safety anymore. To address this limitation,
here we derive sufficient conditions for control policy which holds for any
$r\in\mathbb{Z}_{>0}$. To do so, we first derive a result on the forward
invariance of a function for higher order Lie derivatives. We present the
result below.

###### Lemma 5.2.

Let $\mathcal{A}=\\{x_{t}:h(x_{t})\geq c_{0}\\}\cap\\{x:h^{1}(x_{t})\geq
c_{1}\\}\cap\cdots\cap\\{x_{t}:h^{p-1}(x_{t})\geq c_{p-1}\\}$ for some
$c_{0},c_{1},\cdots,c_{p-1}\geq 0$ and $p=1,2,\cdots,r$ where $r$ is the
relative degree of $h(x)$ on the set $\mathcal{C}$ with respect to dynamics
(1). If $h^{p}(x_{t})+\alpha(h^{p-1}(x_{t})-c_{p-1})\geq 0$ holds for all
$x_{t}\in\mathcal{A}$, then $\mathcal{A}$ is forward invariant. That is,
$x_{t}\in\mathcal{A}$ for all $t\geq t_{0}$ given that
$x_{t_{0}}\in\mathcal{A}$.

###### Proof.

We denote the boundary of a set $\mathcal{A}_{i}=\\{x:h^{i}(x_{t})\geq
c_{i}\\}$ as

$\partial\mathcal{A}_{i}=\\{x:h^{i}(x_{t})=c_{i}\\},~{}~{}\forall
i=0,1,\cdots,p-1.$

Suppose $x_{t_{0}}\in\mathcal{A}$. Note that when
$x_{t}\in\partial\mathcal{A}_{p-1}\cap\mathcal{A}$, we get
$h^{p}(x_{t})\geq-\alpha(0)=0$ which implies $h^{p-1}(x_{t})\geq
c_{p-1}~{}~{}\forall t\geq t_{0}$. This also implies the proof is complete for
the case $p=1$. Now we consider the case $p\geq 2$. For this we first show
that $h^{i}(x_{t})\geq c_{i},~{}~{}\forall t\geq t_{0},~{}~{}\forall
i=0,1,\cdots,p-2$. Since $c_{0},c_{1},\cdots,c_{p-1}\geq 0$, we have that
$h^{i}(x_{t})\geq 0~{}~{}\forall i=0,1,\cdots,p-1$ if $x_{t}\in\mathcal{A}$.
Now consider the case where $x_{t}\in\partial\mathcal{A}_{i}\cap\mathcal{A}$
for any $i=0,1,\cdots,p-2$. Since we have $h^{i+1}(x_{t})\geq 0$, according to
Nagumo’s theorem (Blanchini and Miani, 2008), we have that $h^{i}(x_{t})\geq
c_{i},~{}~{}\forall t\geq t_{0}$. Since this holds for any $i=0,1,\cdots,p-2$
and previously we have shown that $h^{p-1}(x_{t})\geq c_{p-1},~{}~{}\forall
t\geq t_{0}$, hence we conclude that $x_{t}\in\mathcal{A}$ for all $t\geq
t_{0}$. This completes the proof for $p=1,2,\cdots,r$. ∎

Now using the above result we will derive sufficient conditions for a control
policy to ensure safety in the presence of cyber attack, considering that the
policy is implemented as specified by the timing parameters. We will derive
the conditions which can be applied to any CPS regardless of its resilient
architecture. We will consider an arbitrary run on the hybrid system $H$ that
can possibly visit any number of locations before returning to $normal$ for
the purpose of generality. This run starts from the $corrupted$ location
following a cyber attack. Our objective is to find a level set $\mathcal{A}$
and control policy $\mu(x)$ for the recovered or safety controller so that the
CPS remains safe (i.e., never reach the location $l=unsafe$) during any attack
cycle. We also enforce that the CPS returns to the computed level set
$\mathcal{A}$ so that safety of the CPS can be guaranteed for consecutive
attacks. Our derived conditions are presented in the following theorem.

###### Theorem 5.3.

Consider the hybrid model $H$ from Section 4. Let $\mathcal{A}$ be a level set
defined over higher order Lie derivatives of $h(x)$ as

$\mathcal{A}=\\{x:h(x)\geq c_{0}\\}\cap\\{x:L_{f}h(x)\geq
c_{1}\\}\cap\cdots\cap\\{x:L_{f}^{r-1}h(x)\geq c_{r-1}\\}$

for some $c_{0},c_{1},\cdots,c_{r-1}\geq 0$. Consider an attack cycle
$[t_{1},t_{2}]$ for which the system undergoes a sequence of successive
transitions $(l_{1},l_{2})$,$(l_{2},l_{3}),\cdots$, $(l_{k-1},l_{k})$ in the
hybrid model until the controllers are recovered or safety controller is
invoked, where $l_{1}=corrupted$. Let
$\tau_{1},\tau_{2},\cdots,\tau_{k}+\Delta$ be the amount of time elapsed in
each locations $l_{1},l_{2},\cdots,l_{k}$, respectively, where
$\Delta=(t_{2}-t_{1})-\sum_{i=1}^{k}\tau_{i}\geq 0$. If there exist constants
$s_{1},s_{2},\cdots,s_{k}$ and a control policy $\mu(x)\in Inv_{u}(l_{k})$
which is applied at location $l_{k}$ such that

(2a) $\displaystyle L_{f}^{r}h(x)+L_{g}L_{f}^{r-1}h(x)u-s_{j}\geq
0,~{}~{}~{}~{}\forall(x,u)\in\mathcal{C}\times Inv_{u}(l_{j}),\forall
j=1,2,\cdots,k-1$ (2b) $\displaystyle
L_{f}^{r}h(x)+L_{g}L_{f}^{r-1}h(x)\mu(x)-s_{k}\geq 0,~{}~{}~{}~{}\forall
x\in\mathcal{C}\backslash\mathcal{A}$ (2c) $\displaystyle
L_{f}^{r}h(x)+L_{g}L_{f}^{r-1}h(x)\mu(x)+\alpha(L_{f}^{r-1}h(x)-a_{0,r-1})\geq
0,~{}~{}~{}~{}\forall x\in\mathcal{A}$ (2d)
$\displaystyle\sum_{i=1}^{r}\frac{a_{j-1,r-i}(t-\xi_{j})^{r-i}}{(r-i)!}+\frac{s_{j}(t-\xi_{j})^{r}}{r!}\geq
0,~{}~{}~{}~{}\forall t\in[\xi_{j},\xi_{j+1}],\forall j=1,2,\cdots,k$ (2e)
$\displaystyle a_{k,r-p}\geq a_{0,r-p},~{}~{}~{}~{}\forall p=1,2,\dots,r$

where

(3a) $\displaystyle a_{0,i}=c_{i},\forall i=0,1,\dots,r-1$ (3b) $\displaystyle
a_{j,r-p}=\sum_{i=1}^{p}\frac{a_{j-1,r-i}\tau_{j}^{p-i}}{(p-i)!}+\frac{s_{j}\tau_{j}^{p}}{p!},~{}~{}~{}~{}\forall
p=1,2,\dots,r;~{}~{}\forall j=1,2,\dots,k$ (3c)
$\displaystyle\xi_{j}=\sum_{i=0}^{j-1}\tau_{i},~{}~{}~{}~{}\forall
j=1,2,\dots,k+1~{}~{}\text{with}~{}~{}\tau_{0}=t_{1}.$

then the system (1) is safe i.e., $x_{t}\in\mathcal{C},~{}~{}\forall
t\in[t_{1},t_{2}]$ given that $x_{t_{1}}\in\mathcal{A}$. Furthermore,
$x_{t}\in\mathcal{A}$ for $t\in[\xi_{k+1},t_{2}]$.

###### Proof.

From the statement of the theorem, we suppose that $x_{t_{1}}\in\mathcal{A}$,
which implies

$h(x_{t_{1}})\geq c_{0}=a_{0,0},\quad h^{1}(x_{t_{1}})\geq
c_{1}=a_{0,1},~{}\cdots,~{}h^{r-1}(x_{t_{1}})\geq c_{r-1}=a_{0,r-1}.$

First consider the case where the system is at location $l_{1}$. Since
$h^{r}(x)=L_{f}^{r}h(x)+L_{g}L_{f}^{r-1}h(x)u$, therefore by taking
integration over $h^{r}(x_{t})$ and using (2a) with $j=1$, we can write for
all $(x,u)\in\mathcal{C}\times Inv_{u}(l_{1})$ and
$t\in[t_{1},t_{1}+\tau_{1}]=[\xi_{1},\xi_{2}]$

(4)
$h^{r-1}(x_{t})=h^{r-1}(x_{\xi_{1}})+\int_{t=\xi_{1}}^{t}h^{r}(x_{t})~{}~{}dt\geq
a_{0,r-1}+s_{1}(t-\xi_{1})$

By taking integration over $h^{r-1}(x_{t})$, we have that for all
$(x,u)\in\mathcal{C}\times Inv_{u}(l_{1})$ and $t\in[\xi_{1},\xi_{2}]$

$\displaystyle h^{r-2}(x_{t})$
$\displaystyle=h^{r-2}(x_{\xi_{1}})+\int_{t=\xi_{1}}^{t}h^{r-1}(x_{t})~{}~{}dt$
(5) $\displaystyle\geq
a_{0,r-2}+\int_{t=\xi_{1}}^{t}\big{(}a_{0,r-1}+s_{1}(t-\xi_{1})\big{)}~{}dt=a_{0,r-2}+a_{0,r-1}(t-\xi_{1})+\frac{s_{1}(t-\xi_{1})^{2}}{2}$

where the inequality follows from (4) and the fact that
$h^{r-2}(x_{\xi_{1}})\geq c_{r-2}=a_{0,r-2}$. Thus if we continue this by
inductively taking integration over $h^{r}(x_{t})$ for $p$ times where
$p=1,2,\dots,r$, we have that for all $(x,u)\in\mathcal{C}\times
Inv_{u}(l_{1})$ and $t\in[\xi_{1},\xi_{2}]$

(6)
$h^{r-p}(x_{t})\geq\sum_{i=1}^{p}\frac{a_{0,r-i}(t-\xi_{1})^{p-i}}{(p-i)!}+\frac{s_{1}(t-\xi_{1})^{p}}{p!}$

From (6), (3b) and (3c) we have that for all $p=1,2,\dots,r$

(7)
$h^{r-p}(x_{\xi_{2}})\geq\sum_{i=1}^{p}\frac{a_{0,r-i}(\xi_{2}-\xi_{1})^{p-i}}{(p-i)!}+\frac{s_{1}(\xi_{2}-\xi_{1})^{p}}{p!}=\sum_{i=1}^{p}\frac{a_{0,r-i}{\tau_{1}}^{p-i}}{(p-i)!}+\frac{s_{1}{\tau_{1}}^{p}}{p!}=a_{1,r-p}$

Furthermore, by letting $r=p$ in (6) and using (2d) with $j=1$ we get for all
$t\in[\xi_{1},\xi_{2}]$

(8)
$h(x_{t})\geq\sum_{i=1}^{r}\frac{a_{0,r-i}(t-\xi_{1})^{r-i}}{(r-i)!}+\frac{s_{1}(t-\xi_{1})^{r}}{r!}\geq
0$

Therefore, $x(t)\in\mathcal{C},~{}~{}\forall t\in[\xi_{1},\xi_{2}]$. Now
consider the case where the system is at location $l_{2}$. Taking integration
over $h^{r}(x_{t})$ and using (2a) with $j=2$, we can write for all
$(x,u)\in\mathcal{C}\times Inv_{u}(l_{2})$ and $t\in[\xi_{2},\xi_{3}]$

(9)
$h^{r-1}(x_{t})=h^{r-1}(x_{\xi_{2}})+\int_{t=\xi_{2}}^{t}h^{r}(x_{t})~{}~{}dt\geq
a_{1,r-1}+s_{2}(t-\xi_{2})$

The last inequality follows from (7) by letting $p=1$. Similar to before, by
repeated integration we can write for all $(x,u)\in\mathcal{C}\times
Inv_{u}(l_{2})$, $t\in[\xi_{2},\xi_{3}]$ and $p=1,2,\dots,r$

(10)
$h^{r-p}(x_{t})\geq\sum_{i=1}^{p}\frac{a_{1,r-i}(t-\xi_{2})^{p-i}}{(p-i)!}+\frac{s_{2}(t-\xi_{2})^{p}}{p!}$

Similar to before, from (10), (3b) and (3c) we have that
$h^{r-p}(x_{\xi_{3}})\geq a_{2,r-p}$ for all $p=1,\dots,r$. Also by letting
$r=p$ in (10) and using (2d) with $j=2$, we get $h(x_{t})\geq 0$ for all
$t\in[\xi_{2},\xi_{3}]$.

If we continue the above steps for locations $l_{3},\cdots,l_{k-1}$ we can
show that for all $(x,u)\in\mathcal{C}\times Inv_{u}(l_{j})$ and
$t\in[\xi_{j},\xi_{j+1}]$ where $j=1,2,\cdots,k-1$ and $p=1,2,\cdots,r$

(11)
$h^{r-p}(x_{t})\geq\sum_{i=1}^{p}\frac{a_{j-1,r-i}(t-\xi_{j})^{p-i}}{(p-i)!}+\frac{s_{j}(t-\xi_{j})^{p}}{p!},$

$h^{r-p}(x_{\xi_{j+1}})\geq a_{j,r-p}$ and $h(x_{t})\geq 0$ i.e.
$x(t)\in\mathcal{C}$.

Now consider the case when the system is at location $l_{k}$ where control
policy $\mu(x)$ is applied. Integrating (2b) for $p$ times and using the fact
$h^{r-p}(x_{\xi_{j+1}})\geq a_{j,r-p}$ where $j=1,2,\cdots,k-1$ and
$p=1,2,\cdots,r$, we can write for all $x\in\mathcal{C}\backslash\mathcal{A}$
and $t\in[\xi_{k},\xi_{k+1}]\cup[\xi_{k+1},\xi_{k+1}+\Delta]=[\xi_{k},t_{2}]$

(12)
$h^{r-p}(x_{t})\geq\sum_{i=1}^{p}\frac{a_{k-1,r-i}(t-\xi_{k})^{p-i}}{(p-i)!}+\frac{s_{k}(t-\xi_{k})^{p}}{p!}$

Now (12) and (2d) with $j=k$ implies that $h(x_{t})\geq 0$, i.e.,
$x(t)\in\mathcal{C},~{}~{}\forall t\in[\xi_{k},\xi_{k+1}]$. Furthermore from
(12), (3b) and (3c) we get that $h^{r-p}(x_{\xi_{k+1}})\geq
a_{k,r-p}~{}~{}\forall p=1,2,\dots,r$. This along with (2e) imply that for all
$p=1,\dots,r$

$h^{r-p}(x_{\xi_{k+1}})\geq a_{k,r-p}\geq a_{0,r-p}=c_{r-p}.$

Therefore, $x(\xi_{k+1})\in\mathcal{A}$. By using (2c) and applying Lemma 5.2
with $p=r$, we get that $x_{t}\in\mathcal{A},~{}~{}\forall
t\in[\xi_{k+1},t_{2}]=[t_{2}-\Delta,t_{2}]$. Since
$\mathcal{A}\subset\mathcal{C}$ and
$\cup_{i=1}^{k}[\xi_{i},\xi_{i+1}]\cup[\xi_{k+1},t_{2}]=[t_{1},t_{2}]$,
thereby $x_{t}\in\mathcal{C},~{}~{}\forall[t_{1},t_{2}]$, which completes the
proof. ∎

The above theorem gives a set of sufficient conditions for control policy and
timing parameters of any employed CRA so that safety of the CPS is guaranteed.
The value of $k$, the locations $l_{1},l_{2},\cdots,l_{k}$ and the timing
parameters $\tau_{1},\tau_{2},\cdots,\tau_{k}$ depend on the architecture
adopted by the CPS. For example, for BFT++ we have $k=3$, $l_{1}=corrupted$,
$l_{2}=restoration$, $l_{3}=normal$, $\tau_{1}=N_{1}$ epochs, $\tau_{2}=N_{2}$
epochs and $\tau_{3}=N_{3}$ epochs. Therefore at $l=normal$ location the
restored controller needs to apply the control policy $\mu(x)$ for at least
$\tau_{3}$ time to guarantee safety. As the system returns to the level set
$\mathcal{A}$ within one attack cycle, safety is also ensured for consecutive
attacks as long as the attack cycle is greater than
$\tau_{1}+\tau_{2}+\tau_{3}$. The mapping between the arbitrary parameters
$\tau_{1},\tau_{2},\cdots,\tau_{k}$ in Theorem 5.3 and the timing parameters
of CRAs is discussed in detail later in Table 2.

Conditions given in Theorem 5.3 are more general than those derived in (Niu et
al., 2022b, a) as it applies to the cases where relative degree $r>1$ and
number of locations $k>3$. We can derive simpler form of Theorem 5.3 by using
specific values of $r$ and $k$. For example, by letting $r=1$ and $k=2$ we can
recover the result in (Niu et al., 2022a) for hard safety constraint. This
simplified form can be used for the worst-case analysis of a CPS with relative
degree one by considering that control input at any location
$l\in\\{corrupted,restoration,restart,switching\\}$ are malicious. Such result
is given as below.

###### Corollary 5.4.

For the hybrid system model $H$ from Section 4, let $\mathcal{A}$ be a level
set defined as $\mathcal{A}=\\{x:h(x)\geq c\\}$. Consider an attack cycle
$[t_{1},t_{2}]$ where control input is malicious for $\eta$ time until the
controller recovers. If there exist constants $c\geq 0$ and a control policy
$\mu:\mathcal{X}\rightarrow\mathcal{U}$ such that

(13a) $\displaystyle\frac{\partial h}{\partial
x}(x)(f(x)+g(x)u)+\frac{c}{\eta}\geq
0,~{}\forall(x,u)\in\mathcal{C}\times\mathcal{U}$ (13b)
$\displaystyle\frac{\partial h}{\partial
x}(x)(f(x)+g(x)\mu(x))-\frac{c}{\tau}\geq 0,~{}\forall
x\in\mathcal{C}\setminus\mathcal{A}$ (13c) $\displaystyle\frac{\partial
h}{\partial x}(x)(f(x)+g(x)\mu(x))+\alpha(h(x)-c)\geq 0,~{}\forall
x\in\mathcal{A}$

then the system (1) is safe i.e. $x_{t}\in\mathcal{C},~{}~{}\forall
t\in[t_{1},t_{2}]$ by taking policy $\mu$ as desired control input given that
$x_{t_{1}}\in\mathcal{A}$ and $\eta+\tau\leq t_{2}-t_{1}$. Furthermore,
$x_{t}\in\mathcal{A}$ for all $t\in[t_{1}+\eta+\tau,t_{2}]$.

###### Proof.

We can prove the corollary by substituting $r=1$, $k=2$, $l_{1}=corrupted,$
$l_{2}=normal$, $c_{0}=c$, $\tau_{1}=\eta$, $\tau_{2}=\tau$,
$s_{1}=-\frac{c}{\eta}$ and $s_{2}=\frac{c}{\tau}$ into Theorem 5.3. In this
case we note that (13a), (13b) and (13c) are directly obtained from (2a), (2b)
and (2c). Condition (2d) becomes trivial for $j=1$ since
$c-\frac{c}{\eta}(t-t_{1})\geq 0,~{}~{}\forall
t\in[\xi_{1},\xi_{2}]=[t_{1},t_{1}+\eta]$. For $j=2$, condition (2d) is again
trivially satisfied since $a_{1,0}=0$ and $s_{2}\geq 0$. Similarly, condition
(2e) becomes trivial as it yields $c\geq c$. Thus conditions (13) are
sufficient which completes the proof. ∎

The conditions presented in Theorem 5.3 and Corollary 5.4 focus on stringent
safety constraints. We remark that our approach can be readily extended to
derive sufficient conditions for control policies under which the CPS is
allowed to operate outside the safety set $\mathcal{C}$ at the expense of
incurring cost (Niu et al., 2022a). The cost is given by a non-decreasing
function $J$ such that $J(h(x_{t}))\geq 0$ if $h(x_{t})\leq 0$ and zero
otherwise. In this case the goal is to synthesize a control policy that
satisfies a budget constraint $B$ on the total incurred cost

$\int_{t=t_{1}}^{t_{2}}J(h(x_{t})~{}~{}dt\leq B.$

We can achieve this by omitting the condition (2d) in Theorem 5.3 and
replacing $\mathcal{C}$ with $\mathcal{D}=\\{x\in\mathcal{X}:h(x)\geq-d\\}$
for some $d\geq 0$ in the conditions (2a) and (2b). We then compute the upper
bound on incurred cost by utilizing the fact that

$h(x_{t})\geq\sum_{i=1}^{r}\frac{a_{j-1,r-i}(t-\xi_{j})^{r-i}}{(r-i)!}+\frac{s_{j}(t-\xi_{j})^{r}}{r!}$

for all $j=1,\cdots,k$ and for all $t\in[\xi_{1},\xi_{k+1}]$. This bound can
be encoded as a constraint given as

$\sum_{j=1}^{k}\int_{t=\xi_{j}}^{\xi_{j+1}}J(\sum_{i=1}^{r}\frac{a_{j-1,r-i}(t-\xi_{j})^{r-i}}{(r-i)!}+\frac{s_{j}(t-\xi_{j})^{r}}{r!})~{}~{}dt\leq
B$

when synthesizing the control policy. Since for safety-critical CPS the safety
requirements are stringent, we omit consideration of this soft constraint case
in our development.

In the following, we investigate how to synthesize the control policy $\mu$
and other corresponding parameters, e.g., $c_{1},\cdots,c_{r}$,
$\tau_{1},\cdots,\tau_{k}$ to guarantee safety of the CPS. Our approach is to
translate the inequality conditions given in Theorem 5.3 into SOS constraints
and then use SOS program. To do so, we will make following assumption.

###### Assumption 5.1.

We assume that functions $f(x)$, $g(x)$, and $h(x)$ are polynomial in $x$.

The assumption above allows us to derive SOS formulation of Theorem 5.3. The
SOS formulation is given by the following result.

###### Proposition 5.5.

Suppose there exist parameters $c_{0},c_{1},\cdots,c_{r-1}\geq 0$;
$\tau_{1},\tau_{2},\cdots,\tau_{k}\geq 0$, and $s_{1},s_{2}\cdots,s_{k}$ such
that

$\displaystyle L_{f}^{r}h(x)+L_{g}L_{f}^{r-1}h(x)u-s_{j}-q_{j}(x,u)h(x)$ (14a)
$\displaystyle-\sum_{i=1}^{m}\Big{(}w_{j,i}(x,u)([u]_{i}-[u]_{l_{j},i}^{min})+v_{j,i}([u]_{l_{j},i}^{max}-[u]_{i})\Big{)}\in\mathcal{S}(x,u),\forall
j=1,2,\cdots,k-1$ (14b) $\displaystyle
L_{f}^{r}h(x)+L_{g}L_{f}^{r-1}h(x)\lambda(x)-s_{k}+\sum_{i=0}^{r-1}p_{i}(x)(L_{f}^{i}h(x)-a_{0,i})-l(x)h(x)\in\mathcal{S}(x)$
(14c) $\displaystyle
L_{f}^{r}h(x)+L_{g}L_{f}^{r-1}h(x)\lambda(x)+\alpha(L_{f}^{r-1}(x)-a_{0,r-1})-\sum_{i=0}^{r-1}z_{i}(x)(L_{f}^{i}h(x)-a_{0,i})\in\mathcal{S}(x)$
(14d)
$\displaystyle\lambda_{i}(x)-[u]_{l_{k},i}^{min}\in\mathcal{S}(x),\quad[u]_{l_{k},i}^{max}-\lambda_{i}(x)\in\mathcal{S}(x),~{}\forall
i=1,2,\cdots,m,$ (14e)
$\displaystyle\sum_{i=1}^{r}\frac{a_{j-1,r-i}(t-\xi_{j})^{r-i}}{(r-i)!}+\frac{s_{j}(t-\xi_{j})^{r}}{r!}-\phi_{j}(t)(t-\xi_{j})+\psi_{j}(t)(t-\xi_{j+1})\in\mathcal{S}(t),~{}~{}\forall
j=1,2,\cdots,k$

and the following inequality holds:

(15) $a_{k,r-p}\geq a_{0,r-p},~{}~{}~{}~{}\forall p=1,2,\dots,r$

where $a_{j,i}~{}~{}\forall j=0,1,\cdots,k$ $~{}~{}\forall
i=0,1,\cdots,r-1~{}~{}$, and $\xi_{j}~{}~{}\forall j=0,1,\cdots,k+1$ are given
by (3) and $l(x),p_{i}(x),z_{i}(x)\in\mathcal{S}(x)~{}~{}~{}~{}\forall
i=0,1,\dots,r-1$; $\lambda_{i}(x)$ is a polynomial in $x$ for each
$i=1,\ldots,m$;
$q_{j}(x,u),w_{j,i}(x,u),v_{j,i}(x,u)\in\mathcal{S}(x,u),~{}~{}~{}~{}\forall
i=1,2,\ldots,m$ $~{}~{}\forall j=1,2,\cdots,k-1$ and
$\phi_{j}(t),\psi_{j}(t)\in\mathcal{S}(t)$, $\forall j=1,2,\cdots,k$. Then the
control policy
$\mu(x)=\lambda(x)=[\lambda_{1}(x),\ldots,\lambda_{m}(x)]^{\top}$ satisfies
the conditions in (2) for the parameters $c_{0},c_{1},\cdots,c_{r-1}$;
$\tau_{1},\tau_{2},\cdots,\tau_{k}$ and $s_{1},s_{2}\cdots,s_{k}$.

###### Proof.

First we will show that (14) implies (2a). Consider $x\in\mathcal{C}$ and
$u\in Inv_{u}(l_{j})$ which implies
$[u]_{l_{j},i}^{min}\leq[u]_{i}\leq[u]_{l_{j},i}^{max},\forall i=1,\ldots,m$
where $j=1,2,\cdots,k-1$. Therefore we have that $h(x)\geq 0$,
$[u]_{i}-[u]_{l_{j},i}^{min}\geq 0$ and $[u]_{l_{j},i}^{max}-[u]_{i}\geq 0$.
Due to (14) and the condition that $q_{j}(x,u)$, $w_{j,i}(x,u)$, and
$v_{j,i}(x,u)$ are SOS for all $i=1,\ldots,m$ and $j=1,2,\cdots,k-1$, we have
that for all $(x,u)\in\mathcal{C}\times Inv_{u}({l_{j}})$ the following
relation holds:

$L_{f}^{r}h(x)+L_{g}L_{f}^{r-1}h(x)u-s_{j}\geq q_{j}(x,u)h(x)\\\
+\sum_{i=1}^{m}\Big{(}w_{j,i}(x,u)([u]_{i}-[u]_{l_{j},i}^{min})+v_{j,i}([u]_{l_{j},i}^{max}-[u]_{i})\Big{)}\geq
0,~{}~{}\forall j=1,2,\cdots,k-1.$

Hence condition (2a) holds. Now consider
$x\in\mathcal{C}\backslash\mathcal{A}$. Then we have that $h(x)\geq 0$ and
$(L_{f}^{i}h(x)-a_{0,i})=(L_{f}^{i}h(x)-c_{i})\leq 0~{}~{}\forall
i=0,1,\cdots,r-1$. Using (14b) and the fact that $l(x,u)$ and $p_{i}(x,u)$ are
SOS for all $i=1,2,\ldots,m$, for all $x\in\mathcal{C}\backslash\mathcal{A}$
we can write

(16) $L_{f}^{r}h(x)+L_{g}L_{f}^{r-1}h(x)\lambda(x)-s_{k}\geq
l(x)h(x)-\sum_{i=0}^{r-1}p_{i}(x)(L_{f}^{i}h(x)-a_{0,i})\geq 0.$

Thus condition (2b) holds as (14d) ensures that
$[u]_{l_{k},i}^{min}\leq\lambda_{i}(x)\leq[u]_{l_{k},i}^{max},~{}~{}\forall
i=1,2,\ldots,m$, i.e., $\mu(x)=\lambda(x)\in Inv_{u}(l_{k})$. In the same
manner it can be shown that (14c) and (14e) imply (2c) and (2d), respectively.
Thus proof is completed. ∎

The above SOS formulation allows us to construct an algorithm for computing
control policy and the other parameters as shown in Algorithm 1. In Algorithm
1, we search for $c_{0},c_{1},\cdots,c_{r-1}$ from $(0,0,\cdots,0)$ to
$(c_{0}^{max},c_{1}^{max},\cdots,c_{r-1}^{max})$ where
$c_{0}^{max},c_{1}^{max},\cdots,c_{r-1}^{max}$ respectively denotes selected
upper bound on $h(x),$ $h^{1}(x),\cdots,h^{r-1}(x)$ in the set $\mathcal{C}$.
The order and step sizes in the update of these parameters are chosen
appropriately. Next, for the selected values of $c_{0},c_{1},\cdots,c_{r-1}$,
we compute $s_{i}$ for all $i=1,2,\cdots,s_{k}$ and $\mu(x)$ so that the
conditions (14), (14c) and (14d) are satisfied. Then we search for
$(\tau_{1},\tau_{2},\cdots,\tau_{k})$ from
$(\tau_{1}^{max},\tau_{2}^{max},\cdots,$ $\tau_{k}^{min})$ to
$(\tau_{1}^{min},\tau_{2}^{min},\cdots,$ $\tau_{k}^{max})$ and check whether
the condition (15) is satisfied. If it is satisfied, obtained $\mu(x)$ is the
desired control policy. But if (15) is not satisfied for any choice of
$(\tau_{1},\tau_{2},\cdots,\tau_{k})$, then $c_{0},c_{1},\cdots,c_{r-1}$ are
updated until a solution is found or
$(c_{0}^{max},c_{1}^{max},\cdots,c_{r-1}^{max})$ is reached. Since it is
desired that system quickly returns to the level set $\mathcal{A}$, we
initialize $\tau_{k}$ with $\tau_{k}^{min}$ unlike the other parameters
$\tau_{1},\cdots,\tau_{k-1}$.

Algorithm 1 Heuristic algorithm for computing $c_{0},\cdots,c_{r-1}$;
$\tau_{1},\cdots,\tau_{k}$ and control policy $\mu(x)$

1:Input: $f(x);g(x);h(x);c_{i}^{max}~{}~{}\forall i=0,1,\cdots,r-1$;
$\tau_{j}^{min}$ and $\tau_{j}^{max}~{}~{}\forall j=1,2,\cdots,k$

2:Output: $c_{i}~{}~{}\forall i=0,1,\cdots,r-1$; $\tau_{j}~{}~{}\forall
j=1,2,\cdots,k$ and $\mu(x)$

3:Initialization: $c_{i}=0~{}~{}\forall i=0,1,\cdots,r-1$

4:loop sweep $(c_{0},c_{1},\cdots,c_{r-1})$ from $(0,0,\cdots,0)$ to
$(c_{0}^{max},c_{1}^{max},\cdots,c_{r-1}^{max})$

5: Maximize $s_{j}$ subject to (14) $\forall j=1,\cdots,k-1$ and maximize
$s_{k}$ subject to (14b), (14c), (14d).

6: loop sweep $(\tau_{1},\tau_{2},\cdots,\tau_{k})$ from
$(\tau_{1}^{max},\tau_{2}^{max},\cdots,\tau_{k}^{min})$ to
$(\tau_{1}^{min},\tau_{2}^{min},\cdots,\tau_{k}^{max})$

7: check (14e) is feasible $\forall j=1,2,\cdots,k$ and whether (15) is
satisfied

8: if true then

9: return $c_{i}~{}~{}\forall i=0,1,\cdots,r-1$; $\tau_{j}~{}~{}\forall
j=1,2,\cdots,k$ and $\mu(x)=\lambda(x)$

10: end if

11: end loop

12:end loop

In Algorithm 1 we assume that all the timing parameters (e.g.,
$\tau_{1},\tau_{2},\cdots,\tau_{k}$) are unknown. If any of these parameters
is known, we use that value in the algorithm without varying the parameter.
The proposed algorithm is flexible in the sense that it can be mapped to a CPS
employing any of the CRAs to design control policy and associated timing
parameters. Table 2 provides a mapping to CRAs to solve various design
problems inherent to the architectures. The last column in Table 2 lists the
timing parameters to be computed for specific CRAs using our algorithm. We
note that in addition to these parameters, we also need to compute the level
set parameters $c_{0},c_{1},\dots,c_{r-1}$. In this table we consider the
worst-case scenario in the sense that if it is not known whether the
controller is compromised or not, then we assume the controller is
compromised. For example, in the case of YOLO the system can be at either
$l=normal$ or $l=corrupted$ location prior to restart. Therefore we assume,
only $l=corrupted$ and $l=restart$ for YOLO when designing the timing
parameters to ensure that CPS remains safe in the worst-case scenario. This in
fact is equivalent to letting $l_{3}=normal$ and $\tau_{3}=0$ during design.
The same analysis is applied to dual redundant and proactive restart schemes
as it can be seen from the table. Note that for the class of Simplex
architecture, there is no associated timing parameter. In this case we only
synthesize the control policy of the safety controller. For synthesizing the
control policy we only consider the conditions (14c) and (14d). We remark that
Algorithm 1 can also be used for safety verification of a given control policy
$\psi(x)$ by checking the feasibility of the conditions in Proposition 5.5 for
$\lambda(x)=\psi(x)$. If the conditions are feasible, then control policy
$\psi(x)$ will guarantee safety.

CRAs | $k$ |  | Sequence of Locations
---
$l_{1},l_{2},\cdots,l_{k}$
| Known
---
Parameters
| Design
---
Parameters
BFT++ (Mertoguno et al., 2019) | 3 | $corrupted,restoration,normal$ |  |  $\tau_{1}=N_{1}\delta$,
---
$\tau_{2}=N_{2}\delta$
|  $\tau_{3}=N_{3}\delta$,
---
$\mu(x)$
| YOLO (Arroyo et al., 2019, 2017) /
---
Dual Redundant (Gamarra et al., 2019)
2 | $corrupted,restart/switching$ |  |  |  $\tau_{1}=N_{4}\delta$,
---
$\tau_{2}=N_{5}\delta$
Proactive Restart (Abdi et al., 2018; Romagnoli et al., 2019) | 3 | $corrupted,restart,SC$ | $\tau_{2}=N_{7}\delta$ |  |  $\tau_{1}=N_{6}\delta$,
---
$\tau_{2}=N_{8}\delta$,
$\mu(x)$
Reactive Restart (Niu et al., 2022b) | 3 | $corrupted,restart,normal$ |  |  |  $\tau_{1}=N_{9}\delta$,
---
$\tau_{2}=N_{10}\delta$,
$\tau_{3}=N_{11}\delta,$
$\mu(x)$
Simplex/S3A (Sha, 2001; Bak et al., 2009; Mohan et al., 2013) | 1 | $SC$ |  | $\mu(x)$
Table 2. Computation of design parameters in different resilient architectures
via mapping to the Algorithm 1. For the resilient architectures in the first
column, the corresponding numbers of discrete locations $k$ and the
corresponding sequences of discrete locations in each run are listed in the
second and third column, respectively. The known parameters and the parameters
to be designed in these architectures using the proposed algorithm are listed
in the fourth and fifth column, respectively.

Now we will characterize the convergence of our algorithm. To do so, first we
provide a justification of Line 5 of our algorithm where we maximize $s_{j}$
subject to (14), (14b), (14c) and (14d) for $j=1,2,\cdots,k$. We show that
maximizing $s_{j}$ will suffice to find a solution to Proposition 5.5 if any
solution exists. The result is formalized as below.

###### Lemma 5.6.

Suppose $s_{i}^{max}$ maximizes $s_{j}$ subject to (14) for $j=1,2,\cdots k-1$
and $s_{k}^{max}$ maximizes $s_{k}$ subject to (14b), (14c) and (14d) for the
selected $c_{0},c_{1},\cdots c_{r-1}$. If (14e) and (15) are not satisfied by
$s_{1}^{max},s_{2}^{max},\cdots,s_{k}^{max}$ and the selected
$\tau_{1},\tau_{2},\cdots,\tau_{k}$, then there exits no solution to the
conditions given by Proposition 5.5 for the selected $c_{0},c_{1},\cdots
c_{r-1}$ and $\tau_{1},\tau_{2},\cdots,\tau_{k}$.

###### Proof.

Suppose there exist $\tilde{s}_{1},\tilde{s}_{2},\cdots,\tilde{s}_{k}$ such
that conditions given by Proposition 5.5 are satisfied for the selected
$c_{0},\cdots,c_{r-1}$ and $\tau_{1},\tau_{2},\cdots,\tau_{k}$. Since
$s_{j}^{max}$ maximizes $s_{j}$ subject to (14) for all $j=1,2,\cdots k-1$ and
$s_{k}^{max}$ maximizes $s_{k}$ subject to (14b), (14c) and (14d) for the
selected $c_{0},c_{1},\cdots c_{r-1}$, therefore $\tilde{s}_{j}\leq
s_{j}^{max}$ for all $j=1,2,\cdots,k$. Since according to (3b) each $a_{j,i}$
is a non-decreasing function of each $s_{j}$, the expressions in the left hand
sides of (2d) and (2e) are also non-decreasing functions of each $s_{j}$ where
$j=1,2,\cdots,k$ and $i=0,1,\cdots,r-1$. Hence
$s_{1}^{max},s_{2}^{max},\cdots,s_{k}^{max}$ satisfy (2d) and (2e). Since for
univariate polynomial non-negativity and SOS conditions are equivalent
(Powers, 2011), therefore $s_{1}^{max},s_{2}^{max},\cdots,s_{k}^{max}$ also
satisfy (14e) and (15) which contradicts the assumption. Hence proof is
complete. ∎

Now we present our main result on the convergence of Algorithm 1. Our insight
is that if there exists any solution that satisfies the conditions in
Proposition 5.5 strictly in the sense that SOS are nonzero in (14) and the
inequality (15) is strict, then the solution lies within the interior of a
feasible solution set. In that case, by choosing sufficiently small step size
for the update of $c_{0},c_{1},\cdots c_{r-1}$ and
$\tau_{1},\tau_{2},\cdots,\tau_{k}$, convergence of the algorithm to a
feasible solution can be guaranteed. The following proposition formalizes
this.

###### Proposition 5.7.

Suppose there exits a solution $(\hat{c}_{0},\hat{c}_{1},\cdots,$
$\hat{c}_{r-1},\hat{\tau}_{1},\hat{\tau}_{2},\cdots,$ $\hat{\tau}_{k})$ such
that (14) and (15) are satisfied strictly with $0\leq c_{i}\leq
c_{i}^{max}~{}~{}\forall i=0,1,\cdots,r-1$ and
$\tau_{j}^{min}\leq\tau_{j}\leq\tau_{j}^{max}~{}~{}\forall j=1,2,\cdots,k$.
Then Algorithm 1 finds a feasible solution with $0\leq c_{i}\leq
c_{i}^{max}~{}~{}\forall i=0,1,\cdots,r-1$ and
$\tau_{j}^{min}\leq\tau_{j}\leq\tau_{j}^{max}~{}~{}\forall j=1,2,\cdots,k$ in
finite number of iterations if step sizes for updating
$c_{0},c_{1},\cdots,c_{r-1},\tau_{1},\tau_{2},\cdots$ and $\tau_{k}$ are
chosen appropriately small.

###### Proof.

Since the solution $(\hat{c}_{0},\hat{c}_{1},\cdots,$
$\hat{c}_{r-1},\hat{\tau}_{1},\hat{\tau}_{2},\cdots,$ $\hat{\tau}_{k})$
satisfies (14) and (15) strictly, therefore there exists a solution interval
$\mathcal{I}\in\mathbb{R}^{r+k}$ with non-zero measure for which (14) and (15)
are feasible where $0\leq c_{i}\leq c_{i}^{max}~{}~{}\forall i=0,1,\cdots,r-1$
and $\tau_{j}^{min}\leq\tau_{j}\leq\tau_{j}^{max}~{}~{}\forall
j=1,2,\cdots,k$. Denote the lengths of $\mathcal{I}$ in $c_{i}$ and $\tau_{j}$
are respectively $\tilde{c}_{i}$ and $\tilde{\tau}_{j}$ where
$i=0,1,\cdots,r-1$ and $j=1,2,\cdots,k$. Let the update for $c_{i}$ in the
Line 4 of Algorithm 1 be $\epsilon_{c_{i}}\in(0,\tilde{c}_{i})$ and the update
of $\tau_{j}$ in the Line 6 of Algorithm 1 be
$\epsilon_{\tau_{j}}\in(0,\tilde{\tau_{j}})$ for all $i=0,1,\cdots,r-1$ and
for all $j=1,2,\cdots,k$. Then applying Lemma 5.6 we get that Algorithm 1 will
terminate with a feasible solution. Otherwise the interval $\mathcal{I}$
contains some infeasible solutions to Eqn. (14) and (15), which contradicts
its definition. ∎

According to the proof, the time complexity of our algorithm is
$\big{(}\Pi_{i=0}^{r-1}\frac{c_{i}^{max}}{\epsilon_{c_{i}}}\big{)}$
$\big{(}\Pi_{j=1}^{k}\frac{\tau_{j}^{max}-\tau_{j}^{min}}{\epsilon_{\tau_{j}}}\big{)}$
$M$ where $M$ is the average time required for each iteration. In practice,
time complexity is less as some of the timing parameters are known.

##  6\. Case Study

This section presents a case study as a verification of our proposed
framework. We consider two vehicles including a leading vehicle and a trailing
vehicle. The vehicles are modeled as point mass and are assumed to be moving
along a straight road. The trailing vehicle is equipped with an adaptive
cruise control (ACC).

We denote the velocities of the leading and trailing vehicles as $v_{l}$ and
$v_{f}$, respectively. The distance between the vehicles is denoted as $D$.
Let $x=[v_{l},v_{f},D]^{T}$ be the state variable. Then the vehicles jointly
follow the dynamics given below (Ames et al., 2016):

(17) $\dot{x}\doteq\begin{bmatrix}\dot{v}_{l}\\\ \dot{v}_{f}\\\
\dot{D}\end{bmatrix}=\begin{bmatrix}a_{l}\\\ -\frac{F_{r}}{m}\\\
v_{l}-v_{f}\end{bmatrix}+\begin{bmatrix}0\\\ \frac{1}{m}\\\ 0\end{bmatrix}u$

where $u\in[-1,1]$ is the control input to the trailing vehicle, $m=1$ is the
mass of the trailing vehicle, $a_{l}=0.3$ is the acceleration of the leading
vehicle, and $F_{r}=f_{0}+f_{1}v_{f}+f_{2}v_{f}^{2}$ models the resistance
incurred by the trailing vehicle. In this case study, we choose $f_{0}=0$,
$f_{1}=1$, and $f_{2}=0.5$ and note that the dynamics (17) is nonlinear. We
assume that $x\in\mathcal{X}$, where $\mathcal{X}$ is a compact set given as
$\mathcal{X}=\\{x:\|x\|^{2}\leq d\\}$ with $d=10$. We let the initial system
state be $x_{0}=[0,0,3]^{T}$. We suppose that the control input is updated
every $0.1$ second, i.e., with frequency $10$Hz.

The trailing vehicle is required to satisfy a safety constraint modeled as
$x_{t}\in\mathcal{C}$ for all $t\geq 0$, where

$\mathcal{C}=\\{x:h(x)=D-2\geq 0\\}.$

That is, the distance between the leading and trailing vehicles is no less
than $2$, and the trailing vehicle should stay behind the leading vehicle.
Note that the system is of relative degree two (i.e. $r=2$) under the safety
constraint since $L_{g}h(x)=0$ and $L_{f}L_{g}h(x)=-\frac{1}{m}$. Therefore
control synthesis algorithm given by (Niu et al., 2022a) is not applicable
here.

In the remainder of this section, we evaluate a collection of architectures
including BFT++ (Mertoguno et al., 2019), YOLO (Arroyo et al., 2019, 2017),
proactive restart (Abdi et al., 2018; Romagnoli et al., 2019), reactive
restart (Niu et al., 2022b), dual redundant (Gamarra et al., 2019) and Simplex
(Sha, 2001; Bak et al., 2009; Mohan et al., 2013) architectures under our
proposed framework. We compute the set $\mathcal{A}$ along with the control
policy $\mu$ and corresponding timing parameters as shown in Table 2. We also
provide a comparison among these architectures based on our case study.

###  6.1. Evaluation of BFT++

In what follows, we evaluate BFT++ using our proposed framework on the system
(17). We consider that the trailing vehicle is subject to a cyber attack. The
attack exploits the vulnerability of the trailing vehicle’s controller, which
will trigger a controller crash. We consider the worst-case time consumption
for controller crash and restoration which are $N_{1}=2$ and $N_{2}=2$ epochs,
respectively (Mertoguno et al., 2019). We assume that the leading vehicle is
equipped with a memory of length $2$, which stores the delayed control inputs,
so as to provide input signal to the vehicle during controller restoration.

By Table 2, the hybrid system traverses $corrupted,restoration$ and $normal$
statuses during one attack cycle. Under this setup, we have that during one
attack cycle, the controller will take $4$ epochs to return to the normal
status following an exploitation by the attacker. Using Algorithm 1, we obtain
that $c_{0}=0.8$ and $c_{1}=0.1$. In addition, the controller should remain in
$normal$ status for at least $\tau_{3}=4$ epochs. We simulate the distance
between the leading and trailing vehicles in Fig. 2(a) by considering the
worst-case scenario where the input signal during $corrupted$ and
$restoration$ statuses are both malicious. The trajectory generated by
corrupted and delayed inputs is shown in red color, and the trajectory during
the normal status is plotted in green color. Note that to guarantee safety of
the system for possible future attack, the synthesized controller should
ensure that $D\geq 2.8$ at the end of the normal status (as shown at epoch 8
and 16 in Fig. 2(a)). In Fig. 2(a), we observe that the adversary attempts to
cause crash between the leading and trailing vehicles by injecting compromised
inputs to decrease the distance between them (the red portion in Fig. 2(a)).
After the controller is restored, the designed control policy steers the
trailing vehicle to set $\mathcal{A}$, as shown by the green portion in Fig.
2(a). It should be noted that because of Newton’s law of motion there is a
latency between distance $D$ and the control input $u$ in the dynamics (17).
Due to the latency the distance continues to decrease under synthesized policy
in the first green segment of Fig. 2(a).

###  6.2. Evaluation of YOLO

This subsection evaluates YOLO (Arroyo et al., 2019, 2017). In this case,
there is only one controller that turns on and off periodically. During one
attack cycle, the hybrid system visits $corrupted,restart$ and $normal$
statuses. We remark that in this case the trailing vehicle is not equipped
with any mechanism to detect whether the system is compromised by the
adversary or not. Therefore in this case study, we will consider the worst-
case scenario and assume that the controller produces compromised inputs when
it is online. Thus we will consider only $corrupted$ and $restart$ statuses
for our design.

Using Algorithm 1, we have that $c_{0}=0.2$ and $c_{1}=0.1$. In addition, we
obtain that $\tau_{1}=\tau_{2}=5$ epochs. In other words, during one attack
cycle, the controller is switched on and off every $5$ epochs, yielding
controller availability to be $50\%$. We plot the distance between the two
vehicles in Fig. 2(b). We use red and blue color to represent the on
($corrupted$) and off ($restart$) statuses of the controller. We note that the
adversary aims at causing vehicle crash by decreasing distance $D$, as shown
by the red portion in Fig. 2(b). However, the potential crash can be prevented
by restarting the controller (the blue portion in Fig. 2(b)). During the
restart phase, the trailing vehicle slows down due to resistance, and thus
maintains the distance to be within the safety set $\mathcal{C}$.

###  6.3. Evaluation of Proactive Restart

In what follows, we evaluate the proactive restart based approach (Abdi et
al., 2018; Romagnoli et al., 2019). We consider that the trailing vehicle is
equipped with two controllers, one being main controller which is vulnerable
to the cyber attack and the other one being the safety controller. After
restart, the safety controller takes over the system to guarantee safety. To
consider the worst-case scenerio, we assume that the main controller becomes
compromised when it is online. However, safety controller does not become
compromised since all the external interfaces are disabled during this
interval (Abdi et al., 2018; Romagnoli et al., 2019). Hence in this case, the
system visits $corrupted,restart$ and $SC$ statuses during one attack cycle.

Using Algorithm 1, we have that $c_{0}=0.83$ and $c_{1}=0.1$. Assuming that
$\tau_{2}=1$ epoch, we also obtain the timing parameters as $\tau_{1}=3$
epochs and $\tau_{3}=1$ epoch. That is, the maximum number of epochs spent in
$corrupted$ and $restart$ statuses are $3$ and $1$ epochs, respectively. The
minimum number epochs in $SC$ status is $1$ epoch. We simulate the trajectory
in Fig. 2(c). We observe that the adversary can shorten the distance between
the leading and trailing vehicles. The proactive restart commands sent by the
decision module at epoch 3, 8, 13, and 18 prevent the adversary from further
decreasing the distance between the vehicles. Furthermore, during the
$restart$, since the leading vehicle’s velocity is still less than that of the
trailing vehicle, the distance between two vehicles continues to decrease, as
shown by the blue fragment in Fig. 2(c). During $SC$, the safety controller is
implemented that uses the control policy synthesized according to our
algorithm. This is shown by the green portion of the system trajectory in Fig.
2(c) where we observe that the distance between the vehicles starts to
increase so as to maintain the safety constraint and prevent safety violations
in the future.

###  6.4. Evaluation of Reactive Restart

This subsection evaluates the reactive restart based approach (Niu et al.,
2022b). In this setting, the trailing vehicle is equipped with one controller.
Different from proactive restart based approach, restart command is issued as
a response to adversarial exploitation, which triggers controller crash. In
this case, the hybrid system visits $corrupted,restart$ and $normal$ statuses
during one attack cycle as shown in the Table 2.

Using Algorithm 1, we obtain that $c_{0}=0.82$ and $c_{1}=0.1$. We also have
that the controller tolerates $\tau_{1}=3$, $\tau_{2}=1$, and $\tau_{3}=2$
epochs in $corrupted$, $restart$, and $normal$ statuses during one attack
cycle. We simulate the distance between the vehicles in Fig. 3(a). We observe
that the adversary first reduces the distance between the two vehicles by
accelerating the trailing vehicle, as shown by the red color fragment in Fig.
3(a). Then the adversarial exploitation triggers controller restart and leads
to input $u=0$ (shown by the blue fragment in Fig. 3(a)). After completing
controller restart, the desired control input as computed using our algorithm
is provided to the trailing vehicle, which increases the distance with the
leading vehicle as seen in the green color fragment of Fig. 3(a).

(a)

(b)

(c)

Figure 2. The distance between the leading and trailing vehicles where
trailing vehicle is subject fault or attack. The trailing vehicle implements
(a) BFT++, (b) YOLO, and (c) proactive restart scheme. The fragment of
trajectory in red color indicates that the controller is corrupted. The blue
color fragments capture the parts of trajectories generated when control input
$u=0$. The green color fragments depict the trajectories generated using the
designed control policy or safety controller.

###  6.5. Evaluation of Simplex Architecture

This subsection evaluates Simplex architecture (Sha, 2001; Bak et al., 2009;
Mohan et al., 2013). We consider that the trailing vehicle is equipped with a
high performance controller and a safety controller. In this case study, we
assume that there exists no adversary. However, the high performance
controller is vulnerable to random failures. The safety controller is assumed
to be provably correct and thus is fault-free. Following the condition (2c)
and choosing $c_{0}=2.9,c_{1}=0.2$, we design the safety controller as

$\displaystyle\min_{u}~{}$ $\displaystyle u^{T}u$ s.t. $\displaystyle
L_{f}^{2}h(x)+L_{f}L_{g}h(x)u+\alpha(L_{f}h(x)-0.2)\geq 0$

The trailing vehicle switches to the safety controller once the distance
between two vehicles approaches to $D<2.9$ or $h^{1}(x)$ approaches to
$h^{1}(x)<0.2$.

(a)

(b)

(c)

Figure 3. The distance between the leading and trailing vehicles where trailing vehicle is subject fault or attack. The trailing vehicle implements (a) reactive restart, (b) Simplex and (c) dual redundant scheme. The fragment of trajectory in red color indicates that the controller is corrupted. The blue color fragments capture the parts of trajectories generated when control input $u=0$. The green color fragments depict the trajectories generated using the designed control policy or safety controller. CRAs |  | Cyber
---
Attack
| Redundancy
---
| Controller
---
Availability
| Design
---
Freedom
| Maximum
---
Impact
Simplex/S3A (Sha, 2001; Bak et al., 2009; Mohan et al., 2013) | $\times$ |  | Redundant
---
controller
$100\%(0\%)$ | 1 | 0.13
BFT++ (Mertoguno et al., 2019) | $\checkmark$ |  | Redundant
---
controllers
$75\%(50\%)$ | 2 | 0.1088
YOLO (Arroyo et al., 2019, 2017) | $\checkmark$ | NA | $50\%(0\%)$ | 2 | 0.115
Dual Redundant (Gamarra et al., 2019) | $\checkmark$ |  | Redundant
---
controller
$50\%(0\%)$ | 2 | 0.115
Proactive Restart (Abdi et al., 2018; Romagnoli et al., 2019) | $\checkmark$ |  | Redundant
---
control program
$80\%(20\%)$ | 3 | 0.1324
Reactive Restart (Niu et al., 2022b) | $\checkmark$ | NA | $83.33\%(33.33\%)$ | 4 | $0.09$
Table 3. Comparison among the existing resilient architectures when applying
to adaptive cruise control using our proposed framework. We compare the
architectures in terms of (i) whether the system can recover from cyber attack
(second column), (ii) whether redundancy is required (third column), (iii) the
controller availability at each attack cycle (fourth column), (iv) the design
freedom (fifth column), and (v) the maximum impact introduced by the adversary
(sixth column). In fourth column, we list both the controller availability
under attack and nominal controller availability, where the latter is
presented in parenthesis. The architectures are listed in an ascending order
of their respective the design freedom.

We simulate the trajectory in Fig. 3(b). We observe that in the worst-case,
the random failure reduces the distance between two vehicles and thus can
potentially lead to vehicle crash. Once the condition for switching to safety
controller is satisfied at epoch 5, the safety controller is invoked. From the
green color fragment in Fig. 3(b), we observe that the safety controller slows
down the trailing vehicle, and thus increases the distance with the leading
vehicle to prevent safety violation.

###  6.6. Evaluation of Dual Redundant Controllers Architecture

In this subsection, we consider that the trailing vehicle is equipped with two
identical controllers (Gamarra et al., 2019) which are periodically switched
to actuate the vehicle. However the switching may not be instantaneous, and
could incur some delay. During the delay, there is no control input to the
system. To consider the worst-case scenario we assume that the controllers are
compromised when they are online. For this case, the hybrid system visits
$corrupted$ and $switching$ statuses during one attack cycle.

Using Algorithm 1, we have that the system spends $5$ epochs each for status
$switching$ and $corrupt$. We simulate the system trajectory as shown in Fig.
3(c) which is similar to the one for YOLO i.e. Fig. 2(b). We observe that if
the system is compromised, then the distance between two vehicles decreases.
However, switching between controllers ensures that the safety constraint is
satisfied.

###  6.7. Comparison of Resilient Architectures

In this subsection, we compare the resilient architectures evaluated using our
proposed framework considering the following aspects: (i) whether the system
can recover from cyber attack, (ii) whether redundancy is required, (iii) the
worst-case and best-case controller availabilities at each attack cycle, (iv)
the design freedom, and (v) the maximum impact introduced by the adversary.
The controller availability is measured $T_{on}/T_{off}$, where $T_{on}$ and
$T_{off}$ are the number of epochs that some controller is online and offline
during one attack cycle, respectively. We further divide the controller
availability into two cases. The first case gives controller availability
under attack which accounts the total amount of epochs when the controller is
online, regardless of whether the controller being compromised or not. The
second case gives the nominal controller availability which only counts the
epochs during which the controller follows the nominal policy into $T_{on}$.
We consider the design freedom of an architecture to be the number of design
parameters in our proposed framework as given in Table 2. We quantify the
maximum impact introduced by the adversary as the maximum amount of decrease
in the value of $h(x)$ (i.e. distance $D$ between the leading and trailing
vehicles) since the first epoch. The comparison result is summarized in Table
3. We observe that Simplex and S3A are not suitable for the system subject to
cyber attacks. Among the CRAs, BFT++ provides the maximum availability of the
nominal controller under attack during considered attack cycle. We also
observe that reactive restart provides the least impact from the adversary
(0.09) since it has four design parameters ($\tau_{1},\tau_{2},\tau_{3}$ and
$\mu(x)$) unlike other CRAs evaluated in this section.

##  7\. Conclusion

We developed a timing-based framework for safety analysis and parameter design
of CPS that applies to a set of seemingly unrelated resilient architectures.
We presented a hybrid system model to capture CPS employing distinct CRAs. We
used the transition model of the hybrid system to derive architecture-agnostic
sufficient conditions for control policy and timing parameters that ensures
safety of the CPS. Our derived conditions hold for a system whose barrier
certificate for safety is of higher relative degree with respect to the
physical dynamics. We formulated the conditions as a sum-of-squares program
and based on that we proposed an algorithm for computing control policy and
timing parameters of the implemented architecture. Our derived conditions and
proposed algorithm are flexible enough to map them into various design
problems relevant to resilient architectures. We also analyzed the convergence
of our algorithm and proved that the algorithm converges to a feasible
solution given that one exists. We presented a case study on the adaptive
cruise control of vehicles to demonstrate applicability of our proposed
framework for different CRAs. Possible future directions include extending our
proposed framework for interconnected CPS, and incorporating other properties
including stability and reachability.

## References

  * (1)
  * Abdi et al. (2018) Fardin Abdi, Chien-Ying Chen, Monowar Hasan, Songran Liu, Sibin Mohan, and Marco Caccamo. 2018\.  Guaranteed physical security with restart-based design for cyber-physical systems. In _ACM/IEEE 9th International Conference on Cyber-Physical Systems (ICCPS)_. IEEE, 10–21.
  * Abdi et al. (2017) Fardin Abdi, Rohan Tabish, Matthias Rungger, Majid Zamani, and Marco Caccamo. 2017.  Application and system-level software fault tolerance through full system restarts. In _ACM/IEEE 8th International Conference on Cyber-Physical Systems (ICCPS)_. IEEE, 197–206.
  * Alemzadeh et al. (2016) Homa Alemzadeh, Daniel Chen, Xiao Li, Thenkurussi Kesavadas, Zbigniew T Kalbarczyk, and Ravishankar K Iyer. 2016.  Targeted attacks on teleoperated surgical robots: Dynamic model-based detection and mitigation. In _2016 46th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)_. IEEE, 395–406.
  * Ames et al. (2019) Aaron D Ames, Samuel Coogan, Magnus Egerstedt, Gennaro Notomista, Koushil Sreenath, and Paulo Tabuada. 2019.  Control barrier functions: Theory and applications. In _18th European Control Conference (ECC)_. IEEE, 3420–3431.
  * Ames et al. (2016) Aaron D Ames, Xiangru Xu, Jessy W Grizzle, and Paulo Tabuada. 2016\.  Control barrier function based quadratic programs for safety critical systems.  _IEEE Trans. Automat. Control_ 62, 8 (2016), 3861–3876.
  * Arroyo et al. (2017) Miguel Arroyo, Hidenori Kobayashi, Simha Sethumadhavan, and Junfeng Yang. 2017.  FIRED: frequent inertial resets with diversification for emerging commodity cyber-physical systems.  _arXiv preprint arXiv:1702.06595_ (2017).
  * Arroyo et al. (2019) Miguel A Arroyo, M Tarek Ibn Ziad, Hidenori Kobayashi, Junfeng Yang, and Simha Sethumadhavan. 2019\.  YOLO: frequently resetting cyber-physical systems for security. In _Autonomous Systems: Sensors, Processing, and Security for Vehicles and Infrastructure 2019_ , Vol. 11009. International Society for Optics and Photonics, 110090P.
  * Bak et al. (2009) Stanley Bak, Deepti K Chivukula, Olugbemiga Adekunle, Mu Sun, Marco Caccamo, and Lui Sha. 2009\.  The system-level simplex architecture for improved real-time embedded system safety. In _15th IEEE Real-Time and Embedded Technology and Applications Symposium_. IEEE, 99–107.
  * Blanchini and Miani (2008) Franco Blanchini and Stefano Miani. 2008.  _Set-theoretic methods in control_. Vol. 78.  Springer.
  * Cárdenas et al. (2008) Alvaro A Cárdenas, Saurabh Amin, and Shankar Sastry. 2008\.  Research Challenges for the Security of Control Systems.. In _Proceedings of the 3rd Conference on Hot Topics in Security_ , Vol. 5. USENIX Association, 15.
  * Castro and Liskov (2002) Miguel Castro and Barbara Liskov. 2002.  Practical Byzantine fault tolerance and proactive recovery.  _ACM Transactions on Computer Systems (TOCS)_ 20, 4 (2002), 398–461.
  * Cohen and Belta (2020) Max H Cohen and Calin Belta. 2020.  Approximate optimal control for safety-critical systems with control barrier functions. In _59th Conference on Decision and Control (CDC)_. IEEE, 2062–2067.
  * Fawzi et al. (2014) Hamza Fawzi, Paulo Tabuada, and Suhas Diggavi. 2014\.  Secure estimation and control for cyber-physical systems under adversarial attacks.  _IEEE Transactions on Automatic control_ 59, 6 (2014), 1454–1467.
  * Gamarra et al. (2019) Marco A Gamarra, Sachin Shetty, Oscar R Gonzalez, Laurent Njilla, Marcus Pendleton, and Charles Kamhoua. 2019.  Dual redundant cyber-attack tolerant control systems strategy for cyber-physical systems. In _IEEE International Conference on Communications (ICC)_. IEEE, 1–7.
  * Greenberg (2015) Andy Greenberg. 2015\.  Hackers remotely kill a Jeep on the highway–with me in it.  https://www.wired.com/2015/07/hackers-remotely-kill-jeep-highway/
  * Griffioen et al. (2019) Paul Griffioen, Raffaele Romagnoli, Bruce H Krogh, and Bruno Sinopoli. 2019.  Secure networked control via software rejuvenation. In _2019 IEEE 58th Conference on Decision and Control (CDC)_. IEEE, 3878–3884.
  * Halperin et al. (2008) Daniel Halperin, Thomas S Heydt-Benjamin, Benjamin Ransford, Shane S Clark, Benessa Defend, Will Morgan, Kevin Fu, Tadayoshi Kohno, and William H Maisel. 2008\.  Pacemakers and implantable cardiac defibrillators: Software radio attacks and zero-power defenses. In _2008 IEEE Symposium on Security and Privacy (sp 2008)_. IEEE, 129–142.
  * Herbert et al. (2017) Sylvia L Herbert, Mo Chen, SooJean Han, Somil Bansal, Jaime F Fisac, and Claire J Tomlin. 2017\.  FaSTrack: A modular framework for fast and guaranteed safe motion planning. In _56th Annual Conference on Decision and Control (CDC)_. IEEE, 1517–1522.
  * Kc et al. (2003) Gaurav S Kc, Angelos D Keromytis, and Vassilis Prevelakis. 2003\.  Countering code-injection attacks with instruction-set randomization. In _Proceedings of the 10th ACM conference on Computer and communications security_. 272–280.
  * Khalil (1996) HK Khalil. 1996\.  Nonlinear Systems, Printice-Hall.  _Upper Saddle River, NJ_ 3 (1996).
  * Koscher et al. (2010) Karl Koscher, Alexei Czeskis, Franziska Roesner, Shwetak Patel, Tadayoshi Kohno, Stephen Checkoway, Damon McCoy, Brian Kantor, Danny Anderson, Hovav Shacham, and Stefan Savage. 2010.  Experimental security analysis of a modern automobile. In _2010 IEEE symposium on security and privacy_. IEEE, 447–462.
  * Larsen et al. (2014) Per Larsen, Andrei Homescu, Stefan Brunthaler, and Michael Franz. 2014.  SoK: Automated software diversity. In _2014 IEEE Symposium on Security and Privacy_. IEEE, 276–291.
  * Lee et al. (2016) M. Robert Lee, J. Michael Assante, and Tim Conway. 2016\.  Analysis of the cyber attack on the Ukrainian power grid.  https://media.kasperskycontenthub.com/wp-content/uploads/sites/43/2016/05/20081514/E-ISAC_SANS_Ukraine_DUC_5.pdf
  * Manshaei et al. (2013) Mohammad Hossein Manshaei, Quanyan Zhu, Tansu Alpcan, Tamer Başar, and Jean-Pierre Hubaux. 2013.  Game theory meets network security and privacy.  _ACM Computing Surveys (CSUR)_ 45, 3 (2013), 1–39.
  * Mertoguno et al. (2019) J Sukarno Mertoguno, Ryan M Craven, Matthew S Mickelson, and David P Koller. 2019.  A physics-based strategy for cyber resilience of CPS. In _Autonomous Systems: Sensors, Processing, and Security for Vehicles and Infrastructure 2019_ , Vol. 11009. International Society for Optics and Photonics, 110090E.
  * Mo and Sinopoli (2010) Yilin Mo and Bruno Sinopoli. 2010.  False data injection attacks in control systems. In _Preprints of the 1st workshop on Secure Control Systems_ , Vol. 1.
  * Mohan et al. (2013) Sibin Mohan, Stanley Bak, Emiliano Betti, Heechul Yun, Lui Sha, and Marco Caccamo. 2013\.  S3A: Secure system simplex architecture for enhanced security and robustness of cyber-physical systems. In _the 2nd ACM International Conference on High Confidence Networked Systems_. 65–74.
  * Niu et al. (2019) Luyao Niu, Zhouchi Li, and Andrew Clark. 2019.  LQG reference tracking with safety and reachability guarantees under false data injection attacks. In _2019 American Control Conference (ACC)_. IEEE, 2950–2957.
  * Niu et al. (2022a) Luyao Niu, Abdullah Al Maruf, Andrew Clark, J Sukarno Mertoguno, and Radha Poovendran. 2022a.  An Analytical Framework for Control Synthesis of Cyber-Physical Systems with Safety Guarantee. In _IEEE 61st Conference on Decision and Control (CDC)_.
  * Niu et al. (2022b) Luyao Niu, Dinuka Sahabandu, Andrew Clark, and Poovendran Radha. 2022b.  Verifying Safety for Resilient Cyber-Physical Systems via Reactive Software Restart. In _To Appear in ACM/IEEE 13th International Conference on Cyber-Physical Systems (ICCPS)_. ACM/IEEE.
  * Pajic et al. (2014a) Miroslav Pajic, Zhihao Jiang, Insup Lee, Oleg Sokolsky, and Rahul Mangharam. 2014a.  Safety-critical medical device development using the UPP2SF model translation tool.  _ACM Transactions on Embedded Computing Systems (TECS)_ 13, 4s (2014), 1–26.
  * Pajic et al. (2014b) Miroslav Pajic, James Weimer, Nicola Bezzo, Paulo Tabuada, Oleg Sokolsky, Insup Lee, and George J Pappas. 2014b.  Robustness of attack-resilient state estimators. In _ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS)_. IEEE, 163–174.
  * Powers (2011) Victoria Powers. 2011\.  Positive polynomials and sums of squares: Theory and practice.  _Real Algebraic Geometry_ 1 (2011), 78–149.
  * Prajna et al. (2007) Stephen Prajna, Ali Jadbabaie, and George J Pappas. 2007\.  A framework for worst-case and stochastic safety verification using barrier certificates.  _IEEE Trans. Automat. Control_ 52, 8 (2007), 1415–1428.
  * Qin et al. (2021) Zengyi Qin, Kaiqing Zhang, Yuxiao Chen, Jingkai Chen, and Chuchu Fan. 2021.  Learning safe multi-agent control with decentralized neural barrier certificates.  _arXiv preprint arXiv:2101.05436_ (2021).
  * Romagnoli et al. (2020a) Raffaele Romagnoli, Paul Griffioen, Bruce H Krogh, and Bruno Sinopoli. 2020a.  Software rejuvenation under persistent attacks in constrained environments.  _IFAC-PapersOnLine_ 53, 2 (2020), 4088–4094.
  * Romagnoli et al. (2019) Raffaele Romagnoli, Bruce H Krogh, and Bruno Sinopoli. 2019\.  Design of software rejuvenation for cps security using invariant sets. In _2019 American Control Conference (ACC)_. IEEE, 3740–3745.
  * Romagnoli et al. (2020b) Raffaele Romagnoli, Bruce H Krogh, and Bruno Sinopoli. 2020b.  Robust Software Rejuvenation for CPS with State Estimation and Disturbances. In _2020 American Control Conference (ACC)_. IEEE, 1241–1246.
  * Sha (2001) Lui Sha. 2001.  Using simplicity to control complexity.  _IEEE Software_ 18, 4 (2001), 20–28.
  * Sharifi et al. (2010) Farid Sharifi, Mostafa Mirzaei, Brandon W Gordon, and Youmin Zhang. 2010.  Fault tolerant control of a quadrotor UAV using sliding mode control. In _Conference on Control and Fault-Tolerant Systems (SysTol)_. IEEE, 239–244.
  * Wang et al. (2021) Chuanzheng Wang, Yiming Meng, Yinan Li, Stephen L Smith, and Jun Liu. 2021.  Learning control barrier functions with high relative degree for safety-critical control. In _2021 European Control Conference (ECC)_. IEEE, 1459–1464.
  * Xu et al. (2020) Dezhi Xu, Fanglai Zhu, Zepeng Zhou, and Xinggang Yan. 2020\.  Distributed fault detection and estimation in cyber–physical systems subject to actuator faults.  _ISA Transactions_ 104 (2020), 162–174.
  * Xu (2018) Xiangru Xu. 2018\.  Constrained control of input–output linearizable systems using control sharing barrier functions.  _Automatica_ 87 (2018), 195–201.
  * Zhang and Jiang (2008) Youmin Zhang and Jin Jiang. 2008.  Bibliographical review on reconfigurable fault-tolerant control systems.  _Annual Reviews in Control_ 32, 2 (2008), 229–252.
  * Zhu and Başar (2015) Quanyan Zhu and Tamer Başar. 2015.  Game-theoretic methods for robustness, security, and resilience of cyberphysical control systems: games-in-games principle for optimal cross-layer resilient control systems.  _IEEE Control Systems Magazine_ 35, 1 (2015), 46–65.