張 瑋,孫 濤,萬(wàn)曉云

(內(nèi)蒙古大學(xué) 計(jì)算機(jī)學(xué)院, 呼和浩特 010021)

針對(duì)并行軟件待測(cè)行為測(cè)試的模型化簡(jiǎn)方法

張 瑋,孫 濤*,萬(wàn)曉云

(內(nèi)蒙古大學(xué) 計(jì)算機(jī)學(xué)院, 呼和浩特 010021)

(*通信作者電子郵箱cssunt@imu.edu.cn)

針對(duì)并行軟件的狀態(tài)空間規(guī)模大導(dǎo)致測(cè)試難度大的問(wèn)題，提出一種基于著色Petri網(wǎng)(CPN)的針對(duì)待測(cè)行為的并行模型化簡(jiǎn)方法。首先, 將原模型根據(jù)模型中出現(xiàn)的并發(fā)變遷、同步變遷、分叉庫(kù)所、匯合庫(kù)所等特殊節(jié)點(diǎn)的個(gè)數(shù)分成若干個(gè)子模塊；其次，判斷待測(cè)行為在模型中的位置，建立待測(cè)行為測(cè)試集；最后，對(duì)每一個(gè)并行模塊中符合化簡(jiǎn)條件的非待測(cè)行為設(shè)定執(zhí)行優(yōu)先級(jí)。通過(guò)對(duì)化簡(jiǎn)前后狀態(tài)空間分析報(bào)告的對(duì)比，狀態(tài)空間中節(jié)點(diǎn)的縮減率至少達(dá)到40%以上，并且在化簡(jiǎn)前后對(duì)于待測(cè)行為生成的全覆蓋測(cè)試路徑不受影響。

著色Petri網(wǎng)；并行軟件；待測(cè)行為；優(yōu)先級(jí)；測(cè)試集；全覆蓋

0 引言

隨著軟件技術(shù)和產(chǎn)業(yè)的發(fā)展，并行軟件已經(jīng)成為常見(jiàn)的軟件形式，并且在軟件的開(kāi)發(fā)和研究中都占據(jù)了十分重要的位置。例如，很多基于網(wǎng)絡(luò)的軟件系統(tǒng)都具有并行性特點(diǎn)，目前備受關(guān)注的基于云計(jì)算的軟件系統(tǒng)和基于物聯(lián)網(wǎng)的軟件系統(tǒng)也不例外[1]。

然而，和非并行性軟件相比，并行軟件的正確性確認(rèn)更加困難。在并行軟件中，各個(gè)并行實(shí)體具有大量的并行行為，同時(shí)各實(shí)體間還具有交互協(xié)同行為，這就導(dǎo)致了軟件執(zhí)行過(guò)程的高度復(fù)雜性，軟件狀態(tài)空間規(guī)模呈指數(shù)增長(zhǎng)，其執(zhí)行規(guī)模和處理難度都遠(yuǎn)遠(yuǎn)超出了非并行軟件[2]。

從系統(tǒng)建模的角度而言，著色Petri網(wǎng)(Colored Petri Net, CPN)支持可視化建模過(guò)程，通過(guò)位置、變遷、有向弧、函數(shù)式編程語(yǔ)言(Programming Language, ML)表達(dá)式和托肯(token)直接描述系統(tǒng)行為，支持自動(dòng)仿真執(zhí)行，允許多token 并發(fā)運(yùn)轉(zhuǎn)。也就是說(shuō)，對(duì)于并發(fā)、同步及交互行為，直接給出描述即可，多token 的并發(fā)運(yùn)轉(zhuǎn)即表達(dá)了系統(tǒng)的并發(fā)行為和由此而引發(fā)的系統(tǒng)狀態(tài)變化情況[3]。所以，采用CPN 描述并行軟件時(shí)，并行行為的復(fù)雜屬性并不會(huì)導(dǎo)致模型復(fù)雜度的提升，盡管并行行為將導(dǎo)致模型的狀態(tài)空間規(guī)模大幅提升，但CPN 模型的狀態(tài)空間是根據(jù)模型自動(dòng)生成的，建模時(shí)并不需要考慮系統(tǒng)狀態(tài)及其變化過(guò)程[4]。

在并行軟件系統(tǒng)測(cè)試中，為了限定模型狀態(tài)空間規(guī)模，研究者提出了一些模型化簡(jiǎn)方法。在文獻(xiàn)[5]中提出了基于跡等價(jià)的CP-nets的模型化簡(jiǎn)方法，該方法首先對(duì)模型進(jìn)行被測(cè)實(shí)現(xiàn)部分和測(cè)試模擬環(huán)境部分的劃分，并將連接兩部分的端口位置和端口變遷標(biāo)記為可觀察位置和可觀察變遷；其次，提出發(fā)生序列的跡的定義; 最后，提出基于跡等價(jià)的并行軟件模型化簡(jiǎn)算法，對(duì)符合條件的位置、變遷和其他模型元素進(jìn)行化簡(jiǎn)，將被化簡(jiǎn)的功能合并到鄰近的模型元素中。該方法雖然最終可以縮減狀態(tài)空間圖的節(jié)點(diǎn)，但是規(guī)避了模型中的特殊節(jié)點(diǎn)，而且當(dāng)模型足夠大時(shí)，依然存在空間爆炸的可能性。

在并行軟件測(cè)試中，每一次測(cè)試的測(cè)試目的不同，可以選擇不同的行為作為待測(cè)行為[6], 所以待測(cè)行為是指在測(cè)試過(guò)程中測(cè)試人員所指定要測(cè)試的某些軟件功能行為，其余的則稱為非待測(cè)行為。例如，可以選擇待測(cè)軟件中與某些數(shù)據(jù)或資源相關(guān)的行為作為本次測(cè)試的待測(cè)行為。這樣，就可以生成覆蓋待測(cè)行為并行執(zhí)行全部路徑的測(cè)試序列[7]。文獻(xiàn)[8]中提出一種基于并行軟件化簡(jiǎn)的測(cè)試序列生成算法，對(duì)模型化簡(jiǎn)的好處是避免了對(duì)并行軟件全部狀態(tài)空間進(jìn)行搜索和測(cè)試。然而，當(dāng)軟件的狀態(tài)空間規(guī)模過(guò)大時(shí)，生成完全覆蓋待測(cè)行為的測(cè)試序列同樣十分困難。

因此，本文提出一種針對(duì)并行軟件待測(cè)行為測(cè)試的模型化簡(jiǎn)方法,該方法以縮減狀態(tài)空間規(guī)模為目的，采用CPN來(lái)形式化描述軟件系統(tǒng)的轉(zhuǎn)變，并結(jié)合執(zhí)行對(duì)原有模型的分塊處理及非待測(cè)形為執(zhí)行順序的優(yōu)先級(jí)，從總體上減少測(cè)試代價(jià)，達(dá)到測(cè)試序列全局優(yōu)化的目的。設(shè)定優(yōu)先級(jí)可以有效降低軟件系統(tǒng)中非待測(cè)行為的并行復(fù)雜度，所以可以有效縮減模型狀態(tài)空間規(guī)模[9]。由于化簡(jiǎn)操作僅針對(duì)并行執(zhí)行的非待測(cè)行為進(jìn)行了執(zhí)行優(yōu)先級(jí)設(shè)定，而對(duì)于待測(cè)行為和并發(fā)同步交互等特殊節(jié)點(diǎn)不作處理，所以化簡(jiǎn)后再生成覆蓋待測(cè)行為的測(cè)試序列效果不變。通過(guò)實(shí)驗(yàn)對(duì)比和分析，驗(yàn)證了化簡(jiǎn)前后生成測(cè)試序列的一致性和狀態(tài)空間縮減效率，從而證明了該方法的有效性[10]。

1 Petri網(wǎng)定義

定義1 CPN[11]。一個(gè)非層次CPN可以定義為一個(gè)9元組：

CPN=(P，T，A，Σ，V，C，G，E，I)

其中：P是一個(gè)有限的庫(kù)所(Place)的集合;T是一個(gè)有限變遷(Transition)的集合，滿足P∩T=?，即一個(gè)節(jié)點(diǎn)要么是一個(gè)庫(kù)所，要么是一個(gè)變遷;A是有向弧(Arc)的集合，滿足A?P×T∪T×P，即每一條弧開(kāi)始于一個(gè)庫(kù)所(變遷)，結(jié)束于一個(gè)變遷(庫(kù)所);Σ是有限非空顏色集(Color set)，用于定義數(shù)據(jù)類型;V是有限變量(Variable)的集合, 對(duì)所有變量v∈V，滿足Type[v]∈Σ;C:P→Σ是顏色集函數(shù)(Color Set Function)，它指定了每個(gè)庫(kù)所顏色集;G:T→EXPRV是防衛(wèi)表函數(shù)(Guard Function)，它指定了每個(gè)變遷的防衛(wèi)表達(dá)式, 且對(duì)于所有的t∈T，有Type[G(t)]=Bool，即防衛(wèi)表達(dá)式的返回值必須是布爾型。E:A→EXPRV，是弧表達(dá)函數(shù)(Arc Expression Function)，它為每個(gè)弧指定了一個(gè)弧表達(dá)式，且對(duì)于所有的a∈A，有Type[E(a)]=C(p)MS(MS即多重集(Multi Set))，即弧表達(dá)式的類型必須與它相關(guān)的庫(kù)所的類型一致; I:P→EXPR?，是初始化函數(shù)(InitializationFunction)，它給每個(gè)庫(kù)所指定一個(gè)初始標(biāo)記，且對(duì)于所有的p∈P，有Type[I(p)]=C(p)MS, 即，初始表達(dá)式是一個(gè)與庫(kù)所顏色集相一致的元組。

以上定義為CPN的一個(gè)形式化定義，當(dāng)然除了基本定義以外，本文所提算法還將用到以下定義。

定義2 系統(tǒng)模型(SystemModel,SM)。在并行軟件測(cè)試中，首先根據(jù)待測(cè)軟件的需求規(guī)范，建立軟件的CPN模型，稱此CPN模型為待測(cè)的系統(tǒng)模型。

定義3 抑制弧(InhibitionArcs)[12]，又稱抑止弧、約束弧或者禁止弧。帶抑止弧的Petri網(wǎng)(Petrinetwithinhibitionarcs)是在原型Petri網(wǎng)的基礎(chǔ)上增加一種連接庫(kù)所和變遷的弧形成的。這種弧只對(duì)(在原型Petri網(wǎng)意義下)具備發(fā)生條件的變遷是否允許發(fā)生起控制作用，變遷一旦發(fā)生，抑止弧對(duì)由此引起的標(biāo)識(shí)變化不產(chǎn)生影響。目前抑制弧習(xí)慣用帶空心圓圈的線段符號(hào)表示，如圖1所示，p2與t2之間的弧即為抑制弧，作用為當(dāng)p2有token時(shí)，p1庫(kù)所所在路徑不執(zhí)行，直到p2庫(kù)所中沒(méi)有token后再執(zhí)行這一路徑。

定義4 并發(fā)變遷 (ConcurrentTransition,CT)。在系統(tǒng)模型中，如果一個(gè)變遷最多有一個(gè)輸入弧且有多個(gè)輸出弧，則這個(gè)變遷稱為并發(fā)變遷。例如圖1中t1即為模型的并發(fā)變遷。

圖1 抑制弧Fig. 1 Inhibition arc

定義5 同步變遷(SynchronousTransition,ST)。在系統(tǒng)模型中，如果一個(gè)變遷最多只有一個(gè)輸出弧并且有多個(gè)輸入弧，則這個(gè)變遷稱為同步變遷(ST)。例如圖2中t7即為模型的同步變遷。

定義6 分叉庫(kù)所(BranchPlace,BP)。在系統(tǒng)模型中，如果一個(gè)庫(kù)所最多有一個(gè)輸入弧且有多個(gè)輸出弧，則這個(gè)庫(kù)所稱為分叉庫(kù)所。例如圖2中p9即為模型的分叉庫(kù)所。

定義7 匯合庫(kù)所(ConfluencePlace,CP)。在系統(tǒng)模中，如果一個(gè)庫(kù)所最多只有一個(gè)輸出弧且有多個(gè)輸入弧，則這個(gè)庫(kù)所稱為匯合庫(kù)所。例如圖2中p7即為模型的匯合庫(kù)所。

定義8 同步并發(fā)變遷(SynchronousConcurrentTransition,SCT)。在系統(tǒng)模型中，如果一個(gè)變遷有多個(gè)輸入弧和多個(gè)輸出弧，則這個(gè)變遷稱為同步并發(fā)變遷。例如圖2中t12即為模型的同步并發(fā)變遷。

定義9 匯合分叉庫(kù)所(ConfluenceBranchPlace,CBP)。在系統(tǒng)模型中，如果一個(gè)庫(kù)所有多個(gè)輸入弧和多個(gè)輸出弧，則這個(gè)庫(kù)所稱為匯合分叉庫(kù)所。例如圖2中p4即為模型的匯合分叉庫(kù)所。

圖2 節(jié)點(diǎn)定義Fig. 2 Node definition

定義10 特殊節(jié)點(diǎn)(Specialnode)。在系統(tǒng)模型中所有的CT、ST、CP、BP、SCT、CBP均稱為特殊節(jié)點(diǎn)。

定義11 支路(Branch)。在系統(tǒng)模型中，位于系統(tǒng)模型的每一個(gè)子模塊中并發(fā)變遷(同步并發(fā)變遷)或分叉庫(kù)所(匯合分叉庫(kù)索)之后具有單入單出弧的順序路徑稱為支路。如圖3所示，其中用圓角矩形所標(biāo)注的路徑即為支路。

定義12 干路(Trunk)。在系統(tǒng)模型中，位于系統(tǒng)模型的每一個(gè)子模塊中分叉庫(kù)所(BP)或者并發(fā)變遷(CT)之前具有單入單出弧的順序路徑稱為前置干路；位于匯合庫(kù)所(CP)或同步變遷(ST)之后的具有單入單出弧的順序路徑稱為后置干路；位于分叉庫(kù)所或者并發(fā)變遷之后且在匯合庫(kù)所或同步變遷之前的具有單入單出弧的順序路徑稱為中間干路。如圖3所示，其中最左邊直角虛線矩形內(nèi)所注為前置干路，中間直角虛線矩形標(biāo)注為中間干路，最右邊直角虛線矩形所注為后置干路。

圖3 支路與干路模型定義Fig. 3 Model definition of branch and trunk

2 算法描述

因?yàn)楸疚乃惴ㄋ槍?duì)的模型是控制流模型，所以僅考慮單一初始token的情況。針對(duì)待測(cè)行為本文分為含有單個(gè)待測(cè)行為與多個(gè)待測(cè)行為兩種情況來(lái)考慮[13]。

算法1 系統(tǒng)模型預(yù)處理算法。

1)對(duì)系統(tǒng)模型進(jìn)行深度優(yōu)先遍歷，判斷各節(jié)點(diǎn)屬性,并將各節(jié)點(diǎn)歸類。

BeginvoidDFS(SM n)

//n代表系統(tǒng)模型中的節(jié)點(diǎn){ Visited[n]=true;If(n∈CommonNode) {//n為含有非特殊節(jié)點(diǎn)(根據(jù)節(jié)點(diǎn)的出入弧判斷)If(n∈place){Merge(SetPlace[n]);

//將n歸為庫(kù)所集 }elseif(n∈transition) {Merge(SetTransition[n]);

//將n歸為變遷集 }}elseif(n∈SpecialNode) {

//n為特殊節(jié)點(diǎn)if(n∈place) {Merge(SetCP[n]‖SetBP[n]‖SetCBP[n]); //根據(jù)n的出入弧條數(shù)選擇歸并到哪一個(gè)特殊庫(kù)所集 }elseif(n∈transition) {Merge(SetCT[n]‖SetST[n]‖SetSCT[n]); //根據(jù)n的出入弧條數(shù)選擇歸并到哪一個(gè)特殊變遷集 }}}End

2)對(duì)模型進(jìn)行分塊處理。

Begin for (i=1;i<=n;i++) {Modular=1； if (CT!=NULL‖ST!=NULL‖BP!=NULL‖CP!=NULL) ++Modular[]； Record(Modular[i]); //出現(xiàn)特殊節(jié)點(diǎn)，模塊計(jì)數(shù)加1，并記錄模塊信息 else returnSM； //返回模型繼續(xù)尋找特殊節(jié)點(diǎn)，直到將模型分為若干個(gè)模塊 } End

3)判斷模型的支路與干路。

Begin If (CT∈modular[n]‖ST∈modular[n]‖BP∈modular[n]‖CP∈modular[n]‖CBP∈modular[n]‖SCT∈modular[n]){

//模型中出現(xiàn)特殊節(jié)點(diǎn)Branch[]++; Record(Branch[n]);

//記錄支路的條數(shù)與支路上的信息Trunk[]++; Record(Trunk[n]);

//記錄干路的條數(shù)與干路上的信息 }else{Trunk++; Record(Trunk[n]); //沒(méi)有特殊節(jié)點(diǎn)時(shí)僅記錄干路條數(shù)與干路上的信息 } End

首先對(duì)系統(tǒng)模型的預(yù)處理算法實(shí)現(xiàn)描述，具體操作如下所述：

第1)步 對(duì)模型中的所有節(jié)點(diǎn)進(jìn)行遍歷，并記錄每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)的輸入弧與輸出?。?/p>

①當(dāng)一個(gè)節(jié)點(diǎn)有一個(gè)入弧和多個(gè)出弧時(shí)，判斷此節(jié)點(diǎn)是庫(kù)所還是變遷，如果節(jié)點(diǎn)是庫(kù)所時(shí)，則此模型有分叉庫(kù)所；如果節(jié)點(diǎn)是變遷時(shí)，則此模型有并發(fā)變遷。

②當(dāng)一個(gè)節(jié)點(diǎn)有多個(gè)入弧和一個(gè)出弧時(shí)，判斷此節(jié)點(diǎn)是庫(kù)所還是變遷，如果節(jié)點(diǎn)是庫(kù)所時(shí)，則此模型有匯合庫(kù)所；如果節(jié)點(diǎn)是變遷時(shí)，則此模型有匯合變遷。

③當(dāng)一個(gè)節(jié)點(diǎn)有多個(gè)入弧和多個(gè)出弧時(shí)，判斷此節(jié)點(diǎn)是庫(kù)所還是變遷，如果節(jié)點(diǎn)是庫(kù)所時(shí)，此模型中有匯合分叉庫(kù)所；如果節(jié)點(diǎn)是變遷時(shí)，則模型有同步并發(fā)變遷。

④當(dāng)一個(gè)節(jié)點(diǎn)有一個(gè)入弧和一個(gè)出弧時(shí)，則此模型為順序執(zhí)行。

⑤當(dāng)一個(gè)庫(kù)所只有輸出弧沒(méi)有輸入弧時(shí)，此庫(kù)所為初始庫(kù)所。

⑥當(dāng)一個(gè)庫(kù)所只有輸入弧沒(méi)有輸出弧時(shí)，此末庫(kù)所為末庫(kù)所。

第2)步 對(duì)模型進(jìn)行分塊處理。從模型的初始庫(kù)所進(jìn)行遍歷，當(dāng)出現(xiàn)第1)步中的①～③三種特殊節(jié)點(diǎn)時(shí)，特殊節(jié)點(diǎn)之前的路徑記為1模塊，再?gòu)拇颂厥夤?jié)點(diǎn)繼續(xù)遍歷，由此節(jié)點(diǎn)產(chǎn)生含有分支的路徑記為下一模塊，如果分支再出現(xiàn)①～③三種節(jié)點(diǎn)，則此節(jié)點(diǎn)是這一模塊的終止節(jié)點(diǎn)，如果沒(méi)有出現(xiàn)特殊節(jié)點(diǎn)，則這一模塊沒(méi)有嵌套；循環(huán)分塊，直到遍歷到模型的最后一個(gè)節(jié)點(diǎn)。

第3)步 判斷模型中的干路與支路。如果模型中包含分叉庫(kù)所或者并發(fā)變遷，則此節(jié)點(diǎn)之前具有單入單出弧的順序路徑記為前置干路，節(jié)點(diǎn)之后的每一條具有單入單出弧的順序路徑記為支路；如果模型中包含匯合庫(kù)所或者同步變遷，則此節(jié)點(diǎn)之后具有單入單出弧的順序路徑記為后置干路，節(jié)點(diǎn)之前具有單入單出弧的順序路徑記為支路；如果模型中既包含分叉庫(kù)所或者并發(fā)變遷，又包含匯合庫(kù)所或者同步變遷，則這對(duì)特殊節(jié)點(diǎn)之間具有單入單出弧的順序路徑稱為中間干路，其余為支路。

算法2 單個(gè)待測(cè)行為時(shí)的算法。

當(dāng)有單個(gè)待測(cè)行為時(shí)，需要判斷待測(cè)行為所在模型位置并進(jìn)行優(yōu)先級(jí)處理(待測(cè)行為處于同一支路或干路)。

Begin If (BehaviorTest∈Trunk){ Serialization (Branch[])；

// 將支路不在同一路徑的非待測(cè)行為串行化處理 } else if (BehaviorTest∈Branch){ Sequential(Trunk)；

// 順序執(zhí)行干路 Execution(Branch[behaviorTest]);

// 優(yōu)先執(zhí)行含有待測(cè)行為的支路 Serialization (Branch[]); }else if (BehaviorTest∈CT) { Sequential(Trunk)；

//順序執(zhí)行干路 Serialization (Branch[]);

//支路串行化 } else if (BehaviorTest∈ST) { Sequential(Trunk)； Serialization (Branch[]); } End

當(dāng)有單個(gè)待測(cè)行為時(shí)，詳細(xì)步驟如下描述：

判斷待測(cè)行為所在模型的位置,待測(cè)行為位置為干路上時(shí)有3種情況：1)待測(cè)行為在前置干路上時(shí)；2)待測(cè)行為在中間干路上時(shí)；3)待測(cè)行為在后置干路上時(shí)。當(dāng)待測(cè)行為在前置干路上時(shí)，則對(duì)前置干路之后的具有并發(fā)行為的支路進(jìn)行串行化處理，對(duì)含有分叉庫(kù)所的支路不作處理；當(dāng)待測(cè)行為在中間干路上時(shí)，需要對(duì)回溯尋找中間干路之前含有支路的模塊并對(duì)模塊進(jìn)行判斷，如果具有并發(fā)行為，則將并發(fā)行為串行化，如果具有分叉行為，則不作處理，對(duì)于中間干路之后的支路處理方法則和前置干路之后對(duì)支路的處理方法相一致；當(dāng)待測(cè)行為在后置干路上時(shí)，回溯尋找后置干路之前的所有含有支路的模塊，具有并發(fā)行為的將其串行化處理，具有分叉行為的則不作處理。

當(dāng)待測(cè)行為在支路上時(shí)，判斷支路是并發(fā)支路還是分叉支路，如果是并發(fā)支路，則先執(zhí)行含有待測(cè)行為的路徑，將與待測(cè)行為不在同一路徑的非待測(cè)行為進(jìn)行串行化的處理，干路不需要作處理；如果是分叉支路，則執(zhí)行含有待測(cè)行為的路徑，對(duì)于與待測(cè)行為不在同一路徑的非待測(cè)行為加以抑制。

當(dāng)待測(cè)行為在并發(fā)變遷上時(shí)，如果模型沒(méi)有出現(xiàn)匯合節(jié)點(diǎn)，則將支路上的非待測(cè)行為進(jìn)行串行化的處理；如果出現(xiàn)匯合點(diǎn)，則判斷匯合節(jié)點(diǎn)類型；當(dāng)匯合節(jié)點(diǎn)為同步變遷時(shí)，則將并發(fā)變遷后的非待測(cè)行為做串行化處理，模型中的干路不作處理；如果匯合節(jié)點(diǎn)為同步庫(kù)所時(shí)，則需要將并發(fā)變遷后的非待測(cè)行為也進(jìn)行串行化處理，將所有token執(zhí)行到匯合庫(kù)所后，再進(jìn)行下一步操作。

當(dāng)待測(cè)行為在匯合變遷上時(shí)，需要回溯尋找含有此匯合變遷的模塊的初始節(jié)點(diǎn)，當(dāng)模型中含有并發(fā)變遷時(shí)，遍歷尋找其各支路最長(zhǎng)匯合節(jié)點(diǎn)，如果最終匯合節(jié)點(diǎn)為匯合變遷時(shí)，在匯合節(jié)點(diǎn)之前的支路需要作串行化處理，當(dāng)匯合到匯合變遷后，再執(zhí)行下一動(dòng)作；當(dāng)模型中含有分叉庫(kù)所，且最終匯合到匯合庫(kù)所時(shí)，在單token的情況下，此模型執(zhí)行不到最終末庫(kù)所，因此這一情況暫時(shí)不作考慮。

算法3 多個(gè)待測(cè)行為時(shí)的算法。

當(dāng)有多個(gè)待測(cè)行為時(shí)，建立待測(cè)行為集，并根據(jù)一定的化簡(jiǎn)順序進(jìn)行非待測(cè)行為的化簡(jiǎn)。

Begin SetBehaviorTest[ ];

//對(duì)SM中所有變遷遍歷尋找 //待測(cè)行為所在模型位置并建立待測(cè)行為集 SIMP(SM);

//遞歸調(diào)用處理模型中的子模塊 End //以下為遞歸函數(shù)SIMP(Modular)，用于處理模型SM中的子模 //塊嵌套 SIMP(Modular){ For eachiinSetBehaviorTest[] If (SetBehaviorTest[i]∈CT‖SetBehaviorTest[i]∈ST) { If(Modular existSubModular[]) {

//模型中出現(xiàn)模塊嵌套 For eachminSubModular[] SIMP(SubModular[m]); Simplification (ModularCT‖ModularST);

//特殊節(jié)點(diǎn) } Simplification (ModularBranch);

//支路 Simplification (ModularTrunk);

//干路 }

程序后

當(dāng)有多個(gè)待測(cè)行為時(shí)，需要對(duì)待測(cè)行為建立待測(cè)行為集：如果集合中待測(cè)行為所在位置有特殊節(jié)點(diǎn)時(shí)，包括CT、ST，則按特殊節(jié)點(diǎn)出現(xiàn)順序優(yōu)先化簡(jiǎn)含有特殊節(jié)點(diǎn)的模塊；然后再按順序?qū)χ返呐c待測(cè)行為不再一條路徑的非待測(cè)行為根據(jù)上述規(guī)則進(jìn)行化簡(jiǎn)，待測(cè)行為在干路上時(shí)，對(duì)化簡(jiǎn)后的模型再進(jìn)行判斷，如果滿足化簡(jiǎn)規(guī)則，則繼續(xù)化簡(jiǎn)，否則不再進(jìn)行化簡(jiǎn)；當(dāng)模型中某一模塊的支路為下一模塊的干路時(shí)，化簡(jiǎn)順序?yàn)橄然?jiǎn)最內(nèi)層模塊，再化簡(jiǎn)外層模塊；如果特殊節(jié)點(diǎn)為先后順序時(shí)，則化簡(jiǎn)順序依次根據(jù)特殊節(jié)點(diǎn)出現(xiàn)的先后順序?qū)δK進(jìn)行化簡(jiǎn)。綜上，化簡(jiǎn)優(yōu)先級(jí)為RankSpecial node>RankBranch>RankTrunk。當(dāng)模型中出現(xiàn)分叉庫(kù)所時(shí)，對(duì)于起始點(diǎn)為該庫(kù)所的支路將保留一條與待測(cè)行為無(wú)關(guān)的分支，以便于可以執(zhí)行模塊后邊的行為。

3 算法應(yīng)用

圖4是一個(gè)待測(cè)軟件控制流模型[14], 里邊包含了并發(fā)、分叉、匯合、嵌套等軟件中常見(jiàn)可能性，通過(guò)這個(gè)模型來(lái)說(shuō)明化簡(jiǎn)方法的通用性。當(dāng)有單個(gè)待測(cè)行為時(shí)，本文以t0為例來(lái)說(shuō)明算法應(yīng)用。

圖4 系統(tǒng)模型[14]Fig. 4 System model[14]

示例1 單個(gè)待測(cè)行為。

第1步 首先對(duì)模型進(jìn)行遍歷，記錄所有節(jié)點(diǎn)對(duì)應(yīng)的輸入弧與輸出弧，其中：只有輸出弧的庫(kù)所為p0，即p0為初始庫(kù)所；只有輸出弧沒(méi)有輸入弧的庫(kù)所為p14、p12，即此系統(tǒng)模型的末庫(kù)所不唯一；有單個(gè)入弧與多個(gè)出弧的節(jié)點(diǎn)有1個(gè)，為t1；有多個(gè)入弧與單個(gè)出弧的節(jié)點(diǎn)有3個(gè)，分別為t4、p7、p11；有多個(gè)入弧與多個(gè)出弧的節(jié)點(diǎn)有一個(gè)，為t7；有單個(gè)入弧與單個(gè)出弧的節(jié)點(diǎn)有21個(gè)，分別為t0、p1、p2、p3、p4、t2、t3、p5、p6、t5、p13、t11、t6、p8、p9、p10、p15、t8、t9、t12、t10。

第2步 判斷出模型中的干路與支路，其中干路為圖4中虛線直角矩形所示，分別為p0-t0-p1、p7-t6-p8、p11-t10-p12；支路為圖4中包含特殊節(jié)點(diǎn)的圓角矩形標(biāo)注所示，分別為p2-t2-p5、p3-t3-p6、p4-t5-p9-t9、p13-t11-p14、p9-t8、p15-t12、p10-t9。

第3步 通過(guò)第1步模型遍歷可以找到系統(tǒng)模型中含有并發(fā)變遷t1、同步變遷t4、匯合庫(kù)所p7、同步并發(fā)變遷t7、匯合庫(kù)所p11；將模型分塊，t1并發(fā)后，有一條支路并沒(méi)有到達(dá)匯合庫(kù)所或者匯合變遷，而是到達(dá)不同狀態(tài)，因此，系統(tǒng)模型的末狀態(tài)不唯一；圖4中的圓角矩形標(biāo)注即為對(duì)系統(tǒng)模型的分塊處理。

第4步 深度優(yōu)先遍歷系統(tǒng)模型，尋找待測(cè)行為所在位置，由圖4可知，待測(cè)行為t0在模型的干路，且在支路之前，因此屬于算法總結(jié)中的待測(cè)行為在干路上的情況，所以需要對(duì)不同類型模塊進(jìn)行串行化，如圖5所示。根據(jù)規(guī)則分別在p2與t3之間添加抑制弧，p4與t11之間添加抑制弧，p9與t12之間添加抑制弧，p9與t9之間添加抑制弧，p2與t5之間添加抑制弧，p3與t5之間添加抑制弧，p4與t11之間添加抑制弧，p2與t11之間添加抑制弧，p14與t9之間添加抑制弧。

圖5 加入優(yōu)先級(jí)的系統(tǒng)模型Fig. 5 System model after adding priority

在沒(méi)有加入執(zhí)行優(yōu)先級(jí)之前，原模型狀態(tài)空間節(jié)點(diǎn)個(gè)數(shù)為532，加入執(zhí)行優(yōu)先級(jí)之后狀態(tài)空間節(jié)點(diǎn)個(gè)數(shù)變?yōu)?67，縮減了365個(gè)節(jié)點(diǎn)，縮減率為69%。

示例2 多個(gè)待測(cè)行為。

為了保證算法的通用性，本文仍然選擇上述系統(tǒng)模型來(lái)對(duì)算法進(jìn)行說(shuō)明，待測(cè)行為集為{t0，t4，t8},模型如圖6所示。

圖6 含待測(cè)行為系統(tǒng)模型Fig. 6 System model including tested behavior

第1步 與單個(gè)待測(cè)行為方法一致，在此不作贅述；

第2步 對(duì)于模型支路與干路的判斷與上述方法一致；

第3步 遍歷尋找模型特殊節(jié)點(diǎn)并對(duì)模型進(jìn)行分塊方法與單個(gè)待測(cè)行為時(shí)一致；

第4步 深度優(yōu)先遍歷系統(tǒng)模型，尋找待測(cè)行為所在位置，建立待測(cè)行為集{t0,t4,t8}，由圖4可知待測(cè)行為t0在模型的前置支路上，t4在模型子模塊中的同步變遷點(diǎn)上，t8位于子模塊的支路上，因此根據(jù)多token執(zhí)行化簡(jiǎn)優(yōu)先級(jí)規(guī)則，先化簡(jiǎn)含有特殊節(jié)點(diǎn)的含有待測(cè)行為的子模塊，再化簡(jiǎn)待測(cè)行為在支路上的模塊，分別將每一個(gè)含有分支情況的子模塊中的非待測(cè)行為進(jìn)行串行化處理，方法與單個(gè)待測(cè)行為算法相同，即根據(jù)相關(guān)規(guī)則在庫(kù)所與變遷之間添加抑制弧，最終加優(yōu)先級(jí)的模型如圖7所示。

圖7 化簡(jiǎn)后的系統(tǒng)模型Fig. 7 System model with simplification

原模型狀態(tài)空間節(jié)點(diǎn)個(gè)數(shù)為532，加入執(zhí)行優(yōu)先級(jí)之后狀態(tài)空間節(jié)點(diǎn)個(gè)數(shù)變?yōu)?84，縮減了248個(gè)節(jié)點(diǎn)，縮減率為47%。

通過(guò)示例1～2發(fā)現(xiàn)，本文算法對(duì)模型的化簡(jiǎn)率有一個(gè)較大的提升，因此狀態(tài)空間縮減效果好；其次，對(duì)模型化簡(jiǎn)之后關(guān)于模型的測(cè)試生成效果是沒(méi)有改變的。在覆蓋待測(cè)行為的測(cè)試生成方法中，對(duì)于與待測(cè)行為無(wú)關(guān)的非待測(cè)行為的并行執(zhí)行采取的辦法是只取其中一條執(zhí)行序列，化簡(jiǎn)后，由于優(yōu)先級(jí)的作用，使得非待測(cè)行為的執(zhí)行只有一種可能，所以狀態(tài)空間中僅剩一條序列。所以，化簡(jiǎn)后生成的序列效果不變，而且效率提升。

4 結(jié)語(yǔ)

本文提出了針對(duì)待測(cè)行為的并行模型化簡(jiǎn)算法，根據(jù)系統(tǒng)模型中待測(cè)行為所在模型位置的不同，對(duì)非待測(cè)行為設(shè)定了執(zhí)行優(yōu)先級(jí)，從而將狀態(tài)空間節(jié)點(diǎn)進(jìn)行了大幅度的縮減，通過(guò)并行模型化簡(jiǎn)實(shí)例驗(yàn)證了本文方法能夠大幅縮減并行軟件模型的狀態(tài)空間規(guī)模，化簡(jiǎn)前后對(duì)待測(cè)行為進(jìn)行全覆蓋測(cè)試的測(cè)試序列效果不變，從而證明了化簡(jiǎn)后并沒(méi)有影響模型的正確性，即本文算法服務(wù)于針對(duì)待測(cè)行為的全覆蓋測(cè)試序列生成，從根本上提升了并行軟件測(cè)試序列生成的效率，也為解決復(fù)雜的并行軟件測(cè)試問(wèn)題奠定了基礎(chǔ)[15]。

References)

[1] 顏炯, 王戟, 陳火旺. 基于模型的軟件測(cè)試綜述[J]. 計(jì)算機(jī)科學(xué), 2004, 31(2): 184-187.(YAN J, WANG J, CHEN H W. Survey of model-based software testing[J]. Computer Science, 2004, 31(2): 184-187.)

[2] LEYE S, HIMMELSPACH J, UHRMACHER A M. A discussion on experimental model validation[C]// Proceedings of the UKSim 2009: 11th International Conference on Computer Modelling and Simulation. Washington, DC: IEEE Computer Society, 2009: 161-167.

[3] SUN T, YE X. A model reduction method for parallel software testing[EB/OL].[2016-06-20]. http://www.emis.ams.org/journals/HOA/JAM/Volume2013/595897.pdf.

[4] 杜秀娟.基于UML狀態(tài)圖的軟件測(cè)試用例生成方法研究[D]. 西安: 長(zhǎng)安大學(xué),2008.(DU X J. Research on software test case generation based on UML state diagram [D]. Xi’an: Chang’an University, 2008.)

[5] 孫濤.基于CP-nets模型的并行軟件測(cè)試方法研究[D]. 呼和浩特: 內(nèi)蒙古大學(xué),2012.(SUN T. Research on testing method for parallel software based on colored Petri nets[D]. Hohhot: Inner Mongolia University, 2012.)

[6] RAI V, SIVASUBRAMANIAN S, BHULAI S, et al. A multiphased approach for modeling and analysis of the BitTorrent protocol[C]// Proceedings of the 27th International Conference on Distributed Computing Systems. Washington, DC: IEEE Computer Society, 2007: 10.

[7] 胡乃文.基于改進(jìn)蟻群算法的測(cè)試序列優(yōu)化算法[D]. 北京交通大學(xué),2015.(HU N W. The algorithm of test sequence optimization based on the improved ant colony algorithm [D]. Beijing: Beijing Jiaotong University, 2015.)

[8] 陸公正.基于EFSM模型的測(cè)試用例優(yōu)化生成及實(shí)例化[D]. 上海: 上海大學(xué),2014.(LU G Z. EFSM model based optimal generation and instantiation of test cases[D]. Shanghai: Shanghai University, 2014.)

[9] SUN T, YE X, LIU J. A test generation method based on model reduction for parallel software[C]// Proceedings of the 2012 13th International Conference on Parallel and Distributed Computing, Applications and Technologies. Washington, DC: IEEE Computer Society, 2012:777-782.

[10] ZHU H, HE X. A methodology of testing high-level Petri nets[J]. Information and Software Technology, 2002, 44(8):473-489.

[11] JENSEN K. An introduction to the theoretical aspect of colored Petri nets[C]// REX1993: Reflections and Perspectives. London: Springer-Verlag, 1994: 230-272.

[12] RUSHBY J. Automated Test Generation And Verified Software[M]. Berlin: Springer-Verlag, 2005: 161-172.

[13] LEE G, MORRIS J, PARKER K, et al. Using symbolic execution to guide test generation: research articles[J]. Software Testing Verification & Reliability, 2005, 15(1):41-61.

[14] 李華, 葉新銘. 基于Petri 網(wǎng)的控制流與數(shù)據(jù)流相結(jié)合的協(xié)議測(cè)試[J]. 內(nèi)蒙古大學(xué)學(xué)報(bào)(自然科學(xué)版), 1999, 29(5):702-705.(LI H, YE X M. Protocol test based on the combination of control flow and data flow based on Petri net[J]. Journal of Inner Mongolia University (Natural Science Edition), 1999, 29(5):702-705.)

[15] SARGENT R G. Verification and validation of simulation models[C]// Proceedings of the 40th Conference on Winter Simulation. Piscataway, NJ: IEEE, 2013： 37-48.

This work is partially supported by the National Natural Science Foundation of China (61562064, 61462066).

ZHANG Wei, born in 1991, M. S. candidate. His research interests include software testing.

SUN Tao, born in 1980, Ph. D., associate professor. His research interests include software testing.

WAN Xiaoyun, born in 1990, M. S. candidate. Her research interests include software testing.

Simplification method for testing behavior of parallel software

ZHANG Wei, SUN Tao*, WAN Xiaoyun

(SchoolofComputerScience,InnerMongoliaUniversity,HohhotNeiMongol010021,China)

Focusing on the issues that it is very difficult to test the parallel software system, and the size of state space is too large, a Colored Petri Net (CPN) model for simplifying the tested behavior of the parallel model was proposed. Firstly, the original model was divided into several sub modules according to the number of the special nodes, such as concurrent transitions, synchronous transitions, the branch places, and the confluence places. Secondly, the position of the tested behavior and the test set was created. Finally, the execution priority was set for the non-test behavior in each parallel module which met the reduction condition. By comparing the results of the state space analysis before and after simplification, the reduction rate of nodes in state space is at least 40%, and the full coverage test path generated by the tested behavior was not affected by the simplification.

Colored Petri Net (CPN); parallel software; test behavior; priority; test set; full coverage

2016-11-09;

2017-01-12。 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61562064, 61462066)。

張瑋(1991—)，男，內(nèi)蒙古巴彥淖爾人，碩士研究生，主要研究方向：軟件測(cè)試； 孫濤(1980—)，男，內(nèi)蒙古呼和浩特人，副教授，博士，主要研究方向：軟件測(cè)試； 萬(wàn)曉云(1990—)，女，河北張家口人，碩士研究生，主要研究方向：軟件測(cè)試。

1001-9081(2017)05-1276-06

10.11772/j.issn.1001-9081.2017.05.1276

TP306.2

A