Distributed Autoepistemic Logic and its Application to Access Control

Pieter Van Hertum, Marcos Cramer, Bart Bogaerts, Marc DeneckerIJCAI 2016

Abstract

Modern access control systems increasingly rely on distributed architectures where multiple authorities, or principals, issue statements regarding permissions and delegations. Traditional logical frameworks often struggle to model these systems accurately, particularly when dealing with negative introspection—reasoning about what a principal has not said—and recursive delegation. This paper introduces Distributed Autoepistemic Logic (dAEL), a multi-agent extension of classical autoepistemic logic. By leveraging Approximation Fixpoint Theory (AFT) and inductive definitions, dAEL provides a robust algebraic foundation for complex security policies, including revocation and delegation chains. We demonstrate that the well-founded semantics within dAEL offers a superior approach to conflict resolution in security contexts compared to traditional stable semantics.

1. Introduction

Access control is the fundamental security process of determining whether a principal (an agent or authority) has the right to perform a specific action on a resource. In distributed environments, this process is decentralized: Alice might grant access to Bob, while a central authority might revoke that access under specific conditions.

Existing logics for access control face two primary hurdles. First, they often lack a formal mechanism for negative introspection, which is essential for revocation (e.g., "Alice has access unless her credentials have been revoked"). Second, they struggle with recursive rules, such as delegation chains where rights are passed through multiple intermediaries. While standard Autoepistemic Logic (AEL) excels at reasoning about an agent's own knowledge and lack thereof, it was originally designed for a single-agent perspective. This research bridges that gap by formalizing dAEL, a multi-agent logic tailored for distributed security policies.

2. The dAEL Framework

The authors construct dAEL by integrating several sophisticated logical and algebraic tools into a unified framework:

  • Multi-Agent Syntax: The standard knowledge operator ($K$) is replaced with an indexed version ($K_A$), enabling agent $B$ to reason formally about the knowledge or silence of agent $A$.
  • Approximation Fixpoint Theory (AFT): Rather than prescribing a single interpretation, the authors utilize AFT—a high-level algebraic framework. This allows dAEL to automatically generate a family of semantics (such as stable or well-founded models) from a single underlying logic.
  • Inductive Definitions (dAEL(ID)): The logic is extended to support recursive definitions. This is critical for representing "chains of trust," where access rights are derived through a sequence of delegations.
  • Three-Valued Logic: To manage uncertainty and policy conflicts, the logic employs three truth values: true, false, and unknown.

3. Key Insights: The "All I Know" Assumption

A central contribution of this work is the application of the "All I Know" principle to access control. In this context, a principal's issued statements are treated as a complete characterization of their position. If a revocation statement is absent from a principal's set of assertions, the logic treats that revocation as non-existent. dAEL captures this negative introspection precisely, allowing for more intuitive policy modeling.

Furthermore, the research highlights the superiority of well-founded semantics for security applications. In scenarios involving circular or conflicting revocations (e.g., two agents mutually revoking each other's authority), stable semantics might produce multiple contradictory "worlds" or fail to find a solution. In contrast, well-founded semantics assigns the value "unknown" to the conflict. This "cautious" approach ensures that the system remains stable and predictable, which is a prerequisite for secure access control.

4. Formalization and Results

The paper successfully establishes the syntax and semantics for dAEL and demonstrates its utility through several key results:

  1. Lifting AEL to dAEL: The authors prove that standard semantic operators of single-agent AEL can be "lifted" to a distributed setting using bilattice structures.
  2. Modeling SGN Revocation: The framework concisely models Strong Global Negative (SGN) revocation. This is a complex security scheme where a single negative authorization can override positive ones and propagate through an entire delegation chain.
  3. Conflict Resolution: dAEL provides a formal mathematical method to identify and handle policy conflicts that typically break simpler logic systems.

5. Conclusion and Future Work

Distributed Autoepistemic Logic provides a powerful new foundation for reasoning about decentralized security. By combining the expressive power of AEL with the flexibility of AFT, the authors have created a tool capable of handling the most challenging aspects of modern access control.

Future research will focus on two areas: computational complexity and practical integration. While dAEL is highly expressive, determining the computational cost of calculating access rights in large-scale systems is essential for real-world deployment. Additionally, mapping dAEL(ID) onto existing industry standards like XACML (eXtensible Access Control Markup Language) will be a critical step in transitioning this theoretical framework into practical software architectures.

Summary updated

BibTeX
@inproceedings{hertum2016distributed,
  author = {Pieter Van Hertum and Marcos Cramer and Bart Bogaerts and Marc Denecker},
  title = {{Distributed Autoepistemic Logic and its Application to Access Control}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure