Using First-Order Logic to Reason about Policies
Abstract
A policy describes the conditions under which an action is permitted or forbidden. We show that a fragment of (multi-sorted) first-order logic can be used to represent and reason about policies. Because we use first-order logic, policies have a clear syntax and semantics. We show that further restricting the fragment results in a language that is still quite expressive yet is also tractable. More precisely, questions about entailment, such as “May Alice access the file?”, can be answered in time that is a low-order polynomial (indeed, almost linear in some cases), as can questions about the consistency of policy sets.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jul 01, 2008
- Source ID
- 10.1145/1380564.1380569
Entities
People
- Joseph Halpern
- Vicky Weissman
Organizations
- Air Force Office of Scientific Research
- Cornell University
- National Science Foundation
- Office of Naval Research