The Access Control Matrix

What it represents

The access matrix is an abstract model of protection. Rows are domains (subjects, principals — users or processes). Columns are objects (files, devices, processes, memory segments). Each cell specifies the access rights the domain has over the object — typically read, write, execute, or owner.

The matrix is sparse: most domains have no rights over most objects. A modern system with thousands of users and millions of files wastes space if the full matrix is stored literally.

Two concrete representations

Access Control Lists (ACLs)

Store the matrix by column — each object carries a list of (domain, rights) pairs. When a domain tries to access an object, the OS checks whether that domain appears in the object’s ACL and whether the requested right is granted.

Examples: UNIX file permissions (simplified ACL — three fixed domains: owner, group, other), Windows NTFS ACLs (fully general: arbitrary users and groups with arbitrary rights), AWS S3 bucket policies.

Advantages:

• Easy to revoke: change the object’s ACL and it takes effect immediately.
• The object’s owner controls access directly.
• Natural for most access patterns (many users, many files — attach access to the file).

Disadvantages:

• Checking access requires scanning the list (though caching mitigates this).
• Delegation is awkward: to delegate a file right, the owner must modify the ACL.

Capabilities

Store the matrix by row — each domain holds a set of capabilities, where a capability is an unforgeable token representing a specific right to a specific object. The domain presents the capability as a “key” or “ticket” when accessing the object.

Examples: UNIX file descriptors (once a file is opened, the process holds a capability-like descriptor; closing it destroys the capability), Hydra, KeyKOS, CHERI hardware capabilities.

Advantages:

• Natural delegation: passing a capability to another domain is straightforward (if the OS supports it).
• No need to scan an ACL on every access — possession of the capability proves the right.
• Fine-grained: a capability can grant one specific right (read-only) without implying others.

Disadvantages:

• Revocation is hard: if Alice passed a capability to Bob, taking it back requires revoking all capabilities that derive from the original, which can cascade.
• A domain may accumulate a large number of capabilities.

UNIX hybrid approach

UNIX uses a pragmatic hybrid:

• ACLs for file access at open() time: the kernel checks the owner/group/other permission bits against the process’s UID and GID.
• Capabilities for open files: the returned file descriptor is unforgeable by the process (it’s just an integer index into the kernel’s per-process file table) and can be passed to fork()-ed children or across UNIX-domain sockets via SCM_RIGHTS.

Which to use?

On a modern personal laptop, ACLs make more sense: a small number of users but a very large number of files. Each user carries membership in a handful of groups, and files grant access to those groups. Capabilities would require every user to carry an enormous set of capabilities — one per accessible file — which is impractical for POSIX file systems.

---

Past Paper Questions

2025 Paper 2 Question 3(a): The access matrix may be very large but also very sparse. State the two common representations of the access matrix, and explain which you would use to represent access rights for a modern personal laptop. [4 marks]

2019 Paper 2 Question 4(c): Describe how you might implement a capability system to protect files from access, give a possible API, and compare your proposal to the UNIX access control method. [8 marks]