Topics in Knowledge Bases: Epistemic Ontologies and Secrecy-preserving Reasoning

Tao Jia2012 · DOI

TL;DR

This dissertation tackles two key challenges in knowledge representation and reasoning: handling knowledge from multiple experts and protecting sensitive information in knowledge bases. It introduces novel algorithms for query answering in epistemic description logics and develops techniques for secrecy-preserving query answering in both single-agent and multi-agent settings under the open world assumption.

What Problem Does This Paper Address?

The paper addresses two main problems:

  1. Reasoning with Knowledge from Multiple Experts: In many real-world scenarios, knowledge comes from different sources or experts, and it's crucial to represent and reason about what each expert knows. Traditional description logics (DLs) struggle to capture this "epistemic" aspect of knowledge.
  2. Secrecy-Preserving Query Answering: As knowledge bases (KBs) become more prevalent in sensitive domains like healthcare and national security, there's a growing need to answer queries while protecting confidential information (secrets). Existing access control methods can be too restrictive, preventing the use of sensitive information even when it's possible to do so without compromising secrecy. The paper also considers the complexity of this problem in multi-agent systems where agents can share information, each with potentially different secrecy requirements.

Methods

The paper introduces several novel techniques:

  • Epistemic Description Logics (ALCKm and ALCS4m): These logics extend the standard description logic ALC by incorporating modal operators to represent knowledge of different experts.
  • Tableau Algorithms (Ax and As4): Sound and complete tableau algorithms are developed for query answering in ALCKm and ALCS4m knowledge bases with acyclic TBoxes. These algorithms are designed to be implementable in PSPACE.
  • Secrecy-Preserving Query Answering (SPQA) Framework: A general framework is proposed for SPQA under the Open World Assumption (OWA). This framework aims to answer queries informatively while protecting secrets by "feigning ignorance" (answering "Unknown") when a truthful answer might reveal sensitive information.
  • Secrecy Envelopes: The core idea for SPQA is to precompute "secrecy envelopes." These are sets of assertions that "disrupt" proofs of secrets, preventing an agent from deducing sensitive information. The paper focuses on computing "tight" envelopes, which are minimal in the sense that removing any part would compromise secrecy.
  • EL Description Logic for SPQA: The SPQA framework is applied to the Description Logic EL, known for its computational tractability. Novel algorithms for computing tight envelopes in EL are presented, including a naive approach and an optimized procedure (TIGHT).
  • Multi-Agent SPQA: The framework is extended to handle multiple querying agents who can communicate and share answers. This is modeled using a communication graph (a DAG), and the concept of individual secrecy envelopes for each agent is introduced.
  • Horn KB for SPQA: The approach is illustrated with Propositional Horn Knowledge Bases, a computationally efficient class of KBs.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Epistemic DLs Offer a Solution for Expert Knowledge: By adding modal operators, DLs can effectively represent and reason about knowledge attributed to specific experts, opening up new possibilities for modeling complex information.
  • OWA is Crucial for Secrecy: The Open World Assumption is essential for SPQA because it allows the system to answer "Unknown" when information is incomplete or when secrecy is being enforced, preventing agents from distinguishing between the two.
  • Envelopes as a Proactive Secrecy Mechanism: Precomputing secrecy envelopes allows for more efficient and informative query answering compared to reactive, lazy evaluation methods, especially as query histories grow.
  • Tight Envelopes Balance Informativeness and Secrecy: The concept of "tight" envelopes is key to maximizing informativeness while ensuring secrecy. Computing minimum envelopes is hard, but tight envelopes offer a practical compromise.
  • Inverting Inference Rules for Envelope Construction: A novel technique of inverting inference rules is used to construct secrecy envelopes by identifying "disrupting" formulas.
  • Multi-Agent Communication Graphs Model Information Flow: Using communication graphs effectively models how agents share information and how secrecy policies propagate in a multi-agent system.

Key Results

  • PSPACE Algorithms for Epistemic DLs: Sound and complete tableau algorithms (Ax and As4) for ALCKm and ALCS4m are developed, with PSPACE implementations for query answering. This is a significant result, especially considering the higher complexity of general ALC with modal operators.
  • Efficient SPQA Algorithms for EL: Algorithms for computing tight envelopes in EL are presented, with experimental results showing the optimized approach (TIGHT) to be significantly more efficient than the naive approach, especially for smaller TBoxes and secrecy sets.
  • General Framework for Multi-Agent SPQA: A general framework for SPQA in multi-agent settings is introduced, with an illustration using Horn KBs.
  • Theoretical Guarantees: The paper provides theoretical guarantees for the soundness and completeness of the proposed algorithms and the correctness of the secrecy envelopes.

Limitations and Future Work

  • Complexity of Minimum Envelopes: Computing a minimum secrecy envelope is shown to be NP-hard, motivating the focus on tight envelopes.
  • Finite Secrecy Sets: The current work assumes finite secrecy sets. Future work could explore relaxing this assumption to handle secrecy sets with finite descriptions expressible in a policy language.
  • More Expressive Communication Graphs: The multi-agent framework could be extended to more realistic communication graphs, potentially with restrictions on information sharing (e.g., predicates on edges) or more general graph structures.
  • Applying Framework to Other DLs: The multi-agent framework could be applied to other description logics, such as ALC.
  • Automated Secret Specification: Developing strategies for automatically specifying secrets (policy specifications) and generating secrecy sets would be a valuable extension.
  • Combining Probabilistic and Logical Approaches: The paper notes the potential for combining logical approaches with probabilistic methods for privacy-preserving query answering, especially in contexts involving statistical data.

Summary updated

Abstract

Applications of ontologies/knowledge bases (KBs) in many domains (healthcare, national security, intelligence) have become increasingly important. In this dissertation, we focus on developing techniques for answering queries posed to KBs under the open world assumption (OWA). In the first part of this dissertation, we study the problem of query answering in KBs that contain epistemic information, i.e., knowledge of different experts. We study ALCKm, which extends the description logic ALC by adding modal operators of the basic multi-modal logic Km. We develop a sound and complete tableau algorithm for answering ALCKm queries w.r.t. an ALCKm knowledge base with an acyclic TBox. We then consider answering ALCKm queries w.r.t. an ALCKm knowledge base in which the epistemic operators correspond to those of classical multi-modal logic S4m and provide a sound and complete tableau algorithm. Both algorithms can be implemented in PSpace. In the second part, we study problems that allow autonomous entities or organizations (collectively called querying agents) to be able to selectively share information. In this scenario, the KB must make sure its answers are informative but do not disclose sensitive information. Most of the work in this area has focused on access control mechanisms that prohibit access to sensitive information (secrets). However, such an approach can be too restrictive in that it prohibits the use of sensitive information in answering queries against knowledge bases even when it is possible to do so without compromising secrets. We investigate techniques for secrecy-preserving query answering (SPQA) against KBs under the OWA. We consider two scenarios of increasing difficulty: (a) a KB queried by a single agent; and (b) a KB queried by multiple agents where the secrecy policies can differ across the different agents and the agents can selectively communicate the answers that they receive from the KB with each other subject to the applicable answer sharing policies. We consider classes of KBs that are of interest from the standpoint of practical applications (e.g., description logics and Horn KBs). Given a KB and secrets that need to be protected against the querying agent(s), the SPQA problem aims at designing a secrecy-preserving reasoner that answers queries without compromising secrecy under OWA. Whenever truthfully answering a query risks compromising secrets, the reasoner is allowed to hide the answer to the query by feigning ignorance, i.e., answering the query as Unknown. Under the OWA, the querying agent is not able to infer whether an Unknown answer to a query is obtained because of the incomplete information in the KB or because secrecy protection mechanism is being applied. In each scenario, we provide a general framework for the problem. In the single-agent case, we apply the general framework to the description logic EL and provide algorithms for answering queries as informatively as possible without compromising secrecy. In the multiagent case, we extend the general framework for the single-agent case. To model the communication between querying agents, we use a communication graph, a directed acyclic graph (DAG) with self-loops, where each node represents an agent and each edge represents the possibility of information sharing in the direction of the edge. We discuss the relationship between secrecy-preserving reasoners and envelopes (used to protect secrets) and present a special case of the communication graph that helps construct tight envelopes in the sense that removing any information from them will leave some secrets vulnerable. To illustrate our general idea of constructing envelopes, Horn KBs are considered.
BibTeX
@misc{jia2012topics,
  author = {Tao Jia},
  title = {{Topics in Knowledge Bases: Epistemic Ontologies and Secrecy-preserving Reasoning}},
  year = {2012},
  doi = {10.31274/etd-180810-479},
}
Figure