---
abstract: 'In the coming years, usage of Unmanned Aerial Vehicles (UAVs) is expected to grow tremendously. Maintaining security of UAVs under cyber attacks is an important yet challenging task, as these attacks are often erratic and difficult to predict. Secure estimation problems study how to estimate the states of a dynamical system from a set of noisy and maliciously corrupted sensor measurements. The fewer assumptions that an estimator makes about the attacker, the larger the set of attacks it can protect the system against. In this paper, we focus on sensor attacks on UAVs and attempt to design a secure estimator for linear time-invariant systems based on as few assumptions about the attackers as possible. We propose a computationally efficient estimator that protects the system against arbitrary and unbounded attacks, where the set of attacked sensors can also change over time. In addition, we propose to combine our secure estimator with a Kalman Filter for improved practical performance and demonstrate its effectiveness through simulations of two scenarios where an UAV is under adversarial cyber attack.'
author:
- 'Qie Hu$^*$, Young Hwan Chang$^*$, and Claire J. Tomlin'
bibliography:
- 'reference.bib'
title: ' **Secure Estimation for Unmanned Aerial Vehicles against Adversarial Cyber Attacks**'
---

Introduction
============

The already widespread use of Unmanned Aerial Vehicles (UAVs) is expected to continue to grow at a tremendous rate over the next few years [@faa]. Civilian applications of UAVs, such as cargo delivery [@Google; @Amazon], infrastructure surveillance [@Asctec], and agricultural applications [@Croplife], can provide great benefits to society.

However, UAVs may be vulnerable to a variety of cyber attacks. For example, to manage the increased UAV traffic, each UAV may periodically send its position measurements wirelessly to a remote traffic management center. Similarly, two UAVs may exchange position and velocity information in a collaborative collision avoidance procedure. These communication links could be subject to Man-In-The-Middle (MITM) attacks in which a malicious agent spoofs the information being sent and/or received. Successful attacks can lead to collisions of vehicles, economic loss and bodily damage. Therefore, maintaining the security of UAVs under such cyber attacks is an important but also challenging task, as attacks are often erratic and difficult to model.

Secure estimation problems study how to estimate the states of a dynamical system from a set of noisy and maliciously corrupted sensor measurements. In designing such estimators, it is desirable to make as few assumptions about the attackers as possible. This is because it is very difficult, if not impossible, to predict the behavior of attackers, and when an attack signal violates the assumptions of a secure estimator, then this estimator would fail to detect the attack.

Researchers have studied various approaches to securing general cyber-physical systems, each based on a different set of assumptions about the attacker. For example, the authors in [@Bullo; @Liu] assume that the attack signal would follow certain probabilistic distributions and then design filters for detection of such attacks. In [@Wu; @Basar; @Basar2; @Walrand; @Pappas], the authors use the game theory framework, where the controller and attacker are players with competing goals in a game. Attackers are assumed to adopt specific strategies that maximize a certain cost and the controller or estimator is designed to minimize such a cost. More recently, Fawzi *et al.* proposed in [@Fawzi2014] a secure estimation method for arbitrary attacks, with a limiting assumption that the set of attacked sensors do not change with time.

In this paper, we focus on sensor attacks on UAVs and attempt to design a secure estimator for linear time-invariant (LTI) systems based on as few assumptions about the attackers as possible. First, we do not assume that the attack signals follow any stochastic distributions, and thus our proposed estimator works for arbitrary and unbounded attacks. Second, we allow the set of attacked sensors to change over time. The only assumption we make is that the number of attacked sensors is sparse.

We formulate this secure estimation problem into the classical error correction problem, from which we propose an $l_1$-optimization based estimator that is computationally efficient. In addition, we prove the maximum number of sensor attacks that can be corrected with our estimator and propose a practical method for estimator design that guarantees accurate decoding. Finally, to improve the estimator’s practical performance, we propose to combine our secure estimator with a Kalman Filter (KF), and demonstrate its effectiveness using two examples of UAVs under adversarial cyber attacks.

Classical Error Correction: A Review {#sec_review}
====================================

Compressed Sensing
------------------

Sparse solutions $x\in \mathbb{R}^n$, are sought to the following problem: $$\min_x {\left\lVertx\right\rVert}_0 \text{ subject to } b= Ax
    \label{eq:CS}$$ where $b \in \mathbb{R}^m$ are the measurements, and $A \in \mathbb{R}^{m\times n}~ (m \ll n)$ is a sensing matrix. ${\left\lVertx\right\rVert}_0$ denotes the number of nonzero elements of $x$. The following lemma provides a sufficient condition for a unique solution to (\[eq:CS\]).

([@Candes_Tao]) \[lem:CS\] If the sparsest solution to (\[eq:CS\]) has ${\left\lVertx\right\rVert}_0 = q$ and $m\ge 2q$ and all subsets of $2q$ columns of $A$ are full rank, then the solution is unique.

Suppose the solution is not unique. Therefore, there exists $x_1 \neq  x_2$ such that $Ax _1 = b$ and $Ax_2 = b$ where ${\left\lVertx_1\right\rVert}_0 = {\left\lVertx_2\right\rVert}_0 = q$. Then, $A(x_1 - x_2) = 0$ and $x_1 - x_2 \neq 0$. Since ${\left\lVertx_1-x_2\right\rVert}_0 \leq 2q$ and all $2q$ columns of $A$ are full rank (i.e., linearly independent), it is impossible to have $x_1-x_2\neq 0$ that satisfies $A(x_1-x_2) = 0$. This contradicts the assumption.

The Error Correction Problem [@Candes_Tao]
------------------------------------------

Consider the classical error correction problem: $y=Cx + e$ where $C\in \mathbb{R}^{l\times n}$ is a coding matrix $(l > n)$ and assumed to be full rank. We wish to recover the input vector $x \in \mathbb{R}^n$ from corrupted measurements $y$. Here, $e$ is an arbitrary and unknown sparse error vector. To reconstruct $x$, note that it is obviously sufficient to reconstruct the vector $e$ since knowledge of $Cx + e$ together with $e$ gives $Cx$, and consequently $x$ since $C$ has full rank [@Candes_Tao]. In [@Candes_Tao], the authors construct a matrix $F$ which annihilates $C$ on the left, i.e., $FCx = 0$ for all $x$. Then, they apply $F$ to the output $y$ and obtain $$\tilde y = F (Cx + e) = Fe.$$ Thus, the decoding problem can be reduced to that of reconstructing a sparse vector $e$ from the observations $\tilde y = Fe$. Therefore, by Lemma \[lem:CS\], if all subsets of $2q$ columns of $F$ are full rank, then we can reconstruct any $e$ such that $\| e \|_0 \leq q$.

Secure Estimation
=================

Problem Formulation
-------------------

Consider the LTI system as follows: $$\begin{aligned}
x(k+1) &= A_o x(k) + B u(k) \\
y(k) &= C x(k) + e(k),
\end{aligned} 
\label{eq:system_model_se}$$ where $x(k) \in \mathbb{R}^n$, $y(k) \in \mathbb{R}^p$ and $u(k) \in \mathbb{R}^m$ are the states, measurements and control inputs at time step $k$. $e(k) \in \mathbb{R}^p$ represents the attack signal at time $k$. Our goal is to reconstruct the initial state $x(0)$ of the plant from the corrupted observations $y(k)$’s where $k=0,...,T-1$.

The attack vector $e(k)$ is such that if the $i$th sensor is attacked at time $k$, then $e_i(k)$, the $i$th element of $e(k)$ is nonzero, otherwise $e_i(k) = 0$. We assume that the attack signal can be arbitrary and unbounded. In addition, we assume that the set of attacked sensors can change over time. As illustrated by the following example, if 2 sensors are attacked at each time step, we can have sensors 1 and 3 attacked at time step 0, sensors 2 and 3 attacked at time 1, and so on: $$\begin{bmatrix} e(0)  & \lvert & e(1) & \lvert &  ...  & \end{bmatrix} 
    = \begin{bmatrix} * & 0 & * & \cdots \\
                           0 & * & 0 & \cdots \\
                           * & * & 0 & \cdots \\
                           0 & 0 & * &\cdots 
            \end{bmatrix}, \nonumber \\$$ where $*$ denotes a nonzero component (i.e., an attack or corruption).

Furthermore, assume that a local control loop implements secure state feedback and is not subject to attack: $u(k) = Gx(k)$. In the case of UAVs, this corresponds to using measurements from onboard, hardwired sensors such as Inertial Measurement Units (IMU) for autopilot and trajectory following. The resulting closed loop system is: $$\begin{aligned}
x(k+1) &= A x(k)\\
y(k) &= C x(k) + e(k),
\end{aligned} 
\label{eq:system_model_cl}$$ where the closed loop system matrix $A=A_o+BG$.

Finally, we define the number of correctable attacks/errors as follows:

\[def:num\_err\_change\] When the set of attacked sensors/nodes can change over time, $q$ errors are correctable after $T$ steps by the estimator/decoder $\mathcal{D}: {(\mathbb{R} ^p) } ^T  \rightarrow \mathbb{R}^n$ if for any $x(0) \in \mathbb{R}^n$ and any sequence of vectors $e(0),...,e(T-1)$ in $\mathbb{R}^p$ such that $\lvert \textsf{supp}(e(k)) \rvert \leq q$, we have $\mathcal{D} (y(0),...,y(T-1)) = x(0)$ where $y(k) = CA^k x(0) + e(k)$ for $k=0,...,T-1$.

Methodology
-----------

Let $E_{q,T}$ denote the set of error vectors $\begin{bmatrix} e(0); ~ ...~  ;  e(T-1) \end{bmatrix}   \in  \mathbb{R}^{p\cdot T} $ where each $e(k)$ satisfies $\|e(k)\|_0 \leq q \leq p$. $$\begin{aligned}
 \label{eq:sys_err_corr}
\begin{aligned}
    Y &\triangleq \begin{bmatrix} y(0) \\ y(1) \\ \vdots \\ y(T-1) \end{bmatrix}  = \begin{bmatrix} Cx(0) + e(0)\\ CA x(0) + e(1) \\ \vdots \\ CA^{T-1} x(0) + e(T-1) \end{bmatrix} \\
        & =
        \begin{bmatrix} C \\ CA \\ \vdots \\ CA^{T-1} \end{bmatrix} x(0) + E_{q,T}  \triangleq \Phi x(0) + E_{q,T}
        \label{eq:decoder_Phi}
\end{aligned}\end{aligned}$$ where $Y \in \mathbb{R}^{p\cdot T}$ is a collection of corrupted measurements over $T$ time steps and $\Phi \in \mathbb{R}^{p\cdot T \times n}$ represents an observability-like matrix of the system. Here, we need to assume that $\operatorname{rank}(\Phi) = n$; otherwise, the system is unobservable and we cannot determine $x(0)$ even if there is no attack (i.e., $E_{q,T} = 0$).

Inspired by the error correction techniques proposed in [@Candes_Tao] and [@David_Chang], we first determine the error vector $E_{q,T}$, and then solve for $x(0)$. Consider the $QR$ decomposition of $\Phi \in \mathbb{R}^{p\cdot T \times n}$, $$\begin{aligned}
    \Phi = \begin{bmatrix} Q_1 & Q_2 \end{bmatrix} \begin{bmatrix} R_1 \\ 0 \end{bmatrix} = Q_1 R_1\end{aligned}$$ where $\begin{bmatrix} Q_1 & Q_2 \end{bmatrix} \in \mathbb{R}^{p\cdot T \times p\cdot T}$ is orthogonal, $Q_1 \in \mathbb{R}^{p\cdot T\times n}, Q_2 \in \mathbb{R}^{p\cdot T \times (p\cdot T-n)}$, and $R_1 \in \mathbb{R}^{n\times n}$ is a rank-$n$ upper triangular matrix. Pre-multiplying (\[eq:decoder\_Phi\]) by $\begin{bmatrix} Q_1 & Q_2 \end{bmatrix} ^\top$ gives: $$\begin{bmatrix} Q_1 ^\top \\ Q_2 ^\top \end{bmatrix} Y = \begin{bmatrix}R_1 \\ 0  \end{bmatrix} x(0) + \begin{bmatrix} Q_1 ^\top \\ Q_2^\top \end{bmatrix} E_{q,T}.
    \label{eq:QR}$$ We can compute $E_{q,T}$ by using the second block row: $$\tilde Y \triangleq Q_2^\top Y = Q_2^\top E_{q,T}
    \label{eq:E_est}$$ where $Q_2^\top \in \mathbb {R} ^{ (p\cdot T-n) \times p\cdot T}$. From Lemma \[lem:CS\], (\[eq:E\_est\]) has a unique, $s$-sparse solution (where $s\le q\cdot T$) if all subsets of $2s$ columns (at most $2 q\cdot T$ columns) of $Q_2^\top$ are full rank. Clearly, this is a reasonable assumption if $(p\cdot T-n) \ge 2q\cdot T$. Therefore, we consider solving the following $l_1$-minimization problem: $$\hat{E}_{q,T} = \arg \min_E {\left\lVert E\right\rVert}_{l_1} \text{ s.t. } \tilde Y = Q_2^\top E
    \label{eq:solve_E}$$ Now, given the vector $\hat{E}_{q,T}$, we can compute $x(0)$ from the first block row of (\[eq:QR\]) as follows: $$x(0) = R_1^{-1} Q_1^\top (Y- \hat{E}_{q,T})
    \label{eq:QR1}$$ The following lemma provides the conditions under which the solution to (\[eq:QR1\]) exists and is unique.

\[lem:EC\] $x(0) $ is the unique solution if $\lvert \textsf{supp}( \Phi z) \rvert > 2 s = 2 (q\cdot T)$ for all $z \in \mathbb{R}^n \backslash \{ 0 \}$.

We first prove the claim C1: if $\lvert \textsf{supp}( \Phi z) \rvert > 2 s = 2 (q\cdot T)$ for all $z \in \mathbb{R}^n \backslash \{ 0 \}$ then all subsets of $2s$ columns of $Q_2^\top$ are full rank. Then by Lemma \[lem:CS\] and noting that by definition the null space of $Q_2^\top$ equals the column space of $\Phi$, we have $x(0) $ is the unique solution.

Proof of C1 by contradiction: Suppose there exist $2s$ columns of $Q_2^\top$ that are linearly dependent. Then, there exists $E_0 \neq 0$ such that $Q_2^\top E_0 = 0$ where $\lvert \textsf{supp}(E_0) \rvert \le 2s$. Since the null space of $Q_2^\top$ equals the column space of $\Phi$, there exists $z$ such that $E_0 = \Phi z$ (i.e., $E_0$ is in the column space of $\Phi$). Then, $ \lvert  \textsf{supp}(\Phi z) \rvert = \lvert \textsf {supp} (E_0) \rvert \le 2s $ (contradiction).

The sufficient condition, provided in Lemma \[lem:EC\], for the existence of a unique solution to (\[eq:QR1\]) is hard to check as it requires satisfiability of the condition for all $z \in \mathbb{R}^n \backslash \{ 0 \}$. In the following Theorem, we prove an equivalent, yet simple-to-check, sufficient condition that only needs to be verified for the eigenvectors of $A$.

Let $A \in \mathbb{R}^{n\times n}, C \in \mathbb{R}^{p\times n}$. Assume that $C$ is full rank, $(A,C)$ is observable and $A$ has $n$ distinct positive eigenvalues such that $0 < \lambda_1 < \lambda_2 < \cdots < \lambda_n$. Define:

-   $s_i \triangleq \lvert \textsf{supp} (Cv_i) \vert$, where $v_i$ is an eigenvector of $A$,

-   $\mathcal{S} \triangleq \{ s_1, s_2, \cdots, s_n \}$,

-   For every $m \in \{2, \ldots, n\}$, let $\mathcal{S}_m$ be any subset of $\mathcal{S}$ with $m$ elements, define $T_{\mathcal{S}_m} \triangleq \frac {  (m-2) \cdot p + \min \mathcal{S}_m } {\max \mathcal{S}_m - 2q }$. Then $T_m$ is such that $T_m > T_{\mathcal{S}_m}$ for all subsets $\mathcal{S}_m$, i.e. all subsets of $m$ elements from the set $\mathcal{S}$.

Choose $T$ such that $T \ge \max \{ T_2, \cdots, T_n \}$. Then, the following are equivalent: $$\begin{aligned} 
 (i)  &~\forall v_i \in \mathbb{R}^n \text{ where } Av_i =\lambda_i v_i, \\
    &~ \lvert \textsf{supp}(Cv_i) \rvert > 2q  \\
  (ii)  &~\forall v_i \in \mathbb{R}^n \text{ where } Av_i =\lambda_i v_i,  \\
    &~\lvert \textsf{supp} (\Phi v_i) \rvert > 2q \cdot T  \\
  (iii) &~  \forall z \in \mathbb{R}^n\backslash \{0 \}, \lvert \textsf{supp} (\Phi z) \rvert > 2 q \cdot T\\
  \nonumber 
\label{eq:new_condition}
\end{aligned}$$

Interested readers are referred to the proof for Theorem 1 in our archived paper [@Chang_Qie].

Theorem 1 states that if the feedback system and the secure estimator are designed such that all the conditions in the theorem are satisfied, then our proposed secure estimator can guarantee accurate correction of $q$ errors by checking the following very simple condition: $$\forall v_i \in \mathbb{R}^n \text{ where } Av_i =\lambda_i v_i, ~ \lvert \textsf{supp}(Cv_i) \rvert > 2q.  \nonumber$$

Number of Correctable Errors {#sec:max_q}
----------------------------

Given that the set of attacked nodes can change over time and $e(k)$ satisfies $\lvert \textsf{supp} (e(k)) \rvert \le q$ for all $k$, we prove in Proposition \[prop:maximum\] (see below) that the maximum number of correctable errors (as defined in Definition \[def:num\_err\_change\]) by our decoder is $\lceil p/2-1 \rceil$, where $p$ is the number of measurements.

\[prop:maximum\] Let $A_0 \in \mathbb{R}^{n \times n}$, $B \in \mathbb{R}^{n \times m}$ and $C \in \mathbb{R}^{p \times n}$ and assume that the pair ($A_0$, $B$) is controllable, $C$ is full rank and each row of $C$ is not identically zero. Then there exists a finite set $F \subset \mathbb{R}_+$ such that for any choice of $n$ numbers $\lambda_1, \cdots, \lambda_n \in \mathbb{R}_+ \backslash F$ such that $0<\lambda_1< \cdots < \lambda_n$, there exists $G \in \mathbb{R}^{m \times n}$ such that:

-   The eigenvalues of the closed-loop matrix $A~(= A_0+BG)$ are $\lambda_1, \cdots, \lambda_n$.

-   If the pair ($A, C$) is observable, then the number of correctable errors for the pair ($A, C$) is maximal after $T= \max\{n, T^*\}$ time steps and is equal to $\lceil p/2-1 \rceil$, where $T^*$ is the value of $T$ from Theorem 1.

The proof for Proposition 4 in [@Fawzi2014] shows that if the chosen poles $\lambda_1, \cdots, \lambda_n$ are distinct, positive and do not fall in some finite set $F$, then there is a choice of $G$ such that the eigenvalues of $A~(=A_0+B)$ are exactly $\lambda_1, \cdots, \lambda_n$, and the corresponding eigenvectors $v_i$ are such that $\lvert \textsf{supp} (C v_i) \rvert = p$. Thus, by Theorem 1, the number of correctable errors for $(A,C)$ is $\lceil p/2-1 \rceil$.

In addition, recall that $E_{q,T}$ consists of the error vectors $e(0), \cdots, e(T-1)$ stacked vertically and our proofs for the existence of a unique solution to (\[eq:QR1\]) are independent of how the individual error (nonzero) terms are distributed in the vector $E_{q,T}$. Thus, we can remove the assumption: $\lvert \textsf{supp} (e(k)) \rvert \le q$ for all $k$, and allow $e(k)$ to appear in an arbitrary fashion, e.g. $\lvert \textsf{supp} (e(0)) \rvert = 2q$ and $\lvert \textsf{supp} (e(1)) \rvert = 0$, as long as $\sum_{k=0}^{T-1} \lvert \textsf{supp} (e(k)) \rvert \leq q\cdot T$, then our $q$-error-correcting decoder can still recover the true states. In other words, our proposed secure estimator can protect the system against more general attacks where the number of attacked sensors is not necessarily less than or equal to $q$ at every time step.

Combination of Secure Estimation and Kalman Filter {#sec:estimation}
==================================================

Consider the state estimation problem for the following LTI system under attack: $$\begin{aligned}
x(k+1) & = A x(k) + B u(k)\\
y(k) & = C x(k) + e(k) + v(k),
\end{aligned}$$ where $x$, $y$, $u$ and $e$ are as defined in (\[eq:system\_model\_se\]); and $v$ is a zero mean independent and identically distributed (i.i.d.) Gaussian measurement noise.

A KF can be used to estimate the states by modeling the attack signal as noise. More specifically, define a new measurement noise $\bar{v}(k) = e(k) + v(k)$ to give a new measurement equation $y(k) = C x(k) + \bar{v}(k)$. A KF can then estimate the states from the inputs $u(k)$ and the corrupted measurements $y(k)$ [@KwonACC]. One caveat with this method is that KFs assume zero mean and i.i.d. white Gaussian measurement noise, however, attack signals are usually erratic and may be poorly modeled by Gaussian processes [@KwonACC], i.e., $e(k)$ and consequently, $\bar v(k)$ may not be Gaussian. Take Global Positioning System (GPS) spoofing attacks for example, attack signals are often structured to resemble normal GPS signals or can be genuine GPS signals captured elsewhere. When the system is subjected to attacks that are poorly modeled by Gaussian processes, it is reasonable to expect KFs to fail to recover the true states. On the other hand, our proposed secure estimator does not assume the attack signal to follow any model, and therefore, it works for arbitrary and unbounded attacks. The only assumption is that the number of attacked sensors is sparse, i.e., less than $\lceil p/2-1\rceil$. As the set of attacked sensors becomes less sparse, our secure estimator occasionally fails to recover the true states. Based on these observations, we propose to combine our secure estimator with a KF to improve its practical performance, as detailed in Algorithm 1.

Initialize the KF Estimate the attack signal at time $k$, $\hat e(k)$, using secure estimator Set $\hat e(k) = 0$ Form a new measurement equation: $\tilde y(k) =  C x(k) + \tilde v(k)$, where $\tilde y(k) = y(k) - \hat e(k)$ and $ \tilde v(k) = e (k) - \hat e(k) + v(k)$ Apply standard KF using $u$ and $\tilde y$

The intuition is that the secure estimator acts as a pre-filter for the KF, so that $\tilde v(k)$ is close to a zero mean i.i.d. Gaussian process even when the true attack signal $e(k)$ is not. At most time steps $k$, the secure estimator perfectly recovers $e(k)$, i.e., $\hat e(k) = \hat e(k)$, hence $\tilde v(k) = v(k)$ and thus, is a zero mean Gaussian process. What happens when the secure estimator fails? (\[eq:sys\_err\_corr\]) shows that the estimated state at time $k$, $\hat x(k)$, is independent from the estimated state at another time step $\hat x(l)$ ($l \neq k$). As a result, when the secure estimator fails, its estimation error, $e(k) - \hat e(k)$, appears to be quite random. Putting these together: $\tilde v(k) = e(k) - \hat e(k) + v(k)$ is closer to a zero mean i.i.d. white Gaussian process than $\bar v(k)$ (i.e., the corresponding measurement noise if a KF is applied directly to estimate the states), which improves the KF’s performance. Finally, the *if* statement in Algorithm 1 ensures that the secure estimator always has access to $T$ past measurements.

Next, we demonstrate the effectiveness of our proposed method through simulations of a UAV under two types of adversarial attacks, which also provides a realistic example illustrating the behaviors described in this section.

Numerical Examples
==================

UAV Model
---------

We consider a quadrotor with the following dynamics: $$\begin{aligned}
x(k+1) &= A_0 x(k) + B u(k)  + g\\
y(k) &= C x(k) + e(k) + v(k), \\
\end{aligned}$$ where $x = [p_x, v_x, \theta_x, \dot \theta_x, p_y, v_y, \theta_y, \dot\theta_y, p_z, v_z]^T$ is the state vector. $p_x$, $p_y$ and $p_z$ represent the quadrotor’s position along the $x$, $y$ and $z$ axis, respectively, and $v_i$’s are their corresponding velocities. $\theta_x$ and $\theta_y$ are the pitch and roll angles respectively, and $\dot \theta_i$’s are their corresponding angular velocities. The input vector $u = [\theta_{r,x}, \theta_{r,y}, F]^T$, where $\theta_{r,i}$ is the reference pitch or roll angle, and $F$ is the commanded thrust in the vertical direction. $y = [\tilde{p}_x, \tilde{p}_y, \tilde{p}_z]^T$ represents corrupted position measurements under attack $e$ and measurement noise $v$. The constant vector $g$ represents gravitational effects and can be dropped without loss of generality because we can always subtract it out in $u$. Further details about this model and its derivation can be found in [@Bouffard]. Finally, the matrix $C$ depends on the particular measurements taken in each example.

Decoder Design via Pole-Placement
---------------------------------

We assume that the UAV uses the state feedback control law $u(k) = G x(k)$[^1], where $G$ is the feedback matrix which can be designed. In this section, we show that we can design $G$ to achieve our desired trade-off between the control performance and the secure estimation performance.

If the open loop pair $(A_0, B)$ is controllable, then the closed loop poles can be placed anywhere in the complex plane by appropriate choice of $G$. First, we design a Linear Quadratic Regulator (LQR) and evaluate its secure estimation performance: we check the number of errors that the resulting secure estimator can correct by finding the maximum $q$ for which $\lvert \textsf{supp} (C v_i) \rvert > q$ for all $i$. Figure \[fig:ex\_pole\] shows the results for a matrix $C \in \mathbb{R}^{5\times 10}$ (i.e., 5 measurements). Observe that $\lvert \textsf{supp} (C v_i) \rvert < p = 5$ for $i=1,2,9,10$ and furthermore, $\lvert \textsf{supp} (C v_i) \rvert = 1 > 0$ for $i = 9$ and $10$, which means that the resulting secure decoder can correct zero errors! As shown in Figure \[fig:ex\_pole\], to improve the secure estimation performance, we perturb the closed-loop poles slightly until $\lvert \textsf{supp} (C v_i) \rvert = p$ for all $i$, i.e., we design a secure decoder that can achieve the maximum number of correctable errors within the limits of $p$ (i.e., the number of measurements). By keeping the perturbations on the poles small, our final controller achieves both good control and estimation performances.

![$ \lvert \textsf{supp} (C v_i) \rvert $ for all eigenvectors $v_i$ of the closed-loop matrix $A$ for 2 feedback controllers: a LQR and a controller designed by pole-placement. Black dashed line is at $p = 5$, i.e., the number of measurements.[]{data-label="fig:ex_pole"}](fig/supp_ev_2.pdf){width="40.00000%"}

![Different communication channels that are subjected to cyber attacks.[]{data-label="fig:ex_uav_pic"}](fig/qh/uav_pic.pdf){width="35.00000%"}

UAV under Adversarial Cyber Attack
----------------------------------

### MITM Attack in Communication {#sec:uav_utm}

In this section, we consider MITM attacks targeted at Channels 1 and 2 in Figure \[fig:ex\_uav\_pic\], where a malicious agent spoofs the information being sent and/or received over these channels. The goal of the remote control center or the other UAV is to accurately estimate the true flight path of the target UAV from compromised measurements. Note that the attack does not affect the actual path of the target UAV (as opposed to the GPS spoofing example later in this section).

Assume that the attacker aims to deceive the receiver that the target UAV is deviating in the $x$-direction, therefore she spoofs the $x$-position measurements by injecting a continuous and increasing attack signal in $p_x$. To make the estimation task even harder for the receiver, at each time step, the attacker injects a Gaussian noise to an additional randomly selected measurement, and the choice of this measurement changes over time.

In this example, we first demonstrate the effectiveness of our proposed decoder design using the pole-placement method by comparing the estimation performance of the decoder resulting from (1) a LQR controller and (2) a controller designed using pole-placement as described in the previous section. We then implement the latter controller, and compare the performance of three different estimation schemes: (1) KF only (KF), (2) secure estimator only (SE), and (3) secure estimator combined with KF (KF+SE).

![Estimated attack signal, true attack signal and estimation error in the attack signal of the estimator (SE) with 2 different feedback controllers: LQR, controller designed via pole-placement (PP); with 5 measurements. Left column shows estimated attack signals. Middle column shows true attack signal. Right column shows estimation error. Each row corresponds to one type of measurement. Red pixels indicate positive values, green pixels are negative values and black indicates zero. []{data-label="fig:ex_pp_err"}](fig/qh/uav_pp_error.pdf){width="48.00000%"}

Throughout this example, $y \in \mathbb{R}^5$ and the measurements include the $x$, $y$ and $z$ positions and two additional randomly selected states. Figure \[fig:ex\_pp\_err\] compares the accuracy of the estimated attack signals by the LQ regulator (top) and the one designed via pole-placement (bottom). In each plot, one row corresponds to one sensor, and the first 3 rows are the $x$, $y$ and $z$ position measurements, respectively. The color of the pixel indicates the value of the signal or the estimation error. The middle plots show the true attack signal and they highlights three points: first, the attacked sensors change with time; second, the number of attacked sensors at each time step $k$ is less or equal to 2; third, only position measurements are corrupted. The left plots show the estimated attacked signal by each decoder. It is easy to see that the decoder resulting from a feedback controller designed via pole-placement estimates the attack signal much more accurately. The right plots of this figure highlight this observation by explicitly showing the estimation error of the attack signal for each measurement.

Figure \[fig:ex\_uav\_remote\] compares the estimated flight paths by all three methods: KF, SE and KF+SE. The UAV starts from the blue triangle and follows the solid blue line to land at the blue square. The estimated paths by each method are shown in red dashed lines. Observe that the KF fails to filter out the attack signal in the $x$-position measurements as the attack is highly non-Gaussian, and the estimated trajectory differs significantly from the true one. On the other hand, SE correctly estimates most portions of the trajectory and the final position of the vehicle, nevertheless it gives spontaneous errors. Finally the combined method KF+SE perfectly recovers the true path of the target UAV.

![Estimated UAV trajectory by three methods under MITM attack: KF only (KF), secure estimator only (SE), secure estimator with KF (KF+SE). Solid blue lines are the true UAV trajectories. They start from the blue triangle and end at the blue square. Red dashed lines represent estimated trajectories by each method, with 5 measurements.[]{data-label="fig:ex_uav_remote"}](fig/qh/uav_lq_traj){width="50.00000%"}

![Desired and actual UAV trajectory in different cases: KF and KF+SE, each using 3, 5 and 8 different measurements. Blue solid lines are the desired trajectory. Red dash lines are the actual UAV trajectory under adversarial attack.[]{data-label="fig:ex_uav_traj"}](fig/qh/uav_lqg_traj){width="50.00000%"}

### GPS Spoofing

In this section, we focus on adversarial attacks in the GPS navigation system (Channel 3 in Figure \[fig:ex\_uav\_pic\]). Consider the scenario where a UAV uses a Linear Quadratic Gaussian (LQG) controller to follow a desired trajectory, $x_r(k)$. In other words, a KF uses corrupted and noisy measurements $y(k)$ to produce a state estimate $\hat x(k)$, which is then used for state feedback control: $u(k) = G (\hat x(k) - x_r(k))$, where $G$ is the feedback matrix. Note that in the previous example (Section \[sec:uav\_utm\]), the feedback controller had access to uncompromised state measurements $x(k)$, therefore the true trajectory of the UAV is unaffected by attacks. In this example, however, the UAV uses estimated states $\hat x(k)$ for feedback control and path following. Therefore, if the measurements are corrupted and the state estimates are poor, then the UAV may deviate away from its desired path. Hence, the goal of the UAV is to accurately follow its planned trajectory in the presence of cyber attacks.

Assume an attacker spoofs the GPS position measurements in order to deviate the UAV from its desired path. She injects a sinusoidal signal into the $x$ position measurement, as well as a Gaussian noise to a randomly chosen position measurement at each time step.

In this example, we explore the effect of the number of sensor measurements on the secure estimation performance of two schemes: (a) KF only, (b) KF+SE. First, we assume that the UAV only uses GPS for navigation, i.e., 3 positional measurements. Figure \[fig:ex\_uav\_traj\] shows that KF completely fails to estimate the attack signal (KF, $n_y = 3$), consequently, the actual UAV trajectory (red dashed line) deviates significantly from its desired path (solid blue line). On the other hand, the combined method KF+SE’s estimated attack signals are significantly more accurate, therefore the UAV can follow its planned path much more closely (Figures \[fig:ex\_uav\_traj\], KF + SE, $n_y = 3$). Recall from Proposition \[prop:maximum\] that the maximum number of correctable errors for a system with $p$ measurements is $\lceil p/2-1 \rceil$, which equals 1 in this case. However, at any time step $k$, there are at most 2 attacked sensors, which exceeds the above limit and explains the estimation error of the combined method KF+SE. Despite this small estimation error, KF+SE still outperforms the KF.

Next, we show the effect of increasing the number of measurements ($n_y$, or equivalently $p$) on the estimation performance and consequently, the UAV’s path following performance. This can be achieved through sensor fusion. For example, autonomous UAVs often use IMUs in addition to GPS for navigation, the former provides additional measurements such as the UAV’s velocities, pitch and roll angles. Figure \[fig:ex\_uav\_traj\] shows that increasing the number of measurements has no effect on the KF’s estimation accuracy and hence, its path following ability. Even when 8 measurements are used the UAV equipped with a KF still fails to follow the desired trajectory. On the other hand, increasing the number of measurements improves the estimation performance of the secure estimator SE and consequently the performance of the combined scheme KF+SE. Figure \[fig:ex\_uav\_traj\] shows that when 5 and 8 measurements are used, the UAV can follow its original planned path perfectly (KF + SE $n_y=5$ and KF + SE $n_y=8$).

Conclusion {#conclusion .unnumbered}
==========

In this paper, we consider the estimation problem for UAVs under adversarial cyber attack and propose a secure estimation based KF that is computationally efficient and makes no assumptions about the attack signal model. We demonstrate that our proposed secure estimator outperforms standard KF, using numerical examples of UAVs under adversarial cyber attacks. This is important not only for today’s aviation system but also delivery systems with drones in the near future.

Copyright Statement {#copyright-statement .unnumbered}
===================

[^1]: In the GPS spoofing example, direct uncorrupted state measurements are not available. Therefore a KF is used to give estimated states which are then used for state feedback control.
