針對并行軟件待測行為測試的模型化簡方法

張 瑋,孫 濤,萬曉云

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

針對并行軟件待測行為測試的模型化簡方法

張 瑋,孫 濤*,萬曉云

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

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

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

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

0 引言

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

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

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

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

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

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

1 Petri網(wǎng)定義

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

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

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

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

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

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

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

圖1 抑制弧Fig. 1 Inhibition arc

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

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

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

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

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

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

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

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

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

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

2 算法描述

因為本文算法所針對的模型是控制流模型，所以僅考慮單一初始token的情況。針對待測行為本文分為含有單個待測行為與多個待測行為兩種情況來考慮[13]。

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

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

BeginvoidDFS(SM n)

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

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

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

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

2)對模型進行分塊處理。

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é)點，模塊計數(shù)加1，并記錄模塊信息 else returnSM； //返回模型繼續(xù)尋找特殊節(jié)點，直到將模型分為若干個模塊 } 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é)點Branch[]++; Record(Branch[n]);

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

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

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

第1)步 對模型中的所有節(jié)點進行遍歷，并記錄每一個節(jié)點對應的輸入弧與輸出?。?/p>

①當一個節(jié)點有一個入弧和多個出弧時，判斷此節(jié)點是庫所還是變遷，如果節(jié)點是庫所時，則此模型有分叉庫所；如果節(jié)點是變遷時，則此模型有并發(fā)變遷。

②當一個節(jié)點有多個入弧和一個出弧時，判斷此節(jié)點是庫所還是變遷，如果節(jié)點是庫所時，則此模型有匯合庫所；如果節(jié)點是變遷時，則此模型有匯合變遷。

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

④當一個節(jié)點有一個入弧和一個出弧時，則此模型為順序執(zhí)行。

⑤當一個庫所只有輸出弧沒有輸入弧時，此庫所為初始庫所。

⑥當一個庫所只有輸入弧沒有輸出弧時，此末庫所為末庫所。

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

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

算法2 單個待測行為時的算法。

當有單個待測行為時，需要判斷待測行為所在模型位置并進行優(yōu)先級處理(待測行為處于同一支路或干路)。

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

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

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

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

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

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

當有單個待測行為時，詳細步驟如下描述：

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

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

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

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

算法3 多個待測行為時的算法。

當有多個待測行為時，建立待測行為集，并根據(jù)一定的化簡順序進行非待測行為的化簡。

Begin SetBehaviorTest[ ];

//對SM中所有變遷遍歷尋找 //待測行為所在模型位置并建立待測行為集 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é)點 } Simplification (ModularBranch);

//支路 Simplification (ModularTrunk);

//干路 }

程序后

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

3 算法應用

圖4是一個待測軟件控制流模型[14], 里邊包含了并發(fā)、分叉、匯合、嵌套等軟件中常見可能性，通過這個模型來說明化簡方法的通用性。當有單個待測行為時，本文以t0為例來說明算法應用。

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

示例1 單個待測行為。

第1步 首先對模型進行遍歷，記錄所有節(jié)點對應的輸入弧與輸出弧，其中：只有輸出弧的庫所為p0，即p0為初始庫所；只有輸出弧沒有輸入弧的庫所為p14、p12，即此系統(tǒng)模型的末庫所不唯一；有單個入弧與多個出弧的節(jié)點有1個，為t1；有多個入弧與單個出弧的節(jié)點有3個，分別為t4、p7、p11；有多個入弧與多個出弧的節(jié)點有一個，為t7；有單個入弧與單個出弧的節(jié)點有21個，分別為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é)點的圓角矩形標注所示，分別為p2-t2-p5、p3-t3-p6、p4-t5-p9-t9、p13-t11-p14、p9-t8、p15-t12、p10-t9。

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

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

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

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

示例2 多個待測行為。

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

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

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

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

第3步 遍歷尋找模型特殊節(jié)點并對模型進行分塊方法與單個待測行為時一致；

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

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

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

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

4 結(jié)語

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

References)

[1] 顏炯, 王戟, 陳火旺. 基于模型的軟件測試綜述[J]. 計算機科學, 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)圖的軟件測試用例生成方法研究[D]. 西安: 長安大學,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模型的并行軟件測試方法研究[D]. 呼和浩特: 內(nèi)蒙古大學,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] 胡乃文.基于改進蟻群算法的測試序列優(yōu)化算法[D]. 北京交通大學,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模型的測試用例優(yōu)化生成及實例化[D]. 上海: 上海大學,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é)議測試[J]. 內(nèi)蒙古大學學報(自然科學版), 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。 基金項目:國家自然科學基金資助項目(61562064, 61462066)。

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

1001-9081(2017)05-1276-06

10.11772/j.issn.1001-9081.2017.05.1276

TP306.2

A