Proving Data-Poisoning Robustness in Decision Trees

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.

Automated summary

This paper investigates the brittleness of machine learning models, where small changes in training data could lead to different predictions. It proposes a verification technique based on abstract interpretation for decision tree models, and develops a tool called Antidote. Antidote abstractly trains decision trees for various possible poisoned datasets. With the soundness of the abstraction, Antidote can provide proofs that the prediction would stay the same regardless of tampering with the training data, for a given input. The effectiveness of Antidote is demonstrated on several popular datasets.