1 Introduction↩︎

Despite the successful application in computer vision tasks such as image classification [1], [2], Deep Neural Networks (DNNs) have been found vulnerable to adversarial attacks. In particular, the DNN’s prediction can be arbitrarily changed by just applying an imperceptible perturbation to the input image [3], [4]. Moreover, such adversarial attacks can effectively compromise the recent state-of-the-art DNNs such as Inception [5], [6] and ResNet [2]. This poses a serious security risk on many DNN-based applications such as face recognition, where recognition evasion or impersonation can be easily achieved [7]–[10].

Previous adversarial attacks primarily focus on classification, however, we speculate that DNN-based image ranking systems [11]–[17] also suffer from similar vulnerability. Taking the image-based product search as an example, a fair ranking system should rank the database products according to their visual similarity to the query, as shown in Fig. 1 (row 1). Nevertheless, a malicious seller may attempt to raise the rank of his/her own product by adding perturbation to the image (CA+, row 2), or lower the rank of his competitor’s product (CA-, row 3); Besides, a “man-in-the-middle” attacker (., a malicious advertising company) could hijack and imperceptibly perturb the query image in order to promote (QA+, row 4) or impede (QA-, row 5) the sales of specific products.

Unlike classification tasks where images are predicted independently, the rank of one candidate is related to the query as well as other candidates for image ranking. The relative relations among candidates and queries determine the final ranking order. Therefore, we argue that the existing adversarial classification attacks are incompatible with the ranking scenario. Thus, we need to thoroughly study the adversarial ranking attack.

In this paper, adversarial ranking attack aims to raise or lower the ranks of some chosen candidates \(C=\{c_1,c_2,\ldots,c_m\}\) with respect to a specific query set \(Q=\{q_1,q_2,\ldots,q_w\}\). This can be achieved by either Candidate Attack (CA) or Query Attack (QA). In particular, CA is defined as to raise (abbr. CA+) or lower (abbr. CA-) the rank of a single candidate \(c\) with respect to the query set \(Q\) by perturbing \(c\) itself; while QA is defined as to raise (abbr. QA+) or lower (abbr. QA-) the ranks of a candidate set \(C\) with respect to a single query \(q\) by perturbing \(q\). Thus, adversarial ranking attack can be achieved by performing CA on each \(c\in C\), or QA on each \(q\in Q\). In practice, the choice of CA or QA depends on the accessibility to the candidate or query respectively, , CA is feasible for modifiable candidate, while QA is feasible for modifiable query.

An effective implementation of these attacks is proposed in this paper. As we know, a typical DNN-based ranking model maps objects (, queries and candidates) to a common embedding space, where the distances among them determine the final ranking order. Predictably, the object’s position in the embedding space will be changed by adding a perturbation to it. Therefore, the essential of adversarial ranking attack is to find a proper perturbation, which could push the object to a desired position that leads to the expected ranking order. Specifically, we first represent the expected ranking order as a set of inequalities. Subsequently, a triplet-like objective function is designed according to those inequalities, and combined with Projected Gradient Descent (PGD) to efficiently obtain the desired adversarial perturbation.

Opposed to the proposed attacks, adversarial ranking defense is worth being investigated especially for security-sensitive deep ranking applications. Until now, the Madry defense [18] is regarded as the most effective method for classification defense. However, we empirically discovered a primary challenge of diverging training loss while directly adapting such mechanism for ranking defense, possibly due to the generated adversarial examples being too “strong”. In addition, such defense mechanism needs to defend against distinct ranking attacks individually, but a generic defense method against all CA+, CA-, QA+ and QA- attacks is preferred.

To this end, a shift-distance based ranking defense is proposed, which could simultaneously defend against all attacks. Note that the position shift of objects in the embedding space is the key for all ranking attacks. Although different attacks prefer distinct shift directions (, CA+ and CA- often prefer opposed shifting directions), a large shift distance is their common preference. If we could reduce the shift distance of embeddings incurred by adversarial perturbation, all attacks can be simultaneously defensed. Specifically, we first propose a shift-distance based ranking attack, which aims to push the objects as far from their original positions as possible. And then, the adversarial examples generated from such attack is involved in the adversarial training. Experimental results manifest that our ranking defense can converge and moderately improve model robustness.

In addition, our ranking attacks have some good properties for realistic applications. First, our adversary is transferable, , the adversary obtained from a known DNN ranker can be directly used to attack an unknown DNN ranker (, the network architecture and parameters are unknown). Second, our attacks can be extended to universal ranking attacks with slight performance drop, , we could learn a universal perturbation to all candidates for CA, or a universal perturbation to all queries for QA. Such properties illustrate the possibility of practical black-box attack.

To the best of our knowledge, this is the first work that thoroughly studies the adversarial ranking attack and defense. In brief, our contributions are:

1. The adversarial ranking attack is defined and implemented, which can intentionally change the ranking results by perturbing the candidates or queries.

2. An adversarial ranking defense method is proposed to improve the ranking model robustness, and mitigate all the proposed attacks simultaneously.

2 Related Works↩︎

Adversarial Attacks. Szegedy  [3] claimed that DNN is susceptible to imperceptible adversarial perturbations added to inputs, due to the intriguing “blind spot” property, which was later ascribed to the local linearity [4] of neural networks. Following these findings, many white-box (model architecture and parameters are known to the adversary) attacking methods [18]–[29] are proposed to effectively compromise the state-of-the-art DNN classifiers. Among them, PGD [18] is regarded as one of the most powerful attacks [30]. Notably, adversarial examples are discovered to be transferable [31], [32] among different neural network classifiers, which inspired a series of black-box attacks [33]–[38]. On the other hand, universal (, image-agnostic) adversarial perturbations are also discovered [39], [40]. The existence of adversarial examples stimulated research interests in areas such as object detection [41]–[43], semantic segmentation [44], and automatic speech recognition [45], . It is even possible to create physical adversarial examples  [8], [10], [46], [47].

Deep Ranking. Different from the traditional “learning to rank” [48], [49] methods, DNN-based ranking methods often embed data samples (including both queries and candidates) of all modalities into a common embedding space, and subsequently determine the ranking order based on distance. Such workflow has been adopted in distance metric learning [12], [13], [50], [51], image retrieval [11], cross-modal retrieval [14]–[17], and face recognition [52].

Adversarial Attacks in Deep Ranking. For information retrieval and ranking systems, the risk of malicious users manipulating the ranking always exists [53], [54]. However, only a few research efforts have been made in adversarial attacks in deep ranking. Liu  [55] proposed adversarial queries leading to incorrect retrieval results; while Li  [56] staged similar attack with universal perturbation that corrupts listwise ranking results. None of the aforementioned research efforts explore the adversarial ranking attack. Besides, adaptation of distance-based attacks ( [25]) are unsuitable for our scenario.

Adversarial Defenses. Adversarial attacks and defenses are consistently engaged in an arms race [57]. Gradient masking-based defenses can be circumvented [58]. Defensive distillation [59], [60] has been compromised by C&W [22], [61]. As claimed in [62], ensemble of weak defenses are insufficient against adversarial examples. Notably, as an early defense method [3], adversarial training [4], [18], [63]–[69] remains to be one of the most effective defenses. Other types of defenses include adversarial detection [70], [71], input transformation/reconstruction/replacement [72]–[76], randomization [77], [78], feature denoising [79], network verification [80], [81], evidential deep learning [82], . However, defense in deep ranking systems remains mostly uncharted.

3 Adversarial Ranking↩︎

Generally, a DNN-based ranking task could be formulated as a metric learning problem. Given the query \(q\) and candidate set \(X=\{c_1,c_2,\ldots,c_n\}\), deep ranking is to learn a mapping \(f\) (usually implemented as a DNN) which maps all candidates and query into a common embedding space, such that the relative distances among the embedding vectors could satisfy the expected ranking order. For instance, if candidate \(c_i\) is more similar to the query \(q\) than candidate \(c_j\), it is encouraged for the mapping \(f\) to satisfy the inequality \(\|f(q)-f(c_i)\|<\|f(q)-f(c_j)\|\)¹, where \(\|\cdot\|\) denotes \(\ell_2\) norm. For brevity, we denote \(\|f(q)-f(c_i)\|\) as \(d(q,c_i)\) in following text.

Therefore, adversarial ranking attack is to find a proper adversarial perturbation which leads the ranking order to be changed as expected. For example, if a less relevant \(c_j\) is expected to be ranked ahead of a relevant \(c_i\), it is desired to find a proper perturbation \(r\) to perturb \(c_j\), \(\tilde{c}_j=c_j+r\), such that the inequality \(d(q,c_i)<d(q,c_j)\) could be changed into \(d(q,c_i)>d(q,\tilde{c}_j)\). In the next, we will describe Candidate Attack and Query Attack in detail.

3.1 Candidate Attack↩︎

Candidate Attack (CA) aims to raise (abbr. CA+) or lower (abbr. CA-) the rank of a single candidate \(c\) with respect to a set of queries \(Q=\{q_1,q_2,\ldots,q_w\}\) by adding perturbation \(r\) to the candidate itself, \(\tilde{c}=c+r\).

Let \(\text{Rank}_X(q,c)\) denote the rank of the candidate \(c\) with respect to the query \(q\), where \(X\) indicates the set of all candidates, and a smaller rank value represents a higher ranking. Thus, the CA+ that raises the rank of \(c\) with respect to every query \(q\in Q\) by perturbation \(r\) could be formulated as the following problem, \[\begin{align} r &= \mathop{\mathrm{arg\,min}}_{r\in\Gamma}\sum_{q\in Q}\text{Rank}_X(q,c+r), \tag{1} \\ \Gamma &= \{r \big| \|r\|_\infty\leqslant\varepsilon; r,c+r\in [0,1]^N \}, \tag{2} \end{align}\] where \(\Gamma\) is a \(\ell_\infty\)-bounded \(\varepsilon\)-neighbor of \(c\), \(\varepsilon \in [0,1]\) is a predefined small positive constant, the constraint \(\|r\|_\infty \leqslant \varepsilon\) limits the perturbation \(r\) to be “visually imperceptible”, and \(c+r\in [0,1]^N\) ensures the adversarial example remains a valid input image. Although alternative “imperceptible” constraints exist (, \(\ell_0\) [26], [83], \(\ell_1\) [23] and \(\ell_2\) [19], [22] variants), we simply follow [4], [18], [21] and use the \(\ell_\infty\) constraint.

However, the optimization problem Eq. 1 –2 cannot be directly solved due to the discrete nature of the rank value \(\text{Rank}_X(q,c)\). In order to solve the problem, a surrogate objective function is needed.

In metric learning, given two candidates \(c_p, c_n \in X\) where \(c_p\) is ranked ahead of \(c_n\), \(\text{Rank}_X(q,c_p) < \text{Rank}_X(q,c_n)\), the ranking order is represented as an inequality \(d(q,c_p)<d(q,c_n)\) and formulated in triplet loss: \[L_{\text{triplet}}(q,c_p,c_n)=\left[\beta + d(q,c_p) - d(q,c_n)\right]_+, \label{eq:triplet}\tag{3}\] where \([\cdot]_+\) denotes \(\max(0,\cdot)\), and \(\beta\) is a manually defined constant margin. This function is known as the triplet (pairwise ranking) loss [12], [52].

Similarly, the attacking goal of CA+ in Eq. 1 can be readily converted into a series of inequalities, and subsequently turned into a sum of triplet losses, \[L_{\text{CA+}}(c,Q;X)=\sum_{q\in Q}\sum_{x\in X}\big[d(q,c)-d(q,x)\big]_{+}. \label{eq:ca4395loss}\tag{4}\] In this way, the original problem in Eq. 1 –2 can be reformulated into the following constrained optimization problem: \[r=\mathop{\mathrm{arg\,min}}_{r\in\Gamma}L_{\text{CA+}}(c+r,Q;X). \label{eq:ca95opt}\tag{5}\]

To solve the optimization problem, Projected Gradient Descent (PGD) method [18], [21] (a.k.a the iterative version of FGSM [4]) can be used. Note that PGD is one of the most effective first-order gradient-based algorithms [30], popular among related works about adversarial attack.

Specifically, in order to find an adversarial perturbation \(r\) to create a desired adversarial candidate \(\tilde{c}=c+r\), the PGD algorithm alternates two steps at every iteration \(t=1, 2,\ldots,\eta\). Step one updates \(\tilde{c}\) according to the gradient of Eq. 4 ; while step two clips the result of step one to fit in the \(\varepsilon\)-neighboring region \(\Gamma\): \[\tilde{c}_{t+1}=\text{Clip}_{c,\Gamma}\big\{\tilde{c}_{t} -\alpha\text{sign}(\nabla_{\tilde{c}_t}L_{\text{CA+}}(\tilde{c}_t,Q,X))\big\}, \label{eq:PGDsteps}\tag{6}\] where \(\alpha\) is a constant hyper-parameter indicating the PGD step size, and \(\tilde{c}_1\) is initialized as \(c\). After \(\eta\) iterations, the desired adversarial candidate \(\tilde{c}\) is obtained as \(\tilde{c}_{\eta}\), which is optimized to satisfy as many inequalities as possible. Each inequality represents a pairwise ranking sub-problem, hence the adversarial candidate \(\tilde{c}\) will be ranked ahead of other candidates with respect to every specified query \(q\in Q\).

Likewise, the CA- that lowers the rank of a candidate \(c\) with respect to a set of queries \(Q\) can be obtained in similar way: \[L_{\text{CA-}}(c,Q;X)=\sum_{q\in Q}\sum_{x\in X}\big[-d(q,c)+d(q,x)\big]_{+}. \label{eq:ca-95loss}\tag{7}\]

3.2 Query Attack↩︎

Query Attack (QA) is supposed to raise (abbr. QA+) or lower (abbr. QA-) the rank of a set of candidates \(C=\{c_1,c_2,\ldots,c_m\}\) with respect to the query \(q\), by adding adversarial perturbation \(r\) to the query \(\tilde{q}=q+r\). Thus, QA and CA are two “symmetric” attacks. The QA- for lowering the rank could be formulated as follows: \[r=\mathop{\mathrm{arg\,max}}_{r\in\Gamma}\sum_{c\in C}\text{Rank}_X(q+r,c), \label{eq:qa95intuitive}\tag{8}\] where \(\Gamma\) is the \(\varepsilon\)-neighbor of \(q\). Likewise, this attacking objective can also be transformed into the following constrained optimization problem: \[\begin{align} L_{\text{QA-}}(q,C;X)&=\sum_{c\in C}\sum_{x\in X}\big[-d(q,c)+d(q,x)\big]_{+}, \tag{9}\\ r&=\mathop{\mathrm{arg\,min}}_{r\in\Gamma}L_{\text{QA-}}(q+r,C;X), \tag{10} \end{align}\] and it can be solved with the PGD algorithm. Similarly, the QA+ loss function \(L_{\text{QA+}}\) for raising the rank of \(c\) is as follows: \[L_{\text{QA+}}(q,C;X)=\sum_{c\in C}\sum_{x\in X}\big[d(q,c)-d(q,x)\big]_{+}. \label{eq:qa43}\tag{11}\]

Unlike CA, QA perturbs the query image, and hence may drastically change its semantics, resulting in abnormal retrieval results. For instance, after perturbing a “lamp” query image, some unrelated candidates (, “shelf”, “toaster”, ) may appear in the top return list. Thus, an ideal query attack should preserve the query semantics, , the candidates in \(X \setminus C\) ² should retain their original ranks if possible. Thus, we propose the Semantics-Preserving Query Attack (SP-QA) by adding the SP term to mitigate the semantic changes \(q\), ,

where \(C_{\text{SP}} = \left\{ c \in X \setminus C | \text{Rank}_{X \setminus C}(q,c) \leqslant G \right\}\), , \(C_{\text{SP}}\) contains the top-\(G\) most-relevant candidates corresponding to \(q\), and the \(L_{\text{QA+}}(q,C_{\text{SP}};X)\) term helps preserve the query semantics by retaining some \(C_{\text{SP}}\) candidates in the retrieved ranking list. Constant \(G\) is a predefined integer; and constant \(\xi\) is a hyper-parameter for balancing the attack effect and semantics preservation. Unless mentioned, in the following text QA means SP-QA by default.

3.3 Robustness & Defense↩︎

Adversarial defense for classification has been extensively explored, and many of them follows the adversarial training mechanism [18], [63], [65]. In particular, the adversarial counterparts of the original training samples are used to replace or augment the training samples. Until now, Madry defense [18] is regarded as the most effective [58], [67] adversarial training method. However, when directly adapting such classification defense to improve ranking robustness, we empirically discovered a primary challenge of diverging training loss, possibly due to the generated adversarial examples being too “strong”. Moreover, such defense mechanism needs to defend against distinct attacks individually. Therefore, a generic defense against all the proposed attacks is preferred.

Note that the underlying principle of adversarial ranking attack is to shift the embeddings of candidates/queries to a proper place, and a successful attack depends on a large shift distance as well as a correct shift direction. A large shift distance is an indispensable objective for all the CA+, CA-, QA+ and QA- attacks. Predictably, a reduction in shift distance could improve model robustness against all attacks simultaneously.

To this end, we propose a “maximum-shift-distance” attack that pushes an embedding vector as far from its original position as possible (resembles Feature Adversary [25] for classification), \(r = \mathop{\mathrm{arg\,max}}_{r\in\Gamma} d(c+r, c) \label{eq:es}\). Then we use adversarial examples obtained from this attack to replace original training samples for adversarial training, hence reduce the shift distance incurred by adversarial perturbations.

A ranking model can be normally trained with the defensive version of the triplet loss:

Unlike the direct adaptation of Madry defense, the training loss does converge in our experiments.

4 Experiments↩︎

To validate the proposed attacks and defense, we use three commonly used ranking datasets including MNIST [84], Fashion-MNIST [85], and Stanford Online Product (SOP) [50]. We respectively train models on these datasets with PyTorch [86], and conduct attacks ³ on their corresponding test datasets (used as \(X\)).

Evaluation Metric. Adversarial ranking attack aims to change the ranks of candidates. For each candidate \(c\), its normalized rank is calculated as \(R(q,c) = \frac{\text{Rank}_X(q,c)}{|X|}\times 100\%\) where \(c\in X\), and \(|X|\) is the length of full ranking list. Thus, \(R(q,c)\in [0,1]\), and a top ranked \(c\) will have a small \(R(q,c)\). The attack effectiveness can be measured by the magnitude of change in \(R(q,c)\).

Performance of Attack. To measure the performance of a single CA attack, we average the rank of candidate \(c\) across every query \(q \in Q\), , \(R_\text{CA}(c)=\sum_{q\in Q}{R}(q,c)/w\). Similarly, the performance of a single QA attack can be measured by the average rank across every candidate \(c \in C\), , \(R_\text{QA}(q)=\sum_{c\in C}{R}(q,c)/m\). For the overall performance of an attack, we conduct \(T\) times of independent attacks and report the mean of \(R_\text{CA}(c)\) or \(R_\text{QA}(q)\), accordingly.

CA+ & QA+. For CA+, the query set \(Q\) is randomly sampled from \(X\). Likewise, for QA+, the candidate set \(C\) is from \(X\). Without attack, both the \(R_\text{CA}(c)\) and \(R_\text{QA}(q)\) will approximate to \(50\%\), and the attacks should significantly decrease the value.

CA- & QA-. In practice, the \(Q\) for CA- and the \(C\) for QA- cannot be randomly sampled, because the two attacks are often to lower some top ranked candidates. Thus, the two sets should be selected from the top ranked samples (top-\(1\%\) in our experiments) in \(X\). Formally, given the candidate \(c\) for CA-, we randomly sample the \(w\) queries from \(\left\{ q \in X | R(c,q) \leqslant 1\% \right\}\) as \(Q\). Given the query \(q\) for QA-, \(m\) candidates are randomly sampled from \(\left\{ c \in X | R(q,c) \leqslant 1\% \right\}\) as \(C\). Without attack, both the \(R_\text{CA}(c)\) and \(R_\text{QA}(q)\) will be close to \(0\%\), and the attacks should significantly increase the value.

Hyper-Parameters. We conduct CA with \(w \in \{1,2,5,10\}\) queries, and QA with \(m \in \{1,2,5,10\}\) candidates, respectively. In QA, we let \(G=5\). The SP balancing parameter \(\xi\) is set to \(1\) for QA+ , and \(10^2\) for QA-. In addition, We investigate attacks of different strength \(\varepsilon\),  \(0.01,0.03,0.1,0.3\) on MNIST and Fashion-MNIST following [18], and \(0.01,0.03,0.06\) on SOP following [65]. The PGD step size is empirically set to \(\alpha=\min(\max(\frac{\varepsilon}{10},\frac{1}{255}),0.01)\), and the number of PGD iterations to \(\eta=\min(\max(10, \frac{2\varepsilon}{\alpha}),30)\). We perform \(T=|X|\) times of attack to obtain the reported performance.

Adversarial Defense. Ranking models are trained using Eq. 13 with the strongest adversary following the procedure of Madry defense [18].

4.1 MNIST Dataset↩︎

Following conventional settings with the MNIST [84] dataset, we train a CNN ranking model comprising \(2\) convolutional layers and \(1\) fully-connected layer. This CNN architecture (denoted as C2F1) is identical to the one used in [18] except for the removal of the last fully-connected layer. Specifically, the ranking model is trained with cosine distance and triplet loss. The retrieval performance of the model is Recall@1=\(99.1\%\) (R@\(1\)), as shown in Tab. 1 in grey highlight.

Attacking results against this vanilla model (, the ranking model which is not enhanced with our defense method) are presented in Tab. 1. For example, a strong CA+ attack (, \(\varepsilon=0.3\)) for \(w=1\) can raise the rank \(R_\text{CA}(c)\) from \(50\%\) to \(2.1\%\). Likewise, the rank of \(C\) can be raised to \(9.1\%\), \(13.0\%\), \(17.9\%\) for \(w=2,5,10\) chosen queries, respectively.

On the other hand, a strong CA- attack for \(w=1\) can lower the rank \(R_\text{CA}(c)\) from \(2.1\%\) to \(93.9\%\). The results of strong CA- attacks for \(w=2,5,10\) are similar to the \(w=1\) case.

The results of QA+ and QA- are also shown in Tab. 1. the rank changes with QA attacks are less dramatic (but still significant) than CA. This is due to the additional difficulty introduced by SP term in Eq. 12 , and the QA attack effectiveness is inversely correlated with \(\xi\). For instance, a strong QA- for \(m=1\) can only lower the rank \(R_\text{QA}(q)\) from \(0.5\%\) to \(8.6\%\), but the attacking effect can be further boosted by decreasing \(\xi\). More experimental results are presented in following discussion. In brief, our proposed attacks against the vanilla ranking model is effective.

Next, we evaluate the performance of our defense method. Our defense should be able to enhance the robustness of a ranking model, which can be measured by the difference between the attack effectiveness with our defense and the attack effectiveness without our defense. As a common phenomenon of adversarial training, our defense mechanism leads to a slight retrieval performance degradation for unperturbed input (highlighted in blue in Tab. 2), but the attacking effectiveness is clearly mitigated by our defense. For instance, the same strong CA+ attack for \(w=1\) on the defensive model (, the ranking model which is enhanced by our defense method) can only raise the rank \(R_\text{CA}(c)\) from \(50\%\) to \(30.7\%\), compared to its vanilla counterpart raising to \(2.1\%\). Further analysis suggests that the weights in the first convolution layer of the defensive model are closer to \(0\) and have smaller variance than those of the vanilla model, which may help resist adversarial perturbation from changing the layer outputs into the local linear area of ReLU [4].

To visualize the effect of our attacks and defense, we track the attacking effect with \(\varepsilon\) varying from \(0.0\) to \(0.3\) on the vanilla and defensive models, as shown in Fig. 2. It is noted that our defense could significantly suppress the maximum embedding shift distance incurred by adversarial perturbation to nearly \(0\), but the defensive model is still not completely immune to attacks. We speculate the defensive model still has “blind spots” [3] in some local areas that could be exploited by the attacks.

In summary, these results and further experiments suggest that: (1) deep ranking models are vulnerable to adversarial ranking attacks, no matter what loss function or distance metric is selected; (2) vanilla models trained with contrastive loss are more robust than those trained with triplet loss. This is possibly due to contrastive loss explicitly reducing the intra-class embedding variation. Additionally, our defense method could consistently improve the robustness of all these models; (3) different distance metrics have almost negligible contribution on robustness. Specifically, Euclidean distance-based models are slightly more susceptible to weak (, \(\varepsilon=0.03\)) attacks; (4) Euclidean distance-based models are harder to defend than cosine distance-based ones. Beyond these experiments, we also find that the margin hyper-parameter \(\beta\) of triplet loss and the dimensionality of the embedding space have marginal influences on model robustness.

4.2 Fashion-MNIST Dataset↩︎

0.2em

Fashion-MNIST [85] is an MNIST-like but more difficult dataset, comprising \(60,000\) training examples and \(10,000\) test samples. The samples are \(28\times 28\) greyscale images covering \(10\) different fashion product classes, including “T-shirt” and “dress”, . We train the vanilla and defensive models based on the cosine distance and triplet loss and conduct attack experiments.

The attack and defense results are available in Tab. 3. From the table, we note that our attacks could achieve better effect compared to experiments on MNIST. For example, in a strong CA+ for \(w=1\), the rank \(R_\text{CA}(c)\) can be raised to \(1.3\%\). On the other hand, despite the moderate improvement in robustness, the defensive model performs worse in unperturbed sample retrieval, as expected. The performance degradation is more pronounced on this dataset compared to MNIST. We speculate the differences are related to the increased dataset difficulty.

4.3 Stanford Online Products Dataset↩︎

Stanford Online Products (SOP) dataset [50] contains \(120\)k images of \(23\)k classes of real online products from eBay for metric learning. We use the same dataset split as used in the original work [50]. We also train the same vanilla ranking model using the same triplet ranking loss function with Euclidean distance, except that the GoogLeNet [5] is replaced with ResNet-18 [2]. The ResNet-18 achieves better retrieval performance.

Attack and defense results on SOP are present in Tab. 4. It is noted that our attacks are quite effective on this difficult large-scale dataset, as merely \(1\%\) perturbation (\(\varepsilon=0.01\)) to any candidate image could make it ranked ahead or behind of nearly all the rest candidates (as shown by the CA+ and CA- results with \(w=1\)). The QA on this dataset is significantly effective as well. On the other hand, our defense method leads to decreased retrieval performance, i.e. R@1 from \(63.1\%\) to \(46.4\%\), which is expected on such a difficult dataset. Meanwhile, our defense could moderately improve the model robustness against relatively weaker adversarial examples (e.g. \(\varepsilon=0.01\)), but improving model robustness on this dataset is more difficult, compared to experiments on other datasets.

By comparing the results among all the three datasets, we find ranking models trained on harder datasets more susceptible to adversarial attack, and more difficult to defend. Therefore, we speculate that models used in realistic applications could be easier to attack, because they are usually trained on larger-scale and more difficult datasets.

0.2em

5 Discussions↩︎

In this section, we study the transferability of our adversarial ranking examples, and universal adversarial perturbation for ranking. Both of them illustrate the possibility of practical black-box attack. Additionally, we also perform parameter search on the balancing parameter \(\xi\) for QA.

5.1 Adversarial Example Transferability↩︎

As demonstrated in previous experiments, deep ranking models can be compromised by our white-box attacks. In realistic scenarios, the white-box attacks are not practical enough because the model to be attacked is often unknown (, the architecture and parameters are unknown).

On the other hand, adversarial examples for classification have been found transferable [31], [32] (model-agnostic) between different models with different network architectures. And the transferability has become the foundation of a class of existing black-box attacks. Specifically, for such a typical attack, adversarial examples are generated from a replacement model [31] using a white-box attack, and are directly used to attack the black-box model.

Adversarial ranking attack could be more practical if the adversarial ranking examples have the similar transferability. Besides the C2F1 model, we train two vanilla models on the MNIST dataset: (1) LeNet [84], which has lower model capacity compared to C2F1; (2) ResNet-18 [2] (denoted as Res18), which has a better network architecture and higher model capacity.

0.2em

The results are present in Tab. ¿tbl:tab:transfer?. For example, in the CA+ transfer attack, we generate adversarial candidates from the C2F1 model and directly use them to attack the Res18 model (row 2, column 3, top-left table), and the ranks of the adversarial candidates with respect to the same query is still raised to \(31.3\%\). We also find the CA- transfer attack is effective, where the ranks of our adversarial candidates are lowered, e.g. from \(2.1\%\) to \(9.3\%\) (row 2, column 3, bottom-left table). Similar results can be observed on the QA transfer experiments, and they show weaker effect due to the SP term.

From the results, we find that: (1) CNN with better architecture and higher model capacity (, Res18) is less susceptible to adversarial ranking attack. This conclusion is consistent with Madry’s [18], which claims that higher model capacity could help improve model robustness; (2) adversarial examples generated from the Res18 have the most significant effectiveness in transfer attack; (3) CNN of low model capacity (, LeNet), performs moderately in terms of both adversarial example transferability and model robustness. We speculate its robustness stems from a forced regularization effect due low model capacity. Beyond these, adversarial ranking examples are transferable disregarding the difference in loss function or distance metric.

Apart from transferability across different architectures, we also investigated the transferability between the C2F1 models with different network parameters. Results suggest similar transferability between these models. Notably, when transferring adversarial examples to a defensive C2F1 model, the attacking effect is significantly mitigated. The result further demonstrates the effectiveness of our defense.

5.2 Universal Perturbation for Ranking↩︎

Recently, universal (image-agnostic) adversarial perturbation [39] for classification has been found possible, where a single perturbation may lead to misclassification when added to any image. Thus, we also investigate the existence of universal adversarial perturbation for ranking.

To this end, we follow [39] and formulate the image-agnostic CA+ (abbr. I-CA+). Given a set of candidates \(C=\{c_1,c_2,\ldots,c_m\}\) and a set of queries \(Q=\{q_1,q_2,\ldots,q_w\}\), I-CA+ is to find a single universal adversarial perturbation \(r\), so that the rank of every perturbed candidate \(\tilde{c}=c+r ~ (c\in C)\) with respect to \(Q\) can be raised. The corresponding optimization problem of I-CA+ is: \[r=\mathop{\mathrm{arg\,min}}_{r\in\Gamma} \sum_{c\in C} L_\text{CA+}(c+r,Q;X).\] When applied with such universal perturbation, the rank of any candidate w.r.t \(Q\) is expected to be raised. The objective functions of I-CA-, I-QA+ and I-QA- can be obtained in similar way. Note, unlike [56] which aims to find universal perturbation that can make image retrieval system return irrelevant results, our universal perturbations have distinct purposes.

We conduct experiment on the MNIST dataset. For I-CA+ attack, we randomly sample \(5\%\) of \(X\) for generating the universal perturbation. Following [39], another non-overlapping \(5\%\) examples are randomly sampled from \(X\) to test whether the generated perturbation is generalizable on “unseen” (, not used for generating the perturbation) images. Experiments for the other image-agnostic attacks are conducted similarly. Note, we only report the I-CA- and I-QA- effectiveness on the \(1\%\) top ranked samples, similar to CA- and QA-.

0.4em

As shown in Tab. 5, our I-CA can raise the ranks of \(C\) to \(18.1\%\), or lower them to \(9.5\%\). When added to “unseen” candidate images, our universal perturbation could retain nearly the same effectiveness. This may due to low intra-class variance of the MNIST dataset.

5.3 Semantics Preserving for QA↩︎

As discussed previously, the Query Attack (QA) may drastically change the semantics of the query \(q\). To alleviate this problem, the Semantics-Preserving (SP) term is added to the naive QA to help preserve the query semantics. Predictably, it is more difficult to perform QA with a large \(\xi\), as the ranks of \(C_\text{SP}\) are almost not allowed to be changed.

To investigate the actual influence of the balancing parameter \(\xi\), we provide parameter search on it with MNIST dataset. In particular, We set \(\xi\) to \(0,10^0,10^2,10^4\), and compare their results. Note that when \(\xi=0\), the QA becomes naive QA as the SP term is eliminated. With a strong SP constant, \(\xi=10^4\), the semantics of the chosen query is almost not allowed to be changed, hence result in extreme difficulty of attack.

As shown in Tab. 6, setting \(\xi\) to \(0\) could greatly boost the attacking effect, but consequently the ranks of \(C_\text{SP}\) will be drastically changed. In contrast, when \(\xi\) is set to the excessive value \(10^4\) for a perfectly stealth QA, the attack can still raise the rank of chosen candidate from \(50\%\) to \(37.9\%\) in QA+ with \(m=1\), or lower the rank of chosen candidate from \(0.5\%\) to \(1.9\%\) in QA- with \(m=1\). During these attacks, the ranks of \(C_\text{SP}\) are kept within \(0.1\) despite of the extreme difficulty. It means the query semantics can be preserved. In practice, we empirically set the parameter \(\xi\) as \(1\) for QA+, or as \(10^2\) for QA- for the balance between attack effectiveness and preserving query semantics.

0.2em

6 Conclusion↩︎

Deep ranking models are vulnerable to adversarial perturbations that could intentionally change the ranking result. In this paper, we define and implement adversarial ranking attack that can compromise deep ranking models. We also propose an adversarial ranking defense that can significantly suppress embedding shift distance and moderately improve the ranking model robustness. Moreover, the transferability of our adversarial examples and the existence of universal adversarial perturbations for ranking attack illustrate the possibility of practical black-box attack and potential risk of realistic ranking applications. In the potential of future work, we may explore better ranking loss functions, defenses, and black-box attacks.

Acknowledgements↩︎

This work was supported partly by National Key R&D Program of China Grant 2018AAA0101400, NSFC Grants 61629301, 61773312, 61976171, and 61672402, China Postdoctoral Science Foundation Grant 2019M653642, Young Elite Scientists Sponsorship Program by CAST Grant 2018QNRC001, and Natural Science Foundation of Shaanxi Grant 2020JQ-069.

7 Adversarial Example Visualization↩︎

Some adversarial ranking examples are presented in this section. Every figure contains three rows of pictures. The first row shows \(c\), \(r\), \(\tilde{c}=c+r\) for CA, or \(q\), \(r\), \(\tilde{q}=q+r\) for QA. The second row shows the query and the original retrieval results, as well as the chosen candidate \(c\) and its immediately adjacent candidates. The third row shows the effects of the attack on the ranking list, , either the chosen candidate \(c\) is replaced with \(\tilde{c}\) for CA, or the query \(q\) is replaced with \(\tilde{q}\) for QA. The digits above every picture is the value of \(\text{Rank}_X(q,\cdot)-1\) ⁴.

Pictures with a ” ” mark on the top-left corner are adversarial examples. The “\(\leftarrow\)” indicates the chosen candidate whose rank will be raised. The “\(\rightarrow\)” indicates the chosen candidate whose rank will be lowered.

Full visualization results including those on SOP (removed from the Arxiv version due to file size limit) can be found at https://github.com/cdluminate/advrank-pub.

7.1 MNIST Dataset↩︎

CA+. See Fig. 3,4,5. CA-. See Fig. 6,7,8.

QA+. See Fig. 9,10,11. QA-. See Fig. 12,13,14.

7.2 Fashion-MNIST↩︎

CA+. See Fig. 15,16,17. CA-. See Fig. 18,19,20.

QA+. See Fig. 21,22,23. QA-. See Fig. 24,25,26.

7.3 Semantic-Preserving for QA↩︎

Conducting Query Attack without preserving the query semantics will often lead to irrelevant retrieval results at the top of the ranking list, as shown in Fig. 27, which raises red flags and possibly reveals the attack. Therefore, the value of the Semantics-Preserving term in QA is substantial, as it keeps the retrieval results as “normal” as possible while achieving the attacking goal.

8 Complete Results of Attack & Defense↩︎

Some experiments and details on MNIST, Fashion-MNIST and SOP datasets are omitted in the manuscript due to limited space. In this section, we present the complete experimental results on these datasets, including the average rank of \(C_\text{SP}\) during QA. Besides, we also conduct attacking experiments on ranking models trained with different combinations of loss functions and distance metrics. For brevity, we denote the (Cosine distance, Triplet loss) setting as (CT), the (Euclidean distance, Contrastive loss) as (EC). Models trained with our defense method will have a trailing “D” in notation, the (CT) model with our defense will be denoted as (CTD).

See Tab. 8 for complete results on MNIST.

See Tab. 9 for complete results on Fashion-MNIST.

See Tab. 7 for results on SOP.

0.2em

0.2em

9 Complete Results on Transferability↩︎

9.1 Fashion-MNIST↩︎

In addition to the transferability experiment on MNIST dataset, we also conduct the same transferability experiment on the Fashion-MNIST dataset, as shown in Tab. ¿tbl:tab:transfer-fashion?.

9.2 “Self-Transfer” Attack on MNIST↩︎

0.2em

In the adversarial ranking example transferability experiments, we transfer adversarial examples between neural networks with different architectures. In this section, we transfer adversarial examples between neural networks based on the same architecture but with different parameters.

We train three vanilla C2F1 models (denoted as C2F1-1, C2F1-2, and C2f1-3) on MNIST dataset and two models with our defense (denoted as C2F1-D1, C2F1-D2). All these models have exactly the same architecture, but different parameters. Transferability experimental results between these models are present in Tab. 10.

10 Complete Results for Universal Perturbation↩︎

10.1 MNIST↩︎

See Tab. 5.

0.2em

10.2 Fashion-MNIST↩︎

As shown in Tab. 12, Image-agnostic adversarial perturbation has better effect on seen data from Fashion-MNIST, but the gap between the effect on seen samples and that on unseen samples is slightly larger, which may due to the higher intra-class variance of Fashion-MNIST than MNIST.

0.2em

11 Complete Parameter Search on \(\xi\)↩︎

See Tab. 13.

0.2em

12 Analysis on Our Defense↩︎

Ian  [4] proposed a linear explanation of adversarial examples:

In our experiments, we analysed the parameters in models trained on MNIST, as shown in Fig. 28, 29, 30. These violin plots suggest that

• the weights in the first convolution layer of the defensive model are closer to \(0\) and have smaller variance than those of the vanilla model. That means the \(h\) in the above quotation is decreased with our defense, and it will be harder for the \(r\) to incur a large increase in activation \(\varepsilon k h\).

• the bias in the first convolution layer of the defensive model tend to be negative values instead of being nearly “zero-mean”. These negative bias could help further suppress the increase in activation caused by purturbation \(r\).

Therefore, Ian ’s [4] theory could explain why our defense works, as the resulting differences in network parameters may help reduce the probability for adversarial perturbation to increase the layer outputs into the local linear area of ReLU.

13 Alternative Attack↩︎

13.1 Distance-based Ranking Attack↩︎

In order to implement the proposed ranking attack, alternative attacking objectives are possible. Some related works such as Feature Adversary [25] generates untargeted adversarial examples against classifiers by maximizing the distance shift of representation vectors off their original locations. This may inspire an alternative version of CA or QA objective functions which are directly based on distance. For example, such alternative objective for CA+ and QA- could be as follows: \[\begin{align} r&=\mathop{\mathrm{arg\,min}}_{r\in\Gamma}\sum_{q\in Q}d(q,c+r)\\ r&=\mathop{\mathrm{arg\,max}}_{r\in\Gamma}\sum_{c\in C}d(q+r,c). \end{align}\] However, it must be pointed out that our method significantly differs from feature adversary [25]: (1) Feature adversary concerns the pairwise similarity of source-target representations, while our image ranking problem concerns the ranking order of multiple candidates; (2) Feature adversary attempts to reduce the \(\ell_2\) distance as much as possible, while our triplet-like loss attempts to make positive candidates closer to query than the negative ones, which well fits the objective of ranking order optimization. Such relative distance optimization becomes more important since our attack simultaneously involves multiple queries and multiple candidates; (3) The \(\ell_2\) distance based methods suffer from inevitable disadvantages. Specifically, distance-based objectives are suboptimal, because they disregard the relative positions among the candidates and queries.

As shown in the top-left part of Fig. 31, the solution set for for distance-based CA+ (the green dotted line) contains suboptimal solutions. Similarly, in the bottom-left part of Fig. 31 the distance-based objective for QA- tends to maximize the sum of distance neglecting the ranking result, and further optimization (moving \(\tilde{q}\) along the green arrow) will not change the ranking result. In contrast, our proposed inequality-based method does not suffer from these issues, as shown in the top-right and bottom-right parts.

We also implemented such distance-based method and compared it with our triplet-like method, as shown in Tab. 14. Experimental results suggest that our method always outperforms distance-based method by a margin. Especially for QA-, the distance-based objective is very difficult to optimize because the distance-based Semantics-Preserving term contradicts with the other term in the loss function. In summary, distance-based method is not well-suited for our proposed adversarial ranking attack, especially in the scenario of QA-.

14 Alternative Defense↩︎

Apart from the defense provided in the manuscript, we also tried some other loss functions for adversarial training. In literature, there is no predominant choice for the adversarial training loss function. The only common trait among these choices is that all of them involve adversarial examples. Inspired by previous works, we also implement some alternative defenses for ranking systems as follows.

14.1 Straightforward Adaptation of Madry Defense↩︎

Madry [18] formularised improving neural network classifier robustness as a min-max optimization problem, where the inner maximization seeks to generate adversarial examples that lead to maximum cross-entropy loss \(L_\text{CE}\), while the outer minimization tunes the neural network parameters \(\theta\) to suppress the cross-entropy loss: \[\min_\theta \Big\{ \mathbb{E}_{(x,y)\sim D} \big[ \max_{r\in\Gamma} L_\text{CE} (x+r,y) \big] \Big\}\] where \((x,y)\) is a pair of image and ground-truth class label.

Similarly, we follow the idea and use a similar defense for ranking models: \[\min_\theta \Big\{ \mathbb{E}_{(q,c_p,c_n)\sim D} \big[ \max_{r\in\Gamma}L_{\text{triplet}}(q+r,c_p,c_n) \big] \Big\} \label{eq:mintmaxt}\tag{14}\] where the inner maximization aims to generate strongest adversarial examples that could lead to triplet ranking error and a large loss value, while the outer minimization seeks network parameters that could reduce such error.

However, during experiments, we observe that such defensive loss function always diverges, possibly due to the adversarial examples generated by the inner problem being too “strong”. We leave further investigation into this problem for future work.

14.2 Straightforward Adaptation of Ian Defense↩︎

Ian [4] proposed the following loss function for adversarial training: \[\begin{align} L_\text{Ian}(x, y) &= \alpha L_\text{CE}(x,y) \\ &+ (1-\alpha)L_\text{CE}(x + \varepsilon \text{sign}(\nabla_x L_\text{CE} (x,y) )) \end{align}\] where the first term is a normal Cross-Entropy loss, and the second term is the cross-entropy loss with untargeted adversarial example that aims to increase the loss value. Constant \(\alpha\) is a balancing parameter.

When adapted to a deep ranking system, this defense method also suffers from the diverging issue similar to Madry’s defense.

0.2em

14.3 Directly Suppressing Shift Distance↩︎

As discussed in the manuscript, another possible adversarial training method could be to directly suppress the maximum shift distance of embedding vectors, :

where the most severe distance shift incurred by adversarial perturbations is explicitly suppressed, in addition to a standard ranking loss term.

Experimental results (Tab. 15) show that cosine distance-based ranking models are more robust with this defense. However, we note that this loss may numerically explode on an Euclidean distance-based embedding model, as a strong adversary can gradually cause very large embedding shift distance. To mitigate such divergence issue, we also tried to add a balancing parameter to greatly scale down the second term of the loss function, but the instability problem was still not alleviated.

Due to the lack of universality, we leave this alternative defense in supplementary material as a pure discussion, and possible improvements as future work.

References↩︎

---

1. Sometimes cosine distance is used instead.↩︎

2. The complement of the set \(C\).↩︎

3. Specifically, we use PGD without random starts [18].↩︎

4. In mathematical context the rank counts from \(1\), but in implementation it counts from \(0\) instead. Hence the offset.↩︎