Chapter 6 — Discrete structures
Lesson map
Lesson 06 published. Map, example, EX016.
flowchart TD
N0["Learning outcomes"]
N1["6.1 Graphs of access"]
N2["6.2 Shortest attack paths"]
N3["Lab — Attack paths by breadth-first search"]
N4["6.3 Prioritising with graphs"]
N5["Synthesis"]
N0 --> N1 --> N2 --> N3 --> N4 --> N5
N5 --> EX["Worked example"]
EX --> Q["Exercise EX016"]
Logical drawing
flowchart LR
N0["Learning outcomes"]
N1["6.1 Graphs of access"]
N2["6.2 Shortest attack paths"]
N3["Lab — Attack paths by breadth-first search"]
N4["6.3 Prioritising with graphs"]
N5["Synthesis"]
N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> Q["EX016"]
[Learning outcomes]
|
v
[6.1 Graphs of access]
|
v
[6.2 Shortest attack paths]
|
v
[Lab — Attack paths by breadth-first search]
|
v
[6.3 Prioritising with graphs]
|
v
[Synthesis]
|
v
[Worked example] --> [Exercise EX016]
Learning outcomes
You will (1) model systems and access as graphs; (2) find attack paths with graph search; (3) use graph measures to prioritise controls.
6.1 Graphs of access
Dr Bellini shows how graphs model security. Nodes can be users, machines and data stores; edges can be logins, network connections or permissions. An attacker who controls one node can follow edges to others. Lucas builds a small synthetic graph of Fernway: a phished staff laptop, a shared file server, the warehouse management system, an admin workstation and the shop database. Edges represent permissions and network reachability. Drawing the graph makes paths visible that are hard to see in lists of rules spread across different systems and teams.
6.2 Shortest attack paths
Using breadth-first search, Lucas finds the shortest path from the phished laptop to the shop database. The lab below shows a three-hop path: laptop to file server, file server to admin workstation through a saved administrator credential, admin workstation to database. Shortest paths matter because attackers prefer easy routes. Removing the saved credential cuts this path; the search then finds a longer path through the warehouse system. Each change can be checked by rerunning the search, giving a precise way to evaluate whether a control actually blocks the route it targets.
Lab — Attack paths by breadth-first search
# BFS attack paths on a synthetic Fernway graph.
from collections import deque
def bfs(E, s, t):
prev, q = {s: None}, deque([s])
while q:
u = q.popleft()
if u == t:
p = [];
while u: p.append(u); u = prev[u]
return p[::-1]
for v in E.get(u, []):
if v not in prev: prev[v] = u; q.append(v)
E = {"staff-laptop": ["file-server", "warehouse-wms"], "file-server": ["admin-ws"],
"warehouse-wms": ["integration-svc"], "integration-svc": ["stock-api"], "stock-api": ["shop-db"], "admin-ws": ["shop-db"]}
p = bfs(E, "staff-laptop", "shop-db"); print(f"{len(p)-1} hops:", " -> ".join(p))
E["file-server"] = [] # saved admin credential removed
p = bfs(E, "staff-laptop", "shop-db"); print(f"{len(p)-1} hops:", " -> ".join(p))
Run with python3 lab_paths.py. Verified output:
3 hops: staff-laptop -> file-server -> admin-ws -> shop-db
4 hops: staff-laptop -> warehouse-wms -> integration-svc -> stock-api -> shop-db
6.3 Prioritising with graphs
Some nodes appear on many paths; securing them gives more benefit. Lucas counts how many shortest paths from staff laptops to sensitive data pass through each node. The admin workstation and the file server stand out. He recommends hardening the admin workstation and removing stored credentials from the file server first. Graph reasoning gives an objective basis for priorities, but Lucas notes that the graph is only as good as its edges: unknown connections, such as forgotten remote-access tools, would change the answer, which is why inventories matter.
Worked example
Lucas models Fernway as a graph, finds a three-hop path to the shop database, shows removal of a saved credential lengthens the path and prioritises two choke-point nodes.
Synthetic case. The graph and credentials are synthetic.
Errors and limits
Graphs omit edges nobody knows about. Path length is a rough proxy for attacker effort.
Exercises
- EX016 — Edge meaning. What can edges represent in a security graph? Rubric: 3 = logins, network connections or permissions;; 2 = two;; 1 = vague;; 0 = none.
- EX017 — Lab path change. What happened to the shortest path after removing the saved credential? Rubric: 3 = grew from 3 hops to 4 hops via the warehouse system;; 2 = longer;; 1 = unchanged;; 0 = none.
- EX018 — Choke points. Which nodes did Lucas prioritise and why? Rubric: 3 = admin workstation and file server, which lie on many shortest paths;; 2 = both;; 1 = random;; 0 = none.
Synthesis
Graph models turn scattered permissions into visible attack paths and objective priorities.
Continue studying — chapter 06 of 40
← Chapter 05 (draft) · Course chapter index · Chapter 07 (draft) →