# Timber! Poisoning Decision Trees

arXiv: https://arxiv.org/abs/2410.00862 · HTML: https://mlsanity.com/paper/2410.00862/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 65 references that are in the map.
- First posted on arXiv 1 Oct 2024.

## Builds on (most cited first, 29 of 29)

- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning](https://mlsanity.com/paper/1712.05526/) (2017)
- [Making Deep Neural Networks Robust to Label Noise: a Loss Correction Approach](https://mlsanity.com/paper/1609.03683/) (2016)
- [Poison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks](https://mlsanity.com/paper/1804.00792/) (2018)
- [Certified Defenses for Data Poisoning Attacks](https://mlsanity.com/paper/1706.03691/) (2017)
- [Manipulating Machine Learning: Poisoning Attacks and Countermeasures for Regression Learning](https://mlsanity.com/paper/1804.00308/) (2018)
- [Towards Poisoning of Deep Learning Algorithms with Back-gradient Optimization](https://mlsanity.com/paper/1708.08689/) (2017)
- [You Autocomplete Me: Poisoning Vulnerabilities in Neural Code Completion](https://mlsanity.com/paper/2007.02220/) (2020)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [MetaPoison: Practical General-purpose Clean-label Data Poisoning](https://mlsanity.com/paper/2004.00225/) (2020)
- [Deep Partition Aggregation: Provable Defense against General Poisoning Attacks](https://mlsanity.com/paper/2006.14768/) (2020)
- [Certified Robustness to Label-Flipping Attacks via Randomized Smoothing](https://mlsanity.com/paper/2002.03018/) (2020)
- [Intrinsic Certified Robustness of Bagging against Data Poisoning Attacks](https://mlsanity.com/paper/2008.04495/) (2020)
- [Wild Patterns Reloaded: A Survey of Machine Learning Security against Training Data Poisoning](https://mlsanity.com/paper/2205.01992/) (2022)
- [Is feature selection secure against training data poisoning?](https://mlsanity.com/paper/1804.07933/) (2018)
- [Label Sanitization against Label Flipping Poisoning Attacks](https://mlsanity.com/paper/1803.00992/) (2018)
- [Learning to Confuse: Generating Training Time Adversarial Data with Auto-Encoder](https://mlsanity.com/paper/1905.09027/) (2019)
- [Improved Certified Defenses against Data Poisoning with (Deterministic) Finite Aggregation](https://mlsanity.com/paper/2202.02628/) (2022)
- [Preventing Unauthorized Use of Proprietary Data: Poisoning for Secure Dataset Release](https://mlsanity.com/paper/2103.02683/) (2021)
- [Certifying Robustness to Programmable Data Bias in Decision Trees](https://mlsanity.com/paper/2110.04363/) (2021)
- [Support Vector Machines under Adversarial Label Contamination](https://mlsanity.com/paper/2206.00352/) (2022)
- [On Collective Robustness of Bagging Against Data Poisoning](https://mlsanity.com/paper/2205.13176/) (2022)
- [Attack Strength vs. Detectability Dilemma in Adversarial Machine Learning](https://mlsanity.com/paper/1802.07295/) (2018)
- [Analysis of Label-Flip Poisoning Attack on Machine Learning Based Malware Detector](https://mlsanity.com/paper/2301.01044/) (2023)
- [Curie: A method for protecting SVM Classifier from Poisoning Attack](https://mlsanity.com/paper/1606.01584/) (2016)
- [Label Flipping Data Poisoning Attack Against Wearable Human Activity Recognition System](https://mlsanity.com/paper/2208.08433/) (2022)
- [The Power of Localization for Efficiently Learning Linear Separators with Noise](https://mlsanity.com/paper/1307.8371/) (2013)
- [On the Robustness of Random Forest Against Untargeted Data Poisoning: An Ensemble-Based Approach](https://mlsanity.com/paper/2209.14013/) (2022)

## Abstract (arXiv)

We present Timber, the first white-box poisoning attack targeting decision trees. Timber is based on a greedy attack strategy that leverages sub-tree retraining to efficiently estimate the damage caused by poisoning a given training instance. The attack relies on a tree annotation procedure, which enables the sorting of training instances so that they are processed in increasing order of the computational cost of sub-tree retraining. This sorting yields a variant of Timber that supports an early stopping criterion, designed to make poisoning attacks more efficient and feasible on larger datasets. We also discuss an extension of Timber to traditional random forest models, which is valuable since decision trees are typically combined into ensembles to improve their predictive power. Our experimental evaluation on public datasets demonstrates that our attacks outperform existing baselines in terms of effectiveness, efficiency, or both. Moreover, we show that two representative defenses can mitigate the effect of our attacks, but fail to effectively thwart them.