EFSM模型的字符串類型測試數據自動生成

尤楓，邊毅，趙瑞蓮

北京化工大學信息科學與技術學院，北京 100029

EFSM模型的字符串類型測試數據自動生成

尤楓，邊毅，趙瑞蓮

北京化工大學信息科學與技術學院，北京 100029

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

擴展有限狀態機；測試數據生成；字符串；靜態分析

1 引言

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

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

本文利用靜態測試分析，采用符號執行方法對EFSM模型中目標路徑上的字符串類型數據的操作和約束進行收集并解析，導出可以覆蓋目標路徑的測試數據。

2 EFSM模型和符號執行

2.1 EFSM模型

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

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

目前，EFSM模型廣泛應用于通信協議、嵌入式系統、面向對象及對象間的交互行為建模中。

2.2 符號執行

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

3 EFSM模型字符串操作函數定義

在EFSM模型規范中，并未考慮對字符串類型數據的描述，也沒有給出處理字符串的函數定義和操作。為在使用EFSM模型描述軟件系統時，能夠準確描述對字符串類型數據的操作，必須采用適當的方法對字符串類型數據進行描述。

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

表1 字符串操作函數定義

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

圖1 URL處理程序的EFSM模型

表2 URL處理程序的EFSM模型狀態信息

4 EFSM模型字符串測試數據生成

4.1 字符串測試數據生成框架

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

圖2 字符串測試數據生成流程圖

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

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

圖3 字符串變量模型數據結構圖

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

4.3 六項表生成

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

表3 URL模型目標路徑的六項表

4.4 測試數據生成

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

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

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

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

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

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

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

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

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

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

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

表4 用戶登錄程序的EFSM模型狀態信息

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

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

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

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

5 實驗結果及分析

利用Python語言開發了基于上述方法的字符串測試數據生成系統，并進行了方法有效性實驗。

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

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

表5 兩模型目標路徑測試數據生成信息

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

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

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

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

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

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

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

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

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

6 結束語

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

[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模型測試數據自動生成[D].北京：北京化工大學，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.

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

尤楓（1963—），男，副教授，研究方向為實時信息系統平臺、軟件測試；邊毅（1986—），博士研究生，研究方向為軟件測試；趙瑞蓮（1964—），教授，博士，研究方向為軟件測試與軟件可靠性。E-mail：youf@mail.buct.edu.cn

2012-09-18

2012-11-28

1002-8331（2014）16-0057-05

CNKI網絡優先出版：2012-12-19,http://www.cnki.net/kcms/detail/11.2127.TP.20121219.1641.009.htm l