Subject: Decorrelation

From: Matthew Condell <[email-masked]>
Date: 26 Apr 2001 12:05:15 -0000

Here's text from previous drafts describing the need for decorrelation
and an algorithm for decorrelating a set of ordered policies.

Matt

------------------------------------

Decorrelation

It is not possible for a Policy Server to use policies as they are
written in the SPS master file, since those policies are likely to be
correlated.  Two policies are correlated if there is a non-nil
intersection between the values of each of their selectors.  Caching
correlated policies can lead to incorrect policy implementation based
on those cached policies, as the following example shows.

           H1 --- SG1 --------- SG2 --- H2
                   |             |  \__ H3
                   |             |
                  PS1           PS2

PS2 contains the following policies in its master file:
        src   dst     proto    direction   action
   1)    *    H2        *       inbound    permit
   2)    *    *         *       inbound     deny

These two policies are correlated since all the selectors (src, dst,
proto, and direction) overlap.  The following SPP exchanges occur:

  1)  PS1 requests policy for H3.
  2)  PS2 returns policy #2 to PS1 which then caches policy #2.
  3)  PS1 now looks up the policy for H2 and discovers that it already
      has a matching policy (policy #2) and uses that.

This is clearly wrong, since policy #2 indicates that the
communication to H2 should be denied, though PS2's policy actually
indicates that it should be allowed.

The solution is to remove the ambiguities that may exist in
the master file.  The policies of the master file MUST be decorrelated
before they are entered into the Local Policy Database.  That is, the
policies must be rewritten so that for every pair of policies there
exists a selector for which there is a nil intersection between the
values in both of the policies.

The policies in the above example could be decorrelated as follows:
        src   dst     proto    direction   action
   1')   *    H2        *       inbound    permit
   2')   *   not H2     *       inbound     deny

Now the exchange is a bit different:
   1)  PS1 requests policy for H3.
   2)  PS2 returns policy #2' to PS1 which then caches policy #2'.
   3)  PS1 now looks up the policy for H2, doesn't have a matching 
       policy, so it requests a policy for H2.
   4)  PS2 returns policy #1' to PS1 which then caches policy #1', 
       which is the correct policy for H2.

All SPAs and SPRs, therefore, MUST decorrelate their master
files before using those policies for SPP.  Once the policies are
decorrelated, there is no longer any ordering requirement on the
policies, since only one policy will match any requested
communication.  The next section describes decorrelation in more
detail and presents an algorithm that may be used to implement
decorrelation.

C.1 Decorrelation Algorithm

The basic decorrelation algorithm takes each policy in a correlated
set of policies and divides it up into a set of policies using a tree
structure.  Those of the resulting policies that are decorrelated with
the decorrelated set of policies are then added to that decorrelated
set.

The basic algorithm does not guarantee an optimal set of decorrelated
policies.  That is, the policies may be broken up into smaller sets
than is necessary, though they will still provide all the necessary
policy information.  Some extensions to the basic algorithm are
described later to improve this and improve the performance of the
algorithm.

        C  A set of ordered, correlated policies
        Ci The ith policy in C.
        U  The set of decorrelated policies being built from C
        Ui The ith policy in U.

A policy P may be expressed as a mapping of selector values to
actions:
        Pi = Si1 x Si2 x ... x Sik -> Ai

1) Put C1 in set U as U1

For each policy Cj (j > 1) in C

2) If Cj is decorrelated with every policy in U, then add it to U.

3) If Cj is correlated with one or more policies in U, create a tree
rooted at the policy Cj that partitions Cj into a set of decorrelated
policies.  The algorithm starts with a root node where no selectors
have yet been chosen.

  A) Choose a selector in Cj, Scjn, that has not yet been chosen when
     traversing the tree from the root to this node.  If there are no
     selectors not yet used, continue to the next unfinished branch
     until all branches have been completed.  When the tree is 
     completed, go to step D.

     T is the set of policies in U that are correlated with the policy
     to this node.

     The policy at this node is the policy formed by the selector
     values of each of the branches between the root and this node.
     Any selector values that are not yet represented by branches
     assume the corresponding selector value in Cj, since the values
     in Cj represent the maximum value for each selector.

  B) Add a branch to the tree for each value of the selector Scjn that
     appears in any of the policies in T.  (If the value is a superset
     of the value of Scjn in Cj, then use the value in Cj, since that
     value represents the universal set.)  Also add a branch for the
     compliment of the union of all the values of the selector Scjn
     in T.  When taking the compliment, remember that the universal
     set is the value of Scjn in Cj.  A branch need not be created
     for the nil set.

  C) Repeat A and B until the tree is completed.

  D) The policy to each leaf now represents a policy that is a subset
     of Cj.  The policies at the leaves completely partition Cj in
     such a way that each policy is either completely overridden by
     a policy in U, or is decorrelated with the policies in U.

     Add all the decorrelated policies at the leaves of the tree to U.

5) Get next Cj and goto 2.

6) When all policies in C have been processed, then U will contain an
decorrelated version of C.

There are several optimizations that can be made to this algorithm.
A few of them are presented here.

It is possible to optimize, or at least improve, the amount of
branching that occurs by carefully choosing the order of the selectors
used for the next branch.  For example, if a selector Scjn can be
chosen so that all the values for that selector in T are equal to or a
superset of the value of Scjn in Cj, then only a single branch need to
be created (since the compliment will be nil).

Branches of the tree do not have to proceed with the entire
decorrelation algorithm.  For example, if a node represents a policy
that is decorrelated with all the policies in U, then there is no
reason to continue decorrelating that branch.  Also, if a branch is
completely overridden by a policy in U, then there is no reason to
continue decorrelating the branch.

An additional optimization is to check to see if a branch is
overridden by one of the CORRELATED policies in set C that has already
been decorrelated.  That is, if the branch is part of decorrelating
Cj, then check to see if it was overridden by a policy Cm, m < j.
This is a valid check, since all the policies Cm are already expressed
in U.

Along with checking if a policy is already decorrelated in step 2,
check if Cj is overridden by any policy in U. If it is, skip it since
it is not relevant.  A policy x is overridden by another policy y if
every selector in x is equal to or a subset of the corresponding
selector in policy y. Appendix A shows an example of applying the
algorithm to a set of correlated policies.

C.2 Decorrelation Example

This appendix section demonstrates the decorrelation algorithm and the
optimizations presented on a sample set of policies.  We start with
the following set of correlated policies, set C:

    src        dst           prot   sport  dport     user    sec level
C1  199.93/16  199.100.2/24  TCP      *      22    lsanchez    sec    
C2  199.93/16  199.100.2/24  TCP      *      *     lsanchez    conf   
C3  199.93/16  199.100.2/24  UDP      *      *     lsanchez     *     
C4  199.93/16  199.100.2/24  UDP      *      52       *         *     
C5  199.93/16  199.100.2/24   *       *      *        *         *     
C6     *             *        *       *      *        *         *     

C.2.1 policy C1

We start with policy C1:

     src        dst           prot   sport  dport     user    sec level
C1:  199.93/16  199.100.2/24  TCP      *      22    lsanchez    sec   

By step 1 of the algorithm, C1 is put directly into set U as policy
U1.

The current decorrelated policy set U is:
U1  199.93/16  199.100.2/24  TCP      *      22    lsanchez    sec    

C.2.2 policy C2

Next, we look at policy C2:

     src        dst           prot   sport  dport     user    sec level
C2:  199.93/16  199.100.2/24  TCP      *      *     lsanchez    conf  

C2 is decorrelated with the policies already in U (U1) because the
security levels do not overlap.  By step 2, C2 is added to U as U2.

The current decorrelated policy set U is:
U1  199.93/16  199.100.2/24  TCP      *      22    lsanchez    sec    
U2  199.93/16  199.100.2/24  TCP      *      *     lsanchez    conf   

C.2.3 policy C3

Next, we look at policy C3:

     src        dst           prot   sport  dport     user    sec level
C3:  199.93/16  199.100.2/24  UDP      *      *     lsanchez     *    

C3 is decorrelated with the policies already in U (U1 and U2) because
it uses UDP while both policies in U use TCP.  By step 2, C3 is added
to U as U3.

The current decorrelated policy set U is:
U1  199.93/16  199.100.2/24  TCP      *      22    lsanchez    sec    
U2  199.93/16  199.100.2/24  TCP      *      *     lsanchez    conf   
U3  199.93/16  199.100.2/24  UDP      *      *     lsanchez     *     

C.2.4 policy C4

Next, we look at policy C4:

     src        dst           prot   sport  dport     user    sec level
C4:  199.93/16  199.100.2/24  UDP      *      52       *         *    

       T = {U3}            o
                          / \
              ~lsanchez  /   \ (user) lsanchez

Policy C4 is correlated with policy U3 in U, so T = {U3}.  First we
choose to decorrelate the user selector.  The policy in T as the value
"lsanchez" for this selector, so we create a branch for "lsanchez" and
its compliment.  

The lsanchez branch:
199.93/16  199.100.2/24  UDP      *      52    lsanchez     *        
is overriden by the policy U3.

The compliment branch:
199.93/16  199.100.2/24  UDP      *      52    ~lsanchez    *         
is decorrelated with T since ~lsanchez does not overlap any policies 
in T.  Since this branch is decorrelated, it is added to set U.

The current decorrelated policy set U is:
U1  199.93/16  199.100.2/24  TCP      *      22    lsanchez    sec    
U2  199.93/16  199.100.2/24  TCP      *      *     lsanchez    conf   
U3  199.93/16  199.100.2/24  UDP      *      *     lsanchez     *     
U4  199.93/16  199.100.2/24  UDP      *      52    ~lsanchez    *     

C.2.5 policy C5

Next, we look at policy C5:

     src        dst           prot   sport  dport     user    sec level
C5:  199.93/16  199.100.2/24   *       *      *        *         *    

       T = U              o
                  _______/|\_______
       ~UDP,~TCP /        |        \ (prot) UDP
                          |         o  T=U3,U4
                          | TCP     |\_________
                          |         |          \
                          |         | lsanchez  | (user) ~lsanchez
                  T=U1,U2 o                     o  T = U4
                         / \   (user)          / \
       ~lsanchez        /   \ lsanchez    ~52 /   \  (dport) 52
                             |
                     T=U1,U2 o
                   _________/|\_________
      ~sec,~conf  /          |          \  (sec label) conf
                             | sec
                             |
                      T = U1 o
                            / \
                       ~22 /   \  (dport) 22

Policy C5 is correlated with all the policies currently in U, so 
T = U. First we choose to decorrelate the protocol selector. The 
policies in $T$ have the values ``UDP'' and ``TCP'' for this selector,
so we create a branch for each of them and a branch for the complement
of their union.

We can stop processing the complement branch:
199.93/16  199.100.2/24 ~UDP,~TCP *      *        *         *       
since it is decorrelated with T.  This policy will be added to 
the decorrelated set.

The "UDP" and "TCP" branches still require more processing since they
are both still correlated with policies in U.  We will start by
processing the "UDP" branch.  The policy through this branch is
correlated with policies U3 and U4, so T = {U3, U4}.  We choose to
decorrelate on the user selector.  The policies in T have "lsanchez"
and "~lsanchez" as their values for this selector so we create
branches for "lsanchez" and "~lsanchez."  The compliment branch is
redundant to these branches.

We can stop processing the "lsanchez" branch:
199.93/16  199.100.2/24  UDP      *      *     lsanchez     *       
since it is overridden by policy U3.

The "~lsanchez" branch, however, requires more processing since it is
correlated with policy U4 (T = {U4}).  We choose to decorrelate on the
dport selector.  The policy in T has "52" as its value for this
selector so we create a "52" branch and a branch for its compliment
"~52".

We can stop processing the complement branch:
199.93/16  199.100.2/24  UDP      *      ~52   ~lsanchez    *       
since it is decorrelated with T.  This policy will be added to 
the decorrelated set.

We can also stop processing the "52" branch:
199.93/16  199.100.2/24  UDP      *       52   ~lsanchez    *       
since it is overridden by U4.

Now we need to go back and process the "TCP" branch.  The policy
through this branch is correlated with policies U1 and U2, so T = {U1,
U2}.  We choose to decorrelate on the user selector.  The policies in
T have "lsanchez" as their values for this selector so we create
branches for "lsanchez" and its compliment, "~lsanchez."

We can stop processing the complement branch:
199.93/16  199.100.2/24  TCP      *      *     ~lsanchez    *       
since it is decorrelated with T.  This policy will be added to 
the decorrelated set.

The "~lsanchez" branch, however, requires more processing since it is
correlated with both policies in T.  We choose to decorrelate on the
sec label selector.  The policies in T have "sec" and "conf" as their
values for this selector so we create branches "sec", "conf", and the
complement of their union, "~sec,~conf"

We can stop processing the complement branch:
199.93/16  199.100.2/24  TCP      *      *     lsanchez   ~sec,~conf
since it is decorrelated with T.  This policy will be added to 
the decorrelated set.

We can stop processing the "conf" branch:
199.93/16  199.100.2/24  TCP      *      *     lsanchez    conf     
since it is overridden by policy U2.

The "sec" branch, however, requires more processing since it is
correlated with policy U1 (T = U1).  We choose to decorrelate on the
dport selector.  The policy in T has "22" as its value for this
selector so we create a "22" branch and a "~22" branch for its
compliment.

We can stop processing the complement branch:
199.93/16  199.100.2/24  TCP      *      ~22   lsanchez    sec      
since it is decorrelated with T.  This policy will be added to 
the decorrelated set.

We can stop processing the "22" branch:
199.93/16  199.100.2/24  TCP      *      22    lsanchez    sec      
since it is overridden by policy U1.

The decorrelated policy set after decorrelating C5 is:
U1  199.93/16  199.100.2/24  TCP      *      22    lsanchez    sec    
U2  199.93/16  199.100.2/24  TCP      *      *     lsanchez    conf   
U3  199.93/16  199.100.2/24  UDP      *      *     lsanchez     *     
U4  199.93/16  199.100.2/24  UDP      *      52    ~lsanchez    *     

U5  199.93/16  199.100.2/24 ~UDP,~TCP *      *        *         *     
U6  199.93/16  199.100.2/24  UDP      *      ~52   ~lsanchez    *     
U7  199.93/16  199.100.2/24  TCP      *      *     ~lsanchez    *      
U8  199.93/16  199.100.2/24  TCP      *      *     lsanchez  ~sec,~conf
U9  199.93/16  199.100.2/24  TCP      *      ~22   lsanchez    sec    

C.2.6 policy C6

Finally, we look at policy C6:

     src        dst           prot   sport  dport     user    sec level
C6:     *             *        *       *      *        *         *     

       T = U              o
                         /|
           ~199.93/16   / | (src) 199.93/16
       T = U              o
                         /|
        ~199.100.2/24   / | (dst) 199.100.2/24

Policy C6 is correlated with all the policies currently in U, so 
T = U. First we choose to decorrelate the src selector. The 
policies in $T$ have the value "199.93/16" for this selector, 
so we create a branch for "199.93/16" and one for its compliment,
"~199.93/16".

We can stop processing the complement branch:
~199.93/16       *        *       *      *        *         *         
since it is decorrelated with all the policies in T.  This policy will
be added to the decorrelated set.

The "199.93/16" branch, however, requires more processing since it is
correlated with all the policies in T.  We choose to decorrelate on the
dst selector.  The policies in T have "199.100.2/24" as their value
for this selector so we create a "199.100.2/24" branch and a
"~199.100.2/24" branch for its compliment.

We can stop processing the complement branch:
199.93/16  ~199.100.2/24  *       *      *        *         *         
since it is decorrelated with all the policies in T.  This policy will
be added to the decorrelated set.

We can stop processing the "199.100.2/24" branch:
199.93/16  199.100.2/24   *       *      *        *         *         
since it is overridden by policy C5.

The full decorrelated version of C is:
U1  199.93/16  199.100.2/24  TCP      *      22    lsanchez    sec     
U2  199.93/16  199.100.2/24  TCP      *      *     lsanchez    conf    
U3  199.93/16  199.100.2/24  UDP      *      *     lsanchez     *      
U4  199.93/16  199.100.2/24  UDP      *      52    ~lsanchez    *      

U5  199.93/16  199.100.2/24 ~UDP,~TCP *      *        *         *      
U6  199.93/16  199.100.2/24  UDP      *      ~52   ~lsanchez    *      
U7  199.93/16  199.100.2/24  TCP      *      *     ~lsanchez    *      
U8  199.93/16  199.100.2/24  TCP      *      *     lsanchez  ~sec,~conf
U9  199.93/16  199.100.2/24  TCP      *      ~22   lsanchez    sec     

U10 199.93/16  ~199.100.2/24  *       *      *        *         *     
U11 ~199.93/16       *        *       *      *        *         *