Analysis of distributed policy rule-sets for compliance with global policy

• US 8,209,738 B2
• Filed: 05/28/2008
• Issued: 06/26/2012
• 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., Sanders, William H., Singh, Sankalp, Seri, Mouna
• Primary Examiner(s): LaForgia, Christian
• Assistant Examiner(s): TURCHEN, JAMES R
• Application Number:
  US12/128,445
• Publication Number:
  US 20080301765A1
• Time in Patent Office: 1,490 Days
• Field of Search: 726/1, 726/25
• 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 computer-implemented method for analysis of distributed device rule-sets for compliance with global policies, the method executable by a computer having a processor and memory, comprising:

receiving from an administrator a network topology with a plurality of reachable, 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 control elements to capture a snapshot configuration of device rule-sets of the one or more access control elements;

receiving from the administrator a set of global access constraints with reference to the plurality of access control elements;

generating a multi-layered rule graph that captures network interconnectivity and data flow among the intercommunicating elements, where each of a plurality of nodes in the multi-layered rule graph represents a possible access decision by an access control element and paths of the multi-layered rule graph represent sequences of access decisions;

conducting statistical analysis using model-based importance sampling of the multi-layered rule graph to determine violations by the device rule-sets that fail to comply with the set of global access constraints, the importance sampling quantitatively characterizing a level of compliance with the global access constraints without conducting analysis of all potential paths of the multi-layered rule graph; and

providing results of the statistical analysis to the administrator through a graphical user interface (GUI) of the computer as the results are obtained so that the administrator can watch the progress of the analysis.

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 4, 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.

7. The method of claim 1, further comprising:

enabling the administrator to select exhaustive analysis;

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;

labeling a plurality of edges in the multi-layered rule graph, each label describing all traffic that is admitted by a rule corresponding to an edge source node and being analyzed by a rule corresponding to a terminal node; and

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

9. The method of claim 1, 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 to construct unbiased statistical measures of compliance;

using the importance sampling to guide the random selection towards paths likely to be sources of violation of the global access constraints to reduce variance in the compliance measures; and

calculating a desired set of metrics for traffic represented by each explored path.

10. The method of claim 9, where calculating a desired set of metrics includes calculating unbiased metrics estimators to remove a bias introduced by the importance sampling, 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 reachable, 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 operable 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 is operable to;

generating a multi-layered rule graph that captures network interconnectivity and data flow among the intercommunicating elements, where each of a plurality of nodes in the multi-layered rule graph represents a possible access decision by an access control element and paths of the multi-layered rule graph represent sequences of access decisions;

conduct statistical analysis using model-based importance sampling of the multi-layered rule graph to determine violations by the device rule-sets that fail to comply with the GAP, the importance sampling quantitatively characterizing a level of compliance with the GAP without conducting analysis of all potential paths of the multi-layered rule graph; and

provide results of the selected compliance analysis in real time to the GUI for viewing by the administrator as the results are obtained.

12. The system of claim 11, wherein the processor is operable to convert 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 is operable to select, 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 is operable to analyze the network topology to capture a snapshot configuration of the device rule-sets affiliated therewith, and wherein the processor is operable to convert the configuration into a schema of the software language for presentation through the GUI.

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

index and cache 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, to access 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, is operable to analyze the snapshot configuration of the device rule-sets based on the administrator-specified parameters, and return 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 the multi-layered rule graph that captures network interconnectivity and data flow among the plurality of intercommunicating elements, and wherein the processor is operable to integrate the GAP into the software schema for purposes of the compliance analysis, where each of a plurality of nodes in the multi-layered rule graph represents a possible access decision by an access control element.

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

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

enable 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 is operable to:

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

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

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

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

produce 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 by all traffic to which that sequence of access decisions applies.

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

obtain 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;

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

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

label a plurality of edges in the multi-layered rule graph, each label describing all traffic that is admitted by a rule corresponding to an edge source node and being analyzed by a rule corresponding to a terminal node; and

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

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

conduct repeated and random exploration of an extended version of the multi-layered rule graph to sample a number of paths to construct unbiased statistical measures of compliance;

use importance sampling to guide the random selection towards paths likely to be sources of violation of the global access constraints to reduce variance in the compliance measures; and

calculate a desired set of metrics for traffic represented by each explored path.

23. The system of claim 22, where to calculate a desired set of metrics the processor operable to calculate unbiased metrics estimators to remove a bias introduced by the importance sampling, where the processor is further operable to:

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

analyze 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 non-transitory computer readable medium including machine-readable instructions executable by a processor that causes a computer including the processor and memory to perform the operations of:

enabling an administrator to specify a network topology with a plurality of reachable, 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 control 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;

generating a multi-layered rule graph that captures network interconnectivity and data flow among the intercommunicating elements, where each of a plurality of nodes in the multi-layered rule graph represents a possible access decision by an access control element and paths of the multi-layered rule graph represent sequences of access decisions;

conducting statistical analysis using model-based importance sampling of the multi-layered rule graph to determine violations by the device rule-sets that fail to comply with the set of global access constraints, the importance sampling quantitatively characterizing a level of compliance with the global access constraints without conducting analysis of all potential paths of the multi-layered rule graph; and

providing results of the selected analysis to the administrator in real time through a graphical user interface (GUI) as the results are obtained so that the administrator can watch the progress of the analysis.

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, at least one of exhaustive analysis and statistical analysis based on a determined level of resources required to conduct a full exhaustive analysis.

28. A computer-implemented method for analysis of distributed device rule-sets for compliance with global policies, the method executable by a computer having a processor and memory, comprising:

receiving from an administrator a network topology with a plurality of reachable, 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 control elements to capture a snapshot configuration of device rule-sets of the one or more access control elements;

receiving from the administrator a set of global access constraints with reference to the plurality of access control elements;

generating a multi-layered rule graph that captures network interconnectivity and data flow among the intercommunicating elements, where each of a plurality of nodes in the multi-layered rule graph represents a possible access decision by an access control element and paths of the multi-layered rule graph represent sequences of access decisions;

receiving a selection to perform model-based statistical analysis to determine violations by the device rule-sets that fail to comply with the set of global access constraints, where statistical analysis quantitatively characterizes a level of compliance without conducting analysis of all potential paths of the network topology;

conducting the statistical analysis by selecting a probability distribution that biases sampling paths having device rule-sets that increase the likelihood of discovering violations of the global access constraints in the device rule-sets of sampled paths; and

providing results of the statistical analysis to the administrator as the results are obtained.

29. The method of claim 28, where the snapshot configuration of the device rule-sets is received from the administrator.

30. The method of claim 28, where the statistical analysis further comprises:

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

using importance sampling to guide the random selection towards paths likely to be sources of violation of the global access constraints to reduce variance in the compliance measure; and

calculating a desired set of metrics for traffic represented by each explored path.

31. The method of claim 30, where calculating a desired set of metrics includes calculating unbiased metrics estimators to remove a bias introduced by the importance sampling, 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.

32. The method of claim 28, further comprising:

enabling the administrator to abort the analysis;

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

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 conduct again the statistical analysis to analyze the changed configuration.

33. The method of claim 28, further comprising:

presenting the results to the administrator through a graphical user interface (GUI) of the computer; and

enabling the administrator, through the computer and while viewing the results in the GUI as the results are obtained, to manipulate, filter, or navigate through the results and to visualize a violation once the violation is detected, thereby enabling real-time diagnostic of one or more misconfigurations of a configuration of the device rule-set of one or more control access elements.

34. The method of claim 33, further comprising:

accepting one or more proposed modifications to the device rule-sets; and

sending the proposed modifications to an analysis engine of the computer to perform the statistical analysis again to verify whether the proposed modifications would resolve one or more of the misconfigurations.