  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.
  The key insight of our approach is an application of abstract interpretation
that exploits recursive LSTM structure to incrementally propagate symbolic sets
of inputs, compactly representing a large perturbation space. 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.
