Harrison-Ruzzo-Ullman
Can a right ever leak? In general you cannot prove it will not.
Michael Harrison, Walter Ruzzo, Jeffrey Ullman · 1976 · The formal limits of access control
The problem it solves
Given an access control matrix and rules for changing it, you want to guarantee a right never reaches the wrong subject. HRU proved that in the general case this safety question is undecidable. You cannot always prove a system stays safe.
The big idea
Even with a simple set of rules for handing out access rights, you cannot in general prove that a right will never reach a subject who should not have it.
HRU models protection as an access control matrix plus commands that edit it. The natural safety question is whether some sequence of legal commands could ever leak a right into a cell where it should not appear. Harrison, Ruzzo, and Ullman proved this question is undecidable in the general case, meaning no single algorithm can answer it for every possible system. It becomes decidable only when you restrict the model, for example to mono-operational commands where each command performs just one primitive operation.
The rules
Model who can do what by laying out a grid of subjects down the side, objects across the top, and the rights held in each cell.
Access control matrix
Why: It gives one precise structure for the entire protection state, so any change can be described as an edit to a cell.
Build every state change from six basic edits: enter a right, delete a right, create a subject, create an object, destroy a subject, and destroy an object.
Six primitive operations
Why: A tiny fixed set of edits keeps the model simple enough to reason about formally.
Group the primitive operations into named commands that first test for certain rights, then run their edits only if those tests pass.
Commands (conditional, built from primitive operations)
Why: Real authorization rules are conditional, so a command checks preconditions before it changes the matrix.
Ask the key question: starting from a given matrix, could any sequence of commands ever enter a specific right into a cell that did not already have it?
Leak of a right
Why: A leak is the concrete event that tells you whether a protection system can hand out an access it was not meant to grant.
Decide safety by determining whether the system can ever reach a state where a chosen right has leaked.
The safety problem
Why: Safety is the property administrators actually want to guarantee about a protection system.
Accept that there is no general method to answer the safety question for every system, although it can be answered when each command performs only one primitive operation.
Safety is undecidable in general, decidable for mono-operational systems
Why: This is the central HRU result: simple rules do not guarantee you can prove safety, but restricting the model restores a yes-or-no answer.
Try it
| Subj \ Obj | File 1 |
|---|---|
| Aliceactor | |
| Bob |
O = own · R = read · W = write
The safety question
Goal: can Bob get read on File 1? Grant rights and watch a right reach him. Each command is legal on its own. Bob does not hold read yet.
Pick an actor, select a cell, then apply an operation.
Worked example
Testing whether a right can leak.
- 01Allowed
Run a command that adds a right to a cell.
The command meets its conditions, so it fires.
- 02Allowed
Chain commands to push the right toward a new subject.
Each step is legal on its own.
- 03Blocked
Prove no sequence ever leaks the right.
In the general case this cannot be decided. That is the HRU result.
Limits and gotchas
The undecidability result is theoretical, not a practical alarm
Undecidable means no single algorithm works for every possible system. It does not mean any specific real system is impossible to analyze. Many particular configurations can still be checked by hand or by special-purpose tools.
Real systems regain decidability by restricting the model
Practical designs cut the model down, for example by allowing only mono-operational commands or other constrained forms, so that safety becomes a question you can actually answer. The general model is a limit case, not the way systems are usually built.
Decidable does not mean cheap to check
Even in the mono-operational case where safety is decidable, the work needed to decide it can grow very large as the number of subjects, objects, and rights increases. Decidable means an answer exists in finite time, not that it is fast.
It says nothing about what policy should be
HRU only reasons about whether rights can move into cells. It does not tell you which rights are correct, and it does not enforce confidentiality or integrity goals. Deciding what access ought to exist is left entirely to the policy you encode in the matrix and commands.
It models the mechanism, not human behavior or implementation flaws
The result is about the rules for changing rights. It does not cover side channels, buggy code, social engineering, or mistakes in translating a policy into commands.
Key terms
- Protection system
- The whole setup being modeled: the current access control matrix plus the set of commands that are allowed to change it over time.
- Access control matrix
- A grid with subjects as rows and objects as columns, where each cell lists the rights that subject holds over that object. Subjects can also appear as objects, so a subject can hold rights over another subject.
- Primitive operation
- One of the six smallest possible edits to the matrix: enter a right, delete a right, create a subject, create an object, destroy a subject, destroy an object.
- Command
- A named rule that checks for the presence of certain rights in certain cells, and if every check passes, runs a fixed sequence of primitive operations.
- Leak
- The event where a command enters a particular right into a cell that did not previously contain it. In the safety question, a leak means a right has reached a place it was not supposed to reach.
- Safety
- The property that no reachable state ever leaks a given right. Asking whether a system is safe is the safety problem.
- Mono-operational command
- A command whose body performs exactly one primitive operation. Restricting a system so that every command is mono-operational makes the safety problem decidable.
- Decidable vs undecidable
- A question is decidable if a single algorithm can always answer it correctly in finite time. It is undecidable if no such algorithm can exist. General HRU safety is undecidable; mono-operational HRU safety is decidable.
Check yourself
Answer to see if you have it. Nothing is saved.
01What is the central question that the HRU model asks about a protection system?
02Which list correctly names the six primitive operations of HRU?
03What did Harrison, Ruzzo, and Ullman prove about the safety problem in the general case?
04Under what restriction does the HRU safety problem become decidable?
How it connects
Key takeaway
The one line
HRU = access control matrix + the safety problem. Proving a right never leaks is undecidable in general.