# Certified Robustness to Programmable Transformations in LSTMs

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 40 references that are in the map.
- First posted on arXiv 15 Feb 2021.

## Builds on (most cited first, 26 of 26)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [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)
- [Universal Adversarial Triggers for Attacking and Analyzing NLP](https://mlsanity.com/paper/1908.07125/) (2019)
- [Adversarial Examples Are Not Easily Detected: Bypassing Ten Detection Methods](https://mlsanity.com/paper/1705.07263/) (2017)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [TextBugger: Generating Adversarial Text Against Real-world Applications](https://mlsanity.com/paper/1812.05271/) (2018)
- [BAE: BERT-based Adversarial Examples for Text Classification](https://mlsanity.com/paper/2004.01970/) (2020)
- [Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks](https://mlsanity.com/paper/1503.00075/) (2015)
- [Adversarial Example Generation with Syntactically Controlled Paraphrase Networks](https://mlsanity.com/paper/1804.06059/) (2018)
- [Certified Robustness to Adversarial Word Substitutions](https://mlsanity.com/paper/1909.00986/) (2019)
- [Deep Text Classification Can be Fooled](https://mlsanity.com/paper/1704.08006/) (2017)
- [SoK: Certified Robustness for Deep Neural Networks](https://mlsanity.com/paper/2009.04131/) (2020)
- [Crafting Adversarial Input Sequences for Recurrent Neural Networks](https://mlsanity.com/paper/1604.08275/) (2016)
- [Achieving Verified Robustness to Symbol Substitutions via Interval Bound Propagation](https://mlsanity.com/paper/1909.01492/) (2019)
- [On Adversarial Examples for Character-Level Neural Machine Translation](https://mlsanity.com/paper/1806.09030/) (2018)
- [Robustness Verification for Transformers](https://mlsanity.com/paper/2002.06622/) (2020)
- [SAFER: A Structure-free Approach for Certified Robustness to Adversarial Word Substitutions](https://mlsanity.com/paper/2005.14424/) (2020)
- [On Evaluation of Adversarial Perturbations for Sequence-to-Sequence Models](https://mlsanity.com/paper/1903.06620/) (2019)
- [Generating Fluent Adversarial Examples for Natural Languages](https://mlsanity.com/paper/2007.06174/) (2020)
- [Robust Machine Comprehension Models via Adversarial Training](https://mlsanity.com/paper/1804.06473/) (2018)
- [POPQORN: Quantifying Robustness of Recurrent Neural Networks](https://mlsanity.com/paper/1905.07387/) (2019)
- [Verifying Recurrent Neural Networks using Invariant Inference](https://mlsanity.com/paper/2004.02462/) (2020)
- [Comparing Attention-based Convolutional and Recurrent Neural Networks: Success and Limitations in Machine Reading Comprehension](https://mlsanity.com/paper/1808.08744/) (2018)
- [Adversarial Attacks and Defense on Texts: A Survey](https://mlsanity.com/paper/2005.14108/) (2020)
- [Robustness to Programmable String Transformations via Augmented Abstract Training](https://mlsanity.com/paper/2002.09579/) (2020)

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

- [A Survey of Safety and Trustworthiness of Large Language Models through the Lens of Verification and Validation](https://mlsanity.com/paper/2305.11391/) (2023)
- [Interactive Model Cards: A Human-Centered Approach to Model Documentation](https://mlsanity.com/paper/2205.02894/) (2022)
- [A Survey of Adversarial Defences and Robustness in NLP](https://mlsanity.com/paper/2203.06414/) (2022)
- [RS-Del: Edit Distance Robustness Certificates for Sequence Classifiers via Randomized Deletion](https://mlsanity.com/paper/2302.01757/) (2023)
- [NLP Verification: Towards a General Methodology for Certifying Robustness](https://mlsanity.com/paper/2403.10144/) (2024)
- [Spiking Convolutional Neural Networks for Text Classification](https://mlsanity.com/paper/2406.19230/) (2024)
- [A.I. Robustness: a Human-Centered Perspective on Technological Challenges and Opportunities](https://mlsanity.com/paper/2210.08906/) (2022)
- [ANTONIO: Towards a Systematic Method of Generating NLP Benchmarks for Verification](https://mlsanity.com/paper/2305.04003/) (2023)
- [PECAN: A Deterministic Certified Defense Against Backdoor Attacks](https://mlsanity.com/paper/2301.11824/) (2023)
- [The Fundamental Limits of Interval Arithmetic for Neural Networks](https://mlsanity.com/paper/2112.05235/) (2021)
- [Reliability Assurance for Deep Neural Network Architectures Against Numerical Defects](https://mlsanity.com/paper/2302.06086/) (2023)
- [Verified Training for Counterfactual Explanation Robustness under Data Shift](https://mlsanity.com/paper/2403.03773/) (2024)
- [Natural Language Specifications in Proof Assistants](https://mlsanity.com/paper/2205.07811/) (2022)
- [A One-Layer Decoder-Only Transformer is a Two-Layer RNN: With an Application to Certified Robustness](https://mlsanity.com/paper/2405.17361/) (2024)
- [Bridging Robustness and Generalization Against Word Substitution Attacks in NLP via the Growth Bound Matrix Approach](https://mlsanity.com/paper/2507.10330/) (2025)
- [Why Robust Natural Language Understanding is a Challenge](https://mlsanity.com/paper/2206.14575/) (2022)
- [Robustness Verification of Recurrent Neural Networks with Abstraction Refinement](https://mlsanity.com/paper/2606.12490/) (2026)
- [S-GBT: Smooth Growth Bound Tensor for Certified Robustness Against Word Substitution Attacks in NLP](https://mlsanity.com/paper/2606.13439/) (2026)

## Abstract (arXiv)

Deep neural networks for natural language processing are fragile in the face of adversarial examples -- small input perturbations, like synonym substitution or word duplication, which cause a neural network to change its prediction. We present an approach to certifying the robustness of LSTMs (and extensions of LSTMs) and training models that can be efficiently certified. Our approach can certify robustness to intractably large perturbation spaces defined programmatically in a language of string transformations. Our evaluation shows that (1) our approach can train models that are more robust to combinations of string transformations than those produced using existing techniques; (2) our approach can show high certification accuracy of the resulting models.