A Scalable Double Oracle Algorithm for Hardening Large Active Directory Systems

Abstract

Active Directory (AD) is a popular information security management system for Windows domain networks and is an ongoing common target for cyber attacks. Most real-world Active Directory systems consist of millions of entities and links, and there are currently no efficient and effective solutions for hardening Active Directory systems of such scale. In this paper, we propose a novel and scalable double oracle-based algorithm for hardening large AD systems. We formulate the problem as a Stackelberg game between the defender and the attacker on a weighted AD attack graph, where the defender acts as the leader with a budget, and the objective is to find an optimal defender’s pure strategy. We show that our double oracle-based solution has significantly improved speed and scalability compared with previous solutions for hardening AD systems. Lastly, we compare with GoodHound weakest links and show that our solution provides better recommendations for targeting the elimination of optimal attack paths.