Deterministic and Probabilistic Certified Defenses for Content-Based Image Retrieval

Kazuya KAKIZAKI, Kazuto FUKUCHI, Jun SAKUMA

Summary :

This paper develops certified defenses for deep neural network (DNN) based content-based image retrieval (CBIR) against adversarial examples (AXs). Previous works put their effort into certified defense for classification to improve certified robustness, which guarantees that no AX to cause misclassification exists around the sample. Such certified defense, however, could not be applied to CBIR directly because the goals of adversarial attack against classification and CBIR are completely different. To develop the certified defense for CBIR, we first define the new certified robustness of CBIR, which guarantees that no AX that changes the ranking results of CBIR exists around the input images. Then, we propose computationally tractable verification algorithms that verify whether a given feature extraction DNN satisfies the certified robustness of CBIR at given input images. Our proposed verification algorithms are achieved by evaluating the upper and lower bounds of distances between feature representations of perturbed and non-perturbed images in deterministic and probabilistic manners. Finally, we propose robust training methods to obtain feature extraction DNNs that increase the number of inputs that satisfy the certified robustness of CBIR by tightening the upper and lower bounds. We experimentally show that our proposed certified defenses can guarantee robustness deterministically and probabilistically on various datasets.

• Publication: IEICE TRANSACTIONS on Information Vol.E108-D No.1 pp.92-109
• Publication Date: 2025/01/01
• Publicized: 2024/09/05
• Online ISSN: 1745-1361
• DOI: 10.1587/transinf.2023EDP7229
• Type of Manuscript: PAPER
• Category: Image Recognition, Computer Vision

1.  Introduction

Content-based image retrieval (CBIR) is a task that retrieves visually similar images to a given query image from a set of candidate images. Modern CBIR performs retrieval by ranking the similarity between the query image and candidate images based on feature extraction deep neural networks (DNNs) trained by metric learning [1]. However, recent studies reveal that such DNN-based CBIR is vulnerable to small human-imperceptible perturbation to the input data, called adversarial examples (AXs) [2]-[10]. Such AXs can be input to DNN-based CBIR as the query or candidate images and maliciously modify the ranking results by manipulating the output of the feature extraction DNNs. Since the DNN-based CBIR is often involved in security-critical systems such as person re-identification [11], defense methods for DNN-based CBIR against AXs are necessary.

A great deal of effort has been devoted to empirical defense methodologies for the classification task. Adversarial training [12], which trains DNNs using AXs as training data, is one of the most effective empirical defense methodologies for classification. Adversarial training has also been shown to be effective in CBIR empirically [2], [3]. While these empirical defense methods achieve robustness against conventional attacks, they often suffer from adaptive attacks [13], which assume the attacker is aware of the strategy of the defense method. Since there is no guarantee that these empirical defense methods are effective against adaptive attacks, defense methods with theoretical guarantees of robustness are needed to deal with adaptive attacks.

To overcome adaptive attacks, many studies have worked to establish defense with certified robustness of classification [14]. Certified robustness means that there is no AX to cause misclassification within an \(l_p\)-ball centered on a given sample. This type of defense is referred to as certified defense. Certified defense generally consists of (i) a verification algorithm to verify whether a given classifier satisfies certified robustness at a given sample and (ii) robust training for classifiers to increase the number of samples that can be verified by the corresponding verification algorithm. Since exact verification is known to be reduced to an NP-complete problem [15], [16], the verification algorithms alternatively evaluate a sufficient condition of certified robustness that depend on the upper and lower bounds of the classifier’s predictions against AXs in the \(l_p\)-ball. Then, the bounds are computed by computationally tractable deterministic or probabilistic algorithms [16]-[22]. While using the bounds makes the verification computationally tractable, the results can include false negatives, i.e., given samples are determined to be not robust, even when they actually achieve certified robustness. Considering that the looseness of the bounds causes this gap, robust training to make this bound tighter has been introduced. By training the classifier in this way, we can expect to reduce the number of cases where robust samples are misjudged to be non-robust.

1.1  Related Work

Some studies proposed certified defenses for classification, which guarantee certified robustness deterministically. This type of certified defense includes a verification algorithm that computes the upper and lower bounds of logits in a deterministic manner. [19], [23] utilize the Lipschitz constant of neural networks to calculate the bounds. [16]-[18] calculate the bounds by linear relaxations of ReLU activations. [20], [21] propose a straightforward but effective method called interval bound propagation (IBP) that propagates the upper and lower bounds for each layer. These deterministic certified defenses can guarantee certified robustness for low-resolution images such as CIFAR10 (\(32\times32\)) with small false negatives. However, they are known to be difficult to scale to high-resolution images such as ImageNet (\(224\times224\)) [14] because the evaluation of the upper and lower bounds is too loose.

Another line of certified defense for classification is probabilistic. This type of certified defense is also called randomized smoothing (RS). RS achieves the verification for certified robustness by estimating the upper and lower bounds of the classifier’s prediction in a probabilistic manner. Concretely, RS smooths the classifier with Gaussian [22], [24] or Laplace [25] distribution and theoretically derives the upper and lower bounds on the prediction of the smoothed model. Then, the bounds are probabilistically estimated by Monte Carlo algorithm. As a result, different from the deterministic verification algorithms, the result of RS contains not only false negatives but also false positives with small probability. However, RS can scale to high-resolution images; RS can provide the meaningful evaluation of the upper and lower bounds for high-resolution images.

Although certified defense for classification has been investigated extensively, less attention has been paid to certified defense for CBIR. Moreover, the existing certified defenses for classification cannot be directly applied to CBIR because the goals of the adversarial attack against classification and CBIR are completely different. Specifically, the adversarial attacks against classification aim to change the predicted class label of the classifier, whereas the adversarial attacks against CBIR aim to change the ranking results of CBIR calculated by feature extraction DNNs. Thus, new definitions of certified robustness tailored to CBIR and certified defense to guarantee it should be considered. Only [26] have proposed a certified defense for CBIR, named RetrievalGuard, which guarantees that no AX changes the top-1 ranking results of CBIR. However, since RetrievalGuard does not guarantee the invariance of any ranking result other than top-1, its use is limited.

1.2  Our Contributions

In this paper, we develop two types of certified defenses for CBIR that guarantee robustness deterministically or probabilistically. Our contribution is four-fold. First, we define the new certified robustness of CBIR, named \((l_p, \alpha, \epsilon)\)-robustness. \((l_p, \alpha, \epsilon)\)-robustness means that no AX exists within \(l_{p}\)-balls with radius \(\epsilon \in \mathbb{R}\) centered on the query or candidate images that changes the ranking result of a specific candidate image more than \(\alpha \in \mathbb{N}\). Different from the existing certified robustness of CBIR that guarantees the invariance of top-1 ranking results [26], \((l_p,\alpha, \epsilon)\)-robustness can guarantee the invariance of any ranking results.

Second, we introduce a tractable sufficient condition for \((l_p, \alpha, \epsilon)\)-robustness. To verify whether a given feature extraction DNN satisfies \((l_p,\alpha, \epsilon)\)-robustness at given a query and candidate images, we need to evaluate the exact maximum and minimum distances in the feature space between AXs in the \(l_p\)-balls and the benign images. That makes the verification computationally intractable. To alleviate this, we derive the sufficient condition for \((l_p,\alpha, \epsilon)\)-robustness using the upper and lower bounds of the distances. Then, we achieve certified defenses that guarantee \((l_\infty,\alpha, \epsilon)\)-robustness and \((l_2,\alpha, \epsilon)\)-robustness by evaluating the upper and lower bounds of the distances with our proposed deterministic and probabilistic tractable methods, respectively.

Third, we present a certified defense for CBIR, which guarantees \((l_\infty,\alpha, \epsilon)\)-robustness in a deterministic manner. To this end, we first propose a tractable verification algorithm, which evaluates the derived sufficient condition by applying interval bound propagation (IBP) [21] to feature extraction DNNs. Concretely, we evaluate the upper and lower bounds of the distances by propagating bounds from the input space to the feature space. Since the computational complexity of IBP is equivalent to two forward propagations of DNNs, we can evaluate the derived sufficient conditions in polynomial time. Moreover, we also propose robustness training methods of feature extraction DNNs that attain tighter evaluation of the upper and lower bounds of the distances. When the bounds are loose, our verification algorithms can judge truly robust inputs as non-robust. To decrease such misjudging, we introduce new objective functions to train feature extraction DNNs that encourage tighter bounds of distances evaluated by IBP. We experimentally confirmed that the robustness training method can increase the number of samples verified by our proposed deterministic verification algorithm for MNIST [27], Fashion-MNIST [28], and CIFAR10 [29].

Fourth, we present a certified defense for CBIR, which guarantees \((l_2,\alpha, \epsilon)\)-robustness probabilistically. We experimentally confirmed that our proposed deterministic certified defense does not scale to high-resolution images such as CUB (\(224\times224\)) [30]. To overcome this limitation, inspired by the success of randomized smoothing (RS) for classification setting, we propose a verification algorithm to evaluate the derived sufficient condition using the upper and lower bounds of Gaussian smoothed distances, of which input is smoothed with Gaussian distributions. Specifically, we theoretically derive the upper and lower bounds on the Gaussian smoothed distance and probabilistically estimate them by our proposed Monte Carlo algorithms. Moreover, we propose to use Gaussian data augmentation [22], [26] to training data of feature extraction DNNs for obtaining tighter bounds of the Gaussian smoothed distances. We theoretically and experimentally show that our probabilistic certified defense, different from the deterministic one, includes false positives as well as false negatives but can scale to higher-resolution images.

Note that this is an extension of our conference paper [31]. The main content extended from the conference paper is the proposal and experimental evaluations of the probabilistic certified defense.

The paper is organized as follows. Section 2 describes the background of this study and defines the new certified robustness of CBIR, \((l_p, \alpha, \epsilon)\)-robustness. Section 3 derives the sufficient conditions of \((l_p, \alpha, \epsilon)\)-robustness using the upper and lower bounds of the distances. Section 4 proposes deterministic certified defense: deterministic verification algorithms and their robustness training. Section 5 proposes probabilistic certified defense: probabilistic verification algorithms and their robustness training. In Sect. 6, we evaluate our proposed deterministic and probabilistic certified defenses. Section 7 provides potential directions for future research focusing on enhancing the certified defense for CBIR. Section 8 concludes the paper.

2.  Preliminaries

2.1  Content-Based Image Retrieval (CBIR)

CBIR is a task to find images similar to a query image in a set of candidate images. Let \(X\) be the instance space. Let \(q \in X\) be a query image and \(C=\{c_i | c_i \in X \}^{|C|}_{i=1}\) be a set of candidate images. Let \(f: X \rightarrow \mathbb{R}^{d}\) be a feature extractor where \(d\) is the feature dimension. Then, CBIR ranks \(\forall c \in C\) with distance \(d(f(q),f(c))\) and retrieves the top-\(k\) similar images to \(q\) in \(C\). In this paper, \(\mathrm{Rank}(q, c, C)\) represents the rank of \(c \in C\) in terms of the similarity to \(q\). We omit \(f\) from the augments of \(\mathrm{Rank}(q, c, C)\) for notational simplicity when it is obvious from the context.

2.2  Adversarial Attacks against CBIR

In recent years, many studies have focused on adversarial attacks on CBIR [2]-[10]. These attacks can be categorized into two types of attacks, query attack (QA) and candidate attack (CA), depending on whether the AX is given as a query image or a candidate image.

Query Attack (QA). Let \(C_t \subset C\) be the target candidates in \(C\) specified by the adversary. The adversary aiming at QA perturbs a source query image \(q_s\) to raise or lower the rank of the candidates in \(C_t\). When the attacker’s goal is to raise the rank of the candidates in \(C_t\), adversarial perturbation \(\delta\) for QA is obtained by solving the following optimization problem:

\[\begin{align} \min_{\delta \in X, \|\delta\|_{p} \leq \epsilon} \sum_{t \in C_t} \mathrm{Rank}(q_s+\delta,t, C), \tag{1} \end{align}\]

where \(\|\cdot \|_{p}\) is \(l_p\) norm and \(\epsilon \in \mathbb{R}_{\geq 0}\) is a constant that bounds the size of the perturbation. Equation (1) cannot be solved directly due to the discrete nature of \(\mathrm{Rank}(\cdot)\). Instead, [2], [3] minimizes the following objective function:

\[\begin{align} \min_{\substack{\delta \in X, \\ \|\delta\|_{p} \leq \epsilon}} \sum_{t \in C_t} \sum_{c \in C} [d(f(q_s+\delta),f(t)) - d(f(q_s+\delta),f(c)) ]_+. \tag{2} \end{align}\]

Minimization in Eq. (1) is changed to maximization when the attacker’s goal is to lower the rank of the candidates in \(C_t\).

Candidate Attack (CA). Let \(Q_t=\{q_i \in X\}_{i=1}^{M}\) be a set of target query images specified by the adversary. The adversary aiming at CA perturbs a source candidate image \(c_s \in C\) so that the rank of perturbed \(c_s\) is raised or lowered when \(\forall q \in Q_t\) is issued as a query. When the attacker’s goal is to raise the rank of the perturbed \(c_s\), adversarial perturbation for CA is obtained by the following minimization problem with respect to \(\delta\):

\[\begin{align} \min_{\delta \in X, \|\delta\|_{p} \leq \epsilon} \sum_{t \in Q_t} \mathrm{Rank}(t,c_s+\delta, C). \tag{3} \end{align}\]

where \(\|\cdot\|_{p}\) is \(l_p\) norm and \(\epsilon \in \mathbb{R}_{\geq 0}\) is a constant that bounds the size of the perturbation. Since optimization in Eq. (3) is intractable, [2], [3] optimizes the following objective function instead:

\[\begin{align} \min_{\substack{\delta \in X, \\ \|\delta\|_{p} \leq \epsilon}} \sum_{t \in Q_t} \sum_{c \in C} \biggl[d(f(t),f(c_s+\delta)) - d(f(t),f(c)) \biggr]_+, \tag{4} \end{align}\]

As well as QA, minimization in Eq. (3) is changed to maximization when the attacker’s goal is to lower the rank of the perturbed \(c\).

2.3  Certified Robustness

Here, we briefly review the existing definition of the certified robustness and verification algorithms for classification. Then, we define two new certified robustness of CBIR.

2.3.1  Certified Robustness of Classification

The adversarial attacks against the classifier aim to change the predicted label of the classifier to an untargeted or targeted label by perturbing the input images [12], [32]. The certified robustness of classification guarantees that predicted labels are kept invariant when the size of adversarial perturbation is limited within a specified range:

Definition 1 (Certified Robustness of Classification [14]). Let \(x \in X\) be a input image and \(t \in \{1, \ldots, C\}\) be corresponding label to \(x\). Let \(f_c: X \rightarrow \mathbb{R}^C\) and \(f_c(x)_j\) be the vector of logits and the logit of class \(j \in \{1, \ldots, C\}\) for \(x\), respectively. Let \(\epsilon \in \mathbb{R}_{\geq 0}\). Then, classifier \(F_c(x) := \mathop{\mathrm{arg~max}}\limits\nolimits_{j \in \{1, \ldots, C\}} f_c(x)_j\) is certified robust at \(x\) if \(F_c(x+\delta) = t\) for \(\forall \delta \in \{\delta \ | \ \delta \in X, \|\delta \|_{p} \leq \epsilon\}\).

Verification Algorithms for Classification. When classifier \(F_c\) is DNN with ReLUs, verifying whether given \(F_c\) satisfies certified robustness at given \(x\) is reduced to an NP-complete problem [15], [16]. To make the verification computationally tractable, existing verification algorithms use the lower bounds of margins between logits \(\underline{m}_i(x) \leq \min_{\delta, \|\delta \|_{p} \leq \epsilon} f_c(x+\delta)_t - f_c(x+\delta)_{i:i \neq t}\) or class probabilities \(\underline{m}_i(x) \leq \min_{\delta, \|\delta \|_{p} \leq \epsilon} \Pr[F_c(x+\delta)=t] - \Pr[f_c(x+\delta)=i]_{i:i\neq t}\) against AXs in the \(l_p\)-ball. Then, the bounds are computed by computationally tractable deterministic methods such as interval bound propagation [21] or estimated by probabilistic methods such as randomized smoothing [22]. Then, if \(\underline{m}_i(x)>0\), the verification algorithms determine the classifier satisfies certified robustness at \(x\). In this paper, we call the verification algorithms deterministic and probabilistic verification algorithms when the bounds are computed through deterministic and probabilistic methods, respectively. We remark that the results of the deterministic verification algorithms do not include false positives but false negatives because \(\underline{m}_i(x)>0\) is a sufficient condition for Definition 1. On the other hand, the results of the probabilistic verification algorithms include not only false negatives but also false positives with a certain probability. However, the probabilistic verification algorithms have the advantage of scaling to large-scale images such as ImageNet [33], which is difficult to be verified by the deterministic verification algorithms [22].

2.3.2  Certified Robustness of CBIR

Definition 1 is not suitable for CBIR because the goals of adversarial attacks against classification and CBIR are different: the adversarial attacks against classification aim to change the predicted class label of the classifier, whereas QA and CA aim to change the rank of the candidates. Thus, in certified defense for CBIR, we need to consider rank invariance rather than label invariance against AXs. We define the certified robustness of CBIR against QA and CA as follows, respectively:

Definition 2 (\((l_p, \alpha,\epsilon)\)-Robustness against QA). Let \(f: X \rightarrow \mathbb{R}^{d}\) be a feature extractor. Let \(q\in X\) and \(C=\{c_i | c_i \in X \}^{N}_{i=1}\) be a query image and a set of candidate images, respectively. Let \(\alpha \in \mathbb{N}_0\) and \(\epsilon \in \mathbb{R}_{\geq 0}\). Then, for \(\forall \delta \in \{\delta \ | \ \delta \in X, \|\delta \|_{p} \leq \epsilon \}\), \(f\) satisfies \((l_p, \alpha,\epsilon)\)-robust against QA at \(q\), \(c_i \in C\), and \(C\) if

\[\begin{align} | \mathrm{Rank}(q+\delta, c_i, C) - \mathrm{Rank}(q, c_i, C)| \leq \alpha. \tag{5} \end{align}\]

Definition 3 (\((l_p, \alpha,\epsilon)\)-Robustness against CA). Let \(f: X \rightarrow \mathbb{R}^{d}\) be a feature extractor. Let \(q\in X\) and \(C=\{c_i | c_i \in X \}^{N}_{i=1}\) be a query image and a set of candidate images, respectively. Let \(\alpha \in \mathbb{N}_0\) and \(\epsilon \in \mathbb{R}_{\geq 0}\). Then, for \(\tilde{C}=\{c_i + \delta_i\}_{i=1}^{N}\) where \(\forall \delta_1,\ldots,\forall \delta_N \in \{\delta \ | \ \delta \in X, \|\delta \|_{p} \leq \epsilon \}\), \(f\) satisfies \((l_p, \alpha,\epsilon)\)-robust against CA at \(q\), \(c_i \in C\), and \(C\) if

\[\begin{align} | \mathrm{Rank}(q, c_i+\delta_i, \tilde{C}) - \mathrm{Rank}(q, c_i, C)| \leq \alpha. \tag{6} \end{align}\]

In both robustness definitions, we introduced \(\alpha\) to relax the strictness of the guarantee because requiring complete rank invariance can be too strict.

3.  Sufficient Conditions for \((l_p, \alpha, \epsilon)\)-Robustness

Since verifying whether given inputs satisfy \((l_p,\alpha, \epsilon)\)-robustness against QA and CA (Definition 2 and Definition 3) are computationally intractable, the key challenge of designing the verification algorithms is to make them relax and computationally efficient. Our idea to recover tractability is to introduce computationally tractable sufficient conditions for them. Unfortunately, the existing sufficient condition for certified robustness for classifier described in Sect. 2.3 (\(\underline{m}_i(x) > 0\)) cannot be used directly because \((l_p,\alpha, \epsilon)\)-robustness against QA and CA depend on the distances in the feature space rather than the margins of logits or class probabilities. Thus, in this section, we first derive sufficient conditions for \((l_p,\alpha, \epsilon)\)-robustness against QA and CA using the upper and lower bounds of the distances against AXs in the \(l_p\)-ball, assuming that the bounds can be obtained in a tractable way. Then, in Sects. 4 and 5, we introduce computationally tractable algorithms to obtain the upper and lower bounds of the distances in a deterministic and probabilistic manner, respectively.

Let \(x_1, x_2 \in X\) and \(\epsilon \in \mathbb{R}_{\geq0}\). Then, we define upper and lower bounds of distance against AXs in the \(l_p\)-ball as follows:

\[\begin{align} & \overline{d}_{x_2}(x_1) \geq \max_{\delta, \|\delta \|_{p} \leq \epsilon} d(f(x_1+\delta),f(x_2)), \tag{7} \\ & \underline{d}_{x_2}(x_1) \leq \min_{\delta, \|\delta \|_{p} \leq \epsilon} d(f(x_1+\delta),f(x_2)). \tag{8} \end{align}\]

We omit \(f\) from the augments of \(\overline{d}_{x_2}(x_1)\) and \(\underline{d}_{x_2}(x_1)\) for notational simplicity when it is obvious from the context.

To derive sufficient conditions for Definition 2 and Definition 3, we first derive upper and lower bounds of \(\mathrm{Rank}(q+\delta, c_i, C)\) in Eq. (5) and \(\mathrm{Rank}(q, c_i + \delta_i, \tilde{C})\) in Eq. (6) by comparing \(\overline{d}_{x_2}(x_1)\) and \(\underline{d}_{x_2}(x_1)\):

Lemma 1 (Upper and Lower Bounds of Rank against QA). For \(\forall \delta \in \{\delta \ | \ \delta \in X, \|\delta \|_{p} \leq \epsilon \}\), the following holds:

\[\begin{align} & |C|-\sum_{c \in C} \text{𝟙} \bigl[ \overline{d}_{c_i}(q) < \underline{d}_{c}(q) \bigr] \geq \mathrm{Rank}(q+\delta, c_i, C) \tag{9} \\ & \sum_{c \in C} \text{𝟙} \bigl[ \overline{d}_{c}(q) < \underline{d}_{c_i}(q) \bigr]+1 \leq \mathrm{Rank}(q+\delta, c_i, C). \tag{10} \end{align}\]

Proof. The proof is shown in Appendix A.1. \(\tag*{◻}\)

Lemma 2 (Upper and Lower Bounds of Rank against CA). For \(\tilde{C}=\{c_i + \delta_i\}_{i=1}^{N}\) where \(\forall \delta_1, \ldots,\forall \delta_N \in \{\delta \ | \ \delta \in X, \|\delta \|_{p} \leq \epsilon \}\), the following holds:

\[\begin{align} & |C|- \sum_{c \in C} \text{𝟙} \bigl[ \overline{d}_q(c_i) < \underline{d}_q(c) \bigr] \geq \mathrm{Rank}(q, c_i+\delta_i, \tilde{C}) \tag{11} \\ & \sum_{c \in C} \text{𝟙} \bigl[ \overline{d}_q(c) < \underline{d}_q(c_i) \bigr]+1 \leq \mathrm{Rank}(q, c_i+\delta_i, \tilde{C}). \tag{12} \end{align}\]

Proof. The proof is shown in Appendix A.2. \(\tag*{◻}\)

From Theorem 1 and Theorem 2, we can also immediately obtain the upper and lower bounds of \(|\mathrm{Rank}(q+\delta, c_i, C) - \mathrm{Rank}(q, c_i, C)|\) and \(|\mathrm{Rank}(q, c_i + \delta_j, \tilde{C})- \mathrm{Rank}(q, c_i, C)|\) in Eqs. (5) and (6), respectively. We can derive sufficient condition for Definition 2 and Definition 3 by comparing the bounds with \(\alpha\):

Theorem 1 (Sufficient Condition for (\(\alpha,\epsilon\))-Robustness against QA). Feature extractor \(f\) satisfies \((l_p,\alpha,\epsilon)\)-robustness against QA at \(q\), \(c_i \in C\), and \(C\) if

\[\begin{align} & \alpha \geq |C|- \sum_{c \in C} \text{𝟙} \biggl[ \overline{d}_{c_i}(q) < \underline{d}_{c}(q) \biggr] - \mathrm{Rank}(q, c_i, C) \tag{13} \\ & \land -\alpha \leq \sum_{c \in C} \text{𝟙} \biggl[ \overline{d}_{c}(q) < \underline{d}_{c_i}(q) \biggr] +1 - \mathrm{Rank}(q, c_i, C). \nonumber \end{align}\]

Proof. The proof is shown in Appendix A.3 \(\tag*{◻}\)

Theorem 2 (Sufficient Condition for (\(\alpha,\epsilon\))-Robustness against CA). Feature extractor \(f\) satisfies satisfies \((l_p,\alpha,\epsilon)\)-robust against CA at \(q\), \(c_i \in C\), and \(C\) if

\[\begin{align} & \alpha \geq |C|- \sum_{c \in C} \text{𝟙} \biggl[ \overline{d}_q(c_i) < \underline{d}_q(c) \biggr] -\mathrm{Rank}(q, c_i, C) \tag{14} \\ & \land -\alpha \leq \sum_{c \in C} \text{𝟙} \biggl[ \overline{d}_q(c) < \underline{d}_q(c_i) \biggr] +1 -\mathrm{Rank}(q, c_i, C). \nonumber \end{align}\]

Proof. The proof is shown in Appendix A.4. \(\tag*{◻}\)

From Theorem 1 and Theorem 2, verifying \((l_p, \epsilon, \alpha)\)-robustness against QA and CA is computationally tractable if the evaluation of \(\overline{d}_{x_2}(x_1)\) and \(\underline{d}_{x_2}(x_1)\) is computationally tractable.

4.  Deterministic Certified Defense for CBIR

In this section, we propose deterministic certified defenses for CBIR, which guarantee \((l_\infty, \epsilon, \alpha)\)-robustness against QA and CA deterministically.

4.1  Deterministic Verification Algorithms

In this subsection, we propose verification algorithms, which verify whether given inputs satisfy \((l_\infty, \epsilon, \alpha)\)-robustness against QA and CA in a tractable deterministic manner. Our deterministic verification algorithms evaluate the derived sufficient conditions Eqs. (13) and (14). Since they are sufficient conditions, they do not necessarily hold for inputs truly satisfying \((l_p, \epsilon, \alpha)\)-robustness against QA and CA. Whether they can hold depends on the tightness of \(\overline{d}_{x_2}(x_1)\) and \(\underline{d}_{x_2}(x_1)\). For this reason, we need to obtain meaningfully tight evaluation of \(\overline{d}_{x_2}(x_1)\) and \(\underline{d}_{x_2}(x_1)\). To obtain a meaningfully tight evaluation of \(\overline{d}_{x_2}(x_1)\) and \(\underline{d}_{x_2}(x_1)\), we utilize interval bound propagation (IBP) [21], [34]. IBP is an tractable algorithm for calculating the upper and lower bounds of logits when an \(l_\infty\)-ball is given as input. IBP is used for deterministic verification for classification and is known to give a meaningfully tight bound for this purpose.

Original interval bound propagation (IBP). Given, \(x \in X\), \(\epsilon \in \mathbb{R}_{\geq 0}\), and \(L\)-layer classifier \(f_c\), original IBP evaluates the upper and lower bounds of \(f_c(x+\delta)\) for \(\forall \delta \in \{\delta \ | \ \delta \in X, \|\delta \|_{\infty} \leq \epsilon \}\). Let \(z^l = W^l h^{l-1} + b^l\) be the \(l\)-th affine layer (e.g. fully connected layer and convolution layer) and \(h^{l-1}=\sigma(z^{l-1})\) be a monotonic activation function (e.g. ReLU) where \(l \in \{1, \ldots, L\}\) and \(h^{0} = x\). Then, IBP provides upper and lower bounds on the outputs of \(l\)-th affine layers as follows:

\[\begin{align} & \overline{z}^l = W^l \frac{\overline{h}^{l-1} + \underline{h}^{l-1}}{2} + |W^l| \frac{\overline{h}^{l-1} - \underline{h}^{l-1}}{2} + b^l, \tag{15} \\ & \underline{z}^l = W^l \frac{\overline{h}^{l-1} + \underline{h}^{l-1}}{2} - |W^l| \frac{\overline{h}^{l-1} - \underline{h}^{l-1}}{2} + b^l, \tag{16} \end{align}\]

where \(|\cdot|\) represents the element-wise absolute value operator, \(\overline{h}^{l-1} = \sigma(\overline{z}^{l-1})\), \(\underline{h}^{l-1} = \sigma(\underline{z}^{l-1})\), \(\overline{h}^0=x + \epsilon \mathbf{1}\), and \(\underline{h}^0=x - \epsilon \mathbf{1}\).

4.1.1  Evaluation for \(\overline{d}_{x_2}(x_1)\) and \(\underline{d}_{x_2}(x_1)\) via IBP

We propose tractable methods to evaluate \(\overline{d}_{x_2}(x_1)\) and \(\underline{d}_{x_2}(x_1)\) when using Euclidean distance as \(d_{x_2}(x_1)\). Let \(f(x)_i\) be the \(i\)-th element of \(f(x)\). Let \(\overline{f}(x)_i\) and \(\underline{f}(x)_i\) be upper and lower bounds of \(f(x)_i\) calculated by IBP, respectively. Then, we can evaluate \(\overline{d}_{x_2}(x_1)\) and \(\underline{d}_{x_2}(x_1)\) by the following theorems:

Theorem 3. \(\max_{\delta \in X, \|\delta \|_{\infty} \leq \epsilon} \|f(x_1+\delta) - f(x_2) \|_2\) is upper bounded by

\[\begin{align} \sqrt{ \sum_{i \in \{1, \ldots, d\}} \max\bigl \{ |\overline{f}(x_1)_{i}-f(x_2)_{i}|, |f(x_2)_{i}-\underline{f}(x_1)_{i}|\bigr \}^2}. \tag{17} \end{align}\]

Proof. The proof is shown in A.5. \(\tag*{◻}\)

Theorem 4. \(\min_{\delta \in X, \|\delta \|_{\infty} \leq \epsilon} \|f(x_1+\delta) - f(x_2) \|_2\) is lower bounded by

\[\begin{align} \sqrt{ \sum_{i \in \{1, \ldots, d\}} \min\bigl \{ 0, \overline{f}(x_1)_{i}-f(x_2)_{i}, f(x_2)_{i}-\underline{f}(x_1)_{i} \bigr \}^2}. \tag{18} \end{align}\]

Proof. The proof is shown in A.6. \(\tag*{◻}\)

Evaluating Eqs. (17) and (18) to determine if the derived sufficient condition Eq. (13)/Eq. (14) is satisfied, we can obtain our tractable deterministic verification algorithms to verify \((l_\infty, \alpha, \epsilon)\)-robustness against QA and CA as follows:

\[\begin{align} \mathsf{Ver}_{\alpha, \epsilon}(q, c_i, C) = \begin{cases} \text{True} & \text{if Eq.$\,$(13)/(14) is True} \\ \text{False} & \text{otherwise}. \end{cases} \tag{19} \end{align}\]

We omit \(f\) from the augments of \(\mathsf{Ver}_{\alpha, \epsilon}(q,c_i, C)\) for notational simplicity when it is obvious from the context.

The computational costs of calculating the upper bound in Eq. (17) and the lower bound in Eq. (18) for a single pair of \((x_1,x_2)\) is comparable to three forward propagation of DNNs. The total number of forwards in evaluating Eqs. (13) and (14) is equivalent to \(|C|+3\) and \(3|C|+1\), respectively.

4.2  Robust Training Methods

In this subsection, we propose robustness training methods that increase the number of samples verified by our deterministic verification algorithms, Eq. (19). We experimentally confirm that Eqs. (13) and (14) are always not satisfied for all \(q\), \(c_i\), and \(C\) used in our experiments when using \(f\) trained by conventional metric learning (See Sect. 6 for details). This is because the upper and lower bounds calculated by Eqs. (17) and (18) can be too loose to satisfy the sufficient conditions Eqs. (13) and (14). To increase the number of inputs that satisfy Eqs. (13) and (14), we need to train \(f\) so that attains tighter evaluation of \(\overline{d}_{x_2}(x_1)\) and \(\underline{d}_{x_2}(x_1)\).

To this end, we propose two new objective functions to train feature extractor for CBIR. One is training of general feature extractor that attains tighter bounds in Eqs. (17) and (18) without knowledge of query and candidate images. The other is fine tuning of feature extractor given that candidate images for the target CBIR are provided. We remark that both algorithms are independent, and the latter algorithm can be applied to the feature extractor trained with the former algorithm.

4.2.1  Training General Feature Extractor for Robust CBIR

Recall that tighter evaluation of the upper bound in Eq. (17) and the lower bound in Eq. (18) is needed to attain certified robustness in a meaningful way. Our idea is to train \(f\) by simultaneously minimizing conventional objective function (e.g., triplet loss [35]) and the regularization term to make the bounds in Eqs. (17) and (18) tighter.

Let \(D_{train}=\{(a,p,n)_i\}^M_{i=1}\) be a training data set where \(p\) belongs to the same class as \(a\), and \(n\) belongs to a different class than \(a\). Here, the training dataset and query/candidate images of CBIR are mutually exclusive. Then, our objective function is given as follows:

\[\begin{align} & \min_{f} \sum_{(a, p, n)\in D_{train}} \kappa \cdot \mathrm{T}(a, p, n) + (1-\kappa) \cdot \sum_{x \in \{p, n\}}\mathrm{Reg}(a,x), \tag{20} \end{align}\]

where \(\mathrm{Reg}(a, x) = \max\{|d(f(a),f(x)) - \overline{d}_{x}(a)|,\ |d(f(a), f(x)) - \underline{d}_{x}(a)|\}\) and \(\mathrm{T}(a, p, n)\) is the triplet loss [35] often used in metric learning, which affects the performance of CBIR. \(\mathrm{Reg}(a, x)\) is a regularization term to encourage that the upper and lower bound of \(\|f(a+\delta)-f(x)\|_2\) are close to \(\|f(a)-f(x)\|_2\). \(\kappa \in [0,1]\) is a hyper parameter to adjust the trade-off between performance of CBIR and (\(l_\infty, \alpha,\epsilon\))-robustness of CBIR against QA and CA. We call the training with Eq. (20) as Tightly Bounding Training (TBT).

4.2.2  Fine-Tuning DNNs to Candidate Images

The feature extractor obtained by Eq. (20) is independent of the CBIR query and candidate set. In this subsection, assuming that the candidates images for the target CBIR are given, we show a method to fine tune the feature extractor to the set of candidate images. The objective of this fine-tuning is to reduce the gap between Definition 3 and the corresponding sufficient condition in Eq. (14) by adjusting \(f\) with the given candidate images. To achieve this, we update \(f\) so that tighter evaluation of Eqs. (17) and (18) is attained with given candidate images while maintaining the performance of CBIR.

Let \(C=\{c_i | c_i \in X \}^{N}_{i=1}\) be the set of candidate images. Let \(f_0\) be the pre-trained feature extractor before fine-tuning. Then, our objective function for fine-tuning is given as follows:

\[\begin{align} \min_{f} \sum_{c_1, c_2 \in C} \biggl( \kappa \cdot d(f_0(c_1),f(c_1)) + (1-\kappa) \cdot \mathrm{Reg}(c_1, c_2) \biggr). \tag{21} \end{align}\]

The first term maintains the accuracy of the CBIR by ensuring that the difference between the features calculated by \(f\) and \(f_0\) is small. The second term is a regularization term to encourage that the upper and lower bound of \(\|f(c_1+\delta)-f(c_2)\|_2\) are close to \(\|f(c_1)-f(c_2)\|_2\). \(\kappa \in [0,1]\) is a hyperparameter to adjust the trade-off between the performance of CBIR and (\(l_\infty, \alpha,\epsilon\))-robustness against CA. We call fine-tuning with Eq. (21) as Fine-tuning to Candidates with Tighter Bounds (FCTB).

5.  Probabilistic Certified Defense

In this section, we propose probabilistic certified defenses for CBIR, which guarantee \((l_2, \epsilon, \alpha)\)-robustness against QA and CA probabilistically.

5.1  Probabilistic Verification Algorithms

In this subsection, we propose algorithms to verify whether given inputs satisfy \((l_2, \epsilon, \alpha)\)-robustness against QA and CA in a probabilistic manner. We experimentally confirm that our deterministic verification algorithms, Eq. (19), can not verify high-resolution images even if we learn \(f\) with our robust training method, Eq. (20) (See Sect. 6 for details). To overcome the limitation, we utilize randomized smoothing (RS) [22], [24] to evaluate \(\overline{d}_{x_2}(x_1)\) and \(\underline{d}_{x_2}(x_1)\). RS is a tractable algorithm to estimate the upper and lower bounds of the class probability of the classifier against AXs in an \(l_2\)-ball. RS is used for probabilistic verification algorithms for classification and is known to scale to high-resolution images [14].

Original randomized smoothing (RS). Let \(F_c: X \rightarrow [C]\) be a classifier. Let \(N(0, \sigma^2 I)\) be a Gaussian distribution with mean 0 and standard deviation \(\sigma\). Gaussian smoothed classifier \(G_{F_c}(x): X \rightarrow [C]\) is defined as follows:

\[\begin{align} G_{F_c}(x) := \mathop{\mathrm{arg~max}}\limits_{j \in [C]} \Pr_{\xi \sim N(0, \sigma^2 I)} (F_c(x+\xi)=j). \tag{22} \end{align}\]

Then, randomized smoothing estimates the upper and lower bounds of the class probability of Gaussian smoothed classifier \(\Pr[G_{F_c}(x+\delta)=i]\) for \(\forall \delta \in \{\delta \ | \ \delta \in X, \|\delta \|_{2} \leq \epsilon \}\) with a certain probabilistic guarantee. Precisely, randomized smoothing uses Monte Carlo algorithm to estimate the upper and lower bounds \(\Phi(\Phi^{-1}(\Pr[G_{F_c}(x)=i])-\epsilon/\delta) \leq \Pr[G_{F_c}(x+\delta)=i]\leq \Phi(\Phi^{-1}(\Pr[G_{F_c}(x)=i])+\epsilon/\delta)\) theoretically derived by the Lipschitz continuity of Gaussian smoothed functions:

Theorem 5 (Lipschitz continuity of Gaussian Smoothed Functions [24], [36]). For any function \(h: X \rightarrow [0,1]\), \(\Phi^{-1}(\mathbb{E}_{\xi \sim N(0, \sigma^2 I)}[h(x+\xi)])\) is \(\frac{1}{\sigma}\)-Lipschitz in terms of \(l_2\) distance, where \(\Phi^{-1}\) is the inverse of standard Gaussian CDF.

5.1.1  Evaluation for \(\overline{d}_{x_2}(x_1)\) and \(\underline{d}_{x_2}(x_1)\) via RS

We utilize randomized smoothing to estimate \(\overline{d}_{x_2}(x_1)\) and \(\underline{d}_{x_2}(x_1)\). Different from the original randomized smoothing, which smooths the classifier, we smooth the distance with a Gaussian distribution. Precisely, we use the following Gaussian smoothed distance \(sd_{x_2}(x_1)\) as the distance (i.e., \(d_{x_1}(x_2)\)) for computing the CBIR ranking results and estimate the upper and lower bounds of \(sd_{x_2}(x_1)\):

Definition 4. Let \(x_1, x_2 \in X\) be inputs and \(f: X \rightarrow [0,1]^d\) be a feature extractor normalized so that \(\|f(x)\|_2 = 1\). Then, Gaussian smoothed distance \(sd_{x_2}(x_1)\) is defined as follows:

\[\begin{align} sd_{x_2}(x_1):= \mathbb{E}_{\xi \sim \mathcal{N}(0, \sigma^2 I)} \frac{1}{2} \|f(x_1+\xi) - f(x_2)\|_2. \tag{23} \end{align}\]

Upper and lower bound of \(sd_{x_2}(x_1)\). Since the range of \(sd_{x_2}(x_1)\) is \([0,1]\), \(\Phi^{-1}(sd_{x_2}(x_1))\) is \(\frac{1}{\sigma}\)-Lipschitz continuity in terms of \(l_2\) distance from Theorem 5. Thus, we can immediately derive the upper and lower bounds of the Gaussian smoothed distance against AXs in \(l_2\)-ball (i.e., \(\overline{d}_{x_2}(x_1)\) and \(\underline{d}_{x_2}(x_1)\)) as follows:

\[\begin{align} & \Phi\left(\Phi^{-1}(sd_{x_2}(x_1))+\frac{\epsilon}{\sigma}\right) \geq \max_{\delta, \|\delta \|_{2} \leq \epsilon} sd_{x_2}(x_1+\delta), \tag{24} \\ & \Phi\left(\Phi^{-1}(sd_{x_2}(x_1))-\frac{\epsilon}{\sigma}\right) \leq \min_{\delta, \|\delta \|_{2} \leq \epsilon} sd_{x_2}(x_1+\delta). \tag{25} \end{align}\]

Estimation of upper and lower bound of \(sd_{x_2}(x_1)\). The upper and lower bound of \(sd_{x_2}(x_1)\) in Eqs. (24) and (25) can not be calculated directly because \(sd_{x_2}(x_1)\) is not computable in practice. Thus, we estimate Eqs. (24) and (25) with a certain probabilistic guarantee by estimating \(sd_{x_2}(x_1)\) with Monte Carlo sampling. Let \(\hat{sd}_{x_2}(x_1) = \frac{1}{N} \sum_{\xi_1, \ldots,\xi_N} \frac{1}{2} \|f(x_1+\xi_i) - f(x_2)\|_2\) be estimation of \(sd_{x_2}(x_1)\) where \(\xi_1,\ldots, \xi_N\) are sampled from \(\mathcal{N}(0, \sigma^2 I)\). Then, given query image \(q \in X\) and candidate images \(C=\{c_i | c_i \in X \}^{N}_{i=1}\), for \(\forall c \in C\), the gap between \(sd_{c}(q)\) and \(\hat{sd}_{c}(q)\) (or \(sd_{q}(c)\) and \(\hat{sd}_{q}(c)\)) can be guaranteed by utilizing Hoeffding’s inequality [37] as follows:

Lemma 3 (Theoretical Guarantee of Gap between \(sd_{x_2}(x_1)\) and \(\hat{sd}_{x_2}(x_1)\)).¹ Let \(q\in X\) and \(C=\{c_i | c_i \in X \}^{N}_{i=1}\) be a query image and a set of candidate images, respectively. Let \(\beta \in [0,1]\). For \(\forall c \in C\), the following holds with at least probability \(1-\beta\):

\[\begin{align} & \hat{sd}_{c}(q) + \sqrt{\frac{1}{2N} \log\left(\frac{2|C|}{\beta}\right)} > sd_{c}(q) \tag{26} \\ & \hat{sd}_{c}(q) - \sqrt{\frac{1}{2N} \log\left(\frac{2|C|}{\beta}\right)} < sd_{c}(q). \tag{27} \end{align}\]

Equations (26) and (27) also hold if \(\hat{sd}_{c}(q)\) and \(sd_{c}(q)\) are replaced with \(\hat{sd}_{q}(c)\) and \(sd_{q}(c)\), respectively.

Proof. The proof is shown in A.7 \(\tag*{◻}\)

Combining Eqs. (24), (25), and Lemma 3, we can estimate the upper and lower bounds of \(sd_{c}(q)\)/\(sd_{q}(c)\) for \(\forall c \in C\) with a probability of at least \(1-\beta\) as follows:

Corollary 1 (Upper and Lower Bounds of \(sd_{x_2}(x_1)\)).¹ Let \(q\in X\) and \(C=\{c_i | c_i \in X \}^{N}_{i=1}\) be a query image and a set of candidate images, respectively. Then, for \(\forall c \in C\) and \(\forall \delta \in \{\delta| \delta \in X, \|\delta\|_2 \leq \epsilon\}\), with at least probability \(1-\beta\), the followings hold:

\[\begin{align} & \Phi\left(\Phi^{-1}(\hat{sd}_{c}(q)+t)+\frac{\epsilon}{\sigma}\right) > \max_{\delta, \|\delta \|_{2} \leq \epsilon} sd_{c}(q+\delta), \tag{28} \\ & \Phi\left(\Phi^{-1}(\hat{sd}_{c}(q)-t)-\frac{\epsilon}{\sigma}\right) < \min_{\delta, \|\delta \|_{2} \leq \epsilon} sd_{c}(q+\delta), \tag{29} \end{align}\]

where \(t=\sqrt{\frac{1}{2N} \log \frac{2|C|}{\beta}}\). Equations (28) and (29) also hold if \(\hat{sd}_{c}(q)\) and \(sd_{c}(q+\delta)\) are replaced with \(\hat{sd}_{q}(c+\delta)\) and \(sd_{q}(c)\), respectively.

Proof. The proof is shown in A.8 \(\tag*{◻}\)

Equations (28) and (29) show the upper and lower bounds converge asymptotically to \(\hat{sd}_{x_2}(x_1)\) as the sample size of Gaussian noises \(N\) and the standard deviation \(\sigma\) increase.

Estimation of CBIR ranking result with \(sd_{x_2}(x_1)\). Since exact \(sd_{x_2}(x_1)\) is not computable in practice, the exact CBIR ranking results \(\mathrm{Rank}(q, c, C), \forall c \in C\) also cannot be calculated. To evaluate the sufficient conditions Eqs. (13) and (14), we estimate \(\mathrm{Rank}(q, c, C), \forall c \in C\) instead of the exact ones. Specifically, we estimate the upper and lower bounds of \(\mathrm{Rank}(q, c_i, C), \forall c \in C\) by utilizing Lemma 3. The following theorems estimate the upper and lower bounds of ranking results \(\mathrm{Rank}(q, c_i, C), \forall c \in C\) with a probability of at least \(1-\beta\) when we use \(sd_{c}(q)\) and \(sd_{q}(c)\) for computing the CBIR ranking results, respectively:

Theorem 6 (Upper and Lower Bounds of Ranking Results with \(sd_c(q)\)). Let \(q\in X\) and \(C=\{c_i | c_i \in X \}^{N}_{i=1}\) be a query image and a set of candidate images, respectively. Then, for \(\forall c_i \in C\), with at least probability \(1-\beta\), the followings hold:

\[\begin{align} & |C|- \sum_{c \in C} \text{𝟙} ( \hat{sd}_{c_i}(q) + t < \hat{sd}_{c}(q) - t) \geq \mathrm{Rank}(q, c_i, C) \tag{30} \\ & \sum_{c \in C} \text{𝟙} ( \hat{sd}_{c}(q) + t < \hat{sd}_{c_i}(q) - t) + 1 \leq \mathrm{Rank}(q, c_i, C), \tag{31} \end{align}\]

where \(t=\sqrt{\frac{1}{2N} \log \frac{2 |C|}{\beta}}\).

Proof. The proof is shown in A.9 \(\tag*{◻}\)

Theorem 7 (Upper and Lower Bounds of Ranking Result with \(sd_q(c)\)). Let \(q\in X\) and \(C=\{c_i | c_i \in X \}^{N}_{i=1}\) be a query image and a set of candidate images, respectively. Then, for \(\forall c_i \in C\), with at least probability \(1-\beta\), the followings hold:

\[\begin{align} & |C|- \sum_{c \in C} \text{𝟙} ( \hat{sd}_{q}(c_i) + t < \hat{sd}_{q}(c) - t) \geq \mathrm{Rank}(q, c_i, C) \tag{32} \\ & \sum_{c \in C} \text{𝟙} ( \hat{sd}_{q}(c) + t < \hat{sd}_{q}(c_i) - t) + 1 \leq \mathrm{Rank}(q, c_i, C), \tag{33} \end{align}\]

where \(t=\sqrt{\frac{1}{2N} \log \frac{2 |C|}{\beta}}\).

Proof. The proof is shown in A.9 \(\tag*{◻}\)

Theorems 6 and 7 show the upper and lower bounds of ranking results can be tighter as the sample size of Gaussian noises \(N\) increases.

Probabilistic evaluation of sufficient conditions. We evaluate the sufficient conditions Eqs. (13) and (14) with a probabilistic guarantee by estimating the upper and lower bounds of \(sd_{x_2}(x_1)\) and \(\mathrm{Rank}(q, c, C)\) by Corollary 1 and Theorem 6 or Theorem 7, respectively:

Theorem 8 (Probabilistic Evaluation of Sufficient Condition for (\(l_2, \alpha,\epsilon\))-Robustness against QA). At least probability \(1-\beta\), feature extractor \(f\) satisfies \((\alpha,\epsilon)\)-robust against QA at \(c_i \in C\), \(q\), and \(C\) if

\[\begin{align} & \alpha \geq \biggl(|C|- \sum_{c \in C} \text{𝟙} \biggl[ \overline{sd}_{c_i}(q) < \underline{sd}_{c}(q) \biggr]\biggr) - \underline{\mathrm{Rank}}(q, c_i, C) \tag{34} \\ & \land \ \alpha \geq \overline{\mathrm{Rank}}(q, c_i, C) - \biggl(\sum_{c \in C} \text{𝟙} \biggl[ \overline{sd}_{c}(q) < \underline{sd}_{c_i}(q) \biggr] +1 \biggr), \nonumber \end{align}\]

where \(\overline{sd}_{c}(q)=\Phi(\Phi^{-1}(\hat{sd}_{c}(q)+\sqrt{(1/2N) \log (2|C|/\beta)})+\frac{\epsilon}{\sigma})\), \(\underline{sd}_{c}(q)=\Phi(\Phi^{-1}(\hat{sd}_{c}(q)-\sqrt{(1/2N) \log (2 |C|/\beta)})-\frac{\epsilon}{\sigma})\), \(\overline{\mathrm{Rank}}(q, c, C)=|C|- \sum_{c \in C} \text{𝟙} (\hat{sd}_{c_i}(q) + t < \hat{sd}_{c}(q) - t)\), and \(\underline{\mathrm{Rank}}(q, c, C)=\sum_{c \in C} \text{𝟙} ( \hat{sd}_{c}(q) + t < \hat{sd}_{c_i}(q) - t) + 1\).

Proof. The proof is shown in A.10. \(\tag*{◻}\)

Theorem 9 (Probabilistic Evaluation of Sufficient Condition for (\(\alpha,\epsilon\))-Robustness against CA). At least probability \(1-\beta\), feature extractor \(f\) satisfies \((\alpha,\epsilon)\)-robust against QA at \(c_i \in C\), \(q\), and \(C\) if

\[\begin{align} & \alpha \geq \biggl(|C|- \sum_{c \in C} \text{𝟙} \biggl[ \overline{sd}_{q}(c_i) < \underline{sd}_{q}(c) \biggr]\biggr) - \underline{\mathrm{Rank}}(q, c_i, C) \tag{35} \\ & \land \ \alpha \geq \overline{\mathrm{Rank}}(q, c_i, C) - \biggl(\sum_{c \in C} \text{𝟙} \biggl[ \overline{sd}_{q}(c) < \underline{sd}_{q}(c_i) \biggr] +1 \biggr), \nonumber \end{align}\]

where \(\overline{sd}_{q}(c_i)=\Phi(\Phi^{-1}(\hat{sd}_{q}(c_i)+\sqrt{(1/2N) \log (2|C|/\beta)})+\frac{\epsilon}{\sigma})\), \(\underline{sd}_{q}(c_i)=\Phi(\Phi^{-1}(\hat{sd}_{q}(c_i)-\sqrt{(1/2N) \log (2 |C|/\beta)})-\frac{\epsilon}{\sigma})\), \(\overline{\mathrm{Rank}}(q, c_i, C)=|C|- \sum_{c \in C} \text{𝟙} (\hat{sd}_{q}(c_i) + t < \hat{sd}_{q}(c) - t)\), and \(\underline{\mathrm{Rank}}(q, c_i, C)=\sum_{c \in C} \text{𝟙} (\hat{sd}_{q}(c) + t < \hat{sd}_{q}(c_i) - t) + 1\).

Proof. The proof is shown in Appendix A.11. \(\tag*{◻}\)

To determine if Eq. (34) or Eq. (35) is satisfied, we can obtain our probabilistic verification algorithms for CBIR against QA and CA as follows:

\[\begin{align} \mathsf{Ver}_{\alpha, \epsilon,\beta}(q,c_i, C)= \begin{cases} \text{True} \ \ \text{if Eq.$\,$(34) or (35) is True} \\ \text{False} \ \ \text{otherwise}. \end{cases}\! \tag{36} \end{align}\]

We omit \(f\) from the augments of \(\mathsf{Ver}_{\alpha, \epsilon,\beta}(q,c_i, C)\) for notational simplicity when it is obvious from the context.

Different from the deterministic verification algorithms, Eq. (19), the results of probabilistic verification algorithms, Eq. (36), include not only false negatives but also false positives with probability at most \(\beta\). False negatives in Eq. (36) depend on hyperparameters: \(\beta\), the sample size of noises \(N\), and standard deviation \(\sigma\). The total number of forwards propagation of DNN in evaluating Eqs. (34) and (35) is equivalent to \(N + |C|\) and \(1 + N|C|\), respectively. In Sect. 6, we experimentally confirm that the probabilistic verification algorithms, Eq. (35), can verify high-resolution images (\(224 \times 224\)) when we use \(\beta=0.01\) and \(N=100000\).

5.2  Robustness Training Methods

In this subsection, we discuss the robust training method for the feature extractor \(f\), which increases the number of inputs verified by our probabilistic verification algorithm Eq. (36). Recall that tighter evaluation of the upper bound in Eq. (28) and the lower bound in Eq. (29) is needed to attain certified robustness in a meaningful way. From Eqs. (28) and (29), we can obtain a tighter evaluation of the upper and lower bounds when using a larger standard deviation \(\sigma\). However, when \(\sigma\) is large, obtaining meaningful CBIR ranking results is difficult because the estimated smoothed distances \(\hat{sd}_{c}(q)\) or \(\hat{sd}_{q}(c)\) become indistinguishable for \(\forall c \in C\). This is because the distribution difference between the training images of \(f\) and the input images with Gaussian noises becomes larger. To mitigate the distribution shift, we can utilize Gaussian data augmentation [22], [26], which adds sampled Gaussian noise \(\xi \sim N(0,\sigma^2 I)\) to the training data of feature extractor \(f\). In Sect. 6, we show that training \(f\) with Gaussian data augmentation increases the number of inputs verified by our probabilistic verification algorithms.

6.  Experiments

In this section, we evaluate our proposed deterministic and probabilistic certified defenses in terms of CBIR accuracy on clean images and robustness against QA and CA. The robustness is evaluated by empirical robustness, which is the CBIR accuracy on the generated AXs, and certified robustness, which represents how often given inputs achieve \((l_{\infty}, \alpha,\epsilon)\)-robustness and \((l_{2}, \alpha,\epsilon)\)-robustness by our proposed deterministic and probabilistic verification algorithms, respectively.

6.1  Experiments for Deterministic Certified Defenses

6.1.1  Datasets

We use the following three image datasets, MNIST [27], Fashion-MNIST (FMNIST) [28], CIFAR10 (CIFAR) [29], for evaluating our deterministic certified defense.

• MNIST is a gray-scale image dataset with 60,000 training images and 10,000 test images. The size of each image is \(28\times28\) pixels. There are 10 classes.

• Fashion-MNIST is a gray-scale image dataset with 60,000 training images and 10,000 test images. The size of each image is \(28\times28\). There are 10 classes.

• CIFAR is an RGB dataset with 50,000 training samples and 10,000 test samples. The size of each image is \(32\times32\) pixels. There are 10 classes.

We train feature extractors \(f\) on each training set and evaluate \(f\) using each test set. Let \(Q=\{(q_i,y_{q_i})\}_{i=1}^{|Q|}\) and \(C=\{(c_i,y_{c_i}) \in X\}_{i=1}^{|C|}\) be the annotated set of query and candidate images, respectively. We randomly select \(Q\) and \(C\) without duplication from the test set. We set \(|Q|=1000\) and \(|C|=1000\) for MNIST, FMNIST, and CIFAR. Pixel values of images in all datasets are in \([0, 1]\).

6.1.2  Evaluation Measures

Performance of CBIR. To evaluate the performance of CBIR, we use Recall@K, which is one of the evaluation measures for CBIR [38], [39]. Recall@K evaluates whether how often any of the top K candidates is similar to the query image. For evaluation purpose, images belonging to the same class are regarded as similar images. Then, Recall@K is defined as follos:

\[\begin{align} \frac{1}{|Q|} \sum_{(q_i,y_{q_i}) \in Q} \begin{cases} 1 \ \ \text{if $\exists (c,y_c) \in C$ s.t.}\\ \hphantom{1}\ \ \mathrm{Rank} (q_i, c, C) \leq K \land y_c=y_{q_i}\\ 0 \ \ \text{otherwise}. \end{cases} \tag{37} \end{align}\]

Empirical Robustness. To evaluate the empirical robustness against QA and CA, we extend recall@K and define empirical robust Recall@K (ER-Recall@K) against QA and CA. ER-Recall@K against QA represents how often any of the top K candidates is similar to the query image under QA:

\[\begin{align} \frac{1}{|Q|} \sum_{(q_i,y_{q_i}) \in Q} \begin{cases} 1 \ \ \text{if $\exists (c,y_c) \in C$ s.t.}\\ \hphantom{1} \ \ \mathrm{Rank} (q_i+\delta_i, c, C) \leq K \land y_c=y_{q_i}\\ 0 \ \ \text{otherwise} \end{cases}\kern-3.5pt \tag{38} \end{align}\]

where \(\delta_1, \ldots, \delta_{|Q|}\) are adversarial perturbations generated with Eq. (2). We randomly select a single target candidate image \(C_t = \{(c_t, y_{c_t})\} \subset C\) such that \(y_{c_t} \neq y_{q_i}\) for each \((q_i,y_{q_i}) \in Q\). We minimize Eq. (2) by using PGD [12] with the step size of \(\frac{\epsilon}{10}\) and the number of updates of 100, where \(\epsilon \in \{0.1,0.2\}\) for MNIST and FMNIST and \(\epsilon \in \{\frac{2}{255}, \frac{3}{255}\}\) for CIFAR10, respectively.

ER-Recall@K against CA represents how often any of the top K candidates is similar image to the query image under CA:

\[\begin{align} \frac{1}{|Q|} \sum_{(q_i,y_{q_i}) \in Q} \begin{cases} 1 \ \ \text{if $\exists (c,y_c) \in \tilde{C}$ s.t.}\\ \hphantom{1} \ \ \mathrm{Rank} (q_i, c, \tilde{C}) \leq K \land \ y_c=y_{q_i}\\ 0 \ \ \text{otherwise}, \end{cases} \tag{39} \end{align}\]

where \(\tilde{C} = C \setminus C_s \cup \tilde{C_s}\) and \(C_s \subset C\) is a set of source candidate images, and \(\tilde{C_s}=\{(c_i+\delta_i, y_{c_i})| (c_i, y_{c_i})\) \(\in C_s\}_{i=1}^{|C_s|}\) is the set of images obtained by adding adversarial perturbation \(\delta_1, \ldots, \delta_{|C_s|}\) to each image in \(C_s\) with Eq. (4). We randomly select 100 source candidate images \(C_s = \{(c_i, y_{c_i})\}_{i=1}^{100}\) such that \(y_{c_i} \neq y_{q_i}\) for each \((q_i,y_{q_i}) \in Q\). We minimize Eq. (4) using PGD with the same step and perturbation size as the QA.

Certified Robustness. To evaluate the certified robustness, we define an extension of recall@K, certified robust Recall@K (CR-Recall@K). Given a set of query images, this measure evaluates how often (i) the retrieved candidate image by the query image has certified robustness against QA or CA, and (ii) are similar to the query image:

\[\begin{align} \frac{1}{|Q|} \sum_{(q,y_q) \in Q} \begin{cases} 1 \ \ \text{if $\exists (c,y_c) \in C$ s.t. $ y_c=y_q \land{}$} \\ \hphantom{1} \ \ \mathrm{Rank}(q_i, c, C) \leq K \land \mathsf{Ver}_{\alpha, \epsilon}(q, c, C)\\ 0 \ \ \text{otherwise}, \\ \end{cases} \tag{40} \end{align}\]

where \(\mathsf{Ver}_{\alpha, \epsilon}(q, c, C)\) is deterministic verification algorithms defined by Eq. (19). We use \(\alpha=K-\mathrm{Rank}(q,c,C)\) for each \(c \in C\). Then, \(\mathsf{Ver}_{\alpha, \epsilon}(q, c, C)\) verifies whether \(c\) still satisfies \(\mathrm{Rank}(q_i, c, C) \leq K\) under QA and CA.

6.1.3  Comparison Methods

We compare our proposed robustness training Eq. (20) (TBT) and Eq. (21) (FCTB) with three existing methods: (i) triplet Loss (Triplet) [35], (ii) anti-collapse triplet (ACT), which is an adversarial training for CBIR to improve empirical robustness [3], (iii) robust training for classification using interval bound propagation (C-IBP) to improve certified robustness of classification task [20].

We use Triplet as a baseline which does not have any mechanism for robustness. We compare TBT and FCTB with ACT to show that adversarial training is not sufficient to improve certified robustness of CBIR. We also compare TBT and FCTB with C-IBP to show that robust training for improving certified robustness for the classification task is inadequate to improve certified robustness for CBIR. Detail of each method are explained in Appendix B.

6.1.4  Implementations of Feature Extractors

Architectures. In our experiments for probabilistic certified defense, we train the feature extractor \(f\) of embedding dimensionality 128 in the following 6-layer CNN model architecture as \(\mathrm{Conv}(64,3,1,1) \rightarrow \mathrm{Conv}(64,3,1,1) \rightarrow \mathrm{Conv}(128,3,2,1) \rightarrow \mathrm{Conv}(128,3,1,1) \rightarrow \mathrm{Conv}(128,3,1,1) \rightarrow \mathrm{Linear}(128)\) where \(\mathrm{Conv}(c,k,s,p)\) denotes a convolutional layer with a number of filters \(c\) of size \(k \times k\), stride size is \(s\), and padding size is \(p\) and \(\mathrm{Linear}(d)\) denotes a linear layer whose output dimension is \(d\). Note that there is a ReLU between each layer.

Hyperparameters. The total number of training epochs of \(f\) is \(100\) for MNIST and FMNIST and \(200\) for CIFAR10. We use the Adam optimizer [40] with a batch size of \(100\) and an initial learning rate of \(0.001\). We decay the learning rate by times \(0.1\) at \(25\) and \(42\) epochs for MNIST and FMNIST and times \(0.5\) every \(10\) epochs between \(130\) and \(200\) epochs for CIFAR10. The margin of triplet loss is set to \(m=1.0\). When training with TBT, to stabilize training, we use the scheduling strategy for \(\epsilon\) and \(\kappa\) proposed in [20]. Specifically, \(\epsilon\) is gradually increased from \(0.0\) to \(\epsilon_{e}\), and the \(\kappa\) is gradually decreased from \(1.0\) to \(\kappa_{e}\). We use \(\epsilon_{e}=0.2\) for MNIST and FMNIST, and \(\epsilon_{e}= \frac{2}{255}\) for CIFAR10, respectively. We use \(\kappa_{e}=0.5\) for all datasets. Then, we linearly increase \(\epsilon\) and decrease \(\kappa\) between \(2K\) and \(10K\) steps. When training with FCTB, we fine-tune the pre-trained feature extractor with TBT. We set fixed \(\epsilon\) to \(0.2\) for MNIST and FMNIST and \(\frac{2}{255}\) for CIFAR10. We set fixed \(\kappa\) to \(0.2\) for MNIST and \(0.1\) for FMNIST and CIFAR10. Other hyperparameters are shown in Appendix B.1.

6.2  Results for Deterministic Certified Defenses

Tables 1 and 2 show the results for deterministic certified defense proposed in Sect. 4. We can see that our proposed robust training TBT has less Recall@K than Triplet, ACT, and C-IBP from Table 1. This is presumably due to the fact that the diversity of feature representation is reduced by making the upper and lower bound evaluated tighter. However, the gap in Recall@K between TBT and the existing methods becomes smaller as K increases. Thus, that is not a practical problem in situations where K is large.

Table 1  Comparison of Recall@K for deterministic certifed defense. Each value is rounded off to two decimal places.

Table 2  Comparison of empirical robust (ER) Recall@K and certified robust (CR) Recall@K for deterministic certified defense. QA and CA represent query and candidate attack, respectively. Each value is rounded off to two decimal places.

We can also confirm both ER-Recall@K and CR-Recall@K of Triplet are significantly lower than the other methods from Table 2. C-IBP and ACT achieve higher ER-Recall@K than Triplet, while their CR-Recall@K is zero or nearly zero, even with larger \(K\). This implies that C-IBP and ACT cannot help to provide certified robustness of CBIR. This is because ACT is training to improve empirical robustness, which is no enough to improve certified robustness. We also conjecture that C-IBP is not sufficient to tighten Eqs. (17) and (18) since it aims at tightening the upper and lower bounds of logits. In contrast, TBT achieves significantly higher CR-recall@K, particularly when \(K\) is large. This is because TBT can tighten Eqs. (17) and (18) successfully.

We can also confirm that fine-tuning pre-trained feature extractor with TBT to candidate images (FCTB) improve CR-Recall@K while maintaining Recall@K from Tables 1 and 2. This implies that FCTB can further reduce the gap between Definition 3 and the corresponding sufficient condition.

Limitations of deterministic certified defense. A drawback of our deterministic verification algorithms are that it does not scale to high-resolution images, which require advanced architecture. We train feature extractor with TBT using CUB and VGG architecture [41]. As a result, its training collapses, which means that the trained feature extractor returns the same value for all test inputs. This is because IBP provides very loose bounds for advanced deep architectures, resulting in extremely large regularization terms in Eq. (20).

6.3  Experiments for Probabilistic Certified Defenses

6.3.1  Experimental Settings

Datasets. We use the following three image datasets, CUB-200-2011 (CUB) [30], CARS196 (CAR) [42], and Stanford Online Products (SOP) [43], for evaluating our probabilistic certified defense.

• CUB is an RGB dataset with 11,788 images labeled with one of 200 classes. We split this dataset into training and test images for the first and last 100 classes.

• CAR is an RGB dataset with 16,185 images labeled with one of 196 classes. We split this dataset into training and test images for the first and last 98 classes.

• SOP is an RGB dataset with 11,318 classes 59,551 training images and 11,316 classes 60,501 test images.

We crop and resize the images in these datasets to \(224 \times 224\), which is a higher resolution than MNIST, FMNIST, and CIFAR10. We train feature extractors \(f\) on each training set and evaluate \(f\) using each test set. Let \(Q=\{(q_i,y_{q_i})\}_{i=1}^{|Q|}\) and \(C=\{(c_i,y_{c_i}) \in X\}_{i=1}^{|C|}\) be the annotated set of query and candidate images, respectively. We randomly select Q and C without duplication from the test set. We set \(|Q|=100\) and \(|C|=1000\) for CUB, CAR, and SOP. Pixel values of images in all datasets are in \([0, 1]\).

6.3.2  Evaluation Measures

Performance of CBIR. To evaluate the performance of CBIR, we use the lower bound of Recall@K Eq. (37). Since the exact \(\mathrm{Rank}(q, c, C)\) is not computationally tractable when using Gaussian smoothed distance Eq. (23), we cannot also evaluate exact Recall@K. Thus, we evaluate the lower bound of Recall@K by estimating the upper bound of \(\mathrm{Rank}(q, c, C)\) by Theorem 6 or Theorem 7:

\[\begin{align} \frac{1}{|Q|} \sum_{(q_i,y_{q_i}) \in Q} \begin{cases} 1 \ \ \text{if $\exists (c,y_c) \in C$ s.t.}\\ \hphantom{1}\ \ \overline{\mathrm{Rank}} (q, c, C) \leq K \land y_c=y_{q_i}\\ 0 \ \ \text{otherwise}, \end{cases}\kern-1em\tag{41} \end{align}\]

where \(\overline{\mathrm{Rank}}(q, c, C)\) is the upper bound of \(\mathrm{Rank}(q, c, C)\) evaluated by Eq. (30) or Eq. (32).

Certified Robustness. To evaluate the certified robustness, we use the lower bound of CR-Recall@K Eq. (40). As well as the evaluation of the lower bound of Recall@K Eq. (41), we use the upper bound of \(\mathrm{Rank}(q, c, C)\) to calculate the lower bound of CR-Recall@K as follows:

\[\begin{align} \frac{1}{|Q|} \sum_{(q,y_q) \in Q} \begin{cases} 1 \ \ \text{if $\exists (c,y_c) \in C$ s.t.$\ y_c=y_q \land{}$} \\ \hphantom{1}\ \ \overline{\mathrm{Rank}} (q, c, C) \leq K \land \mathsf{Ver}_{\alpha, \epsilon,\beta}(q,c, C)\\ 0 \ \ \text{otherwise}, \end{cases}\kern-5pt \tag{42} \end{align}\]

where \(\mathsf{Ver}_{\alpha, \epsilon,\beta}(q,c, C)\) is probabilistic verification algorithms defined by Eq. (36). We use \(\alpha=K-\mathrm{Rank}(q,c,C)\) for each \(c \in C\). Then, \(\mathsf{Ver}_{\alpha, \epsilon,\beta}(q,c, C)\) verifies whether \(c\) still satisfies \(\mathrm{Rank}_{f} (q_i, c, C) \leq K\) under QA and CA. We set the false positive rate \(\beta\) to \(0.01\) for all experiments of probabilistic certified defenses.

6.4  Implementations of Feature Extractors

Architectures. We use ResNet50 [44] as model architecture of \(f\). We use the parameters pre-trained on ImageNet [33] obtained from torchvision library in PyTorch [45] as initial parameters. We set the feature dimension is \(d=128\). We use the codes² provided by [46] for training \(f\).

Hyperparameters. We use Triplet loss with margin \(m=0.2\) as the loss function. The total number of training epochs is 150. We use the Adam optimizer [40] with a batch size of \(112\), an initial learning rate of 0.00001, and a weight decay of 0.0004. We decay the learning rate by times 0.3 at 1000 iterations. When using Gaussian data augmentation, we sample noise from \(N(0, \sigma^2 I)\) where \(\sigma \in \{0.1,1.0\}\) at each parameter update and added to the training data. Then, We use the same \(\sigma\) during training and testing.

6.5  Results for Probabilistic Certified Defenses

Table 3 shows the results of the lower bounds of Recall@K and CR-Recall@K for probabilistic certified defense proposed in Sect. 5. All results in Table 3 use \(N=100000\). Triplet and GA-Triplet represent the results of models trained with Triplet Loss and Triplet Loss with Gaussian data augmentation, respectively. Note that the results for \(\sigma=0.0\) are a baseline that represents Recall@K when using general Euclidean distance for calculating ranking results. From Table 3, we can see that GA-Triplet has higher lower bounds of Recall@K and CR-Recall@K than Triplet. These are due to the fact that Gaussian data augmentation successfully mitigates the distribution shift between the training and test data of feature extractor \(f\), allowing \(f\) to compute a meaningfully distinguishable estimated smoothed distance \(\hat{sd}_{c}(q)\) or \(\hat{sd}_{q}(c)\) for \(\forall c \in C\). GA-Triplet has less Recall@K than the baseline, but the gap gets smaller as K increases. Thus, that is not a practical problem when \(K\) is large.

Table 3  Comparison of the lower bounds of Recall@K and certified robust (CR) Recall@K for probabilistic certified defense. All results use \(N=100000\) and \(\beta=0.01\). Note that the results for \(\sigma=0.0\) are a baseline that represents Recall@K when using general Euclidean distance for calculating ranking results. QA and CA represent query and candidate attack, respectively.

The effect of standard deviation \(\sigma\). Table 4 shows the results of the lower bounds of Recall@K and CR-Recall@K for GA-Triplet with different standard deviation \(\sigma\). All results in Table 3 use \(N=100000\). We can see that \(\sigma\) controls the trade-off between Recall@K and CR-Recall@K. This is because as \(\sigma\) increases, the upper and lower bounds of the smooth distance in Eqs. (28) and (29) become smaller, but it becomes more difficult to compute a meaningfully distinguishable estimated smoothed distance \(\hat{sd}_{c}(q)\) or \(\hat{sd}_{q}(c)\) for \(\forall c \in C\).

Table 4  Comparison of the lower bounds of Recall@K and certified robust (CR) Recall@K for probabilistic certified defense with different standard deviation \(\sigma\). All results use \(N=100000\) and \(\beta=0.01\). QA and CA represent query and candidate attack, respectively.

The effect of sample sizes of Gaussian noises \(N\). Table 5 shows the results of the lower bounds of Recall@K and CR-Recall@K for GA-Triplet with different sample sizes of Gaussian noises \(N\). All results in Table 5 use \(\sigma=1.0\). We can see that Recall@K and CR-Recall@K improve as \(N\) increases. This is because the upper and lower bounds of Gaussian smoothed distances and ranking results can be tight as the sample size of Gaussian noises \(N\), as explained in Sect. 5. However, the computational complexity increases as \(N\) increases.

Table 5  Comparison of the lower bounds of Recall@K and certified robust (CR) Recall@K for probabilistic certified defense with different sample sizes of Gaussian noises \(N\). All results use \(\sigma=1.0\) and \(\beta=0.01\). QA and CA represent query and candidate attack, respectively.

Limitations of probabilistic certified defense. A drawback of our probabilistic verification algorithm is its high computational cost. As denoted in Sect. 5, in the probabilistic verification algorithms, the total number of forward propagation of DNN in evaluating Eqs. (34) and (35) is equivalent to \(N + |C|\) and \(1 + N|C|\), respectively. For example, we require a total of 101000 and 100000001 forwards to evaluate Eqs. (34) and (35) when \(N=100000\) and \(|C|=1000\).

7.  Future Directions

In this section, we present potential directions for future research focusing on enhancing the certified defense for CBIR. Specifically, we delve into possibilities for improving robust training, reducing the computational complexity of the verification algorithms, and implementing our certified defenses in real-world CBIR systems.

The primary direction is further investigation into more effective robust training of feature extractors, with the aim of enhancing the certified robustness of CBIR. One potential method that could be considered is utilizing adversarial training, which trains DNNs using AXs as training data. [24] has demonstrated that adversarial training can enhance not only empirical robustness but also certified robustness in the classification setting. It is reasonable to explore the application of adversarial training to the training of feature extractors for CBIR, with the expectation of boosting its certified robustness.

Another important direction is to reduce the computational complexity of the verification algorithms used to evaluate the certified robustness of CBIR. As described in Sect. 5, our probabilistic verification algorithms scale to high-resolution images but bear a high computational cost, especially when the number of candidate images \(|C|\) is large. This may limit the practical application of our method in real-world scenarios. One potential solution to mitigate this limitation is to utilize an additional distribution in randomized smoothing. [47] has shown that using an additional distribution can yield higher certified robustness of classification, even with a smaller sampling size (i.e., fewer classification model forwards). Applying this theory and computational methodology to the verification algorithms for CBIR may not be straightforward, but it certainly holds promising potential.

A third vital direction is to assess the effectiveness of our proposed certified defenses in real-world CBIR systems, such as person re-identification, medical image retrieval, and image-based product search. The application of our proposed method to these systems could provide the theoretically guaranteed verification results on ranking invariance against AXs associated with retrieved images, thereby potentially improving the security of these systems. Nonetheless, it’s important to note that in real-world CBIR systems, a domain gap between the training and evaluation data often becomes larger due to the frequent addition of new images to the candidate images (e.g., the addition of new products in image-based product search). The impact of such domain gap on the performance of our proposed certified defenses remains largely unexplored and thus is need for further assessment. A detailed investigation into this matter may reveal unique challenges and solutions for deploying certified defenses in real-world CBIR systems.

8.  Conclusion

In this study, we proposed deterministic and probabilistic certified defenses for CBIR. Our certified defenses provide certified robustness, which deterministically and probabilistically guarantees that no AX that largely changes the ranking of CBIR exists around the query or candidate images. We theoretically and experimentally confirmed that our deterministic certified defenses are lightweight but do not scale to high-resolution images; on the other hand, the probabilistic one is computationally expensive but scales to high-resolution images. Developing a certified defense that is lightweight and scales to high-resolution images is a future work.

Acknowledgments

This work is partly supported by Japan science and technology agency (JST), CREST JPMJCR23M4, and Japan society for the promotion of science (JSPS), Grantr-in-aid 23H00483.

References

[1] S.R. Dubey, “A decade survey of content based image retrieval using deep learning,” IEEE Trans. Circuits Syst. Video Technol., vol.32, no.5, pp.2687-2704, 2021.

[2] M. Zhou, Z. Niu, L. Wang, Q. Zhang, and G. Hua, “Adversarial ranking attack and defense,” Computer Vision―ECCV 2020: 16th European Conference, Glasgow, UK, Aug. 23-28, 2020, Proceedings, Part XIV 16, pp.781-799, Springer, 2020.

[3] M. Zhou, L. Wang, Z. Niu, Q. Zhang, N. Zheng, and G. Hua, “Adversarial attack and defense in deep ranking,” arXiv preprint arXiv:2106.03614, 2021.

[4] J. Li, R. Ji, H. Liu, X. Hong, Y. Gao, and Q. Tian, “Universal perturbation attack against image retrieval,” Proc. IEEE/CVF International Conference on Computer Vision, pp.4898-4907, 2019.

[5] G. Tolias, F. Radenovic, and O. Chum, “Targeted mismatch adversarial attack: Query with a flower to retrieve the tower,” Proc. IEEE/CVF International Conference on Computer Vision, pp.5036-5045, 2019.

[6] H. Wang, G. Wang, Y. Li, D. Zhang, and L. Lin, “Transferable, controllable, and inconspicuous adversarial attacks on person re-identification with deep mis-ranking,” Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.339-348, 2020.

[7] M. Zhou, L. Wang, Z. Niu, Q. Zhang, Y. Xu, N. Zheng, and G. Hua, “Practical relative order attack in deep ranking,” Proc. IEEE/CVF International Conference on Computer Vision, pp.16393-16402, 2021.

[8] X. Li, J. Li, Y. Chen, S. Ye, Y. He, S. Wang, H. Su, and H. Xue, “QAIR: Practical query-efficient black-box attacks for image retrieval,” Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.3329-3338, 2021.

[9] Z. Wang, S. Zheng, M. Song, Q. Wang, A. Rahimpour, and H. Qi, “advPattern: Physical-world attacks on deep person re-identification via adversarially transformable patterns,” Proc. IEEE/CVF International Conference on Computer Vision, pp.8340-8349, 2019.

[10] S. Bai, Y. Li, Y. Zhou, Q. Li, and P.H.S. Torr, “Adversarial metric attack and defense for person re-identification,” IEEE Trans. Pattern Anal. Mach. Intell., vol.43, no.6, pp.2119-2126, 2020.

[11] M. Ye, J. Shen, G. Lin, T. Xiang, L. Shao, and S.C.H. Hoi, “Deep learning for person re-identification: A survey and outlook,” IEEE Trans. Pattern Anal. Machine Intell., vol.44, no.6, pp.2872-2893, 2021.

[12] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu, “Towards deep learning models resistant to adversarial attacks,” International Conference on Learning Representations, 2018.

[13] F. Tramer, N. Carlini, W. Brendel, and A. Madry, “On adaptive attacks to adversarial example defenses,” Advances in Neural Information Processing Systems, vol.33, pp.1633-1645, 2020.

[14] L. Li, X. Qi, T. Xie, and B. Li, “SoK: Certified robustness for deep neural networks,” arXiv preprint arXiv:2009.04131, 2020.

[15] G. Katz, C. Barrett, D.L. Dill, K. Julian, and M.J. Kochenderfer, “Reluplex: An efficient SMT solver for verifying deep neural networks,” International Conference on Computer Aided Verification, pp.97-117, Springer, 2017.

[16] L. Weng, H. Zhang, H. Chen, Z. Song, C.J. Hsieh, L. Daniel, D. Boning, and I. Dhillon, “Towards fast computation of certified robustness for ReLU networks,” International Conference on Machine Learning, pp.5276-5285, PMLR, 2018.

[17] H. Zhang, T.W. Weng, P.Y. Chen, C.J. Hsieh, and L. Daniel, “Efficient neural network robustness certification with general activation functions,” Advances in Neural Information Processing Systems, vol.31, 2018.

[18] G. Singh, T. Gehr, M. Püschel, and M. Vechev, “An abstract domain for certifying neural networks,” Proc. ACM on Programming Languages, vol.3, no.POPL, Article No.41, pp.1-30, 2019.

[19] Y. Tsuzuku, I. Sato, and M. Sugiyama, “Lipschitz-margin training: Scalable certification of perturbation invariance for deep neural networks,” Advances in Neural Information Processing Systems, vol.31, 2018.

[20] S. Gowal, K. Dvijotham, R. Stanforth, R. Bunel, C. Qin, J. Uesato, R. Arandjelovic, T. Mann, and P. Kohli, “On the effectiveness of interval bound propagation for training verifiably robust models,” arXiv preprint arXiv:1810.12715, 2018.

[21] S. Gowal, K. Dvijotham, R. Stanforth, R. Bunel, C. Qin, J. Uesato, R. Arandjelovic, T.A. Mann, and P. Kohli, “Scalable verified training for provably robust image classification,” Proc. IEEE/CVF International Conference on Computer Vision, pp.4841-4850, 2019.

[22] J. Cohen, E. Rosenfeld, and Z. Kolter, “Certified adversarial robustness via randomized smoothing,” International Conference on Machine Learning, pp.1310-1320, PMLR, 2019.

[23] K. Leino, Z. Wang, and M. Fredrikson, “Globally-robust neural networks,” International Conference on Machine Learning, pp.6212-6222, PMLR, 2021.

[24] H. Salman, J. Li, I. Razenshteyn, P. Zhang, H. Zhang, S. Bubeck, and G. Yang, “Provably robust deep learning via adversarially trained smoothed classifiers,” Advances in Neural Information Processing Systems, vol.32, 2019.

[25] M. Lecuyer, V. Atlidakis, R. Geambasu, D. Hsu, and S. Jana, “Certified robustness to adversarial examples with differential privacy,” 2019 IEEE Symposium on Security and Privacy (SP), pp.656-672, IEEE, 2019.

[26] Y. Wu, H. Zhang, and H. Huang, “Retrievalguard: Provably robust 1-nearest neighbor image retrieval,” International Conference on Machine Learning, pp.24266-24279, PMLR, 2022.

[27] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” Proc. IEEE, vol.86, no.11, pp.2278-2324, 1998.

[28] H. Xiao, K. Rasul, and R. Vollgraf, “Fashion-MNIST: A novel image dataset for benchmarking machine learning algorithms,” arXiv preprint arXiv:1708.07747, 2017.

[29] A. Krizhevsky, G. Hinton, et al., “Learning multiple layers of features from tiny images,” Technical report, 2009.

[30] C. Wah, S. Branson, P. Welinder, P. Perona, and S. Belongie, “The caltech-UCSD birds-200-2011 dataset,” California Institute of Technology, 2011.

[31] K. Kakizaki, K. Fukuchi, and J. Sakuma, “Certified defense for content based image retrieval,” Proc. IEEE/CVF Winter Conference on Applications of Computer Vision (WACV), pp.4550-4559, Jan. 2023.

[32] I.J. Goodfellow, J. Shlens, and C. Szegedy, “Explaining and harnessing adversarial examples,” arXiv preprint arXiv:1412.6572, 2014.

[33] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “ImageNet: A large-scale hierarchical image database,” 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp.248-255, IEEE, 2009.

[34] H. Zhang, H. Chen, C. Xiao, S. Gowal, R. Stanforth, B. Li, D. Boning, and C.J. Hsieh, “Towards stable and efficient training of verifiably robust neural networks,” International Conference on Learning Representations, 2019.

[35] F. Schroff, D. Kalenichenko, and J. Philbin, “FaceNet: A unified embedding for face recognition and clustering,” Proc. IEEE Conference on Computer Vision and Pattern Recognition, pp.815-823, 2015.

[36] A. Levine, S. Singla, and S. Feizi, “Certifiably robust interpretation in deep learning,” arXiv preprint arXiv:1905.12105, 2019.

[37] W. Hoeffding, “Probability inequalities for sums of bounded random variables,” Journal of the American Statistical Association, vol.58, no.301, pp.13-30, 1963.

[38] E. Ramzi, N. Thome, C. Rambour, N. Audebert, and X. Bitot, “Robust and decomposable average precision for image retrieval,” Advances in Neural Information Processing Systems, vol.34, 2021.

[39] J. Wang, F. Zhou, S. Wen, X. Liu, and Y. Lin, “Deep metric learning with angular loss,” Proc. IEEE International Conference on Computer Vision, pp.2612-2620, 2017.

[40] D.P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” arXiv preprint arXiv:1412.6980, 2014.

[41] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” arXiv preprint arXiv:1409.1556, 2014.

[42] J. Krause, M. Stark, J. Deng, and L. Fei-Fei, “3D object representations for fine-grained categorization,” 2013 IEEE International Conference on Computer Vision Workshops, Sydney, Australia, pp.554-561, 2013.

[43] H.O. Song, Y. Xiang, S. Jegelka, and S. Savarese, “Deep metric learning via lifted structured feature embedding,” Proc. IEEE Conference on Computer Vision and Pattern Recognition, pp.4004-4012, 2016.

[44] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” Proc. IEEE Conference on Computer Vision and Pattern Recognition, pp.770-778, 2016.

[45] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala, “PyTorch: An imperative style, high-performance deep learning library,” Advances in Neural Information Processing Systems, vol.32, 2019.

[46] K. Roth, T. Milbich, S. Sinha, P. Gupta, B. Ommer, and J.P. Cohen, “Revisiting training strategies and generalization performance in deep metric learning,” International Conference on Machine Learning, pp.8242-8252, PMLR, 2020.

[47] L. Li, J. Zhang, T. Xie, and B. Li, “Double sampling randomized smoothing,” International Conference on Machine Learning, pp.13163-13208, PMLR, 2022.

Appendix A: Proofs of Theorems

A.1 Proof of Lemma 1

Proof. From definitions of Eqs. (7) and (8), for \(\forall \delta \in \{\delta \ | \ \delta \in X, \|\delta \|_{p} \leq \epsilon \}\), the following holds:

\[\begin{align} \sum_{c \in C} \text{𝟙} \bigl[ d(f(q+\delta),f(c_i)) < d(f(q+\delta),f(c)) \bigr]\nonumber\\ \geq \sum_{c \in C} \text{𝟙} \bigl[ \overline{d}_{c_i}(q) < \underline{d}_c(q) \bigr], \tag{A$\cdot $1} \\ \sum_{c \in C} \text{𝟙} \bigl[ d(f(q+\delta),f(c)) < d(f(q+\delta),f(c_i)) \bigr]\nonumber\\ \geq \sum_{c \in C} \text{𝟙} \bigl[ \overline{d}_c(q) < \underline{d}_{c_i}(q) \bigr]. \tag{A$\cdot $2} \end{align}\]

Equations (A\(\cdot\) 1) and (A\(\cdot\) 2) represent the lower bounds of the number of candidate images that are more dissimilar and similar to \(q+\delta\) than \(c_i\), respectively. Thus, we get the claim. \(\tag*{◻}\)

A.2 Proof of Lemma 2

Proof. From Eqs. (7) and (8), for \(\tilde{C}=\{c_i + \delta_i\}_{i=1}^{N}\) where \(\forall \delta_1, \ldots, \delta_N \in \{\delta \ | \ \delta \in X, \|\delta \|_{p} \leq \epsilon \}\), the following holds:

\[\begin{align} \sum_{c+\delta \in \tilde{C}} \text{𝟙} \bigl[ d(f(q),f(c_i+\delta_i)) < d(f(q ),f(c+\delta)) \bigr]\nonumber\\ \geq \sum_{c \in C} \text{𝟙} \bigl[ \overline{d}_q(c_i) < \underline{d}_q(c) \bigr], \tag{A$\cdot $3} \\ \sum_{c+\delta \in\hat{C}} \text{𝟙} \bigl[ d(f(q), f(c+\delta)) < d(f(q),f(c_i+\delta_i)) \bigr]\nonumber\\ \geq \sum_{c \in C} \text{𝟙} \bigl[ \overline{d}_q(c) < \underline{d}_q(c_i) \bigr]. \tag{A$\cdot $4} \end{align}\]

Equations (A\(\cdot\) 3) and (A\(\cdot\) 4) represent the lower bounds of the number of perturbed candidate images in \(\tilde{C}\) that are more dissimilar and similar to \(q\) than \(c_i+\delta_i\), respectively. Thus, we get the claim. \(\tag*{◻}\)

A.3 Proof of Theorem 1

Proof. When Eq. (13) is satisfied, from Theorem 1,

\[\begin{aligned} \nonumber -\alpha \leq \mathrm{Rank}(q+\delta,c_i, C)- \mathrm{Rank}(q, c_i, C) \leq \alpha \end{aligned}\]

holds for \(\forall \delta \in \{\delta \ | \ \delta \in X, \|\delta \|_{p} \leq \epsilon \}\), which is equivalent to Eq. (5). \(\tag*{◻}\)

A.4 Proof of Theorem 2

Proof. When Eq. (14) is satisfied, from Theorem 2,

\[\begin{aligned} \nonumber -\alpha \leq \mathrm{Rank}(q, c_i + \delta_i,\tilde{C})- \mathrm{Rank}(q, c_i, C) \leq \alpha \end{aligned}\]

holds for \(\tilde{C}=\{\mathrm{IR}_f(q, C)_i + \delta_i\}_{i=1}^{N}\) where \(\forall \delta_1, \ldots, \delta_N \in \{\delta \ | \ \delta \in X, \|\delta \|_{p} \leq \epsilon \}\), which is equivalent to Eq. (6). \(\tag*{◻}\)

A.5 Proof of Theorem 3

Proof. Since \(\underline{f}(x_1)_{i} \leq f(x_1+\delta)_i \leq \overline{f}(x_1)_{i}\) holds for \(\forall \delta \in \{\delta \ | \ \delta \in X, \|\delta \|_{\infty} \leq \epsilon \}\) from the definitions of \(\underline{f}(x)_{i}\) and \(\overline{f}(x)_{i}\), \(\max_{\delta \in X, \|\delta \|_{\infty} \leq \epsilon}(f(x_1+\delta)_i - f(x_2)_i)^2 \leq \max\bigl \{ |\overline{f}(x_1)_{i}-f(x_2)_{i}|, |f(x_2)_{i}-\underline{f}(x_1)_{i}| \bigr \}^2\) holds. Then, we obtain

\[\begin{align} & \nonumber \max_{\delta \in X, \|\delta \|_{\infty} \leq \epsilon} \biggl(\sum_{i \in \{1, \ldots, d\}} \bigl(f(x_1+\delta)_i-f(x_2)_i \bigr)^2 \biggr)^{\frac{1}{2}} \\ &\leq \biggl( \sum_{i \in \{1, \ldots, d\}} \max \{ |\overline{f}(x_1)_{i}-f(x_2)_{i}|, |f(x_2)_{i}-\underline{f}(x_1)_{i}| \}^2 \biggr)^{\frac{1}{2}}. \tag{A$\cdot $5} \end{align}\]

\(\tag*{◻}\)

A.6 Proof of Theorem 4

Proof. Since \(\underline{f}(x_1)_{i} \leq f(x_1+\delta)_i \leq \overline{f}(x_1)_{i}\) holds for \(\forall \delta \in \{\delta \ | \ \delta \in X, \|\delta \|_{\infty} \leq \epsilon \}\) from the definitions of \(\underline{f}(x)_{i}\) and \(\overline{f}(x)_{i}\), \(\min_{\delta \in X, \|\delta \|_{\infty} \leq \epsilon}(f(x_1+\delta)_i - f(x_2)_i)^2 \geq \min\bigl \{ 0, \overline{f}(x_1)_{i}-f(x_2)_{i}, f(x_2)_{i}-\underline{f}(x_1)_{i} \bigr \}^2\) holds. Then, we obtain

\[\begin{align} &\nonumber \min_{\delta \in X, \|\delta \|_{\infty} \leq \epsilon} \biggl(\sum_{i \in \{1, \ldots, d\}} \bigl(f(x_1+\delta)_i-f(x_2)_i \bigr)^2 \biggr)^{\frac{1}{2}}\\ & \geq \biggl( \sum_{i \in \{1, \ldots, d\}} \min\bigl \{ 0, \overline{f}(x_1)_{i}-f(x_2)_{i}, f(x_2)_{i}-\underline{f}(x_1)_{i} \bigr \}^2 \biggr)^{\frac{1}{2}}. \tag{A$\cdot $6} \end{align}\]

\(\tag*{◻}\)

A.7 Proof of Lemma 3

Proof. Since \(0 \leq sd_{x_2}(x_1) \leq 1\) for \(\forall x_1, x_2 \in X\) from definition of smoothed distance Eq. (23), the following holds for any \(t>0\) by Hoeffding’s Inequality:

\[\begin{align} \mathbb{P}[|sd_{x_2}(x_1) - \hat{sd}_{x_2}(x_1)| \geq t] \leq 2 \exp (-2N t^2). \tag{A$\cdot $7} \end{align}\]

Then, for \(q \in X\) and \(C=\{c_i | c_i \in X\}^{M}_{i=1}\), we have:

\[\begin{align} \mathbb{P}\bigl[\cup_{c \in C} (|sd_{c}(q) - \hat{sd}_{c}(q)| \geq t) \bigr] \leq 2|C| \exp (-2N t^2). \tag{A$\cdot $8} \end{align}\]

Since \(\mathbb{P}\bigl[\cup_{c \in C} (|sd_{c}(q) - \hat{sd}_{c}(q)| \geq t) \bigr] + \mathbb{P}\bigl[\cap_{c \in C} (|sd_{c}(q) - \hat{sd}_{c}(q)| < t) \bigr] = 1\), we have

\[\begin{align} \mathbb{P}\bigl[\cap_{c \in C} |sd_{c}(q) - \hat{sd}_{c}(q)| < t \bigr] \geq 1- 2|C| \exp (-2N t^2). \tag{A$\cdot $9} \end{align}\]

Equation (A\(\cdot\) 9) represents that \(\hat{sd}_{c}(q) - t < sd_{c}(q) < \hat{sd}_{c}(q) + t\) holds simultaneously for \(\forall c \in C\) with probability at least \(1- 2|C| \exp (-2N t^2)\). Note that Eq. (A\(\cdot\) 9) satisfies if we replace \(sd_c(q)\) and \(\hat{sd}_{c}(q)\) with \(sd_q(c)\) and \(\hat{sd}_{q}(c)\), respectively. If we set \(2|C| \exp (-2N t^2) = \beta\), we obtain \(t=\sqrt{\frac{1}{2N} \log\left(\frac{2|C|}{\beta}\right)}\). Thus, we get the claim. \(\tag*{◻}\)

A.8 Proof of Corollary 1

Proof. Since both \(\Phi\) and \(\Phi^{-1}\) are monotonic increasing functions, the followings with probability at least \(1-\beta\) hold by combining Lemma 3, Eqs. (24), and (25):

\[\begin{align} & \Phi\left(\Phi^{-1}(sd_{x_2}(x_1))+\frac{\epsilon}{\sigma}\right) \nonumber\\ & < \Phi\left(\Phi^{-1}\left(\hat{sd}_{x_2}(x_1) + \sqrt{\frac{1}{2N} \log\left(\frac{2|C|}{\beta}\right)}\right)+\frac{\epsilon}{\sigma}\right) \tag{A$\cdot $10} \\ & \Phi\left(\Phi^{-1}(sd_{x_2}(x_1))-\frac{\epsilon}{\sigma}\right) \nonumber\\ & > \Phi\left(\Phi^{-1}\left(\hat{sd}_{x_2}(x_1) - \sqrt{\frac{1}{2N} \log\left(\frac{2|C|}{\beta}\right)}\right)-\frac{\epsilon}{\sigma}\right). \tag{A$\cdot $11} \end{align}\]

Thus, we get the claim. \(\tag*{◻}\)

A.9 Proof of Theorem 6 and Theorem 7

Proof. Using Lemma 3, the following holds with probability at least \(1-\beta\):

\[\begin{align} &\sum_{c \in C} \text{𝟙} \bigl[ sd_{c_i}(q) < sd_{c}(q) \bigr] \nonumber\\ &\geq \sum_{c \in C} \text{𝟙} \bigl[ \hat{sd}_{c_i}(q) + t < \hat{sd}_{c}(q) - t \bigr], \tag{A$\cdot $12} \\ &\sum_{c \in C} \text{𝟙} \bigl[ sd_{c}(q) < sd_{c_i}(q) \bigr] \nonumber\\ &\geq \sum_{c \in C} \text{𝟙} \bigl[ \hat{sd}_{c}(q) + t < \hat{sd}_{c_i}(q) - t\bigr]. \tag{A$\cdot $13} \end{align}\]

wherer \(t = \sqrt{\frac{1}{2N} \log \frac{2 |C|}{\beta}}\). Note that both Eqs. (A\(\cdot\) 12) and (A\(\cdot\) 13) satisfy if we replace \(sd_c(q)\) and \(\hat{sd}_{c}(q)\) by \(sd_q(c)\) and \(\hat{sd}_{q}(c)\), respectively. Equations (A\(\cdot\) 12) and (A\(\cdot\) 13) represent the lower bounds of the number of candidate images that are more dissimilar and similar to \(q\) than \(c_i\), respectively. Thus, we get the claim. \(\tag*{◻}\)

A.10 Proof of Theorem 8

Proof. From Theorem 6, the following holds with probability at least \(1-\beta\):

\[\begin{align} \underline{\mathrm{Rank}}(q, c_i, C) \leq \mathrm{Rank}(q ,c_i, C) \leq \overline{\mathrm{Rank}}(q, c_i, C), \tag{A$\cdot $14} \end{align}\]

where \(\overline{\mathrm{Rank}}(q, c, C)=|C|- \sum_{c \in C} \text{𝟙} (\hat{sd}_{c_i}(q) + t < \hat{sd}_{c}(q) - t)\) and \(\underline{\mathrm{Rank}}(q, c, C)=\sum_{c \in C} \text{𝟙} (\hat{sd}_{c}(q) + t < \hat{sd}_{c_i}(q) - t) + 1\). Moreover, combining Theorem 1 and Corollary 1, the followings also hold with probability at least \(1-\beta\):

\[\begin{align} & \mathrm{Rank}(q+\delta, c_i, C) \leq |C|- \sum_{c \in C} \text{𝟙} \biggl[ \overline{sd}_{c_i}(q) < \underline{sd}_{c}(q) \biggr] \tag{A$\cdot $15} \\ &\mathrm{Rank}(q+\delta, c_i, C) \geq \sum_{c \in C} \text{𝟙} \biggl[ \overline{sd}_{c}(q) < \underline{sd}_{c_i}(q) \biggr] +1, \nonumber \end{align}\]

where \(\overline{sd}_{x_2}(x_1) = \Phi(\Phi^{-1}(\hat{sd}_{x_2}(x_1)+\sqrt{(1/2N) \log (2|C|/\beta)})+\frac{\epsilon}{\sigma})\) and \(\underline{sd}_{x_2}(x_1) \,{=}\, \Phi(\Phi^{-1}(\hat{sd}_{x_2}(x_1)-\sqrt{(1/2N) \log (2 |C|/\beta)})-\frac{\epsilon}{\sigma})\). Thus, when Eq. (34) holds, the followings hold with probability at least \(1-\beta\) by combining Eqs. (A\(\cdot\) 14) and (A\(\cdot\) 15):

\[\begin{aligned} & \alpha \geq \biggl(N- \sum_{c \in C} \text{𝟙} \biggl[ \overline{sd}_{c_i}(q) < \underline{sd}_{c}(q) \biggr]\biggr) - \underline{\mathrm{Rank}}(q, c_i, C) \nonumber\\ & \land \ \alpha \geq \overline{\mathrm{Rank}}(q, c_i, C) - \biggl(\sum_{c \in C} \text{𝟙} \biggl[ \overline{sd}_{c}(q) < \underline{sd}_{c_i}(q) \biggr] +1 \biggr) \nonumber\\ & \kern-4pt \Leftrightarrow \alpha \geq \biggl(N- \sum_{c \in C} \text{𝟙} \biggl[ \overline{sd}_{c_i}(q) < \underline{sd}_{c}(q) \biggr]\biggr) - \mathrm{Rank}(q, c_i, C)\nonumber\\ & \land \ \alpha \geq \mathrm{Rank}(q, c_i, C) - \biggl(\sum_{c \in C} \text{𝟙} \biggl[ \overline{sd}_{c}(q) < \underline{sd}_{c_i}(q) \biggr] +1 \biggr) \nonumber \\ & \kern-4pt \Leftrightarrow \alpha \geq \mathrm{Rank}(q+\delta, c_i, C) - \mathrm{Rank}(q, c_i, C)\nonumber\\ & \land \ \alpha \geq \mathrm{Rank}(q, c_i, C) - \mathrm{Rank}(q+\delta, c_i, C) \nonumber \\ & \kern-4pt \Leftrightarrow |\mathrm{Rank}(q+\delta, c_i, C) - \mathrm{Rank}(q, c_i, C)| \leq \alpha \nonumber \end{aligned}\]

Thus, we get the claim. \(\tag*{◻}\)

A.11 Proof of Theorem 9

Proof. From Theorem 7, the following holds probability at least \(1-\beta\):

\[\begin{align} \underline{\mathrm{Rank}}(q, c_i, C) \leq \mathrm{Rank}(q, c_i, C) \leq \overline{\mathrm{Rank}}(q, c_i, C), \tag{A$\cdot $16} \end{align}\]

where \(\overline{\mathrm{Rank}}(q, c_i, C)=|C|- \sum_{c \in C} \text{𝟙} (\hat{sd}_{q}(c_i) + t < \hat{sd}_{q}(c) - t)\), and \(\underline{\mathrm{Rank}}(q, c_i, C)=\sum_{c \in C} \text{𝟙} (\hat{sd}_{q}(c) + t < \hat{sd}_{q}(c_i) - t) + 1\). Combining Theorem 2 and Corollary 1, the followings holds with probability at least \(1-\beta\):

\[\begin{align} & \mathrm{Rank}(q, c_i +\delta_j, \tilde{C}) \leq |C|- \sum_{c \in C} \text{𝟙} \biggl[ \overline{sd}_{q}(c_i) < \underline{sd}_{q}(c) \biggr] \tag{A$\cdot $17} \\ & \mathrm{Rank}(q, c_i +\delta_i, \tilde{C}) \geq \sum_{c \in C} \text{𝟙} \biggl[\overline{sd}_{q}(c) < \underline{sd}_{q}(c_i) \biggr] +1, \nonumber \end{align}\]

where \(\overline{sd}_{x_2}(x_1)=\Phi(\Phi^{-1}(\hat{sd}_{x_2}(x_1)+\sqrt{(1/2N) \log (2|C|/\beta}))+\frac{\epsilon}{\sigma})\), \(\underline{sd}_{x_2}(x_1)=\Phi(\Phi^{-1}(\hat{sd}_{x_2}(x_1)-\sqrt{(1/2N) \log (2 |C|/\beta)})-\frac{\epsilon}{\sigma})\). Thus, when Eq. (34) holds, the followings hold with probability at least \(1-\beta\) by combining Eqs. (A\(\cdot\) 16) and (A\(\cdot\) 17):

\[\begin{aligned} & \alpha \geq \biggl(N- \sum_{c \in C} \text{𝟙} \biggl[ \overline{sd}_{q}(c_i) < \underline{sd}_{q}(c) \biggr]\biggr) - \underline{\mathrm{Rank}}(q, c_i, C) \nonumber\\ & \land \ \alpha \geq \overline{\mathrm{Rank}}(q, c_i, C) - \biggl(\sum_{c \in C} \text{𝟙} \biggl[ \overline{sd}_{q}(c) < \underline{sd}_{q}(c_i) \biggr] +1 \biggr) \nonumber\\ & \kern-4pt \Leftrightarrow \alpha \geq \biggl(N- \sum_{c \in C} \text{𝟙} \biggl[ \overline{sd}_{q}(c_i) < \underline{sd}_{q}(c) \biggr]\biggr) - \mathrm{Rank}(q ,c_i, C)\nonumber\\ & \land \ \alpha \geq \mathrm{Rank}(q ,c_i, C) - \biggl(\sum_{c \in C} \text{𝟙} \biggl[ \overline{sd}_{q}(c) < \underline{sd}_{q}(c_i) \biggr] +1 \biggr) \nonumber \\ & \kern-4pt \Leftrightarrow \alpha \geq \mathrm{Rank}(q+\delta, c_i, C) - \mathrm{Rank}(q ,c_i, C)\nonumber\\ & \land \ \alpha \geq \mathrm{Rank}(q ,c_i, C) - \mathrm{Rank}(q+\delta, c_i, C) \nonumber \\ & \kern-4pt \Leftrightarrow |\mathrm{Rank}(q+\delta, c_i, C) - \mathrm{Rank}(q ,c_i, C)| \leq \alpha \nonumber \end{aligned}\]

Thus, we get the claim. \(\tag*{◻}\)

Appendix B: Comparison Methods

We compare our proposed robustness training Eq. (20) (TBT) and Eq. (21) (FCTB) with three existing methods: (i) triplet Loss (Triplet) [35], (ii) anti-collapse triplet (ACT), which is an adversarial training for CBIR to improve empirical robustness [3], (iii) training for classification using interval bound propagation (C-IBP) to improve certified robustness for the classification task [20].

Triplet is one of the loss functions commonly used in metric learning. Let \(D_{t}=\{(a,p,n)_i\}^M_{i=1}\) be a training data set where \(p\) belongs to the same class as \(a\), and \(n\) belongs to a different class than \(a\). Then, Triplet trains the feature extraction DNN \(f\) by minimizing the following loss function:

\[\begin{align} \sum_{(a,p,n)\in D_{t}} \max\{\|f(a)-f(p)\|_2 - \|f(a)-f(n)\|_2+m, 0\}, \tag{A$\cdot $18} \end{align}\]

where \(m\) is a margin parameter.

ACT trains feature extraction DNN \(f\) on generated adversarial examples. Let \(D_{t}=\{(a,p,n)_i\}^M_{i=1}\) be a training data set. For each triplet \((a,p,n) \in D_{t}\), ACT generate \(p+\delta_p\) and \(n+\delta_n\) so that the distance \(\|f(p+\delta_p)-f(n+\delta_{n})\|_2\) is small. Specifically, ACT minimize triplet loss with the triplet \((a, p+\delta_p, n+\delta_n)\) as follows:

\[\begin{align} & \sum_{(a,p,n)\in D_{t}} \max\{\|f(a)-f(p+\delta_{p})\|_2 \nonumber\\ &\kern5.2em - \|f(a)-f(n+\delta_{n})\|_2+m, 0\}, \tag{A$\cdot $19} \end{align}\]

where

\[\begin{align} \delta_p, \delta_n = \mathop{\mathrm{arg~min}}\limits_{\substack{ \delta_p, \delta_n \in X, \\ \|\delta_p\|_{\infty} \leq \epsilon, \|\delta_n\|_{\infty} \leq \epsilon}} \|f(p+\delta_p)-f(n+\delta_{n})\|_2. \tag{A$\cdot $20} \end{align}\]

In our experiments, we minimize Eq. (A\(\cdot\) 20) by using PGD [12] with the step size of \(\frac{\epsilon}{10}\) and the number of updates of \(20\).

C-IBP trains the classifier \(f_c\) by simultaneously minimizing the original cross-entropy loss and cross-entropy loss due to the upper and lower bounds of the logits calculated by IBP. Let \(\hat{f}_c^y(x)\) be the upper and lower bounds of the logits \(f_c(x)\) where the logit of true class \(y\) is equal to its lower bound and the other logits are equal to their upper bounds. Then, C-IBP trains \(f_c(x)\) by minimizing the following loss function with training data \(D_{t}=\{(x,y)_i\}_{i=1}^{M}\):

\[\begin{align} \sum_{(x,y)\in D_{t}} \kappa \cdot CE(f_c(x),y)+ (1-\kappa) \cdot CE(\hat{f}_c^y(x),y), \tag{A$\cdot $21} \end{align}\]

where CE represents Cross-Entropy loss. Note that we use the classifier trained with IBP without the final layer (logit layer) as a feature extractor in our experimentation.

B.1 Hyperparameters of ACT and C-IBP

When training with ACT, we set the fixed maximum perturbation size of the adversarial examples as \(\epsilon=0.2\) for MNIST and FMNIST and \(\epsilon= \frac{2}{255}\) for CIFAR10. Then we generate them by using PGD [12] with the step size of \(\frac{\epsilon}{10}\) and the number of updates of \(20\).

When training with C-IBP, we use the scheduling strategy for \(\epsilon\) and \(\kappa\) proposed in [20] as well as training of TBT. Specifically, \(\epsilon\) is gradually increased from \(0.0\) to \(\epsilon_{e}\), and the \(\kappa\) is gradually decreased from \(1.0\) to \(\kappa_{e}\). We use \(\epsilon_{e}=0.2\) for MNIST and FMNIST, and \(\epsilon_{e}=\frac{2}{255}\) for CIFAR10, respectively. We use \(\kappa_{e}=0.5\) for all datasets. Then, we linearly increase \(\epsilon\) and decrease \(\kappa\) between \(2K\) and \(10K\) steps.

Footnotes

1. [36] derives similar results in the proof of Corollary 1 in their paper. [36] proposes a certified defense for saliency map.

2. https://github.com/Confusezius/Revisiting_Deep_Metric_Learning_PyTorch

Authors

Kazuya KAKIZAKI
  NEC Corporation,University of Tsukuba

Kazuto FUKUCHI
  University of Tsukuba,RIKEN AIP

Jun SAKUMA
  RIKEN AIP,Institute of Science Tokyo

Keyword

adversarial example,  certified defense,  content-based image retrieval