一种有趣的测试方法:pivoted query synthesis

2020-04-16

故事从前一阵子说起。有一哥们在短时间内,给我们报了大量的 bug。他是用机器人在测试我们的数据库。据说是测试了 SQLite,测试了 MySQL,测试了 PG,还有小强等等友商,小强被他折磨的修 bug 修不过来了,他就跑来我们这边试试。 一个人测试发现 bug 的速度,让一个团队都修复不过来,这还是非常生猛的。为什么这么牛X呢?他写了一篇论文的,使用了一种新的测试方法。

好,现在我们开始讲他的这篇文章了。这篇文章叫 Testing Database Engines via Pivoted Query Synthesis

在此之前,比较有效的一种测试方法是 Differential testing,当然 fuzz 是大家耳熟能详的。Differential 测试是构造许许多的 fuzz 输入,我们并不知道输入对应的输出结果是什么。不过 SQL 是一个比较通用的语言,对应着许许多多的实现。所以可以把输入发送到不同的实现,再去对比不同系统的输出结果。如果结果不同,就有可能是某个系统的行为有 bug 了。

我最早听说 Differential 这类的测试方法,是在编译器领域的测试里面。我们要测试编译器实现的 bug,用常规的手段是比较难找 bug 的,效率比较低。Differential 测试方法,可以这样搞:随机构造茫茫多的很小的程序片断,用不同的编译器去编译,因为语言是标准的,之后执行编译后的程序,则各程序的输出结果也应该是相同的,不管是用哪一个编译器编译。如果不同编译器编译出来,执行后生成的结果不一致,肯定有其中哪个实现是有问题的。

那篇文章说了一下 Differential 测试方法的缺点。SQL 尽管是一门语言,但是各种数据库的实现都有自己的方言和 feature,导致很多时候并不通用,这样交叉验证的方式局限性很大。另外,SQL 的查询条件的构造,一点点区别可能查询结果特别多,数据集不好控。

所有作者提出了 Pivoted Query 的方式。这个方法不再是构造输入后用不同实现交叉验证输出结果,而是,先挑一个确定的结果,比如说查询结果里面一行包含某一行,这个叫 pivote row,然后某个基础查询会出这个结果,在此之上去派生出其它的查询请求来。最后验证就是不管查询请求是啥,预期在结果里面一定是包含这样一行的。如果没有,就是发现 bug 了。

查询条件的构造过程举个例子,初始数据里面 c1 列有 0 1 2 NULL 这样四行,然后选择一个 pivot row 比如 c0 == NULL,我们确定了一个基本的查询条件 where c0 == NULL,接下来,我们在这基础上去派生出查询条件,c0 IS NOT 1 这个条件,跟 c0 == NULL 做 and 之后仍然是 TRUE 的,所以我们就可以派生出 where c0 == NULL and c0 IS NOT 1 这样的查询。类似的,我们还可以派出来 join 和其它的查询,只要最终生查的查询请求,结果里面会包含 pivot row。

具体的实现它是用表达式的 ast 生成,做一些基础变换,再筛选出结果为 true 的那些,去生成查询表达式。 列一下整体的流程:

  • 第一步,创建一些库和表,为每个表随机填一些数据,确保每个表都至少包含一行以上数据
  • 第二步,然后随机选出一行,这一行作为 pivot row
  • 第三步,根据这个 pivot row 确定一个 test oracle,基于 SQL 语法随机创建许多查询表达式
  • 第四步,对这些表达式,基于 pivot row 的对应的值替换表达式的列,确认修改表达式计算结果是 true
  • 第五步,在 where 或者 join 的查询条件里面使用这些我们构造的表达式
  • 第六步,调用数据库执行请求
  • 第七步,确认返回的执行结果里面,包含 pivot row

具体细节可以去看原文了。这篇文章其实 overview 部分已经把整个方法讲得很明白了。后面的内容就是一些实现的细节,然后在各个数据库里面的一些实验结果了。 不管是 SQLite,MySQL 还是 Postgres 都是茫茫多的 bug 的。

感慨一下现在的测试方法真是令人耳目一新。Differential 里面,我不知道什么样的结果是对,什么样的结果是错,可以交叉验证对错,这个过程就可以找 bug 了,而输入请求是可以瞎构造的。

在这篇 pivoted query 里面,确定一条 pivoted 的结果,在此基础上就可以瞎构造输入了。就有点像,把问题换了一个角度观察,攻守互换。

证明一个算法是对的,很难,因为无法枚举所有的情况。证明算法是错的更容易一些,因为我们只要找到一处反例,就可以证明算法是错的了。 直接思考程序哪里有 bug 的思维方式,就好比证明一个算法是对的,这很难。而 pivot row 确定一个约束,再以此约束条件下去构造查询,就好比假设算法是对的了,去寻找反例,只要有不满足约束了,就是找到 bug 了。

test