Lab 01 — Active Directory Attack-Path Solver (BloodHound-style)

Lens: Identity attack paths over the directory graph. WARMUP: Chapter 11 (the BloodHound graph model), with the edge techniques drawn from Chapters 5–10. Engagement tie-in: Operation Cedar Lattice, Phase 05. With a foothold user on a Meridian Freight workstation, you model Meridian's directory as a graph and compute the cheapest, quietest chain of identity abuses from that owned user to Domain Admins — then hand the defender the edges to cut.

The problem

A modern Active Directory forest is not a list of permissions — it is a graph of who-can-do-what- to-whom. SharpHound collects it; BloodHound walks it. The reason AD intrusions so often end in total domain compromise is that the graph is dense with abusable relationships nobody audited: a help-desk group with ForceChangePassword over a service account, a workstation where a Domain Admin left a session, an object with GenericAll granted "temporarily" three years ago. Each of these is an edge. Chain enough edges and an unprivileged foothold reaches Domain Admins.

The attacker's question is a shortest-path question — but the cost is not hops, it is attacker effort and detectability. Reusing a live admin session (HasSession → dump) is cheap but loud; walking MemberOf group edges is free and silent; cracking a delegated ticket is expensive. The defender's question is the dual: which edges lie on every path — the choke points — so I cut the fewest things and break the most paths? This lab answers both over a synthetic directory.

What you build (lab.py)

The edge taxonomy (EDGE_CATALOG), the per-edge-type cost table (DEFAULT_COST), the high-value set (DEFAULT_HIGH_VALUE), and the Edge dataclass are given. You implement the graph algorithms:

• shortest_path(edges, start, target) → (node_path, edge_path, total_cost) — Dijkstra over Edge.effective_cost(); (None, (), inf) if unreachable; ((start,), (), 0.0) if start == target.
• path_cost(edges, start, target) → the total attacker effort of the cheapest path.
• reachable_high_value(edges, start, high_value=None) → every reachable high-value target as (target, cheapest_cost), ranked by cost (case-insensitive name match).
• choke_edges(edges, start, target) → the (src, dst, kind) edges whose removal disconnects the target — the highest-leverage remediations.
• path_techniques(edge_path) → per-step {src, dst, kind, cost, technique, technique_name, detection} so every hop names its ATT&CK technique and the Windows/Kerberos event that detects it.

The edge taxonomy (a slice of the BloodHound model)

The cost per edge orders least-resistance paths; lower is quieter. MemberOf is ~free, a session harvest is moderate, DCSync/cert theft is expensive.

Attack cases the tests cover

• Known path found. A foothold user reaches Domain Admins; the returned node path and edge path are consistent (each edge connects consecutive nodes).
• Weighting picks the quieter path. Given a loud session-harvest route and a quiet GenericAll route to the same target, Dijkstra returns the quiet one (the path of least resistance, not fewest hops); a cheaper long path beats an expensive direct edge; an explicit per-edge cost overrides the type default.
• Unreachable target returns (None, (), inf); an isolated component is never reached.
• Reachable high-value targets are ranked by cost — Domain Admins (cheap) ranks above KRBTGT (needs an extra DCSync hop).
• Choke edge identified. The single MemberOf edge into Domain Admins lies on every path and is flagged; the GenericAll edge — which has an alternate route around it — is not a choke.
• Technique + detection labeled for every step; an uncatalogued edge kind degrades to a safe UNKNOWN label instead of crashing the solver.
• Determinism — identical inputs give identical paths, rankings, and choke sets.

Run

pip install -r requirements.txt
LAB_MODULE=solution pytest -q   # reference passes (12 tests)
pytest -q                        # your implementation after the TODOs

Hardening / detection (the break-the-chain pairing)

choke_edges is the remediation engine: it names the few edges whose removal severs the most paths to the crown jewels — the help-desk ForceChangePassword, the stale GenericAll, the Domain Admin's HasSession on a tier-2 box. Cutting a choke edge (remove the dangerous ACE; enforce tiered admin so DAs never log on to workstations; convert to gMSA so service-account creds cannot be reset and reused) is worth more than patching ten leaf nodes. path_techniques ties every surviving edge to the exact telemetry — 4662/5136 for DACL abuse, 4724 for a forced reset, 4769 for delegation, 4886/4887 for ADCS — so the SOC can build the detection for the paths you cannot cut. The lesson: in AD, remediation is graph surgery, and detection is per-edge.

Extensions (your own isolated, owned range)

• Derive edge cost from real BloodHound signals (session freshness, OS patch level, whether the abuse needs cracking) instead of static type costs.
• Compute a true minimum-cost edge cut (cheapest set of edges to disconnect the high-value set), not just single-edge choke points.
• Add inbound high-value reasoning: rank every owned principal by how many high-value targets it can reach (the "where would an attacker start?" view defenders use to find toxic foothold accounts).
• Ingest a real SharpHound JSON export from an owned, purpose-built GOAD-style forest (see HITCHHIKERS-GUIDE.md) and solve over it — never a production domain.
• Emit a Cypher query equivalent for each found path so a blue team can reproduce it in their own BloodHound instance.

Interview / resume

"Built a BloodHound-style AD attack-path solver: model the directory as a typed, weighted, directed graph; Dijkstra finds the quietest (least-resistance) chain of identity abuses from an owned principal to Domain Admins; choke-edge analysis names the minimum set of dangerous ACLs/sessions a defender must cut; every edge is labeled with its ATT&CK technique and the Windows/Kerberos event that detects it."

Limitations: a single static cost per edge type (real BloodHound weights by exploitability and session freshness); choke edges found by single-edge removal, not a formal min-cut; the edge→technique catalog is a representative slice of the BloodHound taxonomy, not exhaustive; costs are illustrative ordering signals, not measured probabilities; reasons over synthetic directory metadata only — no live AD, no collection, no weaponization.