Chapter 2 — Discrete mathematics | Engineering 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.

Chapter 2 — Discrete mathematics

Lesson map

Lesson 02 published. Map, example, EX003.

flowchart TD
  N0["Learning outcomes and connection"]
  N1["2.1 Logic is the language of permissives"]
  N2["2.2 Graphs model dependency"]
  N3["2.5 Practical activity: Lab 2"]
  N4["Chapter synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4
  N4 --> EX["Worked example"]
  EX --> Q["Exercise EX003"]

Logical drawing

flowchart LR
  N0["Learning outcomes and connection"]
  N1["2.1 Logic is the language of permissives"]
  N2["2.2 Graphs model dependency"]
  N3["2.5 Practical activity: Lab 2"]
  N4["Chapter synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> Q["EX003"]

[Learning outcomes and connection]
    |
    v
[2.1 Logic is the language of permissives]
    |
    v
[2.2 Graphs model dependency]
    |
    v
[2.5 Practical activity: Lab 2]
    |
    v
[Chapter synthesis]
    |
    v
[Worked example] --> [Exercise EX003]

Learning outcomes and connection

After this chapter you can (1) write interlock and permissive conditions as Boolean expressions and check them exhaustively with a truth table; (2) model infrastructure dependencies as a directed graph and compute what fails when one node fails; (3) use sets, relations and counting to bound how many states a control system can be in; and (4) state precisely when an exhaustive check is feasible and when it is not. The chapter builds on Chapter 1's stock-and-flow view and prepares Chapter 4, where you will implement these models in code.

2.1 Logic is the language of permissives

Control systems are full of rules of the form "the pump may run only if…". Write them as Boolean expressions. Let $H$ = level above high limit, $S$ = suction pressure low, $P$ = remote permit present, $M$ = local manual selected. A typical rule is $\text{RUN} = \neg H \wedge \neg S \wedge (P \vee M)$. Two rules are equivalent if they agree on every input; De Morgan's laws ($\neg(A\wedge B) = \neg A \vee \neg B$) let you rewrite trip conditions as permissives. With four inputs there are $2^4 = 16$ states, and a truth table checks every one. Security engineering adds a question safety engineering already asks: which input can an attacker influence? If $P$ arrives over a network, then $P \vee M$ means a forged permit is sufficient to start the pump whenever $H$ and $S$ are false. That may be acceptable — the physical trips still hold — or it may not, if running at that moment causes a pressure transient.

2.2 Graphs model dependency

A directed graph $G = (V, E)$ has nodes and arrows. Draw an arrow from $a$ to $b$ when $a$ needs $b$ to function. The set of things impacted when $b$ fails is everything that can reach $b$ along arrows — its ancestors in this orientation. Breadth-first search computes that set in time proportional to the number of edges. Rinaldi, Peerenboom and Kelly (2001) distinguish physical, cyber, geographic and logical interdependencies between infrastructures; a dependency graph is the simplest model that can hold all four, as long as you label each edge with its type.

Graph vocabulary you will use: path, cycle (a loop of dependency — for example, the telemetry network needs grid power and the grid operator's restoration needs telemetry), in-degree and out-degree, cut vertex (a node whose removal disconnects the graph) and strongly connected component. A cut vertex in a supply graph is a single point of failure.

2.3 Counting, state spaces and their limits

A system with $n$ binary inputs has $2^n$ input states; with 30 inputs that is over a billion. Add internal memory (timers, latches) and the state space grows faster. Exhaustive checking is excellent for small interlocks and impossible for whole plants; for those you use structure (decomposition, invariants) and sampling (Chapter 30). The pigeonhole principle gives quick security bounds: a 16-bit message counter wraps after 65,536 messages, so at one message per second it repeats within about 18 hours, after which a replay check based only on that counter fails.

2.4 Worked example: Lowmarsh dependencies (synthetic)

LRWA's engineers list what St Brenna's Hospital supply depends on: Hollin Hill reservoir and the direct feed from PS4; Hollin Hill depends on PS3; each pump station needs grid power and its RTU; both RTUs talk over a private LTE network that is itself powered from grid feeder F1. Lab 2 encodes this and computes the impact set of each failure. Losing feeder F1 takes out the LTE network as well as PS3 — so the "redundant" telemetry for PS4, which is on feeder F2, is lost too. The two-feeder design looked diverse on the electrical drawing; the graph shows a common dependency through communications.

2.5 Practical activity: Lab 2

# Lab 2 - dependency closure and an interlock truth table (synthetic Lowmarsh assets, offline)
from collections import deque
from itertools import product
DEPENDS = {  # asset: assets it needs in order to work
    "hospital_supply": ["hollin_res", "ps4"],
    "hollin_res": ["ps3"], "ps4": ["grid_f2", "rtu4"], "ps3": ["grid_f1", "rtu3"],
    "rtu3": ["lte"], "rtu4": ["lte"], "lte": ["grid_f1"], "fenwick_wtw": ["grid_f1", "chlorine"],
    "ps3_feed": ["fenwick_wtw"],
}
def impacted(failed):
    users = {}
    for a, ds in DEPENDS.items():
        for d in ds: users.setdefault(d, []).append(a)
    seen, q = {failed}, deque([failed])
    while q:
        n = q.popleft()
        for u in users.get(n, []):
            if u not in seen: seen.add(u); q.append(u)
    return sorted(seen - {failed})
for f in ("grid_f1", "lte", "grid_f2", "chlorine"):
    print(f"{f:9} -> {impacted(f)}")
# Pump P3 may run iff level below high AND suction not low AND (remote permit OR local manual)
rows = [(h, s, p, m, (not h) and (not s) and (p or m)) for h, s, p, m in product([0, 1], repeat=4)]
print("states allowing run:", sum(r[4] for r in rows), "of", len(rows))

Expected output:

grid_f1   -> ['fenwick_wtw', 'hollin_res', 'hospital_supply', 'lte', 'ps3', 'ps3_feed', 'ps4', 'rtu3', 'rtu4']
lte       -> ['hollin_res', 'hospital_supply', 'ps3', 'ps4', 'rtu3', 'rtu4']
grid_f2   -> ['hospital_supply', 'ps4']
chlorine  -> ['fenwick_wtw', 'ps3_feed']
states allowing run: 3 of 16

Only 3 of 16 input states allow the pump to run: those with $H = S = 0$ and at least one of $P, M$.

Read the impact list for feeder F1 slowly. It contains the LTE network, both RTUs and PS4, even though PS4 itself is powered from feeder F2, because PS4's RTU reaches the control room only through LTE. That is the hidden common dependency the worked example describes. The truth table result is equally concrete: three of sixteen states allow the pump to run, and every one of them needs the high-level and low-suction inputs to be false, so a forged remote permit alone can never start the pump into a trip condition.

2.6 Common errors and limits

Drawing arrows in mixed directions ("feeds" versus "depends on") in one graph.
Treating two paths as redundant without checking shared nodes further down.
Testing an interlock with "typical" cases only, when the table is small enough to test all.
Forgetting that a graph models whether something works, not how well: degraded modes need weights or states (Chapter 22).
Counter and identifier sizes chosen without counting how long until they wrap.

At LRWA these mistakes have direct consequences: a graph that mixes arrow directions would report that losing PS4 harms feeder F2, and a review that stopped at the electrical drawing would have missed the shared LTE dependency entirely.

Exercises — chapter 2

EX003 — Interlock rewrite. Objective: manipulate Boolean expressions and reason about network-borne inputs. Inputs: RUN in §2.1. Steps: (1) write the trip condition $\neg\text{RUN}$ in sum-of-products form using De Morgan's laws; (2) list the states in which a forged remote permit changes the outcome; (3) propose a change that keeps remote operation but requires a second, independent condition. Expected evidence: expressions, list and proposal. Rubric: 3 = correct algebra, exactly the right states, proposal independent of the same network path; 2 = one slip; 1 = algebra only; 0 = none.

EX004 — Diversity check. Objective: find hidden common dependencies. Inputs: Lab 2. Steps: (1) add a battery-backed satellite link sat that only RTU4 uses, with no grid dependency; (2) rerun and report the impact of grid_f1; (3) state whether the hospital supply now survives loss of F1 and what the graph still does not tell you. Expected evidence: modified dictionary, output, two sentences. Rubric: 3 = correct modelling (rtu4 depends on lte or sat requires noting that this simple graph models AND-dependencies only), conclusion honest about that limit; 2 = correct output, limit missed; 1 = not run; 0 = none.

Chapter synthesis

Write rules as logic and dependencies as graphs, then let the computer check them. Small interlocks can and should be checked exhaustively; whole systems cannot, and the counting tells you so. Look for shared nodes behind apparently diverse paths, label edges with their type, and ask of every input which ones arrive over a network an adversary might reach.

Continue studying — chapter 02 of 50

← Chapter 01 · Course chapter index · Chapter 03 →

Continue to the next authored lesson.