# RS-Del: Edit Distance Robustness Certificates for Sequence Classifiers via Randomized Deletion

arXiv: https://arxiv.org/abs/2302.01757 · HTML: https://mlsanity.com/paper/2302.01757/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 49 of its 93 references that are in the map.
- First posted on arXiv 31 Jan 2023.

## Builds on (most cited first, 30 of 49)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples](https://mlsanity.com/paper/1802.00420/) (2018)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [On Adaptive Attacks to Adversarial Example Defenses](https://mlsanity.com/paper/2002.08347/) (2020)
- [Certified Robustness to Adversarial Examples with Differential Privacy](https://mlsanity.com/paper/1802.03471/) (2018)
- [Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers](https://mlsanity.com/paper/1906.04584/) (2019)
- [On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models](https://mlsanity.com/paper/1810.12715/) (2018)
- [Certified Defenses against Adversarial Examples](https://mlsanity.com/paper/1801.09344/) (2018)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [Towards Stable and Efficient Training of Verifiably Robust Neural Networks](https://mlsanity.com/paper/1906.06316/) (2019)
- [Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks](https://mlsanity.com/paper/1802.04034/) (2018)
- [Certified Robustness to Adversarial Word Substitutions](https://mlsanity.com/paper/1909.00986/) (2019)
- [Randomized Smoothing of All Shapes and Sizes](https://mlsanity.com/paper/2002.08118/) (2020)
- [Scaling provable adversarial defenses](https://mlsanity.com/paper/1805.12514/) (2018)
- [(Certified!!) Adversarial Robustness for Free!](https://mlsanity.com/paper/2206.10550/) (2022)
- [Malware Detection by Eating a Whole EXE](https://mlsanity.com/paper/1710.09435/) (2017)
- [Globally-Robust Neural Networks](https://mlsanity.com/paper/2102.08452/) (2021)
- [SAFER: A Structure-free Approach for Certified Robustness to Adversarial Word Substitutions](https://mlsanity.com/paper/2005.14424/) (2020)
- [Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers](https://mlsanity.com/paper/1906.04948/) (2019)
- [Adversarial Malware Binaries: Evading Deep Learning for Malware Detection in Executables](https://mlsanity.com/paper/1803.04173/) (2018)
- [Robustness Certificates for Sparse Adversarial Attacks by Randomized Ablation](https://mlsanity.com/paper/1911.09272/) (2019)
- [Functionality-preserving Black-box Optimization of Adversarial Windows Malware](https://mlsanity.com/paper/2003.13526/) (2020)
- [Certified Robustness to Text Adversarial Attacks by Randomized [MASK]](https://mlsanity.com/paper/2105.03743/) (2021)
- [Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More](https://mlsanity.com/paper/2008.12952/) (2020)
- [Yes, Machine Learning Can Be More Secure! A Case Study on Android Malware Detection](https://mlsanity.com/paper/1704.08996/) (2017)
- [Certified Defense to Image Transformations via Randomized Smoothing](https://mlsanity.com/paper/2002.12463/) (2020)
- [Training verified learners with learned verifiers](https://mlsanity.com/paper/1805.10265/) (2018)
- [TSS: Transformation-Specific Smoothing for Robustness Certification](https://mlsanity.com/paper/2002.12398/) (2020)

## Built on by (most cited first, 17 of 17)

- [Certifying LLM Safety against Adversarial Prompting](https://mlsanity.com/paper/2309.02705/) (2023)
- [Operationalizing a Threat Model for Red-Teaming Large Language Models (LLMs)](https://mlsanity.com/paper/2407.14937/) (2024)
- [Text-CRS: A Generalized Certified Robustness Framework against Textual Adversarial Attacks](https://mlsanity.com/paper/2307.16630/) (2023)
- [Hierarchical Randomized Smoothing](https://mlsanity.com/paper/2310.16221/) (2023)
- [Certified Circuits: Stability Guarantees for Mechanistic Circuits](https://mlsanity.com/paper/2602.22968/) (2026)
- [RS-Reg: Probabilistic and Robust Certified Regression Through Randomized Smoothing](https://mlsanity.com/paper/2405.08892/) (2024)
- [Position: Certified Robustness Does Not (Yet) Imply Model Security](https://mlsanity.com/paper/2506.13024/) (2025)
- [Adversarial Attacks against Binary Similarity Systems](https://mlsanity.com/paper/2303.11143/) (2023)
- [Living off the Analyst: Harvesting Features from Yara Rules for Malware Detection](https://mlsanity.com/paper/2411.18516/) (2024)
- [CERT-ED: Certifiably Robust Text Classification for Edit Distance](https://mlsanity.com/paper/2408.00728/) (2024)
- [Machine Learning for Windows Malware Detection and Classification: Methods, Challenges and Ongoing Research](https://mlsanity.com/paper/2404.18541/) (2024)
- [A New Formulation for Zeroth-Order Optimization of Adversarial EXEmples in Malware Detection](https://mlsanity.com/paper/2405.14519/) (2024)
- [On the Security Risks of ML-based Malware Detection Systems: A Survey](https://mlsanity.com/paper/2505.10903/) (2025)
- [Certified Adversarial Robustness of Machine Learning-based Malware Detectors via (De)Randomized Smoothing](https://mlsanity.com/paper/2405.00392/) (2024)
- [AdaptDel: Adaptable Deletion Rate Randomized Smoothing for Certified Robustness](https://mlsanity.com/paper/2511.09316/) (2025)
- [What Was That Again? Certified Robustness for Automatic Speech Recognition](https://mlsanity.com/paper/2606.27698/) (2026)
- [EXE-Bench: Ranking the Tradeoffs of AI-based Windows Malware Detectors for Real-World Usability](https://mlsanity.com/paper/2607.24177/) (2026)

## Abstract (arXiv)

Randomized smoothing is a leading approach for constructing classifiers that are certifiably robust against adversarial examples. Existing work on randomized smoothing has focused on classifiers with continuous inputs, such as images, where ℓp-norm bounded adversaries are commonly studied. However, there has been limited work for classifiers with discrete or variable-size inputs, such as for source code, which require different threat models and smoothing mechanisms. In this work, we adapt randomized smoothing for discrete sequence classifiers to provide certified robustness against edit distance-bounded adversaries. Our proposed smoothing mechanism randomized deletion (RS-Del) applies random deletion edits, which are (perhaps surprisingly) sufficient to confer robustness against adversarial deletion, insertion and substitution edits. Our proof of certification deviates from the established Neyman-Pearson approach, which is intractable in our setting, and is instead organized around longest common subsequences. We present a case study on malware detection--a binary classification problem on byte sequences where classifier evasion is a well-established threat model. When applied to the popular MalConv malware detection model, our smoothing mechanism RS-Del achieves a certified accuracy of 91% at an edit distance radius of 128 bytes.