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

熊玉蘭

一、概論

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

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

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

二、 研究方法

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

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

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

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

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

程序導入（Program instrumentation），它的主要工作是：導入以及定位到與第一步中選擇的屬性有關的代碼片段，然后編譯這段代碼片段。

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

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

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

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

三、實驗評估

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

二項堆是一種支持快速合并的堆數據結構，采用二項樹（Binomial Tree）的集合進行實現。二項樹遞歸定義如下：

階為k的二項樹是由階為k-1， k-2， ， 2， 1， 0的二項樹的根節點作為k階二項樹的節點構成的。

二項堆是有二項樹的集合構成的，滿足如下二項堆性質：

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

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

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

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

這是因為第二種變種實現改變了鏈接二項樹的操作，會影響到堆的插入、刪除等各項操作，對產生的堆的結構產生了影響；而第一種變種實現僅會影響到findMin操作，不會對堆的結構產生影響。

四、結論

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