Partial Adversarial Behavior Deception in Security Games

1 Introduction

In many real-world security domains, security agencies are generally uncertain about human attackers' decision making. Therefore, recent research in security games has focused on developing different behavior models of attackers, leveraging historical attack data [Yang et al., 2011; Nguyen et al., 2013; Kar et al., 2015; Sinha et al., 2016]. For example, in wildlife protection, rangers collect poaching signs during their patrols and use such data to learn behavior of poachers. The trained model is then used to generate an optimal defense strategy.

However, since the defender relies on historical attack data, the generated defense strategy is vulnerable to manipulative attacks. The attacker manipulation can influence the learning outcome, leading to ineffective defense strategies. We study the attacker behavior deception in Stackelberg security games (SSGs), a well-known class of games which has been widely applied in security domains [Tambe, 2011]. We aim at characterizing the attacker's deception strategy and analyzing the consequent benefit of the attacker and loss of the defender.

Specifically, we consider the scenario in which there are multiple attackers with different behavior. Among these attackers, there is a rational attacker who intends to play deceptively to mislead the defender. The other attackers always respond honestly. The defender models the whole population of attackers as one adversary and attempts to learn an adversary behavior model based on historical attack data. Previous work in wildlife protection has followed this single-behaviormodel approach to predict the behavior of poachers [Fang et al., 2016; Kar et al., 2017]. Our hypothesis is that even if only one of the attackers is deceptive, then this attacker can cause a great harm to the defender by employing deception.

To test our hypothesis, we propose a new model, partial behavior deception model, in which all attackers have the same payoff but may behave differently. The defender knows the attacker payoffs but is uncertain about their behavior. In the learning phase, the defender collects attack data and trains an attacker behavior model accordingly. In the planning phase, the defender determines an optimal defense strategy to play based on the learning outcome. While the non-deceptive attackers play honestly in both phases, the rational deceptive attacker intentionally modifies its attack strategy in the learning phase to maximize its gain in the planning phase. The deceptive attacker has no control over attacks by other attackers.

Our second contribution is a new scalable algorithm to solve the problem of finding an optimal strategy of the deceptive attacker in the learning phase, called GAMBO (Gradientbased method for Attacker Manipulation of BehaviOr). This computational problem is a tri-level optimization (that is, three levels of nested optimization) as well as non-convex. We employ a projected gradient-based method to solve this optimization. To enable this gradient-based method, we provide a novel dependent differentiation technique by exploiting the uniqueness of the optimal defense strategy and making use of the implicit function theorem.

Finally, we conduct extensive experiments to evaluate the impact of the attacker behavior deception. We show that even though the deceptive attacker can only influence a portion of the attacks in the training phase, the attacker's manipulation substantially changes the learning outcome of the defender. Eventually, it leads to a significant benefit for the deceptive attacker and loss for the defender in the planning phase.

2 RelatedWork

Attacker behavior learning in security games. Learning bounded rational attacker behavior is an important line of research in security games in which various behavior models of the attacker such as Quantal Response, etc. [Yang et al., 2011; Nguyen et al., 2013; Sinha et al., 2016; Kar et al., 2017] have been explored. The behavior learning outcomes are then used to generate a defender strategy, which is vulnerable to attacker manipulation. Our work is orthogonal to work on learning about a rational attacker [Blum et al., 2014] or a rational attacker with multiple resources [Korzhyk et al., 2011].

Deception in security games. There are several works studying deception in security [Carroll and Grosu, 2011; Hor´ak et al., 2017]. A majority of previous work in SSGs, in particular, investigates deception on the defender side [Guo et al., 2017; Rabinovich et al., 2015; Xu et al., 2015; Zhuang et al., 2010]. That is, the defender exploits the information asymmetry to fool the attacker. Recently, some research has started to study attacker deception in SSGs [Gan et al., 2019a; Nguyen and Xu, 2019; Nguyen et al., 2019] or on the follower side in general Stackelberg games [Gan et al., 2019b]. These existing work mainly focuses on the scenario the defender is uncertain about the attacker's payoff while the attacker is known to be perfectly rational. In contrast, in our setup, there are multiple attackers whose attack behavior is unknown while the attacker's payoff is known. Also, only the single rational attacker is deceptive.

Adversarial machine learning (ML). Adversarial ML has received lot of attention in the ML community [Biggio and Roli, 2018; Huang et al., 2011; Lowd and Meek, 2005; Madry et al., 2017]. The attacker behavior deception in our study can be considered as a causative attack in adversarial ML. In adversarial ML, prediction accuracy is the main measure to evaluate attacks against ML algorithms, whereas, in our setting the goal of both players is to maximize their utility, taking into account the learning outcome of the defender.

Decision-focused learning. Our work is also related to work on decision-focused learning, where ML models are trained jointly with optimization algorithms to obtain highquality decisions [Donti et al., 2017; Wilder et al., 2019]. Indeed, our use of implicit function theorem is inspired by the application of this theorem in decision-focused learning, but our novelty is in performing dependent differentiation of a binary search approach to solve an optimization.

3 Background

Stackelberg security games (SSGs). In SSGs [Tambe, 2011], a defender attempts to protect a set of T targets {1, 2, . . . , T} from an attacker. The defender has a limited number of security resources (K < T) to allocate over these targets. A pure strategy of the defender is an allocation of these security resources to K targets. A mixed strategy of the defender is a probability distribution over all of his pure strategies. In this work, we consider the no-schedulingconstraint scenario in which each mixed strategy of the defender can be equivalently represented as a marginal coverage probability vector, denoted by x = {x1, x2, . . . , xT } where xi ∈ [0, 1] is the coverage probability the defender protects target i and ∑i xi ≤ K. In the Stackelberg setting, the attacker is aware of the defender's mixed strategy and chooses one of the targets to attack accordingly.

When the attacker attacks a target i, if the defender is not protecting i, then the attacker obtains a reward of Ra i while the defender receives a penalty of P d i . Conversely, if the defender is protecting i, then the attacker has a penalty of P a i < Ra i and the defender gets a reward of Rd i > P d i . Given x, the expected utility of the defender and attacker for an attack on target i is formulated as follows:

Quantal Response model (QR). QR is a well known model used to model the attacker's behavior in SSGs [McFadden and others, 1973; McKelvey and Palfrey, 1995; Yang et al., 2011]. Essentially, QR predicts the probability the attacker will attack each target i, which is formulated as follows:

Intuitively, the higher expected utility of a target is, the higher probability the attacker will attack that target. The parameter λ governs the attacker's rationality. In particular, when λ = 0, the attacker is predicted to attack each target uniformly at random. When λ = +∞, the attacker is perfectly rational (i.e., attacks a target with the highest expected utility).

Implicit Function Theorem. We state this theorem informally [Krantz and Parks, 2012; Rudin, 1986]: given x∈Rn , y ∈ Rm, consider m equations f1(x, y) = . . . = fm(x, y) = 0 at a fixed x=a, y=b. Then, under some mild conditions, there exists a function g such that g(x) = y, in a ball B around (a, b), and ∇g(x) = -(Ay(x, g(x)))-1Ax(x, g(x)) in ball B where [Ax(x, g(x))Ay(x, g(x))] is the Jacobian of f =[f1, . . . , fm] evaluated at (x, g(x)).

Recently, a few papers have used the implicit function theorem on KKT conditions of optimization problems to obtain derivative of the optimal solution with respect to input parameters [Wilder et al., 2019]. For example, consider the following convex optimization problem which depends on some parameter θ: minx f(x, θ) subject to Ax ≤ b. The implicit function theorem applied on the KKT conditions gives:

Hence, the derivative dx dθ can be computed, given the closed form of the optimal decision x as a function of θ is not known.

4 Partial Behavior DeceptionModel

In our game model, the attackers have the same payoffs but different attack behavior arising from different rationality levels. The defender knows the attacker payoffs but is uncertain about the attackers' behavior. Thus, the defender typically learns a single behavior model of the whole attacker population based on historical attack data. This is the prevalent approach in real-world domains such as wildlife protection since park rangers mostly cannot distinguish poaching signs from different poachers [Kar et al., 2017]. We consider the setting in which the defender adopts QR to model the attacker behavior. The overall problem of the defender has two phases: learning and planning. In the learning phase, the defender optimizes the QR parameter based on the training attack dataset, formulated as follows:

where D is the training set and L(λ,D) is the log-likelihood function. In particular, D can be compactly represented as {xm, {zm i }Ti=1 }Mm=1 in which M is the number of defense strategies and zm i is the number of times target i is attacked with respect to the defender's mixed strategy xm.

In the planning phase, the defender computes a strategy x∗ that maximizes the defender's expected utility against a QR attacker with this λ∗ , which is the result of:

While the defender relies on a single behavior model, some among the attackers can change their attack strategy in the learning phase to benefit in the planning phase. In particular, we expect only a perfectly rational attackers to exhibit such clever deceptive behavior. Hence, we focus on the deception situation in which there is a rational deceptive attacker (in addition to other sub-rational and non-deceptive attackers) who can perturb a fixed fraction of the training attack set. The fixed fraction enforces a natural constraint on the limited amount of deception that the deceptive attacker can do.

Deception mathematical framework. For each strategy, xm, in the training set D, we denote by nmi the number of attacks from non-deceptive attackers at target i against xm. The total number of attacks against xm of these non-deceptive attackers is ∑i nmi . We assume the deceptive attacker can attack at most f(∑i nmi ) attacks against xm where f is the attack ratio of the deceptive attacker to the non-deceptive attackers. The problem of finding the best perturbation for the deceptive attacker can be formulated as follows:

which maximizes the deceptive attacker's utility in the planning phase of the defender. The variable zm i is the perturbed number of attacks at target i against the defender's strategy xm. Constraints (5-6) guarantee that the deceptive attacker can only manipulate its own attacks. Finding the best perturbation for the attacker involves three nested optimization problems, which is not straightforward to solve. In this work, we propose a new algorithm to tackle this challenge, leveraging the implicit function theorem to apply the projected gradient descent (PGD) method as described in next section.

5 GAMBO: A Behavior Deception Algorithm

Our algorithm applies the projected gradient descent (PGD) to find an optimal attacker perturbation {zm i } given the constraint that the deceptive attacker can only manipulate its own attacks. Since zm i is discrete, we relax the feasible region of these variables to be continuous. We denote by Z = {z : ∑i zm i ≤ (f + 1) ∑i nmi , ∀m and zm i ≥ nmi , ∀m, i} the relaxed region of the attacker's manipulation. Given a starting point z0 ∈ Z, PGD iteratively improves the value of z based on the gradients of the attacker's utility with respect to the current value of z. In particular, at step t + 1, given the current value zt, the new value, zt+1, is updated as follows:

where γ > 0 is the step size and Πz is the L2 projection. In particular, Πz(zt + ∇zt U a ) is defined as the feasible point closest to the gradient ascent update:

The gradient ∇zU a can be decomposed using chain rule:

The main challenge of computing ∇zU a lies in the computation of each gradient component ∂U a ∂x∗j , ∂x∗j ∂λ∗ , and ∂λ∗ ∂zm i especially when we do not have closed forms for these components. In the following sub-sections, we elaborate the challenges of computing each component and our ideas to address those challenges, in an increasing order of complexity.

5.1 Computing the Derivative dU a dx∗ = { ∂U a ∂x∗j }

In the planning phase, the rational deceptive attacker will attack the target which gives it the highest expected utility against x∗ . However, this means that U a is not a differentiable function of x∗ . We propose to approximate U a as the following differentiable function, by assuming that the deceptive attacker follows a QR model with a very large λ, denoted by ˆλ (when λ →∞, the attacker is perfectly rational):

It is now straightforward to compute the derivative ∂U a ∂x∗j .

By using Maximum Log-Likelihood Estimation (MLE), finding an optimal λ∗ with respect to the training set {zm i } can be formulated as the following optimization problem:

While it is straightforward to compute the optimal λ∗ with respect to the variable {zm i }, it is unclear how to compute the derivative ∂λ∗ ∂zm i since we do not have a closed form of

λ∗ as a function of {zm i }. Therefore, we propose to apply the implicit function theorem which can be directly applied for convex optimization problems. Note that, -L(λ,D) is a convex function (its Hessian matrix is positive semi-definite). Therefore λ∗ satisfies the following KKT conditions:

By applying the implicit function theorem, we can differentiate the solution to this linear system, which yields: ∀(m, i)

The RHSs of these equations are straightforward to compute.

Recall that x∗ is the defender's optimal strategy, obtained by maximizing the defender's expected utility with respect to the learnt λ∗ . The optimization problem is formulated as follows:

in which the objective is non-convex. In order to compute dx∗ dλ∗ , we first need to show given a λ∗ there is a unique x∗ , which is not obvious as the objective is non-convex. This is required for x∗ to be a well-defined function of λ∗ . We prove the uniqueness by analyzing the GOSAQ algorithm [Yang et al., 2012] to solve DefOPT, which is briefly explained below.

The GOSAQ Algorithm

At a high level, GOSAQ applies binary search and then variable conversion to convert the feasibility problem of binary search into a convex optimization, which can be solved exactly. The binary search idea is simple: given some lower and upper bound on the objective, say (L,U), it starts by solving the feasibility problem: does there exist a strategy, x, such that the defender's expected utility is greater than r = (L+U)/2?

If it is feasible, then binary search updates the lower bound as L = r. Otherwise, it updates the upper bound as U = r. Binary search then solves the feasibility problem again with the updated bounds. This process will continue until it reaches a stopping condition (i.e., U - L ≤ ϵ).

Observe that the feasibility problem can be solved by solving the following minimization problem (BinaryOPT):

Specifically, if the minimum of the objective in (7) is less than zero, then the corresponding optimal solution of x for (7-8) is a feasible solution of the feasibility problem in binary search. Otherwise, if it is strictly greater than zero, there does not exist a feasible x. Note that (7-8) is a non-convex optimization problem, GOSAQ then uses the variable transformation yi = eλ∗ (P a i -Ra i )xi for (7-8), resulting in the following strictly convex program (BinaryOPTTransformed):

where the objective in (9) is equivalent to the objective in (7). Constraints (10-12) correspond to constraint (8).

Proof of the Uniqueness of x∗

Based on the strict convexity of BinaryOPTTransformed, our Lemma 1 proves the uniqueness of x∗ for any given λ∗ .

Proof. The optimal solution of BinaryOPTTransformed is unique for any r, by strict convexity. Thus, there is a unique y∗ as the optimal solution of BinaryOPTTransformed for r = rmax. As the x-to-y transform is one-one, there is a corresponding unique optimal solution x∗ of BinaryOPT.

In addition, by definition of rmax, it must be the case that the objective value of BinaryOPT at x∗ is 0, which is equivalent to rmax = ∑Ti=1 qi(x∗i ; λ∗ )U d i (x∗i ). This can be checked by contradiction: assume the optimal objective value in (7) is not 0, then let it be a ̸= 0. First assume a > 0, we obtain:

which is contradiction. Next, assume a < 0, then, we obtain:

which directly contradicts the definition of rmax.

Since the optimal solution x∗ of DefOPT is unique for each λ∗ according to Lemma 1, x∗ is a well-defined function of λ∗ . Yet, we do not have a closed-form function of λ∗ for x∗ . Therefore, we propose to apply the implicit function theorem to compute dx∗ dλ∗ , as explained in next section.

Applying the Implicit Function Theorem

In order to apply the implicit function theorem to get the derivative dx∗ dλ∗ , we propose to use the KKT conditions of BinaryOPTTransformed. Note that we cannot use KKT conditions of BinaryOPT or DefOPT as these are non-convex optimizations and thus KKT conditions are not the sufficient conditions for the optimal solution of these two problems.

First we relate x∗ (the optimal solution of DefOPT) and x+ (the optimal solution of BinaryOPT) (the uniqueness of x+ follows the strict convexity of BinaryOPTTransformed). This relation is required to get the correct derivative of x∗ through the dependent x+. 1 While x∗ and x+ are dependent variables as x∗ (λ∗ ) and x+(λ∗ , r), for notation ease, we skip writing the explicit dependence in the rest of this paper.

Lemma 2. x∗ = x+ under F(x+, λ∗ , r) = 0 where:

Proof. Given λ∗ , F(x+, λ∗ , r) = 0 implies:

Since x+ is an optimal solution of BinaryOPT with respect to r, we obtain the following inequality: for all x,

Based on (13) and F(x+, λ∗, r)=0, then r is the maximum objective of DefOpt and x+ is the corresponding maximizer. Since such a maximizer is unique (Lemma 1), x+=x∗ .

Thus, dx∗ dλ∗ is same as dx+ dλ∗ under the dependence F(x+, λ∗ , r) = 0; in the sequel we refer to F(x+, λ∗ , r) using the shorthand F . Based on this dependency, we invoke the implicit function theorem to get dx+ dλ∗ as follows. We first use the KKT conditions of BinaryOPTTransformed around its optimal solution y∗ . We then replace y∗ i = eλ∗ (P a i -Ra i )x+i in these KKT conditions and apply Lemma 2 (from where we get F) to obtain the following equality system of x+:

where {µ0, .., µ2T} are dual variables. We denote by G = [F1, . . . , FT , Fµ0 , Fµ1 , . . . , FµT , FµT+1,...,, Fµ2T , F]T the LHSs of above equality constraints. All of these functions take as arguments (x+, λ∗ , r, µ). We get a system of 3T +2 equations, which allows us to invoke the implicit function theorem. The implicit function theorem states that given the function G(λ∗ , (x+, r, µ)) = 0, which is a function from 3T + 3 variables to 3T + 2 dimensional space given by the 3T + 2 equations above, we have the derivative:

1 Capturing dependence is critical to get the correct derivative. For example, ∂xy ∂x = y when y is not dependent on x, but, under the dependence y = x we have ∂xy ∂x = 2x

where M is the (3T + 2) × (3T + 2) matrix, represented as:

and X is the (3T + 2) × 1 column vector, represented as:

and all the partial derivatives are evaluated at x+, λ∗ , r, µ. The first T components of -M-1X is the derivative dx+ dλ∗ under the dependence F = 0, which is same as dx∗ dλ∗ (Lemma 2).

6 Experiments

We analyze the impact of the attacker deception on: (i) the deceptive attacker's utility benefit; (ii) the defender's utility loss; and (iii) the defender's learning outcome. For the sake of analysis, besides the rational attacker, we consider the presence of a boundedly rational (non-deceptive) attacker whose responses follow QR with a fixed λ. We compare two scenarios: (i) Deception: the rational attacker plays deceptively-its attacks in the training phase are computed by our algorithm, GAMBO; (ii) Non-deception: the rational attacker plays non-deceptively. We use the game generator, GAMUT (http://gamut.stanford/edu) to generate player payoffs.

In creating the training dataset, for each game, we generate M = 5 different defense strategies uniformly at random. For each generated strategy xm, we sample 50 attacks (i.e., ∑i nmi = 50) for the boundedly rational attacker with respect to its λ. We plot the experiment results in three cases (the xaxis in the plotted figures): (i) varying the λ of the boundedly rational attacker; (ii) varying the percentage of deceptive attacks ( f f+1 ); and (iii) varying resource-target ratio ( KT ). Each data point is averaged over more than 3000 game instances.

6.1 Evaluation on Utility of Players

In the following, we highlight the results of 40-target games. Figure 1 illustrates our evaluation on the utility of the rational (deceptive) attacker and the defender. Note that the defender's utility is computed as an expectation over the deceptive and non-deceptive attackers. Figure 1 shows that the rational attacker obtains a significantly higher expected utility on average when it plays deceptively compared to when it Attacker avg. utility Attacker avg. utility

8

6

4

2

Deception

Non-Deception

0

2

4

6

8

10

Non-dec Lambda

• (a) Vary λ of non-dec. attacker

8

6

4

2

Deception

Non-Deception

0.1 0.3 0.5 0.7 0.9

Dec. Attack Percentage

• (c) Vary % of dec. attacks
• (e) Vary resource-target ratio

1

0

-1

-2

-3

-4

Deception

Non-Deception

0

2

4

6

8

10

Non-dec Lambda

(b) Vary λ of non-dec. attacker

Deception

Non-Deception

0.1 0.3 0.5 0.7 0.9

Dec. Attack Percentage

• (d) Vary % of dec. attacks

4

2

0

-2

-4

Deception

Non-Deception

0.1 0.2 0.3 0.4 0.5 0.6

Resource ratio

• (f) Vary resource-target ratio

Figure 1: Evaluation on the players' utility

plays honestly (Deception versus Non-Deception). Conversely, the defender receives a significantly lower utility.

In Figures 1(a) and 1(b), the attacker's utility is roughly a decreasing convex function while the defender's utility is an increasing concave function of the QR's λ of the nondeceptive attacker. When this λ is close to zero, the nondeceptive attacker becomes less strategic and thus has less impact on the learning outcome, reflecting increased chance for successful deception of the rational attacker.

In Figures 1(c) and 1(d), in Deception, the utility of the rational attacker increases quickly while the utility of the defender decreases quickly as the percentage of deceptive attacks increases. The increase in the attack percentage reflects the growth in options for deception, leading to increased benefit of the rational attacker for misleading the defender.

In Figures 1(e) and 1(f), the average utility of players is roughly a linearly function (decreasing for the attacker and increasing for the defender) of the resource-target ratio. This makes sense as the players' expected utility at each target is a linearly function (also decreasing for the attacker and increasing for the defender) of the defender's coverage probability.

6.2 Evaluation on Learning Outcomes

Figure 2 shows the learning outcome (i.e., the learnt λ∗ ) of the defender. When the rational attacker plays honestly, the learnt λ∗ gradually increases when λ of the non-deceptive attacker or the percentage of attacks by the rational attacker

Defender avg. utility

Defender avg. utility

Defender avg. utility

0

-1

-2

-3

-4

• (a) Vary λ of non-dec. attacker
• (b) Vary % of dec. attacks

Figure 2: Evaluation on the learnt λ∗ of the defender

20 Targets

40 Targets

60 Targets

0

2

4

6

8 10

60

40

20

0

Non-dec Lambda

• (a) Vary λ of non-dec. attacker

increases. Conversely, by playing deceptively, the rational attacker could influence the learning outcome towards a very small learnt λ∗ . Finally, our results show that the learnt λ∗ is roughly constant when varying the resource-target ratio, showing that this factor does not impact the learning outcome (we do not plot these results due to limited space).

6.3 Runtime Performance

Finally, the runtime performance of our algorithm, GAMBO, is shown in Figure 3. The y-axis is the runtime in seconds on average. Figure 3(a) shows that the runtime of GAMBO increases gradually when the λ of the non-deceptive attacker increases and then becomes roughly constant when this λ reaches the value of 2. This shows that when the non-deceptive attacker is nearly non-strategic (its λ is close to zero), GAMBO can quickly find a deception strategy for the rational attacker. In Figure 3(b), the peak of GAMBO's runtime is at the attack percentage of 0.5, reflecting that the time complexity of GAMBO is highest when the deceptive and non-deceptive attackers contribute equally to the attack dataset. Finally, GAMBO can solve large games (i.e., 200-target games) in approximately 10 minutes (we do not plot these results due to limited space).

7 Summary

This paper studied the problem of the attacker deception in security games, where the defender relies on historical attack data to learn the attackers' behavior. We proposed a novel partial behavior deception model and introduced a new scalable algorithm, GAMBO, to compute an optimal deception strategy of the deceptive attacker. Our algorithm provided a novel usage of the implicit function theorem to solve a tri-level optimization problem. Our thorough experiments reveal a significant benefit for the deceptive attacker while the defender suffers a significant loss in utility.

Runtime (secs)