论文标题
来自嘈杂卷的数据库重建：缓存侧通道攻击SQLITE
Database Reconstruction from Noisy Volumes: A Cache Side-Channel Attack on SQLite
论文作者
论文摘要
我们证明了在sqlite的缓存侧通道攻击下数据库重建的可行性。具体而言，我们对SQLite进行了冲洗+重新加载攻击，该攻击获得了对私有数据库进行的大约（或“嘈杂”）量的范围查询。然后，鉴于这些近似体积，我们提出了几种算法，这些算法在各种实验条件下几乎重建了几乎确切的数据库。我们的重建算法对大约/嘈杂的设置采用新技术，包括一个易于噪声的集团找到算法，一种“匹配和扩展”算法，用于外推量，从该集团中省略了从该集团中省略的量，以及“降低降噪步骤”，可以使用近距离矢量问题（CVP）的solver（CVP）的整体效果，以提高效率（CVP）的效果。我们攻击的时间复杂性随着查询属性的范围的大小而迅速增长，但可以很好地扩展到大型数据库。实验结果表明，我们可以在个人笔记本电脑上重建100,000尺寸的数据库和尺寸12的范围，在12小时内，错误百分比为0.11％。
We demonstrate the feasibility of database reconstruction under a cache side-channel attack on SQLite. Specifically, we present a Flush+Reload attack on SQLite that obtains approximate (or "noisy") volumes of range queries made to a private database. We then present several algorithms that, taken together, reconstruct nearly the exact database in varied experimental conditions, given these approximate volumes. Our reconstruction algorithms employ novel techniques for the approximate/noisy setting, including a noise-tolerant clique-finding algorithm, a "Match & Extend" algorithm for extrapolating volumes that are omitted from the clique, and a "Noise Reduction Step" that makes use of a closest vector problem (CVP) solver to improve the overall accuracy of the reconstructed database. The time complexity of our attacks grows quickly with the size of the range of the queried attribute, but scales well to large databases. Experimental results show that we can reconstruct databases of size 100,000 and ranges of size 12 with error percentage of 0.11 % in under 12 hours on a personal laptop.
