Towards Efficient and Domain-Agnostic Evasion Attack with High-Dimensional Categorical Inputs

Hongyan Bao, Yufei Han, Yujun Zhou, Xin Gao, Xiangliang Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Our work targets at searching feasible adversarial perturbation to attack a classifier with high-dimensional categorical inputs in a domain-agnostic setting. This is intrinsically a NP-hard knapsack problem where the exploration space becomes explosively larger as the feature dimension increases. Without the help of domain knowledge, solving this problem via heuristic method, such as Branch-and-Bound, suffers from exponential complexity, yet can bring arbitrarily bad attack results. We address the challenge via the lens of multi-armed bandit based combinatorial search. Our proposed method, namely FEAT, treats modifying each categorical feature as pulling an arm in multi-armed bandit programming. Our objective is to achieve highly efficient and effective attack using an Orthogonal Matching Pursuit (OMP)-enhanced Upper Confidence Bound (UCB) exploration strategy. Our theoretical analysis bounding the regret gap of FEAT guarantees its practical attack performance. In empirical analysis, we compare FEAT with other state-ofthe-art domain-agnostic attack methods over various real-world categorical data sets of different applications. Substantial experimental observations confirm the expected efficiency and attack effectiveness of FEAT applied in different application scenarios. Our work further hints the applicability of FEAT for assessing the adversarial vulnerability of classification systems with high-dimensional categorical inputs.
Original languageEnglish (US)
Title of host publicationProceedings of the AAAI Conference on Artificial Intelligence
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages9
ISBN (Print)9781577358800
StatePublished - Jun 26 2023

Bibliographical note

KAUST Repository Item: Exported on 2023-08-29
Acknowledgements: The research reported in this paper was partially supported by funding from King Abdullah University of Science and Technology (KAUST).


Dive into the research topics of 'Towards Efficient and Domain-Agnostic Evasion Attack with High-Dimensional Categorical Inputs'. Together they form a unique fingerprint.

Cite this