Controlled Query Evaluation (CQE) is a methodology designed to maintain confidentiality by either rejecting specific queries or adjusting responses to safeguard sensitive information. In this investigation, our focus centers on CQE within Description Logic ontologies, aiming to ensure that queries are answered truthfully as long as possible before resorting to deceptive responses, a cooperativity property which is called the “longest honeymoon”. Our work introduces new semantics for CQE, denoted as MC-CQE, which enjoys the longest honeymoon property and outperforms previous methodologies in terms of cooperativity. We study the complexity of query answering in this new framework for ontologies expressed in the Description Logic DL-Lite_R. Specifically, we establish data complexity results under different maximally cooperative semantics and for different classes of queries. Our results identify both tractable and intractable cases. In particular, we show that the evaluation of Boolean unions of conjunctive queries is the same under all the above semantics and its data complexity is in AC^0. This result makes query answering amenable to SQL query rewriting. However, this favorable property does not extend to open queries, even with a restricted query language limited to conjunctions of atoms. While, in general, answering open queries in the MC-CQE framework is intractable, we identify a sub-family of semantics under which answering full conjunctive queries is tractable.

A deductive module of a knowledge base KB is a subset of KB that preserves a specified class of consequences. Module extraction is applied in ontology design, debugging, and reasoning. The locality-based module extractors of the OWL API are less effective when the knowledge base contains facts such as ABox assertions. The competing module extractor PrisM computes smaller modules at the cost of higher computation time. In this paper, we introduce and study a novel module extraction technique, called conditional module extraction , that can be applied to satisfiable SRIQ ( D ) knowledge bases. Experimental analysis shows that conditional module extraction constitutes an appealing alternative to PrisM and to the locality-based extractors of the OWL API, when the ABox is nonempty.

This paper introduces and investigates k-unmatchability, a counterpart of k-anonymity for knowledge graphs. Like k-anonimity, k-unmatchability enhances privacy by ensuring that any individual in any external source can always be matched to either none or at least k different anonymized individuals. The tradeoff between privacy protection and information loss can be controlled with parameter k. We analyze the data complexity of k-unmatchability under different notions of anonymization.

The growing literature on confidentiality in knowledge representation and reasoning sometimes may cause a false sense of security, due to lack of details about the attacker, and some misconceptions about security-related concepts. This paper analyzes the vulnerabilities of some recent knowledge protection methods to increase the awareness about their actual effectiveness and their mutual differences.

One of the factors that hinder the adoption of nonmonotonic description logics in applications is performance. Even when monotonic and nonmonotonic inferences have the same asymptotic complexity, the implementation of nonmonotonic reasoning may be significantly slower. The family of nonmonotonic logics DLN is no exception to this behavior. We address this issue by introducing two provably correct and complete optimizations for reasoning in DLN. The first optimization is a module extractor that has the purpose of focusing reasoning on a relevant subset of the knowledge base. The second, called optimistic evaluation, aims at exploiting incremental reasoning in a better way. Extensive experimental evaluation shows that the optimized DLN reasoning is often compatible with interactive query answering, thus bringing nonmonotonic description logics closer to practical applications.

Many modern applications of description logics (DLs, for short), such as biomedical ontologies and semantic web policies, provide compelling motivations for extending DLs with an overriding mechanism analogous to the homonymous feature of object-oriented programming. Rational closure (RC) is one of the candidate semantics for such extensions, and one of the most intensively studied. So far, however, it has been limited to strict fragments of SROIQ(D) – the logic on which OWL2 is founded. In this paper we prove that RC cannot be extended to logics that do not satisfy the disjoint model union property, including SROIQ(D). Then we introduce a refinement of RC called stable rational closure that overcomes the dependency on the disjoint model union property. Our results show that stable RC is a natural extension of RC. However, its positive features come at a price: stable RC re-introduces one of the undesirable features of other nonmonotonic logics, namely, deductive closures may not exist and may not be unique.

This paper shows how knowledge representation and reasoning techniques can be used to support organizations in complying with the GDPR, that is, the new European data protection regulation. This work is carried out in a European H2020 project called SPECIAL. Data usage policies, the consent of data subjects, and selected fragments of the GDPR are encoded in a fragment of OWL2 called PL (policy language); compliance checking and policy validation are reduced to subsumption checking and concept consistency checking. This work proposes a satisfactory tradeoff between the expressiveness requirements on PL posed by the modeling of the GDPR, and the scalability requirements that arise from the use cases provided by SPECIAL's industrial partners. Real-time compliance checking is achieved by means of a specialized reasoner, called PLR, that leverages knowledge compilation and structural subsumption techniques. The performance of a prototype implementation of PLR is analyzed through systematic experiments, and compared with the performance of other important reasoners. Moreover, we show how PL and PLR can be extended to support richer ontologies, by means of import-by-query techniques. We prove novel tractability and intractability results related to PL, and some negative results about the restrictions posed on ontology import.

We illustrate a formalization of data usage policies in a fragment of OWL2. It can be used to encode (i) a company's data protection policy, (ii) data subjects' consent to data processing, and (iii) part of the GDPR (the forthcoming European Data Protection Regulation). Then a company's policy can be checked for compliance with data subjects' consent and with part of the GDPR by means of subsumption queries. We provide a complete and tractable structural subsumption algorithm for compliance checking and prove the intractability of a natural generalization of the policy language.

DL^N is a recent nonmonotonic description logic, designed for satisfying independently proposed knowledge engineering requirements, and for removing some recurrent drawbacks of traditional nonmonotonic semantics. In this paper we study the logical properties of DL^N and their relationships with the KLM postulates. We use various versions of the KLM postulates to deepen the comparison with related work, and illustrate the different tradeoffs between opposite expressivity requirements adopted by each approach.

Nonmonotonic inferences are not yet supported by Description Logic technology, although their potential usefulness is widely recognized. Lack of support to nonmonotonic reasoning is due to a number of issues related to expressiveness, computational complexity, and optimizations. This work contributes to the practical support of nonmonotonic reasoning in description logics by introducing a new semantics designed to address knowledge engineering needs. The formalism is validated through extensive comparison with the other nonmonotonic DLs, and systematic scalability tests.

Context-aware access control systems should reactively adapt access control decisions to dynamic environmental conditions. In this paper we present ERBAC – an event-driven extension of the TRBAC model that allows the specification and enforcement of general reactive policies – and its implementation. While almost all the individual features of ERBAC occur separately in some previous model, the detailed design of the policy language, its implementation in XACML, and its testing contribute to the development of expressive, event-driven policy frameworks by demonstrating that this rich model can be satisfactorily implemented, and that its expressivity and performance are compatible with a variety of realistic application scenarios. In particular, a number of examples illustrate ERBAC’s expressive power, and its ability of handling exceptional situations in a flexible way, while keeping policies compact and manageable. The prototype extends XACML’s language and the implementation of the PDP to support the new model. Systematic scalability experiments show that the computational cost of policy rule evaluation in ERBAC is compatible with real-world applications.

Context-aware access control systems should reactively adapt access control decisions to dynamic environmental conditions. In this paper we present an extension of the TRBAC model that allows the specification and enforcement of general reactive policies. Then we extend XACML to support the new model, and illustrate a prototype implementation of the PDP.

The research on low-complexity nonmonotonic description logics recently identified a fragment of EL with bottom, supporting defeasible inheritance with overriding, where reasoning can be carried out in polynomial time. We contribute to that framework by supporting more axiom schemata and all the concept constructors of EL++ without increasing asymptotic complexity. Moreover, we show that all the syntactic restrictions we adopt are necessary by proving several coNP-hardness results.

We analyze the complexity of reasoning in EL with defeasible inclusions and extensions thereof. The results by Bonatti et al., 2009a are extended by proving tight lower complexity bounds and by relaxing the syntactic restrictions adopted there. We further extend the old framework by supporting arbitrary priority relations.

Open distributed environments, such as the World Wide Web, facilitate information sharing but provide limited support to the protection of sensitive information and resources. Trust negotiation (TN) frameworks have been proposed as a better solution for open environments, in which parties may get in touch and interact without being previously known to each other. In this paper, we illustrate Protune, a rule-based TN system. By describing Protune, we will illustrate the advantages that arise from an advanced rule-based approach in terms of deployment efforts, user friendliness, communication efficiency, and interoperability. The generality and technological feasibility of Protune's approach are assessed through an extensive analysis and experimental evaluations.

Abstract Answer set programming—the most popular problem solving paradigm based on logic programs—has been recently extended to support uninterpreted function symbols (Syrjänen 2001, Bonatti 2004; Simkus and Eiter 2007; Gebseret al. 2007; Baseliceet al. 2009; Calimeriet al. 2008). All of these approaches have some limitation. In this paper we propose a class of programs called FP2 that enjoys a different trade-off between expressiveness and complexity. FP2 is inspired by the extension of finitary normal programs with local variables introduced in (Bonatti 2004, Section 5). FP2 programs enjoy the following unique combination of properties: (i) the ability of expressing predicates with infinite extensions; (ii) full support for predicates with arbitrary arity; (iii) decidability of FP2 membership checking; (iv) decidability of skeptical and credulous stable model reasoning for call-safe queries. Odd cycles are supported by composing FP2 programs with argument restricted programs.

As fragments of first-order logic, Description logics (DLs) do not provide nonmonotonic features such as defeasible inheritance and default rules. Since many applications would benefit from the availability of such features, several families of nonmonotonic DLs have been developed that are mostly based on default logic and autoepistemic logic. In this paper, we consider circumscription as an interesting alternative approach to nonmonotonic DLs that, in particular, supports defeasible inheritance in a natural way. We study DLs extended with circumscription under different language restrictions and under different constraints on the sets of minimized, fixed, and varying predicates, and pinpoint the exact computational complexity of reasoning for DLs ranging from ALC to ALCIO and ALCQO. When the minimized and fixed predicates include only concept names but no role names, then reasoning is complete for NExpTime^NP. It becomes complete for NP^NExpTime when the number of minimized and fixed predicates is bounded by a constant. If roles can be minimized or fixed, then complexity ranges from NExpTime^NP to undecidability.

Abstract Disjunctive finitary programs are a class of logic programs admitting function symbols and hence infinite domains. They have very good computational properties; for example, ground queries are decidable, while in the general case the stable model semantics are Π11-hard. In this paper we prove that a larger class of programs, called finitely recursive programs, preserve most of the good properties of finitary programs under the stable model semantics, which are as follows: (i) finitely recursive programs enjoy a compactness property; (ii) inconsistency checking and skeptical reasoning are semidecidable; (iii) skeptical resolution is complete for normal finitely recursive programs. Moreover, we show how to check inconsistency and answer skeptical queries using finite subsets of the ground program instantiation. We achieve this by extending the splitting sequence theorem by Lifschitz and Turner: we prove that if the input program P is finitely recursive, then the partial stable models determined by any smooth splitting ω-sequence converge to a stable model of P.

The fully enriched μ-calculus is the extension of the propositional μ-calculus with inverse programs, graded modalities, and nominals. While satisfiability in several expressive fragments of the fully enriched μ-calculus is known to be decidable and ExpTime-complete, it has recently been proved that the full calculus is undecidable. In this paper, we study the fragments of the fully enriched μ-calculus that are obtained by dropping at least one of the additional constructs. We show that, in all fragments obtained in this way, satisfiability is decidable and ExpTime-complete. Thus, we identify a family of decidable logics that are maximal (and incomparable) in expressive power. Our results are obtained by introducing two new automata models, showing that their emptiness problems are ExpTime-complete, and then reducing satisfiability in the relevant logics to these problems. The automata models we introduce are two-way graded alternating parity automata over infinite trees (2GAPTs) and fully enriched automata (FEAs) over infinite forests. The former are a common generalization of two incomparable automata models from the literature. The latter extend alternating automata in a similar way as the fully enriched μ-calculus extends the standard μ-calculus.

This paper introduces the PeerAccess framework for reasoning about authorization in open distributed systems, and shows how a parameterization of the framework can be used to reason about access to computational resources in a grid environment. The PeerAccess framework supports a declarative description of the behavior of peers that selectively push and/or pull information from certain other peers. PeerAccess local knowledge bases encode the basic knowledge of each peer (e.g., Alice's group memberships), its policies governing the release of each possible piece of information to other peers, and information that guides and limits its search process when trying to obtain particular pieces of information from other peers. PeerAccess proofs of authorization are verifiable and nonrepudiable, and their construction relies only on the local information possessed by peers and their parameterized behavior with respect to query answering, information push/pull, and information release policies (i.e., no omniscient viewpoint is required). We present the PeerAccess language and peer knowledge base structure, the associated formal semantics and proof theory, and examples of the use of PeerAccess in constructing proofs of authorization to access computational resources.

The open nature of modern network applications is potentially an excellent support to cooperative work of all sorts, and at the same time a major source of security and privacy concerns. It is now commonly recognized that traditional authentication techniques do not scale to the new open scenarios, and are not suitable for the dynamic nature of virtual organizations. Research is focussing on more flexible trust management models that let two or more peers interact securely even if they have never interacted with each other before and have no previous knowledge about each other's properties and protection requirements. This situation occurs whenever a new virtual organization is created or extended. Trust management is based on electronic credentials, that constitute a flexible way of representing properties of individuals, groups and organizations. In principle, any entity can issue its own credentials, thereby signing some statements about some entities. Other peers may decide whether that entity can be trusted on those statements, in the framework of a specific task. Credentials are verifiable and un-forgeable, so it can be robustly checked whether a given statement has been actually signed (hence issued) by a specific peer.

While many works have been devoted to service matchmaking and modeling nonfunctional properties, the problem of matching service requests to offers in an optimal way has not yet been extensively studied. In this paper we formalize three kinds of optimal service selection problems, based on different criteria. Then we study their complexity and implement solutions. We prove that one-time costs make the optimal selection problem computationally hard; in the absence of these costs the problem can be solved in polynomial time. We designed and implemented both exact and heuristic (suboptimal) algorithms for the hard case, and carried out a preliminary experimental evaluation with interesting results.

The problem of deciding query containment has important applications in classical query optimization and heterogeneous database systems. Query containment is undecidable for unrestricted recursive queries, and decidable for recursive monadic queries and conjunctive queries over regular path expressions. In this paper, we identify a new class of recursive queries with decidable containment. Our framework extends the aforementioned query classes by supporting recursive predicates with more than two arguments and nonlinear recursion.

The widespread use of Internet-based services is increasing the amount of information (such as user profiles) that clients are required to disclose. This information demand is necessary for regulating access to services, and functionally convenient (e.g., to support service customization), but it h as raised privacy-related concerns which, if not addressed, may affect the users disposition to use network services. At the same time, servers need to regulate service access without disclosing entirely the details of their access control policy. There is therefore a pressing need for privacy-aware techniques to regulate access to services open to the network. We propose an approach for regulating service access and information disclosure on the Web. The approach consists of a uniform formal framework to formulate – and reason about – both service access and information disclosure constraints. It also provides a means for parties to communicate their requirements while ensuring that no private information be disclosed and that the communicated requirements are correct with respect to the constraints.

Despite considerable advancements in the area of access control and authorization languages, current approaches to enforcing access control are all based on monolithic and complete specifications. This assumption is too restrictive when access control restrictions to be enforced come from the combination of different policy specifications, each possibly under the control of independent authorities, and where the specifics of some component policies may not even be known apriori. Turning individual specifications into a coherent policy to be fed into the access control system requires a nontrivial combination and translation process. This article addresses the problem of combining authorization specifications that may be independently stated, possibly in different languages and according to different policies. We propose an algebra of security policies together with its formal semantics and illustrate how to formulate complex policies in the algebra and reason about them. A translation of policy expressions into equivalent logic programs is illustrated, which provides the basis for the implementation of the algebra. The algebra's expressiveness is analyzed through a comparison with first-order logic.

A uniform proof-theoretic reconstruction of the major nonmonotonic logics is introduced. It consists of analytic sequent calculi where the details of nonmonotonic assumption making are modelled by an axiomatic rejection method. Another distinctive feature of the calculi is the use of provability constraints that make reasoning largely independent of any specific derivation strategy. The resulting account of nonmonotonic inference is simple and flexible enough to be a promising playground for investigating and comparing proof strategies, and for describing the behavior of automated reasoning systems. We provide some preliminary evidence for this claim by introducing optimized calculi, and by simulating an existing tableaux-based method for circumscription. The calculi for skeptical reasoning support concise proofs that may depend on a strict subset of the given theory. This is a difficult task, given the nonmonotonic behavior of the logics.

We present an approach for controlling access to data publishers in the framework of Web-based information services. The paper presents a model for enforcing access control regulations, an XML core schema and namespace for expressing such regulations, and illustrates the architecture of the Access Control Unit (ACU), an autonomous software component based on the proposed model. Besides "standard" authorizations, the ACU supports authorizations based on user profiles and dynamic conditions whose outcome is determined by user actions such as the acceptance of a written agreement and/or payment.

Role-based access control (RBAC) models are receiving increasing attention as a generalized approach to access control. Roles may be available to users at certain time periods, and unavailable at others. Moreover, there can be temporal dependencies among roles. To tackle such dynamic aspects, we introduce Temporal-RBAC (TRBAC), an extension of the RBAC model. TRBAC supports periodic role enabling and disabling---possibly with individual exceptions for particular users---and temporal dependencies among such actions, expressed by means of role triggers. Role trigger actions may be either immediately executed, or deferred by an explicitly specified amount of time. Enabling and disabling actions may be given a priority, which is used to solve conflicting actions. A formal semantics for the specification language is provided, and a polynomial safeness check is introduced to reject ambiguous or inconsistent specifications. Finally, a system implementing TRBAC on top of a conventional DBMS is presented.

The widespread use of Internet-based services is increasing the amount of information (such as user pro les) that clients are required to disclose. This information demand is necessary for regulating access to services, and functionally convenient (e.g., to support service customization), but it has raised privacy-related concerns which, if not addressed, may aect the users disposition to use network services. At the same time, servers need to regulate service access without disclosing entirely the details of their access control policy. There is therefore a pressing need for privacy-aware techniques to regulate access to services open to the network. We propose

Article A modular approach to composing access control policies Share on Authors: Piero Bonatti Dip. Scienze dell'Informazione, Polo di Crema, Università di Milano, Via Bramante 65, 26013 Crema, Italy Dip. Scienze dell'Informazione, Polo di Crema, Università di Milano, Via Bramante 65, 26013 Crema, ItalyView Profile , Sabrina de Capitani di Vimercati Dip. Elettronica, Università di Brescia, Via Branze 38, 25123 Brescia, Italy Dip. Elettronica, Università di Brescia, Via Branze 38, 25123 Brescia, ItalyView Profile , Pierangela Samarati Dip. Scienze dell'Informazione, Polo di Crema, Università di Milano, Via Bramante 65, 26013 Crema, Italy Dip. Scienze dell'Informazione, Polo di Crema, Università di Milano, Via Bramante 65, 26013 Crema, ItalyView Profile Authors Info & Claims CCS '00: Proceedings of the 7th ACM conference on Computer and Communications SecurityNovember 2000 Pages 164–173https://doi.org/10.1145/352600.352623Online:01 November 2000Publication History 59citation1,075DownloadsMetricsTotal Citations59Total Downloads1,075Last 12 Months14Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In this paper we present a powerful authorization mechanism which provides support for: (1) periodic authorizations (both positive and negative), that is, authorizations that hold only in specific periods of time; (2) user-defined deductive temporal rules, by which new authorizations can be derived from those explicitly specified; (3) a hierarchical organization of subjects and objects, supporting a more adequate representation of their semantics. From the authorizations explicitly specified, additional authorizations are automatically derived by the system based on those hierarchies. The resulting model is therefore very flexible in terms of the kinds of protection requirements that it can represent. The flexibility provided to the users requires a non trivial underlying formal model where temporal constraints, derivation rules and object and subject hierarchies can be represented. In particular, when inheritance and derivation rules are used simultaneously, there is need for conditions ensuring that the authorization base is free from ambiguities. In this paper, we introduce a notion of safeness , and prove that it guarantees the absence of ambiguities and inconsistencies in the specification. Moreover, we define an efficient algorithm for computing authorizations from safe specifications. Finally, we provide a methodology for supporting temporal authorizations in heterogeneous, distributed systems.

The need to automatically extract and classify the contents of multimedia data archives such as images, video, and text documents has led to significant work on similarity based retrieval of data. To date, most work in this area has focused on the creation of index structures for similarity based retrieval. There is very little work on developing formalisms for querying multimedia databases that support similarity based computations and optimizing such queries, even though it is well known that feature extraction and identification algorithms in media data are very expensive. We introduce a similarity algebra that brings together relational operators and results of multiple similarity implementations in a uniform language. The algebra can be used to specify complex queries that combine different interpretations of similarity values and multiple algorithms for computing these values. We prove equivalence and containment relationships between similarity algebra expressions and develop query rewriting methods based on these results. We then provide a generic cost model for evaluating cost of query plans in the similarity algebra and query optimization methods based on this model. We supplement the paper with experimental results that illustrate the use of the algebra and the effectiveness of query optimization methods using the Integrated Search Engine (I.SEE) as the testbed.

The problem of integrating multiple heterogeneous legacy databases is an important problem. Many papers [3,7,9] to date on this topic have assumed that all the databases comprising a mediated/federated system share the same security ordering. This assumption is often not true as the databases may have been developed independently by different agencies at different points in time. In this paper, we present techniques by which we may merge multiple security orderings into a single unified ordering that preserves the security relationships between orderings. We present a logic programming based approach, as well as a graph theoretical approach to this problem.

Two forms of self-reference that affect complete formalizations of provability will be identified. They had been previously studied separately in works about truth and provability, and in works on non-monotonic reasoning, respectively. It will be shown that formalizing provability envolves non-monotonic reasoning as a subproblem, which implies that the two forms of self-reference need to be faced simultaneously. For this purpose, we will introduce a 3-valued provability predicate Demos, which is perfectly tolerant to both forms of self-reference. It will be shown that Demos formalizes surprisingly natural notions of provability and unprovability and that it preserves many of the intuitions underlying classical provability predicates. Furthermore, Demos can simulate autoepistemic logic as well as several forms of negation-as-failure; this is important because non-monotonic and epistemic reasoning are some of the intended applications of formalized provability. Demos will be given two complete axiomatizations: an extensional axiomatization Ax(D) (that can be obtained by iterating a monotonic operator) and a more structured axiomatization, consisting of a logic program where Demos 's implemented as a meta-interpreter.

We develop a formal logical foundation for secure deductive databases. This logical foundation is based on an extended logic involving several modal operators. We develop two models of interaction between the user and the database called "yes-no" dialogs, and "yes-no-don't know" dialogs. Both dialog frameworks allow the database to lie to the user. We develop an algorithm for answering queries using yes-no dialogs and prove that secure query processing using yes-no dialogs is NP-complete. Consequently, the degree of computational intractability of query processing with yes-no dialogs is no worse than for ordinary databases. Furthermore, the algorithm is maximally cooperative to user in the sense that lying is resorted to only when absolutely necessary. For Horn databases, we show that secure query processing can be achieved in linear time-hence, this is no more intractable than the situation in ordinary databases. Finally, we identify necessary and sufficient conditions for the database to be able to preserve security. Similar results are also obtained for yes-no-don't know dialogs.>