Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks
By Rüdiger Ehlers. 2017
695 citations recorded by the source corpus.
We present an approach for the verification of feed-forward neural networks in which all nodes have a piece-wise linear activation function. Such networks are often used in deep learning and have been shown to be hard to verify for modern satisfiability modulo theory (SMT) and integer linear programming (ILP) solvers. The starting point of our approach is the addition of a global linear approximation of the overall network behavior to the verification problem that helps with SMT-like reasoning over the network behavior. We present a specialized verification algorithm that employs this approximation in a search process in which it infers additional node phases for the non-linear nodes in the network from partial node phase assignments, similar to unit propagation in classical SAT solving. We also show how to infer additional conflict clauses and safe node fixtures from the results of the analysis steps performed during the search. The resulting approach is evaluated on collision avoidance and handwritten digit recognition case studies.
Subfields: Artificial Intelligence, Software, 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
In Software
In Safety, Robustness & Interpretability
- Huan Zhang
- J. Kolter
- Eric Wong
- Cho-Jui Hsieh
- Matthias Hein
- Suman Sekhar Jana
- Percy Liang
- Pushmeet Kohli
In Program Analysis & Verification
- Eric Wong
- J. Kolter
- Huan Zhang
- Suman Sekhar Jana
- Shiqi Wang
- Cho-Jui Hsieh
- Timon Gehr
- Clark W. Barrett
Citations in the corpus
- Efficient Formal Safety Analysis of Neural Networks (2018, methodology): “We build upon two prior works [7, 28] on using interval analysis and linear relaxations for analyzing neural networks.”
- Training verified learners with learned verifiers (2018, neutral): “Algorithms based on formal verification [7, 10, 14] and mixed integer programming [9, 27] have been proposed to solve this problem for networks with piecewise linear activation functions (like ReLUs and maxpooling).”
- Formal Security Analysis of Neural Networks using Symbolic Intervals (2018, background): “Recently, several projects [12, 21, 25] have used customized SMT solvers for verifying security properties of DNNs, such However, such techniques are mostly limited by the scalability of the solver.”
- 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…”
- Provable defenses against adversarial examples via the convex outer adversarial polytope (2017, methodology): “The PLANET solver [Ehlers, 2017] uses a similar high level idea, but also combines a satisfiability solver with a convex approximation of the ReLU nonlinearities (at the level of a single ReLU unit, it is the same outer bound as used in this work, though the nature of our full outer bound is…”
- Reachability Analysis of Deep Neural Networks with Provable Guarantees (2018, methodology): “However, the other tools (Reluplex, Planet, MIP, BaB) can only work with hundreds of neurons.”
- Scaling provable adversarial defenses (2018, background): “…(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, Cheng et al., 2017].”
- A Dual Approach to Scalable Verification of Deep Networks (2018, methodology): “If each h is a ReLU function, then (7) is equivalent to the dual of the LP described in Ehlers [2017].”
- Ground-Truth Adversarial Examples (2017, background): “In recent years, new techniques have been proposed for the formal verification of neural networks [4, 9, 12, 17, 18].”
- On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models (2018, methodology): “L G made: from complete methods that use Satisfiability Modulo Theory (SMT) [4, 8, 11] or MixedInteger Programming (MIP) [1, 5, 17] to incomplete methods that rely on solving a convex relaxation of the verification problem [6, 7, 9, 15, 18, 19, 20].”
- Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers (2019, methodology): “Exact methods, usually based on Satisfiability Modulo Theories solvers [18, 11] or mixed integer linear programming [33, 24, 12], are guaranteed to find an adversarial example around a datapoint if it exists.”
- Semidefinite relaxations for certifying robustness to adversarial examples (2018, methodology): “2 which forms the basis for several existing works on scalable certification [9, 10, 28, 29].”
- Towards Fast Computation of Certified Robustness for ReLU Networks (2018, methodology): “Similarly, (Ehlers, 2017) proposed Planet, another splitting-based approach using satisfiability (SAT) solvers.”
- Toward Scalable Verification for Safety-Critical Deep Networks (2018, background): “For example, some of the more successful verification efforts thus far [3, 8] have focused on piecewise-linear activation functions, such as ReLUs or max-pooling layers, while attempts to verify networks with sigmoid activation functions have proved far less scalable.”
- DeepSafe: A Data-driven Approach for Checking Adversarial Robustness in Neural Networks (2017, methodology): “Traditional verification techniques often cannot directly be applied to neural networks, and this has sparked a line of work focused on transforming the problem into a format more amenable to existing tools such as LP and SMT solvers [4, 8, 18, 19].”
- A Statistical Approach to Assessing Neural Network Robustness (2018, methodology): “We used the COLLISIONDETECTION dataset introduced in the formal verification literature by (Ehlers, 2017).”
- Provably Minimally-Distorted Adversarial Examples (2017, methodology): “…deep neural networks as controllers in safety-critical systems (Ju-lian et al., 2016; Bojarski et al., 2016) has sparked an interest in developing techniques for verifying that they satisfy various properties (Pulina and Tacchella, 2010; 2012; Huang et al., 2016; Ehlers, 2017; Katz et al., 2017b).”
- Training for Faster Adversarial Robustness Verification via Inducing ReLU Stability (2018, methodology): “Exact verification of networks has been the subject of many recent works [15, 9, 3, 30, 19, 6].”
- Fast and Stable Interval Bounds Propagation for Training Verifiably Robust Models (2019, background): “Since then, numerous attacks and defenses have followed Papernot et al. [2016], Moosavi-Dezfooli et al.”