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

• DOI: 10.1609/aaai.v37i6.25828
• Publication Date: 2023-06-27T17:08:36Z
• Authors: Hongyan Bao; Yufei Han; Yujun Zhou; Xin Gao; Xiangliang Zhang
• Keywords: Categorical variable

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