Efficient Preimage Approximation for Neural Network Certification
Anton Björklund, Mykola Zaitsev, Marta Kwiatkowska · 2025
Read Efficient Preimage Approximation for Neural Network Certification by Anton Björklund, Mykola Zaitsev, Marta Kwiatkowska (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-22798.txt.
Introduction
Bjorklund, Zaitsev, Morettin, and Kwiatkowska present PREMAP2 in twenty twenty-five, a tool for certifying neural networks. Use of AI in safety critical settings raises concern about bad or hostile inputs. Most checks bound the network output in the worst case. Preimage methods instead estimate what share of inputs meet a given specification.
Earlier preimage tools handled only simple fully connected networks of modest size. PREMAP2 adds better branching rules, adaptive Monte Carlo sampling, and reverse bound propagation. It also supports non uniform input priors and confidence intervals. These advances open settings that were out of reach before. Examples include patch attacks on image networks, where stickers or lighting hide parts of an image. The team shows uses in reliability, robustness, interpretability, and fairness.
Catalog record
| CREATOR | Anton Björklund, Mykola Zaitsev, Marta Kwiatkowska |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-22798
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Efficient Preimage Approximation for Neural Network Certification Anton Björklund, Mykola Zaitsev, Marta Kwiatkowska 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. † † paperid: 3853 † † orcid: 0000-0002-7749-2918 † † orcid: 0000-0002-7547-5284 † † orcid: 0000-0001-9022-7599 1 Introduction The widespread deployment of AI technologies places significant demands on their trustworthiness and reliability, which are of particular concern in high-stakes applications, as recognized in the EU AI Act [ 9 ] . Much effort has been devoted to ensuring safety and security of AI applications involving neural networks (NNs) because of their instability to adversarial perturbations ( Goodfellow et al. 2014 ) . A particularly challenging real-world example are “patch attacks” on images, such as traffic signs. In Figure 1 , we show two examples of physical patch attacks: real graffiti on a traffic sign Eykholt et al. 2018 (left) and a patch caused by a sunbeam Cao et al. 2024 (middle), which can result from a specific adversarial manipulation of the image or for natural reasons. Figure 1: Examples of physical patch attacks. Left: real graffiti Eykholt et al. 2018 . Middle: sunbeam Cao et al. 2024 . Right: our abstraction of a patch attack. The above examples highlight the importance of studying robustness of image recognition models to adversarial patch attacks for applications such as safe autonomous driving or biometric security software. To this end, a wide range of methodologies have been developed for neural networks to enhance their robustness, either via (certified) adversarial training Shi et al. 2021 ; Mao et al. 2024b or designing certifiable Xiang et al. 2024 or empirical Wei et al. 2024 defences. An alternative method is to certify robustness by computing deterministic Huang et al. 2017 ; Katz et al. 2017 or probabilistic Webb et al. 2018 ; Yang et al. 2021 guarantees on the network outputs. A drawback of certifiable defences is their relatively high inference time, although there are viable trade-offs Xiang et al. 2024 ; Xiang et al. 2023 , Similarly to formal verification, certification is more powerful than adversarial training or empirical defences because it can guarantee that the network output is correct for all inputs in a given region. Using the patch attack in Figure 1 (right) as an illustration, and assuming the patch is placed in a fixed position, certification aims to guarantee the prediction for all possible (RGB) colour values. Adversarial robustness certification methods commonly work by bounding the outputs of the neural network for a given input subdomain, which may yield loose bounds for the resulting output over-approximation. A recently developed alternative approach focuses instead on bounding the preimage of a given output specification (typically a polyhedron), either through over-approximating the preimage Kotha et al. 2023 ; Zhang et al. 2024b or under-approximating it Zhang et al. 2024a ; Zhang et al. 2024b . Preimage under-approximation, in contrast to over-approximation, offers stronger compliance guarantees, since all inputs in the computed approximation satisfy the guarantee, and quantitative verification, i.e., estimating the proportion of inputs that meet the specification, which can directly serve as a reliability certificate. However, despite the positive experimental results reported in Zhang et al. 2024a ; Zhang et al. 2024b , existing methods do not scale to high dimensions, such as commonly used convolutional neural networks, which is compounded by the prohibitive size of the branching computation tree. In this paper, we aim to significantly improve the scalability and computational performance of the state-of-the-art preimage approximation algorithm PREMAP Zhang et al. 2024a ; Zhang et al. 2024b . This raises a number of challenges, which we resolve by careful analysis that allowed us to select effective algorithmic improvements such as bound tightening, optimized branching and refinement, as well as adaptive Monte Carlo sampling. We experimentally evaluate our method on a range of case studies, showing that our method is able to complete almost twice the number of cases solved using the original method. Now we are able to certify robustness to patch attacks for convolutional networks applied on GTSRB (traffic signs), SVHN (house numbers) and CIFAR (standard image benchmark), which were not feasible with the original PREMAP. We also provide a comparison with the previous version of PREMAP on controller benchmarks, showing at least an order of magnitude improvements in running time. Additionally, we demonstrate how PREMAP can be used for interpretability, to investigate important regions of the input. Our results demonstrate the potential of preimage approximation methodology for exploitation in reliability and robustness certification. 2 Background This section presents the relevant background. In Section 2.1 , we define preliminary concepts and provide an overview of the PREiMage APproximation (PREMAP) method ( Zhang et al. 2024a ; Zhang et al. 2024b ) , focusing on key aspects needed for our algorithmic improvements; for more detail of the techniques please refer to ( Zhang et al. 2024b ) . Related works are discussed in Section 2.2 . 2.1 Preliminaries Neural networks. We use f:\mathbb{R}^{d}\rightarrow\mathbb{R}^{m} to denote a feed-forward neural network, where f(\mathbf{x})=\mathbf{y} . For layer l , \mathbf{W}^{l} denotes the weight matrix, \mathbf{b}^{l} the bias, \mathbf{z}^{l} the pre-activation neurons, and h^{l}(\mathbf{z}^{l}) the activation function, such that \mathbf{z}^{l}=\mathbf{W}^{l}h^{l-1}(\mathbf{z}^{l-1})+\mathbf{b}^{l} . We use under- and overlines to denote the lower and upper bounds, e.g., \underline{\mathbf{x}}_{i}\leq\mathbf{x}_{i}\leq\overline{\mathbf{x}}_{i} . In this paper we focus on ReLU neural networks, where h^{l}(\mathbf{z}^{l})=\text{ReLU}(\mathbf{z}^{l})=\max(\mathbf{z}^{l},0) is applied element-wise, but our method can also be generalized to other activation functions that can be bounded by linear functions Zhang et al. 2018 ; Chevalier et al. 2024 . Linear relaxation. Linear relaxation is used to transform non-convex neuron constraints into linear programs, which provide effective means to approximate a neural network to ensure tractability of analysis. As shown in Figure 2 , given concrete lower and upper bounds \underline{\mathbf{z}}^{l}\leq\mathbf{z}^{l}\leq\overline{\mathbf{z}}^{l} on the pre-activation values of layer l , there are three cases to consider. When \overline{\mathbf{z}}^{l}_{i}\leq 0 then h^{l}(\mathbf{z}^{l}_{i})=0 and the neuron is inactive . Similarly, when \underline{\mathbf{z}}^{l}_{i}\geq 0 then h^{l}(\mathbf{z}^{l}_{i})=\mathbf{z}^{l}_{i} and the neuron is active . Otherwise, the neuron is unstable and can be bounded by \alpha\mathbf{z}^{l}_{i}\leq h^{l}(\mathbf{z}^{l}_{i})\leq(\mathbf{z}^{l}_{i}-\underline{\mathbf{z}}^{l}_{i}){\overline{\mathbf{z}}^{l}_{i}}/{(\overline{\mathbf{z}}^{l}_{i}-\underline{\mathbf{z}}^{l}_{i})}, (1) where \alpha is any value in [0,1] . Inactive \mathbf{z}^{l}_{i} h^{l}(\mathbf{z}^{l}_{i}) \underline{\mathbf{z}}^{l}_{i} \overline{\mathbf{z}}^{l}_{i} Active \mathbf{z}^{l}_{i} h^{l}(\mathbf{z}^{l}_{i}) \underline{\mathbf{z}}^{l}_{i} \overline{\mathbf{z}}^{l}_{i} Unstable \mathbf{z}^{l}_{i} h^{l}(\mathbf{z}^{l}_{i}) \underline{\mathbf{z}}^{l}_{i} \overline{\mathbf{z}}^{l}_{i} Figure 2: Linear bounds for inactive, active and unstable ReLU neurons. For the neural network f , linear relaxation is used to compute linear lower and upper bounds for the output like \underline{\mathbf{A}}\mathbf{x}+\underline{\mathbf{b}}\leq f(\mathbf{x})\leq\overline{\mathbf{A}}\mathbf{x}+\overline{\mathbf{b}}, (2) for a given bounded