{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:09:08Z","timestamp":1750219748312,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T00:00:00Z","timestamp":1674172800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1652140, 1704117, 1750965, and 1918211"],"award-info":[{"award-number":["1652140, 1704117, 1750965, and 1918211"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:p>\n            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\n            <jats:italic>data poisoning<\/jats:italic>\n            , 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\n            <jats:italic>abstract interpretation<\/jats:italic>\n            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.\n          <\/jats:p>","DOI":"10.1145\/3576894","type":"journal-article","created":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T15:29:38Z","timestamp":1674228578000},"page":"105-113","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Proving Data-Poisoning Robustness in Decision Trees"],"prefix":"10.1145","volume":"66","author":[{"given":"Samuel","family":"Drews","sequence":"first","affiliation":[{"name":"University of Wisconsin-Madison"}]},{"given":"Aws","family":"Albarghouthi","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison"}]},{"given":"Loris","family":"D'Antoni","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison"}]}],"member":"320","published-online":{"date-parts":[[2023,1,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781680839111"},{"volume-title":"Proceedings of the 29th International Conference on Machine Learning, ICML'12, Omnipress.","author":"Biggio B.","key":"e_1_2_1_2_1","unstructured":"Biggio, B., Nelson, B., Laskov, P. Poisoning attacks against support vector machines. In Proceedings of the 29th International Conference on Machine Learning, ICML'12, Omnipress."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1201\/9781315139470"},{"volume-title":"2017 IEEE Symposium on Security and Privacy (SP). IEEE, 39--57","author":"Carlini N.","key":"e_1_2_1_4_1","unstructured":"Carlini, N., Wagner, D. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy (SP). IEEE, 39--57."},{"key":"e_1_2_1_5_1","volume-title":"Targeted backdoor attacks on deep learning systems using data poisoning. arXiv:1712.05526","author":"Chen X.","year":"2017","unstructured":"Chen, X., Liu, C., Li, B., Lu, K., Song, D. Targeted backdoor attacks on deep learning systems using data poisoning. arXiv:1712.05526, 2017."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/512950.512973"},{"key":"e_1_2_1_7_1","volume-title":"UCI machine learning repository","author":"Dua D.","year":"2017","unstructured":"Dua, D., Graff, C. UCI machine learning repository, 2017."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.00058"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63387-9_5"},{"key":"e_1_2_1_10_1","volume-title":"Curie: A method for protecting SVM classifier from poisoning attack. CoRR, abs\/1606.01584","author":"Laishram R.","year":"2016","unstructured":"Laishram, R., Phoha, V.V. Curie: A method for protecting SVM classifier from poisoning attack. CoRR, abs\/1606.01584, 2016."},{"key":"e_1_2_1_11_1","unstructured":"LeCun Y. Cortes C. Burges C.J.C. The MNIST database of handwritten digits."},{"key":"e_1_2_1_12_1","volume-title":"International Conference on Learning Representations","author":"Levine A.","year":"2020","unstructured":"Levine, A., Feizi, S. Deep partition aggregation: Provable defenses against general poisoning attacks. In International Conference on Learning Representations, 2020."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9569"},{"key":"e_1_2_1_14_1","volume-title":"Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems","author":"Meyer A.P.","year":"2021","unstructured":"Meyer, A.P., Albarghouthi, A., D'Antoni, L. Certifying robustness to programmable data bias in decision trees. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, December 6-14, 2021."},{"volume-title":"Proceedings of the 2014 Workshop on Artificial Intelligent and Security Workshop","author":"Newell A.","key":"e_1_2_1_15_1","unstructured":"Newell, A., Potharaju, R., Xiang, L., Nita-Rotaru, C. On the practicality of integrity attacks on document-level sentiment analysis. In Proceedings of the 2014 Workshop on Artificial Intelligent and Security Workshop (New York, NY, USA). ACM, 83--93."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022643204877"},{"key":"e_1_2_1_17_1","volume-title":"Morgan Kaufmann","author":"Quinlan J.R.","year":"1993","unstructured":"Quinlan, J.R. C4.5: Programs for machine learning. The Morgan Kaufmann Series in Machine Learning, Morgan Kaufmann, San Mateo, CA, 1993."},{"key":"e_1_2_1_18_1","volume-title":"International Conference on Machine Learning. PMLR","author":"Rosenfeld E.","year":"2020","unstructured":"Rosenfeld, E., Winston, E., Ravikumar, P., Kolter, Z. Certified robustness to label-flipping attacks via randomized smoothing. In International Conference on Machine Learning. PMLR, 2020, 8230--8241."},{"key":"e_1_2_1_19_1","first-page":"3529","article-title":"Certified defenses for data poisoning attacks","volume":"3517","author":"Steinhardt J.","year":"2017","unstructured":"Steinhardt, J., Koh, P.W.W., Liang, P.S. Certified defenses for data poisoning attacks. In Advances in Neural Information Processing Systems, 2017, 3517--3529.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_20_1","volume-title":"2nd International Conference on Learning Representations, Banff, AB, Canada","author":"Szegedy C.","year":"2014","unstructured":"Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I. J., Fergus, R. Intriguing properties of neural networks. In 2nd International Conference on Learning Representations, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/3277203.3277323"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning, ICML 2018 (Stockholmsm\u00e4ssan","author":"Wang Y.","year":"2018","unstructured":"Wang, Y., Jha, S., Chaudhuri, K. Analyzing the robustness of nearest neighbors to adversarial examples. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018 (Stockholmsm\u00e4ssan, Stockholm, Sweden, July 10-15, 2018), 5120--5129."},{"key":"e_1_2_1_23_1","volume-title":"International Conference on Machine Learning","author":"Xiao H.","year":"2015","unstructured":"Xiao, H., Biggio, B., Brown, G., Fumera, G., Eckert, C., Roli, F. Is feature selection secure against training data poisoning? In International Conference on Machine Learning, 2015, 1689--1698."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2014.08.081"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 20th European Conference on Artificial Intelligence, ECAI'12","author":"Xiao H.","year":"2012","unstructured":"Xiao, H., Xiao, H., Eckert, C. Adversarial label flips attack on support vector machines. In Proceedings of the 20th European Conference on Artificial Intelligence, ECAI'12 (Amsterdam, The Netherlands, 2012), IOS Press, 870--875."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3576894","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3576894","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3576894","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:47Z","timestamp":1750178207000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3576894"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,20]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["10.1145\/3576894"],"URL":"https:\/\/doi.org\/10.1145\/3576894","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"type":"print","value":"0001-0782"},{"type":"electronic","value":"1557-7317"}],"subject":[],"published":{"date-parts":[[2023,1,20]]},"assertion":[{"value":"2023-01-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}