PaperlayerView exact revision on arXiv

Source-linked AI summary

Poisoning Attacks on the PGM-index

Atsuki Sato, Martin Aumüller, Yusuke Matsui

arXiv:2609.02328v1cs.DBcs.CRcs.LG

TL;DR

The paper asks whether the PGM-index’s segment-minimizing PLA is vulnerable to poisoning. It develops PGM-attack and upper bounds for arbitrary insertions, finding large segment and index-size increases from small poison sets and motivating robustness-aware objectives.

  • Problem

    The paper examines the largely uncharacterized robustness of the PGM-index and its optimal PLA against poisoning and unfavorable data insertions.

  • Method

    PGM-attack sequentially solves poisoning subproblems to maximize PLA segments, while companion algorithms upper-bound segments attainable under arbitrary insertions.

  • Results

    10% poison keys increase PGM-index segment count and size by up to 120×, while the attack also substantially inflates PLA-based learned indexes.

  • Takeaways & Limitations

    Optimal segment minimization does not guarantee robustness to adversarial insertions, motivating robustness-aware learned-index objectives.

  • Takeaways & Limitations

    The greedy repetition of optimal single-point attacks is not necessarily globally optimal, and adjacent-solution theorems assert existence rather than universal adjacency.

Abstract

from arXiv · show

The PGM-index (Ferragina and Vinciguerra, VLDB'20) is one of the most practical learned indexes, owing to its theoretical elegance and consistently strong empirical performance. It is built on optimal piecewise linear approximations (PLAs) that minimize the number of segments. In this paper, we ask how sensitive this optimal PLA itself is to poisoning attacks. We propose PGM-attack, an efficient poisoning attack that sequentially inserts adversarial keys to inflate the resulting number of segments, and we develop a method for deriving theoretical upper bounds on the number of segments attainable under arbitrary insertions. Our experiments show that poisoning only 10% of the keys allows PGM-attack to increase the segment count by up to 120x. On every evaluated instance, our instance-dependent upper bound is at most 1.92x the segment count attained by PGM-attack, certifying that PGM-attack achieves at least 52% of the optimum. This increase in the number of segments enlarges the PGM-index by up to 120x. Moreover, the attack also transfers to other learned indexes, substantially inflating the index size of PLA-based ones in particular. Our results reveal that, despite the optimality of its PLAs, the PGM-index has an intrinsic vulnerability rooted in its optimization objective, motivating robustness-aware objective design for future learned indexes. Our code is publicly available at https://github.com/atsukisato/pgm-attack.

1 INTRODUCTION

The paper studies how poisoning attacks exploit the PGM-index’s optimal PLA construction, which minimizes segments but may be sensitive to data insertions. It introduces PGM-attack, theoretical segment-count bounds, and experiments showing substantial degradation from small poison sets.

  • The PGM-index recursively builds optimal PLAs of the CDF, minimizing segments to balance memory usage and query time.
  • Small data insertions can have unclear effects on learned-index performance because those effects depend sensitively on the data distribution.
  • PGM-index robustness to poisoning remains largely uncharacterized despite its theoretical guarantees, threatening its practical performance advantage over B+-trees.
  • PGM-attack repeatedly solves poisoning subproblems to maximize the number of segments in the optimal PLA.
  • 10% poison keys increase the segment count and PGM-index size by up to 120×, while the attack also substantially inflates PLA-based learned indexes.
  • An instance-dependent upper bound is at most 1.92× PGM-attack’s segment count, certifying that the attack reaches at least 52% of the optimum on evaluated instances.

2 PRELIMINARIES

This section defines learned indexes and PLAs, then identifies the bottom-level optimal PLA as the PGM-index component targeted by the threat model. The attacker is assumed to know the legitimate keys and relevant error parameter before construction.

  • Learned indexes predict a key’s rank from the dataset’s cumulative distribution function and verify the prediction to obtain the exact answer.
  • 2.1 PLA Algorithm: A PLA approximates the rank function with linear segments, extending each segment while its maximum error remains within ε.
  • 2.1 PLA Algorithm: The PGM-index uses an optimal PLA that minimizes the number of segments, whereas faster PLA variants may produce near-optimal approximations.
  • 2.2 PGM-index: The bottom-level optimal PLA dominates PGM-index space and query-time complexity: O(m_opt) space and O(log m_opt + log ε) query time.
  • 2.3 Threat Model: The threat model gives the attacker white-box knowledge of all legitimate keys and ε, permits pre-construction insertions, and restricts poison keys to the legitimate-key range.

3 MAXIMUM-ERROR MAXIMIZATION

The section defines maximum-error linear regression on CDFs and studies how inserted poison keys can maximize that error. Structural results restrict optimal attacks to poison keys adjacent to legitimate keys, substantially reducing the search space and motivating several attack methods.

  • Problem Setting: Maximum-error regression minimizes the largest rank-prediction error, unlike prior MSE-based regression, and lacks a simple closed-form solution.The error can nevertheless be computed in O(N) time via Megiddo’s algorithm.
  • Problem Setting: The maximum-error attack chooses up to λ non-legitimate integers from the key range to maximize the regression’s maximum error.The PLA connection is direct: increasing maximum error beyond ε forces segments to end earlier.
  • Problem Setting: Poisoning inserts keys that shift the ranks of all subsequent keys, while restricted integer choices prevent reuse of legitimate or previously selected poison keys.These global interactions make optimal poison selection non-trivial.
  • Structure of Optimal Attacks: An optimal attack exists in which every poison key is adjacent to a legitimate key, directly or through a chain of adjacent poison keys.The proof shifts isolated poison blocks without decreasing maximum error until no isolated blocks remain.
  • Structure of Optimal Attacks: The adjacency theorem reduces candidate enumeration from dependence on the key-universe size to dependence on n, with at most 2n−3+λ candidates.For a single poison, checking adjacent integers yields an O(n^2) algorithm.
  • Methods for Obtaining Poison Solutions: Greedily repeating optimal single-point attacks is not guaranteed to find a globally optimal multi-point attack.In the illustrated example, {33, 34} is optimal for two points although neither singleton is an optimal one-point attack.

4 COVERED-LEGITIMATE-KEYS MINIMIZATION

This section reformulates poisoning as minimizing the legitimate keys covered by a feasible regression segment. A theorem reduces this problem to maximum-error attacks on prefixes, enabling efficient consecutive and discrete-intercept methods whose repeated application increases PLA segmentation.

  • Problem Setting: Given an error bound ε, CDF linear regression seeks to cover as many keys as possible while keeping maximum error at most ε.The PGM-index repeatedly applies this segment-extension procedure to construct a PLA with as few segments as possible.
  • Problem Setting: The covered-legitimate-keys minimization problem chooses up to λ poison keys to minimize the legitimate keys covered by a feasible segment.The model counts all keys, but the attacker measures only legitimate-key coverage.
  • Connection to the PGM-index: Repeatedly minimizing legitimate-key coverage increases the number of segments in the resulting PGM-index.The attack targets effective segment coverage rather than the model’s total covered-key count.
  • Reduction to Maximum-Error Maximization: Theorem 4 reduces covered-legitimate-keys minimization to maximum-error maximization over prefixes of the legitimate-key sequence.An optimal maximum-error poison set for the prefix of size C*+1 is also optimal for the coverage objective.
  • Methods for Obtaining Poison Solutions: Consecutive enumerates boundary-adjacent consecutive poison sets in O(c(c+λ)) time, while DI-Consecutive reduces the cost to O(c log c) after precomputation.DI-Consecutive uses candidate intercepts and precomputed feasible slope intervals to evaluate candidates efficiently.

5 POISONING TO MAXIMIZE 𝑚opt

This section formulates poisoning as maximizing the minimum segment count of an optimal PLA and develops PGM-attack plus upper bounds for that objective.

  • PGM-attack repeatedly minimizes the legitimate keys covered by one segment, thereby increasing the number of segments in the optimal PLA.
  • The segment maximization problem seeks a poison set, under a budget, that maximizes the optimal PLA’s segment count.
  • The problem is non-local because early poison placement shifts subsequent ranks and changes later segment boundaries and sizes.
  • PGM-attack fixes segments from left to right and evaluates candidate poison allocations using a cost balancing covered legitimate keys against poison consumption.
  • The adaptive penalty coefficient θ increases when poison consumption outpaces progress through legitimate keys and decreases in the opposite case.
  • An instance-agnostic upper bound is tight for some instances, while an efficiently computable instance-dependent bound exploits block structure and poison-budget allocation.

6 EXPERIMENTS

Experiments show that the proposed attacks strongly increase PLA errors, segment counts, and learned-index sizes, while DI-Consecutive preserves effectiveness with much lower generation time.

  • Maximum-Error Maximization: Consecutive attains the maximum-error optimum in 8,994 of 9,000 cases and remains within 0.87 in the other six.
  • Maximum-Error Maximization: Consecutive is at least as effective as Greedy in all 9,000 cases and runs with lower asymptotic time complexity.
  • Covered-Legitimate-Keys Minimization: Consecutive and DI-Consecutive substantially reduce covered legitimate keys, whereas Random has little effect and Random-Adjacent achieves only a modest reduction.
  • Covered-Legitimate-Keys Minimization: DI-Consecutive achieves nearly the same covered-key reduction as Consecutive while exceeding 1,000× speedup in the largest cases.
  • PLA Segment Maximization: 10% poisoning increases m_opt by up to 120×, while the instance-dependent upper bound is at most 1.92× PGM-attack’s achieved segment count.
  • PLA Segment Maximization: Larger ε generally produces larger poisoning increases, reflecting a trade-off between stronger compression and greater poisoning sensitivity.
  • Index Performance: PGM-attack enlarges PGM-index size by up to 120× and lookup time by up to 1.22×, exceeding the effects of random poisoning.
  • Index Performance: The attack transfers to PLA-based indexes, increasing size by 1.25–18.5× for FITing-Tree and 1.13–35,770× for PGM++.

7 RELATED WORK

Related work covers learned indexes, PLA-based designs, adversarial attacks on learned structures, and prior robustness studies that differ from this paper’s poisoning setting.

  • Learned indexes approximate data CDFs with machine-learned regression models to improve memory efficiency or query throughput.
  • PLA-based learned indexes emphasize explicit error control and high compressibility, with examples including FITing-Tree and RadixSpline.
  • Prior attacks target learned Bloom filters, sketches, cardinality estimators, index advisors, linear CDF models, RMIs, and ALEX.
  • Unlike this paper’s pre-construction poisoning, ALEX algorithmic-complexity attacks exploit weaknesses in online insertion algorithms.

8 DISCUSSION

The discussion shows that PGM-attack exposes robustness weaknesses in optimal PLA-based indexes, while also highlighting transferability, parameter-mismatch effectiveness, and limitations of current bounds and attack strategies.

  • Designing robust learned indexes: Worst-case performance guarantees alone are insufficient for robustness, motivating learned-index objectives that remain resilient to unfavorable insertions.The paper suggests relaxing maximum-error constraints, using flexible models, or separating suspicious keys.
  • Effective poisoning keys are difficult to distinguish from legitimate ones because optimal poison sets can consist of consecutive blocks adjacent to legitimate keys.This problem-specific structure prevents direct application of classical robust regression techniques.
  • Improving poisoning attacks and upper bounds: The Instance UB can be up to 1.92× the segment count achieved by PGM-attack because of attack greediness and looseness in the bound.Dynamic programming could improve both components, but naive implementations require quadratic time.
  • Transferability of PGM-attack: PGM-attack transfers across diverse learned indexes because it targets PLA structure rather than an implementation-specific PGM property.The generated keys induce hard-to-approximate local regions, inflating model counts or auxiliary structures.
  • Attacks without knowledge of the PLA parameter: PGM-attack remains substantially effective when the attacker uses an error parameter different from the PLA's true parameter.Its effectiveness is highest when the assumed and true parameters match.
  • Beyond a security threat model: The attack can also serve as worst-case analysis and stress testing for data insertions, exposing performance failure modes in PLA-based indexes.The identified inputs sharply increase segment count, index size, and query time.

9 CONCLUSION

The paper concludes that optimal PLA construction is vulnerable to adversarial insertions and develops a sequence of theoretical arguments characterizing optimal poison placement. Its results show that poison mass can be concentrated on legitimate keys and ultimately on one key value.

  • 9 CONCLUSION: The paper presents the first systematic study of poisoning attacks against optimal PLA construction, combining theoretical results with practical algorithms.It studies maximum regression error, legitimate-key coverage, and segment maximization.
  • Proof of Lemma 1: A feasible regression region is a convex polygon after transforming parameters by (u, v) = (1/w, b/w).The transformation is bijective because the optimal slope is strictly positive.
  • Proof of Lemma 1: Shifting a block within a rank-preserving interval translates its feasible region along the transformed v-axis without changing the underlying feasibility structure.The shifted block's region is the original block's region shifted by −δ.
  • Proof of Lemma 1: Convexity of the Minkowski difference implies that if both extreme shifts are feasible, the unshifted block is feasible as well.This establishes the error bound for the unshifted dataset.
  • Proof of Theorem 2: An optimal poison set uses the full budget, has support on legitimate keys, and can be concentrated on a single legitimate key.These properties follow from adding a poison, shifting unsupported blocks, and merging poison mass between support values.
  • Proof of Theorem 2: Poison mass distributed across multiple key values can be merged onto one endpoint without decreasing maximum error.Repeated merging yields an optimal solution supported on one integer in K.

A.5 Proof of Theorem 6

Theorem 6 gives a constructive instance attaining the stated upper-bound form, while DI-Consecutive efficiently evaluates consecutive poison candidates using slope-range computations and sparse tables.

  • A.5 Proof of Theorem 6: The construction places legitimate-key blocks with gaps and inserts one poison at the center of each gap.The legitimate set and poison set are defined using block size b and spacing B.
  • A.5 Proof of Theorem 6: Before poisoning, the constructed example has m_opt(K, ε) = 3; after poisoning, it has m_opt(K ∪ P, ε) = 5.The example uses λ = 2 and ε = 0.
  • A.5 Proof of Theorem 6: The unpoisoned construction has m_opt(K, ε) = λ + 1 because each block requires one segment and no segment can cover two blocks.The choices of b and B ensure this separation.
  • A.5 Proof of Theorem 6: After poisoning, the construction attains m_opt(K ∪ P, ε) = 2λ + 1 through alternating segments covering poisoned points and portions of adjacent blocks.Greedy left-to-right segmentation verifies the equality.
  • B DETAILS ON DI-CONSECUTIVE: DI-Consecutive reduces candidate evaluation from O(c) to O(|I| log c) by combining intercept enumeration, binary search, and constant-time feasibility checks.Sparse tables provide the required range queries for slope intervals.

B.2 Evaluation

The evaluation procedure computes how many legitimate keys a consecutive poison set can coexist with, then derives an instance-dependent upper bound by partitioning the key set into fixed-slope blocks and allocating poison budget across them.

  • B.2 Evaluation: For each candidate poison set and intercept, maximal coverage is found by binary-searching the largest feasible prefix of legitimate keys.The first legitimate key after the poisons is located using precomputed gap counts and prefix sums.
  • B.2 Evaluation: Coverability holds exactly when the pre-poison, post-poison, and poison-region slope ranges have a non-empty intersection.The pre- and post-poison ranges are obtained from sparse tables.
  • Instance-dependent upper bound: The instance-dependent upper-bound algorithm partitions K into blocks, computes per-block bounds, and allocates the poison budget to maximize their sum.It uses an αε-PLA, fixed slopes, independent blocks, and duplicate poisons in a relaxed problem.
  • B.2 Evaluation: The poison-region range can be obtained from the endpoints because linearity bounds every intermediate error when both endpoint errors are at most ε.This reduces evaluation of the consecutive poison interval to slope-range intersection.
  • Instance-dependent upper bound: Evaluating multiple α values and taking their minimum preserves the upper-bound guarantee.The implementation tests α ∈ {1.0, 1.2, 1.4, 1.6, 1.8, 2.0}.

C.2 Per-Block Upper Bound

The paper models poisoning-induced segmentation changes as a weighted DAG path problem and derives instance-dependent upper bounds under a poison budget. These bounds are computed efficiently across blocks and closely track PGM-attack’s observed segment increases.

  • Per-block formulation: Each DAG path represents a block segmentation, with path length equal to segments and total edge weight lower-bounding required poisons.Edges encode the minimum poisons needed to force segment boundaries.
  • Efficient computation: The edge-cost function has the Monge property, enabling linear-time shortest-path computation with LARSCH.Subtracting the same constant preserves this property.
  • Per-block formulation: The per-block bound follows from shortest-path distances after subtracting a common value from every DAG edge weight.The resulting quantity upper-bounds the number of segments attainable within the block.
  • Global allocation: Global bounds allocate the total poison budget across blocks by repeatedly assigning poisons to the block with the largest current marginal gain.Concavity of each per-block bound makes this allocation optimal.
  • Experimental validation: 10% poisoning increases m_opt by 1.46×–24.5× beyond YCSB, where the increase reaches 120×, while random baselines reach only 1.00×–1.30×.The instance-dependent upper bound is at most 1.92× attained m_opt, certifying at least 52% of optimum.
  • Robustness and practicality: PGM-attack remains effective under parameter mismatch and transfers to other learned indexes, while poison generation takes 0.6–14.7 hours.The offline setting makes this generation cost practical for an attacker.

D.2 Additional Results on Index Performance

Additional evaluations show that PGM-attack enlarges index structures across PLA-based and other learned indexes, with smaller original indexes often suffering the largest multiplicative increases. Query-time degradation is smaller than size growth but remains measurable and broadly transferable.

  • Evaluation setup: Figures 19 and 20 compare index size and query time before and after 10% poisoning with ε=128, reporting ratios relative to original indexes.The evaluations cover multiple datasets, indexes, and poisoning methods.
  • PLA-based indexes: PGM-attack is effective against all four other PLA-based indexes, especially when the original index is small and highly dependent on regular key distributions.Poisoning creates local regions that require many linear segments.
  • PLA-based indexes: On YCSB, index size increases by up to 18.5× for FITing-Tree, 3.03× for RadixSpline, 37.5× for PLEX, and 35,770× for PGM++.The PGM++ ratio partly reflects its extremely small original index size on YCSB.
  • Query performance: Across learned indexes, PGM-attack generally causes the largest query-time degradation, reaching up to 1.30×, likely through cache misses and traversal overhead.Its effects remain broader than those of attacks designed for specific architectures.
  • Other learned indexes: ALEX index size increases by 98.6× on YCSB and 129× on Uniform, indicating transfer beyond PLA-based indexes.The poison keys likely increase prediction errors in ALEX’s linear navigation models.
  • Comparisons with prior attacks: On RMI, PGM-attack increases query time by up to 1.40×, compared with at most 1.04× for RMI-attack.The passage attributes this difference partly to squared error being imperfectly aligned with last-mile search cost.

E.3 Experimental Evaluation

With duplicate keys allowed, PGM-attack still substantially increases the optimal PLA segment count, while random insertions have little effect. The amplification grows with both poisoning rate and ε.

  • Datasets and methods: The duplicate-allowed evaluation uses three real-world datasets containing duplicates and one synthetic duplicate-containing dataset.The datasets include Wiki, Weblogs, IoT, and a synthetic benchmark.
  • Datasets and methods: In this setting, Random samples uniformly from the key range, whereas Random-Adj. samples legitimate keys uniformly with replacement.These policies differ from the duplicate-forbidden baselines.
  • Results: PGM-attack increases m_opt by up to 4.68× at 1% poisoning and up to 36.1× at 10% poisoning in the duplicate-allowed setting.These increases are measured relative to the legitimate-key baseline.
  • Results: Random and Random-Adj. increase m_opt by at most 1.24× and 1.30×, respectively, substantially less than PGM-attack.This comparison holds across every evaluated dataset.
  • Sensitivity to ε: At λ=0.1n, amplification rises from at most 8.01× for ε=16 to 36.1× for ε=128.The paper reports this increasing-ε trend for duplicate-allowed poisoning.
Loading 2609.02328v1…