Certified Defense for Content Based Image Retrieval

Kazuya Kakizaki, Kazuto Fukuchi, Jun Sakuma

Abstract

Content-Based Image Retrieval (CBIR) systems are highly susceptible to adversarial examples that can maliciously manipulate search rankings. Unlike classification, where labels are discrete, CBIR relies on relative feature distances, making traditional certified defenses inapplicable. This paper presents the first framework for certified robustness in CBIR. By leveraging Interval Bound Propagation (IBP) to bound feature distances, we introduce $(\alpha, \epsilon)$-robustness and two novel training objectives: Tightly Bounding Training (TBT) and Fine-tuning to Candidates (FCTB). Our approach provides provable guarantees that search rankings remain stable under perturbation, significantly outperforming existing empirical defenses on standard benchmarks.

Introduction

Content-Based Image Retrieval (CBIR) systems, such as those used in facial recognition or visual search engines, function by mapping images into a high-dimensional feature space. Candidates are then ranked based on their Euclidean distance to a query image. While effective, these systems are vulnerable to adversarial examples (AXs)—small, human-imperceptible perturbations that can cause a target image to jump to the top of search results or disappear entirely.

Most existing defenses are empirical, such as adversarial training, which may fail against adaptive attackers. While "certified robustness" provides theoretical guarantees for image classifiers, it has remained elusive for CBIR because classification focuses on label consistency, whereas retrieval focuses on relative rankings. This work, presented at WACV 2023, bridges this gap by introducing the first certified defense framework for CBIR.

Methodology

The authors propose a three-fold approach to achieve certified robustness:

  1. $(\alpha, \epsilon)$-Robustness: A new definition of robustness for retrieval. It guarantees that for any perturbation within a radius $\epsilon$, the rank of a retrieved image will not shift by more than $\alpha$ positions.
  2. Verification via Distance Bounds: To avoid the impossible task of checking every perturbation, the framework uses Interval Bound Propagation (IBP). This method derives mathematical upper and lower bounds on the Euclidean distance between feature vectors. If the worst-case distance maintains the rank within the $\alpha$ threshold, the query is considered "certified."
  3. Robust Training Objectives:
  4. Tightly Bounding Training (TBT): A general training method that combines standard triplet loss with a regularization term. This term forces the upper and lower distance bounds to be as tight as possible around the actual distance.
  5. Fine-tuning to Candidates (FCTB): A specialized method to further harden the system once the specific set of "candidate" images (the database being searched) is known.

Experimental Results

The proposed methods were evaluated on MNIST, Fashion-MNIST (FMNIST), and CIFAR10 using "Small" (3-layer) and "Large" (6-layer) CNN architectures for feature extraction.

Certified vs. Empirical Robustness

A key finding is that traditional methods provide virtually no theoretical guarantees. As shown in Figure 2, on the MNIST dataset at $K=40$, baseline methods like Triplet loss, Adversarial Training (ACT), and classification-based IBP (C-IBP) all yielded a Certified Robustness (CR-Recall@K) of 0.00 under candidate attacks. In contrast, the proposed TBT+FCTB method achieved a certified robustness of 0.96, proving stability for 96% of queries.

Figure 2: Empirical and Certified Robustness (Recall@K) for Query Attacks (QA) and Candidate Attacks (CA) across three benchmarks.

Accuracy and Robustness Trade-off

While the proposed methods offer unprecedented security guarantees, they introduce a "robustness tax" on standard performance. As seen in Figure 1, standard Recall@1 on CIFAR10 drops from 0.58 for the Triplet baseline to 0.19 for TBT+FCTB. However, this performance gap narrows significantly as the retrieval window $K$ increases, with Recall@40 reaching 0.97 for TBT+FCTB compared to 0.99 for the baseline.

Figure 1: Standard Recall@K performance (non-adversarial) across MNIST, FMNIST, and CIFAR10 benchmarks.

Discussion and Future Work

The primary challenge for certified CBIR remains scalability. While effective on smaller benchmarks, training on high-resolution datasets like CUB-200-2011 often leads to training collapse due to the inherent "looseness" of IBP bounds in deeper architectures. Future research must focus on developing certified defenses that can scale to deeper networks like ResNets or Transformers to make certified CBIR viable for large-scale, real-world applications.

Summary updated

BibTeX
@inproceedings{kakizaki2023certified,
  author = {Kazuya Kakizaki and Kazuto Fukuchi and Jun Sakuma},
  title = {{Certified Defense for Content Based Image Retrieval}},
  booktitle = {IEEE/CVF Winter Conference on Applications of Computer Vision},
  year = {2023},
  doi = {10.1109/wacv56688.2023.00454},
}
Figure