让“无声的漏洞”无可遁形：详解 2023 数据库顶

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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