Scalable Optimization of Randomized Operational Decisions in Adversarial Classification Settings

Bo Li, Yevgeniy VorobeychikAISTATS 2015 · OpenReview

Abstract

In adversarial settings like intrusion detection, intelligent adversaries attempt to evade classification policies. Traditional adversarial classification often ignores operational constraints and the benefits of randomized decision-making. This paper introduces a framework that separates machine learning—used to infer attacker preferences—from operational decision-making. By employing a Stackelberg game model and a scalable randomized policy, we develop a defense system that respects real-world resource constraints while remaining robust against adaptive adversaries.

Problem Statement: The Adversarial Evasion Challenge

In security domains such as spam filtering, machine learning is a dynamic "cat-and-mouse" game. Once a defender deploys a classifier, an intelligent adversary probes it and modifies their attack to bypass detection, a phenomenon known as adversarial evasion.

Existing robust machine learning approaches often suffer from two critical gaps:

  1. Neglect of Operational Constraints: Real-world security teams operate under limited budgets and cannot investigate every alert. Most models focus on accuracy while ignoring the practical "budget" of how many instances can realistically be inspected.
  2. Deterministic Vulnerability: Traditional binary classifiers provide a fixed threshold. An attacker who discovers this threshold can easily craft an exploit that sits just on the other side. Randomizing the defense strategy makes it significantly harder for an adversary to find a guaranteed path to success.

Methodology: A Stackelberg Game Approach

The interaction between defender and attacker is modeled as a Stackelberg game, where the defender commits to a strategy first, and the attacker responds optimally. To scale this model to high-dimensional feature spaces, several novel techniques are employed:

  • Conceptual Separation: Standard machine learning is used to learn attacker preferences, which then inform a separate optimization layer for defensive actions.
  • Randomized Policy ($q(x)$): The defender selects a probability of inspecting an instance, introducing unpredictability.
  • Fourier Representation: To handle exponential complexity, the authors utilize a parity basis representation to approximate the decision function compactly.
  • AAS Algorithm: The Adaptive Adversary based Scalable classification (AAS) algorithm employs iterative constraint generation to keep the underlying Linear Program manageable.

Key Insights: Efficiency and Robustness

A pivotal finding is that randomization acts as a force multiplier against active adversaries. Furthermore, the study reveals a "Greedy Surprise": while finding the absolute optimal evasion for an attacker is NP-Hard, a simple greedy heuristic performs remarkably well.

Adversarial utility and computation time for different attacker best-response methods.

As shown in the evaluation, this heuristic achieves utility levels comparable to complex branch-and-bound (B&B) methods while requiring significantly less computation time. The AAS model also demonstrates robustness to modeling errors, consistently outperforming traditional methods even when attacker cost assumptions are imperfect.

Experimental Evaluation

The framework was evaluated using the TREC spam corpora (2005–2008). These longitudinal datasets allow for training on "current" data and testing on "future" data, simulating the natural evolution of spam tactics.

Key Results

  • Superior Utility: In nearly all scenarios, AAS provided higher "defender utility" compared to state-of-the-art robust classifiers.
  • Budget Efficiency: Performance gains were most pronounced under tight budget constraints, where the ability to prioritize inspections is critical.
  • Scalability: The combination of Fourier basis representation and iterative constraint generation transforms an otherwise intractable problem into one solvable on standard hardware.
Comparison of Normalized Utility for AAS-enhanced models vs. baselines across TREC datasets.

Conclusion

This work provides a scalable, mathematically grounded framework for operationalizing randomized defenses. While currently optimized for binary features, future work will explore extensions to continuous data types and deployment in complex, multi-layered network intrusion systems.

Summary updated

Abstract

When learning, such as classification, is used in adversarial settings, such as intrusion detection, intelligent adversaries will attempt to evade the resulting policies. The literature on adversar...
BibTeX
@inproceedings{li2015scalable,
  author = {Bo Li and Yevgeniy Vorobeychik},
  title = {{Scalable Optimization of Randomized Operational Decisions in Adversarial Classification Settings}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2015},
  url = {https://openreview.net/forum?id=qKwikz9_t3},
}

Loading related content...

Figure