首页 > 旅游 > > 正文
重点聚焦!让“无声的漏洞”无可遁形:详解2023 数据库顶会SIGMOD最佳论文
2023-06-22 16:09:05 东方资讯

【编者按】2023数据库顶会SIGMOD在美国西雅图颁出最佳论文。阿里云与浙江大学合作的《Detecting Logic Bugs of Join Optimizations in DBMS》获得最佳论文,成为自1975年该会议至今49年以来,中国大陆研究团队首次斩获该奖项。

这项工作聚焦数据库逻辑测试,始于阿里云PolarDB云原生数据库的内核测试,通过开发创新的自动化数据库逻辑测试方案TQS,检出不易察觉的逻辑漏洞予以修复。实验发现,TQS运行仅24小时就检测出4大商用数据库管理系统的逻辑漏洞115个,予以修复后,大幅提升数据库稳定性。

该论文一作唐秀系浙江大学博士,这一工作是她在阿里云数据库进行研究型实习时的成果;阿里云数据库负责人李飞飞也是作者之一,此前他曾以一作身份凭借《Wander Join: Online Aggregation via Random Walks》拿下2016年SIGMOD最佳论文。本次论文获奖,完成了中国大陆研究团队在数据库顶会的历史性突破,也成为了中国校企合作攻克科研难题的典范之一。


(资料图片仅供参考)

我们特别邀请到唐秀博士,为我们深入浅出地解读这篇论文的关键成果。

作者 | 唐秀,浙江大学博士,2022 年阿里巴巴优秀研究型实习生

背景与动机

我国数据库正处于高速发展期,并且随着应用复杂程度的增加,企业和用户对于更强大、更安全的数据库的需求也越来越迫切。因此,如何检查数据库漏洞和错误,成为保障数据库安全、提升数据库稳定性的关键之一。

在数据库查询执行期间,主要有两类错误(bug):一种常见的错误是数据库突然崩溃停止,这种错误对于开发人员来说相对容易检测,因为数据库连接会突然中断。然而,还存在一类隐藏的错误,即逻辑漏洞。在这种情况下,数据库正常运行并返回结果,但实际上并非正确的结果。

图说:逻辑漏洞举例

以上图中的两个逻辑漏洞为例,图a展现了MySQL的一个哈希连接错误,这种错误发生在错误地将零和负零视为不同值的情况下,导致最终返回一组空集合;b图涉及数据类型转换和数据精度损失导致的错误半连接:在MySQL中,当比较两个值是否相等时,数据类型转换和精度损失可能导致意外的结果,从而影响查询结果集的构建。

逻辑漏洞很难检测,但其导致的后果确很严重,重则会导致“上万航班延误瘫痪”级别的大规模宕机,因此也被视为“无声的漏洞”。本论文便主要聚焦于此。

针对逻辑漏洞,目前已经有一些检测方法,例如部分查询语义(PQS),但这些方法通常只支持针对单表选择查询的检测,在涉及多表查询以及不同的连接算法和连接结构的情况下,仍存在大量的研究空白。

而最常用的差分测试,通过在不同数据库中执行相同操作,以验证其一致性,这种测试仍存在问题:假如两个数据库返回相同的结果,也有可能是基于同样错误的逻辑生成了一样的结果, 也即如何验证查询结果正确性的关键问题。

同时,测试数据库现在面临的搜索空间是非常庞大的, 如何引导测试以尽可能消耗最小的资源穷尽全部测试,也是一个需要解决的问题。

研究思路与核心内容

围绕这两个关键问题,我们引入了一个名为TQS(转换查询合成)的全新解决方案,以解决MySQL数据库中可能出现的逻辑错误。

图说:TQS架构图

TQS包括DSG和KQE两部分,分别为数据驱动的模式和查询生成,与知识引导的查询空间探索。

为解决真值生成问题,我们采用了以下方法:首先,根据给定的宽表,使用函数依赖(FD)将该表拆分为多个表。

图说:DSG是如何拆分宽表的

同时,为了进行边缘测试,我们还插入了一些噪声数据作为边缘情况的样本(图中彩色数据),并基于数据库的模式图模型,随机游走生成一系列查询。

图说:DSG构建针对表连接的Bitmap 索引

在此基础上,构建RowID映射表,用于记录在表拆分过程中,宽表中的行和拆分后表的行的对应关系。根据表连接是表拆分的逆向过程的直觉,构建基于构建RowID映射的Bitmap索引,以便从宽表中检索到连接查询的理论真值。 这些真值生成后,便是检测潜在逻辑错误的参照样本。

然而,对于给定的数据库模式,可生成的连接查询的数量会随着表格和列的数量呈指数级增长,显然无法使用枚举法一一验证。那么,要如何更高效地探索查询未知空间呢?我们提出了TQS的第二部分设计——KQE。

图说:KQE原理图

KQE首先将模式图进一步拓展为一个规划迭代图,来表示整个查询生成空间。同时,在大量的历史查询图中,KQE构建了一个基于嵌入的图索引,以确保新生成的查询图尽可能地远离其在历史查询中的近邻,探索更多的未知空间。

总体来看,KQE可基于结构相似性为生成的查询图评分,同时也通过自适应随机游走多样化查询生成, 从而极大降低了对于重复查询的概率,节省了计算资源开支。

实验结果分析

我们的研究在MySQL、MariaDB、TiDB 和 PolarDB 等4大常用DBMS上进行了实验。

运行了 24 小时后,TQS 成功找到了 115 个漏洞:MySQL 中 31 个、MariaDB 中 30 个、TiDB 中 31 个、PolarDB 中 23 个。通过最小化测试样例,我们进一步将它们分为20种类型。

图说:实验检出漏洞分类详表

我们已经将检测到的漏洞提交给相应数据库社区,并得到了他们积极的反馈。这些漏洞的危机程度被数据库社区判定为首要危急或严重级别,一些漏洞已经修复在了其数据库最新版本中。

具体来说,MySQL 8.0.28的错误主要集中在Semi-join和Sub-query的执行过程中,其中,几个错误被评定为首要危急,即最紧急的错误,这些错误已经在MySQL 8.0.30版本中得到修复,并提供了相应的修复说明。而对于已使用SQLancer进行全面测试的TiDB,TQS也测出了一些首要危急错误,TiDB对其进行了修复。另外,针对PolarDB,我们则直接提交错误报告,相关错误已经被修复。

图说:TQS与原有方法的有效性对比

总的来说,相比于其它方法,TQS在多项指标上取得了更优的效果,较原有方法实现高达100倍的性能提升,各组件的有效性也通过控制变量实验得到了检验。

6月21日晚上8点整,本文一作唐秀将直播解读论文,欢迎广大读者预约收看。

返回搜狐,查看更多

责任编辑:

x 广告