The Extended Schematic Protection Model

Abstract

Access control models provide a formalism and framework for specifying control over access to information and other resources in multi-user computer systems. Useful access control models must balance expressive power with the decidability and complexity of safety analysis (i.e. the determination of whether or not a given subject can ever acquire access to a given object). The access matrix model as formalized by Harrison, Ruzzo, and Ullman (HRU) has very broad expressive power. Unfortunately, HRU also has extremely weak safety properties. Safety is undecidable for most policies of practical interest, even in the monotonic version of HRU (which only allows revocation which is itself reversible). Remarkably, an alternate formulation of monotonic HRU yields strong safety properties. This alternate formulation is called the Extended Schematic Protection Model (ESPM). ESPM is derived from the Schematic Protection Model (SPM) by extending the creation operation to allow multiple parents for a child, as opposed to the conventional create operation of SPM which has a single parent for a child. Despite its equivalence to monotonic HRU, ESPM retains tractable safety analysis for a large class of protection schemes that are of practical interest. In this paper we first show that ESPM is formally equivalent in expressive power to monotonic HRU. Then we give a complete analysis of the safety properties of ESPM for acyclic can-create relations with attenuating loops (i.e., can-create relations which are acyclic except for certain cycles of length one).