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. We also give a brief overview of a prototype that we have built whose reasoning engine is based on the logic and whose interface is designed for non-logicians, allowing them to enter both policies and background information, such as Alice is a student, and to ask questions about the policies.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 2008
Accession Number
AD1021077

Entities

People

  • Joseph Halpern
  • Vicky Weissman

Organizations

  • Cornell University

Tags

DTIC Thesaurus Topics

  • Consistency
  • Databases
  • Environment
  • Language
  • Malleability
  • Markup Languages
  • Natural Languages
  • New York
  • Standards
  • Students
  • Two Dimensional
  • Universities
  • Vocabulary

Fields of Study

  • Computer science

Readers

  • Artificial Intelligence
  • Computational Linguistics
  • East Asian Political and Security Studies within the Soviet Union