Role mining is a technique that is used to derive a role-based authorization policy from an existing policy. Given a set of users U , a set of permissions P , and a user–permission authorization relation \(\mathit {UPA} \subseteq U \times P\) , a role mining algorithm seeks to compute a set of roles R , a user–role authorization relation \(\mathit {UA} \subseteq U \times R\) , and a permission–role authorization relation \(\mathit {PA} \subseteq R \times P\) , such that the composition of UA and PA is close (in some appropriate sense) to UPA . Role mining is therefore a core problem in the specification of role-based authorization policies. Role mining is known to be hard in general and exact solutions are often impossible to obtain, so there exists an extensive literature on variants of the role mining problem that seek to find approximate solutions and algorithms that use heuristics to find reasonable solutions efficiently. In this article, we first introduce the Generalized Noise Role Mining problem (GNRM)—a generalization of the MinNoise Role Mining problem—which we believe has considerable practical relevance. In particular, GNRM can produce “security-aware” or “availability-aware” solutions. Extending the work of Fomin et al., we show that GNRM is fixed parameter tractable, with parameter \(r + k\) , where \(r\) is the number of roles in the solution and \(k\) is the number of discrepancies between \(\mathit {UPA}\) and the relation defined by the composition of \(\mathit {UA}\) and \(\mathit {PA}\) . We further introduce a bi-objective optimization variant of GNRM, where we wish to minimize both \(r\) and \(k\) subject to upper bounds \(r \le \bar{r}\) and \(k\le \bar{k}\) , where \(\bar{r}\) and \(\bar{k}\) are constants. We show that the Pareto front of this bi-objective optimization problem (BO-GNRM) can be computed in fixed-parameter tractable time with parameter \(\bar{r} +\bar{k}\) . From a practical perspective, a solution to BO-GNRM gives security managers the opportunity to identify a mined policy offering the best tradeoff between the number of policy discrepancies and the number of roles. We then report the results of our experimental work using the integer programming solver Gurobi to solve instances of BO-GNRM. Our key findings are that (a) we obtained strong support that Gurobi’s performance is fixed-parameter tractable, and (b) our results suggest that our techniques may be useful for role mining in practice, based on our experiments in the context of three well-known real-world authorization policies. We observed that, in many cases, our solver is capable of obtaining optimal solutions when the values of either k or r are small.

Role mining seeks to compute a set of roles R, a user-role authorization relation UA and a permission-role authorization relation PA, given a user-permission authorization relation UPA, and is therefore a core problem in the specification of role-based authorization policies. Role mining is known to be hard in general and exact solutions are often impossible to obtain, so there exists an extensive literature on variants of the role mining problem that seek to find approximate solutions and algorithms that use heuristics to find reasonable solutions efficiently.

Recent work has shown that many problems of satisfiability and resiliency in workflows may be viewed as special cases of the authorization policy existence problem (APEP), which returns an authorization policy if one exists and “No” otherwise. However, in many practical settings it would be more useful to obtain a “least bad” policy than just a “No,” where “least bad” is characterized by some numerical value indicating the extent to which the policy violates the base authorization relation and constraints. Accordingly, we introduce the Valued APEP, which returns an authorization policy of minimum weight, where the (non-negative) weight is determined by the constraints violated by the returned solution. We then establish a number of results concerning the parameterized complexity of Valued APEP. We prove that the problem is fixed-parameter tractable (FPT) if the set of constraints satisfies two restrictions, but is intractable if only one of these restrictions holds. (Most constraints known to be of practical use satisfy both restrictions.) Our analysis is based on the novel concept of a user profile. We also introduce a new type of resiliency problem in the context of workflow satisfiability, show how it can be addressed using Valued APEP, and use this to build a set of benchmark instances for Valued APEP. We describe two different formulations of this problem using mixed integer programming and report the results of computational experiments which solve the problem using these formulations as input to a general-purpose solver. Our results show that the formulation which employs the user profile concept, has FPT-like running time and usually significantly outperforms our naive formulation of the problem.

Problems of satisfiability and resiliency in workflows have been widely studied in the last decade. Recent work has shown that many such problems may be viewed as special cases of the authorization policy existence problem (APEP), which returns an authorization policy if one exists and "No'' otherwise. A solution may not exist because of the restrictions imposed by the base authorization relation and constraints that form part of the input to APEP.

User authorization queries in the context of role-based access control have attracted considerable interest in the past 15 years. Such queries are used to determine whether it is possible to allocate a set of roles to a user that enables the user to complete a task, in the sense that all the permissions required to complete the task are assigned to the roles in that set. Answering such a query, in general, must take into account a number of factors, including, but not limited to, the roles to which the user is assigned and constraints on the sets of roles that can be activated. Answering such a query is known to be NP-hard. The presence of multiple parameters and the need to find efficient and exact solutions to the problem suggest that a multi-variate approach will enable us to better understand the complexity of the user authorization query problem (UAQ). In this article, we establish a number of complexity results for UAQ. Specifically, we show the problem remains hard even when quite restrictive conditions are imposed on the structure of the problem. Our fixed-parameter tractable (FPT) results show that we have to use either a parameter with potentially quite large values or quite a restricted version of UAQ. Moreover, our second FPT algorithm is complex and requires sophisticated, state-of-the-art techniques. In short, our results show that it is unlikely that all variants of UAQ that arise in practice can be solved reasonably quickly in general.

Constraints such as separation-of-duty are widely used to specify requirements that supplement basic authorization policies. However, the existence of constraints (and authorization policies) may mean that a user is unable to fulfill her/his organizational duties because access to resources has been denied. In short, there is a tension between the need to protect resources (using policies and constraints) and the availability of resources. Recent work on workflow satisfiability and resiliency in access control asks whether this tension compromises the ability of an organization to achieve its objectives. In this paper, we develop a new method of specifying constraints which subsumes much related work and allows a wider range of constraints to be specified. The use of such constraints leads naturally to a range of questions related to “policy existence”, where a positive answer means that an organization's objectives can be realized. We analyze the complexity of these policy existence questions and, for particular sub-classes of constraints defined by our language, develop fixed-parameter tractable algorithms to solve them.11.An extended abstract of this paper appeared in the Proceedings of the Seventh ACM Conference on Data and Application Security and Privacy [1]. Research was partially supported by Leverhulme Trust grant RPG-2018-161 and Royal Society Wolfson Research Merit Award.

There has been a considerable amount of interest in recent years in the problem of workflow satisfiability, which asks whether the existence of constraints in a workflow specification makes it impossible to allocate authorized users to each step in the workflow. Recent developments have seen the workflow satisfiability problem (WSP) studied in the context of workflow specifications in which the set of steps may vary from one instance of the workflow to another. This, in turn, means that some constraints may only apply to certain workflow instances. Inevitably, WSP becomes more complex for such workflow specifications. Other approaches have considered the possibility of associating costs with the violation of "soft'' constraints and authorizations. Workflow satisfiability in this context becomes a question of minimizing the cost of allocating users to steps in the workflow. In this paper, we introduce new problems, which we believe to be of practical relevance, that combine these approaches. In particular, we consider the question of whether, given a workflow specification with costs and a "budget'', all possible workflow instances have an allocation of users to steps that does not exceed the budget. We design a fixed-parameter tractable algorithm to solve this problem parameterized by the total number of steps, release points and xor branchings.

Constraints such as separation-of-duty are widely used to specify requirements that supplement basic authorization policies. However, the existence of constraints (and authorization policies) may mean that a user is unable to fulfill her/his organizational duties because access to resources is denied. In short, there is a tension between the need to protect resources (using policies and constraints) and the availability of resources. Recent work on workflow satisfiability and resiliency in access control asks whether this tension compromises the ability of an organization to achieve its objectives. In this paper, we develop a new method of specifying constraints which subsumes much related work and allows a wider range of constraints to be specified. The use of such constraints leads naturally to a range of questions related to "policy existence", where a positive answer means that an organization's objectives can be realized. We provide an overview of our results establishing that some policy existence questions, notably for those instances that are restricted to user-independent constraints, are fixed-parameter tractable.

The study of canonically complete attribute-based access control (ABAC) languages is relatively new. A canonically complete language is useful as it is functionally complete and provides a "normal form" for policies. However, previous work on canonically complete ABAC languages requires that the set of authorization decisions is totally ordered, which does not accurately reflect the intuition behind the use of the allow, deny and not-applicable decisions in access control. A number of recent ABAC languages use a fourth value and the set of authorization decisions is partially ordered. In this paper, we show how canonical completeness in multi-valued logics can be extended to the case where the set of truth values forms a lattice. This enables us to investigate the canonical completeness of logics having a partially ordered set of truth values, such as Belnap logic, and show that ABAC languages based on Belnap logic, such as PBel, are not canonically complete. We then construct a canonically complete four-valued logic using connections between the generators of the symmetric group (defined over the set of decisions) and unary operators in a canonically suitable logic. Finally, we propose a new authorization language $\ptacll{\four}$, an extension of \ptacl, which incorporates a lattice-ordered decision set and is canonically complete. We then discuss how the advantages of $\ptacll{\four}$ can be leveraged within the framework of XACML.

It is increasingly common to outsource data storage to untrusted, third party (e.g. cloud) servers. However, in such settings, low-level online reference monitors may not be appropriate for enforcing read access, and thus cryptographic enforcement schemes (CESs) may be required. Much of the research on cryptographic access control has focused on the use of specific primitives and, primarily, on how to generate appropriate keys and fails to model the access control system as a whole. Recent work in the context of role-based access control has shown a gap between theoretical policy specification and computationally secure implementations of access control policies, potentially leading to insecure implementations. Without a formal model, it is hard to (i) reason about the correctness and security of a CES, and (ii) show that the security properties of a particular cryptographic primitive are sufficient to guarantee security of the CES as a whole.

There has been a considerable amount of interest in recent years in the problem of workflow satisfiability, which asks whether the existence of constraints in a workflow specification means that it is impossible to allocate authorized users to each step in the workflow. Recent developments have seen the workflow satisfiability problem (WSP) studied in the context of workflow specifications in which the set of steps may vary from one instance of the workflow to another. This, in turn, means that some constraints may only apply to certain workflow instances. Inevitably, WSP becomes more complex for such workflow specifications. In this paper, we present the first fixed parameter algorithms to solve WSP for workflow specifications of this type. Moreover, we significantly extend the range of constraints that can be used in workflow specifications of this type.

Attribute-based access control (ABAC) has attracted considerable interest in recent years, prompting the development of the standardized XML-based language XACML. ABAC policies written in languages like XACML have a tree-like structure, where leaf nodes are associated with authorization decisions and non-leaf nodes are associated with decision-combining algorithms. However, it may be difficult in XACML to construct a given policy due to the tree-structured nature of XACML and the way in which combining algorithms are defined. Furthermore, there is limited control over how requests are evaluated with respect to targets.

We may enforce an information flow policy by encrypting a protected resource and ensuring that only users authorized by the policy are able to decrypt the resource. In most schemes in the literature that use symmetric cryptographic primitives, each user is assigned a single secret and derives decry ption keys using this secret and publicly available information. Recent work has challenged this approach by developing schemes, based on a chain partition of the information flow policy, that do not require public information for key derivation, the trade-off being that a user may need to be assigned more than one secret. In general, many different chain partitions exist for the same policy and, until now, it was not known how to compute an appropriate one. In this paper, we introduce the notion of a tree partition, of which chain partitions are a special case. We show how a tree partition may be used to define a cryptographic enforcement scheme and prove that such schemes can be instantiated in such a way as to preserve the strongest security properties known for cryptographic enforcement schemes. We establish a number of results linking the amount of secret material that needs to be distributed to users with a weighted acyclic graph derived from the tree partition. These results enable us to develop efficient algorithms for deriving tree and chain partitions that minimize the total amount of secret material that needs to be distributed.

A computerized workflow management system may enforce a security policy, specified in terms of authorized actions and constraints, thereby restricting which users can perform particular steps in a workflow. The existence of a security policy may mean that a workflow is unsatisfiable, in the sense that it is impossible to find a valid plan (an assignment of steps to authorized users such that all constraints are satisfied). Work in the literature focuses on the workflow satisfiability problem, a decision problem that outputs a valid plan if the instance is satisfiable (and a negative result otherwise). In this paper, we introduce the Bi-Objective Workflow Satisfiability Problem (BO-WSP), which enables us to solve optimization problems related to workflows and security policies. In particular, we are able to compute a “least bad” plan when some components of the security policy may be violated. In general, BO-WSP is intractable from both the classical and parameterized complexity point of view (where the parameter is the number of steps). We prove that computing a Pareto front for BO-WSP is fixed-parameter tractable (FPT) if we restrict our attention to user-independent constraints. This result has important practical consequences, since most constraints of practical interest in the literature are user-independent. Our proof is constructive and defines an algorithm, the implementation of which we describe and evaluate. We also present a second algorithm to compute a Pareto front which solves multiples instances of a related problem using mixed integer programming (MIP). We compare the performance of both our algorithms on synthetic instances, and show that the FPT algorithm outperforms the MIP-based one by several orders of magnitude on most instances. Finally, we study the important question of workflow resiliency and prove new results establishing that known decision problems are fixed-parameter tractable when restricted to user-independent constraints. We then propose a new way of modeling the availability of users and demonstrate that many questions related to resiliency in the context of this new model may be reduced to instances of BO-WSP.

Resiliency is a relatively new topic in the context of access control. Informally, it refers to the extent to which a multi-user computer system, subject to an authorization policy, is able to continue functioning if a number of authorized users are unavailable. Several interesting problems connected to resiliency were introduced by Li, Wang and Tripunitara [13], many of which were found to be intractable. In this paper, we show that these resiliency problems have unexpected connections with the workflow satisfiability problem (WSP). In particular, we show that an instance of the resiliency checking problem (RCP) may be reduced to an instance of WSP. We then demonstrate that recent advances in our understanding of WSP enable us to develop fixed-parameter tractable algorithms for RCP. Moreover, these algorithms are likely to be useful in practice, given recent experimental work demonstrating the advantages of bespoke algorithms to solve WSP. We also generalize RCP in several different ways, showing in each case how to adapt the reduction to WSP. Li et al also showed that the coexistence of resiliency policies and static separation-of-duty policies gives rise to further interesting questions. We show how our reduction of RCP to WSP may be extended to solve these problems as well and establish that they are also fixed-parameter tractable.

Attribute-based access control (ABAC) has attracted considerable interest in recent years, resulting in an extensive literature on the subject, including the standardized XML-based language XACML. ABAC policies written in languages like XACML have a tree-like structure in which leaf nodes are associated with authorization decisions and non-leaf nodes are associated with decision-combining algorithms. In this paper, we consider the expressive power of the rule- and policy-combining algorithms defined by the XACML standard. In particular, we identify unexpected dependencies between the combining algorithms and demonstrate that there exist useful combining algorithms that cannot be expressed by any combination of XACML combining algorithms. We briefly discuss the decision operators defined in the PTaCL language, an abstract language for defining ABAC policies, and the advantages of replacing the XACML combining algorithms with the PTaCL operators. Following this, we review results in the literature on multi-valued logic and introduce the notion of canonically complete policy languages. We discuss important practical advantages of canonically complete policy languages, primarily in simplifying policy specification and providing efficiently enforceable policies. Finally, we propose a new policy authorization language PTaCL which is canonically complete and show it is capable of expressing any arbitrary policy in a normal form and discuss the advantages of using PTaCL over existing policy languages such as XACML and PTaCL.

A workflow specification defines a set of steps, a set of users, and an access control policy. The policy determines which steps a user is authorized to perform and imposes constraints on which sets of users can perform which sets of steps. The workflow satisfiability problem (WSP) is the problem of determining whether there exists an assignment of users to workflow steps that satisfies the policy. Given the computational hardness of WSP and its importance in the context of workflow management systems, it is important to develop algorithms that are as efficient as possible to solve WSP. In this article, we study the fixed-parameter tractability of WSP in the presence of class-independent constraints, which enable us to (1) model security requirements based on the groups to which users belong and (2) generalize the notion of a user-independent constraint. Class-independent constraints are defined in terms of equivalence relations over the set of users. We consider sets of nested equivalence relations because this enables us to model security requirements in hierarchical organizations. We prove that WSP is fixed-parameter tractable (FPT) for class-independent constraints defined over nested equivalence relations and develop an FPT algorithm to solve WSP instances incorporating such constraints. We perform experiments to evaluate the performance of our algorithm and compare it with that of SAT4J, an off-the-shelf pseudo-Boolean SAT solver. The results of these experiments demonstrate that our algorithm significantly outperforms SAT4J for many instances of WSP.

Publicly Verifiable Outsourced Computation (PVC) allows devices with restricted resources to delegate computations to more powerful external servers, and to verify the correctness of results. Whilst beneficial in many situations, this increases the visibility and availability of potentially sensitive data, so we may wish to limit the sets of entities that can view input data and results. Additionally, it is highly unlikely that all users have identical and uncontrolled access to all functionality within an organization. Thus there is a need for access control mechanisms in PVC environments. In this work, we define a new framework for Publicly Verifiable Outsourced Computation with Access Control (PVC-AC) and discuss the security models and forms of access control policies that are necessary in such environments.

A workflow specification defines sets of steps and users. An authorization policy determines for each user a subset of steps the user is allowed to perform. Other security requirements, such as separation-of-duty, impose constraints on which subsets of users may perform certain subsets of steps. The workflow satisfiability problem (WSP) is the problem of determining whether there exists an assignment of users to workflow steps that satisfies all such authorizations and constraints. An algorithm for solving WSP is important, both as a static analysis tool for workflow specifications, and for the construction of run-time reference monitors for workflow management systems. Given the computational difficulty of WSP, it is important, particularly for the second application, that such algorithms are as efficient as possible. We introduce class-independent constraints, enabling us to model scenarios where the set of users is partitioned into groups, and the identities of the user groups are irrelevant to the satisfaction of the constraint. We prove that solving WSP is fixed-parameter tractable (FPT) for this class of constraints and develop an FPT algorithm that is useful in practice. We compare the performance of the FPT algorithm with that of SAT4J (a pseudo-Boolean SAT solver) in computational experiments, which show that our algorithm significantly outperforms SAT4J for many instances of WSP. User-independent constraints, a large class of constraints including many practical ones, are a special case of class-independent constraints for which WSP was proved to be FPT (Cohen et al., J. Artif. Intel. Res. 2014). Thus our results considerably extend our knowledge of the fixed-parameter tractability of WSP.

A workflow is a collection of steps that must be executed in some specific order to achieve an objective. A computerised workflow management system may enforce authorisation policies and constraints, thereby restricting which users can perform particular steps in a workflow. The existence of policies and constraints may mean that a workflow is unsatisfiable, in the sense that it is impossible to find an authorised user for each step in the workflow and satisfy all constraints. In this paper, we consider the problem of finding the "least bad" assignment of users to workflow steps by assigning a weight to each policy and constraint violation. To this end, we introduce a framework for associating costs with the violation of workflow policies and constraints and define the valued workflow satisfiability problem (Valued WSP), whose solution is an assignment of steps to users of minimum cost. We establish the computational complexity of Valued WSP with user-independent constraints and show that it is fixed-parameter tractable. We then describe an algorithm for solving Valued WSP with user-independent constraints and evaluate its performance, comparing it to that of an off-the-shelf mixed integer programming package.

Attribute Based Access Control (ABAC) is becoming the reference model for the specification and evaluation of access control policies. In ABAC policies and access requests are defined in terms of pairs attribute names/values. The applicability of an ABAC policy to a request is determined by matching the attributes in the request with the attributes in the policy. Some languages supporting ABAC, such as PTaCL or XACML 3.0, take into account the possibility that some attributes values might not be correctly retrieved when the request is evaluated, and use complex decisions, usually describing all possible evaluation outcomes, to account for missing attributes.

Inspired by the access control models of social network systems, Relationship-Based Access Control (ReBAC) was recently proposed as a general-purpose access control paradigm for application domains in which authorization must take into account the relationship between the access requestor and the resource owner. The healthcare domain is envisioned to be an archetypical application domain in which ReBAC is sorely needed: e.g., my patient record should be accessible only by my family doctor, but not by all doctors.

Attribute-based encryption (ABE) has attracted considerable attention in the research community in recent years. It has a number of applications such as broadcast encryption and the cryptographic enforcement of access control policies. Existing instantiations of ABE make use of access structures encoded either as trees of Shamir threshold secret-sharing schemes or monotone span programs. In both cases, the appropriate computations for these schemes are interleaved with the standard operations for cryptographic pairings. Moreover, the resulting schemes are not particularly appropriate for access control policies. In this paper, therefore, we start by examining the representation of access control policies and investigate alternative secret-sharing schemes that could be used to enforce them. We develop new ABE schemes based on the Benaloh-Leichter scheme, which employs only elementary arithmetic operations, and then extend this to arbitrary linear secret-sharing schemes. We then compare the complexity of existing schemes with our scheme based on Benaloh-Leichter.

Traditional authorization policies are user-centric, in the sense that authorization is defined, ultimately, in terms of user identities. We believe that this user-centric approach is inappropriate for many applications, and that what should determine authorization is the relationships that exist between entities in the system. While recent research has considered the possibility of specifying authorization policies based on the relationships that exist between peers in social networks, we are not aware of the application of these ideas to general computing systems. We develop a formal access control model that makes use of ideas from relationship-based access control and a two-stage method for evaluating policies. Our policies are defined using path conditions, which are similar to regular expressions. We define semantics for path conditions, which we use to develop a rigorous method for evaluating policies. We describe the algorithm required to evaluate policies and establish its complexity. Finally, we illustrate the advantages of our model using an example and describe a preliminary implementation of our algorithm.

The Workflow Satisfiability Problem (WSP) is a problem of practical interest that arises whenever tasks need to be performed by authorized users, subject to constraints defined by business rules. We are required to decide whether there exists a plan - an assignment of tasks to authorized users - such that all constraints are satisfied. It is natural to see the WSP as a subclass of the Constraint Satisfaction Problem (CSP) in which the variables are tasks and the domain is the set of users. What makes the WSP distinctive is that the number of tasks is usually very small compared to the number of users, so it is appropriate to ask for which constraint languages the WSP is fixed-parameter tractable (FPT), parameterized by the number of tasks. This novel approach to the WSP, using techniques from CSP, has enabled us to design a generic algorithm which is FPT for several families of workflow constraints considered in the literature. Furthermore, we prove that the union of FPT languages remains FPT if they satisfy a simple compatibility condition. Lastly, we identify a new FPT constraint language, user-independent constraints, that includes many of the constraints of interest in business processing systems. We demonstrate that our generic algorithm has provably optimal running time O*(2^(klog k)), for this language, where k is the number of tasks.

Social Networks were created to allow users to maintain circles of friends and acquaintances. Over time, they have come to be used to share data objects such as pictures between friends. There have been several approaches to formalize social networks in order to specify complicated access control policies for such objects. These approaches have involved a combination of existing logic with custom languages, with new operators being introduced when more complex policies needed to be expressed. In this paper we demonstrate that set theoretic notation provides a convenient syntax for specifying a social network and the associated access control policies. We demonstrate that our notation enables us to extend the range of policies that can be articulated. We also demonstrate that our notation is simpler and more concise than existing approaches.

A workflow specification defines a set of steps and the order in which those steps must be executed. Security requirements and business rules may impose constraints on which users are permitted to perform those steps. A workflow specification is said to be satisfiable if there exists an assignment of authorized users to workflow steps that satisfies all the constraints. An algorithm for determining whether such an assignment exists is important, both as a static analysis tool for workflow specifications, and for the construction of run-time reference monitors for workflow management systems. We develop new methods for determining workflow satisfiability based on the concept of constraint expressions, which were introduced recently by Khan and Fong. These methods are surprising versatile, enabling us to develop algorithms for, and determine the complexity of, a number of different problems related to workflow satisfiability.

A workflow specification defines a set of steps and the order in which these steps must be executed. Security requirements may impose constraints on which groups of users are permitted to perform subsets of these steps. A workflow specification is said to be satisfiable if there exists an assignment of users to workflow steps that satisfies all the constraints. An algorithm for determining whether such an assignment exists is important, both as a static analysis tool for workflow specifications and for the construction of runtime reference monitors for workflow management systems. Finding such an assignment is a hard problem in general, but work by Wang and Li [2010] using the theory of parameterized complexity suggests that efficient algorithms exist under reasonable assumptions about workflow specifications. In this article, we improve the complexity bounds for the workflow satisfiability problem. We also generalize and extend the types of constraints that may be defined in a workflow specification and prove that the satisfiability problem remains fixed-parameter tractable for such constraints. Finally, we consider preprocessing for the problem and prove that in an important special case, in polynomial time, we can reduce the given input into an equivalent one where the number of users is at most the number of steps. We also show that no such reduction exists for two natural extensions of this case, which bounds the number of users by a polynomial in the number of steps, provided a widely accepted complexity-theoretical assumption holds.

A workflow specification defines a set of steps and the order in which those steps must be executed. Security requirements may impose constraints on which groups of users are permitted to perform subsets of those steps. A workflow specification is said to be satisfiable if there exists an assignment of users to workflow steps that satisfies all the constraints. An algorithm for determining whether such an assignment exists is important, both as a static analysis tool for workflow specifications, and for the construction of run-time reference monitors for workflow management systems. Finding such an assignment is a hard problem in general, but work by Wang and Li in 2010 using the theory of parameterized complexity suggests that efficient algorithms exist under reasonable assumptions about workflow specifications. In this paper, we improve the complexity bounds for the workflow satisfiability problem. We also generalize and extend the types of constraints that may be defined in a workflow specification and prove that the satisfiability problem remains fixed-parameter tractable for such constraints.

The increasing need to share information in dynamic environments has created a requirement for risk-aware access control systems. In this paper, we present a metamodel for risk-aware authorization that captures the key aspects of a system in relation to risk mitigation. In particular, we develop various risk-aware models as instances of the metamodel that broadly differ in the form of risk mitigation that is used (system obligations and user obligations respectively), and study how those obligations are applied to reduce and account for the risk incurred by granting access. Unlike system obligations, an access control system cannot guarantee that user obligations are fulfilled. We propose two approaches to defining risk-aware authorization semantics that takes unfulfilled obligations into account: one is to restrict users' future access because of prior failure to fulfill obligations, and the other is to “reward” users who have been diligent in fulfilling their obligations by permitting risky access requests.

The enforcement of access control policies using cryptography has received considerable attention in recent years and the security of such enforcement schemes is increasingly well understood. Recent work in the area has considered the efficient enforcement of temporal and geo-spatial access control policies, and asymptotic results for the time and space complexity of efficient enforcement schemes have been obtained. However, for practical purposes, it is useful to have explicit bounds for the complexity of enforcement schemes. In this article we consider interval-based access control policies, of which temporal and geo-spatial access control policies are special cases. We define enforcement schemes for interval-based access control policies for which it is possible, in almost all cases, to obtain exact values for the schemes' complexity, thereby subsuming a substantial body of work in the literature. Moreover, our enforcement schemes are more practical than existing schemes, in the sense that they operate in the same way as standard cryptographic enforcement schemes, unlike other efficient schemes in the literature. The main difference between our approach and earlier work is that we develop techniques that are specific to the cryptographic enforcement of interval-based access control policies, rather than applying generic techniques that give rise to complex constructions and asymptotic bounds.

As distributed applications increase in size and complexity, traditional authorization architectures based on a dedicated authorization server become increasingly fragile because this decision point represents a single point of failure and a performance bottleneck. Authorization caching, which enables the reuse of previous authorization decisions, is one technique that has been used to address these challenges. This article introduces and evaluates the mechanisms for authorization “recycling” in RBAC enterprise systems. The algorithms that support these mechanisms allow making precise and approximate authorization decisions, thereby masking possible failures of the authorization server and reducing its load. We evaluate these algorithms analytically as well as using simulation and a prototype implementation. Our evaluation results demonstrate that authorization recycling can improve the performance of distributed-access control mechanisms.

Pervasive computing environments have created a requirement for spatial- and temporal-aware access control systems. Although temporal, spatial and spatio-temporal role-based access control (RBAC) models have been developed, a family of simple, expressive and flexible models that convincingly addresses the interaction between spatio-temporal constraints and inheritance in RBAC does not yet exist. In this paper, we define three spatio-temporal models based on RBAC96 the de facto standard for RBAC, and extend these models to include activation and usage hierarchies. These models provide different authorization semantics, varying in the extent to which RBAC entities and relations are constrained by spatio-temporal restrictions. We introduce the notion of trusted entities, which are used to selectively override certain spatio-temporal restrictions. We also demonstrate that our spatio-temporal models are consistent and compatible with RBAC96 and the ANSI-RBAC standard, in contrast to existing models. Finally, we propose four approaches to encoding spatio-temporal requirements in practical applications that permit access requests to be answered efficiently.

Supporting delegation mechanisms in workflow systems is receiving increasing interest from the research community. An important requirement of a constrained workflow is to guarantee the satisfiability of the workflow, which requires that some set of authorized users can complete a workflow. Typically, any mechanism that is used to establish the satisfiability of a workflow is based on the workflow specification and the user authorization information. The effect of a successful user delegation request is to change the user authorization information, thereby affecting the satisfiability of the workflow.Existing work on delegation in workflows does not consider the satisfiability of the workflow. In this paper, we address the satisfiability problem of workflows, while supporting user delegation mechanisms, in the context of three different workflow execution models. We consider delegation of concrete tasks, abstract tasks and roles. We present algorithms for evaluating various delegation requests in each workflow execution model.

Large and distributed access control systems are increasingly common, for example in health care. In such settings, access control policies may become very complex, thus complicating correct and efficient adminstration of the access control system. Despite being one of the most widely used access control standards, RBAC does not include an administration model for distributed systems. In this paper we fill this gap. We present a model for the administration of RBAC in a distributed system and propose an administration procedure supporting the principle that different systems protect different sets of objects. We demonstrate that our procedure fulfills the formal requirements deriving from safety and availability, and we show how it can be translated to a practical implementation. Finally, we show how our model can be extended with multiple decentralized administrative systems.

As distributed applications increase in size and complexity, traditional authorization mechanisms based on a single policy decision point are increasingly fragile because this decision point represents a single point of failure and a performance bottleneck. Authorization recycling is one technique that has been used to address these challenges. This paper introduces and evaluates the mechanisms for authorization recycling in RBAC enterprise systems. The algorithms that support these mechanisms allow precise and approximate authorization decisions to be made, thereby masking possible failures of the policy decision point and reducing its load. We evaluate these algorithms analytically and using a prototype implementation. Our evaluation results demonstrate that authorization recycling can improve the performance of distributed access control mechanisms.

In existing RBAC literature, administrative privileges are inherited just like ordinary user privileges. We argue that from a security viewpoint this is too restrictive, and we believe that a more flexible approach can be very useful in practice. We define an ordering on the set of administrative privileges, enabling us to extend the standard privilege inheritance relation in a natural way. This means that if a user has a particular administrative privilege, then she is also implicitly authorized for weaker administrative privileges. We prove the non-trivial result that it is possible to decide whether one administrative privilege is weaker than another and show how this result can be used to decide administrative requests in an RBAC security monitor.

This paper describes an extension to the Restricted Growth Function grouping Genetic Algorithm applied to the Consensus Clustering of a retinal nerve fibre layer data-set. Consensus Clustering is an optimisation based method which combines the results of a number of data clustering methods, and is used when it is unknown which clustering method is expected to perform the best. Consensus Clustering has been shown to produce results which are better than the averaged results of the input methods, but could benefit from a more efficient optimisation method. A Restricted Growth Function grouping Genetic Algorithm is a new method of grouping a number of objects into mutually exclusive subsets based upon a fitness function. This method does not suffer from degeneracy, and thus could be applied to the Consensus Clustering problem more efficiently than Simulated Annealing, the current optimisation method. Within this paper it is shown that this type of Genetic Algorithm can indeed improve the performance of Consensus Clustering, and in fact can be improved further by taking advantage of some application specific properties. These findings are demonstrated on a retinal nerve fibre layer data-set and on a synthetic data-set.

Problems that require the partitioning of a set of variables in order to compute a solution such as bin packing or line balancing are typically NP-hard. Hence, researchers have focused on producing heuristic methods for finding appropriate partitions. Many of the representations used in optimisation algorithms including those in GA methods suffer from degeneracy [2]. Furthermore, Falkenauer has found that representations with less degeneracy result in more efficient GAs with respect to grouping problems [1]. Previously we developed a new representation for grouping genetic algorithms called the Restricted Growth Function GA (RGFGA) [3]. The RGFGA effectively removes all degeneracy, resulting in a more efficient search. However, one flaw of the RGFGA is that it converges too quickly resulting in

Role-based access control and role hierarchies have been the subject of considerable research in recent years. In this paper, we consider three useful applications of a new role-based access control model that contains a novel approach to permissions and permission inheritance: one is to illustrate that the new model provides a simpler and more natural way to implement BLP model using role-based techniques; a second application is to make it possible to define separation of duty constraints on two roles that have a common senior role and for a user to be assigned to or activate the senior role; finally, we describe how a single hierarchy in the new model can support the distinction between role activation and permission usage. In short, the oriented permission model provides ways of implementing a number of useful features that have previously required ad hoc and inelegant solutions.

The principle of least privilege is a well known design principle to which access control models and systems should adhere. In the context of role-based access control, the principle of least privilege can be implemented through the use of sessions. In this paper, we first define a family of simple role-based models that provide support for multiple hierarchies and temporal constraints. We then investigate a question related to sessions in each of these models: the inter-domain role mapping problem. The question has previously been defined and analyzed in the context of a particular role-based model. We redefine the question and analyze it in the context of a number of different role-based models.

A key assignment scheme is a cryptographic technique for implementing an information flow policy, sometimes known as hierarchical access control. All the research to date on key assignment schemes has focused on particular encryption techniques rather than an analysis of what features are required of such a scheme. To remedy this we propose a family of generic key assignment schemes and compare their respective advantages. We note that every scheme in the literature is simply an instance of one of our generic schemes. We then conduct an analysis of the Aki-Taylor scheme and propose a number of improvements. We also demonstrate that many of the criticisms that have been made of this scheme in respect of key updates are unfounded, finally, exploiting the deeper understanding we have acquired of key assignment schemes, we introduce a technique for exploiting the respective advantages of different schemes.

Computerized workflow systems have attracted considerable research interest. More recently, there have been several XML-based languages proposed for specifying and orchestrating business processes, culminating in WS-BPEL. A significant omission from WS-BPEL is the ability to specify authorization information associating users with activities in the business process and authorization constraints on the execution of activities such as separation of duty. In this paper, we address these deficiencies by developing the RBAC-WS-BPEL and BPCL languages. The first of these provides for the specification of authorization information associated with a business process specified in WS-BPEL, while BPCL provides for the articulation of authorization constraints

The request-response paradigm used for access control solutions commonly leads to point-to-point (PTP) architectures, with security enforcement logic obtaining decisions from authorization servers through remote procedure calls. In massive-scale and complex enterprises, PTP authorization architectures result in fragile and inefficient solutions. They also fail to exploit virtually free CPU resources and network bandwidth. This talk introduces a three-fold approach to improving availability and performance of authorization solutions: employing publish-subscribe technologies, *actively* recycling authorizations, and flooding PEPs with speculatively precomputed *junk* authorizations. After introducing the approach, the talk describes in detail the active authorization recycling part. Specifically, it defines the secondary and approximate authorization model (SAAM). In SAAM, approximate authorization responses are inferred from cached primary responses, and therefore provide an alternative source of access control decisions in the event that the authorization server is unavailable or slow. The ability to compute approximate authorizations improves the reliability and performance of access control sub-systems and ultimately the application systems themselves. The operation of a system that employs SAAM depends on the type of access control policy it implements. We propose and analyze algorithms for computing secondary authorizations in the case of policies based on the Bell-LaPadula model. In this context, we define a dominance graph, and describe its construction and usage for generating secondary responses to authorization requests. Preliminary results of evaluating SAAM-BLP algorithms demonstrate a 15% increase in the number of authorization requests that can be served without consulting access control policies.

The concept of cohesion in a class has been the subject of various recent empirical studies and has been measured using many different metrics. In the structured programming paradigm, the software engineering community has adopted an informal yet meaningful and understandable definition of cohesion based on the work of Yourdon and Constantine. The object-oriented (OO) paradigm has formalised various cohesion measures, but the argument over the most meaningful of those metrics continues to be debated. Yet achieving highly cohesive software is fundamental to its comprehension and thus its maintainability. In this article we subject two object-oriented cohesion metrics, CAMC and NHD, to a rigorous mathematical analysis in order to better understand and interpret them. This analysis enables us to offer substantial arguments for preferring the NHD metric to CAMC as a measure of cohesion. Furthermore, we provide a complete understanding of the behaviour of these metrics, enabling us to attach a meaning to the values calculated by the CAMC and NHD metrics. In addition, we introduce a variant of the NHD metric and demonstrate that it has several advantages over CAMC and NHD. While it may be true that a generally accepted formal and informal definition of cohesion continues to elude the OO software engineering community, there seems considerable value in being able to compare, contrast, and interpret metrics which attempt to measure the same features of software.

Access control data structures generally need to evolve over time in order to reflect changes to security policy and personnel. An administrative model defines the rules that control the state changes to an access control model and the data structures that model defines. We present a powerful framework for describing role-based administrative models. It is based on the concept of administrative domains and criteria that control state changes in order to preserve certain features of those domains. We define a number of different sets of criteria, each of which control the effect of state changes on the set of administrative domains and thereby lead to different role-based administrative models. Using this framework we are able to identify some unexpected connections between the ARBAC97 and RHA administrative models and to compare their respective properties. In doing so we are able to suggest some improvements to both models.

Many retailers run loyalty card schemes for their customers offering incentives in the form of money off coupons. The total value of the coupons depends on how much the customer has spent. This paper deals with the problem of finding the smallest set of coupons such that each possible total can be represented as the sum of a pre-defined number of coupons. A mathematical analysis of the problem leads to the development of a genetic algorithm solution. The algorithm is applied to real world data using several crossover operators and compared to well known straw-person methods. Results are promising showing that considerable time can be saved by using this method, reducing a few days worth of consultancy time to a few minutes of computation.

We describe a model, independent of any underlying access control paradigm, for specifying authorization constraints such as separation of duty and cardinality constraints in workflow systems. We present a number of results enabling us to simplify the set of authorization constraints. These results form the theoretical foundation for an algorithm that can be used to determine whether a given constrained workflow can be satisfied: that is, does there exist an assignment of authorized users to workflow tasks that satisfies the authorization constraints? We show that this algorithm can be incorporated into a workflow reference monitor that guarantees that every workflow instance can complete. We derive the computational complexity of our algorithm and compare its performance to comparable work in the literature.

There is substantial research into genetic algorithms that are used to group large numbers of objects into mutually exclusive subsets based upon some fitness function. However, nearly all methods involve degeneracy to some degree. We introduce a new representation for grouping genetic algorithms, the restricted growth function genetic algorithm, that effectively removes all degeneracy, resulting in a more efficient search. A new crossover operator is also described that exploits a measure of similarity between chromosomes in a population. Using several synthetic datasets, we compare the performance of our representation and crossover with another well known state-of-the-art GA method, a strawman optimisation method and a well-established statistical clustering algorithm, with encouraging results.

Role-based access control and role hierarchies have generated considerable research activity in recent years.In many role-based models the role hierarchy partially determines which roles and permissions are available to users via various inheritance mechanisms.In this paper, we consider the nature of permissions more closely than is customary in the literature and propose a particular structure for permissions.We then introduce a role-based access control model that contains a novel approach to permission inheritance and illustrate how this model can be used to derive a role-based model with multi-level secure properties.We also consider the issue of redundant and consistent permission-role assignments and describe how such assignments can be avoided.

Constraints in access control in general and separation of duty constraints in particular are an important area of research. There are two important issues relating to constraints: their specification and their enforcement. We believe that existing separation of duty specification schemes are rather complicated and that the few enforcement models that exist are unlikely to scale well.We examine the assumptions behind existing approaches to separation of duty and present a combined specification and implementation model for a class of constraints that includes separation of duty constraints. The specification model is set-based and has a simpler syntax than existing approaches. We discuss the enforcement of constraints and the relationship between static, dynamic and historical separation of duty constraints. Finally, we propose a model for a scalable role-based reference monitor, based on dynamic access control structures, that can be used to enforce constraints in an efficient manner.

We introduce the concept of administrative scope in a role hierarchy and demonstrate that it can be used as a basis for role-based administration. We then develop a family of models for role hierarchy administration (RHA) employing administrative scope as the central concept. We then extend RHA 4 , the most complex model in the family, to a complete, decentralized model for role-based administration. We show that SARBAC, the resulting role-based administrative model, has significant practical and theoretical advantages over ARBAC97. We also discuss how administrative scope might be applied to the administration of general hierarchical structures, how our model can be used to reduce inheritance in the role hierarchy, and how it can be configured to support discretionary access control features.

The ARBAC97 model makes an important contribution to the understanding and modeling of administration in role-based access control. However, there are several features of the model which we believe could be improved. We introduce the concept of administrative scope in a role hierarchy and show how this can be used to control updates to the hierarchy. We then incrementally develop a model for administering the role hierarchy and compare it to the RRA97 sub-model of ARBAC97. We conclude that our model offers significant advantages over RRA97.

The effectiveness of an access control mechanism in implementing a security policy in a centralized operating system is often weakened because of the large number of possible access rights involved, informal specification of security policy and a lack of tools for assisting systems administrators. Herein we present a logical foundation for automated tools that assist in determining which access rights should be granted by reasoning about the effects of an access control mechanism on the computations performed by an operating system. We demonstrate the practicality and utility of our logical approach by showing how it allows us to construct a deductive database capable of answering questions about the security of two real-world operating systems. We illustrate the application of our techniques by presenting the results of an experiment designed to assess how accurately the configuration of an access control mechanism implements a given security policy.

The effectiveness of an access control mechanism in implementing a security policy in a centralized operating system is often weakened because of the large number of possible access rights involved, informal specification of security policy and a lack of tools for assisting systems administrators. Herein we present a logical foundation for automated tools that assist in determining which access rights should be granted by reasoning about the effects of an access control mechanism on the computations performed by an operating system. We demonstrate the practicality and utility of our logical approach by showing how it allows us to construct a deductive database capable of answering questions about the security of two real-world operating systems. We illustrate the application of our techniques by presenting the results of an experiment designed to assess how accurately the configuration of an access control mechanism implements a given security policy.