Security Game with Non-additive Utilities and Multiple Attacker Resources
Security Game with Non-additive Utilities and Multiple Attacker Resources
复制标题
具有非附加实用程序和多个攻击者资源的安全博弈
DOI：
10.1145/3084450
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
N. Shroff
中科院分区：
文献类型：
--
作者：
Sinong Wang;N. Shroff
人们对安全游戏的研究一直很感兴趣，以建模攻击和防御对涉及关键基础设施、金融系统安全、政治竞选和民事保护的各种系统的相互作用。然而，现有的安全博弈模型通常要么假设附加效用函数，要么假设攻击者只能攻击一个目标。这样的假设导致了易于处理的分析，但忽略了当前复杂网络中不同目标之间存在的关键内在依赖关系。在这篇文章中，我们推广了经典的安全博弈模型，以允许非加性效用函数。我们还允许攻击者能够攻击多个目标。我们从理论的角度考察了这样一个一般的安全博弈，并提供了一个统一的观点。特别地，我们证明了每个安全对策等价于由防御者的纯策略空间组成的集合系统ε上的一个组合优化问题。我们使用的关键技术是基于多面体的变换、投影和椭球体方法。这项工作解决了安全对策领域中的几个公开问题，并极大地扩展了安全对策的多项式可解和NP难类的研究现状。
There has been significant interest in studying security games for modeling the interplay of attacks and defenses on various systems involving critical infrastructure, financial system security, political campaigns, and civil safeguarding. However, existing security game models typically either assume additive utility functions, or that the attacker can attack only one target. Such assumptions lead to tractable analysis, but miss key inherent dependencies that exist among different targets in current complex networks. In this paper, we generalize the classical security game models to allow for non-additive utility functions. We also allow attackers to be able to attack multiple targets. We examine such a general security game from a theoretical perspective and provide a unified view. In particular, we show that each security game is equivalent to a combinatorial optimization problem over a set system ε, which consists of defender's pure strategy space. The key technique we use is based on the transformation, projection of a polytope, and the ellipsoid method. This work settles several open questions in security game domain and significantly extends the state-of-the-art of both the polynomial solvable and NP-hard class of the security game.