One of the most challenging problems in security is the safety problem in which we should determine whether a subject can gain access to an object or not. Many approaches have been proposed to address this problem. Nevertheless, most of them lack the ability to model realworld systems or suffer from efficiency problems. In this paper, we propose a general graph-based protection system. In addition to monotonic rules, both non-monotonic rules and rules which may check for absence of rights as their preconditions are included in our model. Moreover, broad range of vulnerabilities including most of DoS vulnerabilities can be modeled via these general rules easily. It is proved that the safety problem in general form of our proposed model is NP-Complete. However, we introduce some simplified cases of the model, such as monotonically increasing systems and systems which contain only permanent rules, in which the safety problem can be answered in polynomial time.
Mohammad Ebrahim Rafiei, Hamid Mousavi,
Hamid Reza Shahriari, Reza Sadoddin, Rasool Jalili
Network Security Center, Department of Computer Engineering,
Sharif University of Technology, Tehran, Iran.