ANALYSIS OF DISTRIBUTED POLICY RULE-SETS FOR COMPLIANCE WITH GLOBAL POLICY

• US 20080301765A1
• Filed: 05/28/2008
• Published: 12/04/2008
• Est. Priority Date: 05/31/2007
• Status: Active Grant

• Current Assignee: Board of Trustees of The University of Illinois
• Original Assignee: Board of Trustees of The University of Illinois
• Inventors: Nicol, David M., Singh, Sankalp, Seri, Mouna, Sanders, William H.
• Granted Patent: US 8,209,738 B2
• Time in Patent Office: Days
• US Class Current: 726/1
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04L 63/20 for managing network security; network security policies in general filtering policies H04L63/0227
• CPC Class Codes: Y04S 40/00 Systems for electrical power generation, transmission, distribution or end-user application management characterised by the use of communication or information technologies, or communication or information technology specific aspects supporting them

Abstract

A method for analysis of distributed device rule-sets for compliance with global policies includes enabling an administrator to specify a network topology with intercommunicating elements and parameters required to secure the intercommunication with access control elements of the network topology; establishing connections to the access controls elements to capture a snapshot configuration of device rule-sets of the access control elements; enabling the administrator to specify a set of global access constraints with reference to the access control elements; enabling the administrator to select between exhaustive analysis and statistical analysis; conducting the selected analysis to determine violations by the device rule-sets that fail to comply with the set of global access constraints, wherein statistical analysis quantitatively characterizes a level of compliance without conducting analysis of all potential network paths; and providing results of the selected analysis to the administrator through a graphical user interface (GUI) as the results are obtained.

Claims

1. A method for analysis of distributed device rule-sets for compliance with global policies, the method comprising:

enabling an administrator to specify a network topology with a plurality of intercommunicating elements and associated parameters required to secure the intercommunication with one or more access control elements of the network topology;

establishing connections to the access controls elements to capture a snapshot configuration of device rule-sets of the one or more access control elements;

enabling the administrator to specify a set of global access constraints with reference to the plurality of access control elements;

enabling the administrator to select between exhaustive analysis and statistical analysis, wherein exhaustive analysis is of each potential path through the network topology;

conducting the selected analysis to determine violations by the device rule-sets that fail to comply with the set of global access constraints, wherein statistical analysis quantitatively characterizes a level of compliance without conducting analysis of all potential paths of the network topology; and

providing results of the selected analysis to the administrator through a graphical user interface (GUI) as the results are obtained.

2. The method of claim 1, wherein the plurality of access control elements include network resources, and wherein enabling the administrator to specify a set of global access constraints comprises enabling the administrator to set a global access constraint for a group of the network resources.

3. The method of claim 1, further comprising:

converting the device rule-sets of the one or more access control elements into a software language format;

integrating the converted device rule-sets into a schema of the software language format for presentation to the administrator through the GUI; and

integrating the administrator-specified global access constraints into the unified software language schema of the converted device rule-sets.

4. The method of claim 1, further comprising:

enabling the administrator to abort the analysis; and

enabling the administrator to perform a post-analysis on any partial or complete results throughout the analysis process.

5. The method of claim 1, wherein the post-analysis comprises:

enabling the administrator to make hypothetical changes to the configuration of the device rule-sets for the plurality of access control elements; and

enabling the administrator to select from at least one of exhaustive analysis and statistical analysis to analyze the changed configuration.

6. The method of claim 1, further comprising:

checking, for consistency, the configuration represented by the snapshot of the plurality of access control elements together with the administrator-specified global access constraints; and

generating a multi-layered rule graph that captures network interconnectivity and data flow among the intercommunicating elements according to the global access constraints.

7. The method of claim 6, wherein upon the administrator selecting the exhaustive analysis, the method further comprising:

analyzing the multi-layered rule graph for the network topology in its entirety, considering each piece of configuration information collected; and

producing a complete list of sequences of access decisions that indicates one or more paths taken through the multi-layered rule graph that violates a global access constraint.

8. The method of claim 7, wherein analyzing the multi-layered rule graph comprises:

obtaining data structures and traffic attribute sets for the multi-layered rule graph that enable rapid traversal thereof, and algorithms to manipulate the data structures and attribute sets;

using multi-dimensional interval trees to represent a network traffic component of the attribute sets;

using custom set data structures to represent discrete components of the attribute sets; and

using intelligent caching of results of analyses of sub-paths to minimize repeated computations.

9. The method of claim 6, wherein upon the administrator selecting the statistical analysis, the method further comprising:

conducting repeated and random exploration of an extended version of the multi-layered rule graph to sample a number of paths;

calculating a desired set of metrics for each explored path through use of mathematically formulated heuristics that guide the path choices toward those likely to be sources of violation of the global access constraints; and

conducting importance sampling on the explored paths to remove any bias introduced by the guidance heuristic and to obtain unbiased estimators of the metrics.

10. The method of claim 9, further comprising:

calculating a quantitative estimate of a remainder of the unexplored paths of the multi-layered rule graph; and

analyzing the sampled paths of the multi-layered rule graph with the unbiased metrics estimators to form an estimate of the total number of paths therethrough that violate a specified global access constraint.

11. A system for analyzing distributed policy rule-sets for compliance with global policies, the system comprising:

a graphical user interface (GUI) through which an administrator specifies a network topology with a plurality of intercommunicating elements and associated parameters required to secure the intercommunication with one or more access control elements of the network topology;

an analysis engine in communication with the GUI and with the plurality of elements, the analysis engine including a processor to unify a plurality of device rule-sets associated with the one or more access control elements, and to convert the device rule-sets into a software language format presentable to the administrator through the GUI; and

a memory to store an administrator-specified global access policy (GAP) that includes a plurality of global access constraints with reference to the plurality of elements, and to store the plurality of access policy rules;

wherein the processor;

enables the administrator to select through the GUI between exhaustive analysis and statistical analysis as the compliance analysis, wherein exhaustive analysis is of each potential path through the network topology;

conducts the selected compliance analysis to determine violations by the device rule-sets that fail to comply with the GAP, wherein statistical analysis quantitatively characterizes a level of compliance without conducting analysis of all potential paths of the network topology; and

provides results of the selected compliance analysis to the GUI for viewing by the administrator.

12. The system of claim 11, wherein the processor converts the GAP into the software language format and analyzes compliance of the one or more access control elements in accordance with the GAP.

13. The system of claim 11, wherein the processor automatically selects, on behalf of the advertiser, the at least one of exhaustive analysis and statistical analysis based on a determined level of resources required to conduct a full exhaustive analysis.

14. The system of claim 11, wherein the processor analyzes the network topology to capture a snapshot configuration of the device rule-sets affiliated therewith, and wherein the processor converts the configuration into a schema of the software language for presentation through the GUI.

15. The system of claim 14, wherein the processor:

indexes and caches in the memory the snapshot configuration of the device rule-sets of the network topology; and

while the analysis engine is disconnected from communication with the plurality of intercommunicating elements, accesses the cached snapshot configuration of the converted device rule-sets to analyze compliance of the one or more access control elements in accordance with the GAP.

16. The system of claim 14, wherein the analysis engine comprises:

a consistency checker that, together with the processor, analyzes the snapshot configuration of the device rule-sets based on the administrator-specified parameters, and returns to the GUI a list of violations thereof with at least one global access constraint for reference by the administrator.

17. The system of claim 16, wherein the consistency checker generates a multi-layered rule graph that captures network interconnectivity and data flow among the plurality of intercommunicating elements according to the GAP, and wherein the processor integrates the GAP into the software schema for purposes of the compliance analysis.

18. The system of claim 11, wherein the processor:

enables the administrator, through the GUI, to abort the analysis; and

enables the administrator to perform a post-analysis on any partial or complete results throughout the compliance analysis.

19. The system of claim 18, wherein the processor:

enables the administrator, through the GUI, to make hypothetical changes to the configuration of the device rule-sets for the plurality of elements; and

enables the administrator to select from at least one of exhaustive analysis and statistical analysis to analyze the changed configuration.

20. The system of claim 11, wherein in response to the administrator selecting the exhaustive analysis, the processor:

analyzes the multi-layered rule graph for the network topology in its entirety, considering each piece of configuration information collected; and

produces a complete list of sequences of access decisions that indicates one or more paths taken through the multi-layered rule graph that violates a global access constraint of the GAP.

21. The system of claim 20, wherein the processor:

obtains data structures and traffic attribute sets for the multi-layered rule graph that enable rapid traversal thereof, and algorithms to manipulate the data structures and attribute sets;

uses multi-dimensional interval trees to represent a network traffic component of the attribute sets;

uses custom set data structures to represent discrete components of the attribute sets; and

uses intelligent caching of results of analyses of sub-paths to minimize repeated computations.

22. The system of claim 11, wherein in response to the administrator selecting the statistical analysis, the processor:

conducts repeated and random exploration of an extended version of the multi-layered rule graph to sample a number of paths;

calculates a desired set of metrics for each explored path through use of mathematically formulated heuristics that guide the path choices toward those likely to be sources of violation of the global access constraints; and

conducts importance sampling on the explored paths to remove any bias introduced by the guidance heuristic and to obtain unbiased estimators of the metrics.

23. The system of claim 22, where the processor:

calculates a quantitative estimate of a remainder of the unexplored paths of the multi-layered rule graph; and

analyzes the sampled paths of the multi-layered rule graph with the unbiased metrics estimators to form an estimate of the total number of paths therethrough that violate a specified global access constraint of the GAP.

24. The system of claim 11, wherein the one or more access control elements comprise a plurality of firewalls.

25. A computer readable medium including program code that causes a computer to perform the operations of:

enabling an administrator to specify a network topology with a plurality of intercommunicating elements and associated parameters required to secure the intercommunication with one or more access control elements of the network topology;

establishing connections to the access controls elements to capture a snapshot configuration of device rule-sets of the one or more access control elements;

enabling the administrator to specify a set of global access constraints with reference to the plurality of access control elements;

enabling the administrator to select between exhaustive analysis and statistical analysis, wherein exhaustive analysis is of each potential path through the network topology;

conducting the selected analysis to determine violations by the device rule-sets that fail to comply with the set of global access constraints, wherein statistical analysis quantitatively characterizes a level of compliance without conducting analysis of all potential paths of the network topology; and

providing results of the selected analysis to the administrator through a graphical user interface (GUI) as the results are obtained.

26. The computer readable medium of claim 25, wherein the plurality of access control elements include network resources, and wherein enabling the administrator to specify a set of global access constraints comprises enabling the administrator to set a global access constraint for a group of the network resources.

27. The computer readable medium of claim 25, further comprising performing the operation of:

automatically selecting, on behalf of the advertiser, the at least one of exhaustive analysis and statistical analysis based on a determined level of resources required to conduct a full exhaustive analysis.