2025/07/10 by Yingze Li, Xianglong Liu, Li, Yingze +11
Computer Science · #Adversarial Robustness in Machine Learning #Data Stream Mining Techniques #Databases (cs.DB) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.2507.07438
openalex publication_date 2025/07/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Learned cardinality estimators show promise in query cardinality prediction, yet they universally exhibit fragility to training data drifts, posing risks for real-world deployment. This work is the first to theoretical investigate how minimal data-level drifts can maximally degrade the accuracy of learned estimators. We propose data-centric algorithmic complexity attacks against learned estimators in a black-box setting, proving that finding the optimal attack strategy is NP-Hard. To address this, we design a polynomial-time approximation algorithm with a (1-κ) approximation ratio. Extensive experiments demonstrate our attack's effectiveness: on STATS-CEB and IMDB-JOB benchmarks, modifying just 0.8% of training tuples increases the 90th percentile Qerror by three orders of magnitude and raises end-to-end processing time by up to 20×. Our work not only reveals critical vulnerabilities in deployed learned estimators but also provides the first unified worst-case theoretical analysis of their fragility under data updates. Additionally, we identify two countermeasures to mitigate such black-box attacks, offering insights for developing robust learned database optimizers.