Query strategies for evading convex-inducing classifiers

摘要: Classifiers are often used to detect miscreant activities. We study how an adversary can systematically query a classifier elicit information that allows the attacker evade detection while incurring near-minimal cost of modifying their intended malfeasance. generalize theory Lowd and Meek (2005) family convex-inducing classifiers partition feature space into two sets, one which is convex. present algorithms for this construct undetected instances approximately minimal using only polynomially-many queries in dimension level approximation. Our results demonstrate nearoptimal evasion be accomplished without reverse engineering classifier's decision boundary. also consider general lp costs show near-optimal on generally efficient both positive negative convexity all levels approximation if p = 1.