Maximum Resilience of Artificial Neural Networks

By Chih-Hong Cheng, Georg Nührenberg, Harald Ruess. 2017

304 citations recorded by the source corpus.

The deployment of Artificial Neural Networks (ANNs) in safety-critical applications poses a number of new verification and certification challenges. In particular, for ANN-enabled self-driving vehicles it is important to establish properties about the resilience of ANNs to noisy or even maliciously manipulated sensory input. We are addressing these challenges by defining resilience properties of ANN-based classifiers as the maximal amount of input or sensor perturbation which is still tolerated. This problem of computing maximal perturbation bounds for ANNs is then reduced to solving mixed integer optimization problems (MIP). A number of MIP encoding heuristics are developed for drastically reducing MIP-solver runtimes, and using parallelization of MIP-solvers results in an almost linear speed-up in the number (up to a certain limit) of computing cores in our experiments. We demonstrate the effectiveness and scalability of our approach by means of computing maximal resilience bounds for a number of ANN benchmark sets ranging from typical image recognition scenarios to the autonomous maneuvering of robots.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Electrical and Electronic Engineering

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 Computer Vision and Pattern Recognition

In Electrical and Electronic Engineering

Citations in the corpus

Certified Adversarial Robustness via Randomized Smoothing (2019, methodology): “, 2017) or mixed integer linear programming (Cheng et al., 2017; Lomuscio & Maganti, 2017; Dutta et al., 2017; Fischetti & Jo, 2018; Bunel et al., 2018).”
Provable defenses against adversarial examples via the convex outer adversarial polytope (2017, neutral): “, 2017) or integer programming approaches (Lomuscio & Maganti, 2017; Tjeng & Tedrake, 2017; Cheng et al., 2017).”
Scaling provable adversarial defenses (2018, background): “In contrast, the previous best verified robust error for this , from [Dvijotham et al., 2018], was 80%. While the robust error is naturally substantially higher for = 8/255 (the amount typically considered in empirical works), we are still able to achieve 71% provable robust error; for comparison, t”
A Dual Approach to Scalable Verification of Deep Networks (2018, background): “More recently, researchers have proposed a set of approaches that make use of branch and bound algorithms either directly or via mixed-integer programming solvers [Bunel et al., 2017, Cheng et al., 2017, Tjeng and Tedrake, 2017].”
On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models (2018, methodology): “However, when running a complete solver (using a MIP formulation), we are able to ﬁnd a counter-example that successfully induces the model to misclassify the “eight” as a “two” (as shown in Figure 6c).”
Towards Fast Computation of Certified Robustness for ReLU Networks (2018, methodology): “For ReLU networks, the verification problem can be transformed into a Mixed Integer Linear Programming (MILP) problem (Lomuscio & Maganti, 2017; Cheng et al., 2017; Fischetti & Jo, 2017) by using binary variables to encode the states of ReLU activation in each neuron.”
Bounding and Counting Linear Regions of Deep Neural Networks (2017, methodology): “For example, Cheng et al. (2017) use another mixed-integer formulation to generate adversarial examples.”
Exactly Computing the Local Lipschitz Constant of ReLU Networks (2020, methodology): “There is a deep body of work using mixed-integer programming to verify the robustness of a neural network (Lomuscio & Maganti, 2017; Fischetti & Jo, 2018; Tjeng et al., 2017; Dutta et al., 2017; Cheng et al., 2017; Xiao et al., 2018).”
Optimization Models for Machine Learning: A Survey (2019, methodology): “MixedInteger Programming (MIP) models for regression and classification tasks are also investigated in [32].”
NATTACK: Learning the Distributions of Adversarial Examples for an Improved Black-Box Attack on Deep Neural Networks (2019, background): “The problem can be converted to a mixed integer linear programming problem for the DNNs with RELU activation (Lomuscio & Maganti, 2017; Cheng et al., 2017; Fischetti & Jo, 2017).”
CAQL: Continuous Action Q-Learning (2019, methodology): “Versions of this MIP model have been used in neural network verification (Cheng et al., 2017; Lomuscio & Maganti, 2017; Bunel et al., 2018; Dutta et al., 2018; Fischetti & Jo, 2018; Anderson et al., 2019; Tjeng et al., 2019) and analysis (Serra et al.”
Efficient Neural Network Robustness Certification with General Activation Functions (2018, methodology): “For ReLU networks, finding the minimum adversarial distortion can be cast as a mixed integer linear programming (MILP) problem [21, 22, 23].”
Evaluating Robustness of Neural Networks with Mixed Integer Programming (2017, methodology): “We used two procedures (in increasing order of speed) to determine bounds: LINEAR PROGRAMMING (LP), and INTERVAL ARITHMETIC (IA), also used in [10, 12, 28].”
Deep neural networks and mixed integer linear optimization (2018, methodology): “We recently became aware that a 0-1 MILP model similar to the one studied in the present paper, has been independently proposed (almost at the same time) in [2, 13, 15].”
Training for Faster Adversarial Robustness Verification via Inducing ReLU Stability (2018, methodology): “Exact verification of networks has been the subject of many recent works (Katz et al., 2017; Ehlers, 2017; Carlini et al., 2017; Tjeng et al., 2017; Lomuscio and Maganti, 2017; Cheng et al., 2017a).”
Provable Certificates for Adversarial Examples: Fitting a Ball in the Union of Polytopes (2019, methodology): “Binary networks were trained to distinguish a subset of 1’s and 7’s from the full MNIST dataset.”