Efficient Preimage Approximation for Neural Network Certification

• URL: http://arxiv.org/abs/2505.22798v1
• Date: Wed, 28 May 2025 19:13:56 GMT
• Title: Efficient Preimage Approximation for Neural Network Certification
• Authors: Anton Björklund, Mykola Zaitsev, Marta Kwiatkowska,
• Abstract summary: A challenging real-world use case is certification against patch attacks''<n>One approach to certification, which also gives quantitative coverage estimates, utilizes preimages of neural networks.<n>Preimage approximation methods, including the state-of-the-art PREMAP algorithm, struggle with scalability.<n>This paper presents novel algorithmic improvements to PREMAP involving tighter bounds, adaptive Monte Carlo sampling, and improved branchings.
• Score: 16.48296008910141
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: The growing reliance on artificial intelligence in safety- and security-critical applications demands effective neural network certification. A challenging real-world use case is certification against ``patch attacks'', where adversarial patches or lighting conditions obscure parts of images, for example traffic signs. One approach to certification, which also gives quantitative coverage estimates, utilizes preimages of neural networks, i.e., the set of inputs that lead to a specified output. However, these preimage approximation methods, including the state-of-the-art PREMAP algorithm, struggle with scalability. This paper presents novel algorithmic improvements to PREMAP involving tighter bounds, adaptive Monte Carlo sampling, and improved branching heuristics. We demonstrate efficiency improvements of at least an order of magnitude on reinforcement learning control benchmarks, and show that our method scales to convolutional neural networks that were previously infeasible. Our results demonstrate the potential of preimage approximation methodology for reliability and robustness certification.

Related papers

• Lightweight CNN Model Hashing with Higher-Order Statistics and Chaotic Mapping for Piracy Detection and Tamper Localization [9.859893936091813]
  Perceptual hashing has emerged as an effective approach for identifying pirated models.<n>We propose a lightweight CNN model hashing technique that integrates higher-order statistics (HOS) features with a chaotic mapping mechanism.
  arXiv  Detail & Related papers  (2025-10-31T03:04:10Z)
• Knowledge-Informed Neural Network for Complex-Valued SAR Image Recognition [51.03674130115878]
  We introduce the Knowledge-Informed Neural Network (KINN), a lightweight framework built upon a novel "compression-aggregation-compression" architecture.<n>KINN establishes a state-of-the-art in parameter-efficient recognition, offering exceptional generalization in data-scarce and out-of-distribution scenarios.
  arXiv  Detail & Related papers  (2025-10-23T07:12:26Z)
• Efficient Reachability Analysis for Convolutional Neural Networks Using Hybrid Zonotopes [4.32258850473064]
  Existing set propagation-based reachability analysis methods for feedforward neural networks often struggle to achieve both scalability and accuracy.<n>This work presents a novel set-based approach for computing the reachable sets of convolutional neural networks.
  arXiv  Detail & Related papers  (2025-03-13T19:45:26Z)
• PREMAP: A Unifying PREiMage APproximation Framework for Neural Networks [30.701422594374456]
  We present a framework for preimage abstraction that produces under- and over-approximations of any polyhedral output set. We evaluate our method on a range of tasks, demonstrating significant improvement in efficiency and scalability to high-input-dimensional image classification tasks.
  arXiv  Detail & Related papers  (2024-08-17T17:24:47Z)
• Policy Verification in Stochastic Dynamical Systems Using Logarithmic Neural Certificates [7.9898826915621965]
  We consider the verification of neural network policies for discrete-time systems with respect to reach-avoid specifications.<n>Existing approaches for such a verification task rely on computed Lipschitz constants of neural networks.<n>We present two key contributions to obtain smaller Lipschitz constants than existing approaches.
  arXiv  Detail & Related papers  (2024-06-02T18:19:19Z)
• Deep Neural Networks Tend To Extrapolate Predictably [51.303814412294514]
  neural network predictions tend to be unpredictable and overconfident when faced with out-of-distribution (OOD) inputs. We observe that neural network predictions often tend towards a constant value as input data becomes increasingly OOD. We show how one can leverage our insights in practice to enable risk-sensitive decision-making in the presence of OOD inputs.
  arXiv  Detail & Related papers  (2023-10-02T03:25:32Z)
• Joint Hierarchical Priors and Adaptive Spatial Resolution for Efficient Neural Image Compression [11.25130799452367]
  We propose an absolute image compression transformer (ICT) for neural image compression (NIC) ICT captures both global and local contexts from the latent representations and better parameterize the distribution of the quantized latents. Our framework significantly improves the trade-off between coding efficiency and decoder complexity over the versatile video coding (VVC) reference encoder (VTM-18.0) and the neural SwinT-ChARM.
  arXiv  Detail & Related papers  (2023-07-05T13:17:14Z)
• Provable Preimage Under-Approximation for Neural Networks (Full Version) [27.519993407376862]
  We propose an efficient anytime algorithm for generating symbolic under-approximations of the preimage of any polyhedron output set for neural networks. Empirically, we validate the efficacy of our method across a range of domains, including a high-dimensional MNIST classification task. We present a sound and complete algorithm for the former, which exploits our disjoint union of polytopes representation to provide formal guarantees.
  arXiv  Detail & Related papers  (2023-05-05T16:55:27Z)
• Certified Interpretability Robustness for Class Activation Mapping [77.58769591550225]
  We present CORGI, short for Certifiably prOvable Robustness Guarantees for Interpretability mapping. CORGI is an algorithm that takes in an input image and gives a certifiable lower bound for the robustness of its CAM interpretability map. We show the effectiveness of CORGI via a case study on traffic sign data, certifying lower bounds on the minimum adversarial perturbation.
  arXiv  Detail & Related papers  (2023-01-26T18:58:11Z)
• Quantization-aware Interval Bound Propagation for Training Certifiably Robust Quantized Neural Networks [58.195261590442406]
  We study the problem of training and certifying adversarially robust quantized neural networks (QNNs) Recent work has shown that floating-point neural networks that have been verified to be robust can become vulnerable to adversarial attacks after quantization. We present quantization-aware interval bound propagation (QA-IBP), a novel method for training robust QNNs.
  arXiv  Detail & Related papers  (2022-11-29T13:32:38Z)
• Can pruning improve certified robustness of neural networks? [106.03070538582222]
  We show that neural network pruning can improve empirical robustness of deep neural networks (NNs) Our experiments show that by appropriately pruning an NN, its certified accuracy can be boosted up to 8.2% under standard training. We additionally observe the existence of certified lottery tickets that can match both standard and certified robust accuracies of the original dense models.
  arXiv  Detail & Related papers  (2022-06-15T05:48:51Z)
• A Robust Backpropagation-Free Framework for Images [47.97322346441165]
  We present an error kernel driven activation alignment algorithm for image data. EKDAA accomplishes through the introduction of locally derived error transmission kernels and error maps. Results are presented for an EKDAA trained CNN that employs a non-differentiable activation function.
  arXiv  Detail & Related papers  (2022-06-03T21:14:10Z)
• NUQ: Nonparametric Uncertainty Quantification for Deterministic Neural Networks [151.03112356092575]
  We show the principled way to measure the uncertainty of predictions for a classifier based on Nadaraya-Watson's nonparametric estimate of the conditional label distribution. We demonstrate the strong performance of the method in uncertainty estimation tasks on a variety of real-world image datasets.
  arXiv  Detail & Related papers  (2022-02-07T12:30:45Z)
• Robustness against Adversarial Attacks in Neural Networks using Incremental Dissipativity [3.8673567847548114]
  Adversarial examples can easily degrade the classification performance in neural networks. This work proposes an incremental dissipativity-based robustness certificate for neural networks.
  arXiv  Detail & Related papers  (2021-11-25T04:42:57Z)
• Increasing the Confidence of Deep Neural Networks by Coverage Analysis [71.57324258813674]
  This paper presents a lightweight monitoring architecture based on coverage paradigms to enhance the model against different unsafe inputs. Experimental results show that the proposed approach is effective in detecting both powerful adversarial examples and out-of-distribution inputs.
  arXiv  Detail & Related papers  (2021-01-28T16:38:26Z)
• Enabling certification of verification-agnostic networks via memory-efficient semidefinite programming [97.40955121478716]
  We propose a first-order dual SDP algorithm that requires memory only linear in the total number of network activations. We significantly improve L-inf verified robust accuracy from 1% to 88% and 6% to 40% respectively. We also demonstrate tight verification of a quadratic stability specification for the decoder of a variational autoencoder.
  arXiv  Detail & Related papers  (2020-10-22T12:32:29Z)
• Bayesian Optimization with Machine Learning Algorithms Towards Anomaly Detection [66.05992706105224]
  In this paper, an effective anomaly detection framework is proposed utilizing Bayesian Optimization technique. The performance of the considered algorithms is evaluated using the ISCX 2012 dataset. Experimental results show the effectiveness of the proposed framework in term of accuracy rate, precision, low-false alarm rate, and recall.
  arXiv  Detail & Related papers  (2020-08-05T19:29:35Z)
• Debona: Decoupled Boundary Network Analysis for Tighter Bounds and Faster Adversarial Robustness Proofs [2.1320960069210484]
  Neural networks are commonly used in safety-critical real-world applications. Proving that either no such adversarial examples exist, or providing a concrete instance, is therefore crucial to ensure safe applications. We provide proofs for tight upper and lower bounds on max-pooling layers in convolutional networks.
  arXiv  Detail & Related papers  (2020-06-16T10:00:33Z)
• Liver Segmentation in Abdominal CT Images via Auto-Context Neural Network and Self-Supervised Contour Attention [6.268517865399281]
  We introduce a CNN for liver segmentation on abdominal computed tomography (CT) images. To improve the generalization performance, we initially propose an auto-context algorithm in a single CNN. The proposed network showed the best generalization performance among the networks.
  arXiv  Detail & Related papers  (2020-02-14T07:32:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.