Near Optimal Strategies for Honeypots Placement in Dynamic and Large Active Directory Networks

Active Directory (AD) is the default security management system for Windows domain networks and is the target of many recent cyber attacks. 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/edges and constantly change over time. We show that the optimal honeypot placement problem is NP-hard even for static graphs and develop a tree decomposition method to derive an optimal deployment strategy and a mixedinteger programming (MIP) formulation to scale to large graphs. We observed that the optimal blocking plan for static graphs performs poorly for dynamic graphs. To handle dynamic graphs, we redesign the mixed-integer programming formulation by combining m MIP (dyMIP(m)) instances. We prove a performance lower-bound on the optimal blocking strategy for dynamic graphs and show that our dyMIP(m) algorithm produces near optimal results.