蚂蚁安全天穹实验室“数据库漏洞挖掘技术”被世界顶会 ICDE 2023收录

近日，蚂蚁安全天穹实验室与清华大学姜宇副教授团队合作的关于数据库漏洞挖掘的文章《Sequence-Oriented DBMS Fuzzing》成功中稿国际数据库三大顶会之一的 ICDE 2023。

ICDE 2023（IEEE International Conference on Data Engineering (ICDE) 是数据库研究领域历史悠久的国际会议，与SIGMOD、VLDB并称为数据库三大顶级会议。ICDE平均录用率25%左右。本文将对这篇 paper的核心内容进行一些解读（点击文末“阅读原文”获取论文全文）。

本次论文的合作方，清华大学软件学院副教授、博士生导师、阿里巴巴达摩院青橙奖获得者姜宇老师表示：数据库系统本身的安全性直接关系到用户数据和隐私的安全性，本研究提出了一种新型的数据库漏洞挖掘思路，并且挖掘出MySQL、PostgreSQL等知名数据库系统中的大量漏洞，对于提升数据库行业安全性有重大参考价值。

0 摘要

数据库作为承载用户数据的底层系统，其安全性和稳定性非常重要，数据库中如果存在漏洞，攻击者可能通过漏洞之间获取到用户的隐私信息和敏感数据。目前市场上存在大量国际及国产数据库，包括拥有数十年历史的MySQL、Oracle数据库、国产自研的OceanBase数据库等等，这些数据库由数百万行代码构成，如何高效自动化的挖掘数据库系统中存在的漏洞一直是行业亟需解决的难题。本文提出了一种新型的数据库漏洞挖掘方式，在多个大型数据库系统中挖掘出了大量bug，大大提升了数据库行业的安全水位。

在现代大型数据库系统中往往存在大量不同的statement类型及大量“方言”，这大大增加了数据库模糊测试的难度，在以往最先进的数据库模糊测试工作中，基本都是重复使用一些预定义的类型作为初始变异种子，但是预定义的类型十分有限导致难以探测到更多的程序代码空间。在本篇工作中，我们提出了一个能主动生成丰富的SQL执行序列的模糊测试引擎LEGO，序列生成的核心思想是“type-affinity”，即相邻的SQL语句对。在每轮Fuzzing变异过程中，LEGO首先会生成不同的SQL语句对，并且根据覆盖率分析其“type-affinity”，如果发现一个新的有价值的“type-affinity”，LEGO就会合成含有此类SQL语句对的SQL序列用于后续的语句变异。

我们在PostgreSQL, MySQL, MariaDB, 和 Comdb中做了实验评估，并且和之前的工具 SQLancer, SQLsmith, 和 SQUIRRE做了比较，实验显示，LEGO和其他模糊测试工具相比有 44%–198% 的覆盖率提升，更重要的是，LEGO在持续模糊测试的过程中挖掘出了大量新的漏洞，并且获得了数十个CVE。

1 背景

数据库管理系统（DBMS）作为管理用户数据的桥梁，其安全性十分的重要，尤其是数据库管理系统中存在的堆栈溢出等传统安全漏洞，一旦被发现，攻击者可能通过这些漏洞窃取、伪造用户数据、也可能直接导致数据库系统拒绝服务，给用户造成巨大的损失。

生成丰富的SQL序列在数据库模糊测试中十分重要，图1展示了SQL序列的含义，对于每个数据库测试用例而言，内部都包含了不同的statement比如CREATE语句、INSERT语句、SELECT语句，SQL序列指的是不同statement之间的序列组合。

图 1  SQL执行序列

数据库模糊测试变异方式主要包括基于生成的变异方式和基于变异的生成方式，之前的一些工作主要关注如何生成语法语义正确的数据库测试用例，但是忽略了在大型数据库系统中语句类型组合的重要性。基于生成的变异方式需要预先定义一些生成规则，比如，SQLsmith主要是生成各类SELECT语句，所以其探索的程序空间十分有限；基于变异的生成方式从已有的一些种子中随机选取作为变异的基础，但他们主要关注序列内部的变异，比如Squirrel在变异的时候不会改变statement类型，而是专注于变异statement内部的语法语义结构。

2 SQL类型序列

图2展示了不同SQL执行序列对程序执行路径的影响。左边是两组test case，他们都有相同的4条SQL语句，唯一的区别是语句的执行顺序不一致：

• 第一组SQL Type Sequences为 CREATE TABLE -> INSERT -> INSERT -> SELECT
• 第二组SQL Type Sequences为 CREATE TABLE -> SELECT -> INSERT -> INSERT

然而正是因为执行顺序不一致导致最终的程序执行路径有很大的差别，第一组序列中SELECT可以查询到内容，而第二组序列查询结果为空。

图 2 SQL执行序列不同导致程序执行路径不同

想要生成丰富而有效的SQL执行序列存在以下几个挑战：

1. SQL执行序列组合的可能性巨大。以PostgreSQL数据库为例子，PostgreSQL有188种的SQL statement类型，如果一个测试用例含有20个SQL statement，总的可能性有3×10^45，对于模糊测试工具Squirrel而言，经过实验1秒能执行10–60个用例，要执行一轮所有的用例需要超过10^35年。
2. 有很多SQL执行序列是无意义的。比如在 “CREATETABLE t2 (v0 int)“ 语句执行之前先执行 ”SELECT * FROM t2“，因为存在语义错误而导致总体代码覆盖率很低。另外有些SQL序列直接没有很强的关联，比如一条创建表的语句和一条修改权限的语句可能完全不相关，他们之间的序列组合不会带来覆盖率上的明显提升。
3. 随机生成的test case可能并不适合用来fuzz。一个测试用例中不是SQL执行序列越多越好，在我们的实验测试中一个含有945个SQL语句的测试用例，其中重复调用了数百次INSERT语句，这些语句有类似的行为和代码覆盖，对代码覆盖率的增长没有太大作用，反而大大降低了执行速度。

图3 亲疏性分析及序列生成示例

为了解决前两个挑战，我们提出了类型亲疏性（type-affinity）来解决合成有意义序列的问题，为了提升覆盖率，LEGO会对覆盖新分支的种子进行亲疏性分析；为了解决第三个挑战，我们限制了最大生成的序列数量，同时通过序列合成来生成不同序列长度的种子。

图3展示了亲疏性分析及序列生成的基本思想，从原始种子中，通过亲疏性分析学习到 INSERT -> CREATE TRIGGER 等序列模式，然后通过序列生成合成了 2->3->5->4 这条SQL语句序列，最后通过对这个序列的变异发现了CVE-2021-35643这个漏洞。

3 设计及实现

图4展示了LEGO基本的fuzzing流程，首先LEGO从种子池中随机选取初始种子，对其进行基于序列的变异，然后对其进行亲疏性分析，如果经过变异的种子发现了新的路径，那么导致路径增长的序列关系会被记录保留，接下来LEGO从序列关系库中主动合成新的变异序列，对其进行实例化及内部变异，最后发送给DBMS处理，并监测是否产生了bug。

图4 LEGO框架及核心fuzzing流程

接下来介绍下LEGO中两个核心步骤，主动亲疏性分析（Proactive affinity analysis）和渐进式序列生成（Progressive Sequence Synthesis）。

3.1 Proactive Affinity Analysis

主动亲疏性分析包括SQL语句亲疏性学习和主动面向序列的变异，具体如下：

✪ 3.1.1 Type-Affinity

SQL语句亲疏性指的是在测试用例中出现的相邻两条语句，如果一个用例中INSERT语句在CREATE TABLE语句之后，那么可以构造一条 (CREATE TABLE, INSERT) type-affinity。

✪ 3.1.2 Proactive Sequence-Oriented Mutation

通过面向序列的变异使LEGO能主动挖掘新的有价值的序列组合，图5展示了面向序列的变异算法：

图5 面向序列的变异算法

面向序列的变异具体包括3大类操作，分别为替换、插入及删除

1. 替换（Substitution.）：从选取的种子中随机挑选一个statement，将其替换成其他类型的statement，替换之后会按照Squirrel的方式重新实例化语句，使其保证语义高正确性。如果发现了新的分支则分析是否是新的type-affinity导致，若是则保存新的type-affinity。
2. 插入（InsertAfter）：从选取的种子中随机挑选一个statement，在其后面插入一天随机类型的statement，插入之后依然会按照Squirrel的方式重新实例化语句，如果发现了新的分支则分析是否是新的type-affinity导致，若是则保存新的type-affinity。
3. 删除（Delete）：从选取的种子中随机挑选一个statement，将其删除后重新实例化语句，如果发现了新的分支则分析是否是新的type-affinity导致，若是则保存新的type-affinity。

✪ 3.1.3 Type-Affinity Analysis

为了从用例中提取type-affinity，需要识别不同的SQL statement类型，而不同数据库往往存在大量方言和特有的statement类型。举例而言，在PostgreSQL中定义了188种SQL statement 类型和349子类型，我们通过构建AST模型来准确的识别不同数据库中的statement类型。

图6 类型亲疏性分析算法

LEGO会顺序分析分析所有的SQL语句，并保存记录当前语句上下相关的type-affinity，如果相邻两个SQL类型一致，则直接忽略此类情况，因为同类型的语句对整体类型丰富度没有帮助，分析完之后LEGO会保存有所已知SQL类型的type-affinity，供后续序列生成使用。

图7 序列变异示例

图7展示了序列变异的一组实例，在初始用例中随机选择了UPDATE语句，在进行序列变异时，分别对其进行替换、插入和删除变异操作，变异之后重新进行实例化，最后得到变异之后的SQL序列。

3.2 Progressive Sequence Synthesis

在获取到高质量的type-affinities之后，接下来是根据已有的type-affinities逐步合成新的变异样本，对于新发现的type-affinitiy，LEGO在序列生成时会优先生成含有此类type-affinitiy的语句：

图8 合成含有新的type-affinitiy的SQL序列

在合成最后的变异序列时，LEGO会先定义一个初始结点类型，默认为CREATE TABLE，并且为了避免生成太大的用例，也设置了默认最长statement数量。

图9 渐进式序列生成算法

图9展示了渐进式的序列生成算法，在得到新的type-affinitiy时，我们并不是重新生成所有序列，为此我们定义了 Prefix Sequence ，即前序序列，以某特定SQL类型为结尾的序列集合，使用Map进行存储，在找到一个新的高价值type-affinitiy（ t1 → t2）时，先从Prefix Sequence中查找t1的所有前序序列，然后基于前序序列生成新的变异序列。

3.3 实现

LEGO基于AFL++实现，其中的变异算法封装成了custom mutator，亲疏性分析和序列生成基于AST解析树，我们复用了Squirrel中定义的IR结构，并且扩展到MySQL、PostgreSQL、MariaDB、Comdb2中所有已定义语法描述。

4 实验结果

经过持续漏洞挖掘，我们通过LEGO发现了大量新的漏洞，其中包括了堆栈溢出、UAF、非法地址访问、NPD等传统代码漏洞，最终获得了数十个CVE，并且得到了多次的官方致谢。

5 总结

本文提出了一个针对数据库的模糊测试工具LEGO，其核心思想是通过分析SQL statement的type-affinities来生成更丰富的SQL测试用例序列，同时通过主动序列变异和渐进式序列生成来探索更有价值和更多的程序代码空间，经过实验发现，LEGO在PostgreSQL，MySQL， MariaDB和Comdb2数据库中发现了大量新的代码漏洞并且在代码覆盖率和效率等方面超过了之前最先进的一些数据库模糊测试工具。

6 引用

[1] https://icde2023.ics.uci.edu/papers-research-track/

蚂蚁安全天穹实验室介绍：