.png){kind=icon}
返回
Algorithmic Complexity Attacks on Dynamic Learned Indexes
.png){kind=icon}
OA
AI
DOI：10.14778/3636218.3636232.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
学习型索引结构（LIS）将有序索引视为一个学习数据分布的模型，以数据元素键作为输入，并输出键的预测位置。原始的LIS只能处理查找操作而不支持更新操作，使其难以适用于典型工作负载。为解决此限制，近期研究聚焦于设计高效的动态学习型索引。ALEX作为首个且代表性的动态学习型索引结构，通过一系列设计选择实现了动态性，包括自适应键空间分区、动态模型再训练以及优先考虑读写性能的复杂工程与策略。尽管这些设计选择提高了平均性能，但对灵活性和性能的强调增加了攻击面，允许恶意行为在极端情况下最大化ALEX的内存空间和时间复杂度。
在本工作中，我们首次系统性地研究了针对ALEX极端情况的算法复杂性攻击（ACAs）。我们引入了两种类型的全新ACAs：空间ACAs和时间ACAs，分别针对内存空间和时间复杂度。首先，我们针对数据节点的空间ACA利用了ALEX的间隔数组布局，使用Multiple-Choice Knapsack（MCK）生成最优的恶意插入计划，以最大化数据节点级别的内存消耗。其次，我们针对内部节点的空间ACA利用了ALEX的灾难性成本缓解机制，仅需数百次恶意插入即可导致内存不足（OOM）错误。最后，我们的时间ACA生成病态插入操作，增大实际键分布与数据节点线性模型之间的差异，使运行时性能相比在合法工作负载下运行ALEX下降高达1,641倍。
期刊
暂无期刊信息
机构
暂无机构信息
引用论文
暂无论文信息