,

# Certified Robustness to Word Substitution Ranking Attack for Neural Ranking
Models

Chen Wu<EMAIL_ADDRESS>CAS Key Lab of Network Data Science and
Technology, ICT, CASUniversity of Chinese Academy of SciencesBeijingChina ,
Ruqing Zhang<EMAIL_ADDRESS>,  Jiafeng Guo<EMAIL_ADDRESS>CAS
Key Lab of Network Data Science and Technology, ICT, CASUniversity of Chinese
Academy of SciencesBeijingChina ,  Wei Chen<EMAIL_ADDRESS>,  Yixing
Fan<EMAIL_ADDRESS>CAS Key Lab of Network Data Science and Technology,
ICT, CASUniversity of Chinese Academy of SciencesBeijingChina ,  Maarten de
Rijke  0000-0002-1086-0202<EMAIL_ADDRESS>University of
AmsterdamAmsterdamThe Netherlands and  Xueqi Cheng<EMAIL_ADDRESS>CAS Key Lab
of Network Data Science and Technology, ICT, CASUniversity of Chinese Academy
of SciencesBeijingChina

(2022)

###### Abstract.

Neural ranking models (NRMs) have achieved promising results in information
retrieval. NRMs have also been shown to be vulnerable to adversarial examples.
A typical Word Substitution Ranking Attack (WSRA) against NRMs was proposed
recently, in which an attacker promotes a target document in rankings by
adding human-imperceptible perturbations to its text. This raises concerns
when deploying NRMs in real-world applications. Therefore, it is important to
develop techniques that defend against such attacks for NRMs. In empirical
defenses adversarial examples are found during training and used to augment
the training set. However, such methods offer no theoretical guarantee on the
models’ robustness and may eventually be broken by other sophisticated WSRAs.
To escape this arms race, rigorous and provable certified defense methods for
NRMs are needed.

To this end, we first define the Certified Top-$K$ Robustness for ranking
models since users mainly care about the top ranked results in real-world
scenarios. A ranking model is said to be Certified Top-$K$ Robust on a ranked
list when it is guaranteed to keep documents that are out of the top $K$ away
from the top $K$ under any attack. Then, we introduce a Certified Defense
method, named CertDR, to achieve certified top-$K$ robustness against WSRA,
based on the idea of randomized smoothing. Specifically, we first construct a
smoothed ranker by applying random word substitutions on the documents, and
then leverage the ranking property jointly with the statistical property of
the ensemble to provably certify top-$K$ robustness. Extensive experiments on
two representative web search datasets demonstrate that CertDR can
significantly outperform state-of-the-art empirical defense methods for
ranking models.

Certified Top-$K$ Robustness, Certified Defense, Word Substitution Ranking
Attack, Ranking Models

††journalyear: 2022††copyright: acmcopyright††conference: Proceedings of the
31st ACM International Conference on Information and Knowledge Management;
October 17–21, 2022; Atlanta, GA, USA††booktitle: Proceedings of the 31st ACM
International Conference on Information and Knowledge Management (CIKM ’22),
October 17–21, 2022, Atlanta, GA, USA††price: 15.00††doi:
10.1145/3511808.3557256††isbn: 978-1-4503-9236-5/22/10††ccs: Information
systems Retrieval models and ranking††ccs: Information systems Adversarial
retrieval

##  1\. Introduction

Neural ranking models (NRMs) (Onal et al., 2018; Mitra et al., 2017; Dai and
Callan, 2019), especially pre-trained ranking models (Nogueira and Cho, 2019;
Khattab and Zaharia, 2020; Ma et al., 2021), have led to substantial
performance improvements in a wide range of search tasks (Ma et al., 2021;
Joshi et al., 2020; Gu et al., 2020). We have also seen NRMs being used in
various practical usages in the enterprise (Lin et al., 2021). Despite their
success, recent observations (Wu et al., 2021, 2022) show that NRMs are
vulnerable to adversarial examples. A typical word substitution ranking attack
(WSRA) (Wu et al., 2022) was proposed and proved successful for attacking
NRMs. In this setting, an attacker promotes a target document in rankings by
replacing important words in its text with their synonyms in a semantic-
preserving way. The adversarial documents generated by WSRAs are imperceptible
to humans but can easily fool NRMs. This may bring great concerns when
deploying these models to real-world applications. Thus, efficient methods for
defending against such attacks are of critical importance for deploying modern
NRMs to practical search engines.

Various approaches have been developed to defend against adversarial attacks.
One representative type of defense is the empirical defense method (Madry et
al., 2018; Wang et al., 2019), where the set of perturbations is known at
training time and adversarial examples are added to the training set (Wang et
al., 2019). However, it is insufficient when considering all possible WSRAs in
which each word in a document can be replaced with any of its synonyms.
Consequently, such defenses may eventually be broken by other sophisticated
WSRAs (Ye et al., 2020). To escape this arms race, procedures with rigorous
and provable robustness guarantees are of special importance to the study of
robustness of NRMs. In general, a model is said to be _certified robust_ if
such an attack is guaranteed to fail, no matter how the attacker manipulates
the input. A line of work on certified defenses against any admissible
adversarial attack has recently been introduced in image and text
classification (Cohen et al., 2019; Katz et al., 2017; Singh et al., 2019).
However, existing certified defense approaches are mainly for simple
classification scenarios. They are quite distant from IR requirements, not
just due to input differences (discrete text vs. continuous image (Cohen et
al., 2019)), but also due to the prediction type (ranked list vs. class label
(Ye et al., 2020)). In this sense, the recent, promising advances in certified
defenses have yet to bring similar robustness guarantees in how NRMs are
approached.

Therefore, in this work, we make the first attempt to develop a certified
defense method for NRMs so as to pursue adversarial immunization to WSRA to
some extent. To this end, we need to answer two key questions: First, what is
certified robustness in IR? Second, can we train NRMs that are robust in this
sense?

Figure 1. Illustration of the WSRA and Certified Top-$K$ Robustness. Given a
ranking model, it is said to be Certified Top-$K$ Robust against WSRA on a
ranked list if it is able to prevent documents outside top $K$ from appearing
in top $K$ for all the possible WSRAs.

To answer the first question, based on the previous definition and inspired by
the IR properties, we propose to define the Certified Top-$K$ Robustness of
ranking models. In IR, it seems well-accepted that in many scenarios users
mainly care about top ranked results (Xia et al., 2009; Niu et al., 2012).
Some observations have shown that traffic (or click-through rate) falls off
steeply as users work their way down the search results (Joachims et al.,
2017). Many widely-used ranking metrics (e.g., MRR and nDCG) are concentrated
on top ranked predictions. Therefore, as illustrated in Figure 1, a ranking
model is said to be _Certified Top- $K$ Robust against WSRA_ on a ranked list
if it is able to prevent documents outside the top $K$ from appearing in top
$K$ for all possible WSRAs.

To answer the second question, we propose a novel Certified Defense method for
Ranking models, CertDR for short, to enhance a model’s certified robustness
against WSRA. To avoid exponential computational costs, our method is based on
the idea of randomized smoothing (Cohen et al., 2019; Ye et al., 2020), which
replaces the ranking model with a smoothed ranker for which it is easier to
verify the certified robustness. Specifically, we first construct a smoothed
ranker by averaging the output ranking scores of randomly perturbed documents.
Then, we obtain a certification criterion to judge models’ certified top-$K$
robustness by leveraging the ranking property and statistical property of
randomized ensembles. Finally, we design a practical certified defense
algorithm, including a noise data augmentation strategy based on the perturbed
documents for training and a rigorous statistical procedure to certify the
top-$K$ robustness.

We conduct experiments on two web search benchmark datasets, i.e., the MS
MARCO document ranking dataset and the MS MARCO passage ranking dataset. We
first compare the certified robustness among different ranking models (i.e.,
traditional probabilistic ranking models, and advanced neural ranking models)
under CertDR. Based on the evaluation results, there clearly remains room for
future certified robustness improvements. Besides, we compare with several
state-of-the-art empirical defense methods and our experimental results show
that CertDR can achieve the best defense performance against WSRA.

##  2\. Related Work

###  2.1. Text Ranking Models

Ranking models lie at the heart of IR. Many different ranking models have been
proposed over the past decades, including probabilistic models (Ponte and
Croft, 1998; Robertson and Walker, 1994) (e.g., BM25 (Robertson and Walker,
1994)) and learning-to-rank (LTR) models (Liu, 2011). With the advance of deep
learning, we have witnessed a substantial growth of interest in NRMs (Onal et
al., 2018; Mitra et al., 2017; Dai and Callan, 2019), achieving promising
results in a variety of search tasks (Ma et al., 2021; Joshi et al., 2020; Gu
et al., 2020). Recently, pre-trained ranking models such as BERT-based models
(Nogueira and Cho, 2019; Khattab and Zaharia, 2020) have shown substantial
performance improvements both in academic research and industry (Lin et al.,
2021). However, recent observations (Wu et al., 2021, 2022) have shown that
NRMs are vulnerable to adversarial examples. In this paper, we study how to
defend against adversarial attacks for NRMs.

###  2.2. Adversarial Attacks

Adversarial attacks aim to generate human-imperceptible adversarial examples
by perturbing inputs to maximally increase a model’s risk of making wrong
predictions. Adversarial examples were first discovered in the image domain
(Szegedy et al., 2013), where early research has developed powerful white-box
attack methods, e.g., Fast Gradient Sign Method (FGSM, Goodfellow et al.,
2014) and Projected Gradient Descent (PGD, Madry et al., 2017), for attacking
continuous image data.

The existence and pervasiveness of adversarial examples have also been
observed in the text domain (Zhang et al., 2020). Despite the fact that
generating adversarial examples for texts has proven to be more challenging
than for images due to their discrete nature, prior work has explored
adversarial attacks for many language tasks, including text classification
(Gao et al., 2018; Liang et al., 2017), dialogue systems (Cheng et al., 2019),
and natural language inference (Alzantot et al., 2018). Among these attacks,
word substitution attacks (Alzantot et al., 2018; Ren et al., 2019; Zang et
al., 2019), which replace words in a sentence with their synonyms via a
synonym table, have attracted considerable attention. The reason is they can
preserve the syntactic and semantics of the original input to the most
considerable extent and are very hard to discern, even from a human’s
perspective (Dong et al., 2020).

Document authors compete for more favorable positions in rankings (Goren et
al., 2018). The behavior is often referred to as search engine optimization
(SEO) (Gyongyi and Garcia-Molina, 2005), which includes “illegitimate” black
hat SEO (Gyongyi and Garcia-Molina, 2005) (e.g., web spam (Castillo and
Davison, 2011)) and “legitimate” white hat SEO (Gyongyi and Garcia-Molina,
2005). Early work proposed methods to detect black-hat SEO behavior (Ntoulas
et al., 2006; Piskorski et al., 2008). Later, Goren et al. (2018) proposed to
attack LTR by replacing a passage in a document with other passages to promote
its ranking. Recently, Wu et al. (2022) proposed word substitution ranking
attacks (WSRAs) to promote the ranking of a document, which easily escapes the
detection of traditional anti-spamming methods. In this paper, we focus on
defending against WSRAs.

###  2.3. Defense Methods

To defend against adversarial attacks, many defense methods have been proposed
to make models more robust. These approaches can be classified into
_empirical_ defenses and _certified_ defenses. Empirical defenses attempt to
make models empirically robust to known adversarial attacks; this has been
extensively explored in image (Madry et al., 2018; Wang et al., 2019) and text
classification (Ye et al., 2020; Jia et al., 2019). Data augmentation (Jia and
Liang, 2017; Ribeiro et al., 2018) is a representative empirical defense by
augmenting adversarial examples with the original training data. Since
empirical defenses are only effective for certain attacks rather than all
attacks, a competition emerges between adversarial attacks and defense
methods.

To solve the attack-defense dilemma, researchers resort to certified defenses
to make models provably robust to certain kinds of adversarial perturbations.
Jia et al. (2019) and Huang et al. (2019) first proposed to certify the
robustness to adversarial word substitutions by leveraging Interval Bound
Propagation (IBP (Dvijotham et al., 2018)) in NLP. These IBP-based methods are
limited to continuous word embeddings and are not applicable to subword-level
models like BERT. Ye et al. (2020) recently adopted randomized smoothing to
certify the robustness to word substitution attacks, by turning the original
classifier into a smoothed classifier by adding noise to the input. The final
class prediction of the smoothed classifier is decided by majority voting over
the noised inputs. Randomized smoothing is the only certification method that
scales up to large-scale neural networks like BERT (Cohen et al., 2019) and
provides tight bounds on large datasets. But existing certified defenses are
limited to simple classification scenarios and NRMs are less well studied.
Therefore, in this work, we develop a certified defense method for NRMs based
on randomized smoothing.

##  3\. Certified Top-$K$ Robustness in IR

We first introduce the WSRA attack we consider in this paper. Then, we
introduce the definition of our proposed notion of Certified Top-$K$
Robustness for ranking models to such attacks.

###  3.1. Word Substitution Ranking Attack

Attacks in Web Search. The web search eco-system is, perhaps, the largest-
scale adversarial setting in which search methods operate (Goren et al.,
2020). For many queries in the web retrieval setting there exists an on-going
ranking competition, i.e., many web document authors manipulate their
documents deliberately to promote them in rankings (Goren et al., 2018). This
practice is often referred to as search engine optimization (SEO) (Gyongyi and
Garcia-Molina, 2005). The consequences of SEO are that the quality of search
results may rapidly decrease since many irrelevant documents are ranked higher
than they deserve.

Very recently, a typical black-box word substitution ranking attack (WSRA) (Wu
et al., 2022) was proposed to simulate such real-world ranking competitions.
Specifically, WSRA could successfully attack NRMs by generating human-
imperceptible adversarial documents for rank promotion. The synonymous word
substitution it employs could maximally maintain the naturalness and semantic
similarity of the original document, making it easy for the generated
adversarial documents to evade spam detection. Due to the popularity of NRMs
and the challenges of defending against human-imperceptible perturbations, we
focus on WSRA attacks and design a corresponding defense in this paper.

Notation. In ad-hoc retrieval, given a query $q$ and a set of document
candidates $\mathcal{D}=\\{d_{1},d_{2},\ldots,d_{N}\\}$ selected from a
collection $\mathcal{C}$, a ranking model $f$ aims to predict the relevance
score $\\{f(q,d_{n}):n=1,2,\ldots,N\\}$ between every pair of query $q$ and
candidate document for ranking the whole candidate set. For example, $f$
outputs the ranked list $L=[d_{N},d_{N-1},\ldots,d_{1}]$ if it determines
$f(q,d_{N})>f(q,d_{N-1})\cdots>f(q,d_{1})$. In this paper, we assume the
ranking score $f(q,d_{n})$ is the probability of relevance from 0 to 1 (Dai
and Callan, 2019), which can be easily achieved by adding a sigmoid operation
on the output given by the ranking model.

In WSRA, an attacker replaces the important words in the document with their
synonyms by maximizing the adversarial ranking loss to promote the target
document in rankings. The number of important words is a hyper-parameter.
Specifically, for any word $w$, we consider a pre-defined synonym set $S_{w}$
containing the synonyms of $w$ (including $w$ itself). Following Ye et al.
(2020), we assume the synonymous relation is symmetric, that is, $w$ is in the
synonym set of all its synonyms. The synonym set $S_{w}$ can be built based on
GLOVE (Pennington et al., 2014).

Definition 3.1. ($\delta$-Word Substitution Ranking Attack). For an input
document $d=\\{w_{1},w_{2},\ldots,w_{M}\\}\in\mathcal{D}$, a $\delta$-word
substitution ranking attack constructs an adversarial document
$d^{\prime}=(w_{1}^{\prime},w_{2}^{\prime},\ldots,w_{M}^{\prime})$ by
perturbing at most $\delta\cdot M$ ($\delta\leq 1$) words in $d$ to any of
their synonyms $w_{m}^{\prime}\in S_{w_{m}}$. We denote the candidate set of
adversarial documents as $S_{d}$, i.e.,

$S_{d}:=\\{d^{\prime}:\|d^{\prime}-d\|_{0}/\|d\|\leq\delta\\},$

where
$\left\|d^{\prime}-d\right\|_{0}:=\sum_{m=1}^{M}\mathbb{I}\\{w_{m}^{\prime}\neq
w_{m}\\}$ is the Hamming distance, with $\mathbb{I}\\{\cdot\\}$ the indicator
function. $\left\|d\right\|$ denotes the number of words in the document $d$
and $w_{m}^{\prime}\in S_{w_{m}}$. Ideally, all $d^{\prime}\in S_{d}$ have the
same semantic meaning as $d$ for human judges, but their ranks may be promoted
by the ranking model $f$. The goal of the attacker is to find $d^{\prime}\in
S_{d}$ such that $f(q,d^{\prime})>f(q,d)$. Note that we do not attack the
documents ranked from 1 to $K$, since there is no need to attack user’s top
search results.

###  3.2. Definition of Certified Top-$K$ Robustness

Certified Top-$K$ Robustness. In general, a model is said to be _certified
robust_ if an attack is guaranteed to fail, no matter how the attacker
manipulates the input (Ye et al., 2020). In a real web search scenario, it is
known that users usually care much more about the top ranking results than
others (Niu et al., 2012). For example, the traffic and click-through rate
(CTR) both fall off as users work their way down the search results in major
search engines: while the first and second search results may achieve 36.4$\%$
and 12.5$\%$ CTR, the 10th search result may achieve a CTR of only
2.2$\%$.111https://www.smartinsights.com/search-engine-optimisation-seo/seo-
analytics/the-number-one-spot-how-to-use-the-new-search-curve-ctr-data/
Moreover, many widely-used ranking metrics (Radev et al., 2002; Burges et al.,
2005) focus on the top-$K$ ranking results, e.g., MRR@K and nDCG@K.

Therefore, protecting the results ranked at the top positions is of great
importance (Xia et al., 2009; Niu et al., 2012), not only for real-world
applications, but also for the robustness guarantee of widely-used ranking
metrics. Inspired by this, we define the Certified Top-$K$ Robustness of
ranking models in IR, where a ranking model $f$ is said to be certified robust
at the ranked list $L$ if it is guaranteed that the documents ranked after top
$K$ will not be attacked to be ranked into top $K$ in $L$. Since we focus on
the WSRAs in this work, based on this basic definition, we further define
Certified Top-$K$ Robustness to WSRA.

Definition 3.2. (Certified Top-$K$ Robustness to WSRA). Formally, a ranking
model $f$ is said to be Certified Top-$K$ Robust against WSRAs on the ranked
list $L_{q}$ with respect to a query $q$ if it can keep all the document $d\in
L_{q}[K+1:]$ away from the top-$K$ for all the possible $\delta$-word
substitution ranking attacks (as defined in Definition 3.1), i.e.,

(1) $Rank_{L_{q}}(f(q,d^{\prime}))>K,\text{for all}~{}d\in
L_{q}[K+1:]~{}\text{and any}~{}d^{\prime}\in S_{d},$

where $Rank_{L_{q}}(f(q,d^{\prime}))$ denotes the rank position of the
adversarial document $d^{\prime}$ in $L_{q}$ given by the ranking model $f$.
It is highly challenging to judge if $f$ is certified robust since all the
candidate adversarial documents in $S_{d}$ should be checked and the size of
possible perturbations grows exponentially with $\delta$. Following existing
work (Ye et al., 2020; Jia et al., 2019), we mainly consider the worst case
when $\delta=1$, which is the most challenging case.

##  4\. Our Certified Defense Method

Based on the definition of certified top-$K$ robustness to WSRA, we introduce
a novel Certified Defense method for Ranking models (CertDR) to enhance the
certified robustness. We first introduce a randomized smoothing function for
ranking and how to use it to certify the robustness theoretically. Then, we
propose a practical certified defense algorithm for ranking models. Proofs are
at the end of this section.

Figure 2. The overall architecture of the proposed practical certified defense
method. We first generate the collection perturbation dictionary $T_{C}$ over
the whole document collection. Then, we train the original ranking model by a
noised data augmentation strategy to increase the robustness of $\bar{f}$.
Finally, we estimate the $\bar{f}(q,d_{K})$ and $\bar{f}(q,d_{K+1})$ by Monte
Carlo estimation. The criterion $\Delta{L_{q}}$ is computed, where if
$\Delta{L_{q}}>0$, we can certify that $\bar{f}$ is top-$K$ robust at the
ranked list $L_{q}^{s}$.

###  4.1. Randomized Smoothing Function for Ranking

To circumvent the computationally expensive combinatorial optimization (e.g.,
enumerating all the candidate adversarial documents in $S_{d}$), we borrow the
idea from the randomized smoothing technique (Cohen et al., 2019; Ye et al.,
2020), which could provably defend against the adversarial attacks by
leveraging the voting of randomly perturbed samples derived from the original
input. We target to replace the ranking model $f$ with a smoothed ranking
model $\bar{f}$ for which it is easier to verify the certified robustness.

Specifically, we construct the smoothed ranker $\bar{f}$ by averaging the
output ranking scores of a set of randomly perturbed documents based on random
perturbations, i.e.,

$\bar{f}(q,d)=\mathbb{E}_{\mathbf{R}\sim\Pi_{d}}f(q,\mathbf{R}),$

where $R$ is a randomly perturbed document and $\Pi_{d}$ is the corresponding
probability distribution that prescribes a random perturbation around $d$. In
our work, we define $\Pi_{d}$ to be the uniform distribution on a set of
random word substitutions following (Ye et al., 2020).

In previous classification tasks (Cohen et al., 2019; Ye et al., 2020), the
output of the smoothed classifier is the class with the largest probability
“voting” by all randomly perturbed inputs. Different from these works, we
compute the output of the smoothed ranker by averaging the ranking scores of
all randomly perturbed documents originated from the $d$, which is more
suitable for the ranking problem. In this way, we could obtain the ranked list
$L_{q}^{s}$ based on the averaged scores produced by the smoothed ranker
$\bar{f}$. Here, we leave the query $q$ free from attack. In the future work,
we would like to explore the defense against query attacks by focusing on $q$
in this formulation.

To obtain random perturbations in defense methods effectively, we propose to
build a perturbation set $T_{w}$ for each word $w$. Specifically, we construct
$T_{w}$ from the synonym set $S_{w}$ used in the attack method, i.e., WSRA in
this work, by choosing the top $J$ nearest neighbors via the cosine similarity
of GLOVE vectors. Then, for a document $d=(w_{1},w_{2},\ldots,w_{M})$, we
define the perturbation distribution $\Pi_{d}$ by perturbing each word $w_{i}$
in $d$ to a word in its perturbation set $T_{w_{i}}$ randomly and
independently, i.e.,

$\Pi_{d}(\mathbf{R})=\prod_{i=1}^{M}\frac{\mathbb{I}\\{r_{i}\in
T_{w_{i}}\\}}{|T_{w_{i}}|},$

where $\mathbf{R}=(r_{1},\ldots,r_{M})$ is the perturbed document and
$|T_{w_{i}}|$ denotes the size of $T_{w_{i}}$.

###  4.2. Certifying Smoothed Ranking Models

Given the smoothed ranking model $\bar{f}$, in this section, we introduce how
to certify its top-$K$ robustness. For all the documents in $L_{q}^{s}[K+1:]$,
if their adversarial documents could achieve lower scores than the document
$d_{K}$ ranked at the position $K$, we think these documents $L_{q}^{s}[K+1:]$
cannot be attacked into top K. Formally, the condition that $\bar{f}$ is
certified top-$K$ robust on $L_{q}^{s}$ can be defined as,

(2) $\max_{d\in L_{q}^{s}[K+1:]}\max_{d^{\prime}\in
S_{d}}\bar{f}(q,d^{\prime})<\bar{f}(q,d_{K}).$

In general, there are two difficulties to complete the above certification
case by case, i.e., the inner maximum and the outer maximum.

Inner Maximum. The first difficulty is to exam all candidate adversarial
documents in $S_{d}$ for the inner maximum, where the computation cost grows
exponentially with the attacked word number $\delta M$. We address this
problem in the following Theorem 4.1.

###### Theorem 4.1 (Certified Upper Bound).

Assume that the perturbation set $T_{w}$ is constructed such that
$|T_{w}|=|T_{w^{\prime}}|$ for every word $w$ and its synonym $w^{\prime}\in
S_{w}$. Define

$o_{w}=\min_{w^{\prime}\in S_{w}}\frac{|T_{w}\cap T_{w^{\prime}}|}{|T_{w}|},$

where $o_{w}$ indicates the overlap between the two different perturbation
sets. For a given document $d=(w_{1},\ldots,w_{M})$, we sort the words
according to $o_{w}$, such that $o_{w_{i_{1}}}\leq o_{w_{i_{2}}}\leq\cdots\leq
o_{w_{i_{M}}}$. Then

$\max_{d^{\prime}\in
S_{d}}\bar{f}(q,d^{\prime})\leq\min(\bar{f}(q,d)+o_{d},1),$

where $o_{d}:=1-\prod_{j=1}^{E}o_{w_{i_{j}}}$.

The idea is that for any adversarial document $d^{\prime}\in S_{d}$, the upper
bound of $\bar{f}(q,d^{\prime})$ can be bounded by its original document
ranking score $\bar{f}(q,d)$ with randomized smoothing. As a result, this
theorem avoids the difficult adversarial optimization of
$\bar{f}(q,d^{\prime})$ on $d^{\prime}\in S_{d}$, and only needs to evaluate
$\bar{f}(q,d)$ at the original document $d$. Note that the difference between
our Theorem 4.1 with Theorem 1 in (Ye et al., 2020) is that we extend the
classification prediction in Theorem 1 to ranking scores between queries and
documents, and prove the theorem in an upper bound situation, which has not
been provided by Ye et al. (2020). The proof is provided in Section 4.4.1.
Besides, the upper bound in Theorem 4.1 is sufficiently tight, which is shown
in Section 4.4.2.

Outer Maximum. The second difficulty is to exam all documents in
$L_{q}^{s}[K+1:]$ for the outer maximum, where the computational costs grow
linearly with the list length $N$. We address the outer maximum in the
following. To simplify our notation, we define
$A_{L}=\bar{f}(q,d_{K})-\max_{d\in L_{q}^{s}[K+1:]}\max_{d^{\prime}\in
S_{d}}\bar{f}(q,d^{\prime})$, where Eq. (2) is equivalent to $A_{L}>0$. By
applying Theorem 4.1 to Eq. (2), we have

$\displaystyle A_{L}$ $\displaystyle\geq\bar{f}(q,d_{K})-\max_{d\in
L_{q}^{s}[K+1:]}(\bar{f}(q,d)+o_{d})$
$\displaystyle\geq\bar{f}(q,d_{K})-\bar{f}(q,d_{K+1})-\max_{d\in
L_{q}^{s}[K+1:]}o_{d},$

where $d_{K+1}$ denotes the document which is ranked at the position $K+1$.
The proof is achieved by utilizing the ranking property that
$\bar{f}(q,d_{1})>\bar{f}(q,d_{2})>\cdot\cdot\cdot$. The idea is that we can
compute $A_{L}$ (in other words, certifying $\bar{f}$) by comparing the
ranking scores of documents ranked at $K$ and $K+1$. Note that the
computational cost of $\max_{d\in L_{q}^{s}[K+1:]}o_{d}$ is negligible.

Based on the above solutions of the inner and outer maximum in Eq. (2), it is
possible to introduce a certification criterion for checking the certified
top-$K$ robustness for ranking models.

###### Proposition 4.2.

For a ranked list $L_{q}^{s}$ with respect to a query $q$, under the condition
of Theorem 4.1, we can certify that
$Rank_{L_{q}^{s}}(\bar{f}(q,d^{\prime}))>K,\text{for all}~{}d\in
L_{q}^{s}[K+1:]~{}\text{and any}~{}d^{\prime}\in S_{d}$ if

(3) $\Delta
L_{q}\overset{\text{def}}{=}\bar{f}(q,d_{K})-\bar{f}(q,d_{K+1})-\max_{d\in
L_{q}^{s}[K+1:]}o_{d}>0,$

where $\Delta L_{q}$ can be estimated by Monte Carlo estimation as we show in
the next section. We can certify whether the ranking model is top-$K$ robust
on the ranked list $L_{q}^{s}$ by simply checking $\Delta L_{q}$. If $\Delta
L_{q}$ is positive, the model is certified top-$K$ robust.

###  4.3. Practical Certified Defense Algorithm

Based on the above theoretical analysis, we now present a practical certified
defense algorithm for ranking models. Formally, we write $S_{C}$ for the
synonym dictionary of the collection. Specifically, $S_{C}$ contains the
synonym set $S_{w}$ for all words in the collection $C$ and is often presented
as a synonym network (Ye et al., 2020). Similar to the process of obtaining
$T_{w}$ from $S_{w}$, we achieve the collection perturbation dictionary
$T_{C}$ by keeping the top $J$ nearest neighbors in $S_{C}$ for each word. The
overall architecture is shown in Figure 2.

The certified defense algorithm contains two key steps, i.e., noised data
augmentation and Top-$K$ Robustness Certification. We describe the two steps
in the following.

Noise Data Augmentation Strategy. The robustness certification holds
regardless of how the original ranker $f$ is trained. However, to rank the
document $d$ with respect to the $q$ correctly and robustly by $\bar{f}$, it
is expected that $f$ properly ranks the perturbed document $R$ (recall that
$R\sim\Pi_{d}$) such that it is close to the rank position of the original
document $d$. That is, the noise of $R$ should have little effect on the
ranking, making the ensembled ranking score $\bar{f}(q,d)$ close to the
original ranking score $f(q,d)$. However, if $f$ is trained via standard
supervised learning without any noised documents, it will not necessarily
learn how to rank $R$ properly.

Inspired by previous works (Lecuyer et al., 2019; Ye et al., 2020; Zhou et
al., 2020), we introduce a noise data augmentation strategy for ranking.
Specifically, we first generate a perturbed document $d_{noised}$ for each $d$
in the collection $C$. The perturbation is achieved by randomly sampling every
word from $d$ using the perturbation distribution $\Pi_{d}$. Then, we train
the original ranker $f$ using the training triples equipped with the noised
documents via the following objective:

(4) $L_{ndat}=\max(0,1-f(q,d_{noised}^{+})+f(q,d_{noised}^{-})),$

where $d_{noised}^{+}/d_{noised}^{-}$ is the perturbed document from
$d^{+}/d^{-}$. And $d^{+}/d^{-}$ denotes the positive/negative document in
original training triples. Then, we can obtain a better smoothed ranker
$\bar{f}$ by Monte Carlo estimation in the following.

Top-$K$ Robustness Certification. In theory, since the perturbation space can
be extremely large, it is impossible to exactly obtain the prediction of
$\bar{f}$ at each $(q,d)$. Therefore, based on the ranker $f$ obtained from
the noised data augmentation strategy, we estimate $\bar{f}(q,d_{K})$ and
$\bar{f}(q,d_{K+1})$ by Monte Carlo estimation. Take $\bar{f}(q,d_{K})$ as an
example, we can estimate it like

$\bar{f}(q,d_{K})=\mathbb{E}_{\mathbf{R}_{K}\sim
d_{K}}f(q,d_{K})\approx\frac{1}{n}\sum_{i=1}^{n}f(q,\mathbf{R}_{K}^{(i)}),$

where $\mathbf{R}_{K}^{(i)}$ are i.i.d. samples from $\Pi_{d_{K}}$ and thus
$\Delta L_{q}$ can be approximated accordingly. We can construct rigorous
statistical procedures to reject the null hypothesis that $\bar{f}$ is not
certified robust at $L_{q}$ (e.g., $\Delta L_{q}<0$) with a given significance
level (e.g., 5%) following (Ye et al., 2020).

Finally, if $\Delta L_{q}>0$, then $\bar{f}$ is certified top-$K$ robust at
the ranked list $L_{q}^{s}$. Otherwise, we will judge it is not certified
top-$K$ robust at the $L_{q}^{s}$. We can see that our practical certified
defense algorithm could be achieved by assembling the ranking outputs and that
it does not require any further information about the ranking models. Thus, it
can be applied to any ranking model.

###  4.4. Proofs

Here we provide all the necessary proofs of Theorem 4.1 and the tightness of
the bound in Theorem 4.1 with its proof. The upper bound of Theorem 4.1 is
achieved by introducing an auxiliary function cluster based on the relevance
between the query and document, and solving the constraint optimization
problem by Lagrange and properties of randomly perturbed sets. Tightness is
proved by constructing the randomized smoothing ranker that satisfies the
desired property we want.

####  4.4.1. Proof of Theorem 4.1

Our goal is to calculate the upper bound $\max_{d^{\prime}\in
S_{d}}\bar{f}(q,d^{\prime})$. The key idea is to frame the computation of the
upper bound into a variational optimization.

###### Lemma 4.3.

Define $\mathcal{G}_{[0,1]}$ to be the set of all bounded functions mapping
from $\mathcal{Q}\times\mathcal{D}$ to [0, 1]. For any
$g\in\mathcal{G}_{[0,1]}$, define

$\Pi_{d}[g]=\mathbb{E}_{\mathbf{R}\sim\Pi_{d}}[g(q,\mathbf{R})].$

Then we have for any $\mathbf{R}$,

$\displaystyle\max_{d^{\prime}\in S_{d}}\bar{f}(q,d^{\prime})$
$\displaystyle\leq\max_{d^{\prime}\in
S_{d}}\max_{g\in\mathcal{G}_{[0,1]}}\\{\Pi_{d^{\prime}}[g]~{}s.t.~{}\Pi_{d}[g]=\bar{f}(q,d)\\}$
$\displaystyle:=\bar{f}_{up}(q,d^{\prime})$

Proof of Lemma 4.3. Define $g_{0}(q,d)=f(q,d)$. Then we have

$\bar{f}(q,d)=\mathbb{E}_{\mathbf{R}\sim\Pi_{d}}[f(q,\mathbf{R})]=\Pi_{d}[g_{0}].$

Therefore, $g_{0}$ satisfies the constraints in the optimization, which makes
it obvious that

$\bar{f}(q,d^{\prime})=\Pi_{d^{\prime}}[g_{0}]\leq\max_{g\in\mathcal{G}_{[0,1]}}\\{\Pi_{d^{\prime}}[g]~{}s.t.~{}\Pi_{d}[g]=\bar{f}(q,d)\\}.$

Taking $\max_{d^{\prime}\in S_{d}}$ on both sides yields the upper bound and
thus the problem reduces to deriving bounds for the optimization problems.

###### Theorem 4.4.

Under the assumption of Theorem 4.1, for the optimization problem in Lemma
4.3, we have

$\bar{f}_{up}(q,d^{\prime})\leq\min(\bar{f}(q,d)+o_{d},1),$

where $o_{d}$ is the quantity defined in Theorem 4.1.

Proof of Theorem 4.4. For notation, we denote $p=\bar{f}(q,d)$. Applying the
Lagrange multiplier to the constraint optimization problem and exchanging the
min and max, we have

$\displaystyle\bar{f}_{up}(q,d^{\prime})$ $\displaystyle=\max_{d^{\prime}\in
S_{d}}\max_{g\in\mathcal{G}_{[0,1]}}\\{\Pi_{d^{\prime}}[g]~{}s.t.~{}\Pi_{d}[g]=\bar{f}(q,d)\\}$
$\displaystyle=-\min_{d^{\prime}\in
S_{d}}\min_{g\in\mathcal{G}_{[0,1]}}\\{-\Pi_{d^{\prime}}[g]~{}s.t.~{}\Pi_{d}[g]=\bar{f}(q,d)\\}$
$\displaystyle\leq-\min_{d^{\prime}\in
S_{d}}\min_{g\in\mathcal{G}_{[0,1]}}\max_{\lambda\in\mathcal{R}}\lambda\Pi_{d}[g]-\Pi_{d^{\prime}}[g]-\lambda
p$ $\displaystyle=\max_{d^{\prime}\in
S_{d}}\min_{\lambda\in\mathcal{R}}\max_{g\in\mathcal{G}_{[0,1]}}\Pi_{d^{\prime}}[g]-\lambda\Pi_{d}[g]+\lambda
p$ $\displaystyle=\min_{\lambda\in\mathcal{R}}\lambda p+\max_{d^{\prime}\in
S_{d}}\max_{g\in\mathcal{G}_{[0,1]}}\int
g(\mathbf{R})(d\Pi_{d^{\prime}}(\mathbf{R})-\lambda d\Pi_{d}(\mathbf{R})).$

Note that

$\max_{g\in\mathcal{G}_{[0,1]}}\int
g(\mathbf{R})(d\Pi_{d^{\prime}}(\mathbf{R})-\lambda
d\Pi_{d}(\mathbf{R}))=\int(d\Pi_{d^{\prime}}(\mathbf{R})-\lambda
d\Pi_{d}(\mathbf{R}))_{+},$

which is achieved by setting

$g(\mathbf{R})=\mathbb{I}\\{d\Pi_{d^{\prime}}(\mathbf{R})-\lambda
d\Pi_{d}(\mathbf{R})\geq 0\\},$

where $(a)_{+}=\max(a,0)$ and $\mathbb{I}\\{\cdot\\}$ denotes the indicator
function. Thus we have,

$\displaystyle\bar{f}_{up}(q,d^{\prime})$
$\displaystyle=\min_{\lambda\in\mathcal{R}}\lambda p+\max_{d^{\prime}\in
S_{d}}\int(d\Pi_{d^{\prime}}(\mathbf{R})-\lambda d\Pi_{d}(\mathbf{R}))_{+}.$

For any $\lambda<0$, we can show that

$\displaystyle\lambda p+\max_{d^{\prime}\in
S_{d}}\int(d\Pi_{d^{\prime}}(\mathbf{R})$ $\displaystyle-\lambda
d\Pi_{d}(\mathbf{R}))_{+}$ $\displaystyle=\lambda p+\max_{d^{\prime}\in
S_{d}}\int(d\Pi_{d^{\prime}}(\mathbf{R})-\lambda d\Pi_{d}(\mathbf{R}))$
$\displaystyle=\lambda(p-1)+1>0(p-1)+1=1,$

which contradicts $\bar{f}(q,d^{\prime})\leq 1$. This implies that the minimum
of $\lambda p+\max_{d^{\prime}\in
S_{d}}\int(d\Pi_{d^{\prime}}(\mathbf{R})-\lambda d\Pi_{d}(\mathbf{R}))_{+}$
must be achieved at $\lambda\geq 0$. Thus we have

$\bar{f}_{up}(q,d^{\prime})=\min_{\lambda\geq 0}\lambda p+\max_{d^{\prime}\in
S_{d}}\int(d\Pi_{d^{\prime}}(\mathbf{R})-\lambda d\Pi_{d}(\mathbf{R}))_{+}.$

Now we calculate $\int(d\Pi_{d^{\prime}}(\mathbf{R})-\lambda
d\Pi_{d}(\mathbf{R}))_{+}$.

###### Lemma 4.5.

Given the words $w$, $w^{\prime}$, we write
$n_{w}=|T_{w}|,n_{w^{\prime}}=|T_{w}^{\prime}|$, and
$n_{w,w^{\prime}}=|T_{w}\cap T_{w^{\prime}}|$. We have the following identify

$\displaystyle\int(d\Pi_{d^{\prime}}(\mathbf{R})$ $\displaystyle-\lambda
d\Pi_{d}(\mathbf{R}))_{+}=1-\prod_{j\in[M],w_{j}\neq
w^{\prime}_{j}}\frac{n_{w_{j},w^{\prime}_{j}}}{n_{w^{\prime}_{j}}}$
$\displaystyle+\left(\prod_{j\in[M],w_{j}\neq
w^{\prime}_{j}}\frac{n_{w_{j},w^{\prime}_{j}}}{n_{w^{\prime}_{j}}}\right)\left(1-\lambda\prod_{j\in[M],w_{j}\neq
w^{\prime}_{j}}\frac{n_{w^{\prime}_{j}}}{n_{w_{j}}}\right)_{+}.$

As a result, under the assumption that
$n_{w}=|T_{w}|=|T_{w^{\prime}}|=n_{w^{\prime}}$ for every word $w$ and its
synonym $w^{\prime}\in S_{w}$, we have

$\displaystyle\int(d\Pi_{d^{\prime}}(\mathbf{R})-\lambda
d\Pi_{d}(\mathbf{R}))_{+}$ $\displaystyle=1-\prod_{j\in[M],w_{j}\neq
w^{\prime}_{j}}\frac{n_{w_{j},w^{\prime}_{j}}}{n_{w^{\prime}_{j}}}$
$\displaystyle+\left(\prod_{j\in[M],w_{j}\neq
w^{\prime}_{j}}\frac{n_{w_{j},w^{\prime}_{j}}}{n_{w^{\prime}_{j}}}\right)\left(1-\lambda\right)_{+}.$

Now we need to solve the optimization of $\max_{d^{\prime}\in
S_{d}}\int(d\Pi_{d^{\prime}}(\mathbf{R})-\lambda d\Pi_{d}(\mathbf{R}))_{+}$.

###### Lemma 4.6.

For any word $w$, define $\tilde{w}^{*}=\arg\min_{w^{\prime}\in
S_{d}}n_{w,w^{\prime}}/n_{w}$. For a given document $d=(w_{1},\ldots,w_{M})$,
we define an ordering of the words $w_{p_{1}},\ldots,w_{p_{W}}$ such that
$n_{w_{p_{i}},\tilde{w}_{p_{i}}^{*}}/n_{w_{p_{i}}}\leq
n_{w_{p_{j}},\tilde{w}_{p_{j}}^{*}}/n_{w_{p_{j}}}$ for any $i\leq j$. For a
given $d$ and $E=\delta M$, we define an adversarial perturbed document
$d^{*}=(w_{1}^{*},\ldots,w_{M}^{*})$, where

$w_{i}^{*}=\left\\{\begin{array}[]{ll}\tilde{w}^{*},&\text{if
}i\in[w_{1},\ldots,w_{E}]\\\ w_{i},&\text{if
}i\notin[w_{1},\ldots,w_{E}]\end{array}\right.$

Then for any $\lambda>0$, we have that $d^{*}$ is the optimal solution of
$\max_{d^{\prime}\in S_{d}}\int(d\Pi_{d^{\prime}}(\mathbf{R})-\lambda
d\Pi_{d}(\mathbf{R}))_{+}$, that is,

$\max_{d^{\prime}\in S_{d}}\int(d\Pi_{d^{\prime}}(\mathbf{R})-\lambda
d\Pi_{d}(\mathbf{R}))_{+}=\int(d\Pi_{d^{*}}(\mathbf{R})-\lambda
d\Pi_{d}(\mathbf{R}))_{+}.$

Now by Lemma 4.6, the upper bound becomes

(5) $\displaystyle\bar{f}_{up}(q,d^{\prime})$ $\displaystyle=\min_{\lambda\geq
0}\lambda p+\max_{d^{\prime}\in
S_{d}}\int(d\Pi_{d^{\prime}}(\mathbf{R})-\lambda d\Pi_{d}(\mathbf{R}))_{+}$
$\displaystyle=\min_{\lambda\geq 0}\lambda
p+\int(d\Pi_{d^{*}}(\mathbf{R})-\lambda d\Pi_{d}(\mathbf{R}))_{+}$
$\displaystyle=\min_{\lambda\geq 0}(\lambda p+o_{d}+(1-o_{d})(1-\lambda)_{+})$
$\displaystyle=\min(p+o_{d},1),$

where $o_{d}$ is consistent with the definition in Theorem 4.1:

$o_{d}=1-\prod_{j\in[M],w_{j}\neq\tilde{w}^{*}_{j}}\frac{n_{w_{j},\tilde{w}^{*}_{j}}}{n_{w_{j}}}=1-\prod_{j=1}^{E}o_{w_{i_{j}}}.$

Here, Eq. (5) is calculated using the assumption of Theorem 4.1. The
optimization of $\min_{\lambda\geq 0}$ in (5) is an elementary step: if
$p+o_{d}>1$, we have $\lambda^{*}=0$ with solution 1; if $p+o_{d}\leq 1$, we
have $\lambda^{*}=1$ with solution $p+o_{d}$. For the proof of Lemma 4.5 and
4.6, we refer readers to (Ye et al., 2020, Lemma 2 and 3).

####  4.4.2. Tightness

Whether the bound in Theorem 4.1 is sufficiently tight is of great importance.
In the following, we provide a theorem to state its tightness.

###### Theorem 4.7 (Tightness).

Assume the conditions of Theorem 4.1 hold. For a ranking model $f$ that maps
$Q\times D$ to [0, 1], there exists a model $f_{*}$ such that its related
smoothed ranker $\bar{f}_{*}$ satisfies

$\bar{f}_{*}(q,d)=\bar{f}(q,d),$

and

$\max_{d^{\prime}\in
S_{d}}\bar{f}_{*}(q,d^{\prime})=\min(\bar{f}_{*}(q,d)+o_{d},1),$

where $o_{d}$ is defined in Theorem 4.1.

As shown in Theorem 4.7, the upper bound in Theorem 4.1 is tight and can not
be further improved if we do not know any other structural information about
$f$. In the following, we provide the proof of Theorem 4.7.

Proof of Tightness. We denote $\bar{f}(q,d)=p_{r}$ in this proof for
simplicity. The $d^{*}$ below is the optimal adversarial document defined in
the proof of Lemma 4.6. Note that $o_{d}=|T_{d}-T_{d^{*}}|/|T_{d}|$ and
$1-o_{d}=|T_{d}\cap T_{d^{*}}|/|T_{d}|$ as defined in Theorem 4.1. Our proof
is based on constructing a randomized smoothing ranker that satisfies the
desired property we want to prove.

Case 1 $p_{r}\leq 1-o_{d}$. Note that in this case $|T_{d}\cap
T_{d^{*}}|=1-o_{d}\geq p_{r}$. Therefore, we can choose set $U$ such that
$U\subseteq T_{d}\cap T_{d^{*}}$ and $|U|/|T_{d}|=p_{r}$. We define the
ranker:

$f_{*}(q,\mathbf{R})=\left\\{\begin{array}[]{ll}1,&\text{if}~{}\mathbf{R}\in
U\cup T_{d^{*}}\\\ 0,&\text{otherwise}\end{array}\right.$

Case 2 $p_{r}>1-o_{d}$. We choose set $U$ such that $U\subseteq T_{d}\cap
T_{d^{*}}$ and $|U|/|T_{d}|=p_{r}$. We define the ranker

$f_{*}(q,\mathbf{R})=\left\\{\begin{array}[]{ll}1,&\text{if}~{}\mathbf{R}\in
U\cup(T_{d^{*}}-T_{d})\\\ 0,&\text{otherwise}\end{array}\right.$

It can easily be verified that for each case, the defined ranker satisfies all
the conditions in Theorem 4.7. This indicates the bound can be achieved by
learning a gold ranker that can judge some specific documents as relevant and
others as irrelevant for the query.

##  5\. Experimental Setup

###  5.1. Datasets

To evaluate the effectiveness of our proposed methods, we conduct experiments
on two representative web search benchmark datasets.

  * •

MS MARCO Document Ranking dataset (Nguyen et al., 2016) (MS-MARCO-Doc) is a
large-scale benchmark dataset for web document retrieval, with about 3.21M web
documents and 0.37M training queries. The average length of the document is
about 1129.

  * •

MS MARCO Passage Ranking dataset (Nguyen et al., 2016) (MS-MARCO-Pas) is a
large-scale benchmark dataset for passage retrieval, with about 8.84M passages
from web pages and 0.5M training queries. The average length of the passage is
about 58.

###  5.2. Baselines

Our CertDR can certify the top-$K$ robustness of different ranking models. We
first compare the certified top-$K$ robustness among different ranking models
(i.e, BM25 (Robertson and Walker, 1994), Duet (Mitra et al., 2017) and BERT
(Devlin et al., 2019)) under CertDR. Then, since the defense methods for NRMs
have not been well explored yet, we adopt the representative empirical
defense, i.e., Data Augmentation (DA), in text classification task (Jia and
Liang, 2017; Ribeiro et al., 2018), for NRMs as a baseline. Specifically, for
each training document $d$, we augment the collection with $2$ new documents
$\tilde{d}$ by sampling $\tilde{d}$ uniformly from $S_{d}$, then train on the
normal hinge loss following (Jia et al., 2019). We do not use adversarial
training (Goodfellow et al., 2014) here because it would require running an
adversarial search procedure at each training step, which would be
prohibitively slow.

###  5.3. Evaluation Metrics

We evaluate the robustness to all WSRAs of models. We propose a metric to
directly measure the Certified Robust Query (CRQ) percentage, the percentage
of test queries for which the model is certified robust at the query $q$ if
all the documents out of top-$K$ are not attacked into the top-$K$. Evaluating
this exactly involves enumerating exponentially many perturbations, which is
intractable (Section 4.2). Instead, we evaluate the $CRQ$ under randomized
smoothing, i.e.,

$CRQ=\frac{\sum_{q\in Q}\mathbb{I}\\{\Delta L_{q}>0\\}}{|Q|},$

where $\Delta L_{q}$ is the criterion mentioned in Section 4.2. The ranking
model is more certified robust with a higher CRQ (%).

To compare the defense ability of CertDR with empirical defense methods, we
also leverage two metrics, i.e., success rate and conditional success rate.
Success Rate (SR) (Wu et al., 2022) evaluates the percentage of the after-
attack documents that are ranked higher than original documents. The
robustness of a ranking model is better with a lower SR (%).

Inspired by CondAcc (Wang et al., 2021), which enables the comparison
certified and empirical defense, we introduce Conditional Success Rate
(CondSR). CondSR evaluates whether the rankings of the adversarial documents
in an attacked ranked list indeed cannot be improved when its counterpart
clean ranked list is certified robust:

$\begin{split}&\text{CondSR}={}\\\\[-5.69054pt] &\frac{\sum_{q\in
Q}\mathbb{I}\\{\Delta
L_{q}>0\\}\frac{1}{N_{q}}\sum_{i=1}^{N_{q}}\mathbb{I}\\{Rank_{L}(d_{i}+p)<Rank_{L}(d_{i})\\}}{\sum_{q\in
Q}\mathbb{I}\\{\Delta L_{q}>0\\}}.\end{split}$

While CRQ is evaluated on clean ranked lists to show certified robustness,
CondSR is tested on attacked ranked lists to show the empirical robustness of
models on these certified ranked lists. The robustness of a ranking model is
better with a lower CondSR (%).

###  5.4. Implementation Details

We implement ranking models following previous work (Wu et al., 2021; Dai and
Callan, 2019). For the MS-MARCO-Doc collection, we use the official top 100
(i.e., $N=100$) ranked documents retrieved by the QL model. For the MS-MARCO-
Pas, initial retrieval is performed using the Anserini toolkit (Yang et al.,
2018) with the BM25 model to obtain the top 100 ranked passages. We evaluate
all ranking models on 200 queries (i.e., $|Q|=200$) randomly sampled from the
dev set of two datasets following (Wu et al., 2022).

For the Monte Carlo estimation of $\Delta L_{q}$, we use 1,000 random
perturbed documents to accept $\Delta L_{q}>0$ with probability of at least
0.95. The corresponding estimation error is 0.086 and is considered during the
estimation following Ye et al. (2020). Further implementation details and the
code can be found online.222https://github.com/ict-bigdatalab/CertDR/

##  6\. Experimental Results

We evaluate our defense method to address the following research questions:
(RQ1) What is the certified robustness among different ranking models via
CertDR?  (RQ2) How does the randomized smoothed ranker perform compared with
the original ranker?  (RQ3) How does $K$ affect certified top-$K$ robustness?
(RQ4) How does CertDR perform compared with empirical defense baselines?

###  6.1. Certified Top-$K$ Robustness of Different Ranking Models

To answer RQ1, we analyze certified top-$K$ robustness of different ranking
models using CertDR on MS-MARCO-Doc and MS-MARCO-Pas. See Figure 3. We find
that (i) Overall, the certified robustness of the ranking model is lower than
that of the text classification models (Ye et al., 2020; Jia et al., 2019),
indicating that ranking models are vulnerable to adversarial attacks. There
are two potential reasons: First, the text ranking task itself needs to model
cross-document interactions to capture query-document relevance, which is more
complex than classifying a single sentence independently as in text
classification. Second, certified top-$K$ robustness imposes requirements on
the ranked list, which is demanding than the point-wise classification
scenario. (ii) Pre-trained model BERT generally outperforms other models,
indicating that BERT is more certified robust than other ranking models. The
reason might be that pre-training on a large text corpus can improve the out-
of-distribution generalizability to adversarial examples attacked by synonyms
substitution. Therefore, it is worthwhile to leverage pre-training techniques
to enhance the robustness of NRMs in the future. (iii) BM25 is less certified
robust than Duet and BERT on MS-MARCO-Doc when $K$ is small, while it is more
certified robust than Duet on MS-MARCO-Pas for all $K$s. BM25 depends on exact
matching signals between the query and document; therefore, a possible
explanation is that there are fewer options of attacked words in the short
passage than the long document, contributing to the robustness on short texts.
Besides, we leave the analysis of different $K$s to Section 6.3.

---

Figure 3. Certified top-$K$ robustness of different ranking models in terms of CRQ (%) on MS-MARCO-Doc (a) and MS-MARCO-Pas (b).  Table 1. Comparing the ranking performance between the original and randomized smoothed ranker in terms of the MRR@10 and MRR@100 on MS-MARCO-Doc. * denotes significant degradation w.r.t. the randomized smoothed ranker w/o noise data augmentation (p-value¡0.05).  Method | MRR@10 | MRR@100
---|---|---
Original $f$ | 0.4428∗ | 0.4470∗
Smoothed $\bar{f}$ w/o noise data aug | 0.2259∗ | 0.2416∗
Smoothed $\bar{f}$ | 0.3635∗ | 0.3722∗

###  6.2. Smoothed Ranker vs. Original Ranker

To answer RQ2, we compare the ranking performance of the randomized smoothed
ranker with the original ranker. We select BERT as the original ranker and
conduct experiments on MS-MARCO-Doc. We also show the ranking performance of
the randomized smoothed ranker without the noised data augmentation.

From Table 1, we observe that: (i) The ranking performance of smoothed ranker
without noised data augmentation drops dramatically (e.g., 0.2259 vs. 0.4428
in terms of MRR@100). The reason might be that the smoothed ranker ranks
documents based on the ensemble ranking scores of perturbed documents, which
are far away from the original documents. (ii) By applying a noised data
augmentation strategy, the ranking performance of the smoothed ranker improves
significantly and becomes closer to the original ranker. The reason might be
that the augmented training documents are generated from the same perturbation
distribution with the perturbed documents, which helps the smoothed ranker
learn to rank the perturbed documents properly. (iii) The smoothed ranker has
a moderate drop in terms of MRR@100 compared with the original ranker with
normal training (0.3722 vs. 0.4470). Similar drops on clean acc (accuracy on
clean examples) are also seen for robust models in previous work (Miyato et
al., 2016; Jia et al., 2019). Future work could explore how to achieve the
trade-off between clean and robust performance.

Table 2. The CRQ (%) of different ranking models with different $K$ on MS-MARCO-Doc and MS-MARCO-Pas. $K$ | MS-MARCO-Doc | MS-MARCO-Pas
---|---|---
BM25 | Duet | BERT | BM25 | Duet | BERT
1 | 3.0 | 9.5 | 15.5 | 12.5 | 7.0 | 14.0
2 | 2.0 | 1.5 | 12.5 | 6.0 | 2.0 | 15.0
3 | 1.5 | 1.5 | 11.5 | 8.0 | 0.5 | 14.5
4 | 3.5 | 0 | 10.0 | 5.5 | 0 | 7.5
5 | 3.5 | 0.5 | 13.0 | 4.5 | 0.5 | 15.0
10 | 1.5 | 0 | 3.0 | 2.5 | 0 | 9.5
20 | 1.5 | 0 | 0 | 0.5 | 0 | 3.0
30 | 0.5 | 0 | 0 | 0 | 0 | 1.5
40 | 0.5 | 0 | 0 | 1.5 | 0 | 0
50 | 0.5 | 0 | 0 | 0.5 | 0 | 0
60 | 0.5 | 0 | 0 | 0 | 0 | 0
70 | 0.5 | 0 | 0 | 1.0 | 0 | 0
80 | 0.5 | 0 | 0 | 0 | 0 | 0
90 | 0.5 | 0 | 0 | 0.5 | 0 | 0

###  6.3. Analysis of the Effect of $K$

To answer RQ3, we analyze the effect of $K$ for CertDR when we certify the
top-$K$ robustness. Specifically, we analyze the ranking performance of
different ranking models in terms of CRQ, and set $K$ to 14 different values.
As shown in Table 2, we can find that: (i) Overall, the model becomes less
certified top-$K$ robust with the increase of $K$ on both datasets.
Intuitively, it is more difficult to attack a document to a higher rank
position than a lower rank position. (ii) However, an interesting finding is
that the certified top-$K$ robustness with a larger $K$ is even greater than a
smaller $K$ in a certain range. For example, the CRQ of BERT is 15.0 with
$K=5$ while 7.5 with $K=4$ on the MS-MARCO-Pas dataset. By conducting further
analysis, we find that although documents ranked out of top $5$ are not easily
attacked into the top $5$, the $5$-th document could be attacked into the top
$4$ easily. (iii) While the CRQ of NRMs reduces to 0 after a point (e.g, the
CRQ of Duet reduces to 0 after $K$=10), it is interesting to find that the CRQ
of BM25 remains at a low positive value when $K$ is very large (e.g., CRQ of
BM25 remains at 0.5 when $K$=30 to 90 on MS-MARCO-Doc). The reason may be that
BM25 relies on the statistical features, which is more robust than word
embeddings of NRMs against adversarial attacks. This is consistent with the
findings in (Wu et al., 2021).

###  6.4. Comparison with Empirical Defenses

Based on the above analysis of certified robustness of different models, we
further compare CertDR with baseline empirical defense methods (i.e., DA)
following (Wang et al., 2021). The WSRA is conducted by PRADA (Wu et al.,
2022), and we set $K=10$ and $5$ for CertDR on MS-MARCO-Doc and MS-MARCO-Pas,
respectively.

To answer RQ4, as shown in Table 3, we observe that: (i) The SR is very high
(i.e., up to 96.7% on MS-MARCO-Doc) if we do not take any defense, indicating
that it is important to develop defense methods for NRMs to fight against
adversarial attacks. (ii) Empirical defense method DA reduces the SR to some
extent. However, it performs worse than CertDR. Hence, simply augmenting the
training documents (as in NLP) is not a robust defense against attacks in IR.
Future work should explore more adequate empirical defense methods in IR.
Importantly, empirical defense methods do not provide rigorous certified
robustness guarantees and the performance may significantly depend on the
datasets and specific attacks. (iii) CertDR achieves the lowest CondSR on both
datasets, indicating that our CertDR could certify the robustness
theoretically while enhancing the robustness empirically for ranking models.

Table 3. Comparisons between our proposed CertDR and the baseline on the BERT. Adversarial attacks are conducted by PRADA (Wu et al., 2022). ADV corresponds to no defense. ADV and DA are evaluated under SR (%) and CertDR is evaluated under CondSR (%). Dataset | ADV | DA | CertDR
---|---|---|---
MS-MARCO-Doc | 96.7 | 57.0 | 40.0
MS-MARCO-Pas | 91.4 | 64.6 | 57.4

##  7\. Conclusion

In this paper, we defined the notion of Certified Top-$K$ Robustness for
ranking models focusing on the characteristics of IR. We proposed a
certifiably robust defense method called CertDR, based on randomized
smoothing. The key idea is to smooth the ranking model with random word
substitutions, and construct provable certification bounds based on the
ranking property. Extensive experiments validate that CertDR outperforms
existing defense methods and improves the certifiable robustness of ranking
models.

In future work, it is worth to strengthen the notion of Certified Top-$K$
Robustness to guarantee that the order of top-$K$ ranking results remains
unchanged. We hope that our study helps to put concerns about the robustness
of NRMs on the research agenda and to motivate new defense ideas, including
empirical and certified defenses of ranking models.

###### Acknowledgements.

This work was funded by the National Natural Science Foundation of China
(NSFC) under Grants No. 62006218 and 61902381, the Youth Innovation Promotion
Association CAS under Grants No. 20144310 and 2021100, the Innovation Project
of ICT, CAS under Grants No. E261090, the Young Elite Scientist Sponsorship
Program by CAST under Grants No. YESS20200121, and the Lenovo-CAS Joint Lab
Youth Scientist Project. This work was also (partially) funded by the Hybrid
Intelligence Center, a 10-year program funded by the Dutch Ministry of
Education, Culture and Science through the Dutch Research Council,
https://hybrid-intelligence-centre.nl. All content represents the opinion of
the authors, which is not necessarily shared or endorsed by their respective
employers and/or sponsors.

## References

  * (1)
  * Alzantot et al. (2018) Moustafa Alzantot, Yash Sharma, Ahmed Elgohary, Bo-Jhang Ho, Mani Srivastava, and Kai-Wei Chang. 2018\.  Generating natural language adversarial examples.  _arXiv preprint arXiv:1804.07998_ (2018).
  * Burges et al. (2005) Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hullender. 2005.  Learning to rank using gradient descent. In _Proceedings of the 22nd international conference on Machine learning_. 89–96.
  * Castillo and Davison (2011) Carlos Castillo and Brian D Davison. 2011.  _Adversarial web search_. Vol. 4.
  * Cheng et al. (2019) Minhao Cheng, Wei Wei, and Cho-Jui Hsieh. 2019.  Evaluating and enhancing the robustness of dialogue systems: A case study on a negotiation agent. In _NAACL_.
  * Cohen et al. (2019) Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. 2019\.  Certified adversarial robustness via randomized smoothing. In _ICML_.
  * Dai and Callan (2019) Zhuyun Dai and Jamie Callan. 2019.  Deeper text understanding for IR with contextual neural language modeling. In _SIGIR_. 985–988.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In _NAACL_.
  * Dong et al. (2020) Xinshuai Dong, Anh Tuan Luu, Rongrong Ji, and Hong Liu. 2020\.  Towards Robustness Against Natural Language Word Substitutions. In _International Conference on Learning Representations_.
  * Dvijotham et al. (2018) Krishnamurthy Dvijotham, Sven Gowal, Robert Stanforth, Relja Arandjelovic, Brendan O’Donoghue, Jonathan Uesato, and Pushmeet Kohli. 2018\.  Training verified learners with learned verifiers.  _arXiv preprint arXiv:1805.10265_ (2018).
  * Gao et al. (2018) Ji Gao, Jack Lanchantin, Mary Lou Soffa, and Yanjun Qi. 2018\.  Black-box generation of adversarial text sequences to evade deep learning classifiers. In _SPW_. IEEE, 50–56.
  * Goodfellow et al. (2014) Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. 2014\.  Explaining and harnessing adversarial examples.  _arXiv preprint arXiv:1412.6572_ (2014).
  * Goren et al. (2018) Gregory Goren, Oren Kurland, Moshe Tennenholtz, and Fiana Raiber. 2018.  Ranking robustness under adversarial document manipulations. In _SIGIR_.
  * Goren et al. (2020) Gregory Goren, Oren Kurland, Moshe Tennenholtz, and Fiana Raiber. 2020.  Ranking-Incentivized Quality Preserving Content Modification. In _SIGIR_.
  * Gu et al. (2020) Jia-Chen Gu, Tianda Li, Quan Liu, Zhen-Hua Ling, Zhiming Su, Si Wei, and Xiaodan Zhu. 2020.  Speaker-aware BERT for multi-turn response selection in retrieval-based chatbots. In _CIKM_. 2041–2044.
  * Gyongyi and Garcia-Molina (2005) Zoltan Gyongyi and Hector Garcia-Molina. 2005.  Web spam taxonomy. In _AIRWeb_.
  * Huang et al. (2019) Po-Sen Huang, Robert Stanforth, Johannes Welbl, Chris Dyer, Dani Yogatama, Sven Gowal, Krishnamurthy Dvijotham, and Pushmeet Kohli. 2019.  Achieving Verified Robustness to Symbol Substitutions via Interval Bound Propagation. In _EMNLP/IJCNLP (1)_.
  * Jia and Liang (2017) Robin Jia and Percy Liang. 2017.  Adversarial Examples for Evaluating Reading Comprehension Systems. In _EMNLP_.
  * Jia et al. (2019) Robin Jia, Aditi Raghunathan, Kerem Göksel, and Percy Liang. 2019.  Certified Robustness to Adversarial Word Substitutions.. In _EMNLP/IJCNLP (1)_.
  * Joachims et al. (2017) Thorsten Joachims, Laura Granka, Bing Pan, Helene Hembrooke, and Geri Gay. 2017.  Accurately interpreting clickthrough data as implicit feedback. In _Acm Sigir Forum_ , Vol. 51. Acm New York, NY, USA, 4–11.
  * Joshi et al. (2020) Mandar Joshi, Danqi Chen, Yinhan Liu, Daniel S Weld, Luke Zettlemoyer, and Omer Levy. 2020\.  SpanBERT: Improving pre-training by representing and predicting spans.  _TACL_ 8 (2020), 64–77.
  * Katz et al. (2017) Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel J Kochenderfer. 2017.  Reluplex: An efficient SMT solver for verifying deep neural networks. In _International conference on computer aided verification_. Springer, 97–117.
  * Khattab and Zaharia (2020) Omar Khattab and Matei Zaharia. 2020.  Colbert: Efficient and effective passage search via contextualized late interaction over bert. In _SIGIR_.
  * Lecuyer et al. (2019) Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. 2019.  Certified robustness to adversarial examples with differential privacy. In _2019 IEEE Symposium on Security and Privacy (SP)_. IEEE.
  * Liang et al. (2017) Bin Liang, Hongcheng Li, Miaoqiang Su, Pan Bian, Xirong Li, and Wenchang Shi. 2017\.  Deep text classification can be fooled.  _arXiv preprint arXiv:1704.08006_ (2017).
  * Lin et al. (2021) Jimmy Lin, Rodrigo Nogueira, and Andrew Yates. 2021\.  Pretrained transformers for text ranking: Bert and beyond.  _Synthesis Lectures on Human Language Technologies_ 14, 4 (2021), 1–325.
  * Liu (2011) Tie-Yan Liu. 2011\.  _Learning to Rank for Information Retrieval_.  Springer Science & Business Media.
  * Ma et al. (2021) Xinyu Ma, Jiafeng Guo, Ruqing Zhang, Yixing Fan, Yingyan Li, and Xueqi Cheng. 2021\.  B-PROP: Bootstrapped pre-training with representative words prediction for ad-hoc retrieval.  _arXiv preprint arXiv:2104.09791_ (2021).
  * Madry et al. (2017) Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. 2017\.  Towards deep learning models resistant to adversarial attacks.  _arXiv preprint arXiv:1706.06083_ (2017).
  * Madry et al. (2018) Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. 2018\.  Towards Deep Learning Models Resistant to Adversarial Attacks. In _ICLR_.
  * Mitra et al. (2017) Bhaskar Mitra, Fernando Diaz, and Nick Craswell. 2017\.  Learning to match using local and distributed representations of text for web search. In _WWW_.
  * Miyato et al. (2016) Takeru Miyato, Andrew M Dai, and Ian Goodfellow. 2016\.  Adversarial training methods for semi-supervised text classification.  _arXiv preprint arXiv:1605.07725_ (2016).
  * Nguyen et al. (2016) Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng. 2016.  MS MARCO: A human generated machine reading comprehension dataset. In _CoCo@ NIPS_.
  * Niu et al. (2012) Shuzi Niu, Jiafeng Guo, Yanyan Lan, and Xueqi Cheng. 2012\.  Top-k learning to rank: labeling, ranking and evaluation. In _SIGIR_. 751–760.
  * Nogueira and Cho (2019) Rodrigo Nogueira and Kyunghyun Cho. 2019.  Passage Re-ranking with BERT.  _arXiv preprint arXiv:1901.04085_ (2019).
  * Ntoulas et al. (2006) Alexandros Ntoulas, Marc Najork, Mark Manasse, and Dennis Fetterly. 2006.  Detecting spam web pages through content analysis. In _Proceedings of the 15th international conference on World Wide Web_. 83–92.
  * Onal et al. (2018) Kezban Dilek Onal, Ye Zhang, Ismail Sengor Altingovde, Md Mustafizur Rahman, Pinar Karagoz, Alex Braylan, Brandon Dang, Heng-Lu Chang, Henna Kim, Quinten McNamara, Aaron Angert, Edward Banner, Vivek Khetan, Tyler McDonnell, An Thanh Nguyen, Dan Xu, Byron C. Wallace, Maarten de Rijke, and Matthew Lease. 2018\.  Neural information retrieval: At the end of the early years.  _Information Retrieval Journal_ 21, 2–3 (June 2018), 111–182.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher D Manning. 2014.  Glove: Global vectors for word representation. In _EMNLP_. 1532–1543.
  * Piskorski et al. (2008) Jakub Piskorski, Marcin Sydow, and Dawid Weiss. 2008\.  Exploring linguistic features for web spam detection: a preliminary study. In _Proceedings of the 4th international workshop on Adversarial information retrieval on the web_. 25–28.
  * Ponte and Croft (1998) Jay M Ponte and W Bruce Croft. 1998.  A language modeling approach to information retrieval. In _SIGIR_. 275–281.
  * Radev et al. (2002) Dragomir R Radev, Hong Qi, Harris Wu, and Weiguo Fan. 2002\.  Evaluating Web-based Question Answering Systems.. In _LREC_. Citeseer.
  * Ren et al. (2019) Shuhuai Ren, Yihe Deng, Kun He, and Wanxiang Che. 2019\.  Generating natural language adversarial examples through probability weighted word saliency. In _ACL_. 1085–1097.
  * Ribeiro et al. (2018) Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. 2018\.  Semantically equivalent adversarial rules for debugging NLP models. In _ACL_.
  * Robertson and Walker (1994) Stephen E Robertson and Steve Walker. 1994.  Some simple effective approximations to the 2-poisson model for probabilistic weighted retrieval. In _SIGIR’94_. Springer, 232–241.
  * Singh et al. (2019) Gagandeep Singh, Rupanshu Ganvir, Markus Püschel, and Martin Vechev. 2019.  Beyond the single neuron convex barrier for neural network certification.  _NIPS_ (2019).
  * Szegedy et al. (2013) Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. 2013\.  Intriguing properties of neural networks.  _arXiv preprint arXiv:1312.6199_ (2013).
  * Wang et al. (2021) Wenjie Wang, Pengfei Tang, Jian Lou, and Li Xiong. 2021\.  Certified robustness to word substitution attack with differential privacy. In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_. 1102–1112.
  * Wang et al. (2019) Yisen Wang, Xingjun Ma, James Bailey, Jinfeng Yi, Bowen Zhou, and Quanquan Gu. 2019\.  On the Convergence and Robustness of Adversarial Training. In _ICML_.
  * Wu et al. (2022) Chen Wu, Ruqing Zhang, Jiafeng Guo, Maarten de Rijke, Yixing Fan, and Xueqi Cheng. 2022\.  PRADA: Practical Black-Box Adversarial Attacks against Neural Ranking Models.  _arXiv preprint arXiv:2204.01321_ (2022).
  * Wu et al. (2021) Chen Wu, Ruqing Zhang, Jiafeng Guo, Yixing Fan, and Xueqi Cheng. 2021.  Are Neural Ranking Models Robust?  _arXiv preprint arXiv:2108.05018_ (2021).
  * Xia et al. (2009) Fen Xia, Tie-Yan Liu, and Hang Li. 2009.  Statistical consistency of top-k ranking.  _NIPS_ 22 (2009).
  * Yang et al. (2018) Peilin Yang, Hui Fang, and Jimmy Lin. 2018.  Anserini: Reproducible ranking baselines using Lucene.  _Journal of Data and Information Quality (JDIQ)_ 10, 4 (2018), 1–20.
  * Ye et al. (2020) Mao Ye, Chengyue Gong, and Qiang Liu. 2020.  SAFER: A structure-free approach for certified robustness to adversarial word substitutions.  _arXiv preprint arXiv:2005.14424_ (2020).
  * Zang et al. (2019) Yuan Zang, Fanchao Qi, Chenghao Yang, Zhiyuan Liu, Meng Zhang, Qun Liu, and Maosong Sun. 2019.  Word-level textual adversarial attacking as combinatorial optimization.  _arXiv preprint arXiv:1910.12196_ (2019).
  * Zhang et al. (2020) Wei Emma Zhang, Quan Z Sheng, Ahoud Alhazmi, and Chenliang Li. 2020.  Adversarial attacks on deep-learning models in natural language processing: A survey.  _TIST_ 11, 3 (2020), 1–41.
  * Zhou et al. (2020) Mo Zhou, Zhenxing Niu, Le Wang, Qilin Zhang, and Gang Hua. 2020.  Adversarial ranking attack and defense. In _ECCV_.