Fast and Effective Robustness Certification
We present a new method and system, called DeepZ, for certifying neural network robustness based on abstract interpretation. Compared to state-of-the-art automated verifiers for neural networks, DeepZ: (i) handles ReLU, Tanh and Sigmoid activation functions, (ii) supports feedforward, convolutional, and residual architectures, (iii) is significantly more scalable and precise, and (iv) and is sound with respect to floating point arithmetic. These benefits are due to carefully designed approximations tailored to the setting of neural networks. As an example, DeepZ achieves a verification accuracy of 97% on a large network with 88, 500 hidden units under L ∞ attack with = 0.1 with an average runtime of 133 seconds.
The paper develops a new approach for the problem of verifying input-output properties of neural network, an emerging area that has received significant interest and attention in the ML community recently. The approach builds on previous work that uses abstract interpretation (sound abstractions of the transformations at each layer of a neural network) that can be used to reason about worst-case behavior of the network with respect to desired input-output properties (for example, that the network should continue to produce the same label despite adversarially chosen small perturbations of the input). If the property is satisfied by the sound abstraction, the property will be satisfied by the underlying network as well.  Strengths of the paper: Well written - the central idea of zonotopes is clearly explained, and the property of area minimizing parallelogram abstractions of various neural network transformations (relu, sigmoid, tanh) is explained geometrically and derived. The paper computes certificates that are sound even accounting for floating point arithmetic - a property that many competing approaches (like those of Kolter et al, Raghunathan et al, Dvijotham et al) do not satisfy. The paper applies to a broad class of transformations commonly found in feedforward neural networks, unlike previous approaches from that use tools from the formal methods community (like Katz et al, Elhers et al etc.)  Weaknesses of the paper: Justifying the use of zonotopes: The authors claim that zonotopes provide a sound abstraction that offers the right tradeoff between precision and computation, but do not provide much justification for why this is the case. For example, it was not clear to me why enforcing a parallelogram shape in the abstraction is necessary - for example, the ReLU is abstract better by the triangle used in the PLANET (Elhers et al) paper. I understand that this helps preserve the affine interval expression structure - however, it is not clear why this interval expression structure is crucial for the approach to work or scale. Comparison to prior work: When specialized to the case of piecewise linear activation functions, the approach seems to be equivalent (or very close to) that of https://www.icml.cc/Conferences/2018/Schedule?showEvent=2976 . This paper also proves that the approach is equivalent to a that form (Kolter and Wang, 2017) https://arxiv.org/abs/1711.00851 . While the authors extend the approach to nonlinear activation functions and ensure that the computations are rigorous under finite precision arithmetic, a careful discussion and comparison to this previous work is certainly warranted. Without it, the novelty of the approach in the paper comes under question. Experimental evaluation: I have several concerns with the experimental evaluation section of the paper: It is well-understood from the works of (Kolter and Wang, 2017) and (Raghunathan et al, 2017) that networks that are trained to be verifiable are significantly easier to verify than networks trained arbitrarily. The Given how close the approach is to that from https://www.icml.cc/Conferences/2018/Schedule?showEvent=2976, a comparison to this approach on ReLU networks is certainly warranted.  It would be good to compare against other approaches that use formal methods and are sound to floating point arithmetic (like ReLUplex from Katz et al, PLANET from Elhers et al). In the comparison against [Dvijotham et al, 2018], the authors only implement the version of the algorithm with optimization based bound propagation. The approach also works with interval arithmetic based bound propagation and is likely much faster in this variant -  Final results: Published numbers for verified robustness against adversarial attacks on MNIST and CIFAR (from https://www.icml.cc/Conferences/2018/Schedule?showEvent=2976 and Kolter and Wang) are significantly better than those from the paper - for example, these papers establish verified error rates of around 5% against perturbations of size .1 or larger while those in the paper are significiantly weaker. While this is likely due to the training procedure used, it would have been good for the authors to apply their methods to the networks trained by (Kolter and Wang), (Mardry et al) which are publicly available to see if they indeed produce state of the art numbers on verified accuracy/robustness. Another possibility is the need to account soundly for finite precision arithmetic, but the reviewer feels that this needs to be justified through numerical studies (or by implementing a version of the authors’ approach that does not guarantee soundness against finite precision, only against precise real arithmetic). Other specifications on the input: The examples considered in the paper assume that the constraints on the input can be given by lower and upper bounds. It is clear that the zonotopes can work with other types of input constraints - however, it is not clear how gracefully the performance (in terms of precision loss) would degrade (for example, with an l2 constraint on the inputs instead of linf).  As a side note, at least in the ML community, “zonotopes” is not a commonly used term. Given the central idea of the paper can be captured in the idea of bounding nonlinear tranforms with affine interval expressions, perhaps a simpler name is more appropriate for the ML community?  Overall evaluation:  Clarity: The paper is clearly written.  Quality: The theoretical results are accurate and well presented. However, the quality of the experimental section can be significantly improved.  Novelty: The paper adds novelty in addressing finite precision arithmetic and general activation functions relative to previous verification approaches. However, the lack of a clear comparison to https://www.icml.cc/Conferences/2018/Schedule?showEvent=2976 casts a shadow on how novel the core idea of zonotopes, particularly in the context of neural network verification.  Significance: The paper is an interesting albeit marginal addition to the state of the art, in that the paper offers a scalable/general approach to robustness certification that is sound against floating point arithmetic.