CS Paper Radar

Robustness Verification against Patch Attacks via Group-Lasso Semidefinite Relaxation

Yukina Nakagawa, Takami Sato, Ken Kobayashi, Kazuhide Nakata

cs.CV ·submitted 2026-11-03 14:07 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

A Convex-Analytic Reformulation for Poisoning Attacks on Logistic Regression

cs.LG math.OC ·2026-11-12 ·Carina Moreira Costa, Maria Eduarda Pinheiro, Martin Schmidt
similarity 0.61
Abstract

We study data poisoning attacks on logistic regression with $\ell_2$-regularization, where an attacker chooses the features of a fixed number of injected observations with prescribed labels to maximize the logistic loss on the clean training data. Strong convexity of the defender's problem yields an exact reformulation through its first-order optimality conditions. Using convex conjugacy of the softplus function, we replace the sigmoid relations by a single convex optimality-gap inequality and express the attacker's objective as a concave function. A change of variables makes the stationarity condition affine, leaving bounded bilinear equalities as the only nonconvex constraints. We derive finite bounds on all variables involved in these equalities, including a global bound on the coefficient norm and tighter bounds obtained by preprocessing based on convex optimization. Experiments on eight binary classification datasets evaluate attack effectiveness and compare the two reformulations when solved with SCIP. Attacks obtained by local optimization degrade predictive performance on most datasets, while the convex-analytic formulation produces substantially stronger reported dual bounds within a fixed time limit.

0.17

$(\text{DNN})^2$: Doubly Non-Negative Relaxations for Deep Neural Networks

cs.LG cs.ROeess.SY ·2026-08-25 ·Hanna Jiamei Zhang, Alan Papalia, Michael Everett, David M. Rosen
published similarity 0.60
Abstract · 6 pages, 3 figures, accepted and to be presented at 64th IEEE Conference on Decision and Control: CDC 2026

Existing linear program (LP) and semidefinite program (SDP) relaxations for rectified linear unit (ReLU) neural network (NN) verification yield overly-conservative safety guarantees due to significant relaxation gaps. While the completely positive program (CPP) formulation closes this gap, it is NP-hard to solve. Its cheapest tractable relaxation, the doubly non-negative program (DNN), retains critical constraints as an SDP, but one whose size exceeds the reach of interior-point methods at practical scale. While Burer-Monteiro (BM) factorization has been applied to make SDP-based verification scalable, no such result exists for the strictly tighter DNN formulation. A key obstacle is that additional non-negativity constraints in the DNN cause dual multipliers for optimality certification to be non-unique, making standard certification methods inapplicable. We propose a novel eigenvalue maximization procedure that searches the non-unique multiplier space for a valid certificate, i.e. a global optimality guarantee. Experiments demonstrate that our approach $(\text{DNN})^2$ produces bounds consistently tighter than the standard SDP method, often matching the exact solution, and that our certification procedure confirms global optimality when a valid certificate exists. These results are a key step toward providing tight, certifiable, and computationally scalable verification guarantees needed to deploy neural network controllers and perception modules in safety-critical autonomous systems.

0.37

KAN-Robust-Bench: A Benchmark for Evaluating the Robustness of Kolmogorov-Arnold Networks

cs.LG cs.AI ·2026-08-21 ·Mohammad Meymani, Roozbeh Razavi-Far
benchmark similarity 0.60
Abstract

While machine learning models have demonstrated strong performance in many domains, these models have shown profound vulnerabilities when they are exposed to adversarial threats. While adversarial attacks fall into various categories, the most prominent category in research studies is evasion. In evasion attacks, the adversary generates perturbed versions of samples, which might not be observable by human eyes. These samples generally fool the machine learning models with high confidence. This phenomenon poses a significant security violation against machine learning models. In this paper, we investigate the certified and empirical robustness of various Kolmogorov-Arnold network architectures against strong evasion attacks. At first, we provide the mathematical foundations for randomized smoothing and interval bound propagation, and report the $\ell_2$-certified robustness of the models under randomized smoothing. After that, we systematically evaluate the robustness of various defended and undefended KAN models under FGSM, PGD, and C&W attacks in order to find out the optimal defense strategies and architectures.

0.23

Certified Robustness via Sparse Second-Order Cone Relaxations

cs.LG ·2026-10-12 ·Mohammadreza Maleki, Daniel Sadig, Rushendra Sidibomma, Mahyar Fazlyab, Arman Adibi +1 more
benchmark similarity 0.60
Abstract

Certified robustness is critical for deploying neural networks in safety-sensitive settings, but computing exact certificates typically requires solving nonconvex optimization problems. Practical verifiers use convex relaxations: linear programming (LP) relaxations are scalable but often too conservative, whereas semidefinite programming (SDP) relaxations can be substantially tighter but are computationally expensive. We introduce a hierarchy of second-order cone programming (SOCP) relaxations that provide stronger certificates than LP while avoiding the cost of global positive-semidefinite constraints. Our construction combines convex-hull relaxations of ReLU activations, selective McCormick lifting over certified variable bounds, and second-order cone constraints induced by 2-by-2 principal minors. Adding these constraints progressively yields a monotone hierarchy of increasingly tight bounds with a controllable computation-tightness trade-off. On fully connected and convolutional networks on MNIST and CIFAR-10, SOCP-based verification improves certified robust accuracy over LP-based verification and is competitive with alpha,beta-CROWN, while remaining orders of magnitude faster than SDP-based verification. These results position selective second-order constraints as a practical middle ground between scalable LP-based and tight SDP-based certification. Finally, we introduce class-optimized robust evaluation (CORE), which applies tighter relaxations only to target classes not certified by cheaper ones. On the fully connected MNIST benchmark, CORE variants match SDP-cert's certified robust accuracy while reducing average verification time by up to 86.30%.

0.11

Frame the adversary: a structure-aware attack methodology

cs.LG ·2026-09-25 ·Vicky Kouni, Stelios Perrakis, Francis Bach, Pascal Frossard, Yann Chevaleyre
top venuetheory similarity 0.59
Abstract · Accepted at NeurIPS'26

Frequency-based adversarial attacks have recently grown popular by exploiting spectral sensitivities shared across neural architectures. Unlike spatial perturbations, frequency-based attacks expose deeper vulnerabilities, making them especially valuable for robust evaluation of safety-critical and security-sensitive applications. Yet, existing approaches are typically not derived as solutions to an optimization problem that explicitly captures transform-domain structure. In this paper, we propose a methodology for crafting principled frequency-based adversarial attacks, via a dedicated optimization framework. A cornerstone of our method hinges on the introduction of a perturbation constraint set, tied to highly structured non-orthogonal transforms, well-known for their flexible, non-predefined frequency handling. We prove that the attacks emerge as weighted $\ell_2$-projections onto this set, yielding a general and controlled attack generation mechanism. By this, we provide a clear geometric attack characterization, ensuring alignment between the optimization objective and the perturbation constraint. We assess our framework on standardized datasets, for pretrained and adversarially robust models. Results highlight that our attacks, being solutions to an optimization problem, over a structured perturbation set, are highly effective, even across different, unseen architectures. Our methodology could serve as a theoretical baseline for designing and analyzing transformed-based attacks, targeting fundamental model vulnerabilities, instead of mere architecture-specific artifacts typically studied in the robustness literature.

0.29

Can Attack Difficulty Be Characterized Before Optimization? A Study of Pre-optimization Difficulty in Person-Vanishing Attacks

cs.CV ·2026-09-28 ·Jingyao Xu, Dongdong Wang, Siyang Lu
similarity 0.59
Abstract

Adversarial attacks against object detectors are traditionally studied from an optimization perspective, where attack difficulty is regarded as an outcome observed only after adversarial optimization. This raises a fundamental question: \emph{can the relative attack difficulty of different inputs be characterized before optimization begins?} In this paper, we investigate this question for person-vanishing attacks by introducing the concept of pre-optimization attack difficulty, which captures intrinsic differences in optimization effort across input images. To estimate this latent difficulty before optimization, we propose Quad-CLEVER, an efficient geometry-based estimator derived from a quadratic approximation of the local person-vanishing margin along the most attack-relevant direction. Extensive experiments across multiple attack algorithms demonstrate that Quad-CLEVER consistently correlates with the observed optimization cost, providing empirical evidence that attack difficulty exhibits a predictable pre-optimization structure. Building upon this finding, we further propose a difficulty-aware attack framework that leverages the estimated difficulty to adaptively allocate optimization budgets for a base attack under a fixed computational budget. On BDD100K, the proposed framework improves the image-level attack success rate by up to 5.78$\%$ while reducing the average optimization cost by up to 11.42 iterations. On the more challenging EventPed dataset, it saves 2.25 optimization iterations while maintaining comparable attack performance. These results demonstrate that attack difficulty can be meaningfully estimated before optimization and that exploiting such estimates enables more computationally efficient adversarial attacks.

0.28

Towards Verifying Neural Networks Against Multi-Parameter Bit-Flip Perturbations

cs.CR ·2026-10-06 ·Hai Duong, Thanh Le, Ho Nguyen, ThanhVu Nguyen
similarity 0.59
Abstract

Hardware faults can flip bits in the stored weights of a quantized neural network, potentially compromising its predictions. While such faults typically affect multiple parameters simultaneously, existing verifiers are limited to single-parameter perturbations due to the combinatorial explosion of possible flip locations in large networks. We present mBFV (m-BitFlip Verifier), an efficient verification framework that proves robustness against simultaneous bit flips across multiple parameters without explicitly enumerating these combinations. mBFV achieves this via a novel multi-parameter bound propagation technique that directly aggregates the m worst-case contributions. To further tighten these bounds, mBFV employs a branch-and-bound mechanism over perturbation locations, partitioning the potential flips to smaller groups of neurons. Evaluated on 625 instances, mBFV successfully verifies 293, significantly outperforming a prior single-parameter verifier (38 verified instances) and an exact mixed-integer linear programming baseline (0 verified instances). Notably, while these baselines are restricted to single-parameter flips on small networks (up to 13k parameters), mBFV scales to verify networks with up to 1.15M parameters against up to four simultaneous parameter flips.

0.22

Certified but Private: Scalable Zero-Knowledge Proofs for Neural Network Guarantees

cs.LG cs.CRcs.LO ·2026-08-17 ·Youwei Zhong, Ben Merbaum, Timos Antonopoulos, Ning Luo, Charalampos Papamanthou +2 more
top venuecode/data similarity 0.57
Abstract · 31 pages, 2 figures (10 pages for the main text), accepted to NeurIPS 2026, for code of implementation and evaluation, see https://github.co…

With the growing deployment of machine learning models, formal guarantees of the robustness and fairness of these models have become increasingly important in safety-critical and legal-compliance settings. However, model parameters are often commercial secrets that cannot be disclosed to auditors or end users. To this end, we present PANDA, a scalable system that uses zero-knowledge proofs (ZKPs) to prove the robustness and fairness properties of a model without revealing its private parameters. PANDA is built on top of CROWN, an efficient robustness certification framework that is used in many state-of-the-art formal verification tools for neural networks. The core contribution of PANDA is a novel algorithm for proving linear relaxation bounds for non-linear activation layers, yielding simple, lightweight proofs. Remarkably, our implementation can generate proofs of local robustness for neural networks with more than 2.9M parameters in 5 minutes, and can verify them in 10 seconds. Prior ZKP-based robustness system rely on exponential-time algorithms that cannot scale to nontrivial networks. In contrast, PANDA scales polynomially in the number of neurons in a network, allowing us to support neural networks 4 orders of magnitude larger than previous approaches with significantly reduced prover overhead.

0.70