Chapter 6 — Discrete structures
Lesson map
Lesson 06 published. Map, example, EX016.
flowchart TD
N0["Learning outcomes"]
N1["6.1 Graphs for access"]
N2["6.2 Breadth-first search"]
N3["Lab — Lab — role paths"]
N4["6.3 Lab result"]
N5["6.4 Why chains appear"]
N6["6.5 Using results"]
N7["Repeating the analysis"]
N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> N6 --> N7
N7 --> EX["Worked example"]
EX --> Q["Exercise EX016"]
Logical drawing
flowchart LR
N0["Learning outcomes"]
N1["6.1 Graphs for access"]
N2["6.2 Breadth-first search"]
N3["Lab — Lab — role paths"]
N4["6.3 Lab result"]
N5["6.4 Why chains appear"]
N6["6.5 Using results"]
N7["Repeating the analysis"]
N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> N6 --> N7 --> Q["EX016"]
[Learning outcomes]
|
v
[6.1 Graphs for access]
|
v
[6.2 Breadth-first search]
|
v
[Lab — Lab — role paths]
|
v
[6.3 Lab result]
|
v
[6.4 Why chains appear]
|
v
[6.5 Using results]
|
v
[Repeating the analysis]
|
v
[Worked example] --> [Exercise EX016]
Learning outcomes
You will (1) model identities and roles as a graph; (2) find paths to privileged roles; (3) reason about reachability; (4) use graph results to reduce privilege.
6.1 Graphs for access
In the cloud, identities can often assume other roles. Treat each identity and role as a node and each "may assume" permission as a directed edge. A path from a person to an administrator role means that person can become an administrator, even if no single permission says so directly.
In StudyHub's accounts, roles are often assumed by pipelines and automation as well as people, so chains can be long and hard to spot by reading policies one at a time. Modelling them as a graph turns the question "who can become administrator?" into a search that a program can answer for every identity.
6.2 Breadth-first search
Breadth-first search explores neighbours level by level and finds the shortest path. It is simple to implement with a queue and a set of visited nodes, and it always terminates on a finite graph.
The visited set is what guarantees termination: without it, two roles that can assume each other would send the search round in circles. Finding the shortest path also helps remediation, since a short chain is usually easier to explain and to break than a long one.
Lab — Lab — role paths
"""Find which identities can reach an admin role through role-assumption chains (BFS, stdlib only)."""
from collections import deque
can_assume = { # identity -> roles it may assume
"dev-alice": ["ci-runner"], "ci-runner": ["deployer"], "deployer": ["cluster-admin"],
"analyst-bo": ["reports-reader"], "reports-reader": [], "support-cy": ["ticket-bot"],
"ticket-bot": ["deployer"], "cluster-admin": [],
}
def path(start, goal="cluster-admin"):
q, seen = deque([[start]]), {start}
while q:
p = q.popleft()
if p[-1] == goal: return p
for n in can_assume.get(p[-1], []):
if n not in seen: seen.add(n); q.append(p + [n])
for who in ["dev-alice", "analyst-bo", "support-cy"]:
p = path(who)
print(f"{who:11} {'REACHES admin: ' + ' -> '.join(p) if p else 'cannot reach admin'}")
Run with python3 lab_graph.py. Verified output:
dev-alice REACHES admin: dev-alice -> ci-runner -> deployer -> cluster-admin
analyst-bo cannot reach admin
support-cy REACHES admin: support-cy -> ticket-bot -> deployer -> cluster-admin
6.3 Lab result
dev-alice reaches cluster-admin through dev-alice -> ci-runner -> deployer -> cluster-admin. support-cy also reaches it through support-cy -> ticket-bot -> deployer -> cluster-admin. analyst-bo cannot reach admin. The surprise is support-cy: a helpdesk account can become cluster administrator through a ticket automation bot.
The analyst-bo result matters too: it confirms that the analysis does not flag everyone, and that read-only roles stay contained. A check that found admin paths for every identity would suggest a mistake in the graph rather than a real problem. Nobody had designed this path deliberately.
6.4 Why chains appear
Roles are added one at a time for convenience. Each edge looks reasonable alone; the risky path only appears when they are combined. NIST SP 800-210 discusses the difficulty of reasoning about combined access rules in cloud systems.
The ticket-bot was given the deployer role so it could restart failing pods, a reasonable fix for a support problem. Nobody connected that to deployer's ability to become cluster-admin, so a helpdesk account inherited a path to full control. The graph makes such combinations visible before someone finds them by accident.
6.5 Using results
Breaking one edge breaks a path. The best edge to remove is one used by many risky paths and needed by few legitimate tasks.
In the lab, the edge from ticket-bot to deployer was used only by the support path, and the bot needed far less than deployment rights. Removing it broke the risky path without harming legitimate work. Removing deployer's link to cluster-admin would also break the path but would stop the pipeline from working. Samuel's recommendation names the edge, the reason it is safe to remove and the narrower role to replace it.
Repeating the analysis
The graph is rebuilt monthly from exports so new risky paths are found early.
Worked example
Tom's team finds the ticket-bot needed to restart pods, not deploy. They replace its link to deployer with a narrow restart role. Rerunning the analysis shows only dev-alice's pipeline path remains, which is expected and protected by review rules.
Synthetic case. Identities and roles are synthetic.
Errors and limits
Graphs built from exports miss conditions such as time limits; check details for each path.
Exercises
- EX016 — Edge meaning. What does an edge represent? Rubric: 3 = may assume permission; 2 = partial; 1 = vague; 0 = none.
- EX017 — Surprise path. Which path was surprising and why? Rubric: 3 = support-cy via ticket-bot; 2 = partial; 1 = vague; 0 = none.
- EX018 — Fix. How was it fixed? Rubric: 3 = ticket-bot given narrow restart role; 2 = partial; 1 = vague; 0 = none.
Synthesis
Graphs reveal privilege paths that single permissions hide.
Continue studying — chapter 06 of 40
← Chapter 05 (draft) · Course chapter index · Chapter 07 (draft) →