Loading learning content...
Every modern operating system faces a fundamental question: Who is allowed to do what to which resources? This seemingly simple question hides enormous complexity. A system may have thousands of users, millions of files, hundreds of running processes, and countless combinations of possible operations. How can we systematically represent, reason about, and enforce these access decisions?
In 1971, Butler Lampson formalized an elegant solution in his seminal paper "Protection." He introduced the Access Matrix Model—a mathematical abstraction that captures the complete protection state of a system in a simple two-dimensional structure. This model has become the theoretical foundation upon which all modern access control mechanisms are built, from Unix file permissions to Windows ACLs, from database authorization to cloud IAM policies.
By the end of this page, you will deeply understand the Access Matrix Model's theoretical foundations, its structural components, and how it provides a unified framework for reasoning about any access control scenario. You'll see how this 50-year-old abstraction remains the conceptual backbone of modern security systems and why every security professional must understand it.
Before examining the Access Matrix, we must understand why formal protection models exist. Early computing systems had no notion of protection—any program could access any memory, any data, any device. This was acceptable for single-user, single-program systems, but the advent of time-sharing and multi-user systems in the 1960s created an urgent need for controlled resource access.
The Protection Problem:
Consider a multi-user system where:
Without a formal model, protection mechanisms become ad-hoc, inconsistent, and riddled with security holes. Each protection decision becomes a special case, making security auditing impossible and vulnerabilities inevitable.
| Era | System Type | Protection Requirement | Challenge |
|---|---|---|---|
| 1950s | Single-user batch | None | N/A |
| 1960s | Time-sharing | User isolation | Multiple concurrent users |
| 1970s | Minicomputers | File protection | Shared storage resources |
| 1980s | Networked systems | Network access control | Remote resource access |
| 1990s | Internet era | Web security | Untrusted code execution |
| 2000s+ | Cloud computing | Multi-tenancy | Thousands of principals, millions of resources |
Why Mathematical Abstraction?
A formal model provides:
The Access Matrix Model emerged as the answer to these needs—simple enough to be understood, yet powerful enough to model any protection scenario.
Butler Lampson developed the Access Matrix while at the Berkeley Computer Corporation and later Xerox PARC. His work drew on earlier concepts from Dennis and Van Horn's "Programming Semantics for Multi-programmed Computations" (1966); however, Lampson's formalization provided the clean abstraction that became the standard reference model for protection.
The Access Matrix is a two-dimensional array that represents the complete protection state of a system at any given instant. Its structure is elegantly simple:
Definition:
An Access Matrix A is defined as:
$$A[s, o] = {r_1, r_2, ..., r_k}$$
Where:
The matrix has one row for each subject and one column for each object. Each cell contains zero or more access rights, representing what operations that subject may perform on that object.
A Concrete Example:
Consider a simple system with three users (Alice, Bob, Carol) and three files (budget.xls, report.doc, config.sys):
| budget.xls | report.doc | config.sys | |
|---|---|---|---|
| Alice | read, write, own | read | - |
| Bob | read | read, write, own | read |
| Carol | - | read | read, write, own |
This matrix completely specifies the protection state:
Any access decision can be answered by looking up the appropriate cell: "Can Bob write to budget.xls?" Look at A[Bob, budget.xls] = {read}. Answer: No, because 'write' is not in that cell.
The Access Matrix's power lies in its generality. Any protection scheme—Unix permissions, Windows ACLs, database GRANT statements, AWS IAM policies—can be viewed as a particular implementation of or restriction on the Access Matrix model. When you understand the matrix, you understand the foundation of all access control.
The Access Matrix represents the protection state of the system at a single point in time. However, protection states are not static—they evolve as users create files, processes spawn, and administrators modify permissions.
Protection State:
Formally, the protection state is a triple:
$$State = (S, O, A)$$
Where:
State Transitions:
Changes to the protection state occur through primitive operations that modify the matrix:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657
# Abstract representation of Access Matrix state transitionsclass AccessMatrix: def __init__(self): self.subjects = set() # S: Set of subjects self.objects = set() # O: Set of objects self.matrix = {} # A: dict[(s,o)] -> set of rights def create_subject(self, subject: str): """Add a new subject (row) to the matrix""" if subject in self.subjects: raise ValueError(f"Subject {subject} already exists") self.subjects.add(subject) # Initialize empty rights for all existing objects for obj in self.objects: self.matrix[(subject, obj)] = set() def create_object(self, obj: str, owner: str = None): """Add a new object (column) to the matrix""" if obj in self.objects: raise ValueError(f"Object {obj} already exists") self.objects.add(obj) # Initialize empty rights for all existing subjects for subject in self.subjects: self.matrix[(subject, obj)] = set() # Optionally grant owner rights if owner and owner in self.subjects: self.enter_right("own", owner, obj) self.enter_right("read", owner, obj) self.enter_right("write", owner, obj) def enter_right(self, right: str, subject: str, obj: str): """Add a right to cell A[subject, object]""" if subject not in self.subjects: raise ValueError(f"Subject {subject} does not exist") if obj not in self.objects: raise ValueError(f"Object {obj} does not exist") self.matrix[(subject, obj)].add(right) def delete_right(self, right: str, subject: str, obj: str): """Remove a right from cell A[subject, object]""" self.matrix[(subject, obj)].discard(right) def check_access(self, subject: str, obj: str, right: str) -> bool: """Authorization decision: Can subject access object with right?""" return right in self.matrix.get((subject, obj), set()) # Example usageam = AccessMatrix()am.create_subject("alice")am.create_subject("bob")am.create_object("file1.txt", owner="alice") print(am.check_access("alice", "file1.txt", "read")) # Trueprint(am.check_access("bob", "file1.txt", "read")) # False am.enter_right("read", "bob", "file1.txt")print(am.check_access("bob", "file1.txt", "read")) # TrueCommands and Authorization:
In practice, subjects do not directly invoke primitive operations. Instead, they issue commands that may trigger sequences of primitives. Commands typically check authorization before executing:
command grant_read(granter, grantee, object):
if "own" in A[granter, object]: # Authorization check
enter "read" into A[grantee, object] # State modification
else:
DENY
This pattern—check authorization in the current state, then modify state—is the fundamental flow of all access control systems.
A fundamental question in access control theory: Given an initial protection state and a set of commands, can a particular right ever enter a particular cell? This is the "safety problem." Harrison, Ruzzo, and Ullman (1976) proved this problem is undecidable in the general case—meaning no algorithm can always determine if a given right will eventually be granted. This has profound implications for security verification.
The Access Matrix's elegance lies in its universality. Every access control system—regardless of its specific implementation—can be understood as maintaining some representation of an Access Matrix. Let's examine how various real-world systems map to this model:
Unix File Permissions:
Unix's classic permission model is a highly constrained Access Matrix:
The matrix cell A[user, file] is determined by which category the user falls into:
-rwxr-x--- maps to:
A[owner, file] = {read, write, execute}
A[group, file] = {read, execute}
A[others, file] = {}
Windows ACLs:
Windows implements a more complete Access Matrix:
Database GRANT/REVOKE:
SQL access control directly implements matrix operations:
GRANT SELECT ON table TO user → enter 'select' into A[user, table]REVOKE UPDATE ON table FROM role → delete 'update' from A[role, table]| System | Subject Examples | Object Examples | Typical Rights |
|---|---|---|---|
| Unix | uid, gid | inodes (files) | r, w, x |
| Windows | SID (user/group) | Named objects | Read, Write, Delete, Execute, ... |
| Linux/SELinux | Security context | Files, sockets, processes | Type-specific permissions |
| PostgreSQL | Roles | Tables, schemas, functions | SELECT, INSERT, UPDATE, DELETE, ... |
| AWS IAM | Principals (users, roles) | Resources (S3, EC2, ...) | Actions (s3:GetObject, ...) |
| Kubernetes | Users, ServiceAccounts | Resources (pods, deployments) | Verbs (get, list, create, ...) |
Abstract Properties Preserved:
Despite their different syntaxes and implementation strategies, all these systems preserve the fundamental Access Matrix properties:
Understanding the Access Matrix means understanding the common foundation beneath all these variations.
When encountering any access control system, mentally map it to an Access Matrix. Ask: What are the subjects? What are the objects? What are the rights? How are matrix cells represented? This mental model helps you understand unfamiliar systems quickly and identify potential security gaps.
A sophisticated feature of the Access Matrix is that subjects can also be objects. This allows the matrix to express control relationships between entities themselves, not just their access to passive resources.
Subjects Appearing in Columns:
When subjects appear as objects, new rights become meaningful:
| Alice | Bob | File1 | |
|---|---|---|---|
| Alice | - | wakeup, signal | read, write |
| Bob | signal | - | read |
| System | terminate, suspend | terminate, suspend | read, write |
Here, the cell A[Alice, Bob] = {wakeup, signal} means Alice can send wakeup or signal operations to Bob (perhaps Bob is a process). The cell A[System, Alice] = {terminate, suspend} means the System can terminate or suspend Alice.
Control Rights:
Typical rights for subject-as-object include:
Domains as Objects:
In systems using protection domains (discussed in the previous module), domains themselves appear as objects in the matrix. The switch right controls domain transitions:
| Domain 1 | Domain 2 | Domain 3 | File A | |
|---|---|---|---|---|
| Domain 1 | - | switch | - | read |
| Domain 2 | switch | - | switch | read, write |
| Domain 3 | - | - | - | execute |
This matrix shows:
This elegantly models the protection ring concept: inner rings can switch to outer rings, but not vice versa (enforced by which cells contain the 'switch' right).
Special rights control matrix modification itself: (1) The copy right (often noted with , e.g., read) allows a subject to grant that right to others; (2) The owner right allows adding/removing any rights for that object; (3) The control right (in some models) allows modifying rights in a subject's row. These meta-rights distinguish between using resources and controlling access to resources.
The Access Matrix enables formal reasoning about security properties. Several important properties can be expressed and analyzed using the matrix framework:
Principle of Least Privilege:
Formally: For each subject s, the set of rights in all cells of row s should be the minimum necessary for s to perform its function.
$$\forall s \in S: \bigcup_{o \in O} A[s, o] = MinimumRequired(function(s))$$
Separation of Duty:
Formally: Certain rights should never co-exist in the same subject's row.
$$\forall s \in S: \neg(approvePayment \in A[s, payroll] \land createPayment \in A[s, payroll])$$
Information Flow:
The matrix implicitly defines information flow paths. If A[s, o₁] contains 'read' and A[s, o₂] contains 'write', then information can flow from o₁ to o₂ via subject s.
$$o_1 \rightarrow o_2 \text{ if } \exists s: read \in A[s, o_1] \land write \in A[s, o_2]$$
Decidability Constraints:
Harrison, Ruzzo, and Ullman (HRU) proved that while the general safety problem is undecidable, restricted versions are decidable:
Practical systems often fall into these tractable categories, enabling formal security verification.
While the Access Matrix provides a clean theoretical model, real systems introduce complications: negative rights (explicit denials), ordered evaluation, wildcards, inheritance hierarchies, and dynamic attribute evaluation. Each extension adds expressive power but complicates formal analysis. Security architects must balance expressiveness against analyzability.
The HRU Model (Harrison, Ruzzo, and Ullman, 1976) formalized the Access Matrix with a rigorous computational framework. It defines exactly how commands operate on the matrix and establishes fundamental limits on what can be computed about access control.
Formal Definition:
An HRU system consists of:
Each command has the form:
command name(X₁, X₂, ..., Xₖ):
if r₁ in A[Xs₁, Xo₁] and
r₂ in A[Xs₂, Xo₂] and
...and
rₘ in A[Xsₘ, Xoₘ]
then
op₁; op₂; ...; opₙ
Where each op is one of the six primitive operations we defined earlier.
1234567891011121314151617181920212223242526272829
# HRU-style command: Creating a file with ownershipcommand create_file(creator, filename): # No conditions (unconditional command) then: create object filename enter "own" into A[creator, filename] enter "read" into A[creator, filename] enter "write" into A[creator, filename] # HRU-style command: Granting read permissioncommand grant_read(owner, recipient, file): if "own" in A[owner, file] # Condition: owner must own file then: enter "read" into A[recipient, file] # HRU-style command: Transferring ownershipcommand transfer_ownership(old_owner, new_owner, file): if "own" in A[old_owner, file] then: delete "own" from A[old_owner, file] enter "own" into A[new_owner, file] # HRU-style command: Spawning a child processcommand spawn_child(parent, child_name): if "spawn" in A[parent, parent] then: create subject child_name enter "terminate" into A[parent, child_name] enter "wait" into A[parent, child_name]The Safety Theorem:
The central result of HRU is the safety theorem:
Definition (Safety): An initial configuration is safe for a right r with respect to command set C if there is no sequence of commands in C that, starting from the initial configuration, can cause r to be entered into a cell where it did not previously exist.
Theorem (HRU, 1976): The safety question is undecidable for arbitrary HRU systems. That is, there exists no algorithm that, given an arbitrary HRU system and initial configuration, can always correctly determine if the system is safe.
Proof Sketch:
The proof works by showing that HRU systems can simulate a Turing machine:
Since the halting problem is undecidable, safety must also be undecidable.
The undecidability of safety means: (1) No tool can guarantee that an arbitrary access control policy will never allow unauthorized access; (2) Security verification requires restricting the policy language; (3) Real systems must be designed with limited command sets that fall into decidable cases. This theoretical result from 1976 still shapes access control system design today.
We've explored the Access Matrix Model—the theoretical foundation underlying all access control mechanisms. Let's consolidate the key concepts:
What's Next:
In the following pages, we'll examine the components of the Access Matrix in greater depth. We'll explore subjects and objects in detail, analyze the taxonomy of access rights, study implementation strategies (Access Control Lists and Capability Lists), and address the critical challenge of matrix size in real systems.
You now understand the Access Matrix Model—the elegant theoretical abstraction that underpins all access control systems. This foundation will serve you whether you're configuring file permissions, designing database security, implementing microservice authorization, or building cloud infrastructure policies. The matrix is everywhere; now you can see it.