針對函數(shù)式編程語言的基于屬性的測試方法研究

熊玉蘭

一、概論

如何提高軟件質(zhì)量是軟件工程致力解決的關(guān)鍵問題之一。軟件測試和驗證是保證軟件正確性和提高可靠性的最基本和最重要的手段，也是工業(yè)界使用的主流技術(shù)。軟件測試有不同的方法，基本可以劃分為基于程序的測試和基于規(guī)范的測試兩大范疇?；诔绦虻臏y試根據(jù)程序特征代碼（如：語句、分支、路徑）產(chǎn)生測試樣例，并以相應(yīng)程序代碼特征是否得到充分測試作為測試終止的判定標準，即測試充分性準則?；谝?guī)范的測試要求根據(jù)功能規(guī)范和設(shè)計規(guī)范產(chǎn)生測試用例，針對相應(yīng)的功能和設(shè)計屬性進行測試，并以相關(guān)屬性是否得到充分測試作為測試充分性準則。

到目前為止，工業(yè)界在軟件開發(fā)過程中采用的測試技術(shù)大多是非系統(tǒng)化的，具有可靠性高、實時性強等要求，通常的完整的軟件測試工作需要耗費大量的人力物力，基本上會占據(jù)軟件開發(fā)周期50%甚至更多的時間。特別地，對于一些特殊的軟件，比如：安全攸關(guān)實時軟件（火箭控制等），他們的高復雜性和高安全需求使得傳統(tǒng)的基于程序代碼的測試在技術(shù)上難以實現(xiàn)，開銷上難以接受。

對于特定目的，采用某些特定結(jié)構(gòu)的程序可以采用一類稱為隨機測試的方法。隨機測試是一種有效的測試策略，該策略簡單易行、成本低，不需要過多了解軟件的內(nèi)部結(jié)構(gòu)的信息，只是按照一定的規(guī)則在整個輸入域中隨機產(chǎn)生測試用例，因而被廣泛地用于軟件測試和可靠性評估中。同時，高昂的測試代價不斷促進研究人員考慮能否有自動化測試的方法，不管是全部自動化還是部分自動化。自動化的測試工具可以幫助編程人員在很短的時間內(nèi)完成測試，并且很容易在每次程序修改過之后重復測試。目前為止，有一類QuickCheck的工具，可以用于測試Haskell程序。

二、 研究方法

一個屬性為基礎(chǔ)的測試框架通常會一遍又一遍地運行相同的生成測試數(shù)據(jù)，這個設(shè)置和當前基于樣例的測試架構(gòu)不太一樣，在基于樣例的測試中，每個單元測試都設(shè)置了一個輸入的情況，然后運行測試的代碼，最后檢查輸出（以及然后代碼應(yīng)該有的其他的影響）。相反的是，一個屬性為基礎(chǔ)的測試通常會運行數(shù)百次不同的輸入，這個測試的框架通常會考慮一些比較邊緣的情況，比如：傳遞空列表、負值、所有可能的邊緣情況，來使測試發(fā)生失敗，以達到學習的目的。

基于屬性的測試人員必須非常仔細地考慮各種各樣的規(guī)范和細節(jié)。比如：支持什么樣的輸入？輸入如何產(chǎn)生？可以對輸入做哪些申明？這些考慮都是非常必要的。

基于屬性的測試主要分為以下八個步驟：

屬性選擇（selecting a property）。它需要從一堆屬性池子中根據(jù)一些準則選擇一個屬性來進行測試。

靜態(tài)分析（Static analysis and slicing），它主要做的工作是為源代碼生成一個基于數(shù)據(jù)流的圖，這個圖通常在基于屬性的其他步驟中有很多作用。

程序?qū)耄≒rogram instrumentation），它的主要工作是：導入以及定位到與第一步中選擇的屬性有關(guān)的代碼片段，然后編譯這段代碼片段。

初步測試（Initial test execution），它的主要工作是：使用之前產(chǎn)生的各種各樣的測試數(shù)據(jù)進行初步測試。

范圍測試（Coverage evaluation），它的主要工作是：根據(jù)第四部測試執(zhí)行過程中產(chǎn)生的代碼片段執(zhí)行的歷史記錄來分析哪些路徑是被執(zhí)行的，以此來得到一個所謂的范圍。

額外測試（Additional test case），它的主要任務(wù)是：根據(jù)第五步返回的結(jié)果進行進一步的測試。

正確性評估（Correctness evaluation），它的主要任務(wù)是：將之前的測試結(jié)果與期望結(jié)果進行比較，依次來判斷基于該屬性的測試是否成功。

三、實驗評估

為了驗證基于屬性的測試的有效性，我們設(shè)計了如下實驗對其進行驗證，選擇二項堆（Binomial Heap）作為測試對象對其進行基于屬性的測試。

二項堆是一種支持快速合并的堆數(shù)據(jù)結(jié)構(gòu)，采用二項樹（Binomial Tree）的集合進行實現(xiàn)。二項樹遞歸定義如下：

階為k的二項樹是由階為k-1， k-2， ， 2， 1， 0的二項樹的根節(jié)點作為k階二項樹的節(jié)點構(gòu)成的。

二項堆是有二項樹的集合構(gòu)成的，滿足如下二項堆性質(zhì)：

堆中的每一棵二項都樹滿足最小堆性質(zhì)，即結(jié)點的值大于其父節(jié)點的值；

堆中具有某階的二階樹具有唯一性。

我們采用Scala實現(xiàn)了中的二項堆，并且設(shè)計實現(xiàn)了5種具有缺陷的二項堆，對這6種二項堆進行了屬性測試。具有缺陷的二項堆對原二項堆的實現(xiàn)進行了變種，使其在某些特定情況下會不滿足二項堆的性質(zhì)。

我們還設(shè)計了6個屬性，采用基于屬性的測試方法對這6種堆實現(xiàn)進行測試，這些屬性都是根據(jù)二項堆的性質(zhì)進行設(shè)計的，所以正確的二項堆實現(xiàn)會全部滿足這些屬性，而我們設(shè)計實現(xiàn)的具有缺陷的二項堆將會違背某個屬性。

這是因為第二種變種實現(xiàn)改變了鏈接二項樹的操作，會影響到堆的插入、刪除等各項操作，對產(chǎn)生的堆的結(jié)構(gòu)產(chǎn)生了影響；而第一種變種實現(xiàn)僅會影響到findMin操作，不會對堆的結(jié)構(gòu)產(chǎn)生影響。

四、結(jié)論

本文對基于屬性的測試進行了研究，實驗中采用Scala編程語言對純函數(shù)式二項堆進行了實現(xiàn)，并設(shè)計實驗了五種具有缺陷的二項堆，并定義了六種滿足二項堆性質(zhì)的屬性，采用基于屬性的測試對二項堆進行測試，通過實驗結(jié)果證明了基于屬性的測試的有效性。