Attack Impact Evaluation by Exact Convexification
through State Space Augmentation

The attack impact evaluation problem has been widely considered in control system security [8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]. The formulations themselves are basically similar, and technically the problem is reduced to a constrained optimal control problem. However, different approaches should be taken depending on the class of the system and the detector, the objective function that quantifies the impact caused by an attack signal, and the class of possible attack strategies. An early work [9] considers the $\chi^{2}$ detector, which is the simplest stateless detector. The work [10] provides a rather general formulation where an essential bound is provided using KLD. The CUSUM detector is considered in [11]. In [15], the author considers a detector using $\ell^{2}$ norm of the output signal assuming that the system is deterministic. Finally, the other works consider one of the detectors. To the best of our knowledge, this study is the first framework that can handle general detectors for attack impact evaluation.

Our proposed method is based on state space augmentation, which adds information of alarm history for decision making at each step. A similar idea has been proposed in risk-averse MDP[22, 23, 24]. In [22], the authors consider a non-standard MDP where the objective function is given by not expectation but conditional-value-at-risk (CVaR), which is also referred to as average-value-at-risk. They show that value iteration can be applied by considering the augmented state space even for CVaR. The idea is generalized in [23] where not only CVaR minimization but also chance-constrained MDP are considered. The work [24] proposes risk-aware reinforcement learning based on the idea. Moreover, linear temporal logic specification techniques provide a rather general framework [25]. While these works are relatively abstract, this study exhibits a clear interpretation through a concrete application in the context of security, where the augmented state has a concrete interpretation, namely the number of alarm’s up until that time step.

The paper is organized as follows. Sec. II provides the system model, clarifies the threat model, and formulates the impact evaluation problem. In Sec. III, the difficulty of the formulated problem is explained, and a solution based on state space augmentation is proposed. Sec. IV considers an extension of the problem where the number of alarms throughout the entire time period is taken into account. It is shown that the approach proposed in Sec. III is still valid in the extended formulation. In Sec. V, the theoretical results are verified through numerical simulation. Finally, Sec. VI concludes and summarizes the paper.

Let $\mathbb{N}$ and $\mathbb{R}$ be the sets of natural numbers and real numbers, respectively. The $k$-ary Cartesian power of the set $\mathcal{X}$ is denoted by $\mathcal{X}^{k}$. The tuple $(x_{0},\ldots,x_{k})$ is denoted by $x_{0:k}$.

This study considers a control system with an attack detector. Its stochastic model is described by the finite-horizon MDP [26] with an alarm region given by

$$\mathcal{M}:=(\mathcal{X},\mathcal{A},P,\mathcal{T},\{r_{t}\}_{t\in\mathcal{T}},\mathcal{X}_{\rm a})$$

(1)

where $\mathcal{X}$ is the state space, $\mathcal{A}$ is the action space, $P$ is the state transition function from $\mathcal{X}\times\mathcal{A}$ to $\mathcal{X}$, $\mathcal{T}:=\{0,\ldots,T\}$ is the time index set, $r_{t}:\mathcal{X}\times\mathcal{A}\to\mathbb{R}$ for $t=0,\ldots,T-1$ and $r_{T}:\mathcal{X}\to\mathbb{R}$ are the reward functions, and $\mathcal{X}_{\rm a}\subset\mathcal{X}$ is the alarm region. An alarm implemented in the control system is triggered when the state reaches the alarm region. For simplicity, we assume the state space and the action space to be finite.

Example: We give a specific example that can be described in the form (1). Consider the block diagram in Fig. 1, which includes a nonlinear stochastic system equipped with a dynamic attack detector, which is also referred to as a stateful attack detector [27]. Let the dynamics of the control system $\Sigma$ and the detector $\mathcal{D}$ be given by

$$\Sigma:z_{t+1}=f(z_{t},a_{t},w_{t}),\quad\mathcal{D}:\left\{\begin{array}[]{ll}z^{\rm d}_{t+1}&=g(z^{\rm d}_{t},z_{t}),\\ \delta_{t}&=h(z^{\rm d}_{t},z_{t}),\end{array}\right.$$

(2)

respectively, where $z_{t}\in\mathcal{Z}$ and $z^{\rm d}_{t}\in\mathcal{Z}^{\rm d}_{t}$ are states, $a_{t}\in\mathcal{A}$ is an actuation signal caused by the attack, $w_{t}\in\mathcal{W}$ is noise, $\delta_{t}\in\{0,1\}$ is a binary signal that describes whether an alarm is triggered or not at the time step. Suppose that the noise $w_{t}$ is an independent and identically distributed random variable over a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $\mathcal{X}:=\mathcal{Z}\times\mathcal{Z}^{\rm d}$ and $\mathcal{A}$ be the state space and the action space in the MDP form (1), respectively. Determine the state transition function by

$$\begin{array}[]{l}P((B_{z},B^{\rm d}_{z})|(z,z^{\rm d}),a)\\ \quad:=\left\{\begin{array}[]{ll}P_{z}(B_{z}|z,a)&{\rm if}\ g(z^{\rm d},z)\in B^{\rm d}_{z},\\ 0&{\rm otherwise},\end{array}\right.\end{array}$$

where $B_{z}$ and $B^{\rm d}_{z}$ are Borel sets in $\mathcal{Z}$ and $\mathcal{Z}^{\rm d}$ and

$$\begin{array}[]{l}P_{z}(B_{z}|z,a):=\mathbb{P}(w_{t}\in B_{w}(B_{z},z,a)),\\ B_{w}(B_{z},z,a):=\{w\in\mathcal{W}:f(z,a,w)\in B_{z}\}.\end{array}$$

Further, let $\mathcal{X}_{\rm a}:=h^{-1}(\{1\})$ be the alarm region¹¹1Note that the state transition function $P$ is guaranteed to be a stochastic kernel if the maps $f,g,h$ are Borel measurable [28, Proposition 7.26].. Then, we can obtain an MDP in the form (1) by discretizing the spaces to be finite sets by using standard methods (for example, see [29]). More specific detector examples include the $\chi^{2}$ attack detector and the CUSUM attack detector [21]. The $\chi^{2}$ attack detector with the observed output $y_{t}=Cz_{t}$, the nominal output $y^{\rm n}_{t},$ and the threshold $\tau>0$ is represented by

$$\mathcal{D}:\delta_{t}=\left\{\begin{array}[]{ll}1&{\rm if}\ \|Cz_{t}-y^{\rm n}_{t}\|^{2}>\tau,\\ 0&{\rm otherwise}.\end{array}\right.$$

The CUSUM attack detector with the bias $b>0$ and the threshold $\tau>0$ is represented by

$$\mathcal{D}:\left\{\begin{array}[]{ll}z^{\rm d}_{t+1}&=\max(0,z^{\rm d}_{t}+\|Cz_{t}-y^{\rm n}_{t}\|-b),\\ \delta_{t}&=\left\{\begin{array}[]{ll}1&{\rm if}\ z^{\rm d}_{t}>\tau,\\ 0&{\rm otherwise}\end{array}\right.\end{array}\right.$$

with the observed signal and the nominal output²²2More precisely, the corresponding MDP should be time-varying owing to the nominal output. However, by adding the time information to the state, our discussion can readily be extended as long as finite-horizon problems are considered..

In this study, we consider the following threat model:

• •

  The adversary has succeeded to intrude into the system and can execute any action $a\in\mathcal{A}$ in a probabilistic manner at every time step.

• •

  The adversary has perfect model knowledge of $\mathcal{M}$.

• •

  The adversary possesses infinite memory and computation resources.

• •

  The adversary can observe the state at every time step.

• •

  The attack begins at $t=0$ and ends at $t=T-1$.

The threat model implies that the adversary can implement an arbitrary history-dependent randomized policy $\pi\in\Pi^{\rm h}$, where $\pi=(\pi_{t})_{t=0}^{T-1}$ is a tuple of policies at each time step, $\Pi^{\rm h}:=\{(\pi_{t})_{t=0}^{T-1}:\pi_{t}:\mathcal{H}_{t}\to\mathcal{P}(\mathcal{A})\}$ is the set of all history-dependent randomized policies, $\mathcal{H}_{t}:=\mathcal{X}^{t}\times\mathcal{A}^{t-1}$ is the set of histories at the time step $t\in\mathcal{T}$, and $\mathcal{P}(\mathcal{A})$ is the set of probabilistic measures with respect to the Borel algebra on $\mathcal{A}$. Let the canonical measurable space of the MDP be denoted by $(\Omega,\mathcal{F})$, where $\Omega:=\mathcal{X}^{T+1}\times\mathcal{A}^{T}$ and $\mathcal{F}$ is its product $\sigma$-algebra. Define the random variables $X_{t}$ and $A_{t}$ as the projection of each outcome into the state and action at the time step $t\in\mathcal{T}$, respectively. Throughout this paper, the initial state is fixed for simplicity. We denote the probability measure induced by $P$ given the policy $\pi$ by $\mathbb{P}^{\pi}$ and the expectation operator with respect to $\mathbb{P}^{\pi}$ by $\mathbb{E}^{\pi}$.

The objective of the adversary is to maximize a cumulative attack impact while avoiding being detected. Let the impact be quantified as the expectation of the sum of the reward functions $r_{t}$ with respect to $t\in\mathcal{T}$. Set the stealth condition to

$$\mathbb{P}^{\pi}(\lor_{t\in\mathcal{T}}X_{t}\in\mathcal{X}_{\rm a})\leq\Delta$$

(3)

where

$$(\lor_{t\in\mathcal{T}}X_{t}\in\mathcal{X}_{\rm a}):=\{x_{0:T}\in\mathcal{X}^{T+1}:\exists x_{t}\in\mathcal{X}_{\rm a}\}$$

with a constant $\Delta\geq 0$. The criterion (3) requires the probability of alarms to be less than or equal to $\Delta$ throughout the attack sequence.

Based on the setting above, the attack impact evaluation problem is formulated as a stochastic optimal control problem with a temporally joint chance constraint.

Technically, the goal of this paper is to solve Problem 1. In the subsequent section, we explain its difficulty and propose a solution method.

It is well known that for standard MDPs without constraints the optimal value can be achieved by Markov policies, namely policies that depend only on the current state. This property is justified by the fact: For any history-dependent policy, there exists a Markov policy such that the probabilities marginalized with respect to time are equal to those of the history-dependent policy [30, Theorem 18.1]. In Problem 1, however, there exists a temporally joint chance constraint, which cannot be decomposed with respect to time. Hence Markov policies cannot achieve the optimal value of (4) in general, an example of which is provided in Appendix A. Thus the dimension of its search space exponentially increases with the time horizon length. Indeed, the dimension of $\Pi^{\rm h}$ is $\sum_{t\in\mathcal{T}}(|\mathcal{A}||\mathcal{X}|)^{t+1}$. This explosion of the search space makes the problem intractable.

The key idea to overcome the difficulty is to add the alarm information by augmenting the state space. We define the augmented state space and the induced augmented MDP.

The augmented state $y_{t}\in\mathcal{Y}$ represents the alarm information. The binary flag $y_{t}=1$ indicates that the alarm has been triggered before the time step $t\in\mathcal{T}$, whereas $y_{t}=0$ indicates otherwise. For the augmented MDP $\hat{\mathcal{M}}$, we denote the set of the history-dependent non-deterministic policies by $\hat{\Pi}^{\rm h}$, the canonical measurable space by $(\hat{\Omega},\hat{\mathcal{F}})$, the random variables of the state by $\hat{X}_{t}:=(X_{t},Y_{t})$, the probability measure and the expectation induced by the initial condition $(x_{0},0)$ and the policy $\hat{\pi}\in\hat{\Pi}^{\rm h}$ by $\mathbb{P}^{\hat{\pi}}$ and $\mathbb{E}^{\hat{\pi}}$, respectively.

By using the augmented information, we can rewrite the temporally joint chance constraint in (4) as an isolated chance constraint on the state at the final step. It is intuitively true that $(\lor_{t\in\mathcal{T}}X_{t}\in\mathcal{X}_{\rm a})$, the event that an alarm is triggered at some time step, is equivalent to $Y_{T}^{-1}(\{1\})$, the event that the augmented state takes the value $1$ at the final time step. This reformulation induces an equivalent problem

$$\begin{array}[]{cl}\displaystyle{\max_{\hat{\pi}\in\hat{\Pi}^{\rm h}}}&\mathbb{E}^{\hat{\pi}}\left[\sum_{t=0}^{T-1}r_{t}(X_{t},A_{t})+r_{T}(X_{T})\right]\\ {\rm s.t.}&\mathbb{P}^{\hat{\pi}}(Y_{T}=1)\leq\Delta.\end{array}$$

(7)

The most important feature of this formulation is that the chance constraint depends on the marginal distribution only for the final time step. Hence, the optimal value of (7) can be achieved by Markov policies for the augmented state space $\hat{\mathcal{X}}$. Thus, the problem (7) can be reduced to

$$\begin{array}[]{cl}\displaystyle{\max_{\hat{\pi}\in\hat{\Pi}^{\rm m}}}&\mathbb{E}^{\hat{\pi}}\left[\sum_{t=0}^{T-1}r_{t}(X_{t},A_{t})+r_{T}(X_{T})\right]\\ {\rm s.t.}&\mathbb{P}^{\hat{\pi}}(Y_{T}=1)\leq\Delta,\end{array}$$

(8)

where the search space of (7) is replaced with $\hat{\Pi}^{\rm m}$, the set of Markov policies for the augmented MDP $\hat{\mathcal{M}}$.

We formally justify the reformulation. We first show the following lemma.

Lemma 1 implies that the stochastic behaviors of the original MDP and the augmented MDP are identical with appropriate policies.

The following theorem is the main result of this paper.

Theorem 1 justifies the reformulation from (4) to (8). The dimension of $\hat{\Pi}^{\rm m}$ is

$$|\mathcal{A}||\hat{\mathcal{X}}||\mathcal{T}|=|\mathcal{A}||\mathcal{X}||\mathcal{Y}||\mathcal{T}|=2|\mathcal{A}||\mathcal{X}||\mathcal{T}|,$$

which is much smaller than $\sum_{t\in\mathcal{T}}(|\mathcal{A}||\mathcal{X}|)^{t+1}$, that of the history-dependent search space. Finally, note that one only has to memorize the binary information $y_{t}$ for implementation of the optimal policy.

It is known that a standard class of constrained MDPs, which the problem (8) belongs to, can be solved using linear programming [31]. The procedure is briefly explained in the following. Denote $\mathbb{P}^{\hat{\pi}}(\hat{X}_{t}=\hat{x},A_{t}=a)$ by $\rho_{t}(\hat{x},a)$ where $\hat{\pi}$ is omitted from the notation. The objective function can be rewritten by

$$\begin{array}[]{l}\mathbb{E}^{\hat{\pi}}\left[\sum_{t=0}^{T-1}r_{t}(X_{t},A_{t})+r_{T}(X_{T})\right]\\ =\sum_{t=0}^{T-1}\sum_{\hat{x}\in\hat{\mathcal{X}},a\in\mathcal{A}}\hat{r}_{t}(\hat{x},a)\rho_{t}(\hat{x},a)+\sum_{\hat{x}\in\hat{\mathcal{X}}}\hat{r}_{T}(\hat{x})\rho_{T}(\hat{x}).\end{array}$$

The left-hand side of the constraint can be rewritten by

$$\mathbb{P}^{\hat{\pi}}(Y_{T}=1)=\mathbb{E}^{\hat{\pi}}\left[\delta_{y=1}(\hat{X}_{T})\right]=\sum_{\hat{x}\in\hat{\mathcal{X}}}\delta_{y=1}(\hat{x})\rho_{T}(\hat{x})$$

where $\delta_{y=1}(\hat{x})$ for $\hat{x}=(x,y)$ takes $1$ if $y=1$ and $0$ otherwise. Moreover, the function $\rho_{t}(\hat{x},a)$ satisfy

$$\left\{\begin{array}[]{l}\displaystyle{\sum_{a\in\mathcal{A}}\rho_{t}(\hat{x},a)=\sum_{\bar{x}\in\hat{\mathcal{X}},a\in\mathcal{A}}\hat{P}(\hat{x}|\bar{x},a)\rho_{t-1}(\bar{x},a),\ 1\leq t\leq T-1,}\\ \rho_{0}(\hat{x},a)=\delta_{x=x_{0}}(\hat{x}),\\ \rho_{T}(\hat{x})=\sum_{\bar{x}\in\hat{\mathcal{X}},a\in\mathcal{A}}\hat{P}(\hat{x}|\bar{x},a)\rho_{T-1}(\bar{x},a),\\ 0\leq\rho_{t}(\hat{x},a)\leq 1,\quad\forall\hat{x}\in\hat{\mathcal{X}},\forall a\in\mathcal{A},t=0,\ldots,T-1,\\ 0\leq\rho_{t}(\hat{x})\leq 1,\quad\forall\hat{x}\in\hat{\mathcal{X}}\end{array}\right.$$

(12)

where $\delta_{x=x_{0}}(\hat{x})$ for $\hat{x}=(x,y)$ takes $1$ if $x=x_{0}$ and $0$ otherwise. Conversely, for any functions that satisfy (12), there exists a policy $\hat{\pi}\in\hat{\Pi}^{\rm m}$ such that $\mathbb{P}^{\hat{\pi}}(\hat{X}_{t}=x,A_{t}=a)=\rho_{t}(\hat{x},a)$. Such a policy can specifically be constructed by

$$\textstyle{\hat{\pi}^{\rm m}_{t}(a|\hat{x})=\rho_{t}(\hat{x},a)/\sum_{\bar{a}\in\mathcal{A}}\rho_{t}(\hat{x},\bar{a})}$$

(13)

when the denominator is nonzero, otherwise $\hat{\pi}^{\rm m}_{t}(a|\hat{x})$ can be arbitrary. Therefore $\rho_{t}(\hat{x},a)$ can be used as the decision variables of the problem (8) instead of the policy. It should be emphasized that all the functions are linear with respect to $\rho_{t}(\hat{x},a)$.

The linear programming formulation is given as follows:

$$\begin{array}[]{cl}\displaystyle{\max_{\rho}}&\displaystyle{\sum_{t=0}^{T-1}\sum_{\hat{x}\in\hat{\mathcal{X}},a\in\mathcal{A}}\hat{r}_{t}(\hat{x},a)\rho_{t}(\hat{x},a)+\sum_{\hat{x}\in\hat{\mathcal{X}}}\hat{r}_{T}(\hat{x})\rho_{T}(\hat{x})}\\ {\rm s.t.}&\displaystyle{\sum_{\hat{x}\in\hat{\mathcal{X}}}\delta_{y=1}(\hat{x})\rho_{T}(\hat{x})\leq\Delta}\ {\rm and}\ \eqref{eq:meas_cond},\end{array}$$

(14)

which can readily be solved by standard solvers.

The solution to Problem 1 is summarized as follows:

1. 1.

   Given the optimization problem (4), consider the state space augmentation given by Definition 1.

2. 2.

   Using the augmented MDP, formulate the linear programming in (14).

3. 3.

   The optimal value of (14) is equal to that of (4). The optimal policy is obtained through (10) and (13).