# Achieving Verified Robustness to Symbol Substitutions via Interval Bound Propagation

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

## Key facts

- Cited by 88 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Sep 2019.

## Built on by (most cited first, 30 of 88)

- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Certifying LLM Safety against Adversarial Prompting](https://mlsanity.com/paper/2309.02705/) (2023)
- [Adversarial GLUE: A Multi-Task Benchmark for Robustness Evaluation of Language Models](https://mlsanity.com/paper/2111.02840/) (2021)
- [Why Should Adversarial Perturbations be Imperceptible? Rethink the Research Paradigm in Adversarial NLP](https://mlsanity.com/paper/2210.10683/) (2022)
- [A Survey of Safety and Trustworthiness of Large Language Models through the Lens of Verification and Validation](https://mlsanity.com/paper/2305.11391/) (2023)
- [Towards Improving Adversarial Training of NLP Models](https://mlsanity.com/paper/2109.00544/) (2021)
- [Towards Robustness Against Natural Language Word Substitutions](https://mlsanity.com/paper/2107.13541/) (2021)
- [Certified Robustness to Text Adversarial Attacks by Randomized [MASK]](https://mlsanity.com/paper/2105.03743/) (2021)
- [Searching for an Effective Defender: Benchmarking Defense against Adversarial Word Substitution](https://mlsanity.com/paper/2108.12777/) (2021)
- [On Guaranteed Optimal Robust Explanations for NLP Models](https://mlsanity.com/paper/2105.03640/) (2021)
- [How Should Pre-Trained Language Models Be Fine-Tuned Towards Adversarial Robustness?](https://mlsanity.com/paper/2112.11668/) (2021)
- [Policy Smoothing for Provably Robust Reinforcement Learning](https://mlsanity.com/paper/2106.11420/) (2021)
- [Text-CRS: A Generalized Certified Robustness Framework against Textual Adversarial Attacks](https://mlsanity.com/paper/2307.16630/) (2023)
- [On the Sensitivity and Stability of Model Interpretations in NLP](https://mlsanity.com/paper/2104.08782/) (2021)
- [Defending Pre-trained Language Models from Adversarial Word Substitutions Without Performance Sacrifice](https://mlsanity.com/paper/2105.14553/) (2021)
- [The Trickle-down Impact of Reward (In-)consistency on RLHF](https://mlsanity.com/paper/2309.16155/) (2023)
- [Grey-box Adversarial Attack And Defence For Sentiment Classification](https://mlsanity.com/paper/2103.11576/) (2021)
- [Certified Robustness Against Natural Language Attacks by Causal Intervention](https://mlsanity.com/paper/2205.12331/) (2022)
- [Achieving Model Robustness through Discrete Adversarial Training](https://mlsanity.com/paper/2104.05062/) (2021)
- [A Survey of Adversarial Defences and Robustness in NLP](https://mlsanity.com/paper/2203.06414/) (2022)
- [Certified Robustness for Large Language Models with Self-Denoising](https://mlsanity.com/paper/2307.07171/) (2023)
- [Improving Zero-Shot Cross-Lingual Transfer Learning via Robust Training](https://mlsanity.com/paper/2104.08645/) (2021)
- [Adversarial Training is Not Ready for Robot Learning](https://mlsanity.com/paper/2103.08187/) (2021)
- [Does Robustness Improve Fairness? Approaching Fairness with Word Substitution Robustness Methods for Text Classification](https://mlsanity.com/paper/2106.10826/) (2021)
- [Textual Manifold-based Defense Against Natural Language Adversarial Examples](https://mlsanity.com/paper/2211.02878/) (2022)
- [Certified Robustness to Programmable Transformations in LSTMs](https://mlsanity.com/paper/2102.07818/) (2021)
- [Center Smoothing: Certified Robustness for Networks with Structured Outputs](https://mlsanity.com/paper/2102.09701/) (2021)
- [Improving the Adversarial Robustness of NLP Models by Information Bottleneck](https://mlsanity.com/paper/2206.05511/) (2022)
- [The King is Naked: on the Notion of Robustness for Natural Language Processing](https://mlsanity.com/paper/2112.07605/) (2021)
- [Text Adversarial Purification as Defense against Adversarial Attacks](https://mlsanity.com/paper/2203.14207/) (2022)

## Abstract (arXiv)

Neural networks are part of many contemporary NLP systems, yet their empirical successes come at the price of vulnerability to adversarial attacks. Previous work has used adversarial training and data augmentation to partially mitigate such brittleness, but these are unlikely to find worst-case adversaries due to the complexity of the search space arising from discrete text perturbations. In this work, we approach the problem from the opposite direction: to formally verify a system's robustness against a predefined class of adversarial attacks. We study text classification under synonym replacements or character flip perturbations. We propose modeling these input perturbations as a simplex and then using Interval Bound Propagation -- a formal model verification method. We modify the conventional log-likelihood training objective to train models that can be efficiently verified, which would otherwise come with exponential search complexity. The resulting models show only little difference in terms of nominal accuracy, but have much improved verified accuracy under perturbations and come with an efficiently computable formal guarantee on worst case adversaries.