The Expressive Power of Multi-Parent Creation in Monotonic Access Control Models


Formal demonstration of equivalence or nonequivalence of different security models helps identify the fundamental constructs and principles in such models. In this paper, we demonstrate the nonequivalence of two monotonic access control models that differ only in the creation operation for new subjects and/or objects; in particular, we show that single-parent creation is less expressive than multi-parent creation. The nature of the proof indicates that this result will apply to any monotonic access control model. The nonequivalence proof is carried out on an abstract access control model, following which the results are interpreted in standard formulations. In particular, we apply the results to demonstrate nonequivalence of the Schematic Protection Model (SPM) and the Extended Schematic Protection Model (ESPM). We also show how the results apply to the typed access matrix model (TAM), which is an extension of the well known access matrix model formalized by Harrison, Ruzzo, and Ullman (HRU). The results in this paper offer theoretical justification for regarding single-parent and multi-parent creation as fundamentally different operations in a monotonic context. The paper also demonstrates that in nonmonotonic models, multi-parent creation can be reduced to single-parent creation, thereby neutralizing the difference in expressive power.


A complete version of the paper is available in postscript.