Elamur Research
☰
home / papers / 2020 / Word-level Textual Adversarial Attacking as Combinatorial Optimization

Word-level Textual Adversarial Attacking as Combinatorial Optimization

Written for the Research library (claude-opus-5-5) from the paper text. Original — aclanthology.org/2020.acl-main.540.pdf

Summary

Word substitution attacks on text classifiers can be framed as combinatorial optimization. This paper splits the task into two stages: first narrowing the space of candidate perturbations, then searching that space for an input that changes the model's prediction. The authors argue that earlier attacks struggled at both stages. Their substitute sets were either noisy (embedding or language-model neighbours) or too small (WordNet synonyms), and their black-box search procedures were slow or weak. They propose a black-box attack with two parts. Candidate replacements come from HowNet: two content words are interchangeable if they have the same POS and some sense of each carries identical sememe annotations. A discrete variant of particle swarm optimization (PSO) then explores the resulting combinations. The authors tested the attack against BiLSTM and BERT on three benchmark datasets. Compared with genetic and greedy baselines, it reaches higher success rates and produces better-quality adversarial examples. Its examples also transfer better between models and make adversarial training more effective. Code and data are publicly released.

Key points

  • HowNet covers more than 100,000 English and Chinese words, labelled at the sense level with roughly 2,000 sememes. This yields more substitutes than WordNet-based synonym methods without admitting antonyms.
  • Sememe+PSO achieved a 100% attack success rate on BiLSTM trained on IMDB. Against BiLSTM on SST-2 it reached 93.80%, compared with 67.70% for Embedding/LM+Genetic and 73.30% for Synonym+Greedy.
  • PSO beat the genetic algorithm consistently, with the largest gains under tight limits on iteration count and population size.
  • In the adversarial training experiment, 692 adversarial examples (10% of the SST-2 training set) were added to the training data and a BiLSTM was retrained. Training on Sememe+PSO examples gave the largest robustness gains. Using only manually verified valid examples improved robustness further, with a decrease in attack success of up to 5.10 points.
  • Code and data are available at github.com/thunlp/SememePSO-Attack.

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

Cited by

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

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2020.acl-main.540

@inproceedings{zang2020word,
  title = {{Word-level Textual Adversarial Attacking as Combinatorial Optimization}},
  author = {Zang, Yuan and Qi, Fanchao and Yang, Chenghao and Liu, Zhiyuan and Zhang, Meng and Liu, Qun and Sun, Maosong},
  booktitle = {Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics},
  year = {2020},
  doi = {10.18653/v1/2020.acl-main.540},
  url = {https://doi.org/10.18653/v1/2020.acl-main.540}
}

References

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

  1. Moustafa Alzantot, Yash Sharma, Ahmed Elgohary, Bo-Jhang Ho, Mani Srivastava, and Kai-Wei Chang. 2018. Generating natural language adversarial examples. In Proceedings of the EMNLP. find our card
  2. Yonatan Belinkov and Yonatan Bisk. 2018. Synthetic and natural noise both break neural machine translation. In Proceedings of ICLR. find
  3. Leonard Bloomfield. 1926. A set of postulates for the science of language. Language, 2(3). find
  4. Samuel Bowman, Gabor Angeli, Christopher Potts, and Christopher D Manning. 2015. A large annotated corpus for learning natural language inference. In Proceedings of EMNLP. find
  5. Leticia Cagnina, Marcelo Errecalde, Diego Ingaramo, and Paolo Rosso. 2014. An efficient particle swarm optimization approach to cluster short texts. Information Sciences, 265:36–49. find
  6. Alexis Conneau, Douwe Kiela, Holger Schwenk, Loı̈c Barrault, and Antoine Bordes. 2017. Supervised learning of universal sentence representations from natural language inference data. In Proceedings of EMNLP. find our card
  7. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of NAACL-HLT. find
  8. Zhendong Dong and Qiang Dong. 2006. HowNet and the computation of meaning. World Scientific. find
  9. Russell Eberhart and James Kennedy. 1995. Particle swarm optimization. In Proceedings of the IEEE International Conference on Neural Networks. find
  10. Javid Ebrahimi, Anyi Rao, Daniel Lowd, and Dejing Dou. 2018. Hotflip: White-box adversarial examples for text classification. In Proceedings of ACL. find our card
  11. Steffen Eger, Gözde Gül Şahin, Andreas Rücklé, Ji-Ung Lee, Claudia Schulz, Mohsen Mesgar, Krishnkant Swarnkar, Edwin Simpson, and Iryna Gurevych. 2019. Text processing like humans do: Visually attacking and shielding NLP systems. In Proceedings of NAACL-HLT. find
  12. Xianghua Fu, Guo Liu, Yanyan Guo, and Zhiqiang Wang. 2013. Multi-aspect sentiment analysis for chinese online social reviews based on topic modeling and hownet lexicon. Knowledge-Based Systems, 37:186–195. find
  13. Ji Gao, Jack Lanchantin, Mary Lou Soffa, and Yanjun Qi. 2018. Black-box generation of adversarial text sequences to evade deep learning classifiers. In Proceedings of IEEE Security and Privacy Workshops. find our card
  14. Max Glockner, Vered Shwartz, and Yoav Goldberg. 2018. Breaking nli systems with sentences that require simple lexical inferences. In Proceedings of ACL. find our card
  15. Zhitao Gong, Wenlu Wang, Bo Li, Dawn Song, and Wei-Shinn Ku. 2018. Adversarial texts with gradient methods. arXiv preprint arXiv:1801.07175. — [arXiv:1801.07175](https://arxiv.org/abs/1801.07175) find
  16. Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. 2015. Explaining and harnessing adversarial examples. In Proceedings of ICLR. find our card
  17. Rania Hassan, Babak Cohanim, Olivier De Weck, and Gerhard Venter. 2005. A comparison of particle swarm optimization and the genetic algorithm. In 46th AIAA/ASME/ASCE/AHS/ASC Structures, Structural Dynamics and Materials Conference. find
  18. Natsuki Higashi and Hitoshi Iba. 2003. Particle swarm optimization with gaussian mutation. In Proceedings of the 2003 IEEE Swarm Intelligence Symposium. find
  19. Hossein Hosseini, Sreeram Kannan, Baosen Zhang, and Radha Poovendran. 2017. Deceiving google’s perspective api built for detecting toxic comments. arXiv preprint arXiv:1702.08138. — [arXiv:1702.08138](https://arxiv.org/abs/1702.08138) find
  20. Mohit Iyyer, John Wieting, Kevin Gimpel, and Luke Zettlemoyer. 2018. Adversarial example generation with syntactically controlled paraphrase networks. In Proceedings of the NAACL-HLT. find our card
  21. Robin Jia and Percy Liang. 2017. Adversarial examples for evaluating reading comprehension systems. In Proceedings of EMNLP. find our card
  22. Di Jin, Zhijing Jin, Joey Tianyi Zhou, and Peter Szolovits. 2019. Is BERT really robust? Natural language attack on text classification and entailment. arXiv preprint arXiv:1907.11932. find our card
  23. James Kennedy and Russell C Eberhart. 1997. A discrete binary version of the particle swarm algorithm. In IEEE International Conference on Systems, Man, and Cybernetics. find
  24. J Zico Kolter and Marcus A Maloof. 2006. Learning to detect and classify malicious executables in the wild. Journal of Machine Learning Research, 7(Dec):2721–2744. find
  25. Alexey Kurakin, Ian Goodfellow, and Samy Bengio. 2016. Adversarial examples in the physical world. arXiv preprint arXiv:1607.02533. — [arXiv:1607.02533](https://arxiv.org/abs/1607.02533) find
  26. Bin Liang, Hongcheng Li, Miaoqiang Su, Pan Bian, Xirong Li, and Wenchang Shi. 2018. Deep text classification can be fooled. In Proceedings of IJCAI. find
  27. Andrew L Maas, Raymond E Daly, Peter T Pham, Dan Huang, Andrew Y Ng, and Christopher Potts. 2011. Learning word vectors for sentiment analysis. In Proceedings of ACL-HLT. find our card
  28. George A Miller. 1995. Wordnet: a lexical database for english. Communications of the ACM, 38(11):39– 41. find our card
  29. Yilin Niu, Ruobing Xie, Zhiyuan Liu, and Maosong Sun. 2017. Improved word representation learning with sememes. In Proceedings ACL. find
  30. Mahamed G Omran, Andries P Engelbrecht, and Ayed Salman. 2004. Image classification using particle swarm optimization. In Recent advances in simulated evolution and learning, pages 347–365. World Scientific. find
  31. Nicolas Papernot, Patrick McDaniel, Ananthram Swami, and Richard Harang. 2016. Crafting adversarial input sequences for recurrent neural networks. In Proceedings of MILCOM. find
  32. Jeffrey Pennington, Richard Socher, and Christopher Manning. 2014. Glove: Global vectors for word representation. In Proceedings of EMNLP. find
  33. Danish Pruthi, Bhuwan Dhingra, and Zachary C Lipton. 2019. Combating adversarial misspellings with robust word recognition. In Proceedings of ACL. find our card
  34. Fanchao Qi, Junjie Huang, Chenghao Yang, Zhiyuan Liu, Xiao Chen, Qun Liu, and Maosong Sun. 2019. Modeling semantic compositionality with sememe knowledge. In Proceedings of ACL. find
  35. Yujia Qin, Fanchao Qi, Sicong Ouyang, Zhiyuan Liu, Cheng Yang, Yasheng Wang, Qun Liu, and Maosong Sun. 2019. Enhancing recurrent neural networks with sememes. arXiv preprint arXiv:1910.08910. — [arXiv:1910.08910](https://arxiv.org/abs/1910.08910) find
  36. Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019. Language models are unsupervised multitask learners. OpenAI Blog, 1(8). find
  37. Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Ng, and Christopher Potts. 2013. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of EMNLP. find
  38. Gianluca Stringhini, Christopher Kruegel, and Giovanni Vigna. 2010. Detecting spammers on social networks. In Proceedings of the 26th Annual Computer Security Applications Conference. find
  39. Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. 2014. Intriguing properties of neural networks. In Proceedings of ICLR. find our card
  40. Eric Wallace, Shi Feng, Nikhil Kandpal, Matt Gardner, and Sameer Singh. 2019. Universal adversarial triggers for attacking and analyzing nlp. In Proceedings of EMNLP-IJCNLP. find
  41. Wenqi Wang, Lina Wang, Benxiao Tang, Run Wang, and Aoshuang Ye. 2019a. A survey: Towards a robust deep neural network in text domain. arXiv preprint arXiv:1902.07285. — [arXiv:1902.07285](https://arxiv.org/abs/1902.07285) find
  42. Xiaosen Wang, Hao Jin, and Kun He. 2019b. Natural language adversarial attacks and defenses in word level. arXiv preprint arXiv:1909.06723. — [arXiv:1909.06723](https://arxiv.org/abs/1909.06723) find
  43. Laurence A Wolsey and George L Nemhauser. 1999. Integer and combinatorial optimization. John Wiley & Sons. find
  44. Huangzhao Zhang, Hao Zhou, Ning Miao, and Lei Li. 2019a. Generating fluent adversarial examples for natural languages. In Proceedings of ACL. find
  45. Shuhuai Ren, Yihe Deng, Kun He, and Wanxiang Che. 2019. Generating natural language adversarial examples through probability weighted word saliency. In Proceedings of ACL. find our card
  46. Lei Zhang, Fanchao Qi, Zhiyuan Liu, Yasheng Wang, Qun Liu, and Maosong Sun. 2019b. Multi-channel reverse dictionary model. arXiv preprint arXiv:1912.08441. — [arXiv:1912.08441](https://arxiv.org/abs/1912.08441) find
  47. Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. 2018. Semantically equivalent adversarial rules for debugging nlp models. In Proceedings of ACL. find
  48. Zhengli Zhao, Dheeru Dua, and Sameer Singh. 2018. Generating natural adversarial examples. In Proceedings of ICLR. find
  49. Suranjana Samanta and Sameep Mehta. 2017. Towards crafting text adversarial samples. arXiv preprint arXiv:1707.02812. — [arXiv:1707.02812](https://arxiv.org/abs/1707.02812) find
  50. A Motoki Sato, Jun Suzuki, Hiroyuki Shindo, and Yuji Matsumoto. 2018. Interpretable adversarial perturbation in input embedding space for text. In Proceedings of IJCAI. find
  51. Yuhui Shi and Russell C Eberhart. 1998. Parameter selection in particle swarm optimization. In Proceedings of the International conference on evolutionary programming. Springer. find
  52. Ana Paula Silva, Arlindo Silva, and Irene Rodrigues. 2012. Biopos: Biologically inspired algorithms for pos tagging. In Proceedings of the First International Workshop on Optimization Techniques for Human Language Technology. find