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

熊玉蘭

一、概論

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

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

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

二、 研究方法

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

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

基于屬性的測(cè)試主要分為以下八個(gè)步驟：

屬性選擇（selecting a property）。它需要從一堆屬性池子中根據(jù)一些準(zhǔn)則選擇一個(gè)屬性來(lái)進(jìn)行測(cè)試。

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

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

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

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

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

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

三、實(shí)驗(yàn)評(píng)估

為了驗(yàn)證基于屬性的測(cè)試的有效性，我們?cè)O(shè)計(jì)了如下實(shí)驗(yàn)對(duì)其進(jìn)行驗(yàn)證，選擇二項(xiàng)堆（Binomial Heap）作為測(cè)試對(duì)象對(duì)其進(jìn)行基于屬性的測(cè)試。

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

階為k的二項(xiàng)樹(shù)是由階為k-1， k-2， ， 2， 1， 0的二項(xiàng)樹(shù)的根節(jié)點(diǎn)作為k階二項(xiàng)樹(shù)的節(jié)點(diǎn)構(gòu)成的。

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

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

堆中具有某階的二階樹(shù)具有唯一性。

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

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

這是因?yàn)榈诙N變種實(shí)現(xiàn)改變了鏈接二項(xiàng)樹(shù)的操作，會(huì)影響到堆的插入、刪除等各項(xiàng)操作，對(duì)產(chǎn)生的堆的結(jié)構(gòu)產(chǎn)生了影響；而第一種變種實(shí)現(xiàn)僅會(huì)影響到findMin操作，不會(huì)對(duì)堆的結(jié)構(gòu)產(chǎn)生影響。

四、結(jié)論

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