  Complete verification of deep neural networks (DNNs) can exactly determine
whether the DNN satisfies a desired trustworthy property (e.g., robustness,
fairness) on an infinite set of inputs or not. Despite the tremendous progress
to improve the scalability of complete verifiers over the years on individual
DNNs, they are inherently inefficient when a deployed DNN is updated to improve
its inference speed or accuracy. The inefficiency is because the expensive
verifier needs to be run from scratch on the updated DNN. To improve
efficiency, we propose a new, general framework for incremental and complete
DNN verification based on the design of novel theory, data structure, and
algorithms. Our contributions implemented in a tool named IVAN yield an overall
geometric mean speedup of 2.4x for verifying challenging MNIST and CIFAR10
classifiers and a geometric mean speedup of 3.8x for the ACAS-XU classifiers
over the state-of-the-art baselines.
