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

• 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)
• 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)
• 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)

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.