Verifying whether connectivity in a composed policy graph reflects a corresponding policy in input policy graphs

Patent metadata

Field	Value
Publication number	US-10567384-B2
Application number	US-201715686552-A
Country	US
Kind code	B2
Filing date	Aug 25, 2017
Priority date	Aug 25, 2017
Publication date	Feb 18, 2020
Grant date	Feb 18, 2020

Abstract

Example method includes: receiving, by a network device, a plurality of input policy graphs and a composed policy graph associated with the input policy graphs; dividing the composed policy graph into a plurality of sub-graphs, each sub-graph comprising a plurality of edges and a plurality of source nodes and destination nodes that the edges are connected to; selecting a first subset of sub-graphs that include, as a source node, a disjoint part of an original source EPG for each input policy graph; identifying a second subset within the first subset of sub-graphs that include, as a destination node, a disjoint part of an original destination EPG for the each input policy graph; and verifying whether connectivity in the composed policy graph reflects a corresponding policy in the plurality of input policy graphs for each sub-graph in the second subset.

First claim

We claim:

1. A method comprising:
receiving, by a network device, a plurality of input policy graphs and a composed policy graph associated with the input policy graphs;
dividing, by the network device, the composed policy graph into a plurality of sub-graphs, each sub-graph comprising a plurality of edges and a plurality of source nodes and destination nodes that the edges are connected to;
selecting, by the network device, a first subset of sub-graphs that include, as a source node, a disjoint part of an original source end point group (EPG) for each input policy graph;
identifying, by the network device, a second subset within the first subset of sub-graphs that include, as a destination node, a disjoint part of an original destination EPG for the each input policy graph;
verifying, by the network device, whether connectivity in the composed policy graph reflects a corresponding policy in the plurality of input policy graphs for each sub-graph in the second subset;
removing, from the second subset of sub-graphs, classifier information associated with the plurality of input policy graphs; and
in response to no input policy graph being associated with the second subset of sub-graphs, indicating that the second subset of sub-graphs are verified.

2. The method of claim 1 , further comprising:
in response to determining that communication between the source node and the destination node in the composed policy graph contradicts to at least one input policy graph, using edge metadata information to identify whether the communication is blocked due to a legitimate composition with other input policy graphs; and
in response to the edge metadata information indicating that the communication is blocked without the legitimate composition with the other input policy graphs, indicating a particular edge between the source node and the destination node in the composed policy graph as a network policy violation.

3. The method of claim 1 , further comprising:
using label tree information and node specific metadata information to track memberships of EPGs in the composed policy graph; and
joining the EPGs such that the joined set corresponds to a whole set of EPGs associated with the plurality of received input policy graphs.

4. The method of claim 1 , further comprising:
in response to each sub-graph being validated for the disjoint parts of both the source EPG and the destination EPG in the each input policy graph, indicating that the each input policy graph is validated.

5. The method of claim 1 , further comprising:
in response to the plurality of input policy graphs being validated, classifying sub-graphs that remain unexamined as incorrect connectivity introduced by the composed policy graph.

6. The method of claim 1 , wherein the original source EPG and the original destination EPG are identified by the EPG metadata information.

7. The method of claim 1 , wherein verifying that connectivity reflects the policy of the input policy graphs further comprises:
verifying whether the input policy graphs include an edge indicating that communication is allowed; and
verifying whether a network function corresponds to the edge.

8. A network device, comprising at least:
a memory;
a processor executing instructions from the memory to:
receive a plurality of input policy graphs and a composed policy graph associated with the input policy graphs;
divide the composed policy graph into a plurality of sub-graphs, each sub-graph comprising a plurality of edges and a plurality of source nodes and destination nodes that the edges are connected to;
select a first subset of sub-graphs that include, as a source node, a disjoint part of an original source end point group (EPG) for each input policy graph;
identify a second subset within the first subset of sub-graphs that include, as a destination node, a disjoint part of an original destination EPG for the each input policy graph;
verify whether connectivity in the composed policy graph reflects a corresponding policy in the plurality of input policy graphs for each sub-graph in the second subset remove, from the second subset of sub-graphs, classifier information associated with the plurality of input policy graphs; and
in response to no input policy graph being associated with the second subset of sub-graphs, indicate that the second subset of sub-graphs are verified.

9. The network device of claim 8 , wherein the processor executing instructions from the memory further to:
verify whether connectivity in a composed policy graph reflects a corresponding policy in a plurality of input policy graphs;
identify, in the composed policy graph, a first original end point group (EPG) to which a source endpoint in an input policy graph corresponds;
identify, in the composed policy graph, a second original EPG to which a destination endpoint in the input policy graph corresponds;
determine whether both the first original EPG and the second original EPG are associated with an input policy allowing communications between the original EPGs;
in response to the input policy allowing the communication between the original EPGs exists, indicate the input policy in the composed policy graph; and
identify a particular sub-graph that interconnects the EPGs including the endpoints of which a host is a member in the composed policy graph.

10. The network device of claim 9 , wherein the processor executing instructions from the memory further to:
determine whether communications are allowed based on the composed policy graph;
in response to communications being allowed without a legitimate reason from composition of the plurality of input policy graphs, send an alert comprising an incorrectly mapped EPG to a network administrator.

11. The network device of claim 8 , wherein the processor executing instructions from the memory further to determine whether a host from a particular EPG is compromised.

12. The network device of claim 11 , wherein the processor executing instructions from the memory further to determine which EPGs are connected to the host through the particular compromised EPG.

13. A non-transitory machine-readable storage medium encoded with instructions executable by at least one processor of an access point, the machine-readable storage medium comprising instructions to:
receive a plurality of input policy graphs and a composed policy graph associated with the plurality of input policy graphs;
divide the composed policy graph into a plurality of sub-graphs, each sub-graph comprising a plurality of edges and a plurality of source nodes and destination nodes that the edges are connected to;
select a subset of sub-graphs that include, as a source node, a disjoint part of an original source end point group (EPG) and, as a destination node, a disjoint part of an original destination EPG for each input policy graph;
verify whether connectivity in the composed policy graph reflects a corresponding policy in the received input policy graphs for each sub-graph in the subset;
identify, in the composed policy graph, a first original EPG to which a source endpoint in an input policy graph corresponds and a second original EPG to which a destination endpoint in the input policy graph corresponds;
indicate an input policy in the composed policy graph in response to both the first original EPG and the second original EPG being associated with the input policy allowing communications between the first and second original EPGs;
remove, from the subset of sub-graphs, classifier information associated with the plurality of input policy graphs; and
indicate that the subset of sub-graphs are verified in response

Assignees

• Hewlett Packard Entpr Dev Lp

Inventors

• Kang Joon-Myung
• Sanchez Mario Antonio
• Zhang Ying
• Mercian Anu
• Dantas Leite Raphael Amorim
• Banerjee Sujata

Classifications

• H04L43/04

  Processing captured monitoring data, e.g. for logfile generation · CPC title

• G06F21/577

  Assessing vulnerabilities and evaluating computer system security · CPC title

• G06F21/57

  Certifying or maintaining trusted computer platforms, e.g. secure boots or power-downs, version controls, system software checks, secure updates or assessing vulnerabilities · CPC title

• G06F21/604

  Tools and structures for managing or administering access control systems · CPC title

• H04L63/0263

  Rule management · CPC title