Abstract
Classical supervised learning assumes that training data is representative of the data expected to be observed in the future. This assumption is clearly violated when an intelligent adversary actively tries to deceive the learner by generating instances very different from those previously seen. The literature on adversarial machine learning aims to address this problem, but often assumes constraints that sophisticated and determined adversaries need not abide by. We model the adversarial machine learning problem by considering an unconstrained, but utility-maximizing, adversary. In addition, rather than modifying the learning algorithm to increase its robustness to adversarial manipulation, we use an output of an arbitrary probabilistic classifier (such as Näıve Bayes) in a linear optimization program that computes optimal randomized operational decisions based on machine learning predictions, operational constraints, and our adversarial model. Our approach is simpler than its predecessors, highly scalable, and we experimentally demonstrate that it outperforms the state of the art on several metrics.
1. Introduction
In adversarial domains such as spam filtering or intrusion detection, the standard independent and identically distributed (i.i.d.) assumption of machine learning is fundamentally broken. Adversaries actively manipulate their behavior to evade detection, creating a dynamic "cat-and-mouse" game. Traditional approaches often attempt to build "robust" classifiers by baking adversarial constraints into the training process. However, these models frequently conflate the act of prediction with the operational decision-making process, often ignoring real-world constraints like limited inspection budgets and the true utility of the adversary.
2. Methodology: Decoupling Prediction and Action
The proposed framework decouples probabilistic prediction from operational decision-making. Instead of modifying the underlying learning algorithm, the system uses the output of an arbitrary probabilistic classifier (e.g., Naive Bayes) as an input to a linear optimization program.
This approach models the interaction as a Stackelberg Game. The defender (the system) commits to a randomized inspection policy $q(x)$, which represents the probability of inspecting a given input $x$. A utility-maximizing adversary observes this policy and chooses an attack $x'$ that maximizes their own payoff. By solving a Linear Program (LP), the defender identifies an optimal randomized policy that accounts for budget constraints and potential adversarial responses. This "moving target defense" prevents attackers from identifying fixed blind spots in the system.
3. Experimental Setup
The framework was evaluated using the TREC spam corpora (2005–2008). Models were trained on the 2005 dataset and tested on subsequent years to measure performance against real-world "concept drift" caused by evolving spammers. Additionally, synthetic datasets were employed to simulate a perfectly rational, unconstrained adversary, providing a "worst-case" performance benchmark.
4. Results and Discussion
Experimental results demonstrate that the optimization wrapper significantly improves the utility of standard classifiers.
Key findings include:
- Superior Performance: The proposed method consistently achieved higher normalized utility than established adversarial learning methods like those by Dalvi et al. and Bruckner et al.
- Budget Efficiency: The benefits of the optimization approach are most pronounced under tight inspection budgets, where strategic resource allocation is critical.
- Robustness: The model remains effective even when the defender's estimates of the adversary's utility parameters are slightly inaccurate.
- Scalability: By utilizing linear programming, the decision engine is computationally efficient and scales better than methods that integrate adversarial logic directly into the training phase.
5. Conclusion
While the model currently assumes a finite instance space, its simplicity and scalability offer a powerful alternative to traditional adversarial ML. Future work will focus on extending the framework to continuous feature spaces and exploring dynamic learning where the classifier is optimized specifically to support the subsequent decision stage.
Summary updated