Worcester Polytechnic Institute Electronic Theses and Dissertations Collection

Title page for ETD etd-041310-122145

Document Typethesis
Author NameNelson, Timothy
TitleMargrave: An Improved Analyzer for Access-Control and Configuration Policies
DepartmentComputer Science
  • Kathi Fisler, Advisor
  • Dan Dougherty, Co-Advisor
  • Craig Wills, Reader
  • Keywords
  • finite model property
  • applied logic
  • firewalls
  • access control
  • Date of Presentation/Defense2010-04-12
    Availability unrestricted


    As our society grows more dependent on digital systems, policies that regulate access to electronic resources are becoming more common. However, such policies are notoriously difficult to configure properly, even for trained professionals. An incorrectly written access-control policy can result in inconvenience, financial damage, or even physical danger. The difficulty is more pronounced when multiple types of policy interact with each other, such as in routers on a network.

    This thesis presents a policy-analysis tool called Margrave. Given a query about a set of policies, Margrave returns a complete collection of scenarios that satisfy the query. Since the query language allows multiple policies to be compared, Margrave can be used to obtain an exhaustive list of the consequences of a seemingly innocent policy change. This feature gives policy authors the benefits of formal analysis without requiring that they state any formal properties about their policies.

    Our query language is equivalent to order-sorted first-order logic (OSL). Therefore our scenario-finding approach is, in general, only complete up to a user-provided bound on scenario size. To mitigate this limitation, we identify a class of OSL that we call Order-Sorted Effectively Propositional Logic (OS-EPL). We give a linear-time algorithm for testing membership in OS-EPL. Sentences in this class have the Finite Model Property, and thus Margrave's results on such queries are complete without user intervention.

  • thesis-latest.pdf

  • Browse by Author | Browse by Department | Search all available ETDs

    [WPI] [Library] [Home] [Top]

    Questions? Email etd-questions@wpi.edu
    Maintained by webmaster@wpi.edu