基于CP-nets模型的并行軟件測(cè)試方法研究.pdf

1、在軟件產(chǎn)業(yè)高速發(fā)展的今天，并行軟件系統(tǒng)已經(jīng)成為一類主流的軟件系統(tǒng)，在社會(huì)生產(chǎn)和生活中發(fā)揮著重要的作用。例如，網(wǎng)絡(luò)軟件系統(tǒng)，包括基于云計(jì)算的軟件系統(tǒng)和基于物聯(lián)網(wǎng)的軟件系統(tǒng)，大都具有并行性特點(diǎn)。
　　對(duì)并行軟件進(jìn)行測(cè)試的難度非常大，因?yàn)椴⑿熊浖臓顟B(tài)空間規(guī)模都很大，軟件中的并行行為導(dǎo)致其狀態(tài)空間規(guī)模呈指數(shù)級(jí)增長(zhǎng)。工業(yè)界大量使用的手工測(cè)試方法無(wú)法完成對(duì)并行軟件的測(cè)試;學(xué)術(shù)界很多基于形式化模型的自動(dòng)測(cè)試方法，也受困于并行行為所導(dǎo)致的狀態(tài)爆

2、炸問(wèn)題，很難有效完成測(cè)試。有的形式化方法并不適合于對(duì)狀態(tài)數(shù)目大的并行軟件進(jìn)行建模，例如有限狀態(tài)機(jī)(FiniteStateMachine，F(xiàn)SM)，所以基于此類模型的經(jīng)典測(cè)試方法都不能適用于并行軟件;有的形式化方法可以完成對(duì)并行軟件的建模，例如著色Petri網(wǎng)(ColoredPetriNets，CP-nets)和符號(hào)變遷系統(tǒng)(LabelledTransitionSystem，LTS)，但是，現(xiàn)有的基于這些模型的測(cè)試方法大都不針對(duì)并行行為作

3、特殊處理，所以生成的測(cè)試序列數(shù)量大、覆蓋率低、冗余度高，無(wú)法有效地針對(duì)并行軟件進(jìn)行測(cè)試。本文認(rèn)為，解決并行軟件的測(cè)試問(wèn)題，一方面要選擇適合于并行行為建模和測(cè)試的形式化建模語(yǔ)言;另一方面要基于這種語(yǔ)言提出針對(duì)并行行為具有高覆蓋率、低冗余率、高執(zhí)行效率的測(cè)試方法。
　　本文選擇形式化建模語(yǔ)言CP-nets為待測(cè)并行軟件系統(tǒng)建模，并針對(duì)并行軟件測(cè)試問(wèn)題提出了完整的解決方法。首先，針對(duì)系統(tǒng)模型狀態(tài)空間規(guī)模過(guò)大的問(wèn)題，提出了基于跡等價(jià)的模型

4、化簡(jiǎn)算法，能夠在不改變測(cè)試結(jié)果的前提下縮小系統(tǒng)狀態(tài)空間規(guī)模，提升測(cè)試效率;其次，針對(duì)系統(tǒng)中復(fù)雜的并性行為，提出了針對(duì)待測(cè)行為線性序列的測(cè)試?yán)伤惴?，能夠高效地生成?duì)待測(cè)行為完全覆蓋的測(cè)試?yán)?最后，提出了測(cè)試序列優(yōu)化算法，能夠去除測(cè)試?yán)械娜哂嘈蛄?，進(jìn)一步提升測(cè)試的效率。上述算法共同構(gòu)成了一種完整的針對(duì)并行軟件的測(cè)試方法，能夠有效地完成針對(duì)并行軟件中待測(cè)行為的測(cè)試，具有完全覆蓋性、無(wú)冗余性和高效性的特點(diǎn)。
　　本文主要的貢獻(xiàn)和創(chuàng)新

5、性成果如下:
　　1、提出一種基于跡等價(jià)的CP-nets模型化簡(jiǎn)算法。首先，定義面向測(cè)試的CP-nets(Testing-orientedCP-nets，ToCPN)模型，在待測(cè)軟件系統(tǒng)的ToCPN模型中，進(jìn)行被測(cè)實(shí)現(xiàn)部分和測(cè)試模擬環(huán)境部分的劃分，并將連接兩部分的端口位置和端口變遷標(biāo)記為可觀察位置和可觀察變遷;其次，提出發(fā)生序列的跡的定義，即一條發(fā)生序列中的可觀察元素構(gòu)成的序列稱為跡;最后，提出基于跡等價(jià)的并行軟件模型化簡(jiǎn)算法，對(duì)

6、符合條件的位置、變遷和其他模型元素進(jìn)行化簡(jiǎn)，將被化簡(jiǎn)的功能合并到鄰近的模型元素中。經(jīng)證明，本文提出的化簡(jiǎn)算法得到的模型與原始模型符合跡等價(jià)條件，也就是外部行為等價(jià)條件;而化簡(jiǎn)后模型的狀態(tài)空間規(guī)模將大幅減小，狀態(tài)數(shù)量和發(fā)生序列數(shù)量都顯著下降。故化簡(jiǎn)可以在保證測(cè)試結(jié)果不變的前提下大幅提升測(cè)試效率，本算法為解決并行軟件測(cè)試問(wèn)題提供了模型基礎(chǔ)。
　　2、提出一種基于CP-nets模型的針對(duì)待測(cè)行為線性序列的測(cè)試?yán)伤惴āＪ紫?，定義了待測(cè)

7、的行為線性序列(LinearBehaviorSequence，LBS)的概念，用于描述待測(cè)行為和測(cè)試目的;其次，提出基于LBS的測(cè)試?yán)伤惴ǎ赐ㄟ^(guò)狀態(tài)投影、極大極小狀態(tài)匹配、子序列及完全序列搜索等操作，自動(dòng)生成覆蓋LBS的測(cè)試?yán)?最后，證明了本算法生成的測(cè)試?yán)軌蛲耆采w系統(tǒng)模型中包含LBS的全部發(fā)生序列。在本算法中，并不需要遍歷系統(tǒng)模型的全部狀態(tài)空間，而是通過(guò)狀態(tài)投影等操作，在系統(tǒng)模型狀態(tài)空間中，定位LBS待測(cè)行為的前后狀態(tài)，再針

8、對(duì)前后狀態(tài)之間的狀態(tài)子圖進(jìn)行測(cè)試序列搜索和生成;而子圖之外的部分與LBS行為無(wú)關(guān)，故本算法不對(duì)子圖之外的部分進(jìn)行測(cè)試序列的搜索和生成，這一點(diǎn)保證了算法具備低冗余率和高執(zhí)行效率。故本算法生成的測(cè)試?yán)哂型耆采w性、低冗余性和高效性的特點(diǎn)。
　　3、提出了基于CP-nets的針對(duì)冗余序列的測(cè)試序列優(yōu)化算法。當(dāng)LBS行為出現(xiàn)在的三路及三路以上并行結(jié)構(gòu)時(shí)，以及當(dāng)系統(tǒng)中含有大量?jī)?nèi)部行為時(shí)，基于LBS的測(cè)試?yán)伤惴▽⑸珊腥哂嘈蛄泻蛢?nèi)部行

9、為信息的測(cè)試?yán)６?，并行路徑?shù)目越多，內(nèi)部行為數(shù)量越大，冗余率就越高。針對(duì)上述問(wèn)題，本文提出了兩種針對(duì)冗余序列的測(cè)試序列優(yōu)化算法。其中，針對(duì)多路并行行為的測(cè)試序列優(yōu)化算法針對(duì)投影操作得到的狀態(tài)空間子圖，進(jìn)行基于LBS點(diǎn)火行為制導(dǎo)的搜索操作，這種算法可以去除多路并行導(dǎo)致的冗余序列;針對(duì)內(nèi)部行為的測(cè)試序列優(yōu)化算法針對(duì)生成的測(cè)試序列進(jìn)行可觀察行為提取操作，并刪除提取后得到的相同序列，這種算法可以去除內(nèi)部行為導(dǎo)致的冗余序列和序列中的內(nèi)部行為信