一、数据库模糊测试简介

数据库管理系统（以下简称为数据库）作为信息技术领域的基石软件之一，在信息技术领域占据至关重要的地位。但是，数据库作为一种复杂软件，在开发过程中会不可避免地引入各种漏洞，这些漏洞有可能被攻击者利用，从而对数据库使用者造成损失。因此，需要一种方法在开发阶段检测数据库中可能存在的漏洞，以此减少可能带来的损失。

模糊测试技术因其高效、自动化等特性，被广泛应用于检测程序中存在的各种漏洞，并取得了卓越的成果。因此，有学者将模糊测试技术应用于数据库漏洞的检测，提出了各种有效的数据库模糊测试工具。

目前，数据库模糊测试工具主要针对数据库中存在的两种错误：逻辑错误和能触发崩溃的错误。前者是指数据库在查询时返回的结果与预期不符，后者则是能够引发数据库崩溃。

对于逻辑错误，数据库模糊测试工具最主要的问题是找到一个合适的oracle，即应当使用什么现象来判断数据库出现了逻辑错误。最早的RAGS使用差异测试的方法检测数据库中的逻辑错误，该方法将同一条SQL语句输入多个不同的数据库，然后比较返回结果，如果返回结果不一致，则某个数据库出现了逻辑错误。这种方法的优点是十分简单，缺点在于：由于不同数据库的语法不同，因此该方法只能使用这些数据库中共同支持的SQL语句，不涉及每个数据库的方言；如果所有数据库出现同样的错误，则无法检测。2020年，Manuel Rigger和Zhendong Su提出了SQLancer工具，该工具集成了TLP、PQS和NoREC 3种方法，用于检测数据库逻辑错误。其中，TLP方法将查询划分为多个分区，并将原输入的结果和划分后每个分区的结果的并集进行比较，以此发现数据库逻辑错误，作者表示划分方法不唯一，而SQLancer使用的方法是使用逻辑谓词进行划分，即选择某个值，在SELECT语句中的WHERE子句中添加该值为真、假和IS NULL，生成3个SELECT语句，在使用UNION将这些语句连起来。PQS方法则是在数据库中选择某一行，生成能够获得该行的查询，再在WHERE子句中随机生成一个为真的表达式，检查结果，如果结果中不存在该行，则数据库存在逻辑错误。NoREC方法是对查询进行逻辑上等价的变形，将能够被优化的查询变为不能被优化的形式，然后对比两种结果的差异，以此寻找逻辑错误。这些方法的优点在于可以测试数据库方言，缺点在于不能对返回结果不确定的查询进行测试。

对于能够引发崩溃的错误，由于数据库崩溃是发生该错误的现象，而且易于观测，因此oracle不是问题。其主要问题在于生成语法和语义正确的输入。根据生成输入方式的差异，检测这种错误的数据库模糊测试工具可以分为两种：基于模板生成的和基于变异的。基于模板生成的数据库模糊测试工具主要是SQLsmith，该工具使用模板随机生成SQL语句，属于黑盒模糊测试工具。该工具在初始化阶段会从数据库中读取已有的数据库的信息，使用这些信息生成SQL语句，主要生成SELECT语句。在生成SQL语句时，会根据特定顺序生成语句中每个子句，对于每个子句，则会根据特定的顺序生成子句中的各个部分，以此类推，直至生成查询中的基本单元（即数值常量、字符常量、数据库对象标识符等）。在生成时，会记录下必要的信息，之后的生成会使用这些信息，确保语义正确，具体的生成顺序和生成方法需要使用专家知识编写。该工具的优点在于生成的语句正确率较高，缺点在于：1、属于黑盒模糊测试工具，效率较低，难以探测深层代码；2、需要手动编写模板。基于变异的数据库模糊测试工具基于变异方法可以分为基于结构变异和基于序列变异，这两种变异方法能找到的bug完全不同，属于互补关系。其中基于结构变异的测试工具主要是Squirrel，该工具将SQL语句解析为语法树，对语法树结构进行变异，Squirrel的具体情况在第二节详细说明。而基于序列变异的测试工具主要是Griffin，该工具的变异方法是对SQL语句的组合和顺序进行变异，即每次选择多组输入，每组输入有若干SQL语句，从这些输入中随机选择一些SQL语句，生成新输入，实践证明该变异方法确实有效。Griffin的创新点在于提出了一种新的实例化方法，能够替换SQL语句中的数据库对象标识符，使输入具有正确的语义关系，该方法分析每条SQL语句产生和使用的数据库对象，并将信息记录下来，在新的输入中，用输入中SQL语句产生的数据库对象，替换输入中SQL语句使用但在该输入中没有生成的数据库对象，以此确保输入中数据库对象引用关系的正确性，进而实现语义正确。基于变异的测试工具的优点在于使用了覆盖率引导机制，效率更高，同时能够探索更深层的代码，缺点则在第五节说明，其中Squirrel的局限性很大程度上反映了基于变异的测试工具的局限性。

二、Squirrel概要

Squirrel是由Rui Zhong等人在2020年提出的一个开源的基于变异的数据库模糊测试工具，其在SQLite、MySQL和MariaDB数据库中找到不少漏洞，是近些年最有名的开源的基于变异的数据库模糊测试工具，其最初是一款基于AFL的灰盒数据库模糊测试工具，不过最近作者进行了更新，基于AFL++实现了新版本的Squirrel。本文先基于最初的AFL版本简单介绍该工具的实现方法，再介绍该工具迁移至AFL++后发生的改变，最后介绍该工具AFL++版本的使用方法。

由于数据库的输入是高度结构化的SQL语句，因此与AFL这种传统的模糊测试工具相比，针对数据库的模糊测试工具有以下两个特点：

项目地址   https://github.com/s3team/Squirrel

论文原文地址   https://dl.acm.org/doi/abs/10.1145/

3372297.3417260

2.1  基本结构

图 1 Squirrel基本结构

2.2  解析器

对SQL语句的解析是通过bison实现的。bison用于自动生成语法分析器程序，把LALR形式的上下文无关文法描述转换为可做语法分析的C或C++程序。关于bison的具体使用方法超出了本文的内容，在此不作赘述，有兴趣的可以在网上查阅相关资料了解，本文只简单讲解Squirrel中对bison的使用。

在Squirrel中，每个非终结符对应了一个类，该类定义如图所示。

在bison解析SQL语句时，每次规约生成式都会生成对应的非终结符对象，并根据归约的生成式编号和该生成式中存在的终结符对新终结符类中的scope_变量和终结符类指针进行赋值，如果该生成式在规约时可以确定identifier非终结符的数据类型和上下文环境，则会对identifier非终结符对象的data_type_、data_flag_和scope_变量进行赋值。最终，在解析结束时，会得到一个以非终结符为节点的AST。

具体过程如下图所示，该图为bison中对CREATE TABLE语句的解析部分，其中if语句之前的部分是创建节点和设置case_idx_变量，以及连接子节点，这部分可以根据文法文件使用脚本自动生成。if语句后的部分是记录实例化中使用的data_type_、data_flag_和scope_变量，该部分需要手动编写。

bison文件决定了Squirrel支持的语法，使用Squirrel检测其他数据库或是对已支持数据库的文法进行扩充时，需要重新编写相应的bison文件，同时还要修改ast.h中非终结符类的定义和修改define.h中的ALLCLASS宏。除此之外，还要编写对应的词法分析器，这部分与编写常规词法分析器相同。

在得到AST后，Squirrel将AST转换为一种类似AST的IR结构。转换的目的主要有两个：1、得到的AST中只有非终结符节点，没有非终结符信息。SQL语句中的非终结符信息需要在转换过程中添加。2、在AST中，每个非终结符节点可能有若干个子节点，子节点数量的不确定性给后续的变异操作带来麻烦，因此需要对AST中的每个节点进行标准化处理，使得每个节点具有相同的结构，方便后续的变异操作。

IR节点的定义如下：

2.3  变异器

2.4  实例化器

以如下输入为例，解释整个实例化过程：

CREATE TABLE x1 (x2 INT);

SELECT x3 FROM x4;

首先，将输入拆分成两条SQL语句，并依序处理。

对于第一条CREATE语句，扫描整个语句，获取相关非终结符节点的信息。其中，

节点x1：

data_flag_ = kDefine

data_type_ = kDataTableName

scope_ = 1

节点x2：

data_flag_ = kDefine

data_type_ = kDataColumnName

scope_ = 2。

于是有：

scope_library_[1][kDataTableName] = {x1}

scope_library_[2][kDataColumnName] = {x2}。

之后，建立依赖关系，首先处理x1节点，在relationmap_查询，发现无依赖关系，再处理x2节点，查询relationmap_，发现

relationmap_[kDataColumnName][kDataTableName] = kRelationSubtype

则根据scope_和对应类型查询能够建立依赖关系的节点

scope_library_[1][kDataTableName] = {x1}

发现只有x1，于是与x1建立依赖关系：

x1→x2

最后，由于x1无父节点，data_flag_ = kDefine，因此x1使用新名称table0，并更新两个变量：

data_library_[kDataTableName] = {"table0"}

data_library_2d_[kDataTableName]["table0"] = {}

由于x2有父节点x1，data_flag_等于kDefine，因此x2使用新名称column0，并更新两个变量：

data_library_[kDataColumnName] = {"column0"}

data_library_2d_[kDataTableName]["table0"][kDataColumnName] = {"column0"}

实例化后，SQL语句变为：

CREATE TABLE table0 (column0 INT);

对于第二条SELECT语句，扫描整个语句，获取相关非终结符节点的信息。其中，

节点x3：

data_flag_ = kUse

data_type_ = kDataColumnName

scope_ = 2

节点x4：

data_flag_ = kUse

data_type_ = kDataTableName

scope_ = 1

于是有：

scope_library_[1][kDataTableName] = {x4}

scope_library_[2][kDataColumnName] = {x3}。

之后，建立依赖关系，首先处理x3节点，查询relationmap_，发现：

relationmap_[kDataColumnName][kDataTableName] = kRelationSubtype

存在依赖关系，则根据scope_和对应类型查询能够建立依赖关系的节点

scope_library_[1][kDataTableName] = {x4}

发现只有x4，于是与x4建立依赖关系：

x4→x3

再处理x4节点，在relationmap_查询，发现无依赖关系.

最后，由于x4无父节点，data_flag_等于kUse，因此x4从data_library_中随机选择一个名称，由于此时

data_library_[kDataTableName] = {"table0"}

只有一个名称，x4选择table0。由于x3有父节点x4，data_flag_等于kUse，因此根据父节点名称在data_library_2d_中随机选择名称，由于

data_library_2d_[kDataTableName]["table0"][kDataColumnName] = {"column0"}

只有一个名称，x3选择column0。实例化后，SQL语句变为：

SELECT column0 FROM table0;

最终整个输入满足了数据库对象之间的依赖关系。

Squirrel在除SQLite外的3个数据库中的实现较为简单，只能处理简单的数据库对象之间的依赖关系。在SQLite中实现较为复杂，但是基本原理相同，只是对于节点的标记以及不同类型节点之间的依赖关系更为复杂。

Squirrel的实例化算法原则上与数据库无关，只要数据库中identifier非终结符之间的依赖关系不变，就不需要对实例化算法进行修改，但是考虑到实际使用中可能会定义更复杂的依赖关系，以及Squirrel的实例化算法较为简单，只能处理数据库对象之间的依赖关系，对于更复杂的语义约束条件，如类型约束，则无能为力，因此为了更好的效果，可以考虑对Squirrel的实例化算法进行修改。Squirrel实例化器的入口为mutator.cpp文件中的validate函数，可以从该函数开始，对实例化算法进行修改。

三、迁移至AFL++的变化

四、在AFL++中的使用

由于Squirrel在AFL++中只是作为一种变异方法实现，因此首先需要安装AFL++，关于AFL++的安装方法本文不多赘述，可以自行参考其他文章。

关于Squirrel的安装方法，如官方文档所示，基于ubuntu 22.04：

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release -DXXXXX=ON -Wno-dev

其中，XXXXX可以为SQLITE、MYSQL、POSTGRESQL或Mariadb，分别对于4中数据库。

cmake --build build -j

编译好的文件在build目录下，其中，libxxxxx_mutator.so为使用AFL++接口自定义的变异方法，使用时需要使用环境变量导入AFL++，db_driver为待测目标，用于连接数据库。

关于Squirrel的安装方法，如官方文档所示：

export SQUIRREL_CONFIG=/path/to/config.yml

export AFL_CUSTOM_MUTATOR_ONLY=1

export AFL_CUSTOM_MUTATOR_LIBRARY =  REPO_DIR/build/libxxxx_mutator.so

export AFL_DISABLE_TRIM=1

其中，第一个是yaml文件的路径，后三个是向AFL++中导入自定义变异方法，该部分环境变量可以参考其他关于AFL++的文章。

afl-fuzz -i input -o output -- ./build/db_driver

启动后，会打印此时使用的共享内存的ID，并暂停30s。在这30s内，需要在命令行中将该ID手动输入环境变量，并启动数据库相应服务器：

export __AFL_SHM_ID=xxxx

xxxx为共享内存ID。对于SQLite，直接对harness进行测试，不用额外的启动步骤。

关于对数据库插桩，在编译时，直接将afl-gcc/afl-g++或afl-clang-fast/afl-clang-fast++设置为编译器即可。

五、结语