Elsevier

Computers & Security

Volume 121, October 2022, 102843
Computers & Security

Beyond robustness: Resilience verification of tree-based classifiers

https://doi.org/10.1016/j.cose.2022.102843Get rights and content

Abstract

In this paper we criticize the robustness measure traditionally employed to assess the performance of machine learning models deployed in adversarial settings. To mitigate the limitations of robustness, we introduce a new measure called resilience and we focus on its verification. In particular, we discuss how resilience can be verified by combining a traditional robustness verification technique with a data-independent stability analysis, which identifies a subset of the feature space where the model does not change its predictions despite adversarial manipulations. We then introduce a formally sound data-independent stability analysis for decision trees and decision tree ensembles, which we experimentally assess on public datasets and we leverage for resilience verification. Our results show that resilience verification is useful and feasible in practice, yielding a more reliable security assessment of both standard and robust decision tree models.

Introduction

Machine Learning (ML) is becoming more and more popular nowadays, in particular for classification tasks, yet it is acknowledged to be susceptible to different types of attacks. A number of research papers showed that classifiers trained using standard ML algorithms cannot be deployed in security-sensitive settings, because they are easily fooled in practice and their performance undergoes significant downgrade when their inputs are subject to adversarial manipulations, imperceptible to human experts (Goodfellow, Shlens, Szegedy, 2015, Szegedy, Zaremba, Sutskever, Bruna, Erhan, Goodfellow, Fergus, 2014). This motivated the development of new performance measures like robustness, which generalize traditional measures like accuracy to account for the threats of adversarial manipulations at test time (Madry, Makelov, Schmidt, Tsipras, Vladu, 2018, Ranzato, Zanella, 2020). Specifically, given an input x and its correct class y, robustness requires the classifier to predict the class y also for all the adversarial manipulations A(x), rather than just for the original input x.

Robustness is certainly an intuitive and desirable property to estimate the performance of classifiers deployed in adversarial settings, yet it is sub-optimal because it is strongly dependent on the choice of a specific input x. While the performance of classifiers must indeed be empirically estimated on a set of correctly labeled inputs (test set), such inputs are normally assumed to be sampled from an underlying data distribution and robustness tells nothing about unsampled data. In other words, a robustness proof for x does not provide any guarantee about any other input z close to x which could have been sampled in place of it. This is concerning, because the actual inputs of the classifier at test time will be different samples drawn from the same distribution of x, which are not covered by standard security assessments based on robustness. This problem has been independently acknowledged in very recent work on global robustness properties (Chen, Wang, Qin, Liao, Jana, Wagner, 2021, Leino, Wang, Fredrikson, 2021), which advocates the need for verification techniques establishing robustness guarantees on all the possible inputs provided to the classifier. Unfortunately, these efforts are still at an early stage and there is no uniform “one size fits all” definition of global robustness that can be readily used to verify the security of classifiers (see Section 6 for a discussion). Our work falls in the same research line of global robustness properties, yet it takes a different direction to better complement the extensive amount of work on robustness verification.

In particular, we here propose a generalization of robustness, called resilience, designed to make the security assessment of classifiers more reliable. Resilience generalizes traditional robustness guarantees from a specific test set to all the other possible test sets which could have been sampled in place of it, i.e., which are close to it given an appropriate definition of neighborhood. Resilience thus provides a more conservative account of the security of classifiers than robustness, while retaining its intuitive flavour. Most importantly, the connection between resilience and robustness allows one to leverage traditional tools for robustness verification as the first step of a resilience verification pipeline, thus integrating with significant research efforts spent on robustness verification.

Contributions In the present paper we make the following contributions:

  • 1.

    We criticize the traditional robustness measure used to estimate the security of classifiers against evasion attacks and we propose an improved measure called resilience. We then discuss how resilience can be estimated by combining an arbitrary robustness verification technique with a data-independent stability analysis, which identifies a subset of the feature space where the classifier does not change its predictions despite adversarial manipulations at test time. The analysis is data-independent because it is based on the classifier alone, rather than on a specific test set (contrary to robustness). We finally present a simple technique to turn any classifier into a globally robust classifier (in the sense of Leino et al., 2021) by leveraging such data-independent stability analysis, thus clarifying the connections with recent work in the area (Section 3).

  • 2.

    We propose a data-independent stability analysis for decision trees and decision tree ensembles, a popular class of ML models (Quinlan, 1986). The stability analysis is based on symbolic attacks, i.e., symbolic representations of a set of instances along with their (relevant) adversarial manipulations, which support the analysis of tree-based classifiers independently of a specific test set. Our analysis is proved sound and can be readily leveraged to establish both robustness and resilience proofs for tree-based classifiers (Section 4).

  • 3.

    We implement our data-independent stability analysis1 and we experimentally assess its effectiveness on public datasets, by estimating the robustness and resilience of both standard and robust tree models trained using a state-of-the-art adversarial ML algorithm (Section 5).

Our experimental evaluation shows that resilience verification is both useful and feasible in practice, yielding a more reliable security assessment of classifiers deployed in adversarial settings. In particular, our experiments show that robustness can be significantly affected by the choice of a specific test set, hence it may give a false sense of security, while resilience is effective at discriminating between secure models and models which turned out to be robust just by accident, i.e., thanks to a lucky, specific sampling of the test set. We thus recommend the use of resilience for the security verification of ML models deployed in adversarial scenarios.

Section snippets

Background

We introduce here the key technical ingredients required to appreciate this work.

Resilience

We now discuss important shortcomings in the traditional robustness measure and we propose a generalization of robustness, called resilience, which is designed to mitigate those. We then explain how resilience can be verified in practice and we further elaborate on its design by discussing its connections with a recent definition of global robustness (Leino et al., 2021).

Data-independent stability analysis

We present here a data-independent stability analysis for decision trees and decision tree ensembles, which allows one to compute the two measures r^ and R^ defined in Section 3.2, thus providing conservative estimates of robustness and (most importantly) resilience. The analysis is proved sound, i.e., we show that the portions of the feature space which are marked as stable by the analysis may only contain instances where the classifier is indeed stable. Proofs are given in Appendix A.

Experimental evaluation

We finally report on the experimental evaluation of our resilience verification technique. We first discuss the setup and the research questions, then we present the key experiments and results.

Global robustness

Recent independent work in the area also acknowledged the limitations of robustness for the security verification of classifiers (Chen, Wang, Qin, Liao, Jana, Wagner, 2021, Leino, Wang, Fredrikson, 2021). Chen et al. defined a set of five new global robustness properties, i.e., universally-quantified statements over one or more inputs to the classifier and its corresponding outputs (Chen et al., 2021). These properties also include a data-independent stability definition, that requires any two

Conclusion

We criticized the traditional robustness measure used to assess the security of classifiers against evasion attacks and we proposed an improved measure called resilience, which provides additional assurances on unsampled data outside the test set. We then discussed how resilience can be estimated by combining traditional tools for robustness verification with a data-independent stability analysis, which does not depend on a specific test set. We finally proposed a formally sound

CRediT authorship contribution statement

Stefano Calzavara: Formal analysis, Writing – original draft, Writing – review & editing. Lorenzo Cazzaro: Software, Investigation. Claudio Lucchese: Conceptualization, Supervision. Federico Marcuzzi: Software, Investigation. Salvatore Orlando: Conceptualization, Supervision.

Declaration of Competing Interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Stefano Calzavara is an associate professor in computer science at Universitá Ca’ Foscari Venezia, Italy. His research focuses on computer security, with a strong focus on formal methods and web security. He has published more than 50 papers on these topics at reputable international conferences and journals.

References (22)

  • M. Andriushchenko et al.

    Provably robust boosted decision stumps and trees against adversarial attacks

  • B. Biggio et al.

    Support vector machines under adversarial label noise

  • S. Calzavara et al.

    Certifying decision trees against evasion attacks by program analysis

  • S. Calzavara et al.

    Treant: training evasion-aware decision trees

    Data Min. Knowl. Discov.

    (2020)
  • S. Calzavara et al.

    Feature partitioning for robust tree ensembles and their certification in adversarial scenarios

    EURASIP J. Inf. Secur.

    (2021)
  • S. Calzavara et al.

    Adversarial training of gradient-boosted decision trees

  • H. Chen et al.

    Robust decision trees against adversarial examples

  • H. Chen et al.

    Robustness verification of tree-based models

  • Y. Chen et al.

    Learning security classifiers with verified global robustness properties

  • J.H. Friedman

    Greedy function approximation: a gradient boosting machine

    Ann. Stat.

    (2001)
  • I.J. Goodfellow et al.

    Explaining and harnessing adversarial examples

  • Cited by (7)

    • Verifiable Learning for Robust Tree Ensembles

      2023, CCS 2023 - Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security
    • Decision trees: from efficient prediction to responsible AI

      2023, Frontiers in Artificial Intelligence
    View all citing articles on Scopus

    Stefano Calzavara is an associate professor in computer science at Universitá Ca’ Foscari Venezia, Italy. His research focuses on computer security, with a strong focus on formal methods and web security. He has published more than 50 papers on these topics at reputable international conferences and journals.

    Lorenzo Cazzaro is a PhD student in Computer Science at the University Ca’ Foscari of Venice. He graduated cum laude in Computer Science in 2021. His main research interest include adversarial machine learning, verification of machine learning models and applications of artificial intelligence and machine learning in cybersecurity.

    Claudio Lucchese is professor with the Universitá Ca’ Foscari di Venezia - Departiment of Environmental Sciences, Informatics and Statistics (DAIS). His main research activities are in the areas of Information Retrieval, Explainable AI, Data Mining. He has published more than 100 papers on these topics in peer reviewed international journals, conferences and other venues. He won the Best Paper Award at the ACM SIGIR Conference on Research and Development in Information Retrieval 2015. He participated to and coordinated activities in European and Italian national projects. Since 2018 he is Delegate of the Head of the Department for Research activities. He is a member of the Data Mining and Information Retrieval Lab.

    Federico Marcuzzi is a PhD student in Computer Science at Ca’ Foscari University of Venice. He graduated cum laude in 2020 and he was a research fellow in the filed of Adversarial Machine Learning until 2020. His main research fields are Information Retrieval and Adversarial Machine Learning.

    Salvatore Orlando (http://www.dais.unive.it/~orlando) MSc (1985) and PhD (1991) in Computer Science, University of Pisa is a full professor at Ca’ Foscari University of Venice. His research interests include data and web mining, information retrieval, parallel/distributed systems. He published over 150 papers in journals and conference proceedings on these topics.

    View full text