尤楓，邊毅，趙瑞蓮

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

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

尤楓，邊毅，趙瑞蓮

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

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

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

1 引言

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

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

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

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

2.1 EFSM模型

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

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

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

2.2 符號執(zhí)行

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

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

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

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

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

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

圖1 URL處理程序的EFSM模型

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

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

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

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

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

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

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

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

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

4.3 六項表生成

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

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

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

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

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

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

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

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

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

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

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

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

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

圖4 兩個字符串分別取子串合并

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

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

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

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

圖6 對一個字符串的子串賦值

5 實驗結(jié)果及分析

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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

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

尤楓（1963—），男，副教授，研究方向為實時信息系統(tǒng)平臺、軟件測試；邊毅（1986—），博士研究生，研究方向為軟件測試；趙瑞蓮（1964—），教授，博士，研究方向為軟件測試與軟件可靠性。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