Safety Verification of Deep Neural Networks
By Xiaowei Huang, Marta Z. Kwiatkowska, Sen Wang, Min Wu. 2016
1,011 citations recorded by the source corpus.
Deep neural networks have achieved impressive experimental results in image classification, but can surprisingly be unstable with respect to adversarial perturbations, that is, minimal changes to the input image that cause the network to misclassify it. With potential applications including perception modules and end-to-end controllers for self-driving cars, this raises concerns about their safety. We develop a novel automated verification framework for feed-forward multi-layer neural networks based on Satisfiability Modulo Theory (SMT). We focus on safety of image classification decisions with respect to image manipulations, such as scratches or changes to camera angle or lighting conditions that would result in the same class being assigned by a human, and define safety for an individual decision in terms of invariance of the classification within a small neighbourhood of the original image. We enable exhaustive search of the region by employing discretisation, and propagate the analysis layer by layer. Our method works directly with the network code and, in contrast to existing methods, can guarantee that adversarial examples, if they exist, are found for the given region and family of manipulations. If found, adversarial examples can be shown to human testers and/or used to fine-tune the network. We implement the techniques using Z3 and evaluate them on state-of-the-art networks, including regularised and deep learning networks. We also compare against existing techniques to search for adversarial examples and estimate network robustness.
Subfields: Artificial Intelligence, Hardware and Architecture, Safety, Robustness & Interpretability, Program Analysis & Verification
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Percy Liang
- J. Kolter
- Cho-Jui Hsieh
- Huan Zhang
- Matthias Hein
- Nicholas Carlini
- Sergey Levine
- Pushmeet Kohli
In Hardware and Architecture
- Nicholas Carlini
- J. Kolter
- Eric Wong
- Suman Sekhar Jana
- Nicolas Papernot
- Ian J. Goodfellow
- Cho-Jui Hsieh
- Patrick Drew McDaniel
In Safety, Robustness & Interpretability
- Huan Zhang
- Cho-Jui Hsieh
- J. Kolter
- Nicholas Carlini
- Matthias Hein
- Eric Wong
- Suman Sekhar Jana
- Percy Liang
In Program Analysis & Verification
- Suman Sekhar Jana
- Eric Wong
- J. Kolter
- Huan Zhang
- Shiqi Wang
- Cho-Jui Hsieh
- Timon Gehr
- Clark W. Barrett
Citations in the corpus
- Risks from Learned Optimization in Advanced Machine Learning Systems (2019, neutral): “There are both white-box algorithms,[31] e.”
- Certified Robustness to Adversarial Examples with Differential Privacy (2018, background): “One line of work focuses on minimizing false positives by finding concrete counterexamples demonstrating robustness violations [24], [29].”
- Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning (2017, background): “We are firmly convinced that new research paths should be explored to address this fundamental issue, complementary to formal verification and certified defenses [80, 99].”
- ZOO: Zeroth Order Optimization Based Black-box Attacks to Deep Neural Networks without Training Substitute Models (2017, background): “readers can refer to recent works in [10, 13, 18, 28, 42, 43] and references therein for details.”
- Towards Evaluating the Robustness of Neural Networks (2016, background): “The former approach, while sound, is substantially more difficult to implement in practice, and all attempts have required approximations [2], [21].”
- Certified Adversarial Robustness via Randomized Smoothing (2019, methodology): “Exact methods are usually based on Satisfiability Modulo Theories (Katz et al., 2017; Carlini et al., 2017; Ehlers, 2017; Huang et al., 2017) or mixed integer linear programming (Cheng et al., 2017; Lomuscio & Maganti, 2017; Dutta et al., 2017; Fischetti & Jo, 2018; Bunel et al., 2018).”
- Efficient Formal Safety Analysis of Neural Networks (2018, background): “Several researchers have tried to extend and customize Satisfiability Modulo Theory (SMT) solvers, which have been very successful at verifying different properties of traditional software, for estimating decision boundaries with strong guarantees [13, 14, 11, 7, 25].”
- AI2: Safety and Robustness Certification of Neural Networks with Abstract Interpretation (2018, methodology): “, [3], [12], [14], [15], [17], [18], [29], [30], [32], [38], [41]).”
- Formal Security Analysis of Neural Networks using Symbolic Intervals (2018, methodology): “To tackle these challenges, all prior work on the formal security analysis of neural networks [6, 9, 16, 20] rely on different types of Satisfiability Modulo Theories (SMT) solvers and are thus severely limited by the efficiency of the solvers.”
- Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach (2018, background): “On the other hand, works done by Ehlers (2017); Katz et al. (2017a;b); Huang et al. (2017) focus on formally verifying the viability of certain properties in neural networks for any possible input, and transform this formal verification problem into satisfiability modulo theory (SMT) and large-scale…”
- Certified Defenses against Adversarial Examples (2018, background): “Huang et al. (2017) use SMT solvers and are able to analyze state-of-the-art networks on MNIST, but they make various approximations such that their numbers are not true upper bounds.”
- Provable defenses against adversarial examples via the convex outer adversarial polytope (2017, methodology): “The first (which is a topic that is broader than merely adversarial examples), is the work in the verification of neural networks [Huang et al., 2017, Katz et al., 2017, Ehlers, 2017].”
- Certifying Some Distributional Robustness with Principled Adversarial Training (2017, background): “Alternative approaches that provide formal verification of deep networks [31, 33, 34] are NP-hard in general; they require prohibitive computational expense even on small networks.”
- DeepXplore: Automated Whitebox Testing of Deep Learning Systems (2017, background): “This observation has inspired several researchers to try to improve the robustness and reliability of DNNs [9, 13, 17, 30, 32, 46, 51, 53, 62, 84, 89, 90].”
- Adversarial Examples: Attacks and Defenses for Deep Learning (2017, neutral): “[138] conducted initial studies on the evaluation.”
- Verifiable Reinforcement Learning via Policy Extraction (2018, background): “There has been work on verifying machine learning systems [3, 30, 16, 6, 19, 18, 15].”
- Scaling provable adversarial defenses (2018, methodology): “…on using exact (combinatorial) solvers to verify the robustness properties of networks, either via Satisfiability Modulo Theories (SMT) solvers [Huang et al., 2017, Ehlers, 2017, Carlini and Wagner, 2017] or integer programming approaches [Lomuscio and Maganti, 2017, Tjeng and Tedrake, 2017,…”