Source-linked AI summary
Query Strategies for Evading Convex-Inducing Classifiers
Blaine Nelson, Benjamin I. P. Rubinstein, Ling Huang, Anthony D. Joseph, Steven J. Lee, Satish Rao, J. D. Tygar
TL;DR
The paper asks how an adversary can find low-cost instances that evade a queried classifier. It develops membership-query algorithms for convex-inducing classifiers and shows that searchability depends on the cost norm and which class is convex.
Problem
The paper studies how an adversary can query a detector to find a low-cost undetected instance, addressing blind spots in detection systems.
Source: §1 · p. 2Method
The paper develops membership-query algorithms that directly search for near-minimal-cost evading instances for convex-inducing classifiers without reverse-engineering their decision boundaries.
Source: §1 · p. 2, §5 · p. 25Results
For p=1, convex-inducing classifiers are ε-IMAC searchable for both positive and negative convexity; for p>1, positive convexity is not searchable for all ε, and for p=2 no efficient algorithm exists for any fixed ε.
Source: §5 · p. 25Takeaways & Limitations
The algorithms provide analysts tools to understand filter vulnerabilities, though real-world obstacles may make them difficult for adversaries to use.
Source: §5 · p. 25Real-world use may be constrained by partially observable or noisy queries and partially known feature sets.
Source: §5 · p. 25
Abstract
from arXiv · showhide
Classifiers are often used to detect miscreant activities. We study how an adversary can systematically query a classifier to elicit information that allows the adversary to evade detection while incurring a near-minimal cost of modifying their intended malfeasance. We generalize the theory of Lowd and Meek (2005) to the family of convex-inducing classifiers that partition input space into two sets one of which is convex. We present query algorithms for this family that construct undetected instances of approximately minimal cost using only polynomially-many queries in the dimension of the space and in the level of approximation. Our results demonstrate that near-optimal evasion can be accomplished without reverse-engineering the classifier's decision boundary. We also consider general lp costs and show that near-optimal evasion on the family of convex-inducing classifiers is generally efficient for both positive and negative convexity for all levels of approximation if p=1.
1. Introduction
The paper studies how an adversary can use classifier queries to find low-cost undetected instances, addressing blind spots in detection systems. It generalizes near-optimal evasion to convex-inducing classifiers and contrasts its direct-search approach with prior work.
1. Introduction
- Adversaries can query fixed or learning-based detectors to find low-cost instances that evade filtering, using as few queries as possible.The introduction motivates this with a spammer seeking to minimally modify a message so it is no longer classified as spam.Source: §1 · p. 2
- Convex-inducing classifiers partition the instance space into two sets, one of which is convex, and include the linear classifiers studied by Lowd and Meek (2005).The family also includes several anomaly-detection and quadratic classifiers.Source: §1 · p. 2, §1.1 · p. 3
1.1 Related Work
- The algorithms directly search for a low-cost negative instance without fully estimating the decision boundary or reverse-engineering the classifier’s state.This contrasts with Lowd and Meek (2005), who reverse-engineered linear classifiers.Source: §1 · p. 2, §1.1 · p. 3
- The algorithms use polynomially many queries in the instance-space dimension, and K-step MultiLineSearch uses fewer queries than the prior reverse-engineering technique in the linear case.The paper assumes the classifier does not adapt during evasion; adapting classifiers are treated as complementary work.Source: §1.1 · p. 3
- Earlier sequence-based intrusion-detector evasion used offline analysis to construct modifications, whereas this paper optimizes modifications through classifier queries.Active learning also uses query strategies, but its objectives differ from near-optimal evasion.Source: §1.1 · p. 3
2. Problem Setup
The setup models an adversary who can query an unknown fixed binary classifier from a known family and seeks a low-cost negative instance near a desired positive instance. It defines multiplicative and additive near-optimality and the query-search framework, including the assumptions and scope of efficient evasion.
2. Problem Setup
- The adversary knows the feature-space representation and classifier family, can query any point, and targets a fixed unknown binary classifier with known examples from both classes.The feature space is D-dimensional Euclidean space; the negative class represents normal instances.Source: §2 · pp. 3–4
2.1 Adversarial Cost
- The adversary minimizes a weighted ℓp cost from a desired positive instance to a negative instance, with the primary goal of finding a negative instance within a factor of (1 + ǫ) of minimal cost.Weighted ℓ1 costs capture feature-specific modification costs; the goal is to find an ǫ-IMAC efficiently with few queries.Source: §2.1 · pp. 4–5
2.2 Search Terminology
- Binary search narrows upper and lower bounds on minimal adversarial cost; additive search uses arithmetic midpoints, while multiplicative search operates on the logarithm of cost.The search stops when the bounds meet the selected additive or multiplicative accuracy criterion.Source: §2.2 · pp. 5–6
2.3 Near-Optimal Evasion
- Near-optimal evasion requires finding one ǫ-IMAC, not reconstructing the classifier: a common near-optimal instance can be found while leaving much of the classifier unspecified.The paper defines efficiency as polynomially many membership queries in dimension D and the number of steps Lǫ.Source: §2.3 · pp. 6–7
2.4 Multiplicative vs. Additive Optimality
- Multiplicative optimality requires a strictly positive lower cost bound; if the desired instance lies on the positive-class boundary, no ǫ-IMAC exists for any ǫ > 0.The text notes that an algorithm can efficiently establish a positive lower bound when one exists.Source: §2.4 · p. 8
- When multiplicative near-optimality cannot be achieved efficiently at sufficiently small ǫ, the paper rules out efficient additive near-optimality at corresponding accuracy levels, and in a corollary at any η.Additive accuracy depends on cost units, whereas multiplicative accuracy is scale invariant.Source: §2.4 · p. 8
3. Evasion of Convex Classes
The section studies query-based evasion of classifiers with convex positive or negative classes, including query lower bounds and methods for finding approximately minimum-cost evasions. It develops adaptations and randomized intersection, sampling, and optimization procedures, including SetSearch’s reuse of successful searches over ℓ1 balls.
3. Evasion of Convex Classes
- Convex-inducing classifiers include cases where either class is convex, but the resulting search problems are asymmetric: positive-class convexity supports vertex tests, while negative-class convexity requires a different algorithm.For a convex negative class, the section presents an efficient ℓ1 algorithm and a polynomial random algorithm for any convex cost.Source: §3 · p. 9
- For convex positive classes under ℓ1 cost, querying the 2·D vertices of each cost ball lets binary search find an ǫ-IMAC using O(D·Lǫ) queries.A negative vertex gives an upper bound on the minimum adversarial cost; if all vertices are positive, convexity establishes a lower bound.Source: §3 · pp. 11–12
3.1.1 K-step Multi-Line Search
- K-step MultiLineSearch combines depth-first and breadth-first queries to address the pruning weaknesses of either strategy on its own.Choosing K = ⌈√Lǫ⌉ balances the strategies and yields a better worst-case complexity than either approach alone.Source: §3.1.1 · pp. 12–13
3.1.2 Lower Bound
- The lower-bound subsection analyzes the queries required for ǫ-IMAC search when the positive class is convex, for both additive and multiplicative optimality.Its multiplicative-optimality statement assumes a positive lower bound on the minimum adversarial cost.Source: §3.1.2 · p. 13
- The lower bounds show that K-step MultiLineSearch has close-to-optimal query complexity for ℓ1 costs.The stated algorithm uses O(Lε + √(LεD)) queries; the lower bounds also apply to arbitrary ℓp costs, while Section 4 gives stronger bounds for p > 1.Source: §3.1.2 · p. 15
3.1.3 Special Cases
- For linear classifiers, an adapted search eliminates as many as half the directions and improves on reverse engineering while applying to a broader family.When feature costs are infinite, those features are removed from the search directions; zero-cost features invalidate near-optimality guarantees, though a decaying-weight strategy may find a 0-IMAC.Source: §3.1.3 · p. 15
- SpiralSearch establishes an existing positive lower bound in O(Lε + D) queries and supplies pruned directions for subsequent MultiLineSearch.It uses a halving search along a direction and then queries remaining directions at that cost; without any lower bound, no algorithm can find an ε-IMAC.Source: §3.1.3 · pp. 15–16
- Without an initial negative example, the algorithms probe ℓ1 balls of doubly exponentially increasing cost until finding one, then initialize MultiLineSearch.For convex feasible sets, randomized query-based minimization of weighted ℓ1 cost finds an ε-IMAC with high probability in at most Lε repetitions of binary search.Source: §3.1.3 · pp. 16–17
3.2.1 Intersection of Convex Sets
- IntersectSearch uses membership-query sampling and separating hyperplanes to shrink a bounded convex search body until it finds an intersection or deems one unlikely.With high probability, its cuts reduce volume substantially when the body is near-isotropic, and it terminates after O(D log(R/r)) unsuccessful iterations.Source: §3.2.1 · pp. 17–18
3.2.2 Sampling from a Queriable Convex Body
- Hit-and-run sampling requires a near-isotropic body; the algorithm uses retained samples to adapt directions to the body's covariance and replenish samples after cuts.RoundingBody provides the initial near-isotropic position as preprocessing for the search algorithms.Source: §3.2.2 · p. 19
3.2.3 Optimization over ℓ1 Balls
- The outer optimization loop can run RoundingBody once as preprocessing because its inputs remain the same across iterations.Source: §3.2.3 · p. 19
- The separating hyperplane depends only on xA, not target cost Ct, and is valid for every ℓ1-ball with cost C < A(y).Because BC(A1) ⊂ BCt(A1) when C < Ct, a successful IntersectSearch state for the Ct-ball can initialize subsequent searches at lower costs.Source: §3.2.3 · p. 20
4. General ℓp Costs
The section extends near-optimal evasion to general ℓp costs and shows that efficient query strategies depend on the cost and which classifier set is convex. Weighted ℓ1 costs admit polynomial-query strategies across both convexity cases, while ℓp costs with p > 1 face exponential lower bounds for some approximation levels.
4. General ℓp Costs
- Only weighted ℓ1 costs are known to have randomized polynomial-query strategies when either the positive or negative classifier set is convex.For general ℓp costs, some approximation levels require exponentially many queries in dimension and approximation level.Source: §4 · p. 20
4.1 Convex Positive Set
- A convex hull of positive queries provides a lower bound on an ℓp cost ball, while negative queries provide an upper bound; the figure varies query configurations and cost norms.The illustrated positive-query configurations are random, coordinate-axis, and circular.Source: §4.1 · pp. 20–21, Figure 3 · p. 21
4.1.1 Bounding ℓp Balls
- Multi-line search achieves ε-multiplicative optimality when M search directions yield a sufficiently tight convex-hull bound; for p = 1, 2D coordinate directions suffice for any ε > 0.The direction configuration's bound and the search's approximation factor together determine whether the target ε is met.Source: §4.1.1 · pp. 22–23
4.1.2 Multiline Search for p < 1
- For p < 1, the 2D corners of the hyperoctahedron suffice for efficient search at every ε > 0, but whether fewer directions suffice remains open.Source: §4.1.2 · p. 23
4.1.3 Multiline Search for p > 1
- For p > 1, multiline-search-type algorithms efficiently find ε-IMACs in certain approximation ranges; for some ε, every algorithm needs at least α_{p,ε}^D membership queries in the worst case.Source: §4.1.3 · p. 23
4.1.4 Multiline Search for p = 2
- For ℓ2 costs, no algorithm achieves ǫ-multiplicative optimality for any fixed ǫ > 0 with only polynomially many queries in D; at fixed D, Theorem 13 suggests reasonable approximations may be achievable as αǫ → 1.Source: §4.1.4 · p. 24
4.2 Convex Negative Set
- For convex negative sets, SetSearch applies to any convex cost when separating hyperplanes for its sublevel sets can be computed; non-convex costs may make minimization hard.The paper identifies weighted ℓp costs with p < 1 as an example of non-convex costs.Source: §4.2 · pp. 24–25
5. Conclusions and Future Work
The paper gives membership-query algorithms for near-optimal evasion of convex-inducing classifiers, without reverse-engineering the classifier. It identifies cost and convexity conditions that determine when such search is efficient.
5. Conclusions and Future Work
- The algorithms achieve polynomial-query ε-IMAC search by eliminating inconsistent hypotheses and concentrating queries near a minimum-cost evading instance.The paper says this works despite the size of the family of convex-inducing classifiers.Source: §5 · p. 25
- For ℓp costs, efficient search for both positive and negative convexity at every approximation level is established when p = 1.For p > 1, the results are asymmetric: the Ellipsoid method applies to convex negative sets, while efficient search for all ε is impossible for convex positive sets.Source: §5 · p. 25
- The paper identifies partial observability, noisy or restricted queries, and unknown feature mappings as real-world obstacles to applying its search algorithms.It calls for further study of partial observability and approximate querying, and of designing more secure filters.Source: §5 · p. 25
Appendix A. Proof of Theorems for MultiLineSearch Algorithms
The proof analyzes K-step MultiLineSearch against a classifier that chooses responses to maximize query cost. It bounds the work by distinguishing iterations that shrink the candidate gap from those that eliminate feasible directions.
Appendix A. Proof of Theorems for MultiLineSearch Algorithms
- The proof assumes conservatively that only case-1 iterations reduce the gap, and termination requires at least L_ε binary-search steps across those iterations.Each case-1 iteration contributes exactly K steps.Source: Appendix A · p. 28
- In case 1, each iteration uses K + |W_t| − 1 queries and reduces the candidate multiplicative gap by a factor of 2^-K, without eliminating directions.The analysis bounds |W_t| by the initial feasible-direction set W.Source: Appendix A · pp. 27–28
- In case 2, an iteration uses K + E_t queries and eliminates E_t ≥ 1 feasible directions, so there can be at most |W| − 1 such iterations.The malicious classifier may choose E_t = 1 to limit the number of directions eliminated per iteration.Source: Appendix A · p. 28
Appendix B. Proof of Lower Bounds
The lower-bound proofs construct convex-inducing classifiers that agree on queried instances but have incompatible near-optimal evasion sets. This establishes that too few membership queries cannot guarantee a shared near-optimal answer.
Appendix B. Proof of Lower Bounds
- The proof’s indistinguishable-classifier argument requires queries to constrain all consistent classifiers to share a point among their ε-IMAC sets.It assumes the queries are membership queries in D-dimensional space.Source: Appendix B · p. 29
- Fewer than the stated L_ε membership queries can leave two consistent convex-inducing classifiers with no common ε-IMAC.The construction contrasts classifiers whose positive sets are cost balls enclosing the positive queries, with different MAC values.Source: Appendix B · p. 30
- For the additive criterion, the construction likewise yields classifiers with no common η-IMAC when the query count falls below the stated L^(+) bound.The passage states their MAC values differ by more than η.Source: Appendix B · p. 30
Appendix C. Proof of Theorem 12
The proof of Theorem 12 builds a convex set consistent with positive queries by covering their orthants, then uses hypercube covering bounds to limit how few queries can suffice. For 1 < p < ∞, the required covering grows exponentially with dimension for the stated accuracy range.
Appendix C. Proof of Theorem 12
- For 1 < p < ∞, the hypercube covering argument requires exponentially many covering vertices to achieve the stated accuracy.The proof invokes a covering-number bound for the D-dimensional hypercube graph.Source: Appendix C · pp. 31, 35
- The proof forms a convex set G from regions in orthants containing positive queries, then uses its largest enclosed ℓp ball to upper-bound the alternative classifier’s MAC.The construction uses a covering of the orthants represented as vertices of a D-dimensional hypercube graph.Source: Appendix C · p. 33
- For p = ∞, the proof gives a lower bound M > α^D for 0 < ε < 1, with α = 2(1 − H(ε/(1 + ε))) > 1.Here H is the entropy function defined in the proof.Source: Appendix C · pp. 31, 35
Appendix D. Proof of Theorem 13
The proof turns query sufficiency into a spherical-covering requirement: if projected positive queries fail to cover the relevant hypersphere, an alternative consistent classifier can prevent ε-multiplicative optimality.
Appendix D. Proof of Theorem 13
- A spherical cap is the intersection of a halfspace with a hypersphere, parameterized by radius and half-angle φ.Source: Appendix D · p. 36
- For ε-optimality, the queries must constrain every consistent classifier to have a common point among its ε-IMAC sets.Source: Appendix D · p. 37
- Projected positive queries define an enlarged convex hull; an uncovered φ*-cap yields an alternative classifier with MAC below C−_0/(1 + ε).Source: Appendix D · p. 38
- An φ*-covering is necessary for ε-multiplicative optimality, and Lemma 16 supplies a lower bound on the number of caps required.Source: Appendix D · pp. 36, 38