Covariance-Robust Dynamic Watermarking

Robust data-driven decision-making has gained attention in the literature on algorithmic fairness. Motivated by machine learning tasks with societal applications, the fairness literature has sought to design learning methods that refrain from considering certain variables. To that extent, this body of work defines rigorous, mathematical notions of fairness for supervised learning [15, 16, 17, 18, 19, 20, 21, 22], which have recently been extended to unsupervised learning by [23, 24].

The work in [25] outlines a general framework: Consider $(X,Y,Z)$ with a joint distribution $\mathbb{P}$, where $X$ are exogenous inputs, $Y$ are endogenous “targets”, and $Z$ is a “protected attribute”. The goal is to choose a decision rule $\delta(x)$ that makes a decision $d$ using inputs $X$, in order to minimize some risk function $\mathcal{R}_{\mathbb{P}}(\delta,Y)$. In dynamic watermarking: $X$ are measurements, $Y$ is a binary variable that denotes if the system is under attack, and $Z$ is the true system characterization; our decision rule $\delta$ for if the system is under attack is made without $Y$ and $Z$, which are not observed. We then define a decision rule to be without disparate impact if

where $\delta(X)\perp\!\!\!\perp Z$ means $\delta(X)$ is independent of $Z$. This increases fairness because it removes any impact of $Z$ on the decision by imposing independence as a constraint. However, some [18, 16] have argued that this above definition of fairness can be too restrictive in some cases and that equalized odds is a better definition of fairness. Its only difference is that in (1) we replace $\delta(X)\perp\!\!\!\perp Z$ with $(\delta(X)\perp\!\!\!\perp Z)|Y$. That is, equalized odds ask for independence of $\delta(X)$ and $Z$ when conditioned on $Y$. We can interpret equalized odds as requiring error rates to be similar across protected groups. Finally, a notion associated equalized odds is that of equal opportunity, which amounts to enforcing $(\delta(X)\perp\!\!\!\perp Z)|Y=y$, for some value $y$. This is relevant when one particular type of error is of more interest than another.

Fairness is relevant to the design of robust tests for two reasons. First, it provides a well-established technical language with which to discuss our requirement of robustness. Past dynamic watermarking techniques require exact system knowledge, and as such the corresponding watermarking tests will have error rates that are biased over inevitable system perturbations or uncertainties. Fairness notions such as equalized odds and equal opportunity allow for more specific framing of the problem and thus give a framework to design more robust methods for dynamic watermarking.

Second, robust cyber-security methods will have improved social impacts, which is the most general way of interpreting “fairness”. For example, smart homes can have many sensors. Changes in the distribution of sensor noise can correlate with factors such as climate, which correlates with geography and thus attributes like race, ethnicity, or class. A systemic bias in the ability to detect threats thus yields, and possibly perpetuates, systemic bias in outcomes among these groups. Robustness of cyber-security methods thus have the potential to improve societal fairness of the corresponding methods.

In Sect. II, we outline key terminology and results in dynamic watermarking. In Sect. III-A, we present our covariance-robust dynamic watermarking scheme for the case of fixed, but unknown, measurement noise covariance. This is then extended in Sect. III-B to the case where measurement noise covariance is allowed to slowly vary. Sect. IV presents empirical results that demonstrate efficacy of our approach.

Consider a partially-observed MIMO LTI system

for $x_{n},w_{n}\in\mathbb{R}^{p},u_{n}\in\mathbb{R}^{q}$ and $y_{n},z_{n},v_{n}\in\mathbb{R}^{m}$. Here $w_{n}$ is mean-zero i.i.d. multivariate Gaussian process noise with covariance matrix $\Sigma_{W}$, and this is independent of $z_{n}$ that is i.i.d. Gaussian measurement noise with mean-zero; but we assume that the covariance matrix for $z_{n}$ is a linear function $\Sigma_{Z}(\theta)$ of a set of parameters $\theta\in\mathcal{P}\subset\mathbb{R}^{d}$ taking values in polyhedron $\mathcal{P}$. For now, $\theta$ is assumed constant but unknown for any fixed system. The $v_{n}$ is an additive signal chosen by an attacker who seeks to corrupt sensor measurements.

Stabilizability of $(A,B)$ and detectability of $(A,C)$ imply the existence of a controller $K$ and observer $L$ such that $A+BK$ and $A+LC$ are Schur stable. The closed-loop system can be stabilized using the control input $u_{n}=K\hat{x}_{n}$, where $\hat{x}_{n}$ is the observer-estimated state. Define $\tilde{x}_{n}^{\vphantom{\textsf{T}}}=\begin{bmatrix}x_{n}^{\textsf{T}}&\hat{x}_{n}^{\textsf{T}}\end{bmatrix}^{\textsf{T}}$, $\underline{D}^{\vphantom{\textsf{T}}}=\begin{bmatrix}I^{\vphantom{\textsf{T}}}&0^{\vphantom{\textsf{T}}}\end{bmatrix}^{\textsf{T}}$, $\underline{L}^{\vphantom{\textsf{T}}}=\begin{bmatrix}0^{\vphantom{\textsf{T}}}&-L^{\textsf{T}}\end{bmatrix}^{\textsf{T}}$, and

We can write the closed-loop evolution of the state and estimated state when $v_{n}\equiv 0$ as $\tilde{x}_{n+1}=\underline{A}\tilde{x}_{n}+\underline{D}w_{n}+\underline{L}z_{n}$. Alternatively, we may define the observation error $\delta_{n}=\hat{x}_{n}-x_{n}$. Let $\breve{x}_{n}^{\vphantom{\textsf{T}}}=\begin{bmatrix}x_{n}^{\textsf{T}}&\delta_{n}^{\textsf{T}}\end{bmatrix}^{\textsf{T}}$, $\underline{\underline{D}}^{\vphantom{\textsf{T}}}=\begin{bmatrix}I^{\vphantom{\textsf{T}}}&-I^{\vphantom{\textsf{T}}}\end{bmatrix}^{\textsf{T}}$, $\underline{\underline{L}}^{\vphantom{\textsf{T}}}=\underline{L}^{\vphantom{\textsf{T}}}$, and

The closed-loop system for this change of variables is $\breve{x}_{n+1}=\underline{\underline{A}}\breve{x}_{n}+\underline{\underline{D}}w_{n}+\underline{\underline{L}}z_{n}$. Note that $\underline{\underline{A}}$ is Schur stable since both $A+BK$ and $A+LC$ are Schur stable.

Following [26], we consider attacks where $v_{n}=\alpha(Cx_{n}+z_{n})+C\eta_{n}+\zeta_{n}$ for a fixed $\alpha\in\mathbb{R}$ and i.i.d. Gaussian $\zeta_{n}$ with mean-zero and covariance matrix $\Sigma_{S}$. Here, the $\eta_{n}$ are chosen to follow the process $\eta_{n+1}=(A+BK)\eta_{n}+\omega_{n}$, where $\omega_{n}$ are similarly i.i.d. Gaussian with mean-zero and covariance matrix $\Sigma_{O}$. The implication is that the attacker minimizes or mutes the true output $Cx_{n}+z_{n}$, and instead replaces it with a simulated output that follows the system dynamics and is thus not easily distinguishable as false. Furthermore, the attacker has access to process $w_{n}$ and measurement noise $z_{n}$. With this attack, the closed-loop systems above become $\tilde{x}_{n+1}=\underline{A}\tilde{x}_{n}+\underline{D}w_{n}+\underline{L}(z_{n}+v_{n})$ and $\breve{x}_{n+1}=\underline{\underline{A}}\breve{x}_{n}+\underline{\underline{D}}w_{n}+\underline{\underline{L}}(z_{n}+v_{n})$.

The steady-state distribution of $\delta_{n}$ in an unattacked system will be Gaussian with mean-zero and a covariance matrix of

Dynamic watermarking adds a small amount of Gaussian noise $e_{n}$, the values unknown to the attacker, into the control input $u_{n}=K\hat{x}_{n}+e_{n}$. This private excitation has mean-zero and covariance matrix $\Sigma_{E}$. Defining $\underline{B}^{\vphantom{\textsf{T}}}=\begin{bmatrix}B^{\textsf{T}}&B^{\textsf{T}}\end{bmatrix}^{\textsf{T}}$ and $\underline{\underline{B}}^{\vphantom{\textsf{T}}}=\begin{bmatrix}B^{\textsf{T}}&0^{\vphantom{\textsf{T}}}\end{bmatrix}^{\textsf{T}}$, the closed-loop systems with watermarking are given by $\tilde{x}_{n+1}=\underline{A}\tilde{x}_{n}+\underline{B}e_{n}+\underline{D}w_{n}+\underline{L}(z_{n}+v_{n})$ and $\breve{x}_{n+1}=\underline{\underline{A}}\breve{x}_{t}+\underline{\underline{B}}e_{n}+\underline{\underline{D}}w_{n}+\underline{\underline{L}}(z_{n}+v_{n})$, respectively.

The watermarking noise $e_{n}$ leaves a detectable signal in the measurements $y_{n}$, which can detect the presence of an attack $v_{n}$ by comparing the observer error $C\hat{x}_{n}-y_{n}$ to previous values of the watermark $e_{n-k}$ for some integer $k>0$. Specifically, the work in [26] proposes the tests

where $k^{\prime}=\min_{k\geq 1}\{C^{\vphantom{\textsf{T}}}(A+BK)^{k}B^{\textsf{T}}\neq 0\}$. Any modeled attack passing these tests can be shown to asymptotically have zero power $\operatorname{as-lim}_{N\rightarrow\infty}\frac{1}{N}\sum_{n=0}^{N-1}v_{n}^{\textsf{T}}v_{n}^{\vphantom{\textsf{T}}}=0$ [26].

Finally, [26] also provides a test statistic for implementing the above test. Define $\psi_{n}=\begin{bmatrix}(C\hat{x}_{n}-y_{n})^{\textsf{T}}&e_{n-k^{\prime}-1}^{\textsf{T}}\end{bmatrix}^{\textsf{T}}$ and $S_{n}=\sum_{i=n+1}^{n+\ell}\psi_{n}^{\vphantom{\textsf{T}}}\psi_{n}^{\textsf{T}}$. Then the negative log-likelihood of a Wishart distribution is

This can be used to perform a statistical hypothesis test to detect attacks when using dynamic watermarking.

We begin by stating our assumptions for this case. First, we assume that we have knowledge of a set of positive semidefinite matrices $\Sigma_{z,1},\dots,\Sigma_{z,d}$ such that these matrices are affinely independent and $\Sigma_{Z}(\theta)\in\mathrm{int}(\Omega^{Z})$ for the set

Note that $\Omega^{Z}$ is a polyhedron, and that this set is defined to be the convex combination of ${\Sigma}_{z,1},\dots,{\Sigma}_{z,d}$. Our first result characterizes $\Omega^{\Delta}$, which is the set of possible $\Sigma_{\Delta}(\theta)$.

Since $E[\psi_{n}^{\vphantom{\textsf{T}}}\psi_{n}^{\textsf{T}}]=\mathrm{blkdiag}\{C^{\vphantom{\textsf{T}}}\Sigma_{\Delta}^{\vphantom{\textsf{T}}}C^{\textsf{T}}+\Sigma_{Z},\Sigma_{E}\}$, we need to characterize the set $\Omega$ of feasible matrices in terms of $\theta$.

The set $\Omega$ represents covariance matrices of $\psi_{n}$ that are “acceptable”, according to the original set $\Omega^{Z}$ of observation noise covariances that we should not mistake for attacks.

Finally, consider a modification of (DW) given by

Note (9) is the negative log-likelihood of an $(m+q)\times(m+q)$ Wishart distribution with scale matrix $V^{-1}$ and $\ell$ degrees of freedom. Now, we may present our test statistic. Let $\Omega^{-1}=\{V:V^{-1}\in\Omega\}$ and define the test statistic

for the composite null hypothesis $H_{0}:E[\psi_{n}^{\vphantom{\textsf{T}}}\psi_{n}^{\textsf{T}}]\in\textrm{int}(\Omega)$. For some $0\leq\nu$, consider the test

Since $\arg\min_{V\in\Omega^{-1}}\mathcal{L}(S_{n},V)=S_{n}^{-1}$, this proposed test is equivalent to the generalized likelihood ratio test.

This is a useful result because it implies that, in the proper regime, our test can come arbitrarily close to satisfying the initial goal of remaining robust to some uncertainty in the distribution of the measurement noise. However, $\Omega^{-1}$ is a non-convex set, and so the computation of $T(S_{n})$ is difficult. To this end, we propose the approximate test statistic

A key difference between this setting and that of the static distribution is that a shift in the observer noise covariance in one period can have impacts on $\Sigma_{\Delta}$ over the next few periods that do not easily fit into our previous representation of the $\Omega$. This is because it will take many steps before the covariance of $\delta_{n}$ approaches its asymptotic limit in $\Omega$. Thus, to accommodate a dynamically changing distribution of $z_{n}$, we must use an expansion of the set $\Omega$.

We modify our setup for this subsection. The true covariance of $\delta_{n}$ and $z_{n}$ are $\Sigma_{\Delta_{n}}$ and $\Sigma_{Z_{n}}$, respectively. Let $\Psi_{n}=\Sigma_{Z_{n}}-\Sigma_{Z_{n-1}}$ and $\Phi_{n}^{j}=(A+LC)^{j}L\Psi_{n}L^{\textsf{T}}{(A+LC)^{j}}^{\textsf{T}}$. Note that all $\Sigma_{Z_{n}}$ are still assumed to be in $\Omega^{Z}$. Finally, we make some additional assumptions. Since the spectral radius of $A+LC$ is less than one, there exists some induced norm (denote this $\|\cdot\|$) such that $\|A+LC\|<1$ [29]. We assume $\theta$ changes every step but $\Sigma_{Z_{0}}\in\Omega$ and all $\Psi_{n}$ satisfy $\|\Psi_{n}\|\leq\xi$ for some known value of $\xi>0$. We also assume the system starts at steady state in the sense $\Sigma_{\Delta_{0}}=(A+LC)\Sigma_{\Delta_{0}}(A+LC)^{\textsf{T}}+\Sigma_{W}+L\Sigma_{Z_{0}}L^{\textsf{T}}$. Under these assumptions we have:

With this $\varepsilon$, it is straightforward to extend the previous test statistic (CRDW) to this new expansion of $\Omega$ as long as $\bar{\Sigma}_{k}-\varepsilon I$ remains positive definite for all $k$. In this case, we may define our new test statistic as