🤖 AI

Practical Graph Optimisation and AI-Driven Models for Active Directory Security Hardening

This paper proposes a series of game-theoretic and optimization-based models to address the dynamic nature, limited active defense mechanisms, and practical implementation constraints of Active Directory security hardening by introducing strategies for honeypot placement, dynamic decoy deployment, and adaptive, admin-in-the-loop remediation prioritization.

Original authors: Huy Q. Ngo

Published 2026-07-27

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Huy Q. Ngo

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine the digital world of a large company as a massive, invisible castle. Inside this castle, there are thousands of rooms, secret passages, and guard towers. The most important treasure—the crown jewels of the company's data—is locked in the "Tier 0" vault, guarded by the Domain Admins. To keep the castle safe, security teams build a map of every possible route an intruder could take to reach that vault. This map is called an "attack graph." In a perfect world, the castle is designed so that no one can sneak from the front gate (a low-level employee's computer) to the vault without passing through a series of locked doors. But in reality, the castle is messy. Employees forget to lock doors, admins accidentally leave keys on the wrong tables, and new secret passages open up every time someone logs into a computer. This mess is called "insecure drift."

The paper you are about to read tackles a very tricky problem: How do you protect a castle that is constantly changing shape, where the walls move and new doors appear every hour? Traditional security tools are like a static list of "bad doors" to fix. They tell you, "Fix this one, then that one." But in a dynamic castle, fixing one door might just open a new window five minutes later. The researchers in this study realized that instead of just fixing broken doors, you need to be smarter. You need to set up traps (honeypots) that look like real treasure but are actually fake, and you need to figure out exactly where to put them so that even if the castle changes, the intruder gets caught early. They also wanted to know how to ask the castle's human managers, "Should we lock this door?" in a way that doesn't waste time asking about every single door, but still finds the best way to stop the thief.

The Paper's Mission: Catching the Thief in a Moving Castle

This research, titled "Practical Graph Optimisation and AI-Driven Models for Active Directory Security Hardening," dives deep into the messy reality of protecting Microsoft Active Directory (AD) networks. The authors, led by Quang Huy Ngo, argue that the old way of thinking about security is broken because it treats the network like a frozen snapshot. In the real world, the network is a living, breathing thing that changes every second as people log in, log out, and move around.

The paper proposes four main ways to outsmart attackers in this moving target environment, using a mix of math, game theory, and artificial intelligence.

1. The "Where to Hide the Fake Treasure" Problem (Honeypot Placement)
Imagine you are the castle guard. You have a limited number of fake treasure chests (honeypots) to place. If a thief touches one, an alarm goes off. The problem is: where do you put them?
The authors found that if you just look at a map of the castle at one specific moment, you might place your traps perfectly for that second. But if the castle shifts an hour later, your traps might be useless. They proved mathematically that finding the perfect spot for these traps is incredibly hard (so hard it's called "NP-hard" and "W[1]-hard").
To solve this, they developed a new method that looks at many different versions of the castle map at once. They used a technique called "clustering" to find the most "representative" versions of the castle and placed traps there. Their experiments showed that this method works on massive networks with over 137,000 nodes (rooms) and nearly 1.5 million connections (doors). They found that their new strategy could stop attackers much better than old methods, even when the network was constantly changing.

2. Buying Time: The "Response Time" Metric
The researchers realized that catching a thief isn't just about stopping them; it's about how much time you have to react after you see them. They invented a new way to measure success called "Response Time." This is the time between the moment a thief steps on a fake trap and the moment they actually steal the crown jewels.
They modeled the attacker as a smart, patient player who waits for the perfect moment to move. The goal for the defender is to place traps so that even if the thief gets through, it takes them as long as possible to reach the vault.
They found that standard computer algorithms were too slow to figure this out on big, moving maps. So, they built a faster, smarter algorithm (using a method called Evolutionary Diversity Optimization) that could calculate the best trap placements quickly. In their tests, their new method was about 5 times faster than existing tools for calculating paths and found solutions 108 times faster than older methods in some cases. They also showed that their method could handle networks with millions of connections without crashing the computer.

3. The "Adaptive Wizard": Asking the Right Questions
Sometimes, you can't just delete a connection (like a permission) because it's needed for the business to work. You have to ask a human manager, "Is it okay to lock this door?" But asking about every single door would take forever.
The authors created a "Wizard" (a smart software guide) that asks the manager questions in a specific order. Instead of asking, "Should we lock Door A?" then "Door B?", the Wizard looks at a whole path the thief might take and asks, "Which of these three doors on this path should we lock?"
They proved that finding the perfect way to ask these questions is also mathematically impossible to solve perfectly in a reasonable time. However, they built a "Dynamic Programming" algorithm that gets very close to the perfect answer. Their simulations showed that this "Wizard" could find the best set of doors to lock while asking the human manager far fewer questions than random guessing or simple lists.

4. The "Self-Improving Robot" (Reinforcement Learning)
Finally, the team tried teaching a computer to learn how to ask the right questions on its own using a technique called Reinforcement Learning (RL). They created an AI agent that plays the game of "Security Hardening" over and over again.
At first, the AI is bad at it. But they gave it a special "self-improvement" trick: every time it makes a mistake, it learns from it and gets better. They also gave it a "reward system" that encourages it to find the shortest path to a solution.
In their tests, this AI agent learned to ask fewer questions than any other method they tried. It was able to generalize its learning, meaning it could apply what it learned about one type of network to a completely different one. The results showed that this AI approach significantly outperformed the other methods, reducing the number of questions needed to secure the network.

What the Paper Rules Out
The authors are very clear about what doesn't work. They explicitly show that treating the network as a static, unchanging picture is a bad idea. If you plan your defense based on a map from this morning, it will likely fail by this afternoon because the network has changed. They also rule out the idea that you can simply list the "worst" vulnerabilities and fix them one by one; they show that you need to look at the whole picture and how the paths connect.

How Sure Are They?
The authors are very confident in their mathematical proofs that these problems are hard to solve. However, their solutions are based on simulations and experiments on synthetic (fake but realistic) networks and some real-world data from anonymous organizations. They didn't test this on a live, real-world company network where a mistake could cause a real breach. So, while the math is solid and the simulations are promising, the real-world effectiveness is suggested by these tests rather than proven in a live battle. They show that their methods can work and are much faster and more effective than current tools, but they present this as a strong recommendation based on rigorous testing, not a guaranteed fix for every situation.

In short, this paper suggests that to protect a modern, messy digital castle, you need to stop looking at static maps and start using smart, adaptive strategies that can handle change, ask the right questions, and buy you precious time to react.

Technical Summary: Practical Graph Optimisation and AI-Driven Models for Active Directory Security Hardening

1. Problem Definition

Microsoft Active Directory (AD) serves as the core identity and access management system for approximately 90% of Fortune 500 companies. Despite its ubiquity, AD environments are frequently compromised, with penetration testers achieving full compromise in up to 82% of assessed networks. The primary vulnerability stems from "insecure drift," where day-to-day operations (e.g., privileged admins signing into low-privilege workstations) create cross-tier attack paths that violate the "Clean Source Principle."

Defenders traditionally rely on attack graphs (e.g., generated by BloodHound) to visualize these paths. However, existing hardening approaches face three critical limitations:

Static Assumptions: Most models treat the AD graph as static, ignoring dynamic edges (e.g., HasSession edges) that appear and disappear based on user activity, leading to suboptimal defenses in real-world scenarios.
Limited Defense Mechanisms: Current research focuses almost exclusively on edge removal (revoking permissions). It lacks models for active defenses, such as the strategic placement of honeypots or decoys, which can intercept attackers without disrupting operations.
Lack of Human-in-the-Loop Scalability: Practical hardening requires IT administrator approval. Existing models either assume all edge removability is known in advance (impractical) or query edges one-by-one (non-scalable). There is a need for adaptive models that learn administrator decision patterns to minimize query effort while guaranteeing the disconnection of attack paths.

This thesis addresses these gaps by developing game-theoretic and optimization-based models specifically for AD-style attack graphs, proving the computational intractability of these problems, and proposing scalable algorithms ranging from Mixed-Integer Programming (MIP) to Reinforcement Learning (RL).

2. Methodology and Contributions

The thesis is structured around four primary contributions, each addressing specific research objectives regarding active defense, temporal dynamics, and adaptive human interaction.

Contribution 1: Honeypot Placement in Static and Dynamic Graphs (Chapter 3)

Problem: How to optimally place a limited budget of honeypots on AD nodes to intercept attackers, considering both "simple" attackers (who cannot detect honeypots) and "competent" attackers (who can observe and avoid them).
Methodology:

Game-Theoretic Formulation: The problem is modeled as a Stackelberg game. The defender minimizes the attacker's success probability against a mix of simple and competent attackers.
Complexity: The problem is proven to be NP-hard against simple attackers and W[1]-hard against competent attackers.
Static Solution: A Mixed-Integer Programming (MIP) formulation is developed. Leveraging the tree-like structure of AD graphs, the solver achieves high efficiency even on large graphs (up to ~137k nodes).
Dynamic Solution: Recognizing that AD graphs evolve via HasSession edges, the thesis proposes dyMIP(m), which optimizes over $m$ $m$ graph snapshots. To handle scalability, two heuristics are introduced:
- Voting-based: Runs MIP on batches of snapshots and selects nodes appearing most frequently.
- Clustering-based: Uses k-means clustering on graph features to select representative snapshots, solving the MIP only on this reduced set.
  Results: Experiments on synthetic and real-world authentication data show that the clustering-based heuristic produces near-optimal blocking plans with significantly lower computational cost than solving for all snapshots. The approach scales to graphs with millions of edges, outperforming static-only defenses which fail to account for dynamic edge appearance.

Contribution 2: Optimizing Cyber Response Time on Temporal Graphs (Chapter 4)

Problem: In a temporal setting, attackers may "lurk" in a node waiting for a specific edge to become available. The goal is not just to block paths but to maximize the Response Time (RT)—the duration between the attacker triggering the first decoy and reaching the Domain Admin (DA).
Methodology:

Metric: RT is defined as the time difference between the first honeypot trigger and the compromise of the DA. The defender aims to maximize the worst-case RT.
Complexity: The optimization problem is proven NP-hard via reduction from the strict temporal $(s, d)$ -separator problem.
Algorithm: An Evolutionary Diversity Optimization (EDO) algorithm is employed to find diverse, high-quality defense strategies.
Optimizations:
- Faster Fitness Evaluation: A novel Dijkstra-based algorithm is proposed to compute the "earliest-arrival path" in temporal graphs. It exploits the fact that most AD edges are static, achieving a 5x speedup over state-of-the-art temporal path algorithms (Wu et al.).
- Constraint Handling: Two techniques are introduced to handle the difficulty of finding feasible solutions (cuts) in the evolutionary search:
  1. ILP Repair: Uses Integer Linear Programming to "patch" infeasible offspring into valid cuts.
  2. Surrogate-Assisted Fitness: Uses a lightweight surrogate function evaluating only a set of "important" paths, iteratively updated with new optimal attack paths found by the attacker.

Results: The Surrogate-Assisted (EST) approach converges to feasible solutions approximately 108 times faster than the vanilla EDO and outperforms ILP-based repair by ~23% in response time metrics, while avoiding Out-of-Memory errors on larger graphs.

Contribution 3: Adaptive Wizard for Cross-Tier Path Removal (Chapter 5)

Problem: How to interactively query an IT administrator to remove edges and disconnect attack paths with the minimum number of queries, without knowing in advance which edges are removable.
Methodology:

Adaptive Path Removal (APR): A "wizard" presents an attack path to the administrator as a set of multiple-choice options (edges on that path). The admin selects one edge to remove. The process repeats until the path is cut or the budget is exhausted.
Complexity: Finding the optimal adaptive policy is proven #P-hard.
Algorithms:
- Exact (OPT): A Dynamic Programming approach for small graphs.
- Approximation (APP): An adaptive submodular approximation algorithm.
- Scalable Heuristic (DPR): A "Dynamic Programming with Restrictions" heuristic that builds on exact methods but scales to larger graphs.
- RL Approach: A Reinforcement Learning heuristic trained offline for low inference time.
  Results: The DPR heuristic delivers the strongest results, guaranteeing the elimination of all $s-t$ paths when sufficient budget is available. It significantly outperforms baseline non-adaptive strategies in reducing the expected number of queries.

Contribution 4: Feature-Based Adaptive Connectivity Test (F-ACT) (Chapter 6)

Problem: Extending the adaptive query model to generalize administrator decisions based on edge features (e.g., object properties) rather than querying edges individually.
Methodology:

F-ACT Framework: Instead of asking "Remove edge $e$ ?", the wizard presents an edge with its feature vector. The admin's decision (cut/keep) is applied to all edges sharing that feature pattern.
RL Solution (RL4FT): A Reinforcement Learning agent is trained to learn an adaptive query policy.
- Self-Improvement: A mechanism allowing the agent to improve upon any given reference policy.
- Reward Shaping: A policy-invariant scheme to handle sparse rewards.
- Prioritized Experience Replay: A custom replay buffer to focus on high-value transitions.
  Results: RL4FT guarantees improvement over any reference policy and significantly outperforms state-of-the-art baselines (including the DPR heuristic from Chapter 5) in minimizing the expected number of queries, demonstrating the efficacy of feature-based generalization in security hardening.

3. Key Results and Significance

The thesis demonstrates that:

Dynamic Defense is Critical: Static honeypot placement strategies degrade significantly when applied to dynamic AD graphs. The proposed clustering-based and voting-based heuristics for dynamic graphs achieve near-optimal performance with high scalability.
Temporal Awareness Enhances Response: By modeling the graph temporally and maximizing response time, defenders gain a critical window for incident response. The proposed Dijkstra-based fitness evaluation and surrogate-assisted EDO algorithms make this computationally feasible for large-scale networks.
Human-in-the-Loop is Scalable: Adaptive querying models (APR and F-ACT) successfully reduce the administrative burden of hardening. By generalizing decisions across edge features (F-ACT) or using adaptive path selection (APR), the system minimizes the number of queries required to secure the network while guaranteeing path disconnection.
Computational Hardness: The thesis rigorously establishes that the underlying problems (honeypot placement, temporal cut maximization, adaptive querying) are computationally intractable (NP-hard, W[1]-hard, #P-hard), justifying the need for the proposed heuristic and approximation algorithms.

Significance:
This work bridges the gap between theoretical graph security models and practical Active Directory hardening. It moves beyond simple edge-removal heuristics to provide a comprehensive toolkit that includes active defense (honeypots), temporal awareness (response time optimization), and human-centric automation (adaptive wizards). The proposed algorithms are designed to scale to enterprise-sized networks (hundreds of thousands of nodes), addressing the specific constraints of real-world AD environments where operational continuity and administrator workload are paramount. The thesis concludes that while the problems are theoretically hard, the proposed AI-driven and optimization-based approaches provide practical, effective solutions for modern AD security.