Source-linked AI summary
Simple Black-Box Adversarial Perturbations for Deep Networks
Nina Narodytska, Shiva Prasad Kasiviswanathan
TL;DR
The paper addresses whether CNNs can be attacked without internal knowledge of the target network. It proposes direct black-box pixel attacks using random selection and greedy local search, and reports effective adversarial-example generation with very small localized perturbations, including k-misclassification. The paper concludes that these simple attacks expose vulnerabilities relevant to robustness testing.
Problem
CNNs are vulnerable to adversarial perturbations, motivating the question of whether practical attacks can be crafted with only black-box access to the target network.
Method
The paper uses gradient-free attacks that randomly perturb one or a small set of pixels, then applies greedy local search to carefully select pixels while querying the network as an oracle.
Results
The attacks effectively generate adversarial examples while perturbing only a small fraction of pixels, averaging about 0.5% per ImageNet1000 image, and extend to k-misclassification.
Takeaways & Limitations
Simple localized black-box attacks can reveal vulnerabilities in deep CNNs and provide a litmus test for designing robust networks.
Takeaways & Limitations
Localized adversarial images do not represent the original data distribution, and adversarial training improves resistance to new local-search attacks only marginally, by 1-2% on average.
Abstract
from arXiv · showhide
Deep neural networks are powerful and popular learning models that achieve state-of-the-art pattern recognition performance on many computer vision, speech, and language processing tasks. However, these networks have also been shown susceptible to carefully crafted adversarial perturbations which force misclassification of the inputs. Adversarial examples enable adversaries to subvert the expected system behavior leading to undesired consequences and could pose a security risk when these systems are deployed in the real world. In this work, we focus on deep convolutional neural networks and demonstrate that adversaries can easily craft adversarial examples even without any internal knowledge of the target network. Our attacks treat the network as an oracle (black-box) and only assume that the output of the network can be observed on the probed inputs. Our first attack is based on a simple idea of adding perturbation to a randomly selected single pixel or a small set of them. We then improve the effectiveness of this attack by carefully constructing a small set of pixels to perturb by using the idea of greedy local-search. Our proposed attacks also naturally extend to a stronger notion of misclassification. Our extensive experimental results illustrate that even these elementary attacks can reveal a deep neural network's vulnerabilities. The simplicity and effectiveness of our proposed schemes mean that they could serve as a litmus test for designing robust networks.
1 Introduction
The paper investigates simple black-box adversarial attacks on CNNs, showing that randomly or greedily selected pixel perturbations can produce misclassification without internal network knowledge. The attacks also extend to k-misclassification, where the true label falls outside the top-k predictions.
- Motivation: CNNs perform many computer-vision tasks but are susceptible to adversarial perturbations that can cause undesirable consequences in deployed systems.Examples include subverting fraud or malware detection and misleading autonomous navigation systems.
- Problem setting: The paper studies black-box attacks in which adversaries observe network outputs on probed inputs rather than access architecture or parameters.This threat model is more realistic but more challenging than white-box attacks.
- Initial attack: Randomly perturbing one pixel, or about 50 pixels for high-resolution images, can generate adversarial images in many cases.The experiments investigate whether modifying a single pixel can force misclassification.
- Greedy approach: Greedy local search carefully selects a small set of pixels, reducing the perturbation needed while using iterative neighborhood refinement.The method minimizes the network’s confidence in the true class and relates selected pixels to image saliency.
- Experimental findings: 0.5% of ImageNet1000 pixels per image are perturbed on average, while the approach generates adversarial examples despite lacking perfect network knowledge.Most previous attacks require perturbing all pixels, whereas this approach changes only a very small fraction.
- Stronger misclassification: k-misclassification excludes the true label from the network’s top-k predictions, matching evaluation settings based on ranked predictions.The paper presents these as the first adversarial attacks on deep neural networks achieving this stronger condition.
2 Related work
Prior adversarial attacks commonly assume full knowledge of the target network, whereas black-box methods operate with restricted access. This paper uses a direct gradient-free strategy that avoids transferability assumptions and substitute-network training, while defenses remain outside its scope.
- White-box attacks: Earlier attacks use detailed architecture and parameter knowledge, often constructing perturbations from loss gradients.These requirements limit applicability to adversaries able to obtain insider information.
- Black-box attacks: Black-box attacks instead assume that the adversary can observe outputs from probed inputs, creating a more realistic but more challenging threat model.The paper falls into this restricted-access line of work.
- Paper’s approach: Unlike substitute-network approaches, the proposed attack directly queries the target, avoids transferability assumptions, and requires no retraining.It also avoids the overhead of gathering data and training a substitute network.
- Defenses: Defense design is outside the paper’s scope, although regularization, distillation, and differentially private training may reduce attack efficacy.The paper presents these as possible adaptations rather than evaluated solutions.
3 Preliminaries
The preliminaries formalize normalized image inputs, network outputs, ranked predictions, adversarial images, and black-box threat models. They define k-misclassification as excluding the true label from the top-k predictions and distinguish required oracle access levels.
- Notation and normalization: Images are normalized inputs whose coordinate values lie within the valid range [LB, UB].Normalization is treated as an external procedure, and all images in the analysis are assumed normalized.
- Network notation: A network maps an image I to class probabilities, while π(NN(I), k) returns the indices of its top-k predictions.Ties in ranking are broken arbitrarily.
- Misclassification: k-misclassification occurs when the true label is absent from the network’s top-k predictions.The conventional case is k = 1, and larger k defines a stronger adversary.
- Adversarial goal: An adversarial image is produced by an adversary function Adv that transforms an initially correctly classified image into one that satisfies the chosen misclassification condition.The goal is to succeed for many images while applying only a small perturbation.
- Threat model: The black-box threat model makes no assumptions about the target network’s architecture or parameters and may restrict the adversary to using a proxy oracle.The experimental setting also considers this weakened access condition.
- Oracle access: The randomized adversary needs class-label access, whereas local search additionally uses the probability assigned to the true class and the π vector.Neither approach requires the complete network probability vector.
4 Black-box Generation: A First Attempt
The paper’s first black-box attack randomly perturbs one pixel or a small pixel set and queries the network to identify misclassification-inducing changes. Experiments show that critical pixels are common, so even random trials and small perturbations can generate adversarial images.
- Random single-pixel attack: RandAdv randomly selects one pixel or a small pixel set, applies a sign-preserving perturbation, and queries the network for misclassification.The perturbation is oblivious to network parameters and does not require access to gradients.
- Definitions and evaluation setting: A critical pixel is one whose perturbation produces an image misclassified by the network.Experiments focus on good images, which the network initially classifies correctly.
- Random single-pixel attack: RandAdv randomly samples pixels with replacement and returns an unbiased estimate of the fraction of critical pixels, while succeeding if it finds at least one.The procedure can fail when its trials find no critical pixel.
- Empirical findings: p = 1 can suffice for misclassification after perturbing one pixel, although the altered pixel is sometimes visible and often imperceptible to humans.Table 2 includes automobile-to-truck and cat-to-dog misclassifications after one-pixel perturbation.
- Empirical findings: Almost 80% of randomly selected pixels are critical in CIFAR10 at p = 100, and success becomes easier as p increases.The reported success measure is the fraction of good inputs for which RandAdv finds at least one critical pixel.
- Empirical findings: Critical-pixel rates are lower for MNIST and STL10 than for SVHN and CIFAR10, attributed respectively to background pixels and higher image resolution.STL10 images are 96 × 96, making a single pixel potentially less influential on the prediction.
- Pixel-set extension: For high-resolution images, the attack extends to critical sets of 50 pixels, only 0.09% of a 224 × 224 crop, with increasing p again making adversarial construction easier.The modified procedure uses 5000 trials per image and reports that relatively small perturbations remain sufficient.
5 Black-box Generation: A Greedy Approach
The greedy black-box attack searches locally for critical pixels by minimizing the network’s probability for the original class while keeping perturbed images valid. It efficiently constructs adversarial images from oracle outputs and reveals overlap with high-saliency pixels.
- Because exhaustive search over pixel sets is computationally prohibitive, the attack uses greedy local search over the image space.The procedure evaluates a restricted neighborhood and iteratively refines the current image.
- The method minimizes the probability assigned to the original class and generates images differing from the original in only a few pixels.The local-search procedure provides an implicit gradient approximation without requiring network gradients.
- Each round forms a neighborhood around previously perturbed pixels, considering nearby locations within a square controlled by parameter d.The neighborhood contains images differing from the current image in one pixel.
- The transformation function evaluates candidate perturbations, ranks images by their score, and selects the first t candidates to determine which pixels to perturb.Pixels producing larger decreases in the objective are prioritized.
- The cyclic perturbation keeps every coordinate within [LB, UB], so each intermediate image remains in the original image space.The perturbation parameter r is kept in [0, 2], while p is adjusted to help identify useful pixels.
- A Relation to Saliency Maps: More than 23% of pixels selected by LocSearchAdv overlap with the top-10% saliency-map pixels on average.The overlap exceeds the roughly 10% expected from a random set of pixels, suggesting the attack rediscovers salient pixels without explicitly computing gradients.
6 Experimental Evaluation
The evaluation compares gradient-free black-box attacks with the fast-gradient sign method across multiple datasets and CNN variants. Local search generally generates more adversarial images with smaller localized perturbations, while performance changes with the misclassification criterion and model setting.
- The fast-gradient sign baseline uses a gradient-based update and requires selecting perturbation magnitude ϵ, with ϵ = 0.212 reported as its smallest competitive value on CIFAR10 Network-in-Network.At ϵ = 0.1, generated adversarial images decrease by around 10% compared with ϵ = 0.2 on that setting.
- Local-search attacks are more effective than the fast-gradient sign method in generating adversarial images without network architecture or parameter access.The difference is especially prominent for batch-normalized networks, where the baseline has difficulty producing adversarial images.
- On ImageNet1000, local search is more successful in most cases while perturbing less than 0.55% of pixels on average.
- For k-misclassification on CIFAR10, increasing k reduces effectiveness while increasing perturbation and computation time, yet local search still fools a large fraction at k = 4.
- Between 25% and 43% of adversarial images generated on the original CIFAR10 network also transfer to modified Network-in-Network models at k = 1.
7 Conclusion
The paper presents practical black-box attacks that locate small pixel sets without gradients and demonstrates their effectiveness against deep CNNs. It concludes that localized attacks expose robustness weaknesses, while existing adversarial training improves resistance only marginally in the reported setting.
- The attacks efficiently locate a small set of pixels whose perturbation causes deep neural networks to misclassify images without using gradient information.
- Batch-normalized models were observed to be somewhat more resilient to adversarial perturbations, possibly because of batch normalization's regularization properties.
- The experiments demonstrate that the proposed simple approaches effectively generate adversarial examples.
- Because localized adversarial images do not represent the original data distribution, adversarial training improves resistance to new local-search attacks by only 1–2% on average.
- The local-search approach may also attack other machine-learning systems and serve as a tool for measuring their robustness.