---
title: "Certified Robustness to Adversarial Word — Jia 2019"
description: "NLP classifiers can often be broken by swapping words for near-synonyms that leave the label unchanged."
authors: ["Robin Jia", "Aditi Raghunathan", "Kerem Göksel", "Percy Liang"]
year: 2019
venue: "Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)"
source: "https://aclanthology.org/D19-1423/"
doi: "10.18653/v1/d19-1423"
licence: "CC BY 4.0 (ACL Anthology)"
licence_url: "https://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/jia-2019-certified-robustness-adversarial-word-substitutions/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/jia-2019-certified-robustness-adversarial-word-substitutions/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2019](https://md.research.elamur.ai/free/en/papers/2019/) / Certified Robustness to Adversarial Word Substitutions

# Certified Robustness to Adversarial Word Substitutions

**Authors:** [Robin Jia](https://md.research.elamur.ai/free/en/authors/robin-jia/), [Aditi Raghunathan](https://md.research.elamur.ai/free/en/authors/aditi-raghunathan/), Kerem Göksel, [Percy Liang](https://md.research.elamur.ai/free/en/authors/percy-liang/) · **Year:** 2019 · **Venue:** Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP) · **Licence:** [CC BY 4.0 (ACL Anthology)](https://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://aclanthology.org/D19-1423/) · [PDF](https://aclanthology.org/D19-1423.pdf) · [DOI 10.18653/v1/d19-1423](https://doi.org/10.18653/v1/d19-1423) · [OpenAlex](https://openalex.org/W2970078867)

**Citations:** 222 citations (openalex-snapshot · 2026-10-14) · [114](#cited-by) in our library, of the 140673 papers whose bibliographies we read

## Summary

NLP classifiers can often be broken by swapping words for near-synonyms that leave the label unchanged. Because every word may be replaced independently, the number of variants grows exponentially with text length. Neither heuristic attack search nor data augmentation can cover that space. The authors address this by training models whose robustness to every combination of allowed substitutions can be formally verified.

They adapt Interval Bound Propagation (IBP) from computer vision. Each word's substitution set becomes an axis-aligned box in embedding space, and interval bounds are pushed forward through the network. This yields an upper bound on the worst-case loss, which training then minimizes. To support NLP models, they derive new interval rules for softmax, element-wise multiplication and dot products, which extends IBP to LSTMs and attention.

On IMDB sentiment classification and SNLI inference, across bag-of-words, CNN, LSTM and attention models, IBP training reaches about 75% adversarial accuracy on both tasks. It clearly beats normal training and data augmentation. The work shows that provable guarantees are achievable for discrete text perturbations.

## Key points

- **Search space size:** IMDB reviews have a median of roughly 10^31 possible substitution variants and up to 10^271, so exhaustive checking is impossible.
- **Adversarial accuracy:**

  | Training | IMDB | SNLI |
  |---|---|---|
  | Normal | 8% | 41% |
  | Data augmentation | 35% | 71% |
  | IBP-based certified training | 75% | 75% |

- **Technical additions to IBP:** new bound formulas for softmax, multiplication and dot-product operations, plus support for discrete (rather than continuous) perturbation sets.
- **Ablations:**
  - Adding a trainable feed-forward layer over pre-trained word vectors, and bounding its outputs, is essential. Without it, the CNN stayed at or below 52.2% certified accuracy on the development set.
  - Keeping ε fixed at 1 during training, instead of ramping it up, lowered certified accuracy by 5 points.
- **Availability:** code, data and experiments are released on Codalab.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

Fields: [Natural language processing](https://md.research.elamur.ai/free/en/shelves/nlp/)

## Cited by

Cited by

114 papers of our library cite it (of the 140673 whose bibliographies we read); 5 of them have a page here, 109 not yet.

- [A Survey of Data Augmentation Approaches for NLP](https://md.research.elamur.ai/free/en/papers/feng-2021-survey-data-augmentation-approaches-nlp/)
- [Evaluating Models' Local Decision Boundaries via Contrast Sets](https://md.research.elamur.ai/free/en/papers/gardner-2020-evaluating-models-local-decision-boundaries/)
- [TrustLLM: Trustworthiness in Large Language Models](https://md.research.elamur.ai/free/en/papers/huang-2024-trustllm-trustworthiness-large-language-models/)
- [Contextualized Perturbation for Textual Adversarial Attack](https://md.research.elamur.ai/free/en/papers/li-2021-contextualized-perturbation-textual-adversarial-attack/)
- [TextAttack: A Framework for Adversarial Attacks, Data Augmentation, and Adversarial Training in NLP](https://md.research.elamur.ai/free/en/papers/morris-2020-textattack-framework-adversarial-attacks-data/)

## Cite

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{jia2019certified,
  title = {{Certified Robustness to Adversarial Word Substitutions}},
  author = {Jia, Robin and Raghunathan, Aditi and Göksel, Kerem and Liang, Percy},
  booktitle = {Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)},
  year = {2019},
  doi = {10.18653/v1/d19-1423},
  url = {https://doi.org/10.18653/v1/d19-1423}
}
```

- [← previous CCMatrix: Mining Billions of High-Quality Parallel Sentences on the WEB](https://md.research.elamur.ai/free/en/papers/schwenk-2019-ccmatrix-mining-billions-high-quality/)
- [next → Challenges and frontiers in abusive content detection](https://md.research.elamur.ai/free/en/papers/vidgen-2019-challenges-frontiers-abusive-content-detection/)
- [↑ back to papers of 2019](https://md.research.elamur.ai/free/en/papers/2019/)

## References

28 references, 13 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. M. Alzantot, Y. Sharma, A. Elgohary, B. Ho, M. Srivastava, and K. Chang. 2018. Generating natural language adversarial examples. In Empirical Methods in Natural Language Processing (EMNLP). [find](https://scholar.google.com/scholar?q=M%2E+Alzantot%2C+Y%2E+Sharma%2C+A%2E+Elgohary%2C+B%2E+Ho%2C+M%2E+Srivastava%2C+and+K%2E+Chang%2E+2018%2E+Generating+natural+language+adversarial+examples%2E+In+Empirical+Methods+in+Natural+Language+Processing+%28EMNLP%29%2E) [our card](https://md.research.elamur.ai/free/en/papers/alzantot-2018-generating-natural-language-adversarial-examples/)
2. A. Athalye, N. Carlini, and D. Wagner. 2018. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. arXiv preprint arXiv:1802.00420. — [arXiv:1802.00420](https://arxiv.org/abs/1802.00420) [find](https://scholar.google.com/scholar?q=A%2E+Athalye%2C+N%2E+Carlini%2C+and+D%2E+Wagner%2E+2018%2E+Obfuscated+gradients+give+a+false+sense+of+security%3A+Circumventing+defenses+to+adversarial+examples%2E+arXiv+preprint+arXiv%3A1802%2E00420%2E+%E2%80%94+%5BarXiv%3A1802%2E00420%5D%28)
3. D. Bahdanau, K. Cho, and Y. Bengio. 2015. Neural machine translation by jointly learning to align and translate. In International Conference on Learning Representations (ICLR). [find](https://scholar.google.com/scholar?q=D%2E+Bahdanau%2C+K%2E+Cho%2C+and+Y%2E+Bengio%2E+2015%2E+Neural+machine+translation+by+jointly+learning+to+align+and+translate%2E+In+International+Conference+on+Learning+Representations+%28ICLR%29%2E) [our card](https://md.research.elamur.ai/free/en/papers/bahdanau-2014-neural-machine-translation-jointly-learning/)
4. Y. Belinkov and Y. Bisk. 2017. Synthetic and natural noise both break neural machine translation. arXiv preprint arXiv:1711.02173. [find](https://scholar.google.com/scholar?q=Y%2E+Belinkov+and+Y%2E+Bisk%2E+2017%2E+Synthetic+and+natural+noise+both+break+neural+machine+translation%2E+arXiv+preprint+arXiv%3A1711%2E02173%2E)
5. S. Bowman, G. Angeli, C. Potts, and C. D. Manning. 2015. A large annotated corpus for learning natural language inference. In Empirical Methods in Natural Language Processing (EMNLP). [find](https://scholar.google.com/scholar?q=S%2E+Bowman%2C+G%2E+Angeli%2C+C%2E+Potts%2C+and+C%2E+D%2E+Manning%2E+2015%2E+A+large+annotated+corpus+for+learning+natural+language+inference%2E+In+Empirical+Methods+in+Natural+Language+Processing+%28EMNLP%29%2E)
6. C. Chelba, T. Mikolov, M. Schuster, Q. Ge, T. Brants, P. Koehn, and T. Robinson. 2013. One billion word benchmark for measuring progress in statistical language modeling. arXiv preprint arXiv:1312.3005. [find](https://scholar.google.com/scholar?q=C%2E+Chelba%2C+T%2E+Mikolov%2C+M%2E+Schuster%2C+Q%2E+Ge%2C+T%2E+Brants%2C+P%2E+Koehn%2C+and+T%2E+Robinson%2E+2013%2E+One+billion+word+benchmark+for+measuring+progress+in+statistical+language+modeling%2E+arXiv+preprint+arXiv%3A1312%2E300) [our card](https://md.research.elamur.ai/free/en/papers/chelba-2013-one-billion-word-benchmark-measuring/)
7. N. Dalvi, P. Domingos, Mausam, S. Sanghai, and D. Verma. 2004. Adversarial classification. In International Conference on Knowledge Discovery and Data Mining (KDD). [find](https://scholar.google.com/scholar?q=N%2E+Dalvi%2C+P%2E+Domingos%2C+Mausam%2C+S%2E+Sanghai%2C+and+D%2E+Verma%2E+2004%2E+Adversarial+classification%2E+In+International+Conference+on+Knowledge+Discovery+and+Data+Mining+%28KDD%29%2E)
8. K. Dvijotham, S. Gowal, R. Stanforth, R. Arandjelovic, B. O’Donoghue, J. Uesato, and P. Kohli. 2018. Training verified learners with learned verifiers. arXiv preprint arXiv:1805.10265. — [arXiv:1805.10265](https://arxiv.org/abs/1805.10265) [find](https://scholar.google.com/scholar?q=K%2E+Dvijotham%2C+S%2E+Gowal%2C+R%2E+Stanforth%2C+R%2E+Arandjelovic%2C+B%2E+O%E2%80%99Donoghue%2C+J%2E+Uesato%2C+and+P%2E+Kohli%2E+2018%2E+Training+verified+learners+with+learned+verifiers%2E+arXiv+preprint+arXiv%3A1805%2E10265%2E+%E2%80%94+%5BarXiv%3A1805%2E1)
9. M. Iyyer, J. Wieting, K. Gimpel, and L. Zettlemoyer. 2018. Adversarial example generation with syntactically controlled paraphrase networks. In North American Association for Computational Linguistics (NAACL). [find](https://scholar.google.com/scholar?q=M%2E+Iyyer%2C+J%2E+Wieting%2C+K%2E+Gimpel%2C+and+L%2E+Zettlemoyer%2E+2018%2E+Adversarial+example+generation+with+syntactically+controlled+paraphrase+networks%2E+In+North+American+Association+for+Computational+Linguistics) [our card](https://md.research.elamur.ai/free/en/papers/iyyer-2018-adversarial-example-generation-syntactically-controlled/)
10. R. Jia and P. Liang. 2017. Adversarial examples for evaluating reading comprehension systems. In Empirical Methods in Natural Language Processing (EMNLP). [find](https://scholar.google.com/scholar?q=R%2E+Jia+and+P%2E+Liang%2E+2017%2E+Adversarial+examples+for+evaluating+reading+comprehension+systems%2E+In+Empirical+Methods+in+Natural+Language+Processing+%28EMNLP%29%2E) [our card](https://md.research.elamur.ai/free/en/papers/jia-2017-adversarial-examples-evaluating-reading-comprehension/)
11. D. Kingma and J. Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980. [find](https://scholar.google.com/scholar?q=D%2E+Kingma+and+J%2E+Ba%2E+2014%2E+Adam%3A+A+method+for+stochastic+optimization%2E+arXiv+preprint+arXiv%3A1412%2E6980%2E)
12. N. F. Liu, R. Schwartz, and N. A. Smith. 2019. Inoculation by fine-tuning: A method for analyzing challenge datasets. In North American Association for Computational Linguistics (NAACL). [find](https://scholar.google.com/scholar?q=N%2E+F%2E+Liu%2C+R%2E+Schwartz%2C+and+N%2E+A%2E+Smith%2E+2019%2E+Inoculation+by+fine%2Dtuning%3A+A+method+for+analyzing+challenge+datasets%2E+In+North+American+Association+for+Computational+Linguistics+%28NAACL%29%2E)
13. A. L. Maas, R. E. Daly, P. T. Pham, D. Huang, A. Y. Ng, and C. Potts. 2011. Learning word vectors for sentiment analysis. In Association for Computational Linguistics (ACL). [find](https://scholar.google.com/scholar?q=A%2E+L%2E+Maas%2C+R%2E+E%2E+Daly%2C+P%2E+T%2E+Pham%2C+D%2E+Huang%2C+A%2E+Y%2E+Ng%2C+and+C%2E+Potts%2E+2011%2E+Learning+word+vectors+for+sentiment+analysis%2E+In+Association+for+Computational+Linguistics+%28ACL%29%2E) [our card](https://md.research.elamur.ai/free/en/papers/maas-2011-learning-word-vectors-sentiment-analysis/)
14. A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. 2017. Towards deep learning models resistant to adversarial attacks (published at ICLR 2018). arXiv. [find](https://scholar.google.com/scholar?q=A%2E+Madry%2C+A%2E+Makelov%2C+L%2E+Schmidt%2C+D%2E+Tsipras%2C+and+A%2E+Vladu%2E+2017%2E+Towards+deep+learning+models+resistant+to+adversarial+attacks+%28published+at+ICLR+2018%29%2E+arXiv%2E) [our card](https://md.research.elamur.ai/free/en/papers/madry-2017-towards-deep-learning-models-resistant/)
15. A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. 2018. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations (ICLR). [find](https://scholar.google.com/scholar?q=A%2E+Madry%2C+A%2E+Makelov%2C+L%2E+Schmidt%2C+D%2E+Tsipras%2C+and+A%2E+Vladu%2E+2018%2E+Towards+deep+learning+models+resistant+to+adversarial+attacks%2E+In+International+Conference+on+Learning+Representations+%28ICLR%29%2E) [our card](https://md.research.elamur.ai/free/en/papers/madry-2017-towards-deep-learning-models-resistant/)
16. P. Michel, X. Li, G. Neubig, and J. M. Pino. 2019. On evaluation of adversarial perturbations for sequence-to-sequence models. In North American Association for Computational Linguistics (NAACL). [find](https://scholar.google.com/scholar?q=P%2E+Michel%2C+X%2E+Li%2C+G%2E+Neubig%2C+and+J%2E+M%2E+Pino%2E+2019%2E+On+evaluation+of+adversarial+perturbations+for+sequence%2Dto%2Dsequence+models%2E+In+North+American+Association+for+Computational+Linguistics+%28NAACL%29%2E)
17. J. Ebrahimi, A. Rao, D. Lowd, and D. Dou. 2017. Hotflip: White-box adversarial examples for text classification. arXiv preprint arXiv:1712.06751. [find](https://scholar.google.com/scholar?q=J%2E+Ebrahimi%2C+A%2E+Rao%2C+D%2E+Lowd%2C+and+D%2E+Dou%2E+2017%2E+Hotflip%3A+White%2Dbox+adversarial+examples+for+text+classification%2E+arXiv+preprint+arXiv%3A1712%2E06751%2E) [our card](https://md.research.elamur.ai/free/en/papers/ebrahimi-2018-hotflip-white-box-adversarial-examples/)
18. N. Mrkšić, D. Ó Séaghdha, B. Thomson, M. Gašić, L. Rojas-Barahona, P. Su, D. Vandyke, T. Wen, and S. Young. 2016. Counter-fitting word vectors to linguistic constraints. In North American Association for Computational Linguistics (NAACL). [find](https://scholar.google.com/scholar?q=N%2E+Mrks%CC%8Cic%CC%81%2C+D%2E+O%CC%81+Se%CC%81aghdha%2C+B%2E+Thomson%2C+M%2E+Gas%CC%8Cic%CC%81%2C+L%2E+Rojas%2DBarahona%2C+P%2E+Su%2C+D%2E+Vandyke%2C+T%2E+Wen%2C+and+S%2E+Young%2E+2016%2E+Counter%2Dfitting+word+vectors+to+linguistic+constraints%2E+In+North+American+Associ)
19. A. Globerson and S. Roweis. 2006. Nightmare at test time: robust learning by feature deletion. In International Conference on Machine Learning (ICML), pages 353–360. [find](https://scholar.google.com/scholar?q=A%2E+Globerson+and+S%2E+Roweis%2E+2006%2E+Nightmare+at+test+time%3A+robust+learning+by+feature+deletion%2E+In+International+Conference+on+Machine+Learning+%28ICML%29%2C+pages+353%E2%80%93360%2E)
20. A. Parikh, O. Täckström, D. Das, and J. Uszkoreit. 2016. A decomposable attention model for natural language inference. In Empirical Methods in Natural Language Processing (EMNLP). [find](https://scholar.google.com/scholar?q=A%2E+Parikh%2C+O%2E+Ta%CC%88ckstro%CC%88m%2C+D%2E+Das%2C+and+J%2E+Uszkoreit%2E+2016%2E+A+decomposable+attention+model+for+natural+language+inference%2E+In+Empirical+Methods+in+Natural+Language+Processing+%28EMNLP%29%2E) [our card](https://md.research.elamur.ai/free/en/papers/parikh-2016-decomposable-attention-model-natural-language/)
21. I. J. Goodfellow, J. Shlens, and C. Szegedy. 2015. Explaining and harnessing adversarial examples. In International Conference on Learning Representations (ICLR). [find](https://scholar.google.com/scholar?q=I%2E+J%2E+Goodfellow%2C+J%2E+Shlens%2C+and+C%2E+Szegedy%2E+2015%2E+Explaining+and+harnessing+adversarial+examples%2E+In+International+Conference+on+Learning+Representations+%28ICLR%29%2E) [our card](https://md.research.elamur.ai/free/en/papers/goodfellow-2014-explaining-harnessing-adversarial-examples/)
22. J. Pennington, R. Socher, and C. D. Manning. 2014. GloVe: Global vectors for word representation. In Empirical Methods in Natural Language Processing (EMNLP), pages 1532–1543. [find](https://scholar.google.com/scholar?q=J%2E+Pennington%2C+R%2E+Socher%2C+and+C%2E+D%2E+Manning%2E+2014%2E+GloVe%3A+Global+vectors+for+word+representation%2E+In+Empirical+Methods+in+Natural+Language+Processing+%28EMNLP%29%2C+pages+1532%E2%80%931543%2E)
23. S. Gowal, K. Dvijotham, R. Stanforth, R. Bunel, C. Qin, J. Uesato, T. Mann, and P. Kohli. 2018. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv:1810.12715. — [arXiv:1810.12715](https://arxiv.org/abs/1810.12715) [find](https://scholar.google.com/scholar?q=S%2E+Gowal%2C+K%2E+Dvijotham%2C+R%2E+Stanforth%2C+R%2E+Bunel%2C+C%2E+Qin%2C+J%2E+Uesato%2C+T%2E+Mann%2C+and+P%2E+Kohli%2E+2018%2E+On+the+effectiveness+of+interval+bound+propagation+for+training+verifiably+robust+models%2E+arXiv+preprint)
24. D. Pruthi, B. Dhingra, and Z. C. Lipton. 2019. Combating adversarial misspellings with robust word recognition. In Association for Computational Linguistics (ACL). [find](https://scholar.google.com/scholar?q=D%2E+Pruthi%2C+B%2E+Dhingra%2C+and+Z%2E+C%2E+Lipton%2E+2019%2E+Combating+adversarial+misspellings+with+robust+word+recognition%2E+In+Association+for+Computational+Linguistics+%28ACL%29%2E) [our card](https://md.research.elamur.ai/free/en/papers/pruthi-2019-combating-adversarial-misspellings-robust-word/)
25. S. Hochreiter and J. Schmidhuber. 1997. Long short-term memory. Neural Computation, 9(8):1735– 1780. [find](https://scholar.google.com/scholar?q=S%2E+Hochreiter+and+J%2E+Schmidhuber%2E+1997%2E+Long+short%2Dterm+memory%2E+Neural+Computation%2C+9%288%29%3A1735%E2%80%93+1780%2E)
26. A. Raghunathan, J. Steinhardt, and P. Liang. 2018. Certified defenses against adversarial examples. In International Conference on Learning Representations (ICLR). [find](https://scholar.google.com/scholar?q=A%2E+Raghunathan%2C+J%2E+Steinhardt%2C+and+P%2E+Liang%2E+2018%2E+Certified+defenses+against+adversarial+examples%2E+In+International+Conference+on+Learning+Representations+%28ICLR%29%2E)
27. M. T. Ribeiro, S. Singh, and C. Guestrin. 2018. Semantically equivalent adversarial rules for debugging NLP models. In Association for Computational Linguistics (ACL). [find](https://scholar.google.com/scholar?q=M%2E+T%2E+Ribeiro%2C+S%2E+Singh%2C+and+C%2E+Guestrin%2E+2018%2E+Semantically+equivalent+adversarial+rules+for+debugging+NLP+models%2E+In+Association+for+Computational+Linguistics+%28ACL%29%2E)
28. C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. 2014. Intriguing properties of neural networks. In International Conference on Learning Representations (ICLR). [find](https://scholar.google.com/scholar?q=C%2E+Szegedy%2C+W%2E+Zaremba%2C+I%2E+Sutskever%2C+J%2E+Bruna%2C+D%2E+Erhan%2C+I%2E+Goodfellow%2C+and+R%2E+Fergus%2E+2014%2E+Intriguing+properties+of+neural+networks%2E+In+International+Conference+on+Learning+Representations+%28ICLR%29%2E) [our card](https://md.research.elamur.ai/free/en/papers/szegedy-2013-intriguing-properties-neural-networks/)