Game Theory for Cyber Security

点击翻译按钮获取中文摘要

This project falls within the EPSRC research theme of Information and Communication Technologies and aims at studying techniques for applying computational game theory to addressing issues in cyber security. Computational game theory (CGT) is a research field in the intersection of game theory and computer science. While classical game theory has provided rich mathematical foundations and equilibrium concepts for modeling and understanding strategic interactions between self-interested agents, CGT focuses on the computational aspects and asks in general how to design efficient algorithms to compute equilibrium solutions. With its help, quantitative analyses have been made available, extending existing results to more constructive ones that are able to predict strategic behaviors or provide guidance for strategic decision-making in real-world scenarios.Recent research in CGT has found many successful applications in the security domain. These are known as security games. The key problem in security games is how to allocate limited defense resources (e.g., police guards) to protect potential targets (e.g., ports, trains, wildlife) against strategic attackers (e.g., terrorists, poachers). To come up with the optimal solution, security events are modeled as leader-follower games played between a defender (the leader) and an attacker (the follower). Algorithms have been designed to compute the equilibria of such games. Systems applying these algorithms have been developed and deployed in many real security settings, including the PROTECT system for the US Coast Guard, IRIS for the US Federal Air Marshals service, and the PAWS system for wildlife protection.Given these achievements, it is plausible to consider applying CGT to tackle security issues in the cyber domain. Cyber systems are ubiquitous in today's world with more than 5 billion connected devices in 2015 and a prediction of 20 billion by 2020. The large pool of targets constitutes a large playground for cyber attackers. Improving cyber security is therefore imperative. Unfortunately, migrating the concepts and techniques of existing security games to cyber security faces many challenges due to novelties of cyber problems: (1) Cyber scenarios may involve multiple (more than two) parties/players. Network users, who are free to make their decisions and whose interests align with none of the defender's or the attacker's, might be treated as another party in cyber games. With these players added, the interactions become quite complicated. Issues such as bounded rationality of network users may also arise. (2) Complex network structures are often embedded in cyber problems. Unlike networks in the physical world which are mostly planar, cyber networks can have higher dimensions. In addition, cyber networks can be much larger, easily involving thousands of distributed agents, whereas in many physical scenarios this already exceeds the realistic size. The large input size can make even simple problems computationally infeasible to solve. (3) The frequency of cyber attacks is higher than physical attacks, and the cost is much lower. As a result, the one-shot game model widely used in existing research might be inappropriate in cyber domain.With these challenges in mind, in this project we will particularly focus on: (1) Modeling cyber security games, including building new models of security games that are appropriate for use in cyber scenarios, such as games involving multiple parties; and modeling human behaviors, such as bounded rationality of human players. (2) Designing scalable solution algorithms, including establishing results of computational complexity, and exploring approximate or heuristic algorithms to overcome the complexity barrier. Given the foreseeable computational complexity of cyber security games, it it is also practical to study adversaries with limited computational capability, which is another unexplored area in the literature.