Source-linked AI summary
OASIS: Optimizing Attacker Sequences for Hard-Label Black-Box Text Attacks
Qian Chen, Shiliang Xiao, Yuzhi Liang
TL;DR
Hard-label black-box text attacks must work with label-only feedback and limited queries, while different attackers succeed on partly distinct sample subsets. OASIS searches candidate sequences for a fixed reusable chain, and experiments show it consistently outperforms strong standalone baselines and manual compositions across datasets, victim models, and large language models.
Problem
Hard-label black-box text attacks operate with label-only feedback and limited query budgets, while existing methods mainly improve individual attackers or manually combine them despite their partly distinct successful-sample sets.
Source: §1 · p. 1Method
OASIS performs bi-objective attack-chain search for high attack success rate and low perturbation, then reuses the selected fixed chain sequentially on target samples.
Source: §1 · p. 2, §3.1 · p. 4Results
Across datasets, victim models, and large language models, OASIS consistently outperforms strong standalone baselines and manual compositions.
Source: §1 · p. 2, §5 · p. 12Takeaways & Limitations
The results frame attacker composition as an optimization target because chains can exploit complementarity among attackers that succeed on different sample subsets.
Source: §1 · p. 2, §4.2 · p. 7
Abstract
from arXiv · showhide
Different attack methods follow different search trajectories, they succeed on different subsets of samples, whereas existing hard-label black-box text attacks mainly focus on improving individual attackers or manually combining them. We present OASIS, a method for optimizing attacker sequences in hard-label black-box text attacks. OASIS first performs a one-time bi-objective attack chain search over candidate sequences to balance attack success rate and perturbation, and then reuses the selected fixed global chain during attack chain execution. Experiments across multiple datasets, victim models, and large language models show that OASIS consistently outperforms strong standalone baselines and simple manually constructed chains. These results suggest that attacker composition is not merely an implementation choice, but a practical optimization target for improving hard-label black-box text attacks.
1 Introduction
Hard-label black-box text attacks use label-only feedback under limited query budgets, and different attackers succeed on partly distinct sample subsets. OASIS searches for a reusable attacker chain, and experiments show it outperforms strong standalone attackers and manual compositions.
1 Introduction
- Different attackers follow distinct search trajectories and succeed on partly non-overlapping sample subsets, motivating chain search that exploits their complementarity.The stated goal is to maximize overall coverage of successful attacks under label-only feedback and limited query budgets.Source: §1 · pp. 1–2
- Existing hard-label black-box attacks mainly improve individual attackers or manually combine methods, without explicitly optimizing attacker complementarity.The introduction names OpenFact as an empirical hand-crafted combination.Source: §1 · p. 1
- OASIS searches candidate attack chains on a local model and dataset, jointly optimizing attack success rate and perturbation before selecting a fixed chain for reuse.NSGA-II searches the Pareto front, and TOPSIS selects the global chain.Source: §1 · p. 1
- Across multiple target datasets, victim models, and large language models, OASIS consistently outperforms strong standalone attackers and manually constructed chains.The selected chain also remains effective beyond the local search setting.Source: §1 · p. 2
- The paper frames attacker composition as a global attack-chain search problem that selects a fixed, reusable chain by capturing cross-attacker complementarity.The contribution claims describe experiments across target datasets and victim models as outperforming strong standalone attackers and manually constructed chains.Source: §1 · p. 2
2 Related Work
Textual adversarial attacks are categorized by the adversary’s knowledge of the victim model. In hard-label black-box settings, prior work spans single-attacker search and manually combined pipelines, but does not explicitly optimize attacker complementarity or execution order.
2 Related Work
- Textual attack methods are categorized by victim-model knowledge, with white-box methods using gradients or confidence scores and soft-label black-box methods using confidence-guided substitutions or generation.The section also notes toolkit support such as TextAttack.Source: §2 · p. 2
- Hard-label black-box attacks expose only the victim’s predicted label, and much prior work improves one attacker’s search, direction estimation, or token selection.Examples include genetic and hybrid search, boundary-guided methods, and discrete perturbation heuristics.Source: §2 · p. 2
- OpenFact manually combines attack algorithms, whereas prior combinations do not explicitly optimize attacker complementarity or execution order.This contrast motivates treating attacker composition as a search problem.Source: §2 · p. 2
3 Methodology
OASIS exploits complementary attack success by optimizing an ordered attacker sequence rather than choosing attackers solely by standalone performance. It searches candidate chains locally for a balanced ASR–Pert trade-off, selects one fixed chain, and reuses it across target datasets and models.
3 Methodology
- OASIS targets cross-attacker complementarity because different attackers succeed on different subsets of samples.The method seeks a chain whose components work well together to improve successful-attack coverage.Source: §3 · p. 3
3.1 Attack Chain Formulation
- The attack chain is an ordered, nonrepeating attacker sequence, and valid adversarial outputs must meet label-flip, perturbation, similarity, and query-budget constraints.The chain objective jointly favors high ASRL and low PertL.Source: §3.1 · pp. 3–4
3.2 Attack Chain Search via NSGA-II
- NSGA-II searches candidate chains on a local development set under the joint ASR–Pert objective, then returns a Pareto front for selection.The one-time search evaluates 100 development samples; order-preserving crossover and swap-or-replace mutation generate offspring.Source: §3.2 · p. 4
3.3 TOPSIS-based Chain Selection
- TOPSIS selects a fixed global chain from the Pareto front by balancing high ASR against low Pert rather than optimizing one metric alone.It chooses the solution closest to the normalized ideal point, avoiding chains that excel on only one local objective.Source: §3.3 · p. 5
3.4 Attack Chain Execution
- During execution, the selected chain runs sequentially under a shared query budget; empty or invalid candidates lead to the next attacker trying the original input.All candidates are checked against the same original text, and execution stops when the budget is exhausted.Source: §3.1 · p. 4, §3.4 · p. 5
4 Experiments
The experiments examine fixed-budget performance, query-budget and perturbation sensitivity, transfer across datasets and models, manual chains, and component effects. The setup searches for one chain locally, then reuses it across target settings.
4 Experiments
- Six research questions cover baseline comparison, varying query budgets and perturbation thresholds, transfer, manual chains, and OASIS components.The study uses a fixed query budget for its baseline comparison.Source: §4 · p. 5
4.1 Experimental Setup
- MR is the local search dataset; SST-2, AG News, Yahoo, and Yelp are target datasets, with Table 1 summarizing dataset statistics.The table covers scale, label space, and average input length.Source: §4.1 · p. 6, Table 1 · p. 6
- Evaluations span WordCNN and WordLSTM, DistilBERT, and Qwen2.5 in zero-shot and fine-tuned settings; BERT is the local search model.The other evaluated victims serve as target models.Source: §4.1 · p. 6
- OASIS is compared with representative hard-label attackers and two sequential OpenFact combinations, BAm2&Genetic and GSWSE&T.The combinations test whether a searched chain can outperform manually designed compositions.Source: §4.1 · p. 6
- ASR measures successful flips among originally correct samples, while Pert measures modified-token fraction and Sim measures semantic preservation.The same sentence-level similarity module is used for Sim and the attack constraint.Source: §4.1 · p. 6
- NSGA-II searches once for an ordered, without-replacement length-3 chain from seven hard-label attackers, maximizing ASR and minimizing Pert on 100 correctly classified local samples; TOPSIS selects a fixed global chain reused across target datasets and models.Search and final evaluation constraints use B = 1000, ρ = 0.1, and τ = 0.9; each target evaluation uses 1000 samples, with results averaged over three independent runs.Source: §4.1 · p. 7
4.2 Overall Result (RQ1)
OASIS achieves higher ASR than strong standalone attackers while keeping perturbation comparable, and its results also surpass the OpenFact combination baselines. The paper attributes the gains to complementary attacker coverage.
4.2 Overall Result (RQ1)
- 52.3% ASR on WordCNN for SST-2 exceeds LeapAttack and HQAAttack (both 36.5%), with similar Pert (6.4%).The same pattern appears on Qwen2.5-FT for SST-2: OASIS reaches 42.0% ASR versus HQAAttack (37.5%) and LeapAttack (35.4%), with comparable perturbation (6.8%).Source: §4.2 · p. 7
- OASIS also consistently surpasses the two combination baselines adapted from OpenFact.The authors explain that OASIS searches automatically, unlike OpenFact’s manually constructed combinations.Source: §4.2 · p. 7
- Different attackers succeed on different sample subsets, allowing later chain members to cover residual cases missed by earlier attackers.The paper identifies this complementarity as a better explanation for the gain.Source: §4.2 · p. 7
4.3 ASR under Varying Query Budgets (RQ2)
Across five tested query budgets, OASIS stays above the baselines on Qwen2.5-FT for SST-2 and Yahoo. The reported gains reflect broader sample coverage, not additional query budget.
4.3 ASR under Varying Query Budgets (RQ2)
- Across five budgets, OASIS stays above the baselines on Qwen2.5-FT for both SST-2 and Yahoo.The tested budgets are B ∈ {100, 300, 500, 700, 900}.Source: §4.3 · p. 7
- On Yahoo, the gap becomes more visible once the budget is large enough for later attackers to act on residual hard examples.The passage reports a less pronounced gap on SST-2.Source: §4.3 · p. 7
- Later attackers receive no extra budget; the improvement is attributed to broader sample coverage rather than budget inflation.Source: §4.3 · p. 7
4.4 ASR under Varying PERT (RQ3)
Across perturbation thresholds, OASIS remains on or near the favorable ASR–Pert frontier, especially on Yahoo. Its balanced chain selection is consistent with smaller ASR drops under stricter perturbation limits.
4.4 ASR under Varying PERT (RQ3)
- On Yahoo, OASIS traces the upper ASR–Pert frontier across almost the entire threshold range for both victim models; on SST-2, curves are closer.OASIS remains on or near the favorable frontier on SST-2.Source: §4.4 · p. 7
- NSGA-II jointly optimizes ASR and Pert, and TOPSIS selects a balanced chain rather than one that attains high ASR through larger edits.Source: §4.4 · p. 7
- As the perturbation threshold becomes stricter, the selected chain shows a smaller ASR drop while later attackers cover some valid low-perturbation examples missed earlier.Source: §4.4 · p. 7
4.5 Transferability of the Fixed Global Chain (RQ4)
The TOPSIS-selected fixed chain stays on or near the favorable ASR–Pert frontier across target datasets and models. It also achieves higher ASR than manually constructed chains on SST-2 and Yahoo, surpassing best-3 on Yahoo by 7.0% despite slightly higher Pert.
4.5 Transferability of the Fixed Global Chain (RQ4)
- Across target datasets and models, the TOPSIS-selected chain stays on or near the favorable ASR–Pert frontier.The evaluation covers Yahoo, Yelp, SST-2, and AG on Qwen2.5-FT and DistilBERT.Source: §4.5 · p. 9
- TOPSIS selects the Pareto-front chain nearest the ideal of high ASR and low Pert, favoring a balanced compromise over a single-objective endpoint.The authors connect this selection to the chain's balanced margin across model and dataset shifts.Source: §4.5 · p. 9
4.6 Comparison with Manually Constructed Chains (RQ5)
- On SST-2 and Yahoo, OASIS achieves higher ASR than best-3 and random-3; on Yahoo, it exceeds best-3 by 7.0% with slightly higher Pert.The comparison uses Qwen2.5-FT; the additional successful Yahoo cases are harder and often require perturbing more words.Source: Table 3 · p. 9, §4.6 · p. 9
4.7 Ablation Study (RQ6)
Ablations show that removing any of OASIS's three components hurts performance, especially on Yahoo. The authors also relate the gains to attacker complementarity: overlapping standalone attackers may add limited coverage, while searched chains can capture complementarity.
4.7 Ablation Study (RQ6)
- The ablation compares ASR-only search, random search in the same chain space, and random Pareto-front selection against OASIS's component choices.The reduced variants respectively remove multi-objective optimization, NSGA-II search, or TOPSIS selection.Source: §4.7 · p. 9
- The degraded variants often have lower Pert because they succeed on easier, fragile samples that few-word changes can flip, even at random positions.The authors caution that lower Pert here accompanies weaker attack success, not stronger overall performance.Source: §4.7 · p. 10
- On Yahoo, OASIS's ASR of 56.5 falls to 38.8 without TOPSIS, 27.3 without multi-objective optimization, and 28.1 without NSGA-II.Table 4 reports the component ablation results on Qwen2.5-FT.Source: Table 4 · p. 10, §4.7 · p. 10
- On 100 local samples, best-3's HQAAttack, TextHoaxer, and SSPAttack show strong pairwise overlap, while searched chains better capture attacker complementarity.Figure 5's diagonal records successful-sample counts, and darker off-diagonal cells indicate stronger pairwise overlap.Source: §4.7 · pp. 11–12, Figure 5 · p. 11
4.8 Case Study
The case study illustrates cross-attacker complementarity: an attacker that fails or violates quality constraints can be followed by one that finds a valid adversarial example for the same input.
4.8 Case Study
- In four DistilBERT SST-2 examples, later attackers can find valid adversarial examples for inputs where earlier attackers fail to flip the prediction or violate quality constraints.The authors attribute the chain's gain to cross-attacker complementarity rather than any single attacker alone.Source: §4.8 · p. 12
5 Conclusion
OASIS treats attacker composition as a sequence-optimization problem and searches for a reusable global chain. Across datasets, victim models, and large language models, it outperforms strong standalone attackers and simple manual compositions.
5 Conclusion
- Across datasets, victim models, and large language models, OASIS's searched fixed chain consistently outperforms strong standalone baselines and simple manual compositions.The conclusion also reports vulnerability in large language models such as Qwen2.5 in both zero-shot and robust fine-tuned settings.Source: §5 · p. 12