Robustra: Training Provable Robust Neural Networks over Reference Adversarial Space

1 Introduction

In recent years, machine learning techniques, especially deep neural networks (DNNs), have been widely adopted in various applications, such as image classification and machine translation. However, DNNs are recently found to be vulnerable against adversarial examples, i.e., maliciously perturbed inputs that can mislead the models to make arbitrary prediction errors [Szegedy et al., 2014]. Such malicious perturbations are usually imperceptible to human eyes, but allow attackers to easily mislead the behavior of DNNs. The existence of adversarial examples impedes application of DNNs in domains where the safety is highly sensitive, such as autonomous driving and access control systems. Although a series of heuristic defenses [Papernot et al., 2016; Samangouei et al., 2018] have been proposed to defend against existing adversarial examples, many of these defenses can be adaptively attacked again [Carlini and Wagner, 2017b; Athalye et al., 2018]. How to train DNNs that are guaranteed to be robust to any attack serves as an open problem to the community.

∗Both authors contributed equally to this work.

Recently, provable defenses [Wong and Kolter, 2018; Wong et al., 2018] have been proposed to train DNNs with low provable error bound, which refers to the fraction of test set inputs for which there is provably no adversarial example within allowed perturbations. However, provable error bounds of DNNs so far are far from satisfaction. For example, on CIFAR10, the state-of-the-art provable error bound is still as high as 46.11%, when bounded by ℓ∞, with ϵ = 2/255 [Tjeng et al., 2019].

To address the issue, in this paper, we present our approach named Robustra for effectively improving the provable error bound of ReLU-based DNNs. We formalize the target task as a min-max game between the attackers and defenders. Different from previous work [Wong and Kolter, 2018] that solves the min-max optimization over the whole normbounded space, we additionally leverage the adversarial space of a reference model as the feasible region. Specifically, given a reference model, our formalized problem seeks to train a model that is robust in the adversarial space of the reference model, i.e., the adversarial examples cannot transfer to the model that we train.

Solving such a non-convex problem is non-trivial. We use linear approximation for ReLU activations in the DNNs, and solve its dual problem. The constraint related to the reference adversarial space introduces a family of slack variables in the dual problem, causing no existing approach to effectively solve it. To address the problem, by leveraging the monotonicity and boundedness of the slack variables' gradients, only querying the gradients once, our approach directly calculates out the solution for slack variables. Thus, we solve the problem in the same order of time as the previous work [Wong et al., 2018]. Furthermore, by using similar techniques introduced in the previous work [Wong et al., 2018], Robustra is scalable to be applied to large models such as ResNet. Moreover, we train a pair of models mutually, i.e., iteratively using one as training model and the other as reference, and thus we obtain a pair of robust models at the same time, without requiring external reference.

We evaluate Robustra on the MNIST and CIFAR10 datasets. The evaluation results show that our approach can provide significantly better provable adversarial error bounds on both datasets, compared to the state-of-the-art results. Specifically, we reduce the error bound from 24.19% to 16.91% with ℓ∞ norm ϵ = 0.3 on MNIST, and from 46.11% to 43.68% with ℓ∞ norm ϵ = 2/255 on CIFAR10.

In summary, this paper makes the following main contributions:

• We propose Robustra, a novel approach for training robust ReLU-based DNNs. Robustra formalizes the problem of robust training as a min-max optimization over the adversarial space of a reference model.
• We propose an algorithm that leverages the monotonicity and boundedness of the slack variables in the dual problem to efficiently solve the optimization problem.
• We evaluate Robustra on both MNIST and CIFAR10 datasets. The evaluation results show that Robustra produces DNNs with significantly better provable adversarial error bounds compared to the state-of-the-art results.

Our code and model weights are available at https://github.com/llylly/Robustra.

2 Preliminaries

In this work, we consider a pair of ReLU-based DNNs f and g, where f is the trainable model, and g is the reference model. We refer to f as fθ in some places to explicitly emphasize the trainable parameters θ.

Let n denote the dimension of input vector, and m denote the number of classes. The ReLU function is ReLU(x) = max(x, 0). f and g are formally defined as follows:

Namely, f (resp. g): Rn → Rm is a k1 (resp. k2)-layer neural network with parameters Wi, bi, 1 ≤ i ≤ k1 (resp. Ui, bi, 1 ≤ i ≤ k2). All activations functions are ReLU functions in f and g.

Given an input x, we have f(x), g(x) ∈ Rm, representing the predicted probability for each class. Let (f(x))i (resp. (g(x))i ) represent the ith dimension of f(x) (resp. g(x)), i.e., the predicted probability of class i.

In this paper, we use ℓ∞ norm to measure the adversarial perturbation. We also support to work on ℓ1 norm or ℓ2 norm by applying the techniques introduced in [Wong et al., 2018].

3 RelatedWork and Background

Attacks and Empirical Defenses. Szegedy et al. [2014] discover the broad existence of adversarial examples in neural networks. From then on, various attack approaches have been proposed, such as FGSM [Goodfellow et al., 2015], CW [Carlini and Wagner, 2017b; Carlini and Wagner, 2017a], and PGD [Madry et al., 2018]. At the same time, heuristic defenses have been proposed, such as Distillation [Papernot et al., 2016] and Defense-GAN [Samangouei et al., 2018]. Although these heuristic defenses have empirically shown effectiveness against existing attacks, they can be adaptively attacked again after being proposed [Athalye et al., 2018; Carlini, 2019].

Provable Defenses. Provable defenses train DNNs with low provable error bound, i.e., they can provably guarantee robustness for a fraction of test set inputs against any attacks for the trained DNNs. Existing provable defenses use the upper bound of loss function as (part or all of) the training objective. Existing upper-bound derivation approaches include SDP [Raghunathan et al., 2018], LP-dual [Wong and Kolter, 2018; Wong et al., 2018], and LP [Mirman et al., 2018; Singh et al., 2018]. Besides, concurrent work by Xiao et al. [2019] combines PGD adversarial training with regularization for weight sparsity and ReLU stability. However, provable error bounds of DNNs obtained from these existing approaches are far from satisfaction.

DNNVerification. DNNverification approaches determine provable error bound for trained DNNs. Reluplex [Katz et al., 2017] pioneers the field but is not scalable to verify DNNs with more than a thousand neurons. By using Mixed Integer Programming, Tjeng et al. [2019] provide a much faster approach for DNN verification. Other approaches provide relaxed provable error bound by using LPbased relaxations [Weng et al., 2018; Singh et al., 2019; Salman et al., 2019] or SDP-based relaxations [Fazlyab et al., 2019].

4 Motivation: An Empirical Observation

Our approach is inspired by an empirical observation: during training, merely limiting overlap of the adversarial space with a reference model can make the model internally robust. This observation indicates that the adversarial space of one model should be defended against with high priority.

Specifically, given an input x and its true label y, a naturally trained reference model g(·), we train a model f(·) by modifying the training objective from original loss function ℓf def = ℓ (f(x), y) to ℓf + λ| cos〈▽xℓf ,▽xℓg〉|, where λ is a tunable hyper parameter, being set to 0.1; g, the reference model, is a naturally trained model. Our intuitive approach aims at guiding the local gradients between two models to be diverse (orthogonal) in terms of their cosine angle, hence reducing the overlap of their adversarial spaces.

Figure 1 shows the error curves by training epochs. The error rate is measured by the success rate of untargeted PGD attack bounded by ℓ∞ with ϵ = 0.1. The blue curve represents the natural trained model g, where as the natural training goes, the error rate slightly increases. The two dashed curves represent the transfer attack's success rate, where adversarial examples are generated from f/g model and used to attack the other model. The curves show that the transfer error rate is reduced as expected. The red curve represents the error rate of model f. We find that, after a few epochs, the error rate of model f decreases below 20% although we never deliberately train the model to be self-robust.

This observation inspires us to train a robust model constrained on the adversarial space of another model.

5 Robustra

In this section, we introduce Robustra in detail.

5.1 Min-Max ProblemFormulation

We formalize our target task as a min-max game.

Given an input sample x∗ , the true label y∗ , and some target label ytarg ̸= y∗ , we define Aϵ(x∗ ), the adversarial space of g bounded by ℓ∞ norm with ϵ, as follows:

where t measures the margin between the decision boundary of adversarial examples in Aϵ(x∗ ). Particularly, when t = 0, Aϵ(x∗ ) is the exact adversarial space of g; when t decreases, Aϵ(x∗ ) becomes larger, vice versa.

We want the model f to be robust to adversarial examples of the reference model g. Specifically, for each input in the adversarial space Aϵ(x∗ ), the output of f has a larger value at y∗ than at ytarg . We formalize the objective as the following optimization problem:

Let c = eytarg - ey∗, and let FA denote the value space of Aϵ(x∗ ), i.e.,

Then, the optimization (Eqn. 2) can be rewritten as follows:

Since the set FA(x∗ ) is consecutive and highly non-convex, solving such optimization problem is computationally intractable.

5.2 Linear Convex Relaxation

In order to solve the optimization problem, we approximate the optimization space FA(x∗ ) of the problem by using relaxation of the ReLU function. A convex space ˆ F ˆ A(x∗ ) is obtained from the approximation.

Since both f(·) and g(·) are ReLU-based DNNs, we use the linear relaxation for ReLU function. Let o = ReLU(i) denote the ReLU function and [l, u] denote the range of input i, i.e., l ≤ i ≤ u. The approximation of ReLU function corresponds to its convex outer space:

1. When l ≤ u ≤ 0, o = 0;
2. When 0 ≤ l ≤ u, o = i;

We replace each ReLU function in the problem with corresponding linear constraints according to the range of the input.

We apply the relaxation to both f(·) and g(·) models, as shown in Figure 2.

First, we apply the relaxation to the ReLU neurons in model g(·). Let ˆG(·) denote the output space after applying the relaxation. Note that ˆG(x) ⊆ Rm, while g(x) ∈ Rm. Accordingly, the adversarial space Aϵ(x∗ ) is replaced with its approximation subspace ˆ Aϵ(x∗ ):

Note that ˆ Aϵ(x∗ ) is a convex subspace of Aϵ(x∗ ), because ˆG(x) is a convex outerspace of g(x). Then, we obtain an approximated optimization subspace F ˆ A(x∗ ) (shown in Figure 2).

Second, we similarly apply the relaxation to the ReLU neurons in model f(·). Let ˆ F(·) denote the output space after applying the relaxation. Then, we obtain ˆ F ˆ A(x∗ ) = ⋃x∈ ˆ Aϵ(x∗ ) ˆ F(x), which is a convex approximation space of FA(x∗ ).

After the two-step relaxation, the optimization problem that we would like to address is as follows:

It is an approximation of the original optimization problem (Eqn. 4).

Figure 2 illustrates the procedure of the relaxation. At the beginning, the optimization space FA(x∗ ) is non-convex; after relaxation of model g, we obtain a subspace F ˆ A(x∗ ); after relaxation of model f, we obtain ˆ F ˆ A(x∗ ), which is a convex approximation of the original space. We address the optimization problem over this approximation convex space.

5.3 Duality

Training on the outer minimization in Eqn. 6 requires to calculate the gradient of model parameter θ w.r.t. the inner maximization problem: ▽θ maxv c⊤v = ▽θc⊤v∗ , where v∗ is the solution to the inner problem. In order to calculate the gradient, efficiently solving the inner problem, i.e., finding v∗ , is desirable.

Since the inner maximization is an optimization over linear convex space ˆ F ˆ A(x∗ ), the minimum of its dual problem corresponds to the solution due to strong duality. Inspired by previous work [Wong and Kolter, 2018; Wong et al., 2018], we formulate the dual problem by a feedforward network as follows:

ν and q are defined as follows:

In Eqn. 8 and 9, ui,j and li,j represent the upper and lower bound of the ReLU function input for the j th neuron in layer i of network f(·). Similarly, u′i,j and l′i,j represent the upper and lower bounds of the ReLU function input for the j th neuron in layer i of network g(·).

For layer i in model f and g, I + i and Q+i represent the sets of neurons where the inputs are always positive, respectively (0 ≤ l ≤ u); similarly, I - i and Q-i are the sets of neurons where the inputs are always negative (l ≤ u ≤ 0); and Ii and Qi are the sets of neurons spanning zero (l < 0 < u).

ν, ˆ ν, q, ˆ q, and η are newly introduced dual variables. We transform the original problem to an optimization problem over the new variable η.

5.4 Gradient Monotonicity and t selection

In order to solve the dual problemminη≥0 hc(η), we turn to the gradient ▽ηhc(η), which can be written as follows:

where γ(η) = ∑nj=1 sgn(ˆ v1,j + ηˆ q1,j) · ˆ q1,j and C is a constant independent of η and t. Note that γ(η) is the analytic form of ▽η‖ˆ ν1 + ηˆ q1‖1.

Theorem 1 (Property of γ(η)) γ(η) is a bounded nondecreasing step-function, and the transition points are {-ˆ ν1,j /ˆ q1,j : 1 ≤ j ≤ n}.

The theorem can be proved by case discussion over sign of ˆ q1,j. Since γ(η) is the only η-dependent term in Eqn. 10, ▽ηhc(η) has the same property, i.e., ▽ηhc(η) is a bounded non-decreasing step-function. Thus, we can obtain the value range of the gradient of hc(η). Specifically, we have

Theorem 2 (Property of hc(η)) When the domain of hc(η) is [0,∞), let ηl = 0, ηr = maxj(-ˆ ν1,j /ˆ q1,j), the gradient value ▽ηhc(η) ∈ [l, r] def = [▽ηhc(η)|η=ηl ,▽ηhc(η)|η=ηr ].

Let us define adversarial space constraints to be constraints imposed by the reference model, i.e., those corresponding to ((g(x))ytarg - (g(x))y∗ ≥ t) in Eqn. 1. We can relate the solution for minη≥0 hc(η) to sign of l and r:

• If l ≤ r ≤ 0, when η → +∞, hc(η) → -∞. According to the duality theorem, there is no solution to the original problem maxv c⊤v, indicating that the space ˆ F ˆ A(x∗ ) is empty. In this situation, we regard adversarial space constraints to be infeasible. We need to decrease t, i.e., enlarge adversarial space ˆ Aϵ(x∗ ).
• If l < 0 < r, a positive η solution exists. In this situation, we regard adversarial space constraints to be tight.
• If 0 ≤ l ≤ r, the solution is η = 0. As seen from Eqn. 8, reference-model-related variables are all eliminated

from objective function hc(η), indicating that the adversarial space constraints are loose. In this situation, we would like to increase t, i.e., narrow adversarial space ˆ Aϵ(x∗ ).

The ideal situation is that for all optimization objectives hc(η), the adversarial space constraints are tight and the solution exists, i.e., l < 0 < r. To guarantee so, we fix a reasonable η as the solution and inversely obtain the corresponding t.

Specifically, we set η to be the median number of γ(η) transition points. Combining Theorem 1, Theorem 2, and constraint η ≥ 0, we pick the median number in {-ˆ ν1,j /ˆ q1,j : 1 ≤ j ≤ n,-ˆ ν1,j /ˆ q1,j > 0} as the solution for η, denoted as ηmed.

ηmed being the solution indicates ▽ηhc(η)|η=ηmed = 0, which yields t = t0 = ϵγ(ηmed) + C. Thus, the hyperparameter t is set to t0 according to ηmed.

As result, we effectively solve the inner maximization problem minη≥0 hc(η) by forward passing c to the network defined in Eqn. 9 and extracting the median number using ˆ v1 and ˆ q1. After that, we use t0 and ηmed to directly calculate hc(η). Formally,

5.5 Scaling

To scale up the training process, we find that Cauchy random projection estimation of ℓ1 norm [Wong et al., 2018] can be directly applied in our approach. When a vector multiplies a standard Cauchy random matrix, the median number of the result vector is an estimation of ℓ1 norm of the vector. Using this property, we can approximately calculate ∑k1-1 i=2 ∑j∈Ii li,j[νi,j]+ and ∑k2-1 i=2 ∑j∈Qi l′i,j [qi,j]+ of Eqn. 8 in linear complexity w.r.t neuron numbers [2018].

With this calculation, our approach has the same order of complexity with [Wong et al., 2018]. This calculation enables our approach to scale up to large datasets such as CIFAR10 and large DNN models such as ResNet.

5.6 Training

During the training process, we use the solution for each ytarg as the probability of that class. Then we use cross-entropy with softmax as the training loss to jointly minimize errors for all ytarg ̸= y∗ .

We adopt a manual training scheme to optimize a pair of models. Initially, f(·) and g(·) are randomly initialized independently. When the model size is small, in each epoch, we train model f(·) where model g(·) is the reference, and then train model g(·) where model f(·) is the reference. When the model size is large, we accelerate the process by distributing model f(·) and model g(·) to two GPUs. By loading the last epoch weights of the other model as the reference, two models are trained parallelly, both using the other model as the reference at the same time. This training scheme optimizes both models efficiently.

6 Experiments

We evaluate Robustra on image classification tasks with two datasets: MNIST [LeCun et al., 1998] and CIFAR10 [Krizhevsky and Hinton, 2009].

We use the same DNNs as used in [Wong et al., 2018] for comparison. All DNNs are convolutional neural networks with multiple layers, using only ReLU activations. Table 1 shows the statistics of DNNs that we use.

For each model and dataset, we run 100 epochs on the training set. Adam optimizer is used for MNIST models, and SGD optimizer (0.9 momentum, 5 × 10-4 weight decay) is used for CIFAR10 models. The ℓ∞ norm ϵ is initialized by 0.01, and then it linearly increases to the configured ϵ (0.1 or 0.3 for MNIST, 2/255 or 8/255 for CIFAR10) in the first 20 epochs. In the first 20 epochs, the learning rate is set to be 0.001; then, it decades by half every 10 epochs. The batch size is set to 50. The scaling approximation (Section 5.5) is applied for training 'Large' and 'ResNet' models, where the projection dimension is 50. Note that no hyperparameter selection or tuning is applied to guarantee the soundness of the results. All experiments are run on Geforce GTX 1080 Ti GPUs.

6.1 Provable Error Bound

We use two provable error bounds to evaluate the models trained by Robustra: LP bound [Wong and Kolter, 2018] and MILP bound [Tjeng et al., 2019]. The full test set is used in our evaluation. We compare the error bounds of Robustra to the state of the art on the same model structures [Wong et al., 2018; Wong and Kolter, 2018].

The results in Table 2 show that on both the MNIST dataset and CIFAR10 dataset, Robustra outperforms the state of the art in most of the settings. Specifically, on the MNIST dataset, with ϵ = 0.1, Robustra significantly improves the MILP bound on 'Large' model from 2.74% to 2.09%; with ϵ = 0.3, Robustra achieves 16.91% provable test error using 'Small' model and improves LP bound, from previous 43.10%/45.66% to 31.42%/34.59% for 'Small' and 'Large' models, respectively. On the CIFAR10 dataset, with ϵ = 2/255, Robustra exceeds the state of the art on all models. It reduces the previous bound from 46.11% to 43.68%. With ϵ = 8/255, Robustra reduces the error bound from 77.60% (on 'ResNet', MILP bound) to 74.87% (on 'Small', MILP bound).

Clean error represents the error rate of a model on a clean (i.e., unperturbed) test set. The model trained by Robustra has similar or smaller clean error rate compared to state-ofthe-art models. Furthermore, we find that a model with less clean error usually has a tighter provable error bound.

6.2 Training Progress

The training curves are shown in Figure 3. Provable error is measured by LP bound. Clean error is measured by error rate on clean (i.e., unperturbed) examples. Both are evaluated on the test set.

In the first 20 epochs, ϵ used for training is linearly increased to desired ϵ (0.3). The provable robust error keeps being 100% for these first 20 epochs, and then a significant drop occurs as the training ϵ reaches 0.3. The result reveals that the model is not robust to larger perturbations unless it is trained at that perturbation level. During these first 20 epochs, the clean error increases while the provable robust error bound decreases. Then both provable errors and clean errors decrease.

At each epoch, both models are trained mutually: we first regard g(·) as the reference model and train the model f(·); then, we set the trained f(·) as the reference model and train the model g(·). Thus, at each epoch, the test error of g(·) is slightly smaller than the test error of f(·), as shown in Figure 3.

6.3 t Selection Effectiveness

In our approach, we select some t to solve the inner maximization problem, as discussed in Section 5.4. Figure 4a plots the curve of selected t. Larger t corresponds tighter reference space, as shown in Eqn. 1. In the first 20 epochs, t is small and sharply increases to around -3. This result indicates that our approach dynamically tightens these constraints along with increasing training ϵ. After 20 epochs, as the reference model is trained more robust, its adversarial space becomes smaller. The approach gradually decreases t to loosen the constraints.

In Figure 4b, on MNIST with ϵ = 0.3, we study the solution status on test dataset if fixing t = 0. In the first 20 epochs, non-robust models make almost all constraints loose. After 20 epochs, the robust models make almost all constraints infeasible. Thus, when t = 0, we are not able to effectively solve the problem. Instead, we need to dynamically select t as we propose in Section 5.4.

7 Conclusion

We have presented Robustra, an approach for training provable robust neural networks. In particular, we formalize the training procedure as a min-max game over the adversarial space of the reference model, and effectively solve the minmax game. The experimental results have shown that Robustra significantly outperforms the state-of-the-art approach.

Acknowledgments

This work was supported in part by NSF under grants no. CNS-1513939, CNS-1564274, CCF-1816615.