Access matrices, ACLs and capabilities
The access matrix sliced two ways, by object into access control lists and by subject into capability lists, with what each costs to store and where each is actually used.
- Read the same access matrix as an access control list and as a capability list.
- Explain what an ACL entry and a capability entry each store.
- Compare the storage cost of the dense matrix against its two sparse representations.
15 min read
Intuition
The access matrix from the previous topic is called “naive” in the lecture’s own slides for a reason: storing the full subjects-by-objects grid directly does not scale, because most cells in a real system are empty. Nobody actually keeps a grid where Sam’s row lists every object he has no access to. 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.
Mechanism
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 own 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 right
there in one place.
Mechanism
The matrix can equally be sliced by row instead: one subject’s rights across every object it can touch. The lecture does not name this the “capability list” directly, but the idea follows straight from the same access matrix, and it is the standard second half of this picture in the week’s own recommended reading (Anderson, Security Engineering, Chapter 6). A capability sits with the subject rather than the object, typically as a token or ticket the holder presents to prove what it may do, in contrast to an ACL, which 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.
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. Same underlying rights, two different ways of indexing them.
Exam detail
Storage cost has two different answers depending on what you’re comparing. Against the dense matrix, both an ACL and a capability list win: the matrix needs a cell for every subject-object pair, subjects times objects, even when almost all of them are empty, while an ACL or capability list holds only the pairs actually granted. Compared to each other, an ACL and a capability list cost exactly the same: they store the same sparse set of non-empty cells, just filed under a different key, object for an ACL, subject for a capability list. Build a matrix in the widget above and switch between the three views; the ACL and capability entry counts always move together.
Exam detail
Where each is actually used: ACLs are, in the unit’s own 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 once the lecture reaches mobile platforms: iOS apps are “granted specific capabilities through APIs”, and Android permissions are described as being “in effect capabilities” that grant access to device services such as SMS, the camera and the address book. That mobile usage is a per-subject (per-app) grant, the same shape as a capability list, even though the lecture never contrasts it with ACLs directly.
Compare
Sits with the object. Answers “who can do what to this one thing?” directly. This is how Unix, Windows and web-platform permissions work.
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.
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.”
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.
Aside
The widget’s storage-cost panel is the fastest way to build intuition here. Add a subject with rights on several objects, then a subject with almost none, and watch how the matrix cell count stays fixed at subjects times objects while the ACL and capability counts both track only what is actually granted.
Source
Week 3 notes PDF