Nonzero-sum Adversarial Hypothesis Testing Games

Sarath Yasodharan, Patrick Loiseau

TL;DR

This paper models adversarial classification as a nonzero-sum game where an attacker strategically chooses a data distribution to deceive a defender. The authors prove that even in this strategic tug-of-war, classification errors vanish exponentially fast as more data is collected, with the "speed" of error reduction determined by the attacker's least-cost distribution.

What Problem Does This Paper Address?

In traditional machine learning, we usually assume that data is generated by a neutral "nature." However, in security-sensitive applications like fraud detection or malware classification, an adversary deliberately manipulates data to bypass filters.

Most research in "adversarial ML" focuses on evasion attacks, where an attacker tweaks a specific image or file to fool a model. This paper tackles a different, more fundamental scenario: adversarial hypothesis testing. Here, the attacker doesn't just change one data point; they choose an entire probability distribution from which a sequence of data points is generated. The defender must observe this sequence and decide: "Is this a normal user or an attacker?"

The challenge is that this is a nonzero-sum game. The attacker has costs (it might be expensive to mimic a normal user perfectly), and the defender has different priorities (balancing false alarms vs. missed detections). Analyzing these games is mathematically difficult because the players have an infinite (uncountable) number of possible strategies.

Methods

The authors use game theory and large deviations theory to analyze the interaction.

  1. Game Formulation: They define a two-player game where the attacker picks a distribution $q$ (with an associated cost $c(q)$) and the defender chooses a decision rule.
  2. Nash Equilibrium (NE): They prove that a mixed-strategy Nash equilibrium exists. Interestingly, they show that even against a strategic adversary, the defender's optimal move is a version of the likelihood ratio test—a classic tool from statistics.
  3. Asymptotic Analysis: They investigate what happens as the number of observed data samples ($n$) grows toward infinity. They use the Chernoff-Stein Lemma and Chernoff Information—concepts that describe how fast errors drop in non-adversarial settings—and adapt them to this strategic environment.

Datasets

This is a theoretical paper, so it does not use large-scale real-world datasets like ImageNet. Instead, the authors use synthetic numerical experiments with a binary alphabet (e.g., sequences of 0s and 1s) to validate their mathematical proofs. They simulate the game across different sample sizes ($n$ ranging from 10 to 400) to show that their predicted error rates match the experimental results.

Key Insights and Ideas

  • The "Least-Cost" Anchor: The most important finding is that the game's long-term behavior is anchored by $q^*$, the distribution that is cheapest for the attacker to use. As the defender gets more data, the attacker’s strategy "concentrates" around this least-cost distribution.
  • Strategic Equivalence to Classical Testing: Surprisingly, the authors show that the adversarial game eventually "behaves" like a classical, non-adversarial test between the normal distribution ($p$) and the attacker's least-cost distribution ($q^*$).
  • The Importance of "Distance": The paper introduces a specific geometric assumption (Assumption A4). If the attacker can find a distribution that is "closer" to the normal data than the least-cost distribution is, the standard error rates might break down. This highlights a potential "blind spot" for defenders if an adversary is willing to spend more to be extra stealthy.
  • Nonzero-sum Complexity: Unlike zero-sum games (where one player's gain is exactly the other's loss), nonzero-sum games are much harder to solve. This paper successfully characterizes the equilibrium behavior without needing to explicitly calculate the exact (and likely very complex) strategy of the attacker.

Key Results

  • Existence Proof: The authors successfully proved that these complex, uncountable games always have a stable equilibrium (Nash Equilibrium).
  • Error Exponents: They derived the exact mathematical rates at which classification errors disappear. In the Bayesian framework, the error rate is $-\Lambda^*_0(0)$, and in the Neyman-Pearson framework, it is $-D(p||q^*)$.
  • Numerical Validation: Their simulations confirmed that as the number of samples $n$ increases, the actual error rates converge perfectly to their theoretical predictions, provided their geometric assumptions hold.

Limitations and Future Work

  • Finite Alphabets: The current proofs assume the data comes from a finite set of possibilities (like a vocabulary or a set of discrete sensor readings). Extending this to continuous data (like images or audio) is a significant mathematical hurdle because the "distance" between distributions becomes harder to manage.
  • Structure of the Attacker's Strategy: While the authors proved the existence of an equilibrium and its rate of convergence, they acknowledge that finding the exact structure of the attacker's strategy remains a "difficult problem" because the strategy space is infinite.
  • Sequential Testing: The paper assumes the defender looks at a fixed number of samples ($n$) and then decides. In reality, a defender might want to decide as quickly as possible (sequential detection). The authors suggest this as a promising direction for future research.

Summary updated

Abstract

We study nonzero-sum hypothesis testing games that arise in the context of adversarial classification, in both the Bayesian as well as the Neyman-Pearson frameworks. We first show that these games admit mixed strategy Nash equilibria, and then we examine some interesting concentration phenomena of these equilibria. Our main results are on the exponential rates of convergence of classification errors at equilibrium, which are analogous to the well-known Chernoff-Stein lemma and Chernoff information that describe the error exponents in the classical binary hypothesis testing problem, but with parameters derived from the adversarial model. The results are validated through numerical experiments.
BibTeX
@inproceedings{yasodharan2019nonzero,
  author = {Sarath Yasodharan and Patrick Loiseau},
  title = {{Nonzero-sum Adversarial Hypothesis Testing Games}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=7TqXyR3VEK},
}
Figure