机器之心编辑部
本文中，浙大的研究者提出了一种名为 Transformed Query Synthesis（TQS）的方法。在运行了 24 小时后，TQS 成功找到了 115 个漏洞，包括 MySQL 中 31 个、MariaDB 中 30 个、TiDB 中 31 个、PolarDB 中 23 个。
2023 年度的 ACM SIGMOD/PODS 国际数据管理大会（SIGMOD 2023）将于当地时间 6 月 18-23 日在美国西雅图举办。近日，该会议公布了最佳论文名单，微软研究院的《Predicate Pushdown for Data Science Pipelines》和浙江大学的《Detecting Logic Bugs of Join Optimizations in DBMS》获奖。自 1975 年该会议始办以来，这是中国大陆研究团队首次获得该会议的最佳论文奖。其中浙大的研究提出了一种新颖的方法，可以自动发现 MySQL、MariaDB、TiDB 和 PolarDB 等数据库管理系统的逻辑漏洞。
过去几十年，现代数据库管理系统（DBMS）不断演进，可以支持多种不同的新架构，比如云平台和 HTAP，这需要对查询评估进行越来越复杂精细的优化。查询优化器（query optimizer）被认为是 DBMS 中最复杂和最重要的组件之一，其功能是解析输入的 SQL 查询，然后在内置成本模型的协助下生成高效的执行方案。查询优化器实现中的错误可能会导致出现漏洞（bug)，包括崩溃漏洞和逻辑漏洞。崩溃漏洞很容易检测，因为崩溃会导致系统立即停止。然而逻辑漏洞却容易被忽视，因为逻辑漏洞会导致 DBMS 返回难以检测的错误结果集。这篇论文关注的重心是检测这些无声的漏洞。
在检测 DBMS 中的逻辑漏洞方面有一种新兴方法，即 Pivoted Query Synthesis（PQS）。该方法的核心思路是从表格中随机选定一个枢轴数据行（pivot row），然后生成以该行作为结果的查询。如果合成的任何查询都不能返回该数据行，那么就检测到了一个逻辑漏洞。PQS 主要用来支持单表中的选项查询，其报告的漏洞中 90% 都是仅涉及单表查询。对于使用不同连接算法和连接结构的多表查询（比单表查询更易出错），还存在很大研究空白。
下图展示了 MySQL 中连接查询两个的逻辑漏洞的。这两个漏洞通过使用本文新提出的工具都能被检测到。
图 1：DBMS 中连接优化的逻辑漏洞示例
图 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 给出的标记法，连接优化漏洞检测问题可以形式化地定义为：
定义：对于查询工作负载
中的每个查询
，令查询优化器通过多个实际规划执行
的连接，并使用基本真值 
验证其结果集
。如果
，则发现了一个连接优化漏洞。
表 1：符号说明表
方案概述
图 2 给出了 TQS 的架构概况。给定一个基准数据集和目标 DBMS，TQS 通过基于数据集生成查询来搜索 DBMS 可能存在的逻辑漏洞。TQS 有两大关键组件：数据引导的模式和查询生成（DSG）和知识引导的查询空间探索（KQE）
图 2：TQS 概况
DSG 将输入数据集视为一个宽表，并且除了原始元组外，DSG 还会刻意合成一些有易错值（比如空值或非常长的字符串）的元组。针对连接查询，DSG 会为该宽表创建一个新模式，其方法是将该宽表分成多个表，确保这些表符合基于功能依赖性的范式。DSG 会将该数据库模式建模成一个图，然后在该模式图上通过随机游走来生成逻辑 / 概念查询。DSG 会将逻辑查询具体化为物理执行计划，并通过不同的提示对该查询进行变换，使 DBMS 能够执行多个不同的物理执行计划，以搜索漏洞。对于一个连接查询，其基本真值结果是通过将连接图映射回宽表而得到。
在完成模式设置和数据拆分之后，KQE 将该模式图扩展为一个规划迭代图。每个查询都表示为一个子图。KQE 为历史中的查询图（即在已探索过的查询空间中）的嵌入构建一个基于嵌入的图索引。直观地说，KQE 的作用是确保新生成的查询图尽可能地远离其在历史中的最近邻，即这是为了探索新的查询图，而不是重复已有的查询图。为此，KQE 通过基于结构相似性（与历史中的查询图）为生成的查询图评分，同时使用自适应随机游走方法来生成查询。。
算法 1 总结了 TQS 的核心思想，其中第 2、10、12 行是 DSG，第 4、8、9 行是 KQE。
给定一个数据集
和从
采样得到的宽表
，DSG 将单个宽表
拆分成多表，这些表格组成符合 3NF 的数据库模式
（第 2 行）。模式
可以被视为一个图
，其中表格和列是顶点，边代表的是顶点之间的关系。DSG 在 
上使用随机游走来生成查询的连接表达（第 10 行）。事实上，连接查询可以被投射为
的子图。通过将子图映射回宽表格
，DSG 可轻松地检索到该查询的基本真值结果（第 12 行）。
KQE 将模式图扩展为一个规划迭代图（第 4 行）。为避免测试相似的路径，KQE 会构建一个基于嵌入的图索引
来索引已有查询图的嵌入（第 9 行）。KQE 根据当前查询图与已有查询图的结构相似性来更新规划迭代图 G 的边权重 π （第 8 行）。KQE 为下一条可能路径评分，其引导着随机游走生成器，从而更倾向于探索未知的查询空间。
对于一个查询 
，TQS 通过提示集
对该查询进行变换，以执行多个不同的实际查询规划（第 11 行）。最后，将查询
的结果集与基本真值
进行比较（第 14 行）。如果它们不一致，那么就检测到了连接优化漏洞（第 15 行）。
有关 DSG 和 KQE 的更多详细描述请阅读原论文。
实验结果
TQS 成功找到了 MySQL、MariaDB、TiDB 和 PolarDB 等数据库管理系统的一些逻辑漏洞，它们分为 20 种类型，其中 MySQL 的漏洞有 7 种、MariaDB 的有 5 种、TiDB 的有 5 种、PolarDB 的有 3 种，如下表所示。
相比于其它方法，浙大提出的 TQS 的整体表现也相当亮眼，在多项指标上都取得了显著更优的成绩，而各组件的有效性也通过控制变量实验得到了检验。
但研究者也表示，TQS 目前关注的是等值连接查询。尽管如此，DSG 和 KQE 思想也可扩展到非等值连接的情况。唯一的难题是如何生成和管理查询真值结果 —— 在非等值连接的情况下，这些结果的规模将指数级增长。这方面还有待未来进一步研究。
