{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T11:21:59Z","timestamp":1772623319220,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,11,24]],"date-time":"2021-11-24T00:00:00Z","timestamp":1637712000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,11,24]],"date-time":"2021-11-24T00:00:00Z","timestamp":1637712000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007601","name":"horizon 2020","doi-asserted-by":"publisher","award":["956123"],"award-info":[{"award-number":["956123"]}],"id":[{"id":"10.13039\/501100007601","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2022,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The embedding and extraction of knowledge is a recent trend in machine learning applications, e.g., to supplement training datasets that are small. Whilst, as the increasing use of machine learning models in security-critical applications, the embedding and extraction of malicious knowledge are equivalent to the notorious backdoor attack and defence, respectively. This paper studies the embedding and extraction of knowledge in tree ensemble classifiers, and focuses on knowledge expressible with a generic form of Boolean formulas, e.g., point-wise robustness and backdoor attacks. For the embedding, it is required to be<jats:italic>preservative<\/jats:italic>(the original performance of the classifier is preserved),<jats:italic>verifiable<\/jats:italic>(the knowledge can be attested), and<jats:italic>stealthy<\/jats:italic>(the embedding cannot be easily detected). To facilitate this, we propose two novel, and effective embedding algorithms, one of which is for black-box settings and the other for white-box settings. The embedding can be done in<jats:bold>PTIME<\/jats:bold>. Beyond the embedding, we develop an algorithm to extract the embedded knowledge, by reducing the problem to be solvable with an SMT (satisfiability modulo theories) solver. While this novel algorithm can successfully extract knowledge, the reduction leads to an<jats:bold>NP<\/jats:bold>computation. Therefore, if applying embedding as backdoor attacks and extraction as defence, our results suggest a complexity gap (P vs. NP) between the attack and defence when working with tree ensemble classifiers. We apply our algorithms to a diverse set of datasets to validate our conclusion extensively.<\/jats:p>","DOI":"10.1007\/s10994-021-06068-6","type":"journal-article","created":{"date-parts":[[2021,11,24]],"date-time":"2021-11-24T16:02:35Z","timestamp":1637769755000},"page":"1925-1958","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Embedding and extraction of knowledge in tree ensemble classifiers"],"prefix":"10.1007","volume":"111","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1418-6267","authenticated-orcid":false,"given":"Wei","family":"Huang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xingyu","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaowei","family":"Huang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,11,24]]},"reference":[{"key":"6068_CR1","unstructured":"Asuncion, A., & Newman, D. (2007). Uci machine learning repository."},{"key":"6068_CR2","doi-asserted-by":"crossref","unstructured":"Bachl, M., Hartl, A., Fabini, J., & Zseby, T. (2019). Walling up backdoors in intrusion detection systems. In Proceedings of the 3rd ACM CoNEXT workshop on big data, machine learning and artificial intelligence for data communication networks (pp. 8\u201313).","DOI":"10.1145\/3359992.3366638"},{"key":"6068_CR3","doi-asserted-by":"crossref","unstructured":"Calzavara, S., Lucchese, C., & Tolomei, G. (2019). Adversarial training of gradient-boosted decision trees. In Proceedings of the 28th ACM international conference on information and knowledge management, (pp. 2429\u20132432).","DOI":"10.1145\/3357384.3358149"},{"issue":"3","key":"6068_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1961189.1961199","volume":"2","author":"CC Chang","year":"2011","unstructured":"Chang, C. C., & Lin, C. J. (2011). Libsvm: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology (TIST), 2(3), 1\u201327.","journal-title":"ACM Transactions on Intelligent Systems and Technology (TIST)"},{"key":"6068_CR5","unstructured":"Chen, B., Carvalho, W., Baracaldo, N., Ludwig, H., Edwards, B., Lee, T., Molloy, I., & Srivastava, B. (2019). Detecting backdoor attacks on deep neural networks by activation clustering. In Workshop on artificial intelligence safety 2019 co-located with the thirty-third AAAI conference on artificial intelligence, vol. 2301."},{"key":"6068_CR6","unstructured":"Chen, H., Zhang, H., Boning, D., & Hsieh, C. J. (2019). Robust decision trees against adversarial examples. In Proceedings of the 36th international conference on machine learning (Vol.\u00a097, pp. 1122\u20131131)."},{"key":"6068_CR7","unstructured":"Chen, X., Liu, C., Li, B., Lu, K., & Song, D. (2017). Targeted backdoor attacks on deep learning systems using data poisoning. CoRR. (abs\/1712.05526)."},{"issue":"5","key":"6068_CR8","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1109\/MNET.011.1900577","volume":"34","author":"Y Chen","year":"2020","unstructured":"Chen, Y., Gong, X., Wang, Q., Di, X., & Huang, H. (2020). Backdoor attacks and defenses for deep neural networks in outsourced cloud environments. IEEE Network, 34(5), 141\u2013147. https:\/\/doi.org\/10.1109\/MNET.011.1900577","journal-title":"IEEE Network"},{"issue":"3","key":"6068_CR9","doi-asserted-by":"publisher","first-page":"806","DOI":"10.1557\/mrc.2019.90","volume":"9","author":"CM Childs","year":"2019","unstructured":"Childs, C. M., & Washburn, N. R. (2019). Embedding domain knowledge for machine learning of complex material systems. MRS Communications, 9(3), 806\u2013820. https:\/\/doi.org\/10.1557\/mrc.2019.90","journal-title":"MRS Communications"},{"key":"6068_CR10","unstructured":"Du, M., Jia, R., & Song, D. (2020). Robust anomaly detection and backdoor attack detection via differential privacy. In International conference on learning representations (ICLR)."},{"key":"6068_CR11","doi-asserted-by":"crossref","unstructured":"Einziger, G., Goldstein, M., Sa\u2019ar, Y., & Segall, I. (2019). Verifying robustness of gradient boosted models. In The thirty-third AAAI conference on artificial intelligence (pp. 2446\u20132453). AAAI Press.","DOI":"10.1609\/aaai.v33i01.33012446"},{"issue":"4","key":"6068_CR12","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1002\/(SICI)1526-4025(199910\/12)15:4<277::AID-ASMB393>3.0.CO;2-B","volume":"15","author":"F Esposito","year":"1999","unstructured":"Esposito, F., Malerba, D., Semeraro, G., & Tamma, V. (1999). The effects of pruning methods on the predictive accuracy of induced decision trees. Applied Stochastic Models in Business and Industry, 15(4), 277\u2013299.","journal-title":"Applied Stochastic Models in Business and Industry"},{"key":"6068_CR13","doi-asserted-by":"crossref","unstructured":"Gao, H., Chen, Y., & Zhang, W. (2019). Detection of trojaning attack on neural networks via cost of sample classification. Security and Communication Networks.","DOI":"10.1155\/2019\/1953839"},{"key":"6068_CR14","doi-asserted-by":"publisher","first-page":"47230","DOI":"10.1109\/ACCESS.2019.2909068","volume":"7","author":"T Gu","year":"2019","unstructured":"Gu, T., Liu, K., Dolan-Gavitt, B., & Garg, S. (2019). Badnets: Evaluating backdooring attacks on deep neural networks. IEEE Access, 7, 47230\u201347244.","journal-title":"IEEE Access"},{"issue":"2","key":"6068_CR15","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1080\/00031305.1998.10480559","volume":"52","author":"JL Hintze","year":"1998","unstructured":"Hintze, J. L., & Nelson, R. D. (1998). Violin plots: A box plot-density trace synergism. The American Statistician, 52(2), 181\u2013184.","journal-title":"The American Statistician"},{"issue":"8","key":"6068_CR29","doi-asserted-by":"publisher","first-page":"832","DOI":"10.1109\/34.709601","volume":"20","author":"TK Ho","year":"1998","unstructured":"Ho, T. K. (1998). The random subspace method for constructing decision forests. IEEE Transactions on Pattern Analysis and Machine Intelligence, 20(8), 832\u2013844.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"6068_CR16","unstructured":"Kantchelian, A., Tygar, J. D., Joseph, A. D. (2016). Evasion and hardening of tree ensemble classifiers. In Proceedings of the 33nd international conference on machine learning (Vol.\u00a048, pp. 2387\u20132396)."},{"key":"6068_CR17","doi-asserted-by":"crossref","unstructured":"Lamb, L. C., d\u2019Avila Garcez, A. S., Gori, M., Prates, M. O. R., Avelar, P. H. C., & Vardi, M. Y. (2020). Graph neural networks meet neural-symbolic computing: A survey and perspective. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, 4877\u20134884.","DOI":"10.24963\/ijcai.2020\/679"},{"key":"6068_CR18","doi-asserted-by":"crossref","unstructured":"Liu, K., Dolan-Gavitt, B., & Garg, S. (2018). Fine-pruning: Defending against backdooring attacks on deep neural networks. In Research in attacks, intrusions, and defenses - 21st international symposium, RAID, Lecture Notes in Computer Science (Vol. 11050, pp. 273\u2013294). Springer.","DOI":"10.1007\/978-3-030-00470-5_13"},{"key":"6068_CR19","doi-asserted-by":"crossref","unstructured":"Liu, Y., Ma, S., Aafer, Y., Lee, W., Zhai, J., Wang, W., & Zhang, X. (2018). Trojaning attack on neural networks. In 25th annual network and distributed system security symposium. The Internet Society.","DOI":"10.14722\/ndss.2018.23291"},{"key":"6068_CR20","doi-asserted-by":"crossref","unstructured":"Liu, Y., Xie, Y., & Srivastava, A. (2017). Neural trojans. In 2017 IEEE international conference on computer design (pp. 45\u201348). IEEE Computer Society.","DOI":"10.1109\/ICCD.2017.16"},{"key":"6068_CR21","doi-asserted-by":"crossref","unstructured":"Maes, F., Geurts, P., & Wehenkel, L. (2012). Embedding monte carlo search of features in tree-based ensemble methods. In Joint European conference on machine learning and knowledge discovery in databases (pp. 191\u2013206). Springer.","DOI":"10.1007\/978-3-642-33460-3_18"},{"key":"6068_CR22","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1016\/B978-008045405-4.00149-X","volume-title":"Encyclopedia of ecology","author":"G Moisen","year":"2008","unstructured":"Moisen, G. (2008). Classification and regression trees. In S. E. J\u00f8rgensen & B. D. Fath (Eds.), Encyclopedia of ecology (Vol. 1, pp. 582\u2013588). Oxford, UK: Elsevier."},{"key":"6068_CR23","unstructured":"Qiao, X., Yang, Y., & Li, H. (2019). Defending neural backdoors via generative distribution modeling. In Advances in neural information processing systems (pp. 14004\u201314013)."},{"key":"6068_CR24","doi-asserted-by":"crossref","unstructured":"Ranzato, F., & Zanella, M. (2020). Abstract interpretation of decision tree ensemble classifiers. In In Proceedings of the thirty-fourth AAAI conference on artificial. (Intelligence).","DOI":"10.1609\/aaai.v34i04.5998"},{"issue":"3","key":"6068_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3178582","volume":"51","author":"PAA Resende","year":"2018","unstructured":"Resende, P. A. A., & Drummond, A. C. (2018). A survey of random forest based methods for intrusion detection systems. ACM Computing Surveys (CSUR), 51(3), 1\u201336.","journal-title":"ACM Computing Surveys (CSUR)"},{"issue":"2","key":"6068_CR26","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1587\/transinf.2019EDP7120","volume":"103D","author":"N Sato","year":"2020","unstructured":"Sato, N., Kuruma, H., Nakagawa, Y., & Ogawa, H. (2020). Formal verification of a decision-tree ensemble model and detection of its violation ranges. IEICE Transation Information System, 103D(2), 363\u2013378.","journal-title":"IEICE Transation Information System"},{"key":"6068_CR27","unstructured":"Shafahi, A., Huang, W. R., Najibi, M., Suciu, O., Studer, C., Dumitras, T., & Goldstein, T. (2018). Poison frogs! targeted clean-label poisoning attacks on neural networks. In Advances in neural information processing systems 31: annual conference on neural information processing systems (pp. 6106\u20136116)."},{"key":"6068_CR28","unstructured":"Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., & Fergus, R. (2014). Intriguing properties of neural networks. In ICLR2014."},{"key":"6068_CR30","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/978-3-030-26250-1_24","volume-title":"Computer Safety, Reliability, and Security","author":"J T\u00f6rnblom","year":"2019","unstructured":"T\u00f6rnblom, J., & Nadjm-Tehrani, S. (2019). An abstraction-refinement approach to formal verification of tree ensembles. In A. Romanovsky, E. Troubitsyna, I. Gashi, E. Schoitsch, & F. Bitsch (Eds.), Computer Safety, Reliability, and Security (pp. 301\u2013313). Cham: Springer International Publishing."},{"key":"6068_CR31","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2020.102450","volume":"194","author":"J T\u00f6rnblom","year":"2020","unstructured":"T\u00f6rnblom, J., & Nadjm-Tehrani, S. (2020). Formal verification of input-output mappings of tree ensembles. Science Computer Programm, 194, 102450.","journal-title":"Science Computer Programm"},{"key":"6068_CR32","doi-asserted-by":"crossref","unstructured":"Wang, X., He, X., Feng, F., Nie, L., & Chua, T. S. (2018). Tem: Tree-enhanced embedding model for explainable recommendation. In Proceedings of the 2018 world wide web conference (pp. 1543\u20131552).","DOI":"10.1145\/3178876.3186066"},{"key":"6068_CR33","unstructured":"Webb, S., Rainforth, T., Teh, Y. W., & Kumar, M. P. (2018). A statistical approach to assessing neural network robustness. In International Conference on Learning. (Representations)."},{"key":"6068_CR34","unstructured":"Yang, Y., Rashtchian, C., Zhang, H., Salakhutdinov, R. R., & Chaudhuri, K. (2020). A closer look at accuracy vs. robustness. In Advances in neural information processing systems 33: annual conference on neural information processing systems 2020, NeurIPS 2020, December 6\u201312, 2020, virtual. https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/61d77652c97ef636343742fc3dcf3ba9-Abstract.html."},{"key":"6068_CR35","doi-asserted-by":"crossref","unstructured":"Zhao, Q., Shi, Y., & Hong, L. (2017). Gb-cent: Gradient boosted categorical embedding and numerical trees. In Proceedings of the 26th international conference on world wide web (pp. 1311\u20131319).","DOI":"10.1145\/3038912.3052668"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-06068-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-021-06068-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-06068-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T19:24:59Z","timestamp":1726169099000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-021-06068-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,24]]},"references-count":35,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["6068"],"URL":"https:\/\/doi.org\/10.1007\/s10994-021-06068-6","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,24]]},"assertion":[{"value":"13 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 July 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 September 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 November 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"Yes.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Yes.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}