數(shù)據(jù)庫測(cè)試用例生成系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

周 聚

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

0 引言

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

本文實(shí)現(xiàn)了一個(gè)根據(jù)BNF 范式生成SQL 測(cè)試用例的自動(dòng)化測(cè)試系統(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 范式會(huì)被翻譯成一段程序，用來解析SQL 語言的詞法和語法。本文描述的測(cè)試用例生成系統(tǒng)則是利用BNF 范式來生成一組SQL 語句，盡可能多地覆蓋所有語法。

1 相關(guān)背景

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

2 核心算法

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

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

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

3.1 代碼生成模塊

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

3.2 參數(shù)配置模塊

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

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

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

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

3.4 日志模塊

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

3.5 測(cè)試用例生成模塊

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

4 結(jié)語

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