Chapter 6 — Discrete structures | Bachelor's Critical infrastructure and sector security

Open, free learning for anyone who wants to protect people and technology. No account is required to read this text or its worked answers.

Lesson map

Lesson 06 published. Map, example, EX012.

flowchart TD
  N0["Learning outcomes and connection"]
  N1["6.1 Sets and relations"]
  N2["6.2 Logic"]
  N3["6.3 Graphs"]
  N4["6.5 Practical activity"]
  N5["Chapter synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5
  N5 --> EX["Worked example"]
  EX --> Q["Exercise EX012"]

Logical drawing

flowchart LR
  N0["Learning outcomes and connection"]
  N1["6.1 Sets and relations"]
  N2["6.2 Logic"]
  N3["6.3 Graphs"]
  N4["6.5 Practical activity"]
  N5["Chapter synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> Q["EX012"]

[Learning outcomes and connection]
    |
    v
[6.1 Sets and relations]
    |
    v
[6.2 Logic]
    |
    v
[6.3 Graphs]
    |
    v
[6.5 Practical activity]
    |
    v
[Chapter synthesis]
    |
    v
[Worked example] --> [Exercise EX012]

Learning outcomes and connection

After this chapter you can (1) use sets and set operations to reason about inventories and permissions; (2) write logical conditions and check them with truth tables; (3) model dependencies between services as a directed graph and compute what is affected when one node fails; and (4) recognise when an exhaustive check is feasible and when the number of states makes it impossible. It builds on Chapter 3's programming and prepares Chapter 13 (access), Chapter 22 (dependencies) and Chapter 28 (failure analysis).

6.1 Sets and relations

A set is a collection of distinct items. The devices on the clinical network form a set $C$; the devices past end of support form a set $U$; their intersection $C \cap U$ is the set to isolate first. The union $A \cup B$ collects items in either; the difference $A \setminus B$ keeps items in $A$ but not $B$. Access control is set reasoning: a user's effective permissions are the union of the permissions of their roles, and a separation-of-duties rule says certain pairs must never both be in that union (Chapter 13). A relation connects items of two sets — "user u holds role r", "service s depends on service t". Many security questions are questions about relations: who can reach what, what depends on what.

6.2 Logic

A proposition is true or false. Combine propositions with and ($\wedge$), or ($\vee$) and not ($\neg$). A rule such as "a payment above £10,000 is released only if it is created by one person and approved by a different person, or if it is an emergency transfer approved by two directors" is a logical expression; writing it formally exposes gaps ("what if the creator is also a director?"). A truth table lists every combination of inputs; with $n$ inputs it has $2^n$ rows. For 4 inputs that is 16 rows — easy. For 40 inputs it is about $10^{12}$ rows — impossible to check by hand, which is why complex systems need structure, testing and argument rather than exhaustive enumeration. De Morgan's laws — $\neg(A \wedge B) \equiv \neg A \vee \neg B$ — let you rewrite "not allowed" conditions as "allowed" conditions and check that both say the same thing.

6.3 Graphs

A graph is a set of nodes and edges. In a directed graph, edges have direction; we write $u \to v$ to mean "$v$ depends on $u$". Starting from a failed node, a breadth-first search visits every node reachable along edges: that set is everything that can be affected. The number of nodes reachable from a node is its reach; nodes with high reach are candidates for extra protection or backup. Graphs also expose single points of failure: a node whose removal disconnects services from what they need. Rinaldi, Peerenboom and Kelly's classic paper describes infrastructures as interdependent in exactly this sense — physical, cyber, geographic and logical (Rinaldi et al., 2001).

6.4 Worked example and Lab 3: Calder County dependencies (synthetic)

This case is synthetic. The CRP drew a first dependency map: the electricity substation feeds water pumps, the hospital's mains supply, the telecom exchange and rail signalling; the telecom exchange carries dispatch, card payments, water telemetry and the hospital's cloud image archive.

# Lab 3 - cross-sector dependency closure on a directed graph (synthetic Calder County, offline)
from collections import deque
# edge u -> v means "v depends on u"
DEPENDS = {
    "grid-substation-N": ["water-pumps", "hospital-main", "telecom-exchange", "rail-signalling"],
    "telecom-exchange": ["dispatch-cad", "card-payments", "water-telemetry", "hospital-pacs-cloud"],
    "water-pumps": ["hospital-water"],
    "water-telemetry": ["water-pumps"],
    "dispatch-cad": ["ambulance-dispatch"],
    "hospital-main": [],
    "card-payments": ["fuel-retail"],
    "rail-signalling": [], "hospital-water": [], "hospital-pacs-cloud": [],
    "ambulance-dispatch": [], "fuel-retail": [],
}
def affected(start):
    seen, q = {start}, deque([start])
    while q:
        for v in DEPENDS.get(q.popleft(), []):
            if v not in seen:
                seen.add(v); q.append(v)
    return sorted(seen - {start})
for node in ("grid-substation-N", "telecom-exchange", "water-telemetry"):
    a = affected(node)
    print(f"{node}: {len(a)} affected -> {', '.join(a)}")
fan = sorted(((len(affected(n)), n) for n in DEPENDS), reverse=True)[:3]
print("highest reach:", fan)

Expected output:

grid-substation-N: 11 affected -> ambulance-dispatch, card-payments, dispatch-cad, fuel-retail, hospital-main, hospital-pacs-cloud, hospital-water, rail-signalling, telecom-exchange, water-pumps, water-telemetry
telecom-exchange: 8 affected -> ambulance-dispatch, card-payments, dispatch-cad, fuel-retail, hospital-pacs-cloud, hospital-water, water-pumps, water-telemetry
water-telemetry: 2 affected -> hospital-water, water-pumps
highest reach: [(11, 'grid-substation-N'), (8, 'telecom-exchange'), (2, 'water-telemetry')]

Read the result carefully. The graph says can be affected, not will fail: it ignores backup power, storage and manual operation. That is deliberate — the first map finds where to look; Chapter 22 adds time and backup autonomy. It also reveals a modelling choice: water pumps depend on telemetry here only if they cannot run locally. Every edge is a claim that someone should be able to justify.

6.5 Practical activity

Add an edge you think is missing (for example, the hospital's water depends on the water-treatment works, which depends on the substation) and an alternative path (a second telecom exchange). Recompute reach. Write three sentences on what the change does and does not show.

Adding "treatment works → hospital water" and "substation → treatment works" raises the substation's reach further, while a second exchange removes nothing from the plain reachability count: the search still marks every node that one path can reach. That is the limitation EX012 asks you to explain, and it is the reason to write AND and OR dependencies differently.

6.6 Common errors and limits

Confusing edge direction ("depends on" versus "supplies"); write the convention at the top of every diagram.
Treating reachability as certainty of failure.
Building a graph from one organisation's view: other operators know dependencies you do not.
Trying to enumerate state spaces that are exponentially large.

In Lab 3 the convention line edge u -> v means "v depends on u" is what makes the 11-node reach of the substation readable; reversed, the same list would claim the substation depends on fuel retail. Reach of 11 means exposure, not failure, since the hospital has 72 hours of generator autonomy. The map is CRP's first view and lacks what CW and CPN engineers know. And the truth table argument scales the other way: 40 binary inputs give about a trillion rows.

Exercises — chapter 6

EX011 — Sets for triage. Objective: use set operations. Inputs: C = {INF-01, INF-02, IMG-01, IMG-02, ADM-02}; U = {INF-02, IMG-01, IMG-02, LAB-01, ADM-02}; K (devices with a known exploited flaw) = {IMG-01, ADM-02}. Steps: compute $C \cap U$, $(C \cap U) \cap K$ and $U \setminus C$; say which set you would act on first and why. Expected evidence: three sets and a reason. Rubric: 3 = all correct and priority to $(C \cap U) \cap K$ = {IMG-01, ADM-02}; 2 = one error; 1 = two errors; 0 = none.

EX012 — An alternative path. Objective: see how redundancy changes reach. Inputs: Lab 3. Steps: model that dispatch-cad can also use a satellite link independent of the exchange, so losing the exchange alone no longer stops dispatch. Explain why a simple reachability search cannot express this, and propose a modelling change. Expected evidence: explanation and proposal. Rubric: 3 = recognises OR-dependency (needs any one of several suppliers) versus AND-dependency, proposes nodes requiring all/any inputs; 2 = recognises problem only; 1 = edits edges incorrectly; 0 = none.

Chapter synthesis

Sets describe inventories and permissions; logic makes rules exact and checkable; graphs make dependencies visible and computable. Each model answers a narrower question than it seems to: reachability shows exposure, not failure, and exhaustive checking only works while the state space is small.