Chapter 2 — Discrete mathematics | Engineering Security architecture and engineering

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 Access as a relation"]
  N2["2.2 Transitive closure"]
  N3["Lab — Indirect rights via transitive closure"]
  N4["2.3 Separation of duties as sets"]
  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 Access as a relation"]
  N2["2.2 Transitive closure"]
  N3["Lab — Indirect rights via transitive closure"]
  N4["2.3 Separation of duties as sets"]
  N5["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> Q["EX004"]

[Learning outcomes]
    |
    v
[2.1 Access as a relation]
    |
    v
[2.2 Transitive closure]
    |
    v
[Lab — Indirect rights via transitive closure]
    |
    v
[2.3 Separation of duties as sets]
    |
    v
[Synthesis]
    |
    v
[Worked example] --> [Exercise EX004]

Learning outcomes

You will (1) represent access rights as relations and graphs; (2) compute transitive closure to find indirect access; (3) use set operations to check separation of duties.

2.1 Access as a relation

Daniel shows Sofia that an access-control list is a relation: a set of pairs (subject, object). Group membership is another relation: (user, group). Groups can contain groups. Writing these as sets lets Sofia reason precisely. If user ana is in group fare-ops, and fare-ops is in group fare-admins, and fare-admins can modify tariff tables, then ana can modify tariffs, even though no single entry says so. Discrete mathematics gives the tool for this: composition of relations and transitive closure, which make indirect rights visible instead of leaving them buried in nested groups that nobody reads.

2.2 Transitive closure

The transitive closure of a relation adds every pair reachable through a chain. Sofia writes a small Python program that takes Corvia's synthetic nested group memberships and computes, for every user, all groups they belong to directly or indirectly, then the objects those groups can access. The lab below runs on a synthetic directory and shows one contractor account inheriting tariff-modification rights through three levels of nesting. The audit had missed it because reviewers looked only at direct memberships. Closure computations of this kind underlie many commercial access-review tools, but understanding them lets an engineer check the tools.

Lab — Indirect rights via transitive closure

# Transitive closure of synthetic nested groups; find indirect tariff rights and SoD conflicts.
member = {"ana": {"fare-ops"}, "ben": {"tariff-approvers"}, "contractor-07": {"vendor-support"},
          "vendor-support": {"field-tech"}, "field-tech": {"fare-ops"}, "fare-ops": {"fare-admins"},
          "dina": {"tariff-approvers", "fare-ops"}}
rights = {"fare-admins": {"tariff:create"}, "tariff-approvers": {"tariff:approve"}}
def closure(x, seen=None):
    seen = seen or set()
    for g in member.get(x, ()):
        if g not in seen: seen.add(g); closure(g, seen)
    return seen
users = ["ana", "ben", "contractor-07", "dina"]
eff = {u: set().union(*(rights.get(g, set()) for g in closure(u))) for u in users}
for u in users: print(f"{u:14} groups={len(closure(u))} rights={sorted(eff[u])}")
create = {u for u in users if "tariff:create" in eff[u]}; approve = {u for u in users if "tariff:approve" in eff[u]}
print("create & approve conflict:", sorted(create & approve))

Run with python3 lab_closure.py. Verified output:

ana            groups=2 rights=['tariff:create']
ben            groups=1 rights=['tariff:approve']
contractor-07  groups=4 rights=['tariff:create']
dina           groups=3 rights=['tariff:approve', 'tariff:create']
create & approve conflict: ['dina']

2.3 Separation of duties as sets

Corvia requires that nobody can both create a tariff change and approve it. In set terms, the set of users able to create and the set able to approve must be disjoint. Sofia computes both sets from the closure and their intersection. A non-empty intersection is a violation. This is the separation of privilege principle from Saltzer and Schroeder (1975) expressed as a simple set test. She notes that set reasoning catches structural violations but not collusion between two people, which needs process controls such as logging and review.

Worked example

Sofia computes the closure of synthetic nested groups, finds a contractor with indirect tariff rights and tests create and approve sets, finding dina in both.

Synthetic case. Users, groups and rights are synthetic; Saltzer and Schroeder (1975) is real.

Errors and limits

Closure assumes memberships are current; stale data hide or invent rights. Disjoint sets do not prevent collusion.

Exercises

EX004 — Hidden right. Which account gained tariff rights indirectly in the lab, and through how many levels?
Show marking criteria
Rubric: 3 = contractor-07, through a chain of four groups ending in fare-admins;; 2 = account;; 1 = vague;; 0 = none.
EX005 — SoD test. How is separation of duties expressed with sets?
Show marking criteria
Rubric: 3 = creators and approvers sets must be disjoint; intersection empty;; 2 = disjoint;; 1 = union;; 0 = none.
EX006 — Collusion gap. What does a disjoint-set check fail to prevent?
Show marking criteria
Rubric: 3 = collusion between two different people;; 2 = collusion;; 1 = vague;; 0 = none.

Synthesis

Relations, closure and set tests turn tangled access rules into precise, checkable statements.

Continue studying — chapter 02 of 50

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