◇ OpenCyber Academy
Bachelor's · Chapter 6 · English

Chapter 6 — Discrete structures

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 6 — Discrete structures

Lesson map

Lesson 06 published. Map, example, EX016.

flowchart TD
  N0["Learning outcomes"]
  N1["6.1 Sets and relations"]
  N2["6.2 Graphs"]
  N3["6.3 Search on graphs"]
  N4["6.4 Counting"]
  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 Sets and relations"]
  N2["6.2 Graphs"]
  N3["6.3 Search on graphs"]
  N4["6.4 Counting"]
  N5["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> Q["EX016"]

[Learning outcomes]
    |
    v
[6.1 Sets and relations]
    |
    v
[6.2 Graphs]
    |
    v
[6.3 Search on graphs]
    |
    v
[6.4 Counting]
    |
    v
[Synthesis]
    |
    v
[Worked example] --> [Exercise EX016]

Learning outcomes

You will (1) use sets, relations and graphs to model systems; (2) express access rules as relations and check them; (3) find paths from untrusted inputs to sensitive actions in a graph; and (4) count possibilities to judge whether brute force is feasible.

6.1 Sets and relations

An access-control rule is a relation between subjects, actions and objects: (patient P, book, own appointment) is allowed; (patient P, view, other patient's record) is not. Writing rules as sets of allowed triples makes them checkable by program and exposes missing cases.

Once the rules are a set, a program can check every request against it and list any action that has no rule at all. Rina's first attempt found that "cancel" had no rule for patients cancelling another person's appointment, which the prose policy had simply not mentioned. Adding an explicit denial closed the gap, and the set became the reference for her booking checks.

6.2 Graphs

A graph has nodes and edges. Draw an AI system as a directed graph: user → chatbot → model → booking tool → scheduling system, plus document store → model. A path from an untrusted node (a public web page, an uploaded document) to a sensitive node (booking tool) is a potential attack route. Indirect prompt injection follows exactly such paths (Greshake et al., arXiv:2302.12173).

Drawing the graph made one edge visible that the architecture document had missed: partner organisations upload documents into the store that the model reads.

6.3 Search on graphs

Breadth-first search finds all nodes reachable from a start node. Running it from every untrusted node and checking whether sensitive nodes are reachable is a simple, automatable architecture check.

The cost grows with the number of nodes and edges, so even large systems can be checked in seconds. The value is in keeping the graph accurate: a new upload source or tool must be added as soon as it exists, or the search reports a clean result for a system that no longer matches it. Rina reruns the check whenever the architecture map changes and keeps the output with the map.

6.4 Counting

If a booking code has 6 digits, there are 10⁶ possibilities; at 10 guesses per second an attacker needs about 28 hours to try them all, so rate limits and lockouts matter. Counting turns intuition into numbers.

With a lockout after five wrong guesses, an attacker gets five tries per account instead of a million, a success chance of five in a million. The same arithmetic applies to guessing patient identifiers through the chatbot: if identifiers are short and sequential, enumeration is cheap. Rina includes such calculations in her reviews so rate-limit settings rest on numbers rather than feel.

6.5 Worked example (synthetic LCH case)

Rina listed Ask Lumen's nodes and edges and ran a reachability check by hand. Two untrusted sources reached the booking tool: patient chat (expected, controlled by authentication) and clinic-document uploads by partner organisations (unexpected). Partner uploads could contain instruction-like text that the model might follow. LCH added review for partner documents and kept the booking tool behind a policy check tied to the logged-in patient.

The second path explains why both controls were kept rather than one: review lowers the chance of hostile text, the policy check limits its effect.

6.6 Errors and limits

Prose rules leave cases undefined, as the missing cancel rule showed. Graphs that omit uploads and data stores miss the very route by which indirect prompt injection reaches a tool. Underestimating enumeration speed leads to weak limits on codes and identifiers; a six-digit code without rate limits falls in about a day at only ten guesses per second, and far faster with more.

Exercises

Synthesis

Discrete structures give exact tools — relations for rules, graphs for data flow, counting for feasibility — that make AI-system weaknesses visible.

Continue studying — chapter 06 of 40

← Chapter 05 (draft) · Course chapter index · Chapter 07 (draft) →