Abstract
Securing Microsoft Active Directory (AD) environments against lateral movement is a complex task often characterized by reactive remediation. This paper introduces Spiral, a novel anytime algorithm designed for the judicious partitioning of attack graphs. By treating the network as a graph and strategically removing a limited budget of edges, Spiral maximizes the number of entry points blocked from reaching administrative accounts. Our evaluation on large-scale simulated AD networks shows that Spiral significantly outperforms traditional Integer Linear Programming (ILP) in speed and surpasses shortest-path interdiction methods in security effectiveness.
Introduction
In modern enterprise networks, Microsoft Active Directory (AD) manages the relationships between users, computers, and permissions. Attackers exploit these relationships to perform "lateral movement," escalating from low-privilege accounts to high-privilege "Domain Admin" targets. While tools like BloodHound help visualize these paths, remediating them is difficult. Removing edges (permissions or connections) has a cost: it requires manual IT review and risks breaking business processes.
The challenge is a judicious partitioning problem: given a budget $b$, which $b$ edges should be removed to maximize the number of source nodes disconnected from the target? This problem is proven to be NP-hard, making exact solutions for large-scale corporate networks (often exceeding 30,000 nodes) computationally infeasible for standard solvers.
The Spiral Algorithm
To address the scalability limits of exact solvers, we propose the Spiral Algorithm. Spiral is an "anytime" algorithm, meaning it can be stopped at any moment to provide the best solution found so far, with quality improving monotonically over time.
The algorithm avoids processing the entire massive AD graph at once. Instead, it operates in layers based on source connectivity—a metric that ranks subgraphs by how many entry points can reach the target through them. Spiral iterates through two main phases:
- Edge Sampling: It uses a modified Dijkstra’s algorithm to identify "k-trees" (subgraphs where $k$ sources reach a target) containing unexplored edges.
- Local Optimization: It runs an Integer Linear Programming (ILP) solver only on the small, high-impact subset of edges identified during sampling.
This approach ensures that the solver focuses on the most critical parts of the graph, allowing it to find high-quality solutions for massive networks in seconds rather than hours.
Experimental Evaluation
We evaluated Spiral using four simulated AD networks (G1-G4) generated by ADSimulator, ranging from approximately 3,000 to 30,000 nodes. We compared Spiral against a pure ILP solver and a "Double Oracle" shortest-path interdiction method.
Performance and Scalability
Spiral demonstrates remarkable speed advantages over standard ILP solvers. As shown in the runtime comparison, the pure ILP solver often fails to find a solution within an hour (3600s) for larger graphs as the budget increases. In contrast, Spiral consistently finds high-quality solutions in a fraction of the time, such as solving the G4 graph with a budget of 5 in under 70 seconds.
Security Effectiveness
Beyond speed, Spiral is significantly more effective at securing the network than traditional shortest-path interdiction. While methods like Double Oracle focus on making attack paths longer, Spiral focuses on complete disconnection.
As seen in Table 2, Spiral disconnects substantially more sources than the Double Oracle approach across all tested graphs. For instance, in G4 with a budget of 5, Spiral disconnects 38 sources compared to only 2 by the Double Oracle method, representing a massive improvement in network security posture.
Conclusion
The Spiral algorithm provides a practical, scalable solution for hardening Active Directory networks. By framing security remediation as a judicious partitioning problem and utilizing an anytime approach, Spiral allows security engineers to make informed, high-impact decisions within operational time constraints. Future work will focus on adapting the algorithm for dynamic graphs and validating it against real-world corporate telemetry.
Summary updated