For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
The Dynamic-Typed Access Matrix Model and Decidability of the Safety Problem
Masakazu SOSHI Mamoru MAEKAWA Eiji OKAMOTO
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2004/01/01
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
access control, access matrix model, safety problem, computational complexity, decidability,
Full Text: PDF>>
The safety problem in access matrix models determines whether a given subject can eventually obtain access privilege to a given object. Generally speaking, the safety problem is, unfortunately undecidable. Not much is known about protection systems for which the safety problem is decidable, except for strongly constrained systems (e.g., monotonic systems). Therefore, we propose the Dynamic-Typed Access Matrix (DTAM) Model, which extends the Typed Access Matrix model of Sandhu by allowing the type of an object to change dynamically. The DTAM model has an advantage that it can describe non-monotonic protection systems for which the safety problem is decidable. In particular, with further restrictions, we can show that the problem becomes NP-hard. In this paper, we formally define the DTAM model and then discuss various aspects of it thoroughly.