EFSM模型的字符串類型測(cè)試數(shù)據(jù)自動(dòng)生成

尤楓，邊毅，趙瑞蓮

北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院，北京 100029

EFSM模型的字符串類型測(cè)試數(shù)據(jù)自動(dòng)生成

尤楓，邊毅，趙瑞蓮

北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院，北京 100029

基于軟件描述模型的測(cè)試數(shù)據(jù)自動(dòng)生成研究中，字符串類型測(cè)試數(shù)據(jù)生成是一個(gè)研究熱點(diǎn)和難點(diǎn)。EFSM模型是一種重要的軟件描述模型。分析了EFSM模型的特點(diǎn)，針對(duì)面向EFSM模型目標(biāo)路徑的字符串測(cè)試數(shù)據(jù)生成，建立了字符串輸入變量模型和操作模型，結(jié)合靜態(tài)測(cè)試的特點(diǎn)，給出了通過字符串變量模型在目標(biāo)路徑上的符號(hào)執(zhí)行結(jié)果生成字符串類型測(cè)試數(shù)據(jù)的方法。實(shí)驗(yàn)結(jié)果表明，該方法能夠達(dá)到預(yù)期效果，提高測(cè)試生成效率。

擴(kuò)展有限狀態(tài)機(jī)；測(cè)試數(shù)據(jù)生成；字符串；靜態(tài)分析

1 引言

擴(kuò)展有限狀態(tài)機(jī)（EFSM）模型已廣泛應(yīng)用于軟件系統(tǒng)的抽象[1]，在軟件測(cè)試領(lǐng)域，基于EFSM模型驅(qū)動(dòng)的測(cè)試得到了越來越多的重視。作為保證軟件質(zhì)量的重要手段，軟件測(cè)試的成本通常要占到整個(gè)研發(fā)成本相當(dāng)大的比例[2]。因此運(yùn)用測(cè)試數(shù)據(jù)自動(dòng)生成技術(shù)降低軟件測(cè)試成本，提高軟件可靠性就變得十分重要。目前基于模型的測(cè)試數(shù)據(jù)生成主要是采用搜索算法，例如遺傳算法、模擬退火算法和禁忌搜索算法等，但這些方法一般僅限于整型、布爾型和二叉樹類型等數(shù)據(jù)類型的測(cè)試數(shù)據(jù)生成。

軟件測(cè)試的主要技術(shù)手段有兩種：動(dòng)態(tài)測(cè)試和靜態(tài)測(cè)試[3]。動(dòng)態(tài)測(cè)試是針對(duì)不同的測(cè)試輸入，檢查程序執(zhí)行后的結(jié)果是否與期望結(jié)果相符。靜態(tài)測(cè)試是通過查找相關(guān)代碼和算法的健全性、邏輯性找到目標(biāo)路徑的測(cè)試數(shù)據(jù)。目前針對(duì)字符串類型測(cè)試數(shù)據(jù)生成主要采用動(dòng)態(tài)測(cè)試方法，通過改變編碼的方式，將字符串類型的數(shù)據(jù)轉(zhuǎn)換成整型數(shù)據(jù)，再利用搜索算法實(shí)現(xiàn)測(cè)試數(shù)據(jù)的自動(dòng)生成[4-7]。但這類方法面臨一個(gè)問題，就是字符串長(zhǎng)度不確定且字符變化范圍較大，導(dǎo)致在求解過程中，解空間巨大，搜索成本極高。

本文利用靜態(tài)測(cè)試分析，采用符號(hào)執(zhí)行方法對(duì)EFSM模型中目標(biāo)路徑上的字符串類型數(shù)據(jù)的操作和約束進(jìn)行收集并解析，導(dǎo)出可以覆蓋目標(biāo)路徑的測(cè)試數(shù)據(jù)。

2 EFSM模型和符號(hào)執(zhí)行

2.1 EFSM模型

EFSM模型是FSM模型的擴(kuò)展，它可以表示為一個(gè)六元組M=〈S，s0，I，O，T，V〉，其中S是一個(gè)非空狀態(tài)集，s0是初始狀態(tài)，I是非空輸入消息集合，O是非空輸出消息集合，T是非空狀態(tài)變遷集合，V是變量集合。

每一個(gè)T中的元素是一個(gè)五元組t=(src，tgt，event，cond，action)，src表示原狀態(tài)，tgt表示目標(biāo)狀態(tài)，event是t的激勵(lì)事件或?yàn)榭眨琧ond是t執(zhí)行的前置條件或?yàn)榭?，action為執(zhí)行t所引起的操作[8]。

目前，EFSM模型廣泛應(yīng)用于通信協(xié)議、嵌入式系統(tǒng)、面向?qū)ο蠹皩?duì)象間的交互行為建模中。

2.2 符號(hào)執(zhí)行

在軟件測(cè)試數(shù)據(jù)生成研究中，符號(hào)執(zhí)行是一種非常重要的方法。不同于軟件測(cè)試中常用的動(dòng)態(tài)執(zhí)行，符號(hào)執(zhí)行是利用符號(hào)表達(dá)式表示變量，再代入被測(cè)程序中參與運(yùn)算。在實(shí)際運(yùn)用時(shí)通常是針對(duì)被測(cè)程序的某條目標(biāo)路徑，利用符號(hào)執(zhí)行找出目標(biāo)路徑的變量表達(dá)式，導(dǎo)出能夠覆蓋該條目標(biāo)路徑的測(cè)試用例[9]。

3 EFSM模型字符串操作函數(shù)定義

在EFSM模型規(guī)范中，并未考慮對(duì)字符串類型數(shù)據(jù)的描述，也沒有給出處理字符串的函數(shù)定義和操作。為在使用EFSM模型描述軟件系統(tǒng)時(shí)，能夠準(zhǔn)確描述對(duì)字符串類型數(shù)據(jù)的操作，必須采用適當(dāng)?shù)姆椒▽?duì)字符串類型數(shù)據(jù)進(jìn)行描述。

針對(duì)字符串類型數(shù)據(jù)的操作，本文參照C#語言定義了在EFSM模型中使用的字符串操作函數(shù)，并使用python語言編程實(shí)現(xiàn)了這些字符串操作函數(shù)，如表1所示。其中函數(shù)類型分為兩類：（1）操作函數(shù)，即需要改變或生成新字符串的操作。（2）判斷類型，即判斷字符串是否滿足某些條件，不會(huì)生成新字符串。其中Input和SubString函數(shù)所需的入口變量既可以是一個(gè)，也可以是兩個(gè)。連接字符串函數(shù)除操作變量外，還有一位布爾變量來判斷是在原串前添加還是在原串后添加，默認(rèn)是在原串后添加。

表1 字符串操作函數(shù)定義

在EFSM模型中可以使用這些函數(shù)來描述對(duì)字符串?dāng)?shù)據(jù)的操作，如圖1所示為URL處理程序的EFSM模型，該程序引自文獻(xiàn)[10]，在對(duì)原程序進(jìn)行修改后抽象成EFSM模型，各狀態(tài)的信息描述如表2所示。

圖1 URL處理程序的EFSM模型

表2 URL處理程序的EFSM模型狀態(tài)信息

4 EFSM模型字符串測(cè)試數(shù)據(jù)生成

4.1 字符串測(cè)試數(shù)據(jù)生成框架

EFSM模型字符串測(cè)試數(shù)據(jù)生成框架如圖2所示。首先讀入被測(cè)的EFSM模型，建立與字符串輸入變量名對(duì)應(yīng)的輸入變量模型和全局變量模型，用以記錄字符串?dāng)?shù)據(jù)在目標(biāo)路徑執(zhí)行過程中的變化情況；然后利用編譯技術(shù)，在EFSM模型上提取目標(biāo)路徑各狀態(tài)的condition、event、action信息并進(jìn)行識(shí)別，以獲取有關(guān)對(duì)字符串?dāng)?shù)據(jù)的操作和約束信息，并將其記錄在一個(gè)字符串操作信息表中，文中稱為六項(xiàng)表；最后采用靜態(tài)分析中符號(hào)執(zhí)行的方法對(duì)六項(xiàng)表中記錄的字符串操作和約束信息進(jìn)行求解，以得到目標(biāo)路徑的測(cè)試數(shù)據(jù)。

圖2 字符串測(cè)試數(shù)據(jù)生成流程圖

4.2 字符串變量模型的初始化

字符串輸入變量模型和全局變量模型被初始化為相同的數(shù)據(jù)結(jié)構(gòu)：（1）每個(gè)變量模型存儲(chǔ)的字符串為定長(zhǎng)，具體長(zhǎng)度n由被測(cè)模型決定，并預(yù)先設(shè)置，且n要大于等于輸入字符串的有效位數(shù)；（2）字符串變量模型中每個(gè)字符表示成一個(gè)三元組：實(shí)際值、序號(hào)位和修改位。其中實(shí)際值表示某狀態(tài)下該位的字符，初始值為隨機(jī)生成的字符；序號(hào)位表示該字符在字符串中的位置，范圍由0到n-1，字符串常量的序號(hào)位為-1；修改位為一個(gè)布爾值，表示該位在目標(biāo)路徑上是否被修改，未被修改為0，修改后置1。若被測(cè)模型的字符串輸入變量有兩個(gè)或多個(gè)，則序號(hào)位依次累進(jìn)，保證字符串每一位都具有唯一標(biāo)識(shí)。如圖3所示為兩個(gè)長(zhǎng)度為6的字符串變量模型string1和string2的數(shù)據(jù)結(jié)構(gòu)。

圖3 字符串變量模型數(shù)據(jù)結(jié)構(gòu)圖

輸入變量模型和全局變量模型在目標(biāo)路徑中用以記錄不同的內(nèi)容，輸入變量模型直接參與目標(biāo)路徑上的操作，而全局變量用來生成最后的測(cè)試數(shù)據(jù)。由于在目標(biāo)路徑執(zhí)行過程中某個(gè)輸入字符串可能被多次約束或修改，第一次約束或修改時(shí)輸入變量模型和全局變量模型同時(shí)修改，修改為被約束或被修改后的內(nèi)容，而在余下的目標(biāo)路徑執(zhí)行過程中，只有輸入變量模型會(huì)做相應(yīng)修改，以便參與目標(biāo)路徑上的后續(xù)操作，全局變量模型不再變化。當(dāng)出現(xiàn)第一次修改時(shí)，輸入變量模型和全局變量模型的修改位都會(huì)被修改為1。但當(dāng)該位再次發(fā)生約束或修改時(shí)，會(huì)對(duì)修改位進(jìn)行判斷，若為1，則不再對(duì)全局變量模型進(jìn)行修改。

4.3 六項(xiàng)表生成

依據(jù)EFSM模型和目標(biāo)路徑構(gòu)建狀態(tài)遷移隊(duì)列，并解析各狀態(tài)上的condition、event和action以獲取目標(biāo)路徑中對(duì)各字符串的操作序列，再利用詞法分析將操作序列分解成單獨(dú)詞的表示，以獲取字符串操作函數(shù)名、原變量、目的變量和操作參數(shù)，并填入六項(xiàng)表。表中的列元素分別為：操作名、目的變量、原變量、常量字符串、整型變量1和整型變量2。其中操作名為字符串操作函數(shù)名，目的變量為被賦值變量名，原變量為被操作變量名，后面三個(gè)元素為可能的輸入?yún)?shù)，在操作中的參數(shù)要求只能是變量名或基本數(shù)據(jù)類型，不能出現(xiàn)復(fù)合型的函數(shù)賦值，如操作str1.ChainW ith（str2.SubString（0，2））必須手工進(jìn)行簡(jiǎn)化，將其分解為兩步操作，且參數(shù)最多為一個(gè)變量、一個(gè)常量字符串和兩個(gè)整型參數(shù)。其中Input函數(shù)當(dāng)輸入兩個(gè)變量時(shí)將會(huì)占用原變量和目的變量?jī)蓚€(gè)位置。如表3所示為URL模型中，目標(biāo)路徑（T1，T2，T5，T6，T8）上的操作在六項(xiàng)表中的表示。

表3 URL模型目標(biāo)路徑的六項(xiàng)表

4.4 測(cè)試數(shù)據(jù)生成

六項(xiàng)表中保存了目標(biāo)路徑上所有對(duì)字符串?dāng)?shù)據(jù)的操作和約束信息，根據(jù)這些信息采用符號(hào)執(zhí)行方法可生成覆蓋目標(biāo)路徑的測(cè)試數(shù)據(jù)。在此需要構(gòu)建一個(gè)變量列表，用來記錄字符串變量名以及該變量名對(duì)應(yīng)的變量模型。具體操作步驟如下：

步驟1計(jì)算六項(xiàng)表的行數(shù)n，置m=1。

步驟2若m≤n，讀入第m行六項(xiàng)表元素；若m＞n，轉(zhuǎn)步驟6。

步驟3檢查操作名是否為Input：

若是，將變量名和對(duì)應(yīng)的輸入變量模型添加到變量列表中，置m=m+1，返回步驟2；否則，執(zhí)行步驟4。

步驟4檢查字符串操作是否包含原變量和目的變量：

若包含，查找變量列表，提取相應(yīng)的原變量和目的變量的變量模型。當(dāng)目的變量模型不在變量列表中，即為新的變量，初始化一個(gè)對(duì)應(yīng)的變量模型，執(zhí)行步驟5；否則，直接執(zhí)行步驟5。

步驟5符號(hào)執(zhí)行相應(yīng)的字符串操作函數(shù)，修改對(duì)應(yīng)原變量和目的變量模型的三元組信息，更新變量列表。若含有新變量，則將操作后的變量模型信息加入變量列表，置m=m+1，返回步驟2。

步驟6根據(jù)全局變量模型中三元組的序號(hào)位順序抽取三元組的實(shí)際值形成字符串，生成最終的測(cè)試數(shù)據(jù)。

在這里，針對(duì)操作函數(shù)，要依據(jù)操作的不同，對(duì)變量模型中三元組信息進(jìn)行相應(yīng)修改。如圖4所示為語句String3=String1.SubString（3，5）+String2.SubString（0，4）中變量模型的修改示例。

圖4 兩個(gè)字符串分別取子串合并

表4 用戶登錄程序的EFSM模型狀態(tài)信息

若操作中的參數(shù)是字符串常量，則要在序號(hào)位進(jìn)行特殊標(biāo)記，表示串中的內(nèi)容為字符串常量，與輸入變量沒有直接關(guān)系，如圖5所示為語句String4=String1.Sub-String（0，3）+“_welcome”中變量模型的修改示例。

圖5 字符串變量與常量字符串合并

對(duì)判斷函數(shù)的處理方法，因?yàn)橐笞址嚓P(guān)內(nèi)容滿足相應(yīng)的約束條件，即要對(duì)相應(yīng)位的數(shù)值位進(jìn)行修改，以滿足約束要求的內(nèi)容，且相應(yīng)的修改位必須由0變?yōu)?，表示被第一次修改。如圖6所示為語句String1. StartW ith（“aaa”）中變量模型的修改示例。

圖6 對(duì)一個(gè)字符串的子串賦值

5 實(shí)驗(yàn)結(jié)果及分析

利用Python語言開發(fā)了基于上述方法的字符串測(cè)試數(shù)據(jù)生成系統(tǒng)，并進(jìn)行了方法有效性實(shí)驗(yàn)。

實(shí)驗(yàn)1基于一個(gè)簡(jiǎn)化的用戶登錄程序的EFSM模型，如圖7和如表4所示，其中主要遷移路徑有（T1，T3，T6），（T1，T2，T4，T5，T6）。兩個(gè)輸入變量name和psw d對(duì)應(yīng)的輸入變量模型和全局變量模型長(zhǎng)度均設(shè)為6，因?yàn)槟繕?biāo)路徑上沒有涉及字符串類型數(shù)據(jù)的多次約束和修改，所以最終的輸入變量模型和全局變量模型中存儲(chǔ)的字符串?dāng)?shù)據(jù)相同。最終由全局變量模型解析生成的測(cè)試數(shù)據(jù)如表5所示。

圖7 用戶登錄程序的EFSM模型

表5 兩模型目標(biāo)路徑測(cè)試數(shù)據(jù)生成信息

實(shí)驗(yàn)2基于URL模型，該模型主要遷移路徑有（T2），（T1，T4），（T1，T3，T5），（T1，T3，T6，T7），（T1，T3，T6，T8）。實(shí)驗(yàn)針對(duì)每條路徑，生成相應(yīng)能夠覆蓋目標(biāo)路徑的測(cè)試用例。

輸入變量str對(duì)應(yīng)的輸入變量模型和全局變量模型長(zhǎng)度均設(shè)為25，最終由全局變量模型解析生成的測(cè)試數(shù)據(jù)如表5所示。

在表5中，測(cè)試數(shù)據(jù)加下劃線字符為初始隨機(jī)生成的字符，在測(cè)試數(shù)據(jù)生成過程中未被修改。這些字符可能超出輸入字符串需求的冗余位，也可能是任意字符均可，在生成最終測(cè)試數(shù)據(jù)時(shí)可根據(jù)該位的不同字符生成多個(gè)不同的測(cè)試用例。

為驗(yàn)證本文方法的執(zhí)行效率，將其與遺傳算法和模擬退伙算法在測(cè)試數(shù)據(jù)生成時(shí)間上進(jìn)行了對(duì)比。

實(shí)驗(yàn)在用戶登錄程序的EFSM模型上進(jìn)行，選取目標(biāo)路徑為（T1，T2，T4，T5，T6），字符串輸入長(zhǎng)度設(shè)計(jì)為1位和2位，遺傳算法和模擬退伙算法測(cè)試數(shù)據(jù)生成方法引自文獻(xiàn)[8]和[11]，這兩種方法可實(shí)現(xiàn)整數(shù)類型的測(cè)試數(shù)據(jù)生成。

為在遺傳算法和模擬退火算法上進(jìn)行字符串類型測(cè)試數(shù)據(jù)生成，本文首先對(duì)字符串類型數(shù)據(jù)進(jìn)行十進(jìn)制編碼，且在編碼方式上采用兩種方法：（I）采用兩位整型數(shù)編碼一個(gè)字符，即00～09表示數(shù)字0～9，10～35表示a～z，36～61表示A～Z；（II）采用ASCII碼表示字符。

遺傳算法初始化個(gè)體為20個(gè)，最大迭代次數(shù)為300 000，交叉率0.7，變異率0.08；模擬退火算法種群大小為20，最大迭代次數(shù)15 000。每種方法均進(jìn)行了100次實(shí)驗(yàn)，生成一組覆蓋目標(biāo)路徑的測(cè)試數(shù)據(jù)所消耗的時(shí)間如表6所示。

表6 三種解決方法在時(shí)間上的比較s

從表中數(shù)據(jù)可見，采用遺傳算法和模擬退伙算法完成目標(biāo)路徑測(cè)試數(shù)據(jù)生成平均花費(fèi)時(shí)間遠(yuǎn)高于本文方法所花費(fèi)的時(shí)間。并且模擬退火算法在使用ASCII碼編碼兩字符的字符串時(shí)，實(shí)驗(yàn)過程中迭代超過迭代次數(shù)上限后退出，無法生成測(cè)試數(shù)據(jù)?？梢姡?dāng)所需輸入字符串長(zhǎng)度更長(zhǎng)時(shí)，遺傳算法和模擬退火算法無法在合理的時(shí)間內(nèi)生成測(cè)試數(shù)據(jù)，而符號(hào)執(zhí)行可以在較短時(shí)間生成測(cè)試數(shù)據(jù)，但是相比于遺傳算法和模擬退火，符號(hào)執(zhí)行所能求解的邏輯復(fù)雜性還需進(jìn)一步提高。

6 結(jié)束語

在基于模型的軟件測(cè)試領(lǐng)域，字符串類型測(cè)試數(shù)據(jù)自動(dòng)生成還沒有相對(duì)完善且高效的解決辦法。本文針對(duì)含字符串?dāng)?shù)據(jù)類型輸入的EFSM模型，采用靜態(tài)分析方法，運(yùn)用三元組模型和六項(xiàng)表，通過符號(hào)執(zhí)行方法就文中涉及的函數(shù)操作自動(dòng)生成覆蓋相應(yīng)目標(biāo)路徑的字符串測(cè)試數(shù)據(jù)。但是該方法還存在不足：（1）所處理的字符串操作函數(shù)的數(shù)量有待擴(kuò)充，以便處理更為復(fù)雜的字符串操作；（2）針對(duì)復(fù)雜的字符串邏輯判斷，無法很好處理。（3）相關(guān)冗余位中信息的處理。在今后的工作中，針對(duì)以上不足還需做繼續(xù)的研究。

[1]Kalaji A S，Hierons R M，Sw ift S.An integrated search-based approach for automatic testing from extended finite state machine（EFSM）models[J].Information and Software Technology，2011，53：1297-1318.

[2]Beizer B.Software testing techniques[M].2nd ed.[S.l.]：Van Nostrand Reinhold.1990.

[3]Gupta N，M athur A P，Soa M L.Automated test data generation using an iterative relaxation method[J].Special Interest Group on Software Engineering，1998（11）：231-244.

[4]Zhao Ruilian，Lyu M R.Character string predicate based automatic software test data generation[C]//International Conference on Quality Software，2003：255-262.

[5]Zhao Ruilian，Lyu M R，M in Yinghua.Domain testing based on character string predicate[C]//Asian Test Sym posium，2003：96-101.

[6]A lshraideh M，Bottaci L.Search-based software test data generation for string data using program-specific search operators[J].Software Testing，Verification and Reliability，2006，16（3）：175-203.

[7]Zhao Ruilian，Lyu M R，M in Yinghua.Automatic string test data generation for detecting domain errors[J].Software Testing Verification and Reliability，2010，20（3）：209-236.

[8]You Feng，Yan Yu，Zhao Rui-Lian.Test data generation for EFSM models with procedure calls[J].International Conference on Information Science and Engineering，2011：5508-5511.

[9]Ruan Hui，Zhang Jian，Yan Jun.Test data generation for C programs with string-handling functions[C]//International Symposium on Theoretical Aspects of Software Engineering，2008，25：219-226.

[10]Bj?rner N，Tillmann N，Voronkov A.Path feasibility analysis for string manipulating programs[C]//International Conference on Tools and A lgorithms for the Construction and Analysis of Systems，2009：307-321.

[11]程喜朝.基于模擬退火算法的EFSM模型測(cè)試數(shù)據(jù)自動(dòng)生成[D].北京：北京化工大學(xué)，2011.

YOU Feng,BIAN Yi,ZHAO Ruilian

Department of Information Science and Technology,Beijing University of Chem ical Technology,Beijing 100029,China

In the field of automatic test data generation for software description model,one of the most difficult challenge is string test data generation.EFSM model is a kind of important software description model,so the characteristic of EFSM model is analyzed,then the input variable model and operational model are built.Based on path-oriented test data generation method and static analysis,the string test data for goal path by using symbolic execution is generated.Em pirical results show that this approach is applicable and can effectively generate test suite to cover the target paths.

Extended Finite State Machine（EFSM）;test data generation;string;static analysis

A

TP311.5

10.3778/j.issn.1002-8331.1209-0179

YOU Feng,BIAN Yi,ZHAO Ruilian.Autom atic string test data generation for EFSM model.Computer Engineering and Applications,2014,50（16）：57-61.

國(guó)家自然科學(xué)基金（No.61073035，No.61170082）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助（No.ZZ1224）。

尤楓（1963—），男，副教授，研究方向?yàn)閷?shí)時(shí)信息系統(tǒng)平臺(tái)、軟件測(cè)試；邊毅（1986—），博士研究生，研究方向?yàn)檐浖y(cè)試；趙瑞蓮（1964—），教授，博士，研究方向?yàn)檐浖y(cè)試與軟件可靠性。E-mail：youf@mail.buct.edu.cn

2012-09-18

2012-11-28

1002-8331（2014）16-0057-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2012-12-19,http://www.cnki.net/kcms/detail/11.2127.TP.20121219.1641.009.htm l