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

Jary Pomponi, Simone Scardapane, Aurelio Uncini

TL;DR

Pixle is a novel black-box adversarial attack that fools image classifiers not by adding noise, but by simply rearranging a handful of existing pixels. It achieves near-100% success rates across major benchmarks like ImageNet while requiring significantly fewer model queries and lower pixel distortion than previous state-of-the-art $L_0$ attacks.

What Problem Does This Paper Address?

Deep Neural Networks (DNNs) are notoriously fragile. Adversarial attacks can trick them into misclassifying images by making tiny, human-imperceptible changes. Most research focuses on "white-box" attacks (where the attacker knows the model's internal weights) or attacks that modify pixel values (adding a layer of "noise").

This paper tackles the more difficult black-box $L_0$ attack scenario. In a black-box setting, the attacker can only see the model's output (the class probabilities) for a given input. An $L_0$ attack aims to minimize the number of pixels modified, rather than the intensity of the change. Existing $L_0$ black-box methods, like the famous "One-Pixel Attack," often struggle to scale to high-resolution images or require thousands of iterations to find a successful perturbation.

Methods

The authors introduce Pixle, a random-search-based algorithm. Instead of calculating gradients or introducing new colors, Pixle selects a small "patch" of pixels and moves them to new coordinates within the image.

Key components include:

  • Mapping Functions ($m$): These determine where a pixel should move. The authors tested 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 getting stuck in local minima.
  • Search Algorithms:
    • Restart-Iterative: A robust approach that performs multiple "restarts," keeping only the modifications that most significantly decrease the model's confidence in the correct class.
  • Iterative: A faster version that updates the adversarial image every time a successful pixel swap is found.

Datasets

The researchers evaluated Pixle on three standard computer vision benchmarks:

  1. CIFAR10: Low-resolution (32x32) images of 10 classes.
  2. TinyImageNet: Medium-resolution (64x64) images of 200 classes.
  3. ImageNet: High-resolution images of 1,000 classes.

They tested these against popular architectures including ResNet (18, 20, 50) and VGG (11, 16).

Key Insights and Ideas

  • "The Information is Already There": The most striking insight is that you don't need to inject "malicious" noise to break a model. An image usually contains all the pixel data necessary to trigger a misclassification; you just have to move a few pixels to the "wrong" places to disrupt the spatial features the network relies on.
  • Spatial Fragility: The success of Pixle highlights that even state-of-the-art models are highly sensitive to local spatial arrangements. Moving a single pixel can sometimes be enough to turn a "Bird" into a "Vase" (as shown in Figure 1 of the paper).
  • Efficiency through Randomness: By using random search and distribution-based mapping, Pixle bypasses the need for complex optimization (like Differential Evolution used in OnePixel), making it much faster and more effective on high-resolution images where the search space is massive.

Key Results

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

  • 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.
  • Distortion: Pixle modified fewer pixels on average than its competitors while maintaining a higher success rate.
  • Targeted Attacks: In "targeted" scenarios (forcing the model to pick a specific wrong class), Pixle was significantly more successful than previous methods, which often fail to reach the target class in black-box settings.

Limitations and Future Work

While highly effective, the authors note a few areas for further exploration:

  • Interpretability: It is currently unclear why specific pixel rearrangements trigger specific misclassifications. Future work aims to understand the correlation between the source pixels and the resulting adversarial class.
  • Cross-Domain Application: The current study is limited to images. The authors suggest that the logic of "rearranging existing data" could be applied to other domains like audio or text.
  • Defense Mechanisms: Because Pixle doesn't change pixel values (only positions), standard noise-reduction defenses might not work. The authors hope this research leads to the development of new defenses specifically designed for $L_0$ rearrangement attacks.

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},
}

Loading related content...

Figure