Chapter 6 — Discrete structures
Lesson map
Lesson 06 published. Map, example, EX016.
flowchart TD
N0["Learning outcomes and connection"]
N1["6.1 Relations and graphs"]
N2["6.2 Breadth-first search"]
N3["6.3 Invariants"]
N4["6.4 State transitions"]
N5["Chapter synthesis"]
N0 --> N1 --> N2 --> N3 --> N4 --> N5
N5 --> EX["Worked example"]
EX --> Q["Exercise EX016"]
Logical drawing
flowchart LR
N0["Learning outcomes and connection"]
N1["6.1 Relations and graphs"]
N2["6.2 Breadth-first search"]
N3["6.3 Invariants"]
N4["6.4 State transitions"]
N5["Chapter synthesis"]
N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> Q["EX016"]
[Learning outcomes and connection]
|
v
[6.1 Relations and graphs]
|
v
[6.2 Breadth-first search]
|
v
[6.3 Invariants]
|
v
[6.4 State transitions]
|
v
[Chapter synthesis]
|
v
[Worked example] --> [Exercise EX016]
Learning outcomes and connection
You will be able to (1) model accounts, groups and systems as a directed graph; (2) compute which systems are reachable from a compromised principal; (3) express a safety property of access revocation as an invariant; and (4) reason about state transitions during containment. Chapter 5 introduced assets and authorization; this chapter gives you a precise structure for "who can reach what". Chapter 13 applies it to identity systems.
6.1 Relations and graphs
A relation on sets pairs elements: "user u is a member of group g", "group g has admin rights on server s". A directed graph G = (V, E) has vertices V and directed edges E. In access modelling, vertices are principals (users, service accounts, groups) and resources (servers, databases); an edge a → b means "a can act as, or act on, b". A path is a sequence of edges; b is reachable from a if a path exists. Reachability, not direct permission, is what matters when an account is compromised: a user who is in a group that can administer a server that stores a service account's credential can, in effect, become that service account.
6.2 Breadth-first search
The standard way to compute reachability is breadth-first search (BFS): start at the compromised vertex, visit its neighbours, then their neighbours, keeping a set of visited vertices so no vertex is processed twice. BFS also returns the shortest path to each vertex, which is useful for explaining why something is reachable.
In Lab 06 the parent dictionary records how each vertex was first reached, and the path function walks it backwards. That is why the output can explain that db-billing is reachable through nurse-12-admin, grp-helpdesk, srv-jump-01 and svc-backup, a route an analyst could check edge by edge. Depth-first search would find the same reachable set but not necessarily the shortest explanation.
6.3 Invariants
An invariant is a property that must hold in every state of a process. For revocation: "after step k, no vertex in the compromised set has a path to any production database except through an edge that is currently disabled". Stating the invariant tells you what to check after each change and catches the classic failure — removing the obvious edge while an indirect path remains.
Write the invariant before the first change, not after. In the nurse-12 case it is checked after each step, and Lab 06 shows it failing after step 1 and holding only after step 2.
6.4 State transitions
Containment is a sequence of state changes: disable account, rotate credential, remove group membership. Model each as a transition from graph Gᵢ to Gᵢ₊₁. Order matters: rotating a service-account secret before removing the attacker's ability to read the new secret is wasted work. A small state diagram (states and allowed transitions) also clarifies which steps are reversible.
In Lab 06 the graph after step 1 still allows a route to db-billing; only the state after step 2 contains the account. Recording each state with a timestamp gives the incident log a precise account of when containment actually held, which matters if later activity must be judged as before or after it.
6.5 Worked example and lab (synthetic): access graph
Fictional graph. nurse-12 is suspected compromised. Save as lab06.py.
# Lab 06 - reachability from a suspected compromised account (synthetic graph, stdlib only)
from collections import deque
EDGES = {
"nurse-12": ["grp-ward-staff"],
"grp-ward-staff": ["app-charting"],
"helpdesk-3": ["grp-helpdesk"],
"grp-helpdesk": ["srv-jump-01"],
"nurse-12-admin": ["grp-helpdesk"],
"app-charting": ["db-clinical"],
"srv-jump-01": ["svc-backup"],
"svc-backup": ["db-clinical", "db-billing"],
}
# nurse-12 also owns a second, privileged account on the same credential store:
EDGES["nurse-12"].append("nurse-12-admin")
def reach(start, edges, disabled=frozenset()):
seen, parent, q = {start}, {start: None}, deque([start])
while q:
v = q.popleft()
for w in edges.get(v, []):
if (v, w) in disabled or w in seen:
continue
seen.add(w); parent[w] = v; q.append(w)
return seen, parent
def path(parent, v):
out = []
while v is not None:
out.append(v); v = parent[v]
return " -> ".join(reversed(out))
seen, parent = reach("nurse-12", EDGES)
for target in ["db-clinical", "db-billing"]:
print(target, "reachable via", path(parent, target))
step1 = {("nurse-12", "grp-ward-staff")}
seen1, p1 = reach("nurse-12", EDGES, step1)
print("after disabling ward membership, db-billing reachable:", "db-billing" in seen1)
step2 = step1 | {("nurse-12", "nurse-12-admin")}
seen2, _ = reach("nurse-12", EDGES, step2)
print("after also cutting admin link, reachable:", sorted(seen2))
Expected output:
db-clinical reachable via nurse-12 -> grp-ward-staff -> app-charting -> db-clinical
db-billing reachable via nurse-12 -> nurse-12-admin -> grp-helpdesk -> srv-jump-01 -> svc-backup -> db-billing
after disabling ward membership, db-billing reachable: True
after also cutting admin link, reachable: ['nurse-12']
Interpretation: the obvious containment step (removing ward-staff membership) leaves the billing database reachable through the linked admin account and the backup service. The invariant "no path from nurse-12 to any database" holds only after step 2. In real environments, the graph is built from directory and permission exports, and edges such as "has a session on" or "can read credential of" are often missing from those exports — the graph is only as complete as its sources.
6.6 Common errors and limits
- Checking direct permissions only.
- Forgetting linked or secondary accounts belonging to the same person.
- Assuming the graph is complete; unknown edges (cached credentials, shared passwords) are the dangerous ones.
-
Cutting edges that break critical services without checking dependants (Chapter 24).
-
Treating a successful BFS run as proof of safety, when the result covers only the edges that were exported.
- Removing an edge in the model without confirming the change in the real directory, so the graph and the system disagree.
- Recording the final state but not the order of steps, which hides when containment actually held.
Exercises — chapter 6
Attempt each exercise before opening the worked results. Every case, organization, person, address and number in an exercise is synthetic unless a cited public source is named.
EX016 — Run and extend. Steps: run Lab 06; add edge app-charting → svc-backup and report whether step 2 still contains the account. Rubric: 3 = correct output and explanation (still contained, because nurse-12 cannot reach app-charting after step 1); 2 = output without explanation; 1 = not run; 0 = none.
EX017 — Write the invariant. Steps: state, in words and in set notation, the invariant that should hold after containment for a compromised set K and a protected set P. Rubric: 3 = "for all k in K and p in P, p is not reachable from k in the current graph", with note that reachability uses only enabled edges and that the graph's completeness is an assumption; 2 = direct edges only; 1 = vague; 0 = none.
EX018 — Order of transitions. Inputs: steps: (a) rotate svc-backup secret; (b) remove nurse-12-admin from grp-helpdesk; (c) terminate sessions on srv-jump-01. Steps: choose an order and justify it. Rubric: 3 = (b) and (c) before (a) so the attacker cannot read the new secret, with note on checking dependants; 2 = order right without reasons; 1 = (a) first; 0 = none.
Chapter synthesis
Model access as a directed graph, contain by reachability rather than direct permissions, write the invariant you must restore, and sequence transitions so that the attacker cannot follow your changes.
Continue studying — chapter 06 of 40
← Chapter 05 · Course chapter index · Chapter 07 →
Continue to the next authored lesson.