~/learn / algorithms / graphs

Graphs and Attack Paths

How graphs model networks, permissions, and trust, how breadth-first and weighted search find shortest attack paths, the Cypher queries behind BloodHound, and why graph thinking changed how both attackers and defenders see Active Directory and the cloud.

advancedupdated

A graph is a set of nodes joined by edges. In security, nodes are users, computers, groups, roles, and resources. Edges are relationships: “is a member of,” “has admin rights on,” “has a session on,” “can reset the password of,” “can assume role.” Edges often have a direction (you can reset their password, not the reverse) and sometimes a weight (some steps are harder than others).

Model an environment this way and a vague worry like “can this intern’s account reach the domain controller?” becomes a precise, answerable question: is there a directed path from this node to that one, and what is the shortest or cheapest one?

Breadth-first search (BFS) explores a graph in layers: every node one edge away, then every node two edges away, and so on. Because it expands outward evenly, the first time it reaches the target it has found a path with the fewest edges.

from collections import deque

def shortest_path(edges: dict[str, list[str]], start: str, goal: str) -> list[str] | None:
    previous = {start: None}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            path = []
            while node is not None:
                path.append(node)
                node = previous[node]
            return path[::-1]
        for neighbor in edges.get(node, []):
            if neighbor not in previous:
                previous[neighbor] = node
                queue.append(neighbor)
    return None

BFS runs in O(nodes + edges), which is why a tool can search a graph of hundreds of thousands of objects in seconds. The previous map does double duty: it marks nodes already seen (so cycles do not loop forever) and records how each node was reached (so the path can be reconstructed backward from the goal).

Depth-first search (DFS) instead follows one path to its end before backtracking. It is the natural tool for detecting cycles, for topological sorting (ordering dependencies so each comes before what needs it, used in build systems and supply-chain analysis), and for reachability questions where any path, not the shortest, is enough.

When edges have different costs, Dijkstra’s algorithm generalizes BFS to find the cheapest path by always expanding the lowest-total-cost node next. In attack-path terms, weights model difficulty: a cleartext credential lying in a share is a cheap edge, while an attack needing a specific user to log in is expensive. Weighting turns “is there a path” into “what is the easiest path,” which is the question an attacker actually cares about.

BloodHound and Active Directory

Active Directory is a graph whether or not anyone draws it. Group nesting, local-admin rights, logged-on sessions, ACLs on objects, and delegation settings are all edges. In a large organization the result is far beyond hand analysis.

BloodHound collects these relationships, stores them in a graph database (Neo4j), and answers questions with the Cypher query language. The signature query is a shortest path:

MATCH path = shortestPath(
  (start:User {owned: true})-[*1..]->(admin:Group {name: "DOMAIN [email protected]"})
)
RETURN path

A path such as owned user, member of a help-desk group, that group has GenericAll on a service account, that account is local admin on a server where a domain admin has a live session was always present in the configuration. The graph makes the otherwise invisible chain obvious, which is exactly why it reshaped internal assessment: the hard part was never the final step, it was seeing the route.

Defenders think in graphs too

  • Find and cut the edges that create the most paths to crown-jewel assets; removing one overly broad permission can eliminate thousands of paths at once (BloodHound reports this as “choke points”).
  • Use tiered administration so admin accounts never log in to lower-tier machines and leave reusable sessions behind, which deletes a whole category of edges.
  • Monitor for changes that create new edges, such as ACL edits on privileged groups.
  • Apply the same model to the cloud, where tools graph IAM roles, trust policies, and “can assume” relationships to find privilege-escalation paths between roles.

Field notes: running the attack-path analysis

The theory becomes a finding when you collect the graph and query it:

  • Collect. SharpHound (or BloodHound.py / the Rust AzureHound) gathers AD objects, group membership, ACLs, sessions, and local-admin rights into JSON, which you import into BloodHound’s Neo4j. In the cloud, Cartography, PMapper, and AWSPX build the equivalent graph of IAM roles and “can assume” edges.
  • Query the shortest path from what you control to what you want. BloodHound ships the common ones as buttons (“Shortest Paths to Domain Admins,” “Shortest Paths from Owned Principals”), and you drop to Cypher for anything custom:
MATCH p = shortestPath(
  (n {owned:true})-[:MemberOf|AdminTo|HasSession|GenericAll|WriteDacl*1..]->(m:Group {name:"DOMAIN [email protected]"})
) RETURN p
  • Read the edges as actions. GenericAll or WriteDacl on a user means you can reset their password or grant yourself rights; AdminTo plus a live HasSession from a privileged user means credential theft with Mimikatz-class tooling; AddMember on a group means you add yourself. Each edge type maps to a concrete technique.

Field notes: thinking in choke points

Defenders run the same graph to find the choke points, the few edges that sit on the most paths to crown-jewel assets, and cut them: remove one over-broad GenericAll, enforce tiered admin so privileged sessions never land on low-tier hosts, and alert on new edges (ACL changes on privileged groups). One removed permission can delete thousands of attack paths at once, which is why the graph is as valuable to the blue team as to the red. Run collection only in environments you are authorized to assess.

Other graphs in security

  • Network reachability: which hosts can reach which, through firewall rules and routes.
  • Dependency graphs: which packages a project pulls in transitively, for supply-chain risk.
  • Call graphs: which functions can reach a dangerous sink, used by static analysis to trace tainted input from source to sink.
  • Attack trees: structured models of how a goal can be achieved, used in threat modeling.

Seeing these structures as graphs is the point: once drawn, the shortest-path question answers itself, for the attacker and the defender alike.