G.O.S.S.I.P 阅读推荐 2022-08-25 Detecting logical bugs in DBMS

今天为大家推荐一篇来自宾州州立大学胡宏研究组投稿的，关于检测数据库管理系统 (DBMS) 逻辑漏洞 (logical bugs) 的论文Detecting Logical Bugs of DBMS with Coverage-based Guidance。论文提出并实现了一个名为 SQLRight 的工具，用来查找数据库里面的代码逻辑错误。SQLRight 从两个常用的 DBMS, 即 SQLite 和 MySQL 里面发现了 18 个逻辑错误。该工作已经发表于 USENIX Security 2022。

[背景介绍]

数据库系统安全是一个被研究了多年的课题。以往的研究侧重于如何高效地检测数据库管理系统 （DBMS) 的内存漏洞，而忽略了代码里面潜在的逻辑错误。这些逻辑错误可能导致 DBMS 输出错误的结果，从而误导数据库的使用者。最近两年，有不少数据库逻辑错误被发现和报告，引来了越来越多学者的注意。

已有的工作尝试使用差分测试 (Differential Testing) 来测试 DBMS 里面的逻辑错误。这种方法将同一个 SQL 语句发送到不同的 DBMS，然后检查不同数据库的输出是否相同。如果不同的数据库结果不一致，则可能该 SQL 语句在其中至少一个 DBMS 触发了逻辑错误。但是，每个数据库都有大量独特自定义的功能。如果生成的语句只用来测试所有DBMS 的通用功能，那么每个 DBMS 能被测试到的代码将会非常有限；如果想要用一个 SQL 语句测试不同 DBMS 的特有功能，那么生成语句的正确率会非常低。

另一份已知的工作是 SQLancer。这个工具使用 oracle 来检测 DBMS 的逻辑错误。这里的 oracle 是指可以预测出正确结果的程序，而不是指数据库管理软件 Oracle 或其母公司。oracle 会将一段 SQL 语句转化成 “形式不同但语义相同” 的另一种格式，并

把所有的同义 SQL 语句发往同一个 DBMS 去执行。如果某些语句的执行结果和其他的不一致，则这些 SQL 语句很可能触发了该 DBMS 的某个逻辑错误。可惜的是，SQLancer 严重依赖于被测试 DBMS 的特定语法规则和语义规则来生成 SQL 语句。这些特定的生成规则限制了 SQLancer 测试各个 DBMS 深度代码逻辑的能力。

[典型数据库逻辑错误分析]

上图展示了一个存在于 SQLite 里的逻辑错误。该错误由 SQLight 首次发现，并已经被开发者火速修复。上面这个 SQL 语句首先创建了一张名为 person 的表 (table): 该表只有一个名为 pid 的列。接下来，该语句向 person 表插入了三行数据:

11010

随后该语句为 person 表构造了一个部分唯一索引 unique partial index。唯一索引 (unique index) 的含义是，每一行该列的值都是唯一的；否则该 index 无法创建（程序会报错）。部分索引 (partial index) 的含义是只有符合条件的某些行会被该索引所包含。在这个例子中，person 表包含了三个数据行，但是每一行的 pid 列并不唯一。直接创建唯一索引会导致程序报错。但是满足 pid=1 行只有一列。所以最终创建的部分唯一索引只包含了第一行，并不包含后面的两行。最后一条 select 语句在 person 表里查找 pid=10 的行，并使用 distinct 关键字来要求对结果去重。正确的结果应该只有一行:

10

但因为处理 unique partial index 和 distinct 的代码之间出现了错误的逻辑，导致 SQLite 错误地输出了两行结果：

1010

[研究工作概览]

文章中提出了工具 SQLRight，首次将 coverage-based fuzzing 和 oracle 相结合来查找 DBMS 的逻辑错误。文章证明了使用 coverage-based fuzzing 查找逻辑错误的可行性和有效性。文章同时着重解决两个查找 DBMS 逻辑错误的难点：

1. 如何稳定生成高质量（即语法正确且语义正确）的 SQL 语句（高质量的 SQL 语句对于检测 DBMS 逻辑错误至关重要）；
   

2. 如何方便地实现新的 oracle 并把他们跟 fuzzing 工具结合起来。

文章提出了四个提高 SQL 语句质量的方法。

首先，SQLRight 使用自动化脚本将各个数据库的语法分析器 (parser) 前端逻辑移植到 SQLRight 中。具体来说，每个 DBMS 都有自己的逻辑来进行词法分析和语法分析；词法分析的最后一步，是生成特定的数据结构来存放分析结果（比如，当前语句是一个 select 语句，该语句查找 person 表格里面 pid 列为 10 的行）。SQLRight 要做的，是接管语法分析器的最后一步：不再生成每个 DBMS 特定的数据结构，而是创建一个统一的基础结构用来表示所有的语句（可参考 CCS 2020 论文 Squirrel: Testing Database Management Systems with Language Validity and Coverage Feedback 来理解该统一数据结构）。如此以来，SQLRight 完全支持每个 DBMS 的原生词法规则和语法规则，相比其他工具残缺的词法和语法规则，SQLRight可以更充分的测试每个数据库，大大提高了测试的覆盖率。SQLRight 遵照每个 DBMS 的规则来检查所有生成的 SQL 语句，保证了生成语句较高的正确性。

第二，SQLRight 会根据 SQL 语句的语义动态调整数据库中表格的属性，选取合适的参数（比如，表名，列名，操作数等等）填充每一条语句。比如，当某条 SQL 语句使用 (ALTER TABLE) 来更改表格某一列的名称，SQLRight 能够记录下表格列名的变化，从而避免使用旧的列名作为查询条件。 

第三，在语句变异的过程中，SQLRight 确保 SQL 语句中对 oracle 必要的部分不变。比如，select 语句可以打印查询结果。如果一次查询没有 select 语句，我们将无法判断多条同义语句的执行结果是否一致（或者说，总是一致）。为避免这种无效操作，开发者可以指定 SQLRight 变异过程保留一定的 select 语句。

第四，SQLRight 自动检测并移除语义模糊或者会产生随机结果的 SQL 语句。即使在 DBMS 没有逻辑错误的情况下，这些语句依然会导致运行结果不一致。去掉这些语句可以避免大部分的误报 (false positive)。

除此之外，SQLRight 提供了一套通用接口来辅助开发者更容易地开发新的 oracle 或者将 oracle 与当前的 fuzzing 技术相结合。这套接口包含四个通用 API：

• preprocess() 预处理 给定的 SQL 语句，比如删除产生随机结果的语句，或者加上对当前 oracle 必要的语句；
  

• attach_output() 添加必要的与 oracle 兼容的 select 语句；

• transform() 将给定的 SQL 语句转变成 “形式不同但语义相同” 的格式；

• compare() 允许开发者自定义判断 SQL 结果是否一致的方法。

这套通用接口为开发人员快速开发新 oracle 并付于实践提供了便利。

[工具评估]

作者在三个常用数据库上评估了 SQLRight 检测逻辑错误的表现。三个数据库包括：SQLite，PostgreSQL 和 MySQL。下图节选一部分的评估结果：

SQLRight 一共找到了 18 个 DBMS 逻辑错误，其中 14 个错误来自于 SQLite，4 个错误源于 MySQL；另外，SQLRight 工具还找到了 5 个内存漏洞，以及 4 个 Assertion Failure；其中大部分的漏洞都已被相关开发人员修复。

评估节选：在 SQLite 上测试不同工具使用 NoREC oracle 检测逻辑错误的能力。作者将 SQLRight 与Squirrel+oracle 和 SQLancer这两个已有工具做了对比。Squirrel 是当前最先进的 DBMS 内存漏洞检测工具。作者将 oracle 通用接口移植到 Squirrel，使其具备检测 DBMS 逻辑错误的能力。SQLancer 则是目前最先进的检测 DBMS 逻辑错误的工具。上图的结果表明，SQLRight 在 72 个小时内找到了明显更多的逻辑错误。

评估节选：在 SQLite 上测试代码覆盖率的反馈对使用 NoREC oracle 检测逻辑错误能力的影响。在这个实验中，作者移除了 SQLRight 的代码覆盖反馈，并构建了三个基准工具：这些基准工具要么丢掉了所有随机生成的语句 (drop)，要么随机保存变异后的语句(rand)，要么保存所有变异后的语句 (save)。从图中可知，基于代码覆盖率的反馈有助于 SQLRight 发现更多的 DBMS 逻辑错误。

评估节选：在 SQLite 上测试高质量 SQL 语句对使用 NoREC oracle 检测逻辑错误能力的影响。这个评估逐步移除了 SQLRight 里面提高生成语句质量的方法。由图可知，高质量的生成语句有助于 SQLRight 工具找到更多的 DBMS 逻辑错误。

论文PDF：https://steveleungyl.github.io/papers/liang-sqlright.pdf

代码地址：https://github.com/psu-security-universe/sqlright

本文作者均来自于宾夕法尼亚州立大学的系统安全实验室 。在完成本论文时, Yu Liang 为该院系一年级 PhD 学生，Song Liu 为奇安信技术研究院研究员，现已作为 PhD 学生加入ps3lab， Hong Hu 为该院系助理教授，同时也是ps3lab的领导老师之一。

实验室主页：https://ps3lab.github.io/

原文始发于微信公众号（安全研究GoSSIP）：G.O.S.S.I.P 阅读推荐 2022-08-25 Detecting logical bugs in DBMS