Propose with the Gradient, Accept with the Loss: One Hedged Attack for Pixel-Sparse Robustness
Organizations: City University of Hong Kong
Abstract
A pixel-sparse adversary may change a few pixels of an image to any value. Robustness to such attacks is currently measured with an ensemble, sparse-AutoAttack (sAA), because its members fail in different places: sparse projected gradient descent (sPGD) trusts a first-order model that a full pixel change breaks, and sparse random search (Sparse-RS) ignores the gradient even where it is informative. We show that both attacks are local searches, each a proposal distribution plus an acceptance rule, and ask what such a search can learn from the gradient. A Taylor bound says what to measure, and measurements at the states the search visits give five rules. The sign of the gradient is its most reliable use at a single pixel and sets a new pixel's value. Its ranking of candidate pixels should be followed loosely, and its ranking of the pixels to remove, which is often more reliable, can be followed more closely. A pixel should not be proposed twice before a move is accepted, and acceptance should be decided by the loss alone. These rules define Gradient-guided Random Search (GRS), which runs once and costs one forward and one backward pass per step. On 13 CIFAR-10 configurations and 5 ImageNet models, GRS matches or beats the best single member of sAA and is within one point of sAA itself or stronger on 17 of 18 settings, and it is significantly stronger than sAA on 8. It uses 3 instead of up to 7 forward-pass units, and on CIFAR-10 it runs 3.7 to 5.0 times faster than the members of sAA run in full.
Figures & tables
| members of sAA | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| model | proj | unproj | Sparse-RS | sAA | GRS | sAA GRS | -zero | PGD 0 | GreedyPixel | ||
| Std. PRN-18 | 5 | 8.7 | 18.6 | 6.8 | 5.7 | 6.0 | 14/20 | 5.0 | 26.7 | 23.5 | 61.1 |
| Std. PRN-18 | 10 | 0.2 | 4.0 | 0.1 | 0.1 | 0.1 | 1/1 | 0.1 | 3.2 | 6.2 | 36.8 |
| Gowal PRN-18 | 20 | 9.4 | 15.7 | 7.2 | 6.3 | 4.6 ∗ | 49/15 | 3.8 | 23.3 | 23.7 | 49.3 |
| Sehwag RN-18 | 20 | 10.0 | 14.6 | 9.2 | 7.6 | 5.0 ∗ | 67/16 | 4.2 | 23.4 | 21.4 | 50.5 |
| Cui WRN-28 | 20 | 9.1 | 15.2 | 6.5 | 5.6 | 3.4 ∗ | 27/5 | 2.9 | 20.1 | 27.6 | 48.6 |
| members of sAA | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| model | proj | unproj | Sparse-RS | sAA | GRS | 3 seeds | sAA GRS | -zero | PGD 0 | GreedyPixel | ||
| Std. RN-50 | 20 | 23.9 | 42.7 | 20.0 | 17.6 | 17.2 | 26/22 | – | 15.0 | – | – | – |
| Std. RN-50 | 50 | 3.7 | 21.9 | 5.3 | 2.6 | 3.3 | 6/13 | 3.6 0.5 | 2.0 | 5.7 | 48.2 | 42.2 |
| Std. RN-50 | 100 | 0.3 | 6.6 | 1.7 | 0.3 | 0.9 † | 0/6 | – | 0.3 | – | – | – |
| Salman RN-18 | 20 | 14.4 | 19.7 | 12.7 | 11.4 | 10.5 | 19/10 | – | 9.5 | – | – | – |
| Salman RN-18 | 50 | 5.3 | 7.6 | 6.5 | 4.2 | 4.0 | 10/8 | 4.2 0.2 | 3.2 | 5.5 | 26.7 | 19.0 |
| GRS | GRS 0 | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| model | full | no tabu | accept all | full | uniform prop. | random corner | no value steps | cross-entropy | no gradient use | official Sparse-RS | |
| Std. PRN-18 | 5 | 6.0 | 6.1 | 17.5 † | 5.8 | 6.4 | 6.7 † | 6.2 | 6.0 | 7.1 † | 6.8 † |
| Gowal PRN-18 | 20 | 4.6 | 4.5 | 26.1 † | 4.3 | 4.8 | 5.4 † | 4.3 | 4.4 | 7.5 † | 7.2 † |
| Sehwag RN-18 | 20 | 5.0 | 5.4 | 25.6 † | 5.3 | 6.1 † | 6.5 † | 5.2 | 5.5 | 10.1 † | 9.2 † |
| Sehwag RN-18 | 20 | 6.4 | 6.1 | 24.4 † | 6.3 | 7.6 † | 8.8 † | 6.3 | 6.7 | 12.2 † | 10.9 † |
| sTRADES PRN-18 | 20 | 58.0 | 62.0 † | 87.2 † | 58.0 | 59.1 † | 60.3 † | 58.4 | 58.2 | 61.8 † | 61.4 † |
Appendix figures & tables12 assets
Supplementary material from the paper’s appendix.
Appendix
| variant | Salman | Wong | vs GRS 0 | vs Sparse-RS |
|---|---|---|---|---|
| GRS 0 (value steps 25%) | 10.6 | 9.6 | – | 32/24 |
| official Sparse-RS | 11.0 | 10.8 | 24/32 | – |
| Sparse-RS proposal inside our code | 10.6 | 9.2 | 23/21 | 26/16 |
| no value steps only | 10.6 | 9.4 | 19/18 | 27/18 |
| best-response fill, uniform add/drop | 9.8 | 9.4 | 28/23 | 27/14 |
| cold drop ( ), add at | 10.0 | 9.2 | 21/16 | 31/18 |
| model | GRS seeds | mean | GRS 0 seeds | mean |
|---|---|---|---|---|
| Std. RN-50 | 3.3 / 3.3 / 4.1 | 3.6 0.5 | 4.2 / 4.0 / 3.4 | 3.9 0.4 |
| Salman RN-18 | 4.0 / 4.4 / 4.2 | 4.2 0.2 | 5.6 / 5.3 / 5.3 | 5.4 0.2 |
| Salman RN-50 | 7.7 / 7.6 / 8.5 | 7.9 0.5 | 10.0 / 10.5 / 10.7 | 10.4 0.4 |
| Wong RN-50 | 6.7 / 6.9 / 7.3 | 7.0 0.3 | 9.5 / 8.2 / 9.0 | 8.9 0.7 |
| XCiT-S12 | 26.4 / 26.3 / 26.7 | 26.5 0.2 | 27.9 / 27.5 / 28.6 | 28.0 0.6 |
| model | GRS | GRS 0 | Sparse-RS | sAA | |||
|---|---|---|---|---|---|---|---|
| Std. RN-50 | 20 | 17.2 | 17.2 | 21/21 | 1.00 | 20.0 | 17.6 |
| Std. RN-50 | 50 | 3.3 | 4.2 | 20/11 | 0.15 | 5.3 | 2.6 |
| Std. RN-50 | 100 | 0.9 | 0.9 | 5/5 | 1.00 | 1.7 | 0.3 |
| Salman RN-18 | 20 | 10.5 ∗ | 14.0 | 39/4 | 12.7 | 11.4 | |
| Salman RN-18 | 50 | 4.0 ∗ | 5.6 | 18/2 | 6.5 | 4.2 | |
| Salman RN-18 | 100 | 1.3 | 1.8 | 9/4 | 0.27 | 4.1 | 1.3 |
| model | GRS | no tabu | accept all | Sparse-RS |
|---|---|---|---|---|
| Std. RN-50 | 3.3 | 3.3 | 27.3 † | 5.3 |
| Salman RN-18 | 4.0 | 5.1 † | 13.1 † | 6.5 |
| Salman RN-50 | 7.7 | 9.1 † | 22.9 † | 9.5 |
| Wong RN-50 | 6.7 | 8.7 † | 18.9 † | 9.3 |
| XCiT-S12 | 26.4 | 26.3 | 43.7 † | 40.3 |
| model | sPGD proj | Sparse-RS | GRS | sAA | ratio | |
|---|---|---|---|---|---|---|
| Sehwag RN-18 | 20 | 138 | 423 | 139 | 699 | 5.0 |
| Gowal PRN-18 | 20 | 172 | 277 | 166 | 622 | 3.7 |
| Std. PRN-18 | 5 | 117 | 292 | 138 | 527 | 3.8 |
| model | loc | lin | drop | br | add. | ratio 100 | ratio 1000 | fill | temp. |
|---|---|---|---|---|---|---|---|---|---|
| Std. PRN-18 | 0.00 | -0.09 | 0.14 | 0.23 | 0.95 | 1.8 | 1.0 | 1.21 | 0.79 |
| Gowal PRN-18 | 0.28 | 0.19 | 0.17 | 0.31 | 0.99 | 4.5 | 2.2 | 1.48 | 1.50 |
| Sehwag RN-18 | 0.26 | 0.19 | 0.25 | 0.33 | 0.99 | 4.7 | 2.3 | 2.14 | 1.09 |
| Cui WRN-28 | 0.22 | 0.17 | 0.07 | 0.29 | 0.99 | 2.9 | 2.5 | 1.82 | 1.36 |
| Wang WRN-28 | 0.24 | 0.19 | 0.07 | 0.29 | 0.99 | 4.0 | 2.4 | 1.60 | 1.53 |
| XCiT-S12 | 0.24 | 0.18 | 0.37 | 0.26 | 0.98 | 3.8 | 2.1 | 1.29 | 1.66 |
| model | kurtosis | top 1% (%) | pixels at | acceptance / 4 / unif. | drop cost / 4 / unif. | uniform add: unif. / cold drop |
|---|---|---|---|---|---|---|
| Std. PRN-18 | 20 | 4.1 | 625 | 0.004 / 0.002 / 0.002 | 2.307 / 2.356 / 2.380 | – |
| Gowal PRN-18 | 28 | 4.6 | 521 | 0.086 / 0.018 / 0.012 | 0.263 / 0.263 / 0.267 | 0.012 / 0.015 |
| Sehwag RN-18 | 24 | 4.7 | 492 | 0.082 / 0.021 / 0.014 | 0.190 / 0.203 / 0.210 | – |
| Cui WRN-28 | 31 | 4.8 | 503 | 0.066 / 0.023 / 0.018 | 0.235 / 0.231 / 0.232 | – |
| Wang WRN-28 | 31 | 4.5 | 533 | 0.089 / 0.020 / 0.015 | 0.237 / 0.240 / 0.243 | – |
| XCiT-S12 | 19 | 3.8 | 671 | 0.077 / 0.018 / 0.012 | 0.141 / 0.154 / 0.161 | – |
| model | bin | predicted | true |
|---|---|---|---|
| Salman RN-18 | top 0.1% | ||
| Salman RN-18 | 0.1–1% | ||
| Salman RN-18 | 1–10% | ||
| Salman RN-18 | rest | ||
| Wong RN-50 | top 0.1% | ||
| Wong RN-50 | rest |
| model | sAA [7] | GRS [3] | GRS 0 [3] | GRS 0 2 seeds [6] | GRS 0 23k [6.9] | proj unproj [6] | |||
|---|---|---|---|---|---|---|---|---|---|
| Std. PRN-18 | 5 | 5.7 | 6.0 | 5.8 | 4.6 | 5.2 | 8.6 | 22/12 | 0.12 |
| Std. PRN-18 | 10 | 0.1 | 0.1 | 0.1 | 0.1 | 0.1 | 0.2 | 1/0 | 1.00 |
| Gowal PRN-18 | 20 | 6.3 | 4.6 | 4.3 | 3.3 | 3.6 ∗ | 9.2 | 61/8 | |
| Sehwag RN-18 | 20 | 7.6 | 5.0 | 5.3 | 4.1 | 4.4 ∗ | 9.7 | 75/12 | |
| Cui WRN-28 | 20 | 5.6 | 3.4 | 3.3 | 2.4 | 2.9 ∗ | 9.0 | 28/1 | |
| Wang WRN-28 | 20 | 5.2 | 3.1 | 3.2 | 2.8 | 2.5 ∗ | 8.7 | 29/2 |
| model | proj | unproj | Sparse-RS | sAA | GRS 0 | |||
|---|---|---|---|---|---|---|---|---|
| Std. PRN-18 | 3 | 27.6 | 36.1 | 22.0 | 20.6 | 21.8 | 15/27 | 0.088 |
| Std. PRN-18 | 8 | 1.3 | 7.6 | 1.0 | 0.6 | 0.7 | 1/2 | 1.00 |
| Gowal PRN-18 | 5 | 52.8 | 57.5 | 45.5 | 44.3 | 45.2 | 20/29 | 0.25 |
| Gowal PRN-18 | 10 | 31.3 | 36.4 | 24.9 | 23.6 | 22.5 | 28/17 | 0.14 |
| Gowal PRN-18 | 15 | 17.6 | 24.9 | 11.4 | 10.8 | 9.5 ∗ | 25/12 | 0.047 |
| Gowal PRN-18 | 30 | 1.3 | 4.3 | 1.0 | 0.7 | 0.4 | 4/1 | 0.38 |
Adversarial Attacks
Adversarial attacks exploit crafted inputs, poisoned data, or system interactions to manipulate AI predictions, behavior, privacy, or reliability.
See all 474 papers