Policy expressions and the bottom-up design of computing policies

A policy is a sequence of rules, where each rule consists of a predicate and a decision, and where each decision is either “accept” or “reject”. A policy P is said to accept (or reject, respectively) a request iff the decision of the first rule in P, that matches the request is “accept” (or “reject”, respectively). Examples of computing policies are firewalls, routing policies and software-defined networks in the Internet, and access control policies. In this paper, we present a generalization of policies called policy expressions. A policy expression is specified using one or more policies and the three policy operators: “not”, “and”, and “or”. We show that policy expressions can be utilized to support bottom-up methods for designing policies. We also show that each policy expression can be represented by a set of special types of policies, called slices. We present several algorithms that use the slice representation of given policy expressions to verify whether the given policy expressions satisfy logical properties such as adequacy, implication, and equivalence. Finally, we present 19 equivalence laws of policy expressions.