Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions
Authors: Atsuki Sato, Martin Aumüller, Yusuke Matsui
Organizations: Graduate School of Information Science and Technology, The University of Tokyo, Tokyo, Japan · Algorithms Group, IT University of Copenhagen, Copenhagen, Denmark
Learned indexes are a class of index data structures that enable fast search by approximating the cumulative distribution function (CDF) using machine learning models (Kraska et al., SIGMOD'18). However, recent studies have shown that learned indexes are vulnerable to poisoning attacks, where injecting a small number of poison keys into the training data can significantly degrade model accuracy and reduce index performance (Kornaropoulos et al., SIGMOD'22). In this work, we provide a rigorous theoretical analysis of poisoning attacks targeting linear regression models over CDFs, one of the most basic regression models and a core component in many learned indexes. Our main contributions are as follows: (i) We present a theoretical proof characterizing the optimal single-point poisoning attack and show that the existing method yields the optimal attack. (ii) We show that in multi-point attacks, the existing greedy approach is not always optimal, and we rigorously derive the key properties that an optimal attack should satisfy. (iii) We propose a method to compute an upper bound of the multi-point poisoning attack's impact and empirically demonstrate that the loss under the greedy approach is often close to this bound. Our study deepens the theoretical understanding of attack strategies against linear regression models on CDFs and provides a foundation for the theoretical evaluation of attacks and defenses on learned indexes.
Figures & tables
Original Setting ( Definition 2 )
Relaxed Setting ( Definition 2 )
Algorithm
Time Complexity
Empirical Performance (Ratio)
Time Complexity
Empirical Performance (Ratio)
Greedy ( Kornaropoulos et al., 2022 )
O(nλ)
≥0.933
-
-
Exact Seg+E (Ours)
O(nλ3)
1
O(nλ)
1
Heuristic Seg+E (Ours)
O(nλ)
≥0.998
-
-
Optimal (Ours)
O((n+λ)(λ2n−2+λ))
1
O((n+λ)(λn+λ−1))
1
Upper Bound (Ours)
O(T(n+λ)) or O((n+λ)log(n+λ))
≤1.092
O(T(n+λ)) or O((n+λ)log(n+λ))
≤1.087
Table 1. Overview over time complexity and empirical performance of poisoning attacks and upper-bounding methods under the original setting ( Kornaropoulos et al., 2022 ) (duplicate keys disallowed; Definition 2 ) and the relaxed setting (duplicate keys allowed; Definition 2 ). Here, n is the number of legitimate keys, λ is the poisoning budget, and T is the number of iterations in our upper-bounding methods. Empirical Performance (Ratio) is the achieved MSE (attacks) or the bound (upper bounds) normalized by the optimal-attack MSE over 3,000 cases in Section 6.6 (values closer to 1 indicate a better attack or a tighter upper bound).
Figure 1. Single-point poisoning attack on K={2,11,13,19,32,36,39} . By inserting a poison point, the rank of every key greater than the poison increases by one. The linear regression model is fitted on the poisoned key set, leading to a change in MSE.
Figure 2. Proof of Theorem 1 . Lemma 2 implies that either E(K∪{p∗−1}) or E(K∪{p∗+1}) is greater than E(K∪{p∗}) .
Figure 3. Multi-point poisoning attack. The greedy two-point attack ( Kornaropoulos et al., 2022 ) injects the poison point 12 first ( Figure 3(a) ), followed by the injection of the poison point 10 ( Figure 3(b) ). In contrast, the optimal attack is {37,38} , resulting in a higher MSE ( Figure 3(c) ).
Figure 4. Proof of Theorem 1 . Lemma 1 implies that E(K∪P−) or E(K∪P+) is greater than E(K∪P∗) .
Figure 5. Examples of the Segment + Endpoint (Seg+E) attack in original and relaxed settings.
Figure 6. MSEUB (our upper bound), MSEG (greedy attack), and MSEL (legitimate) for seed = 0. We set n=1,000 and R=100,000 . We observe that MSEUB≥MSEG in all cases and the gap is small, which indicates that our upper bound is tight and greedy attack is close to the optimal attack.
Figure 7. Boxplots of MSEG/MSEUB over 100 seeds for each dataset and poisoning percentage. We set n=1,000 and R=100,000 . The ratio never exceeds 1 and is always greater than 0.8 . In particular, for Exponential, Amzn, Face, and Osmc, the median ratio is ≥0.99 , which indicates that our upper bound is tight and greedy attack is close to the optimal attack.
Figure 8. Boxplots of MSEG/MSESeg+E over 100 seeds for each dataset and poisoning percentage. We set n=1,000 and R=100,000 . The ratio never exceeds 1, that is, the Seg+E attack is never worse than the greedy attack.
Figure 9. Boxplots of MSESeg+E(H)/MSESeg+E−1 over 100 seeds for each dataset and poisoning percentage (for better visibility, we plot the value obtained by subtracting 1 from the ratio). We set n=1,000 and R=100,000 . The ratio consistently remains very close to 1, indicating that our heuristic algorithm yields solutions nearly identical to those of the exact Seg+E algorithm.
Figure 10. Running time vs poisoning percentage. We set n=1,000 and R=100,000 . The running time of the greedy poisoning method grows linearly with the poisoning percentage (consistent with O((n+λ)λ) time complexity), whereas our upper-bound methods (Golden, Binary, Strict) are nearly flat (consistent with O(n+λ) or O((n+λ)log(n+λ)) time complexity).
Figure 11. Running time vs n . We set the poisoning percentage to 10% and R=100,000 . The running time of the greedy poisoning method grows quadratically with n (consistent with O((n+λ)λ) time complexity), whereas our upper-bound methods (Golden, Binary, Strict) grow linearly with n (consistent with O(n+λ) or O((n+λ)log(n+λ)) time complexity).
Figure 12. MSEG/MSEUB vs n . We set the poisoning percentage to 10% and R=100,000 . As n increases, MSEG/MSEUB shows a slight tendency to decrease.
Figure 13. MSEG/MSEUB vs R for synthetic data. We set the poisoning percentage to 10% and n=1,000 for all datasets. When R is quite small, the ratio tends to decrease.
Figure 14. Boxplots of the ratios ρG , ρR , and ρUB , defined in Equation 15 , over 100 seeds for each dataset and poisoning percentage. We set n=50 and R=1,000 . All ratios remain close to 1 (minimum 0.92 ), with MSEOPT/MSEROPT particularly tight.
Figure 15. The ratios ( ρG , ρR , and ρUB ) vs R for synthetic data. We set the poisoning percentage to 10% and n=50 . ρUB and ρG remain stable as R varies, whereas ρR stays close to 1 for large R but drops when R is small.
Figure 16. A counter example where the exact Seg+E solution is not globally optimal. The legitimate key set is K={0,1,…,16,48,49,…,64}∖{1,8,56,63} . The optimal solution is P={8,56} , but the exact Seg+E solution is P={1,8} .
Figure 17. Lookup time. The lookup time includes both regression inference and exponential search. We measure it 10 times for each key and report the average. We set n=1,000 and R=100,000 . Poisoning increases the lookup time by up to 1.6 times.
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 18. Proof of Theorem 3 . Lemma 1 implies that E(K∪P−) or E(K∪P+) is greater than E(K∪P∗) .
Figure 19. Empirical observations, conjectures, and counterexamples. All examples (especially those in the second and third columns) illustrate Observation 3 , showing that poisons tend to appear either near the endpoints or around the intersection between the regression line and the sequence of points formed by the legitimate keys. Columns 1–4 correspond to Seg+E configurations that satisfy Observation 4 , whereas columns 5–7 show artificially constructed corner cases that violate Observation 4 . In all examples, the optimal poisons in the relaxed setting are Seg+E, supporting Conjecture 1 .
Continual learning (CL), where a model is trained on a sequence of data tasks, is increasingly being adopted across key fields such as large language models and image recognition, yet it remains highly vulnerable to data poisoning that triggers learning divergence or severe excess risk. Despite these threats, a principled theoretical foundation in CL for understanding attack and defense remains lacking. In this paper, we develop a theoretical framework to analyze strategic attacks and defenses in regularization-based CL, a cornerstone of recent CL theory. By framing the adversary-defender interaction as an online zero-sum game, we first establish a fundamental performance limit: no defense succeeds when an adversary poisons a linear proportion of tasks by injecting unbounded noise or pattern shifts in regularization-based CL. We then analyze two possibly defensible scenarios: infrequent attacks and bounded noise per attack. For the former regime, we propose a task-to-task verification mechanism to detect data poisoning and reduce cumulative bias for learning convergence. For the latter regime, we derive a robust defense that minimizes the model's sensitivity to poisoned features, provably accelerating the convergence rate. Extensive experiments on realistic tasks further validate our theoretical results.
Yiting Hu, Lingjie Duan
Singapore University of Technology and Design, Singapore · The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China.
This paper studies active regression for single-index models under general ℓp-loss with an unknown 1-Lipschitz link function f, formulated as minf,x∥f(Ax)−b∥pp with full access to A but coordinate-query access to b. Prior work established upper bounds for known link functions for all p≥1 and for unknown link functions only in the p=2 case, together with lower bounds for p≤2. This work addresses the more challenging setting of unknown link functions and general p≥1. A non-adaptive sampling algorithm is presented that achieves a (1+ε)-approximation using O(dp/2∨1/εp∨2polylog(n/ε)) queries. Nearly tight lower bounds are also established for p>2. These results close much of the remaining gap in active ℓp-regression for single-index models.
Chansophea Wathanak In, Yi Li, Wai Ming Tai +1
School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore · Independent Researcher · John Hopcroft Center for Computer Science, Shanghai Jiao Tong University, China
Targeted data poisoning attacks manipulate model predictions on specific test samples by injecting malicious data into training. Yet existing evaluations report average attack success rates over randomly selected targets, obscuring true worst-case effectiveness. We argue that the right evaluation focuses on the hardest samples to poison. The same reasoning applies to defense: since targeted attacks leave no footprint at the distribution level, defenders should proactively identify the most vulnerable samples and apply targeted countermeasures. Given a test dataset, this paper identifies both the easiest and hardest to poison examples based on only clean model information. Specifically, we offer coarse evaluations using clean training dynamics, and fine-grained classification on poison class using poison distances and budgets. Our experiments show these metrics reliably stratify samples by poisoning vulnerability, enabling both rigorous worst-case evaluation and proactive vulnerability-aware defense.
William Xu, Chenyu Zhang, Yihan Wang +5
Waabi AI · University of Waterloo · Carnegie Mellon University +3