  Recent work has made great progress in verifying the forwarding correctness
of networks . However, these approaches cannot be used to verify networks
containing middleboxes, such as caches and firewalls, whose forwarding behavior
depends on previously observed traffic. We explore how to verify reachability
properties for networks that include such "mutable datapath" elements. We want
our verification results to hold not just for the given network, but also in
the presence of failures. The main challenge lies in scaling the approach to
handle large and complicated networks, We address by developing and leveraging
the concept of slices, which allow network-wide verification to only require
analyzing small portions of the network. We show that with slices the time
required to verify an invariant on many production networks is independent of
the size of the network itself.
