mlsanityData to 7 Oct 2026

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

arXiv 2302.01757 ↗First posted 31 Jan 2023cs.CR cs.LG stat.MLcited by 17

Not on the map. Why?

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.

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

Builds on

49 of 93 references.

References · 49

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2013Intriguing properties of neural networkscited by 5,114
  3. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,324
  4. 2018Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examplescited by 1,259
  5. 2017Provable defenses against adversarial examples via the convex outer adversarial polytopecited by 564
  6. 2020On Adaptive Attacks to Adversarial Example Defensescited by 547
  7. 2018Certified Robustness to Adversarial Examples with Differential Privacycited by 462
  8. 2019Provably Robust Deep Learning via Adversarially Trained Smoothed Classifierscited by 328
  9. 2018On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Modelscited by 322
  10. 2018Certified Defenses against Adversarial Examplescited by 305
  11. 2018Towards Fast Computation of Certified Robustness for ReLU Networkscited by 254
  12. 2019Towards Stable and Efficient Training of Verifiably Robust Neural Networkscited by 204
37 more
  1. 2018Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networkscited by 193
  2. 2019Certified Robustness to Adversarial Word Substitutionscited by 164
  3. 2020Randomized Smoothing of All Shapes and Sizescited by 146
  4. 2018Scaling provable adversarial defensescited by 141
  5. 2022(Certified!!) Adversarial Robustness for Free!cited by 130
  6. 2017Malware Detection by Eating a Whole EXEcited by 114
  7. 2021Globally-Robust Neural Networkscited by 106
  8. 2020SAFER: A Structure-free Approach for Certified Robustness to Adversarial Word Substitutionscited by 72
  9. 2019Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifierscited by 65
  10. 2018Adversarial Malware Binaries: Evading Deep Learning for Malware Detection in Executablescited by 60
  11. 2019Robustness Certificates for Sparse Adversarial Attacks by Randomized Ablationcited by 59
  12. 2020Functionality-preserving Black-box Optimization of Adversarial Windows Malwarecited by 58
  13. 2021Certified Robustness to Text Adversarial Attacks by Randomized [MASK]cited by 57
  14. 2020Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and Morecited by 56
  15. 2017Yes, Machine Learning Can Be More Secure! A Case Study on Android Malware Detectioncited by 51
  16. 2020Certified Defense to Image Transformations via Randomized Smoothingcited by 51
  17. 2018Training verified learners with learned verifierscited by 50
  18. 2020TSS: Transformation-Specific Smoothing for Robustness Certificationcited by 49
  19. 2021PointGuard: Provably Robust 3D Point Cloud Classificationcited by 49
  20. 2018Exploring Adversarial Examples in Malware Detectioncited by 41
  21. 2018Adversarial Deep Learning for Robust Detection of Binary Encoded Malwarecited by 32
  22. 2019Malware Makeover: Breaking ML-based Static Analysis by Modifying Executable Bytescited by 31
  23. 2019Explaining Vulnerabilities of Deep Learning to Adversarial Malware Binariescited by 30
  24. 2020Certified Robustness of Community Detection against Adversarial Structural Perturbation via Randomized Smoothingcited by 29
  25. 2019Dynamic Malware Analysis with Feature Engineering and Feature Learningcited by 23
  26. 2020Classifying Sequences of Extreme Length with Constant Memory Applied to Malware Detectioncited by 23
  27. 2022GSmooth: Certified Robustness against Semantic Transformations via Generalized Randomized Smoothingcited by 23
  28. 2018Non-Negative Networks Against Adversarial Attackscited by 20
  29. 2018Deceiving End-to-End Deep Learning Malware Detectors using Adversarial Examplescited by 19
  30. 2019On Training Robust PDF Malware Classifierscited by 19
  31. 2021Certified Robustness to Programmable Transformations in LSTMscited by 18
  32. 2020Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbationscited by 16
  33. 2021Learning Security Classifiers with Verified Global Robustness Propertiescited by 14
  34. 2017Black-Box Attacks against RNN based Malware Detection Algorithmscited by 13
  35. 2023Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networkscited by 10
  36. 2020Against All Odds: Winning the Defense Challenge in an Evasion Competition with Diversificationcited by 5
  37. 2021secml-malware: Pentesting Windows Malware Classifiers with Adversarial EXEmples in Pythoncited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 4; 2024: 7; 2025: 3; 2026: 3.

17 papers.

Sort:

By area:

  1. 2023Certifying LLM Safety against Adversarial Promptingcited by 248
  2. 2024Operationalizing a Threat Model for Red-Teaming Large Language Models (LLMs)cited by 44
  3. 2023Text-CRS: A Generalized Certified Robustness Framework against Textual Adversarial Attackscited by 32
  4. 2023Hierarchical Randomized Smoothingcited by 9
  5. 2024RS-Reg: Probabilistic and Robust Certified Regression Through Randomized Smoothingcited by 4
  6. 2025Position: Certified Robustness Does Not (Yet) Imply Model Securitycited by 4
  7. 2026Certified Circuits: Stability Guarantees for Mechanistic Circuitscited by 4
  8. 2023Adversarial Attacks against Binary Similarity Systemscited by 3
  9. 2024Living off the Analyst: Harvesting Features from Yara Rules for Malware Detectioncited by 3
  10. 2024CERT-ED: Certifiably Robust Text Classification for Edit Distancecited by 2
  11. 2024Machine Learning for Windows Malware Detection and Classification: Methods, Challenges and Ongoing Researchcited by 1
  12. 2024A New Formulation for Zeroth-Order Optimization of Adversarial EXEmples in Malware Detectioncited by 1
5 more
  1. 2025On the Security Risks of ML-based Malware Detection Systems: A Surveycited by 1
  2. 2024Certified Adversarial Robustness of Machine Learning-based Malware Detectors via (De)Randomized Smoothingcited by 0
  3. 2025AdaptDel: Adaptable Deletion Rate Randomized Smoothing for Certified Robustnesscited by 0
  4. 2026What Was That Again? Certified Robustness for Automatic Speech Recognitioncited by 0
  5. 2026EXE-Bench: Ranking the Tradeoffs of AI-based Windows Malware Detectors for Real-World Usabilitycited by 0