Controlled Query Evaluation for Datalog and OWL 2 Profile Ontologies

Bernardo Cuenca Grau, Evgeny Kharlamov, Egor V. Kostylev, Dmitriy Zheleznyakov

TL;DR

This paper explores how to keep sensitive information private in knowledge bases (ontologies) without being overly restrictive. The authors introduce "view" and "obstruction" censors to filter query results and prove that while finding an optimal balance is impossible for general Datalog, it is computationally feasible for the lightweight OWL 2 profiles used in modern web standards.

What Problem Does This Paper Address?

In the world of Semantic Web and Knowledge Representation, ontologies provide a way to store data alongside "background knowledge" (rules). This creates a unique security challenge: even if you hide a specific fact (e.g., "Alice has Cancer"), a clever user might use the ontology's rules to infer that fact from other visible data.

Controlled Query Evaluation (CQE) is a framework designed to solve this. A "censor" sits between the user and the database. When a user asks a query, the censor checks if the answer would allow the user to deduce something forbidden by a security policy. If it does, the censor must distort or block the answer.

The authors tackle two main hurdles:

  1. Optimality: How do we ensure the censor isn't "too safe"? We want to provide as much information as possible without violating the policy.
  2. Implementability: Can we build these censors using existing, "off-the-shelf" database and reasoning tools?

Methods

The authors propose two distinct types of censors:

  • View Censors: These work by creating an "anonymized" version of the dataset (a view). Some constants are replaced with "labeled nulls" (placeholders). The system then answers queries against this modified view. This is ideal for systems that pre-calculate (materialize) data.
  • Obstruction Censors: Instead of changing the data, these define a set of "forbidden query patterns." If a query answer matches a forbidden pattern, it is blocked. This is better suited for "Virtual Data Access" (OBDA), where data stays in its original SQL database.

The paper provides a formal characterization of the duality between these two approaches. They use techniques from SLD Resolution (a logic programming proof method) to identify exactly which "proof paths" lead to a policy violation and must be blocked.

Datasets

As a theoretical research paper, it does not evaluate against standard empirical benchmarks (like LUBM or WatDiv). Instead, it uses illustrative examples involving social network ontologies (e.g., relationships like FrOf and interests like ThrillerFan) to demonstrate how policies can be bypassed and how censors fix the leak.

Key Insights and Ideas

  • The Duality Gap: Surprisingly, view and obstruction censors are not equivalent. The authors prove that there are some security policies that can be perfectly enforced by a view but not by an obstruction, and vice versa.
  • The Limits of Logic: The authors show that for general Datalog (a powerful rule language), it is undecidable to even determine if an optimal view censor exists. This means there is no "perfect" general-purpose algorithm for data privacy in complex rule-based systems.
  • Tractability in OWL 2: The "aha moment" is that by restricting the logic to specific "profiles" (OWL 2 QL, EL, and RL), the problem becomes manageable. They show that for OWL 2 QL—the standard for linking databases to ontologies—an optimal censor always exists and can be computed efficiently.
  • Anonymization Strategy: To achieve optimality, a censor might need to create multiple "anonymous copies" of a single person or object to satisfy different "harmless" parts of a query while still hiding the sensitive connection.

Key Results

  • OWL 2 QL: Admits a unique optimal censor that can be implemented using a view of polynomial size. This is a big win for practical implementation in OBDA systems.
  • Guarded/EL Ontologies: These admit an optimal view, though it may require exponential time to compute relative to the size of the ontology schema (but polynomial relative to the data size).
  • Linear Datalog: The authors provide a polynomial-time algorithm to compute optimal obstructions using a "proof graph" approach.
  • General Datalog: Proved that checking for the existence of an optimal view is undecidable, drawing a hard line for what is possible in automated privacy enforcement.

Limitations and Future Work

The primary limitation acknowledged is the "Closed World" assumption regarding the user's knowledge. The current framework assumes the user only knows the ontology and the answers they receive. In reality, an attacker might have external background knowledge (e.g., from a different public database).

The authors suggest that future work should investigate "robust" censors that remain secure even when the user has access to outside information. Additionally, while they solved the problem for "tree-shaped" and "linear" rules, extending these optimal results to more complex, non-guarded Datalog fragments remains an open challenge.

Summary updated

Abstract

We study confidentiality enforcement in ontologies under the Controlled Query Evaluation framework, where a policy specifies the sensitive information and a censor ensures that query answers that may compromise the policy are not returned. We focus on censors that ensure confidentiality while maximising information access, and consider both Datalog and the OWL 2 profiles as ontology languages.
BibTeX
@inproceedings{grau2015controlled,
  author = {Bernardo Cuenca Grau and Evgeny Kharlamov and Egor V. Kostylev and Dmitriy Zheleznyakov},
  title = {{Controlled Query Evaluation for Datalog and OWL 2 Profile Ontologies}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=rJVzbVM_-r},
}

Loading related content...

Figure