The Foundational Work of Harrison-Ruzzo-Ullman Revisited
Authors:
- 11 September 2012
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Dependable and Secure Computing
- Vol. 10 (1) , 28-39
Abstract
The work by Harrison, Ruzzo, and Ullman (the HRU paper) on safety in the context of the access matrix model is widely considered to be foundational work in access control. In this paper, we address two errors we have discovered in the HRU paper. To our knowledge, these errors have not been previously reported in the literature. The first error regards a proof that shows that safety analysis for mono-operational HRU systems is in NP. The error stems from a faulty assumption that such systems are monotonic for the purpose of safety analysis. We present a corrected proof in this paper. The second error regards a mapping from one version of the safety problem to another that is presented in the HRU paper. We demonstrate that the mapping is not a reduction, and present a reduction that enables us to infer that the second version of safety introduced in the HRU paper is also undecidable for the HRU scheme. These errors lead us to ask whether the notion of safety as defined in the HRU paper is meaningful. We introduce other notions of safety that we argue have more intuitive appeal, and present the corresponding safety analysis results for the HRU scheme.Keywords
This publication has 22 references indexed in Scilit:
- Beyond proof-of-compliance: security analysis in trust managementJournal of the ACM, 2005
- Safety Analysis of the Dynamic-Typed Access Matrix Model2000
- Undecidability of safety for the schematic protection model with cyclic createsJournal of Computer and System Sciences, 1992
- The schematic protection modelJournal of the ACM, 1988
- Selective and locally controlled transport of privilegesACM Transactions on Programming Languages and Systems, 1984
- Safety in grammatical protection systemsInternational Journal of Parallel Programming, 1983
- A Linear Time Algorithm for Deciding Subject SecurityJournal of the ACM, 1977
- Protection in operating systemsCommunications of the ACM, 1976
- A comparison of polynomial time reducibilitiesTheoretical Computer Science, 1975
- ProtectionACM SIGOPS Operating Systems Review, 1974