Adaptive Wizard for Removing Cross-Tier Misconfigurations in Active Directory

Adaptive Wizard for Removing Cross-Tier Misconfigurations in Active Directory

Huy Q. Ngo, Mingyu Guo, Hung X. Nguyen

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence
Main Track. Pages 7661-7669. https://doi.org/10.24963/ijcai.2025/852

Security vulnerabilities in Windows Active Directory (AD) systems are typically modeled using an attack graph and hardening AD systems involves an iterative workflow: security teams propose an edge to remove, and IT operations teams manually review these fixes before implementing the removal. As verification requires significant manual effort, we formulate an Adaptive Path Removal Problem to minimize the number of steps in this iterative removal process. In our model, a wizard proposes an attack path in each step and presents it as a set of multiple-choice options to the IT admin. The IT admin then selects one edge from the proposed set to remove. This process continues until the target t is disconnected from source s or the number of proposed paths reaches B. The model aims to optimize the human effort by minimizing the expected number of interactions between the IT admin and the security wizard. We first prove that the problem is #P-hard. We then propose a set of solutions including an exact algorithm, an approximate algorithm, and several scalable heuristics. Our best heuristic, called DPR, can operate effectively on larger-scale graphs compared to the exact algorithm and consistently outperforms the approximate algorithm across all graphs. We verify the effectiveness of our algorithms on several synthetic AD graphs and an AD attack graph collected from a real organization.
Keywords:
Multidisciplinary Topics and Applications: MTA: Security and privacy
Search: S: Combinatorial search and optimisation
Agent-based and Multi-agent Systems: MAS: Human-agent interaction