Exploiting Verified Neural Networks via Floating Point Numerical Error
Authors: Kai Jia
Martin Rinard
Venue:  (2021)

Abstract: Motivated by the need to reliably characterize the robustness of deep neural networks, researchers have developed verification algorithms for deep neural networks. Given a neural network, the verifiers aim to answer whether certain properties are guaranteed with respect to all inputs in a space. However, little attention has been paid to floating point numerical error in neural network verification.

We exploit floating point errors in the inference and verification implementations to construct adversarial examples for neural networks that a verifier claims to be robust with respect to certain inputs. We argue that, to produce sound verification results, any verification system must accurately (or conservatively) model the effects of any float point computations in the network inference or verification system.

Under review as a conference paper at ICLR 2021
EXPLOITING VERIFIED NEURAL NETWORKS VIA FLOATING POINT NUMERICAL ERROR
Anonymous authors Paper under double-blind review
ABSTRACT
Motivated by the need to reliably characterize the robustness of deep neural net- works, researchers have developed verification algorithms for deep neural net- works. Given a neural network, the verifiers aim to answer whether certain prop- erties are guaranteed with respect to all imputs space. However, little attention has been paid to floating point numerical error in neural network verification.
We exploit floating point enrors in the inference and verification implementations to construct adversarial examples for neural networks that a verifier claims to be robust with respect certain inputs. We argue that, produce sound verifica- tion results, any verification system must accurately (or conservatively) model the effects of any float point computations in the network inference or verification system.
INTRODUCTION
Deep neural networks (DNNs) are known to be vulnerable to adversarial inputs (Szegedy et al, 2014), which are images, audio, or texts indistinguishable human perception that cause DNN to give substantially different results. This situation has motivated the development of network verification algorithms that claim to prove the robustness of a network (Bunel al., 2020 Tieng et al. 2019 Salman et al., 2019). specifically that the network produces identical classifications for all inputs a perturbation space around given input.
Verification algorithms typically reason about the behavior of the network assuming real-valued arithmetic. In practice, however, the computation of both the verifier and the neural network is performed on physical computers that use floating point numbers and floating point arithmetic to approximate the underlying real-valued computations. This use of floating point introduces numeri- cal error that can potentially invalidate the guarantees that the verifiers claim provide. Moreover, the existence of multiple software and hardware systems for DNN inference further complicates the situation, because different implementations exhibit different numerical error characteristics.
We present concrete instances where numerical error leads to unsound verification of real-valued networks. Specifically, train robust networks the MNIST and CIFAR10 datasets. We work with the MIPVeriFF complete verifier (Tjeng et al. 2019) and several inference implementations included in the PyTorch (Paszke et al. 2019) framework. For each implementation, we construct image pairs (æo, Fadv) where 2o is a brightness modified natural image, such that the implemen- tation classifies Fadv differently from æog Fadv falls in -bounded perturbation space around Zo. and the verifier incorrectly claims that no such adversarial image &adv exists for Do within the perturbation space. Moreover, we show that the incomplete verifier CROWN is also vulnerable to floating point error. Our method of constructing adversarial images is not limited to our setting, and is applicable other verifiers that do not soundly model floating point arithmetic.
BACKGROUND AND RELATED WORK
Training robust networks: Researchers have developed various techniques to train robust net- works (Madry et al. 2018; Mirman et al. 2018 Tramer & Boneh 2019 Wong et al. 2020). Madry et al. formulate the robust training problem as minimizing the worst loss within the input perturba- tion and propose train robust networks the data generated by the Projected Gradient Descent

---

Under review as a conference paper at ICLR 2021
(PGD) adversary (Madry et al. 2018). In this work we consider robust networks trained with the PGD adversary.
The goal of complete verification (a.k.a. exact verification) methods is to either prove the property being verified or provide counterexample to disprove Complete verification approaches have formulated the verification problem as Satisfiability Modulo Theo-
Complete verification:
ries (SMT) problem (Scheibler et al. 2015 Huang et al. 2017 Katz et al., 2017, Ehlers, 2017]
Bunel et al. 2020) or Mixed Integer Linear Programming (MILP) problem (Lomuscio & Ma- 2017 Fischetti Jo 2018 Dutta et al. 2018: Tjeng et al. al.] 2019). While
ganti 2017 Cheng et al.
SMT solvers are able to model exact floating point arithmetic (Rümmer & Wahl 2010) exact
real arithmetic (Corzilius et al.) 2012), deployed SMT solvers for verifying neural networks all use
inexact floating point arithmetic reason about the neural network inference for efficiency reasons. MILP solvers work directly with floating point, do not attempt to exactly model real arithmetic, and therefore exhibit numerical error. Since floating point arithmetic is not associative, different neu- ral network implementations may produce different results for the same neural network, implying that any sound verifier for this class of networks must reason about the specific floating point error characteristics of the neural network implementation at hand. To the best of our knowledge, no prior work formally recognizes the problem of floating point error in neural network complete verification or exploits floating point error to invalidate verification results.
Incomplete verification: On the spectrum of the tradeoff between completeness and scalability, incomplete methods (a.k.a. certification methods) aspire to deliver more scalable verification by adopting over-approximation, while admitting the inability to either prove or disprove the properties
in certain cases. There is a large body of related research (Wong & Kolter [017 Weng et al. 2018
Gehr et al. 2018 Zhang et al. 2018 Raghunathan et al. Dvijothm et MMrmmnn al. 2018 Singh et al.) 2019). Salman et al. (2019) has unitied most of the relaxation methods under common convex relaxation framework. Their results suggest that there is an inherent barrier to tight verification via layer-wise convex relaxation captured by their framework. We highlight that floating point error of implementations that use a direct dot product formulation has been accounted for in some certification frameworks (Singh et al., 2018 2019) by maintaining upper and lower rounding bounds for sound floating point arithmetic (Miné 2004). Such frameworks should be extensible to model numerical error in more sophisticated implementations like the Winograd convolution (Lavin) & Gray| 2016). but the effectiveness of this extension remains to be studied. Most of the certification algorithms, however, have not considered floating point error and may be vulnerable to attacks that exploit this deficiency.
Floating point arithmetic: Floating point is widely adopted an approximate representation of real numbers in digital computers. After each calculation, the result rounded to the nearest repre- sentable value, which induces roundoff error. In the field of neural networks, the SMT- verifier Reluplex (Katz et al. (2117) has been observed to produce false adversarial examples due to floating point error (Wang et al. 2018). The MILP--aseed verifier MIPVerify (Tjeng al.! 2019) has been observed to give NaN results when verifying pruned neural networks (Guidotti et al. 2020). Such observed floating point unsoundness behavior occurs unexpectedly in running large scale bench- marks. However, no prior work tries to systematically invalidate neural network verification results via exploiting floating point error.
The IEEE-754 (EEE, 2008) standard defines the semantics of operations and correct rounding be- havior. On an IEEE- 754 compliant implementation, computing floating point expressions consisting of multiple steps that are equivalent in the real domain may result in different final roundoff error because rounding is performed after each step, which complicates the error analysis. Research on estimating floating point roundoff error and verifying floating point programs has a long history and is actively growing (Boldo & Melquiond 2017), but we are unaware of any attempt to apply these tools to obtain sound verifier for any neural network inference implementation. Any such verifier must reason soundly about floating point errors in both the verifier and the neural network inference algorithm. The failure to incorporate floating point error in software systems has caused real-worle disasters. For example, in 1992 a Patriot missile missed its target and lead to casualties due to floating point roundoff emrr related to time calculation (Skeel 1992).
2

---

Under review as a conference paper at ICLR 2021
3 PROBLEM DEFINITION
3.1 ADVERSARIAL ROBUSTNESS OF NEURAL NETWORKS
We consider 2D image classification problems. Let y NN (æ; W) denote the classification confidence given by neural network with weight parameters W for an input æ, where æ E [0.1]] R an image with m rows and n columns of pixels each containing e color channels represented by floating point values in the range [0, 1J, and IR* is logits vector containing the classification scores for each of the classes. The class with the highest score is the classification result of the neural network.
For a logits vector y and a target class number i, we define the Carlini-Wagner (CW) loss (Carlini & Wagner 2017 as the score of the target class subtracted by the maximal score of the other classes:
Lew (y, t) = Vt max t
(1)
Note that i classified as an instance of class if and only Lew (NN (ar; W); () > 0, assuming no equal scores of two classes.
Adversarial robustness of neural network is defined for an input zo and a perturbation bound e, such that the classification result is stable within allowed perturbations:
Vo E Adv, (æo) Lew (NN (æ; W), 1o) > 0
(2)
where to argmax NN (æo; W)
In this work we focus on -nom bounded perturbations:
Adv. (zo) = {x || - zolloc S < A min 2 A max x 1}
(3)
3.2 FINDING ADVERSARIAL EXAMPLES FOR VERIFIED NETWORKS VIA EXPLOITING NUMERICAL ERROR
Due to the inevitable presence of numerical eтror in both the network inference system and the verifier, the exact specification of NN (-: W) (i.e., a bit-level accurate description of the under- lying computation) is not clearly defined in (2) We consider the following implementations of convolutional layers included the PyTorch framework to serve as our candidate definitions convolutional layers in NN (c; W), and other layers use the default PyTorch implementation:
NNc.M (<; W): A matrix multiplication based implementation on x86/64 CPUs. The con- volution kernel is copied into a matrix that describes the dot product be applied on the flattened input for each output value.
NNc.c (<; W): The default convolution implementation on x86/64 CPUs.
NNG.M (:: W): A matrix multiplication based implementation on NVIDIA GPUs.
NNo.c (5 W): A convolution implementation using the IMPLICIT_GENS algorithm from the cuDNN library (Chetlur et al. 2014) on NVIDIA GPUs.
NNG,cwG (+: W): A convolution implementation using the WINOGRAD IETOGRAD_NONFUUSS NONFUSED al- gorithm from the cuDNN library (Chetlur et al.) (0144) on NVIDIA GPUs. It is based on the Winograd fast convolution algorithm (Lavin & Gray 2016), which has much higher numerical error compared others.
For given implementation NN (+: W), our method finds pairs of (æo. Tadv) represented as single precision floating point numbers such that
1. To and Fadv in the dynamic range of images: min 20 2 0, min Fadv 2 max Do S
1, and max Badv < 1.
2. Wadv falls in the perturbation space of wo: ||aadv - xolloc S
3. The verifier claims that (2) holds for mo
4. Bady is adversarial image for the implementation: Lew (NNimpt (Fndv; W), (0)
3

---

Under review as a conference paper at ICLR 2021
Note that the first two conditions are accurately defined for any implementation compliant with the 1EEE-754 standard, because the computation only involves element- wise subtraction and max- reduction that incur accumulated error. The Gurobi (Gurobi Optimization 2020) solver used by MTPVeri fy operates with double precision internally. Therefore, to ensure that our adversarial examples satisfy the constraints considered by the solver, also require that the first two conditions hold for adv float64 (Iadv) and vi = float64 (zo) that are double precision representations of Tadv and Zo.
3.3 MILP FORMULATION FOR COMPLETE VERIFICATION
We adopt the small CNN architecture from Xiao et al. 2019) and the MIPVeri fy complete verifier of TTeng et al. (2019) to demonstrate our attack method. We can also deploy our method against other complete verifiers long the property being verified involves thresholding continuous variables whose floating point arithmetic is not exactly modeled in the verification process.
The MIPVerifi fy verifier formulates the verification problem as an MILP problem for networks composed of linear transformations and piecewise-lineal functions (Tieng et al.) 2019). An MILP problem optimizes linear objective function subject linear equality and linear inequality con- straints over a set of variables, where some variables take real values while others are restricted to be integers. The MILP formulation of the robustness of a neural network involves three parts: intro- ducing free variable x: for the adversarial input subject to the constraint x: E Adv, (Eo), formulating the computation y = NN (æ: W), and formulating the attack goal Lew (NN (æ; W), to) S 0. The network is robust with respect to zo if the MILP problem is infeasible, and æ serves sarial image otherwise. The MILP problem typically optimizes one of the two objective functions: (i) min ||æ æollos to find adversarial image closest to æ, (ii) min Lew (NN (x: W). to) to find an adversarial image that causes the network to produce a different prediction with the highest confidence. Note that although the above constraints and objective functions are nonlinear, most modern MILP solvers can handle them by automatically introducing necessary auxiliary decision variables to convert them into linear forms.
adver-
4 EXPLOITING A COMPLETE VERIFIER
4.1 EMPIRICAL CHARACTERIZATION IMPLEMENTATION NUMERICAL ERROR
To guide the design of our attack algorithm we present statistics about numerical error of different implementations.
To investigate end-to-end error behavior, we select an image x and present in Figure Ta a plot of ||NN (a: + 5; W) NN (æ:; W)l against - 10-6 5 < 10-6, where the addition of only applied on the single imput element that has the largest gradient magnitude. To minimize the effect of numerical instability due to nonlinearity in the network and focus on fluctuations caused by numerical eтror, the image æ is chosen to be the first MNIST test image on which the network produces a verified robust prediction. We have also checked that the pre-activation values of all the ReLU units do not switch sign. We observe that the change of the logits vector is highly nonlinear with respect to the change of the input, and small perturbation could result in a large fluctuation. The MENNOGADD_OOOEE NONFUSED algorithm on NVIDIA GPU is much more unstable and its variation is two orders of magnitude larger than the others.
is
We also evaluate all of the implementations the first layer (i.c., with only one linear transformation applied to the input) against that NN CN and present the histogram in Figure 1b] It is clear that different implementations usually manifest different error behavior, and again CwG induces much higher numerical error than others.
the whole MNIST test set and compare the outputs of
These observations inspire to construct adversarial images for each implementation independently by applying small random perturbations on an image close to the robustness decision boundary. We present the details of our method in /Section 4.2
4

---

Under review as a conference paper at ICLR 2021
16-4
15 18-4
0.0
03
1646
10-1
16-4
10-3
Mi.
M42 -N
VA26 NNPU
1.0
0.9
0.
12
16-6
16-18
In -X1-
10-4
Mmp
Pobaaby
Podeddy
16:0
Vvl
16:7
12-
(a) Change of logits vector due to small single-clement input perturbations for different implementations. The
(b) Distribution of difference relative to NNc.M of first layer evaluated on MNIST test images. This plot shows that different implementations usually exhibit
dashed lines are change of output is nonlinear with respect input changes, the magnitude of output changes usu- ally larger than that of input changes. The changes are due to floating point error rather than network nonlin- earity because all the pre-activation values of ReLU units do not switch sign.
1ö). This plot shows that the
different floating point characteristics.
Figure I: Empirical characterization of numerical error of different implementations
Fluctustion due to numerical error
quasi-adversarial:
aacarsariall:
X
Adjusting brightiiess
Decision boundary assumed by the verifier
Safe image: *eass
quasi-safe: %
Decision boundary the implementation
Perturbation space
Perturbation
space
Figure 2: Illustration of our method. Since the verifier does not model the floating point arith- metic details of the implementation, their decision boundaries for the classification problem diverge, which allows Note that the verifier usually does not comply with a well defined specification of NN (+; W), and therefore it does not define decision boundary. The dashed boundary in the diagram is just for illustrative purposes.
to find adversarial inputs by crossing the boundary via numerical error fluctuations.
4.2 CONSTRUCTING ADVERSARIAL EXAMPLES
Given a network and weights NN (+: W), there exist image pairs (xo, x1) such that the network verifiably robust with respect Co, while æ1 Adv, (æo) and Lew (NN (æ1; W). : to) is less than the numerical fluctuation introduced by tiny input perturbations. We call Zg a quasi-safe image and 2i the corresponding anasi-adversaria image. We then apply small random perturbations the quasi-adversarial image to obtain an adversarial image. The process is illustrated in Figure 2
We propose the following proposition for more formal and detailed description:

---

Under review as a conference paper at ICLR 2021
Proposition 1. Let E >> 0 be arbitrarily small positive number. If a continuous neural network NN (+; W) can produce a verifiably robust classification for class t, and it does not constantly classify all inputs as class then there exists input ao such that
min Lew (NN (æ: W) 1) rEAdv, (mo)
Let æ1 = -aagamnnneaaa EeAv, (mo) Lew (NN (z; W), t) be the minimizer of the above function. We call 2t a quasi-safe image und 11 a quasi-adversarial image.
(x) Lew (NN (ar; W); t). Since f()) is composed of continuous functions, f(-) is continuous. Suppose NN (-; W) is verifiably robust with respect to 24 that belongs to class t. Let x- be be any input such that Lew (NN (x_: W), t) < 0. which exists because NN (+; W) does not constantly classify all inputs as class t. We have f(++) > 0 and f(x-) < 0, and therefore zo exists such that 0 < f f(ro) < E due to continuity.
Proof. Let (ax)
Our method works by choosing E be number smaller than the average fluctuation of logits vector introduced by tiny input perturbations as indicated in Figure 1a and finding a quasi-safe image by adjusting the brightness of a natural image. An adversarial image then likely to be obtained by applying random perturbations on the corresponding quasi-adversarial image.
Given a particular implementation NN (-; W) and a natural image 3seed which the network robustly classifies as class to according to the verifier, we construct an adversarial input pair (xo. Tadv) that meets the constraints described in Section 3.2 in three steps:
1. We search for coefficient a E [0, 1] such that zo o.Eaeed serves as the quasi-safe image. Specifically, we require the verifier to claim that the network is robust for seed but not so for (a 8)es with 8 being small positive value. Although the function is not guaranteed to be monotone, we can still use a binary search to find a while minimizing 5 because we only need one such value. However, solver becomes extremely slow for small 5 values, so we start with a binary search and switch grid search if the solver exceeds time limit. We set the target of á to be 1e-7 in our experiments and divide the best known d to 16 intervals if grid search is needed.
observe that in many cases the MILP
2. We search for the quasi-adversarial image Øi corresponding to Tg- We define a loss func- tion with tolerance of T as L(x, W, (o) == Lew (NN (æ;; W), (o) T, which can be incorporated in any verifier by modifying the bias of the Softmax layer. We aim to find which is the minimal confidence of all images in the perturbation space of wo and TI which is slightly larger than Tu with œ1 being the corresponding adversarial image:
Va E Adv. (xo) L(zo, To: W, to) > 0 21 Adv, (xo)
L( Ti; W, (n) < 0
T1 TD 1e-7
Note that 11 is produced by the complete verifier as proof for nonrobustness given the tolerance T1. The above values are found via a binary search with initialization To +- and 7i f- Tiax where Tmax == Lew (NN (zo; W), fo). If the verifier is able to compute the worst objective Tu = (mo) Lew (NN (æ:; W), tu), the binary search can be accelerated by initializing Tu <- Tw - 8₂ and TI Tu + 8g. We empirically set 8, 3e 6 to incorporate the numerical error in the verifier so that L(æ0. To da; W, lo) >> 0 and L( Tur 8,; W, ()) O. The binary search is aborted if the solver times out.
3. We minimize Lew (NN (æ1: W). . to) with hill climbing via applying small random per- turbations on the quasi-adversarial image 24 while projecting back to Adv, (æo) to find an adversarial example. The perturbations are applied on patches of æı, described in Ap- pendix A) The random perturbations are on the scale of 2e-7, corresponding to the input perturbations that cause a change in Figure la
4.3 EXPERIMENTS
We conduct our experiments on a workstation equipped with two GPUs (NVIDIA Titan RTX and NVIDIA GeForce RTX 2070 SUPER), 128 GiB of RAM and an AMD Ryzen Threadripper 2970WX

---

Under review as a conference paper at ICLR 2021
Table Number of successful adversarial attacks for different neural network implementations. The number of auasi-adversarial images in the first column corresponds to the cases where the solver does not time out the initialization step. For each implementation, we try find adversarial images by applying random perturbations on each quasi-adversarial image and report the number of successfully found adversarial images here.
#quasi-adv #tested
NNC.M
NNc,c
NNG.M
NNg.c
NNG,cwG
MNIST CIFARIO
18 /8/2 32 26 32
2
3
1
16
12
7
25
verified robust 7 2.5
NNc. 2
NNc.c
NNG. 2
NNg.c
NNg cws 2
2
-.BB-37
Low*-1.2e-00
Low Lcw--2.4e-01
Lew Sly=-8.9e-0
7
airplane 0.5
horse Low 5e-06
horse
horse
horse
1-.Be-8
Lcy=-115e-06
Lcw--3.5e-06
7cw--700e-04
horse
deer Low 1. .2-066
deer Low
deer Lcw
deer - 2.4e--0
Lcw
-ow 11.6-006
-c2--712 .2
Figure 3: The quasi-safe images with respect which all implementations successfully attacked, and corresponding adversarial images
24-core processor. We train the small architecture from Xiao et al. (2099) with the PGD adversary and the RS Loss MNIST and CIFAR10 datasets. The trained networks achieve 94.63% and 44.73% provable robustness with perturbations of & norm bounded by 0.1 and 2/255 on the two datasets respectively, similar the results reported in Xiao al. (2019). Our code will be made publicly available after the review process.
Although method only needs ( log <) invocations of the verifier where is the gap in the binary search, the verifier is too slow to run large benchmark in reasonable time. Therefore, for each dataset we only test our method on 32 images randomly sampled from the verifiably robustly classified test images. The time limit of MILP solving is 360 seconds. Out of these 32 images, we have successfully found quasi- avver-adversrrial images (æ1 from [Section 4.2) Step where failed cases are solver timeouts) for 18 images MNIST and 26 images on CIFAR 10. We apply random perturbations these quasi-adversarial images to obtain adversarial images within the perturbation range of the quasi-safe image (æo = af'eeed from [Section 4.2) Step 1). All the implementations that we have considered are successfully attacked. We present the detailed numbers in Table I We also present in Figure 3 the quasi-safe images which our attack method succeeds for all implementations and the corresponding adversarial images.
5 EXPLOITING AN INCOMPLETE VERIFIER
The relaxation adopted in certification methods renders them incomplete but also makes their ver- ification claims more robust to floating point eтror compared to complete verifiers. In particular, evaluate the CROWN framework (Zhang al. 2018) randomly selected test images and

---

Under review as a conference paper at ICLR 2021
CROWN is able to verify the robustness of the network on 29 out the 32 original test images, but is unable to prove the robustness for any of the quasi-safe images. Note that MIPVeri fy claims that the network is robust with respect to all the original test images and corresponding quasi-safe images.
corresponding quasi-safe images from Section 4.3
Given the above situation, demonstrate that incomplete verifiers still prone to floating point emro. We build a neural network that takes a 13 x 13 single-channel input image, followed by a 5 5 convolutional layer with a single output channel, two fully connected layers with 16 output neurons each, fully connected layer with one output neuron denoted as w max W h. + bu, 0), and final linear layer that computes y [u, 1c 7] as the logits vector. All the hidden layers have ReLU activation. The imput To is taken from Gaussian distribution. The hidden layers have random Gaussian coefficients, and the biases are chosen so that (i) the ReL.U neurons before u are always activated for inputs in the perturbation space of Zo. (ii) u 0 always holds for these inputs, and (iii) by is maximized with all other parameters fixed. CROWN able to prove that all ReLU neurons before are always activated but is never activated, and therefore it claims that the network is robust with respect to perturbations around zo. However, by initializing the quasi-adversarial input 21 < Zo + sign (W eequiv) where W Weguie is the product of all the coefficient matrices of the layers up to u, we successfully find adversarial inputs for all the five implementations considered in this work by randomly perturbing 21 in way similar to Step 3 of Section 4.2
6 DISCUSSION
We agree with the security expert Window Snyder, "One single vulnerability is all an attacker needs". Unfortunately, most previous work neural network verification abstains from discussing possible vulnerabilities in their methods. We have demonstrated that neural network verifiers, although meant provide security guarantees, are systematically exploitable. The underlying tradeoff between soundness and scalability in the verification of floating point programs is fundamental but has not received enough attention in the neural network verification literature.
One appealing remedy is to introduce floating point error relaxations into complete verifiers, such as by verifying for a larger c or setting a threshold for accepted confidence score. However, a tight and sound relaxation is extremely challenging to find. We are unaware of prior attempt to formally prove error bounds for practical and accelerated neural network implementations or verifiers.
Some incomplete verifiers have incorporated floating point error by maintaining upper and lower rounding bounds of internal computations (Singh et al., 2018 2019). which is also potentially appli- cable complete verifiers. However, this approach relies the specific implementation details of the inference algorithm - optimizations such as Winograd (Lavin & Gray 2016) or FFT (Abtahi et al., 2018) would either invalidate the robustness guarantees or require changes the analysis algorithm.
Another approach is quantize the computation to align the inference implementation with the verifier. For example, if we require all activations to be multiples of 8o and all weights to be mul- tiples of 81, where 8081 2F and F. is very loose bound of possible implementation error, then the output can be rounded to multiples of 8081 to completely climinate numerical error. Binarized neural networks (Hubara al. 2016) are family of extremely quantized networks, and their ver- ification (Narodytska et al., 2018 Shih et al.) 2019) is sound and complete. However, the problem of robust training and verification of quantized neural networks (Jia & Rinard (020) is relatively under-examined compared to that of real-valued neural networks (Madry et al. 2018 Mirman al. 2018 Tjeng et al. 2019 Xiao et al. 2019).
7 CONCLUSION
Floating point error should not be overlooked in the verification of real-valued neural networks, as we have presented techniques that construct adversarial examples for neural networks claimed to be robust by verifier. We hope our results will help to guide future neural network verification research by providing another perspective for the tradeoff between soundness, completeness, and scalability.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Tahmid Abtahi, Colin Shea, Amey Kulkarni, and Tinoosh Mohsenin. Accelerating convolutional neural network with FFT on embedded hardware. IEEE Transactions on Very Large Scale Inte- gration (VLSI) Systems, 26(9):1737-1749, 2018.
Sylvie Boldo and Guillaume Melquiond. Computer Arithmetic and Formal Proofs: Verifying Floating-pooe point Algorithms with the Coq System. Elsevier, 2017.
Rudy Bunel, Jingyue Lu, llker Turkaslan, Kohli, P Torr, and P Mudigonda. Branch and bound for piecewise linear neural network verification. Journal of Machine Learming Research, 21(2020), 2020.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp), pp. 39-57. IEEE, 2017.
Chih-Hong Cheng, Georg Nührenberg, and Harald Ruess. Maximum resilience of artificial neural networks. In International Symposium on Automated Technology for Verification and Analysis, pp. 251-268. Springer, 2017.
Sharan Chetlur, Cliff Woolley, Philippe Vandermersch, Jonathan Cohen, John Tran, Bryan Catan- zaro, and Evan Shelhamer. cudnn: Efficient primitives for deep learning. arXiv preprint arXiv:/410.077 2014.
Florian Corzilius, UIrich Loup, Sebastian Junges, and Erika Ábrahám. Smt-rat: an smt-compliant nonlinear real arithmetic toolbox. International Conference on Theory and Applications of Satisfubility Testing, pp. 442-448. Springer, 2012.
Souradeep Dutta, Susmit Jha, Sriram Sankaranarayanan, and Ashish Tiwari. Output range analy- sis for deep feedforward neural networks. In NASA Formal Methods Symposium, pp. 121-138.
Springer, 2018.
Krishnamurthy Dvijotham, Sven Gowal, Robert Stanforth, Relja Arandjelovic, Brendan O'Donoghue, Jonathan Uesato, and Pushmeet Kohli. Training verified learners with learned ver- ifiers. arXiv preprint 1..Kv:8805..1222 2018.
Ruediger Ehlers. Formal verification of wise linear foeward neural networks. In Interna- tional Symposium on Automated Technology for Verification and Analysis, pp. 269-286. Springer, 2017.
Matteo Fischetti and Jason Jo. Deep neural networks and mixed integer linear optimization. Con- straints, 23(3):296-309) 2018.
Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen. Petar Tsankov, Swarat Chaudhuri, and Mar- tin Vechev. Ai2: Safety and robustness certification of neural networks with abstract interpreta- tion. In 2018 IEEE Symposium on Security and Privacy (SP), pp. 3-18. IEEE, 2018.
Dario Guidotti, Francesco Leofante, Luca Pulina, and Armando Tacchella. Verification of neural networks: Enhancing scalability through pruning. arXiv preprint ar arXhv:2003.07666, 2020.
LLC Gurobi Optimization.
Gurobi optimizer reference manual, 2020. URL http: www.
gurobi. com
Xiaowei Huang, Marta Kwiatkowska, Sen Wang, and Min Wu. Safety verification of deep neural networks. In International Conference Computer Aided Verification, pp. 3-29. Springer, 2017.
Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio. Binarized neural networks. In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29, pp. 4107-414 4115-4 Curran Associates, Inc., 2016.
IEEE. IEEE standard for floating-poin arithmetic. IEEE Std 754-2008, pp. 1-70, 2008
Kai Jia and Martin Rinard. Efficient exact verification binarized neural networks. arXiv preprint arXiv:2005.03599 2020.

---

Under review as a conference paper at ICLR 2021
Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In International Conference on Computer Aided Verification, pp. 97-117. Springer. 2017.
Andrew Lavin and Scott Gray. Fast algorithms for convolutional neural networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4013-4021, 2016.
Alessio Lomuscio and Lalit Maganti. An approach to reachability analysis for feed-forward relu neural networks. arXiv preprint arXiv: 2017.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
Antoine Miné. Relational abstract domains for the detection of floating-poits run-time errors. In European Symposium on Programming, pp. 3-17. Springer, 2004.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for prov- ably robust neural networks. In Jennifer Dy and Andreas Krause (eds.). Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 3578-3561 3586, Stockholmsmässan. Stockholm Sweden, 10-15 Jul 2018, PMLR.
Nina Narodytska, Shiva Kasiviswanathan, Leonid Ryzhyk, Mooly Sagiv, and Toby Walsh. Verifying properties of binarized deep neural networks. In Thirty-Second AAAI Conference Artificial Intelligence, 2018.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Detito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy. Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' ''Alcé--Buc E. Fox, and R. Gareett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024 8035. Curran Associates, Inc., 2019.
Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang. Semidefinite relaxations for certifying robustness to adversarial examples. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 10877-10887. Curran Associates, Inc., 2018.
Philipp Rümmer and Thomas Wahl. An smt-lib theory of binary floating-poit point arithmetic. In Inter- national Workshop on Satisfiability Modulo Theories (SMT), pp. 151, 2010.
Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsich, and Pengchuan Zhang. A convex relaxation barrier tight robustness verification of neural networks. Advances Neural Information Processing Systems, pp. 2832-98422 2019.
Karsten Scheibler, Leonore Winterer, Ralf Wimmer, and Bernd Becker. Towards verification of artificial neural networks. In MBMV, pp. 30-40, 2015.
Andy Shih, Adnan Darwiche and Arthur Choi. Verifying binarized neural networks by angluin- style learning. In International Conference on Theory and Applications of Satisfiability Testing, pp. 350-370. Springer, 2019.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effective robustness certification. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cess-BBanchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 10802-10813. Curran Associates, Inc., 2018. BRL/http://pappt 8278 fast and effective robustnesussssee certification. pdf
nips cc/paper/
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for certify- ing neural networks. Proc. ACM Program. 3(OOPL). January 2019. doi: 10. 10.1145/329035,
Robert Skeel. Roundoff error and the patriot missile. SIAM News, 25(4):11, 1992.
10

---

Under review as a conference paper at ICLR 2021
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna Estrach, Dumitru Erhan, Ian Goodfellow, and Robert Fergus. Intriguing properties of neural networks. In 2nd International Conference Learning Representations, ICLR 2014, 2014.
Vincent Tjeng, Kai Y. Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In International Conference on Learning Representations, 2019.
Florian Tramer and Dan Boneh. Adversarial training and robustness for multiple perturbations. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-But E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 5866-5876. Curran Associates, Inc., 2019.
Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and Suman Jana. Formal security analysis of neural networks using symbolic intervals. In 27th {USENIX) Security Symposium (UUSENIX) Security 18), pp. 1599-1614, 2018.
Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsich, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for ReLU networks. In International Conference on Machine Learning, pp. 5276-5285, 2018.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. arXiv preprint arXiv:1711.0083 2017.
Eric Wong, Leslie Rice, and J. Zico Kolter. Fast is better than free: Revisiting adversarial training. In International Conference on Learning Representations, 2020.
Kai Y. Xiao, Vincent Tjeng,
Nur Muhammad (Mahi) Shafiullah, and Aleksander Madry. Training for faster adversarial robustness verification via inducing reLU stability. In International Conference on Learning Representations, 2019.
Huan Zhang, Tsui-Wei Weng, Pin-Yu Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi and R. Gameet (eds.), Advances in Neural Infor- Curran Associates, Inc., 2018.
mation P Processing Systems 31, pp. 9939-4948
11

---

Under review as a conference paper at ICLR 2021
A RANDOM PERTURBATION ALGORITHM
We present the details of our random perturbation algorithm below. Note that the Winograd convo- lution computes whole output patch in one iteration, and therefore we handle it separately in the algorithm.
Input: quasi-safe image Zo Input: target class number t
Input: quasi-adversarial image æ1
Input: input perturbation bound e
Input: a neural network inference implementation NNNmpl (:: W)
Input: number of iterations N (default value 1000)
Input: perturbation scale u (default value 2e-7) 7)
Output: adversarial image Fadv FAILED
for Index i of zo do xx[i] <- max(nextafter
Find the weakest bounds mz and Bu for allowed perturbations
- 0), 0)
Tuli f- min(mextafterr
+. 1),
while 2o[4] - [x > or float64 (xn(i)) float64 (i) > do
[ nextaftcr(x;/11111
end while
while
xuld [ > fooat64 (s.(ii) float64 (mn > do
[ull < ==extafter(x.11..0)
end while
end for
if NNimppl (+; W) is NNc.cwa (:: W) then (offset, stride) <- (4,9)
The Winograd algorithm in cuDNN produces 9 x 9 out- put tiles for 13 x 13 input tiles and x kernels. The offset and stride here ensure that perturbed tiles contribute independently to the output.
else
(offset, stride) < 40,4)
B Work on small tiles to avoid random errors get cancelled
end if
for i + to N do
for
(h, w) t (0, 0) (ze)ght(x1), width(21)) step (stride, stride) do
8 +- uniform(-a u, (stride offset, stride - offset))
x/ <- x1
x h + offset h + stride, w offset w + stride] + = Tu); xt)
Φ +- max(mmnnaaa
if Lew (NNimpt (x1; W), t) < Lew (NNimp) (x1; W), 1) then
11 + x¹
end if
end for
end for
Lew (NNimp) (x1; W), 1) < then
return Badv 31
else
return FAILED end if
12


Reviews:
[{"review_id": "zd3H4EhfIGP", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper focuses on the floating point unsoundness of neural network verification procedures, and shows that the results from such verifiers can not be trusted. To drive home the message of the paper, the authors take MIPVerify (which doesn't ensure FP soundness) and shows that they are able to construct adversarial examples for the cases that are returned as verified by MIPVerify. \n\nIt is an interesting nice paper but the contribution is weakened by two  facts: One, it is already known that MIPVerify doesn't ensure FP soundness; which is also acknowledged by its authors. Second, when FP soundness is not ensured, and given the fact that adversarial examples are widely present, it is no surprise that one could find adversarial examples. \n\nSo I am split on the paper. From a formal methods perspective, the discovery of the paper is not surprising as Floating point computations are known to be important (this is one of the reasons that SMT solvers put a lot of emphasis on FP). But perhaps from ML practitioner, it may be interesting. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZnkLSqs2wmy", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe authors develop a method to generate pairs of sample that are separated by a small adversarial perturbation, that have different class, but with the specificity that the a complete verifier would returns a result indicating that this sample admits no adversarial perturbation (despite the fact that it does, as evidenced by the second element of the pair). \nThese samples are obtained by considering a brightness perturbation of the image and finding the parameter (alpha) at which the verifier switch from returning \"safe\" to \"unsafe\". The resulting perturbed image is going to have adversarial examples very close to the boundary of the region considered, so small floating point errors might result in returning incorrect results.\n\nMain thoughts:\nThe problem that the author discuss is very well highlighted and explained. It is clear what vulnerability they identified, as well as the mechanism that they use to highlight it. \nOn the other hand, in terms of importance, I would rank it more as an interesting observation that an actual critical problem. If we assume, that what I'm caring is robustness of my image classification system for perturbation of size epsilon=0.1, then it seems that the worst that can happen is that some samples that I verified to be robust for epsilon=0.1, are in practice only robust for epsilon=0.09999? This doesn't seem overtly critical and would result in essentially the same result in any application.\n\nQuestions:\n- The choice of what solver to use as a backend for a MIP formulation of the Neural Network verification problem is an implementation detail. MIPVerify could well be implemented with a different solver? (MIP solvers returning incorrect result due to floating point errors is not a new problem and there seems to be some literature in how to adress these problems if they are considered of importance \"Safe bounds in linear and mixed-integer linear programming, Neumaier & Shcherbina\")\nIn addition, could this problem be solved by simply adjusting the tolerance parameters of the solver? I did not see any discussion of this by the authors, but I imagine that the default parameters used by the verifier might be geared more towards speed than towards perfect accuracy.\n- The authors mention verifiers that incorporate proper handling of floating point errors (ERAN) but then reject it by saying that it rely on specific implementation details of the inference algorithm. This seems strange because that's exactly the recommendation that the authors make. Page 2: \"any sound verifier for this class of networks must reason about the specific floating point error characteristics of the neural network implementation at hand.\"\n\nMinor questions:\nIn Figure 1.a, it seems like for the first 4 graphs, the dotted lines which I assume implies what the difference should be are lines with slope 1. Why would the change in the logit vector vary at the same rate as the perturbations? Shouldn't there be a slope dependent on the corresponding gradient coefficient?", "extra_scores": {}, "extra_text": {}}, {"review_id": "NDpPlRFSWA3", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In the recent literature there has been a rise in the number of papers which attempt to verify neural networks. The specification of the verification problems often gets adapted according to the application in mind. More specifically, for image classification networks, the problem is to prove that the output of the neural network does not flip for small perturbations to the pixel values. For a robotic setting, the problem is often safety and convergence to some goal state. Where the neural network operates in closed loop with the system dynamics. \n\nThe authors in this paper present an adversarial attack model on neural networks, which is deemed correct by some verifier. More specifically , given a neural network which can be shown to be robust to adversarial perturbations around some input, the authors exploit numerical errors in the computations to attack the network. Demonstrating the presence of loop holes in the proving engines itself. This is due to the approximation errors introduced by using floating point numbers.\n\nIn my opinion, the notion of input sets in the space of images, is not a very useful one. Mainly because the interval valued sets representing  perturbations of the input image, is far removed from the intended specification.  It's a step in the right direction, if the verification of computer vision task was a well defined problem. Since it's not clear what to verify in the first place, the use case of this paper  is not a very convincing one in my opinion. The problem of verifying neural networks in a robotic setting has a more meaningful specification.  Hence, i don't think that this paper in itself will be interesting to the general theme of the conference. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "4NIpHlIh5AT", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a method to find adversarial inputs for neural networks in regions where the networks can be \"proven\" not to admit any such adversarial examples, practically demonstrating the unsoundness of a \"complete verifier\" as well as an \"incomplete verifier\".\nWhile it was already obvious to me that \"verifiers\" that assume floating-point arithmetic is the same as real arithmetic are unsound, the paper is a service to the community in that it also makes this very obvious to informed outsiders who may not have already questioned the validity of robustness verification research that does not model round-off and even ignores it in its own implementation. The related work section does a good job of surveying the state of the art as it relates to floating-point soundness. The authors also took some space to discuss how their findings relate to current and future research on robustness verification, which I think is important in this case.\n\nPerhaps there could be a short discussion of challenges that different approaches face to become sound with respect to floating-point semantics. (For example, it seems particularly challenging for approaches based on duality, as the correctness of certificates depends non-trivially on closed-form solutions to optimization problems as well as associativity of addition.)\n\nThe technical sections are mostly well-written, though I was not able to figure out some details. For example, it is not so clear how precisely binary search is used to find α and δ simultaneously. Section 4.2 is a bit dense and its presentation could probably be improved.\n\n\n\"inevitable presence of numerical error in [...] the verifier\".\nIt is not inevitable that the verifier is subject to \"error\". We could encode the precise floating-point semantics of the neural network as a SAT formula (and then watch the SAT solver time out, but this does give a sound and complete method).\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: There are many recent methods for the formal verification of neural networks. However, most of these methods do not soundly model the floating-point representation of real numbers. This paper shows that this unsoundness can be exploited to construct adversarial examples for supposedly verified networks. The takeaway is that future approaches to neural network verification should take into account floating-point semantics.

This was a borderline paper. On the other hand, to anyone well-versed in formal methods, it is not surprising that unsound verification leaves the door open for exploits. Also, there is prior work (Singh et al., NeurIPS 2018) on verification of neural networks that explicitly aims for soundness w.r.t. floating-point arithmetic. On the other hand, it is true that many adversarial learning researchers do not appreciate the value of this kind of soundness. In the end, the decision came down to the significance of the result. Here I have to side with Reviewer 1: the impact of this problem is limited in the first place, and also, the issue of floating-point soundness has come up in prior work on neural network verification. For these reasons, the paper cannot be accepted this time around.
Decision: Reject