Cyber-security is an important societ al concern. Cyber-attacks have increased in numbers as well as in the extent of damage caused in every attack. Large organizations operate a Cyber Security Operation Center (CSOC), which form the first line of cyber-defense. The inspection of cyber-alerts is a critical part of CSOC operations. A recent work, in collaboration with Army Research Lab, USA proposed a reinforcement learning (RL) based approach to prevent the cyber-alert queue length from growing large and overwhelming the defender. Given the potential deployment of this approach to CSOCs run by US defense agencies, we perform a red team (adversarial) evaluation of this approach. Further, with the recent attacks on learning systems, it is even more important to test the limits of this RL approach. Towards that end, we learn an adversarial alert generation policy that is a best response to the defender inspection policy. Surprisingly, we find the defender policy to be quite robust to the best response of the attacker. In order to explain this observation, we extend the earlier RL model to a game model and show that there exists defender policies that can be robust against any adversarial policy. We also derive a competitive baseline from the game theory model and compare it to the RL approach. However, we go further to exploit assumptions made in the MDP in the RL model and discover an attacker policy that overwhelms the defender. We use a double oracle approach to retrain the defender with episodes from this discovered attacker policy. This made the defender robust to the discovered attacker policy and no further harmful attacker policies were discovered. Overall, the adversarial RL and double oracle approach in RL are general techniques that are applicable to other RL usage in adversarial environments.
Game theoretic inspection or auditing has appeared in many papers @cite_14 @cite_8 @cite_27 , however, all these works have a single shot interaction model and are not focused on cyber-alert inspection. As stated already, one game based work @cite_9 on cyber-alert inspection is single shot, and has other stringent assumptions such as fixed number of analysts and alerts per hour. Another recent game theoretic work @cite_3 uses a zero-sum Markov game model for cyber-alert inspection, but the model assumes complete information for both the players and hence solves the game using standard minimax value iteration. Our approach accounts for the realistic scenario of incomplete information and signals, and explains theoretically and empirically the subtle relation between the budget of the players. Game theory has also been used for other problems in cyber-security such as deception @cite_2 , attack graphs @cite_11 , man in the middle attacks @cite_4 , and spear fishing @cite_6 @cite_17 , which are quite different from our cyber-security problem. Also, scalability is still an issue in solving partially observable stochastic games @cite_29 . Further, our game has a non-standard long term utility.
@cite_14 @cite_4 @cite_8 @cite_9 @cite_29 @cite_17 @cite_3 @cite_6 @cite_27 @cite_2 @cite_11
2963619318 2739823785 1908253641 2907590737 2565355925 2794861508 2257448745
A wide variety of mechanisms, such as alert triggers and auditing routines, have been developed to notify administrators about types of suspicious activities in the daily use of large databases of personal and sensitive information. However, such mechanisms are limited in that: 1) the volume of such alerts is often substantially greater than the auditing capabilities of budget-constrained organizations and 2) strategic attackers may disguise their actions or carefully choose which records they touch, thus evading auditing routines. To address these problems, we introduce a novel approach to database auditing that explicitly accounts for adversarial behavior by 1) prioritizing the order in which types of alerts are investigated and 2) providing an upper bound on how much budget to allocate for auditing each alert type. We model the interaction between a database auditor and potential attackers as a Stackelberg game in which the auditor chooses an auditing policy and attackers choose which records in a database to target. We further introduce an efficient approach that combines linear programming, column generation, and heuristic search to derive an auditing policy, in the form of a mixed strategy. We assess the performance of the policy selection method using a publicly available credit card application dataset, the results of which indicate that our method produces high-quality database audit policies, significantly outperforming baselines that are not based in a game theoretic framing. We develop an exact dynamic programming algorithm for partially observable stochastic games (POSGs). The algorithm is a synthesis of dynamic programming for partially observable Markov decision processes (POMDPs) and iterated elimination or dominated strategies in normal form games. We prove that when applied to finite-horizon POSGs, the algorithm iteratively eliminates very weakly dominated strategies without first forming a normal form representation of the game. For the special case in which agents share the same payoffs, the algorithm can be used to find an optimal solution. We present preliminary empirical results and discuss ways to further exploit POMDP theory in solving POSGs. Allocating cyber-security analysts to incoming cyber alerts is an important task in any organization employing cyber-defense mechanisms. Alerts are typically generated when intrusion detection software on computer systems (e.g., servers, routers) detect abnormal or suspicious activity. Based on the respective significance level of the alerts, some are assigned to cyber-security analysts for further investigation. Due to the wide range of potential attacks coupled with high degrees of attack sophistication, identifying what constitutes a true attack is a challenging problem, especially for organizations performing critical operations (e.g., military bases, financial institutions, etc.) that are constantly being subjected to cyber attacks every day. In this paper, we develop a game-theoretical framework that assigns cyber-security analysts to cyber alerts to minimize the overall risk faced by an organization. Our approach considers a series of games between the attacker and the defender in which a state is maintained between sub-games. The state captures the availability of analysts as well as an attack budget metric that enables us to model the level of risk an attacker is willing to undertake. Through dynamic programming and Q-maximin value iteration-based algorithms, we identify optimal allocation strategies that take into account the current availability of analysts, the risk faced by the attacker, the incoming alerts, and the future outlook of the system. We assess the effectiveness of our allocation strategies by comparing them to other sensible heuristics (e.g., random, greedy and myopic). Our results show that our approach outperforms these other strategies in minimizing risk. Highly targeted spear phishing attacks are increasingly common, and have been implicated in many major security breeches. Email filtering systems are the first line of defense against such attacks. These filters are typically configured with uniform thresholds for deciding whether or not to allow a message to be delivered to a user. However, users have very significant differences in both their susceptibility to phishing attacks as well as their access to critical information and credentials that can cause damage. Recent work has considered setting personalized thresholds for individual users based on a Stackelberg game model. We consider two important extensions of the previous model. First, in our model user values can be substitutable, modeling cases where multiple users provide access to the same information or credential. Second, we consider attackers who make sequential attack plans based on the outcome of previous attacks. Our analysis starts from scenarios where there is only one credential and then extends to more general scenarios with multiple credentials. For single-credential scenarios, we demonstrate that the optimal defense strategy can be found by solving a binary combinatorial optimization problem called PEDS. For multiple-credential scenarios, we formulate it as a bilevel optimization problem for finding the optimal defense strategy and then reduce it to a single level optimization problem called PEMS using complementary slackness conditions. Experimental results show that both PEDS and PEMS lead to significant higher defender utilities than two existing benchmarks in different parameter settings. Also, both PEDS and PEMS are more robust than the existing benchmarks considering uncertainties. An important way cyber adversaries find vulnerabilities in modern networks is through reconnaissance, in which they attempt to identify configuration specifics of network hosts. To increase uncertainty of adversarial reconnaissance, the network administrator (henceforth, defender) can introduce deception into responses to network scans, such as obscuring certain system characteristics. We introduce a novel game theoretic model of deceptive interactions of this kind between a defender and a cyber attacker, which we call the Cyber Deception Game. We consider both a powerful (rational) attacker, who is aware of the defender's exact deception strategy, and a naive attacker who is not. We show that computing the optimal deception strategy is NP-hard for both types of attackers. For the case with a powerful attacker, we provide a mixed-integer linear program solution as well as a fast and effective greedy algorithm. Similarly, we provide complexity results and propose exact and heuristic approaches when the attacker is naive. Our extensive experimental analysis demonstrates the effectiveness of our approaches. Preventing attacks in a computer network is the core problem in network security. We introduce a new game-theoretic model of the interaction between a network administrator who uses limited resource to harden a network and an attacker who follows a multi-stage plan to attack the network. The possible plans of the attacker are compactly represented using attack graphs, while the defender adds fake targets (honeypots) to the network to deceive the attacker. The compact representation of the attacker's strategies presents a computational challenge and finding the best response of the attacker is NP-hard. We present a solution method that first translates an attack graph into an MDP and solves it using policy search with a set of pruning techniques. We present an empirical evaluation of the model and solution algorithms, evaluating scalability, the types of solutions that are generated for realistic cases, and sensitivity analysis.