PaperlayerView exact revision on arXiv

Source-linked AI summary

Feature-Guided Black-Box Safety Testing of Deep Neural Networks

Matthew Wicker, Xiaowei Huang, Marta Kwiatkowska

arXiv:1710.07859v2cs.CV

TL;DR

Adversarial examples threaten the reliability of deep neural networks, while many existing attacks require network knowledge. This paper proposes feature-guided black-box testing with SIFT-based saliency and stochastic-game search, reporting competitive benchmark performance and safety-testing applications. It also identifies theoretical guarantees under restrictions, while the game’s state space can be impractically large and distance comparisons require care across color channels.

  • Problem

    Adversarial examples threaten safety-critical neural-network applications, while many existing crafting approaches require knowledge of the target network.

  • Method

    The method extracts SIFT features, converts them into a saliency distribution, formulates manipulation as a two-player stochastic game, and searches it with MCTS without network knowledge.

  • Results

    The MCTS implementation achieves competitive performance on benchmark networks and supports robustness evaluation and potential real-time decision support in safety-critical applications.

  • Takeaways & Limitations

    Feature-guided black-box testing provides a practical approach for evaluating adversarial resilience in image classifiers, including safety-critical traffic-light recognition.

  • Takeaways & Limitations

    The game state space can be impractically large, and reported L0 comparisons differ because color images may count pixels or channels differently.

Abstract

from arXiv · show

Despite the improved accuracy of deep neural networks, the discovery of adversarial examples has raised serious safety concerns. Most existing approaches for crafting adversarial examples necessitate some knowledge (architecture, parameters, etc.) of the network at hand. In this paper, we focus on image classifiers and propose a feature-guided black-box approach to test the safety of deep neural networks that requires no such knowledge. Our algorithm employs object detection techniques such as SIFT (Scale Invariant Feature Transform) to extract features from an image. These features are converted into a mutable saliency distribution, where high probability is assigned to pixels that affect the composition of the image with respect to the human visual system. We formulate the crafting of adversarial examples as a two-player turn-based stochastic game, where the first player's objective is to minimise the distance to an adversarial example by manipulating the features, and the second player can be cooperative, adversarial, or random. We show that, theoretically, the two-player game can con- verge to the optimal strategy, and that the optimal strategy represents a globally minimal adversarial image. For Lipschitz networks, we also identify conditions that provide safety guarantees that no adversarial examples exist. Using Monte Carlo tree search we gradually explore the game state space to search for adversarial examples. Our experiments show that, despite the black-box setting, manipulations guided by a perception-based saliency distribution are competitive with state-of-the-art methods that rely on white-box saliency matrices or sophisticated optimization procedures. Finally, we show how our method can be used to evaluate robustness of neural networks in safety-critical applications such as traffic sign recognition in self-driving cars.

1 Introduction

The paper addresses adversarial vulnerabilities in safety-critical neural-network applications by proposing feature-guided black-box testing for image classifiers. It combines perception-informed feature extraction, stochastic-game search, and Monte Carlo tree search to evaluate robustness without network knowledge.

  • Motivation: Adversarial examples can cause safety-critical networks to misclassify inputs after only minor pixel changes.Examples include steering off-road, driving into barriers, and misclassifying traffic signs as safe or unsafe alternatives.
  • Approach: The proposed approach uses image features to identify elements most vulnerable to a CNN-based visual system.The authors motivate feature extraction as a way to target structurally important image elements despite limited understanding of CNN feature extraction.
  • Approach: SIFT features are converted into a Gaussian mixture model that guides black-box exploration toward salient pixels while reducing dimensionality.The method uses far fewer features than pixels and models manipulation as a two-player turn-based stochastic game.
  • Theory: The game can theoretically converge to an optimal strategy representing a globally minimal adversarial image, with additional safety conditions for Lipschitz networks.Player II may cooperate, oppose the search, or sample according to the saliency distribution.
  • Evaluation: MCTS is implemented as an anytime algorithm that achieves competitive performance on benchmark networks after about one minute per image without network knowledge.The experiments include MNIST, CIFAR10, and state-of-the-art networks.
  • Applications: The software supports offline robustness evaluation and potentially real-time decision support in safety-critical applications.The authors state that failure to find adversarial examples under the asymptotic strategy can provide a theoretical safety guarantee, while practical termination may require an alternative criterion.

2 Preliminaries

The preliminaries define network decisions, image distances, adversarial examples, safety, feature extraction, and pixel manipulations. SIFT keypoints are represented by position, scale, and response strength, then used to construct a saliency distribution for guided analysis.

  • Network and image model: A classifier assigns each input a class by maximizing its normalized confidence across the network’s class set.The input domain is typically represented as a width-by-height-by-channel real vector space.
  • Network and image model: Image dimensions are normalized to [0, 1], and L_k distance neighborhoods define which perturbed inputs remain within a specified distance d.The neighborhood η(α, k, d) contains points whose L_k distance from α is at most d.
  • Adversarial examples and safety: An adversarial example is a nearby input whose classification changes to a specified target class or to any different class.Targeted safety requires the target-class adversarial set to be empty; non-targeted safety requires the union over alternative classes to be empty.
  • Feature extraction: SIFT extracts scale-, rotation-, and transformation-invariant keypoints, each represented by image coordinates, feature size, and response strength.Its stages include scale-space extrema detection, keypoint localization, and descriptor assignment.
  • Saliency distribution: The keypoints are converted into a Gaussian mixture model whose components center on keypoint locations, use keypoint sizes as variances, and receive response-based weights.This produces the saliency distribution illustrated by the original image, keypoint annotation, and heatmap.
  • Pixel manipulation: Pixel manipulations add or subtract a magnitude τ on selected pixels and channels, subject to the permitted value bounds.In the experiments, manipulated dimensions may be set to the upper or lower bound according to the instruction.

3 Safety Against Manipulations

The paper replaces gradient-based, network-dependent attacks with feature-guided black-box search, modeling adversarial-example crafting as a stochastic two-player game. Player I selects image features to minimize adversarial distance, while player II selects pixels and manipulations under cooperative, adversarial, or random behavior.

  • Feature-guided black-box approach: The approach searches for adversarial examples by manipulating image features recognized through human perception rather than following network gradients.SIFT features provide a perception-based guide without requiring network knowledge or training a surrogate network.
  • Two-player stochastic game: The game assigns player I feature selection and player II pixel selection plus a manipulation instruction, with player I minimizing distance to an adversarial example.Player II may cooperate, oppose player I, or sample pixels and instructions from the feature distribution.
  • Two-player stochastic game: Adversarial-example severity is defined by the L_k distance from the original image, and the objective is to find a minimum-distance adversarial example.The choice of L_k affects perceptual similarity.
  • Game-theoretic properties: Deterministic and memoryless strategies suffice for player I across cooperative, adversarial, and nature choices by player II.The result applies when player II uses max, min, or natural sampling behavior.
  • Game-theoretic properties: Although deciding safety is polynomial in the game-model size, the state space can grow as O(|P0|^h), making exact probabilistic computation impractical.The paper estimates roughly O(50000100) states for ImageNet-scale images and O(100020) for CIFAR10 and MNIST-scale images.

4 Monte Carlo Tree Search for Asymptotically Optimal Strategy

The paper uses Monte Carlo tree search to explore the feature-manipulation game and approach an optimal strategy asymptotically. Its theory connects optimal game values to minimum adversarial distance and supplies safety guarantees under grid and Lipschitz conditions.

  • MCTS procedure: MCTS gradually expands the game tree and uses UCB to balance exploration and exploitation, with simulations and reward backpropagation guiding search.Each simulation ends at a terminated node and assigns reward 1/sevα(α′).
  • Asymptotic optimality: MCTS is guaranteed to converge to an optimal solution when the finite game tree is fully expanded, although convergence may take a very long time.A practical 1/ϵ criterion stops after ⌈1/ϵ⌉ iterations without finding a less severe adversarial example.
  • MCTS procedure: The implementation accepts termination conditions, returns an adversarial example, and changes child selection for nature or adversarial player-II behavior.Nature samples the feature distribution, while an adversarial player selects the worst child.
  • Safety guarantees: For τ-grid adversarial examples, the optimal cooperative-player game value is no greater than the severity of any such example.The result follows because every τ-grid image can be reached by some game play.
  • Safety guarantees: If all τ-grid images are misclassification aggregators with respect to τ/2 and the optimal game severity exceeds d, no adversarial example exists within the tested region.The theorem supports progressively reducing τ to distinguish unsafe from safely verified cases.
  • Safety guarantees: For Lipschitz networks, τ ≤ 2ℓ/ℏ together with game severity greater than d guarantees that advN,k,d(α,c) is empty.ℏ is the Lipschitz constant and ℓ is the minimum confidence gap for a class change.

5 Experimental Results

Experiments evaluate the game-based black-box approach against established attacks, test convergence, and examine robustness in traffic-light and physical settings. The results show efficient adversarial generation, convergence on MNIST examples, severe Nexar vulnerabilities, and persistence across physical transformations.

  • Comparison with Existing Approaches: The game-based approach achieves a significant margin over optimised JSMA within limited computation time, although it does not outperform CW.The comparison uses termination conditions of 20 seconds and 60 seconds per image; JSMA requires several minutes per image and CW is reported as 10 times slower than JSMA.
  • Convergence in Limited Runs: Two MNIST images converge in fewer than 50 iterations when manipulations change 2 pixels, representing optimal player strategies.The convergence plots track best, current, and recent-window adversarial severity across iterations.
  • Evaluating Safety-Critical Networks: On Nexar traffic-light data, an average of 4.85 dimensions changes the classification, with each image processed in 0.303 seconds.The evaluated network scored above 90% accuracy, and testing 1000 images took 304 seconds including image input and output.
  • Evaluating Safety-Critical Networks: Targeted manipulation changes all 500 non-green Nexar classifications to green, with average L0 severity 3.23 and 0.21 seconds per image.The targeted procedure excludes images already classified as green and aims specifically for green predictions.
  • Physical-Domain Robustness: Physical-domain adversarial examples remain misclassified across multiple viewing angles and scales, including traffic lights classified as ovens, screens, microwaves, or a pizza.The experiment uses the scale- and rotation-invariant SIFT-based approach to test printed adversarial examples photographed under changed conditions.

6 Related Works

Related work covers white-box optimization and saliency-based attacks that use network information or optimization procedures. It also positions the paper against black-box approaches relying on surrogate models.

  • White-box heuristic approaches: White-box attacks such as L-BFGS, FGSM, and Carlini–Wagner optimize adversarial examples using network parameters, gradients, or related model information.Carlini–Wagner formulates attacks for L0, L2, and L∞ distances, while FGSM uses model parameters, inputs, and target labels.
  • White-box heuristic approaches: JSMA constructs a pixel-importance saliency map from a loss function, distinguishing it from optimization-based attacks.The paper compares its approach with JSMA because both use saliency distributions, while CW is optimization-based.

7 Conclusion

The paper presents a feature-guided black-box algorithm for evaluating DNN resilience, combining SIFT extraction, theoretical safety guarantees under restrictions, and efficient testing. Experiments across networks and benchmarks reveal many instabilities, while no tested network was found safe.

  • Conclusion: The proposed algorithm evaluates DNN resilience against adversarial examples without requiring network knowledge and uses SIFT for feature extraction.The paper develops a software package and demonstrates the approach on state-of-the-art networks and benchmark datasets.
  • Conclusion: The method provides a theoretical safety guarantee under certain restrictions and is designed for efficient, potentially real-time decision support.The appendix contains additional experimental results, method details, proofs, and network architectures.
  • Conclusion: The experiments detect many instabilities in state-of-the-art networks, but the authors have not found a network that is safe.The authors identify comparison with Bayesian inference for adversarial-example identification as future work.

A Empirical Results of the MCTS Algorithm

The paper evaluates MCTS convergence and adversarial-example generation across MNIST, CIFAR10, Nexar traffic-light, and ImageNet networks. Results include comparisons with existing attacks and rapid single-pixel misclassifications in the safety-critical Nexar setting.

  • Experiments assess MCTS performance and convergence on networks trained using MNIST, CIFAR10, Nexar Challenge, and ImageNet datasets.
  • MNIST: Figure 6 presents MNIST examples and MCTS performance plots for several digit misclassifications.
  • CIFAR10: Figure 7 compares the game-based approach with CW-L0 and JSMA on CIFAR10 networks.
  • Nexar Challenge: A single-pixel misclassification was found for many Nexar inputs in eight simulations, requiring about 0.3 seconds.
  • ImageNet: Experiments on VGG16 ImageNet networks show clear convergence of the algorithm.

B Proofs of Theorems

The theoretical section proves conditions under which the adversarial-image set is empty. The supplied empirical figures additionally document MCTS convergence and adversarial examples across digit, CIFAR10, traffic-light, and ImageNet cases.

  • The proof section establishes results for the two theorems introduced earlier in the paper.
  • If all τ-grid images aggregate misclassifications within τ/2 and the maximum-severity optimal strategy exceeds d, no adversarial examples exist.
  • The empirical figures show convergence plots and adversarial examples for MNIST, CIFAR10, Nexar traffic lights, and VGG16 ImageNet images.
  • The contradiction argument shows that any presumed adversarial image would yield a τ-grid adversarial image whose severity exceeds the allowed distance d.
  • For a Lipschitz network with constant ℏ, τ ≤ 2ℓ/ℏ together with maximum-strategy severity greater than d implies an empty adversarial-example set.

C Network Architectures in the Experiments

The experiments use specified network architectures and training parameters for MNIST, CIFAR10, ImageNet, and Nexar. SIFT supplies scale- and transformation-robust keypoints that support the feature-guided image representation.

  • The implementation details cover MNIST, CIFAR10, VGG16 ImageNet, and Nexar network architectures and training parameters.
  • Feature Detection: SIFT extracts image features through scale-space extrema detection, keypoint localization, and descriptor assignment without using neural networks.
  • Scale-Space Extrema Detection: Gaussian scale-space processing varies σ, filters some image noise, and enables detection of extrema at different sizes across octaves.
  • Scale-Space Extrema Detection: SIFT uses difference of Gaussians at different scales as noted in the implementation footnote.
  • Scale-Space Extrema Detection: Extrema detection is invariant to translation, scaling, and rotation and is minimally affected by noise and small distortions.
  • Keypoint Description: Localized extrema become keypoints with exact x and y coordinates, then receive size, orientation, local descriptors, and response strength.

E Intuition for Using Feature Detection for Safety Testing

The paper motivates feature-guided safety testing by linking adversarial vulnerability to image structure and composition. It combines deterministic SIFT features with mutable, query-updated saliency distributions while acknowledging that SIFT does not generalize.

  • Adversarial examples motivate testing whether artificial visual systems are sensitive to structural and compositional image changes.
  • SIFT provides deterministic, interpretable feature detection, whereas CNNs learn image-to-classification mappings whose dependence on basic structure is difficult to assess.
  • The method transforms keypoint information into a saliency distribution and updates its components using CNN-query outcomes through Monte Carlo saliency updating and MCTS.
  • Flexible saliency distributions help target crucial image elements, including pixel arrangements that can create or disguise structural cues.
  • SIFT is fast but does not generalize, and the approach does not rely on that generalization property.
  • The Nexar network is retrained using the SafeCV package, with its architecture and hyperparameters specified in the experimental materials.

G Overview of the Monte Carlo Tree Search Algorithm

The paper presents Monte Carlo tree search as a progressively updated exploration of adversarial-example manipulations, guided initially by SIFT-derived saliency policies. The search alternates tree expansion, simulation, and reward-based policy updates within the two-player game representation.

  • Tree representation: MCTS represents each image reachable after successive manipulations as a tree node, with children corresponding to manipulating particular pixels.A path through the tree corresponds to alternating moves by player I, which selects a keypoint, and player II, which selects and manipulates a pixel.
  • Tree exploration: MCTS maintains a partial tree of explored states while continuously updating the policies used to explore each state's children.The paper interprets this process as maintaining previous game plays and updating the players' strategies.
  • Initial policies: SIFT keypoints and Gaussian-mixture components provide initial saliency distributions and exploration policies for the two players.The search uses these policies as its starting point before updating them through tree exploration.
  • Selection and expansion: At an unexplored leaf, the initial policy selects a new child, expanding the tree before termination conditions are checked.This expansion step is illustrated as selecting a node from a previously unexplored root or leaf.
  • Simulation: After expansion, Monte Carlo simulation continues using the default policy until a termination condition is reached, without adding simulated nodes to the partial tree.The simulation applies the manipulation process while keeping the exploratory tree restricted to previously recorded states.
  • Backpropagation: The terminal reward updates policies along the explored path through an upper confidence bound, favoring consistently rewarding or underexplored nodes.The update is interpreted as backtracking through the game sequence and revising both players' exploration strategies.

H Lk Distance as a Manipulation Severity Metric

The paper treats L_k norms as imperfect but widely used measures of adversarial-manipulation severity. It emphasizes that changing k changes which kinds of image perturbations are favored and how severe they appear.

  • Metric motivation: Perceptual similarity lacks a perfect quantitative metric, making the distance measure central to finding minimally distinct adversarial examples.The paper therefore discusses the widely adopted L_k norm while noting that no single k is principled for all cases.
  • Effect of k: Small k values such as 0 or 1 favor sparse, intense changes, whereas large k values favor pervasive, slight pixel changes.Thus, the same manipulation can have different perceived severity depending on the selected norm.
  • Broader applicability: The method is presented for image inputs but can extend to diverse inputs when dimensions can be semantically partitioned into subsets serving as keypoint substitutes.Regular partitions allow saliency values to evolve toward a coarse-grained approximation of input features.
  • Initialization: MCTS can learn saliency from a random initial distribution, although this slows convergence toward an optimal strategy.Domain knowledge can instead provide an a priori saliency assignment, even when only approximate.
Loading 1710.07859v2…