THANOS: DBMS Bug Detection via Storage Engine Rotation Based Differential Testing

ABSTRACT

摘要——差分测试是一种在自动化数据库管理系统（DBMS）测试中建立测试预言的普遍策略。然而，选择具有不同实现和兼容输入语法的等效DBMS需要大量的人工努力。在本文中，我们提出了THANOS，这是一种通过存储引擎轮换的差分测试来发现DBMS漏洞的框架。我们的关键见解是，不同存储引擎的DBMS必须提供一致的基础存储功能。因此，可以基于存储引擎轮换来构建等效的DBMS，确保相同的SQL测试用例在这些等效DBMS上产生一致的结果。该框架包括四个主要步骤：1）选择适当的存储引擎；2）提取所选存储引擎之间的等效性信息；3）综合确保DBMS等效性的特征导向测试用例；4）将测试用例发送到具有所选存储引擎的DBMS，并比较结果。

我们在三种广泛使用且广泛测试的DBMS上评估了THANOS，分别是MySQL、MariaDB和Percona，并将其与最先进的模糊测试工具SQLancer、SQLsmith和SQUIRREL进行了对比。THANOS在分支覆盖率方面比它们高出24%-116%，并且还发现了其他模糊测试工具未发现的许多漏洞。更重要的是，厂商已经确认了THANOS发现的32个此前未知的漏洞，其中29个被验证为关键漏洞。

INTRODUCTION

Background

DBMS作用：数据库管理系统（DBMS）为现代计算中的高效和安全数据处理提供了结构化框架，确保数据的存储、检索和管理。

DBMS测试的重要性：测试DBMS对于保证其可靠性、性能和安全性至关重要，直接影响关键业务和技术操作中的数据管理的准确性和一致性。

测试预言问题：在自动化DBMS测试中，建立能够区分DBMS正确行为的测试预言是一个主要问题。

差分测试的兴起：差分测试作为一种常见策略，通过比较等效DBMS实现的输出，以发现兼容输入语法中的不一致性。

两种差分测试方法：

基于版本的比较：在不同版本的DBMS上执行相同的SQL查询，例如在MySQL中使用APOLLO检测性能回归，但这种方法可能忽略由于小版本差异导致的真实问题。
基于厂商的比较：在不同DBMS上执行等效的SQL语句，例如在SQLite、PostgreSQL、MySQL、SQL Server和Oracle之间进行逻辑测试。

复杂系统中的挑战：由于DBMS特性、索引策略和数据存储机制的多样性，将这种方案应用于更复杂的系统面临挑战。

理想的差分测试方案：应结合不同的DBMS实现，并使用相似的输入语法，以发现隐藏问题并减少SQL生成成本。

现有方法的局限性：目前的差分测试方法在同时实现发现问题和降低成本方面存在困难。

Key insight

本文提出了一种新的差分测试方案，用于DBMS漏洞检测，通过轮换存储引擎来平衡实现的多样性与输入语法的一致性。

存储引擎的重要性：存储引擎是DBMS中的关键组件，连接查询计划器和底层存储基础设施。

等效DBMS实例：通过为DBMS配置各种存储引擎，创建等效的DBMS实例，以建立测试预言来检测漏洞。

存储引擎的复杂性：大多数生产DBMS支持多个存储引擎，具有不同的功能和性能特性，这些存储引擎在索引数据、原子性和物理布局方面引入了复杂性。

执行计划的多样性：不同的存储引擎导致SQL查询的执行计划优化有所不同，增强了DBMS逻辑的多样性。

成本降低：由于存储引擎在SQL解析、语义分析和查询规划后被调用，该方案确保了输入语法的一致性，同时降低了工具开发成本。

challenges

主要挑战：存储引擎轮换的主要挑战在于确保生成的测试用例在不同存储引擎间具有等效性，同时能够全面测试存储引擎的所有功能。

1、等效性问题：确保生成的测试用例在不同的存储引擎之间具有等效性，尤其是当某些存储引擎不支持特定功能时，测试用例可能无法保持等效。

2、特性支持差异：不同存储引擎支持的功能不同，例如MySQL中的InnoDB支持全文索引，而Memory引擎不支持，这会导致测试用例在不同引擎间不等效。

3、随机选择特性的风险：随机选择存储引擎相关特性可能导致测试用例不具备等效性，而选择无关特性则可能使测试无效。

4、测试的全面性：需要生成广泛覆盖存储引擎特性的测试用例，以确保对DBMS进行全面的功能测试，而不仅仅是基础功能的测试。

5、多样化测试需求：测试用例必须考察DBMS在多种存储相关操作、数据结构和优化机制方面的能力，以确保其处理不同存储引擎的多样性。

approaches

作者通过以下四个步骤来解决这些挑战：

选择合适的存储引擎：首先，选择适当的存储引擎作为构建等效DBMS的基础，确保覆盖更多DBMS的存储引擎特性。
提取等效性信息：其次，提取所选存储引擎之间的等效性信息，以构建等效的DBMS。
feature-oriented的测试用例：第三，使用等效性信息和元数据指导，综合生成feature-oriented的测试用例，这不仅确保语义正确性，还能够全面探索存储引擎的所有功能。
比较测试结果：最后，将测试用例发送到具有所选存储引擎的DBMS，比较结果以检测漏洞。

evaluation

框架实现与应用：作者实现了一个通用的DBMS测试框架THANOS，并应用于MySQL、MariaDB和Percona这三个广泛测试的DBMS。

发现漏洞：THANOS共发现了32个新漏洞，已被相应厂商确认。其中，MySQL发现了11个漏洞，MariaDB发现了17个漏洞，Percona发现了4个漏洞，其中29个被验证为关键漏洞。

与其他方法的对比：为了评估THANOS的有效性，作者将其与最先进的DBMS测试方法（如SQLancer、SQLsmith和SQUIRREL）进行对比。THANOS在分支覆盖率上分别比这些方法高出115.95%、45.23%和23.72%。

漏洞发现能力：在24小时内，THANOS比SQLancer、SQLsmith和SQUIRREL分别多发现了14个、13个和11个漏洞。

特性导向测试用例的有效性：同时，作者还展示了feature-oriented测试用例综合方法的有效性。

contributions

论文的主要贡献概括如下：

提出新的差分测试方法：提出了一种新的差分测试方法，通过轮换存储引擎构建等效的DBMS，补充了现有DBMS测试预言的方法，为验证执行结果提供了参考。
实现了THANOS框架：实现了THANOS，一个DBMS测试框架，通过基于所选存储引擎特性合成测试用例，确保测试DBMS实例的等效性。任何不一致的执行结果都会被视为潜在的异常。
评估THANOS的有效性：在三个广泛使用和测试的DBMS上对THANOS进行了评估，结果表明THANOS优于其他先进技术，发现了32个漏洞，并且比其他方法找到了更多的基本块和漏洞。

BACKGROUND AND MOTIVATION

DBMS Storage Engines.

这段话主要概括了DBMS存储引擎的作用和关键特性：

存储引擎的作用：存储引擎是DBMS的基础组件，负责数据存储、检索和处理，充当DBMS和物理数据存储之间的中介，确保高效的数据处理和访问。
多样性：现代DBMS通常支持多种存储引擎，每个引擎都有特定的特性和能力，适用于不同的使用场景。例如，MySQL支持InnoDB、MyISAM和Memory等存储引擎。
重要性：存储引擎与DBMS的基础组件（如优化器和解析器）紧密相关，对数据库的整体性能有重要影响。
可扩展性：存储引擎组件具有高度的可扩展性，能够无缝集成新的存储引擎作为插件，帮助系统应对新的技术挑战和业务需求。

Storage Engine Features.

这段话的主要内容如下：

存储引擎特性定义：存储引擎特性是DBMS中的存储引擎提供的功能和属性，旨在优化数据库操作的各个方面，如数据管理、检索和处理。
特性集合F：这些特性被正式定义为集合F，其中包含数据索引、事务支持、数据分区等多个功能。
关注的特性：本文主要关注通过SQL语句使用和展示的存储引擎特性。
分类和文档：作者将存储引擎特性分类为10个主要类别，并根据官方DBMS文档进行了整理。由于特性列表过长，完整的特性列表可以在THANOS的官方网站上查阅。

Basic Idea

THANOS的基本理念：THANOS的关键思想是通过利用DBMS的存储引擎来构建等效的DBMS实例，作为验证执行结果的参考，帮助发现潜在的漏洞，而无需花费大量时间寻找不同的DBMS进行差分比较。

利用存储引擎构建等效DBMS：THANOS通过为DBMS配置不同的存储引擎来构建等效实例。当等效的DBMS在执行相同的测试用例时产生不同的结果时，这表明可能存在漏洞。

MySQL中的实际案例：THANOS在MySQL中发现了一个处理NULL值的不一致性问题，涉及InnoDB和Memory存储引擎的行为差异。InnoDB返回空结果集，而Memory返回包含四列NULL值的结果，这表明MySQL存储引擎的实现存在问题。

传统方法的局限性：传统的DBMS模糊测试方法（如SQUIRREL）无法检测到此类问题，而依赖特定规则的变形测试（如SQLancer）在检测这一特定问题上也表现不佳。

THANOS的优势：THANOS能够在短时间内检测到其他DBMS测试方法难以发现的问题，显示了其在漏洞检测中的有效性。

DESIGN OF THANOS

选择存储引擎：THANOS首先选择合适的存储引擎作为构建等效DBMS的基础。

提取等效信息：THANOS从所选存储引擎中提取等效性信息，包括这些存储引擎支持的共同和互补特性。

生成特性导向的测试用例：THANOS使用提取的等效性信息来综合生成特性导向的测试用例，这些测试用例与所选存储引擎的DBMS语义相关。

执行测试并检测漏洞：THANOS在具有所选存储引擎的DBMS上执行测试，分析不同引擎间的结果。如果结果不一致，表明可能存在漏洞，THANOS可以进行检测。

A. Definitions

DBMS等效性：DBMS等效性指的是不同DBMS实例在实现或配置上存在差异的情况下，仍能表现出相同的功能行为。即等效的DBMS在面对相同的语义查询和操作时，能够产生一致的结果。

形式化定义：给定一个SQL语句$s$和DBMS $D$，如果两个DBMS实例在一系列测试用例中的执行结果保持一致，则它们被视为等效。对于两个测试用例和两个DBMS实例，等效性满足公式：

存储引擎相关等效性：本文侧重于基于存储引擎的DBMS等效性，考虑了支持多种可选存储引擎的DBMS。定义了存储引擎集合，以及其各自的特性和测试用例。若两个DBMS实例在相同的测试用例下表现一致，则认为它们是等效的。

形式表达：若两个DBMS实例$D_{e_i}$和$D_{e_j}$在特定测试用例集合中表现一致，它们被认为是等效的，表达为：

B. Feature-Guided Storage Engine Selection

THANOS的主要策略：THANOS通过为测试DBMS配置不同的存储引擎，并基于这些引擎的特性生成等效的测试用例。选择适当的存储引擎作为构建等效DBMS的基础非常重要。
存储引擎组合：不同的存储引擎组合具有不同的功能和代码分支。某些存储引擎组合可能存在更多潜在漏洞，因此选择适当的引擎组合进行测试有助于发现潜在的漏洞。例如，InnoDB和Aria支持70多个等效特性，而Archive和Memory只支持40个等效特性。
选择存储引擎的重要性：大多数漏洞（70%）是通过与InnoDB相关的存储引擎组合发现的，因此在测试准备阶段，选择合适的存储引擎非常关键。
特性引导的选择过程：THANOS根据所覆盖的特性和代码分支设计存储引擎选择算法，生成所有存储引擎组合，并为每个组合分配权重值。根据权重值高低选择存储引擎组合进行测试。如果在测试过程中发现新特性或新漏洞，THANOS会增加该组合的权重。

什么是equivalent features？

C. Extract Equivalence Information

等效信息提取：THANOS从所选存储引擎中提取等效性信息，以确保不同存储引擎的DBMS在测试中的一致性。这些等效信息用于处理各存储引擎的特性差异，确保在测试时涵盖所有存储引擎的相关功能。

等效性信息的组成：等效性信息（$F_{equivalent}$）包括各存储引擎共同支持的功能和那些所有引擎都不支持的特性。这些特性要么是所有存储引擎都支持的，要么是所有存储引擎都不支持的。

等效信息的计算：等效性信息通过两个集合的并集计算得出，一个集合是所有引擎共享的特性，另一个是所有引擎都缺少的特性。公式为：

其中，$U$为所有存储引擎的特性全集，$f_i$为第$i$个存储引擎的特性集。

等效性信息的应用：THANOS自动提取等效信息并生成等效DBMS的测试用例。这些信息用于构建测试用例，以检测DBMS在不同存储引擎下的行为一致性。

表格展示：THANOS提取了如InnoDB、MyISAM、Archive和Mroonga等存储引擎的等效信息，支持的特性包括数据类型、索引类型、分区、事务和加密等，用于生成测试用例。

D. Feature-Oriented Test Case Synthesis

测试用例生成：THANOS利用从存储引擎提取的等效性信息，系统性地生成特性导向的测试用例，这些用例激活并调度存储引擎的不同特性，确保在DBMS实例之间建立等效性。

标准和非标准SQL特性：测试用例包括标准SQL特性和非标准SQL特性。标准特性可以通过关键词或SQL语句表示，而非标准特性如CHECK TABLE和REPAIR TABLE等则通过非标准SQL语句表达。

测试用例结构：THANOS首先综合DDL（数据定义语言）来构建存储基础，如CREATE TABLE和CREATE INDEX语句。然后，生成DML（数据操作语言）和DQL（数据查询语言），执行存储引擎相关操作，如数据修改和查询。

元数据管理：为了确保测试的语义正确性，THANOS开发了元数据池，保留表、列、索引和数据类型等元数据，帮助生成具有语义正确的测试用例。

特性替换：THANOS将等效特性插入到SQL语句框架中，比如根据等效性信息将CREATE TABLE的节点替换为具体的数据类型。

执行测试：最终，THANOS将测试用例转换为可执行版本，通过指定的存储引擎运行这些用例，并在测试期间记录相关元数据，确保测试结果的一致性。

E. Discrepancy Analysis of Execution Results

在执行结果差异分析中，THANOS通过分发生成的测试用例并分析结果差异来检测DBMS中的正确性错误，具体分析三类信息差异：

查询结果差异：当测试用例包含查询语句（如SELECT）时，THANOS比较各个DBMS返回的查询结果，标记任何差异为潜在的正确性错误。在比较过程中，THANOS忽略了不同DBMS中数据返回顺序的差异。
错误消息差异：THANOS也会比较各个DBMS实例中生成的错误消息。如果错误消息存在差异，THANOS会记录并报告这些不一致，尤其是内容不同的错误信息。
数据库最终状态差异：THANOS在执行测试用例后会比较各个DBMS实例的数据库最终状态（如表的一致性）。任何不一致之处都会被记录为差异。

此外，THANOS采用了去重方法，首先将测试用例最小化以减少重复，然后记录每个测试用例的配置和输出。

F. Implementation

特性分类：THANOS根据官方DBMS文档，将存储引擎的特性分为10个主要类别：数据类型、索引类型、数据完整性、分区、加密、压缩、事务、健康检查、缓存、更新统计。每个类别包含约2到40个具体特性。

特性统计：对于每个存储引擎，THANOS统计各类别中的特性数量，并以“特性-存储引擎”作为最小计量单位，如BTree-MyISAM表示MyISAM存储引擎支持BTree索引。

基础元素：THANOS的基础元素包括选择适当的存储引擎（通过算法1详细说明）以及基于所选引擎共享的特性生成等效的测试用例（在算法2中描述）。

语法树模型：THANOS使用抽象语法树（AST）模型合成特性导向的测试用例，遵循SQL-2003标准，并利用BISON 3.3.2和FLEX生成解析器和词法分析器文件。

ODBC接口：为了防止不同存储引擎之间的干扰，THANOS通过ODBC客户端接口进行连接，实现统一的接口和调度，确保与每个等效DBMS的直接连接。

EVALUATION

RQ1: Can THANOS find DBMSs’ bugs?

RQ2: How does THANOS perform compared to other DBMS testing techniques?

RQ3: How effective is the feature-oriented test case synthesis algorithm?

A. Evaluation Setup

实验设置部分的主要内容如下：

测试的DBMS和比较的技术：THANOS在三个广泛使用的DBMS上进行测试，分别是MySQL、MariaDB和Percona。为了评估THANOS的有效性，作者将其与当前先进的DBMS测试工具进行了比较，包括SQUIRREL、SQLancer和SQLsmith。这些工具通过生成大量查询来检测崩溃和逻辑漏洞，SQUIRREL利用覆盖率引导SQL生成以检测崩溃错误。
实验环境：实验在运行64位Ubuntu 20.04的机器上进行，每个DBMS实例运行在Docker容器中，配置为5个CPU核心（AMD EPYC 7742 2.25GHz）和40GiB内存。三个测试的DBMS使用AFL++编译，用于收集覆盖率和反馈。

B. DBMS Bug Detection

在DBMS Bug Detection部分，THANOS在三周内成功检测到32个此前未知的漏洞，这些漏洞出现在MySQL、MariaDB和Percona这三个DBMS中，开发者确认了所有漏洞，没有误报。其中29个被评为关键漏洞。作者展示了THANOS在DBMS的多个组件中发现的漏洞分布情况和严重程度。

不同的DBMS对漏洞有不同的严重性定义，例如MySQL中的Critical，MariaDB中的Blocker，以及Percona中的Urgent等。THANOS不仅发现了存储引擎相关的漏洞，还检测到了与DBMS核心组件（如优化器和解析器）相关的问题。

THANOS通过存储引擎的轮换和广泛的测试暴露了DBMS中的漏洞，同时也触发了其他核心组件中的商业逻辑，揭示了更多的隐藏漏洞和脆弱性。

这个案例描述了THANOS检测到的MySQL查询结果不一致的问题。该问题通过执行相同的SQL测试用例，利用MySQL的不同存储引擎（InnoDB、MyISAM和Memory）触发。结果显示：

InnoDB返回空结果集；
MyISAM和Memory返回包含两行NULL值的结果集。

这种差异源于各存储引擎对NULL值的不同实现方式。当用户使用ALTER TABLE等命令改变存储引擎时，可能会导致这些不一致性，进而引发潜在的安全风险和业务逻辑问题。

此类问题对于现有的DBMS模糊测试工具（如SQUIRREL）和基于规则的工具（如SQLancer）较难检测，因为它们通常侧重于崩溃错误或依赖于特定规则，而THANOS通过对不同存储引擎的结果比较，能够有效发现这些差异。

这个案例描述了THANOS在MySQL中发现的一个错误消息不一致的问题。具体来说，CSV和Archive存储引擎都不支持B-tree索引，但当执行创建B-tree索引的SQL语句时：

CSV存储引擎返回了用户友好的错误消息，提示过多的键被指定。
Archive存储引擎则返回了模糊的未知错误消息“Unknown error”。

这种不一致性对于同样的问题应保持统一的错误提示，以确保用户能够理解并解决问题。开发者已经承认了这个问题，并计划修复。

此外，THANOS还发现了其他类似的问题，例如类似问题却有不同的错误代码。尽管这些问题对安全性影响较小，但它们对DBMS的可靠性和健壮性至关重要。当前的DBMS测试工具难以发现这些问题，而THANOS能够通过自动化测试检测出这些问题。

这个案例描述了THANOS在MariaDB的Mroonga存储引擎中发现的一个已隐藏近10年的问题。当使用Mroonga存储引擎执行测试时，服务器发生崩溃，而使用InnoDB等其他存储引擎则可以正常获取查询结果。具体来说，测试用例创建了一个包含触发器的表，并执行了UPDATE语句，最终导致MariaDB在Mroonga引擎上的崩溃。

通过调用堆栈信息分析，THANOS发现这个问题与Mroonga存储引擎处理AUTO_INCREMENT功能有关，而这部分代码已有10年未更新。THANOS通过存储引擎的轮换测试机制，成功检测到了这个长期未被发现的错误。传统的DBMS测试工具由于仅使用默认存储引擎，难以发现此类问题，而THANOS的存储引擎导向的等效DBMS构建使其能够识别出这个潜在的漏洞。

C. Comparison with Existing Techniques

THANOS与其他DBMS测试工具（SQLancer、SQLsmith和SQUIRREL）进行了比较。具体表现如下：

漏洞检测：THANOS在24小时内检测到的漏洞数量显著高于其他工具。THANOS共检测到14个漏洞，而SQLsmith检测到1个，SQUIRREL检测到3个，SQLancer未检测到任何漏洞。THANOS的14个漏洞均被开发者确认，其中大部分是以前未被发现的。
覆盖的代码分支：THANOS覆盖的代码分支数量也显著高于其他工具。THANOS覆盖了395,981个分支，比SQUIRREL、SQLsmith和SQLancer分别多23.72%、45.23%和115.95%。
原因分析：THANOS的优势主要源于其对存储引擎的深入测试。相比于其他工具主要测试默认存储引擎，THANOS测试了多种存储引擎，覆盖了更广泛的DBMS功能。此外，THANOS在生成测试用例时也包含了许多非标准SQL语法，进一步提高了其覆盖范围和漏洞检测能力。

THANOS的这种差异化方法使其能够测试更多DBMS的功能，从而在代码覆盖率和漏洞检测方面取得显著的提升。

D. Effectiveness of Feature-Oriented Test Case Synthesis

作者评估了其feature-oriented的测试用例合成算法的有效性，并与一个随机生成测试用例的工具（Thanos-）进行对比。结果显示，Thanos在MySQL、MariaDB和Percona中激活了更多的特征，并生成了更多与存储引擎相关的测试用例。

具体而言，Thanos在MySQL、MariaDB和Percona分别激活了187、273和214个更多的特征，比Thanos-高出16.14%、22.48%和17.60%。这一结果与预期一致，说明Thanos的特征导向合成算法可以触发DBMS中的更多存储引擎功能，而随机测试用例生成在这一方面较为低效，无法充分探索和激活多样的存储引擎功能。

DISCUSSION

在讨论部分，作者指出了THANOS适用于支持多存储引擎的DBMS。THANOS为8个常用存储引擎提供了特征列表模板，使其能够高效组织测试。作者提到，适应不同的存储引擎是一次性的手动工作，之后可以重复使用该模板。例如，收集MySQL特征约需6小时。

对于仅支持单一存储引擎的DBMS，THANOS可以通过构建等效DBMS进行测试，方法包括使用不同版本的存储引擎进行差异测试，或替换DBMS的其他组件。在未来，THANOS将扩展能力以支持单一存储引擎配置。

THANOS通过差异测试检测DBMS中的bug，表明约40%的bug（13/32）与存储引擎相关，其他则涉及DBMS核心组件，如Optimizer和Parser。