Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper investigates the vulnerability of the PGM-index to poisoning attacks, specifically through a newly proposed method called PGM-attack that inserts adversarial keys to inflate segment counts. The authors demonstrate that even a modest 10% poisoning can lead to a dramatic increase in segment count by up to 120 times, revealing a significant flaw in the index's optimization strategy. Their theoretical upper bounds confirm that the attack achieves at least 52% of the optimal segment count, highlighting the need for more robust design in learned indexes.
Poisoning just 10% of keys can inflate the segment count of the PGM-index by up to 120x, exposing a critical vulnerability in its design.
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.