Chapter 6 — Discrete structures
Lesson map
Lesson 06 published. Map, example, EX016.
flowchart TD
N0["Learning outcomes"]
N1["6.1 Networks as graphs"]
N2["6.2 Directed edges and reachability"]
N3["6.3 Relations and policy"]
N4["6.4 Counting paths and pairs"]
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 Networks as graphs"]
N2["6.2 Directed edges and reachability"]
N3["6.3 Relations and policy"]
N4["6.4 Counting paths and pairs"]
N5["Synthesis"]
N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> Q["EX016"]
[Learning outcomes]
|
v
[6.1 Networks as graphs]
|
v
[6.2 Directed edges and reachability]
|
v
[6.3 Relations and policy]
|
v
[6.4 Counting paths and pairs]
|
v
[Synthesis]
|
v
[Worked example] --> [Exercise EX016]
Learning outcomes
You will (1) model networks as graphs; (2) reason about paths and reachability; (3) use relations for policy.
6.1 Networks as graphs
A graph has nodes connected by edges, and it is a natural model for networks. Priya draws the clinic network with devices and network groups as nodes and permitted connections as edges. Questions about security then become questions about graphs: can a visitor phone reach a clinical cart by any path, how many steps does it take, and which single edge would disconnect them if removed? Graph thinking moves attention from individual rules to the overall shape of what can reach what, which is often where design problems become obvious.
6.2 Directed edges and reachability
Network connections usually have a direction: a staff laptop may open a connection to the booking server, but the server should not open connections to laptops. Directed graphs capture this. Reachability means there is some path following the arrows from one node to another, possibly through intermediate nodes. Priya learns that removing a direct edge is not enough if an indirect path remains; for example, a visitor phone blocked from the clinical network might still reach it through a shared printer that both groups can use. Reachability must be checked over all paths.
6.3 Relations and policy
A relation is a set of ordered pairs, and a firewall policy can be described as a relation between source groups and destination services. Properties of relations help reasoning. A policy that is not symmetric allows connections one way only. A transitive closure computes everything reachable through any number of hops, which matches the reachability question above. Writing the policy as a relation lets Priya compare the intended policy with the configured one as two sets of pairs and list exactly the pairs that differ.
6.4 Counting paths and pairs
With four groups, there are twelve ordered pairs of different groups. Priya counts how many are needed for clinic work and finds only four: staff to booking, clinical to lab results, staff and clinical to the internet. The shared wireless network effectively allows all twelve. Counting the difference between what is allowed and what is needed gives a simple measure of excess access, which she will use later to show how much a redesign reduces exposure, in the same way that larger projects count reachable zone pairs.
Worked example
Priya's graph shows that removing the visitor-to-clinical edge still leaves a path through the shared printer, so the printer must be moved or restricted.
Synthetic case. The graph is synthetic.
Errors and limits
Checking only direct rules misses indirect paths through shared devices.
Exercises
- EX016 — Indirect path. Why is removing a direct edge not always enough? Rubric: 3 = indirect path via shared node remains;; 2 = other paths;; 1 = says it is enough;; 0 = none.
- EX017 — Ordered pairs count. How many ordered pairs of distinct groups exist with four groups? Rubric: 3 = twelve, four times three;; 2 = 12;; 1 = 16;; 0 = none.
- EX018 — Excess access measure. How can excess access be measured simply? Rubric: 3 = allowed pairs minus needed pairs;; 2 = compare;; 1 = vague;; 0 = none.
Synthesis
Graphs and relations let network policies be checked for reachability and excess access.
Continue studying — chapter 06 of 40
← Chapter 05 (draft) · Course chapter index · Chapter 07 (draft) →