Part 4 of 7 · 4 min read
The access matrix
Think of a grid in a school office. The rows are pupils, the columns are rooms, and each cell says whether the pupil may enter. To see who may enter the lab, read the column. To see where a pupil may go, read the row. The analogy stops in one place: a school grid has hundreds of cells, while a computer has billions.
In plain words: The access matrix is a model with a row for each subject (a user or process), a column for each object (a file, a device, a process), and in each cell the set of rights that the subject has on the object. It is the full policy in one picture. It is far too large and too empty to store as a table, so real systems store it in pieces. Cutting it by column gives an access control list (ACL): for each object, a list of subjects and their rights. Cutting it by row gives a capability list: for each subject, a list of objects and rights.
A worked example. The program below holds a matrix of four subjects and four objects, prints both cuts, and answers two questions.
#include <stdio.h>
#include <string.h>
#define S 4
#define O 4
static const char *subj[S] = {"alice", "bob", "carol", "daemon"};
static const char *obj[O] = {"report", "payroll", "printer", "logfile"};
/* The access matrix: row = subject, column = object. r = read, w = write, x = use. */
static const char *m[S][O] = {
{"rw", "", "x", "r"},
{"r", "", "x", ""},
{"r", "rw", "", "r"},
{"", "", "x", "w"},
};
static int allowed(int s, int o, char right) { return strchr(m[s][o], right) != NULL; }
int main(void) {
printf("Access control lists (the matrix read by column):\n");
for (int o = 0; o < O; o++) {
printf(" %-8s:", obj[o]);
for (int s = 0; s < S; s++) if (m[s][o][0]) printf(" %s(%s)", subj[s], m[s][o]);
printf("\n");
}
printf("Capability lists (the matrix read by row):\n");
for (int s = 0; s < S; s++) {
printf(" %-8s:", subj[s]);
for (int o = 0; o < O; o++) if (m[s][o][0]) printf(" %s(%s)", obj[o], m[s][o]);
printf("\n");
}
printf("bob may write report? %s\n", allowed(1, 0, 'w') ? "yes" : "no");
printf("carol may write payroll? %s\n", allowed(2, 1, 'w') ? "yes" : "no");
int cells = 0, empty = 0;
for (int s = 0; s < S; s++) for (int o = 0; o < O; o++) { cells++; if (!m[s][o][0]) empty++; }
printf("%d of %d cells are empty\n", empty, cells);
return 0;
}
Output:
Access control lists (the matrix read by column):
report : alice(rw) bob(r) carol(r)
payroll : carol(rw)
printer : alice(x) bob(x) daemon(x)
logfile : alice(r) carol(r) daemon(w)
Capability lists (the matrix read by row):
alice : report(rw) printer(x) logfile(r)
bob : report(r) printer(x)
carol : report(r) payroll(rw) logfile(r)
daemon : printer(x) logfile(w)
bob may write report? no
carol may write payroll? yes
6 of 16 cells are empty
Six of the 16 cells are empty, so more than a third of the table holds nothing. In a large system it is much emptier. With 1,000 users and 1,000,000 objects the matrix has 1,000,000,000 cells. If 0.1% of them hold a right, only 1,000,000 entries matter, and at 8 bytes each they need 8 MB, while a full table of single bits would need 125 MB.
The key lines. Both lists carry the same information. They differ in which question is easy to answer.
Access matrix
The access matrix is a model of protection in which rows are subjects, columns are objects and each cell holds the rights of that subject on that object. Real systems store it by columns as access control lists, or by rows as capability lists.
Example: the cell for alice and report holds rw, so alice may read and write the report.
Check yourself: 1. What does one column of the matrix give? 2. What does one row of the matrix give? 3. Why is the full matrix not stored as a table?