  As deep neural networks are increasingly being deployed in practice, their
efficiency has become an important issue. While there are compression
techniques for reducing the network's size, energy consumption and
computational requirement, they only demonstrate empirically that there is no
loss of accuracy, but lack formal guarantees of the compressed network, e.g.,
in the presence of adversarial examples. Existing verification techniques such
as Reluplex, ReluVal, and DeepPoly provide formal guarantees, but they are
designed for analyzing a single network instead of the relationship between two
networks. To fill the gap, we develop a new method for differential
verification of two closely related networks. Our method consists of a fast but
approximate forward interval analysis pass followed by a backward pass that
iteratively refines the approximation until the desired property is verified.
We have two main innovations. During the forward pass, we exploit structural
and behavioral similarities of the two networks to more accurately bound the
difference between the output neurons of the two networks. Then in the backward
pass, we leverage the gradient differences to more accurately compute the most
beneficial refinement. Our experiments show that, compared to state-of-the-art
verification tools, our method can achieve orders-of-magnitude speedup and
prove many more properties than existing tools.
