Administrative Models, Safety Analysis, and Sandhu's Schematic Protection Model

Every article in this cluster so far describes how a system decides an access. This one asks a different question about the same system: granted the rules for changing permissions, is there any sequence of operations that ends with an unauthorized subject holding a right it should never receive? That is the safety problem, and it was settled in the negative for the general case in the 1970s. The useful engineering follows from knowing exactly where the undecidability comes from and which restrictions remove it.

The access matrix and its three implementation families

The abstract model is a matrix whose rows are subjects, columns are objects, and cells hold rights. Rights change through operations that write into cells, and the structure of those operations is the whole problem.

Lampson’s 1971 formulation of the matrix is the reference point for the three ways of realizing it. A capability list stores the matrix by row: each subject holds an unforgeable list of the objects it may touch. An access control list stores it by column: each object holds a list of the subjects permitted to touch it. A lock-and-key scheme stores it sparsely, with objects carrying locks and subjects carrying keys that match.

The three are equivalent in the model and not equivalent in what they make easy. Capability lists make it cheap to enumerate a subject’s rights and to answer “what can this process do”, which is the question a sandbox needs. Access control lists make it cheap to answer “who can read this object”, which is the question an auditor asks. Reviewing a subject’s authority in an ACL system requires scanning every object; the reverse review in a capability system requires scanning every subject. Whichever direction the organization reviews more often is the direction the storage should make cheap, which is the argument in the capability article carried to its structural conclusion.

The HRU result: safety is undecidable

Harrison, Ruzzo, and Ullman modelled a protection system as a set of commands. A command has a name, a sequence of conditions that must hold for it to be applied, and a sequence of primitive operations that copy, grant, or remove a right. Mono-operational commands are the special case where each command performs exactly one primitive operation.

Their result is that deciding whether a given right can ever leak to a given subject is undecidable for the general command language, and decidable for mono-operational systems. The reduction constructs commands whose application simulates a Turing machine, so a leak exists exactly when the simulated machine halts.

The consequence for design is direct: any system whose administrative operations are a general-purpose programming language over the matrix is a system for which no general leak analysis exists. That is what policy-as-code engines are, and it explains why their safety arguments are made by testing and review rather than by proof. Policy-as-code evaluation gains expressiveness by moving into the undecidable region, and the trade is real rather than nominal.

The take-grant model and what its definitions buy

The take-grant model restricts the operation set to four: a subject can take a right from an object it holds the take right on, grant a right it holds to an object it holds the grant right on, create a new object, and remove a right it owns. With that small grammar, the leak question becomes a graph reachability problem, and the answer is computable in time linear in the size of the graph.

Reachability is decided by finding a path in a graph whose edges are labelled by the rights that permit the transfer. A path exists from subject s to object x for right r if a sequence of take and grant edges connects them, where each edge requires holding the corresponding transfer right. Sharing along such a path, and the conditions under which a right can be stolen rather than merely shared, both reduce to path properties.

s --take--> t --grant--> x

The path above means: s holds take on t, so s can obtain any right t holds; t holds grant on x, so the right can be placed on x. Whether that chain actually lets s end with the right on x depends on the direction of the rights at each step, and the model’s definitions pin down exactly which combinations transfer authority and which merely observe it. The distinction between a path that transfers and one that only permits reading the label is the part that naive graph analyses miss.

Attenuating schemes and the tractability boundary

Sandhu’s schematic protection model generalized the take-grant structure by parameterizing the set of commands: rather than fixing four operations, the model takes a function mapping each right to the set of rights it may confer. A protective scheme is attenuating when every right confers only itself or a subset of itself, so that authority never grows as it moves along a transfer. For acyclic attenuating schemes, safety is decidable and the decision procedure is a reachability analysis over a graph in which each edge is annotated with the right sets it can carry.

The result is the theoretical justification for the engineering intuition that authority should only narrow. A scheme where a right can confer a stronger right is a scheme where a chain of transfers can amplify authority, and amplification is what makes the analysis intractable: the state space stops being bounded by the graph and starts being bounded by the number of distinct right combinations, which is exponential.

Attenuation in the model is the same property token exchange enforces by refusing to grant scopes the subject token did not carry, and the same property capability derivation enforces when a derived capability is strictly weaker than its parent. Both are instances of a design rule that predates both mechanisms by decades: confinement is analysable when rights only shrink.

Applying the analysis to a real system

The procedure that follows from the theory is short. Enumerate the operations that change permissions. For each, determine whether it can introduce a right that was not already reachable by the party performing it. Classify the scheme as attenuating, amplifying, or neither. If attenuating and acyclic, the reachability analysis applies and can be run against the actual graph. If amplifying, the analysis does not apply, and the safety argument must come from somewhere else: review of every widening operation, or a runtime constraint that rejects the widening.

The point at which most systems stop being analysable is the existence of an administrative interface that can grant arbitrary rights. A console that lets an operator add any role to any user is an amplifying operation, and once one exists, every reachability argument is conditional on the assumption that the console was not misused. The practical mitigation is not to remove the console but to subordinate it to the same model: the console’s own rights should be expressed as a role, and the set of principals holding it should be small, enumerated, and reviewed. The analysis then applies to the console like anything else, at the cost of a system whose administrative authority is itself a thing that can leak.

The final limitation is that all of these models treat rights as static labels. They have nothing to say about the check-and-use gap, about the reference monitor being bypassed, or about a right that is correctly held but applied to the wrong object. A system can be provably safe in the take-grant sense and still leak data through an unmediated path, because the safety question is asked about the permission state rather than about the actual accesses. Both questions are needed, and they are asked at different levels: the state model bounds what the rules permit, and complete mediation bounds whether the rules are consulted at all.