數據庫測試用例生成系統設計與實現

周 聚

(南京航空航天大學黨政辦公室，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] | g0gggggg，其中產生式右端的“|”符號表示或的意思，被尖括號＜＞包圍的為必選項，被中括號[]包圍的為可選項，而被大括號{}包圍的元素則可以出現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.