Robustness Verification against Patch Attacks via Group-Lasso Semidefinite Relaxation
Organizations: Institute of Science Tokyo, 2-12-1 Ookayama, Meguro-ku, Tokyo 152-8550, Japan · Keio University, 2-15-45 Mita, Minato-ku, Tokyo 108-8345, Japan
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.
Figures & tables
| Hidden layer | matrix size | Accuracy | |
|---|---|---|---|
| Tiny | 5 nodes 2 layers | 44.37% | |
| Small | 10 nodes 2 layers | 51.81% | |
| Medium | 15 nodes 2 layers | 52.74% | |
| Large | 20 nodes 2 layers | 53.34% |
| Method | Tiny [s] | Small [s] | Medium [s] | Large [s] |
|---|---|---|---|---|
| MISDP ( 9 ) | 6.64 | 22.95 | 77.88 | 115.84 |
| Full-Group | 0.161 | 0.11 | 0.057 | 0.080 |
| norm | 0.032 | 0.06 | 0.055 | 0.074 |
| Group-Lasso | 0.036 | 0.06 | 0.059 | 0.081 |
| Method | ||
|---|---|---|
| Full-Group | 92.82% | 1.07% |
| -norm | 20.76% | 0.19% |
| Group-Lasso | 0.34% | 0.00% |
| Category | Method | FCNNa | FCNNb | ||
|---|---|---|---|---|---|
| Clean ( ) | Adv. ( ) | Clean ( ) | Adv. ( ) | ||
| Ours | Full-Group | 83% | 70% | 59% | 21% |
| -norm | 86% | 70% | 59% | 69% | |
| Group-Lasso | 86% | 91% | 69% | 69% | |
| Baselines | Bounded-MILP | 80% | 70% | 84% | 0% |
| CROWN-IBP | 77% | 2% | 0% | 0% | |
| Method | FCNNa Clean | FCNNa Adv. |
|---|---|---|
| Full-Group | 83% | 70% |
| -norm | 83% | 66% |
| Group-Lasso | 83% | 80% |
Neural Network Verification
Neural network verification develops methods to prove whether networks satisfy properties such as robustness, safety, and bounded output behavior.
See all 139 papers