--- title: "Partial Adversarial Behavior Deception in Security Games" authors: - "Thanh H. Nguyen" - "Arunesh Sinha" - "He He" doi: "10.24963/ijcai.2020/40" url: "https://ijcai.org/proceedings/2020/40" pdf: "https://ijcai.org/proceedings/2020/0040.pdf" venue: "Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence" year: 2020 pages: "283-289" track: "Main track" keywords: - "Agent-based and Multi-agent Systems: Algorithmic Game Theory" - "Machine Learning: Adversarial Machine Learning" - "Agent-based and Multi-agent Systems: Noncooperative Games" --- # Partial Adversarial Behavior Deception in Security Games Thanh H. Nguyen, Arunesh Sinha, He He *Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence*, pages 283-289. DOI: [10.24963/ijcai.2020/40](https://doi.org/10.24963/ijcai.2020/40) ## Abstract Learning attacker behavior is an important research topic in security games as security agencies are often uncertain about attackers' decision making. Previous work has focused on developing various behavioral models of attackers based on historical attack data. However, a clever attacker can manipulate its attacks to fail such attack-driven learning, leading to ineffective defense strategies. We study attacker behavior deception with three main contributions. First, we propose a new model, named partial behavior deception model, in which there is a deceptive attacker (among multiple attackers) who controls a portion of attacks. Our model captures real-world security scenarios such as wildlife protection in which multiple poachers are present. Second, we introduce a new scalable algorithm, GAMBO, to compute an optimal deception strategy of the deceptive attacker. Our algorithm employs the projected gradient descent and uses the implicit function theorem for the computation of gradient. Third, we conduct a comprehensive set of experiments, showing a significant benefit for the attacker and loss for the defender due to attacker deception. ## Full text ## 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 ![Image](https://ijcai.org/proceedings/2020/fulltext/40/image_000000_d3214ba9f89a8f174fdddc7a2b2e480ddcf1b326517dff9a4d392caf909c4003.png) 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 ![Image](https://ijcai.org/proceedings/2020/fulltext/40/image_000001_8b4fa52aa2d151735c06f30f4f494566a8890aab3b99c61285499c355e741ddd.png) - (a) Vary λ of non-dec. attacker - (b) Vary % of dec. attacks ![Image](https://ijcai.org/proceedings/2020/fulltext/40/image_000002_1e149b5c9886f39f5adf52fce477fb1bc7732cd06dba3a90d794325c6b0680d7.png) 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 Figure 3: Runtime performance of GAMBO ![Image](https://ijcai.org/proceedings/2020/fulltext/40/image_000003_902245f366ec1ca2b7cfc969daae4c26c9fbb2a0da44f38dced9509c437a2f9f.png) 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) ## References 1. [Biggio and Roli, 2018] Battista Biggio and Fabio Roli. Wild patterns: Ten years after the rise of adversarial ma- chine learning. Pattern Recognition, 84:317-331, 2018. 2. [Blum et al., 2014] Avrim Blum, Nika Haghtalab, and Ariel D Procaccia. Learning optimal commitment to over- come insecurity. In Neural Information Processing Sys- tems, 2014. 3. [Carroll and Grosu, 2011] Thomas E Carroll and Daniel Grosu. A game theoretic investigation of deception in network security. Security and Communication Networks, 4(10):1162-1172, 2011. 4. [Donti et al., 2017] Priya Donti, Brandon Amos, and J Zico Kolter. Task-based end-to-end model learning in stochastic optimization. In Neural Information Processing Systems, 2017. 5. [Fang et al., 2016] Fei Fang, Thanh H Nguyen, Rob Pickles, Wai Y Lam, Gopalasamy R Clements, Bo An, Amandeep Singh, Milind Tambe, and Andrew Lemieux. Deploying paws: Field optimization of the protection assistant for wildlife security. In IAAI, 2016. 6. [Gan et al., 2019a] Jiarui Gan, Qingyu Guo, Long Tran- Thanh, Bo An, and Michael Wooldridge. Manipulating a learning defender and ways to counteract. In NeurIPS, 2019. 7. [Gan et al., 2019b] Jiarui Gan, Haifeng Xu, Qingyu Guo, Long Tran-Thanh, Zinovi Rabinovich, and Michael Wooldridge. Imitative follower deception in stackelberg games. In Proceedings of the ACM EC, EC '19, 2019. 8. [Guo et al., 2017] Qingyu Guo, Bo An, Branislav Bosan- sky, and C. Kiekintveld. Comparing strategic secrecy and Stackelberg commitment in security games. In IJCAI, 2017. 9. [Horák et al., 2017] Karel Horák, Quanyan Zhu, and Branislav Bošanskỳ. Manipulating adversary's belief: A dynamic game approach to deception by design for proactive network security. In GameSec, 2017. 10. [Huang et al., 2011] Ling Huang, Anthony D Joseph, Blaine Nelson, Benjamin IP Rubinstein, and J Doug Tygar. Ad- versarial machine learning. In ACM workshop on Security and Artificial Intelligence, pages 43-58, 2011. 11. [Kar et al., 2015] Debarun Kar, Fei Fang, Francesco Delle Fave, Nicole Sintov, and Milind Tambe. A game of thrones: when human behavior models compete in repeated stackelberg security games. In AAMAS, 2015. 12. [Kar et al., 2017] Debarun Kar, Benjamin Ford, Shahrzad Gholami, Fei Fang, Andrew Plumptre, Milind Tambe, Margaret Driciru, Fred Wanyama, Aggrey Rwetsiba, Mustapha Nsubaga, et al. Cloudy with a chance of poach- ing: Adversary behavior modeling and forecasting with real-world poaching data. In AAMAS, 2017. 13. [Korzhyk et al., 2011] Dmytro Korzhyk, Vincent Conitzer, and Ronald Parr. Security games with multiple attacker resources. In IJCAI, 2011. 14. [Krantz and Parks, 2012] Steven G Krantz and Harold R Parks. The implicit function theorem: history, theory, and applications. Springer Science & Business Media, 2012. 15. [Lowd and Meek, 2005] Daniel Lowd and Christopher Meek. Adversarial learning. In SIGKDD, 2005. 16. [Madry et al., 2017] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.06083, 2017. 17. [McFadden and others, 1973] Daniel McFadden et al. Con- ditional logit analysis of qualitative choice behavior. 1973. 18. [McKelvey and Palfrey, 1995] Richard D McKelvey and Thomas R Palfrey. Quantal response equilibria for normal form games. Games and economic behavior, 10, 1995. 19. [Nguyen and Xu, 2019] Thanh Nguyen and Haifeng Xu. Im- itative attacker deception in stackelberg security games. In IJCAI, pages 528-534, 7 2019. 20. [Nguyen et al., 2013] Thanh Hong Nguyen, Rong Yang, Amos Azaria, Sarit Kraus, and Milind Tambe. Analyzing the effectiveness of adversary modeling in security games. In AAAI, 2013. 21. [Nguyen et al., 2019] Thanh H Nguyen, Yongzhao Wang, Arunesh Sinha, and Michael P Wellman. Deception in finitely repeated security games. In AAAI, 2019. 22. [Rabinovich et al., 2015] Zinovi Rabinovich, Albert Xin Jiang, Manish Jain, and Haifeng Xu. Information disclo- sure as a means to security. In AAMAS, 2015. 23. [Rudin, 1986] W. Rudin. Principles of Mathematical Analy- sis. McGraw -Hill Book C., 1986. 24. [Sinha et al., 2016] Arunesh Sinha, Debarun Kar, and Milind Tambe. Learning adversary behavior in security games: A pac model perspective. In AAMAS, 2016. 25. [Tambe, 2011] Milind Tambe. Security and game theory: al- gorithms, deployed systems, lessons learned. Cambridge university press, 2011. 26. [Wilder et al., 2019] Bryan Wilder, Bistra Dilkina, and Milind Tambe. Melding the data-decisions pipeline: Decision-focused learning for combinatorial optimization. In AAAI, pages 1658-1665, 2019. 27. [Xu et al., 2015] Haifeng Xu, Zinovi Rabinovich, Shaddin Dughmi, and Milind Tambe. Exploring information asym- metry in two-stage security games. In AAAI, 2015. 28. [Yang et al., 2011] Rong Yang, Christopher Kiekintveld, Fernando Ordonez, Milind Tambe, and Richard John. Im- proving resource allocation strategy against human adver- saries in security games. In IJCAI, 2011. 29. [Yang et al., 2012] Rong Yang, Fernando Ordonez, and Milind Tambe. Computing optimal strategy against quan- tal response in security games. In AAMAS, 2012. 30. [Zhuang et al., 2010] Jun Zhuang, Vicki M. Bier, and Oguzhan Alagoz. Modeling secrecy and deception in a multi-period attacker-defender signaling game. European Journal of Operational Research, 203:409-418, 2010.