Chapter 2 — Discrete mathematics | Engineering AI and machine-learning 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 02 published. Map, example, EX004.

flowchart TD
  N0["Learning outcomes"]
  N1["2.1 Sets, functions and logic"]
  N2["2.2 Relations and graphs"]
  N3["2.3 Counting"]
  N4["2.4 Induction and invariants"]
  N5["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5
  N5 --> EX["Worked example"]
  EX --> Q["Exercise EX004"]

Logical drawing

flowchart LR
  N0["Learning outcomes"]
  N1["2.1 Sets, functions and logic"]
  N2["2.2 Relations and graphs"]
  N3["2.3 Counting"]
  N4["2.4 Induction and invariants"]
  N5["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> Q["EX004"]

[Learning outcomes]
    |
    v
[2.1 Sets, functions and logic]
    |
    v
[2.2 Relations and graphs]
    |
    v
[2.3 Counting]
    |
    v
[2.4 Induction and invariants]
    |
    v
[Synthesis]
    |
    v
[Worked example] --> [Exercise EX004]

Learning outcomes

You will (1) use sets, relations, functions and logic to describe system behaviour precisely; (2) express access and tool-use policies as predicates; (3) count possibilities to estimate search spaces; and (4) reason about graphs of data and control flow in AI systems.

2.1 Sets, functions and logic

A model is a function f: X → Y from an input set to an output set. A policy is a predicate P(user, action, resource) that is true when the action is allowed. Logical connectives (∧, ∨, ¬, →) and quantifiers (∀, ∃) let us write security properties exactly: "∀ tool call c issued by Wrench, Authorised(requesting_user(c), c)". Writing properties this way reveals ambiguities — what is the "requesting user" when the call was triggered by text in a supplier bulletin?

Sam resolves it by defining the requesting user as the person whose session started the conversation.

2.2 Relations and graphs

A directed graph of components (camera → preprocessing → model → alert queue → technician) shows where data flows and where trust changes. Paths from an untrusted source to a privileged sink are the routes an attacker can use; for language-model applications, the path "supplier bulletin → Wrench prompt → work-order tool" is exactly an indirect prompt-injection path (Greshake et al., arXiv:2302.12173). Reachability in graphs is computed by breadth- or depth-first search.

Drawing the graph first makes the search mechanical: mark every node whose content an outsider can influence, mark every node that can change something in the world, and list the paths between them. Each path found this way needs a control somewhere along it, and the graph shows where.

2.3 Counting

Combinatorics estimates search spaces. If an attacker can change any 3 of 100 features to one of 4 values, there are C(100,3) × 4³ = 161,700 × 64 ≈ 10.3 million variants — feasible to search by computer. Counting shows why "nobody will find the bad input" is not a defence.

Ten million variants can be evaluated in minutes on an ordinary computer if each model query is fast, so an attacker does not need cleverness, only patience and access to the model or a close copy of it. The same counting tells defenders where to limit queries: if each variant had to pass through a rate-limited interface allowing a thousand requests a day, exhaustive search would take decades, and the attacker would need to search much more cleverly.

2.4 Induction and invariants

An invariant is a property that holds before and after every step. "The work-order tool can only be called with a technician's session token" is an invariant; proving it holds for every code path (by induction over steps) is stronger than testing a few cases.

The induction has two parts. The base case checks that no tool call is possible before a session exists. The step shows that if every earlier call carried a valid token, the code path that issues the next call also attaches one and refuses otherwise. A test of a few calls cannot show that no path skips the check; an argument over every path can, provided the code paths are listed completely.

2.5 Worked example (synthetic NRS case)

Sam draws Wrench's data-flow graph with nodes for user chat, manuals, technician notes, supplier bulletins (external), the model and two tools (search, create_work_order). Two untrusted-to-privileged paths exist: bulletin → model → create_work_order and technician notes (editable by contractors) → model → create_work_order. Sam writes the property "∀ create_work_order calls, a human technician confirmed it" and marks both paths for controls.

The second path is easy to miss because technician notes look internal, but contractors can edit them, so they belong with untrusted inputs. The confirmation property places one control at the sink, which covers both paths at once, rather than trying to filter every untrusted source separately.

2.6 Errors and limits

Informal policies with hidden exceptions.
Forgetting indirect paths through data stores.
Underestimating search spaces that computers enumerate easily.

Hidden exceptions appear when a policy written as 'technicians may create work orders' turns out to mean 'except contractors on weekend shifts', which nobody wrote down. Indirect paths are missed when a graph shows only live connections and omits stores, such as notes saved today and read by the model tomorrow. Search spaces are underestimated by people who picture a human trying inputs by hand, rather than a program trying millions.

Exercises

EX004 — Predicate. Write a predicate stating that Wrench may only create work orders for assets in the requesting technician's depot. Rubric: 3 = correct quantified predicate; 2 = minor error; 1 = informal; 0 = none.
EX005 — Paths. List the untrusted-to-privileged paths in Sam's graph and one control for each. Rubric: 3 = both paths, sensible controls; 2 = one; 1 = vague; 0 = none.
EX006 — Counting. Count variants if an attacker changes any 2 of 50 features to one of 3 values. Rubric: 3 = C(50,2)×3² = 1,225×9 = 11,025; 2 = arithmetic slip; 1 = method only; 0 = none.

Synthesis

Discrete mathematics gives precise language for policies, data flows and search spaces — the basis for stating and checking AI-security properties instead of hoping for them.

Continue studying — chapter 02 of 50

← Chapter 01 (draft) · Course chapter index · Chapter 03 (draft) →