Imitative Attacker Deception in Stackelberg Security Games

Thanh Nguyen, Haifeng XuIJCAI 2019 · DOI

Introduction

Stackelberg Security Games (SSGs) provide a robust mathematical framework for optimizing security resource allocation, protecting critical infrastructure ranging from airports to wildlife preserves. In these games, a defender commits to a randomized security strategy, and an attacker responds after observing this commitment. A common assumption in modern SSG research is that the defender can learn the attacker's preferences by observing their reactions to various security deployments. However, this learning process introduces a significant vulnerability: if an attacker knows they are being monitored, they can strategically manipulate their behavior to "poison" the defender's model.

This paper, "Imitative Attacker Deception in Stackelberg Security Games" (IJCAI-19), explores the concept of "imitative deception." Authors Thanh Nguyen and Haifeng Xu demonstrate that a strategic attacker can significantly enhance their utility by consistently projecting a false payoff signal, thereby misleading the defender into a sub-optimal long-term commitment.

The Imitative Deception Game

Standard SSG models typically assume a rational and honest attacker who always targets the location yielding their highest immediate reward. Defenders leverage this predictability, using machine learning to "reverse engineer" the attacker's payoff structure and optimize future patrol schedules.

The authors formalize a new interaction model where the attacker chooses a "deceptive payoff" to project. By playing consistently according to this lie, the attacker forces the defender to eventually commit to a Strong Stackelberg Equilibrium (SSE) based on the false information. This is a form of causative attack on the defender's learning algorithm.

Theoretical Insights: The Maximin Trap

A key theoretical contribution of the paper is the characterization of optimal deception in an unconstrained setting. The authors prove that an attacker’s optimal strategy is to pretend the game is strictly competitive (zero-sum). By mimicking a "pure hater"—someone whose payoffs are the exact inverse of the defender's—the attacker forces the defender to adopt a Maximin strategy.

While Maximin is designed to provide a guaranteed baseline of security regardless of the attacker's true payoffs, it is highly predictable. In a general-sum game, this predictability allows the attacker to achieve a much higher "true" utility than they would have obtained by being honest.

Constrained Deception and Optimization

In practice, an attacker may face constraints on their ability to lie. They might only be able to misrepresent payoffs within certain bounds or for a limited subset of targets. To address these realistic scenarios, the authors developed a general optimization framework.

The problem is initially formulated as a Mixed Integer Non-Linear Program (MINLP). The researchers successfully linearized this into a Mixed Integer Linear Program (MILP) for two primary constraint types:

  • Value-Bound Constraints: The deceptive payoff must remain within a specific interval ($I$) of the true value.
  • Target-Limited Constraints: The attacker can only lie about a specific percentage or number of targets.

Experimental Results

The authors evaluated their framework using synthetic data generated via GAMUT, simulating games with up to 200 targets. The MILP formulation proved computationally practical, solving games with 160 targets and complex constraints in approximately 7.5 minutes.

Experimental results showing attacker gain and defender loss across various parameters, including number of targets, defender resources, and target ratio.

As shown in the experimental results (Figure 1), the attacker's true utility (decAttU) consistently outperforms the utility achieved through honest play (trueAttU) across various scales (plots a, c). This advantage scales with the number of targets and the degree of allowed deception ($I$). Conversely, the defender suffers a significant loss (plots b, d). The "Defender Loss"—the gap between the utility the defender expects based on the deceptive signal and what they actually receive—widens as the game scale increases.

Furthermore, the study found that even a small "Target Ratio" (the percentage of targets the attacker lies about) can yield massive strategic gains for the attacker (plot g), while simultaneously degrading defender performance (plot h). The utility gain curve for the attacker shows strong concavity, suggesting that the most significant benefits of deception are realized even with limited manipulation.

Conclusion and Future Directions

This research highlights a critical flaw in naive security learning loops. By treating an attacker's behavior as a static data source rather than a strategic signal, defenders leave themselves open to manipulation.

Future work should focus on "Deception-Aware Defense" mechanisms that can detect or mitigate the impact of imitative deception. Additionally, exploring these dynamics in repeated games—where defenders might verify outcomes over time—and considering non-consistent deception strategies remain vital areas for securing real-world infrastructure against sophisticated adversaries.

Summary updated

BibTeX
@inproceedings{nguyen2019imitative,
  author = {Thanh Nguyen and Haifeng Xu},
  title = {{Imitative Attacker Deception in Stackelberg Security Games}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/75},
}
Figure