Pixle: a fast and effective black-box attack based on rearranging pixels

Jary Pomponi, Simone Scardapane, Aurelio Uncini

Abstract: Recent research has found that neural networks are vulnerable to several types of adversarial attacks, where the input samples are modified in such a way that the model produces a wrong prediction that misclassifies the adversarial sample. In this paper we focus on black-box adversarial attacks, that can be performed without knowing the inner structure of the attacked model, nor the training procedure, and we propose a novel attack that is capable of correctly attacking a high percentage of samples by rearranging a small number of pixels within the attacked image. We demonstrate that our attack works on a large number of datasets and models, that it requires a small number of iterations, and that the distance between the original sample and the adversarial one is negligible to the human eye.

Introduction

Deep Neural Networks (DNNs) are notoriously fragile. Adversarial attacks can trick them into misclassifying images by making tiny, human-imperceptible changes. While white-box attacks (where the attacker knows the model's internal weights) are well-studied, this paper addresses the more challenging black-box $L_0$ attack scenario. In a black-box setting, the attacker only has access to the model's output probabilities. An $L_0$ attack specifically aims to minimize the number of pixels modified, rather than the intensity of the change. Existing $L_0$ black-box methods, such as the "One-Pixel Attack," often struggle to scale to high-resolution images or require thousands of iterations to find a successful perturbation.

Methodology

The authors introduce Pixle, a random-search-based algorithm that fools image classifiers not by adding noise, but by simply rearranging a handful of existing pixels. Instead of calculating gradients or introducing new colors, Pixle selects a small "patch" of pixels and moves them to new coordinates within the image.

Mapping Functions ($m$)

Central to the attack are mapping functions that determine where a pixel should move. The authors evaluated several strategies:

  • Random: Moving pixels to random new locations.
  • Similarity/Distance: Moving a pixel to the position of the most similar (or most different) pixel in the image.
  • Distribution-based: Sampling the new location from a probability distribution based on similarity, which helps the algorithm avoid local minima.
Illustration of the mapping function $m(x,y)$ used to rearrange pixels from their original coordinates to new positions.

Search Algorithms

Pixle utilizes two primary search strategies: Restart-Iterative, a robust approach that performs multiple "restarts" to keep only the most effective modifications, and Iterative, a faster version that updates the adversarial image immediately upon finding any successful pixel swap.

Experimental Setup

The researchers evaluated Pixle on three standard computer vision benchmarks: CIFAR10 (32x32), TinyImageNet (64x64), and ImageNet (224x224). These were tested against popular architectures including ResNet (18, 20, 50) and VGG (11, 16).

Results and Insights

Pixle consistently outperformed existing $L_0$ attacks like OnePixel and ScratchThat across several metrics:

  • Success Rate: Pixle achieved a 100% success rate on CIFAR10 and TinyImageNet (VGG16), and 98-99% on the much harder ImageNet dataset.
  • Query Efficiency: On CIFAR10 with ResNet18, Pixle required an average of only 119 iterations, compared to 5,125 for the OnePixel attack.
  • Targeted Attacks: In scenarios forcing the model to pick a specific wrong class, Pixle was significantly more successful than previous methods.
An adversarial example where rearranging a small number of pixels can cause a model to misclassify a bird as a different object, such as a vase.

A striking insight from this work is that an image usually contains all the pixel data necessary to trigger a misclassification; one simply has to move a few pixels to the "wrong" places to disrupt the spatial features the network relies on. This highlights the spatial fragility of state-of-the-art models, where moving a single pixel can sometimes be enough to turn a "Bird" into a "Vase."

Conclusion and Future Work

Pixle demonstrates that effective adversarial attacks do not require injecting malicious noise. Because Pixle doesn't change pixel values—only positions—standard noise-reduction defenses may prove ineffective. Future work aims to improve the interpretability of these attacks to understand why specific rearrangements trigger specific misclassifications and to explore applying this logic to other domains like audio or text.

Summary updated

Abstract

Recent research has found that neural networks are vulnerable to several types of adversarial attacks, where the input samples are modified in such a way that the model produces a wrong prediction that misclassifies the adversarial sample. In this paper we focus on black-box adversarial attacks, that can be performed without knowing the inner structure of the attacked model, nor the training procedure, and we propose a novel attack that is capable of correctly attacking a high percentage of samples by rearranging a small number of pixels within the attacked image. We demonstrate that our attack works on a large number of datasets and models, that it requires a small number of iterations, and that the distance between the original sample and the adversarial one is negligible to the human eye.
BibTeX
@inproceedings{pomponi2022pixle,
  author = {Jary Pomponi and Simone Scardapane and Aurelio Uncini},
  title = {{Pixle: a fast and effective black-box attack based on rearranging pixels}},
  booktitle = {IJCNN},
  year = {2022},
  doi = {10.1109/ijcnn55064.2022.9892966},
}
Figure