Graham-Denning
Eight rules for creating, deleting, and sharing rights.
G. Scott Graham and Peter Denning · 1972 · How rights are securely created and shared
The problem it solves
Before you can enforce access, you need safe rules for how subjects, objects, and rights come into being and move around. Graham-Denning defines eight primitive operations that govern the whole lifecycle.
The big idea
Graham-Denning is a complete rulebook for safely creating, sharing, and revoking access rights across subjects and objects, all tracked in one access control matrix.
Picture a big grid where every row is a subject (a user or process) and every column is an object (a file, device, or even another subject). Each cell lists the rights that subject holds over that object. Graham-Denning defines eight primitive commands that are the only legal ways to change that grid, and it ties the power to share a right back to authority: only an owner of the object, or a holder of a transferable right, can pass a right along.
The rules
Add a new active entity (a user or process) as a row, or a new resource (a file or device) as a column.
Create subject, create object
Why: New users, programs, and resources must enter the matrix in a controlled way before anyone can act on them.
Remove a subject and clear the rights it held, or remove an object and its column.
Delete subject, delete object
Why: Retired users and decommissioned resources must be cleanly removed so no stale access lingers.
Look at the rights stored in a cell to see what a subject may do to an object, without changing anything.
Read access right
Why: Administration and auditing need a safe way to inspect current permissions.
An owner gives a right over an object to another subject, and an authorized subject can later remove a right from a cell (the object's owner, or the subject that controls the holder).
Grant access right, delete access right
Why: Owners need a legitimate channel to share their resources, and access must always be revocable by the right authority.
Pass a right you hold along to another subject when that right is marked as transferable, optionally giving up your own copy.
Transfer access right
Why: Some rights are meant to be delegated by their holder, not just handed out by the owner, so sharing can flow in a controlled way.
Whoever creates an object gets the owner right and is the one allowed to grant rights on it; a separate control right lets one subject manage and revoke the rights another subject holds.
Owner right and control right
Why: Sharing and revocation must trace back to a clear authority: ownership governs an object, control governs a subject, so rights cannot be handed out or taken away by just anyone.
Try it
| Subj \ Obj | File 1 |
|---|---|
| Aliceactor | |
| Bob |
O = own · R = read · W = write
Pick an actor, select a cell, then apply an operation.
Worked example
An owner sharing a file.
- 01Allowed
Create a new file object.
Create object. The owner takes control of it.
- 02Allowed
Grant a colleague read access.
Grant right. An owner can share what they own.
- 03Blocked
Grant read on a file you do not own.
Only the owner, or a holder of the grant right, can give it away.
- 04Allowed
Revoke the access later.
Delete right. The owner takes it back.
Limits and gotchas
It does not answer whether a right can leak
Graham-Denning tells you which operations are allowed, but it does not prove that some sequence of those legal operations cannot eventually deliver a right to a subject who should never have it. That deeper question is the safety problem, which Harrison-Ruzzo-Ullman later showed is undecidable in general.
It is a theoretical framework, not a policy
The model describes the mechanics of creating, sharing, and revoking rights. It does not decide what your security policy should be, who should own what, or which rights are appropriate for a given situation. Those choices are left to the system designer.
Real systems only approximate it
A literal matrix with a cell for every subject and object pair would be huge and mostly empty. Real systems implement the same ideas with access control lists, capabilities, roles, and groups, so they capture the spirit of the model rather than its exact structure.
It assumes trusted, correct operations
The model presumes the eight commands run faithfully and that ownership and control are honored. It does not address bugs, covert channels, side channels, or operations that bypass the matrix entirely.
Key terms
- Access control matrix
- A grid that records all permissions in a system. Each row is a subject, each column is an object, and each cell lists the rights that subject holds over that object.
- Subject
- An active entity that can act on resources, such as a user, a process, or a program. Subjects are the rows of the matrix.
- Object
- A passive resource that can be acted upon, such as a file, a device, or a record. Objects are the columns of the matrix. A subject can also be treated as an object when rights over it are managed.
- Right
- A specific permission a subject holds over an object, for example read, write, execute, owner, or control. Rights are the contents of the matrix cells.
- Owner right
- A special right gained automatically by whoever creates an object. The owner is the authority allowed to grant rights on that object to other subjects.
- Control right
- A special right one subject holds over another subject. It lets the holder manage and revoke the rights that the controlled subject possesses, which is how a creator supervises the subjects it makes.
- Transferable right
- A right that is marked as transferable (written with an asterisk in the model's notation) so its holder can pass it to another subject. The holder can still use the right and can copy or move it onward without needing to be the object's owner.
- Primitive command
- One of the eight basic operations Graham-Denning allows. These commands are the only legal ways to change the matrix, which keeps every change to rights well defined.
Check yourself
Answer to see if you have it. Nothing is saved.
01What does each cell in the access control matrix hold?
02Which subject is normally allowed to grant rights on an object to others?
03How many primitive commands does Graham-Denning define, and which of these is one of them?
04What question does Graham-Denning leave unanswered, that Harrison-Ruzzo-Ullman later addressed?
How it connects
Key takeaway
The one line
Graham-Denning = 8 primitive rules for subjects, objects, and rights. Create, delete, grant, transfer, read.