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% 都是仅涉及单表查询。对于使用不同连接算法和连接结构的多表查询（比单表查询更易出错），还存在很大研究空白。
为多表连接查询的逻辑漏洞检测问题采用查询合成方法的难度远远超过单表查询的情况，这涉及到的挑战有两个：
结果验证：为了验证查询结果的正确性，之前的方法采用的是差分测试策略。其思路是使用不同的物理执行计划（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 被强行终止，原因包括内存等资源不足或访问了无效内存地址等。因此，崩溃漏洞很容易被发现。相较而言，逻辑漏洞则更难以发现，因为数据库依然会正常运行，处理查询后也会返回看似正确的结果（并且大多数情况下它们确实会返回正确结果，但在少数情况下却可能读取错误的结果集）。这些无声漏洞就像是隐形炸弹，要更加危险一些，因为它们难以检测到，还可能影响到应用的正确性。
