{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T06:22:47Z","timestamp":1770963767449,"version":"3.50.1"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSF of China","doi-asserted-by":"crossref","award":["61925205, 62232009, 62102215"],"award-info":[{"award-number":["61925205, 62232009, 62102215"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"CCF-Huawei Populus Grove Challenge Fund","award":["CCF-HuaweiDBC202309"],"award-info":[{"award-number":["CCF-HuaweiDBC202309"]}]},{"name":"Science and Technology Research and Development Plan of China Railway","award":["K2022S005"],"award-info":[{"award-number":["K2022S005"]}]},{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["2023YFB4503600"],"award-info":[{"award-number":["2023YFB4503600"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>Cardinality estimation (CE) plays a crucial role in database optimizer. We have witnessed the emergence of numerous learned CE models recently which can outperform traditional methods such as histograms and samplings. However, learned models also bring many security risks. For example, a query-driven learned CE model learns a query-to-cardinality mapping based on the historical workload. Such a learned model could be attacked by poisoning queries, which are crafted by malicious attackers and woven into the historical workload, leading to performance degradation of CE.<\/jats:p>\n          <jats:p>In this paper, we explore the potential security risks in learned CE and study a new problem of poisoning attacks on learned CE in a black-box setting. There are three challenges. First, the interior details of the CE model are hidden in the black-box setting, making it difficult to attack the model. Second, the attacked CE model's parameters will be updated with the poisoning queries, i.e., a variable varying with the optimization variable, so the problem cannot be modeled as a univariate optimization problem and thus is hard to solve by an efficient algorithm. Third, to make an imperceptible attack, it requires to generate poisoning queries that follow a similar distribution to historical workload. We propose a poisoning attack system, PACE, to address these challenges. To tackle the first challenge, we propose a method of speculating and training a surrogate model, which transforms the black-box attack into a near-white-box attack. To address the second challenge, we model the poisoning problem as a bivariate optimization problem, and design an effective and efficient algorithm to solve it. To overcome the third challenge, we propose an adversarial approach to train a poisoning query generator alongside an anomaly detector, ensuring that the poisoning queries follow similar distribution to historical workload. Experiments show that PACE reduces the accuracy of the learned CE models by 178\u00d7, leading to a 10\u00d7 decrease in the end-to-end performance of the target database.<\/jats:p>","DOI":"10.1145\/3639292","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-27","source":"Crossref","is-referenced-by-count":9,"title":["PACE: Poisoning Attacks on Learned Cardinality Estimation"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-6114-9429","authenticated-orcid":false,"given":"Jintao","family":"Zhang","sequence":"first","affiliation":[{"name":"Tsinghua University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8924-7629","authenticated-orcid":false,"given":"Chao","family":"Zhang","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1398-0621","authenticated-orcid":false,"given":"Guoliang","family":"Li","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8080-5594","authenticated-orcid":false,"given":"Chengliang","family":"Chai","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"1","article-title":"Variational autoencoder based anomaly detection using reconstruction probability","volume":"2","author":"An Jinwon","year":"2015","unstructured":"Jinwon An and Sungzoon Cho. 2015. Variational autoencoder based anomaly detection using reconstruction probability. Special Lecture on IE, Vol. 2, 1 (2015), 1--18.","journal-title":"Special Lecture on IE"},{"key":"e_1_2_1_2_1","volume-title":"Minimization of functions having Lipschitz continuous first partial derivatives. Pacific Journal of mathematics","author":"Armijo Larry","year":"1966","unstructured":"Larry Armijo. 1966. Minimization of functions having Lipschitz continuous first partial derivatives. Pacific Journal of mathematics, Vol. 16, 1 (1966), 1--3."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-010-5188-5"},{"key":"e_1_2_1_4_1","volume-title":"Mathematical statistics: basic ideas and selected topics, volumes I-II package","author":"Bickel Peter J","unstructured":"Peter J Bickel and Kjell A Doksum. 2015. Mathematical statistics: basic ideas and selected topics, volumes I-II package. Chapman and Hall\/CRC."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/3042573.3042761"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3329772.3329780"},{"key":"e_1_2_1_7_1","unstructured":"GaussDB. 2021. GaussDB is a cloud-based distributed relational database. https:\/\/www.huaweicloud.com\/intl\/en-us\/product\/gaussdb.html"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3422622"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3412174"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-59497-3_175"},{"key":"e_1_2_1_11_1","unstructured":"Yue Han Chengliang Chai Jiabin Liu Guoliang Li Chuangxian Wei and Chaoqun Zhan. 2022. Dynamic materialized view management using graph neural network. (2022)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00217"},{"key":"e_1_2_1_13_1","volume-title":"Kai Zeng, Gao Cong, Yanzhao Qin, Andreas Pfadler, Zhengping Qian, Jingren Zhou, Jiangneng Li, and Bin Cui.","author":"Han Yuxing","year":"2021","unstructured":"Yuxing Han, Ziniu Wu, Peizhi Wu, Rong Zhu, Jingyi Yang, Liang Wei Tan, Kai Zeng, Gao Cong, Yanzhao Qin, Andreas Pfadler, Zhengping Qian, Jingren Zhou, Jiangneng Li, and Bin Cui. 2021b. Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation. CoRR, Vol. abs\/2109.05877 (2021)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR42600.2020.01394"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384349"},{"key":"e_1_2_1_16_1","volume-title":"ACR-Tree: Constructing R-Trees Using Deep Reinforcement Learning. In International Conference on Database Systems for Advanced Applications. Springer, 80--96","author":"Huang Shuai","year":"2023","unstructured":"Shuai Huang, Yong Wang, and Guoliang Li. 2023. ACR-Tree: Constructing R-Trees Using Deep Reinforcement Learning. In International Conference on Database Systems for Advanced Applications. Springer, 80--96."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526154"},{"key":"e_1_2_1_18_1","volume-title":"Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980","author":"Kingma Diederik P","year":"2014","unstructured":"Diederik P Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014)."},{"key":"e_1_2_1_19_1","volume-title":"Learned Cardinalities: Estimating Correlated Joins with Deep Learning. In CIDR","author":"Kipf Andreas","year":"2019","unstructured":"Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter A. Boncz, and Alfons Kemper. 2019. Learned Cardinalities: Estimating Correlated Joins with Deep Learning. In CIDR 2019."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517867"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588713"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526179"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554893"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3522565"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00297"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457542"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476380"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3386126"},{"key":"e_1_2_1_30_1","volume-title":"Foundations of statistical natural language processing","author":"Manning Christopher","unstructured":"Christopher Manning and Hinrich Schutze. 1999. Foundations of statistical natural language processing. MIT press."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2886521.2886721"},{"key":"e_1_2_1_32_1","volume-title":"Conditional generative adversarial nets. arXiv preprint arXiv:1411.1784","author":"Mirza Mehdi","year":"2014","unstructured":"Mehdi Mirza and Simon Osindero. 2014. Conditional generative adversarial nets. arXiv preprint arXiv:1411.1784 (2014)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687738"},{"key":"e_1_2_1_34_1","first-page":"9","article-title":"Exploiting machine learning to subvert your spam filter","volume":"8","author":"Nelson Blaine","year":"2008","unstructured":"Blaine Nelson, Marco Barreno, Fuching Jack Chi, Anthony D Joseph, Benjamin IP Rubinstein, Udam Saini, Charles Sutton, J Doug Tygar, and Kai Xia. 2008. Exploiting machine learning to subvert your spam filter. LEET, Vol. 8, 1 (2008), 9.","journal-title":"LEET"},{"key":"e_1_2_1_35_1","volume-title":"snowmobile, and boat registrations. catalog.data.gov\/dataset\/vehicle-snowmobile-and-boat-registrations, [Online","author":"State of New York. 2020. Vehicle","year":"2020","unstructured":"State of New York. 2020. Vehicle, snowmobile, and boat registrations. catalog.data.gov\/dataset\/vehicle-snowmobile-and-boat-registrations, [Online; accessed November 12, 2020]."},{"key":"e_1_2_1_36_1","volume-title":"An empirical analysis of deep learning for cardinality estimation. arXiv preprint arXiv:1905.06425","author":"Ortiz Jennifer","year":"2019","unstructured":"Jennifer Ortiz, Magdalena Balazinska, Johannes Gehrke, and S Sathiya Keerthi. 2019. An empirical analysis of deep learning for cardinality estimation. arXiv preprint arXiv:1905.06425 (2019)."},{"key":"e_1_2_1_37_1","volume-title":"An overview of gradient descent optimization algorithms. arXiv preprint arXiv:1609.04747","author":"Ruder Sebastian","year":"2016","unstructured":"Sebastian Ruder. 2016. An overview of gradient descent optimization algorithms. arXiv preprint arXiv:1609.04747 (2016)."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3555041.3589677"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physd.2019.132306"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3485450.3485459"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594528"},{"key":"e_1_2_1_42_1","unstructured":"TPC. 2021. Tpch benchmark. http:\/\/www.tpc.org."},{"key":"e_1_2_1_43_1","volume-title":"Principles of risk minimization for learning theory. Advances in neural information processing systems","author":"Vapnik Vladimir","year":"1991","unstructured":"Vladimir Vapnik. 1991. Principles of risk minimization for learning theory. Advances in neural information processing systems, Vol. 4 (1991)."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3485450.3485458"},{"key":"e_1_2_1_45_1","volume-title":"Cardinality estimation using normalizing flow. The VLDB Journal","author":"Wang Jiayi","year":"2023","unstructured":"Jiayi Wang, Chengliang Chai, Jiabin Liu, and Guoliang Li. 2023. Cardinality estimation using normalizing flow. The VLDB Journal (2023), 1--26."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461552"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3291264.3291267"},{"key":"e_1_2_1_48_1","volume-title":"BayesCard: Revitilizing Bayesian Frameworks for Cardinality Estimation. arXiv preprint arXiv:2012.14743","author":"Wu Ziniu","year":"2020","unstructured":"Ziniu Wu, Amir Shaikhha, Rong Zhu, Kai Zeng, Yuxing Han, and Jingren Zhou. 2020. BayesCard: Revitilizing Bayesian Frameworks for Cardinality Estimation. arXiv preprint arXiv:2012.14743 (2020)."},{"key":"e_1_2_1_49_1","volume-title":"ECAI","author":"Xiao Han","year":"2012","unstructured":"Han Xiao, Huang Xiao, and Claudia Eckert. 2012. Adversarial label flips attack on support vector machines. In ECAI 2012. IOS Press, 870--875."},{"key":"e_1_2_1_50_1","volume-title":"Generative poisoning attack method against neural networks. arXiv preprint arXiv:1703.01340","author":"Yang Chaofei","year":"2017","unstructured":"Chaofei Yang, Qing Wu, Hai Li, and Yiran Chen. 2017. Generative poisoning attack method against neural networks. arXiv preprint arXiv:1703.01340 (2017)."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421432"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368294"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565838.3565846"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3400903.3400921"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-019-07279-6"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-11404-6_2"},{"key":"e_1_2_1_57_1","volume-title":"AutoCE: An Accurate and Efficient Model Advisor for Learned Cardinality Estimation. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 2621--2633","author":"Zhang Jintao","year":"2023","unstructured":"Jintao Zhang, Chao Zhang, Guoliang Li, and Chengliang Chai. 2023. AutoCE: An Accurate and Efficient Model Advisor for Learned Cardinality Estimation. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 2621--2633."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/CISS.2017.7926118"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/3485450.3485456"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588948"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639292","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639292","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:17:27Z","timestamp":1755789447000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639292"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":60,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639292"],"URL":"https:\/\/doi.org\/10.1145\/3639292","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}