Game Theory for Cyber Security

该项目属于EPSRC的信息和通信技术研究主题，旨在研究应用计算博弈论解决网络安全问题的技术。计算博弈论(CGT)是博弈论和计算机科学交叉的一个研究领域。经典博弈论为建模和理解自利主体之间的战略互动提供了丰富的数学基础和均衡概念，而CGT则专注于计算方面，并询问如何设计有效的算法来计算均衡解。在它的帮助下，已经提供了定量的分析，将现有的结果扩展到更有建设性的结果，能够预测现实世界中的战略行为或为战略决策提供指导。最近的研究发现，CGT在安全领域有许多成功的应用。这些游戏被称为安全游戏。安全游戏中的关键问题是如何分配有限的防御资源(如警察警卫)来保护潜在目标(如港口、火车、野生动物)免受战略攻击者(如恐怖分子、偷猎者)的攻击。为了提出最优解决方案，安全事件被建模为防御者(领导者)和攻击者(追随者)之间进行的领导者-追随者游戏。已经设计了算法来计算这类博弈的均衡。应用这些算法的系统已经被开发并部署在许多真实的安全环境中，包括美国海岸警卫队的保护系统，美国联邦空警服务的IRIS，以及野生动物保护的PAWS系统。鉴于这些成就，考虑应用CGT来解决网络领域的安全问题是合理的。网络系统在当今世界无处不在，2015年互联设备超过50亿台，预计到2020年将达到200亿台。庞大的目标池构成了网络攻击者的一个巨大游乐场。因此，改善网络安全势在必行。不幸的是，由于网络问题的新颖性，将现有安全游戏的概念和技术迁移到网络安全面临许多挑战：(1)网络场景可能涉及多个(多于两个)方/玩家。网络用户可以自由地做出决定，他们的利益与防御者或攻击者都不一致，他们可能会被视为网络游戏中的另一方。随着这些玩家的加入，互动变得相当复杂。也可能出现网络用户的有限理性等问题。(2)复杂的网络结构往往嵌入到网络问题中。与物理世界中大多是平面的网络不同，网络网络可以有更高的维度。此外，网络可能更大，很容易涉及数千个分布式代理，而在许多物理场景中，这已经超过了实际规模。较大的输入大小甚至会使简单的问题在计算上无法解决。(3)网络攻击频次高于物理攻击，成本远低于物理攻击。因此，现有研究中广泛使用的一次性游戏模型可能不适用于网络领域。考虑到这些挑战，在本项目中，我们将特别关注：(1)网络安全游戏的建模，包括构建适合于网络场景的新的安全游戏模型，如涉及多方的游戏；以及建模人类行为，如人类玩家的有限理性。(2)设计可扩展的求解算法，包括建立计算复杂性的结果，探索克服复杂性障碍的近似或启发式算法。考虑到网络安全游戏可预见的计算复杂性，研究计算能力有限的对手也是可行的，这是文献中另一个未探索的领域。

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.