Fast Compliance Checking in an OWL2 Fragment

Piero A. BonattiIJCAI 2018 · DOI

TL;DR

This paper introduces a specialized fragment of OWL2, called Policy Logic (PL), designed for formalizing data usage policies and checking compliance with regulations like GDPR. They present a novel, tractable structural subsumption algorithm that enables efficient policy comparison, a crucial task for ensuring data privacy and adherence to consent.

What Problem Does This Paper Address?

In today's data-driven world, organizations collect and process vast amounts of personal data. Ensuring compliance with privacy regulations like the GDPR, which mandates explicit consent for data usage, is a significant challenge. This involves comparing a company's data usage policies against individual data subject consents and the legal requirements themselves. Manually verifying these policies is error-prone and doesn't scale, especially with millions of data subjects and complex usage scenarios. The authors aim to provide a formal, automated, and efficient method for this compliance checking.

Methods

The core of the paper is the introduction of Policy Logic (PL), a fragment of OWL2-DL tailored for data usage policies. PL allows for the formal representation of:

  • Data usage policies: Including purpose, data categories, processing types, recipients, storage locations, and duration.
  • Data subject consent: Formalizing what users agree to.
  • GDPR requirements: Capturing key obligations like consent and data transfer rules.

The key reasoning task is compliance checking, which is reduced to subsumption checking (i.e., checking if policy A is more general than or equivalent to policy B). To address the scalability issue, the authors developed a structural subsumption algorithm (STS). This algorithm is designed to be efficient for the specific PL fragment, avoiding the general intractability of Description Logics. They also introduce a method for policy validation by checking concept satisfiability.

Datasets

Not discussed in the paper. The paper focuses on formalizing policies and developing reasoning algorithms rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Bridging the gap between formal logic and real-world policies: The paper demonstrates how a well-defined fragment of OWL2 can effectively model complex data usage policies and consent, making them amenable to automated reasoning.
  • Subsumption as the key to compliance: Reducing compliance checking to subsumption queries simplifies the problem and allows for leveraging existing DL reasoning techniques, albeit specialized ones.
  • Tractability through specialization: By restricting the expressivity of OWL2 (e.g., limiting concrete features), the authors achieve polynomial-time complexity for subsumption checking, which is crucial for practical applications.
  • The importance of concrete domains: The paper highlights the role of concrete domains (like numerical intervals for duration) and how their handling is critical for both expressivity and tractability.
  • Intractability of generalization: While their PL fragment is tractable, the authors show that even a slight generalization (adding unrestricted concrete features) leads to coNP-complete complexity, underscoring the importance of their carefully chosen fragment.

Key Results

  • Formalization of policies: The paper provides a clear method for encoding data usage policies, consent, and GDPR aspects into a DL framework.
  • Efficient subsumption algorithm: The proposed structural subsumption algorithm (STS) is proven to be correct and complete for the PL fragment.
  • Polynomial-time compliance checking: For interval-safe PL subsumption queries, compliance checking can be answered in polynomial time with respect to the size of the ontology and policies.
  • coNP-completeness of general PL: Subsumption checking in PL with unrestricted concrete features is coNP-complete, highlighting the trade-off between expressivity and tractability.

Limitations and Future Work

  • Limited expressivity of PL: The PL fragment, while tractable, has limitations. For instance, it restricts the use of concrete features to avoid intractability. The authors acknowledge that real-world vocabularies might require more expressive DLs like OWL2-EL.
  • Scalability for real-time scenarios: Checking storage consent for high-throughput data streams (hundreds of thousands per minute) is identified as a challenge requiring further optimization, potentially through knowledge compilation techniques.
  • Integration with existing tools: The authors plan to integrate their STS algorithm with ELK, a specialized reasoner for OWL2-EL, to leverage richer vocabularies.
  • Experimental validation: Future work includes implementing and optimizing the STS algorithm and conducting scalability tests, especially for parallelization of compliance checks across multiple data subject consents.

Summary updated

BibTeX
@inproceedings{bonatti2018fast,
  author = {Piero A. Bonatti},
  title = {{Fast Compliance Checking in an OWL2 Fragment}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/241},
}
Figure