周 聚

(南京航空航天大学党政办公室，210000)

0 引言

现代数据库管理系统以其丰富的功能和卓越的性能著称，鉴于其内部逻辑的高度耦合性，实现一个数据库管理系统在工程上极具挑战，用测试来保障工程实现的正确性是目前软件工程领域最为重要的手段。现代数据库管理系统通常以符合SQL 标准的声明性语言提供服务，对其进行测试需要构造一系列SQL 语句，尽可能地覆盖所有的实现逻辑。自动化测试能够减少人工重复劳动，尤其对于SQL 语言，要能够覆盖尽可能多的实现逻辑，需要构造海量的测试用例，如果完全依赖手动构造，将是一件极其繁复耗时的工程，如果能够自动化地生成测试用例，将能够大幅提升效率，从而加速数据库管理系统的开发进程。

本文实现了一个根据BNF 范式生成SQL 测试用例的自动化测试系统，BNF 范式是由John Backus 和Peter Naur 发明的一种用来描述给定语言语法的一种文法系统，目前主流的商用数据库系统和大部分的开源数据库系统都采用BNF 范式来描述其SQL 语言，在数据库系统中，BNF 范式会被翻译成一段程序，用来解析SQL 语言的词法和语法。本文描述的测试用例生成系统则是利用BNF 范式来生成一组SQL 语句，尽可能多地覆盖所有语法。

1 相关背景

首先，我们给出一个上下文无关文法的形式化定义，上下文无关文法被定义为一个四元组G=(VN,VT,S,P)，其中VN 是一个非终结符号集合，VT 是一个终结符号集合，S 是开始符号，P是产生式集合，P 中的每个元素都是一个产生式，产生式形如A::=a，其中A ∈VN 并且a ∈（VN ∪VT）*，A 称作产生式的左端，而a 则称为产生式的右端，整个产生式的物理意义是A 能够被替换为a。BNF 范式通过引入一些符号，能够很方便地表达上下文无关文法，对于文法中的一条产生式，BNF 范式用一条规则来表示，该规则形如A ::= ＜a＞ | B | [c] | {d}，其中产生式右端的“|”符号表示或的意思，被尖括号＜＞包围的为必选项，被中括号[]包围的为可选项，而被大括号{}包围的元素则可以出现0次或多次。利用文法来生成测试用例集合的研究从上世纪70 年代就开始了，Hanford 最早提出随机覆盖法来生成测试用例，该方法比较简单，计算复杂度也很小，但是不能保证覆盖所有的规则。此后Purdom 提出Purdom 算法，该算法利用栈将候选规则展开，遇到终止符号就产生一条语句，然后回溯选取另一条候选规则，直到所有规则被穷尽为止，Purdom 算法能够覆盖全部规则，但生成的语句较少较复杂，所以不太适合真实生产系统。

2 核心算法

作为一个测试用例生成系统，系统的输入是BNF 范式，输出则是一组SQL 语句组成的测试集合，本文采用“代码生成”技术来完成BNF 范式到SQL 语句的转化，整个过程由两个步骤组成，首先，对于输入的BNF 范式，我们根据该范式生成一段程序代码，然后对这段程序代码进行编译得到二进制文件；在第二阶段，我们运行一下这个生成的二进制文件，该程序的输出就是最终的SQL语句测试集了。第一个步骤是整个系统的核心算法过程，该算法主要负责根据输入的BNF 范式生成一段代码，它本身包含三个子过程，第一个过程对所有的BNF 范式进行扫描，将范式中的所有非终结符号提取出来，并存放一个中间数据结构中；然后在第二阶段，生成函数框架，对于文法中的每一个非终结符，我们会为它生成一个函数，函数名为该终结符的文本；最后一步是生成函数体，将函数体填充入函数框架内，就得到了最终的程序。函数体的生成是整个算法最为核心的部分，函数体生成需要处理三种典型的情况，第一是或符号的生成，其次是终结符的生成，最后是非终结符的生成。其中或符号表示某个非终结符能够推导出多条规则，到底使用哪条规则，我们采用随机的方法，因此或符号最终会生成一组switch，case 语句，通过随机数来指定到底进入哪一路分支。终结符的生成比较简单，就直接在程序中加一条append语句，用于将该终结符添加到生成的SQL 语句中。最为复杂的是非终结符的生成，一般的非终结符是通过调用该非终结符对应的函数生成SQL 语句，因此对于一般情况下的非终结符，只需要在程序中生成一个函数调用即可，但是有一类特殊的非终结符，它对应的是数据库中的某一个表名或者列名，这些非终结符是需要到元数据中去查询的，因此会在这里生成一段代码，用来从元数据模块中获取相应的表名信息或列名信息。

3 系统总体设计及模块功能

为了使得系统具有清晰的结构，我们使用了模块化的设计，整个系统包括以下几个模块，分别是：代码生成模块，参数配置模块，元数据管理模块，日志模块和测试用例生成模块。

3.1 代码生成模块

代码生成模块是整个系统的核心模块，它负责将输入的BNF范式转化成一段C++的程序。该模块首先对BNF 范式进行预处理，生成一个中间数据结构，最后再从中间数据结构生成代码逻辑。对于范式中的每条规则，我们先根据推出符号“::=”将其切分成左右两部分，左部是一个非终结符，右部则是生成规则。然后再将其右部的生成规则根据或符号“|”进行划分并生成一个数组，每个数组元素就是一条候选规则。将左部的非终结符作为key，右部生成的数组作为value 插入到一个map 中，这个map 就是我们的中间数据结构。中间数据结构保留了BNF 范式的所有信息，并且将所有的非终结符都提取了出来，在最终生成代码逻辑的时候，我们遍历中间数据结构map 中的所有键值，按照前文的代码生成算法生成一组函数，再生成一个main 函数调用起始规则生成的函数。值得注意的是，后面的参数配置模块，元数据管理模块和日志模块都会以代码的形式生成嵌入到程序中，譬如需要在程序中输出一条日志，代码生成模块会在需要输出日志的地方加上一条log 语句，在编译的时候，则需要将日志模块的lib 一起编译生成最终的可执行文件。

3.2 参数配置模块

参数配置模块用来统一管理系统参数，所有的系统可配置参数都会被集中存放在一个配置文件中，当系统启动的时候，参数配置模块会读取该文件进行参数加载，如需要改变配置，则仅需要对参数文件中的某个参数项进行修改，再重启系统，修改后的参数即会生效。

在我们的测试用例生成系统中，很多参数都是可以配置的，包括非终结符的嵌套层数，随机数的生成算法，生成语句的最大长度，日志输出等级等等。通过修改参数项，我们能够生成适合生产系统实际情况的测试用例集合。参数配置模块支持整型参数，浮点型参数，字符串型参数和布尔型参数，参数项的使用包括参数定义，参数声明和参数使用三个部分，参数项是在配置文件中进行定义的，参数项的定义由参数名，类型和值三部分组成，用户可以进行修改；在程序中如果要使用某个参数项，则需要对该参数项进行声明，声明的过程实际上是在当前文件中定义了一个变量，这个变量是跟配置文件中的某个参数相关联的；最后声明的变量就可以在程序中使用了。

3.3 元数据管理模块

元数据管理模块负责维护系统的元数据，元数据是指数据库中的表信息和字段信息，这些信息被存放在一个元数据库中，用户可以增删修改这些元数据信息。系统在最终生成SQL 语句的时候，元数据管理模块会从元数据中取出表名和列名，填充到相应的位置。元数据中的表信息包括表名和该表拥有的字段名，字段信息包括字段名，字段类型和字段的取值范围。在生成SQL 语句的时候，首先会生成表名，然后根据表名去元数据库中查询该表拥有的字段，再对语句中的字段进行相应替换。

3.4 日志模块

日志模块负责记录系统运行的轨迹，对于大型生产系统来说，日志是保障系统可靠稳定运行的基础，它不但能在系统运行出错的时候快速定位故障点，很多现代数据库系统更是将日志系统作为系统监控和审计的基础系统。我们的日志系统拥有三个级别的日志，分别是调试级别，普通级别和警告级别，调试级别将输出所有的日志，包括调试信息，一般在开发时使用；普通级别输出普通信息和警告信息，在正常情况下使用；警告级别只输出警告信息，通常在对系统性能有严格要求的情况下使用。日志的输出级别可以通过参数项进行配置。日志的输出格式和轮换策略通过一个单独的日志配置文件进行配置，日志系统会在系统初始化的时候读取该配置文件。输出格式的可配置项比较多，它使用了模板机制，可以在日志中输出时间，线程号和模块等信息；而轮换策略则指定以什么样的规则对日志进行备份，通常我们选取每天产生一个新的日志文件。

3.5 测试用例生成模块

测试用例生成模块负责最终生成SQL 语句测试集，该模块实际上是整个系统的驱动模块，它驱动代码生成模块生成代码，将生成的代码跟参数配置模块、元数据管理模块以及日志模块的lib 进行联编，生成可执行的二进制文件，然后fork 出一个进程来运行可执行文件，最终生成一组SQL 语句作为测试集。

4 结语

现代数据库管理系统的开发已经在向TDD（Test Driven Development）发展，测试的地位日益凸显，对于数据库管理系统这类模块高度耦合的系统，E2E（End To End）场景测试是最为重要的一类测试，E2E 场景测试有赖于构建海量测试用例，本文提出的测试用例生成系统可以自动生成覆盖所有SQL 语法的测试用例集合，能够极大提升数据库系统的开发效率。

[1] Harm J,Lammel R. Two-dimensional Approximation Coverage[J]. Informatica,2000,24(3)

[2] Knuth D Semantics of context-free languages[J] Mathematical Systems Theory,1968,2:127-145 Corrections in 1971,5:95-96

[3] Hanford KV. Automatic generation of test cases [J] IBM Systems Journal,1970(4)

[4] Purdom,Paul. "A sentence generator for testing parsers." BIT Numerical Mathematics 12.3 (1972): 366-375.