Retrieval-Augmented Convolutional Neural Networks for Improved Robustness against Adversarial Examples

We propose a retrieval-augmented convolutional network and propose to train it with local mixup, a novel variant of the recently proposed mixup algorithm. The proposed hybrid architecture combining a convolutional network and an off-the-shelf retrieval engine was designed to mitigate the adverse effect of off-manifold adversarial examples, while the proposed local mixup addresses on-manifold ones by explicitly encouraging the classifier to locally behave linearly on the data manifold. Our evaluation of the proposed approach against five readily-available adversarial attacks on three datasets--CIFAR-10, SVHN and ImageNet--demonstrate the improved robustness compared to the vanilla convolutional network.


Introduction
Since the initial investigation by Szegedy et al. (2013), adversarial examples have drawn a large interest. Various methods for both generating adversarial examples as well as protecting a classifier from them have been proposed (see Sec. 3-4 for more details.) Adversarial examples exist due to misbehaviors of a classifier in some regions of the input space and are generated often by finding a point in such a region using optimization.
According to (Gilmer et al., 2018), adversarial examples can be categorized into those off the data manifold, which is defined as a manifold on which training examples lie, and those on the data manifold. Off-manifold adversarial examples occur as the classifier does not have a chance to observe any off-manifold examples during training, which is a natural consequence from the very definition of the data manifold. On-manifold adversarial examples however exist between training examples on the data manifold. There are two causes behind this phenomenon; (1) the sparsity of training examples and (2) the non-smooth behavior of the classifier on the data manifold.
In this paper, we propose to tackle both off-and on-manifold adversarial examples by incorporating an off-the-shelf retrieval mechanism which indexes a large set of examples and training this combination of a deep neural network classifier and the retrieval engine to behave linearly on the data manifold using a novel variant of the recently proposed mixup algorithm (Zhang et al., 2017), to which we refer as "local mixup." The retrieval mechanism efficiently selects a subset of neighboring examples from a candidate set near the input. These neighboring examples are used as a local approximation to the data manifold in the form of a feature-space convex hull onto which the input is projected. The classifier then makes a decision based on this projected input. This addresses offmanifold adversarial examples. Within this feature-space convex hull, we encourage the classifier to behave linearly by using local mixup to further address on-manifold adversarial examples.
We evaluate the proposed approach, called a retrievalaugmented classifier, with a deep convolutional network (Le-Cun et al., 1998) on object recognition. We extensively test the retrieval-augmented convolutional network (RaCNN) on datasets with varying scales; CIFAR-10 (Krizhevsky & Hinton, 2009), SVHN (Netzer et al., 2011) as well as Ima-geNet (Deng et al., 2009), against five readily-available adversarial attacks including both white-box (FGSM, iFGSM, DeepFool and L-BFGS) and black-box attacks (Boundary). Our experiments reveal that the RaCNN is more robust to these five attacks than the vanilla convolutional network. robust classifier by combining an off-the-shelf retrieval engine and a variant of the recently proposed mix-up learning strategy.

Setup
Let D = {(x 1 , y 1 ), . . . , (x M , y M )} be a candidate set of examples. This set may be created as a subset from a training set D = {(x 1 , y 1 ), . . . , (x N , y N )} or may be an entire separate set. We use D as a proxy to the underlying data manifold.
k(x, x ) is a distance function that measures the dissimilarity between two inputs x and x . In order to facilitate the use of an off-the-shelf retrieval engine, we use where φ is a predefined, or pretrained, feature extractor. We assume the existence of a readily-available retrieval engine F that takes x as input and returns the K nearest neighbors in D according to k(x, x ).
We then have a deep neural network classifier composed of a feature extraction φ and a classifier g. This classifier is trained on a training set D, taking into account the extra set D and the retrieval engine.

Inference
In this setup, we first describe the forward evaluation of the proposed network. This forward pass is designed to handle adversarial examples "off" the data manifold by projecting them onto the data manifold.
Local Characterization of Data Manifold Given a new input x, we use the retrieval engine F to retrieve the examples x k 's from D that are closest to x: F (x) = {x 1 , . . . , x K }. We then build a feature-space convex hull by As observed earlier, linear interpolation of two input vectors in the feature space of a deep neural network often corresponds to a plausible input vector, unlike when interpolation was done in the raw input space (see, e.g., Bengio et al., 2013;Kingma & Welling, 2013;Radford et al., 2015). Based on this observation, we consider the feature-space convex hull C(F (x)) as a reasonable local approximation to the underlying data manifold.
Trainable Projection Exact projection of the input x onto this convex hull C(F (x)) requires expensive optimization, especially in the high-dimensional space. As we consider a deep neural network classifier, the dimension of the feature space φ could be hundreds or more, making this exact projection computationally infeasible. Instead, we propose to learn a goal-driven projection procedure based on the attention mechanism (Bahdanau et al., 2014).
We compare each input x k ∈ F (x) against x and compute a score: where U is a trainable weight matrix (Luong et al., 2015). These scores are then normalized to form a set of coefficients: . These coefficients α k 's are then used to form a projection point of x in the feature-space convex hull C(F (x)): This trainable projection could be thought of as learning to project an off-manifold example on the locallyapproximated manifold to maximize the classification accuracy.
Classification The projected feature P C(F (x)) (x) now represents the original input x and is fed to a final classifier g. In other words, we constrain the final classifier to work only with a point inside a feature-space convex hull of neighboring training examples. This constraint alleviates the issue of the classifier's misbehavior in the region outside the data manifold up to a certain degree. 1

Training
The output of the classifier g(P(x)) is almost fully differentiable with respect to the classifier g, both of the features extractors (φ and φ) and the attention weight matrix U , except for the retrieval engine F . 2 This allows us to train the entire pipeline in the previous section using backpropagation (Rumelhart et al., 1986) and gradient-based optimization.
Local Mixup This is however not enough to ensure the robustness of the proposed approach to on-manifold adversarial examples. During training, the classifier g only observes a very small subset of any feature-space convex hull. Especially in a high-dimensional space, this greatly increase the chance of the classifier's misbehavior within these feature-space convex hulls, as also noted by Gilmer et al. (2018). In order to address this issue, we propose to augment learning with a local variant of the recently proposed mix-up algorithm (Zhang et al., 2017).
The goal of original mixup is to encourage a classifier to act linearly between any pair of training examples. This is done by linearly mixing in two randomly-drawn training examples and creating a new linearly-interpolated example pair during training. Let two randomly-drawn pairs be (x i , y i ) and (x j , y j ), where y i and y j are one-hot vectors in the case of classification. Mixup creates a new pair (λx i + (1 − λ)x j , λy i + (1 − λ)y j ) and uses it as a training example, where λ ∈ [0, 1] is a random sample from a beta distribution. We call this original version global mixup, as it increases the linearity of the classifier between any pair of training examples.
It is however unnecessary for our purpose to use global mixup, as our goal is to make the classifier better behave (i.e., linearly behave) within a feature-space convex hull C(F (x)). Thus, we use a local mixup in which we uniformly sample the convex coefficients α k 's at random to create a new mixed example pair ( Overall We use stochastic gradient descent (SGD) to train the proposed network. At each update, we perform N CE descent steps for the usual classification loss, and N MU descent steps for the proposed local mixup.

Retrieval Engine F
The proposed approach does not depend on the specifics of a retrieval engine F . Any off-the-shelf retrieval engine that supports dense vector lookup could be used, enabling the use of a very large-scale D with latest fast dense vector lookup algorithms, such as FAISS (Johnson et al., 2017). In this work, we used a more rudimentary retrieval engine based on locality-sensitive hashing (LSH; see, e.g., Datar et al., 2004) with a reduced feature dimension using random projection (see, e.g., Bingham & Mannila, 2001, and references therein), as the sizes of candidate sets D in the experiments contain approximately 1M or less examples.
The key φ (x) from Eq. (1) was chosen to be a pretrained deep neural network without the final fully-connected classifier layers (Krizhevsky et al., 2012;He et al., 2016).

Attack Scenarios
Scenario 1 (Direct Attack) In this work, we consider the candidate set D and the retrieval engine which indexes it to be "hidden" from the outside world. This property makes a usual white-box attack more of a gray-box attack in which the attacker has access to the entire system except for the retrieval part. This is our first attack scenario.
Scenario 2 (Retrieval Attack) Despite the hidden nature of the retrieval engine and the candidate set, it is possible for the attacker to confuse the retrieval engine, if she/he could access the feature extractor φ . We furthermore give the attacker the access not only to φ but the original classifier g which was tuned together with φ . This allows the attacker to create an adversarial example on g (φ (x)) that could potentially disrupt the retrieval process, thereby fooling the proposed network. Although this is unlikely in practice, we test this second scenario to investigate the possibility of compromising the retrieval engine.

Attack Methods
Under each of these scenarios, we evaluate the robustness of the proposed approach on the five widely used/tested adversarial attack algorithms including both white-box and blackbox attacks. They are fast gradient sign method (FGSM, Goodfellow et al., 2014b), its iterative variant (iFGSM, Kurakin et al., 2016), DeepFool (Moosavi-Dezfooli et al., 2016), L-BFGS (Tabacof & Valle, 2016) and Boundary . We acknowledge that this is not an exhaustive list of attacks, however find it to be extensive enough to empirically evaluate the robustness of the proposed approach.
Fast Gradient Sign Method (FGSM) FGSM creates an adversarial example by adding the scaled sign of the gradient of the loss function L computed using a target classŷ to the input: x where the scale controls the difference between the original input x and its adversarial version x . This is a white-box attack, requiring the availability of the gradient of the loss function with respect to the input.
Iterative FGSM (iFGSM) iFGSM improves upon the FGSM by iteratively modifying the original input x for a fixed number S of steps. At each step, where s = 1, . . . , S and x 0 = x. Similarly to the FGSM, the iFGSM is a white-box attack.
DeepFool Moosavi-Dezfooli et al. (2016) proposed to create an adversarial example by finding a residual vector r ∈ R dim(x) with the minimum L p -norm with the constraint that the output of a classifier must flip. They presented an efficient iterative procedure to find such a residual vector.
Similarly to the FGSM and iFGSM, this approach relies on the gradient of the classifier's output with respect to the input, and is hence a white-box attack. (2016) proposed an optimization-based approach, similar to DeepFool above, however, more explicitly constraining the input to lie inside a tight box defined by training examples. They use L-BFGS-B (Zhu et al., 1997) to solve this box-constrained optimization problem. This is also a white-box attack.

L-BFGS Tabacof & Valle
Boundary Brendel et al. (2017) proposed a powerful black-box attack, or more specifically decision-based attack, that requires neither the gradient of a classifier nor the predictive distribution. It only requires the final decision of the classifier. Starting from an adversarial example, potentially far away from the original input, it iteratively searches for a next adversarial example that has a smaller difference to the original input. This procedure guarantees the reduction in the difference by rejecting any step that neither decreases the difference nor makes the example not adversarial.
Implementation We use Foolbox 3 released by Rauber et al. (2017). Whenever necessary for further analysis, such as the accuracy per the amount of adversarial perturbation, we implement some of these attacks ourselves.

Related Work
Since the phenomenon of adversarial examples was noticed by Szegedy et al. (2013), there have been a stream of attempts at making a deep neural network more robust. Most of the existing work are orthogonal to the proposed approach here and could be used together. We however detail them here to demonstrate similarities and contrasts against our approach.

Input Transformation
An off-manifold adversarial example can be avoided, if it could be projected onto the data manifold, characterized by training examples. This could be thought of as transforming an input. There have been two families of algorithms in this direction.
Data-Independent Transformation The first family of defense mechanisms aims at reducing the input space so as to minimize regions that are off the data manifold. Dziugaite et al. (2016) demonstrated that JPEG-compressed images suffer less from adversarial attacks. Lu et al. (2017) suggest that trying various scaling of an image size could overcome adversarial attacks, as they seem to be sensitive to the scal-ing of objects. Guo et al. (2017) uses an idea of compressed sensing to transform an input image by reconstructing it from its lower-resolution version while minimizing the total variation (Rudin et al., 1992). More recently, Jacob Buckman (2018) proposed to discretize each input dimension using thermometer coding. These approaches are attractive due to their simplicity, but there have some work showing that it is often not enough to defend against sophisticated adversarial examples (see, e.g., Shin & Song, 2017).

Data-Dependent Transformation
On the other hand, various groups have tried using a data-dependent transformation mostly relying on density estimation. Gu & Rigazio (2014) used a denoising autoencoder (Vincent et al., 2010) to push an input back toward the data manifold. Pouya Samangouei (2018) and Song et al. (2017) respectively use a pixel-CNN (van den Oord et al., 2016) and generative adversarial network (Goodfellow et al., 2014a) to replace an input image with a nearby, likely image. Instead of using a separately trained generative model, Guo et al. (2017) uses a technique of image quilting (Efros & Freeman, 2001). These approaches are similar to our use of a retrieval engine over the candidate set. They however do not attempt at addressing the issue of misbehaviors of a classifier on the data manifold.

Attack-Aware Learning
Another direction has been on modifying a learning algorithm to make a classifier more robust to adversarial examples. As our approach relies on usual backpropagation with stochastic gradient descent, most of the approaches below, as well as above, are readily used together.  ensures that the classifier well-behaves in the neighborhood of each training point. It is highly relevant to the proposed local mixup which also aims at making a classifier wellbehave between any pair of neighboring training examples.

Retrieval-Augmented Neural Networks
The proposed approach tightly integrates an off-the-shelf retrieval engine into a deep neural network. This approach of retrieval-augmented deep learning has recently been proposed in various tasks. Gu et al. (2017) use a text-based retrieval engine to efficiently retrieve relevant training translation pairs and let their non-parametric neural machine translation system seamlessly fuse an input sentence and the retrieved pairs for better translation. Wang et al. (2017) proposed a similar approach to text classification, and Guu et al. (2017) to language modeling. More recently, Sprechmann et al. (2018) applied this retrieval-based mechanism for online learning, similarly to the earlier work by Li et al. (2016) in the context of machine translation. Pretrained Feature Extractor φ We train a deep convolutional network for each dataset, remove the final fullyconnected layers and use the remaining stack as a feature extractor φ for retrieval. This feature extractor is fixed when used in the proposed RaCNN.

Experiments
RaCNN: Feature Extractor φ and Classifier g We use the same convolutional network from above for the RaCNN as well (separated into φ and g by the final average pooling) for each dataset. For CIFAR-10 and SVHN, we train φ and g from scratch. For ImageNet, on the other hand, we fix φ = φ and train g from the pretrained ResNet-18 above. The latter was done, as we observed it greatly reduced training time in the preliminary experiments.
Evaluation In addition to the accuracy on the clean test set, we look at the accuracy per the amount of perturbation used to create adversarial examples. We use the default MeanSquaredDistance from the Foolbox library; this amount is computed as a normalized L 2 distance between the original example x and its perturbed versionx: We further notice that our attacks are generally performed with clipping the outbounded pixel values at each step.

CIFAR-10
Model In the CIFAR-10 experiments, our model contains 6 convolutional layers followed by 2 fully-connected layers. Every layer is operated with batch normalization (Ioffe & Szegedy, 2015) and ReLU after. More details can be found in Appendix 7.
Scenario 1 (Direct Attack) We present in Fig. 1 the effect of adversarial attacks with varying strengths (measured in the normalized L 2 distance) on both the vanilla convolutional network (Baseline) and the proposed RaCNN's with various settings. Across all five adversarial attacks, it is clear that the proposed RaCNN is more robust to adversarial examples than the vanilla classifier is. The proposed local mixup improves the robustness further, especially when the number of retrieved examples is small, i.e., K = 5. We conjecture that this is due to the quadratically increasing number of pairs, i.e., K(K−1) 2 , for which local mixup must take care of, with respect to K.
Scenario 2 (Retrieval Attack) In Table 1, we present the accuracies of both the baseline and RaCNN's with varying strengths of white-box attacks, when the feature extractor φ for the retrieval engine is attacked. We observe that it is indeed possible to fool the proposed RaCNN by attacking the retrieval process. Comparing Fig. 1 and Table 1, we however notice that the performance degradation is much less severe in this second scenario.

SVHN
Model We use the same architecture and hyper-parameter setting as in the CIFAR-10 experiments.
Scenario 1 (Direct Attack) On SVHN, we observe a similar trend from CIFAR-10. The proposed RaCNN is more robust against all the adversarial attacks compared to the vanilla convolutional network. Similarly to CIFAR-10, the proposed approach is most robust to DeepFool and Boundary, while it is most susceptible to L-BFGS. We however notice that the impact of local mixup is larger with SVHN than was with CIFAR-10.
Another noticeable difference is the impact of the number of retrieved examples on the classification accuracy. In the case of CIFAR-10, the accuracies on the clean test examples (the first column in Table 1) between using 5 and 10 retrieved examples differ significantly, while it is much less so with SVHN (the first column in Table 2.) We conjecture that this is due to a lower level of variation in input examples in SVHN, which are pictures of house numbers taken from streets, compared to those in CIFAR-10, which are pictures of general objects. Scenario 2 (Retrieval Attack) We observe a similar trend between CIFAR-10 and SVHN, when the feature extractor φ for retrieval was attacked, as shown in Tables 1-2.

ImageNet
Model We use ResNet-18 (He et al., 2016). We pretrain it as a standalone classifier on ImageNet and use the feature extractor part φ for retrieval. We use the same feature extractor φ = φ for the RaCNN without updating it. The classifier g is initialized with g and tuned during training.
In the case of ImageNet, we only try K = 10 retrieved examples with local mixup. Due to the high computational cost of the L-BFGS and Boundary attacks, we evaluate both the vanilla classifier and RaCNN against these two attacks on 200 images drawn uniformly at random from the validation set. We use Accuracy@5 which is a standard metric with ImageNet.
Scenario 1 (Direct Attack) A general trend with Ima-geNet is similar to that with either CIFAR-10 or SVHN, as can be seen in Fig. 3. The proposed RaCNN is more robust to adversarial attacks. We however do observe some differences. First, iFGSM is better at compromising both the baseline and RaCNN than L-BFGS is, in this case. Second, DeepFool is much more successful at fooling the baseline convolutional network on ImageNet than on the other two datasets, but is much less so at fooling the proposed RaCNN.
Scenario 2 (Retrieval Attack) Unlike CIFAR-10 and SVHN, we have observed that the retrieval attack is sometimes more effective than the direct attack in the case of ImageNet. For instance, FGSM can compromise the retrieval feature extractor φ to decrease the accuracy from 77.68 down to 0.20 at L 2 = 10 −4 . We observed a similar behavior with DeepFool, but not with iFGSM.

Discussion
In summary, we have observed that the proposed RaCNN, when trained with the local mixup, is more robust to adversarial attacks, at least those five considered in the experiments, than the vanilla convolutional network. More specifically, the RaCNN was most robust to the black-box, decision-based attach , while it was more easily compromised by white-box attacks, especially by the L-BFGS attack (Tabacof & Valle, 2016) which relies on a strong, quasi-Newton optimizer. This suggests that the RaCNN could be an attractive alternative to the vanilla convolutional network when deployed, for instance, in a cloud-based environment.
In Fig. 4, we show retrieval results given a query image from ImageNet. Although adversarial attack did indeed alter the retrieval engine's behavior, we see that the semantics of the original query image could still be maintained in those sets of retrieved images, suggesting two insights. First, the robustness of the RaCNN is largely due to the robustness of the retrieval engine to small perturbation in the input. Even when the retrieval quality degrades, we observe that a majority of retrieved examples are of the same, or a similar, class. Second, we could further improve the robustness by designing the feature extractor φ for the retrieval engine more carefully. For instance, an identity function φ (x) = x would correspond to retrieval based on the raw pixels, . On the left-most column shows the query image, and the next ten images have been retrieved by F . We show the retrieval results using the original image and the adversarial images one row at a time. With the amount of injected noise high enough to fool any vanilla convolutional network, the behavior of the retrieval engine changes however largely maintains the semantics of the query image. That is, most of the retrieved images contain fish, although specific species may change.
which would make the retrieval engine extremely robust to any adversarial attack imperceptible to humans. This may however results in a lower accuracy on clean examples, which is a trade-off that needs to be determined per task.
As have been observed with the existing input transformation based defense strategies, the robustness of the proposed RaCNN comes at the expense of the generalization performance on clean input examples. We have observed however that this degradation could be controlled at the expense of computational overhead by varying the number of retrieved examples per input. This controllability could be an important feature when deploying such a model in production.

Conclusion
In this paper, we proposed a novel retrieval-augmented convolutional network classifier (RaCNN) that integrates an offthe-shelf retrieval engine to counter adversarial attacks. The RaCNN was designed to tackle both off-and on-manifold adversarial examples, and to do so, we use a retrieval engine to locally characterize the data manifold as a feature-space convex hull and the attention mechanism to project the input onto this convex hull. The entire model, composed of the retrieval engine and a deep convolutional network, is trained jointly, and we introduced the local mixup learning strategy to encourage the classifier to behave linearly on the feature-space convex hull.
We have evaluated the proposed approach on three standard object recognition benchmarks-CIFAR-10, SVHN and ImageNet-against four white-box adversarial attacks and one black-box, decision-based attack. The experiments have revealed that the proposed approach is indeed more robust than the vanilla convolutional network in all the cases. The RaCNN was found to be especially robust to the black-box, decision-based attack, suggesting its potential for the cloudbased deployment scenario.
The proposed approach consists of three major components; (1) local characterization of data manifold, (2) data manifold projection and (3) regularized learning on the manifold. There is a large room for improvement in each of these components. For instance, a feature-space convex hull may be replaced with a more sophisticated kernel estimator. Projection onto the convex hull could be done better, and a learning algorithm better than local mixup could further improve the robustness against on-manifold adversarial examples. We leave these possibilities as future work.