A budgeted maximum multiple coverage model for cybersecurity planning and management
A budgeted maximum multiple coverage model for cybersecurity planning and management
复制标题
用于网络安全规划和管理的预算最大多重覆盖模型
DOI：
10.1080/24725854.2019.1584832
复制
发表时间：
2019
影响因子：
2.6
通讯作者：
Eli Towle
中科院分区：
文献类型：
--
作者：
Kaiyue Zheng;Laura A. Albert;James R. Luedtke;Eli Towle
摘要 本文研究如何确定减轻网络基础设施漏洞的策略。我们提出了一个优化框架，优先考虑安全缓解措施的投资，以最大限度地覆盖漏洞。我们使用多重覆盖来体现分层防御的实施，并考虑覆盖失败的可能性，以解决某些缓解措施有效性的不确定性。制定了预算最大多重覆盖（BMMC）问题，并证明该问题是受背包约束的子模最大化问题。考虑到选择缓解措施的不同可能要求，包括单位成本基数约束和组基数约束，制定了该问题的其他变体。我们设计贪婪近似算法来识别模型的接近最优解。我们证明了 BMMC 的最佳 (1–1/e) 近似比和考虑覆盖失败可能性的 BMMC 变体，以及使用基数约束和组基数约束的 BMMC 变体的 1/2 近似比。计算研究表明，我们的模型产生了强大的解决方案，该解决方案使用分层防御，并提供有效的机制来对冲可能的覆盖失败的风险。我们还发现，近似算法可以有效地识别接近最优的解决方案，并且我们提出的 Benders 分支剪切算法可以在一小时内为考虑到覆盖失败的提议模型的变化找到绝大多数测试实例的可证明最优解决方案。
Abstract This article studies how to identify strategies for mitigating cyber-infrastructure vulnerabilities. We propose an optimization framework that prioritizes the investment in security mitigations to maximize the coverage of vulnerabilities. We use multiple coverage to reflect the implementation of a layered defense, and we consider the possibility of coverage failure to address the uncertainty in the effectiveness of some mitigations. Budgeted Maximum Multiple Coverage (BMMC) problems are formulated, and we demonstrate that the problems are submodular maximization problems subject to a knapsack constraint. Other variants of the problem are formulated given different possible requirements for selecting mitigations, including unit cost cardinality constraints and group cardinality constraints. We design greedy approximation algorithms for identifying near-optimal solutions to the models. We demonstrate an optimal (1–1/e)-approximation ratio for BMMC and a variation of BMMC that considers the possibility of coverage failure, and a 1/2-approximation ratio for a variation of BMMC that uses a cardinality constraint and group cardinality constraints. The computational study suggests that our models yield robust solutions that use a layered defense and provide an effective mechanism to hedge against the risk of possible coverage failure. We also find that the approximation algorithms efficiently identify near-optimal solutions, and that a Benders branch-and-cut algorithm we propose can find provably optimal solutions to the vast majority of our test instances within an hour for the variations of the proposed models that consider coverage failures.