The Dynamic-Typed Access Matrix Model and Decidability of the Safety Problem

Masakazu SOSHI  Mamoru MAEKAWA  Eiji OKAMOTO 

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences  Vol.E87-A  No.1  pp.190-203
Publication Date: 2004/01/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Applications
Keyword: 
access control,  access matrix model,  safety problem,  computational complexity,  decidability, 

Full Text: PDF(696.9KB)

Summary: 
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.