Access Matrix Model - Access Matrix: The Foundation of Access Control | OneNoughtOne

0/236

Operating SystemsAccess Matrix

Access Matrix: The Foundation of Access Control

LevelIntermediate

Duration90 mins

TopicAccess Matrix

1 / 5

Access Matrix Model

The Authorization Problem

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.

What You Will Learn

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.

The Need for Formal Protection Models

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:

Users should access their own files but not others'
Some files should be shared among specific user groups
System files should be readable but not modifiable
Some operations (like shutting down) should be restricted to administrators
Processes should be isolated from each other

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.

Evolution of Protection Needs in Computing
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:

Precise Definitions: Unambiguous meaning for security concepts
Completeness: A framework that covers all possible access scenarios
Reasoning Tools: Mathematical techniques to prove security properties
Implementation Guidance: Clear requirements for mechanism designers
Comparison Basis: A common language to evaluate different systems

The Access Matrix Model emerged as the answer to these needs—simple enough to be understood, yet powerful enough to model any protection scenario.

Historical Context

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 Defined

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:

s ∈ S is a subject (an active entity that can initiate operations)
o ∈ O is an object (a passive entity that can be operated upon)
r ∈ R is an access right (a specific operation that can be performed)
A[s, o] is the cell containing the set of rights that subject s has over object o

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.

Converting Mermaid diagram...

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:

Alice owns budget.xls and can read/write it; she can only read report.doc
Bob owns report.doc, can read budget.xls, and can read config.sys
Carol owns config.sys and can only read report.doc

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 Power of Simplicity

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.

Protection State and State Transitions

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:

S = current set of subjects
O = current set of objects
A = current access matrix (S × O → 2^R)

State Transitions:

Changes to the protection state occur through primitive operations that modify the matrix:

create subject s: Add a new row for subject s
delete subject s: Remove the row for subject s
create object o: Add a new column for object o
delete object o: Remove the column for object o
enter right r into A[s, o]: Add right r to cell [s, o]
delete right r from A[s, o]: Remove right r from cell [s, o]

State Transition Model
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
# Abstract representation of Access Matrix state transitions
class 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 usage
am = AccessMatrix()
am.create_subject("alice")
am.create_subject("bob")
am.create_object("file1.txt", owner="alice")
 
print(am.check_access("alice", "file1.txt", "read"))   # True
print(am.check_access("bob", "file1.txt", "read"))     # False
 
am.enter_right("read", "bob", "file1.txt")
print(am.check_access("bob", "file1.txt", "read"))     # True

Commands 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.

The Safety Problem

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 Matrix as a Universal Abstraction

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:

Subjects: owner, group, others (three categories)
Objects: files, directories, devices
Rights: read (r), write (w), execute (x)

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:

Each object has an Access Control List (ACL)
Each ACL entry specifies (subject, rights) pairs
Rights include: Read, Write, Execute, Delete, Change Permissions, Take Ownership, etc.

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]

Access Matrix in Different Systems
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:

Finite, enumerable subjects and objects: Every system has a bounded set of principals and resources
Well-defined rights: Operations are discrete and identifiable
State-based authorization: Access decisions depend on current matrix contents
State modification operations: Some mechanism exists to change rights

Understanding the Access Matrix means understanding the common foundation beneath all these variations.

Thinking in Matrix Terms

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.

Self-Referential Matrix: Subjects as Objects

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:

signal: Send a signal to a process
terminate: Kill a process
suspend/resume: Pause/continue execution
exec: Execute as this subject identity
su/sudo: Switch user identity to this subject

Converting Mermaid diagram...

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:

From Domain 1, you can switch to Domain 2
From Domain 2, you can switch to Domain 1 or Domain 3
From Domain 3, no domain switching is allowed

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).

The Copy and Owner Rights

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.

Formal Properties of the Access Matrix

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: eg(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]$$

Security Properties Expressible via Access Matrix

•Confinement: A subject cannot leak data to unauthorized recipients — no unintended write paths exist
•Isolation: Subjects in different security domains share no common objects — disjoint column access
•Integrity: Critical objects are writable only by trusted subjects — cell membership restriction
•Availability: Subjects have sufficient rights to perform their duties — minimum rights guaranteed
•Accountability: Rights granting can be traced — copy/owner rights tracked
•Monotonicity: Rights, once removed, cannot be regained (in some models) — restricted state transitions

Decidability Constraints:

Harrison, Ruzzo, and Ullman (HRU) proved that while the general safety problem is undecidable, restricted versions are decidable:

Mono-conditional commands: Only one condition checked → decidable but NP-complete
Mono-operational commands: Only one state change per command → decidable in linear time
No creation of subjects/objects: Fixed matrix size → decidable

Practical systems often fall into these tractable categories, enabling formal security verification.

Theory Meets Reality

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 Harrison-Ruzzo-Ullman (HRU) Model

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:

R: a finite set of access rights
C: a finite set of commands
Config: configurations (S, O, A) representing protection states

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.

HRU Command Example

Pseudo-code

# HRU-style command: Creating a file with ownership
command 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 permission
command 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 ownership
command 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 process
command 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:

Subjects represent tape cells
Rights represent tape symbols
Commands simulate tape head movement and symbol writing
Halting corresponds to a right entering a specific cell

Since the halting problem is undecidable, safety must also be undecidable.

Profound Implications

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.

Summary: The Access Matrix Foundation

We've explored the Access Matrix Model—the theoretical foundation underlying all access control mechanisms. Let's consolidate the key concepts:

Key Takeaways

•The Access Matrix is a 2D array A[s, o] capturing the complete protection state: which subjects have which rights over which objects
•Protection states change through primitive operations: create/delete subjects and objects, enter/delete rights in cells
•Every access control system can be viewed as an implementation of the Access Matrix model, from Unix permissions to cloud IAM
•Subjects can also be objects, enabling the matrix to express control relationships between active entities (processes, domains)
•Formal properties (least privilege, separation of duty, information flow) can be precisely expressed using matrix notation
•The HRU model formalizes the matrix with commands and proves that general safety is undecidable—a fundamental limit on security verification
•Practical systems use restricted command sets that allow decidable security analysis

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.

Page Complete

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.

Operating SystemsAccess Matrix

Access Matrix: The Foundation of Access Control

LevelIntermediate

Duration90 mins

TopicAccess Matrix

1 / 5

Access Matrix Model

The Authorization Problem

What You Will Learn

The Need for Formal Protection Models

The Protection Problem:

Consider a multi-user system where:

Users should access their own files but not others'
Some files should be shared among specific user groups
System files should be readable but not modifiable
Some operations (like shutting down) should be restricted to administrators
Processes should be isolated from each other

Evolution of Protection Needs in Computing
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:

Precise Definitions: Unambiguous meaning for security concepts
Completeness: A framework that covers all possible access scenarios
Reasoning Tools: Mathematical techniques to prove security properties
Implementation Guidance: Clear requirements for mechanism designers
Comparison Basis: A common language to evaluate different systems

The Access Matrix Model emerged as the answer to these needs—simple enough to be understood, yet powerful enough to model any protection scenario.

Historical Context

The Access Matrix Defined

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:

s ∈ S is a subject (an active entity that can initiate operations)
o ∈ O is an object (a passive entity that can be operated upon)
r ∈ R is an access right (a specific operation that can be performed)
A[s, o] is the cell containing the set of rights that subject s has over object o

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.

Converting Mermaid diagram...

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:

Alice owns budget.xls and can read/write it; she can only read report.doc
Bob owns report.doc, can read budget.xls, and can read config.sys
Carol owns config.sys and can only read report.doc

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 Power of Simplicity

Protection State and State Transitions

Protection State:

Formally, the protection state is a triple:

$$State = (S, O, A)$$

Where:

S = current set of subjects
O = current set of objects
A = current access matrix (S × O → 2^R)

State Transitions:

Changes to the protection state occur through primitive operations that modify the matrix:

create subject s: Add a new row for subject s
delete subject s: Remove the row for subject s
create object o: Add a new column for object o
delete object o: Remove the column for object o
enter right r into A[s, o]: Add right r to cell [s, o]
delete right r from A[s, o]: Remove right r from cell [s, o]

State Transition Model
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
# Abstract representation of Access Matrix state transitions
class 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 usage
am = AccessMatrix()
am.create_subject("alice")
am.create_subject("bob")
am.create_object("file1.txt", owner="alice")
 
print(am.check_access("alice", "file1.txt", "read"))   # True
print(am.check_access("bob", "file1.txt", "read"))     # False
 
am.enter_right("read", "bob", "file1.txt")
print(am.check_access("bob", "file1.txt", "read"))     # True

Commands 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.

The Safety Problem

The Matrix as a Universal Abstraction

Unix File Permissions:

Unix's classic permission model is a highly constrained Access Matrix:

Subjects: owner, group, others (three categories)
Objects: files, directories, devices
Rights: read (r), write (w), execute (x)

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:

Each object has an Access Control List (ACL)
Each ACL entry specifies (subject, rights) pairs
Rights include: Read, Write, Execute, Delete, Change Permissions, Take Ownership, etc.

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]

Access Matrix in Different Systems
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:

Finite, enumerable subjects and objects: Every system has a bounded set of principals and resources
Well-defined rights: Operations are discrete and identifiable
State-based authorization: Access decisions depend on current matrix contents
State modification operations: Some mechanism exists to change rights

Understanding the Access Matrix means understanding the common foundation beneath all these variations.

Thinking in Matrix Terms

Self-Referential Matrix: Subjects as Objects

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

Control Rights:

Typical rights for subject-as-object include:

signal: Send a signal to a process
terminate: Kill a process
suspend/resume: Pause/continue execution
exec: Execute as this subject identity
su/sudo: Switch user identity to this subject

Converting Mermaid diagram...

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:

From Domain 1, you can switch to Domain 2
From Domain 2, you can switch to Domain 1 or Domain 3
From Domain 3, no domain switching is allowed

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).

The Copy and Owner Rights

Formal Properties of the Access Matrix

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: eg(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]$$

Security Properties Expressible via Access Matrix

•Confinement: A subject cannot leak data to unauthorized recipients — no unintended write paths exist
•Isolation: Subjects in different security domains share no common objects — disjoint column access
•Integrity: Critical objects are writable only by trusted subjects — cell membership restriction
•Availability: Subjects have sufficient rights to perform their duties — minimum rights guaranteed
•Accountability: Rights granting can be traced — copy/owner rights tracked
•Monotonicity: Rights, once removed, cannot be regained (in some models) — restricted state transitions

Decidability Constraints:

Harrison, Ruzzo, and Ullman (HRU) proved that while the general safety problem is undecidable, restricted versions are decidable:

Mono-conditional commands: Only one condition checked → decidable but NP-complete
Mono-operational commands: Only one state change per command → decidable in linear time
No creation of subjects/objects: Fixed matrix size → decidable

Practical systems often fall into these tractable categories, enabling formal security verification.

Theory Meets Reality

The Harrison-Ruzzo-Ullman (HRU) Model

Formal Definition:

An HRU system consists of:

R: a finite set of access rights
C: a finite set of commands
Config: configurations (S, O, A) representing protection states

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.

HRU Command Example

Pseudo-code

# HRU-style command: Creating a file with ownership
command 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 permission
command 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 ownership
command 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 process
command 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:

Subjects represent tape cells
Rights represent tape symbols
Commands simulate tape head movement and symbol writing
Halting corresponds to a right entering a specific cell

Since the halting problem is undecidable, safety must also be undecidable.

Profound Implications

Summary: The Access Matrix Foundation

We've explored the Access Matrix Model—the theoretical foundation underlying all access control mechanisms. Let's consolidate the key concepts:

Key Takeaways

•The Access Matrix is a 2D array A[s, o] capturing the complete protection state: which subjects have which rights over which objects
•Protection states change through primitive operations: create/delete subjects and objects, enter/delete rights in cells
•Every access control system can be viewed as an implementation of the Access Matrix model, from Unix permissions to cloud IAM
•Subjects can also be objects, enabling the matrix to express control relationships between active entities (processes, domains)
•Formal properties (least privilege, separation of duty, information flow) can be precisely expressed using matrix notation
•The HRU model formalizes the matrix with commands and proves that general safety is undecidable—a fundamental limit on security verification
•Practical systems use restricted command sets that allow decidable security analysis

What's Next:

Page Complete