Graph Optimisation for Active Directory Attack Path Defence
Ask any blue team what keeps them awake at 3 AM and Active Directory shows up before coffee does. A single misplaced `AdminSDHolder` edge or a forgotten `GenericAll` on a nested group turns a phished intern into a Tie…
Graph Optimisation for Active Directory Attack Path Defence
Ask any blue team what keeps them awake at 3 AM and Active Directory shows up before coffee does. A single misplaced AdminSDHolder edge or a forgotten GenericAll on a nested group turns a phished intern into a Tier-0 compromise in under nine minutes. A recent PhD thesis on practical AD hardening frames this as what it actually is: a graph optimisation problem, and a computationally intractable one at that.
Why static edge removal isn’t the answer
BloodHound turned attack-path visualisation into a standard blue-team exercise, and defenders have spent five years trying to prune those graphs by hand. The thesis proves what practitioners already suspected — the optimal edge-removal problem is NP-hard even under restrictive assumptions, mirroring the shortest-path interdiction hardness results catalogued by MITRE’s D3FEND matrix. Greedy pruning of “the top 20 dangerous edges” leaves the graph structurally similar; attackers reroute through the second-best path within hours.
The interesting contribution is the shift from static optimisation to three tractable-in-practice variants: honeypot/decoy placement as a Stackelberg game, dynamic-graph defence against an adaptive adversary, and admin-in-the-loop edge prioritisation. Each acknowledges that AD is a living object — every Set-ADUser and every new group membership rewrites the graph.
2026-07-28T04:12:07Z bloodhound.ingest: new_edge type=GenericAll
src=SVC_BACKUP@corp.local dst=DA_GROUP@corp.local
path_delta=+3_tier0_paths risk_score=94
2026-07-28T04:12:09Z aegis.decoy: honeypot_placed node=FAKE_DA_01
intercept_prob=0.71 admin_ack_required=trueWhere honeypots earn their keep
Decoy placement wins on a defender’s-choice metric: the attacker must invest a probe to distinguish real Tier-0 from bait, and each probe raises detection likelihood. The thesis models this against an attacker who observes the graph but not the honeypot labels — the same threat model ENISA’s AD hardening guidance assumes for post-initial-access lateral movement. In practice, decoys placed on the top 5% of betweenness-central nodes catch the majority of BloodHound-driven pathfinding.
This connects directly to how we design detection topologies in the AEGIS pillar — sensors go on the edges attackers must cross, not on the edges that generate the most log volume. It also aligns with the argument that agentic-system safety lives in graph topology rather than in the weights of the model doing the reasoning.
What we do differently
Most AD-hardening engagements deliver a static PDF of “risky edges to remove” and call it done. That report is stale before the client signs the SoW. CAI’s working position: treat the AD attack graph as a streaming data structure, ingest changes hourly via Microsoft’s Get-ADReplicationAttributeMetadata feed, and re-score paths under the same NIST SP 800-207 zero-trust assumptions (NIST 800-207) that the NIS2 Directive Article 21 now makes non-optional for essential entities.
The thesis’s real gift is permission to stop pretending we can solve this optimally. We can, however, keep the attacker’s expected cost rising faster than their tooling improves. If you run more than 2,000 AD objects and haven’t modelled your graph dynamically in the last quarter, talk to the AEGIS team about a two-week baseline.