WorksComputer Science

Robustness Verification against Patch Attacks via Group-Lasso Semidefinite Relaxation

Yukina Nakagawa, Takami Sato, Ken Kobayashi, Kazuhide Nakata

Published Nov 03, 2026Fresh — added to the Hub within the last 30 daysv120 min read

AI contributions

Not recorded for this paper

Abstract

Robustness verification is essential for ensuring the safety and security of neural networks, but current methods focus heavily on norm-ball attacks, which do not adequately model typical real-world threats that present physical perturbations, known as patch attacks. A naive approach requires computationally prohibitive enumeration of all possible patch positions. To address the challenge, we propose a novel neural network verification method specialized to the patch-attack threat. Instead of enumerating patch locations, we first model the patch attack with group-wise sparsity and formulate its verification methods as a mixed-integer semidefinite program (MISDP) by applying SDP relaxation to the neural network. We then propose three relaxations, including Group-Lasso relaxation, that remove the integer variables while preserving the sparse, group-wise structure of the original attack, enabling substantially efficient verification. Our empirical analysis demonstrates that the proposed relaxations require less than 3% of the computation time of the original MISDP, while the Group-Lasso relaxation incurs only a 0.34% average increase in the objective value over the original formulation. Furthermore, Group-Lasso achieves a verified rate of 91%, compared with under 70% for prior methods.

Introduction

Deep Neural Networks (DNNs) have achieved remarkable success in many fields and have been widely deployed in safety-critical vision applications such as autonomous driving [4, 24] and medical image analysis [11, 33]. However, DNNs are widely known to be vulnerable to adversarial attacks [8, 14, 29] that intentionally modify an input with subtle malicious perturbations to induce an incorrect prediction. The vulnerability to adversarial attacks has raised critical concerns about their reliability and security, spurring extensive research into DNN verification [10, 15, 30, 32].

DNN verification has traditionally focused on $L_p$ norm-ball attacks. For an input image $\boldsymbol{x}^{*}$ , the verifier considers all possible perturbed images $\boldsymbol{x}$ under a perturbation radius $\epsilon$ , i.e., $\lVert\boldsymbol{x}-\boldsymbol{x}^{*}\rVert_p \le\epsilon$ , and determines whether the model prediction remains unchanged. This verification problem is generally solved as an optimization problem. While the $L_p$ norm-ball assumption can cover broader types of perturbations, it does not adequately represent the threat model of practical physical-world attacks [6, 28] in which an attacker modifies only a localized region, for example by attaching a sticker or placing a patterned object on part of an image. A naive approach to patch attacks enumerates possible patch locations and solves a verification problem for each candidate location, but the computational cost grows exponentially with the number of possible attack locations.

To address this limitation, we propose a novel DNN verification method specialized for patch attacks. Instead of enumerating patch locations, we model the patch attack with group-wise sparsity [12]. We then incorporate the patch position as a variable within a single mixed-integer program (MIP), which is an exact model but is not practical due to its high combinatorial complexity. We thus relax the problem with an SDP relaxation [16] and three proposed relaxations for the group-wise patch attack. We propose a full-group naive relaxation that permits perturbations in every group, an $L_2$ -norm relaxation that replaces the group-wise constraints with a global $L_2$ constraint, and a Group-Lasso relaxation that constrains the sum of the $L_2$ norms of the group-wise perturbations. All three relaxed problems provide a valid guarantee for the original attack model.

We evaluate the proposed formulations from both computational and verification perspectives. We found that all three relaxations require less than 3% of the computation time of the original problem in the evaluated settings. Group-Lasso relaxation achieves an average objective increase of only 0.34% in the evaluated setting, substantially outperforming the Full-Group and $L_2$ -norm relaxations. These results indicate that preserving the group structure of the attack is important for obtaining a tight relaxation. Group-Lasso relaxation also demonstrated high verification capability; while existing methods achieve verification rates of $\leq70\%$ , it was able to verify 91% of the samples on the adversarially trained model. We conduct qualitative analysis and confirm that the perturbations considered in Group-Lasso relaxation are locally grouped and concentrated around the digit character, as shown in Figure 1.

Figure 1. Adversarial perturbations generated during verification. Red and blue mean positive- and negative-direction perturbations, respectively. Compared to existing baselines (MILP and IBP) that spread perturbations across the entire image, our proposed Group-Lasso relaxation restricts perturbations to localized foreground regions, closely matching the localized patch attack threat model.

Our main contributions are summarized as follows:

We are the first to formulate DNN verification specialized for patch attacks with group-wise sparsity modeling. We first formulate it as an exact MIP problem and design an effective relaxation enabling efficient verification.

We design three relaxations for the group-wise modeling with theoretical soundness guarantees. In particular, Group-Lasso relaxation explicitly preserves the group-sparse structure and provides a substantially tighter approximation than the simpler relaxations.

We demonstrate the high efficiency and effectiveness of our proposed methods, which require at most 3% of the computation time of the original MISDP. Group-Lasso relaxation differs from the exact formulation by only 0.34% in objective value and achieves a verification rate of up to 91%, outperforming existing methods, whose verification rates are at most 70%.

Related Work

Adversarial Attacks

Deep Neural Networks (DNNs) are widely known to be vulnerable to adversarial attacks [8, 14, 29], where carefully crafted perturbations alter model predictions while remaining imperceptible to humans. To bound perturbation magnitude, traditional attacks are typically formulated within an $L_p$ -norm ball, such as $L_\infty$ [21] or $L_2$ [8] balls.

Beyond global perturbation, recent work has demonstrated that effective attacks can be realized by perturbing only a localized region of the input image [19, 27, 28]. We refer to this threat model as patch attacks. Attacks based on $L_p$ -norm balls perturb the entire image, which would require physically perturbing everything within the camera’s field of view, an unrealistic requirement in the physical world. An attacker would therefore need to compromise the system itself. In contrast, patch attacks allow an adversary to introduce localized physical perturbations by placing patches within the camera’s field of view [6, 26] or attaching stickers to target objects [28], without compromising the system. Owing to this practicality in real-world scenarios, patch attacks have drawn significant attention.

This emerging threat model has motivated the development of certified defenses against patch attacks [9, 17, 22, 34, 35]. Chiang et al. [9] proposed a certified defense that enumerates possible patch locations and performs verification for each location. Levine et al. [17] developed a deterministic certification approach that restricts the set of possible patch regions and verifies the resulting cases. BagCert [22] avoids explicit enumeration of all patch locations by partitioning the input image into multiple regions and performing certified defense for CNNs. However, existing approaches focus on developing certified defenses, not verification for all possible attacks. None of the prior studies has studied DNN verification methods specialized for patch attacks. This gap motivates our study.

DNN Verification Problem

DNN verification aims to determine whether a model preserves its prediction for all inputs within a specified perturbation set. Given an input image $x^*$ with correct class label $y^*$ , the model $f:\mathbb{R}^n \to\mathbb{R}^C$ is certified as robust against the attack of interest if its predicted class remains unchanged throughout the perturbation set $\mathcal{X}$ centered at $\boldsymbol{x}^*$ . We formulate the DNN verification problem as the following decision problem:

\forall x \in\mathcal{X},\quad\underset{i\in\{1,2,\ldots,C\}}{\arg\max}\ f(x)=\underset{i\in\{1,2,\ldots,C\}}{\arg\max}\ f(x^*)=y^*. \tag*{(1)}

For an $L_p$ norm ball, the perturbation set can be defined as follows:

\mathcal{X}_{L_p}=\{x\mid\lVert x-x^*\rVert_p\leq\varepsilon\}. \tag*{(2)}

DNN verification has been studied through both complete and incomplete verification approaches. Complete verification [2, 5, 10, 15, 20, 30] seeks to solve Problem Eq. (1) exactly, typically using mixed-integer programming (MIP) [30, 32] or satisfiability modulo theories (SMT) [10, 15]. Although these methods can provide exact verification, their computational cost is generally unaffordable for practical use.

Incomplete verification instead replaces the original verification problem with a relaxed problem that is computationally more tractable. The relaxed problem is constructed as a necessary condition for the original verification problem: consequently, if the relaxed problem is verified, then the original DNN verification problem is also verified. However, this relaxation can introduce false negatives, meaning that a model may be certifiably robust under complete verification even when the incomplete verifier fails to establish robustness.

Methodology

We first formalize the patch-attack threat model using group-wise sparsity (§ 3.1) and derive an exact mixed-integer program that jointly optimizes the perturbation and patch location (§ 3.2). We then apply an SDP relaxation to obtain a more tractable MISDP (§ 3.3), and finally propose three relaxations that remove the remaining combinatorial structure (§ 3.4).

Patch Attack Modeling

We model the patch attack with group-wise sparsity [12]. Let the pixel index set of an input image be $\mathcal{P}=\{1,2,\ldots,n_0\}$ . We partition $\mathcal{P}$ into $m$ non-overlapping groups:

\mathcal{G}=\{1,2,\ldots,m\}, \tag*{(3)}

\mathcal{P}_i\cap\mathcal{P}_j=\varnothing\quad(i,j\in\mathcal{G},\ i\ne j), \tag*{(4)}

\bigcup_{g\in\mathcal{G}}\mathcal{P}_g=\mathcal{P}. \tag*{(5)}

where $\mathcal{P}_g$ denotes the set of pixels belonging to the group $g$ . Eq. (3b) and Eq. (3c) respectively guarantee the non-overlap and coverage of the partition.

The attacker can select at most $k$ groups to perturb. The verifier cannot know which groups are selected. The perturbation applied to each selected group is bounded by $\varepsilon$ . Let $\boldsymbol{G}\in\{0,1\}^m$ denote the group-selection vector, where $G^{(g)}=1$ indicates that group $g$ is attacked. For an original input $\boldsymbol{x}_0^*$ , the corresponding perturbation set is defined as

\lVert x_0^{(g)}-x_0^{*(g)}\rVert_2\leq\varepsilon G^{(g)}\quad(g\in\mathcal{G}), \tag*{(6)}

\mathbf{1}^{\mathsf{T}}\boldsymbol{G}=k, \tag*{(7)}

\boldsymbol{G}\in\{0,1\}^m. \tag*{(8)}

The vectors $x_0^{(g)}$ and $x_0^{*(g)}$ denote the sub-vectors of the perturbed and original images restricted to the index set $\mathcal{P}_g$ of group $g$ . The first constraint allows a perturbation of radius at most $\varepsilon$ only for an attacked group, while the second constraint restricts the attacker to at most $k$ groups. The binary vector $\boldsymbol{G}\in\{0,1\}^m$ indicates which groups are attacked, where $G^{(g)}=1$ if group $g$ is attacked and $G^{(g)}=0$ otherwise.

Patch Attack Complete Verification Modeling

Given the perturbation set defined in Eq. (4), robustness verification can be formulated as an optimization problem that jointly searches for the adversarial perturbation and its attack location. For a given target class, we maximize the difference between the target and true class scores:

\max_{\{x_i\}_{i=0}^{L},\boldsymbol{G}}\quad x_L[j]-x_L[j^*] \tag*{(9)}

\text{s.t.}\quad x_L=f(x_0), \tag*{(10)}

\lVert x_0^{(g)}-x_0^{*(g)}\rVert_2\leq\varepsilon G^{(g)},\quad\forall g\in\mathcal{G}, \tag*{(11)}

\mathbf{1}^{\mathsf{T}}\boldsymbol{G}=k, \tag*{(12)}

\boldsymbol{G}\in\{0,1\}^m, \tag*{(13)}

where $j^*$ and $j$ ( $j\ne j^*$ ) denote the true and target labels, and $x_L[j]$ represents the $j$ -th entry of the vector $x_L$ . $x_0$ denotes the perturbed input and $\boldsymbol{G}$ determines the attacked groups. If the optimal value is non-positive, the model is verified to be robust against the specified target class; otherwise, the existence of a patch attack cannot be ruled out.

For an $L$ -layer ReLU network, Eq. (5) can be formulated as an extension of the existing mixed-integer program (MIP)based complete verification [15]:

\begin{aligned} \max_{\{x_i\}_{i=0}^{L},G}\quad& \mathbf{c}^{\top}\mathbf{x}_L+c_0 \\ \mathrm{s.t.}\quad& \mathbf{x}_{i+1}\ge0,\quad(i\in\mathbb{I}_{[0,L-1]}),\\ & \mathbf{x}_{i+1}\ge W_i\mathbf{x}_i+\mathbf{b}_i\quad(i\in\mathbb{I}_{[0,L-1]}),\\ & \mathbf{x}_{i+1}\le(1-z_i)M+W_i\mathbf{x}_i+\mathbf{b}_i\quad(i\in\mathbb{I}_{[0,L-1]}),\\ & \mathbf{x}_{i+1}\le Mz_i\quad(i\in\mathbb{I}_{[0,L-1]}),\\ & 0\le\mathbf{x}_0\le1,\\ & z_i\in\{0,1\}^{n_i}\quad(i\in\mathbb{I}_{[0,L-1]}),\\ & \left\|\mathbf{x}_0^{(g)}-\mathbf{x}_0^{*(g)}\right\|_2\le\varepsilon G^{(g)}\quad(g\in\mathcal{G}),\\ & \mathbf{1}^{\top}G=k,\quad G\in\{0,1\}^{m}. \tag*{(14)} \end{aligned}

where $\mathbf{c}^{\top}=W_L(j,:)-W_L(j^*,:)$ and $c_0=b_L[j]-b_L[j^*]$ , $\mathbb{I}_{[0,L-1]}=\{0,1,\ldots,L-1\}$ , and $M$ represents a sufficiently large constant derived from the bounds on the pre-activation values. The first four constraints encode the ReLU activations using binary variables $z_i$ , while Eq. (14) restricts the image pixels to their valid range. The remaining constraints define the group-wise patch attack. Since Eq. (14) introduces a binary variable for every ReLU unit, its computational cost grows rapidly with the network size, and directly applying this approach to large-scale neural network models is impractical.

Incomplete Verification via SDP Relaxation

We introduce our incomplete verification for the patch attack in this section. Firstly, we replace the ReLU representations, Eq. (14) and Eq. (14), with quadratic constraints to enable SDP relaxation [25]. By retaining the binary group-selection variable $G$ , the resulting mixed-integer semidefinite program (MISDP) preserves the exact group-wise patch attack model. Compared to Eq. (14), this MISDP eliminates binary variables for individual neurons, drastically reducing the total number of binary decision variables from $\sum_{i=0}^{L-1}n_i$ to the number of groups $m$ .

Following [25], we introduce a vector

\widetilde{\mathbf{x}}=(1,\mathbf{x}_0^{\top},\mathbf{x}_1^{\top},\ldots,\mathbf{x}_L^{\top})^{\top}\in\mathbb{R}^{1+\sum_{i=0}^{L}n_i} \tag*{(15)}

that concatenates 1 and the activation vectors of all layers, and a symmetric matrix

P=\widetilde{\mathbf{x}}\widetilde{\mathbf{x}}^{\top}\in\mathbb{S}^{1+\sum_{i=0}^{L}n_i}. \tag*{(16)}

Then, Eq. (5) is equivalently reformulated with respect to the variable $P$ with a rank constraint $\operatorname{rank}(P)=1$ . By removing the rank constraint, we obtain the following MISDP:

\begin{aligned} \max_{P,G}\quad& \mathbf{c}^{\top}P[\mathbf{x}_L]+c_0\\ \mathrm{s.t.}\quad& P[\mathbf{x}_{i+1}]\ge0\quad(i\in\mathbb{I}_{[0,L-1]}),\\ & P[\mathbf{x}_{i+1}]\ge W_iP[\mathbf{x}_i]+\mathbf{b}_i\quad(i\in\mathbb{I}_{[0,L-1]}),\\ & \operatorname{diag}\left(P[\mathbf{x}_{i+1}\mathbf{x}_{i+1}^{\top}]-W_iP[\mathbf{x}_i\mathbf{x}_{i+1}^{\top}]-\mathbf{b}_i\odot P[\mathbf{x}_{i+1}]\right)=0\quad(i\in\mathbb{I}_{[0,L-1]}),\\ & \operatorname{diag}\left(P[\mathbf{x}_i\mathbf{x}_i^{\top}]-(\mathbf{l}_i+\mathbf{u}_i)\odot P[\mathbf{x}_i]+\mathbf{l}_i\odot\mathbf{u}_i\right)\le0\quad(i\in\mathbb{I}_{[0,L]}),\\ & 0\le P[\mathbf{x}_0]\le1,\\ & \left\|P[\mathbf{x}_0^{(g)}]-\mathbf{x}_0^{*(g)}\right\|_2\le\varepsilon G^{(g)}\quad(g\in\mathcal{G}),\\ & \mathbf{1}^{\top}G=k,\quad G\in\{0,1\}^{m},\\ & P[1]=1,\quad P\succeq0. \tag*{(17)} \end{aligned}

where we use the same indexing notation $P[\cdot]$ as in [25], and $\mathbf{l}_i$ and $\mathbf{u}_i$ denote the lower and upper bounds of the pre-activation values of layer $i$ , obtained by a lightweight method such as bound propagation [31, 36]. In addition, for the group-wise constraints we write $P[\mathbf{x}_0^{(g)}]$ for the sub-block of $P[\mathbf{x}_0]$ restricted to the index set $\mathcal{P}_g$ of group $g$ .

Proposed Relaxation for Group-Wise Sparsity

The MISDP (9) eliminates the binary variables associated with the ReLU activations, but retains the binary attack-selection variable $G$ . This remaining combinatorial structure still limits the scalability of the verification problem. To address these limitations, we further relax the group-wise patch attack by removing the binary variable $G$ . Specifically, we construct a convex perturbation set $\widetilde{\mathcal{X}}$ satisfying

\mathcal{X}\subseteq\widetilde{\mathcal{X}}, \tag*{(18)}

where $\mathcal{X}$ is the original perturbation set defined in Eq. (4). Replacing $\mathcal{X}$ with $\widetilde{\mathcal{X}}$ yields a relaxation of the original verification problem. Since the relaxed set contains the original attack set, a successful verification result remains sound for the original threat model. We propose three relaxations with different levels of approximation: Full-Group, $L_2$ -norm, and Group-Lasso relaxations. Specifically, we replace the constraints Eq. (17) and Eq. (17) with the following proposed constraints Eq. (19)- Eq. (21).

Full-Group Naive Relaxation

The full-group relaxation simply removes the attack-selection constraint and allows a perturbation of radius $\varepsilon$ in every group:

\mathcal{X}_{\mathrm{Full}}=\left\{\mathbf{x}_0\ \middle|\ \left\|\mathbf{x}_0^{(g)}-\mathbf{x}_0^{*(g)}\right\|_2\le\varepsilon,\ \ \forall g\in\mathcal{G}\right\}. \tag*{(19)}

This relaxation corresponds to fixing $G^{(g)} = 1$ for all groups. Consequently, this completely removes the sparsity constraint, yielding the simplest convex approximation for the original attack set.

L2-Norm Relaxation

The $L_2$ -norm relaxation replaces the group-wise perturbation constraints with a single constraint on the entire image:

\mathcal{X}_{L_2} = \left\{ \mathbf{x}_0 \mid\|\mathbf{x}_0 - \mathbf{x}_0^*\|_2 \le k\varepsilon\right\}. \tag*{(20)}

Although this relaxation method ignores the group structure of the attacks, it offers the advantage of reducing the problem to the standard $L_2$ -norm ball formulation; consequently, existing SDP (semidefinite programming)-based verification frameworks for $L_p$ -norm ball attacks can be applied directly.

Group-Lasso Relaxation

Group-Lasso relaxation preserves the group structure of the original attack while removing the binary selection variables. Specifically, we replace the individual group-wise constraints with a single group-sparse constraint:

\mathcal{X}_{\mathrm{GL}} = \left\{ \mathbf{x}_0 \;\middle|\; \sum_{g \in\mathcal{G}} \|\mathbf{x}_0^{(g)} - \mathbf{x}_0^{*(g)}\|_2 \le k\varepsilon\right\}. \tag*{(21)}

This constraint bounds the total group-wise perturbation by the maximum perturbation that can be introduced into $k$ groups, while allowing the optimization to determine how the perturbation is distributed across groups. Among the three relaxations, Group-Lasso most directly reflects the spatial sparsity of the original group-wise patch attack.

Soundness and Inclusion Relations

The relationships among the original attack set and the proposed convex relaxations are formalized by the following propositions.

Proposition 1 (Soundness). All three relaxed perturbation sets contain the original attack set $\mathcal{X}$ . Specifically, we have the following relationships:

\mathcal{X} \subseteq\mathcal{X}_{\mathrm{Full}}, \qquad\mathcal{X} \subseteq\mathcal{X}_{\mathrm{GL}}, \qquad\mathcal{X} \subseteq\mathcal{X}_{L_2}. \tag*{(22)}

Proof. Let $\mathbf{x}_0 \in\mathcal{X}$ be an arbitrary input satisfying Eq. (4). For each group $g$ ,

\|\mathbf{x}_0^{(g)} - \mathbf{x}_0^{*(g)}\|_2 \le\varepsilon G^{(g)} \le\varepsilon,

which immediately gives $\mathbf{x}_0 \in\mathcal{X}_{\mathrm{Full}}$ . Furthermore,

\sum_g \|\mathbf{x}_0^{(g)} - \mathbf{x}_0^{*(g)}\|_2 = \sum_{g:G^{(g)}=1} \|\mathbf{x}_0^{(g)} - \mathbf{x}_0^{*(g)}\|_2 \le k\varepsilon,

where the last inequality follows from $\mathbf{1}^{\top}\mathbf{G} = k$ . Therefore, $\mathbf{x}_0 \in\mathcal{X}_{\mathrm{GL}}$ . Finally, because the groups form a non-overlapping partition of the image,

\|\mathbf{x}_0 - \mathbf{x}_0^*\|_2 \le\sum_g \|\mathbf{x}_0^{(g)} - \mathbf{x}_0^{*(g)}\|_2 \le k\varepsilon. \tag*{(23)}

Hence, $\mathbf{x}_0 \in\mathcal{X}_{L_2}$ .

Proposition 2 (Inclusion Relations). Group-Lasso relaxation is contained within the $L_2$ -norm relaxation ( $\mathcal{X}_{\mathrm{GL}} \subseteq\mathcal{X}_{L_2}$ ). Combined with the soundness properties, the resulting relationships can be summarized as:

\mathcal{X} \subseteq\mathcal{X}_{\mathrm{GL}} \subseteq\mathcal{X}_{L_2}, \qquad\mathcal{X} \subseteq\mathcal{X}_{\mathrm{Full}}. \tag*{(24)}

Proof. We can establish the inclusion relation between Group-Lasso and $L_2$ -norm relaxations by using the triangle inequality. For any $\mathbf{x}_0 \in\mathcal{X}_{\mathrm{GL}}$ , we have:

\|\mathbf{x}_0 - \mathbf{x}_0^*\|_2 \le\sum_{g \in\mathcal{G}} \|\mathbf{x}_0^{(g)} - \mathbf{x}_0^{*(g)}\|_2 \le k\varepsilon. \tag*{(25)}

Thus, $\mathcal{X}_{\mathrm{GL}} \subseteq\mathcal{X}_{L_2}$ . In contrast, no general inclusion relation exists between $\mathcal{X}_{\mathrm{Full}}$ and the other two relaxed sets, and their relative tightness depends on the number of groups $m$ and the number of attacked groups $k$ .

Thus, Group-Lasso provides a tighter relaxation than the $L_2$ -norm relaxation while explicitly retaining the group structure of the original attack. After replacing the original perturbation set $\mathcal{X}$ with any of the three convex sets above, the binary variable $\mathbf{G}$ is no longer required. The resulting verification problem is therefore a pure SDP with continuous variables only. This removes the combinatorial optimization over attack locations and enables substantially more scalable verification of larger neural networks.

Numerical Experiments {#sec:4}

We evaluate the proposed relaxation methods from three perspectives: computational efficiency, relaxation tightness, and verification performance.

Common Setup {#sec:4.1}

All experiments were conducted on a node with two AMD EPYC 9654 CPUs (96 cores per socket, up to 3707 MHz) and 768 GiB of memory. To solve the MISDP, we used SCIP-SDP [3] with SoPlex [13] to handle the branch-and-bound framework required for solving the auxiliary LPs. For our methods, we used MOSEK [23] to solve the relaxed SDPs. The image is partitioned into non-overlapping square groups using a sliding window, where the side length of each square group specifies the group size. When the side length of the image is not evenly divisible by the group size, the remaining pixels are grouped together as a single group.

Evaluation of Computational Efficiency

We evaluate the computational efficiency of the original MISDP and the three proposed relaxations. We measure both wall-clock computation time and memory consumption as the size of the underlying semidefinite matrix increases. This experiment is intended to quantify the computational benefit of eliminating the binary variables associated with the attack location.

Experimental Setup. We evaluate four network architectures, denoted Tiny, Small, Medium, and Large, as in Table 1. We vary the width of the hidden layers, which is the primary factor governing the dimension of the semidefinite matrix. Because the original $28 \times28$ MNIST resolution is computationally prohibitive for complete verification baselines, we train and evaluate our models on downsampled $5 \times5$ images (25 dimensions) of the MNIST training data. For the verification setup, we set the perturbation radius to $\varepsilon= 0.1$ , the target class to 5, and attack cardinality to $k = 1$ , partitioning the input into 4-pixel groups.

	Hidden layer	$P$ matrix size	Accuracy
Tiny	5 nodes $\times$ 2 layers	$46 \times46$	44.37%
Small	10 nodes $\times$ 2 layers	$56 \times56$	51.81%
Medium	15 nodes $\times$ 2 layers	$66 \times66$	52.74%
Large	20 nodes $\times$ 2 layers	$76 \times76$	53.34%

Table 1. Model settings used for the scalability evaluation

Results. The computation time results are reported in Table 2. Across all four evaluated network architectures, the proposed relaxations drastically accelerate verification compared to the exact MISDP formulation (Eq. (17)), requiring at most 3% of the computation time of the original MISDP. Specifically, the proposed relaxation methods achieve speedup factors of at least $41\times$ , $209\times$ , $1320\times$ , and $1430\times$ for the Tiny, Small, Medium, and Large networks, respectively. This significant reduction in runtime stems from removing the binary group-selection vector $\mathbf{G}$ .

Method	Tiny [s]	Small [s]	Medium [s]	Large [s]
MISDP (17)	6.64	22.95	77.88	115.84
Full-Group	0.161	0.11	0.057	0.080
$L_2$ norm	0.032	0.06	0.055	0.074
Group-Lasso	0.036	0.06	0.059	0.081

Table 2. Execution time comparison between MISDP (9) and three proposed relaxations, across different network sizes. All proposed relaxations achieve <3% of MISDP runtime.

Evaluation of Relaxation Tightness

We investigate how closely the proposed relaxations approximate the original MISDP. We compare the objective values obtained by the three relaxations with those of the original MISDP. Because each relaxation enlarges the feasible perturbation set, its optimal objective value provides a measure of the relaxation tightness.

Experimental Setup. We use the Small network configuration from Table 1. The input consists of MNIST images compressed to 25 dimensions. We set the target class to 5, use the ground-truth class as the true class, set $k = 1$ , and use groups containing four elements. We evaluate two perturbation radii, $\varepsilon= 0.1$ and $\varepsilon= 10^{-4}$ . For each setting, we compare the objective value of each relaxation with that of the original MISDP. The reported increase is computed relative to the original MISDP objective value.

Results. Table 3 shows the average increase in the objective value relative to the original MISDP for different perturbation radii. For each perturbation radius, we randomly sampled 50 images from the MNIST test set, computed the percentage increase in the objective value relative to the original MISDP solution for each sample, and averaged the results. As shown, Group-Lasso relaxation provides the tightest approximation to the original MISDP among the three relaxations. Even at the large attack radius $\varepsilon= 0.1$ , the objective value changes by only 0.34% relative to the exact solution. This tight approximation is enabled by Group-Lasso relaxation, which can retain the group-wise structure of the original attack, whereas the other relaxations discard an increasing amount of this structure. This trend is also evident in Figure 2. Group-Lasso solutions lie closest to the diagonal, while the $L_2$ -norm and Full-Group relaxations exhibit progressively larger deviations. This ordering is consistent with the inclusion relations established in § 3.4.4.

Method	$\varepsilon= 0.1$	$\varepsilon= 10^{-4}$
Full-Group	92.82%	1.07%
$L_2$ -norm	20.76%	0.19%
Group-Lasso	0.34%	0.00%

Table 3. Average increase in the objective value relative to the original MISDP for different perturbation radii, averaged over 50 randomly sampled test images.

Comparison of objective function values of the original MISDP and proposed relaxations — Figure 2. Comparison of the objective values obtained by the original MISDP and the proposed relaxations for $\varepsilon= 0.1$ . Each point corresponds to one evaluation sample. Group-Lasso is almost on the diagonal, demonstrating its very tight relaxation of the MISDP.

Verification Rate Comparison

We evaluate the verification rates of the proposed relaxations, comparing them with prior verification methods in addition to the relaxation tightness comparison in § 4.3.

Experimental Setup. We follow the evaluation methodology adopted in prior work [18] to facilitate comparison with existing verification methods. We evaluate two fully connected architectures, FCNNa and FCNNb. FCNNa consists of two hidden layers with width 20, while FCNNb consists of three hidden layers with width 100. For both FCNNa and FCNNb, the input layer dimension matches the total number of pixels in the input image, which is 784 for MNIST in our case. For each architecture, we consider both normally trained (Clean) and PGD-adversarially trained (Adv.) models. The adversarially trained models are trained using PGD with the perturbation radius specified by the corresponding setting. For each setting, we evaluate 100 test samples, selected at indices 0, 100,...,9900. The verification rate is the fraction of samples for which the verification optimization certifies that the model remains robust against the specified target class under the corresponding perturbation set. We compare the proposed Full-Group, $L_2$ -norm, and Group-Lasso relaxations against bounded-MILP [30], CROWN-IBP [37], and CROWN [36]. The attack cardinality $k$ is 1, partitioning the input into 4-pixel groups. These baselines are representative $L_p$ -norm-based verification methods and include the state-of-the-art methods reported in [18].

Results. The verification rates across models and defense settings are summarized in Table 4. For the FCNNa architecture, our proposed Group-Lasso relaxation achieves high verification rates of 86% on the standard (Clean) model and

Category	Method	FCNNa Clean ( $\varepsilon= 0.02$ )	FCNNa Adv. ( $\varepsilon= 0.10$ )	FCNNb Clean ( $\varepsilon= 0.02$ )	FCNNb Adv. ( $\varepsilon= 0.30$ )
Ours	Full-Group	83%	70%	59%	21%
Ours	$L_2$ -norm	86%	70%	59%	69%
Ours	Group-Lasso	86%	91%	69%	69%
Baselines	Bounded-MILP	80%	70%	84%	0%
Baselines	CROWN-IBP	77%	2%	0%	0%
Baselines	CROWN	79%	47%	84%	4%

Table 4. Verification results on standard (Clean) and adversarially trained (Adv.) models. We compare our proposed SDP relaxations against prior verification baselines, showing state-of-the-art performance [18].

91% on the adversarially trained (Adv.) model. Under the Adv. setting, Group-Lasso substantially outperforms existing baselines, including bounded-MILP (70%), CROWN (47%), and CROWN-IBP (2%). Similarly, for the deeper $FCNNb$ network, Group-Lasso achieves the highest verification rate of 69% in the Adv. setting, whereas prior baselines fail almost completely (bounded-MILP at 0%, CROWN-IBP at 0%, and CROWN at 4%). The observation is consistent when $k$ is increased to 10, as shown in Table 5. Although bounded-MILP and CROWN yield higher certified rates on the Clean $FCNNb$ model (84%), we consider that our relaxations are particularly effective on challenging samples that are difficult to verify.

Method	FCNNa Clean	FCNNa Adv.
Full-Group	83%	70%
$L_2$ -norm	83%	66%
Group-Lasso	83%	80%

Table 5. Verification performance with $k = 10$ . Group-Lasso shows higher verification rates than other unstructured relaxations.

To quantify this, we examine the margin of the optimal objective value $f(x^{[j]}) - f(x^{[j_*]})$ , where negative values closer to zero indicate narrower margins. Among the evaluated inputs, the average optimal value for samples certified exclusively by Group-Lasso was $-1.69$ , compared to $-10.94$ for samples certified by all methods. This significant gap indicates that conventional verifiers suffer from loose relaxation bounds on challenging inputs with small margins, whereas preserving the group-sparse attack structure allows Group-Lasso to certify such instances that remain unprovable by existing baselines.

Qualitative Analysis

We qualitatively examine the perturbations obtained from the optimization solutions. This analysis provides an intuitive comparison between the perturbations produced by the proposed group-wise threat model and those produced by conventional $L_p$ -based verification methods.

For bounded MILP, we directly use the optimal solution, as it is complete verification. For incomplete verification, which only tests the upper bound of the objective value and does not return attack perturbations, we construct approximated attack perturbations using the following procedure. For IBP perturbations, we determine the perturbation direction for each pixel based on its sensitivity to the true and target label scores, computed via forward propagation, and obtain an approximate perturbation by moving as far as possible in that direction within the input perturbation bound. For SDP-based methods including ours, we extract the sub-vector corresponding to the original image and reshape it back into the original image’s 2D array. Specifically, the sub-vector extracted corresponds to entries [0,1] through [0,256] of the SDP solution.

Perturbations of a Successfully Verified Sample. Figure 3 shows the perturbations obtained for an input image whose true label is 7, shown in Figure 1, with target class 0, in a setting where Group-Lasso successfully verifies the model.

Figure 3. Visualization of perturbations of successfully verified samples when changing the predicted label from 7 to 0. Red and blue mean positive- and negative-direction perturbations, respectively. Only Group-Lasso can assume the localized perturbation.

All methods attempt to suppress or modify the digit 7. However, Group-Lasso relaxation concentrates the perturbation almost entirely on the digit itself, leaving the surrounding background unchanged. This behavior is consistent with the assumed localized patch threat model. In contrast, the perturbations obtained by the other methods extend into the background region. In particular, the perturbations produced by IBP and MILP distribute non-negligible changes outside the digit region. The proposed Full-Group and $L_2$ -norm relaxations reduce this effect compared with these baselines, but still permit perturbations outside the localized region. These observations illustrate the benefit of explicitly retaining group sparsity in the perturbation set.

Perturbations of an Unverified Sample. Figure 4 shows an instance with true label 2, shown in Figure 1, and target class 0 for which Group-Lasso does not certify robustness. Figure 5 shows the corresponding reconstructed images. In this case, the perturbations produced by most methods modify both the digit and the surrounding background. Group-Lasso not only concentrates its perturbation on the digit region, but also tries to draw the target digit, 0. This supports the high capability of Group-Lasso to handle the patch attack, which can only inject localized perturbations. When subtle perturbations are insufficient, it is natural that the attacker instead draws the target digit.

Figure 4. Visualization of perturbations for an unverified sample when changing the predicted label from 2 to 0. Red and blue mean positive- and negative-direction perturbations, respectively. Group-Lasso’s perturbation is localized, but it attempts to draw 0.

Reconstructed attacked images from Fig. 4 — Figure 5. Reconstructed attacked images from Figure 4, attempting to change the prediction from 2 to 0.

In summary, the qualitative results support the motivation for the proposed relaxation: Group-Lasso not only provides a substantially tighter relaxation than the simpler alternatives, but also produces optimization solutions whose perturbations are spatially concentrated in a manner consistent with the assumed patch attack.

Discussion and Limitations

The results highlight the importance of preserving the spatial structure of patch threats during verification. Among the proposed relaxations, Group-Lasso consistently provides the tightest approximation to the original MISDP and effectively concentrates perturbations within targeted regions, leading to stronger robustness certification against patch attacks. However, there are several limitations in this study. We evaluated only fully connected networks and small-scale inputs, leaving high-resolution images and modern architectures for future work. Our primary focus is the theoretical formulation of patch attacks (§ 3) and the tightness of the proposed relaxations relative to the original MISDP, which is itself unsuitable for large-scale problems. As the first formal verification framework specialized for patch attacks, we leave the development of scalable solvers, such as first-order methods [1, 7], to future work. Finally, our fixed, non-overlapping image partition may not effectively capture arbitrary physical patch geometries. Nevertheless, it can flexibly incorporate realistic deployable regions, which are naturally constrained in physical settings (e.g., stickers cannot be placed on the sky).

Conclusion

In this work, we introduced a one-shot framework for robustness verification against patch attacks. Instead of enumerating possible attack locations, we formulated the attack location jointly with the adversarial perturbation and derived an exact mixed-integer semidefinite programming formulation. We then eliminated the discrete attack-selection variables through three convex relaxations: Full-Group, $L_2$ -norm, and Group-Lasso. Our analyses demonstrate that explicitly preserving the spatial group-sparsity of real-world threats is critical for effective verification. Group-Lasso relaxation provides a tight and efficient approximation, incurring only a 0.34% average increase in the objective value compared to the original MISDP while requiring less than 3% of the computation time. Furthermore, by achieving a verification rate of 91% compared to $\le70\%$ for prior baselines, our approach offers a practical, scalable solution for certifying neural network robustness. Future work will explore extending this framework to broader classes of physical attacks and larger network architectures.

References

[1]Amir Ali Ahmadi and Anirudha Majumdar. DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization. SIAM Journal on Applied Algebra and Geometry, 3(2):193–230, 2019. doi: 10.1137/18M118935X.DOI
[2]Osbert Bastani, Yani Ioannou, Leonidas Lampropoulos, Dimitrios Vytiniotis, Aditya V. Nori, and Antonio Criminisi. Measuring Neural Net Robustness with Constraints. In NeurIPS, volume 29, pages 2613–2621, 2016.arxiv.org/abs/1605.07262
[3]Ksenia Bestuzheva, Leon Eifler, Ambros Gleixner, Gerald Gamrath, Katrin Halbig, Christopher Hojny, Thorsten Koch, Antonia Chmiela, Marc Pfetsch, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Stefan Vigerske, and Dieter Weninger. The SCIP Optimization Suite 9.0. Technical Report ZR-24-06, Zuse Institute Berlin, 2024. URL https://arxiv.org/abs/2402.17702.
[4]Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp, Prasoon Goyal, Lawrence D. Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, Xin Zhang, Jake Zhao, and Karol Ziebа. End to End Learning for Self-Driving Cars. arXiv preprint arXiv:1604.07316, 2016.arxiv.org/abs/1604.07316
[5]Elena Botoeva, Panagiotis Kouvaros, Jan Kronqvist, Alessio Lomuscio, and Ruth Misener. Efficient Verification of ReLU-Based Neural Networks via Dependency Analysis. In AAAI, pages 3291–3299, 2020.DOI
[6]Tom B Brown, Dandelion Mané, Aurko Roy, Martín Abadi, and Justin Gilmer. Adversarial Patch. In NIPS 2017 Workshop on Machine Learning and Computer Security, 2017. URL https://arxiv.org/abs/1712.09665.
[7]Samuel Burer and Renato D. C. Monteiro. A Nonlinear Programming Algorithm for Solving Semidefinite Programs via Low-Rank Factorization. Mathematical Programming, 95 (2):329–357, 2003. doi: 10.1007/s10107-002-0352-8.
[8]Nicholas Carlini and David Wagner. Towards Evaluating the Robustness of Neural Networks. In SP, pages 39–57, 2017.arxiv.org/abs/1608.04644
[9]Ping-Yeh Chiang, Renkun Ni, Ahmed Abdelkader, Chen Zhu, Christoph Studer, and Tom Goldstein. Certified Defenses for Adversarial Patches. In ICLR, 2020. URL https://arxiv.org/abs/2003.06693.
[10]Rüdiger Ehlers. Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks. In ATVA, 2017. URL https://api.semanticscholar.org/CorpusID:1931807.arxiv.org/abs/1705.01320
[11]Andre Esteva, Brett Kuprel, Roberto A. Novoa, Justin Ko, Susan M. Swetter, Helen M. Blau, and Sebastian Thrun. Dermatologist-Level Classification of Skin Cancer with Deep Neural Networks. Nature, 542(7639):115–118, 2017. doi: 10.1038/nature21056.DOI
[12]Yanbo Fan, Baoyuan Wu, Tuanhui Li, Yong Zhang, Mingyang Li, Zhifeng Li, and Yuju Yang. Sparse Adversarial Attack via Perturbation Factorization. In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm, editors, ECCV, pages 35–50, Cham, 2020. Springer International Publishing.DOI
[13]Ambros Gleixner and Daniel E Steffy. Linear Programming Using Limited-Precision Oracles. Mathematical Programming, 183(1):525–554, 2020.
[14]Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and Harnessing Adversarial Examples. In ICLR, 2015.DOI
[15]Guy Katz, Clark W. Barrett, David L. Dill, Kyle D. Julian, and Mykel J. Kochenderfer. Replex: An Efficient SMT Solver for Verifying Deep Neural Networks. In CAV, pages 97–117. Springer, 2017.arxiv.org/abs/1702.01135
[16]Jianglin Lan, Benedikt Brückner, and Alessio Lomuscio. A Semidefinite Relaxation Based Branch-and-Bound Method for Tight Neural Network Verification. In AAAI, pages 14946–14954, 06 2023. doi: 10.1609/aaai.v37i12.26745.DOI
[17]Alexander Levine and Soheil Feizi. (De)Randomized Smoothing for Certifiable Defense against Patch Attacks. In NeurIPS, volume 33, 2020. URL https://arxiv.org/abs/2002.10733.
[18]Linyi Li, Tao Xie, and Bo Li. SoK: Certified Robustness for Deep Neural Networks. In SP, San Francisco, CA, USA, 2023. IEEE.arxiv.org/abs/2009.04131
[19]Xin Liu, Huanrui Yang, Ziwei Liu, Linghao Song, Hai Li, and Yiran Chen. DPatch: An Adversarial Patch Attack on Object Detectors. In Proceedings of the 2019 AAAI Workshop on Artificial Intelligence Safety (SafeAI 2019), 2019. URL https://ceur-ws.org/Vol-2301/paper_5.pdf.
[20]Alessio Lomuscio and Lalit Maganti. An Approach to Reachability Analysis for Feed-Forward ReLU Neural Networks. arXiv preprint arXiv:1706.07351, 2017.arxiv.org/abs/1706.07351
[21]Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards Deep Learning Models Resistant to Adversarial Attacks. In ICLR, 2018. arXiv:1706.06083.arxiv.org/abs/1706.06083
[22]Jan Hendrik Metzen and Maksym Yatsura. Efficient Certified Defenses against Patch Attacks on Image Classifiers. In ICLR, 2021. URL https://openreview.net/forum?id=hr-3PMvDpi1.arxiv.org/abs/2102.04154
[23]MOSEK ApS. The MOSEK Python Fusion API Manual. Technical report, 2026. URL https://docs.mosek.com/latest/pyfusion/index.html. Version 11.2.
[24]Dean A. Pomerleau. ALVINN: An Autonomous Land Vehicle in a Neural Network. In David S. Touretzky, editor, Advances in Neural Information Processing Systems 1, pages 305–313. Morgan Kaufmann, San Francisco, CA, 1989.
[25]Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang. Semidefinite Relaxations for Certifying Robustness to Adversarial Examples. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, NeurIPS, volume 31, pages 10900–10910, 2018. URL https://proceedings.neurips.cc/paper_files/paper/2018/file/29c0605a3bab4229e46723f89cf59d83-Paper.pdf.arxiv.org/abs/1811.01057
[26]Takami Sato, Junjie Shen, Ningfei Wang, Yunhan Jia, Xue Lin, and Qi Alfred Chen. Dirty Road Can Attack: Security of Deep Learning Based Automated Lane Centering under Physical-World Attack. In 30th USENIX Security Symposium (USENIX Security 21), pages 3309–3326. USENIX Association, August 2021. ISBN 978-1-939133-24-3. URL https://www.usenix.org/conference/usenixsecurity21/presentation/sato.arxiv.org/abs/2009.06701
[27]Mahmood Sharif, Sruti Bhagavatula, Lujo Bauer, and Michael K Reiter. Accessorize to a Crime: Real-World Fooling of Face Recognition. In CCS, pages 1528–1540. ACM, 2016. doi: 10.1145/2976749.2978392. URL https://dl.acm.org/doi/10.1145/2976749.2978392.DOI
[28]Dawn Song, Kevin Eykholt, Ivan Evtimov, Earlence Fernandes, Bo Li, Amir Rahmati, Florian Tramer, Atul Prakash, and Tadayoshi Kohno. Physical Adversarial Examples for Object Detectors. In 12th USENIX Workshop on Offensive Technologies (WOOT 18), Baltimore, MD, August 2018. USENIX Association. URL https://www.usenix.org/conference/woot18/presentation/eykholt.arxiv.org/abs/1807.07769
[29]Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In ICLR, 2014.arxiv.org/abs/1312.6199
[30]Vincent Tieng, Kai S. Xiao, and Russ R. Salakhutdinov. Evaluating Robustness of Neural Networks with Mixed Integer Programming. In ICLR, 2019. URL https://arxiv.org/abs/1711.07356.
[31]Shiqi Wang, Huan Zhang, Kaidi Xu, Suman Jana, Xue Lin, Cho-Jui Hsieh, and J. Zico Kolter. Beta-CROWN: Efficient Bound Propagation with Per-Neuron Split Constraints for Neural Network Verification. In NeurIPS, volume 34, pages 29909–29921, 2021.
[32]Eric Wong and J. Zico Kolter. Provable Defenses against Adversarial Examples via the Convex Outer Adversarial Polytope. In ICML, pages 5283–5292, 2018.
[33]Yuzheng Wu, Maryellen L. Giger, Kunio Doi, Carl J. Vyborny, Robert A. Schmidt, and Charles E. Metz. Artificial Neural Networks in Mammography: Application to Decision Making in the Diagnosis of Breast Cancer. Radiology, 187(1):81–87, 1993. doi: 10.1148/radiology.187.1.8451441.DOI
[34]Chong Xiang, Arjun Nitin Bhagoji, Vikash Sehwag, and Prateek Mittal. PatchGuard: A Provably Robust Defense against Adversarial Patches via Small Receptive Fields and Masking. In 30th USENIX Security Symposium (USENIX Security 21), pages 2237–2254, 2021.arxiv.org/abs/2005.10884
[35]Chong Xiang, Saeed Mahloujifar, and Prateek Mittal. PatchCleanser: Certifiably Robust Defense against Adversarial Patches for Any Image Classifier. In 31st USENIX Security Symposium (USENIX Security 22), pages 2065–2082, Boston, MA, August 2022. USENIX Association. ISBN 978-1-939133-31-1. URL https://www.usenix.org/conference/usenixsecurity22/presentation/xiang.arxiv.org/abs/2108.09135
[36]Huan Zhang, Tsui-Wei Weng, Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient Neural Network Robustness Certification with General Activation Functions. In NeurIPS, volume 31, 2018.arxiv.org/abs/1811.00866
[37]Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane Boning, and Cho-Jui Hsieh. Towards Stable and Efficient Training of Verifiably Robust Neural Networks. In ICLR, 2020.arxiv.org/abs/1906.06316