The Foundational work of Harrison-Ruzzo-Ullman Revisited

Get BibTex-formatted data

Download

PDF

Author

Mahesh V. Tripunitara and Ninghui Li

Tech report number

CERIAS TR 2006-33

Entry type

techreport

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.

Download

PDF

Edition

Key alpha

TrLi6

Affiliation

CERIAS and Department of Computer Science, Purdue University

Publication Date

2001-01-01

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.

@Techreport{ TrLi6,
	title = "The Foundational work of Harrison-Ruzzo-Ullman Revisited",
	author = "Mahesh V. Tripunitara and Ninghui Li",
	edition = " ",
	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.",
	affiliation = "CERIAS and Department of Computer Science, Purdue University",
}