arXiv:2505.01028v1 通告类型: 新 摘要: Windows Active Directory (AD) 系统中的安全漏洞通常通过攻击图进行建模，增强 AD 系统涉及一个迭代工作流：安全团队提出一个要移除的边，而 IT 运维团队需要手动审核这些修复后再实施移除。由于验证需要大量的手动工作，我们提出了一个自适应路径移除问题，旨在最小化这个迭代移除过程中的步骤数。在我们的模型中，向导在每一步提出一条攻击路径，并将其表示为多选项集合提供给 IT 经理。然后，IT 经理从中选择一个边进行移除。这一过程将继续进行，直到目标 \(t\) 与源 \(s\) 断开连接，或者提出路径的数量达到 \(B\)。该模型旨在通过最小化 IT 经理与安全向导之间的交互次数来优化人力投入。我们首先证明该问题是 \(\#P\) 硬的。然后，我们提出了一组解决方案，包括精确算法、近似算法以及几种可扩展的启发式方法。我们最佳的启发式方法被称为 DPR，它在处理大规模图方面比精确算法更有效，并且在所有图中都持续优于近似算法。我们通过在多个合成 AD 图和从实际组织收集的 AD 攻击图上验证我们的算法的有效性。