[翻译]【Griffin】语法自由的DBMS模糊测试，论文学习

发表于: 2025-3-27 01:10 1380

[翻译]【Griffin】语法自由的DBMS模糊测试，论文学习

fuxxcss

2025-3-27 01:10

1380

ASE 2022
题目：
Griffin : Grammar-Free DBMS Fuzzing

仓库：
807K9s2c8@1M7s2y4Q4x3@1q4Q4x3V1k6Q4x3V1k6Y4K9i4c8Z5N6h3u0Q4x3X3g2U0L8$3#2Q4x3V1k6s2M7X3W2X3k6X3W2F1i4K6u0V1x3U0l9J5x3W2)9J5c8V1N6J5K9h3k6X3K9h3^5`.

为什么选择Griffin

1.数据库适配

在数据库适配层面，Griffin不需要语法解析，它是基于用例重排的。由于DBMS的SQL语法不统一，其他的方案适配各种数据库开销大，且语法不完整。
下图列出了其他DBMS fuzzer为了适配各种数据库，额外的代码量。

2.指导变异

在指导变异层面，Griffin对比其他。

     Griffin                    其他
 
  SQL文件的执行结果         解析SQL语句语法
        ↓                        ↓
生成 <SQL-元数据> 图        生成 AST/IR 树
        ↓                        ↓
  重组算法指导变异         树变异算法指导变异
        ↓                        ↓
   变异SQL继续执行           变异SQL开始执行

3.语法/语义正确性

由2.指导变异的区别可以看出，在语法正确性方面，Griffin：

SQL执行在变异之前，进行了初筛。
基于SQL语句重排，具有天然优势。

其他fuzzer ：

语法正确性依赖于AST/IR的正确性。
SQL执行在变异之后，无法进行初筛。

在语义正确性方面，Griffin基于 <SQL-元数据> 图进行语义的修复；其他fuzzer需要额外维护数据关联图。

4.总结

总的来说，Griffin是一种动态变异方案，基于SQL语句的结果来指导变异；其他fuzzer是静态变异方案，基于SQL语句本身的结构进行变异。

Griffin摒弃了语法解析，提出重排算法，优点：

工作重心，语法解析 → 元数据分析
测试用例，一条语句 → 一个sql文件
很容易适配到任何的DBMS

Griffin原理

1.元数据的分析

在关系型数据库中，元数据是关于数据的数据。DBMS使用元数据检查语义。下图展示了一个表的元数据结构。

一个表被创建出来，会生成四种元数据：

// 表名
table_name(
  primary_key,  // 主键
  column_name,  // 列名
  index_name,   // 索引名
)

为了收集元数据，需要编写一条SQL获取元数据，适用于ANSI标准DBMS。

据此可以建立起元数据之间的映射关系。

name            type            parentname
table_name      TABLE           null
column_name     column_type     table_name
trigger_name    TRIGGER         table_name
index_name      INDEX        (table_name,column_name)

2.构建 <SQL-元数据> 图

基于元数据的分析结果，设计出图构建算法。如下图所示，执行的两条SQL语句在收集好元数据之后，可以构建出一个有向无环图。

构建出的 <SQL-元数据> 图中有两种节点：语句节点和元数据节点，它们之间可以反映出三种依赖关系：

<SQL语句，元数据>，元数据依赖于SQL语句。
<元数据，SQL语句>，SQL语句依赖于元数据。
<元数据，元数据>，元数据依赖于元数据。

3.用例重组算法

在建立的<SQL-元数据> 图之上，用例重组阶段可以使用语义修复来确保变异的正确性。如下图所示，两个选择出来的测试用例进行重组，在r3进行语义修复之后，r3的依赖得到满足。

简单而言，Griffin的语义修复策略由以下两条构成：

元数据类型匹配，b(table) → a(table)；u(column) → x(column)
元数据之间关系匹配，b(u) → a(x)

符合语义修复条件，因此b替换为a，u替换为x。这里存在另一种修复方案，在图中以红色箭头标注。

4.整体流程图

实验评估

Griffin漏洞挖掘情况，在四个流行的开源DBMS上。

个数                        类型
SQLite      16              段错误      21
DuckDB      12              断言失败    15
MariaDB     24              内存损坏    15
PostgreSQL   3

论文以SQLite中发现的一个断言失败作为例子，说明了Griffin的优越性。该断言失败自2009年SQLite 3.6.19版本就存在，当SQLite在外键约束上使用无效的虚拟触发器时，就会触发断言失败。

SQLancer、SQLsmith和Squirrel对SQLite进行了多年的模糊测试，为什么直到Griffin才被发现？