TY - GEN
T1 - Attackability Characterization of Adversarial Evasion Attack on Discrete Data
AU - Wang, Yutong
AU - Han, Yufei
AU - Bao, Hongyan
AU - Shen, Yun
AU - Ma, Fenglong
AU - Li, Jin
AU - Zhang, Xiangliang
N1 - Funding Information:
Our research in this publication was supported by funding from King Abdullah University of Science and Technology (KAUST), under award number FCC/1/1976-19-01 and KAUST AI Initiative, and NSFC No. 61828302.
Publisher Copyright:
© 2020 ACM.
PY - 2020/8/23
Y1 - 2020/8/23
N2 - Evasion attack on discrete data is a challenging, while practically interesting research topic. It is intrinsically an NP-hard combinatorial optimization problem. Characterizing the conditions guaranteeing the solvability of an evasion attack task thus becomes the key to understand the adversarial threat. Our study is inspired by the weak submodularity theory. We characterize the attackability of a targeted classifier on discrete data in evasion attack by bridging the attackability measurement and the regularity of the targeted classifier. Based on our attackability analysis, we propose a computationally efficient orthogonal matching pursuit-guided attack method for evasion attack on discrete data. It provides provably computational efficiency and attack performances. Substantial experimental results on real-world datasets validate the proposed attackability conditions and the effectiveness of the proposed attack method.
AB - Evasion attack on discrete data is a challenging, while practically interesting research topic. It is intrinsically an NP-hard combinatorial optimization problem. Characterizing the conditions guaranteeing the solvability of an evasion attack task thus becomes the key to understand the adversarial threat. Our study is inspired by the weak submodularity theory. We characterize the attackability of a targeted classifier on discrete data in evasion attack by bridging the attackability measurement and the regularity of the targeted classifier. Based on our attackability analysis, we propose a computationally efficient orthogonal matching pursuit-guided attack method for evasion attack on discrete data. It provides provably computational efficiency and attack performances. Substantial experimental results on real-world datasets validate the proposed attackability conditions and the effectiveness of the proposed attack method.
UR - http://www.scopus.com/inward/record.url?scp=85090408948&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85090408948&partnerID=8YFLogxK
U2 - 10.1145/3394486.3403194
DO - 10.1145/3394486.3403194
M3 - Conference contribution
AN - SCOPUS:85090408948
T3 - Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
SP - 1415
EP - 1425
BT - KDD 2020 - Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
PB - Association for Computing Machinery
T2 - 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2020
Y2 - 23 August 2020 through 27 August 2020
ER -