Completeness in Languages for Attribute-Based Access Control

Conrad Williams

Research output: ThesisDoctoral Thesis

141 Downloads (Pure)


Access control restricts the interactions that are possible between users (or programs operating under the control of users) and sensitive resources, and is an essential component of any security architecture in multi-user computing systems. The most common means of implementing access control is to define an authorization policy, specifying which requests (that is, attempted user-resource interactions) are authorized and can thus be allowed. In recent years, we have seen the emergence of attribute-based access control (ABAC), in part to cater for open, distributed computing environments where it is not necessarily possible to authenticate all entities directly. The primary goal of this thesis is to improve the understanding and specification of ABAC languages.

Our approach focuses on the connection between multi-valued logics (MVLs) and many ABAC languages present in the literature. We introduce the necessary theoretical foundations to analyse and reason about various properties of ABAC languages. This enables us to show that XACML, the predominant language for authoring ABAC policies, exhibits a number of shortcomings. We present extensions to the ABAC language PTaCL, and demonstrate how it may be modified to address the shortcomings identified in XACML. Later, we extend our foundations to lattice-based logics and languages, establishing new results about Belnap logic and its associated ABAC languages.

Another major difficulty encountered in many ABAC languages is how to construct a desired policy using the operators defined in the given language. Even in languages that are known to be functionally complete, this is in general a non-trivial task. We present a novel solution to this problem: specifying policies in a tabular form. We demonstrate why representing policies in this manner is convenient, intuitive and flexible for policy authors, and provide a method for automatically compiling policy tables into a form that is machineenforceable.
Original languageEnglish
Awarding Institution
  • Royal Holloway, University of London
  • Crampton, Jason, Supervisor
Thesis sponsors
Award date1 Feb 2018
Publication statusUnpublished - 2018


  • Access Control
  • ABAC
  • Canonical Completeness
  • Functional Completeness
  • Belnap Logic
  • Jobe's Logic

Cite this