OpenNovelty.org

A General Framework for Black-Box Attacks Under Cost Asymmetry

ICLR 2026 Conference SubmissionAnonymous Authors
OpenReview Score: 6.0Download Report PDF
zeroth-order optimizationasymmetric costblack-box adversarial attacks
Abstract:

Traditional decision-based black-box adversarial attacks on image classifiers aim to generate adversarial examples by slightly modifying input images while keeping the number of queries low, where each query involves sending an input to the model and observing its output. Most existing methods assume that all queries have equal cost. However, in practice, queries may incur asymmetric costs; for example, in content moderation systems, certain output classes may trigger additional review, enforcement, or penalties, making them more costly than others. While prior work has considered such asymmetric cost settings, effective algorithms for this scenario remain underdeveloped. In this paper, we introduce asymmetric black-box attacks, a new family of decision-based attacks that generalize to the asymmetric query-cost setup. We develop new methods for boundary search and gradient estimation when crafting adversarial examples. Specifically, we propose Asymmetric Search (AS), a more conservative alternative to binary search that reduces reliance on high-cost queries, and Asymmetric Gradient Estimation (AGREST), which shifts the sampling distribution in Monte Carlo style gradient estimation to favor low-cost queries. We design efficient algorithms that reduce total attack cost by balancing different query types, in contrast to earlier methods such as stealthy attacks that focus only on limiting expensive (high-cost) queries. We perform both theoretical analysis and empirical evaluation on standard image classification benchmarks. Across various cost regimes, our method consistently achieves lower total query cost and smaller perturbations than existing approaches, reducing the perturbation norm by up to 40% in some settings.

Disclaimer
This report is AI-GENERATED using Large Language Models and WisPaper (A scholar search engine). It analyzes academic papers' tasks and contributions against retrieved prior work. While this system identifies POTENTIAL overlaps and novel directions, ITS COVERAGE IS NOT EXHAUSTIVE AND JUDGMENTS ARE APPROXIMATE. These results are intended to assist human reviewers and SHOULD NOT be relied upon as a definitive verdict on novelty.
NOTE that some papers exist in multiple, slightly different versions (e.g., with different titles or URLs). The system may retrieve several versions of the same underlying work. The current automated pipeline does not reliably align or distinguish these cases, so human reviewers will need to disambiguate them manually.
If you have any questions, please contact: mingzhang23@m.fudan.edu.cn

Overview

Overall Novelty Assessment

The paper introduces asymmetric black-box attacks, proposing Asymmetric Search (AS) and Asymmetric Gradient Estimation (AGREST) to handle scenarios where different query types incur different costs. It resides in the 'General Framework for Cost Asymmetry' leaf, which contains only two papers total (including this one and one sibling). This indicates a relatively sparse research direction within the broader taxonomy of decision-based black-box attacks, suggesting the problem formulation itself is not yet heavily explored.

The taxonomy reveals that the broader field includes Decision-Based Attack Techniques (e.g., query-efficient patch attacks), Theoretical Foundations (query complexity bounds), and Game-Theoretic Models (asymmetric information scenarios). The paper's leaf sits under 'Asymmetric Cost-Aware Attack Methods,' which explicitly excludes uniform-cost assumptions and domain-specific evasion methods. Neighboring work like 'Evasion-Focused Methods with Flagged Query Awareness' addresses similar cost concerns but targets security-critical evasion rather than general cost-balancing frameworks, highlighting the paper's broader scope.

Among 26 candidates examined, the analysis found limited prior work overlap. The AS boundary search contribution examined 10 candidates with 1 refutable match, while AGREST examined 6 candidates with none refutable. The general framework contribution also examined 10 candidates with 1 refutable match. These statistics suggest that within the top-26 semantic matches, most contributions appear relatively novel, though the search scope is modest and does not guarantee exhaustive coverage of all relevant prior work in adversarial machine learning.

Based on the limited search scope and sparse taxonomy leaf, the work appears to address an underexplored problem setting. The sibling paper and one refutable candidate per contribution indicate some prior exploration, but the overall field structure suggests this cost-asymmetry framing is not yet crowded. A broader literature review beyond top-26 semantic matches would be needed to confirm whether related ideas exist under different terminology or in adjacent domains.

Taxonomy

Core-task Taxonomy Papers
6
3
Claimed Contributions
26
Contribution Candidate Papers Compared
2
Refutable Paper

Research Landscape Overview

Core task: decision-based black-box adversarial attacks under asymmetric query costs. The field addresses scenarios where attackers must craft adversarial examples by querying a target model without access to internal parameters or gradients, and where different types of queries incur different costs. The taxonomy organizes this landscape into four main branches: Asymmetric Cost-Aware Attack Methods focus on practical algorithms that explicitly account for varying query expenses; Decision-Based Attack Techniques encompass broader strategies that rely solely on final classification decisions; Theoretical Foundations and Complexity Analysis examine the fundamental limits and computational hardness of such attacks; and Game-Theoretic Models with Asymmetric Information study the strategic interplay between attackers and defenders when information or resources are unevenly distributed. Representative works like Query-Efficient Patch Attack[3] and Query Complexity Attacks[6] illustrate how query budgets shape attack design, while efforts such as Evading Without Breaking Eggs[1] and DoS Asymmetric Information[2] highlight the diverse settings where cost asymmetries arise. A particularly active line of work centers on developing general frameworks that balance attack effectiveness against heterogeneous query costs, contrasting with methods that optimize purely for query count or perturbation size. Black-Box Cost Asymmetry[0] sits within the Asymmetric Cost-Aware Attack Methods branch, specifically under a General Framework for Cost Asymmetry, positioning it alongside Rewriting Budget Framework[5], which similarly addresses budget constraints in adversarial settings. Compared to Query-Efficient Patch Attack[3], which emphasizes minimizing total queries in a patch-based scenario, Black-Box Cost Asymmetry[0] appears to offer a broader treatment of cost heterogeneity across query types. The main open questions revolve around how to optimally allocate limited budgets when different queries yield different information gains, and how theoretical complexity bounds translate into practical attack strategies under real-world cost structures.

Claimed Contributions

Asymmetric Search (AS) for boundary search under cost asymmetry

AS is a boundary search method that splits search intervals according to the cost ratio between high-cost and low-cost queries, rather than equally as in binary search. This minimizes expected total cost instead of merely minimizing the number of queries.

10 retrieved papers
Can Refute
Asymmetric Gradient Estimation (AGREST) for Monte Carlo gradient estimation

AGREST shifts the sampling center away from the boundary point toward the low-cost region and reweights high-cost and low-cost queries differently. This reduces the frequency of high-cost queries while maintaining effective gradient approximation.

6 retrieved papers
General framework for decision-based attacks under arbitrary query cost asymmetry

The authors propose a versatile framework that handles arbitrary cost ratios between high-cost and low-cost queries. Unlike prior stealthy attacks that assume zero cost for benign queries, this framework balances different query types to reduce total attack cost.

10 retrieved papers
Can Refute

Core Task Comparisons

Comparisons with papers in the same taxonomy category

Contribution Analysis

Detailed comparisons for each claimed contribution

Contribution

Asymmetric Search (AS) for boundary search under cost asymmetry

AS is a boundary search method that splits search intervals according to the cost ratio between high-cost and low-cost queries, rather than equally as in binary search. This minimizes expected total cost instead of merely minimizing the number of queries.

Contribution

Asymmetric Gradient Estimation (AGREST) for Monte Carlo gradient estimation

AGREST shifts the sampling center away from the boundary point toward the low-cost region and reweights high-cost and low-cost queries differently. This reduces the frequency of high-cost queries while maintaining effective gradient approximation.

Contribution

General framework for decision-based attacks under arbitrary query cost asymmetry

The authors propose a versatile framework that handles arbitrary cost ratios between high-cost and low-cost queries. Unlike prior stealthy attacks that assume zero cost for benign queries, this framework balances different query types to reduce total attack cost.

Table of Contents