Abstract
Classifiers are often used to detect miscreant activities. We study how an adversary can efficiently query a classifier to elicit information that allows the adversary to evade detection at near-minimal cost. We focus on the family of convex-inducing classifiers, where either the malicious or benign class forms a convex set.
Introduction
In the adversarial landscape of security, machine learning models act as automated sentinels against spam, malware, and fraud. However, these models are susceptible to evasion. An adversary’s goal is typically not just to bypass the filter, but to do so at a minimal cost. For instance, a spammer seeks to modify a message just enough to evade a filter while maintaining its semantic impact on the recipient.
While previous research established methods for evading linear classifiers through reverse-engineering, this paper generalizes the problem to convex-inducing classifiers. These are models where one of the decision regions (either the "malicious" positive class or the "benign" negative class) is a convex set. The authors provide algorithms to find an $\epsilon$-approximate instance of minimal adversarial cost ($\epsilon$-IMAC) using a near-optimal number of queries.
Methodology
The evasion strategy depends on which side of the decision boundary is convex. The authors move away from full reverse-engineering, which is query-intensive, in favor of direct search approaches.
1. Convex Positive Class ($X_f^+$)
When the set of malicious instances is convex, the authors introduce a $K$-step Multi-Line Search. Standard binary search is often too slow, and full boundary mapping is too expensive. This algorithm balances breadth and depth by querying multiple directions simultaneously but prioritizing those that show the most promise for pruning the search space.
2. Convex Negative Class ($X_f^-$)
If the benign set is convex, finding the minimal cost point is more complex because it may not lie on a simple "corner" of the cost-ball. To address this, the authors adapt a randomized polynomial algorithm utilizing Hit-and-Run sampling and Intersect Search. This method uses a random walk within a bounded convex body to estimate its centroid, determining if it intersects with a specific cost-ball to iteratively narrow down the optimal evasion point.
Key Insights and Query Complexity
- Direct Search vs. Reverse Engineering: The core insight is that one does not need to map the entire decision boundary to find the nearest "exit." By focusing on the shortest path across the boundary, the proposed algorithms achieve significantly better query complexity.
- Broad Applicability: Many common machine learning models, including linear classifiers, anomaly detectors using bounded PCA, and quadratic classifiers, are convex-inducing.
- Efficiency Bounds: The authors establish a theoretical lower bound of $\Omega(D + L)$ queries (where $D$ is the dimension and $L$ is the precision). Their $K$-step algorithm approaches this bound with a complexity of $O(L + \sqrt{L}D)$, outperforming the $O(LD)$ complexity of previous reverse-engineering techniques.
- Lazy Querying: The algorithms employ a "lazy" strategy—once a negative instance is identified at a certain cost level, the search immediately refines its focus, conserving the query budget.
Limitations and Future Directions
Despite the theoretical advancements, several practical challenges remain:
- Inverse Feature Mapping: Translating a mathematical vector back into a functional object (like a valid email or binary) is non-trivial.
- Stochasticity: The current models assume deterministic classifier responses. Real-world systems may exhibit noise or "jitter."
- Online Adaptation: The study assumes a static classifier. If a model employs online learning to adapt to queries, the evasion problem becomes a dynamic game.
- Non-Convexity: Extending these techniques to non-convex models, such as deep neural networks, remains an open research frontier.
Summary updated