Scalable Optimal Classifiers for Adversarial Settings under Uncertainty

Patrick Loiseau, Benjamin Roussillon

Abstract

We consider the problem of finding optimal classifiers in an adversarial setting where the class-1 data is generated by an attacker whose objective is not known to the defender -- an aspect that is key to realistic applications but has so far been overlooked in the literature. To model this situation, we propose a Bayesian game framework where the defender chooses a classifier with no a priori restriction on the set of possible classifiers. The key difficulty in the proposed framework is that the set of possible classifiers is exponential in the set of possible data, which is itself exponential in the number of features used for classification. To counter this, we first show that Bayesian Nash equilibria can be characterized completely via functional threshold classifiers with a small number of parameters. We then show that this low-dimensional characterization enables to develop a training method to compute provably approximately optimal classifiers in a scalable manner; and to develop a learning algorithm for the online setting with low regret (both independent of the dimension of the set of possible data). We illustrate our results through simulations.

Introduction

In security-critical domains such as spam filtering and fraud detection, the data distribution is not stationary. Instead, it is shaped by strategic adversaries who adapt their tactics to bypass defensive measures. Traditional machine learning models often struggle in these adversarial settings because they assume independent and identically distributed (i.i.d.) data. While game-theoretic models have been proposed to address this "arms race," they frequently rely on two restrictive assumptions: complete information (the defender knows the attacker's exact utility) and limited classifier complexity (restricting the defender to simple models like linear classifiers to maintain computational feasibility).

This paper introduces a scalable framework for finding optimal classifiers against adaptive attackers with unknown objectives. By framing the problem as a Bayesian game, the authors prove that complex defense strategies can be reduced to a few simple parameters, enabling efficient training and online learning that remains effective even in high-dimensional data spaces.

Methodology

The proposed approach models the interaction between a defender and an attacker as a Bayesian game. The defender faces an attacker of an unknown "type," representing various possible objectives or gain functions.

Dimensionality Reduction and Threshold Classifiers

A primary contribution is the mathematical proof that the defender does not need to search through an exponentially large space of possible classifiers. Instead, the optimal defense is characterized by a probability of detection function defined by a small number of parameters—specifically, one parameter per attacker type. These optimal defenses take the form of generalized threshold classifiers: a data point is flagged as an attack if its "suspicion score" (derived from the attacker's potential gain) exceeds a randomized threshold.

Training and Online Learning

For offline scenarios, the authors employ Sample Average Approximation (SAA) to transform the game-theoretic optimization into a standard linear program. This allows training on labeled datasets without requiring an explicit model of the "normal" data distribution. For real-time applications, they provide an Online Gradient Descent algorithm. Notably, the "regret"—the performance gap between the defender's strategy and the theoretical optimum—is shown to be independent of the number of features in the data, ensuring scalability to high-dimensional "big data" environments.

Experimental Evaluation

The framework was evaluated using both synthetic benchmarks and real-world data:

  • ULB Credit Card Fraud Dataset: Comprising approximately 285,000 European cardholder transactions with 31 features.
  • Synthetic Benchmarks: Including a bank fraud simulation and a "worst-case" random game to verify theoretical properties like convergence rates and regret bounds.

Results and Insights

The research yields several key insights into adversarial learning:

  • Strategic Simplicity: Counter-intuitively, the presence of a strategic attacker simplifies the learning problem. The set of optimal defenses has a VC dimension of only 1, as attackers act predictably to maximize gain.
  • Feature Independence: The efficiency of the defense depends on the number of attacker types rather than the number of data features.
  • Robustness: The SAA method implicitly models normal data through sampling, providing robustness against noise.
Probability of detection for different attacker types on the credit card fraud dataset.

As shown in the figure above, the model identifies the "Pareto frontier" of defense. For the credit card dataset, the detection probability curves for different attacker gain profiles illustrate how the defender can trade off between fraud detection and false alarms based on the transaction amount. The training algorithm is proven to find the exact optimal strategy with a probability that approaches 1 exponentially fast, while the online learning algorithm achieves a regret bound of $O(\sqrt{T})$, independent of the data space size.

Conclusion

This work provides a theoretically grounded and computationally efficient framework for adversarial classification under uncertainty. While the model assumes fixed attacker utilities and focuses on binary classification, it establishes a robust foundation for defending against strategic agents. Future work may explore "learning attackers" who actively reverse-engineer defenses and extensions to multi-class classification problems.

Summary updated

Abstract

We consider the problem of finding optimal classifiers in an adversarial setting where the class-1 data is generated by an attacker whose objective is not known to the defender -- an aspect that is key to realistic applications but has so far been overlooked in the literature. To model this situation, we propose a Bayesian game framework where the defender chooses a classifier with no a priori restriction on the set of possible classifiers. The key difficulty in the proposed framework is that the set of possible classifiers is exponential in the set of possible data, which is itself exponential in the number of features used for classification. To counter this, we first show that Bayesian Nash equilibria can be characterized completely via functional threshold classifiers with a small number of parameters. We then show that this low-dimensional characterization enables to develop a training method to compute provably approximately optimal classifiers in a scalable manner; and to develop a learning algorithm for the online setting with low regret (both independent of the dimension of the set of possible data). We illustrate our results through simulations.
BibTeX
@inproceedings{loiseau2021scalable,
  author = {Patrick Loiseau and Benjamin Roussillon},
  title = {{Scalable Optimal Classifiers for Adversarial Settings under Uncertainty}},
  booktitle = {GameSec},
  year = {2021},
  url = {https://openreview.net/forum?id=cZDiKgAXQf},
}
Figure