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

• DOI: 10.48550/arxiv.2212.06836
• Publication Date: 2022-01-01
• 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 an 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 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.