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

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

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

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

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

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

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

7、的行為線性序列(LinearBehaviorSequence，LBS)的概念，用于描述待測行為和測試目的;其次，提出基于LBS的測試例生成算法，即通過狀態(tài)投影、極大極小狀態(tài)匹配、子序列及完全序列搜索等操作，自動生成覆蓋LBS的測試例;最后，證明了本算法生成的測試例能夠完全覆蓋系統(tǒng)模型中包含LBS的全部發(fā)生序列。在本算法中，并不需要遍歷系統(tǒng)模型的全部狀態(tài)空間，而是通過狀態(tài)投影等操作，在系統(tǒng)模型狀態(tài)空間中，定位LBS待測行為的前后狀態(tài)，再針

8、對前后狀態(tài)之間的狀態(tài)子圖進行測試序列搜索和生成;而子圖之外的部分與LBS行為無關(guān)，故本算法不對子圖之外的部分進行測試序列的搜索和生成，這一點保證了算法具備低冗余率和高執(zhí)行效率。故本算法生成的測試例具有完全覆蓋性、低冗余性和高效性的特點。
　　3、提出了基于CP-nets的針對冗余序列的測試序列優(yōu)化算法。當(dāng)LBS行為出現(xiàn)在的三路及三路以上并行結(jié)構(gòu)時，以及當(dāng)系統(tǒng)中含有大量內(nèi)部行為時，基于LBS的測試例生成算法將生成含有冗余序列和內(nèi)部行

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