Abstract
We study confidentiality enforcement in ontologies under the Controlled Query Evaluation (CQE) framework. In this framework, a security policy specifies sensitive information, and a "censor" ensures that query answers that may compromise the policy are not returned. This research focuses on censors that maximize information access while ensuring confidentiality, specifically considering Datalog and the OWL 2 profiles as ontology languages.
The Challenge of Inference-Based Leaks
In the Semantic Web and Knowledge Representation, ontologies store data alongside background knowledge or rules. This creates a unique security challenge: even if a specific fact is hidden (e.g., "Alice has Cancer"), a user might use the ontology's rules to infer that fact from other visible data.
Controlled Query Evaluation (CQE) addresses this by placing a censor between the user and the database. When a user queries the system, the censor must determine if the answer would allow the user to deduce forbidden information. The primary hurdles are achieving optimality (providing the maximum amount of safe information) and implementability (using existing database and reasoning tools).
Censorship Methods
The authors propose two distinct types of censors to manage these leaks:
- View Censors: These create an "anonymized" version of the dataset. Sensitive constants are replaced with "labeled nulls" (placeholders), and queries are answered against this modified view. This is ideal for systems that pre-calculate or materialize data.
- Obstruction Censors: Rather than altering the data, these define 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 remains in its original SQL database.
The paper characterizes a duality between these approaches, using techniques from SLD Resolution to identify exactly which proof paths lead to a policy violation.
Key Insights and Tractability
A major contribution of this work is identifying the limits of logic in privacy enforcement. For general Datalog, the authors prove it is undecidable to determine if an optimal view censor even exists. However, by restricting the logic to modern web standards like OWL 2 profiles, the problem becomes manageable.
The Anonymization Strategy
To achieve optimality, a censor may need to create multiple "anonymous copies" of a single individual. This allows the system to satisfy different harmless parts of a query while still hiding the sensitive connection between them.
Summary of Results
- OWL 2 QL: Admits a unique optimal censor that can be implemented using a view of polynomial size, making it highly practical for OBDA systems.
- Guarded/EL Ontologies: These admit an optimal view, though computation may require exponential time relative to the ontology schema.
- Linear Datalog: Optimal obstructions can be computed in polynomial time using a proof-graph approach.
- General Datalog: Proved that checking for the existence of an optimal view is undecidable.
Limitations and Future Work
The current framework operates under a "Closed World" assumption, assuming the user only knows the ontology and the answers they receive. Future work will investigate "robust" censors that remain secure even when an attacker has access to external background knowledge. Additionally, extending these optimal results to more complex, non-guarded Datalog fragments remains an open challenge.
Summary updated