-We report on our research effort, called Fast Semantic Attribute-Role-Based Access Control (ARBAC), to develop a semantic platform-independent framework enabling information originators and security administrators to specify access rights to information consistently and completely, in a social network environment, and then to rigorously enforce that specification. We use a modified ARBAC security model and an OWL ontology with additional rules in a logic programming and Java framework to express access policy, going beyond the limitations of previous attempts in this vein. We also experimented with knowledge compilation optimizing techniques that allow access policy constraint checking to be implemented in real-time, via a bit-vector encoding that can be used for rapid run-time reasoning. Approved for Public Release; Distribution Unlimited. 13-3295
Index Terms—access control policy, attribute-based, rolebased, Semantic Web, logic programming, knowledge compilation, social network, ontology, rule-based reasoning
I. INTRODUCTION
This paper is a report of our effort to provide a semantic
platform-independent framework so that information
originators and security administrators can specify access rights
to information consistently and completely, in a social network
environment, and then to rigorously enforce that specification.
In previous work [
For many sensitivity, privacy, and proprietary reasons, information sharing cannot be totally open. This is especially true for collaborative social environments such as the emerging MITRE Partnership Network (MPN), a large-scale environment for group-based (social network) information sharing among disparate governmental, commercial, academic, and other communities.
In addition, it is difficult to enforce unambiguous access rights and information privileges consistently and coherently and apply the access rules correctly and efficiently.
In a collaborative social environment, access control of information protecting privacy, security, and also enabling a complex range of policy respecting those requirements, is difficult.
To accomplish these objectives it is necessary to link a security policy model to a policy language with sufficient expressive power to ensure logical consistency. We used a modified Attribute-Role-Based Access Control (ARBAC) security model and an OWL ontology with additional rules in a logic programming framework to express access policy, going beyond the limitations of previous attempts in this vein, and then optimized with bit-vectors the runtime policy checking inference.
We focused on three aspects: expressivity, adaptability, and efficiency. We developed two implementations: one that transforms the policy model instance into a logic programming execution environment that includes rules; and a second that transforms the model instance into Java data structures, that in turn are optimized via a bit-encoding. In both cases, the prototype was embedded in a Java program that interfaces with external services, e.g., obtaining identity and access tokens (and their specific attribute information) from the authentication service.
The structure of the rest of the paper is as follows. In section II, we present the overall architecture and describe the runtime components. Then in section III, we briefly walk through the processing involved, followed in section IV by a discussion of the implementation. Section V addresses the optimization issues. We introduce related work in section VI, and finally, in section VII, we propose future directions.
II. SYSTEM ARCHITECTURE AND RUNTIME COMPONENTS The general system architecture of the semantic ARBAC system is represented in Figure 1. It consists of three processes which flow from left to right. The three processes are: 1) the Development time process; 2) the Transformation time process; and 3) the Execution (runtime) process.
The Development process (the red rounded rectangle in Figure 1) involves: 1) The creation (or update) of the ARBAC ontology, represented in OWL and RDF, i.e., the semantic policy model (SPM); and 2) The instantiation of the specific ARBAC policy (policies) to be transformed and deployed, i.e., the semantic policy instance (SPI). This is an instance of the semantic policy model.
The Transformation process (the yellow rounded rectangle in Figure 1) involves developing and/or generating in Prolog and Java: 1) The transformer interpreter that will take the SPI and generate the runtime semantic policy instance (RSPI), which is the bit-vector representation of the policy + rules; 2) The attribute signature assignment engine (ASAE) which generates and updates the resource access registry (RAR); 3) The RAR, which captures the attributes of the resources in bit-vector representation, indexed by resource URI; 4) The runtime user access routine (RUAR); 5) The runtime inference engine (RTIE) which will execute the RSPI using the RUAR.
The Transformation process can thus be considered a knowledge compilation process, where source semantic models and their interpreting engines get transformed to efficient Execution time process objects.
The Execution process (the blue rounded rectangle in Figure 1) thus includes the RAR, ASAE, RTIE, and the RUAR, in addition to access to the Development and Transformation models and data.
The SPM consists of the OWL ontology classes, object properties, and data properties. The major classes consist of: Subject (the person, organization, software that requests specific access to a resource), Action (the kind of access requested, e.g., read, write, create, delete, execute, etc.), Resource (the object needing to be accessed by a subject: executable, graphic, text, sound, video, hardware, etc.), Environment (salient aspects of the space or session’s environment, e.g., risk or alert level, entry network domain), Role (traditional roles such as administrator, expert, end user, developer, etc., that are also related to groups), and related notions: Authentication (how one authenticates one’s identity and so, derivatively, one’s potential access rights) , Security (can span information security notions such as protocols, standards, user- and group-level passwords, encryption methods, hashing algorithms and values, etc.), Classification Level (proprietary, sensitive, confidential, secret, top-secret, etc.), Identity (Public Key Infrastructure [PKI], digital certificates, etc.), Time (time-stamps, time intervals with respect to various policy notions), etc.
In addition, rules are a very important component of the semantic policy model (SPM). Rules exist outside of the OWL ontology per se, but are based on the classes and properties specified in the ontology. Rules were expressed initially in Prolog, and then in Java code for the second prototype. Rules are potentially recursive and express logical constraints among and across class and property values (instances). Some examples are given below.
The SPM represents a set of generic semantic components for ARBAC policy, and thus constitutes a family of potential specific ARBAC instantiations.
For more detailed descriptions of other components of the
architecture, including the SPI, RSPI, RAR, ASAE, RIE,
RUAR, the OWL parser, and external service interface, we
direct interested readers to [
III. ACCESS DECISION PROCESS FLOW AND WALKTHROUGH The following depicts the access decision process flow.
Initially, the Policy/Rules KB is read and loaded (including any general rules that apply to all circumstances) by the inference engine.
Then a request comes in containing the Subject, Resource, Action, and Environment.
The Subject’s Group membership is looked up and formed.
An initial Resource/Group/Access check may be performed.
For some common accesses these may be cached, or may require no further processing if a quick decision can be made.
Otherwise, the appropriate rule set is generated and populated with: any referenced access rule (pre-filtered to keep the KB small and fast), all facts about the Subject, Resource, Groups, and Environment, and General (generally applicable) rules. The rule set is passed to a runtime inference engine which evaluates the truth of the permission statement (something along the lines of allow(Subject, Access, Resource)).
The Inference Engine passes back the permission decision.
The semantic policy model (SPM) is the holder of much of the underlying knowledge. Its contents include:
Ontology Access Rules Group Membership Rules
General Rules
The Access Rules ultimately determine whether an action can be performed on a resource (a ‘Privilege’ to denote the pairing of actions and resources); each rule has three parts: 1. The head, or consequence, which is always a privilege (e.g., hasPrivilege(subject22, read,medicalRecord66) ). This leaves the body of the rule which for convenience is broken into 2 parts: 2. The Group membership required to obtain the privilege, and 3. Any additional requirements, expressed in terms of environment variables.
Example: hasPrivilege(Subject, Action, Resource) agent(Subject), member(Subject, Group), environmentalConstraints(Group, Action, Resource, Environment), groupWithPrivilege(Group, Action, Resource, Environment).
Premises:
All access decisions can be expressed as a privilege requirements rule.
All role or subject attributes can be expressed as group membership.
Group membership is both dynamic and contextual. Resources and their attributes are known a priori. If resources and attributes can change arbitrarily dynamically, this will decrease performance.
Knowledge of four things is used to resolve a permission question: 1. The Subject (the entity requesting the permission) 2. The Resource that the Subject is requesting permission about 3. The Action that the Subject wishes to perform 4. The Environment, which is a set of facts/assertions that the rules may take into account in order to make a permission determination.
The result will be either a yes or no answer as to whether permission is granted.
The access rules can have fairly complicated group membership conditions (e.g., a doctor who is an associate of a patient’s primary care physician can have read access to that patient’s medical record). Therefore, determining group membership may rely on a number of General Rules to help resolve the inferences (e.g., a doctor may be a member of a group; if another doctor is also a member of that group, then that doctor is an associate of the first doctor, etc.). By making group membership dynamic we can keep the access rules general.
IV. IMPLEMENTATION
The Fast Semantic ARBAC software prototype was designed to show how a system could quickly make access decisions based on the attribute values of the requesting agent. How the agent obtained the attribute values is outside the scope of the prototype; the ARBAC system is provided these from a separate source, projected to be a session authentication token (with a prescribed lifespan), that points to the attribute store, which has been obtained and encoded by the ARBAC system.
To achieve this, five conceptual classes were defined that constitute the “ARBAC view” of the world: Agents, Resources, Groups, ResourceCollections, and Policies. Two of these are collections, or sets: Groups (collections of Agents) and ResourceCollections (collections of Resources). They are hierarchical, e.g., one group may be a subset of another group, so any member of the subset group is automatically a member of the larger group. The other three classes are “flat” in an ontological sense, but contain many instances. Agents have (at least) a unique ID, and zero or more attribute/value pairs, which contain values that may be assigned to them by an organization or may be values contained in a security token. A Group is a set of Agents; group membership can be expressed in two ways: directly (an Agent by his/her ID value is asserted to be a member of a specific group) or indirectly (by specifying a set of attribute/value pairs an agent must possess in order to be a member of that group; any agent having all of the specified attribute/value pairs is considered a member of the group). Each group also has a unique ID. Unique IDs are considered special attributes and are assigned by the attribute signature assignment engine (ASAE), which updates the resource access registry (RAR). Agent IDs in the future will probably inherit the IDs of the identity token received from the external authentication service.
Resources and ResourceCollections are organized similarly to Agents and Groups. Resources also have a unique ID assigned by the attribute signature assignment engine (ASAE), and possess attribute/value pairs (such as ownedBy:: someOrganization, or locatedAt:: area). ResourceCollections likewise are sets of Resources, and membership can also be asserted directly or indirectly using a set of attribute/value pairs that a Resource must have.
Policies are different from the other four classes, in that they specify the “access rules” of what it takes for an Agent to perform some action on a Resource. In essence, a policy is just a 3-tuple containing a reference to a ResourceCollection ID that the policy controls, a reference to the Group ID to which an Agent must belong, and the action (from an enumerated set) which the Agent is requesting to perform.
The result is a simple but very flexible way to organize authorization decisions about accessing resources. In addition to general group membership, some special cases are also supported. For instance, a ResourceCollection can be created to contain a single resource in order to directly control it. Similarly, a Group can be defined to consist of a single agent thus allowing individualized policies. Again, Groups and ResourceCollections may be organized in a hierarchy which simplifies policy creation and application. Some advanced access control mechanisms, such as an expiration date/time for an agent’s token value, or the ability to specify negative conditions (e.g., agents which have a certain attribute/value pair(s) are NOT allowed access) are not implemented in this prototype, but are not precluded by this approach (i.e., they could be added at a later date without having to re-design the prototype system).
The ARBAC software is able to make quick authorization decisions because 1) most of the required information is known a priori and 2) the actual decision becomes a largely lookup-and-compare operation. The policies and resource attributes are known and stored in a location accessible to the ARBAC system. The Group and ResourceCollection definition rules are also known ahead of time and stored (although these may need to be recomputed from time to time). The agent’s attribute/value pairs are passed to the ARBAC system (usually via a secureID token, but it can be done in other ways) once the agent logs onto the system. The Groups to which the Agent belongs can then be pre-computed right after login (before the Agent even selects a Resource, in most cases). Once the agent selects a Resource and the action he/she wants to take, a series of lookups take place. First, all of the policies related to the Groups to which the Agent belongs and allow the requested Action are obtained. Next, all of the IDs of the ResourceCollections to which the Resource belongs are obtained. Then the retrieved policies are examined to see if any of them contain a reference to any of the relevant ResourceCollections. If any one of them does, then that allows the Agent to access the requested Resource and perform the desired action. If none of the policies contains a reference to any of the possible ResourceCollections, then the action is not allowed.
The actual implementation of the system allows for several possibilities. Based on our work in FY12, the initial design represented each of the five conceptual classes as OWL classes, and each instance as an OWL individual. Attribute/value pairs were implemented as OWL datatype properties, as were the policy tuples. While some of the reasoning (such as class hierarchy subsumption) could be done in OWL, most of the actual policy/rule reasoning was done using Prolog. The ARBAC system converted the (hierarchically extended) information into Prolog assertions and then made a prolog query to see if a particular Agent/Resource/Action combination was allowable. While this proved workable, expressing all of the information in OWL (and using the Jena OWL reasoner to do some of the pre-computation) turned out to be somewhat cumbersome. Furthermore, the OWL format is not very interoperable with what are likely to be the other components of a true ARBAC system (such as other databases). Since only a small portion of the OWL semantics were needed, it was decided to generalize the expression of the ARBAC data by allowing it to be held in other formats, e.g., JSON (Java Script Object Notation).
Using JSON instead of OWL (with Jena) resulted in a performance increase. Also, because many data sources support JSON this approach will make interoperability much easier. Another implementation change was to use a direct bit vector approach in Java for policy evaluation, rather than Prolog. The idea is that by keeping everything in Java (Prolog requires a call to an external .dll or .so application) and using the inherent efficiency of bit reasoning, performance would increase further. So a parallel implementation using the standard Java BitSet class was created, whereby each attribute/value pair is assigned a bit position at runtime. Group membership and ResourceCollection membership were then pre-computed using a set of bits (i.e., a bit vector). When an agent selects a Resource, all of the Policies are retrieved based on the pre-computed ResourceCollections, and these are compared with the set of the Agent’s Groups. If any Group is found in any of the policies, then the action is approved. Given the small set of data available, it was not possible to determine which approach (Prolog based or bit vector based, or both) will have the better performance at scale; this determination will need to be made during a follow-on test and integration effort.
V. OPTIMIZATION: BIT-ENCODING
Bit representation for ontology constructs (classes, properties, etc.), subsumption, and rule reasoning must address two related notions: 1) Efficiency of the representation in space and time. This includes efficiency of the encoding for storage purposes, but also compaction/compression techniques. It also includes the time required to perform the offline, development time encoding, as well as the time required to do the matching, subsumption computations, and automated reasoning performed at runtime. 2) Incremental encoding, i.e., making modifications dynamically during runtime to ontology constructs and rules, potentially recomputing the encodings of ontology constructs and rules, and then continuing efficient reasoning.
A. Ontology Constructs
The primary ontology constructs we use are the following: Group: A subclass of Collection. There are Classes of Groups (such as the Federally Funded Research and Development Center [FFRDC] class) and there are instances of Classes that are groups (e.g., the instances of the FFRDC class, such as MITRE, Aerospace, Los Alamos National Lab, etc.) Resource: A resource is any hardware, software, or service.
ResourceCollection: A subclass of Collection. There are Classes of ResourceCollections and there instances of Classes that are resource collections. User: A user (agent) is generally a person, but could be a software agent.
Policy: A policy is a set of access constraints on a Group or Resource created by a User who has the requisite permissions to create the policy.
Access: The kind of access a User has to a Resource, as permitted by a Policy. Examples: Create, Read,
Write, Delete, Execute, etc.
Because we are focusing primarily on “attributes” for access control, whether or not a User U belongs to a specific Group is a Boolean attribute, with value either ‘true’ or ‘false’ (of value ‘true’ if the User U is a member of a Group G, else of value ‘false’). Similarly, whether or not a Resource R is a member of a ResourceCollection RG is a Boolean attribute. If it helps us in our processing, even a User U can be considered a singleton Group, i.e., a specific instance of a Group having just one member, U.
We assume a User U can create a Policy P (perhaps of a specific type) that grants another User U’ specific Accesses A to a Resource R of ResourceCollection RC if the User is a member of some Group G and Group G ‘owns’ the ResourceCollection. Other policies may specify Roles, etc., which we are not yet addressing here.
The bit-representation for Group (and Resource) constructs is similar to the following, naïve representation:
Subsumption is the relatively simple automated reasoning that can be done on hierarchies of classes, i.e., the taxonomic subclass ‘backbone’o ft heo ntology.T heses ubclassh ierarchies are important for ontologies, but also important for strongly typed programming languages, which perform subsumption reasoning as ‘type inference’ over the formal types of constructions in the specific program.
Ait-Kaci et al [
An ontology subclass relation is an ordering relation on the classes, i.e., reflexive, antisymmetric, and transitive. OWL provides a top (greatest or most general) and bottom (least or most specific) class, called respectively Thing and Nothing, which makes OWL into a language able to model bounded (semi-) lattices. Bottom is often notated as , with top notated as ⊤.
C. Encoding Bit Representations of Subsumption and Inheritance
We will discuss encodings proposed in the literature, beginning first with a naïve bit matrix representation. For all of these encodings, we adapt the example used by [17, p. 1617], displayed in graph form as the ontology of classes in Figure 3 (where the isa relation is taken to be synonymous with the subclass relation). We use this example, rather than one drawn from our domain ontology, simply because our ontology does not currently have much depth and no multiple inheritance, which this example has. Note that these ‘role’ subclasses are not ontologically correct, but have been accommodated to a simple example.
Table 2 displays the naïve bit matrix representation for this ontology’s subsumption relations. Note that the bit assignment goes as follows: 1) Initially assign 1 (true) for every class (i, j) (where i is the row, j is the column) and itself, because every class subsumes itself. This means there is a diagonal with value 1 from (1, 1) to (n, n). 2) Then for each cell of the matrix (i, j), if the class i is an ancestor of class j, assign the value 1, otherwise assign the value 0. Teaching Assistant This encoding thus is the reflexive, transitive closure of the (antisymmetric) subclass (isa) hierarchy of Figure 4.
The naïve bit-assignment algorithm as represented in Table 2 is bottom-up, with an implicit ‘bottom’ ( ). The classes Employee and Student, and then Person, are the only classes which have subclasses.
Subsumption between two classes can then be computed in constant time using a binary AND operation on the bit vectors of the two classes. The subsumption operator over the bitencoded classes is defined as follows.
Definition: Subsumption over Bit-Encoded Classes:
Let x1, …, xn, be classes in a subclass hierarchy, be an bitencoding function, and ⊑ be the subsume relation (where , are classes and ⊑ is read as ‘class subsumes class ’): Then the following holds: i. (xi) ⊑ (xj) (xi) AND (xj) = (xj) ii.
[the encoding of the first class subsumes the encoding of the second class if and only if the binary AND of those encodings is equal to the encoding of the second class] (xj) ⊑/ (xi) (xj) AND (xi) (xj)
[the encoding of the first class does not subsume the encoding of the second class if and only if the binary AND of those encodings is not equal to the encoding of the second class] Example 1: Does TeachingAssistant subsume AssociateProfessor? I.e., does AssociateProfessor occur in the transitive closure of the subclass relation of TeachingAssistant? SubsumeS (TeachingAssistant, AssociateProfessor) = AND (0000001, 0001000) = 00000000, i.e., no.
Example 2: Does Person subsume TeachingAssistant? Subsumes (Person, TeachingAssistant)
= AND (1111111, 0000001) = 0000001, i.e., yes, because the result 0000001 = 0000001 (the encoding for TeachingAssistant.
Example 3: Does Employee subsume Student? Subsumes (Employee, Student)
= AND (0011101, 0100011) = 0000001, i.e., no, because the result 0000001 0100011 (the encoding for Student).
What if one wants at runtime to add a new class incrementally (dynamically) after the above bit-representation has been generated at development time? We add the new class ResearchAssistant to the original ontology, resulting in Figure 4.
Recomputing our bit-matrix, we arrive at the following, Table 3. Note that we have to add a new bit by creating a new row and new column for ResearchAssistant, which we add as a new i+1 row and a new j+1 column into the matrix (but above
Fig. 4. Academic Role Ontology + ResearchAssistant
If we added the new bit as a new row and new column at the beginning of the matrix, then we would maintain the 1-bit diagonal we saw in Table 2. In addition, of course, we have to update the entries in the new Research Assistant column with their values (1 if an ancestor of Research Assistant, 0 otherwise). The naïve bit-encoding of Subsumption requires n2 bits.
Ait-Kaci et al [
i: row j: column Person Student Employee Associate Professor Tenured Professor
PhD Student Teaching Assistant Research Assistant 1 1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 whenever a false positive subsumption would result. If incremental updates to the encoding are necessary, there are potential complications. If one wants to add new leaf (terminal) class nodes to the hierarchy, such as we did with ResearchAssistant above, there are no issues. However, if one wants to add new non-terminal (or root) nodes, there are complications. If a class Cj is added that has the same inheriting subclasses as an existing class Ci, then a new bit must be added to re-encode the existing class and all of its ancestors too. In addition, any new non-terminal class will have to have the ancestors of its children classes checked for conflicting encodings.
For a discussion of other bit-encoding techniques, the interested reader is directed to [17, pp. 16-23]. There are other encoding approaches, including interval-encodings. Intervalbased encodings compute non-overlapping codes for the children within the interval of the parent, but do not support multiple inheritance.
In fact, although each of the above approaches out-perform
the naïve encoding, all of them have some issues (except
perhaps [
Rules too may be given encodings, but space limitations
preclude a discussion of this topic here, but see [
There is much previous related research across multiple dimensions (access control regimes, policy languages and approaches, specialized languages (and logics) vs. ontology approaches, knowledge compilation issues, bit-vector and other optimization approaches, social network approaches, privacy vs. security issues and approaches, etc.) that have influenced our current and impending work.
In order to accomplish our objectives it was necessary to
link a security policy model to a policy language with
sufficient expressive power to ensure logical consistency. We
extend the NIST Role-Based Access Control (RBAC) security
model [
In addition, there is extensive research in more general
policy-based approaches that could be employed also for
access control [
There are other Semantic Web-based approaches (including
[
For implementation in real-time, via a bit-vector or other
efficient encodings that can be used for rapid run-time
reasoning, we’ve looked at [
Our own previous work addressed issues in translating
OWL/RDF ontologies and Semantic Web Rule Language
Rules (SWRL) [
Although we have investigated and implemented some optimizations, e.g., extensionalization and delayed rule evaluation, we have only rudimentarily implemented the second-level of optimization we intended, i.e., the bitrepresentation execution at runtime.
If we had additional time, we intended to implement the
prime-number bit-encoding of subsumption described in [
Therefore, we would consider implementing the
bitencoding scheme based on assigning prime numbers to nodes
in the class and property subsumption graphs, as developed by
Preuveneers and Berbers [
FIG. 5. PRIME NUMBER ENCODING FOR CLASS SUBSUMPTION
In addition to the use of prime numbers, the scheme of [
Evaluation done in [30, p. 32] shows that subsumption testing in his scheme is much faster than that of some major existing description logic reasoners, on the order of 250 times faster than Pellet. An evaluation performed on a different project we are involved in, written in C/C++ demonstrated 1000% improvement using this method of subsumption checking over the previous naïve, breadth-first search of the subsumption graph.
ACKNOWLEDGMENT © 2013, The MITRE Corporation. All Rights Reserved.