A Game-Theoretic Analysis of Adversarial Classification
Authors:
- Lemonia DritsoulaLDLemonia Dritsoula
- Patrick LoiseauPLPatrick Loiseau
- John MusacchioJMJohn Musacchio
Preprint
Abstract
Attack detection is usually approached as a classification problem. However, standard classification tools often perform poorly because an adaptive attacker can shape his attacks in response to the algorithm. This has led to the recent interest in developing methods for adversarial classification, but to the best of our knowledge, there have been very few prior studies that take into account the attacker's tradeoff between adapting to the classifier being used against him with his desire to maintain the efficacy of his attack. Including this effect is key to derive solutions that perform well in practice. In this investigation we model the interaction as a game between a defender who chooses a classifier to distinguish between attacks and normal behavior based on a set of observed features and an attacker who chooses his attack features (class 1 data). Normal behavior (class 0 data) is random and exogenous. The attacker's objective balances the benefit from attacks and the cost of being detected while the defender's objective balances the benefit of a correct attack detection and the cost of false alarm. We provide an efficient algorithm to compute all Nash equilibria and a compact characterization of the possible forms of a Nash equilibrium that reveals intuitive messages on how to perform classification in the presence of an attacker. We also explore qualitatively and quantitatively the impact of the non-attacker and underlying parameters on the equilibrium strategies.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Binary Hypothesis Testing Game With Training DataIEEE Transactions on Information Theory, 2014
- Game theory meets network security and privacyACM Computing Surveys, 2013
- The Source Identification Game: An Information-Theoretic PerspectiveIEEE Transactions on Information Forensics and Security, 2013
- Bayesian Reasoning and Machine Learning2012
- Stackelberg vs. Nash in Security Games: An Extended Investigation of Interchangeability, Equivalence, and UniquenessJournal of Artificial Intelligence Research, 2011
- Settling the complexity of computing two-player Nash equilibriaJournal of the ACM, 2009
- A Game Theoretical Framework on Intrusion Detection in Heterogeneous NetworksIEEE Transactions on Information Forensics and Security, 2009
- Game strategies in network securityInternational Journal of Information Security, 2005
- Professionals Play MinimaxReview of Economic Studies, 2003
- Correlated equilibria in some classes of two-person gamesInternational Journal of Game Theory, 1974