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.
The classification game we investigate is similar in nature to the inspection game, a multi-stage game between a customs inspector and a smuggler, proposed and studied by Dresher @cite_27 and Maschler @cite_39 . @cite_8 find the equilibrium of the general nonzero-sum game by using an auxiliary zero-sum game in which the inspectee chooses a violation procedure and the inspector chooses a statistical test with a given false alarm probability. We do not separate the general nonzero-sum game into two games but show the equivalence to a zero-sum game and provide structure to the equilibrium strategies of a single-shot simultaneous-move game.
@cite_8 @cite_27 @cite_39
69361866 2159243063 2548493877 2102794165
Abstract Starting with the analysis of arms control and disarmament problems in the sixties, inspection games have evolved into a special area of game theory with specific theoretical aspects, and, equally important, practical applications in various fields of human activity where inspection is mandatory. In this contribution, a survey of applications is given first. These include arms control and disarmament, theoretical approaches to auditing and accounting, for example in insurance, and problems of environmental surveillance. Then, the general problem of inspection is presented in a game-theoretic framework that extends a statistical hypothesis testing problem. This defines a game since the data can be strategically manipulated by an inspectee who wants to conceal illegal actions. Using this framework, two models are solved, which are practically significant and technically interesting: material accountancy and data verification. A second important aspect of inspection games is the fact that inspection resources are limited and have to be used strategically. This is demonstrated in the context of sequential inspection games, where many mathematically challenging models have been studied. Finally, the important concept of leadership, where the inspector becomes a leader by announcing and committing himself to his strategy, is shown to apply naturally to inspection games. We focus on solving two-player zero-sum extensive-form games with perfect information and simultaneous moves. In these games, both players fully observe the current state of the game where they simultaneously make a move determining the next state of the game. We solve these games by a novel algorithm that relies on two components: (1) it iteratively solves the games that correspond to a single simultaneous move using a double-oracle method, and (2) it prunes the states of the game using bounds on the sub-game values obtained by the classical Alpha-Beta search on a serialized variant of the game. We experimentally evaluate our algorithm on the Goofspiel card game, a pursuit-evasion game, and randomly generated games. The results show that our novel algorithm typically provides significant running-time improvements and reduction in the number of evaluated nodes compared to the full search algorithm. We consider in this chapter a class of two-player nonzero-sum stochastic games with incomplete information, which is inspired by recent applications of game theory in network security. We develop fully distributed reinforcement learning algorithms, which require for each player a minimal amount of information regarding the other player. At each time, each player can be in an active mode or in a sleep mode. If †This material is based upon work supported in part by the U.S. Air Force Office of Scientific Research (AFOSR) under grant number AFOSR MURI FA9550-09-1-0249. D R A F T October 2, 2011, 1:59am D R A F T 2 HYBRID LEARNING IN STOCHASTIC GAMES AND ITS APPLICATION IN NETWORK SECURITY a player is in an active mode, she updates her strategy and estimates of unknown quantities using a specific pure or hybrid learning pattern. The players’ intelligence and rationality are captured by the weighted linear combination of different learning patterns. We use stochastic approximation techniques to show that, under appropriate conditions, the pure or hybrid learning schemes with random updates can be studied using their deterministic ordinary differential equation (ODE) counterparts. Convergence to state-independent equilibria is analyzed for special classes of games, namely, games with two actions, and potential games. Results are applied to network security games between an intruder and an administrator, where the noncooperative behaviors are well characterized by the features of distributed hybrid learning. Part I of this paper has described a new theory for the analysis of games with incomplete information. It has been shown that, if the various players' subjective probability distributions satisfy a certain mutual-consistency requirement, then any given game with incomplete information will be equivalent to a certain game with complete information, called the “Bayes-equivalent” of the original game, or briefly a “Bayesian game.” Part II of the paper will now show that any Nash equilibrium point of this Bayesian game yields a “Bayesian equilibrium point” for the original game and conversely. This result will then be illustrated by numerical examples, representing two-person zero-sum games with incomplete information. We shall also show how our theory enables us to analyze the problem of exploiting the opponent's erroneous beliefs. However, apart from its indubitable usefulness in locating Bayesian equilibrium points, we shall show it on a numerical example the Bayes-equivalent of a two-person cooperative game that the normal form of a Bayesian game is in many cases a highly unsatisfactory representation of the game situation and has to be replaced by other representations e.g., by the semi-normal form. We shall argue that this rather unexpected result is due to the fact that Bayesian games must be interpreted as games with “delayed commitment” whereas the normal-form representation always envisages a game with “immediate commitment.”