Access matrices, ACLs and capabilities

The naive matrix does not scale, so systems store only the non-empty cells

The access matrix from the previous topic is called “naive” in the lecture’s own slides: storing the full subjects-by-objects grid directly does not scale, because most cells in a real system are empty. What gets stored instead is only the non-empty cells, and there are exactly two ways to organise that sparse information: by object, or by subject.

An ACL slices the matrix by object, a capability list by subject

An access control list (ACL) slices the matrix by column. It belongs to one object, and each entry maps a user ID to the operations that user may perform, coarse (r/w/x) or very fine-grained depending on the system. The unit’s example is Table 2: an ACL for the object “Accounting Data”, where Sam holds rw, Alice holds rw and Bob holds r. Read an ACL and the answer to “who can touch this one object, and how” is in one place.

Slicing by row instead gives one subject’s rights across every object it can touch. The lecture does not name this the “capability list” directly, but it follows from the same matrix and is the standard second half of the picture in the week’s recommended reading (Anderson, Security Engineering, Chapter 6). A capability sits with the subject, typically as a token or ticket the holder presents to prove what it may do. An ACL sits with the object and is checked against whoever is asking.

An access control list is the matrix read one column at a time — for one object, who can do what. A capability list is the same matrix read one row at a time — for one subject, what they can touch. ACLs sit with the object (this is how Unix, Windows and web ACLs work); capabilities sit with the subject, as a token or ticket the holder presents. Both values above come straight out of the lecture's own Table 1 and Table 2.

Compare

ACL

Sits with the object. Answers “who can do what to this one thing?” directly. This is how Unix, Windows and web-platform permissions work.

Capability

Sits with the subject, as a token or ticket it holds. Answers “what can this one principal touch?” directly. Mobile app permission grants take this shape, even though the lecture doesn’t use the formal term for them.

Recall

A system needs to answer 'which files can Bob touch?' as fast as possible, for every request. Would an ACL-per-file layout or a capability-per-subject layout answer that question more directly?

A capability-per-subject layout answers it directly: Bob’s own row already lists everything he holds. An ACL-per-file layout would need every file’s ACL checked for a Bob entry, since the rights are indexed by object, not by subject.

Both sparse forms cost the same, and both beat the dense matrix

Against the dense matrix, both win: the matrix needs a cell for every subject-object pair (subjects times objects) even when almost all are empty, while an ACL or capability list holds only the pairs actually granted. Compared to each other, they cost exactly the same: the same non-empty cells, filed under a different key, object for an ACL, subject for a capability list. In the widget below, build a matrix and switch between the three views; the ACL and capability entry counts always move together while the matrix count stays at subjects times objects.

Access matrix explorer

Edit subjects, objects and rights, then compare the matrix, ACL and capability views of the same data.

Add subject

Add subject

Add object

Add object

Access matrix: rows are subjects, columns are objects, cells are rights held.

MatrixACL (per object)Capability (per subject)

The matrix above is the master copy. This panel confirms it is the same shape shown either way below.

Exam detail

Both slices come from the same source data. Sam’s row in Table 1, the naive matrix from the previous topic, is rwx on the Operating System, rwx on Accounts, rwx on the Program, rw on Accounting, rw on Data and r on the Audit Trail. That full row is Sam’s capability list. The Accounting column across all three users, rw, rw, r, is the ACL shown in Table 2.

Where each is used: ACLs are, in the unit’s words, common in “all UNIX systems (POSIX standards)” and Windows, and also appear in social networking sites, content management systems and enterprise resource management. Per-subject rights show up under a different name on mobile platforms: iOS apps are “granted specific capabilities through APIs”, and Android permissions are “in effect capabilities” that grant access to device services such as SMS, the camera and the address book. That is a per-subject (per-app) grant, the same shape as a capability list, even though the lecture never contrasts it with ACLs directly.

Pitfall

The word “capability” does double duty in this unit. On this page it names a way of storing the access matrix, by subject instead of by object. On the mobile platform pages later in this module it names a specific permission an app has been granted, like camera access. They are related, an app’s granted permissions are exactly its capability-list row, but a question asking about the access matrix wants the storage-strategy meaning, not “which device features can this app use.”