We study a Stackelberg game between an attacker and a defender on large
Active Directory (AD) attack graphs where the defender employs a set of
honeypots to stop the attacker from reaching high-value targets. Contrary to
existing works that focus on small and static attack graphs, AD graphs
typically contain hundreds of thousands of nodes and edges and constantly
change over time. We consider two types of attackers: a simple attacker who
cannot observe honeypots and a competent attacker who can. To jointly solve the
game, we propose a mixed-integer programming (MIP) formulation. We observed
that the optimal blocking plan for static graphs performs poorly in dynamic
graphs. To solve the dynamic graph problem, we re-design the mixed-integer
programming formulation by combining m MIP (dyMIP(m)) instances to produce a
near-optimal blocking plan. Furthermore, to handle a large number of dynamic
graph instances, we use a clustering algorithm to efficiently find the m-most
representative graph instances for a constant m (dyMIP(m)). We prove a lower
bound on the optimal blocking strategy for dynamic graphs and show that our
dyMIP(m) algorithms produce close to optimal results for a range of AD graphs
under realistic conditions.

研究了一个堆栈博弈，针对大型活动目录（AD）攻击图中的攻击者和防御者，其中防御者使用一组蜜罐阻止攻击者接近高价值目标。通过提出混合整数规划（MIP）公式来共同解决这个博弈问题。通过重新设计混合整数规划公式并使用聚类算法来高效找到最具代表性的图实例，以处理大量动态图实例。通过证明动态图的最优阻塞策略的下界，并展示在现实条件下，我们的算法在一系列 AD 图中产生接近最优的结果。