Rule compiler for computer network policy enforcement systems

• US 7,203,744 B1
• Filed: 10/07/2002
• Issued: 04/10/2007
• Est. Priority Date: 10/07/2002
• Status: Expired due to Fees

• Current Assignee: Tech Mahindra Limited
• Original Assignee: iPolicy Networks, Inc (Tech Mahindra Limited)
• Inventors: Biswas, Proneet, Tutliani, Puneet, Mamtani, Vijay, Gupta, Sandeep, Parekh, Pankaj
• Primary Examiner(s): Etienne, Ario
• Assistant Examiner(s): JACOBS, LASHONDA T
• Application Number:
  US10/264,889
• Time in Patent Office: 1,646 Days
• Field of Search: 709223-224, 709/229, 709/232
• US Class Current: 709/223
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0894 Policy-based network configuration management
• CPC Class Codes: H04L 41/0895 Configuration of virtualised networks or elements, e.g. virtualised network function or OpenFlow elements
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 63/0263 Rule management

Abstract

An integrated policy enforcement system for a computer network implements several policies on the network traffic. A rule compiler compiles these policies and converts them into a rule tree-graph, which is then used to provide desired behavior to the network traffic comprising data packets. The rule compiler comprises three sub-modules namely—a rule input module, a rule tree generator module and a rule output module. The rule input module receives the input for the rule compiler and prepares the input for the rule tree generator module. The rule tree generator module generates the rule tree-graph. The rule tree-graph is a data structure comprising tree data structure and graph data structure. Such a data structure combines the properties of tree data structure and graph data structure, and enhances the performance of the policy enforcement systems by striking a balance between the memory requirement for storing the data structure and the processing capabilities of the system required to process the network traffic. The Output module converts the rule tree-graph to policy files, which can be downloaded to various modules of the policy enforcement systems.

Claims

1. A method for compiling rules for an integrated policy enforcement system for a computer network, the integrated policy enforcement system comprising modules for implementing policies on network traffic, the method comprising the steps of:

a. receiving an input, the input comprising description of expressions and values of the expressions;

b. processing the input, wherein the step of processing the input comprises;

i. creating an expression value tree for the expressions used in the rules;

ii. creating an mutually exclusive set of values for an expression based on the expression value tree, wherein the mutually exclusive set of values for the expression is used for creating a modified set of rules; and

iii. assigning expression weights to the expressions in the modified set of rules, wherein the expression weights are used for defining a tree generation process;

c. generating a rule tree-graph data structure using the tree generation process, the rule tree-graph data structure comprising a tree data structure and a graph data structure, wherein the step of generating the rule tree-graph data structure comprises the steps of;

i. creating an expression value matrix based on relations between the expressions and the values of the expressions;

ii. receiving a cutoff value;

iii. defining the tree generation process based on the cutoff value and the expression weights of the expressions in the modified set of rules; and

iv. applying the tree generation process upon the expression value matrix; and

d. outputting policy files from the rule tree-graph data structure, the policy files being used by the modules for implementing policies on the network traffic.

2. The method as recited in claim 1, wherein the step of receiving the input comprises the step of receiving an expression resource file, wherein the expression resource file describes relations between the expressions and the values of the expressions.

3. The method as recited in claim 1, wherein the step of receiving the input comprises the step of receiving multiple catalogues wherein the multiple catalogues contain data to which the rules point.

4. The method as recited in claim 3, wherein the multiple catalogues are time catalog object models containing data, the data comprising information regarding time related expressions used in the rules.

5. The method as recited in claim 1, wherein the step of processing the input further comprises the steps of:

a. creating an expression value tree based on the input;

b. adding adjacencies to the expression value tree, wherein the adjacencies are relations between an expression and a value of another expression;

c. splitting OR'"'"'ed conditions in the rules to create a modified set of rules;

d. adding implicit conditions to the modified set of rules based on the expression value tree;

e. adding implicit rules to the modified set of rules;

f. extracting Internet Protocol (IP) based expressions from the modified set of rules;

g. extracting IP values of the IP based expressions from the modified set of rules;

h. creating mutually exclusive sets of IP buckets from the IP values;

i. creating an IP bucket lookup object model from the values of the IP based expressions; and

j. assigning expression weights to the expressions in the modified set of rules.

6. The method as recited in claim 1, wherein the step of creating the expression value matrix comprises the steps of:

a. creating cells in the expression value matrix, wherein the step of creating the cells comprises the steps of;

i. creating rows in the expression value matrix, wherein the rows represent the rules;

ii. creating columns in the expression value matrix, wherein the columns represent the expressions; and

iii. arranging the expressions in the columns based on expression weights assigned to the expressions; and

b. assigning values to the cells, wherein the step of assigning the values comprises the steps of;

i. assigning values of the expressions to the cells if the values of the expressions are required for satisfying the rules in corresponding rows;

ii. assigning ‘

Do Not Care (*)’

values to the cells if the values of the expressions are not predefined by the rules in the corresponding rows; and

iii. assigning ‘

Not Applicable (NA)’

values to the cells when the values of the expressions are not required for satisfying the rules in the corresponding rows.

7. The method as recited in claim 1, wherein the step of defining the tree generation process comprises the steps of:

if the number of rules in the expression value matrix is greater than the cutoff value, then

a. defining a tree algorithm, wherein the defining the tree algorithm comprises the steps of;

i. picking the expression corresponding to a first column of the expression value matrix as a node of the tree data structure;

ii. picking various values of the picked expression as path edges of the node;

iii removing the first column of the expression value matrix for each path edge;

iv. removing the rows from the expression value matrix based on the value that the path edges represent; and

v. removing the columns from the expression value matrix based on the values of cells of the expression value matrix; and

if the number of the rules in the expression value matrix is less than or equal to the cutoff value, then;

b. defining a graph algorithm, wherein the defining the graph algorithm comprises the steps of;

i. picking the expression corresponding to the first column of the expression value matrix as a node of the graph data structure;

ii. picking distinct values of the picked expression as different path edges of the node;

iii. initializing a confirmation bitmap and an elimination bitmap for path edges;

iv. removing the columns in the expression value matrix based on the confirmation bitmap and the elimination bitmap;

v. removing the first column from the expression value matrix to create a reduced expression value matrix; and

vi. recursively using the graph algorithm on the reduced expression value matrix when the number of rules in the reduced expression value matrix is less than or equal to the cutoff value.

8. A method for compiling rules for an integrated policy enforcement system for a computer network, the integrated policy enforcement system comprising modules for implementing policies on network traffic, the method comprising the steps of:

a. receiving an input, the input comprising rules and related information;

b. processing the input to generate an output, wherein the step of processing the input comprises the steps of;

i. creating an expression relationship structure from the input, wherein the input is obtained from an expression resource file;

ii. adding adjacencies to the expression relationship structure;

iii. splitting OR'"'"'ed conditions in the rules to generate a first set of modified set of rules;

iv. adding implicit expressions to the first set of modified rules to generate a second set of modified rules;

v. adding implicit rules to the second set of modified rules to generate a third set of modified rules;

vi. extracting IP based expressions and their values from the third set of modified rules;

vii. creating mutually exclusive sets of IP buckets from the values of the IP based expressions in the third set of modified rules;

viii. modifying the third set of modified rules according to the mutually exclusive sets of IP buckets to create a final set of rules; and

ix. assigning expression weights to different expressions by using the final set of rules and a weight criteria;

c. generating a data structure using the output of the processing step; and

d. outputting policy files from the data structure.

9. A method for compiling rules for an integrated policy enforcement system for a computer network, the integrated policy enforcement system comprising modules for implementing policies on network traffic, the method comprising the steps of:

a. receiving an input, the input comprising the rules and related information;

b. processing the input to generate an output;

c. generating a data structure using the output of the processing step, wherein the step of generating the data structure further comprises the steps of;

i. creating an expression value matrix, wherein the step of creating the expression value matrix further comprises creating the expression value matrix by processing expression weights, an expression relationship structure with added adjacencies and a final set of rules, the expression value matrix consisting of cells, the rows of the expression value matrix corresponding to the final set of rules, the columns of the expression value matrix denoting the expressions in decreasing order of the expression weights, the cell being assigned a specific value if an expression corresponding to the column must possess that value for the corresponding rule represented by the row, the cell being assigned “

Do Not Care (*)”

if the value of the expression does not make a difference to the satisfaction of the corresponding rule, the cell being assigned “

Not Applicable (NA)”

if the value of an expression does not have significance for evaluation of the corresponding rule;

ii. defining a tree graph procedure; and

iii. applying the tree graph procedure upon the first column of the expression value matrix; and

d. outputting policy files from the data structure.

10. A system for compiling rules for an integrated policy enforcement system for computer networks, the integrated policy enforcement system comprising modules for implementing policies on network traffic, the system for compiling the rules receives a cutoff value, expression data, rules and a weight criteria, the expression data comprising definitions of a plurality of expressions, an expression denoting a property of the network traffic, the rule comprising an action associated with conditions, a condition comprising the plurality of expressions and their corresponding values, the system for compiling rules comprising:

a. a rule input module for processing an input and generating an output, wherein the rule input module further comprises;

i. means for creating an expression relationship structure from the expression data;

ii. means for adding adjacencies to the expression relationship structure;

iii. means for splitting OR'"'"'ed conditions in the rules to generate a first set of modified rules;

iv. means for adding implicit expressions to the first set of modified rules to generate a second set modified rules;

v. means for adding implicit rules to the second set of modified rules to generate a third set of modified rules;

vi. means for extracting IP based expressions and their values from the third set of modified rules;

vii. means for creating mutually exclusive sets of IP buckets and an IP lookup object model from the values of the IP based expressions in the third set of modified rules;

viii. means for modifying the third set of modified rules according to the mutually exclusive sets of IP buckets to create a final set of rules; and

ix. means for assigning expression weights to different expressions by using the final set of rules and the weight criteria;

b. a rule tree generator module that generates a rule tree-graph structure from the output generated by the rule input module; and

c. an output module for outputting policy files from the rule tree-graph structure and object models.

11. The system as recited in claim 10, wherein the rule tree generator module comprises:

a. means for creating an expression value matrix based on relations between the expressions and the values of the expressions, wherein the means for creating an expression value matrix comprises;

i. means for processing expression weights;

ii. means for identifying adjacencies between the expressions and the values of the expressions, wherein the adjacencies are relations between an expression and a value of another expression; and

iii. means for identifying non-adjacencies between the expressions and the values of the expressions;

b. means for receiving a cutoff value;

c. means for defining a tree generation process based on the cutoff value and the expression weights of the expressions in the modified set of rules; and

d. means for generating the rule tree-graph data structure by applying the tree generation process on the expression value matrix.