面向值语义的 DBMS 变形测试（OSDI 2026）
原题：ValScope: Value-Semantics-Aware Metamorphic Testing for Detecting Logical Bugs in DBMSs
一句话总结：现有 DBMS 变形测试主要检查结果集合，难以发现集合不变但聚合或数值已错误的逻辑 bug；ValScope 用集合语义和值语义的单调关系统一约束 SQL 变异，在 6 个 MySQL 系 DBMS 上报告 67 个逻辑 bug，其中 57 个已确认。
问题与动机
DBMS 逻辑 bug 不一定崩溃，可能静默返回错误结果。复杂 SQL 又难以直接计算正确答案，因此测试通常依赖变形测试：对原查询施加语义可控的变换，再检查两个结果之间应满足的关系。
NOREC、TLP 等等价关系方法要求结果完全相同，变异后的查询往往仍共享同一个错误算子。PINOLO 放宽为结果集合的包含关系，扩大了测试空间，但仍看不到 SUM、AVG、排序和算术表达式中的值错误。论文用 MySQL Bug #119321 说明这一点：SUM(DISTINCT c * 2) 与 SUM(DISTINCT c) 的集合关系未变，但 DBMS 可能把结果算成 NULL。
关键观察 / 隐含假设
- 观察 1：值错误可以发生在结果集合完全相同的查询中。 MySQL 的上述聚合 bug 保持输入元组集合不变，却破坏了输出数值（§1）。
- 依赖假设：变异前后的目标列可以按分组键或确定性顺序对齐，并且 SQL 类型具有可比较的全序。
- 可能失效场景：无确定性顺序、重复元组难以对齐或包含复杂
NULL/浮点语义时，单调比较可能产生误报或漏报。
- 观察 2：局部变异的语义会沿 SQL AST 在集合和值两个维度之间传播。 例如
MAX→MIN先改变值，再经谓词影响结果集合（§3.3–§3.4）。- 依赖假设：路径上的算子具有已知单调性，且实现中的依赖关系能从 AST 和列引用中准确恢复。
- 可能失效场景：
ABS、ROUND、复杂CASE等非单调表达式，以及RAND()、NOW()等非确定性函数不满足稳定方向。
- 观察 3：复杂查询结构是 bug 的主要载体。 57 个已确认 bug 中，45 个涉及子查询，17 个涉及聚合，19 个涉及 join，22 个涉及
GROUP BY/HAVING（§6.2）。- 证据强度：中。数据来自发现到的 bug 集合，说明触发能力，但不能直接估计真实生产 bug 分布。
核心方法
ValScope 遵循“生成—变异—验证”流程。它先随机生成合法数据库和 SQL 查询，再用 SQLGlot 构建 AST，选择可安全变异的节点，最后执行原查询与变异查询并验证预测的关系（图 2）。
模型包含两类关系。集合语义用多重集合的包含关系表示；值语义按 GROUP BY 键或确定性排序对齐目标列，并检查值的逐组单调方向（§3.1–§3.2）。这使得聚合输出可以被当作值，而不必错误地套用元组包含关系。
系统实现了 26 个 approximate mutator，其中 17 个面向集合语义，9 个面向值语义（§4.3）。代表性变异包括放宽谓词、UNION→UNION ALL、移除 DISTINCT、COUNT(DISTINCT c)→COUNT(c)、MAX↔MIN 以及算术表达式变换。
传播分析从变异节点沿祖先链向根节点遍历。每个算子给出输入/输出语义维度和是否反转方向的符号，系统累积这些符号，得到最终查询级别的集合或值关系（算法 1、表 2）。发现违反预测关系后，再用 SQLESS 做 delta debugging 简化查询并人工去重。
设计取舍
- 扩大覆盖范围与单调性限制：值语义让聚合和跨维度传播可测试，但无法直接处理非单调函数。
- 随机生成的合法性与方言覆盖：系统围绕 MySQL 语法设计，适配 TiDB、OceanBase 等 MySQL 系 DBMS；新方言仍需修改语法、类型和操作支持。
- 结果关系而非正确答案：变形测试避免构造 oracle，但要求维护大量算子单调性规则，并处理浮点误差、
NULL和厂商特有类型转换。
实验与结果
- ValScope 在 MySQL、MariaDB、OceanBase、Percona、PolarDB、TiDB 上报告 67 个此前未知的逻辑 bug，57 个已确认（§6.2）。
- 已确认 bug 中 43 个违反值语义关系，32 个需要集合和值语义之间的传播分析；类别可重叠（§6.2）。
- 24 小时对比中，ValScope 对 61 个 24 小时内发现的 bug 独有地发现 48 个，占 78.9%；PINOLO、TLP、NOREC、DQP 分别能发现其中 12、4、2、6 个（§6.3）。
- 生成吞吐约为 1923–2000 个测试用例/秒；执行成功率为 72%–93%，其中 PolarDB 最低（§6.2）。
- 67 个 bug 中 61 个在首日发现；最长确认 bug 的历史延迟达到 20 年（§6.2）。
论断—证据表
| 论断 | 证据 | 评测边界 | 置信度 |
|---|---|---|---|
| 值语义关系扩大了可发现的逻辑 bug 范围 | 67 个 bug；48/61 个为相对既有 oracle 的独有发现 | 6 个 DBMS、24 小时对比，部分结果依赖手工构造对应变形 | 强 |
| 跨集合和值的传播能捕获复杂查询错误 | 32 个确认 bug 需要跨维度推理；子查询、聚合、join 和分组 bug 分布见 §6.2 | MySQL 语法及其衍生方言；类别可重叠 | 中 |
| 系统具备实际测试效率 | 1923–2000 queries/s，首日发现 61/67 个 bug | 单台 104 核、500 GB 内存服务器，DBMS 版本固定 | 中 |
批判性分析
论证链条
论文的主链条是闭合的：集合关系无法表达值错误，值语义关系补足这一维度，AST 传播把局部变异转换成可检查的全局关系，实验证明它确实触发了既有方法遗漏的 bug。需要谨慎的是，“独有发现”来自对每个 ValScope 查询手工构造其他 oracle 的比较，不等同于完整重跑所有工具在相同搜索空间中的覆盖率。
假设压力测试
值语义比较依赖目标行的配对。无 GROUP BY 时用主键或字典序对齐，若查询输出没有稳定唯一键、包含重复行或排序本身是 bug 触发点，关系可能不可靠。单调性规则也依赖 SQL 类型和运算语义；浮点运算、隐式转换以及厂商方言会削弱方向判断。论文以容差和人工确认处理这些问题，但没有给出误报率的系统统计。
实验可信度
6 个 DBMS 覆盖了 MySQL 家族的多个实现，且有长期维护背景。基线包含等价关系、集合近似、差分查询计划等路线，比较维度较完整。实验主要衡量发现数量，未系统报告查询计划覆盖、CPU/存储成本、每个 mutator 的单位成本或 bug 的严重性分布。随机数据库和生成语法也未必代表生产查询。
系统性缺陷
系统包含 26 个手工定义 mutator 和算子传播表，扩展 SQL 功能时需要维护单调性知识。执行成功率最低为 PolarDB 的 72%，说明复杂语法跨方言仍有明显边界。论文未讨论长时间运行中的资源隔离、并发 DBMS 实例管理、崩溃恢复和可观测性成本；这些因素会影响其作为持续测试服务的部署方式。
局限与后续工作
- 局限 1：非单调函数和非确定性函数目前基本不在值语义检查范围内（§7）。
- 局限 2：系统以 MySQL 语法为中心，跨方言支持需要额外适配，测试结论不能直接外推到 PostgreSQL 等语义差异更大的 DBMS。
- 后续工作 1：为非单调函数建立区间或条件近似关系，并在固定数据集上测量误报率、漏报率与每个规则的有效 bug 产出。
- 后续工作 2：将覆盖反馈或查询计划反馈接入 mutator 选择，比较相同执行预算下随机选择与反馈导向选择的 bug 发现效率。
相关
- 相关概念：Metamorphic Testing、SQL、DBMS Fuzzing
- 同类系统：PINOLO、NOREC、TLP、SQLancer
- 同会议：OSDI-2026