基于EFSM不定型切片測試用例自動生成的研究

蘇 寧 郭俊霞 李 征 趙瑞蓮

(北京化工大學信息科學與技術學院 北京 100029) (suning311@163.com)

基于EFSM不定型切片測試用例自動生成的研究

蘇 寧 郭俊霞 李 征 趙瑞蓮

(北京化工大學信息科學與技術學院 北京 100029) (suning311@163.com)

基于模型的測試是軟件測試中一個重要分支，但隨著模型規模的增大，測試用例生成也變得越來越困難.擴展有限狀態機(extended finite state machine, EFSM)是一種廣泛應用的模型，它是對有限狀態機(finite state machine，FSM)的擴展，能夠更精確地刻畫軟件系統的動態行為.對EFSM模型的測試主要包含2個部分：測試遷移路徑的生成和覆蓋測試遷移路徑的測試數據的生成.基于搜索的方法已被應用于測試數據的生成.為了提高在大規模EFSM模型中測試用例生成的效率，在前期對EFSM模型非終止性研究新型依賴性分析和切片技術的基礎上，提出了基于EFSM模型不定型切片的測試用例生成方法和測試用例補全方法.通過2個案例分析得出：基于模型切片可以更加準確地生成可行路徑和提高測試強度.基于7個基準EFSM模型的實驗結果表明，在大多數情況下，在切片上生成測試用例的效率都比在原模型上高.

EFSM模型；依賴性分析；切片；測試用例生成；測試用例補全

Fig. 1 The EFSM model of lift and its amorphous slice圖1 電梯EFSM模型及其不定型切片

模型是軟件系統的抽象，基于模型的測試[1-2]將軟件測試提前到模型階段，采用形式化的方法驗證軟件行為，從而發現軟件中的錯誤和故障，是軟件測試領域中的一個重要研究方向.擴展有限狀態機(extended finite state machine, EFSM)模型在有限狀態機(finite state machine, FSM)模型的基礎上增加了變量、操作和狀態遷移的前置條件.EFSM模型可以更加精確地刻畫軟件系統的動態行為，因此被廣泛應用于通信協議軟件、嵌入式系統、對象之間的交互行為建模等.基于EFSM模型的測試技術具有重要的研究意義與實用價值.

通常來說，基于EFSM模型的測試用例生成主要包含2個部分：測試遷移路徑的生成和覆蓋遷移路徑的測試數據生成[3].其中，測試遷移路徑生成是指生成一條從起始遷移到被測遷移的連續遷移序列路徑；測試數據生成是指根據測試遷移路徑生成遷移中的事件以及事件上的變量值.近年來，隨著基于搜索的軟件工程及軟件測試技術的發展，啟發式搜索算法在EFSM模型測試數據生成中的應用獲得了很大進展，主要包括禁忌搜索算法[3]、遺傳算法(genetic algorithm， GA)[4-5]、模擬退火算法[6]、爬山算法[7]等，其中Zhao等人[4]研究了基于遺傳搜索的EFSM模型測試數據生成效率的影響因素，表明測試用例的生成效率與EFSM模型的規模成反比關系.在實際應用中，軟件系統規模的增大使對應模型的規模也變得越來越大，這必將會導致測試難度的增加和效率的降低.

為了提高EFSM模型中測試用例生成的效率，本文提出了一種基于模型切片的測試用例生成方法.與程序切片技術相似，EFSM模型切片同樣是根據依賴性分析，以原模型特定遷移為準則對模型進行約簡.不同的是EFSM模型自身具有非決定性和非終止性，目前針對模型非終止性的依賴性分析[8]和切片方法[9]已有了一定的研究，為基于模型切片的測試用例生成奠定了基礎.依賴性分析可以準確識別出模型中與被測遷移有依賴關系的遷移，而切片方法則可以移除沒有依賴關系的遷移，進而縮短測試路徑，提高測試用例生成效率.另外，覆蓋被測遷移的路徑通常有很多，現有的方法優先選取最短路徑.但一條包含盡可能多的具有依賴關系遷移的測試路徑，其測試強度會大大增強，能夠發現更加復雜的錯誤.目前，基于程序切片的測試已有了廣泛的研究和應用[10]，但基于模型切片的測試還是一個有待開發的研究領域.

本文考慮了基于依賴性分析的EFSM模型不定型切片[9]用于測試用例生成.不定型切片只保留了模型的語義但不再保留模型的語法，即以EFSM模型的特定遷移為準則生成切片模型，其行為與原模型一致，但結構不同.基于EFSM模型切片生成測試用例，首先生成覆蓋被測對象的測試路徑，但由于模型結構的改變，基于切片模型生成的測試路徑不能直接匹配到原模型上，進而生成的測試數據不能直接應用到原模型上.例如圖1(a)給出了電梯系統門控制器的EFSM模型[11]，它描述電梯等待乘客進入或離開，以及開關門的過程；圖1(b)是對原模型進行依賴分析后應用約簡合并規則形成的不定型切片.以t11為被測遷移，從原模型(如圖1(a)所示)中選取一條從t1到t11的路徑，會優先選取最短路徑[t1，t3，t5，t10，t11]，但在切片模型(如圖1(b)所示)中會選取路徑[t5，t11].由于不定型切片算法中的約簡合并規則導致了測試路徑變短，可以降低測試用例生成成本，但切片上生成的測試數據不能在原模型上直接使用.研究發現，切片上的測試路徑是原模型對應路徑的子集，所以可以設計補全方法來保證在原模型上運行.本文進一步提出測試路徑和測試數據的補全規則，并通過7個基準的EFSM模型實驗驗證，證明了方法的可行性.

本文的主要貢獻有：1)提出了基于EFSM模型不定型切片的測試用例生成方法框架；2)給出了基于EFSM模型切片遷移路徑選取準則，和在原模型上選取測試路徑相比，基于切片的方法可以精確選取測試路徑，同時提高測試強度；3)針對切片過程中遷移的約簡和狀態的合并，給出了測試路徑補全規則和測試數據補全規則；4)實驗結果表明切片上生成的測試數據通過補全規則可以全部在原模型上運行，并且在大多數情況下，在切片上生成測試用例的效率比在原模型上高.

1 EFSM模型及相關概念

1.1 擴展有限狀態機(EFSM)模型

定義1. 擴展有限狀態機(EFSM).EFSM可以表示為一個六元組，M=(S，s0，T，E，Var，v0)，其中S，T，E，Var分別是狀態集、遷移集、觸發事件集和變量集.遷移集T中的每個遷移t由源狀態source(t)∈S，目標狀態target(t)∈S和標簽label(t)組成.標簽的形式為e[c]a，其中e∈E，當事件e觸發后，若滿足c中的條件，則執行a中的一系列操作.標簽中的每個部分都是可選的.若遷移t的標簽為空，稱之為ε-遷移.若遷移滿足source(t)=target(t)，稱之為自循環遷移.若遷移滿足source(tj)=target(ti)，稱tj是ti的后繼遷移.若遷移是以初始狀態Start為源狀態，稱之為起始遷移.

1.2 依賴分析

一般說來，依賴關系主要有2種：數據依賴和控制依賴.其中，數據依賴體現的是遷移上變量的定義使用關系，控制依賴體現的是遷移之間的支配關系.

定義2. 數據依賴(data dependence, DD).ti→DDtj表示遷移tj對于變量v數據依賴于遷移ti滿足：

1)v∈vdef(ti)，其中vdef(ti) 是由遷移ti定義的變量集合，即由遷移ti上的操作定義或作為事件參數定義的;

2)v∈vuse(tj)，其中vuse(tj)是遷移tj在觸發條件和操作中使用的變量集合;

3) 存在一條從ti出發到tj的EFSM路徑，其中v沒有被任何中間遷移修改過.

定義3. 控制依賴(control dependence， CD).ti→CDtj表示遷移tj控制依賴于遷移ti當且僅當ti具有至少一個兄弟遷移tk并且：

1) 對于所有路徑π∈PATH(ti)，source(tj) 屬于π;

2) 存在一條路徑π∈PATH(tk)，滿足source(tj)不屬于π.

根據路徑類型的不同，控制依賴主要可以分為3種類型[8]：非終止敏感控制依賴(non-termination sensitive control dependence， NTSCD)、非終止非敏感控制依賴(non-termination insensitive control de-pendence, NTICD)、不公平非終止非敏感控制依賴(unfair non-termination insensitive control dependence， UNTICD).本文主要考慮的是NTICD和NTSCD.除了對應路徑類型的不同，NTICD和NTSCD還有一個很大的區別，就是NTICD無法計算出control sink(control sink是指可以形成一個強連通結構的遷移集合K，其中，K中的每個遷移的后繼遷移也都存在于K)中的控制依賴信息,但是NTSCD卻可以.所以在大多數情況下，使用NTSCD生成的切片也會比用NTICD生成的切片大一些.

1.3 不定型切片

根據是否保留原模型的語法，模型切片可以分為定型切片和不定型切片.定型切片是基于依賴分析，依據切片準則，將與切片準則中的被測遷移無關的遷移標簽置空得到的.在得到定型切片后，依據制定的約簡合并規則移除空遷移(即ε-遷移)就可以得到不定型切片.

定義4. 切片準則(slicing criterion).EFSM模型的切片準則是一個(t,V)對，其中t∈T，變量集V?Var.

Fig. 2 The EFSM model of ATM圖2 ATM取款機的EFSM模型

定義5. 切片(slice).EFSM模型切片M′是對原EFSM模型M的約簡.如果e1是M的輸入事件，那么M′存在一個輸入事件e2，使得：

1)e2是e1的子序列.在不改變元素順序的情況下，移除序列e1中的一些元素，從而得到其子序列e2.

2) 當觸發M中的e1時，t上的變量V的值與M′中e2觸發期間的t上的V值相等.

本文采用文獻[9]中定義使用的約簡合并規則來生成不定型切片.文獻中先應用Ilie和Yu[12]定義的規則合并狀態移除ε-遷移，然后應用ε-消除移除剩余的ε-遷移以及不可達的狀態，最后應用遷移之間的恒等關系(左恒等右恒等)生成一個最小化的切片模型.

1.4 遷移路徑

定義6. 遷移路徑(transition path， TP).EFSM模型的路徑指的是連續的遷移序列.即路徑π=[t1，t2，…，ti-1，ti，ti+1，…，tn]，其中target(ti)=source(ti+1),1≤i

一條遷移路徑TP是可行遷移路徑(feasible transition path， FTP) 當且僅當存在輸入使其按順序遍歷路徑中的每個遷移ti.然而在EFSM模型中，由于動作(action)和條件(condition)中變量之間的依賴關系，導致了給定的遷移路徑TP可能是不可行的[13].

2 實例研究

在本節中，我們通過2個實例對基于EFSM模型切片的測試用例生成優勢，即基于模型切片可以更加準確地生成可行路徑和提高測試強度進行說明.

圖2是ATM取款機的EFSM模型[14]，模型中描述了2種賬戶類型(查詢和儲蓄)和3種交易類型(取款、存款和查詢余額).遷移t3是3次輸入密碼錯誤后退出系統的操作.為了正確測試遷移t3，要連續3次輸入錯誤密碼，即t2遷移連續執行3次.在原模型中選取從初始遷移t1到t3的路徑時，由于t2是一條自循環遷移，可以加入路徑中，也可以不加入路徑中.而路徑選取會優先選取最短路徑，即[t1，t3]，但顯然這是一條不可行路徑.

在使用基于切片的測試方法中，首先以被測遷移t3為準則生成切片，如圖3所示.由于切片是通過依賴分析得到的，也就是說對切片準則存在影響的遷移都應該包含在切片中.從圖3所示的切片中，可以直觀地看出遷移t2對切片準則中的t3存在影響，也就是說在選取從t1到t3的路徑時，要將t2包含進路徑中才可能保證選取路徑的可行性.

第2個實例同樣以圖2所示ATM模型為例，但選取遷移t11為測試對象.在原模型中選取一條從t1到t11的路徑，會優先選取最短路徑[t1，t4，t6，t7，t11].圖4給出了以t11為切片準則生成的不定型切片，可以直觀地發現與t11存在依賴關系的所有遷移.為了保證測試的有效性和強度，可以通過設定規則將與之有依賴關系的遷移(如t13，t14)盡可能包含進路徑中，這種情況下在切片中選取的路徑長度會變長，但測試強度也會增大.

Fig. 3 Amorphous slice with slicing criterion t3 for Fig.2圖3 圖2中模型以t3為切片準則生成的不定型切片

Fig. 4 Amorphous slice with slicing criterion t11 for Fig.2圖4 圖2中模型以t11為切片準則生成的不定型切片

3 基于不定型切片測試用例的生成

3.1 方法概述

本文考慮的不定型切片是基于依賴性分析的，所以要首先對模型進行依賴分析，得到其遷移之間的依賴關系.之后，就可以依據切片準則以及狀態遷移的合并約簡準則得到目標模型，也就是不定型切片.不定型切片雖然是對原模型的約簡，但也是一個EFSM模型，測試用例生成的步驟同樣適用，所以要首先基于切片模型生成測試路徑，然后再對路徑生成測試數據.在切片上生成的測試數據，需要在原模型中運行.依據切片的定義，可以知道基于切片生成的測試數據是原模型測試數據的子集，需要設計補全方法將其補全才能保證在原模型上運行.

圖5給出了基于不定型切片的測試用例生成系統框圖.從圖5中可以看出，基于不定型切片的測試用例生成主要包含2部分：切片生成(slicing)和測試生成(test generation).圖5中虛線框部分，即測試用例生成是本文研究的重點.

Fig. 5 The framework of amorphous slicing based test case generation圖5 基于不定型切片測試用例生成的基本框圖

切片生成主要包括依賴分析(dependence analysis)和用切片工具(slicing tool)生成切片.

1) 依賴分析.分析EFSM模型遷移之間的依賴關系，包括數據依賴關系和控制依賴關系.

2) 切片工具.以被測遷移為切片準則在依賴分析的基礎上生成不定型切片.

測試生成主要包括在切片上生成測試用例(test case generation)和補全測試用例(test case compensating).

1) 生成測試用例.首先在切片上生成測試路徑，然后對測試路徑生成測試數據.

2) 補全測試用例.在切片上生成測試用例后，要在原EFSM模型中運行來執行測試.根據不定型切片的定義，針對切片準則在切片上生成的路徑應是原模型對應路徑的子集.為保證切片上生成的測試用例能在原模型上運行需要對路徑進行補全，并對新遷移上的變量補全測試數據.

3.2 基于不定型切片的測試用例生成

EFSM模型的不定型切片是對原模型的約簡，它雖然不再保留原EFSM模型的語法，但是仍然保留了原模型的語義.在EFSM模型切片上生成測試用例和原模型相同，也包含2個步驟：測試遷移路徑的生成和測試數據的生成.

3.2.1 測試遷移路徑的生成

本文是以被測遷移為測試對象來進行測試用例生成，以驗證被測遷移的正確性，故本文的測試路徑指的是從起始遷移到被測遷移的連續遷移序列.

不定型切片是對原EFSM模型進行依賴分析后，依據切片準則對原模型某些狀態進行合并，某些遷移進行約簡后得到的.保留在切片中的遷移都是與被測遷移存在依賴關系的遷移.一般來說路徑通常選取最短路徑，但是通過第2節的實例研究可以知道，為了保證測試路徑的可行性和測試強度，應該選取更多對被測遷移存在影響的遷移加入到路徑當中.與此同時，由于切片中可能會存在遷移的合并，如圖6中的t9t10，在選取路徑的時候也需對此問題進行考慮.

所以，依據上面的分析以及不定型切片的特點，定義3個規則：

規則1. 若切片中包含原模型中的自循環遷移，在選取路徑時，要至少遍歷這個自循環一次.

規則2. 在選取路徑時，要盡可能多地包含切片中的遷移，即選取最長簡單路徑(最長簡單路徑是指含有最多遷移的簡單路徑).

規則3. 若切片中存在遷移的合并，在選取路徑時，可只選擇其中一個遷移進行遍歷.

Fig. 6 Amorphous slice with slicing criterion t9 for Fig.2圖6 圖2中模型以t9為切片準則生成的不定型切片

規則1考慮的是第2節中案例1的情況，即原模型的自循環遷移如果包含在切片中，則和被測對象之間一定存在依賴關系，也就是對其會產生影響，不包含在路徑中會導致路徑的不可行；規則2考慮的是第2節中案例2的情況，即通過對切片的分析，在選取最短路徑的基礎上可以考慮加入更多的與被測對象存在依賴關系的遷移到路徑中去，也就是選取最長簡單路徑，從而增加測試強度；規則3是針對存在等價遷移的情況，從圖6中可以看到t9t10是一條合并的遷移，它是在切片形成的過程中對遷移做恒等分析造成的，也就是說合并的遷移在合并前相對于被測對象是等價的，所以在選取路徑的時候，選擇其一加入路徑中即可.

3.2.2 測試數據的生成

在生成了測試路徑之后就可以對這條路徑進行測試數據的生成.測試數據指的是路徑上的事件以及事件上的輸入變量值.本文使用了基于遺傳算法的EFSM模型測試數據自動化生成的方法[4].

Fig. 7 Example of test data圖7 測試數據舉例

具體而言，給定一條測試路徑[t1，t2，…，tm]，對應測試數據是[e1[c1]a1，e2[c2]a2，…，em[cm]am]，其中ei[ci]ai表示遷移ti上的事件ei被觸發后，如果滿足ci中的條件，則執行ai中的動作.遺傳算法的個體就是按順序出現的事件序列e1，e2， …，em以及事件上的輸入變量值x=(x1，x2，…，xn).圖7給出了一條含有3個遷移的路徑.路徑中的測試序列是(eve1(a,b)，eve2，eve3)，其中a，b是需要生成數值的變量.例如(eve1(2,3)，eve2，eve3)是可以遍歷這條路徑的測試數據.

3.2.3 切片路徑的補全

在切片上生成的測試數據，需要在原模型上運行.通過前面的分析以及切片的定義可知，在切片上生成的測試路徑是原模型對應測試路徑的子集，需要進行路徑補全并對新補充的遷移生成測試數據.

通過對切片路徑與對應原模型路徑的對比分析，定義2個規則:

還是以圖1為例，假設在切片模型(圖1(b))中選取的測試路徑是[t5，t11]，相對于原模型這是一條不完整的路徑，無法直接將其對應到原模型路徑中去，需要對其進行補充.首先發現切片路徑中的起始遷移t5不是原模型(如圖1(a)所示)中的起始遷移(原模型的起始遷移為t1)，此時就需要按照規則4補充原模型中從t1到t5的連續遷移序列；進一步觀察可以發現，在原模型(如圖1(a)所示)中t11不是t5的后繼遷移，此時也需要對路徑進行補充，也就是按照規則5補充原模型中從t5到t11的連續遷移序列.

顯然，若規則4和規則5都不滿足則無需進行路徑的補全，即切片路徑直接對應于原模型中的路徑.

需要補充的遷移是在切片形成的過程中約簡的，與被測遷移沒有數據依賴或者控制依賴的關系.在選擇補充路徑的時候只需要選取一條可行的路徑進行補充即可.

3.2.4 測試數據的補全

補全完路徑之后，需對補充的遷移路徑上的變量生成測試數據，這樣才是完整的測試數據，才能保證其能在原模型上運行.通過對補充路徑中的遷移進行分析，定義2個規則:

規則6. 若補充遷移上的變量v是切片路徑中已存在的變量，則將切片上生成的測試數據直接賦值給v.

規則7. 若補充遷移上的變量v是新引入的變量，則根據變量v的值域，采用隨機算法生成測試數據.

規則6指的是對于已經在切片路徑中存在的變量，它在對切片路徑生成測試數據的時候已經有了數值，所以就不用再對其進行測試數據的生成，直接將切片上生成的測試數據復制給它即可.而對于規則7中新引入的變量，它之所以會在切片形成過程中隨著它所在的遷移被一起約簡，是因為它與被測遷移上的變量不存在任何數據依賴關系，那么在對其生成測試數據時，只要隨機生成一個值保證能夠通過路徑中的新增遷移即可.

4 實驗及結果分析

為了驗證基于EFSM模型切片測試用例生成方法的有效性，本文提出3個研究問題，并通過實驗進行驗證.

RQ1. 在切片上生成的測試用例在原模型是否可行？

RQ2. 在切片上和原模型上生成測試用例，哪種方法生成測試用例的效率更高？

RQ3. 不同的依賴關系得到的切片是否會影響測試用例的生成效率？

4.1 實驗設計

本文選取了7個基準模型進行實驗.表1給出了每個模型的狀態數(s)、遷移數(t)、事件數(e)以及出現在遷移標簽上的變量數(v)，最后4列給出了實驗中使用的切片算法生成切片平均大小.實驗平臺為一臺配有16核英特爾Xeon?CPU E5620主頻2.40 GHz的服務器，編程語言為Python.

實驗過程中，分別把7個模型的每個遷移作為被測對象，同時基于原模型和切片模型，生成能夠覆蓋被測遷移的測試數據.不定型切片使用了SLIMER工具[9]，依賴性分析包括了NTICD和NTSCD兩種控制依賴關系及數據依賴DD.原模型上的測試用例生成采用了文獻[4]中的基于GA的方法，基于切片的測試用例生成按本文提出的方法生成路徑及測試數據，并按規則補全成可以在原模型上運行的測試數據.

Table 1 Description of Experimental Models

4.2 實驗結果和分析

由于EFSM模型不定型切片的特點，切片上的測試數據需經過補全才能運行在原模型上.RQ1的提出是為了檢驗本文提出的路徑補全規則和數據補全規則.測試數據的生成和補全是全自動完成的，在測試數據運行階段，我們通過人工檢驗了生成的測試數據能否在對應的原模型上運行.檢驗結果是在切片上生成的測試數據通過路徑補全和數據補全在原模型上都是可行的，說明了本文提出的補全規則是正確的.

針對后2個問題，雖然切片尺寸小，理論上生成測試用例的時間少，但執行EFSM模型的依賴性分析和切片及后期的用例補全等操作都會額外增加時間，所以只能通過實驗結果來比較不同方法生成測試用例的效率.在實驗過程中分別采用了NTICD+DD和NTSCD+DD依賴關系生成切片，并統計了在切片上生成測試用例的時間和在原模型上生成測試用例的時間.

在基于切片生成測試用例時，因為每個模型的依賴性分析只需要執行一次就可以完成所有切片，在統計測試用例生成時間上，設計了2種方法，一種是對模型中單個遷移ti的比較，另一種是模型整體上的比較.圖8、圖9分別給出了7個模型中單個遷移ti以及模型整體上在生成測試用例時間上的比較.圖8中單個遷移的時間不包含依賴性分析，圖9中以模型整體分析上加入了一次依賴性分析時間.由于有些模型時間跨度較大，圖上的時間是對其取lg得到的結果.Lift模型生成測試用例的時間較短，圖9中Lift模型的時間是乘100后得到的結果.

圖8中的橫軸表示遷移，縱軸表示測試用例生成的時間(以秒為單位).從圖8中可以看出，ATM， FuelPump， Lift(Lift僅在NTICD+DD)在切片上生成測試用例的效率比在原模型上高，Cashier，PrintToken，Vending Machine，Lift(Lift僅在NTSCD+DD)在切片上生成測試用例的效率比在原模型上低，而CruiseControl在切片上生成測試用例的效率和在原模型上差不多.通過分析CruiseControl的切片可以發現，CruiseControl切片形狀與原模型形狀幾乎相同，故其在切片上做測試用例生成與在原模型上的結果差不多.雖然有些模型在切片上生成測試用例的效率較低，但是通過分析實驗數據可知其在切片上生成測試用例的時間與原模型上的時間差基本上都在2 s以內.結合表1進一步分析比較切片與原模型測試用例生成可以發現，切片對原模型約簡得越多，其做測試用例的生成效率越好.

對于RQ3，結合表1中NTICD+DD與NTSCD+DD平均切片大小分析圖8中的數據，可以發現當切片規模相近時(如ATM，Cashier，CruiseControl，FuelPump)， 2種切片的測試用例生成效率也相近；當切片規模相差較大時(如Vending Machine，Lift)，切片越大，其生成測試用例的效率就越低.對于PrintToken模型，2種切片的規模差不多，但是發現某些遷移用NTICD+DD生成測試用例的效率低些.通過分析實驗數據可知，這是由于這些遷移生成的切片時間較長導致的(2種切片的測試用例的生成時間差不多).

Fig. 8 The comparison of test generation between slices and original EFSMs on single transition ti圖8 單個遷移ti在切片上和原模型上的測試用例生成效率比較

Fig. 9 The comparison of test generation between slices and original EFSMs on whole EFSM圖9 EFSM整體在切片上和原模型上的測試用例生成效率比較

圖9中的橫軸表示模型，縱軸表示測試用例生成的時間(以秒為單位).從圖9可以看出，除了PrintToken模型，其余6個模型整體上在NTICD+DD切片上的測試用例生成效率都比在原模型上生成效率高些.而導致PrintToken模型切片測試用例生成效率低的原因是其生成切片的時間較長，但平均時間差仍基本在2 s內.

對于RQ3，同樣結合表1中NTICD+DD與NTSCD+DD平均切片大小分析圖9中的數據，可以發現不同依賴關系得到的切片不會影響測試用例生成效率，測試用例生成效率與切片規模的大小相關：切片規模越小，其生成測試用例的效率就越高(如ATM，Cashier，FuelPump，VendingMachine，Lift).由于CruiseControl模型的2種切片的規模和形狀差不多，故其整體上生成測試用例的效率也差不多.而PrintToken模型由于使用NTICD+DD生成切片的時間整體上較長，故其生成測試用例的效率較低.

5 相關工作

本文方法的思想來源于基于程序切片的測試用例生成，關于程序切片的測試現在已經有大量的研究，可以參閱相關綜述文章[15-17].

EFSM模型是狀態模型的一種，目前存在一些針對其他的狀態切片的方法.Heimdahl等人[18]提出了一個需求狀態機語言(Requirement State Machine Language, RSML)規則說明的切片方法，首先它通過移除不滿足定義條件的行為來進行約簡；然后依據一個遷移或者變量，用數據流和控制流做切片.Wang等人[19]給出了一個擴展的層次自動機(extended hierarchical automaton, EHA)[20]切片算法.通過分層處理，依據并發和通信，他們定義了數據依賴和控制依賴,并通過得到的依賴關系依據切片準則生成切片.

在針對EFSM模型切片的研究中，根據切片準則的不同，以遷移觸發事件為準則的模型切片方法被提出，稱為基于事件的模型切片(也稱為模型映射Model Projection)[21-22].該觸發事件集在模型外部環境中將不再能夠被觸發(即事件失效)，形成了一個具有約束的模型外部環境.Androutsopoulos等人[9]對EFSM模型的不定型切片進行了研究，介紹了基于依賴集的EFSM模型切片算法以及一個工具，并證實了他們提出的算法適合基于依賴的切片.

由于EFSM模型在FSM模型的基礎上增加了變量以及狀態遷移的前置條件，遷移之間可能會存在沖突導致遷移路徑的不可行.基于FSM模型的測試用例生成方法不能直接用于EFSM模型中，所以有學者對EFSM模型的測試用例生成做了研究.文獻[4,14,23-30]是對測試路徑生成做的研究，這些文獻給出了判定路徑可行的方法，從而為后續生成有效的測試數據奠定了理論基礎.其中，Hierons等人[28-29]嘗試通過擴展EFSM模型來繞開不可行路徑問題.經過擴展后的EFSM模型簡化了測試序列的生成，并且擴展后的EFSM模型中的所有路徑都是可行的.最終，這個方法選取了一組可執行路徑集和相應的可以覆蓋所選測試準則的測試數據集.Duale等人[26,30]考慮解決EFSM模型中2條遷移之間的沖突問題.他們消除沖突的方法是基于一種圖像分割技術，這個技術將存在沖突的遷移分別置于2個獨立的子圖中，以避免它們包含在相同的路徑中.在這些方法中，通過對原EFSM模型進行研究以處理路徑的不可行性；而本文通過對EFSM模型不定型切片進行研究，在切片的基礎上對路徑不可行性進行處理.文獻[3-7,31-35]對測試數據的生成做了研究，他們大多采用基于搜索的算法生成測試數據，其中，Zhao等人[4]采用遺傳算法生成測試數據，本文在不定型切片上生成測試數據時也采用了遺傳算法.

6 結束語

本文提出了一種基于EFSM模型不定型切片的測試用例生成方法，并通過案例分析說明基于EFSM模型切片的測試用例生成方法可以更準確地選取測試路徑和有效增大測試強度.根據切片上測試路徑是原模型對應路徑子集的特點，提出了測試路徑和測試數據補全規則.實驗結果顯示在切片上生成的測試數據補全后都可在原模型上運行.同時基于切片的方法中測試用例生成效率在大多數情況下都比較高，效率低的主要原因是依賴性分析和執行切片的時間較長，但整體評價時間差在2 s范圍內.

[1]Padgham L, Zhang Zhiyong, Thangarajah J, et al. Model-based test oracle generation for automated unit testing of agent systems[J]. IEEE Trans on Software Engineering, 2013, 39(9): 1230-1244

[2]Enoiu E P, Sundmark D, Pettersson P. Model-based test suite generation for function block diagrams using the uppaal model checker[C]Proc of the 6th IEEE Int Conf on Software Testing, Verification and Validation Workshops (ICSTW). Piscataway, NJ: IEEE, 2013: 158-167

[3]Ren Jun, Zhao Ruilian, Li Zheng. Automatic generation of test data for extended finite state machine models based on Tabu search algorithm[J]. Journal of Computer Applications, 2011, 31(9): 2440-2443 (in Chinese)(任君, 趙瑞蓮, 李征. 基于禁忌搜索算法的可擴展有限狀態機模型測試數據自動生成[J]. 計算機應用, 2011, 31(9): 2440-2443)

[4]Zhao Ruilian, Harman M, Li Zheng. Empirical study on the efficiency of search based test generation for EFSM models[C]Proc of the 3rd IEEE Int Conf on Software Testing, Verification, and Validation Workshops (ICSTW). Piscataway, NJ: IEEE, 2010: 222-231

[5]Zhou Xiaofei, Zhao Ruilian, You Feng. EFSM-based test data generation with multi-population genetic algorithm[C]Proc of the 5th IEEE Int Conf on Software Engineering and Service Science (ICSESS). Piscataway, NJ: IEEE, 2014: 925-928

[6]Cheng Xichao. Test data automatic generation based on simulated annealing algorithm for EFSM [D]. Beijing: Beijing University of Chemical Technology, 2011 (in Chinese)(程喜朝. 基于模擬退火算法的 EFSM 模型測試數據自動生成[D]. 北京: 北京化工大學, 2011)

[7]Kalaji A S, Hierons R M, Swift S. A search-based approach for automatic test generation from extended finite state machine (EFSM)[C]Proc of Testing: Academic and Industrial Conf-Practice and Research Techniques(TAIC PART). Piscataway, NJ: IEEE, 2009: 131-132

[8]Androutsopoulos K, Gold N, Harman M, et al. A theoretical and empirical study of EFSM dependence[C]Proc of the 25th IEEE Int Conf on Software Maintenance (ICSM). Piscataway, NJ: IEEE, 2009: 287-296

[9]Androutsopoulos K, Clark D, Harman M, et al. Amorphous slicing of extended finite state machines[J]. IEEE Trans on Software Engineering, 2013, 39(7): 892-909

[10]Binkley D. The application of program slicing to regression testing[J]. Information and Software Technology, 1998, 40(11): 583-594

[11]Strobl F, Wisspeintner A. Specification of an elevator control system—An autofocus case study[JOL]. 1999[2015-12-09]. https:www.researchgate.netpublication239552338_Specification_of_an_Elevator_Control_System_An_AutoFocus_Case_Study

[12]Ilie L, Yu S. Reducing NFAs by invariant equivalences[J]. Theoretical Computer Science, 2003, 306(1): 373-390

[13]Kalaji A S, Hierons R M, Swift S. Generating feasible transition paths for testing from an extended finite state machine (EFSM)[C]Proc of the 3rd IEEE Int Conf on Software Testing Verification and Validation (ICST). Piscataway, NJ: IEEE, 2009: 230-239

[14]Korel B, Singh I, Tahat L, et al. Slicing of state-based models[C]Proc of the 19th IEEE Int Conf on Software Maintenance (ICSM). Piscataway, NJ: IEEE, 2003: 34-43

[15]Tip F. A survey of program slicing techniques[J]. Journal of Programming Languages, 1995, 3(3): 121-189

[16]Binkley D, Harman M. A survey of empirical results on program slicing[J]. Advances in Computers, 2004, 62(1112): 105-178

[17]Xu Baowen, Qian Jun, Zhang Xiaofang, et al. A brief survey of program slicing[J]. ACM SIGSOFT Software Engineering Notes, 2005, 30(2): 1-36

[18]Heimdahl M P E, Whalen M W. Reduction and slicing of hierarchical state machines[J]ACM SIGSOFT Software Engineering Notes, 1999, 22(6): 450-467

[19]Wang Ji, Dong Wei, Qi Zhichang. Slicing hierarchical automata for model checking UML statecharts[C]Proc of the 4th Int Conf on Formal Engineering Methods: Formal Methods and Software Engineering. Berlin: Springer, 2002: 435-446

[20]Dong Wei, Wang Ji, Qi Xuan, et al. Model checking UML statecharts[C]Proc of the 8th Asia-Pacific on Software Engineering Conf (APSEC). Los Alamitos, CA: IEEE Computer Scienty, 2001: 363-370

[21]Androutsopoulos K, Binkley D, Clark D, et al. Model projection: Simplifying models in response to restricting the environment[C]Proc of the 33rd Int Conf on Software Engineering. New York: ACM, 2011: 291-300

[22]Lano K, Rahimi S K. Slicing techniques for UML models[J]. Journal of Object Technology, 2011, 10(11): 1-49

[23]Yang Rui, Chen Zhenyu, Xu Baowen, et al. Improve the effectiveness of test case generation on EFSM via automatic path feasibility analysis[C]Proc of the 13th IEEE Int Symp on High -Assurance Systems Engineering (HASE). Piscataway, NJ: IEEE, 2011: 17-24

[24]Wu Tianyong, Yan Jun, Zhang Jian. A path-oriented approach to generating executable test sequences for extended finite state machines[C]Proc of the 6th IEEE Int Symp on Theoretical Aspects of Software Engineering. Piscataway, NJ: IEEE, 2012: 267-270

[25]Lu Gongzheng, Miao Huaikou. Feasibility analysis of the EFSM transition path combining slicing with theorem proving[C]Proc of IEEE Int Symp on Theoretical Aspects of Software Engineering. Piscataway, NJ: IEEE, 2013: 153-156

[26]Duale A Y, Uyar M U. A method enabling feasible conformance test sequence generation for EFSM models[J]. IEEE Trans on Computers, 2004, 53(5): 614-627

[27]Wong S, Ooi C Y, Hau Y W, et al. Feasible transition path generation for EFSM-based system testing[C]Proc of IEEE Int Symp on Circuits and Systems. Piscataway, NJ: IEEE, 2013: 1724-1727

[28]Hierons R M, Kim T H, Ural H. Expanding an extended finite state machine to aid testability[C]Proc of Int Computer Software and Applications Conf on Prolonging Software Life: Development and Redevelopment. Los Alamitos, CA: IEEE Computer Society, 2002: 334-339

[29]Hierons R M, Kim T H, Ural H. On the testability of SDL specifications[J]. Computer Networks, 2004, 44(5): 681-700

[30]Uyar M U, Duale A Y. Test generation for EFSM models of complex army protocols with inconsistencies[C]Proc of Century Military Communications Conf. Piscataway, NJ: IEEE, 2000: 340-346

[31]Kalaji A S, Hierons R M, Swift S. An integrated search-based approach for automatic testing from extended finite state machine (EFSM) models[J]. Information and Software Technology, 2011, 53(12): 1297-1318

[32]Yano T, Martins E, De Sousa F L. MOST: A multi-objective search-based testing from EFSM[C]Proc of the 4th IEEE Int Conf on Software Testing, Verification and Validation Workshops. Piscataway, NJ: IEEE, 2011: 164-173

[33]Asoudeh N, Labiche Y. Multi-objective construction of an entire adequate test suite for an EFSM[C]Proc of the 25th IEEE Int Symp on Software Reliability Engineering. Piscataway, NJ: IEEE, 2014: 288-299

[34]Zhang Jie, Yang Rui, Chen Zhenyu, et al. Automated EFSM-based test case generation with scatter search[C]Proc of the 7th Int Workshop on Automation of Software Test. Piscataway, NJ: IEEE, 2012: 76-82

[35]You Juan, Li Junquan, Xia Song. Algorithm for generating test sequences based on branch and bound in EFSM model[J]. Application Research of Computers, 2013, 30(5): 1349-1352 (in Chinese)(尤娟, 李俊全, 夏松. 基于分支界限搜索的EFSM協議測試序列生成算法[J]. 計算機應用研究, 2013, 30(5): 1349-1352)

Su Ning, born in 1990. Master candidate. Her main research interests include EFSM model slicing and test generation.

Guo Junxia, born in 1977. PhD, lecturer. Senior member of CCF. Her main research interests include partial information extraction and Web application testing (gjxia@mail.buct.edu.cn).

Li Zheng, born in 1974. Professor and PhD supervisor. Senior member of CCF. His main research interests include software analysis and testing, model analysis and testing, search based software testing.

Zhao Ruilian, born in 1964. Professor and PhD supervisor. Senior member of CCF. Her main research interests include software testing and software reliability analysis (rlzhao@mail.buct.edu.cn).

EFSM Amorphous Slicing Based Test Case Generation

Su Ning, Guo Junxia, Li Zheng, and Zhao Ruilian

(CollegeofInformationScienceandTechnology,BeijingUniversityofChemicalTechnology,Beijing100029)

Model based testing is a crucial dimension in software testing. However, with the increase of model scale, model based test case generation is becoming more and more arduous. Extended Finite State Machine (EFSM) has been widely used in industry, which is extended from Finite State Machine (FSM), and can depict the dynamic behavior of software system more accurately. EFSM based test case generation mainly includes two parts: test transition paths generation and test data generation that covers the test transition paths, in which search based technology is adapted in test data generation. In order to improve the efficiency of test case generation in large-scale EFSM models, EFSM slicing based test case generation and test case compensating are proposed based on the previous research on EFSM dependence analysis and slicing for non-termination of EFSM models. Two case studies are introduced to show that model slicing based test case generation is more accurate in feasible path generation and test intensity improvement. In this paper, the experiments on 7 standard EFSMs are conducted, and the results show that all of the test case generated from slice can be used in the original model, and in most cases, test case generation efficiency on slice is higher than that on the original model.

EFSM model; dependence analysis; slicing; test case generation; test case compensating

2015-12-09；

2016-06-14

國家自然科學基金項目(61170082,61472025)；教育部新世紀優秀人才支持計劃項目(NCET-12-0757) This work was supported by the National Natural Science Foundation of China (61170082, 61472025) and the Project for New Century Excellent Talents in University (NCET-12-0757).

李征(lizheng@mail.buct.edu.cn)

TP311