周 聚

(南京航空航天大學(xué)黨政辦公室，210000)

0 引言

現(xiàn)代數(shù)據(jù)庫管理系統(tǒng)以其豐富的功能和卓越的性能著稱，鑒于其內(nèi)部邏輯的高度耦合性，實(shí)現(xiàn)一個數(shù)據(jù)庫管理系統(tǒng)在工程上極具挑戰(zhàn)，用測試來保障工程實(shí)現(xiàn)的正確性是目前軟件工程領(lǐng)域最為重要的手段?，F(xiàn)代數(shù)據(jù)庫管理系統(tǒng)通常以符合SQL 標(biāo)準(zhǔn)的聲明性語言提供服務(wù)，對其進(jìn)行測試需要構(gòu)造一系列SQL 語句，盡可能地覆蓋所有的實(shí)現(xiàn)邏輯。自動化測試能夠減少人工重復(fù)勞動，尤其對于SQL 語言，要能夠覆蓋盡可能多的實(shí)現(xiàn)邏輯，需要構(gòu)造海量的測試用例，如果完全依賴手動構(gòu)造，將是一件極其繁復(fù)耗時的工程，如果能夠自動化地生成測試用例，將能夠大幅提升效率，從而加速數(shù)據(jù)庫管理系統(tǒng)的開發(fā)進(jìn)程。

本文實(shí)現(xiàn)了一個根據(jù)BNF 范式生成SQL 測試用例的自動化測試系統(tǒng)，BNF 范式是由John Backus 和Peter Naur 發(fā)明的一種用來描述給定語言語法的一種文法系統(tǒng)，目前主流的商用數(shù)據(jù)庫系統(tǒng)和大部分的開源數(shù)據(jù)庫系統(tǒng)都采用BNF 范式來描述其SQL 語言，在數(shù)據(jù)庫系統(tǒng)中，BNF 范式會被翻譯成一段程序，用來解析SQL 語言的詞法和語法。本文描述的測試用例生成系統(tǒng)則是利用BNF 范式來生成一組SQL 語句，盡可能多地覆蓋所有語法。

1 相關(guān)背景

首先，我們給出一個上下文無關(guān)文法的形式化定義，上下文無關(guān)文法被定義為一個四元組G=(VN,VT,S,P)，其中VN 是一個非終結(jié)符號集合，VT 是一個終結(jié)符號集合，S 是開始符號，P是產(chǎn)生式集合，P 中的每個元素都是一個產(chǎn)生式，產(chǎn)生式形如A::=a，其中A ∈VN 并且a ∈（VN ∪VT）*，A 稱作產(chǎn)生式的左端，而a 則稱為產(chǎn)生式的右端，整個產(chǎn)生式的物理意義是A 能夠被替換為a。BNF 范式通過引入一些符號，能夠很方便地表達(dá)上下文無關(guān)文法，對于文法中的一條產(chǎn)生式，BNF 范式用一條規(guī)則來表示，該規(guī)則形如A ::= ＜a＞ | B | [c] | 26smweq，其中產(chǎn)生式右端的“|”符號表示或的意思，被尖括號＜＞包圍的為必選項，被中括號[]包圍的為可選項，而被大括號{}包圍的元素則可以出現(xiàn)0次或多次。利用文法來生成測試用例集合的研究從上世紀(jì)70 年代就開始了，Hanford 最早提出隨機(jī)覆蓋法來生成測試用例，該方法比較簡單，計算復(fù)雜度也很小，但是不能保證覆蓋所有的規(guī)則。此后Purdom 提出Purdom 算法，該算法利用棧將候選規(guī)則展開，遇到終止符號就產(chǎn)生一條語句，然后回溯選取另一條候選規(guī)則，直到所有規(guī)則被窮盡為止，Purdom 算法能夠覆蓋全部規(guī)則，但生成的語句較少較復(fù)雜，所以不太適合真實(shí)生產(chǎn)系統(tǒng)。

2 核心算法

作為一個測試用例生成系統(tǒng)，系統(tǒng)的輸入是BNF 范式，輸出則是一組SQL 語句組成的測試集合，本文采用“代碼生成”技術(shù)來完成BNF 范式到SQL 語句的轉(zhuǎn)化，整個過程由兩個步驟組成，首先，對于輸入的BNF 范式，我們根據(jù)該范式生成一段程序代碼，然后對這段程序代碼進(jìn)行編譯得到二進(jìn)制文件；在第二階段，我們運(yùn)行一下這個生成的二進(jìn)制文件，該程序的輸出就是最終的SQL語句測試集了。第一個步驟是整個系統(tǒng)的核心算法過程，該算法主要負(fù)責(zé)根據(jù)輸入的BNF 范式生成一段代碼，它本身包含三個子過程，第一個過程對所有的BNF 范式進(jìn)行掃描，將范式中的所有非終結(jié)符號提取出來，并存放一個中間數(shù)據(jù)結(jié)構(gòu)中；然后在第二階段，生成函數(shù)框架，對于文法中的每一個非終結(jié)符，我們會為它生成一個函數(shù)，函數(shù)名為該終結(jié)符的文本；最后一步是生成函數(shù)體，將函數(shù)體填充入函數(shù)框架內(nèi)，就得到了最終的程序。函數(shù)體的生成是整個算法最為核心的部分，函數(shù)體生成需要處理三種典型的情況，第一是或符號的生成，其次是終結(jié)符的生成，最后是非終結(jié)符的生成。其中或符號表示某個非終結(jié)符能夠推導(dǎo)出多條規(guī)則，到底使用哪條規(guī)則，我們采用隨機(jī)的方法，因此或符號最終會生成一組switch，case 語句，通過隨機(jī)數(shù)來指定到底進(jìn)入哪一路分支。終結(jié)符的生成比較簡單，就直接在程序中加一條append語句，用于將該終結(jié)符添加到生成的SQL 語句中。最為復(fù)雜的是非終結(jié)符的生成，一般的非終結(jié)符是通過調(diào)用該非終結(jié)符對應(yīng)的函數(shù)生成SQL 語句，因此對于一般情況下的非終結(jié)符，只需要在程序中生成一個函數(shù)調(diào)用即可，但是有一類特殊的非終結(jié)符，它對應(yīng)的是數(shù)據(jù)庫中的某一個表名或者列名，這些非終結(jié)符是需要到元數(shù)據(jù)中去查詢的，因此會在這里生成一段代碼，用來從元數(shù)據(jù)模塊中獲取相應(yīng)的表名信息或列名信息。

3 系統(tǒng)總體設(shè)計及模塊功能

為了使得系統(tǒng)具有清晰的結(jié)構(gòu)，我們使用了模塊化的設(shè)計，整個系統(tǒng)包括以下幾個模塊，分別是：代碼生成模塊，參數(shù)配置模塊，元數(shù)據(jù)管理模塊，日志模塊和測試用例生成模塊。

3.1 代碼生成模塊

代碼生成模塊是整個系統(tǒng)的核心模塊，它負(fù)責(zé)將輸入的BNF范式轉(zhuǎn)化成一段C++的程序。該模塊首先對BNF 范式進(jìn)行預(yù)處理，生成一個中間數(shù)據(jù)結(jié)構(gòu)，最后再從中間數(shù)據(jù)結(jié)構(gòu)生成代碼邏輯。對于范式中的每條規(guī)則，我們先根據(jù)推出符號“::=”將其切分成左右兩部分，左部是一個非終結(jié)符，右部則是生成規(guī)則。然后再將其右部的生成規(guī)則根據(jù)或符號“|”進(jìn)行劃分并生成一個數(shù)組，每個數(shù)組元素就是一條候選規(guī)則。將左部的非終結(jié)符作為key，右部生成的數(shù)組作為value 插入到一個map 中，這個map 就是我們的中間數(shù)據(jù)結(jié)構(gòu)。中間數(shù)據(jù)結(jié)構(gòu)保留了BNF 范式的所有信息，并且將所有的非終結(jié)符都提取了出來，在最終生成代碼邏輯的時候，我們遍歷中間數(shù)據(jù)結(jié)構(gòu)map 中的所有鍵值，按照前文的代碼生成算法生成一組函數(shù)，再生成一個main 函數(shù)調(diào)用起始規(guī)則生成的函數(shù)。值得注意的是，后面的參數(shù)配置模塊，元數(shù)據(jù)管理模塊和日志模塊都會以代碼的形式生成嵌入到程序中，譬如需要在程序中輸出一條日志，代碼生成模塊會在需要輸出日志的地方加上一條log 語句，在編譯的時候，則需要將日志模塊的lib 一起編譯生成最終的可執(zhí)行文件。

3.2 參數(shù)配置模塊

參數(shù)配置模塊用來統(tǒng)一管理系統(tǒng)參數(shù)，所有的系統(tǒng)可配置參數(shù)都會被集中存放在一個配置文件中，當(dāng)系統(tǒng)啟動的時候，參數(shù)配置模塊會讀取該文件進(jìn)行參數(shù)加載，如需要改變配置，則僅需要對參數(shù)文件中的某個參數(shù)項進(jìn)行修改，再重啟系統(tǒng)，修改后的參數(shù)即會生效。

在我們的測試用例生成系統(tǒng)中，很多參數(shù)都是可以配置的，包括非終結(jié)符的嵌套層數(shù)，隨機(jī)數(shù)的生成算法，生成語句的最大長度，日志輸出等級等等。通過修改參數(shù)項，我們能夠生成適合生產(chǎn)系統(tǒng)實(shí)際情況的測試用例集合。參數(shù)配置模塊支持整型參數(shù)，浮點(diǎn)型參數(shù)，字符串型參數(shù)和布爾型參數(shù)，參數(shù)項的使用包括參數(shù)定義，參數(shù)聲明和參數(shù)使用三個部分，參數(shù)項是在配置文件中進(jìn)行定義的，參數(shù)項的定義由參數(shù)名，類型和值三部分組成，用戶可以進(jìn)行修改；在程序中如果要使用某個參數(shù)項，則需要對該參數(shù)項進(jìn)行聲明，聲明的過程實(shí)際上是在當(dāng)前文件中定義了一個變量，這個變量是跟配置文件中的某個參數(shù)相關(guān)聯(lián)的；最后聲明的變量就可以在程序中使用了。

3.3 元數(shù)據(jù)管理模塊

元數(shù)據(jù)管理模塊負(fù)責(zé)維護(hù)系統(tǒng)的元數(shù)據(jù)，元數(shù)據(jù)是指數(shù)據(jù)庫中的表信息和字段信息，這些信息被存放在一個元數(shù)據(jù)庫中，用戶可以增刪修改這些元數(shù)據(jù)信息。系統(tǒng)在最終生成SQL 語句的時候，元數(shù)據(jù)管理模塊會從元數(shù)據(jù)中取出表名和列名，填充到相應(yīng)的位置。元數(shù)據(jù)中的表信息包括表名和該表擁有的字段名，字段信息包括字段名，字段類型和字段的取值范圍。在生成SQL 語句的時候，首先會生成表名，然后根據(jù)表名去元數(shù)據(jù)庫中查詢該表擁有的字段，再對語句中的字段進(jìn)行相應(yīng)替換。

3.4 日志模塊

日志模塊負(fù)責(zé)記錄系統(tǒng)運(yùn)行的軌跡，對于大型生產(chǎn)系統(tǒng)來說，日志是保障系統(tǒng)可靠穩(wěn)定運(yùn)行的基礎(chǔ)，它不但能在系統(tǒng)運(yùn)行出錯的時候快速定位故障點(diǎn)，很多現(xiàn)代數(shù)據(jù)庫系統(tǒng)更是將日志系統(tǒng)作為系統(tǒng)監(jiān)控和審計的基礎(chǔ)系統(tǒng)。我們的日志系統(tǒng)擁有三個級別的日志，分別是調(diào)試級別，普通級別和警告級別，調(diào)試級別將輸出所有的日志，包括調(diào)試信息，一般在開發(fā)時使用；普通級別輸出普通信息和警告信息，在正常情況下使用；警告級別只輸出警告信息，通常在對系統(tǒng)性能有嚴(yán)格要求的情況下使用。日志的輸出級別可以通過參數(shù)項進(jìn)行配置。日志的輸出格式和輪換策略通過一個單獨(dú)的日志配置文件進(jìn)行配置，日志系統(tǒng)會在系統(tǒng)初始化的時候讀取該配置文件。輸出格式的可配置項比較多，它使用了模板機(jī)制，可以在日志中輸出時間，線程號和模塊等信息；而輪換策略則指定以什么樣的規(guī)則對日志進(jìn)行備份，通常我們選取每天產(chǎn)生一個新的日志文件。

3.5 測試用例生成模塊

測試用例生成模塊負(fù)責(zé)最終生成SQL 語句測試集，該模塊實(shí)際上是整個系統(tǒng)的驅(qū)動模塊，它驅(qū)動代碼生成模塊生成代碼，將生成的代碼跟參數(shù)配置模塊、元數(shù)據(jù)管理模塊以及日志模塊的lib 進(jìn)行聯(lián)編，生成可執(zhí)行的二進(jìn)制文件，然后fork 出一個進(jìn)程來運(yùn)行可執(zhí)行文件，最終生成一組SQL 語句作為測試集。

4 結(jié)語

現(xiàn)代數(shù)據(jù)庫管理系統(tǒng)的開發(fā)已經(jīng)在向TDD（Test Driven Development）發(fā)展，測試的地位日益凸顯，對于數(shù)據(jù)庫管理系統(tǒng)這類模塊高度耦合的系統(tǒng)，E2E（End To End）場景測試是最為重要的一類測試，E2E 場景測試有賴于構(gòu)建海量測試用例，本文提出的測試用例生成系統(tǒng)可以自動生成覆蓋所有SQL 語法的測試用例集合，能夠極大提升數(shù)據(jù)庫系統(tǒng)的開發(fā)效率。

[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.