设为首页 - 加入收藏
广告 1000x90
您的当前位置:主页 > 教程 > 数据库 > 正文

一天自动发现四大数据库100+漏洞浙大研究获SIG

来源:未知 编辑:天选资讯 时间:2023-05-23

  过去几十年,现代数据库管理系统(DBMS)不断演进,可以支持多种不同的新架构,比如云平台和 HTAP,这需要对查询评估进行越来越复杂精细的优化。查询优化器(query optimizer)被认为是 DBMS 中最复杂和最重要的组件之一,其功能是解析输入的 SQL 查询,然后在内置成本模型的协助下生成高效的执行方案。查询优化器实现中的错误可能会导致出现漏洞(bug),包括崩溃漏洞和逻辑漏洞。崩溃漏洞很容易检测,因为崩溃会导致系统立即停止。然而逻辑漏洞却容易被忽视,因为逻辑漏洞会导致 DBMS 返回难以检测的错误结果集。这篇论文关注的重心是检测这些无声的漏洞。

  在检测 DBMS 中的逻辑漏洞方面有一种新兴方法,即 Pivoted Query Synthesis(PQS)。该方法的核心思路是从表格中随机选定一个枢轴数据行(pivot row),然后生成以该行作为结果的查询。如果合成的任何查询都不能返回该数据行,那么就检测到了一个逻辑漏洞。PQS 主要用来支持单表中的选项查询,其报告的漏洞中 90% 都是仅涉及单表查询。对于使用不同连接算法和连接结构的多表查询(比单表查询更易出错),还存在很大研究空白。

  下图展示了 MySQL 中连接查询两个的逻辑漏洞的。这两个漏洞通过使用本文新提出的工具都能被检测到。

  图 1 (a) 展示了 MySQL 8.0.18 中的哈希连接(hash join)的一个逻辑漏洞。在这个示例中,第一个查询返回了正确的结果集,因为其执行过程中使用了块嵌套循环连接(block nested loop join)。但是,第二个查询使用内部哈希连接(inner hash join)却出了问题,返回的是一个不正确的空结果集。这是因为其底层的哈希连接算法错误地认定 0 不等于 −0。

  图 1 (b) 中的逻辑漏洞源自 MySQL 8.0.28 中的半连接(semi-join)处理过程。在第一个查询中,嵌套循环内部连接会将数据类型 varchar 转换成 bigint,进而得到正确的结果集。而当使用哈希半连接执行第二个查询时,数据类型 varchar 会被转换成 double,从而导致数据准确度出现损失以及等值比较出错。

  为多表连接查询的逻辑漏洞检测问题采用查询合成方法的难度远远超过单表查询的情况,这涉及到的挑战有两个:

  结果验证:为了验证查询结果的正确性,之前的方法采用的是差分测试策略。其思路是使用不同的物理执行计划(physical plan,即数据库系统实际执行查询语句的方式)来处理查询。如果这些规划返回的结果集不一致,那么就可能是检测到了逻辑漏洞。但是,差分测试方法有两个缺点。其一,某些逻辑漏洞可影响多个物理执行计划并让它们全部生成同样的错误结果。其二,当观察到不一致的结果集时,需要人工检查生成正确结果的是哪一个执行计划,从而导致成本开销变得高昂。这个问题有一个可能的解决方案,即为任意测试查询构建真值(ground-truth)结果,但现有的工具并不支持这种操作;

  搜索空间:对于给定的数据库模式,可生成的连接查询的数量随表格和列的数量呈指数级变化。由于我们不可能为了验证而枚举出所有可能的查询,因此就需要一种有效的查询空间探索机制,以便让我们尽可能高效地检测出逻辑漏洞。

  针对以上难题,浙大的研究者提出了一种名为 Transformed Query Synthesis(TQS)的方法。在检测 DBMS 中连接优化的逻辑漏洞任务上,TQS 是一种普适且成本高效的全新工具。

  针对上述第一个挑战,研究者提出的应对方法是 DSG,即数据驱动的模式和查询生成(Data-guided Schema and query Generation)。给定表示为一个宽表数据集,DSG 可基于检测到的范式将该数据集拆分为多个表格。为了加快发现漏洞的速度,DSG 还会向生成的数据库中注入一些人工噪声数据。首先,将该数据库模式转换成一个图(graph),其中节点是表 / 列,边是节点之间的关系。DSG 会在模式图上使用随机游走来为查询选择表格,然后再使用这些表格来生成连接(join)。对于涉及多表的特定连接查询,我们可以轻松从宽表格中找到其真值结果。这样一来,DSG 就能有效地为数据库验证生成 (查询,结果) 集合 了。

  针对上述第二个挑战,研究者设计的方法是 KQE,即知识引导的查询空间探索(Knowledge-guided Query space Exploration)。该方法首先是将模式图扩展成一个规划迭代图(plan-iterative graph),其表示整个查询生成空间。然后将每个连接查询表示为一个子图。为了给生成的查询图评分,KQE 采用了一种基于嵌入的图索引,其可以在已经探索过的空间中搜索是否有结构相似的查询图。根据覆盖度分数引导随机游走查询生成器,以尽可能多地探索未知的查询空间。

  为了展现该方法的通用性和有效性,研究者在四个常用 DBMS 上对 TQS 进行了评估:MySQL、MariaDB、TiDB 和 PolarDB。运行了 24 小时后,TQS 成功找到了 115 个漏洞,包括 MySQL 中 31 个、MariaDB 中 30 个、TiDB 中 31 个、PolarDB 中 23 个。通过分析根本原因,可归纳出这些漏洞的类型,其中 MySQL 中的漏洞有 7 种、MariaDB 有 5 种、TiDB 有 5 种、PolarDB 有 3 种。研究者已经将发现的漏洞提交给相应的社区并且收到了积极的反馈。

  数据库的漏洞有两种:崩溃和逻辑漏洞。崩溃漏洞来自于操作系统和 DBMS 的执行过程。它们会导致 DBMS 被强行终止,原因包括内存等资源不足或访问了无效内存地址等。因此,崩溃漏洞很容易被发现。相较而言,逻辑漏洞则更难以发现,因为数据库依然会正常运行,处理查询后也会返回看似正确的结果(并且大多数情况下它们确实会返回正确结果,但在少数情况下却可能读取错误的结果集)。这些无声漏洞就像是隐形炸弹,要更加危险一些,因为它们难以检测到,还可能影响到应用的正确性。

  这篇论文为多表连接查询问题引入了查询优化器来检测逻辑漏洞。研究者将这些漏洞称为连接优化漏洞(join optimization bugs)。使用表 1 给出的标记法,连接优化漏洞检测问题可以形式化地定义为:

  图 2 给出了 TQS 的架构概况。给定一个基准数据集和目标 DBMS,TQS 通过基于数据集生成查询来搜索 DBMS 可能存在的逻辑漏洞。TQS 有两大关键组件:数据引导的模式和查询生成(DSG)和知识引导的查询空间探索(KQE)

  DSG 将输入数据集视为一个宽表,并且除了原始元组外,DSG 还会刻意合成一些有易错值(比如空值或非常长的字符串)的元组。针对连接查询,DSG 会为该宽表创建一个新模式,其方法是将该宽表分成多个表,确保这些表符合基于功能依赖性的范式。DSG 会将该数据库模式建模成一个图,然后在该模式图上通过随机游走来生成逻辑 / 概念查询。DSG 会将逻辑查询具体化为物理执行计划,并通过不同的提示对该查询进行变换,使 DBMS 能够执行多个不同的物理执行计划,以搜索漏洞。对于一个连接查询,其基本真值结果是通过将连接图映射回宽表而得到。

  在完成模式设置和数据拆分之后,KQE 将该模式图扩展为一个规划迭代图。每个查询都表示为一个子图。KQE 为历史中的查询图(即在已探索过的查询空间中)的嵌入构建一个基于嵌入的图索引。直观地说,KQE 的作用是确保新生成的查询图尽可能地远离其在历史中的最近邻,即这是为了探索新的查询图,而不是重复已有的查询图。为此,KQE 通过基于结构相似性(与历史中的查询图)为生成的查询图评分,同时使用自适应随机游走方法来生成查询。。

  上使用随机游走来生成查询的连接表达(第 10 行)。事实上,连接查询可以被投射为

  KQE 将模式图扩展为一个规划迭代图(第 4 行)。为避免测试相似的路径,KQE 会构建一个基于嵌入的图索引

  来索引已有查询图的嵌入(第 9 行)。KQE 根据当前查询图与已有查询图的结构相似性来更新规划迭代图 G 的边权重 π (第 8 行)。KQE 为下一条可能路径评分,其引导着随机游走生成器,从而更倾向于探索未知的查询空间。

  对该查询进行变换,以执行多个不同的实际查询规划(第 11 行)。最后,将查询

  的结果集与基本线 行)。如果它们不一致,天选那么就检测到了连接优化漏洞(第 15 行)。

  原标题:《一天自动发现四大数据库100+漏洞,浙大研究获SIGMOD 2023最佳论文》天选团队

相关推荐:

网友评论:

发表评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
用户名: 验证码:点击我更换图片

织梦模板大全 dedecms.codesdq 联系QQ:121673232 邮箱:121673232@qq.com

Copyright © 2002-2011 DEDECMS. 织梦科技 版权所有 Power by DedeCms

Top