Are Safety Guarantees in Neural Networks Safe? How to Compute Trustworthy Robustness Certifications

• URL: http://arxiv.org/abs/2606.23858v1
• Date: Mon, 22 Jun 2026 18:50:52 GMT
• Title: Are Safety Guarantees in Neural Networks Safe? How to Compute Trustworthy Robustness Certifications
• Abstract summary: We introduce the apothem measure and show how to compute apothem-optimal certifications in a linear number of calls to a NN verifier.<n>We also present the ParallelepipedoNN system, which we evaluate on the standard MNIST and Fashion MNIST benchmarks.
• Score: 10.268619734362547
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: A primary challenge in AI safety is the existence of adversarial examples -- slightly distorted inputs that cause a neural network (NN) to misclassify. To mitigate this problem, recent research focuses on the computation of robustness certifications, which, for a given input, determine the largest distortion the input may receive without breaking the network's prediction. Robustness certifications can be interpreted as an axis-aligned hyper-rectangle (multi-dimensional intervals). Most existing approaches focus on maximizing the certification's volume, but recent intractability results prohibit the computation of volume-optimal certifications in reasonable time. We introduce the apothem measure and show how to compute apothem-optimal certifications in a linear number of calls to a NN verifier (oracle) w.r.t. the input domain's diameter. Moreover, we prove that we cannot have a volume-optimal, oracle-based algorithm, even if we discard the oracle costs. Also, we introduce dual certifications -- an interval including all instances of a class -- thus providing apothem-minimum upper bounds to a robustness certification. Further, we present the ParallelepipedoNN system, which we evaluate on the standard MNIST and Fashion MNIST benchmarks. A preliminary comparison with existing work on the same datasets reveals at least two-fold improvement w.r.t. the minimum edge length.

Related papers

• $(\ ext{DNN})^2$: Doubly Non-Negative Relaxations for Deep Neural Networks [6.796081662087122]
  We propose a novel eigenvalueifiable procedure that searches the non-unique multiplier space for a valid certificate.<n>Experiments demonstrate that our approach produces bounds consistently tighter than the standard SDP method.
  arXiv  Detail & Related papers  (2026-08-25T15:48:32Z)
• Fast and Flexible Robustness Certificates for Semantic Segmentation [6.1903263165298945]
  We introduce a new class of certifiably robust semantic networks with built-in Lipschitz constraints.<n>Our approach unlocks real-time compatible certifiably robust semantic segmentation for the first time.<n>We find our approach to be around 600 times faster than randomized smoothing methods at inference with comparable certificates on an NVIDIA A100 GPU.
  arXiv  Detail & Related papers  (2025-12-03T10:10:16Z)
• Exact Certification of (Graph) Neural Networks Against Label Poisoning [50.87615167799367]
  We introduce an exact certification method for label flipping in Graph Neural Networks (GNNs)<n>We apply our method to certify a broad range of GNN architectures in node classification tasks.<n>Our work presents the first exact certificate to a poisoning attack ever derived for neural networks.
  arXiv  Detail & Related papers  (2024-11-30T17:05:12Z)
• Certified Robustness for Deep Equilibrium Models via Serialized Random Smoothing [12.513566361816684]
  Implicit models such as Deep Equilibrium Models (DEQs) have emerged as promising alternative approaches for building deep neural networks. Existing certified defenses for DEQs employing deterministic certification methods can not certify on large-scale datasets. We provide the first randomized smoothing certified defense for DEQs to solve these limitations.
  arXiv  Detail & Related papers  (2024-11-01T06:14:11Z)
• Towards General Robustness Verification of MaxPool-based Convolutional Neural Networks via Tightening Linear Approximation [51.235583545740674]
  MaxLin is a robustness verifier for MaxPool-based CNNs with tight linear approximation. We evaluate MaxLin with open-sourced benchmarks, including LeNet and networks trained on the MNIST, CIFAR-10, and Tiny ImageNet datasets.
  arXiv  Detail & Related papers  (2024-06-02T10:33:04Z)
• The #DNN-Verification Problem: Counting Unsafe Inputs for Deep Neural Networks [94.63547069706459]
  #DNN-Verification problem involves counting the number of input configurations of a DNN that result in a violation of a safety property. We propose a novel approach that returns the exact count of violations. We present experimental results on a set of safety-critical benchmarks.
  arXiv  Detail & Related papers  (2023-01-17T18:32:01Z)
• 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)
• Getting a-Round Guarantees: Floating-Point Attacks on Certified Robustness [19.380453459873298]
  Adversarial examples pose a security risk as they can alter decisions of a machine learning classifier through slight input perturbations. We show that these guarantees can be invalidated due to limitations of floating-point representation that cause rounding errors. We show that the attack can be carried out against linear classifiers that have exact certifiable guarantees and against neural networks that have conservative certifications.
  arXiv  Detail & Related papers  (2022-05-20T13:07:36Z)
• Smooth-Reduce: Leveraging Patches for Improved Certified Robustness [100.28947222215463]
  We propose a training-free, modified smoothing approach, Smooth-Reduce. Our algorithm classifies overlapping patches extracted from an input image, and aggregates the predicted logits to certify a larger radius around the input. We provide theoretical guarantees for such certificates, and empirically show significant improvements over other randomized smoothing methods.
  arXiv  Detail & Related papers  (2022-05-12T15:26:20Z)
• Second-Order Provable Defenses against Adversarial Attacks [63.34032156196848]
  We show that if the eigenvalues of the network are bounded, we can compute a certificate in the $l$ norm efficiently using convex optimization. We achieve certified accuracy of 5.78%, and 44.96%, and 43.19% on 2,59% and 4BP-based methods respectively.
  arXiv  Detail & Related papers  (2020-06-01T05:55:18Z)

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.