Algorithmic Complexity Attacks on Dynamic Learned Indexes

学习索引结构（LIS）将排序索引视为学习数据分布的模型，将数据元素键作为输入，并输出键的预测位置。原始LIS只能处理查找操作，不支持更新操作，这使得它在典型工作负载中不实用。为了解决这个限制，最近的研究集中在设计高效的动态学习索引上。作为开创性的动态学习索引结构，ALEX通过整合一系列设计选择（包括自适应键空间分区、动态模型重新训练以及优先考虑读写性能的复杂工程和策略）实现了动态性。虽然这些设计选择提供了改进的平均性能，但是对灵活性和性能的强调增加了攻击面，使得对抗行为可以在最坏情况下最大化ALEX的内存空间和时间复杂度。在这项工作中，我们提出了针对ALEX最坏情况下算法复杂度攻击（ACAs）的第一个系统性调查。我们介绍了两类新的ACAs，即空间ACA和时间ACA，分别针对内存空间和时间复杂度。首先，我们的数据节点空间ACA利用ALEX的间隙数组布局，并使用多重选择背包（MCK）生成最优的对抗性插入计划，以最大化数据节点级别的内存消耗。其次，我们的内部节点空间ACA利用ALEX的灾难性成本缓解机制，只需进行几百次对抗性插入即可导致内存不足错误。第三，我们的时间ACA生成病态插入，增加实际键分布与数据节点线性模型之间的差异，使运行时性能恶化了高达1641倍，与在合法工作负载下运行的ALEX相比。

本论文旨在解决学习索引结构（LIS）在更新操作上的限制，提出了一种名为ALEX的动态学习索引结构，并探究了其可能面临的算法复杂度攻击（ACAs）问题。

ALEX采用自适应键空间划分、动态模型重训练和优化的读写性能等设计选择，实现了动态更新操作。而针对其可能面临的ACAs问题，本文提出了两种类型的攻击策略：空间ACA和时间ACA，分别针对内部节点和数据节点进行攻击，从而最大化其内存和时间复杂度。

本文实现了新的算法复杂度攻击，并通过实验验证了其对ALEX结构的影响。其中，空间ACA利用ALEX的间隔数组布局和多重选择背包问题生成最优的对抗插入计划，从而最大化数据节点的内存消耗；时间ACA则通过插入病态数据来增加实际键分布与数据节点的线性模型之间的差异，使运行时间性能降低多达1641倍。

相关研究包括对学习索引结构的改进和优化，以及对算法复杂度攻击的研究。例如，Bender等人提出了一种名为Bw-Tree的学习索引结构，能够支持高效的并发操作；而关于算法复杂度攻击方面，最近的研究主要集中在对哈希表的攻击上，如Wang等人提出的算法复杂度攻击方法。