Lune

EMNLP Findings2024

CERT-ED: Certifiably Robust Text Classification for Edit Distance

Zhuoqun Huang, Neil G. Marchant, Olga Ohrimenko, Benjamin I. P. Rubinstein

Abstract

With the growing integration of AI in daily life, ensuring the robustness of systems to inferencetime attacks is crucial. Among the approaches for certifying robustness to such adversarial examples, randomized smoothing has emerged as highly promising due to its nature as a wrapper around arbitrary black-box models. Previous work on randomized smoothing in natural language processing has primarily focused on specific subsets of edit distance operations, such as synonym substitution or word insertion, without exploring the certification of all edit operations. In this paper, we adapt Randomized Deletion (Huang et al., 2023) and propose, CERTified Edit Distance defense (CERT-ED) for natural language classification. Through comprehensive experiments, we demonstrate that CERT-ED outperforms the existing Hamming distance method RanMASK (Zeng et al., 2023) in 4 out of 5 datasets in terms of both accuracy and the cardinality of the certificate. By covering various threat models, including 5 direct and 5 transfer attacks, our method improves empirical robustness in 38 out of 50 settings.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

3 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Iron Sharpens Iron: Defending Against Attacks in Machine-Generated Text Detection with Adversarial Training cites BERT-ATTACK: Adversarial Attack Against BERT Using BERT
  • Iron Sharpens Iron: Defending Against Attacks in Machine-Generated Text Detection with Adversarial Training cites Is BERT Really Robust? A Strong Baseline for Natural Language Attack on Text Classification and Entailment
  • AdaptDel: Adaptable Deletion Rate Randomized Smoothing for Certified Robustness cites Certified Robustness to Adversarial Examples with Differential Privacy
  • AdaptDel: Adaptable Deletion Rate Randomized Smoothing for Certified Robustness cites FreeLB: Enhanced Adversarial Training for Natural Language Understanding
  • AdaptDel: Adaptable Deletion Rate Randomized Smoothing for Certified Robustness cites BERT-ATTACK: Adversarial Attack Against BERT Using BERT
  • AdaptDel: Adaptable Deletion Rate Randomized Smoothing for Certified Robustness cites Word-level Textual Adversarial Attacking as Combinatorial Optimization
  • AdaptDel: Adaptable Deletion Rate Randomized Smoothing for Certified Robustness cites Is BERT Really Robust? A Strong Baseline for Natural Language Attack on Text Classification and Entailment
  • Learning From Dictionary: Enhancing Robustness of Machine-Generated Text Detection in Zero-Shot Language via Adversarial Training cites Iron Sharpens Iron: Defending Against Attacks in Machine-Generated Text Detection with Adversarial Training
  • Learning From Dictionary: Enhancing Robustness of Machine-Generated Text Detection in Zero-Shot Language via Adversarial Training cites Is BERT Really Robust? A Strong Baseline for Natural Language Attack on Text Classification and Entailment
  • BERT-ATTACK: Adversarial Attack Against BERT Using BERT cites Word-level Textual Adversarial Attacking as Combinatorial Optimization
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers3

  1. Iron Sharpens Iron: Defending Against Attacks in Machine-Generated Text Detection with Adversarial TrainingYuanfan Li, Zhaohan Zhang, Chengzhengxu Li, Chao Shen et al.ACL 2025 · 10 citations
  2. AdaptDel: Adaptable Deletion Rate Randomized Smoothing for Certified RobustnessZhuoqun Huang, Neil G. Marchant, Olga Ohrimenko, Benjamin I. P. RubinsteinNeurIPS 2025
  3. Learning From Dictionary: Enhancing Robustness of Machine-Generated Text Detection in Zero-Shot Language via Adversarial TrainingYuanfan Li, Qi Zhou, Zexuan XieICLR 2026

Builds on15

  1. Is BERT Really Robust? A Strong Baseline for Natural Language Attack on Text Classification and EntailmentDi Jin, Zhijing Jin, Joey Tianyi Zhou, Peter SzolovitsAAAI 2020 · 1,333 citations
  2. Certified Robustness to Adversarial Examples with Differential PrivacyMathias Lécuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu et al.S&P 2019 · 1,022 citations
  3. BERT-ATTACK: Adversarial Attack Against BERT Using BERTLinyang Li, Ruotian Ma, Qipeng Guo, Xiangyang Xue et al.EMNLP 2020 · 529 citations
  4. FreeLB: Enhanced Adversarial Training for Natural Language UnderstandingChen Zhu, Yu Cheng, Zhe Gan, Siqi Sun et al.ICLR 2020 · 502 citations
  5. Word-level Textual Adversarial Attacking as Combinatorial OptimizationYuan Zang, Fanchao Qi, Chenghao Yang, Zhiyuan Liu et al.ACL 2020 · 188 citations

Related papers

  1. Text-CRS: A Generalized Certified Robustness Framework against Textual Adversarial AttacksXinyu Zhang, Hanbin Hong, Yuan Hong, Peng Huang et al.S&P 2024 · 41 citations
  2. RS-Del: Edit Distance Robustness Certificates for Sequence Classifiers via Randomized DeletionZhuoqun Huang, Neil G. Marchant, Keane Lucas, Lujo Bauer et al.NeurIPS 2023 · 24 citations
  3. Robustness Certificates for Sparse Adversarial Attacks by Randomized AblationAlexander Levine, Soheil FeiziAAAI 2020 · 114 citations
  4. GSmooth: Certified Robustness against Semantic Transformations via Generalized Randomized SmoothingZhongkai Hao, Chengyang Ying, Yinpeng Dong, Hang Su et al.ICML 2022 · 27 citations
  5. Higher-Order Certification For Randomized SmoothingJeet Mohapatra, Ching-Yun Ko, Tsui-Wei Weng, Pin-Yu Chen et al.NeurIPS 2020 · 51 citations
Dusk over the sea between two cliffs drawn in fine vertical lines