Squirrel：利用语义有效性和覆盖反馈来测试数据库管理系统

 

这是一篇会议论文，提出了针对DBMS的一种模糊测试框架SQUIRREL，效果显著优于其他的模糊器。

0 摘要

模糊测试是一种越来越流行的用于验证软件功能和寻找安全漏洞的技术。然而，现在的基于突变的模糊器（Fuzzer）不能有效地测试数据库管理系统（DBMS），因为数据库管理系统对于有效的语法和语义有着严格的检查。基于生成的测试可以保证输入的语法正确性，但是它不利用任何反馈（例如代码覆盖率）来指导路径探索。

在本文中，我们开发了SQUIRREL，这是一个新颖的模糊框架，考虑了语言的有效性和覆盖反馈来测试数据库管理系统。我们设计了一个中间表示（IR），以结构化和信息丰富的方式维护SQL查询。为了生成语法正确的查询，我们在IR上执行基于类型的突变，包括语句插入，删除和替换。为了减轻语义错误，我们通过分析每个IR来确定参数之间的逻辑依赖性，然后生成满足这些依赖性的查询。我们在四个流行的数据库管理系统上测试了SQUIRREL：SQLite,MySQL,PostgreSQL,MariaDB。SQUIRREL发现了SQLite的51个漏洞，MySQL和MariaDB则分别是7个和5个。其中，有52个是已经修复了的，有12个具有CVE编号。在我们的实验中，与最新的模糊测试相比，SQUIRREL的语义正确性提高了2.4-243.9倍，与基于变异的工具相比，它所探寻的新边缘（Edges）增加了2.0-10.9倍。这些结果表明，SQUIRREL可有效地发现数据库管理系统中的内存错误。

 

1 介绍

数据库管理系统（DBMS）是现代数据密集型系统的组成部分。与所有其他复杂系统一样，DBMS也会出现许多错误，这些错误不仅会影响其功能，而且还可能导致恶意攻击。在所有威胁中，臭名昭著的内存错误漏洞使攻击者能够泄漏甚至破坏正在运行的DBMS进程的内存，这最终可能导致远程代码执行，数据库违规（breach），或者拒绝服务。例如，最近的“Collection＃1”数据泄露揭示了7.73亿个电子邮件地址和210亿个密码。

基于生成的测试技术是DBMS的事实上的错误查找工具，这些技术要求开发人员创建一个正式模型，以精确地定义SQL（结构化查询语言）。该工具基于该模型枚举所有可能的SQL查询，以验证DBMS的功能或查找错误。 但是，基于生成的测试工具的有效性有限，因为它们将工作量平均分配给每个SQL查询。考虑到无限的输入空间和罕见的错误触发查询，这种类似蛮力的枚举无法有效地从DBMS中查找内存错误漏洞。

近年来，模糊测试已被广泛用作检测内存错误漏洞的软件测试技术。与基于生成的测试不同，模糊测试依靠随机突变来创建新的测试用例，并利用诸如代码覆盖率之类的反馈来指导输入空间探索。从种子主体开始，模糊器会随机更改现有输入（例如翻转几位）以生成略有不同的变体。它使用新的输入运行目标程序，并检测异常行为，例如执行崩溃和断言失败。 在执行期间，模糊器还会记录代码路径信息，例如执行的块或分支。触发新代码路径的输入具有更高的优先级，可以选择用于另一轮变异。通过花费大量的精力来提高模糊的效率和功效，模糊器已经成功地从流行的应用程序中发现了数千个错误。

但是，将模糊测试技术用于测试DBMS具有挑战性，因为DBMS在执行SQL查询之前执行两项正确性检查，即语法检查和语义检查。 具体来说，DBMS首先解析每个SQL查询以获得其语法含义。 如果查询中有任何语法错误，则DBMS将停止执行，并立即通过错误消息来提示。 否则，DBMS会进一步检查查询中是否存在语义错误，例如使用不存在的表，并且在出现语义错误的任何情况下会停止。 经过这两项检查后，DBMS将创建多个执行计划，并选择最有效的执行计划来执行查询。 因此，为了达到DBMS的深层逻辑，查询应在语法和语义上正确。

当前的模糊测试技术使用的随机字节突变无法轻易生成语法正确或语义正确的输入。 例如，基于突变的代表性模糊器AFL 可以在24小时内生成2000万个SQLite 查询，但只有30％的查询可以通过语法检查，而4％的查询具有正确的语义。 但是，大多数DBMS代码负责查询计划的构建，优化和执行，只有一小部分用于语法检查和语义检查。 例如，AFL生成的20,000个语义正确查询触发了SQLite中的19,291条代码分支，而相同数量的语法错误查询仅覆盖9,809条分支，仅占前者的50.8％。 因此，当前的模糊技术无法触发DBMS的深层逻辑，也无法全面探索程序状态。

在本文中，我们提出了一个Squirrel系统来应对这些挑战，以便我们可以有效地模糊DBMS。 我们的系统嵌入了两项关键技术，即保留语法的变异和基于语义的实例化。为了生成语法正确的SQL查询，我们设计了一个中间表示（IR），以结构化和信息丰富的方式维护查询。每个IR语句最多包含两个操作数，每个操作数也是另一个IR语句。每个IR具有指示语法结构（例如，SELECT a FROM b）的结构类型和数据类型（例如，表名称）。进行突变之前，我们的系统会从IR中剥离具体数据，仅保留操作的框架。然后，我们执行三个随机突变，包括插入类型匹配的操作数，删除可选操作数或用其他类型匹配的操作数替换操作数。基于类型的变异确保了生成的查询具有正确的语法。接下来，我们执行查询分析以找出不同IR数据之间的预期依赖关系。例如，SELECT子句中的数据应该是FROM子句中表的列。我们用具体数据填充每个剥离的IR，并确保它们满足所有预期的依赖性。最后，我们将IR转换回SQL，并将其提供给DBMS进行测试。 Squirrel结合了基于覆盖的模糊测试（即指导性探索）和基于模型的生成（即高语言正确性）的优势，因此可以触发DBMS的深层逻辑并发现严重的错误。

我们用43,783行C ++代码实现了Squirrel，主要集中在保留语法的变异和语义指导的实例化上。 我们将AFL的代码重复用于覆盖率收集和输入优先级划分。 我们对Squirrel的设计是通用的，经过一些工程工作，它应该可以与其他模糊测试器一起使用。

为了了解我们系统的有效性，我们使用Squirrel测试了四个流行的DBMS：SQLite，MySQL，PostgreSQL和MariaDB。 Squirrel在40天内成功发现了63个内存错误问题，其中包括SQLite中的51个错误，MySQL中的7个错误和MariaDB中的5个错误。 相比之下，Google OSS-Fuzz在40个月内检测到19个来自SQLite的错误，在5个月内检测到来自MySQL的15个错误。 我们已经以负责任的态度向DBMS开发人员报告了所有这些错误，并获得了积极的反馈。 在撰写本文时，已修复了52个错误。 由于严重的安全后果，例如窃取数据库内容，我们甚至可以获得12个错误的CVE编号。

我们检查了模糊测试的各个方面，并将Squirrel与其他先进的工具进行了比较，包括基于突变的模糊器AFL和Angora，基于生成的工具SQLsmith，结构模糊器GRIMOIRE和混合模糊器QSYM。 在24小时的测试过程中，Squirrel成功地发现了9个独特的错误，而其他错误则检测到了一个或零个错误。 与基于突变的工具相比，Squirrel发现了2.0-10.9倍的新边缘，并且获得了与基于生成的测试器SQLsmith相当的结果。 与其他工具相比，它的语义正确性也高2.4-243.9倍。

我们在本文中做出了以下贡献：

• 我们提出了保留语法的变异和语义指导的实例化，以解决使DBMS模糊化的挑战。

• 我们实现了Squirrel，这是一个将变异和生成结合起来以检测DBMS错误的端到端系统。

• 我们在实际的DBMS上评估了Squirrel，并确定了63个内存错误问题。 结果表明，在从DBMS查找错误时，Squirrel优于现有工具。

我们计划发布Squirrel的代码，以帮助DBMS开发人员测试其产品，并加强对DBMS安全的未来研究。

 

2 问题定义（Problem Definition）

在本节中，我们首先简要描述DBMS如何处理SQL查询。 然后，我们介绍现有的DBMS测试技术，并说明它们在查找深层逻辑中的隐藏错误时的局限性。 最后，我们提出解决这一问题的见解。

2.1 DBMS中的查询过程

图1：测试DBMS的挑战.DBMS采取四个步骤来处理一个SQL查询。 其中，parse检查语法正确性，而validation检查语义有效性。 随机变异不太可能保证语法正确性，而基于语法的生成可能无法确保语义正确性。

现代DBMS通常以四个阶段处理SQL查询：解析，验证，优化和执行，如图1所示。在收到SQL查询之后，DBMS首先解析查询以获取其语法含义。解析器将查询分解为单独的标记，并对照语法规则检查它们。如果检测到任何语法错误，DBMS将立即终止执行并将错误消息返回给客户端。其次，DBMS在验证阶段检查查询的语义正确性，例如数据库中是否存在表或表中的列是否明确。在此阶段可以检测到大多数语义错误。接下来，在优化阶段，查询优化器构造几种可能的查询计划，并尝试确定执行给定查询的最有效计划。最后，DBMS在数据库上执行选定的计划，并将结果发送回客户端。因此，仅在查询语法正确的情况下，执行才会进入第二阶段，而在查询语义正确的情况下，执行将进入最后两个短语。

Motivating Example. 图1中的“原始查询”首先连接两个表t1和t2，并搜索t1的c1列与t2的c5列相同的行。 对于每个匹配的行，查询将返回c2和c6的值。 DBMS发现此查询通过了语法检查和语义检查。 它在数据库中搜索，最后返回“ alice read”。

2.2 测试DBMS的难点

生成SQL查询以测试DBMS的方法主要有两种：基于模型的生成和随机变异。 基于模型的生成遵循精确的语法模型，因此可以构造语法正确的输入。 例如，流行的DBMS测试工具SQLsmith直接从抽象语法树（AST）生成语法正确的测试用例。但是，在没有任何指导的情况下，基于模型的生成顺序扫描整个输入空间。考虑到许多查询是由DBMS以相同的方式处理的，因此该方法无法有效地探索程序的状态空间。 此外，基于生成的方法几乎不能保证语义的正确性，并且在验证过程中，DBMS会过滤掉语义不正确的查询。 图1显示了由生成器（生成后）构造的查询。 尽管此查询在语法上是正确的，但由于当前数据库中不存在WHERE子句中的表t3，因此无法执行该查询。

随机突变更新现有输入以生成新输入。为了提高性能，模糊器利用先前执行的反馈来评估生成输入的优先级。如果反馈指示先前的输入很有趣，例如触发新的执行路径，则模糊测试人员会将其放入队列中以进行进一步的更改。这样，模糊测试者将收集越来越多有趣的测试用例，从而可以有效地探索程序的状态空间。统计数据表明，在许多软件中，具有反馈驱动的随机突变效果很好。例如，谷歌通过基于反馈的基于突变的模糊器发现了5,000多个漏洞。但是，盲语法突变策略在处理结构化输入（例如SQL和JavaScript）方面效率较低。例如，随机翻转SQL关键字的位几乎不会产生另一个有效关键字，并且整个查询在语法上将变得不正确。图1显示了这种情况（突变后），其中将SELECT中S的最后一位翻转会导致无效的关键字RELECT。 DBMS将在解析阶段拒绝新查询。

我们设计评估以了解AFL生成的SQL查询的质量以及语法正确性和语义正确性的重要性。 具体来说，我们使用AFL在24小时内测试SQLite，这会生成2000万个查询。 但是，只有大约30％的语法正确，只有4％的语法可以通过语义检查。 我们随机选择了20,000个语义正确的查询，并发现它们在SQLite中触发了19,291个不同的代码分支。 相同数量的语法不正确和语义不正确的查询分别分别到达9,809和12,811个分支。 这些结果表明：AFL生成的查询的验证率较低，以及语义正确性对于探索程序状态空间的重要性。

2.3 我们的解决方法

本文的想法是将语法正确和语义感知的变异引入模糊测试中，以便我们可以利用基于变异的技术和基于生成的机制来最大化测试DBMS的能力。

生成语法正确的查询： 我们设计了一个新的中间表示（IR），以结构化和信息化的方式维护SQL查询，并采用基于类型的变异来保证语法的正确性。 每个IR语句最多只包含两个操作数，因此，我们的突变只需要处理两个值。 每个语句都有一个关联的语法类型，例如SELECT语句的SelectStmt，而每个数据都有一个语义类型，例如表名。 我们的变异执行基于类型的操作，包括插入类型匹配的操作数、删除可选操作数以及用类型匹配的操作数替换操作数。 我们从每个IR中剥离具体数据（如表名），以专注于骨架的变异。 基于IR的突变有效地保留了语法正确性。 一些基于生成的工具从AST生成SQL查询。 但是，由于严格的类型约束和复杂的操作，对AST进行更改与修改SQL查询同样具有挑战性。

提高语义的正确性： 由于确保生成的SQL查询的语义正确性被证明是NP-hard的，因此我们将尝试实际的解决方案以尽可能提高语义正确性。 现有的基于生成的工具定义了一组查询模板。 每个模板代表一个完整的查询，并包含操作数之间的特定静态约束。 但是，由于人力有限，这些框架无法保证其SQL模板的可表达性。 我们通过动态查询实例化解决了这个问题。 给定语法正确的SQL查询的骨架（即没有具体的操作数），我们的方法首先根据预定义的基本规则构建其数据依赖图。 例如，SELECT的操作数可以是FROM中使用的表的列名。 然后，我们尝试用关系满足数据依赖图的具体操作数填充骨架。 通过实例化，语义正确率足以测试DBMS。

3 Squirrel概览

图2：SQUIRREL概览，Squirrel旨在查找使DBMS崩溃的查询。 Squirrel首先将查询从SQL转换为IR； 然后，它使IR突变以生成新骨架。 接着用具体的操作数填充骨架。 最后，它运行新查询并检测错误。

图2概述了我们的DBMS测试框架Squirrel。给定一组正常的SQL查询，Squirrel的目标是查找使DBMS崩溃执行的查询。查询意味着一个测试用例，并且可能包含多个SQL语句。 Squirrel从一个空的数据库开始，并且需要查询来创建内容。 Squirrel通过四个关键组件来实现其目标：Translator，Mutator，Instantiator和SQL Fuzzer。首先，Squirrel从包含初始查询和保存的有趣查询的队列中选择一个查询。然后，Translator将查询I转换为IR的向量V。同时，转换器将中的具体值剥离，以使其成为查询框架。我们的Mutator通过插入，删除和替换来产生新的IR向量'–'在语法上是正确的。接下来，我们的Instantiator执行'的数据依赖关系分析，并建立一个数据依赖关系图。然后，Instantiator选择满足数据依赖性的新具体值，并用这些值填充'。由于满足了数据依赖性，所以，'在语义上可能是正确的。最后，我们将'转换回SQL查询'并在DBMS中执行'查询。如果执行崩溃，我们将找到触发错误的输入。否则，如果'触发了程序的新执行路径，我们会将其保存到队列中以进行进一步的变异。

4 中间表示

我们设计SQL的中间表示（IR）以支持语法正确的查询变异。 我们将每个查询从SQL转换为IR，对IR进行突变，然后将新的IR转换回SQL查询以执行。 我们对IR的设计旨在实现三个目标：IR可以代表任何SQL语句（表达性）； 中间表示IR的格式和运作是统一的（一般性）； IR和SQL之间的转换非常有效（简单性）。

IR采用静态单一分配（SSA）形式。 一个查询或测试用例包含一个或多个IR语句。 每个语句都是一个赋值，其中左侧是目标变量，右侧是文字或带操作数的运算符。 我们在IR中添加以下字段以存储必要的信息。

ir_type: 一个IR语句的类型。 此类型基于AST中的相应节点，例如列名称的colum类型或表达式的expr类型。 我们还定义了一个特殊类型“Unknown”来表示在AST中没有相应节点的中间语句。

operator: 由SQL关键字和数学运算符组成。 它指示IR执行的操作，包括三部分：前缀op_prefix，间缀 op_mid和后缀op_suffix。 例如，“ CREATE trigger BEGIN list END”的IR带有前缀CREATE，间缀BEGIN和后缀END。

left_operand, right_operand: IR运算符的操作数。 操作数是另一个IR语句，或者操作数是可选的或不需要的话，则可以为NULL。

data_value: IR携带的具体数据，例如表名t1。

data_type: 数据类型，如ColumnName就代表列名。

我们在附录A中提供了IR语法的正式定义。下面是SQL语句“SELECT c2，c6 FROM t1，t2 WHERE t1.c1 = t2.c5”的IR示例：

图3：执行SQL查询的IR示例。相关的AST语法树见图4.

图4：执行示例的AST语法树。Squirrel解析SQL查询并以AST表示它，最后将AST转换为IR。

图3显示了图1中的有效示例的IR（原始查询）。 图4中给出了相应的AST。V1和V4表示列名称c2和c6，它们对应于图4中的节点1和4。它们不包含任何运算符或操作数，但具有ColumnName数据类型和适当的数据值 。 V2和V5定义对列（V1和V4）的引用，而V3和V6创建两个表达式，它们每个只有一个操作数。 V7描述了SELECT的参数列表，包括c2和c6。 V8代表SELECT子句，它可以将DISTINCT作为其左操作数（此处为NULL）。 SELECT出现在左操作数之前，因此它是运算符前缀。 由于我们的IR最多只允许两个操作数，因此我们必须使用两个中间节点Va和Vb连接三个节点8、14和25来构造SelectStmt的IR。 它们的ir_types设置为“Unknown”。 最后，V26定义了SELECT语句，它是图4中的节点26。

我们的IR只是一系列分配语句。 这种线性表示形式不同于树或图形结构（如AST），可帮助开发人员采用统一且简单的突变策略。 我们可以在保持语法正确性的同时执行语句的插入，删除和替换。 我们在附录B中介绍了有关SQL查询和IR之间转换的算法。

5 保留语法的变异

我们根据功能将SQL查询中的令牌分为两组。 SQL关键字和数学运算符定义要执行的操作，我们称这些标记为结构令牌。 其他标记指定已定义操作的目标，我们称它们为数据令牌。 数据可以是具有基本意义的文字，例如常量1，也可以表示语义，例如表名。

我们观察到，更改结构令牌比更改数据令牌对DBMS执行的影响更大。 差异来自两个原因。 首先，更改结构将更改查询的操作，从而触发不同的功能，而DBMS可能使用相同的逻辑来处理不同的文字数据。 例如，SQLite使用几乎相同的路径来处理查询A：“ SELECT c FROM t WHERE c = 1”和查询B：“ SELECT c FROM t WHERE c = 10”，但是使用明显不同的代码来处理查询C：“ SELECT c FROM t WHERE c>1“开始。 其次，随机修改与语义相关的数据很可能会生成一个语义上不正确的查询，DBMS将拒绝执行该查询。 例如，用另一个表中的列替换查询A中的c会导致无效查询。 无论哪种情况，随机数据突变的效率都低于随机结构突变。

因此，我们从查询IR中剥离数据，并将变异主要应用于结构。 我们将在第6部分中讲数据修改。

5.1 数据结构分离

我们遍历IR，根据类型为data_type的预定义值替换每个数据。 具体来说，我们将语义数据替换为字符串“ x”，将常数更改为1或1.0，并将所有字符串更新为“ a”。 因此，在分离之后，正在运行的示例“ SELECT t2，c6 FROM t1，t2 WHERE t1.c1 = t2.c5”变为“ SELECT x，x FROM x，x，WHERE x.x = x.x”。 查询A和B都变为“ SELECT x FROM x WHERE x = 1”，而查询C更改为“ SELECT x FROM x WHERE x> 1”。

在库中存储IR： 我们使用称为IR库的字典来存储各种IR。 字典的键是IR类型，而值是IR列表。 一个列表中的IR具有相同的类型，并且其结构完全不同。 例如，分离后，查询A，B和C具有相同的SelectStmt类型，它们应存储在相同的列表中。 我们从列表中删除查询B，因为它与A具有相同的结构。每当我们需要某种类型的IR时，我们都会从字典中找到相应的列表并随机返回一个元素。 在图2中，Squirrel接受种子查询以初始化IR库。 只要Squirrel发现生成的IR具有新结构，我们就会将其添加到库中的相应列表中。 我们对库中IR的最大数量设置了限制，以避免过多的内存使用。

5.2 基于类型的变异

我们定义了一组基于类型的突变，以更新IR或IR本身的左右操作数。 我们的突变集中在操作数上，因为IR的其他成员不能轻易更改：该运算符与IR类型密切相关，就像SelectClause IR中的SELECT运算符一样，而data_type由其在查询中的位置决定，例如“ CREATE TABLE”必须是表名。 因此，我们的突变要么作用于整个IR，要么修改其操作数。 具体来说，对于IR程序中的每个IR :v，我们都以一定的概率执行以下突变：

插入：将IR添加到v的适当位置。 如果v的左孩子节点为空，我们从IR库中随机选择一个与v共享相同类型的IR w。 如果w的左孩子节点不为空，我们将其用作v的左孩子。 相同的操作适用于右孩子节点。

替换： 更改v或其操作数。 我们首先从IR库中随机选择一个与类型相同的IR w。 然后，我们将w的孩子复制到v，或者将v替换为w，并将所有v的引用更新为w。

删除： 只需将一个IR–v替换为一个空的IR即可整体删除它。 可以对其子代执行相同的操作。

由于我们实质上是根据IR的类型来操作IR，因此语法正确性被保留的可能性很高。 为了进一步提高语法的正确性，我们将变异的IR转换回SQL查询，并使用解析器执行语法验证。 如果解析成功，我们得出结论该查询没有语法错误，将在下一阶段使用它。 否则，我们将丢弃新的IR，然后尝试生成另一个IR。

图5：IR程序的变异策略，包括基于类型的插入和替换，以及可选操作数的删除。

图5显示了对正在运行的示例的IR进行变异以生成三个新查询的示例。 具体来说，我们在V26的右子元素中插入ORDERBY子句，（因为）； 我们用CountClause替换V8的右子元素，其中新查询将对原始结果的行进行计数； 我们删除Vb的右子元素以有效删除WHERE子句。 这三个新的IR在语法上都是正确的。 UnknownType： 正如我们在§4中提到的，某些IR的类型为Unknown，因为它们在AST中没有相应的节点。 我们使用Unknown类型执行模糊类型匹配，而无需搜索具体类型，这可以加快查询的生成速度。 始终需要一次性解析的语法验证不受影响。 但是，如果没有精确的类型匹配，Squirrel可能会创建一些无效的查询。

6 语义引导实例化

语义正确的查询使模糊测试者可以深入了解DBMS的执行逻辑并有效地发现错误。 但是，对于模糊处理采用结构化，语义绑定输入的程序，生成语义正确的测试用例是一项尚未解决的挑战[44]。 先前的研究表明，由jsfunfuzz（一种最先进的JavaScript模糊器）生成的测试用例在语义上是无效的。 DBMS测试中也存在类似的问题。 我们提出一种数据实例化算法，以提高生成的SQL查询的语义正确性。 如§5所述，在进行突变后，IR程序是语法正确的框架，其中删除了数据。 我们的实例化程序首先分析不同数据之间的依赖关系，然后用满足所有依赖关系的具体值填充骨架。 实例化之后，查询很有可能在语义上是正确的。

6.1 数据依赖推断

图6：数据依赖示例。 该示例由三个新的CREATE语句和我们正在运行的示例组成。 在“Relation”中，我们显示两种类型的关系：“ isAnElement”（虚线）和“ isA”（实线）。

数据依赖性描述了语义绑定数据之间的关系。 任何不满足的依赖关系都将使查询无法通过语义检查。 图6显示了四个SQL语句之间的数据依赖关系，包括三个CREATE语句和我们的执行示例。 我们的语法正确的变异已将每个变量替换为x。 为了区分不同的x，我们为每个x分配一个索引。 这四个语句包含两种类型的关系：一种定义A是B（isAnElement）的元素，如x2所示的灰色虚线表示x1的列； 另一个描述A可以是B（isA），如x12所示的黑色实线可以是x1。

我们定义了一组规则，以自动推断查询中数据之间的依赖关系。 这些规则遵循两个原则。 生存期原则要求我们在使用SQL变量之前先创建它们，并在删除变量后停止使用它。 定制原则要求我们考虑数据类型，范围和操作来确定关系。 我们需要完善§4中提到的数据类型，以准确描述数据依赖性。

数据类型： 我们优化每种数据类型，以便它不仅描述语义含义，而且反映使用上下文。即使使用相同的基本类型，不同语句中的数据库元素也可以具有不同的依赖关系。基于生命周期原理，我们将定义/使用信息包含在数据类型中，以指示元素是新定义还是现有定义的使用。例如，CREATE TABLE子句中的表将具有CreateTable类型，而FROM子句中的表将具有UseTable类型。根据自定义原则，我们还包括数据范围，以显示在哪里可以找到潜在的候选值。例如，FROM子句中的表可以是任何已定义的表，因此具有UseAnyTable类型，而WHERE子句中的表必须是FROM子句中的表之一，因此具有UseFromTable类型。变量的精确数据类型取决于其在AST中的位置。因此，Squirrel在查询解析和转换期间识别并设置数据类型。

图6显示了每个IR数据的精确类型。例如，x1是一个新定义的表，因此类型为CreateTable。 x2和x3的类型为CreateColumn。 x12具有UseAnyTable类型，因为它可以是任何已定义的表（x1，x4，x7），而x14只能是FROM子句中列出的表。 x10可以是FROM中表的任何列，而x15只能是表x14中的列。

数据关系规则：使用精炼的数据类型，我们可以进一步定义数据关系规则，以帮助自动推断数据依赖性。 关系规则是四个元素的元组（A，B，C，D） ：A是关系目标，B是关系源；C定义关系；D表示关系的范围， 包括针对同一语句中的关系的intraStmt，针对多个语句的关系的interStmt，对于任何实例都适用，而对于根据Define-Use链最短路径的元素而言，最接近。 我们为所有DBMS定义了八条通用规则，为SQLite定义了一条附加规则，为MySQL定义了两条附加规则，为MariaDB附加了两条附加规则，为PostgreSQL附加了一条附加规则。 例如，关系规则（UseFromTable，UseTableColumn，isAnElement，nearest）意味着UseTableColumn类型的数据是同一语句中具有UseFromTable类型的最近数据的元素。 在图6中，我们可以使用此关系规则推断x15和x14之间的关系。

依赖图： 利用数据类型和关系，Squirrel会为每个突变的IR程序自动构造一个依赖图G = {V,E}。 中的每个节点都是IR数据及其数据类型。 E中的每个边缘描述了从边缘源到目标的一种关系。 如果数据类型可能依赖于两种或多种数据类型，我们将随机选择一种以避免循环依赖。 另外，如果有多个候选值用于从属类型，Squirrel会随机选择一个以建立边。 这样，图中的每个节点最多具有一个父节点，并且依赖图形成为一棵树或几棵树。 附录C包含有关依赖关系图构造的更多详细信息。

图7：IR结构的实例化。我们从图6的依赖关系创建一个具体的依赖关系图，替换所有占位符x，最后得到一个具体的新查询。

图7显示了从图6构建的一种可能的依赖关系图。例如，我们选择x1作为x12的依赖关系，尽管根据图6，它可以是（x1，x4，x7）中的任何一个。基于不同的选择，我们可以为每个突变的IR创建多个具体的数据依赖图。 有一些细节未在图中显示，例如x10应该是x2和x3之一。 Squirrel可以正确处理这些隐式依赖性。

6.2 IR实例化

算法1：语义实例化

Squirrel通过填写具体数据来实例化查询。算法1显示了我们的实例化算法。对于依赖关系图中的每棵树，我们都基于广度优先搜索和语句顺序对节点进行排序，从而保证了生命周期的正确性。对于整数之类的文字数据，我们将其设置为随机值或预定义值集中的一个（第5行）。对于语义绑定数据，我们填写适当的有效名称。在此过程中，我们维护两个映射：dataMap跟踪具有不同类型的唯一名称，而RelationMap将每个元素映射到其依赖项。如果当前节点没有依赖项（第6行），则它要么定义一个新变量（我们在其中创建一个新的唯一字符串作为其名称）（第7-9行），要么是一个预定义的术语，例如函数名（第10-行） 13）。如果当前节点有一个父节点，我们就知道它有一些依赖关系（第15-27行）：如果当前节点创建了一个新变量，我们只需为其生成一个唯一的字符串（第16-19行）；如果当前节点使用变量，则我们检查RelationMap为其找到合适的值（第22-23行）。最后，我们将IR程序转换回SQL查询并返回。如果由于不满意的依赖关系导致该过程失败，则IR程序将包含语义错误。

图7显示了数据和列值实例化的结果以及最终的SQL查询。 Squirrel将v1分配给x1，因为它是不依赖的CreateTable。 由于语句的顺序，我们接下来处理x2和x3并分别为其分配名称v2和v3。 我们以类似的方式处理x4-x9。 对于x12，它的类型为UseAnyTable，并且依赖于x1，因此根据算法1的第23行，我们将x1的名称v1分配给x12。 其他数据可以用相同的方式实例化。

7 实现

我们用43783行代码实现了Squirrel。表1显示了不同组件的细分。

表1：SQUIRREL组件的代码大小，共43783行

AST解析器。我们设计了一个通用的AST解析器来处理不同DBMS的通用功能，并为每个DBMS自定义解析器以支持特定于实现的功能。我们的实现基于Bison 3.3.2和Flex 2.6.4。我们的AST解析器的语法符合官方DBMS文档中描述的规范。我们支持该规范中的大多数语法，但是不涉及与管理功能相关的某些部分。通过这种方式，我们可以专注于测试与数据库操作有关的那些语法。

模糊器。我们在AFL 2.56b之上构建Squirrel，并用保留语法的mutator和语义指导的实例化器替换其mutator。当模糊器发现一个有趣的测试用例时，我们将其剥离的IR保存到IR库中。我们在每个查询之后删除数据库，以最大程度地减少不同查询之间的相互作用。

应用效果。将Squirrel应用于其他DBMS的工作可能取决于DBMS。首先，我们应该自定义通用解析器以支持目标DBMS的独特功能。其次，我们将根据语法编写语义关系规则。第三，如果DBMS在客户端-服务器模式下运行（例如MySQL和PostgreSQL），我们需要为其实现一个客户端。在我们的案例中，我们的一位作者花了一天的时间来定制解析器，而花了不到六个小时的时间来为我们测试的每个DBMS实施语义规则和客户端。我们认为，将Squirrel应用于另一个DBMS最多需要两天的时间。

8 评估

我们在实际的关系DBMS上测试了Squirrel，以了解其在查找内存错误中的有效性。 具体来说，我们的评估旨在回答以下问题：

• Squirrel是否可以检测来自实际生产级别DBMS的内存错误？ （§8.1）

• Squirrel是否可以胜过最新的测试工具？ （§8.2）

• DBMS测试中基于语言正确性和覆盖范围的反馈有哪些贡献？ （§8.3）

基准: 我们选择三种广泛使用的DBMS进行广泛评估，包括SQLite ，PostgreSQL ，MySQL。我们还使用Squirrel测试了MariaDB ，仅用于查找错误。我们使用默认的配置和编译选项来编译它们。我们将Squirrel与五个模糊器进行比较，包括基于突变的模糊器AFL 和Angora，混合模糊器QSYM ，结构模糊器GRIMOIRE和基于生成的模糊器SQLsmith。我们尝试运行尽可能多的测试，但是如表2所示，我们遇到了一些兼容性问题。由于MySQL需要客户端发送查询（即C / S模式），因此QSYM，Angora和GRIMOIRE无法直接对其进行测试。由于缺少接口，SQLsmith不正式支持MySQL。 PostgreSQL支持C / S模式和单一模式，我们可以使用QSYM在单一模式下对其进行测试。但是，GRIMOIRE无法将PostgreSQL成功编译为单个静态二进制文件。 Angora可以编译它，但不能运行二进制文件。我们正在积极寻求潜在的解决方案。

种子语料库： 我们从每个DBMS的官方Github存储库收集种子输入，其中单元测试通常涵盖大多数类型的查询。 我们向评估中的所有六个模糊器提供相同的种子，但SQLsmith不需要任何初始输入。

设置： 我们在装有Intel Xeon CPU E5-2690（2.90GHz），16核和188GB RAM的计算机上的Ubuntu 16.04系统中执行评估。 我们将afl-clang与llvm模式结合使用，以测试经过测试的DBMS，并采用边缘覆盖作为反馈。 考虑到DBMS的代码量很大，我们使用256K字节的位图来缓解路径冲突问题。 Angora使用1024K字节的位图，这是设计中的默认大小。 对于错误检测，由于时间限制和实施进度的原因，我们已经运行Squirrel来测试SQLite 40天，测试MySQLite和PostgreSQL 11天，以及MariaDB测试1天。 对于其他评估，我们将每个模糊测试实例（fuzzer + DBMS）运行24小时，然后重复该过程五次。 每个模糊测试实例都在具有一个CPU和10G内存的docker中单独运行。 我们报告平均结果以减少随机噪声，并在附录表6中提供p值。

8.1 DBMS Bugs

Squirrel已成功检测到来自经过测试的DBMS的63个错误，包括SQLite的51个错误，MySQL的7个错误和MariaDB的5个错误。表3列出了已发现的错误的详细信息。我们已将所有错误报告给了相应的DBMS开发人员，并收到了他们的积极反馈。在撰写本文时，已修复了所有错误中的52个。由于严重的安全后果，其中12个获得了CVE编号。相比之下，由Google发起的OSS-Fuzzer项目已经对第一个数据库管理系统进行了广泛的测试，并且在三年内发现了来自SQLite的19个错误，在四个月内发现了来自MySQL的15个错误，而没有来自PostgreSQL的错误。我们检查了OSS-Fuzzer检测到的MySQL错误，并发现所有错误均发生在MySQL逻辑的最开始：在解析阶段之前。概念验证（PoC）甚至不是有效的SQL查询，而只是一些随机位。因此，我们相信我们的模糊器可以更有效地发现来自DBMS的错误。我们计划将我们的工具集成到OSS-Fuzzer中，以提高DBMS的安全性。

表3：已检测到的错误。SQLite 3.31正在开发中，我们在Github上测试了最新版本。SQLite没有漏洞的严重性评分。表示严重性尚未由开发人员确定。

UAF: use-after-free. BOF: buffer overflow of Global(G), Heap(H), and Stack(S). BUF: buffer underflow. AF: assertion failure. OOM: ouf of memory. UB: undefined behavior.

ID	TYPE	FUNCTION	STATUS	SEVERITY	REFERENCE
SQLite v3.30.1,300K LoC
1	BOF	PRAGMA integrity_check	Fixed	Critical	CVE-2019-19646
2	NP	lookupName	Fixed	Critical	CVE-2019-19317
3	UAF	WITH	Fixed	High	CVE-2019-20218
4	BOF	exprListAppendList	Fixed	High	CVE-2019-19880
5	BOF	ZipFile extension	Fixed	High	CVE-2019-19959
6	NP	zipfileUpdate	Fixed	High	CVE-2019-19925
7	NP	parser	Fixed	High	CVE-2019-19926
8	NP	LEFT JOIN optimization	Fixed	High	CVE-2019-19923
9	SBOF	ALTER TABLE	Fixed	Medium	CVE-2019-19645
10	NP	JOIN INDEX	Fixed	Medium	CVE-2019-19242
11	NP	parser	Fixed	Medium	CVE-2019-19924
12	BOF	propagateConstantExprRewrite	Fixed	Medium	CVE-2020-6405
13	UB	fopen/fopen64	Fixed	–	0c4f820
14	GBOF	sqlite3VdbeMemPrettyPrint	Fixed	–	5ca0632
15	AF	sqlite3GenerateConstraintChecks	Fixed	–	ad5f157
16	AF	IN expression optimization	Fixed	–	b97f353
17	AF	whereLoopAddOr	Fixed	–	9a1f2e4
18	AF	WHERE with OR opt.	Fixed	–	a4b2df5
19	AF	wherePathSatisfiesOrderBy	Fixed	–	77c9b3c
20	AF	Bytecode OP_DeferredSeek	Fixed	–	be3da24
21	AF	WHERE	Fixed	–	4adb1d0
22	AF	WHERE flag setting	Fixed	–	118efd1
23	AF	Bytecode OP_ResultRow release	Fixed	–	02ff747
24	AF	sqlite3SelectReset	Fixed	–	aa328b6
25	AF	Bytecode OP_SCopy	Fixed	–	629b88c
26	AF	scalar subquery	Fixed	–	629b88c
27	AF	Bytecode OP_ResultRow	Fixed	–	02ff747
28	AF	SELECT	Fixed	–	fbb6e9f
29	AF	WHERE	Fixed	–	f1bb31e
30	AF	PRAGMA encoding	Fixed	–	b5f0e40
SQLite v3.31 (under development), 304K LoC
31	GBOF	ZipFile extension	Fixed	–	8d7f44c
32	HBOF	ZipFile extension	Fixed	–	a194d31
33	HBUF	ZipFile extension	Fixed	–	8d7f44c
34	UAF	sqlite3GenerateConstraintChecks	Fixed	–	6d67aff
35	NP	VTable	Fixed	–	c7a5ff4
36	NP	ORDER BY Windows Function	Fixed	–	73bacb7
37	NP	SF_Aggregate flag setting	Fixed	–	9e10f9a
38	NP	USING	Fixed	–	0824d5b
39	NP	ZipFile extension	Fixed	–	0d21eae
40	NP	LEFT JOIN uses values from IN	Fixed	–	74ebaad
41	AF	WHERE	Fixed	–	b592d47
42	AF	NEVER marco can be true	Fixed	–	78b5220
43	AF	impliesNotNullRow	Fixed	–	aef8167
44	AF	Code Generator for inline function	Fixed	–	25c4296
45	AF	scalar SELECT w/ WINDOW	Fixed	–	4ea562e
46	AF	Code Generator for sub query	Fixed	–	fc705da
47	AF	AND¸ optimization	Fixed	–	2b6e670
48	AF	Bytecode OP_Move	Fixed	–	4cbd847
49	AF	Bytecode OP_Copy-coalesce opt.	Fixed	–	9099688
50	AF	sqlite3ExprCodeIN	Fixed	–	f6ea97e
51	AF	whereTermPrint	Fixed	–	6411d65
MySQL v8.0, 4250K LoC
52	OOM	WITH optimization	Verified	Critical	ID98190
53	NP	JOIN optimization	Fixed	Serious	ID98119
54	NP	JOIN optimization	Verified	?	ID99438
55	NP	UPDATE optimization	Verified	?	ID99424
56	AF	SELECT	Verified	?	ID99420
57	AF	INDEX	Verified	?	ID99421
58	AF	CREATE TABLE	Verified	?	ID99454
MariaDB v10.5.3, 3641K LoC
59	BOF	UPDATE	Verified	?	MDEV22464
60	BOF	UPDATE	Verified	?	MDEV22476
61	AF	JOIN	Verified	?	MDEV22461
62	AF	SELECT	Verified	?	MDEV22462
63	AF	Array OOB	Verified	?	MDEV22463

错误多样性: 表3中的63个错误几乎涵盖了所有常见的内存错误类型，这表明Squirrel可以从多个方面提高DBMS安全性。 尤其是，通常认为缓冲区溢出和释放后重用的bug可以被利用，而Squirrel分别发现了12个bug和2个bug。 Squirrel还从SQLite中检测到33个断言失败，这表明执行已达到意外状态。 更糟糕的是，已发布的二进制文件中的断言检查被禁用，这可能导致严重的安全问题。 例如，在案例研究3中，断言失败会导致严重的事后使用漏洞。

案例研究1: 一个11年的Bug。 Squirrel检测到11年前引入SQLite的Bug（表3中的ID 16，附录1的清单1中的PoC），该错误位于IN子句的优化例程中。具体来说，isCandidateForInOpt检查各种条件以确定IN子句中的子查询是否可以优化。这些检查之一应确保子查询没有任何GROUP BY子句。由于SQL语法不允许IN子句中使用GROUP BY，因此开发人员无法为这种情况找到测试用例，因此通过签入将检查转换为assert（）[…] （2009-05-28）。在发布的SQLite版本中禁用了断言。 Squirrel发现，如果两个具有DISTINCT的查询通过NATURAL JOIN连接，则SQLite将在内部将GROUP BY属性设置为这些查询。在IN子句中使用此类查询时，它将使先前的断言失败。但是，发布的SQLite将错误地继续优化，并可能导致意外结果，例如错误结果。

Squirrel仅在14分钟内通过8个突变发现了这个11岁的bug。 图8显示了Squirrel从良性查询生成错误触发查询的八个步骤。 我们将表示为突变。 原始查询包含三个CREATE语句：第一个CREATE不必更改； 第二个CREATE被更改五次，其中有三个插入（1，，5和8）和两个替换（4和7）； 最后的CREATE更改了两次，分别有两次替换（2和6）和一次插入（3）。 每一轮突变都提供了新的语法结构，并保持了语法和语义的正确性。 最终查询满足断言失败的条件，因为SQLite会将最后一个SELECT放入第二条语句的IN中，这使IN的子查询包含两个自然连接的SELECTs。

案例研究2：数据库泄漏。 Squirrel确定了一个基于堆的缓冲区溢出漏洞（表3中的ID 5，附录2中的PoC），攻击者可以利用该漏洞读取内存空间中的任意数据。 此错误使攻击者有可能访问SQLite DBMS中存储的所有数据库。 由于SQLite被广泛用作多用户服务，因此攻击者可以检索其他用户的数据，这些用户默认情况下没有访问权限。 即使数据库的所有者明确删除了该数据库，攻击者仍然可以从其内存残留中窃取该数据库。 除了窃取数据库外，此错误还使攻击者能够读取敏感的关键信息，这些信息可能使攻击者能够进行进一步的攻击，例如远程执行代码。 例如，读取代码页地址将帮助攻击者绕过基于随机化的防御，而泄漏堆栈Canary将使堆栈缓冲区溢出再次可利用。

案例研究3：断言失败导致释放后重用。我们检查了几个断言失败，并发现了一个断言失败（表3中的ID 3，附录3中的PoC）最终导致了严重性高的释放后重用Bug（得分7.5 / 10）。断言确认只要执行到达断言点，谓词就始终为真。否则，开发人员会认为程序正在运行意外状态。此错误使SQLite失败了pParse-> pWith断言，因为由于无法创建圆形视图，pWith是一个悬空的指针。在调试模式下，SQLite将在断言失败后终止执行。但是，发布的二进制文件将禁用所有断言。有了触发错误的输入，SQLite将继续在意外状态下运行，并最终触发释放后使用的错误。

案例研究4：模糊测试作为回归测试。 Squirrel可以有效地发现新引入的错误，因此可以用于快速回归测试。例如，表3中ID为35的错误（附录中的清单4中的PoC）仅存在不到一天，然后才发现。 ID为38的Bug（附录5中的PoC）在存在后仅一小时内就被检测到，报告并修复。引入此错误的提交旨在解决与生成的列功能有关的另一个问题。但是，此修复程序并不完全正确，因此在USING子句中引入了新问题。这两个案例表明Squirrel可以对DBMS进行快速有效的回归测试。

8.2 与现有工具的对比

我们将Squirrel与五个不同方面的最新模糊测试器进行比较，以了解其在测试DBMS方面的优势和劣势。图9显示了我们的评估结果，包括唯一崩溃的次数，唯一错误的数目，新边缘的数目，语法正确性和语义正确性。我们评估的p值显示在附录表6中。大多数p值都小于0.05，这意味着Squirrel的结果与其他结果之间的差异具有统计意义。我们将逐案讨论异常的高p值。

图9：与现有工具的对比。图（a）和（b）显示了使SQLite模糊化的独特崩溃次数和独特错误数量。 图（c）-（k）显示了每个模糊实例的新边缘数，语法正确性和语义正确性。 我们将每个模糊测试实例运行24小时，将每个模糊测试重复五次，并报告平均结果。

唯一的崩溃：我们利用边缘覆盖图来计算唯一崩溃的次数，并在图9（a）中显示模糊SQLite的结果。我们排除了PostgreSQL和MySQL的结果，因为只有Squirrel在MySQL中发现很少crash，而其他模糊测试实例在24小时内都没有发现crash。 Squirrel在四分钟内检测到SQLite的第一次崩溃，总共检测到约600个唯一的崩溃。 AFL在32分钟内捕获了第一个crash，总共获得30次uniq crash，而QSYM在14分钟内发现了第一个crash，最终收集了13g个crashes。 Angora，GRIMOIRE和SQLsmith无法找到任何崩溃。

我们可以看到，最新的高级模糊测试工具并没有明显优于AFL。在某些情况下，他们甚至可能发现更少的唯一崩溃。我们认为，由于模糊的不确定性和对DBMS系统的严格语义要求，这种结果是合理的。

独特的错误: 我们会根据官方补丁将每次崩溃映射到相应的错误。在SQLite中，Squirrel发现的600个崩溃仅属于两个bug，而AFL检测到的30个崩溃和QSYM发现的13个崩溃属于同一个bug。由于少量的错误在统计上不是有用的，因此我们采取了不同的策略来获取更多的错误：每隔一个小时，我们会检查检测到的崩溃（如果有的话），将它们映射到真实的bug并进行patch，以避免以后发生类似的崩溃。我们在图9（b）中显示了新策略的结果。这种方法对于Squirrel查找更多错误（从两个到九个）非常有效，因为每次patch后，Squirrel几乎可以立即查找一个新的bug。 AFL和QSYM在一个小时内只能发现一个错误，即使进行patch也没有任何进展。表4显示了检测到的错误的分布，其中Squirrel还涵盖了AFL和QSYM发现的唯一错误。

New Edges: 与基于突变的工具相比，Squirrel可以识别出2.0×-10.9×的新边缘，并且可以获得与基于世代的测试器SQLsmith相当的结果。图9（c），（f）和（i）分别显示了SQLite（S），PostgreSQL（P）和MySQL（M）的新优势。 Squirrel在八项比较中胜过其他模糊测试：它比AFL多收集6.6×（S），4.4×（P）和2.0×（M）的新边，比SQLsmith，7.7×（S）多收集新的边，3.6×（S）和比QSYM高10.9倍（P），比安哥拉（Angora）高2.3倍（S），比GRIMOIRE高3.3倍（S）。唯一的例外是使用SQLsmith对PostgreSQL进行模糊处理，其中Squirrel通过SQLsmith收集了89.3％的新优势。考虑到SQLsmith是为处理PostgreSQL的特定语法而设计的，这不足为奇。由于SQLsmith在PostgreSQL上的性能略好于Squirrel，因此表6中的相关p值大于0.05。

语法有效性: Squirrel的语法正确性比基于突变的工具高1.8×-20.9×，并且获得与SQLsmith相当的结果。 图9（d），（g）和（j）分别显示了在测试SQLite（S），PostgreSQL（P）和MySQL（M）期间语法有效性的变化。 Squirrel的语法正确性比AFL高1.8倍（S），11.5倍（P）和2.5倍（M），比SQLsmith高6.1倍（S），比QSYM更高2.4倍（S）和20.9倍（P） 比Angora高×（S），比GRIMOIRE高2.9×（S）。 例外来自使用SQLsmith混淆PostgreSQL，其中Squirrel在语法上达到SQLsmith的97.1％。 同样，我们认为原因是SQLsmith是针对PostgreSQL的特定语法高度定制的。 例如，在模糊SQLite时，SQLsmith只能达到12.7％的语法正确性，而在模糊PostgreSQL时却可以获得近100％的语法准确性。 由于类似的结果，PostgreSQL上Squirrel与SQLsmith的p值大于0.05。

语义有效性: Squirrel的语义正确性比其他工具高2.4×-243.9×。图9（e），（h）和（k）分别显示了在测试SQLite（S），PostgreSQL（P）和MySQL（M）期间语义有效性的趋势。 Squirrel的语义正确率比AFL高8.3倍（S），7.0倍（P）和27.0倍（M），比SQLsmith分别高125.4倍（S）和243.9倍（P），8.8倍（S）和4.7倍（P） ）高于QSYM，比Angora高8.3×（S），比GRIMOIRE高2.4×（S）。有趣的是，尽管SQLsmith在测试PostgreSQL方面在新边缘和语法正确性方面表现稍佳，但Squirrel在语义上却获得了更高的准确性。另一个值得注意的观察结果是，AFL实际上为PostgreSQL比Squirrel生成了更多正确的输入（2.2x，请参阅附录中的表7），但仍然实现了较低的边缘覆盖率。这表明更多的正确查询或更高的正确率不能保证探索更多的程序状态。一个极端的例子是继续使用相同的正确查询，这将具有更多的执行次数（无生成开销）和100％的正确性。但是显然，它不会导致代码覆盖率的增加。 Squirrel的优势既来自保留各种语法的变异，也源自语义指导的实例化，后者推断参数之间的语义关系以协助查询合成。

总体而言，Squirrel的性能优于所有基于变异的工具，即使它们通过污点分析或符号执行加以增强，或将结构信息也考虑在内。 它可以达到与为PostgreSQL定制的SQLsmith相当的结果。 更重要的是，与所有其他经过测试的工具相比，Squirrel可以检测到明显更多的错误。

8.3 有效性和反馈

为了了解Squirrel中不同因素的作用，特别是保留语法的变异，语义指导的实例化和基于覆盖率的反馈，我们通过禁用每个因素并测量模糊过程的各个方面来执行单元测试。 结果在图10中给出。在Squirrel [!semantic]中，我们仅禁用了语义指导的实例化；仅启用了基于语义的实例化。 在Squirrel [!feedback]中，我们仅禁用基于coverage的反馈； Squirrel [!syntax＆!semantic]禁用语义引导的实例化和语法正确的突变，并且实际上与AFL相同。 由于语义指导的实例化需要语法正确的查询，因此我们无法创建仅禁用突变的版本。 我们还排除了所有禁用的设置，这将是AFL的哑模式。

表6中显示了我们评估的p值。大多数p值均小于0.05，这表明Squirrel的结果与其他结果之间的差异具有统计学意义。 我们将解释高于0.05的特殊p值。

图10：有效性和反馈的作用。 图（a）和（b）显示了使SQLite模糊化的独特崩溃次数和独特错误数量。 图（c）-（k）显示了每个模糊实例的新边缘数，语法正确性和语义正确性。 我们将每个模糊测试实例运行24小时，将每个模糊测试重复五次，并报告平均结果。

独特的崩溃: 图10（a）显示了每种设置在SQLite中发现的唯一崩溃的数量。同样，由于24小时评估期间崩溃的次数很少，因此我们跳过了PostgreSQL和MySQL的结果。功能齐全的Squirrel可达到最佳效果。首先，Squirrel在四分钟之内找到了第一起坠机事故。 Squirrel[!semantic]需要60倍以上的时间才能检测到第一次崩溃（261分钟）。有趣的是，Squirrel [!syntax＆!semantic]在32分钟内发现了第一次崩溃-比Squirrel差，但比Squirrel [!semantic]好。考虑到后者每秒运行220个查询，而前者每秒可以执行507个查询（即快1.3倍），因此我们认为Squirrel [!syntax＆!semantic]优于Squirrel [!semantic]的优势主要在于生成速度更快。 Squirrel [!feedback]需要700分钟才能找到第一个崩溃。唯一崩溃的总数遵循相同的模式，其中Squirrel，Squirrel [!semantic]，Squirrel [!syntax＆!managet]和Squirrel [!feedback]分别检测到600、30、10和3次崩溃。上面的结果表明，Squirrel的所有三个因素对碰撞检测至关重要。此外，基于覆盖的反馈起着最重要的作用，而仅语法测试无法胜过AFL。

独特的错误: 我们采用相同的策略来测量独特的错误，我们每小时都会对检测到的错误进行修补。图10（b）显示了结果。功能齐全的Squirrel可发现9个独特的错误，而其他变体仅检测一个独特的错误。如表4所示，全功能版本还涵盖了Squirrel变体（!feedback&!semantic）发现的唯一错误。

New Edges: 图10（c），（f）和（i）展示了一种（几乎）一致的模式，该模式为SQLite，PostgreSQL和MySQL寻找新的边缘：Squirrel> Squirrel[!semantic]> Squirrel[!syntax&semantic]> Squirrel[!feedback]。 基于覆盖率的反馈有助于使SQLite，PostgreSQL和MySQL变得模糊2.0倍的新优势。与AFL相比，语法正确性可以帮助找到多1.0×-1.5×的边，而语义正确性可以使数字增加0.3×-1.7×。 该结果表明，提高语法正确性或语义正确性有助于达到更多的DBMS状态。

语法有效性和语义有效性: 图10（d），（g）和（j）显示了在测试三个DBMS期间的语法变化，而图10（e），（h）和（k）显示了语义变化。在大多数情况下，Squirrel的有效性最高，而AFL的有效性最差。这个结果是合理的，因为我们设计Squirrel来获得更好的语言有效性，而AFL随机地变异SQL查询。但是，我们可以从图中发现一些有趣的异常。首先，Squirrel[!semantic]的语法准确性与图10（d）和（g）中的Squirrel相似，这表明提高语义正确性不会增加语法正确性。实际上，实例化可能会降低语法正确性，如图10（j）所示，因为它倾向于删除短查询。短查询在语法上更可能正确，但是我们的实例化程序无法修复其语义。例如，SELECT a FROM b在语义上是不正确的，因为不存在表b。由于SQLsmith的性能类似或什至优于Squirrel，因此PostgreSQL和MySQL的p值大于0.05。

其次，在图10（j）中，Squirrel[!feedback]与Squirrel具有相似的语义正确性。 这个结果似乎表明反馈对MySQL的语义正确性没有影响。 但是，进一步检查发现，Squirrel[!feedback]会产生非常不同的语义正确性：在五个实验中，两个实验的正确率超过40％，而其他三个实验的正确率则低于10％。 我们发现，MySQL中的初始种子比SQLite和PostgreSQL中的种子小。 这些小种子可能会导致Squirrel[!feedback]继续为MySQL生成正确但简单且重复的输入。 由于MySQL结果的随机性，附录表6中的p值大于0.05。 但是，图10（i）显示，与Squirrel[!feedback]相比，Squirrel生成的查询在结构上更加多样化，因为Squirrel发现了更多具有相似语义正确性的执行路径。

总体而言，语法，语义和反馈在Squirrel中起着至关重要的作用，以从DBMS中发现更多的内存错误。 基于覆盖率的反馈影响最大，而语法正确性和语义正确性则具有不同的影响。 最终结果是所有三个因素之间的相互作用。

9 讨论

我们讨论了当前Squirrel实施的局限性以及我们在未来的工作中解决这些局限的计划。

DBMS特定逻辑: 尽管我们的Squirrel设计与DBMS无关，但是我们发现合并特定于程序的功能始终有助于获得更好的测试结果。首先，每个DBMS都实现其SQL的方言，该方言与正式版本的SQL几乎相同（例如SQLite），或者在许多功能方面却与正式的显著不同（例如PostgreSQL）。 Squirrel完全支持SQL的通用语法，并且还包含针对不同方言的补丁。由于这个原因，Squirrel在SQLite上运行良好（51个错误），但在PostgreSQL，MySQL和MariaDB中仅触发了几个错误。我们计划对不同的SQL方言实施更准确的语法，以提高模糊测试的效率。其次，DBMS在执行查询之前可能会采取额外的检查。例如，我们发现PostgreSQL要求所有操作数之间的类型正确，并且不允许在整数和浮点数之间进行比较。 SQLite不会检查任何内容，但会在执行过程中自动执行类型转换，而MySQL仅警告类型不匹配的警告。我们计划在我们的语义指导实例中实现类型一致性关系，以测试PostgreSQL。

关系规则构建: Squirrel依赖关系规则来推断不同操作数之间的数据依赖关系。 目前，我们基于领域知识编写关系规则。 我们有两位作者花了两个小时来编写这些规则，这些规则仅涵盖133个条款。 为了减轻开发人员的繁琐工作，我们计划采用自动推断这些规则的技术。 例如，通过数据流分析，我们可以找出每个操作数之间的预期关系。 另外，我们可以尝试使用机器学习技术来自动从大量正常执行中捕获关系。

代码覆盖中的冲突: Squirrel依靠AFL的反馈机制来指导查询选择，不幸的是，它受到冲突问题的困扰。 默认情况下，AFL使用具有64K条目的位图记录分支覆盖范围，每个分支覆盖一个。 对于分支很少的小型程序，此方法效果很好。 但是，DBMS包含成千上万的分支，因此使用AFL测试DBMS具有严重的冲突问题。 例如，SQLite有大约20,000个不同的分支，其中14％的分支与其他分支共享位图条目。 在我们的评估过程中，我们将位图放大到256K以减轻冲突问题。 下一步，我们计划采用CollAFL中提出的解决方案来消除碰撞问题。

替代反馈机制: 最近的软件测试实践广泛采用代码覆盖率来指导基于突变的模糊测试。 但是，在我们的评估中，我们发现了潜在的有害代码覆盖范围，该覆盖范围阻碍了语义正确查询的生成。 特别是，在测试语法开始时，不正确的查询会在错误处理代码中触发许多新分支。 基于覆盖率的反馈指导Squirrel专注于这些输入，而不是原始的语义正确查询。 模糊语言编译器和解释器的最新著作提到了类似的观察。 我们计划调查此问题并开发解决方案以减轻此问题，例如删除输入以在短时间内触发新分支。

10 相关工作

在DBMS中检测逻辑和性能错误. DBMS已针对逻辑和性能缺陷进行了严格的测试[53、56、61、64]。 RAGS通过差异测试来检测DBMS中的正确性错误[56]。它在多个DBMS中生成并执行查询。结果之间的任何不一致都表明至少一个DBMS包含错误。 SQLancer构造查询以从表中获取随机选择的行[53]。如果测试的DBMS无法获取该行，则可能包含错误。 QTune [41]是基于深度强化学习模型的数据库调优系统，可以有效地调优数据库配置以获得最佳性能。 Apollo使用差异测试来发现性能错误[37]。它在同一DBMS的两个版本中生成并运行查询。如果两次执行所花费的时间明显不同，则该查询将触发性能回归错误。 BmPad在目标DBMS中运行预定义的测试套件，并在执行时间超过阈值时报告性能错误[52]。 Squirrel与这些作品的不同之处在于，它专注于检测可能导致严重安全后果的内存损坏错误。

基于生成的DBMS测试. 基于生成的测试通常用于测试DBMS。它可以有效地生成语法正确的测试用例，但很少保证语义的正确性。 QAGen表明，确保完美的语义正确性是一个NP完全问题。相反，它提供了一种近似的解决方案来提高语义正确性。一些工作减少了SAT问题的产生，并使用SAT解算器（例如Alloy ）提供了潜在的解决方案。基于世代的模糊器通常需要一些初始数据库的架构才能生成查询。 Bikash Chandra等提出了一种生成初始数据库的方法，该数据库可以覆盖大多数类型的SQL查询。 SQLsmith是最新的基于生成的DBMS测试器。它从初始数据库收集模式，并生成有限类型的查询，例如SELECT，以确保数据库不变，这限制了代码覆盖率。相反，Squirrel生成无上下文的测试用例，并且不依赖于特定的数据库或架构。它从一个空的数据库开始，并在使用它们进行测试之前创建适当的内容。

基于突变的DBMS测试. 最近，基于突变的模糊器在发现内存错误方面取得了巨大的成功。但是，它们被实现为通用的模糊器，并且不知道输入的结构。尽管它们中的一些采用了诸如污点分析或符号执行之类的高级技术，但是它们仍然无法深入测试像DBMS这样的程序，这些程序接受具有正确语义的高度结构化的输入。 Tim Blazytko等提出了一种利用类似语法的组合来合成高度结构化的输入的方法，但是它在SQL中生成的大多数测试用例在语法上仍然不正确。 Hardik Bati等提出通过添加或删除语法组件来变异SQL语句。它们可能保留语法正确性，但不能保证语义正确性。最近的工作倾向于提高生成的输入的语义正确性，但是SQL对语义的要求更加严格，并且没有一个在测试DBMS方面显示出其有效性。因此，由这些模糊器生成的大多数测试用例都无法通过语法检查或语义检查，并且没有机会触发深层逻辑，例如优化或执行。 Squirrel通过保留语法的变异和语义指导的实例化克服了这些缺点，并设法检测出深层逻辑背后的错误。

11 总结

我们已经提出并实现了Squirrel来对数据库管理系统进行模糊测试，以查找与内存相关的错误。我们的系统采用了两种新颖的技术，即保留语法的变异和语义指导的实例化，以帮助生成正确的SQL查询。我们在四种流行的DBMS（SQLite，MySQL，MariaDB和PostgreSQL）上评估了Squirrel，并发现SQLite中有51个错误，MySQL中有7个错误，MariaDB中有5个错误。 Squirrel在语义正确性方面的改进至少是当前基于突变和基于生成的模糊器的3.4倍，并且触发的代码覆盖率是当前基于突变的模糊器的12倍。结果表明，Squirrel在测试数据库管理系统方面是有效且高效的。

致谢

我们感谢匿名审稿人的有益反馈。这项工作得到了美国国家科学基金会（NSF）在CNS-1652790项下的部分支持，以及海军研究办公室（ONR）在N00014-16-1-2912，N00014-16-1-2265，N0001417-1项下的支持-2894，N00014-17-1-2895和N00014-18-1-2662。本材料中表达的任何观点，发现，结论或建议均为作者的观点，不一定反映NSF或ONR的观点。

ex: 备注

模糊测试工具通常可以被分为两类。变异测试(Mutation-based)通过改变已有的数据样本去生成测试数据。生成测试(Generation-based)则通过对程序输入的建模来生成新的测试数据。

–wikipedia

bail out: 具体意思不明确，使用其本意（保释，解困）有点不妥。

NP-hard: 指一些很难的非确定性的问题，具体可百度。

p-values: P值是用来判定假设检验结果的一个参数，也可以根据不同的分布使用分布的拒绝域进行比较。P值越小，代表结果越显著。

论文中的附录还对文中的具体算法进行了阐述，鉴于篇幅限制，有兴趣的师傅自行查阅。