欒家偉 吳 陳

（江蘇科技大學(xué) 鎮(zhèn)江 212003）

1 引言

隨著軟件行業(yè)的蓬勃發(fā)展，軟件的逐漸規(guī)范化以及軟件規(guī)模的日益遞增，不僅僅表面上繁重軟件開(kāi)發(fā)工作，規(guī)模遞增的軟件也意味著有著大量的軟件測(cè)試工作，甚至往往軟件測(cè)試工作占據(jù)一半以上的軟件開(kāi)發(fā)周期。所以面對(duì)巨大的軟件測(cè)試工作量必須提高測(cè)試效率，減少開(kāi)發(fā)周期降低開(kāi)發(fā)成本，并且能夠同時(shí)完成測(cè)試目標(biāo)提高軟件質(zhì)量。

面向?qū)ο蟮慕y(tǒng)一建模語(yǔ)言UML主要由圖形、模型元素、視圖以及通用機(jī)制組成。主要用于描述軟件規(guī)格、可視化研究、軟件系統(tǒng)的建模與分析。UML可以針對(duì)不同的軟件開(kāi)發(fā)方法，貫穿軟件生命周期的各個(gè)階段。UML通常用來(lái)描述對(duì)象、子系統(tǒng)、系統(tǒng)的狀態(tài)遷移關(guān)系。描述面向?qū)ο箢?lèi)的某一對(duì)象整個(gè)生存周期的具體行為。直觀地給出了特定對(duì)象可能進(jìn)入的所有狀態(tài)，以及該對(duì)象的狀態(tài)如何影響該對(duì)象的事件。

本文選取UML圖形中的狀態(tài)圖用以研究如何基于UML實(shí)現(xiàn)測(cè)試用例的自動(dòng)生成。狀態(tài)圖主要是由狀態(tài)和變遷組成的圖，包括事件、狀態(tài)、變遷三個(gè)部分。UML狀態(tài)圖是UML中對(duì)系統(tǒng)的動(dòng)態(tài)行為進(jìn)行建模的表示方法，它包括對(duì)反應(yīng)型對(duì)象的行為建模。UML狀態(tài)圖能夠直觀地給出了特定對(duì)象可能進(jìn)入的所有狀態(tài)和觸發(fā)狀態(tài)轉(zhuǎn)移的條件，以及對(duì)象的動(dòng)作行為，通常表現(xiàn)為狀態(tài)所經(jīng)歷的狀態(tài)序列，也包含引起狀態(tài)轉(zhuǎn)移的事件，以及狀態(tài)轉(zhuǎn)移伴隨的動(dòng)作，它可以對(duì)一個(gè)對(duì)象的生命周期建模［1］。UML狀態(tài)圖其實(shí)就是代表一個(gè)狀態(tài)機(jī)，刻畫(huà)描述對(duì)象狀態(tài)變遷。

J.Offutt等曾經(jīng)提出關(guān)于UML狀態(tài)圖主要有四個(gè)測(cè)試覆蓋準(zhǔn)則：狀態(tài)覆蓋準(zhǔn)則、狀態(tài)變遷覆蓋準(zhǔn)則、狀態(tài)變遷對(duì)覆蓋準(zhǔn)則、全序列覆蓋準(zhǔn)則。并開(kāi)發(fā)了一個(gè)驗(yàn)證性的測(cè)試用例生成工具UMLTest實(shí)現(xiàn)了對(duì)Rational Rose模型文件的解析，從而讀出狀態(tài)圖模型，然后利用相應(yīng)的測(cè)試準(zhǔn)則來(lái)產(chǎn)生測(cè)試用例［2］。

2 基于深度優(yōu)先算法的路徑覆蓋策略

基于UML模型生成軟件測(cè)試主要是對(duì)軟件系統(tǒng)進(jìn)行UML建模，根據(jù)需求規(guī)格說(shuō)明所建立的UML模型的狀態(tài)圖，提取對(duì)應(yīng)信息將其轉(zhuǎn)化為有向圖，用深度優(yōu)先算法對(duì)有向圖進(jìn)行遍歷得到相應(yīng)的測(cè)試用例。

路徑覆蓋：在白盒測(cè)試中，路徑覆蓋能夠滿(mǎn)足設(shè)計(jì)出足夠多的測(cè)試用例，覆蓋程序中所有可能的路徑以達(dá)到覆蓋度最高。但是當(dāng)程序過(guò)于復(fù)雜，判斷和循環(huán)過(guò)多時(shí)，實(shí)現(xiàn)路徑的完全覆蓋卻幾乎是不可能的。程序中的路徑數(shù)（復(fù)雜度）通過(guò)公式V（G）=e-n+2得到（e為邊數(shù)，n為節(jié)點(diǎn)數(shù)）。

深度優(yōu)先算法思想從圖的頂點(diǎn)V出發(fā)，訪問(wèn)V的未被訪問(wèn)鄰接點(diǎn)V'，再?gòu)腣'出發(fā)，繼續(xù)訪問(wèn)未被訪問(wèn)的鄰接點(diǎn)，直至一個(gè)不存在未被訪問(wèn)鄰接點(diǎn)的某節(jié)點(diǎn)，此時(shí)返回上一個(gè)存在未被訪問(wèn)鄰接點(diǎn)的節(jié)點(diǎn)，當(dāng)所有節(jié)點(diǎn)的鄰接點(diǎn)都處于已被訪問(wèn)狀態(tài)，結(jié)束遍歷。路徑覆蓋策略實(shí)現(xiàn)過(guò)程如圖1。

圖1 路徑覆蓋策略

利用深度優(yōu)先算法對(duì)有向圖進(jìn)行遍歷從而實(shí)現(xiàn)路徑覆蓋的目的。從圖的開(kāi)始節(jié)點(diǎn)進(jìn)行遍歷，一直到路徑的結(jié)尾，遇到分支即進(jìn)行拷貝，用二維數(shù)組event［rows］［0］存儲(chǔ)事件集合，path［rows］［1］存儲(chǔ)路徑集合，當(dāng)path是完整路徑時(shí)結(jié)束遍歷循環(huán)。

不過(guò)在開(kāi)始路徑尋找之前，首先判斷是否有分支

Isbranch（s，n，i）｛

If（s［i］.start==s［num］.start&&s［i］.end！=s［num］.end）；

｝

如果存在分支的話(huà)，還需要進(jìn)行起始節(jié)點(diǎn)和分支節(jié)點(diǎn)的判斷，如果該節(jié)點(diǎn)為起始節(jié)點(diǎn)，則進(jìn)行下面的處理：

If（s［i］.start==“start”）｛

event［rows］［0］=s［i］.sevent+“”；

path［rows］［1］=s［i］.start+“-＞”+s［i］.end；

｝

如果判斷為該節(jié)點(diǎn)為分支節(jié)點(diǎn)，則如下處理：

event［rows］［0］=event［rows］［0］+s［i］.sevent+“”；

path［rows］［1］=path［rows］［1］+“-＞”+s［i］.end；

3 基于貪心算法和回溯法的語(yǔ)句覆蓋策略

在采用語(yǔ)句覆蓋策略時(shí)，先通過(guò)貪心算法對(duì)進(jìn)行第一次遍歷，每個(gè)節(jié)點(diǎn)只遍歷一次。如果節(jié)點(diǎn)為聚合節(jié)點(diǎn)或者分支節(jié)點(diǎn)的特殊情況下，可能會(huì)出現(xiàn)節(jié)點(diǎn)遍歷遺漏的情況，這種情況下基于回溯法的思想，采用雙向回溯，實(shí)現(xiàn)回溯功能。

對(duì)節(jié)點(diǎn)的上下遍歷過(guò)程進(jìn)行檢查，如果該節(jié)點(diǎn)存在下一個(gè)未遍歷過(guò)程則返回該節(jié)點(diǎn)在數(shù)組中的下標(biāo)，則進(jìn)行如下的處理：

isnext=Istrackingnext（s，n，finals）；//測(cè)試是否存在下一個(gè)

未訪問(wèn)過(guò)的節(jié)點(diǎn)

intIstrackingnext（Swant s［］，int n，String finals）｛

for（int j=0；j＜n；j++）｛

if（s［j］.state==1&&s［j］.start==finals）

return j；

｝｝

當(dāng)只存在下節(jié)點(diǎn)未遍歷時(shí)，對(duì)下節(jié)點(diǎn)進(jìn)行遍歷，然后將結(jié)束節(jié)點(diǎn)標(biāo)記置為下節(jié)點(diǎn)的結(jié)尾，并將下結(jié)點(diǎn)設(shè)置為已遍歷訪問(wèn)。

If（isnext=！-1&&ispre==-1）//當(dāng)只存在下節(jié)點(diǎn)時(shí)操作

｛

getnxtevent=s ［isnext］.DateOfConditionOrPredicateAnd?Condition（s［isnext］.sevent）；

event［rows］［0］=event［rows］［0］+“”+getnxtdate［1］；

path［rows］［1］=path［rows］［1］+“-＞”+s［isnext］.end；

finals=s［isnext］.end；//將結(jié)束節(jié)點(diǎn)標(biāo)記置為下節(jié)點(diǎn)的末尾

s［isnext］.state=0；//下節(jié)點(diǎn)置已訪問(wèn)標(biāo)記

｝

如果該節(jié)點(diǎn)存在上一個(gè)未遍歷的過(guò)程則進(jìn)行如下處理：

ispre=Istrackingpre（s，n，begin）；//測(cè)試是否存在上一個(gè)未訪問(wèn)過(guò)的節(jié)點(diǎn)

int Istrackingpre（Swant s［］，int n，String begin）｛

for（int j=0；j＜n；j++）｛

if（s［j］.state==1&&s［j］.end==begin）

return j；

｝｝

當(dāng)存在上節(jié)點(diǎn)未遍歷時(shí)，對(duì)上節(jié)點(diǎn)進(jìn)行遍歷，然后將開(kāi)始節(jié)點(diǎn)標(biāo)記置為上節(jié)點(diǎn)的開(kāi)頭，并將上節(jié)點(diǎn)設(shè)置為已遍歷訪問(wèn)。

If（isnext==-1&&ispre！=-1）//當(dāng)只存在上節(jié)點(diǎn)時(shí)操作

｛

getpreevent=s ［ispre］.DateOfConditionOrPredicateAnd?Condition（s［ispre］.sevent）；

event［rows］［0］=getpreevent［1］+“ ”+event［rows］［0］；

path［rows］［1］=s［ispre］.start+“-＞”+path［rows］［1］；

begin=s［ispre］.start；//將開(kāi)始節(jié)點(diǎn)標(biāo)記置為上節(jié)點(diǎn)的開(kāi)頭

s［ispre］.start=0；//上節(jié)點(diǎn)置已訪問(wèn)標(biāo)記

｝

如果上下節(jié)點(diǎn)都存在未訪問(wèn)的情況，將開(kāi)始節(jié)點(diǎn)標(biāo)記設(shè)置為上節(jié)點(diǎn)的開(kāi)頭，結(jié)束節(jié)點(diǎn)標(biāo)記設(shè)置為下節(jié)點(diǎn)的末尾，并將上下節(jié)點(diǎn)設(shè)置為已遍歷訪問(wèn)。

if（isnext！=-1&&ispre！=-1）//上下節(jié)點(diǎn)都存在時(shí)進(jìn)行的操作

｛

getpreevent=s ［ispre］.DateOfConditionOrPredicateAnd?Condition（s［ispre］.sevent）；

getnxtevent=s ［isnext］.DateOfConditionOrPredicateAnd?Condition（s［isnext］.sevent）；

event［rows］［0］=getpreevent［1］+“”+event［rows］［0］+“”+getnxtevent［1］；

path［rows］［1］=s［ispre］.start+“-＞”+path［rows］［1］+“-＞”+s［isnext］.end；

begin=s［ispre］.start；//將開(kāi)始節(jié)點(diǎn)標(biāo)記置為上節(jié)點(diǎn)的開(kāi)頭

finals=s［isnext］.end；//將結(jié)束節(jié)點(diǎn)標(biāo)記置為下節(jié)點(diǎn)的末尾

s［ispre］.state=0；//上節(jié)點(diǎn)置已訪問(wèn)標(biāo)記

s［isnext］.state=0；//下節(jié)點(diǎn)置已訪問(wèn)標(biāo)記｝

4 結(jié)語(yǔ)

軟件測(cè)試是為了發(fā)現(xiàn)軟件開(kāi)發(fā)的錯(cuò)誤，測(cè)試用例的自動(dòng)生成對(duì)于整個(gè)軟件開(kāi)發(fā)的效率和軟件質(zhì)量有著巨大的促進(jìn)作用。UML狀態(tài)圖能夠通過(guò)描述對(duì)象的狀態(tài)變化，提供對(duì)象在整個(gè)生命周期中的詳細(xì)狀態(tài)信息。本文研究了基于UML狀態(tài)圖實(shí)現(xiàn)測(cè)試用例的生成，主要介紹了兩種生成策略，將白盒測(cè)試技術(shù)中的路徑覆蓋以及語(yǔ)句覆蓋和UML狀態(tài)圖相結(jié)合，以此實(shí)現(xiàn)測(cè)試用例的自動(dòng)生成。今后可能還會(huì)嘗試基于UML中其他如類(lèi)圖，活動(dòng)圖等實(shí)現(xiàn)測(cè)試用例的生成進(jìn)行更多研究探討。