The Application of Graph Theory to Access Control Systems

Computer systems contain vital information that must be protected. One of the crucial aspects of protection is access control. A review of some of the research into ways in which access to the information in computers can be controlled focuses on a question about safety. The safety question asks, “Can a user ever gain access to a resource for which he is not authorized?” This question cannot be answered in general because of the unbounded, unrestricted nature of a general-purpose access control system. It can be answered only for systems that are specifically designed to restrict the actions that can be taken by users of a system so that all of its possible future states, with respect to a certain right ‘leaking’ to an unauthorized user, can be predicted. There is a tension between the power to take useful actions within a system, and the ability to predict safety. Another way to ensure safety is to express all of a system’s security policies as constraints. Then the access control system itself can be unrestricted, but each action is checked to ensure that no security policy has been violated so far. These are very complex and difficult to manage and, therefore, are difficult systems for which to verify the safety property. This thesis models an alternative access control system, consolidating disparate research and balancing expressive power and safety analysis. The system, called Graph Plus, uses a graph representation of the protection state. It has decidable safety algorithms, and many useful operations. The usefulness is further enhanced by combining the constraint philosophy with the restricted model philosophy into one hybrid system. Additional operations have been included that can be analyzed by the efficient safety algorithms of the underlying model. This safety analysis acts as a constraint upon the additional operations, so that safety can be retained even with the additional operations added to the model. The model and its implementation are described