Fast Semantic Attribute-Role-Based Access Control (ARBAC) Leo Obrsta, Dru McCandlessb, David Ferrella The MITRE Corporation a McLean, VA b Colorado Springs, CO {lobrst, mccandless, ferrell}@mitre.org Abstract—We report on our research effort, called Fast expressive power to ensure logical consistency. We used a Semantic Attribute-Role-Based Access Control (ARBAC), to modified Attribute-Role-Based Access Control (ARBAC) develop a semantic platform-independent framework enabling security model and an OWL ontology with additional rules in a information originators and security administrators to specify logic programming framework to express access policy, going access rights to information consistently and completely, in a beyond the limitations of previous attempts in this vein, and social network environment, and then to rigorously enforce that then optimized with bit-vectors the runtime policy checking specification. We use a modified ARBAC security model and an inference. OWL ontology with additional rules in a logic programming and We focused on three aspects: expressivity, adaptability, and Java framework to express access policy, going beyond the efficiency. We developed two implementations: one that limitations of previous attempts in this vein. We also experimented with knowledge compilation optimizing techniques transforms the policy model instance into a logic programming that allow access policy constraint checking to be implemented in execution environment that includes rules; and a second that real-time, via a bit-vector encoding that can be used for rapid transforms the model instance into Java data structures, that in run-time reasoning. turn are optimized via a bit-encoding. In both cases, the prototype was embedded in a Java program that interfaces with Index Terms—access control policy, attribute-based, role- external services, e.g., obtaining identity and access tokens based, Semantic Web, logic programming, knowledge (and their specific attribute information) from the compilation, social network, ontology, rule-based reasoning authentication service. The structure of the rest of the paper is as follows. In I. INTRODUCTION section II, we present the overall architecture and describe the This paper is a report of our effort to provide a semantic runtime components. Then in section III, we briefly walk platform-independent framework so that information through the processing involved, followed in section IV by a originators and security administrators can specify access rights discussion of the implementation. Section V addresses the to information consistently and completely, in a social network optimization issues. We introduce related work in section VI, environment, and then to rigorously enforce that specification. and finally, in section VII, we propose future directions. In previous work [1], we discussed the architecture and some II. SYSTEM ARCHITECTURE AND RUNTIME COMPONENTS issues with optimization. In this paper, we introduce the architecture (adapted from [1]), but focus more on the The general system architecture of the semantic ARBAC optimization and implementation issues; as such, this paper can system is represented in Figure 1. It consists of three processes be viewed as a follow-on to [1]. which flow from left to right. The three processes are: 1) the For many sensitivity, privacy, and proprietary reasons, Development time process; 2) the Transformation time process; information sharing cannot be totally open. This is especially and 3) the Execution (runtime) process. true for collaborative social environments such as the emerging The Development process (the red rounded rectangle in MITRE Partnership Network (MPN), a large-scale Figure 1) involves: environment for group-based (social network) information 1) The creation (or update) of the ARBAC ontology, sharing among disparate governmental, commercial, academic, represented in OWL and RDF, i.e., the semantic policy and other communities. model (SPM); and In addition, it is difficult to enforce unambiguous access 2) The instantiation of the specific ARBAC policy (policies) rights and information privileges consistently and coherently to be transformed and deployed, i.e., the semantic policy and apply the access rules correctly and efficiently. instance (SPI). This is an instance of the semantic policy In a collaborative social environment, access control of model. information protecting privacy, security, and also enabling a The Transformation process (the yellow rounded rectangle complex range of policy respecting those requirements, is in Figure 1) involves developing and/or generating in Prolog difficult. and Java: To accomplish these objectives it is necessary to link a security policy model to a policy language with sufficient Approved for Public Release; Distribution Unlimited. 13-3295 STIDS 2013 Proceedings Page 133 1) The transformer interpreter that will take the SPI and standards, user- and group-level passwords, encryption generate the runtime semantic policy instance (RSPI), methods, hashing algorithms and values, etc.), Classification which is the bit-vector representation of the policy + Level (proprietary, sensitive, confidential, secret, top-secret, rules; etc.), Identity (Public Key Infrastructure [PKI], digital certificates, etc.), Time (time-stamps, time intervals with 2) The attribute signature assignment engine (ASAE) which respect to various policy notions), etc. 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. Fig. 2. ARBAC Runtime System Components 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. B. Other Components of the Architecture For more detailed descriptions of other components of the architecture, including the SPI, RSPI, RAR, ASAE, RIE, Fig. 1. Fast Semantic ARBAC System Architecture RUAR, the OWL parser, and external service interface, we direct interested readers to [1]. Figure 2 displays the runtime system components of the Fast Semantic ARBAC system. The runtime system III. ACCESS DECISION PROCESS FLOW AND WALKTHROUGH components view represents most components of the system The following depicts the access decision process flow. architecture modules displayed in Figure 1, but focuses on their x Initially, the Policy/Rules KB is read and loaded relationships at runtime only. (including any general rules that apply to all A. Semantic Policy Model (SPM) circumstances) by the inference engine. x Then a request comes in containing the Subject, The SPM consists of the OWL ontology classes, object Resource, Action, and Environment. properties, and data properties. The major classes consist of: Subject (the person, organization, software that requests x The   Subject’s   Group   membership   is   looked   up   and   specific access to a resource), Action (the kind of access formed. requested, e.g., read, write, create, delete, execute, etc.), x An initial Resource/Group/Access check may be Resource (the object needing to be accessed by a subject: performed. executable, graphic, text, sound, video, hardware, etc.), x For some common accesses these may be cached, or Environment (salient   aspects   of   the   space   or   session’s   may require no further processing if a quick decision environment, e.g., risk or alert level, entry network domain), can be made. Role (traditional roles such as administrator, expert, end user, x Otherwise, the appropriate rule set is generated and developer, etc., that are also related to groups), and related populated with: any referenced access rule (pre-filtered notions: Authentication (how   one   authenticates   one’s   identity   to keep the KB small and fast), all facts about the and   so,   derivatively,   one’s   potential   access   rights), Security Subject, Resource, Groups, and Environment, and (can span information security notions such as protocols, General (generally applicable) rules. STIDS 2013 Proceedings Page 134 x The rule set is passed to a runtime inference engine group membership dynamic we can keep the access rules which evaluates the truth of the permission statement general. (something along the lines of allow(Subject, Access, Resource)). IV. IMPLEMENTATION x The Inference Engine passes back the permission The Fast Semantic ARBAC software prototype was decision. designed to show how a system could quickly make access The semantic policy model (SPM) is the holder of much of decisions based on the attribute values of the requesting agent. the underlying knowledge. Its contents include: How the agent obtained the attribute values is outside the x Ontology scope of the prototype; the ARBAC system is provided these x Access Rules from a separate source, projected to be a session authentication x Group Membership Rules token (with a prescribed lifespan), that points to the attribute x General Rules store, which has been obtained and encoded by the ARBAC The Access Rules ultimately determine whether an action system. can be performed on a resource (a ‘Privilege’   to   denote   the   To achieve this, five conceptual classes were defined that pairing of actions and resources); each rule has three parts: constitute   the   “ARBAC   view”   of   the   world:     Agents,   1. The head, or consequence, which is always a Resources, Groups, ResourceCollections, and Policies. Two privilege (e.g., hasPrivilege(subject22, of these are collections, or sets: Groups (collections of read,medicalRecord66) ). This leaves the body of the Agents) and ResourceCollections (collections of Resources). rule which for convenience is broken into 2 parts: They are hierarchical, e.g., one group may be a subset of 2. The Group membership required to obtain the another group, so any member of the subset group is privilege, and automatically a member of the larger group. The other three 3. Any additional requirements, expressed in terms of classes   are   “flat”   in   an   ontological   sense,   but   contain   many   environment variables. instances. Agents have (at least) a unique ID, and zero or Example: more attribute/value pairs, which contain values that may be hasPrivilege(Subject, Action, Resource) assigned to them by an organization or may be values m agent(Subject), member(Subject, Group), contained in a security token. A Group is a set of Agents; environmentalConstraints(Group, Action, Resource, group membership can be expressed in two ways: directly (an Environment), groupWithPrivilege(Group, Action, Agent by his/her ID value is asserted to be a member of a Resource, Environment). specific group) or indirectly (by specifying a set of Premises: attribute/value pairs an agent must possess in order to be a x All access decisions can be expressed as a member of that group; any agent having all of the specified privilege m requirements rule. attribute/value pairs is considered a member of the group). x All role or subject attributes can be expressed as Each group also has a unique ID. Unique IDs are considered group membership. special attributes and are assigned by the attribute signature x Group membership is both dynamic and contextual. assignment engine (ASAE), which updates the resource access registry (RAR). Agent IDs in the future will probably inherit x Resources and their attributes are known a priori. If the IDs of the identity token received from the external resources and attributes can change arbitrarily authentication service. dynamically, this will decrease performance. Resources and ResourceCollections are organized similarly Knowledge of four things is used to resolve a permission to Agents and Groups. Resources also have a unique ID question: assigned by the attribute signature assignment engine (ASAE), 1. The Subject (the entity requesting the permission) and possess attribute/value pairs (such as ownedBy:: 2. The Resource that the Subject is requesting someOrganization, or locatedAt:: area). ResourceCollections permission about likewise are sets of Resources, and membership can also be 3. The Action that the Subject wishes to perform asserted directly or indirectly using a set of attribute/value 4. The Environment, which is a set of facts/assertions pairs that a Resource must have. that the rules may take into account in order to make Policies are different from the other four classes, in that a permission determination. they  specify  the  “access  rules”  of  what  it  takes  for  an  Agent  to   The result will be either a yes or no answer as to whether perform some action on a Resource. In essence, a policy is permission is granted. just a 3-tuple containing a reference to a ResourceCollection The access rules can have fairly complicated group ID that the policy controls, a reference to the Group ID to membership conditions (e.g., a doctor who is an associate of a which an Agent must belong, and the action (from an patient’s   primary   care   physician   can   have   read access to that enumerated set) which the Agent is requesting to perform. patient’s   medical   record).     Therefore,   determining   group   The result is a simple but very flexible way to organize membership may rely on a number of General Rules to help authorization decisions about accessing resources. In addition resolve the inferences (e.g., a doctor may be a member of a to general group membership, some special cases are also group; if another doctor is also a member of that group, then supported. For instance, a ResourceCollection can be created that doctor is an associate of the first doctor, etc.). By making STIDS 2013 Proceedings Page 135 to contain a single resource in order to directly control it. be held in other formats, e.g., JSON (Java Script Object Similarly, a Group can be defined to consist of a single agent Notation). thus allowing individualized policies. Again, Groups and Using JSON instead of OWL (with Jena) resulted in a ResourceCollections may be organized in a hierarchy which performance increase. Also, because many data sources simplifies policy creation and application. Some advanced support JSON this approach will make interoperability much access control mechanisms, such as an expiration date/time for easier. Another implementation change was to use a direct bit an   agent’s   token   value,   or   the   ability   to   specify   negative   vector approach in Java for policy evaluation, rather than conditions (e.g., agents which have a certain attribute/value Prolog. The idea is that by keeping everything in Java (Prolog pair(s) are NOT allowed access) are not implemented in this requires a call to an external .dll or .so application) and using prototype, but are not precluded by this approach (i.e., they the inherent efficiency of bit reasoning, performance would could be added at a later date without having to re-design the increase further. So a parallel implementation using the prototype system). standard Java BitSet class was created, whereby each The ARBAC software is able to make quick authorization attribute/value pair is assigned a bit position at runtime. decisions because 1) most of the required information is Group membership and ResourceCollection membership were known a priori and 2) the actual decision becomes a largely then pre-computed using a set of bits (i.e., a bit vector). When lookup-and-compare operation. The policies and resource an agent selects a Resource, all of the Policies are retrieved attributes are known and stored in a location accessible to the based on the pre-computed ResourceCollections, and these are ARBAC system. The Group and ResourceCollection compared  with  the  set  of  the  Agent’s  Groups.    If  any  Group  is   definition rules are also known ahead of time and stored found in any of the policies, then the action is approved. (although these may need to be recomputed from time to Given the small set of data available, it was not possible to time).     The   agent’s   attribute/value   pairs   are   passed   to   the   determine which approach (Prolog based or bit vector based, ARBAC system (usually via a secureID token, but it can be or both) will have the better performance at scale; this done in other ways) once the agent logs onto the system. The determination will need to be made during a follow-on test and Groups to which the Agent belongs can then be pre-computed integration effort. right after login (before the Agent even selects a Resource, in most cases). Once the agent selects a Resource and the action V. OPTIMIZATION: BIT-ENCODING he/she wants to take, a series of lookups take place. First, all Bit representation for ontology constructs (classes, of the policies related to the Groups to which the Agent properties, etc.), subsumption, and rule reasoning must address belongs and allow the requested Action are obtained. Next, all two related notions: of the IDs of the ResourceCollections to which the Resource 1) Efficiency of the representation in space and time. This belongs are obtained. Then the retrieved policies are includes efficiency of the encoding for storage examined to see if any of them contain a reference to any of purposes, but also compaction/compression techniques. the relevant ResourceCollections. If any one of them does, It also includes the time required to perform the offline, then that allows the Agent to access the requested Resource development time encoding, as well as the time and perform the desired action. If none of the policies required to do the matching, subsumption contains a reference to any of the possible computations, and automated reasoning performed at ResourceCollections, then the action is not allowed. runtime. The actual implementation of the system allows for several 2) Incremental encoding, i.e., making modifications possibilities. Based on our work in FY12, the initial design dynamically during runtime to ontology constructs and represented each of the five conceptual classes as OWL rules, potentially recomputing the encodings of classes, and each instance as an OWL individual. ontology constructs and rules, and then continuing Attribute/value pairs were implemented as OWL datatype efficient reasoning. properties, as were the policy tuples. While some of the reasoning (such as class hierarchy subsumption) could be done A. Ontology Constructs in OWL, most of the actual policy/rule reasoning was done The primary ontology constructs we use are the following: using Prolog. The ARBAC system converted the x Group: A subclass of Collection. There are Classes of (hierarchically extended) information into Prolog assertions Groups (such as the Federally Funded Research and and then made a prolog query to see if a particular Development Center [FFRDC] class) and there are Agent/Resource/Action combination was allowable. While instances of Classes that are groups (e.g., the instances this proved workable, expressing all of the information in of the FFRDC class, such as MITRE, Aerospace, Los OWL (and using the Jena OWL reasoner to do some of the Alamos National Lab, etc.) pre-computation) turned out to be somewhat cumbersome. x Resource: A resource is any hardware, software, or Furthermore, the OWL format is not very interoperable with service. what are likely to be the other components of a true ARBAC x ResourceCollection: A subclass of Collection. There system (such as other databases). Since only a small portion are Classes of ResourceCollections and there instances of the OWL semantics were needed, it was decided to of Classes that are resource collections. generalize the expression of the ARBAC data by allowing it to STIDS 2013 Proceedings Page 136 x User: A user (agent) is generally a person, but could provides a top (greatest or most general) and bottom (least or be a software agent. most specific) class, called respectively Thing and Nothing, x Policy: A policy is a set of access constraints on a which makes OWL into a language able to model bounded Group or Resource created by a User who has the (semi-) lattices. Bottom is often notated as A, with top notated requisite permissions to create the policy. as ⊤. x Access: The kind of access a User has to a Resource, C. Encoding Bit Representations of Subsumption and as permitted by a Policy. Examples: Create, Read, Inheritance Write, Delete, Execute, etc. We will discuss encodings proposed in the literature, Because  we  are  focusing  primarily  on  “attributes”  for   beginning first with a naïve bit matrix representation. For all access control, whether or not a User U belongs to a specific of these encodings, we adapt the example used by [17, p. 16- Group is a Boolean  attribute,  with  value  either  ‘true’  or  ‘false’   17], displayed in graph form as the ontology of classes in (of  value  ‘true’  if  the  User  U  is  a  member  of  a  Group  G,  else   Figure 3 (where the isa relation is taken to be synonymous of  value  ‘false’).  Similarly,  whether  or  not  a  Resource  R  is  a   with the subclass relation). We use this example, rather than member of a ResourceCollection RG is a Boolean attribute. If one drawn from our domain ontology, simply because our it helps us in our processing, even a User U can be considered ontology does not currently have much depth and no multiple a singleton Group, i.e., a specific instance of a Group having inheritance, which this example has. Note   that   these   ‘role’   just one member, U. subclasses are not ontologically correct, but have been We assume a User U can create a Policy P (perhaps of a accommodated to a simple example. 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: Table 1. User Groups: Bit Representation Fig. 3. Academic Role Ontology G1 G2 G3 G4 G5 G6 G7 G8 G9 U1 1 1 0 0 0 0 0 0 0 Table 2 displays the naïve bit matrix representation for this U2 0 1 1 0 0 0 0 0 0 ontology’s  subsumption  relations.  Note  that  the  bit  assignment   U3 0 0 1 1 1 0 0 0 0 U4 1 0 1 1 1 1 0 0 0 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 B. Subsumption class subsumes itself. This means there is a diagonal Subsumption is the relatively simple automated reasoning with value 1 from (1, 1) to (n, n). that can be done on hierarchies of classes, i.e., the taxonomic 2) Then for each cell of the matrix (i, j), if the class i is subclass ‘backbone’  of  the  ontology.  These  subclass  hierarchies   an ancestor of class j, assign the value 1, otherwise are important for ontologies, but also important for strongly assign the value 0. typed programming languages, which perform subsumption reasoning   as   ‘type   inference’   over   the   formal   types   of   Table 2. Naïve bit matrix representation of Subsumption constructions in the specific program. i: row Pe St E As Te PhD Teachi Ait-Kaci et al [4] proposed a number of bit-representations j: column rs ud m so nu Studen ng that could be used for very efficient subsumption reasoning, by on en pl ci re t Assista plungeing the hierarchy of classes (or types), which typically t oy at d nt ee e Pr constitutes   a   ‘partially   ordered   set’   (poset),   into   a   boolean Pr of lattice, thus enabling efficient Greatest Lower Bound (GLB) of es and Least Upper Bound (LUB) operations, and efficient es so so r transitive closure. In an arbitrary poset, neither the GLB or the r LUB is guaranteed to exist, but there are formal structural embeddings one can perform on the poset into an order- Person 1 1 1 1 1 1 1 preserving structure, a semilattice, a lower semilattice in this Student 0 1 0 0 0 1 1 initial case, which preserves the GLB, sometimes called a meet-semilattice, which says that for any nonempty finite Employee 0 0 1 1 1 0 1 subset of poset, there is a GLB. Note that the ordering relation on the elements of the poset (which define the poset) is Associate 0 0 0 1 0 0 0 Professor typically   notated   as   ≤   ,   e.g.,   a   ≤   b,   where   ≤   is   reflexive,   antisymmetric, and transitive. Tenured 0 0 0 0 1 0 0 An ontology subclass relation is an ordering relation on the Professor classes, i.e., reflexive, antisymmetric, and transitive. OWL STIDS 2013 Proceedings Page 137 PhD 0 0 0 0 0 1 0 Recomputing our bit-matrix, we arrive at the following, Student Table 3. Note that we have to add a new bit by creating a new Teaching 0 0 0 0 0 0 1 row and new column for ResearchAssistant, which we add as a Assistant new i+1 row and a new j+1 column into the matrix (but above A 0 0 0 0 0 0 0 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’   (A). 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 bit- Fig. 4. Academic Role Ontology + ResearchAssistant encoded classes is defined as follows. If we added the new bit as a new row and new column at Definition: Subsumption over Bit-Encoded Classes: the beginning of the matrix, then we would maintain the 1-bit Let x1, …,  xn, be classes in a subclass hierarchy, J be an bit- diagonal we saw in Table 2. In addition, of course, we have to encoding function, and ⊑ be the subsume relation (where D, E update the entries in the new Research Assistant column with are classes and D ⊑ E is  read  as  ‘class  D subsumes class E’): their values (1 if an ancestor of Research Assistant, 0 Then the following holds: otherwise). The naïve bit-encoding of Subsumption requires i. J (xi) ⊑ J (xj) l J (xi) AND J (xj) = J (xj) n2 bits. [the encoding of the first class subsumes the Table 3. Naïve bit matrix representation of Subsumption with Incrementally Added ResearchAssistant Class encoding of the second class if and only if the binary AND of those encodings is equal to the encoding of i: row Resear Pe St E As Te PhD Teachi the second class] j: column ch rs ud m so nu Studen ng ii. J (xj) ⊑ / J (xi) l J (xj) AND J (xi) z J (xj) Assista nt on en t pl oy ci at re d t Assista nt ee e Pr [the encoding of the first class does not subsume Pr of the encoding of the second class if and only if the of es binary AND of those encodings is not equal to the es so so r encoding of the second class] r Example 1: Does TeachingAssistant subsume Person 1 1 1 1 1 1 1 1 AssociateProfessor? Student 1 0 1 0 0 0 1 1 I.e., does AssociateProfessor occur in the transitive closure of the subclass relation of TeachingAssistant? Employee 1 0 0 1 1 1 0 1 SubsumeS (TeachingAssistant, AssociateProfessor) Associate 0 0 0 0 1 0 0 0 = AND (0000001, 0001000) = 00000000, i.e., no. Professor Example 2: Does Person subsume TeachingAssistant? Tenured 0 0 0 0 0 1 0 0 Professor Subsumes (Person, TeachingAssistant) = AND (1111111, 0000001) = 0000001, i.e., yes, PhD 0 0 0 0 0 0 1 0 because the result 0000001 = 0000001 (the encoding for Student TeachingAssistant. Teaching 0 0 0 0 0 0 0 1 Assistant Example 3: Does Employee subsume Student? Research 1 0 0 0 0 0 0 0 Subsumes (Employee, Student) Assistant = AND (0011101, 0100011) = 0000001, i.e., no, A 0 0 0 0 0 0 0 0 because the result 0000001 z 0100011 (the encoding for Student). What if one wants at runtime to add a new class Ait-Kaci et al [4] propose a number of new methods for incrementally (dynamically) after the above bit-representation encoding subsumption. Their first method requires a bottom-up has been generated at development time? We add the new class (from the terminal classes to the root class) computing of the ResearchAssistant to the original ontology, resulting in Figure binary OR of the bits assigned to children classes, the result of 4. which becomes the bit-encoding of their parent classes. New bits are introduced whenever a parent has just one class and STIDS 2013 Proceedings Page 138 whenever a false positive subsumption would result. If Our own previous work addressed issues in translating incremental updates to the encoding are necessary, there are OWL/RDF ontologies and Semantic Web Rule Language potential complications. If one wants to add new leaf (terminal) Rules (SWRL) [25] into logic programming for efficient class nodes to the hierarchy, such as we did with runtime reasoning, and employing knowledge compilation ResearchAssistant above, there are no issues. However, if one techniques [26-28], which we also generalized to address wants to add new non-terminal (or root) nodes, there are services using first-order logic theorem provers and for complications. If a class Cj is added that has the same ontology alignment [29]. inheriting subclasses as an existing class Ci, then a new bit must be added to re-encode the existing class and all of its VII. FUTURE WORK ancestors too. In addition, any new non-terminal class will have to have the ancestors of its children classes checked for Although we have investigated and implemented some conflicting encodings. optimizations, e.g., extensionalization and delayed rule For a discussion of other bit-encoding techniques, the evaluation, we have only rudimentarily implemented the interested reader is directed to [17, pp. 16-23]. There are other second-level of optimization we intended, i.e., the bit- encoding approaches, including interval-encodings. Interval- representation execution at runtime. based encodings compute non-overlapping codes for the If we had additional time, we intended to implement the children within the interval of the parent, but do not support prime-number bit-encoding of subsumption described in [17]. multiple inheritance. In general, for the restricted reasoning we need for access In fact, although each of the above approaches out-perform control policy enforcement as described in this paper, and the naïve encoding, all of them have some issues (except given the probable volume of access request determinations perhaps [17], which relies on binary representation of prime (and thus subsumption and equivalence checks, rule numbers) with incremental (dynamic) updates, requiring some execution) we foresee needing in a complex collaborative recomputation of encodings and determination of conflicts, social network environment such as the MPN, optimized which in turn may require recomputation of encodings. efficient automated reasoning is necessary. Traditional, more Rules too may be given encodings, but space limitations general description logic reasoners were deemed too slow preclude a discussion of this topic here, but see [8] for (Pellet, etc.) In addition, most proposed bitmap encodings for Boolean satisfiability (SAT) reasoning using bit-matrices. subsumption and type reasoning are efficiently statically initialized and then used, but dynamically updating the VI. RELATED WORK subsumption/type hierarchy, i.e., adding, deleting, modifying There is much previous related research across multiple classes and properties (which will happen, under the Open dimensions (access control regimes, policy languages and World Assumption of OWL and first-order logic), leads to approaches, specialized languages (and logics) vs. ontology degraded performance and increasingly baroque re-encodings approaches, knowledge compilation issues, bit-vector and to avoid conflicts. other optimization approaches, social network approaches, Therefore, we would consider implementing the bit- privacy vs. security issues and approaches, etc.) that have encoding scheme based on assigning prime numbers to nodes influenced our current and impending work. in the class and property subsumption graphs, as developed by In order to accomplish our objectives it was necessary to Preuveneers and Berbers [17, 30]. Adding a new class or link a security policy model to a policy language with property does not require re-encoding. Furthermore, the sufficient expressive power to ensure logical consistency. We encoding automatically provides us the direction of the extend the NIST Role-Based Access Control (RBAC) security relationship. Modular hierarchies, each separately encoded, model [15] and related approaches [18-19], as have many with very efficient subsumption-checking, are the result. other researchers to include attributes, and extend the Web Figure 5 depicts a subclass hierarchy encoded using prime Ontology Language (OWL) with additional rules to express numbers. access policy using logic programming, and beyond the limitations of [20]. Unfortunately, given our own space limitations here, we cannot do an extensive comparison of our approach across the multiples dimensions with other approaches, nor justly describe those other approaches. In addition, there is extensive research in more general policy-based approaches that could be employed also for access control [21-22]. There are other Semantic Web-based approaches (including [22]), some of which address more specifically social network types of applications [23, 24]. 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 [2-6, 7-12, 17]. For bit-vector representation to support RDF triples, we investigated [11-14]. FIG. 5. PRIME NUMBER ENCODING FOR CLASS SUBSUMPTION STIDS 2013 Proceedings Page 139 In addition to the use of prime numbers, the scheme of [17, Semantic Web Conference (ESWC 2010), Heraklion, Greece. May 30 – June 3, 2010.. 30] defines a compact binary matrix representation of the [15] http://csrc.nist.gov/groups/SNS/rbac/. inheritance relationships, which we will not go into here. [16] Neumann, T.; G.   Weikum.   2009.   “RDF-3X: a RISC-style engine for Evaluation done in [30, p. 32] shows that subsumption RDF.”  In  Proc.  of  VLDB,  pages  647-659, September 2009. testing in his scheme is much faster than that of some major [17] Preuveneers, D.; Berbers,  Y.,  2006.  “Prime  numbers  considered  useful:   existing description logic reasoners, on the order of 250 times Ontology encoding for   efficient   subsumption   testing,”   Tech.   Rep.   faster than Pellet. An evaluation performed on a different CW464. http://www.cs.kuleuven.be/publicaties/rapporten/cw/CW464. project we are involved in, written in C/C++ demonstrated Department of Computer Science, Katholieke Universiteit Leuven, Belgium (October 2006). 1000% improvement using this method of subsumption [18] Sandhu,  R.  1998.  “Role-based  access  control.”  In  M.  Zerkowitz, editor, checking over the previous naïve, breadth-first search of the Advances in Computers, volume 48. Academic Press. subsumption graph. [19] Sandhu, R.; E. J. Coyne; H. L. Feinstein; and   C.   E.   Youman.   “Role- based   access   control   models.”   1996.   IEEE   Computer,   29(2):38–47, ACKNOWLEDGMENT February 1996. © 2013, The MITRE Corporation. All Rights Reserved. [20] Finin, T.; A. Joshi; L. Kagal; J. Niu; R. Sandhu, W. Winsborough; and B.   Thuraisingham.   2008.   “ROWLBAC:   representing   role   based   access   REFERENCES control   in   OWL.”   In   Proceedings   of   the   13th   ACM   symposium   on   Access control models and technologies (SACMAT '08). ACM, New [1] Obrst,   L.;;   D.   McCandless;;   D.   Ferrell.   2012.   “Fast   Semantic   Attribute- York, NY, USA, 73-82. Role-Based  Access  Control  (ARBAC)  in  a  Collaborative  Environment.”   [21] Tonti, G.; J. M. Bradshaw; R. Jeffers, R. Montanar; N. Suri; and A. The 7th IEEE International Workshop on Trusted Collaboration Uszok.   2003.   “Semantic   web   languages   for   policy   representation   and   (TrustCol 2012), October 14–17, 2012, Pittsburgh, PA. reasoning:   A   comparison   of   kaos,   rei,   and   ponder.”   2nd   International   [2] Abadi, D. J.; A. Marcus; S. Madden; K.  J.  Hollenbach.  2007.  “Scalable   Semantic Web Conference (ISWC2003). Springer-Verlag. Semantic   Web   Data   Management   Using   Vertical   Partitioning.”   In   [22] Uszok, A.; J.M. Bradshaw; J. Lott; M. Breedy; L. Bunch; P. Feltovich; Proceedings of VLDB, pages 411~422, September 2007. M. Johnson; H. Jung. 2008. New Developments in Ontology-Based [3] Ait-Kaci, H.     1984.     “A   Lattice-Theoretic Approach to Computation Policy Management: Increasing the Practicality and Comprehensiveness Based on a Calculus of Partially-Ordered  Type  Structures.”    Ph.D  thesis,   of KAoS, IEEE Workshop on Policies for Distributed Systems and Computer and Information Science Dept., Univ. of Pennsylvania, Networks, 145-152. Philadelphia, PA. [23] Carminati, B.; E. Ferrari; and  A.  Perego,  “Rule-based access control for [4] Ait-Kaci,   H.;;   R.   Boyer;;   P.   Lincoln;;   R.   Nasr.   1989.   “Efficient   social  networks,”  in  Proc.  OTM  2006  Workshops,  ser.  LNCS,  vol.  4278.   Implementation  of  Lattice  Operations.”  TOPLAS  11-1-1989. Springer, Oct 2006, pp. 1734–1744. [5] Blandford, D. K.; Blelloch, G. E.; and   Kash,   I.   A.   2003.   “Compact   [24] Masoumzadeh,  Amirreza;;  James  Joshi.  2010.    “OSNAC:  An  Ontology- representations   of   separable   graphs.”   Proceedings   of   the   14 th Annual Based   Access   Control   Model   for   Social   Networking   Systems.”   Social   ACM-SIAM Symposium on Discrete Algorithms (Baltimore, Maryland, Computing (SocialCom), 2010 IEEE Second International Conference January 12 - 14, 2003). on Social Computing, 20-22 Aug. 2010, Minneapolis, MN, 751 – 759. [6] Blandford, D. K.; Blelloch, G. E.; and   Kash,   I.   A.   2004.   “An   [25] Horrocks I.; Patel-Schneider, P.; Boley H.; Tabet, S.; Grosof, B.; Dean, Experimental   Analysis   of   a   Compact   Graph   Representation.”   In   M.  2004.  “SWRL:  A  Semantic  Web  Rule  Language  Combining  OWL   Proceedings of ALENEX04. and  RuleML.”  /www.w3.org/Submission/SWRL/ . [7] Caseau, Y.; M. Habib; L. Nourine;;   O.   Raynaud.   1999.   “Encoding   of   [26] Samuel, K.; L. Obrst; S. Stoutenberg; K. Fox; P. Franklin; A. Johnson; multiple   inheritance   hierarchies   and   partial   orders.”   Computational   K.   Laskey;;   D.   Nichols;;   S.   Lopez;;   and   J.   Peterson.   2008.   “Applying Intelligence 15 (1), 50-62. Prolog to Semantic Web Ontologies & Rules: Moving Toward [8] Dershowitz,  N.  2008.  “Bit  Inference.”  Workshop  on  Practical  Aspects  of   Description   Logic   Programs.”   Journal   of   the   Theory   and   Practice   of   Automated Reasoning, August, 2008, Sydney. 26-35. Logic Programming (TPLP), M. Marchiori, ed., Cambridge University Press, Volume 8, Issue 03, May 2008, 301-322. [9] Fall,   A.   1995.   “Heterogeneous   Encoding.”   In   Proceedings   of   International KRUSE Symposium: Knowledge Retrieval, Use, and [27] Samuel, K.; L.  Obrst.  2007.  “Answer  Set  Programming:  Final  Report  on   Storage for Efficiency, Gerard Ellis, Robert Levinson, Andrew Fall, a Comparison Between ASP and Prolog for Semantic Web Ontology and Veronica Dahl, eds., Santa Cruz, CA, Aug. 11-13, pp. 134-146 (1995). Rule  Reasoning.”  October,  2007.  MITRE  MTR090069. [10] Krall, A.; Vitek, J., Horspool, 1997.  “Near  optimal  hierarchical  encoding   [28] Obrst, L; Stoutenburg, S; D. McCandless; D. Nichols; P. Franklin; M. of  types.”  11th  European  Conference  on  Object  Oriented  Programming   Prausa; R. Sward.   “Ontologies   for   Rapid   Integration   of   Heterogeneous   (ECOOP’97).  Springer  (1997). Data   for   Command,   Control,   &   Intelligence.”   Chapter   in:   Obrst,   Leo;;   Terry Janssen; Werner Ceusters, eds., 2010. Ontologies and Semantic [11] McGlothlin, J. P.; L.   Khan,   B.   Thuraisingham.   2011.   “RDFKB:   A   Technologies for the Intelligence Community. Amsterdam, The Semantic Web Knowledge  Base.”  IJCAI,  2011. Netherlands: IOS Press. [12] McGlothlin, J. P.; L.  Khan.  2008.  “RDFVector:  A  Scalable  Data  Model   [29] McCandless,   Dru;;   Leo   Obrst.   2009.   “Dynamic   Web   Service   Chaining   for   Efficient   Querying   of   RDF   Datasets.”   http://   using  OWL  and  a  Theorem  Prover.”  3rd  IEEE  International  Conference   www.utdallas.edu/~jpm083000/ssDBM.pdf. on Semantic Computing, Berkeley, CA, USA - September 14-16, 2009. [13] McGlothlin,   J.P.;;   L.   Khan.   2010b.   “Efficient   RDF   data   management   [30] Preuveneers, D.; Y. Berbers.  2008.  “Encoding  Semantic  Awareness  in   including provenance  and  uncertainty.”  IDEAS,  193-198, August 2010. Resource-Constrained  Devices,”  IEE  Intelligent  Systems,  March  – April, [14] McGlothlin,   J.   2010.   “RDFVector:   An   Efficient   and   Scalable   Schema   2008. for   Semantic   Web   Knowledge   Bases.”   PhD   Symposium,   7th   Extended   STIDS 2013 Proceedings Page 140