Non-Lipschitz Attack: A More Sparse Adversarial Attack via Non-Lipshitz $\ell_{p}$ Regularization

Abstract

Deep neural networks are considerably vulnerable to adversarial attacks. Therein, sparse attacks mislead image classifiers with a sparse, pixel-level perturbation that alters few pixels, and have much potential in physical world applications. The existing sparse attacks are mostly based on ${\mathcal{l}}_{0}$ optimization, and there are few theoretical results in these works. In this paper, we propose a novel sparse attack approach named the non-Lipschitz attack (NLA). For the proposed ${\mathcal{l}}_{p}(0<p<1)$ regularization attack model, we derive a lower bound theory that indicates a support inclusion analysis. Based on these discussions, we naturally extend previous works to present an iterative algorithm with support shrinking and thresholding strategies, as well as an efficient ADMM inner solver. Experiments show that our NLA method outperforms comparative attacks on several datasets with different networks in both targeted and untargeted scenarios. Our NLA achieves the 100% attack success rate in almost all cases, and the pixels perturbed are roughly 14% fewer than the recent ${\mathcal{l}}_{0}$ attack FMN- ${\mathcal{l}}_{0}$ on average.

Keywords

Sparse adversarial attack / $\ell_{p}(0<p<1)$ regularization / lower bound theory / support shrinkage / ADMM