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.