Formal Security Analysis of Neural Networks using Symbolic Intervals
By Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, Suman Sekhar Jana. 2018
532 citations recorded by the source corpus.
Due to the increasing deployment of Deep Neural Networks (DNNs) in real-world security-critical domains including autonomous vehicles and collision avoidance systems, formally checking security properties of DNNs, especially under different attacker capabilities, is becoming crucial. Most existing security testing techniques for DNNs try to find adversarial examples without providing any formal security guarantees about the non-existence of such adversarial examples. Recently, several projects have used different types of Satisfiability Modulo Theory (SMT) solvers to formally check security properties of DNNs. However, all of these approaches are limited by the high overhead caused by the solver. In this paper, we present a new direction for formally checking security properties of DNNs without using SMT solvers. Instead, we leverage interval arithmetic to compute rigorous bounds on the DNN outputs. Our approach, unlike existing solver-based approaches, is easily parallelizable. We further present symbolic interval analysis along with several other optimizations to minimize overestimations of output bounds. We design, implement, and evaluate our approach as part of ReluVal, a system for formally checking security properties of Relu-based DNNs. Our extensive empirical results show that ReluVal outperforms Reluplex, a state-of-the-art solver-based system, by 200 times on average. On a single 8-core machine without GPUs, within 4 hours, ReluVal is able to verify a security property that Reluplex deemed inconclusive due to timeout after running for more than 5 days. Our experiments demonstrate that symbolic interval analysis is a promising new direction towards rigorously analyzing different security properties of DNNs.
Subfields: Artificial Intelligence, Software, Safety, Robustness & Interpretability, Program Analysis & Verification, Signal Processing
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
- Cho-Jui Hsieh
- Huan Zhang
- Pushmeet Kohli
- J. Kolter
- Mohit Bansal
- Suman Sekhar Jana
- Sven Gowal
In Software
- Suman Sekhar Jana
- Huan Zhang
- Cho-Jui Hsieh
- Gagandeep Singh
- Markus Püschel
- Shiqi Wang
- Baishakhi Ray
- Pushmeet Kohli
In Safety, Robustness & Interpretability
- Huan Zhang
- Cho-Jui Hsieh
- Suman Sekhar Jana
- Shiqi Wang
- Pushmeet Kohli
- Sven Gowal
- Timon Gehr
- Clark W. Barrett
In Program Analysis & Verification
- Huan Zhang
- Suman Sekhar Jana
- Shiqi Wang
- Cho-Jui Hsieh
- Gagandeep Singh
- Markus Püschel
- Pushmeet Kohli
- Timon Gehr
In Signal Processing
- Suman Sekhar Jana
- Sven Gowal
- Shiqi Wang
- Kexin Pei
- Timothy A. Mann
- Junfeng Yang
- Justin Whitehouse
- Clark W. Barrett
Citations in the corpus
- Certified Robustness to Adversarial Examples with Differential Privacy (2018, background): “Second, several works seek to formally verify [26], [30], [61], [62], [15], [20], [58] or lower bound [49], [63] the robustness of pre-trained ML models against adversarial attacks.”
- Efficient Formal Safety Analysis of Neural Networks (2018, methodology): “It is comparably small and only has five input features so that ReluVal [39] can efficiently check different safety properties.”
- On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models (2018, methodology): “Substantial progress has been made: from complete methods that use Satisfiability Modulo Theory (SMT) [14–16] or Mixed-Integer Programming (MIP) [13, 17, 18] to incomplete methods that rely on solving a convex relaxation of the verification problem [19–26].”
- The Marabou Framework for Verification and Analysis of Deep Neural Networks (2019, methodology): “The formal methods community has taken initial steps in this direction, by developing algorithms and tools for neural network verification [5,9,10,12,18,20,23,24].”
- Achieving Verified Robustness to Symbol Substitutions via Interval Bound Propagation (2019, methodology): “…Mixed-Integer Programming (MIP) (Bunel et al., 2017; Cheng et al., 2017) or Satisfiability Modulo Theory (SMT) (Katz et al., 2017; Carlini et al., 2017), and incomplete methods that solve a convex relaxation of the verification problem (Weng et al., 2018; Wong and Kolter, 2018; Wang et al., 2018).”
- Software Engineering for AI-Based Systems: A Survey (2021, background): “Five papers focus on formal model analysis with different goals: analysis of safety and scalability in models for autonomous vehicles [183], quantitative analysis for systems based on recurrent neural networks [49], improvement and certification of robustness for ML models [220], and approaches for ”
- MixTrain: Scalable Training of Formally Robust Neural Networks (2018, methodology): “To solve such problem, sound approximations successfully simplify the verification problem with traditional analysis methods like interval [7], convex polytope [26], abstract domain [28], Lagrangian relaxation [29] and Lipschitz continuous [65], [30].”
- Fast and Effective Robustness Certification (2018, methodology): “Complete verifiers do not have false positives but have limited scalability as they are based on computationally expensive methods such as SMT solving [14, 8], mixed integer linear programming [27] or input refinement [28].”
- Algorithms for Verifying Deep Neural Networks (2019, methodology): “1 ReluVal ReluVal [40] takes a hyperrectangle input set |x − x0| ≤ r and any output set that implements the abstract polytope type.”
- Provable Certificates for Adversarial Examples: Fitting a Ball in the Union of Polytopes (2019, background): “An equivalent formulation of this problem is providing overestimations on the range of neural nets, for which interval arithmetic has been shown useful [23, 24].”
- Metric Learning for Adversarial Robustness (2019, background): “This degradation raises serious concern — especially when we deploy deep networks to safety and reliability critical applications [29, 43, 41, 20, 36].”
- Model Agnostic Defence Against Backdoor Attacks in Machine Learning (2019, methodology): “ReluVal [28] uses interval arithmetic [15] to estimate a DNN’s decision boundary by calculating tight bounds on the output of a model”
- An abstract domain for certifying neural networks (2019, background): “…verifiers are based on SMT solving [Ehlers 2017; Katz et al. 2017], mixed integer linear programming [Tjeng and Tedrake 2017] or input refinement [Wang et al. 2018] whereas existing incomplete verifiers are based on duality [Dvijotham et al. 2018; Raghunathan et al. 2018], abstract…”
- Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Neural Network Robustness Verification (2021, background): “Besides branching on ReLU neurons, input domain branching was also considered in [41, 29, 1] but limited by input dimensions [8].”