Network property verification

• US 10,693,744 B2
• Filed: 11/02/2017
• Issued: 06/23/2020
• Est. Priority Date: 11/02/2017
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Horn, Alexander, Prasad, Mukul R., Oguchi, Naoki, Palacharla, Paparao
• Primary Examiner(s): Chen, Cai Y
• Application Number:
  US15/802,412
• Publication Number:
  US 20190132216A1
• Time in Patent Office: 964 Days
• Field of Search: None
• 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/142 using statistical or mathematical methods
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04L 43/045 for graphical visualisation of monitoring data
• CPC Class Codes: H04L 63/0263 Rule management
• CPC Class Codes: H04L 63/20 for managing network security; network security policies in general filtering policies H04L63/0227

Abstract

A method may include obtaining packet handling rules from at least one firewall in a network and at least one routing table in the network, and translating the packet handling rules to canonical data structures based on priority of rules at a given routing table or a given firewall. Each canonical data structure may represent a subset of packets affected by one or more corresponding packet handling rules such that each packet handling rule is covered by at least one canonical data structure. The method may also include generating a graph representation of the firewalls and the nodes corresponding to the routing tables in the network. The method may additionally include labeling vertices and edges in the graph representation based on the packet handling rules. The method may also include, using the graph representation, verifying one or more network properties to identify any network issues.

Claims

1. A method, comprising:

obtaining a plurality of packet handling rules from at least one firewall in a network and at least one routing table in the network;

translating the packet handling rules to one or more canonical data structures based on priority of rules at a given routing table or a given firewall, each canonical data structure representing a subset of packets affected by one or more corresponding packet handling rules such that each packet handling rule is covered by at least one canonical data structure;

generating a graph representation of the at least one firewall and at least one node corresponding to the at least one routing table in the network;

labeling a vertex in the graph representation with a first canonical data structure based on the first canonical data structure being associated with a first packet handling rule of the given firewall, the vertex in the graph representation corresponding to the given firewall;

labeling an edge in the graph representation with a second canonical data structure based on the second canonical data structure being associated with a second packet handling rule of the given routing table, the edge in the graph representation corresponding to the given routing table; and

using the graph representation, verifying one or more network properties to identify any network issues.

2. The method of claim 1, wherein verifying one or more network properties includes, for each packet handling rule with a source and a destination, verifying that the source can reach the destination in the graph representation.

3. The method of claim 1, wherein the canonical data structures include packet equivalence classes, each packet equivalence class including the subset of packets, a protocol field, and an action field.

4. The method of claim 3, wherein at least one of the protocol field and the action field are empty.

5. The method of claim 1, wherein the canonical data structures are independent of a manufacturer of the network nodes in the network.

6. The method of claim 1, wherein verifying one or more network properties includes, for each packet handling rule of the at least one firewall, verifying that a given packet handling rule includes at least one canonical data structure by subtracting out the canonical data structures for higher priority rules of the at least one firewall.

7. The method of claim 1, further comprising:

labeling vertices in the graph representation with any canonical data structures associated with a subset of packets that are accepted by a corresponding firewall; and

labeling edges in the graph representation with any canonical data structures associated with a subset of packets that are routed along a given edge based on a corresponding routing table.

8. The method of claim 7, wherein verifying one or more network properties includes for each vertex in the graph representation labeled with a canonical data structure, verifying that an outgoing edge from the vertex in the graph representation is labeled with the canonical data structure.

9. A non-transitory computer readable medium including instructions that, when executed by one or more processors, are configured to perform or control performance of operations, the operations comprising:

obtaining a plurality of packet handling rules from at least one firewall in a network and at least one routing table in the network;

translating the packet handling rules to one or more canonical data structures based on priority of rules at a given routing table or a given firewall, each canonical data structure representing a subset of packets affected by one or more corresponding packet handling rules such that each packet handling rule is covered by at least one canonical data structure;

generating a graph representation of the at least one firewall and at least one node corresponding to the at least one routing table in the network;

labeling a vertex in the graph representation with a first canonical data structure based on the first canonical data structure being associated with a first packet handling rule of the given firewall, the vertex in the graph representation corresponding to the given firewall;

labeling an edge in the graph representation with a second canonical data structure based on the second canonical data structure being associated with a second packet handling rule of the given routing table, the edge in the graph representation corresponding to the given routing table; and

using the graph representation, verifying one or more network properties to identify any network issues.

10. The computer readable medium of claim 9, wherein verifying one or more network properties includes, for each packet handling rule with a source and a destination, verifying that the source can reach the destination in the graph representation.

11. The computer readable medium of claim 9, wherein the canonical data structures include packet equivalence classes, each packet equivalence class including a corresponding subset of packets, a protocol field, and an action field.

12. The computer readable medium of claim 11, wherein at least one of the protocol field and the action field are empty.

13. The computer readable medium of claim 9, wherein the canonical data structures are independent of a manufacturer of the network nodes in the network.

14. The computer readable medium of claim 9, wherein verifying one or more network properties includes, for each packet handling rule of the at least one firewall, verifying that a given packet handling rule includes at least one canonical data structure by subtracting out the canonical data structures for higher priority rules of the at least one firewall.

15. The computer readable medium of claim 9, the operations further comprising:

labeling vertices in the graph representation with any canonical data structures associated with a subset of packets that are accepted by a corresponding firewall; and

labeling edges in the graph representation with any canonical data structures associated with a subset of packets that are routed along a given edge based on a corresponding routing table.

16. The computer readable medium of claim 15, wherein verifying one or more network properties includes for each vertex in the graph representation labeled with a canonical data structure, verifying that an outgoing edge from the vertex in the graph representation is labeled with the canonical data structure.

17. A system comprising:

one or more processors; and

one or more non-transitory computer readable media including instructions that, when executed by the one or more processors, are configured to perform or control performance of operations, the operations comprising;

obtaining a plurality of packet handling rules from at least one firewall in a network and at least one routing table in the network;

translating the packet handling rules to one or more canonical data structures based on priority of rules at a given routing table or a given firewall, each canonical data structure representing a subset of packets affected by one or more corresponding packet handling rules such that each packet handling rule is covered by at least one canonical data structure;

generating a graph representation of the at least one firewall and at least one node corresponding to the at least one routing table in the network;

labeling a vertex in the graph representation with a first canonical data structure based on the first canonical data structure being associated with a first packet handling rule of the given firewall, the vertex in the graph representation corresponding to the given firewall;

labeling an edge in the graph representation with a second canonical data structure based on the second canonical data structure being associated with a second packet handling rule of the given routing table, the edge in the graph representation corresponding to the given routing table; and

using the graph representation, verifying one or more network properties to identify any network issues.

18. The system of claim 17, the operations further comprising:

labeling vertices in the graph representation with any canonical data structures associated with a subset of packets that are accepted by a corresponding firewall; and

labeling edges in the graph representation with any canonical data structures associated with a subset of packets that are routed along a given edge based on a corresponding routing table;

wherein verifying one or more network properties includes for each vertex in the graph representation labeled with a canonical data structure, verifying that an outgoing edge from the vertex in the graph representation is labeled with the canonical data structure.

19. The system of claim 17, wherein verifying one or more network properties includes, for each packet handling rule with a source and a destination, verifying that the source can reach the destination in the graph representation.

20. The system of claim 17, wherein the canonical data structures include packet equivalence classes, each packet equivalence class including the subset of packets, a protocol field, and an action field.