Semantic forgetting in answer set programming

The notion of forgetting, also known as variable elimination, has been investigated extensively in the context of classical logic, but less so in (nonmonotonic) logic programming and nonmonotonic reasoning. The few approaches that exist are based on syntactic modifications of a program at hand. In this paper, we establish a declarative theory of forgetting for disjunctive logic programs under answer set semantics that is fully based on semantic grounds. The suitability of this theory is justified by a number of desirable properties. In particular, one of our results shows that our notion of forgetting can be entirely captured by classical forgetting. We present several algorithms for computing a representation of the result of forgetting, and provide a characterization of the computational complexity of reasoning from a logic program under forgetting. As applications of our approach, we present a fairly general framework for resolving conflicts in inconsistent knowledge bases that are represented by disjunctive logic programs, and we show how the semantics of inheritance logic programs and update logic programs from the literature can be characterized through forgetting. The basic idea of the conflict resolution framework is to weaken the preferences of each agent by forgetting certain knowledge that causes inconsistency. In particular, we show how to use the notion of forgetting to provide an elegant solution for preference elicitation in disjunctive logic programming.     

Semantics and complexity of recursive aggregates in answer set programming

The addition of aggregates has been one of the most relevant enhancements to the language of answer set programming (ASP). They strengthen the modelling power of ASP in terms of natural and concise problem representations. Previous semantic definitions typically agree in the case of non-recursive aggregates, but the picture is less clear for aggregates involved in recursion. Some proposals explicitly avoid recursive aggregates, most others differ, and many of them do not satisfy desirable criteria, such as minimality or coincidence with answer sets in the aggregate-free case.In this paper we define a semantics for programs with arbitrary aggregates (including monotone, antimonotone, and nonmonotone aggregates) in the full ASP language allowing also for disjunction in the head (disjunctive logic programming — DLP). This semantics is a genuine generalization of the answer set semantics for DLP, it is defined by a natural variant of the Gelfond–Lifschitz transformation, and treats aggregate and non-aggregate literals in a uniform way. This novel transformation is interesting per se also in the aggregate-free case, since it is simpler than the original transformation and does not need to differentiate between positive and negative literals. We prove that our semantics guarantees the minimality (and therefore the incomparability) of answer sets, and we demonstrate that it coincides with the standard answer set semantics on aggregate-free programs.Moreover, we carry out an in-depth study of the computational complexity of the language. The analysis pays particular attention to the impact of syntactical restrictions on programs in the form of limited use of aggregates, disjunction, and negation. While the addition of aggregates does not affect the complexity of the full DLP language, it turns out that their presence does increase the complexity of normal (i.e., non-disjunctive) ASP programs up to the second level of the polynomial hierarchy. However, we show that there are large classes of aggregates the addition of which does not cause any complexity gap even for normal programs, including the fragment allowing for arbitrary monotone, arbitrary antimonotone, and stratified (i.e., non-recursive) nonmonotone aggregates. The analysis provides some useful indications on the possibility to implement aggregates in existing reasoning engines.     

Role mining using answer set programming

With the increasing adoption of role-based access control (RBAC) in business security, role mining technology has been widely applied to aid the process of migrating a non-RBAC system to an RBAC system. However, because it is hard to deal with a variety of constraint conflicts at the same time, none of existing role mining algorithms can simultaneously satisfy various constraints that usually describe organizations’ security and business requirements. To extend the ability of role mining technology, this paper proposes a novel role mining approach using answer set programming (ASP) that complies with constraints and meets various optimization objectives, named constrained role miner (CRM). Essentially, the idea is that ASP is an approach to declarative problem solving. Thus, either to discover RBAC configurations or to deal with conflicts between constraints, ASP programs do not need to specify how answers are computed. Finally, we demonstrate the effectiveness and efficiency of our approach through experimental results.     

Complexity results for answer set programming with bounded predicate arities and implications

Answer set programming is a declarative programming paradigm rooted in logic programming and non-monotonic reasoning. This formalism has become a host for expressing knowledge representation problems, which reinforces the interest in efficient methods for computing answer sets of a logic program. The complexity of various reasoning tasks for general answer set programming has been amply studied and is understood quite well. In this paper, we present a language fragment in which the arities of predicates are bounded by a constant. Subsequently, we analyze the complexity of various reasoning tasks and computational problems for this fragment, comprising answer set existence, brave and cautious reasoning, and strong equivalence. Generally speaking, it turns out that the complexity drops significantly with respect to the full non-ground language, but is still harder than for the respective ground or propositional languages. These results have several implications, most importantly for solver implementations: Virtually all currently available solvers have exponential (in the size of the input) space requirements even for programs with bounded predicate arities, while our results indicate that for those programs polynomial space should be sufficient. This can be seen as a manifestation of the “grounding bottleneck” (meaning that programs are first instantiated and then solved) from which answer set programming solvers currently suffer. As a final contribution, we provide a sketch of a method that can avoid the exponential space requirement for programs with bounded predicate arities. Some results in this paper have been presented in preliminary form at KR 2004 [15].     

Possibilistic uncertainty handling for answer set programming

In this work, we introduce a new framework able to deal with a reasoning that is at the same time non monotonic and uncertain. In order to take into account a certainty level associated to each piece of knowledge, we use possibility theory to extend the non monotonic semantics of stable models for logic programs with default negation. By means of a possibility distribution we define a clear semantics of such programs by introducing what is a possibilistic stable model. We also propose a syntactic process based on a fix-point operator to compute these particular models representing the deductions of the program and their certainty. Then, we show how this introduction of a certainty level on each rule of a program can be used in order to restore its consistency in case of the program has no model at all. Furthermore, we explain how we can compute possibilistic stable models by using available softwares for Answer Set Programming and we describe the main lines of the system that we have developed to achieve this goal.     

Enhancing grid security by fine-grained behavioral control and negotiation-based authorization

Nowadays, Grid has become a leading technology in distributed computing. Grid poses a seamless sharing of heterogeneous computational resources belonging to different domains and conducts efficient collaborations between Grid users. The core Grid functionality defines computational services which allocate computational resources and execute applications submitted by Grid users. The vast models of collaborations and openness of Grid system require a secure, scalable, flexible and expressive authorization model to protect these computational services and Grid resources. Most of the existing authorization models for Grid have granularity to manage access to service invocations while behavioral monitoring of applications executed by these services remains a responsibility of a resource provider. The resource provider executes an application under a local account, and acknowledges all permissions granted to this account to the application. Such approach poses serious security threats to breach system functionality since applications submitted by users could be malicious. We propose a flexible and expressive policy-driven credential-based authorization system to protect Grid computational services against a malicious behavior of applications submitted for the execution. We split an authorization process into two levels: a coarse-grained level that manages access to a computational service; and a fine-grained level that monitors the behavior of applications executed by the computational service. Our framework guarantees that users authorized on a coarse-grained level behave as expected on the fine-grained level. Credentials obtained on the coarse-grained level reflect on fine-grained access decisions. The framework defines trust negotiations on coarse-grained level to overcome scalability problem, and preserves privacy of credentials and security policies of, both, Grid users and providers. Our authorization system was implemented to control access to the Globus Computational GRAM service. A comprehensive performance evaluation shows the practical scope of the proposed system.

基于委托的分布式动态授权策略

针对分布式协作环境中的授权问题,基于委托模型和RBAC模型,提出一种基于委托的分布式动态授权策略。通过扩展RBAC模型的元素集和静态授权操作,并由委托者动态创建临时委托角色和委托授权,支持“部分角色转授权”。系统授权采用三级层次结构实现,并给出了动态委托授权过程。系统实现及应用表明了其能够适应分布协作环境下的分布动态授权需求,遵循“最小特权”原则。     

Abstractions for distributed programming

The StarMod language is designed to provide its users with abstractions for distributed computations. The language is based on Wirth's definition of a “module” as impiemented in Modula. The paper discusses abstraction mechanisms for distributed access control and scheduling: in addition, several examples are used to illustrate these concepts.     

可计算的基于信任的授权委托模型

在开放式多域环境中,信任管理是最常用的访问控制方法.但是,目前的信任管理系统存在着以下不足:(1)没有给出实体之间信任的计算方式,使得模型难以实现;(2)信任的传递过程没有得到很好的控制.针对上述问题,提出了一种多域系统中可计算的基于信任的授权委托模型--CTBAD模型(Computable Trust-Based Authorization Delegation model),重点探讨了CTBAD模型的信任计算方法以及信任传递机制,并且进行了信任关系计算的数据仿真.     

Enable delegation for RBAC with Secure Authorization Certificate

Our motivation in this paper is to explore a Secure Delegation Scheme that could keep access control information hidden through network transmission. This approach introduces the quasirandom structure, 3-Uniform Hypergraph, as the representation structure for authorization information. It generates a Secure Authorization Certificate (SAC) in place of an Attribute Certificate (AC) to enable both Role-based Access Control (RBAC) and a delegation process for hiding authorization information. We have two contributions in this regard: (1) a value-based delegation scheme and (2) a pattern-based RBAC. A Secure Delegation Scheme is based on the hashing values generated with the quasirandom structure. With this scheme, the delegation process will greatly reduce the risk of sensitive authorization information leakage for applications. In the case of pattern-based access, we introduce a new hash function using quasirandom structure to make a fingerprint¹ for RBAC. The quasirandom structure derived from k-Uniform Hypergraph has measurable uniformity, which is an advantage over traditional hash functions. Another advantage is that it does not need to access the entire message context to generate the fingerprint which is essential for traditional hash functions such as MD5, SHA-1, etc.     

Answer set based design of knowledge systems

The aim of this paper is to demonstrate that A-Prolog is a powerful language for the construction of reasoning systems. In fact, A-Prolog allows to specify the initial situation, the domain model, the control knowledge, and the reasoning modules. Moreover, it is efficient enough to be used for practical tasks and can be nicely integrated with programming languages such as Java. An extension of A-Prolog (CR-Prolog) allows to further improve the quality of reasoning by specifying requirements that the solutions should satisfy if at all possible. The features of A-Prolog and CR-Prolog are demonstrated by describing in detail the design of USA-Advisor, an A-Prolog based decision support system for the Space Shuttle flight controllers.     

An incremental algorithm for generating all minimal models

The task of generating minimal models of a knowledge base is at the computational heart of diagnosis systems like truth maintenance systems, and of nonmonotonic systems like autoepistemic logic, default logic, and disjunctive logic programs. Unfortunately, it is NP-hard. In this paper we present a hierarchy of classes of knowledge bases, Ψ₁,Ψ₂,… , with the following properties: first, Ψ₁ is the class of all Horn knowledge bases; second, if a knowledge base T is in Ψk, then T has at most k minimal models, and all of them may be found in time O(lk²), where l is the length of the knowledge base; third, for an arbitrary knowledge base T, we can find the minimum k such that T belongs to Ψk in time polynomial in the size of T; and, last, where K is the class of all knowledge bases, it is the case that , that is, every knowledge base belongs to some class in the hierarchy. The algorithm is incremental, that is, it is capable of generating one model at a time.     

基于2型模糊描述逻辑的知识描述与推理及其在信任管理系统中的应用

描述逻辑由于其强大的描述能力与成熟的推理算法而被广泛应用。然而,经典描述逻辑局限于处理确定的概念和关系,从而导致描述逻辑很难处理类似语义网等大型本体系统中的模糊知识。虽然1型模糊集可以一定程度上减轻不确定性带来的影响,但是其采用确定的隶属度值来决定模糊度的方法是不够精准的。与之相比,基于2型模糊集的系统能够利用隶属度区间更加精确地描述模糊信息。本文给出描述逻辑ALC的2型模糊扩展形式,并且给出并分析了2型模糊ALC的描述和推理方法。最后使用2型模糊ALC建立了一个基于模糊本体的信任管理系统FOntoTM。     

Delegation with supervision

Delegation certificates (e.g. SPKI) support the decentralized management of access rights in organizations without the need for a centralized server to mediate every delegation operation. However, it does not allow the access rights to be delegated in a flexible way. For instance, a user cannot be granted the authorization to perform delegation of permission without granting himself/herself the authorization to exercise the associated permission at the same time. In this paper, we propose an improved delegation model, where the various users in a delegation chain may perform supervision on the delegate to exercise the delegated permission. We describe the way to support the model using SPKI as an example. Also, we describe how to support efficient authorization in delegation with supervision using proxy signature techniques.     

Reasoning with infinite stable models

This paper illustrates extensively the theoretical properties, the implementation issues, and the programming style underlying finitary programs. They are a class of normal logic programs whose consequences under the stable model semantics can be effectively computed, despite the fact that finitary programs admit function symbols (hence infinite domains) and recursion. From a theoretical point of view, finitary programs are interesting because they enjoy properties that are extremely unusual for a nonmonotonic formalism, such as compactness. From the application point of view, the theory of finitary programs shows how the existing technology for answer set programming can be extended from problem solving below the second level of the polynomial hierarchy to all semidecidable problems. Moreover, finitary programs allow a more natural encoding of recursive data structures and may increase the performance of credulous reasoners.     

Outlier detection for simple default theories

It was noted recently that the framework of default logics can be exploited for detecting outliers. Outliers are observations expressed by sets of literals that feature unexpected properties. These observations are not explicitly provided in input (as it happens with abduction) but, rather, they are hidden in the given knowledge base. Unfortunately, in the two related formalisms for specifying defaults — Reiter's default logic and extended disjunctive logic programs — the most general outlier detection problems turn out to lie at the third level of the polynomial hierarchy. In this note, we analyze the complexity of outlier detection for two very simple classes of default theories, namely NU and DNU, for which the entailment problem is solvable in polynomial time. We show that, for these classes, checking for the existence of an outlier is anyway intractable. This result contributes to further showing the inherent intractability of outlier detection in default reasoning.