Technology advances in areas such as sensors, IoT, and robotics, enable new collaborative applications (e.g., autonomous devices). A primary requirement for such collaborations is to have a secure system that enables information sharing and information flow protection. A policy-based management system is a key mechanism for secure selective sharing of protected resources. However, policies in each party of a collaborative environment cannot be static as they have to adapt to different contexts and situations. One advantage of collaborative applications is that each party in the collaboration can take advantage of the knowledge of the other parties for learning or enhancing its own policies. We refer to this learning mechanism as policy transfer. The design of a policy transfer framework has challenges, including policy conflicts and privacy issues. Policy conflicts typically arise because of differences in the obligations of the parties, whereas privacy issues result because of data sharing constraints for sensitive data. Hence, the policy transfer framework should be able to tackle such challenges by considering minimal sharing of data and supporting policy adaptation to address conflict. In the paper, we propose a framework that aims at addressing such challenges. We introduce a formal definition of the policy transfer problem for attribute-based access control policies. We then introduce the transfer methodology which consists of three sequential steps. Finally, we report experimental results.

One of the ultimate goals of Artificial Intelligence is to assist humans in complex decision making. A promising direction for achieving this goal is Neuro-Symbolic AI, which aims to combine the interpretability of symbolic techniques with the ability of deep learning to learn from raw data. However, most current approaches require manually engineered symbolic knowledge, and where end-to-end training is considered, such approaches are either restricted to learning definite programs, or are restricted to training binary neural networks. In this paper, we introduce Neuro-Symbolic Inductive Learner (NSIL), an approach that trains a general neural network to extract latent concepts from raw data, whilst learning symbolic knowledge that maps latent concepts to target labels. The novelty of our approach is a method for biasing the learning of symbolic knowledge, based on the in-training performance of both neural and symbolic components. We evaluate NSIL on three problem domains of different complexity, including an NP-complete problem. Our results demonstrate that NSIL learns expressive knowledge, solves computationally complex problems, and achieves state-of-the-art performance in terms of accuracy and data efficiency. Code and technical appendix: https://github.com/DanCunnington/NSIL

Abstract Logic-based machine learning aims to learn general, interpretable knowledge in a data-efficient manner. However, labelled data must be specified in a structured logical form. To address this limitation, we propose a neural-symbolic learning framework, called Feed-Forward Neural-Symbolic Learner (FFNSL), that integrates a logic-based machine learning system capable of learning from noisy examples, with neural networks, in order to learn interpretable knowledge from labelled unstructured data. We demonstrate the generality of FFNSL on four neural-symbolic classification problems, where different pre-trained neural network models and logic-based machine learning systems are integrated to learn interpretable knowledge from sequences of images. We evaluate the robustness of our framework by using images subject to distributional shifts, for which the pre-trained neural networks may predict incorrectly and with high confidence. We analyse the impact that these shifts have on the accuracy of the learned knowledge and run-time performance, comparing FFNSL to tree-based and pure neural approaches. Our experimental results show that FFNSL outperforms the baselines by learning more accurate and interpretable knowledge with fewer examples.

Reinforcement Learning (RL) is an effective technique for building ‘smart’ SDN controllers because of its model-free nature and ability to learn policies online without requiring extensive training data. However, as RL agents are geared to maximize functionality and explore the environment without constraints, security can be breached. In this paper, we propose Jarvis-SDN, a RL framework that constrains explorations by taking security into account. In Jarvis-SDN, the RL agent learns ‘intelligent policies’ which maximize functionality but not at the cost of security. Standard network flow based attack sig-natures obtained from intrusion detection system (IDS) datasets cannot be used as policies because they do not conform to the state model of the RL framework and thus have poor accuracy and high false positives. To address such issue, the security policies for constraining explorations in Jarvis-SDN are learnt in a semi-supervised manner in the form of ‘partial attack signatures’ from packet captures of IDS datasets that are then encoded in the objective function of the RL based optimization framework. These signatures are learnt using Deep Q-Networks (DQN). Our analysis shows that DQN based attack signatures perform better than classical machine learning techniques, like decision trees, random forests and deep neural networks (DNN), for common network attacks. We instantiate our framework for a SDN controller with the goal of intelligent rate control to further analyze the effectiveness of the attack signatures.

Inductive Logic Programming (ILP) systems aim to find a set of logical rules, called a hypothesis, that explain a set of examples. In cases where many such hypotheses exist, ILP systems often bias towards shorter solutions, leading to highly general rules being learned. In some application domains like security and access control policies, this bias may not be desirable, as when data is sparse more specific rules that guarantee tighter security should be preferred. This paper presents a new general notion of a scoring function over hypotheses that allows a user to express domain-specific optimisation criteria. This is incorporated into a new ILP system, called FastLAS, that takes as input a learning task and a customised scoring function, and computes an optimal solution with respect to the given scoring function. We evaluate the accuracy of FastLAS over real-world datasets for access control policies and show that varying the scoring function allows a user to target domain-specific performance metrics. We also compare FastLAS to state-of-the-art ILP systems, using the standard ILP bias for shorter solutions, and demonstrate that FastLAS is significantly faster and more scalable.

We introduce a novel approach for the computation of stable and supported models of normal logic programs in continuous vector spaces by a gradient-based search method. Specifically, the application of the immediate consequence operator of a program reduct can be computed in a vector space. To do this, Herbrand interpretations of a propositional program are embedded as 0-1 vectors in $\mathbb{R}^N$ and program reducts are represented as matrices in $\mathbb{R}^{N \times N}$. Using these representations we prove that the underlying semantics of a normal logic program is captured through matrix multiplication and a differentiable operation. As supported and stable models of a normal logic program can now be seen as fixed points in a continuous space, non-monotonic deduction can be performed using an optimisation process such as Newton's method. We report the results of several experiments using synthetically generated programs that demonstrate the feasibility of the approach and highlight how different parameter values can affect the behaviour of the system.

There has been over the past decade a rapid change towards computational environments that are comprised of large and diverse sets of devices, many of them mobile, which can connect in flexible and context-dependent ways. Examples range from networks where we can have communications between powerful cloud centers, to the myriad of simple sensor devices on the IoT. As the management of these dynamic environments becomes ever more complex, we want to propose policy migrations as a methodology to simplify the management of security policies by re-utilizing and re-deploying existing policies as the systems change. We are interested in understanding the challenges raised answering the following question: given a security policy that is being enforced in a particular source computational device, what does it entail to migrate this policy to be enforced in a different target device? Because of the differences between devices and because these devices cannot be seen in isolation but in the context where they are deployed, the meaning of the policy enforced in the source device needs to be re-interpreted and implemented in the context of the target device. The aim of the paper is to present a formal framework to evaluate the appropriateness of the migration.

In this paper we introduce an extension of context-free grammars called answer set grammars (ASGs). These grammars allow annotations on production rules, written in the language of Answer Set Programming (ASP), which can express context-sensitive constraints. We investigate the complexity of various classes of ASG with respect to two decision problems: deciding whether a given string belongs to the language of an ASG and deciding whether the language of an ASG is non-empty. Specifically, we show that the complexity of these decision problems can be lowered by restricting the subset of the ASP language used in the annotations. To aid the applicability of these grammars to computational problems that require context-sensitive parsers for partially known languages, we propose a learning task for inducing the annotations of an ASG. We characterise the complexity of this task and present an algorithm for solving it. An evaluation of a (prototype) implementation is also discussed.

Policy systems are critical for managing missions and collaborative activities carried out by coalitions involving different organizations. Conventional policy-based management approaches are not suitable for next-generation coalitions that will involve not only humans, but also autonomous computing devices and systems. It is critical that those parties be able to generate and customize policies based on contexts and activities. This paper introduces a novel approach for the autonomic generation of policies by autonomous parties. The framework combines context free grammars, answer set programs, and inductionbased learning. It allows a party to generate its own policies, based on a grammar and some semantic constraints, by learning from examples. The paper also outlines initial experiments in the use of such a symbolic approach and outlines relevant research challenges, ranging from explainability to quality assessment of policies.

We present a formal method for computing the best security provisioning for Internet of Things (IoT) scenarios characterized by a high degree of mobility. The security infrastructure is intended as a security resource allocation plan, computed as the solution of an optimization problem that minimizes the risk of having IoT devices not monitored by any resource. We employ the shortfall as a risk measure, a concept mostly used in the economics, and adapt it to our scenario. We show how to compute and evaluate an allocation plan, and how such security solutions address the continuous topology changes that affect an IoT environment.

Relationships like friendship to limit access to resources have been part of social network applications since their beginnings. Describing access control policies in terms of relationships is not particular to social networks and it arises naturally in many situations. Hence, we have recently seen several proposals formalizing different Relationship-based Access Control (ReBAC) models. In this paper, we introduce a class of Datalog programs suitable for modeling ReBAC and argue that this class of programs, that we called ReBAC Datalog policies, provides a very general framework to specify and implement ReBAC policies. To support our claim, we first formalize the merging of two recent proposals for modeling ReBAC, one based on hybrid logic and the other one based on path regular expressions. We present extensions to handle negative authorizations and temporal policies. We describe mechanism for policy analysis, and then discuss the feasibility of using Datalog-based systems as implementations.

With the introduction of network function virtualization technology, migrating entire enterprise data centers into the cloud has become a possibility. However, for a cloud service provider (CSP) to offer such services, several research problems still need to be addressed. In previous work, we have introduced a platform, called network function center (NFC), to study research issues related to virtualized network functions (VNFs). In an NFC, we assume VNFs to be implemented on virtual machines that can be deployed in any server in the CSP network. We have proposed a resource allocation algorithm for VNFs based on genetic algorithms (GAs). In this paper, we present a comprehensive analysis of two resource allocation algorithms based on GA for: 1) the initial placement of VNFs and 2) the scaling of VNFs to support traffic changes. We compare the performance of the proposed algorithms with a traditional integer linear programming resource allocation technique. We then combine data from previous empirical analyses to generate realistic VNF chains and traffic patterns, and evaluate the resource allocation decision making algorithms. We assume different architectures for the data center, implement different fitness functions with GA, and compare their performance when scaling over the time.

Researchers have recently shown that declarative database query languages, such as Datalog, could naturally be used to specify and implement network protocols and services. In this paper, we present a declarative framework for the specification, execution, simulation, and analysis of distributed applications. Distributed applications, including routing protocols, can be specified using a Declarative Networking language, called D2C, whose semantics capture the notion of a Distributed State Machine (DSM), i.e., a network of computational nodes that communicate with each other through the exchange of data. The D2C specification can be directly executed using the DSM computational infrastructure of our framework. The same specification can be simulated and formally verified. The simulation component integrates the DSM tool within a network simulation environment and allows developers to simulate network dynamics and collect data about the execution in order to evaluate application responses to network changes. The formal analysis component of our framework, instead, complements the empirical testing by supporting the verification of different classes of properties of distributed algorithms, including convergence of network routing protocols. To demonstrate the generality of our framework, we show how it can be used to analyze two classes of network routing protocols, a path vector and a Mobile Ad-Hoc Network (MANET) routing protocol, and execute a distributed algorithm for pattern formation in multi-robot systems.

In this paper we show that the logical framework proposed by Becker et al. [1] to reason about security policy behavior in a trust management context can be captured by an operational framework that is based on the language proposed by Miller in 1989 to deal with scoping and/or modules in logic programming. The framework of Becker et al. uses propositional Horn clauses to represent both policies and credentials, implications in clauses are interpreted in counterfactual logic, a Hilbert-style proof system is defined and a system based on SAT is used to prove whether properties about credentials, permissions and policies are valid, i.e. true under all possible policies. Our contributions in this paper are three. First, we show that this kind of validation can rely on an operational semantics (derivability relation) of a language very similar to Miller's language, which is very close to derivability in logic programs. Second, we are able to establish that, as in propositional logic, validity of formulas is a co-NP-complete problem. And third, we present a provably correct implementation of a goal-oriented algorithm for validity.

By allowing network functions to be virtualized and run on commodity hardware, NFV enables new properties (e.g., elastic scaling), and new service models for Service Providers, Enterprises, and Telecommunication Service Providers. However, for NFV to be offered as a service, several research problems still need to be addressed. In this paper, we focus and propose a new service chaining algorithm. Existing solutions suffer two main limitations: First, existing proposals often rely on mixed Integer Linear Programming to optimize VM allocation and network management, but our experiments show that such approach is too slow taking hours to find a solution. Second, although existing proposals have considered the VM placement and network configuration jointly, they frequently assume the network configuration cannot be changed. Instead, we believe that both computing and network resources should be able to be updated concurrently for increased flexibility and to satisfy SLA and Qos requirements. As such, we formulate and propose a Genetic Algorithm based approach to solve the VM allocation and network management problem. We built an experimental NFV platform, and run a set of experiments. The results show that our proposed GA approach can compute configurations to to three orders of magnitude faster than traditional solutions.

Signature-based network intrusion detection systems (S-IDS) have become an important security tool in the protection of an organisation's infrastructure against external intruders. By analysing network traffic, S-IDS' detect network intrusions. An organisation may deploy one or multiple S-IDS', each working independently with the assumption that it can monitor all packets of a given flow to detect intrusion signatures. However, emerging technologies (e.g., Multi-Path TCP) violate this assumption, as traffic can be concurrently sent across different paths (e.g., WiFi, Cellular) to boost network performance. Attackers may exploit this capability and split malicious payloads across multiple paths to evade traditional signature-based network intrusion detection systems. Although multiple monitors may be deployed, none of them has the full coverage of the network traffic to detect the intrusion signature. In this paper, we formalise this distributed signature-based intrusion detection problem as an asynchronous online exact string matching problem, and propose an algorithm for it. To demonstrate its effectiveness we conducted comprehensive experiments. Our results show that the behaviour of our algorithm depends only on the packet arrival rate: delay in detecting the signature grows linearly with respect to the packet arrival rate and with small communication overhead.

In a federated database system, each independent party exports some of its data for information sharing. The information sharing in such a system is very inflexible, as all peer parties access the same set of data exported by a party, while the party may want to authorize different peer parties to access different portions of its information. We propose a novel query evaluation scheme that supports differentiated access control with decentralized query processing. Anew efficient join method, named split-join, along with other safe join methods is adopted in the query planning algorithm. The generated query execution reduces the communication cost by pushing partial query computation to data sources in a safe way. The proofs of the correctness and safety of the algorithm are presented. The evaluation demonstrates that the scheme significantly saves the communication cost in a variety of circumstances and settings while enforcing autonomous and differentiated information sharing effectively.

Assessing similarity of policies is crucial in a variety of scenarios, such as finding the cloud service providers which satisfy users' privacy concerns, or finding collaborators which have matching security and privacy settings. Existing approaches to policy similarity analysis are mainly based on logical reasoning and Boolean function comparison. Such approaches are computationally expensive and do not scale well for large heterogeneous distributed environments (like the cloud). In this paper, we propose a policy similarity measure as a lightweight ranking approach to help one party quickly locate parties with potentially similar policies. In particular, given a policy P, the similarity measure assigns a ranking (similarity score) to each policy compared with P. We formally define the measure by taking into account various factors and prove several important properties of the measure. Our extensive experimental study demonstrates the efficiency and practical value of our approach.

Abstract There is an increasing interest in using logic programming to specify and implement distributed algorithms, including a variety of network applications. These are applications where data and computation are distributed among several devices and where, in principle, all the devices can exchange data and share the computational results of the group. In this paper we propose a declarative approach to distributed computing whereby distributed algorithms and communication models can be (i) specified as action theories of fluents and actions; (ii) executed as collections of distributed state machines, where devices are abstracted as (input/output) automata that can exchange messages; and (iii) analysed using existing results on connecting causal theories and Answer Set Programming. Results on the application of our approach to different classes of network protocols are also presented.

This paper addresses the making of security decisions, such as access-control decisions or spam filtering decisions, under uncertainty, when the benefit of doing so outweighs the need to absolutely guarantee these decisions are correct. For instance, when there are limited, costly, or failed communication channels to a policy-decision-point. Previously, local caching of decisions has been proposed, but when a correct decision is not available, either a policy-decision-point must be contacted, or a default decision used. We improve upon this model by using learned classifiers of access control decisions. These classifiers, trained on known decisions, infer decisions when an exact match has not been cached, and uses intuitive notions of utility, damage and uncertainty to determine when an inferred decision is preferred over contacting a remote PDP. Clearly there is uncertainty in the predicted decisions, introducing a degree of risk. Our solution proposes a mechanism to quantify the uncertainty of these decisions and allows administrators to bound the overall risk posture of the system. The learning component continuously refines its models based on inputs from a central policy server in cases where the risk is too high or there is too much uncertainty. We have validated our models by building a prototype system and evaluating it with requests from real access control policies. Our experiments show that over a range of system parameters, it is feasible to use machine learning methods to infer access control policies decisions. Thus our system yields several benefits, including reduced calls to the PDP, reducing latency and communication costs; increased net utility; and increased system survivability.

An understanding of information flow has many applications, including for maximizing marketing impact on social media, limiting malware propagation, and managing undesired disclosure of sensitive information. This paper presents scalable methods for both learning models of information flow in networks from data, based on the Independent Cascade Model, and predicting probabilities of unseen flow from these models. Our approach is based on a principled probabilistic construction and results compare favourably with existing methods in terms of accuracy of prediction and scalable evaluation, with the addition that we are able to evaluate a broader range of queries than previously shown, including probability of joint and/or conditional flow, as well as reflecting model uncertainty. Exact evaluation of flow probabilities is exponential in the number of edges and naive sampling can also be expensive, so we propose sampling in an efficient Markov-Chain Monte-Carlo fashion using the Metropolis-Hastings algorithm -- details described in the paper. We identify two types of data, those where the paths of past flows are known -- attributed data, and those where only the endpoints are known -- unattributed data. Both data types are addressed in this paper, including training methods, example real world data sets, and experimental evaluation. In particular, we investigate flow data from the Twitter microblogging service, exploring the flow of messages through retweets (tweet forwards) for the attributed case, and the propagation of hash tags (metadata tags) and urls for the unattributed case.

This paper describes our system, built as part of a commercially available product, for inferring the risk in an RBAC policy model, i.e., the assignment of permissions to roles and roles to users. Our system implements a general model of risk based on any arbitrary set of properties of permissions and users. Our experience shows that fuzzy inferencing systems are best suited to capture how humans assign risk to such assignments. To implement fuzzy inferencing practically we need the axiom of monotonicity, i.e., risk can not decrease when more permissions are assigned to a role or when the role is assigned to fewer users. We describe the visualization component which administrators can use to infer aggregate risk in role assignments as well as drill down into which assignments are actually risky. Administrators can then use this knowledge to refactor roles and assignments.

In this paper, we describe a framework for a refinement scheme located in a centralized policy server that consists of three components: a knowledge database, a refinement rule set, and a policy repository. The refinement process includes two successive steps: policy transformation and policy composition. Our refinement scheme takes policies written in our logic-based abstract policy language as input and generates low level rules directly implementable by individual enforcement points. We provide concrete policy examples in a coalition scenario that forms a mobile ad hoc network (MANET). We demonstrate policy composition using a distributed firewall scheme named ROFL (ROuting as the Firewall Layer) and access control list as enforcement mechanisms.

Fuzzy inference is a promising approach to implement risk-based access control systems. However, its application to access control raises some novel problems that have not been yet investigated. First, because there are many different fuzzy operations, one must choose the fuzzy operations that best address security requirements. Second, risk-based access control, though it improves information flow and better addresses requirements from critical organizations, may result in damages by malicious users before mitigating steps are taken. Third, the scalability of a fuzzy inference-based access control system is questionable. The time required by a fuzzy inference engine to estimate risks may be quite high especially when there are tens of parameters and hundreds of fuzzy rules. However, an access control system may need to serve hundreds or thousands of users. In this paper, we investigate these issues and present our solutions or answers to them.

The automation of policy refinement, whilst promising great benefits for policy-based management, has hitherto received relatively little treatment in the literature, with few concrete approaches emerging. In this paper we present initial steps towards a framework for automated distributed policy refinement for both obligation and authorization policies. We present examples drawn from military scenarios, describe details of our formalism and methods for action decomposition, and discuss directions for future research.

There has been increasing interest in automatic techniques for generating roles for role based access control, a process known as role mining. Most role mining approaches assume the input data is clean, and attempt to optimize the RBAC state. We examine role mining with noisy input data and suggest dividing the problem into two steps: noise removal and candidate role generation. We introduce an approach to use (non-binary) rank reduced matrix factorization to identify noise and experimentally show that it is effective at identifying noise in access control data. User- and permission-attributes can further be used to improve accuracy. Next, we show that our two-step approach is able to find candidate roles that are close to the roles mined from noise-less data. This method performs better than the approach of mining noisy data directly and offering the administrator increased control in the noise removal and candidate role generation phases. We note that our approach is applicable outside role engineering and may be used to identify errors or predict missing values in any access control matrix.

With the growing adoption of Role-Based Access Control (RBAC) in commercial security and identity management products, how to facilitate the process of migrating a non-RBAC system to an RBAC system has become a problem with significant business impact. Researchers have proposed to use data mining techniques to discover roles to complement the costly top-down approaches for RBAC system construction. An important problem is how to construct RBAC systems with low complexity. In this article, we define the notion of weighted structural complexity measure and propose a role mining algorithm that mines RBAC systems with low structural complexity. Another key problem that has not been adequately addressed by existing role mining approaches is how to discover roles with semantic meanings. In this article, we study the problem in two primary settings with different information availability. When the only information is user-permission relation, we propose to discover roles whose semantic meaning is based on formal concept lattices. We argue that the theory of formal concept analysis provides a solid theoretical foundation for mining roles from a user-permission relation. When user-attribute information is also available, we propose to create roles that can be explained by expressions of user-attributes. Since an expression of attributes describes a real-world concept, the corresponding role represents a real-world concept as well. Furthermore, the algorithms we propose balance the semantic guarantee of roles with system complexity. Finally, we indicate how to create a hybrid approach combining top-down candidate roles. Our experimental results demonstrate the effectiveness of our approaches.

In this article, we introduce a comprehensive framework supporting a privacy-aware access control mechanism, that is, a mechanism tailored to enforce access control to data containing personally identifiable information and, as such, privacy sensitive. The key component of the framework is a family of models (P-RBAC) that extend the well-known RBAC model in order to provide full support for expressing highly complex privacy-related policies, taking into account features like purposes and obligations. We formally define the notion of privacy-aware permissions and the notion of conflicting permission assignments in P-RBAC, together with efficient conflict-checking algorithms. The framework also includes a flexible authoring tool, based on the use of the SPARCLE system, supporting the high-level specification of P-RBAC permissions. SPARCLE supports the use of natural language for authoring policies and is able to automatically generate P-RBAC permissions from these natural language specifications. In the article, we also report performance evaluation results and contrast our approach with other relevant access control and privacy policy frameworks such as P3P, EPAL, and XACML.

Despite several research studies, the effective analysis of policy based systems remains a significant challenge. Policy analysis should at least (i) be expressive (ii) take account of obligations and authorizations, (iii) include a dynamic system model, and (iv) give useful diagnostic information. We present a logic-based policy analysis framework which satisfies these requirements, showing how many significant policy-related properties can be analysed, and we give details of a prototype implementation.

This paper proposes a D-algebra to compose decisions from multiple access control policies. Compared to other algebra-based approaches aimed at policy composition, D-algebra is the only one that satisfies both functional completeness (any possible decision matrix can be expressed by a D-algebra formula) and computational effectiveness (a formula can be computed efficiently given any decision matrix). The D-algebra has several relevant applications in the context of access control policies, namely the analysis of policy languages decision mechanisms, and the development of tools for policy authoring and enforcement.

In spite of the large effort behind the development of the WBEM and CIM standards for the management of distributed systems, there has been very little work addressing security in those standards. In this paper we present a role-based access control (RBAC) policy language to render fine-grained access control policies for WBEM and CIM. The language is an extension of CIM-SPL, a preliminary DMTF policy language standard. The CIM-SPL RBAC extension fully complies with the WBEM standards. Access control policies can be specified for CIM object constructs according to the standard NIST RBAC model as well as with an extended model adapted for CIM. This extension provides a policy-based RBAC mechanism in the WBEM infrastructure.

This panel discusses specific challenges in the usability of access control technologies and new opportunities for research. The questions vary from "Why nobody, even experts, uses access control lists (ACLs)?" to "Shall access controls (and corresponding languages) be totally embedded and invisible and never, ever seen by the users?" to "What should be the user-study methodology for access control systems?".

Many access control policy languages, e.g., XACML, allow a policy to contain multiple sub-policies, and the result of the policy on a request is determined by combining the results of the sub-policies according to some policy combining algorithms (PCAs). Existing access control policy languages, however, do not provide a formal language for specifying PCAs. As a result, it is difficult to extend them with new PCAs. While several formal policy combining algebras have been proposed, they did not address important practical issues such as policy evaluation errors and obligations; furthermore, they cannot express PCAs that consider all sub-policies as a whole (e.g., weak majority or strong majority). We propose a policy combining language PCL, which can succinctly and precisely express a variety of PCAs. PCL represents an advancement both in terms of theory and practice. It is based on automata theory and linear constraints, and is more expressive than existing approaches. We have implemented PCL and integrated it with SUN's XACML implementation. With PCL, a policy evaluation engine only needs to understand PCL to evaluate any PCA specified in it.

While many role mining algorithms have been proposed in recent years, there lacks a comprehensive study to compare these algorithms. These role mining algorithms have been evaluated when they were proposed, but the evaluations were using different datasets and evaluation criteria. In this paper, we introduce a comprehensive framework for evaluating role mining algorithms. We categorize role mining algorithms into two classes based on their outputs; Class 1 algorithms output a sequence of prioritized roles while Class 2 algorithms output complete RBAC states. We then develop techniques that enable us to compare these algorithms directly. We also introduce a new role mining algorithm and two new ways for algorithmically generating datasets for evaluation. Using synthetic as well as real datasets, we compared nine role mining algorithms. Our results illustrate the strengths and weaknesses of these algorithms.

Role-based provisioning has been adopted as a standard component in leading Identity Management products due to its low administration cost. However, the cost of adjusting existing roles to entitlements from newly deployed applications is usually very high. In this paper, a learning-based approach to automate the provisioning process is proposed and its effectiveness is verified by real provisioning data. Specific learning issues related to provisioning are identified and relevant solutions are presented.

Collaborative and distributed applications, such as dynamic coalitions and virtualized grid computing, often require integrating access control policies of collaborating parties. Such an integration must be able to support complex authorization specifications and the fine-grained integration requirements that the various parties may have. In this paper, we introduce an algebra for fine-grained integration of sophisticated policies. The algebra, which consists of three binary and two unary operations, is able to support the specification of a large variety of integration constraints. To assess the expressive power of our algebra, we introduce a notion of completeness and prove that our algebra is complete with respect to this notion. We then propose a framework that uses the algebra for the fine-grained integration of policies expressed in XACML. We also present a methodology for generating the actual integrated XACML policy, based on the notion of Multi-Terminal Binary Decision Diagrams.

With the advances in web service techniques, new collaborative applications have emerged like supply chain arrangements and coalition in government agencies. In such applications, the collaborating parties are responsible for managing and protecting resources entrusted to them. Access control decisions thus become a collaborative activity in which a global policy must be enforced by a set of collaborating parties without compromising the autonomy or confidentiality requirements of these parties. Unfortunately, none of the conventional access control systems meets these new requirements. To support collaborative access control, in this paper, we propose a novel policy-based access control model. Our main idea is based on the notion of policy decomposition and we propose an extension to the reference architecture for XACML. We present algorithms for decomposing a global policy and efficiently evaluating requests.

With the growing adoption of role-based access control (RBAC) in commercial security and identity management products, how to facilitate the process of migrating a non-RBAC system to an RBAC system has become a problem with significant business impact. Researchers have proposed to use data mining techniques to discover roles to complement the costly top-down approaches for RBAC system construction. A key problem that has not been adequately addressed by existing role mining approaches is how to discover roles with semantic meanings. In this paper, we study the problem in two settings with different information availability. When the only information is user-permission relation, we propose to discover roles whose semantic meaning is based on formal concept lattices. We argue that the theory of formal concept analysis provides a solid theoretical foundation for mining roles from userpermission relation. When user-attribute information is also available, we propose to create roles that can be explained by expressions of user-attributes. Since an expression of attributes describes a real-world concept, the corresponding role represents a real-world concept as well. Furthermore, the algorithms we proposed balance the semantic guarantee of roles with system complexity. Our experimental results demonstrate the effectiveness of our approaches.

In this paper, we present a novel obligation model for the Core Privacy-aware Role Based Access Control (P-RBAC), and discuss some design issues in detail. Pre-obligations, post-obligations, conditional obligations, and repeating obli-gations are supported by the obligation model. Interaction between permissions and obligations is discussed, and ef-ficient algorithms are provided to detect undesired effects. Core P-RBAC is extended to support both access control policies and privacy policies simultaneously. We believe that a full-fledged obligation solution based on RBAC may have a great potential because it could be easily deployed in sys-tems already adopting RBAC and would thus allow one to seamlessly introduce policies with obligation requirements, either for access control purposes or for privacy purposes.

The objectives of this paper are twofold. First, we introduce a novel policy language, called CIM-SPL (simple policy language for CIM) that complies with the CIM (common information model) Policy Model and fully incorporates CIM constructs. Currently, the CIM standards from distributed management task force (DMTF) include a policy model, but there is no satisfactory way to render this policy model. CIM-SPL is a language that has been defined for this purpose. Second, we address design and implementation issues for policy languages in general, and for CIM-SPL in particular. The design of CIM-SPL was inspired by our previous experiences in designing various policy languages (e.g., PDL from Bell Laboratories, and ACPL from IBM) and lessons learned from studying other well-known policy languages (e.g., Ponder from Imperial College). We will discuss our design choices, evaluating the pros and cons of various alternatives. The ideas presented in this paper are meant to shed light on our design decisions, and provide guidance for those who want to build a CIM-based policy system or some other policy system in the future.

Recent collaborative applications and enterprises very often need to efficiently integrate their access control policies. An important step in policy integration is to analyze the similarity of policies. Existing approaches to policy similarity analysis are mainly based on logical reasoning and boolean function comparison. Such approaches are computationally expensive and do not scale well for large heterogeneous distributed environments (like Grid computing systems). In this paper, we propose a policy similarity measure as a filter phase for policy similarity analysis. This measure provides a lightweight approach to pre-compile a large amount of policies and only return the most similar policies for further evaluation. In the paper we formally define the measure, by taking into account both the case of categorical attributes and numeric attributes. Detailed algorithms are presented for the similarly computation. Results of our case study demonstrates the efficiency and practical value of our approach.

Privacy has been acknowledged to be a critical requirement for many business (and non-business) environments. Therefore, the definition of an expressive and easy-to-use privacy related access control model, based on which privacy policies can be specified, is crucial. In this work we introduce a family of models (P-RBAC) that extend the well known RBAC model in order to provide full support for expressing highly complex privacy-related policies, taking into account features like purposes and obligations. We also compare our work with access control and privacy policy frameworks such as P3P, EPAL, and XACML.

This paper addresses issues involved in applying the event-condition-action (ECA) rule paradigm of active databases to policies-collections of general principles specifying the desired behavior of a system. We use a declarative policy description language, PDL, in which policies are formulated as sets of ECA rules. The main contribution of the paper is a framework for detecting action conflicts and finding resolutions for them. Conflicts are captured as violations of action constraints. The semantics of rules and conflict detection and resolution are defined axiomatically using logic programs. Given a policy and a set of action constraints, the framework defines a range of monitors that filter the output of the policy to satisfy the constraints.

This work addresses the problem of workflow requirements specifications considering the realistic assumptions that, it involves experts from different domains (i.e. representatives of different business policies); not all the possible execution scenarios are known beforehand, during the early stage of specification. In particular, since the main purpose of a workflow is to achieve a certain (bussiness) goal, we propose a formalism which enables the users to specify their requirements (and expectations) and test if the information that they have provided is, in a sense, sufficient for the workflow to behave "as desired", in terms of the goal. Our methodology allows domain experts to express not only their knowledge, but also the "ignorance" (the semantics allows for unknown values to reflect a realistic situation of agents dealing with incomplete information) and the possibility of occurrence of exceptional situations. As a basis for formalizing the process of equirements specifications, we are using the recent results on reasoning about actions. We propose a high level language AW which enables specifying the effects that activites have on the environment and how they should be coordinated. We also describe our prototype tool for process specification. Strictly speaking, in this work we go "one step" before actual analysis and design, and offer a formalism which enables the involved partners to see if the extent to which they have expressed their domain knowledge (which may sometimes be subject to a proprietary restricions) can satisfy the intended needs and behaviour of their product_to_be. We define an entailment relation which enables reasoning about the correctness of the specification, in terms of achieving a desired goal and, also testing about consequences of modifications in the workflow descriptions.

Policies are increasingly being used to manage complex communication networks. In this paper we present our work on a "policy server" which is being used to provide centralized administration of packet voice gateways and "soft switches" in next generation circuit and packet telephony networks. The policies running in the policy server are specified using a domain independent policy description language (PDL). This paper is motivated by the problem of evaluating policies specified in PDL. We present an algorithm for evaluating policies and study both its theoretical and empirical behavior. We show that the problem of evaluating policies is quite intractable. However we note that the hard instances of the policy evaluation problem are quite rare in real world networks. Under some very realistic assumptions we are able to show that our policy evaluation algorithm is quite efficient and is well suited for enforcing policies in complex networks. These results constitute the first attempt to develop a formal framework to study the informal concepts of policy based network management.

We present the design and implementation of the network management layer (Netmon) of the SARAS softswitch developed at Bell Laboratories. The key distinguishing feature of the Netmon subsystem is that the "logic" governing the management is tailored on a per-customer basis by crafting a set of policies appropriate for the customer, and enforcing them via the system. Most such policies can be formulated as sets of low-level rules that describe how to (re)configure a device or how to manipulate the different network elements under different conditions. The system has been currently deployed to do operations, administration, maintenance and provisioning (OAM&P) in carrier-grade communication networks.

This paper presents a rigorous methodology for using annotated logic programming techniques to handle user preferences and needs in answering database queries. Two alternative transformations turn a database program into a new program that returns an

Presents the design of an interactive tool for minimal updates of views in knowledge bases, while maintaining the consistency, expressed by a set of integrity constraints. Minimality is based on a partial order which captures the distance between the old state, before the update request, and the new state, in which the request is satisfied. On the user interface part, once the schema and the database are selected from the initial menu, the system automatically generates the selection menus and communication boxes to guide the user through the update.

An uncertainty reasoning method is presented in this article. The method can be used to compute from a given set of conditional probabilities the best lower bounds and the best upper bounds of those conditional probabilities that are not explicitly provided. The computation of the best upper(lower) bound of such a conditional probability relies on solution of a linear programming problem. Some reduction techniques are proposed in this article to improve the efficiency of our uncertainty reasoning method. As illustrated in Section 4.3, for many uncertainty reasoning problems in medical diagnosis, by using our reduction techniques, the best range of a conditional probability, which is specified by a lower bound and an upper bound, can be computed in polynomial time in terms of the number of basic events involved in the reasoning.

This paper describes a change theory based on abductive reasoning. We take the AGM postulates for revisions, expansions and contractions, and Katsuno and Mendelzon postulates for updates and incorporate abduction into them. A key feature of the theory is that presents a unified view of standard change operators and abductive change operators rather than a new and independent change theory for abductive changes. Abductive operators reduce to standard change operators in the limiting cases.

A new high level Petri net (HLPN) model is introduced as a graphical syntax for Horn clause logic (HCL) programs. We call these nets: Horn clause logic goal directed nets (HCLGNs). It is shown that there is a bijection between the queried definite programs and the class of HCLGNs. In addition, a visualization of SLD resolution is realized through the enabling and firing rules and net markings. The correctness of these rules with respect to SLD resolution is also proven. We model SLD refutations and failing computations. It is shown how HCLGNs can be used to model built in atoms and provide a new AND/OR parallel execution model. Recently, several software packages (graphical editors) have become available for editing and executing HLPNs. The simulation capabilities of the HLPN software offer opportunities to perform automated, interactive code walk throughs and also have potential for providing a framework for visual debugging environments. However, HCLGNs differ from the major classes of HLPNs for which software tools have been developed in primarily two ways: the tokens in the markings can have variables; and the firing of a transition may not only update the marking of the adjacent places, but may instantiate variables in tokens in the markings of places that are non adjacent to the fired transition. Thus, the existing packages can only provide graphical syntax editing and are not appropriate for graphical simulation of HCLGNs. We provide an algebraic characterization of HCLGNs that can serve as a design guideline for implementing HCLGNs.

In this paper, we present our research on defining a correct semantics for a class of update rule (UR) programs, and discuss implemanting these programs in a DBMS environment. Update rules execute by updating relations in a database which may cause the further execution of rules. A correct semantics must guarantee that the execution of the rules will terminate and that it will produce a minimal updated database. The class of UR programs is syntactically identified, based upon a concept that is similar to stratification. We extend that strict definition of stratification and allow a relaxed criterion for partitioning of the rules in the UR program. This relaxation allows a limited degree of nondeterminism in rule execution. We define an execution semantics based upon a monotonic fixpoint operator T UR , resulting in a set of fixpoints for UR. The monotionicity of the operator is maintained nby explicitly representing the effect of asserting and retracting tuples in the database. A declarative semantics for the update rule program is obtained by associating a normal logic program UR to represent the UR program. We use the stable model semantics which characterize a normal logic program by a set of minimal models which are called stable models. We show the equivalence between the set of fixpoints for UR and the set of stable models for UR. We briefly discuss implementing the fixpoint semantics of the UR program in a DBMS environment. Relations that can be updated by the rules are updatable relations and they are extended with two flags. An update rule is represented by a database query, which queries the updatable relations as well as database relaions, i.e., those relations which are not update by rules. We describe an algorithm to process the queries and compute a fixpoint in the DBMS environment and obtain a final database.

This paper presents an application of the concepts of siphons (deadlocks) and inhibitor arcs in Petri net theory to logic programs with negations. More specifically, an extended Petri net is used to model function-free normal logic programs. In this model, because of the presence of inhibitor arcs, the arbitrary applications of firing rule may cause a contradictory situation. We suggest two directions to avoid contradictions: greedy and secure applications of firing rule. We choose the secure application and show that this is a direct translation of the well-founded semantics in the net model. Furthermore, we show that the greatest unfounded set corresponds to the greatest siphon in Petri net theory when we delete the transitions disabled by the secure application of firing rule, and that the property of siphon simplifies the computation of well-founded semantics for logic programs. We also propose the reduced-Petri-net method by which we can reduce an extended Petri net to a Petri net without inhibitor arcs and compute the well-founded model by iterative applications of this transformation using conventional application of firing rule.>

An extended Petri net is used to model function-free logic programs with negation, i.e. normal logic programs. In this model, because of the presence of inhibitor arcs, the arbitrary application of firing rules may cause a contradictory situation. The authors suggest two directions to avoid contradictions, greedy and secure application of firing rules. Secure application is a direct translation of the well-founded semantics in the net model. Furthermore, the authors show that an unfounded set corresponds to a siphon in Petri net theory when one deletes the transitions disabled by the secure application of firing rules, and that the property of siphons simplifies the computation of well-founded semantics for logic programs.>