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 an 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-of-the-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.
翻译:我们的工作目标是寻找可行的对抗性扰动,以攻击在域名中具有高度绝对投入的分类者。这本质上是一个NP-hard knapsack问题,即随着特征层面的增加,探索空间会变得爆炸性更大。没有域知识的帮助,通过外观方法(如分形和分形)解决这个问题就会受到指数复杂性的影响,但也可以带来任意恶劣的攻击结果。我们通过多臂强盗的组合搜索的镜头来应对这一挑战。我们提出的方法,即FEAT,将每个绝对特征的改变视为在多臂强盗编程中拉动一个手臂。我们的目标是利用Orthoopogonal Matchit(OMP)-增强高度信任(UCB)的探索战略,实现高效和有效的攻击。我们对FEAT的遗憾差距进行理论分析,保证其实际攻击性能。在实证分析中,我们将FAT与其他最先进的域名攻击方法比于不同应用程序中的各种真实的绝对数据集。实质性实验观测证实了我们应用的FAT的可靠性应用性应用率和FAT系统。