Search

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.

We consider a game in which a strategic defender classifies an intruder as spy or spammer. The classification is based on the number of file server and mail server attacks observed during a fixed window. The spammer naively attacks (with a known distribution) his main target: the mail server. The spy strategically selects the number of attacks on his main target: the file server. The defender strategically selects his classification policy: a threshold on the number of file server attacks. We model the interaction of the two players (spy and defender) as a nonzero-sum game: The defender needs to balance missed detections and false alarms in his objective function, while the spy has a tradeoff between attacking the file server more aggressively and increasing the chances of getting caught. We give a characterization of the Nash equilibria in mixed strategies, and demonstrate how the Nash equilibria can be computed in polynomial time. Our characterization gives interesting and non-intuitive insights on the players' strategies at equilibrium: The defender uniformly randomizes between a set of thresholds that includes very large values. The strategy of the spy is a truncated version of the spammer's distribution. We present numerical simulations that validate and illustrate our theoretical results.