让“无声的漏洞”无可遁形：详解2023 数据库顶会SIGMOD最佳论文

2023-06-23 15:50:46 来源：CSDN

【编者按】 2 0 23 数据库顶会 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 的错误主要集中在Semi-join和Sub-query的执行过程中，其中，几个错误被评定为首要危急，即最紧急的错误，这些错误已经在MySQL 版本中得到修复，并提供了相应的修复说明。而对于已使用SQLancer进行全面测试的TiDB，TQS也测出了一些首要危急错误，TiDB对其进行了修复。另外，针对PolarDB，我们则直接提交错误报告，相关错误已经被修复。

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

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

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