  Machine learning models are brittle, and small changes in the training data
can result in different predictions. We study the problem of proving that a
prediction is robust to data poisoning, where an attacker can inject a number
of malicious elements into the training set to influence the learned model. We
target decision-tree models, a popular and simple class of machine learning
models that underlies many complex learning techniques. We present a sound
verification technique based on abstract interpretation and implement it in a
tool called Antidote. Antidote abstractly trains decision trees for an
intractably large space of possible poisoned datasets. Due to the soundness of
our abstraction, Antidote can produce proofs that, for a given input, the
corresponding prediction would not have changed had the training set been
tampered with or not. We demonstrate the effectiveness of Antidote on a number
of popular datasets.
