Coded Estimation: Design of  Backscatter Array Codes for 3D Orientation Estimation

M. Rida Rammal^⋆, Suhas N. Diggavi^⋆, and Ashutosh Sabharwal^†

^⋆Department of Electrical and Computer Engineering, UCLA.

^†Department of Electrical and Computer Engineering, Rice University.

We consider the problem of estimating the orientation of a 3D object with the assistance of configurable backscatter tags. We explore the idea of designing tag response codes to improve the accuracy of orientation estimation. To minimize the difference between the true and estimated orientation, we propose two code design criteria. We also derive a lower bound on the worst-case error using Le Cam's method and provide simulation results for multiple scenarios including line-of-sight only and multipath, comparing the theoretical bounds to those achieved by the designs.

§ INTRODUCTION

3D orientation tracking is an important function in many domains, e.g., in robotics, aerospace, and medicine. Orientation can be estimated using many methods, e.g., inertial sensors can be mounted on the object whose orientation has to be measured.  Orientation can also be measured using a computer vision based methods[1, 2, 3, 4]. Each of the existing methods have their own pros and cons. For example, inertial sensors may not be suitable for many Internet-of-Things applications, e.g., tracking packages where the solutions have to be very  cost-effective. Additionally, the performance of computer vision methods  methods depends on light conditions, and can be confused for objects that exhibit symmetries. As an extreme example of that
last problem, one can rotate a cube in many ways such that it would look precisely the same as it did prior to rotation.

Wireless sensing has emerged as an interesting alternative sensing modality. Radio-frequency based methods can be useful when visible light wavelengths are not effective, e.g., cases with poor visibility or non-line-of-sight scenarios. In particular, backscatter arrays have been recently used for geo-location and 3D orientation estimation[5, 6, 7, 8]. Using backscatter arrays is philosophically akin to “painting the faces" of an object, making it a promising option for the orientation detection of symmetric objects such as the solid cube in the last example. In this work, we study 3D orientation estimation with the help of configurable backscatter arrays.

In order to aid with the estimation task, one can design the backscatter response to received signals. Specifically, we design the backscatter responses by changing their reflectivities. The design can be captured as a binary code specifying what or when the backscatter tags reflect. The problem of finding the best code for the estimation task was first formulated and explored in [9], where we proposed a heuristic code design criterion and had a preliminary exploration of the systems performance.

Contributions: In this paper, we revisit the problem and expand our understanding in the following ways. First, we propose two analytic code design criteria that depend on channel knowledge, and investigate their performance with respect to a baseline orthogonal code. We also develop a lower bound on the worst-case error, which quantifies the systems performance with respect to channel parameters such as the number of antennas and the number of tags used. Finally, we provide a comprehensive numerical exploration of the systems performance, including the impact of multipath, and the robustness of the design criteria against imperfect channel knowledge.

By numerically evaluating the performance, we observe the following. Our design criteria yield codes that offer significant advantages over the channel-oblivious orthogonal code for both the average and worst-case error performance (see Section <ref> for precise definitions). In some cases, our designs provide two orders of magnitude improvements in error performance. We also found that precise channel knowledge at the transmitter is not critical; Our design criteria are robust against channel estimation errors, retaining almost all improvements when computed with SNR values greater than or equal to $10\mathrm{dB}$.  Furthermore, our numerical results suggest that multipath offers SNR gain but not multipath-diversity gain; this means that when one fixes the total energy received across paths, the performance does not improve when multipath is present.

Related work: In [9], we suggested a heuristic design criteria aimed at maximizing the average-case performance, but did not make attempts to assess its performance. Furthermore, we only considered the average-case error of the system, and did not study the worst-case error, explored in this paper. In  [7, 8, 10], the authors present various methods for orientation estimation (2D or 3D) using backscatter tags, but do not explore the design of backscatter responses and its effect on the estimation problem. In [11], the authors use orthogonal codes (see Section <ref> for a definition) to distinguish the tags from each other and the environment. However, none of these past works has considered optimal code design for 3D orientation sensing.

Organization: Section <ref> describes the channel model and formulates the estimation problem.  Section <ref> describes the main results, including the two code design criteria. Section <ref> provides the various numerical results. Finally, Section <ref> provides proofs for the theorems and lemmas shown in Section <ref>.

§ PROBLEM FORMULATION

[txantenna, scale =0.25] at (-3,0.25) ;
[text width=0cm] at (-2.7,0) ⋮;
[rxantenna, scale=0.25] at (-3,-1) ;
(-1,0) arc (180:360:1cm and 0.5cm);

[dashed] (-1,0) arc (180:0:1cm and 0.5cm);
(0,1) arc (90:270:0.5cm and 1cm);
[dashed] (0,1) arc (90:-90:0.5cm and 1cm);
(0,0) circle (1cm);
[ball color=blue!10!white,opacity=0.20] (0,0) circle (1cm);

[draw, fill=red, star,star points=7,star point ratio=0.8, inner sep=1.5] at (-0.44,-0.44) ;
[draw, fill=red, star,star points=7,star point ratio=0.8, inner sep=1.5] at (0.44,0.44) ;
[draw, fill=red, star,star points=7,star point ratio=0.8, inner sep=1.5] at (-1,0) ;
[draw, fill=red, star,star points=7,star point ratio=0.8, inner sep=1.5] at (0,-1) ;

(2 - ,) arc (180:360:0.125 cm and 0.0625 cm);
[densely dotted] (2 - ,) arc (180:0:0.125 cm and 0.0625 cm);
(2,0.125+) arc (90:270:0.0625 cm and 0.125 cm);
[densely dotted] (2,0.125+) arc (90:-90:0.0625 cm and 0.125 cm);
(2,) circle (cm);
[ball color=blue!10!white,opacity=0.20] (2,) circle (cm);
[draw, fill=red, star,star points=7,star point ratio=0.8, inner sep=1.5] at (2, - 0.375+) ;
[antenna, scale=0.125] at (2, -0.925+);

draw = black,
minimum width = 1.75cm,
minimum height = 1.5cm] (r) at (2.5,0.37) ;
[] at (2.65, 0.75) Object;
[] at (2.55, 0.35) Tag;
[] at (2.75, -0.025) Antenna;

The components of the considered system. The object along with the tags, rotate around a specific point (in this case, the center of the sphere). The full-duplex antennas interrogate the configurable tags and receive back the reflected signal. We then use the received signal to infer the orientation.

§.§ Notation

$\mathbb{R}^k$ and $\mathbb{C}^k$ are the sets of real-valued and complex-valued $k-$dimensional vectors, respectively. $A^T$ and $A^H$ denote the transpose and conjugate transpose of the matrix $A$. If $\mathbf{x}$ is a vector with $n$ elements, then $\textrm{diag}(\mathbf{x})$ denotes the $n\times n$ square matrix with the elements of $\mathbf{x}$ on its main diagonal;   $\left\lVert \cdot \right\rVert$ is the standard Euclidean norm on vectors, and $\left\lVert \cdot \right\rVert_F$ is the Frobenius norm on matrices.

§.§ System Model

We assume a system having $K$ full-duplex antennas with position vectors
$\mathbf{x}_1^{\textrm{ant}}, \ldots,\mathbf{x}_K^{\textrm{ant}}\in\mathbb{R}^3$, and $N$ backscatter tags with position vectors $\mathbf{x}_1^{\textrm{tag}},\ldots, \mathbf{x}_N^{\textrm{tag}}\in\mathbb{R}^{3}$. We consider an object on which we place the $N$ configurable backscatter tags. The object can freely rotate around a specific point in space. For ease of computation, we consider the coordinate system in which the point that the object rotates around is the center $\textbf{0} = [0, 0, 0]^T$ (see Figure <ref>).

We specify the orientation of the object using a rotation matrix $Q\in SO(3)\subseteq \mathbb{R}^{3\times 3}$, where $SO(3)$ is the 3D rotation group. If the object has tags with positions $\mathbf{x}_1^{\textrm{tag}},\ldots, \mathbf{x}_N^{\textrm{tag}}$ on it, and a rotation $Q$ is applied to the object, the tags would have the new positions $Q\mathbf{x}_1^{\textrm{tag}},\ldots, Q\mathbf{x}_N^{\textrm{tag}}$ (see Figure <ref>). In this framework, we specify the original orientation of the object using the $3\times 3$ identity matrix $I_3$.

Each backscatter tag can be configured by setting its state to a value $i\in \{0,1\}$. The state, in turn, determines the reflectivity of the tag. For instance, we may choose to correspond a state of $0$ to a reflectivity of $+0.5$ and a state of $1$ to a reflectivity of $-0.5$. In this scenario, tags reflect regardless of the their state. On the other hand, we may choose to correspond a state of $0$ to a reflectivity of $0$ (does not reflect), and a state of $1$ to a reflectivity of $1$ (reflects) i.e. the state determines the on-off condition of the tag. In addition, the state of each tag can either remain constant (passive) or change over time (active). We study the performance of both options.

The orientation of the object determines the position of the tags, and the states of the tags set their reflectivities. Hence, the orientation and tag states determines the channel model, and in turn the received signal. We use the received signal to estimate the orientation of the object. Our goal is to analyze the performance of this system, and find the best set of tag states for the estimation task. We describe our channel model next.

[tdplot_main_coords, scale=0.7]
group style=group size= 2 by 1, vertical sep=0cm, horizontal sep = -1 cm ,

[axis equal,
axis lines = center,
xlabel = $x$,
ylabel = $y$,
zlabel = $z$,
xmin = -0.65,
xmax = 1.15,
ymin = -0.65,
ymax = 1.15,
zmin = -0.55,
zmax = 1.2,
scale uniformly strategy=units only,]
opacity = 1,
z buffer = sort,
samples = 21,
variable = ,̆
variable y = ,̌
domain = 0:180,
y domain = 0:360,
faceted color=black,
(cos(u)*sin(v), sin(u)*sin(v), cos(v));

[axis equal,
axis lines = center,
xlabel = $x$,
ylabel = $y$,
zlabel = $z$,
xmin = -0.65,
xmax = 1.15,
ymin = -0.65,
ymax = 1.15,
zmin = -0.55,
zmax = 1.2,
scale uniformly strategy=units only,]
opacity = 1,
z buffer = sort,
samples = 21,
variable = ,̆
variable y = ,̌
domain = 0:180,
y domain = 0:360,
faceted color=black,
(cos(u)*sin(v), sin(u)*sin(v), cos(v));

[draw, fill=red, star,star points=7,star point ratio=0.8, inner sep=1.5] at (3.78,3.04, 6.95) ;
[draw, fill=red, star,star points=7,star point ratio=0.8, inner sep=1.5] at (2.81,3.45, 5.45) ;
[draw, fill=red, star,star points=7,star point ratio=0.8, inner sep=1.5] at (4.57,5, 7.22) ;
[draw, fill=red, star,star points=7,star point ratio=0.8, inner sep=1.5] at (3,5.35, 7.25);
[->,color=black, line width=0.32mm](0,3.33,7.35)0.50340anchor=south west,color=black;
[thick, -stealth,decorate,decoration=snake,amplitude=3pt,pre length=2pt,post length=3pt] (3.78,3.04, 6.95) – ++(-1,-1,-1) node [font=3pt3pt,left]$\mathbf{x}_1^{\mathrm{tag}}$;
[thick, -stealth,decorate,decoration=snake,amplitude=3pt,pre length=2pt,post length=3pt] (2.81,3.45, 5.45) – ++(-2.2,-2.2,-2.2) node [font=3pt3pt, left]$\mathbf{x}_2^{\mathrm{tag}}$;

[draw, fill=red, star,star points=7,star point ratio=0.8, inner sep=1.5] at (3.78 +,3.04 +, 6.95 + ) ;
[draw, fill=red, star,star points=7,star point ratio=0.8, inner sep=1.5] at (-1,11.05, 5.57) ;
[draw, fill=red, star,star points=7,star point ratio=0.8, inner sep=1.5] at (1.57,11.2, 6.2) ;
[draw, fill=red, star,star points=7,star point ratio=0.8, inner sep=1.5] at (0,11.83, 7.37);

[-stealth,decorate,decoration=snake,amplitude=3pt,pre length=2pt,post length=3pt, thick]  (3.78 +,3.04 +, 6.95 + ) – ++(-1.95,-1.95,-1.45) node [ left]$Q\mathbf{x}_1^{\mathrm{tag}}$;
[-stealth,decorate,decoration=snake,amplitude=3pt,pre length=2pt,post length=3pt, thick] (1.57,11.2, 6.2) – ++(-3.75,-3.75,-3.25) node  [left]$Q\mathbf{x}_2^{\mathrm{tag}}$;

Rotation of the object about the $z$-axis. When the object rotates, the tags rotate along with it. The new positions of the tags produce a different received signal. While the tags are equidistant from the point of rotation in the figure, this does not have to be the case.

We use the following free-space path loss formula for line-of-sight propagation[12] between points $\mathbf{x}_1,\mathbf{x}_2\in\mathbb{R}^3$:

\begin{equation}
\label{eq:free_loss}
\eta(\mathbf{x}_1,\mathbf{x}_2) =  \frac{1}{4\pi\left\lVert \mathbf{x}_1-\mathbf{x}_2\right\rVert}\textrm{exp}\left(\frac{-2\pi j \left\lVert \mathbf{x}_1-\mathbf{x}_2\right\rVert}{\lambda}\right),
\end{equation}

where $\lambda$ is the wavelength. In other words, suppose $\mathbf{x}_{\mathrm{T_x}}$ and $\mathbf{x}_{\mathrm{R_x}}$ are the position vectors of an isolated transmitter and receiver, and $s_{\mathrm{T_x}}$ and $s_{\mathrm{R_x}}$ the transmitted and received signals, respectively, then

\begin{equation}
\label{eq:free_loss_example}
s_{\mathrm{R_x}} = s_{\mathrm{T_x}}\eta(\mathbf{x}_{\mathrm{T_x}}, \mathbf{x}_{\mathrm{R_x}}).
\end{equation}

We now specify the matrices involved in our channel model. Let $H_Q$ be the $K\times N$ matrix of the line-of-sight responses between the tags and antennas when the object is in orientation $Q$, i.e. $(H_Q)_{k,n} = \eta(\mathbf{x}_k^{\textrm{ant}}, Q\mathbf{x}_n^{\textrm{tag}})$. Let $A$ be the symmetric $K\times K$ matrix of inter-antenna line-of-sight responses with $A_{k,k'} = \eta(\mathbf{x}_k^{\textrm{ant}},\mathbf{x}_{k'}^{\textrm{ant}})$. Let $B$ be the symmetric $N\times N$ matrix of the inter-tag channel responses when the object is in orientation $Q$. In other words,

\begin{equation}
(B_Q)_{n,n'} = \eta(Q\mathbf{x}_n^{\textrm{tag}},Q\mathbf{x}_{n'}^{\textrm{tag}}) = \eta(\mathbf{x}_n^{\textrm{tag}},\mathbf{x}_{n'}^{\textrm{tag}}).
\end{equation}

Applying the same rotation to any two tags does not change the distance between them, so we can drop $Q$ from the subscript of $B_Q$ and use $B$ instead (see Figure <ref>). Now, let $\mathbf{s}_t$ and $\mathbf{s}_t'$ be the vectors of the transmitted signals at the antennas and tags respectively at time $t$, and $\mathbf{\Psi}_t$ and $\mathbf{\Psi}_t'$ be the vectors of the received signals at the antennas and tags respectively at time $t$. The relationship between these vectors is given by:

\begin{equation}
\label{eq:signal_rel}
\begin{bmatrix}
\mathbf{\Psi}_t \\
\mathbf{\Psi}_t'
\end{bmatrix} = \begin{bmatrix}
A & H_Q \\
H_Q^T & B
\end{bmatrix}\begin{bmatrix}
\mathbf{s}_t \\
\mathbf{s}_t'
\end{bmatrix}.
\end{equation}

As mentioned before, each backscatter tag can be configured by setting its state to a value $i\in \{0,1\}$, which in turn determines its reflectivity $r_i\in \mathbb{C}$. Hence, the reflectivities can expressed in terms of the states assigned to the tags. Letting $s_{t,n}$ be the state of the $n^{\mathrm{th}}$ tag at time $t$, $\mathbf{c}_t = (s_{t,1},\ldots,s_{t,N})$ be the codeword at time $t$ (a codeword is a vector of states), and $r(\cdot)$ be the mapping from codewords to reflectivity vectors, we define the matrix of reflectivities at time $t$ as:

\begin{align}
\label{reflectivities}
R_t &= \textrm{diag}(r(\mathbf{c}_t)).
\end{align}

Using the fact that the tags reflect the incident signals, the transmitted signal at the tags is given by $\mathbf{s}_t' = R_t\mathbf{\Psi}_t'$. Substituting the value of $s_t'$ in (<ref>), we obtain the following equations:

\begin{align}
\mathbf{\Psi}_t &= A\mathbf{s}_t + H_QR_t\mathbf{\Psi}_t' \\
\mathbf{\Psi}_t'&= H_Q^T\mathbf{s}_t + BR_t\mathbf{\Psi}_t'
\end{align}

Solving the above equations, we obtain that the received signal is given by $\mathbf{\Psi}_t = As_t + H_QR_t(I - BR_t)^{-1}H_Q^T\mathbf{s}_t$. Since the first term in the previous expression does not depend on $Q$, we can subtract it at the receiver[We are eliminating full-duplex self-interference, e.g., see [13].] yielding a modified noiseless signal $\mathbf{f}(Q;\mathbf{c}_t)\in\mathbb{C}^K$ given by:

\begin{equation}
\label{eq:static_output}
\mathbf{f}(Q;\mathbf{c}_t) =  H_QR_t(I - BR_t)^{-1}H_Q^T\mathbf{s}_t.
\end{equation}

§.§ Codes

[bareantenna, scale=0.5] at (0,-1) ;
[] (0,-1)–(0,-1.5);
[->, ultra thick] (0.25,-1)  – (2.1,-1) node[midway, above] $A_{k,\ell}$;
[bareantenna, scale=0.5] at (2.45,-1) ;
[] (2.45,-1)–(2.45,-1.5);
[] at (-0.75,-1) ant $k$;
[] at (3.2,-1) ant $\ell$;

[draw, fill=red, star,star points=7,star point ratio=0.8, inner sep=5] at (0,0+) ;
[] at (-0.75,0+) tag $i$;
[->, ultra thick] (0.35,0+)  – (2.1,0+) node[midway, above] $B_{i,j}$;
[draw, fill=red, star,star points=7,star point ratio=0.8, inner sep=5] at (2.45,0+) ;
[] at (3.2,0+) tag $j$;

[bareantenna, scale=0.5] at (0,0+) ;
[] (0,)–(0,-0.5+);
[] at (-0.75,0+) ant $k$;
[->, ultra thick] (0.35,0+)  – (2.1,0+) node[midway, above] $H_{Q,k,i}$;

[draw, fill=red, star,star points=7,star point ratio=0.8, inner sep=5] at (2.45,0+) ;
[] at (3.2,0+) tag $i$;

The matrices associated with the model. For instance, $A_{k,\ell}$ corresponds to the free space loss from antennas $k$ to antenna $\ell$.

The expression in (<ref>) is the noiseless channel output when using a codeword $\mathbf{c}_t$. Based on numerical simulations, we have observed that a single codeword often only allows us to detect some orientations, and not others. Specifically, all tag arrays we came across had the following property: for every codeword $\mathbf{c}\in \{0,1\}^N$, there exists some $Q,Q'$ such that $Q\neq Q'$ and $\mathbf{f}(Q;\mathbf{c}) \approx \mathbf{f}(Q';\mathbf{c})$ (see Figure <ref> in Section <ref> for such an array). In other words, for every codeword, there is a pair of orientations that the codeword makes almost indistinguishable based on the received signal.

Therefore, using different codewords over time is a natural extension to the model as a new codeword could fill in the gaps left by the ones used previously. Based on this intuition, we define a code $C = [\mathbf{c}_1 \cdots \mathbf{c}_T]\in\{0,1\}^{N\times T}$ to be a binary matrix where each column corresponds to the codeword at a specific time $t$ (See Figures <ref>,<ref>). Given the code $C$, we denote the concatenated channel output as (using $F$ instead of $f$):

\begin{align}
\label{eq:concatenated_output}
F(Q;C) &= \begin{bmatrix}
\mathbf{f}(Q;\mathbf{c}_1) &
\cdots &
\mathbf{f}(Q;\mathbf{c}_T)
\end{bmatrix} \in \mathbb{C}^{K\times T}.
\end{align}

§.§ Performance Measures

We consider estimation over finite uniform subset of orientations $\mathcal{Q}\subset \mathrm{SO}(3)$, and use the loss function $\theta(Q,Q')$, equal to the Frobenius norm between the two rotation matrices i.e.,

\begin{equation}
\label{eq:rotation_distance}
\theta(Q,Q') = \left\lVert Q - Q'\right\rVert_F.
\end{equation}

Letting $C$ be any code, and $W$ be complex Gaussian noise, we define the noisy received signal as:

\begin{equation}
\label{eq:noisy_output}
Y=F(Q;C) + W.
\end{equation}

Hence, the unnormalized average error of coding matrix $C$ is given by:

\begin{equation}
\label{eq:avg_error}
\mathcal{L}(C) = \sum_{Q\in \mathcal{Q}} \mathbb{E}_{W} \left[\theta(\widehat{Q}(Y), Q)\right],
\end{equation}

where $\widehat{Q}(Y)$ is the minimum distance decoder to the grid of orientations $\mathcal{Q}$ i.e., the MMSE estimator of $Q$ given $Y$. Note if the orientation is considered a random variable, we implicitly assume a uniform prior over the orientations in $\mathcal{Q}$. Now, a code that minimizes the average error could still provide poor performance for a particular orientation. For this reason, we study the worst-case error as it delivers guarantees on the performance across all possible orientations. We define worst-case error (over all possible orientations in $\mathcal{Q}$) as:

\begin{equation}
\label{eq:worst_error}
\mathcal{M}(C) = \max_{Q\in \mathcal{Q}} \mathbb{E}_W \left[\theta(\widehat{Q}(Y), Q)\right].
\end{equation}

We believe that both quantities are of interest for designing an orientation estimation system and hence, we suggest criteria for minimizing either depending on the application's particular requirements.

[width=6.5em, height=2.5em]TagTime     1     2     $\cdots$     T
1     [baseline=0]
[draw, fill=blue(munsell), star,star points=7,star point ratio=0.8, inner sep=2.5] ;    1mm
[draw, fill=blue(munsell), star,star points=7,star point ratio=0.8, inner sep=2.5] ;    1mm
$\cdots$     [baseline=0]
[draw, fill=amber, star,star points=7,star point ratio=0.8, inner sep=2.5] ;    1mm

2     [baseline=0]
[draw, fill=amber, star,star points=7,star point ratio=0.8, inner sep=2.5] ;    1mm
[draw, fill=amber, star,star points=7,star point ratio=0.8, inner sep=2.5] ;    1mm
$\cdots$     [baseline=0]
[draw, fill=blue(munsell), star,star points=7,star point ratio=0.8, inner sep=2.5] ;    1mm

⋮    ⋮       ⋮    $\ddots$     ⋮

N     [baseline=0]
[draw, fill=blue(munsell), star,star points=7,star point ratio=0.8, inner sep=2.5] ;    1mm
[draw, fill=amber, star,star points=7,star point ratio=0.8, inner sep=2.5] ;    1mm
$\cdots$     [baseline=0]
[draw, fill=amber, star,star points=7,star point ratio=0.8, inner sep=2.5] ;    1mm

An illustration of coding over time. Different colors denote different states (reflectivities) of the tag, and different patterns of the states denote different codewords.

tikz/mymatrixenv/.style=decoration=brace,every left delimiter/.style=xshift=8pt,every right delimiter/.style=xshift=-8pt
tikz/mymatrix/.style=matrix of math nodes,nodes in empty cells,
left delimiter=[,right delimiter=],inner sep=1pt,outer sep=1.5pt,
column sep=8pt,row sep=8pt,nodes=minimum width=20pt,minimum height=10pt,
anchor=center,inner sep=0pt,outer sep=0pt,scale=,transform shape

fill=green!50!lime!60,draw opacity=0.4,
draw=green!50!lime!60,fill opacity=0.1,
fill=cyan!90!blue!60, draw opacity=0.4,
draw=blue!70!cyan!30,fill opacity=0.1,
fill=orange!90, draw opacity=0.8,
draw=orange!90, fill opacity=0.3,
fill=brown!70!orange!40, draw opacity=0.4,
draw=brown, fill opacity=0.3,
fill=violet!90!pink!20, draw opacity=0.5,
draw=violet, fill opacity=0.3,
fill=red!90, draw opacity=0.5,
draw=red, fill opacity=0.3,

The associated matrix to the coding over time example in Figure $4$.

§ MAIN RESULTS

Our goal is to find the best code for the estimation task. However, $\mathcal{L}(C)$ in (<ref>) and $\mathcal{M}(C)$ in (<ref>) are intractable. One route we could take is to investigate tractable upper or lower bounds on the errors, and minimize those bounds as a proxy for minimizing the errors themselves.

§.§ Design Criterion For The Average Error

As a proxy for the average error $\mathcal{L}(C)$, we minimize an upper bound to it. We obtain the upper bound on the average error by replacing the probability of misestimating the actual orientation of the object by a tractable quantity. The proof of the following result is given in Section <ref>.

Assuming complex white Gaussian noise, the average error $\mathcal{L}(C)$ given in (<ref>) is upper bounded by:

\begin{align}
\label{eq:upper_bound}
\mathcal{U}(C) = \sum_{Q,Q'\in \mathcal{Q}} \mathrm{erfc}\left(\frac{\left\lVert F(Q;C) - F(Q';C) \right\rVert_F}{2\sqrt{2}\sigma}\right) \theta(Q, Q').
\end{align}

where $\theta(Q,Q')$ is given in (<ref>), $\mathrm{erfc}$ is the complement of the Gaussian error function, and $\sigma$ is the standard deviation of the noise.

Hence, the design criteria for minimizing the average error is simply given by the optimization problem $\min_C \mathcal{U}(C)$.
We can infer the following intuition from $\mathcal{U}(C)$ in (<ref>): good codes should map orientations that are far apart (in terms of $\theta$) to channel outputs that are also far apart. Moreover, since $\mathrm{erfc}(x)$ is tightly upper bounded by $\mathrm{exp}(-x^2)$, $\mathcal{U}(C)$ implies that the distance between channel outputs  $\left\lVert F(Q;C) - F(Q';C) \right\rVert_F$ has an inverse exponential relationship with the average error.

[width=6.5em, height=2.5em]TagTime     1     2     $\cdots$     T
1     [baseline=0]
[draw, fill=blue(munsell), star,star points=7,star point ratio=0.8, inner sep=2.5] ;    1mm
[draw, fill=blue(munsell), star,star points=7,star point ratio=0.8, inner sep=2.5] ;    1mm
$\cdots$     [baseline=0]
[draw, fill=amber, star,star points=7,star point ratio=0.8, inner sep=2.5] ;    1mm

2     [baseline=0]
[draw, fill=amber, star,star points=7,star point ratio=0.8, inner sep=2.5] ;    1mm
[draw, fill=amber, star,star points=7,star point ratio=0.8, inner sep=2.5] ;    1mm
$\cdots$     [baseline=0]
[draw, fill=blue(munsell), star,star points=7,star point ratio=0.8, inner sep=2.5] ;    1mm

⋮    ⋮       ⋮    $\ddots$     ⋮

N     [baseline=0]
[draw, fill=blue(munsell), star,star points=7,star point ratio=0.8, inner sep=2.5] ;    1mm
[draw, fill=amber, star,star points=7,star point ratio=0.8, inner sep=2.5] ;    1mm
$\cdots$     [baseline=0]
[draw, fill=amber, star,star points=7,star point ratio=0.8, inner sep=2.5] ;    1mm

§.§ Codes For the Worst-Case Error

Whereas we optimize an upper bound for the average error in Section <ref>, we obtain a lower bound on the worst-case error $\mathcal{M}(C)$ using Le Cam's method[14], and minimize the bound to obtain a code for the worst-case performance. The proof of the following theorem is provided in Section <ref>.

Assuming complex white Gaussian noise, the worst-case error $\mathcal{M}(C)$ given in (<ref>) is lower bounded by:

\begin{multline}
\label{eq:lower_bound}
\mathcal{V}(C) = \max_{Q,Q'\in \mathcal{Q}}\mathrm{exp}\left({-\frac{\left\lVert F(Q;C) - F(Q';C)\right\rVert_F^2}{2\sigma^2}}\right)\\
\frac{\theta(Q, Q')}{4},
\end{multline}

where $\theta(Q,Q')$ is given in (<ref>).

Hence, the design criteria for minimizing the worst-case error is given by the optimization problem $\min_C \mathcal{V}(C)$. $\mathcal{V}(C)$ corroborates the observations from Theorem <ref>, and relates the worst-case error to the model only through the distances between channel outputs. $\mathcal{V}(C)$ again implies that the worst-case error has an inverse exponential relationship with $\left\lVert F(Q;C) - F(Q';C) \right\rVert_F$.

§.§ Minimax Bound

Unlike Theorem <ref> which suggests a design criteria for the worst-case error using Le Cam's method, the following theorem uses the same tools to quantify the worst-error error decay with parameters including the number of antennas $K$, the number of tags $N$ through the Frobenius norm of $X^{\mathrm{tag}}$, and the number of samples through the variance $\sigma^2$ (as the effective variance of the noise is $\sigma^2/n$ when provided with $n$ samples). It also reflects the effect of code design on the error.

The worst-case error is bounded as:

\begin{align}
\label{eq:LecCamBound}
\mathcal{M}(C) \geq \frac{32\pi^2\lambda^2\sigma^2 D^4}{27K^2 \left\lVert X^{\mathrm{tag}}\right\rVert_F^2 \sum_{t=1}^T \lVert \widetilde{B}_t\rVert_F^2\left\lVert r(\mathbf{c}_t)\right\rVert^2}
\end{align}

where $\widetilde{B}_t= (I-BR_t)^{-1}$ and $D$ is an approximate range between the tagged object and the antennas.

The bound indicates that placing the tags far away from the antennas leads to a larger error. This is clear as the farther away the tags, the weaker the signal we receive due to attenuation. Moreover, it implies an inverse quadratic relationship between the number of antennas and the error. This is again logical because we would be able to receive more power from the reflected signal with more antennas. The bound also reflects the effect of code design through the term $\Vert \tilde{B}_t \Vert_{F}^{2}\left\lVert r(\mathbf{c}_t)\right\rVert^2$. For instance, if tags can have each have one of two states with corresponding reflectivities $0$ and $1$ (on or off), then the bound favors most tags to be "on" through the term $\left\lVert r(\mathbf{c}_t)\right\rVert^2$.

§.§ Structure of the optimal codes

Finding the codes that minimize $\mathcal{U}(C)$ and $\mathcal{V}(C)$ is a combinatorial optimization problem that requires an exhaustive search. Performing an exhaustive search has a running time of $\mathcal{O}(2^{NT})$ if wish to look for the best coding matrix of size $T$. Hence, for our purposes, finding the best code using brute-force is intractable except for cases when the number of tags $N$, and the size of the coding matrix $T$, are very small.

Therefore, we introduce the idea of code proportions which is essential in reducing the search space. We show that our performance measures depend only on the code through particular proportions of each codeword (see Theorem <ref>), therefore reducing the search space to only those proportions. We begin by carefully defining this idea. Let $C = [\mathbf{c}_1 \cdots \mathbf{c}_T]$ be any code, then we define the proportion of code configuration $\mathbf{c}\in \{0,1\}^N$ in $C$ as

\begin{align}
\pi_\mathbf{c} = \frac{1}{T}\sum_{t=1}^{T} 1_{\mathbf{c} = \mathbf{c}_t},
\end{align}

where $1_{\mathbf{c}=\mathbf{c}_t}$ is the indicator of the event $\{\mathbf{c} = \mathbf{c}_t\}$. In other words, $\pi_\mathbf{c}$ is the number of occurrences of $\mathbf{c}$, normalized by $T$, the size of the code. Moreover, let $\mathbf{c}^{(1)},\ldots, \mathbf{c}^{\left(M\right)}$ be an enumeration of the codewords in $\{0,1\}^N$, then we define the vector of code proportions as $\mathbf{\pi} = \begin{bmatrix} \pi_{\mathbf{c}^{(1)}}, \cdots, \pi_{\mathbf{c}^{\left(M\right)}}\end{bmatrix}^T$. It is straightforward to see that if two coding matrices share the same size $T$, and the same proportions vector $\mathbf{\pi}$, then they are permutations of one another. In what follows, instead of directly using the coding matrix $C$, we search for the optimal coding scheme through the proportions vector $\pi$.

The following theorem allows us to analyze the effect of $C$ on the average and worst-case errors through the proportions vector $\mathbf{\pi}$. Moreover, we show that the derived bounds in (<ref>) and $(\ref{eq:lower_bound})$ can be written in terms of $\pi$. The proofs of the following results is given in Section <ref>.

Assuming independent and identically distributed noise, $\mathcal{L}(C)$ and $\mathcal{M}(C)$ only depend on coding matrix $C$ through the proportions vector $\mathbf{\pi}$.

If we fix $T$, the size of the code $C$, then we can write the minimization of $\mathcal{U}(C)$ and $\mathcal{V}(C)$ in term of $\pi$ respectively as:

\begin{align}
\label{eq:upper_bound_rewrite}
\mathcal{U}(\pi) &= \sum_{Q,Q'\in \mathcal{Q}} \mathrm{erfc}\left(\sqrt{\frac{T\pi \mathbf{g}(Q,Q')}{8\sigma^2}}\right) \theta(Q,Q'),\\
\label{eq:lower_bound_rewrite}
\mathcal{V}(\pi) &=\max_{Q,Q'\in \mathcal{Q}} \mathrm{exp}\left(-\frac{T\mathbf{\pi}^T\mathbf{g}(Q,Q')}{2\sigma^2}\right)\theta(Q,Q'),
\end{align}

where $\mathbf{g}(Q,Q')\in \mathbb{R}^M$ is given by $g(Q,Q')_i =\left\lVert f(Q;\mathbf{c}^{(i)}) - f(Q';\mathbf{c}^{(i)})\right\rVert$.

Theorem <ref> and Lemma <ref> allow us to write our design criteria as optimization problems with respect to the proportions vector $\pi$. In other words, the design criteria for the average and worst-case errors are equivalent to $\min_{\pi} \mathcal{U}(\pi)$ and $\min_{\pi}\mathcal{V}(\pi)$, respectively. In (<ref>) and (<ref>), $\mathbf{g}(Q,Q')$ represents the link between the design criteria channel model. This implies that our design criteria will depend on the channel model only through the distances between channel outputs for different values of the orientation.

§ NUMERICAL SIMULATIONS

§.§ Simulation Setup

We use $N=4$ backscatter tags that we place randomly within a sphere of radius $0.25$m. The 4 tags can each have two states, with reflection coefficients $-0.5$ and $0.5$, encoded as $0$ and $1$, respectively. We arrange $K=4$ full-duplex antennas in a $1\mathrm{m}\times1\mathrm{m}$ square on a plane $4$m away from the center of the object (see Figure <ref> for a sample arrangement). Each antenna emits an identical signal $s_k = 1$ for all $k=1,\ldots,K$. We use a wavelength $\lambda = 0.005$m, and generate a set of orientations $\mathcal{Q}$ with $\left\lvert \mathcal{Q}\right\rvert=4000$ by uniformly sampling the ranges of the euler angles  and computing the rotation matrices that correspond to the angles.

We define SNR as signal-to-noise ratio, the received signal strength at each antenna, divided by the noise power. That is, given the signal-noise ratio SNR, the noise variance is given by $K/\mathrm{SNR}$, where $K$ is the number of antennas. We test each value of $\mathrm{SNR}=0,1,\ldots,10$ dB, with $500$ trials for each of the $4000$ "ground truth" orientations in $\mathcal{Q}$. As a measure of distance, we use the polar and azimuthal angles in the polar coordinate system $(r,\theta,\varphi)$. It is necessary to define a unique set of spherical coordinates for each point, so we restrict the ranges of the polar angle and azimuthal angle to $[0, \pi)$ and  $[0, 2\pi)$, respectively. All things considered, the measure of distance we use in our trials is given by:

\begin{equation}
\ell \left[(\theta,\varphi), (\hat{\theta}, \hat{\varphi})\right] = (\theta-\hat{\theta})^2 + (\varphi - \hat{\varphi})^2,
\end{equation}

where $(\theta,\varphi)$ are the ground truth angles, and $(\hat{\theta},\hat{\varphi})$ are the estimated angles. To obtain an estimate $\widehat{\mathcal{L}}(C)$ of the average-case error $\mathcal{L}(C)$, we average the value of the error over the $500\times 4000 =2,000,000$ trials. The performance of a code varies across different orientations. Hence, unique to average error trials, we have included the variance of each coding method at an SNR value of $10\mathrm{dB}$. The variance indicates how much the performance varies from the total average across the different tested orientations. On the other hand, to obtain an estimate $\widehat{\mathcal{M}}(C)$ of the worst-case error $\mathcal{C}$, we average the $500$ trials for each of the considered orientations, and then take the maximum over all the orientations in $\mathcal{Q}$. In these simulation trials, we use codes of size $T=24$, and compare the performance of the following methods:

* REP_OPT: The best repetition code (all $T=24$ codewords used are the same). This method is equivalent to the design criteria suggested in [9].

* ORTHOGONAL: The code where each of the vectors in the standard basis $\{e_1,\ldots,e_4\}$ is used $6$ times. Note that $e_i$ is the vector components whose are all zero, except for a $1$ in the $i^{th}$ component.

* AVERAGE_DESIGN: The method we suggested to minimize the average error. This is the coding scheme that minimizes the upper bound of the average error i.e. $\pi^*=\arg\min_{\pi} \mathcal{U}(\pi)$.

* MINIMAX_DESIGN: The method we suggested to minimize the worst-case error. This is the coding scheme that minimizes the lower bound of the worst-case error i.e. $\pi^*=\arg\min_{\pi} \mathcal{V}(\pi)$.

An example of a simulation setup. The tags (given by the red dots) are in a tetrahedron configuration, while the antennas (given by the black dots) are in a square configuration.

§.§ The Average Error

The results shown in Figures <ref> and <ref> suggest that channel knowledge at the receiver provides significant benefits over orthogonal codes. For the average error, the code we designed for the average error lead to the best performance out of the considered methods, with the code produced by the method we suggested for the worst-case error trailing behind as a close second. In particular, for the tetrahedron tag configuration shown in Figure <ref>, the average error when using the code produced by the optimization problem $\min_\pi \mathcal{U}(\pi)$ is $70\times$ lower than the error when using orthogonal code. Furthermore, the performance obtained when using the best static code is consistently the worst out of the considered methods. This corroborates the intuition that lead us to introduce the idea of different codes over time.

In order to test the effectiveness of the designed criteria on tag arrays different from the one shown in Figure <ref>, we randomize the positions of the tags (within a sphere of radius 0.25m), compute the designed code, and calculate the average error ratio obtained when using orthogonal codes and the designed code. We perform these steps for a total of 200 times, and produce the density histogram shown in Figure <ref>. In almost all of the 200 trials, the designed code offered more than a $5\times$ improvement over the channel oblivious orthogonal code, and in almost half of the trials, the designed code offered more than a $10\times$ improvement.

§.§ The Worst-Case Error

Moreover, the results shown in Figure <ref> suggest that channel knowledge for code design once again provides large benefits. For the tetrahedron array of Figure <ref>,  the worst-case error produced by the optimization problem $\min_\pi \mathcal{V}(\pi)$ is $100\times$ lower than the error produced when using orthogonal codes.

As we did before, we randomize the positions of tags, and compute the worst error ratio obtain when using orthogonal codes and the code that minimizes (<ref>). We repeat these steps for a total of 150 times, and produce the density histogram in Figure $\ref{fig:worst_histogram}$. In almost all of the 150 trials, the designed code offered a $5\times$ advantage over orthogonal codes, and in almost half of the trials, the designed code offered more than a $20\times$ improvement.

The average squared error versus SNR for the tag array in Figure <ref>. At an $\mathrm{SNR}$ value of $10\mathrm{dB}$, the designed code for the average error is nearly $70\times$ more accurate than the channel-agnostic orthogonal code.

Probability density histogram of the average error ratios when using the orthogonal code and the designed code at an SNR of $10\mathrm{dB}$.

§.§ Multipath

Suppose we now add $M$ reflectors with positions $\mathbf{x}_1^{\textrm{ref}},\ldots, \mathbf{x}_M^\textrm{ref}\in\mathbb{R}^{3}$ to our system. We treat reflectors as virtual sources, and use the following loss formula for the path that begins at $x_1$, is reflected at $x^{\mathrm{ref}}$, and ends at $x_2$:

\begin{equation}
\gamma(x_1,x^{\textrm{ref}},x_2) = \eta(x_1,x^{\textrm{ref}})\eta(x^{\textrm{ref}},x_2).
\end{equation}

Let $D_{m,Q}$ be the $K\times N$ matrix of the multipath only channel responses between the tags and antennas in the presence of $x^{\textrm{ref}}_m$, i.e.

\begin{align}
(D_{Q,m})_{k,n} &= \gamma(x_k^{\textrm{ant}}, x_m^{\textrm{ref}},Qx_n^{\textrm{tag}}).
\end{align}

Now, the matrices involved in our channel model remain precisely the same, except for $H_Q$ which is now replaced by $E_Q = H_Q + D_Q$. The channel model is thus extended to:

\begin{equation}
f_m(Q;\mathbf{c}_t) =  E_QR_t(I - BR_t)^{-1}E_Q^T\mathbf{s}_t.
\end{equation}

In our trials, we use 10 multipath components placed 1m away from the object. Based on observations, and the results of Figure <ref>, multipath does little in the way of diversity gain. However, given a fixed transmit power, multipath does offer an SNR gain at the receiver.

The worst-case error versus SNR for the tag array in Figure <ref>. At an $\mathrm{SNR}$ value of $10\mathrm{dB}$, the designed code for the worst-case error is nearly $100\times$ more accurate than the orthogonal code.

Probability density histogram of the worst error ratios when using the orthogonal code and the designed code at an SNR of $10\mathrm{dB}$.

§.§ Robustness

Computing the codes schemes suggested by our design criteria requires channel knowledge. However, since we are not likely to have perfect channel knowledge, we test the performance of our design criteria when computed using imperfect channel estimation. We introduce channel estimation errors by adding noise to the channel outputs in different orientations. Specifically, instead of using $F(Q;C)$ to compute the suggested coding scheme, we use

\begin{equation}
F'(Q;C) = F(Q;C) + W_Q,
\end{equation}

where $W_Q$ is white Gaussian noise, and $W_Q$ is independent of $W_{Q'}$ for every $Q'\neq Q$. We tested the following values of the $\mathrm{SNR}= 5,10,15\mathrm{dB}$, with $50$ trials each, and then averaged the performance. In particular, the results of Figure <ref> indicate that our designed codes retain nearly all even when computed with channel estimation errors greater than or equal to $10$dB. The figures also indicate that the design criteria maintain considerable improvement over channel oblivious codes when computed with channel estimation errors less than $10\mathrm{dB}$.

The average (left) and worst-case (right) errors for the designed codes in the cases of line-of-site only and multipath.

The average (left) and worst-case error (right) of the designed codes for different levels of channel estimation errors.

§ PROOFS

§.§ Proof of Theorem <ref>

Let $Y = F(Q,C) + W$ be as in <ref>. $\{\widehat{Q}(Y) = Q'\}$ is the event that our estimator outputs a different orientation $Q'$ when the object is in orientation $Q$. We can rewrite the average error in terms of events of this form.

\begin{align}
\mathcal{L}(C) &= \sum_{Q\in \mathcal{Q}} \mathbb{E}_W \left[\theta(\widehat{Q}(Y), Q)\right],\\ \label{eq:different_form}
&= \sum_{Q\in\mathcal{Q}}\sum_{Q'\neq Q}\mathbb{P}\left(\widehat{Q}(Y) = Q'\right)\theta(Q, Q').
\end{align}

The probability of the event $\{\widehat{Q}(Y) = Q'\}$ is a difficult quantity to compute outside of cases when $\mathcal{Q}$ is very small. Therefore, we wish to upper bound it with another probability that is easier to compute. Recall that

\begin{align}
\widehat{Q}(Y) =\arg\min_{Q\in \mathcal{Q}} \left\lVert Y - F(Q,C)\right\rVert_F.
\end{align}

Given the functional form of the estimator, a necessary but insufficient condition for our estimator to output $Q'$ is for the received signal $Y$ to satisfy $\left\lVert Y - F(Q;C) \right\rVert \geq  \left\lVert Y - F(Q';C) \right\rVert$. Given this relationship between the events, we have that:

\begin{align}
\label{eq:upperboundevent}
\big\{ \widehat{Q}(Y) = Q' \big\} &\subseteq \big\{ \left\lVert Y - F(Q;C) \right\rVert_F \geq  \left\lVert Y - F(Q';C) \right\rVert_F \big\}.
\end{align}

The latter is event that our noisy channel output is closer to the noiseless channel output corresponding to $Q'$ than the noiseless channel output corresponding to $Q$. Combining (<ref>) and (<ref>) with the monotonicity of the probability function ($\mathbb{P}(A) \leq \mathbb{P}(B)$ for all events $A\subseteq B$), we obtain an upper bound on the average error.

\begin{align}
\mathcal{L}(C) = \sum_{Q\in\mathcal{Q}}\sum_{Q'\neq Q}&\mathbb{P}\left(\widehat{Q}(Y) = Q'\right)\theta(Q, Q'), \\
\leq\sum_{Q\in\mathcal{Q}}\sum_{Q'\neq Q}&\mathbb{P}\big(\left\lVert Y - F(Q;C) \right\rVert_F \geq  \left\lVert Y - F(Q';C) \right\rVert_F \big)\nonumber \\
\label{eq:upperbound2}
&\theta(Q, Q').
\end{align}

In other words, we use the standard pairwise error probability to develop an upper bound to the average error. Combining (<ref>) with the following standard lemma [15], which provides the form for the probability of the event in the right-hand-side of (<ref>), we obtain the desired result.

Let $Y \sim \mathbb{C}\mathcal{N}(\mathbf{0}, \sigma^2I_n)$, and let $a\in \mathbb{C}^n$, then

\begin{align}
\mathbb{P}\left( \left\lVert Y \right\rVert \geq \left\lVert Y - a\right\rVert\right) = \frac{1}{2} \mathrm{erfc}\left(\frac{\left\lVert a\right\rVert}{2\sqrt{2}\sigma}\right),
\end{align}

where $\mathrm{erfc}$ is the complement of the Gauss error function.

§.§ Proof of Theorem <ref>

Let $C\in[m]^{N\times T}$ be a coding matrix, and let $\mathcal{P}$ be the family of distributions given by

\begin{align}
\label{eq:prob_family}
\mathcal{P}= \{\mathbb{C}\mathcal{N}(F(Q;C), \sigma^2I); Q\in \mathcal{Q}\}.
\end{align}

The probability distributions in $\mathcal{P}$ can be parameterized by their orientation. Let $P,P'\in\mathcal{P}$ be distributions with $Q$ and $Q'$ as their corresponding orientations, then Le Cam's method[14] asserts that:

\begin{align}
\mathcal{M}(C) &\geq \frac{\theta(Q,Q')}{2} \left( 1 - \mathrm{TV}(P,P')\right),
% \label{eq:exp_KL}
% &\geq \frac{\left\lVert \mathbb{E}(P) - E(P')\right\rVert}{4} \mathrm{exp}\left(-\mathrm{KL}(P
% ||P')\right).
\end{align}

where $\mathrm{TV}(P,P')$ is the total variation distance[16]. The Kullback-Leibler divergence[17] is a different and widely used measure of discrepancy between two probability distributions. It has many desirable properties, and it's an upper bound for many other popular discrepancy measures. Through Pinsker's inequality[16], one can upper bound the total-variation distance through the Kullback-Leibler divergence. The total-variation distance between two probability distributions $P$ and $P'$, the Kullback-Leibler divergence, and Pinsker's inequality are respectively given by:

\begin{align}
&\mathrm{TV}(P,P') = \int_{\mathbb{C}^{KT}} \left\lvert P(x) - P'(x)\right\rvert\mathrm{d}x. \\
&\mathrm{KL}(P||P') = \int_{\mathbb{C}^{KT}} P(x) \log\frac{P(x)}{P'(x)}\mathrm{d}x. \\
&\left\lVert P - P'\right\rVert_{\mathrm{TV}} \leq \sqrt{\frac{1}{2}\mathrm{KL}(P||P')}.
\end{align}

\begin{align}
&\mathcal{M}(C) \\
&\geq \frac{\theta(Q,Q')}{2} \left( 1 - \mathrm{TV}(P,P')\right), \\
\label{eq:pinsker_step}
&\geq \frac{\theta(Q,Q')}{2} \left( 1 - \sqrt{\frac{1}{2}\mathrm{KL}(P||P')}\right),\\
\label{eq:minus_step}
&\geq \frac{\theta(Q,Q')}{4} \mathrm{exp}\left(-\mathrm{KL}(P||P')\right), \\
\label{eq:subst_step}
&= \frac{\theta(Q,Q')}{4}\mathrm{exp}\left(-\frac{\left\lVert F(Q;C) - F(Q';C)\right\rVert_F^2}{2\sigma^2}\right).
\end{align}

(<ref>) follows from Pinsker's inequality, and (<ref>) follows from the inequality $1-x\leq e^{-x}$. For two independent Gaussians $P = \mathbb{C}\mathcal{N}(\mu, \sigma^2I)$ and $P'= \mathbb{C}\mathcal{N}(\mu', \sigma^2I)$ with the same co-variance matrix, the Kullback-Leibler divergence is given by $\left\lVert \mu - \mu' \right\rVert^2/2\sigma^2$[16], and therefore, we obtain (<ref>). Since (<ref>) holds for every $P,P'\in\mathcal{P}$, we can take the maximum over every pair of distributions (equivalently, every pair of orientations $Q,Q'\in\mathcal{Q}$), which gives

\begin{multline}
\mathcal{M}(C) \geq \max_{Q,Q'\in\mathcal{Q}}
\mathrm{exp}\left(\frac{-\left\lVert F(Q;C) - F(Q';C)\right\rVert_F^2}{2\sigma^2}\right)\\\frac{\theta(Q,Q')}{4}.
\end{multline}

§.§ Proof of Theorem <ref>

Letting $\mathcal{P}$ be the same family of distributions as in (<ref>), $P$ and $P'$ distributions in $\mathcal{P}$ with $Q$ and $Q'$ as their corresponding distributions, then we can start with Equation (<ref>) which was obtained with Le Cam's method and Pinsker's inequality. In other words, we start with:

\begin{align}
\label{eq:2ndstep}
\mathcal{M}(C) &\geq\frac{\theta(Q,Q')}{2} \left(1-\sqrt{\frac{1}{2}\mathrm{KL}(P||P')}\right),
\end{align}

where $\mathrm{KL}(P||P')$ is the Kullback-Leibler Divergence. We obtain (<ref>) using Pinsker's inequality[16]. For two independent Gaussians $P = \mathbb{C}\mathcal{N}(\mu,  \sigma^2I)$ and $P'=\mathbb{C}\mathcal{N}(\mu', \sigma^2I)$ with the same covariance matrix, $\mathrm{KL}(P,P') = \left\lVert \mu - \mu'\right\rVert_2/2\sigma^2$. Hence,

\begin{equation}
\mathcal{M}(C) \geq \frac{\theta(Q,Q')}{2}\left(1 - \frac{1}{2\sigma}\left\lVert F(Q;C) - F(Q';C)\right\rVert_F\right).
\end{equation}

Now, let $R_t$ be the diagonal matrix of reflectivities when using code configuration $\mathbf{c}_t$, then recall

\begin{align}
f(Q;\mathbf{c}_t) &= H_{Q}R(I-BR_t)^{-1}H_{Q}^T\mathbf{s}_t, \\
&= H_{Q}(I-BR_t)^{-1}R_tH_{Q}^T\mathbf{s}_t, \\
&= H_{Q}(I-BR_t)^{-1}\textrm{diag}\left\{H_{Q}^T\mathbf{s}_t\right\}r(\mathbf{c}_t),
\end{align}

where $r(\mathbf{c}_t)$ is the column vector of reflectivities corresponding to code $\mathbf{c}_t$. We wish to bound $\left\lVert f(Q;\mathbf{c}_t) - f(Q';\mathbf{c}_t)\right\rVert$, so we use the inequality $\left\lVert A_t\mathbf{x}_t\right\rVert\leq \left\lVert A_t\right\rVert_F\left\lVert \mathbf{x}_t\right\rVert$ with $\mathbf{x}_t = r(\mathbf{c}_t)$ and

\begin{align*}
A_t = &H_{Q}(I-BR_t)^{-1}\textrm{diag}\{H_{Q}\mathbf{s}_t\} \\
&- H_{Q'}(I-BR_t)^{-1}\textrm{diag}\{H_{Q'}\mathbf{s}_t\}.
\end{align*}

If $D$ is an approximate range between the tagged object's hinge point and the aperture, then for all $t\in \{1,\ldots,T\}$

\begin{equation}
\label{eq:frobenius_bound}
\left\lVert A_t\right\rVert_F \leq \left(\frac{K}{4\pi\lambda D^2}\right) \left\lVert X^{\mathrm{tag}}\right\rVert_F \left\lVert \widetilde{B}_t\right\rVert_F \theta(Q,Q').
\end{equation}

Letting $\delta = \sqrt{\theta(Q,Q')}$, we have that:

\begin{align}
&\left\lVert F(Q;C) - F(Q';C)\right\rVert_F \\
&= \sqrt{\sum_{t=1}^T \left\lVert f(Q;\mathbf{c}_t) - f(Q';\mathbf{c}_t)\right\rVert } \\
\label{eq:sstep1}
&\leq \sqrt{\sum_{t=1}^T  \left\lVert A_t\right\rVert_F^2\left\lVert r(\mathbf{c}_t)\right\rVert^2}\\
\label{eq:sstep2}
&\leq \delta \sqrt{\sum_{t=1}^T  \underbrace{\left(\frac{K}{2\pi\lambda D^2} \left\lVert X^{\mathrm{tag}}\right\rVert_F \left\lVert \widetilde{B}_t\right\rVert_F \left\lVert r(\mathbf{c}_t)\right\rVert\right)^2}_{\Delta_t}},
\end{align}

where (<ref>) follows from the inequality $\left\lVert A\mathbf{x}\right\rVert \leq \left\lVert A\right\rVert_F\left\lVert \mathbf{x}\right\rVert$, and (<ref>) follows from Lemma <ref>. Hence, a lower bound on the worst-case error is given by:

\begin{equation}
\label{eq:bound_max}
\mathcal{M}(C) \geq \frac{\delta^2}{2} \left(1 - \frac{\delta}{2\sigma}\sqrt{\sum_{t=1}^{T}\Delta_t}\right).
\end{equation}

To obtain a tightest bound, we have to find the maximum of the right-hand side with respect to $\delta$. Maximizing (<ref>) with respect to $\delta$ is equivalent to finding:

\begin{equation}
\label{eq:boundop}
\begin{aligned}
\max_{x} \quad & x^2\left(1-x\right)
\end{aligned}
\end{equation}

(<ref>) attains it's maximum value at $x=2/3$. This gives us that:

\begin{equation}
\mathcal{M}(C) \geq  \frac{32\pi^2\lambda^2\sigma^2D^4}{27K^2 \left\lVert X^{\mathrm{tag}}\right\rVert_F^2 \sum_{t=1}^T \lVert \widetilde{B}_t\rVert_F^2\left\lVert r(c_t)\right\rVert_2^2}
\end{equation}

§.§ Proof of Lemma <ref>

For ease of computation, we drop the $t$ subscript for now, and define $\widetilde{B}= (I-BR_t)^{-1}$ with $\tilde{b}_{i,j} = \tilde{B}_{i,j}$, and $\tilde{H}_Q = H_Q\tilde{B}$ with $\tilde{h}_{Q,i,j} = (\tilde{H}_Q)_{i,j}$. Taking $\mathbf{s}_t = \mathbf{1}$, we have that:

\begin{align}
\left \lVert A_t \right \rVert_{F}^{2} &= \sum_{k = 1}^{K}\sum_{n = 1}^{N} \left|\sum_{i = 1}^{K} \tilde{h}_{k,n}^{Q} h_{i,n}^{Q} - \tilde{h}_{k,n}^{Q'} h_{i,n}^{Q'} \right|^{2}, \\
\label{eq: A_bound}
&\leq \sum_{k = 1}^{K}\sum_{n = 1}^{N}\sum_{i = 1}^{K} \left|\tilde{h}_{k,n}^{Q} h_{i,n}^{Q} - \tilde{h}_{k,n}^{Q'} h_{i,n}^{Q'} \right|^{2}.
\end{align}

Using Cauchy-Schwartz inequality, we arrive at:

\begin{align}
\left|\tilde{h}_{k,n}^{Q_1} h_{i,n}^{Q_1} - \tilde{h}_{k,n}^{Q_2} h_{i,n}^{Q_2} \right|^{2} &\leq \left \lVert {\tilde{\mathbf{b}}}_{n} \right \rVert_{2}^{2}\sum_{l = 1}^{N} \left|h_{k,l}^{Q_1} h_{i,n}^{Q_1} - h_{k,l}^{Q_2} h_{i,n}^{Q_2} \right|^{2}
\end{align}

Assuming we operate in the far-field region, we can approximate $h$ with

\begin{equation}
h^{Q}_{i,j} = \frac{e^{-j \left(\frac{2 \pi}{\lambda} \right) \left \Vert \mathbf{x}_{i}^{ant} - Q \mathbf{x}_{j}^{tag} \right \Vert_{2}}}{4 \pi \left \Vert \mathbf{x}_{i}^{ant} - Q\mathbf{x}_{j}^{tag} \right \Vert_{2}} \approx \frac{e^{-j \left(\frac{2 \pi}{\lambda} \right) \left \Vert \mathbf{x}_{i}^{ant} - Q\mathbf{x}_{j}^{tag} \right \Vert_{2}}}{4 \pi D},
\end{equation}

where $D$ is an approximate range between the tagged object's hinge point and the aperture. Hence, we can make the following approximation:

\begin{multline}
\label{eq:lower13}
\left|h_{k,l}^Q h_{i,n}^Q - h_{k,l}^{Q'} h_{i,n}^{Q'}  \right|^{2} \approx \\
\left(\frac{1}{4 \pi D} \right)^{4} \left\lvert e^{-j \left(\frac{2 \pi}{\lambda} \right) \big(\left \Vert \mathbf{x}_{k}^{ant} - Q\mathbf{x}_{l}^{tag} \right \Vert_{2} + \left \Vert \mathbf{x}_{i}^{ant} - Q\mathbf{x}_{n}^{tag} \right \Vert_{2} \big)} \right. \\
\left. -e^{-j \left(\frac{2 \pi}{\lambda} \right) \big(\left \Vert \mathbf{x}_{k}^{ant} - Q'\mathbf{x}_{l}^{tag} \right \Vert_{2} + \left \Vert \mathbf{x}_{i}^{ant} - Q'\mathbf{x}_{n}^{tag} \right \Vert_{2} \big)}  \right\rvert.
\end{multline}

Using $1 - e^{-x} \leq x$, we can further upper bound (<ref>) by:

\begin{multline}
\label{eq:lower15}
\left(\frac{\sqrt{\frac{2 \pi}{\lambda}}}{4 \pi D} \right)^{4} \left( \left\lVert \mathbf{x}_{k}^{ant} - Q\mathbf{x}_{l}^{tag} \right\rVert_{2} + \left \lVert \mathbf{x}_{i}^{ant} - Q \mathbf{x}_{n}^{tag} \right\rVert_{2}\right. \\
- \left. \left \lVert \mathbf{x}_{k}^{ant} - Q'\mathbf{x}_{l}^{tag} \right \rVert_{2} - \left \lVert \mathbf{x}_{i}^{ant} - Q'\mathbf{x}_{n}^{tag} \right \rVert_{2} \right).
\end{multline}

Using the triangle and matrix norm inequalities in (<ref>), we obtain

\begin{multline}
\label{eq:upper16}
\left\lvert h_{k,l}^{Q} h_{i,n}^{Q} - h_{k,l}^{Q'} h_{i,n}^{Q'} \right\rvert^{2} \\
\leq 2\left(\frac{\sqrt{\frac{2 \pi}{\lambda}}}{4 \pi D} \right)^{4} \left(\left \Vert x_{l}^{\textrm{tag}}   \right \Vert_{2}^{2} + \left \Vert x_{n}^{\textrm{tag}}   \right \Vert_{2}^2 \right)\theta(Q,Q').
\end{multline}

Combining (<ref>) and (<ref>), and summing over the indices of the tags and antennas, we obtain the desired result.

§.§ Proof of Theorem <ref>

Suppose $C = [\mathbf{c}_1 \cdots \mathbf{c}_T]$ and $C'=[\mathbf{c}'_1 \cdots \mathbf{c}'_T]$ are two coding matrices with the same relative weight vectors. In other words, $\mathbf{\pi}_{\mathbf{c}} = \mathbf{\pi}_{\mathbf{c}}'$ for every code configuration $\mathbf{c}$. If the counts of the different configurations are the same, then there exists some permutation $\tau$ on $\{1,\ldots, T\}$ such that $\mathbf{c}_{\tau(t)} = \mathbf{c}_t'$ for all $t$. We show the errors do not depend on the ordering of the code configurations due to the iid nature of the noise. To see this, let $Y = F(Q;C) + W$, then

\begin{align}
\label{eq:c_hat}
&\widehat{Q}(Y) \\
&= \widehat{Q}\left(F(Q;C) + W\right),\\
&= \arg\min_{Q'} \left\lVert F(Q;C) - F(Q';C) + W\right\rVert_F^2, \\
&= \arg\min_{Q'} \sum_{t=1}^{T} \left\lVert f(Q;\mathbf{c}_t) - f(Q';\mathbf{c}_t) + \mathbf{w}_t \right\rVert^2, \\
&= \arg\min_{Q'} \sum_{t=1}^{T} \left\lVert f(Q;\mathbf{c}_\tau(t)) - f(Q';\mathbf{c}_\tau(t)) + \mathbf{w}_{\tau(t)} \right\rVert^2, \\
&= \arg\min_{Q'} \sum_{t=1}^{T} \left\lVert f(Q;\mathbf{c}_t') - f(Q';\mathbf{c}_t') + \mathbf{w}_{\tau(t)} \right\rVert^2, \\
&=  \widehat{Q}\left(F(Q;C') + W'\right), \\
\label{eq:c_hatt}
&= \widehat{Q}(Y'),
\end{align}

where $\mathbf{w}_t$ is the $t^{\mathrm{th}}$ $K$-sized block of $W$, $W'$ is the vector with $\mathbf{w}'_t = \mathbf{w}_{\tau(t)}$, and $Y' = F(Q;C') + W'$. Since the elements of $W$ independent and identically distributed, we get that $W$ and $W'$ are also identically distributed. Combining the previous statement with the fact that $W$ and $W'$ are permutations of one another, we can replace any expectation with respect to $W$ with an expectation with respect to $W'$. Hence,

\begin{align}
\mathcal{L}(C) &= \sum_{Q\in \mathcal{Q}} \mathbb{E}_{W} \left[\theta(\widehat{Q}(Y), Q)\right], \\
\label{eq:step_1}
&= \sum_{Q\in \mathcal{Q}} \mathbb{E}_{W} \left[\theta(\widehat{Q}(Y'), Q)\right], \\
\label{eq:step_2}
&= \sum_{Q\in \mathcal{Q}} \mathbb{E}_{W'} \left[\theta(\widehat{Q}(Y'), Q)\right], \\
\end{align}

(<ref>) follows from the earlier computation, and (<ref>) follows from the our earlier discussion. Repeating the exact same computation with $\sum_{Q\in\mathcal{Q}}$ replaced with $\max_{Q\in\mathcal{Q}}$ shows that $\mathcal{M}(C) = \mathcal{M}(C')$ i.e. $C$ and $C'$ share the same worst-case performance. Hence, we get that $C$ and $C'$ share the same errors, and that our performance measures depend only on the coding matrix through the relative weight vector. It is worthwhile to note that this property of the errors is not unique to Gaussian noise, but is valid for any noise vector whose components are independent and identically distributed.

§ CONCLUSION

Active backscatter tags can be very useful when estimating the 3D orientation of objects if tag responses are carefully designed. In this work, we suggested two design criteria, and developed a bound showing how different system parameters affect performance. Through numerical simulations, we exhibited the effectiveness of the suggested designs, and their robustness in the face of imperfect channel knowledge. There are several open questions remaining including designs for more complicated or time-varying environments. Additionally, an exploration of the effectiveness of non-coherent coding in such scenarios is a potentially interesting direction.

[1]
A. Saxena, J. Driemeyer, and A. Y. Ng, “Learning 3-d object orientation from
images,” in 2009 IEEE International Conference on Robotics and
Automation, 2009, pp. 794–800.

[2]
A. Collet, D. Berenson, S. S. Srinivasa, and D. Ferguson, “Object recognition
and full pose registration from a single image for robotic manipulation,” in
2009 IEEE International Conference on Robotics and Automation, 2009,
pp. 48–55.

[3]
H. Fujiyoshi, T. Nagahashi, and S. Shimizu, Robust and Accurate Detection
of Object Orientation and ID without Color Segmentation, 12 2007.

[4]
T. Starner, B. Leibe, D. Minnen, T. Westyn, A. Hurst, and J. Weeks, “The
perceptive workbench: Computer-vision-based gesture tracking, object
tracking, and 3d reconstruction for augmented desks,” Machine Vision
and Applications, vol. 14, pp. 59–71, 01 2003.

[5]
E. Soltanaghaei, A. Prabhakara, A. Balanuta, M. Anderson, J. M. Rabaey,
S. Kumar, and A. Rowe, “Millimetro: Mmwave retro-reflective tags for
accurate, long range localization,” in Proceedings of the 27th Annual
International Conference on Mobile Computing and Networking, ser. MobiCom
'21.1em plus 0.5em minus 0.4emNew York, NY, USA: Association
for Computing Machinery, 2021, p. 69–82. [Online]. Available:

[6]
E. Soltanaghaei, A. Dongare, A. Prabhakara, S. Kumar, A. Rowe, and
K. Whitehouse, “Tagfi: Locating ultra-low power wifi tags using unmodified
wifi infrastructure,” Proc. ACM Interact. Mob. Wearable Ubiquitous
Technol., vol. 5, no. 1, Mar. 2021. [Online]. Available:

[7]
T. Wei and X. Zhang, “Gyro in the air: tracking 3d orientation of batteryless
internet-of-things,” in Proceedings of the 22nd Annual International
Conference on Mobile Computing and Networking.1em plus 0.5em minus
0.4emACM, 2016, pp. 55–68.

[8]
A. A. N. Shirehjini, A. Yassine, and S. Shirmohammadi, “An rfid-based position
and orientation measurement system for mobile objects in intelligent
environments,” IEEE Transactions on Instrumentation and Measurement,
vol. 61, no. 6, pp. 1664–1675, 2012.

[9]
K. Chang, N. Raymondi, A. Sabharwal, and S. N. Diggavi, “Wireless paint: Code
design for 3D orientation estimation with backscatter arrays,” in
IEEE International Symposium on Information Theory, ISIT.1em plus 0.5em minus 0.4emIEEE, 2020, pp. 1224–1229.

[10]
C. Jiang, Y. He, X. Zheng, and Y. Liu, “Orientation-aware rfid tracking with
centimeter-level accuracy,” in Proceedings of the 17th ACM/IEEE
International Conference on Information Processing in Sensor Networks.1em plus 0.5em minus 0.4emIEEE Press, 2018, pp. 290–301.

[11]
X. Fu, A. Pedross-Engel, D. Arnitz, and M. S. Reynolds, “Simultaneous
sensor localization via synthetic aperture radar (sar) imaging,” in
2016 IEEE SENSORS, Oct 2016, pp. 1–3.

[12]
D. Tse and P. Viswanath, Fundamentals of Wireless Communication.1em plus 0.5em minus 0.4emUSA: Cambridge University Press, 2005.

[13]
A. Sabharwal, P. Schniter, D. Guo, D. W. Bliss, S. Rangarajan, and R. Wichman,
“In-band full-duplex wireless: Challenges and opportunities,” IEEE
Journal on selected areas in communications, vol. 32, no. 9, pp. 1637–1652,

[14]
A. N. Shiryayev and Y. A. Koshevnik, “Review: Lucien le cam, asymptotic
methods in statistical decision theory,” Bull. Amer. Math. Soc.
(N.S.), vol. 20, no. 2, pp. 280–285, 04 1989. [Online]. Available:

[15]
U. Madhow, Introduction to Communication Systems, 1st ed.1em plus
0.5em minus 0.4emUSA: Cambridge University Press, 2014.

[16]
T. M. Cover and J. A. Thomas, Elements of Information Theory (Wiley
Series in Telecommunications and Signal Processing).1em plus 0.5em
minus 0.4emUSA: Wiley-Interscience, 2006.

[17]
P. Harremoes and N. Tishby, “The information bottleneck revisited or how to
choose a good distortion measure,” in 2007 IEEE International
Symposium on Information Theory, 2007, pp. 566–570.


# IoTWarden: A Deep Reinforcement Learning Based Real-time Defense System to
Mitigate Trigger-action IoT Attacks

Md Morshed Alam  Department of Software and Information Systems, University of
North Carolina at Charlotte, Charlotte, USA  Israt Jahan  Department of
Computer Science, University of Memphis, Memphis, USA  Weichao Wang
Department of Software and Information Systems, University of North Carolina
at Charlotte, Charlotte, USA

###### Abstract

In trigger-action IoT platforms, IoT devices report event conditions to IoT
hubs notifying their cyber states and let the hubs invoke actions in other IoT
devices based on functional dependencies defined as rules in a rule engine.
These functional dependencies create a chain of interactions that help
automate network tasks. Adversaries exploit this chain to report fake event
conditions to IoT hubs and perform remote injection attacks upon a smart
environment to indirectly control targeted IoT devices. Existing defense
efforts usually depend on static analysis over IoT apps to develop rule-based
anomaly detection mechanisms. We also see ML-based defense mechanisms in the
literature that harness physical event fingerprints to determine anomalies in
an IoT network. However, these methods often demonstrate long response time
and lack of adaptability when facing complicated attacks. In this paper, we
propose to build a deep reinforcement learning based real-time defense system
for injection attacks. We define the reward functions for defenders and
implement a deep Q-network based approach to identify the optimal defense
policy. Our experiments show that the proposed mechanism can effectively and
accurately identify and defend against injection attacks with reasonable
computation overhead.

###### Index Terms:

Internet of Things, Remote Injection Attack, Deep Reinforcement Learning,
Markov Decision Process, Trigger-action Platform, Deep Q-Network

© 2024 IEEE. Personal use of this material is permitted. Permission from IEEE
must be obtained for all other uses, in any current or future media, including
reprinting/republishing this material for advertising or promotional purposes,
creating new collective works, for resale or redistribution to servers or
lists, or reuse of any copyrighted component of this work in other works.

##  I Introduction

Emerging Internet of Things (IoT) platforms support trigger-action
functionality that enables IoT hubs in smart homes instructing IoT devices to
perform predefined actions (e.g., turning on smart light) based on specific
event conditions reported by other IoT devices (e.g., the door is unlocked)
[1]. Hence, event conditions act as triggers, which activate corresponding
actions associated with rules set in a rule engine defined by users in the IoT
hubs. These rules represent functional dependencies between various IoT event
conditions and actions. In a smart home network, these functional dependencies
create a chain of interactions among IoT devices to automate network tasks.
IoT devices report event conditions to the hub informing the cyber states of
the devices themselves, and the hub leverages physical evidence captured by
some deployed sensors in the network to verify the physical states of those
devices. The trigger-action functionality also allows the hub to communicate
with users with important notifications and alerts about the physical
developments (e.g., when the fire alarm sounds) in a smart home environment
[2]. SmartThings [3] and IFTTT [4] are two prominent examples of such
platforms.

Although the chain of interactions generated in a smart home enables network
automation, it creates security vulnerabilities in the environment [5].
Attackers can exploit this chain to manipulate IoT devices to trigger
sensitive actions in the network, such as setting up thermostat at 120°F.
Attackers can also collect seamless sensitive user data without raising
suspicion to the defense system, or cause unsafe state transitions in the
environment violating rule execution integrity [6]. In this paper, we focus on
the remote injection attack [5] that allows attackers to inject fake event
conditions into the hub and trick it to command target IoT devices to perform
some actions that help attackers achieve certain attack goals. For instance,
given that there is a functional dependency between fire alarm and smart lock,
an attacker can inject a fake fire alarm event condition to the IoT hub
representing a false fire hazard situation and let the hub instruct the lock
to automatically open the front door. This attack is also called event
spoofing attack since attackers deceive the hub with malicious reporting of
spoofed event conditions [1]. Thus, it is possible for attackers to exploit
functional dependencies present in the chain of interactions to implement
safety-critical attacks in smart environments [7].

In the literature, we see great efforts to address this security
vulnerability. For example, we see rule-based and ML-based IoT anomaly
detection systems (also called event verification systems) that use physical
event fingerprints of IoT devices to verify whether the reported events to the
hub occurred physically [8] [9]. Sensors deployed in the environment to
continuously measure physical channels of devices (e.g., light intensity) help
determine these unique fingerprints. We also see approaches that diagnose
unsafe and insecure state transitions between IoT devices in the network to
ensure that each event reporting to the hub complies with the defined security
policy of the network [10] [11]. However, most of the existing security
approaches either require active intervention on the IoT app source code, or
do not provide realtime security against an ongoing trigger-action attack.

In this paper, we propose IoTWarden, a deep reinforcement learning (deep RL)
based defense system that allows a defense agent to model attack behavior
based on the impact of attack actions in the IoT environment and obstructs the
progression of an ongoing attack in realtime. We make the following
contributions in this paper:

  * •

We propose a deep RL based realtime defense system, namely IoTWarden, that
allows defenders to take necessary defense actions at runtime against ongoing
trigger-action attacks.

  * •

We implement an LSTM-based [12] Recurrent Neural Network (RNN) to discern
optimal attack sequences to help IoTWarden infer attack behavior at runtime.

  * •

We implement Deep Q-Network [13] to obtain optimal defense policy and train
the decision process of defenders.

  * •

We conduct extensive experiments and simulation to evaluate the performance of
IoTWarden, showing that the adoption of optimal defense policy yields improved
security gain with very low computation overhead.

The rest of the paper is organized into six sections. In section II, we
introduce the trigger-action attack, discuss attack strategy, and define a
relevant threat model. We also describe how defenders characterize the attack
progression by generating attack graphs. In section III, we present the
IoTWarden defense system and describe each individual component in detail. We
provide the details of our experiment and simulation in section IV. Later, in
section V, we include the simulation results and evaluate the performance of
the system in countering attacks in realtime. Finally, we conclude the paper
summarizing the methodology and discuss future extensions in section VI.

##  II Attack Overview

To perform a remote injection attack exploiting functional dependencies in a
smart home network, an attacker injects necessary amount of event conditions
into the hub, which act as triggers for the actions in other devices. We call
the injection operations exploits, which trick the hub to activate actions in
target devices. Note that the terms event condition and event signify the same
aspect in our attack scenario, and therefore, we interchangeably use these
terms throughout the rest of the paper to avoid verbosity.

###  II-A Attack Definition

We assume that there are $\mathcal{N}$ possible event conditions in the
network $C\negmedspace=\negmedspace\\{c_{i}\\},1\negmedspace\leq\negmedspace
i\negmedspace\leq\negmedspace\mathcal{N}$, and the attacker conducts an
optimal sequence of $\mathcal{M}$ exploits
$\xi\negmedspace=\negmedspace\\{e_{j}\\},1\negmedspace\leq\negmedspace
j\negmedspace\leq\negmedspace\mathcal{M}$ to report a subset of these
conditions to the hub to perform a trigger-action attack. We assume that the
attacker performs an exploit $e_{t}\negmedspace\in\negmedspace\xi$ at timestep
$t$ to maliciously report an event condition $c_{t}\negmedspace\in\negmedspace
C$ to the hub and expects the hub to invoke an event condition
$c_{t^{\prime}}\negmedspace\in\negmedspace C$ at another device, which is a
target of the attacker. Since complex functional dependencies may exist in the
chain of interactions, it is possible that the attacker needs to perform a set
of exploits $\\{e_{t}\\}\negmedspace\in\negmedspace\xi$ at timestep $t$ to
report multiple event conditions $\\{c_{t}\\}\negmedspace\in\negmedspace C$ to
achieve the attack goal. The attacker considers an IoT device compromised if
the following definition 1 applies to it.

Definition 1 (IoT Device Compromise): An IoT device $d_{g}$ is said to be
compromised at timestep $t$ if an event condition
$c_{g}\negmedspace\in\negmedspace C$ is triggered at the device $d_{g}$ due to
the malicious reporting of a set of event conditions
$\\{c_{t}\\}\negmedspace\in\negmedspace C$ to the IoT hub by an attacker
through a sequence of exploits $\\{e_{t}\\}\negmedspace\in\negmedspace\xi$
adopting a strategy $z\negmedspace\in\negmedspace Z$ that dictates the attack
operations.

###  II-B Attack Characterization

To model complex interactions of the attacker with the network and
characterize the attack progression over time, we assume that the defense
agent embeds event conditions and corresponding exploits to construct a
directed acyclic attack dependency graph
$G\negmedspace=\negmedspace\\{C,\xi\\}$. Since attack dependency graph grows
non-linearly across time horizon with the increase of the number of nodes, the
defense agent considers the inclusion of monotonicity [14] property in attack
behavior to prevent state explosion problem [15] and keep the attack
dependency graph reasonably small to perform security analysis. This property
enforces a constraint on the attack behavior by limiting the influence of past
exploits on the future ones. We assume that the defender constructs this graph
using state-of-the-art vulnerability analysis tools, such as TVA tool of [16].

###  II-C Attack Strategy

Since exploits drive the remote injection attack, it is important for the
attacker to follow an effective attack strategy in choosing the optimal
exploits. We assume that the attacker crafts a set of attack strategies
$Z\negmedspace=\negmedspace\\{z_{i}\\},1\negmedspace\leq\negmedspace
i\negmedspace\leq\negmedspace\kappa$, where $\kappa$ is the total number of
possible strategies for the attacker. Hence, each
$z\negmedspace\in\negmedspace Z$ gives a unique set of exploits to perform
during the attack. The attacker changes the adopted attack strategy once the
defender blocks certain event conditions making some event reporting
untenable. We assume that the attacker precomputes optimal attack paths from
each IoT device to the ultimate target device using LSTM-based RNNs exploiting
temporal dependencies exist in the network. Based on these optimal attack
paths, the attacker crafts several exploit sequences, which act as attack
strategy $z\negmedspace\in\negmedspace Z$.

###  II-D Threat Model

We assume that the attacker injects event conditions into the IoT hub using
multiple ghost devices with stolen IDs and credentials of valid devices. A
ghost device usually is a computer program designed to simulate the behavior
of a real IoT device. The attacker steals information about valid devices from
public data hosted in manufacturer’s websites or public repository, including
GitHub. The attacker also extracts real-time event information from network
traffic using different IoT network analysis tools [17] [18]. We also assume
that the attacker is intelligent enough to profile the impact of IoT event
occurrences over the physical environment and perform opportunistic attack
similar to the attacks explained in [8]. To evade detection by the defense
system, the attacker follows a minimally invasive attack strategy that
requires as few injections as possible. From a limited pool of attack
strategies, the attacker dynamically selects strategy by observing defender’s
actions in realtime. As we discuss in section I, the defense system uses
physical evidence about the network collected by sensors to verify event
occurrences in the network. We assume that the attacker cannot compromise
these sensors and is incapable of compromising the IoT hub through which all
sorts of communication among IoT devices occur in a smart home network.

##  III IoTWarden Defense System

We design IoTWarden as a real-time defense system that infers attack behavior
by monitoring the impact of attacker’s actions in the network and adopts an
optimal policy to select defense actions, maximizing the total security
reward. IoTWarden continuously assesses the security status of the smart home
network and takes necessary defense actions to make some exploits infeasible
so that the attacker cannot complete a trigger-action IoT attack. We assume
that IoTWarden is hosted in the hub, and it enables the hub to block the
activation of actions in target IoT devices when it identifies the event
injection in the network.

IoTWarden consists of three main components: 1) state machine generator, 2)
policy determiner, and 3) policy enforcer. Fig. 1 presents the system
architecture of IoTWarden.

Figure 1: IoTWarden System Architecture

###  III-A State Machine Generator

Considering the IoT network as system environment, this component creates a
finite state machine with $N$ unique system states, such as
$S\negmedspace=\negmedspace\\{s_{i}\\},1\negmedspace\leq\negmedspace
i\negmedspace\leq\negmedspace N$ and $M$ unique actions, such as
$A\negmedspace=\negmedspace\\{a_{k}\\},1\negmedspace\leq\negmedspace
k\negmedspace\leq\negmedspace M$. Hence, $s_{t}\negmedspace\in\negmedspace S$
represents the environment state inferred by the hub at timestep $t$ due to
the reporting of $\\{c_{t}\\}\negmedspace\in\negmedspace C$, and the action
$a_{t}\negmedspace\in\negmedspace A$ makes the environment transition into
another state $s_{t+1}$ at timestep $t+1$ with a probability
$T(s_{t},a_{t},s_{t+1})\negmedspace=\negmedspace Pr(s_{t+1}|s_{t},a_{t})$
yielding a security gain (reward) $R(s_{t},a_{t},s_{t+1})=\\{r_{t}\\}$. We
assume that the action space $A$ contains the following four
$(M\negmedspace=\negmedspace 4)$ actions: {event injection ($a_{1}$), checking
device accessibility ($a_{2}$), monitoring security status of the network
($a_{3}$), and blocking triggers ($a_{4}$)}. IoTWarden chooses $<\negmedspace
a_{1},a_{2}\negmedspace>$ to mimic the behavior of an attacker during the
training phase of the system, and the defense agent takes the actions
$<\negmedspace a_{3},a_{4}\negmedspace>$ during both the training and the
deployment phase.

####  III-A1 Reward Function

We design the defense agent to be reactive against attack actions. If event
injection actions are taken aggressively, we want the defense agent to take
blocking triggers actions more frequently. We define a parameter attack
proximity factor $p$ to indicate how close the attack is to the ultimate goal
node. We compute $p$ by taking ratio between the number of events already
compromised and the total events in the attack chain. When $p$ increases, we
want the defense agent to take more blocking triggers actions. The ultimate
goal here is not to let the attacker compromise the goal node. Therefore, we
design the reward function to help the defense agent decide when to allow the
attacker to perform injection operations and when to start blocking triggers.
The reward function is defined using the following equation (1):

$R(.)=\begin{cases}n_{a_{3}}r_{a_{3}}-\frac{pn_{a_{1}}r_{a_{1}}}{n_{a_{1}}+n_{a_{2}}}-G_{r}&\mbox{
if }\frac{n_{a_{1}}p}{n_{a_{1}}+n_{a_{2}}}<k\\\ \\\
\frac{(n_{a_{4}}r_{a_{4}})(n_{a_{3}}r_{a_{3}})}{n_{a_{4}}+n_{a_{3}}}\\\
-max\big{(}n_{a_{2}}r_{a_{2}},\frac{pn_{a_{1}}r_{a_{1}}}{n_{a_{1}}+n_{a_{2}}}+G_{r}\big{)}&\mbox{otherwise}\end{cases}$
(1)

Hence, $n_{a_{1}},n_{a_{2}},n_{a_{3}},\text{ and }n_{a_{4}}\negmedspace$
respectively represent the number of actions $a_{1},a_{2},a_{3},\text{ and
}a_{4}$ taken in the environment. On the contrary,
$r_{a_{1}},r_{a_{2}},r_{a_{3}},\text{ and }r_{a_{4}}\negmedspace$ respectively
represent the immediate reward given by the environment for taking the actions
$a_{1},a_{2},a_{3},\text{ and }a_{4}$. The injection threshold $k$ is a user
defined parameter here. The value of $k$ indicates the tolerance of the
defense agent against the injection operations. The parameter $G_{r}$
represents the reward for the attacker to compromise the ultimate goal node,
and the defense agent always tries to make that impossible. Any node
compromised beyond goal node yields $G_{r}=0$.

###  III-B Policy Determiner

IoTWarden adopts an optimal policy that dictates how the defense agent chooses
actions at runtime. To determine this policy, IoTWarden solves a Markov
Decision Process $<\negmedspace S,A,T,R\negmedspace>$ and trains a policy that
maximizes the future discounted reward,
$R_{t}\negmedspace=\negmedspace\sum_{t=0}^{t=T}\gamma^{t}r_{t}$ at timestep
$t$, where the simulation stops at $t=T$, and $\gamma$ ($0\leq\gamma\leq 1$)
is the discount factor. Given a state $s\in S$, the objective here is to
discern a policy $\pi(s)$ that provides optimal state-action value pairs
$<\negmedspace s,a\negmedspace>$ from a function $Q^{*}(s,a)$ (called
Q-function) yielding the maximum security reward $R_{t}$, such as:

$Q^{\pi^{*}}(s_{t},a_{t})=\max_{\pi}E\big{[}R_{t}|s_{t}=s,a_{t}=a,\pi\big{]}$
(2)

The Q-function obeys the Bellman equation [19], and the equation (2) can be
rewritten as:

$Q^{\pi^{*}}(s_{t},a_{t})=E\big{[}r_{t}+\gamma\max_{a^{\prime}\in\pi(s_{t})}Q^{*}(s_{t+1},a^{\prime}|s_{t},a)\big{]}$
(3)

The policy determiner constructs a Deep Q-Network (DQN) [13] to estimate the
Q-function and utilizes a neural network function approximator with weights
$\theta_{i}$ at the iteration $i$ to compute the temporal difference error
$\delta$. As shown in equation (5), it uses the Huber loss [20] function to
minimize this error $\delta$ over a batch $\beta$ of transitions
$<\negmedspace s_{t},a_{t},s_{t+1},r_{t}\negmedspace>$ from a replay memory.
These transitions represent the defense agent’s history of interactions with
the environment. The policy determiner samples these transitions from the
replay memory using an exploration-exploitation trade-off approach similar to
the $\epsilon$-greedy approach discussed in [21]. The following equation (4)
presents the formula used to compute $\delta$ and equation (5) shows how this
quantity $\delta$ is minimized during the training period.

$\delta=E\big{[}r_{t}+\gamma\max_{a^{\prime}\in\pi(s_{t})}Q(s_{t+1},a^{\prime};\theta_{i+1})-Q(s_{t},a;\theta_{i})\big{]}$
(4)

$\mathcal{L}=\frac{1}{|\beta|}\sum_{{(s_{t},a,s_{t+1},r_{t})}\in\beta}\mathcal{L(\delta)}$
(5)

where,

$\mathcal{L(\delta)}=\begin{cases}\frac{1}{2}\delta^{2}&\mbox{ if
}|\delta|\leq 1\\\ |\delta|-\frac{1}{2}&\mbox{otherwise}\end{cases}$

When we train the DQN, we ensure that the following action selection method is
adopted to balance between exploration and exploitation.

  * •

Exploration: an action $a$ is randomly selected from $A$ with the probability
of $\epsilon$,

  * •

Exploitation: the optimal action $a_{t}\in A$ is chosen as a greedy option
with the probability of $1-\epsilon$.

We formulate $\epsilon$ using the following equation (6):

$\epsilon=\epsilon_{end}+(\epsilon_{start}-\epsilon_{end})\medspace
e^{{\frac{-t}{\epsilon_{decay}}}}$ (6)

Hence, $\epsilon_{start}$ and $\epsilon_{end}$ respectively denotes the
maximum and minimum value of a range in which the value of $\epsilon$ lies.
The parameter $\epsilon_{decay}$ denotes the decay factor that gradually
diminishes the value of $\epsilon$, and $t$ denotes the current timestep.

###  III-C Policy Enforcer

To counter a realtime attack, IoTWarden leverages the trained policy $\pi^{*}$
to choose optimal defense actions. At timestep $t$, IoTWarden receives the
state $s_{t}$ from the environment and utilizes the function approximator to
choose the best defense action $a_{t}\in A$ that maximizes the ultimate
reward. Once the policy enforcer takes the chosen action, the environment
returns a reward $r_{t}$ to the defense agent based on the reward function
given in the equation (1). The complete policy enforcement process is
illustrated in Fig. 2.

Figure 2: Illustration of IoTWarden Policy Enforcement

##  IV Experiment and Simulation

We implement IoTWarden using TensorFlow and conduct experiments simulating a
trigger-action attack in a smart home network to evaluate the performance of
the system. We utilize the PEEVES [8] dataset to extract the state space
needed to be encoded in the simulating environment. This dataset contains
event traces collected from 12 different IoT devices and physical evidence
measured by 48 different sensors. We utilize 24-hours data in our experiment.
We run the experiment on an Apple M1 Pro machine with 16 GB RAM and 8-core
GPU.

###  IV-A Determining Optimal Attack Sequences

We use a Hidden Markov Model based approach described in [5] to determine IoT
events likely to occur in a trigger-action attack. We call them crucial nodes.
Later, we implement an LSTM [12] based RNN to create optimal attack sequences
exploiting temporal dependencies exist among IoT events captured in the PEEVES
[8] dataset and considering each crucial node as the starting node of a
possible attack chain. The RNN architecture contains one embedding layer to
convert input event sequences into fixed-length vectors of size 128, two
bidirectional LSTM layers with 64 and 32 units respectively, and one fully-
connected output layer with 23 classes. Each event sequence given as input to
the embedding layer records 227 different event occurrences.

###  IV-B IoT Environment

From the optimal attack sequences, we extract events based on origin, convert
them into states, and encode them into the system environment for simulation.
We encode 12 unique states and 4 actions in the environment using OpenAI Gym
[22]. We also integrate the reward function in the environment so that the
defense agent is rewarded accordingly for the actions taken at runtime.

###  IV-C Function Approximator

Given a state in the environment, we use a neural network function
approximator to estimate reward for each available action and output the
optimal action yielding the highest reward. The neural network we use has 2
hidden layers with 64 and 32 neurons, while the input and output layers
include 128 and 4 units respectively. We use the $ReLU$ activation function
for the input and hidden layers. For the output layer, we use the $Linear$
activation function. We use Huber loss [20] as the loss function in this
neural network.

###  IV-D Deep Q-Network

The DQN we use to estimate Q-function has the hyperparameter settings listed
in Table I. We train the network for $250$ episodes and use Adam [23]
optimizer with the learning rate, $\alpha\negmedspace=\negmedspace 1e^{-4}$.
During our training, we update a policy network at a constant rate, $\tau=20$.
To record the defense agent’s interaction with the environment, we use a
replay buffer of size $50,000$ and sample $16$ interactions at a time when the
optimal action is chosen.

Parameter | Quantity
---|---
Total episodes | 250
Number of epochs per episode | 100
Optimizer | Adam
Minibatch size, $\beta$ | 16
Discount factor, $\gamma$ | 0.95
Learning rate, $\alpha$ | $1e^{-4}$
$(\epsilon_{start},\epsilon_{end},\epsilon_{decay})$ | (1.0, 0.1, 0.99999)
Target network update frequency, $\tau$ | 20 episodes
Replay buffer size | 50,000
TABLE I: Hyperparameter settings for Deep Q-network

##  V Results and Evaluation

###  V-A Optimal Attack Sequence

Before training the LSTM-based RNN to extract optimal attack sequences, we
split the PEEVES dataset into training and validation sets with 80-20 ratio.
In Fig. 3(a), we see the training and validation accuracy of the model over
100 epochs, while the training and validation loss are depicted in Fig. 3(b).
We see that both training and validation accuracy becomes $>0.99$ after
$epoch\negmedspace=\negmedspace 9$. Even though we see some unexpected decline
in several occasions, for example, at $epoch\negmedspace=\negmedspace 44$, we
still achieve $>\negmedspace 0.90$ accuracy all the time. On the other hand,
both the training and validation loss becomes $\approx 0.02$ most of the time
after $epoch\negmedspace=\negmedspace 15$. Despite a few irregular loss at
$epoch\negmedspace=\negmedspace 23,44,69$, we can conclude that after
$epoch\negmedspace=\negmedspace 9$, the training and validation loss always
stays $<\negmedspace 0.10$, and they become very close to $0$ a number of
times.

(a) Training and validation accuracy over epochs

(b) Training and validation loss over epochs

Figure 3: Performance evaluation of the LSTM-based RNN

###  V-B Rewards

In our simulation, the defense agent is trained for $250$ episodes,
interacting with the environment for $100$ epochs in each episode. Each
interaction yields a discrete reward for the defense agent, and the defense
agent accumulates all the rewards received over $100$ epochs together to
compute the total reward it achieves in a single episode. Fig. 4(a) shows the
total reward earned in our simulation over the entire $250$ episodes. We see
that the total reward the defense agent receives for the first few episodes
doesn’t follow a stable pattern, and that’s because instead of following a
fixed optimal policy from the start, it explores all possible scenarios to
determine the optimal policy that guarantees the maximization of the total
reward at the end. Once the agent learns the optimal policy, the total reward
it receives over the episodes follows a pretty stable pattern, as shown in
Fig. 4(a) after $\approx 70$ episodes.

(a) Reward over episodes

(b) Time overhead over episodes

Figure 4: Simulation results: reward and time overhead over episodes

###  V-C Computation Overhead

In our simulation, the defense agent dedicates most of its computation time to
determine optimal state-action value pairs, sample experiences from the replay
buffer, and train the policy network. Therefore, we compute the total time
required in each episode to perform all these tasks and call it time overhead.
Fig. 4(b) shows how time overhead changes over the episodes. We can see that
after $40$ episodes, the overhead reaches stability, close to $2.85$ seconds.

###  V-D Attack-Defense Dynamic

We design the defense agent to be reactive against the attack actions. If
event injection ($a_{1}$) actions are taken aggressively, the defense agent
chooses to take blocking triggers ($a_{4}$) actions more often. As we see in
Fig. 5, the defense agent initially becomes very aggressive, but it quickly
starts to learn the attack-defense dynamic. Since blocking triggers action
negatively impacts the availability of the network devices, the defense agent
avoids taking redundant blocking triggers actions. Fig. 5 shows that the
number of blocking triggers actions taken by the defense agent is always
smaller than the number of event injection actions taken after a certain
number of episodes ($\approx$ 30 episodes). It is possible that the attacker
needs to inject multiple fake events to compromise a certain device,
especially if any trigger operation to that particular device has been blocked
earlier by the defense agent. Therefore, the objective of a trained defense
agent is to take less blocking triggers actions compared to the event
injection actions taken, which is clearly evident from Fig. 5.

Figure 5: Number of injection and block actions over episodes

###  V-E Impact of Injection Threshold

As we see in equation (1), the injection threshold, parameterized as $k$,
dictates the selection of optimal defense actions. To show the impact of $k$
on the reward function, we compute the average episodic reward,
$\bar{R_{t}}=\frac{\sum_{t=1}^{N}R_{t}}{N}$, where $N=100$ epochs, and $R_{t}$
represents the total reward achieved in a single epoch. In Fig. 6, we show how
the injection threshold $k$ ranging between $[0,1]$ impacts the average
episodic reward achieved by the defense agent. We see that after $k=0.25$, the
impact of injection threshold on the reward function is quite constant, i.e.,
even though a greater $k$ allows an attacker to perform more event injection
operations, the defense agent still achieves a certain level of reward and
effectively secure network nodes. In conclusion, once the defense agent
determines the optimal defense policy, the increased aggressiveness in attack
behavior barely changes the security status of the network.

Figure 6: Average episodic return over injection thresholds

##  VI Conclusion

In this paper, we propose a real-time defense system named IoTWarden that
infers attack behaviors upon an IoT network and counters a trigger-action
attack by following an optimal action policy. We implement a neural network
function approximator to select optimal action at each environment state by
maximizing the security gain and train the defense policy using a Deep
Q-Network. We implement the system using TensorFlow and conduct extensive
simulation to evaluate the performance of the system. The experiment results
show that the defense agent is capable of achieving stable security rewards
with very low computation overhead by following an optimal defense policy
under different aggressiveness levels of the injection operations conducted by
an attacker. As our approach focuses on real time detection, it can work in
parallel with the static analysis-based security measures.

Future extensions of our approach contain the following aspects. First, we
plan to improve our reinforcement learning-based mechanism so that it has
user-configurable overhead. This will allow the mechanism to be adopted at
different IoT environments with computation restriction. Second, we will
extend our model with probability-based attack path and defense method
selection so that end users have a better understanding of the coverage of the
selected defense measures. Last but not least, we will deploy our approach at
the SmartHome lab at our school and conduct experiments on real devices.

## References

  * [1] M. O. Ozmen, R. Song, H. Farrukh, and Z. B. Celik, “Evasion attacks and defenses on smart home physical event verification,” in _30th Annual Network and Distributed System Security Symposium, NDSS_ , 02 2023.
  * [2] Z. B. Celik, E. Fernandes, E. Pauley, G. Tan, and P. McDaniel, “Program analysis of commodity iot applications for security and privacy: Challenges and opportunities,” _ACM Comput. Surv._ , vol. 52, no. 4, Aug. 2019. [Online]. Available: https://doi.org/10.1145/3333501
  * [3] “Samsung smartthings,” https://www.smartthings.com/, accessed: 2022-10-21.
  * [4] “Ifttt: Every thing works better together,” https://ifttt.com/, accessed: 2022-10-21.
  * [5] M. M. Alam, M. S. I. Sajid, W. Wang, and J. Wei, “Iotmonitor: A hidden markov model-based security system to identify crucial attack nodes in trigger-action iot platforms,” in _2022 IEEE Wireless Communications and Networking Conference (WCNC)_ , 2022, pp. 1695–1700.
  * [6] J. Fan, Y. He, B. Tang, Q. Li, and R. Sandhu, “Ruledger: Ensuring execution integrity in trigger-action iot platforms,” in _IEEE INFOCOM 2021 - IEEE Conference on Computer Communications_ , 2021, pp. 1–10.
  * [7] M. M. Alam and W. Wang, “A comprehensive survey on data provenance: State-of-the-art approaches and their deployments for iot security enforcement,” _Journal of Computer Security_ , vol. 29, pp. 423–446, 06 2021.
  * [8] S. Birnbach, S. Eberz, and I. Martinovic, “Peeves: Physical event verification in smart homes,” in _Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security_. ACM, 2019.
  * [9] C. Fu, Q. Zeng, and X. Du, “HAWatcher: Semantics-Aware anomaly detection for appified smart homes,” in _30th USENIX Security Symposium (USENIX Security 21)_ , Aug. 2021, pp. 4223–4240.
  * [10] L. Babun, A. K. Sikder, A. Acar, and A. S. Uluagac, “Iotdots: A digital forensics framework for smart environments,” _CoRR_ , 2018. [Online]. Available: http://arxiv.org/abs/1809.00745
  * [11] Z. B. Celik, G. Tan, and P. Mcdaniel, “Iotguard: Dynamic enforcement of security and safety policy in commodity iot,” _Proceedings 2019 Network and Distributed System Security Symposium_ , 2019. [Online]. Available: https://api.semanticscholar.org/CorpusID:141048877
  * [12] S. Hochreiter and J. Schmidhuber, “Long short-term memory,” _Neural Comput._ , vol. 9, no. 8, p. 1735–1780, nov 1997. [Online]. Available: https://doi.org/10.1162/neco.1997.9.8.1735
  * [13] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. A. Riedmiller, “Playing atari with deep reinforcement learning,” _ArXiv_ , vol. abs/1312.5602, 2013. [Online]. Available: https://api.semanticscholar.org/CorpusID:15238391
  * [14] P. Ammann, D. Wijesekera, and S. Kaushik, “Scalable, graph-based network vulnerability analysis,” in _Proceedings of the 9th ACM Conference on Computer and Communications Security_ , ser. CCS ’02. New York, NY, USA: Association for Computing Machinery, 2002, p. 217–224. [Online]. Available: https://doi.org/10.1145/586110.586140
  * [15] O. Sheyner, J. Haines, S. Jha, R. Lippmann, and J. Wing, “Automated generation and analysis of attack graphs,” in _Proceedings 2002 IEEE Symposium on Security and Privacy_ , 2002, pp. 273–284.
  * [16] S. Jajodia, “Topological analysis of network attack vulnerability,” ser. PST ’06. New York, NY, USA: Association for Computing Machinery, 2006. [Online]. Available: https://doi.org/10.1145/1501434.1501437
  * [17] R. Trimananda, J. Varmarken, A. Markopoulou, and B. Demsky, “Packet-level signatures for smart home devices,” in _Network and Distributed System Security Symposium_ , 2020. [Online]. Available: https://api.semanticscholar.org/CorpusID:211266570
  * [18] W. Zhang, Y. Meng, Y. Liu, X. Zhang, Y. Zhang, and H. Zhu, “Homonit: Monitoring smart home apps from encrypted traffic,” in _Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security_ , ser. CCS ’18. New York, NY, USA: Association for Computing Machinery, 2018, p. 1074–1088. [Online]. Available: https://doi.org/10.1145/3243734.3243820
  * [19] R. Bellman, “A markovian decision process,” _Indiana Univ. Math. J._ , vol. 6, pp. 679–684, 1957.
  * [20] P. J. Huber, “Robust Estimation of a Location Parameter,” _The Annals of Mathematical Statistics_ , vol. 35, no. 1, pp. 73 – 101, 1964. [Online]. Available: https://doi.org/10.1214/aoms/1177703732
  * [21] M. Wunder, M. Littman, and M. Babes-Vroman, “Classes of multiagent q-learning dynamics with $\epsilon$-greedy exploration,” in _International Conference on Machine Learning_ , 08 2010, pp. 1167–1174.
  * [22] G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba, “Openai gym,” _CoRR_ , vol. abs/1606.01540, 2016. [Online]. Available: http://arxiv.org/abs/1606.01540
  * [23] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _CoRR_ , vol. abs/1412.6980, 2014. [Online]. Available: https://api.semanticscholar.org/CorpusID:6628106