A New General Graph-based Model for Non-Monotonic Protection Systems

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 real-world 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.

Keywords:

Safety Problem , Protection System , Vulnerability Analysis , Access Control Models , NP-Completeness , 3-SAT Problem