Chapter 2 — Discrete mathematics
Lesson map
Lesson 02 published. Map, example, EX004.
flowchart TD
N0["Learning outcomes"]
N1["2.1 Sets and relations"]
N2["2.2 Composition and effective access"]
N3["2.3 Counting and role explosion"]
N4["2.4 Partial orders and hierarchies"]
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 and relations"]
N2["2.2 Composition and effective access"]
N3["2.3 Counting and role explosion"]
N4["2.4 Partial orders and hierarchies"]
N5["Synthesis"]
N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> Q["EX004"]
[Learning outcomes]
|
v
[2.1 Sets and relations]
|
v
[2.2 Composition and effective access]
|
v
[2.3 Counting and role explosion]
|
v
[2.4 Partial orders and hierarchies]
|
v
[Synthesis]
|
v
[Worked example] --> [Exercise EX004]
Learning outcomes
You will (1) model users, roles and permissions as sets and relations; (2) compose relations to find effective access; (3) count combinations that drive role growth.
2.1 Sets and relations
Access control is naturally described with sets. Users, roles and permissions are sets; assignments are relations between them. The user-to-role relation says who holds which role, and the role-to-permission relation says what each role grants. Composing them gives the user-to-permission relation: everything each person can actually do. Sandhu and colleagues (1996) built role-based access control models on exactly this structure. Writing access in this way lets Sana ask precise questions, such as which users can approve payments, rather than relying on the impression given by role names.
2.2 Composition and effective access
Effective access is often larger than anyone intended, because roles overlap. A person holding both a finance clerk role and a temporary project role may gain a permission that neither role was meant to provide in combination. By composing relations, Sana computes every user's effective permissions and compares them with what their job requires. The difference, permissions held but not needed, is excess access. Set difference is a simple operation, but applying it consistently across thousands of users reveals problems that manual review of role names would never find.
2.3 Counting and role explosion
With n permissions there are two to the power n possible permission sets. Even with thirty permissions, that is over a billion combinations. Organisations that create a new role whenever someone needs a slightly different set drift towards role explosion, with hundreds of roles that differ by one or two permissions. Counting shows why role design needs principles, such as roles based on job functions plus a small number of well-governed exceptions, rather than a role for every case. Linmouth's existing applications already show this pattern.
2.4 Partial orders and hierarchies
Role hierarchies let a senior role inherit the permissions of junior ones, forming a partial order. A finance manager role might inherit everything from finance clerk and add approval rights. Hierarchies reduce duplication, but inheritance also spreads permissions silently: adding a permission to a junior role grants it to every role above. Sana draws the hierarchy as a directed graph and checks that inheritance flows only in intended directions, and that no cycle exists, since a cycle would make two roles equivalent and confuse every later review.
Worked example
For users {u1, u2}, roles {clerk, project} and permissions {raise, approve, view}, Sana composes assignments to show that u2, holding both roles, can raise and approve payments, a combination neither role intended alone.
Synthetic case. Users, roles and permissions are synthetic.
Errors and limits
Reviewing role names instead of computing effective permissions misses combinations that arise from overlapping roles.
Exercises
- EX004 — Effective access. How is each user's effective access computed? Rubric: 3 = compose user-role with role-permission relations;; 2 = compose;; 1 = list roles;; 0 = none.
- EX005 — Permission sets count. How many possible permission sets exist with thirty permissions? Rubric: 3 = 2^30, over a billion;; 2 = 2^30;; 1 = 30;; 0 = none.
- EX006 — Hierarchy cycle. Why must a role hierarchy contain no cycle? Rubric: 3 = cycle makes roles equivalent and confuses review;; 2 = equivalence;; 1 = speed;; 0 = none.
Synthesis
Sets, relations and counting make access precise, expose excess and explain why roles must follow principles.
Continue studying — chapter 02 of 50
← Chapter 01 (draft) · Course chapter index · Chapter 03 (draft) →