System Design: Active Directory Attack Path Solver

1. Problem Statement

Design a system that ingests an Active Directory environment snapshot and returns a prioritized list of attack paths from a given starting principal to a target objective (e.g., Domain Admin).

Functional requirements:

• Ingest AD objects: users, computers, groups, GPOs, and their relationships (group membership, ACLs, delegation settings, SPN registrations)
• Model relationships as a directed graph where edges are permissions or exploitation paths
• Find shortest/most-dangerous paths from a start node (e.g., JSMITH@MERIDIAN.LOCAL) to a target node (e.g., Domain Admins)
• Prioritize by detection visibility (low-noise paths preferred by the attacker)
• Return each path step with: source, edge type (permission), target, ATT&CK technique ID, detection opportunity
• Support "what if" analysis: "if we disable Kerberos RC4 for all service accounts, how many paths are removed?"

Non-functional requirements:

• Scale: up to 100,000 AD objects, 1,000,000 edges
• Query latency: under 5 seconds for a full path search
• Offline: operates on a snapshot; does not need live AD connectivity

2. Constraints

In scope:

• Graph model and edge taxonomy
• Path finding algorithm choice and complexity tradeoff
• Detection visibility scoring
• Data ingestion pipeline
• Query API design

Out of scope:

• Collection module (how the snapshot is gathered from the target AD)
• Authentication to the target domain
• Automated exploitation

3. High-Level Architecture

                ┌──────────────────────┐
                │  AD Snapshot Input   │
                │  (BloodHound JSON /  │
                │   LDAP dump / CSV)   │
                └──────────┬───────────┘
                           │
                           ▼
                ┌──────────────────────┐
                │  Ingestion Pipeline  │
                │  - Parse objects     │
                │  - Normalize edge    │
                │    types             │
                │  - Score each edge   │
                │    (detection cost)  │
                └──────────┬───────────┘
                           │
                           ▼
                ┌──────────────────────┐
                │  Graph Store         │
                │  (in-memory or       │
                │   embedded graph DB) │
                │  Nodes: principals   │
                │  Edges: permissions  │
                └──────────┬───────────┘
                           │
                    ┌──────┴────────┐
                    │               │
                    ▼               ▼
          ┌──────────────┐  ┌───────────────────┐
          │ Path Finder  │  │ What-If Analyzer  │
          │ (Dijkstra /  │  │ (remove edge set, │
          │  BFS)        │  │  recount paths)   │
          └──────┬───────┘  └────────┬──────────┘
                 │                   │
                 └─────────┬─────────┘
                           ▼
                ┌──────────────────────┐
                │  Report Generator    │
                │  - Path table        │
                │  - Detection mapping │
                │  - ATT&CK IDs        │
                └──────────────────────┘

4. Component Deep-Dives

4.1 Graph Model

Nodes: principals (users, computers, groups, GPOs, OUs). Minimal model:

{
    "id": "JSMITH@MERIDIAN.LOCAL",
    "type": "user",   # user | computer | group | gpo | ou
    "properties": {
        "enabled": True,
        "spn_count": 2,
        "kerberos_pre_auth": True,
        "admin_count": False,
    }
}

Edges: permission relationships. Each edge has a type, a weight (detection cost), and an ATT&CK mapping:

Graph cost function: edge weight = detection cost. Dijkstra finds the path with minimum total detection cost → the path least likely to be detected.

4.2 Path Finder

Algorithm: Dijkstra's shortest path on the detection-cost-weighted graph.

• source = start principal
• target = Domain Admins group (or any specified target node)
• weight = edge detection cost
• Output: ordered list of edges forming the minimum-cost path

Why Dijkstra over BFS?

• BFS finds the path with fewest hops, not the stealthiest path. A 3-hop path through a DCSync edge (cost 4) is worse OPSEC than a 5-hop path through only low-cost edges.
• Dijkstra minimizes total cost.

Complexity: O((V + E) log V) with a binary heap. At 100,000 nodes and 1,000,000 edges, this is acceptable for interactive query latency.

Multiple paths: run K-shortest-paths (Yen's algorithm) to return the top-K paths for the analyst. The first is the stealthiest; subsequent paths are alternatives if the first is blocked.

4.3 Detection Visibility Scoring

Each edge gets a detection cost based on:

1. Event volume: how many events does traversing this edge generate? (DCSync = 1 high-value event with EID 4662; MemberOf = 0 events)
2. Event specificity: is the event type exclusively associated with attacks, or does it have high legitimate overlap? (EID 4769 RC4 TGS request = high attack specificity; EID 4624 logon = high benign overlap)
3. Sensor coverage: is the relevant sensor deployed in the target environment? (If EID 4662 is not in the SIEM scope, DCSync has effective cost = 0)

The system accepts a sensor_inventory parameter that marks which detections are active. This allows "red team OPSEC mode" (model only detections that exist in the target) vs. "blue team audit mode" (model all possible detections).

4.4 What-If Analyzer

Use case: "If we disable Kerberos RC4 encryption for all service accounts, how many attack paths are removed?"

Implementation:

1. Filter edges of type HasSPN where kerberos_rc4_allowed = True
2. Remove those edges from the graph
3. Re-run path finder for all possible start→target pairs
4. Report: paths removed count, paths remaining count, new shortest path (if any)

Use in purple teaming: this is the analytical counterpart to the purple team session. The what-if analyzer predicts which hardening controls remove the most attack paths. The purple team session validates whether the detection rules fire on the remaining paths.

5. Tradeoffs

In-memory graph vs. embedded DB:

• In-memory: sub-millisecond edge traversal, no I/O. Sufficient for a single engagement snapshot (100K nodes, 1M edges ≈ 2–4 GB RAM).
• Embedded DB (Neo4j, DGraph): persistent, queryable by multiple users, handles larger graphs.
• Decision: in-memory for the single-analyst tool model; use an embedded graph DB if the platform is shared among 10+ analysts.

Dijkstra vs. A:*

• A* requires a heuristic (estimated cost to goal). In an AD graph, no simple heuristic exists — the graph structure is irregular.
• Decision: Dijkstra. If performance is an issue at scale, use bidirectional Dijkstra.

K-shortest paths computational cost:

• Yen's K-shortest paths is O(K × V × (V + E) log V). For K=10, V=100K, E=1M, this is expensive for real-time interactive use.
• Decision: limit K to 5; cache results for repeated queries on the same snapshot.

6. Detection-Forward Perspective

This system is itself a detection-forward tool: it produces the attacker's view and the defender's view simultaneously.

• Every path step includes the detection opportunity. A path with 4 steps has 4 detection opportunities. The report shows which ones the client currently has deployed.
• The what-if analyzer is the blue team planning tool: it answers "which single control removes the most paths?"
• The sensor inventory parameter allows the blue team to see the attacker's effective graph (with deployed detections removed) and understand what paths survive their current controls.

This is purple teaming formalized. The Lab 01 solver in Phase 05 implements a simplified version of this system.