Abstract Interpretation of Decision Tree Ensemble Classifiers

Francesco Ranzato, Marco ZanellaAAAI 2020 · DOI

Introduction

In critical machine learning applications—such as malware detection, fraud prevention, or autonomous driving—accuracy alone is insufficient. Models must also be robust. While adversarial attacks on neural networks are well-documented, decision tree ensembles like Random Forests and Gradient Boosted Decision Trees (GBDTs) have received less formal verification attention. At AAAI-20, Francesco Ranzato and Marco Zanella presented a principled framework to close this gap using Abstract Interpretation, a classic technique from software engineering.

The Challenge of Formal Verification

Formal verification aims to prove that a classifier will return the same label for every possible point within a perturbation region (e.g., a ±1% change in pixel values). For high-dimensional data like MNIST, the search space for potential attacks is astronomically large, making exhaustive checking impossible. Previous tools for tree ensembles often lacked formal proofs of correctness or struggled to scale to industrial-sized forests.

Methodology: The silva Tool

The authors introduced silva, a tool named after the Latin word for forest, which applies abstract interpretation to verify ensemble robustness.

  1. Abstract Domains: Instead of individual data points, the algorithm analyzes "abstract" shapes—specifically hyperrectangles (boxes). These align naturally with the axis-parallel decision boundaries of standard decision trees.
  2. Refinement Algorithm: silva uses a best-first search to iteratively split the perturbation region. If a box is entirely within a region where the forest gives a consistent label, it is "proven." If a label change is found, the tool generates a concrete adversarial counterexample.
  3. Soundness and Completeness: The framework is mathematically proven to be sound (if it claims robustness, the model is robust) and complete (it will eventually find a proof if one exists, given sufficient time).

Key Insight: The Accuracy-Stability Paradox

A striking finding of the research is that more accurate models are not necessarily more robust. On the MNIST dataset, increasing tree depth initially improves both accuracy and stability, but stability eventually peaks and declines even as accuracy continues to rise.

Figure 2: MNIST Stability vs. Accuracy across different tree depths.

As shown in the figure above, a depth of 25 often represents the "sweet spot" for robustness. Increasing the depth to 50 can actually make the models easier to attack, despite marginal gains in accuracy.

Key Results and Performance

Implemented in C, silva achieved significant performance gains over previous state-of-the-art verifiers like VoTE. It demonstrated a 1.7x speedup on Random Forests and a 6.6x speedup on GBDTs.

Figure 5: Performance metrics for Random Forests across different configurations.

The table above illustrates how silva handles various forest sizes ($B$) and depths ($d$). While previous tools often timed out after seven hours on complex MNIST tasks, silva could verify a 100-tree GBDT in approximately 2.5 minutes.

Conclusion

By leveraging abstract interpretation, the authors have provided a scalable and mathematically rigorous way to verify the robustness of tree-based models. This work paves the way for "Certified Robust" training, where verification logic is integrated directly into the training loop to build models that are inherently resistant to adversarial manipulation.

Summary updated

BibTeX
@inproceedings{ranzato2020abstract,
  author = {Francesco Ranzato and Marco Zanella},
  title = {{Abstract Interpretation of Decision Tree Ensemble Classifiers}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i04.5998},
}
Figure