Countering Attacker Data Manipulation in Security Games

Abstract

Defending against attackers with unknown behavior is an important area of research in security games. A well-established approach is to utilize historical attack data to create a behavioral model of the attacker. However, this presents a vulnerability: a clever attacker may change its own behavior during learning, leading to an inaccurate model and ineffective defender strategies. In this paper, we investigate how a wary defender can defend against such deceptive attacker. We provide four main contributions. First, we develop a new technique to estimate attacker true behavior despite data manipulation by the clever adversary. Second, we extend this technique to be viable even when the defender has access to a minimal amount of historical data. Third, we utilize a maximin approach to optimize the defender’s strategy against the worst-case within the estimate uncertainty. Finally, we demonstrate the effectiveness of our counter-deception methods by performing extensive experiments, showing clear gain for the defender and loss for the deceptive attacker.

A Appendix

1.1 A.1 Proof of Theorem 1

In order to prove this theorem, we introduce a series of Lemmas (3–6). For the sake of analysis, we denote by:

$$\begin{aligned}&y^m_i = \frac{z^m_i}{\sum _j z^m_j}&c^m = \frac{1}{\sum _j z^m_j} \end{aligned}$$

Intuitively, $y^m_i$ is the empirical attack distribution estimated from the perturbed training data $\mathcal {\hat{D}} = \{x^m_i, z^m_i\}$ and $c^m$ is the normalization term. Also, $\{y^m_i, c^m\}$ and $\{z^m_i\}$ are interchangeable. That is, given $\{y^m_i, c^m\}$, we can determine $z^m_i = \frac{y^m_i}{c^m}$. We first present the Lemma 1 which determines the deception capability of the deceptive attacker:

Lemma 3

Given the true behavior $\lambda ^{\text {true}}$ of the non-deceptive attackers and the attack ratio f, the deceptive space for the deceptive attacker is specified as follows:

$$\begin{aligned}&\sum \nolimits _m \frac{1}{c^m} \left[ \sum \nolimits _i y^m_i U^a_i(x^m_i) - U^a(\mathbf {x}^m,\lambda )\right] =0 \end{aligned}$$

(14)

$$\begin{aligned}&\frac{y^m_i }{c^m} \ge n^m_i,\forall m, i \end{aligned}$$

(15)

$$\begin{aligned}&c^m \ge \frac{1}{(f+1) \sum _i n^m_i},\forall m \end{aligned}$$

(16)

$$\begin{aligned}&y^m_i\in [0,1], \sum \nolimits _i y^m_i = 1,\forall m, i \end{aligned}$$

(17)

That is, any deceptive $\lambda$ that the defender learns has to be a part of a feasible solution $(\lambda , y^m_i, c^m)$ of the system (14–17). Conversely, given any feasible $(\lambda , y^m_i, c^m)$ satisfying (14–17), the deceptive attacker can make the defender learn $\lambda$ by inducing the following perturbed data:

$$\begin{aligned}&z^m_i = \frac{y^m_i}{c^m} \end{aligned}$$

Proof

Equation (14) is simply the $\mathtt {KKT}$ condition presented in the previous section with $y^m_i$ and $c^m$ substituted in. Similarly, the constraints (15–16) correspond to the constraints for the deception capability of the deceptive attacker in (5–6). Finally, the constraint (17) follows from the definition of $y^m_i$ and ensures that $\sum _i\frac{z^m_i}{\sum _j z^m_j} = 1$ and $\frac{z^m_i}{\sum _j z^m_j} \le 1$.

According to Lemma 3, we now can prove Theorem 1 based on the characterization of the feasible solution domain of $\lambda$ for the system (14–17). We denote by:

$$\begin{aligned}&\mathcal {F}(\lambda , \{y^m_i, c^m\}) = \sum _m \frac{1}{c^m} \left[ \sum _i y^m_i U^a_i(x^m_i) - U^a(\mathbf {x}^m,\lambda )\right] \end{aligned}$$

the LHS of (14). In addition, we denote by $\mathbf {S} = \{(y^m_i, c^m)$ : conditions (15–17) are satisfied} the feasible region of $(y^m_i, c^m)$ which satisfy the conditions (15–17). In the following, we provide Lemmas 4 and 5 which specify the range of $\mathcal {F}$ as a function of $\lambda$. Essentially, if the value of $\mathcal {F}$ contains the point zero, then $\lambda$ is a feasible solution of the system (14–17). We will use this property to characterize the feasible region of $\lambda$.

Lemma 4

Assume that, WLOG, $U^a_1(x^m_1) \le U^a_2(x^m_2)\le \dots \le U^a_T(x^m_T)$ for all m. Given a $\lambda$, the optimal solution to

$$\begin{aligned}&\mathcal {F}^{\max }(\lambda ) = \max _{\{y^m_i, c^m\}\in \mathbf {S}} \mathcal {F}(\lambda , \{y^m_i, c^m\}) \end{aligned}$$

(18)

is determined as follows:

$$\begin{aligned}&c^m = \frac{1}{(f+1) \sum _i n^m_i}\end{aligned}$$

(19)

$$\begin{aligned}&y^m_i =n^m_i c^m, \text { when } i < T\end{aligned}$$

(20)

$$\begin{aligned}&y^m_i = 1 - c^m\sum _{i = 1}^{T-1} n^m_i \text { when }i = T \end{aligned}$$

(21)

Proof

First, $\mathcal {F}(\lambda , \{y^m_i, c^m\})$ can be reformulated as:

$$\begin{aligned}&\sum _m \frac{1}{c^m}\left[ U^a_T(x^m_T) + \sum _{i = 1}^{T-1} y^m_i[U^a_i(x^m_i) - U^a_T(x^m_T)] - U^a(\mathbf {x}^m,\lambda )\right] \end{aligned}$$

Under our assumption that $U^a_1(x^m_1) \le U^a_2(x^m_2)\le \dots \le U^a_T(x^m_T)$, we know that $[U^a_i(x^m_i) - U^a_T(x^m_T)]$ is a strictly non-positive term for all i. Thus, maximizing $\mathcal {F}$ involves minimizing $y^m_i$ when $i < T$. From constraint (15), the minimum $y^m_i$ for all i is $n^m_i c^m$. This gives us $y^m_i = n^m_i c^m$ when $i < T$. From constraint (17), we know that this leaves us with $y^m_i = 1 - c^m\sum _{i = 1}^{T-1} n^m_i$ when $i=T$.

Finally, given this specification of $\{y^m_i\}$, the optimization problem (18) is reduced to:

$$\begin{aligned} \max _{c^m}&\sum _m \sum _{i<T} n^m_i [U^a_i(x^m_i) - U^a_{T}(x^m_T)] + \frac{U^a_{T}(x^m_T) - U^a(\mathbf {x}^m,\lambda )}{c^m} \\&\text {s.t. }c^m \ge \frac{1}{(f+1) \sum _i n^m_i} \text { and } c^m\le \frac{1}{\sum _i n^m_i},\forall m \end{aligned}$$

in which the objective function comprises of two terms: the first term does not depend on $\{c^m\}$ and the second term is a decreasing function of $c^m$ (since $U^a_{T}(x^m_T) - U^a(\mathbf {x}^m,\lambda ) > 0$). Therefore, it is maximized when $c^m$ is minimized, which is $c^m = \frac{1}{(f+1) \sum _i n^m_i}$, concluding the proof.

Lemma 5

Assume that, WLOG, $U^a_1(x^m_1) \le U^a_2(x^m_2)\le \dots \le U^a_T(x^m_T)$ for all m. Given a $\lambda$, the optimal solution to

$$\begin{aligned}&\mathcal {F}^{\min }(\lambda ) = \min _{\{y^m_i, c^m\}\in \mathbf {S}} \mathcal {F}(\lambda , \{y^m_i, c^m\}) \end{aligned}$$

(22)

is determined as follows:

$$\begin{aligned}&c^m = \frac{1}{(f+1) \sum _i n^m_i}\end{aligned}$$

(23)

$$\begin{aligned}&y^m_i = n^m_i c^m, \text { when } i > 1\end{aligned}$$

(24)

$$\begin{aligned}&y^m_i = 1 - c^m\sum _{i = 2}^{T} n^m_i \text { when }i = 1 \end{aligned}$$

(25)

The proof of Lemma 5 is similar. Finally, using Lemmas (4–5) and the approximation in Eq. 7, we obtain:

$$\begin{aligned} \mathcal {F}^{\max }(\lambda )&= \sum _m\left[ \sum _j n^m_j\right] \Bigg [U^a(\mathbf {x}^m,\lambda ^{\text {true}}) \nonumber \\&+ f U^a_{T}(x^m_T) - (f + 1)U^a(\mathbf {x}^m,\lambda ) \Bigg ]\end{aligned}$$

(26)

$$\begin{aligned} \mathcal {F}^{\min }(\lambda )&= \sum _m\left[ \sum _j n^m_j\right] \Bigg [U^a(\mathbf {x}^m,\lambda ^{\text {true}}) \nonumber \\&+ f U^a_{1}(x^m_1) - (f + 1)U^a(\mathbf {x}^m,\lambda ) \Bigg ] \end{aligned}$$

(27)

Observe that, given $\lambda$, $\mathcal {F}(\lambda , \cdot )$ is continuous in $\{y^m_i, c^m\}$. Therefore, given a $\lambda '$, if $\mathcal {F}^{\max }(\lambda ') \ge 0\ge \mathcal {F}^{\min }(\lambda ')$, there must exist $\{y^m_i, c^m\} \in \mathbf {S}$ such that $\mathcal {F}(\lambda ', \{y^m_i, c^m\}) = 0$. In other words, $\lambda '$ is a part of a feasible solution for (14–17). Conversely, if $\mathcal {F}^{\max }(\lambda ') < 0$ or $\mathcal {F}^{\min }(\lambda ') > 0$, it means $\lambda '$ is not feasible for (14–17). Moreover, using Observation 1, we can infer that both $\mathcal {F}^{\max }$ and $\mathcal {F}^{\min }$ are continuous and decreasing in $\lambda$. We obtain Lemma 6 which states that feasible solutions of (14–17) form an interval.

Lemma 6

Let us assume $\lambda _1 < \lambda _2$ are two feasible solutions of (14–17). Then any $\lambda \in [\lambda _1,\lambda _2]$ is also a feasible solution of the system.

Proof

Since $\lambda _1$ and $\lambda _2$ are feasible solutions of (14–17), we obtain the inequalities:

$$\begin{aligned}&\mathcal {F}^{\max }(\lambda _1) \ge 0\ge \mathcal {F}^{\min }(\lambda _1)\\&\mathcal {F}^{\min }(\lambda _2) \ge 0\ge \mathcal {F}^{\min }(\lambda _2) \end{aligned}$$

For any $\lambda \in [\lambda _1,\lambda _2]$, since $\mathcal {F}^{\max }$ and $\mathcal {F}^{\min }$ are decreasing functions in $\lambda$, the following inequality holds true:

$$\begin{aligned}&\mathcal {F}^{\max }(\lambda )\ge \mathcal {F}^{\max }(\lambda _2) \ge 0\ge \mathcal {F}^{\min }(\lambda _1)\ge \mathcal {F}^{\min }(\lambda ) \end{aligned}$$

which implies that $\lambda$ is also a feasible solution for (14–17), concluding the proof.

Lemma 7 specifies the interval $[\lambda ^{\text {learnt}}_{\min },\lambda ^{\text {learnt}}_{\max }]$ of feasible $\lambda$ values for (14–17).

Lemma 7

There exist $\lambda ^{\text {learnt}}_{\max } \ge \lambda ^{\text {learnt}}_{\min }$ such that:

$$\begin{aligned} \mathcal {F}^{\max }(\lambda ^{\text {learnt}}_{\max }) = \mathcal {F}^{\min }(\lambda ^{\text {learnt}}_{\min }) = 0, \end{aligned}$$

which means $\lambda ^{\text {learnt}}_{\min }$ and $\lambda ^{\text {learnt}}_{\max }$ are feasible solutions for (14–17) and any $\lambda \notin [\lambda ^{\text {learnt}}_{\min },\lambda ^{\text {learnt}}_{\max }]$ is not a feasible solution for (14–17).

Proof

As noted before, $\mathcal {F}^{\max }(\lambda )$ is a continuous and decreasing function in $\lambda$. On the other hand, we have:

$$\begin{aligned} \mathcal {F}^{\max }(\lambda = +\infty )&=\sum _m\left[ \sum _j n^m_j\right] \Bigg [U^a(\mathbf {x}^m,\lambda ^{\text {true}}) - U^a_{T}(x^m_T) \Bigg ]\le 0\\ \mathcal {F}^{\max }(\lambda = -\infty )&= \sum _m\left[ \sum _j n^m_j\right] \Bigg [U^a(\mathbf {x}^m,\lambda ^{\text {true}})\\&+ f U^a_{T}(x^m_T) - (f + 1)U^a_{1}(x^m_1)) \Bigg ]\ge 0 \end{aligned}$$

for all $\lambda ^{\text {true}}$ since $U^a(\mathbf {x}^m,\lambda ^{\text {true}} = +\infty ) = U^a_T(x^m_T)$ and $U^a(\mathbf {x}^m,\lambda ^{\text {true}} = -\infty ) = U^a_1(x^m_1)$ is the highest and lowest expected utilities for the attacker among all targets , respectively, and by Observation 1, $U^a(\mathbf {x}^m,\lambda ^{\text {true}})$ is increasing in $\lambda ^{\text {true}}$. Since $\mathcal {F}^{\max }(\lambda )$ is continuous, there must exist a value of $\lambda ^{\text {learnt}}_{\max } \in (-\infty ,+\infty )$ such that $\mathcal {F}^{\max }(\lambda ^{\text {learnt}}_{\max }) = 0$. The proof for $\lambda ^{\text {learnt}}_{\min }$ is similar.

Finally, for any $\lambda < \lambda ^{\text {learnt}}_{\min }$, we have $\mathcal {F}^{\min }(\lambda ) > \mathcal {F}^{\min }(\lambda ^{\text {learnt}}_{\min }) = 0$ since $\mathcal {F}^{\min }$ is decreasing in $\lambda$. Similarly, for any $\lambda > \lambda ^{\text {learnt}}_{\max }$, we have $\mathcal {F}^{\max }(\lambda ) < \mathcal {F}^{\max }(\lambda ^{\text {learnt}}_{\max }) = 0$. Both imply that $\lambda$ is not feasible, concluding our proof.

By combining Lemmas 3, 6, and 7, we obtain Theorem 1.

Proof of Corollary 1

Proof

Corollary 1 is deduced based on the monotonicity property of the attacker’s utility (Observation 1). When $\lambda ^{\text {true}}_1 \le \lambda ^{\text {true}}_2$, we have $U^a(\mathbf {x}^m;\lambda ^{\text {true}}_1)\le U^a(\mathbf {x}^m;\lambda ^{\text {true}}_2)$ for all m. Based on the relationship between $U^a(\mathbf {x}^m;\lambda ^{\text {true}})$ and $U^a(\mathbf {x}^m;\lambda ^{\text {learnt}}_{\max })$ presented in Theorem 1, we readily obtain $\lambda ^{\text {learnt}}_{\max ,1}\le \lambda ^{\text {learnt}}_{\max ,2}$. Similarly, we have: $\lambda ^{\text {learnt}}_{\min ,1}\le \lambda ^{\text {learnt}}_{\min ,2}$.

Proof of Corollary 2

Proof

We first prove (8). Let’s consider the true behavior parameters $\lambda ^{\text {true}}_1\le \lambda ^{\text {true}}_2$. Based on Corollary 1, the corresponding optimal deception solutions have to belong to the deception ranges: $\mathtt {DecAlter}(\lambda ^{\text {true}}_1)\in [\lambda ^{\text {learnt}}_{\min ,1},\lambda ^{\text {learnt}}_{\max ,1}]$ and $\mathtt {DecAlter}(\lambda ^{\text {true}}_2)\in [\lambda ^{\text {learnt}}_{\min ,2},\lambda ^{\text {learnt}}_{\max ,2}]$ where $\lambda ^{\text {learnt}}_{\min ,1}\le \lambda ^{\text {learnt}}_{\min ,2}$ and $\lambda ^{\text {learnt}}_{\max ,1}\le \lambda ^{\text {learnt}}_{\max ,2}$. We have two cases:

The first case is when the deception ranges do not overlap, i.e., ($\lambda ^1_{\max } < \lambda ^2_{\min }$). In this case, it is apparent that $\mathtt {DecAlter}(\lambda ^{\text {true}}_1) < \mathtt {DecAlter}(\lambda ^{\text {true}}_2)$.

The other case is when the ranges overlap (i.e., $\lambda _1^{max} \ge \lambda _2^{min}$). If the optimal deceptive value for one or both does not belong to the overlap, i.e., $\mathtt {DecAlter}(\lambda ^{\text {true}}_1) < \lambda ^{\text {learnt}}_{\min ,2}$ and/or $\mathtt {DecAlter}(\lambda ^{\text {true}}_2) > \lambda ^{\text {learnt}}_{\max ,1}$), the result is clearly the same as in our previous case ($\mathtt {DecAlter}(\lambda ^{\text {true}}_1) < \mathtt {DecAlter}(\lambda ^{\text {true}}_2)$). On the other hand, if both values fall within the overlap, that is $\lambda ^{\text {learnt}}_{\min ,2} \le \mathtt {DecAlter}(\lambda ^{\text {true}}_1),\mathtt {DecAlter}(\lambda ^{\text {true}}_2)\le \lambda ^{\text {learnt}}_{\max ,1}$, both will take on the same value ($\mathtt {DecAlter}(\lambda ^{\text {true}}_1) = \mathtt {DecAlter}(\lambda ^{\text {true}}_2)$). This is true because both deceptive values $\mathtt {DecAlter}(\lambda ^{\text {true}}_1)$ and $\mathtt {DecAlter}(\lambda ^{\text {true}}_2)$ are being optimized to maximize the same objective: the utility of the deceptive attacker (as shown in $\mathtt {DecAlter}$).

Finally, (9) can be easily deduced based on (8). Let’s consider $\mathtt {DecAlter}(\lambda ^{\text {true}}_1) < \mathtt {DecAlter}(\lambda ^{\text {true}}_2)$. We can prove $\lambda ^{\text {true}}_1 < \lambda ^{\text {true}}_2$ by contradiction. That is, we assume $\lambda ^{\text {true}}_1 \ge \lambda ^{\text {true}}_2$. According to (8), it means $\mathtt {DecAlter}(\lambda ^{\text {true}}_1) \ge \mathtt {DecAlter}(\lambda ^{\text {true}}_2)$, which is a contradiction.

Proof of Corollary 3

Proof

Corollary 3 is a direct result of Corollary 2. Indeed, since $\lambda ^{\text {true}}_1 \le \lambda ^{\text {true}}\le \lambda ^{\text {true}}_2$, we obtain the inequality among optimal deception solutions $\mathtt {DecAlter}(\lambda ^{\text {true}}_1)\le \mathtt {DecAlter}(\lambda ^{\text {true}})\le \mathtt {DecAlter}(\lambda ^{\text {true}}_2)$ as a result of Corollary 2. Therefore if $\mathtt {DecAlter}(\lambda ^{\text {true}}_1) = \mathtt {DecAlter}(\lambda ^{\text {true}}_2)$, we obtain the optimal deception solution: $\mathtt {DecAlter}(\lambda ^{\text {true}}) = \mathtt {DecAlter}(\lambda ^{\text {true}}_1)$.

Proof of Lemma 1

Proof

Corollary 2 says that the deception outcome $\lambda ^{\text {learnt}} = \mathtt {DecAlter}(\lambda ^{\text {true}})$ is an increasing (not strict) function of $\lambda ^{\text {true}}$, and additionally using Corollary 3, we can say that given some deception outcome $\lambda ^{\text {learnt}}$, there exists (unknown) $\lambda ^{\text {true}}_{\min },\lambda ^{\text {true}}_{\max }$ such that any $\lambda ^{\text {true}} \in [\lambda ^{\text {true}}_{\min },\lambda ^{\text {true}}_{\max }]$ leads to the same outcome $\lambda ^{\text {learnt}} = \mathtt {DecAlter}(\lambda ^{\text {true}})$. Any $\lambda$ outside of the range $[\lambda ^{\text {true}}_{\min },\lambda ^{\text {true}}_{\max }]$ cannot lead to the deception outcome $\lambda ^{\text {learnt}}$. Corollary 2 further implies that $\lambda ^{\text {true}}_{\min }$ and $\lambda ^{\text {true}}_{\max }$ are increasing functions of $\lambda ^{\text {learnt}}$.

Proof of Lemma 2

Proof

Assume WLOG, $U^a_1(x^m_1) \le U^a_2(x^m_2)\le \dots \le U^a_T(x^m_T)$. We claim that $S(i,\lambda ^{\text {true}}) = \sum _{j=1}^i q_j(\mathbf {x}^m;\lambda ^{\text {true}})$ for $T > i \ge 1$ is decreasing (not strictly) in $\lambda ^{\text {true}}$, or in other words, the upper bound of the $i^{th}$ segment is decreasing (not strictly) for all i except $i=T$. This means that for any single fixed u value, increasing $\lambda ^{\text {true}}$ implies that $f_{\lambda ^{\text {true}}}(u)$ is also increasing (or stays same) because the upper bound of the interval that u lies in shifts downwards as $\lambda ^{\text {true}}$ increases. $f_{\lambda ^{\text {true}}}(u)$ increasing means a higher value target is chosen for attack. Thus, for fixed u, a higher $\lambda ^{\text {true}}$ implies that the empirical distribution places more (or equal) attacks on higher utility targets and hence $U^a(\mathbf {x}^m,E(u;\lambda ^{\text {true}}))$ increases (not strictly) with $\lambda ^{\text {true}}$. Finally, to prove our claim at the start of the proof, we show that the derivative of $S(i,\lambda ^{\text {true}})$ is non-positive everywhere. Indeed, its derivative is computed as follows:

$$\begin{aligned} \nonumber&\sum _{j=1}^i q_j(\mathbf {x}^m;\lambda ^{\text {true}}) U^a_j(x^m_j) - S(i,\lambda ^{\text {true}})U^a(\mathbf {x}^m;\lambda ^{\text {true}})\\&=S(i,\lambda ^{\text {true}}) \Big [ \sum _{j=1}^i \frac{q_j(\mathbf {x}^m;\lambda ^{\text {true}})}{S(i,\lambda ^{\text {true}})} U^a_j(x^m_j) - U^a(\mathbf {x}^m;\lambda ^{\text {true}}) \Big ] \end{aligned}$$

(28)

decomposing the attacker utility function $U^a(\mathbf {x}^m;\lambda ^{\text {true}})$, as follows:

$$\begin{aligned}&S(i,\lambda ^{\text {true}})\sum _{j=1}^i \frac{q_j(\mathbf {x}^m;\lambda ^{\text {true}})}{S(i,\lambda ^{\text {true}})} U^a_j(x^m_j) + \\&\Big (\sum _{j=i+1}^T q_j(\mathbf {x}^m;\lambda ^{\text {true}}) \Big )\sum _{j=i+1}^T \frac{q_j(\mathbf {x}^m;\lambda ^{\text {true}})}{\sum _{j=i+1}^T q_j(\mathbf {x}^m;\lambda ^{\text {true}})} U^a_j(x^m_j) \end{aligned}$$

As we know that $U^a_1(x^m_1) \le U^a_2(x^m_2) \ldots \le U^a_T(x^m_T)$, the following inequality holds:

$$\begin{aligned}&\sum _{j=i+1}^T \frac{q_j(\mathbf {x}^m;\lambda ^{\text {true}})}{\sum _{j=i+1}^T q_j(\mathbf {x}^m;\lambda ^{\text {true}})} U^a_j(x^m_j)&\ge U^a_i(x^m_i)\ge \sum _{j=1}^i \frac{q_j(\mathbf {x}^m;\lambda ^{\text {true}})}{S(i,\lambda ^{\text {true}})} U^a_j(x^m_j) \end{aligned}$$

Using this we get:

$$\begin{aligned}&U^a(\mathbf {x}^m;\lambda ^{\text {true}}) \ge \ \Big (S(i,\lambda ^{\text {true}}) +\sum _{j=i+1}^T q_j(\mathbf {x}^m;\lambda ^{\text {true}}) \Big )\sum _{j=1}^i \frac{q_j(\mathbf {x}^m;\lambda ^{\text {true}})}{S(i,\lambda ^{\text {true}})} U^a_j(x^m_j)\\&= 1\cdot \sum _{j=1}^i \frac{q_j(\mathbf {x}^m;\lambda ^{\text {true}})}{S(i,\lambda ^{\text {true}})} U^a_j(x^m_j) \end{aligned}$$

Using the above in the derivative Eq. 28, we get that the derivative of $S(i,\lambda ^{\text {true}})$ is non-positive, hence it is decreasing w.r.t. $\lambda$, concluding our proof.

Supplemental Experiments. First, in Fig. 4, we examine the range $[\lambda ^{\text {true}}_{\min }, \lambda ^{\text {true}}_{\max }]$ that the defender learns. Figure 4a shows that the range increases w.r.t. the percentage of attacks controlled by the deceptive attacker. This is intuitive, as more manipulation gives more power to the deceptive attacker. Figure 4b displays how this range also increases with the ground truth $\lambda ^{\text {true}}$ value of the non-deceptive attackers. As $\lambda ^{\text {true}}$ increases, the deceptive attacker produces a larger uncertainty range.

Fig. 4.

Lambda range evaluation with 20 targets

Fig. 5.

Utility evaluation with 30 targets

Lastly, Figs. 6 through 5 are for 30-target games, and each corresponds to a previously discussed 20-target figure. We observe the same trends in both cases.

Fig. 6.

Runtime and $\lambda$ evaluation with 30 targets

Experimental Details. All experiments were run on the same HPC cluster, on instances using dual E5-2690v4 processors (28 cores). Each process was allocated 16000 megabytes of RAM. Instances run Red Hat Enterprise Linux Server, version 7.8. The Matlab version used was R2018b.

All experiments used the L-Infinity norm with a value of 2 as a rejection threshold for non-deceptive attack samples. This is done to prevent outlying samples from compromising the binary search. Values between .5 and 5 for this metric were tested, along with the same value ranges for the L1 and L2 norms. This norm and value were shown to produce the best results, without drastically increasing the runtime of the algorithm.

Additionally, all experiments used a value of 0.05 as a tolerance multiplier within the binary search itself. This prevents the inherent inaccuracy of discrete attack samples from ruining binary search. For the sake of consistency, an initial random number generation seed of 1 was used across all experiments. After defender strategy generation and solving ($\mathtt {DecAlter}$), the binary search is run 10 times, each with a different random seed. The superset of all resulting ranges forms our final uncertainty set for $\lambda ^{\text {true}}$.

The trials shown in Figs. 4a, 2a, 2c, 3, 6c, 5a, 5c, and 6 were conducted using a true lambda value of 0.4 and a resource/target ratio of 0.2. Those in Figs. 4b, 2b, 2d, 6d, 5d, and 5d utilized a deceptive attack percentage of 0.3, and a resource/target ratio of 0.2. Experiments in Figs. 3 and use deceptive attack percentage of 0.1, a true lambda value of 0.4, and a resource/target ratio of 0.2.