Protection, Access Control, and OS Security Basics

The access matrix is the reference model of protection. Let $S$ be the set of subjects (users, processes, or protection domains) and $O$ be the set of objects (files, memory segments, devices, even other processes). The matrix $M$ has one row per subject and one column per object; the entry $M[s, o]$ is the set of operations $s$ may perform on $o$ — for example $\{\text{read}, \text{write}\}$ or $\{\text{execute}\}$. Access control is then simply: before honoring subject $s$'s request to perform operation $op$ on object $o$, the reference monitor checks whether $op \in M[s, o]$. The access matrix is never stored as a literal 2-D array, because it is enormous and almost entirely empty — a system with a million files and a thousand users has $10^9$ cells, nearly all $\varnothing$. Every real protection mechanism is a compression strategy for this sparse matrix, and the compression axis you choose determines the mechanism's whole character:

• Store the matrix by column: for each object, keep the (short) list of subjects with nonzero rights. This is an Access Control List (ACL). It is cheap to answer "who can touch this file?" and cheap to revoke a user everywhere the object appears once — but expensive to answer "what can this process do, across the whole system?" without scanning every object.
• Store the matrix by row: for each subject, keep the (short) list of objects it may touch and with which rights, bundled as unforgeable tokens called capabilities. This is cheap to answer "what can this process do?" (just enumerate its capability list) and naturally supports delegation (hand a capability to another process) — but expensive to answer "who can touch this object?" and famously hard to revoke a single capability once copies have propagated.

A third, still-important idea is the principle of least privilege (Saltzer & Schroeder, 1975): a subject should be granted exactly the rights necessary for its current task, and those rights should be dropped the moment the task is done. Least privilege is not a mechanism but a design discipline — it tells you how to fill in the access matrix, whereas ACLs and capabilities tell you how to store it. A system can implement least privilege badly (a `sudo` script that grants full root for a one-line task) or well (a container that gets exactly one open file descriptor and nothing else); the mechanism does not save you from a sloppy policy.

The access-matrix operations

Beyond static lookup, an access-control model needs operations that change the matrix itself: granting, revoking, and creating subjects/objects. A minimal command language: ``` matrix M[Subjects][Objects] = all entries ∅

# Create a new object (e.g., a new file); owner gets full rights CREATE-OBJECT(owner, o): Objects.add(o) M[owner][o] = {read, write, execute, own}

# Grant a right — only allowed if the granter itself possesses "own"

# or the specific right with grant-permission on that object GRANT(granter, grantee, o, right): if "own" in M[granter][o] or right + ":grant" in M[granter][o]: M[grantee][o] = M[grantee][o] ∪ {right} else: deny("granter lacks authority")

# Revoke a right REVOKE(revoker, revokee, o, right): if "own" in M[revoker][o]: M[revokee][o] = M[revokee][o] \ {right} else: deny("revoker lacks authority")

# The reference-monitor check performed on EVERY access CHECK-ACCESS(subject, o, op): if op in M[subject][o]: allow() else: deny() ``` The `own` right is what makes the matrix dynamic: it lets a subject who created an object propagate and later withdraw rights to others, which is exactly how a Unix file owner can `chmod` and `chown` their own files.

ACL realization

Storing by column, each object carries a list of `(subject, rights)` pairs: ``` struct ACL_Entry: subject_id rights: bitset # e.g. {READ, WRITE, EXECUTE} struct Object: acl: list CHECK-ACCESS-ACL(subject, obj, op): for entry in obj.acl: if entry.subject_id == subject and op in entry.rights: return ALLOW return DENY # default-deny ``` Real ACL systems (NTFS, POSIX ACLs, AFS) add groups as a level of indirection, so a single ACL entry can name a group instead of every member individually — this is precisely a compression of the compression, because otherwise adding one employee to "Engineering" would require editing every file's ACL.

Capability realization

Storing by row, each subject (a process, or a protection domain) carries a list of capabilities, each naming an object and a right set: ``` struct Capability: object_ref # unforgeable pointer/handle, kernel-protected rights: bitset struct Process: cap_list: list CHECK-ACCESS-CAP(subject, cap_index, op): cap = subject.cap_list[cap_index] if op in cap.rights: return ALLOW_ON(cap.object_ref) return DENY ``` The crucial property is unforgeability: a user-level process must never be able to synthesize a capability out of thin air (e.g., by guessing a bit pattern) — capabilities must live in kernel memory, be tagged in hardware, or be cryptographically signed. This is what separates a capability system from "just an integer file descriptor a program could fake."

Unix permission bits, as a compressed ACL

Unix compresses the access matrix down to 9 bits per inode by pre-partitioning subjects into exactly three classes relative to each file: owner, group, other — plus three special bits (setuid, setgid, sticky). This trades expressiveness (you cannot list five arbitrary users with five different rights) for O(1) storage per file and O(1) check time, independent of how many users exist on the system. ``` struct Inode: owner_uid, group_gid mode: 9 bits # rwxrwxrwx (owner | group | other) special: {setuid, setgid, sticky} CHECK-ACCESS-UNIX(process, inode, op): if process.euid == inode.owner_uid: bits = mode.owner_bits else if process.egid in group_memberships(inode.group_gid): bits = mode.group_bits else: bits = mode.other_bits return op in bits # r, w, or x ``` Note the semantics: Unix checks the first matching class only — a directory owner who is accidentally excluded from `rwx` in the owner triad does not fall back to the (possibly more permissive) "other" bits. This single-class, first-match rule is what keeps the check to three comparisons and a bitmask test, regardless of file size or user-base size. `setuid` and `setgid` are the mechanism by which Unix punches a controlled hole in least privilege: when set on an executable, the process runs with the file owner's identity rather than the invoker's, e.g. `passwd` runs as root so an ordinary user can edit `/etc/shadow` through a narrow, audited interface. The sticky bit on a directory (`/tmp`) restricts deletion to the file's owner even though the directory itself is world-writable — a narrow patch for a specific attack (users deleting each other's temp files).

The confused-deputy and revocation problems, mechanically

Two structural failure modes recur across both models and deserve their own algorithmic framing.

Confused deputy. A subject $D$ (the "deputy," e.g. a compiler) holds a right to object $o$ (its own log file) that a caller $C$ lacks. If $C$ tricks $D$ into using its own authority on $C$'s behalf — e.g. by naming a different file as "the log file" via a parameter — $D$ unwittingly writes over an object $C$ could never touch directly. The bug is that ACL-style systems authorize based on ambient identity (who is $D$?) rather than on which specific right was actually passed for this call — capabilities fix this by making the deputy operate only on the exact object handle it was explicitly handed, with no implicit "my own privileges apply to whatever filename you typed."

Revocation. With ACLs, revoking alice's access to `f1` is one list deletion: $O(1)$ amortized, and immediate for every future check. With naively copied capabilities, once alice has handed a copy of the `f1` capability to five other processes, there is no central list to edit — you must either use indirection (all copies point through a revocable indirection object) or generation counters (each capability carries an object generation number; bumping the counter on the object invalidates all outstanding capabilities at once). Both fixes reintroduce a small ACL-like structure at the object, which is a fundamental theorem-in-practice: pure capability systems cannot get $O(1)$ selective revocation without some column-oriented bookkeeping.

Storage. A dense access matrix is $O(|S| \times |O|)$, intractable for real systems ($|S|, |O|$ each in the millions). ACLs cost $O(\sum_o |\{\text{nonzero rows for } o\}|)$, i.e., proportional to actual grants, typically $O(|O| \cdot \bar{k})$ where $\bar{k}$ is the average number of distinct subjects per object — small in practice because most files are touched by a handful of accounts or one group. Capabilities cost $O(|S| \cdot \bar{m})$ symmetrically, where $\bar{m}$ is average capabilities held per subject. Unix bits are $O(|O|)$ flat — 9 bits per file, independent of user count, because the compression discards subject-level granularity entirely in exchange for a fixed-size record.

Time. ACL lookup is $O(k)$ in the number of entries on that object's list (or $O(\log k)$ / $O(1)$ with a hash map keyed by subject), plus group-membership resolution, which is itself $O(g)$ for $g$ groups the subject belongs to. Capability lookup is $O(1)$ if the capability is presented directly by the caller (no search needed — the caller names the exact capability), which is why capability systems are attractive for performance-critical kernels: no per-call linear scan. Unix lookup is strictly $O(1)$: one identity comparison, one group-membership test bounded by a small constant, one bitmask AND.

Correctness argument. The essential invariant every reference monitor must uphold is:

Three properties are necessary for a mechanism to satisfy this invariant in practice, and each maps to a design requirement: 1. Complete mediation — every access path to $o$ must go through the check; if a process can reach the raw disk block bypassing the file system, the ACL/capability layer is vacuous. This is why kernels, not libraries, enforce file permissions: a user-mode library check can be skipped by calling the syscall directly. 2. Unforgeability of the identity/token used in the check — for ACLs, the subject's claimed UID must be attested by the kernel (not self-reported); for capabilities, the capability handle itself must be un-fabricable. Violating this collapses the whole model, since an attacker who can forge either side trivially satisfies $op \in M[s,o]$ for any $s$. 3. Atomicity relative to time — the check and the use must be atomic, or the matrix entry that was true at check-time may differ from the entry true at use-time (this is exactly the TOCTOU race discussed below). Formally we need

Given these three properties, correctness of any compression (ACL, capability, or Unix bits) reduces to showing the compressed structure is a faithful, queryable encoding of $M$: for ACLs, $\forall s: op \in M[s,o] \iff (s,op) \text{ appears in } o\text{'s list}$; for Unix bits, correctness holds only relative to the coarsened matrix where all non-owner, non-group subjects are unioned into a single "other" row — meaning Unix bits are provably correct for the policy they can express, but many policies (e.g., "alice and bob may write, carol may only read, everyone else denied") are simply inexpressible, not incorrectly enforced. This is the honest tradeoff: Unix bits sacrifice expressive power for a constant-time, constant-space guarantee, and no amount of clever engineering recovers the lost expressiveness without adding real ACL/capability machinery (POSIX ACLs, extended attributes) back on top.

Consider a small file server. Users: `alice` (uid 501), `bob` (uid 502, group `staff`), `carol` (uid 503, group `staff`). File `payroll.csv`, owned by alice, group `staff`, mode `640` (`rw-r-----`).

Step-by-step access-matrix view first, the ground truth we want:

This exact matrix is not expressible in 9 Unix bits, because Unix cannot exclude one member of a group while admitting the rest. Let's trace what actually happens under each mechanism.

Unix bits (mode 640, group staff). ``` CHECK-ACCESS-UNIX(carol, payroll.csv, READ): carol.euid (503) != owner_uid (501) -> not owner class carol.egid includes staff, file group = staff -> GROUP class applies group_bits = "r--" READ in "r--"? -> YES => ALLOW ``` Carol is granted read access even though the intended policy excludes her — the mechanism is correctly implementing Unix semantics but incorrectly implementing the desired policy, because the policy simply cannot be represented. The fix requires either a POSIX ACL (`setfacl -m u:carol:--- payroll.csv`, which adds an explicit deny-equivalent entry checked before the group bits) or moving carol out of `staff` (which may break other, unrelated permissions she legitimately needs) — illustrating why least privilege is often defeated not by weak enforcement but by coarse policy granularity.

ACL-based system (e.g., NTFS or POSIX ACL), storing the matrix column for `payroll.csv` directly: ``` payroll.csv.acl = [ (alice, rw), (bob, r), (carol, deny-all) ] CHECK-ACCESS-ACL(carol, payroll.csv, READ): scan list -> match (carol, deny-all) found first deny-all excludes READ -> DENY ``` The list is scanned in specificity order (explicit user entries checked before group entries), so carol's individual deny entry overrides the group-level allow that `staff` would otherwise confer — this is exactly the extra column-oriented bookkeeping an access matrix needs to express exceptions, and it costs one extra list entry, not a redesign.

Capability-based system. Suppose the file server hands out capabilities at login instead. Alice's process is minted `cap(payroll.csv, {read, write})`; bob's process gets `cap(payroll.csv, {read})`; carol's process is simply never minted a capability naming `payroll.csv` at all. ``` carol_process.cap_list = [ cap(other_file, {r,w}), ... ] # no entry for payroll.csv CHECK-ACCESS-CAP(carol, payroll.csv, READ): search cap_list for object_ref == payroll.csv -> not found return DENY # default-deny by absence, not by explicit rule ``` This achieves the same outcome as the ACL deny-entry, but via a different mechanism: absence of a capability, rather than an explicit denial rule. It is arguably safer against a class of bugs (there is no "forgotten deny entry to disable" — you cannot accidentally leave carol a capability she was never given), but it moves the burden onto whoever mints capabilities at login to get the initial grant set exactly right, and onto revocation infrastructure if carol is later untrusted after already holding a capability.

Every commodity operating system layers its security on the ideas above. Unix/Linux/macOS enforce the rwx model at the VFS layer for every file access; Linux additionally supports POSIX ACLs (`setfacl`/`getfacl`) for the cases 9 bits cannot express, and capabilities(7) (`CAP_NET_ADMIN`, `CAP_SYS_ADMIN`, etc.) which split root's monolithic superpower into fine-grained, individually grantable rights — a direct least-privilege refinement of the historically all-or-nothing setuid-root model. SELinux and AppArmor implement mandatory access control (MAC): a separate, kernel-enforced policy layer that constrains even root, addressing the classic weakness that discretionary ACLs let any owner grant away access arbitrarily. Android's permission model is a capability-flavored ACL hybrid: apps declare needed permissions, and the OS mediates every sensitive API call as a check against the granted set. Web browsers sandbox each tab/process with capability-style file-descriptor confinement (Chrome's `seccomp-bpf`, Capsicum on FreeBSD), so a compromised renderer cannot open arbitrary files — a textbook least-privilege deployment. Cloud IAM systems (AWS IAM, GCP IAM) are, structurally, ACLs at planetary scale: policies attached to resources (columns) and roles attached to principals (rows), with exactly the same revocation and confused-deputy failure modes described above appearing in real incident post-mortems (e.g., the "confused deputy" pattern recurring as cross-account role assumption bugs).

Ask the tutor: How would you redesign a specific vulnerable setuid program to follow least privilege correctly?