A method of network property verification, the method including obtaining a property of a network to be verified and obtaining forwarding rules for multiple network devices in the network, the forwarding rules indicative of how the network devices handle incoming packets and at least one of the network devices including forwarding rules to forward an address-based packet and forward a variable-length header packet. The method may also include generating a graph representation of the forwarding rules, where each rule of the forwarding rules is independently applicable to address-based packets or variable-length header packets. The method may additionally include assigning transition operations between the network devices in the graph representation based on the forwarding rules, assigning, in the graph representation, an atom to links between network devices that forward variable-length header packets, and verifying the property of the network using the graph representation to identify any network issue.