協議一致性測試用例生成模型研究

齊建業(yè)，李 強，余 祥

（電子工程學院，安徽 合肥230037）

0 引 言

對協議進行一致性測試，通過有限狀態(tài)機（finite state machine，FSM）對協議標準文本描述進行形式化分析，由于主觀上的理解可能會在建模中產生偏差，影響后續(xù)測試用例的生成。利用FSM 直接描述協議標準文本，轉化過程比較抽象，要求相對較高。由于UML 具有交互性強、直觀生動的特點，可以通過UML 圖自動生成軟件測試用例［1］。因此，可以采用UML 中的活動圖對被測協議標準的功能說明進行描述，進而生成協議一致性測試的測試用例。

本文建立了協議一致性測試用例生成模型，由形式化活動圖、擴展有限狀態(tài)機和算法FADToEFSM 組成。通過形式化定義UML 活動圖，可以將由自然語言描述的任意的協議標準文本轉化為形式化的活動圖，降低了協議形式化分析的復雜程度。設計FADToEFSM 算法將形式化的活動圖轉化為擴展有限狀態(tài)機（extended finite state machine，EFSM），將EFSM 再轉化為測試用例，上述兩個轉化過程按照數學運算，消除了協議一致性測試覆蓋的不完備問題。根據實際被測的協議實現產品說明實例化測試數據，生成協議一致性測試用例。

1 相關概念

1.1 形式化活動圖

活動圖是UML模型中用于對系統(tǒng)的動態(tài)行為建模的一種圖形工具，它或是對活動的序列進行描述，或是描述對活動控制轉化進行描述。UML 對動態(tài)語義的描述不是十分清楚，例如一個活動圖的節(jié)點可以描述事件、退出、入口以及執(zhí)行等4 種動作，具體是哪一種動作，不清楚。因此，對活動圖模型中若干圖形元素的語義和語法進行形式化。

定義1 形式化活動圖（formal activity diagram，FAD）［2］

通過圖像來描述協議實現之間的數據包交互關系：

FAD＝＜ID，Start，End，SA，IN，OUT，Judge，FL，Con＞

（1）標識ID：唯一地標識一個FAD；

（2）系統(tǒng)動作SA：描述數據包生成；

（3）輸出動作OUT：描述數據包發(fā)送；

（4）輸入動作IN：描述數據包捕獲；

（5）起始端點Start：描述FAD 的開始狀態(tài)，即START 事件，限定一個FAD 只有一個起始點；

（6）結束端點End：描述FAD 的終結狀態(tài)，即CLOSURE事件，限定一個FAD 只有一個結束點；

（7）判斷框Judge：作為一種條件判斷，描述一個或者幾個進口點、出口點；

（8）連線FL：描述FAD 中兩個節(jié)點之間的控制流線條；

（9）聯系點Con：作為連線的連接部分，可以有一條或多條連線進入，限定只有一個連線出口。

1.2 擴展有限狀態(tài)機

定義2 擴展的有限狀態(tài)機（EFSM）［2］

擴展有限狀態(tài)機EFSM 用五元組來表示：EFSM＝（S，s0，sF，T，δ）。擴展有限狀態(tài)機將形式化活動圖轉換為轉移事件集合以及狀態(tài)集合。集合元素的唯一性，使得用同一語義的轉移事件或狀態(tài)時，使用唯一的定義，從而避免了語義矛盾的產生。

2 FAD 轉換EFSM 算法

根據EFSM 的定義，設計從FAD到EFSM 的轉換原則：

（1）將起始端點轉換為開始狀態(tài)s0；

（2）將系統(tǒng)動作轉換為EFSM 中的一個事件狀態(tài)和一個系統(tǒng)轉移Trig＿SystemAction＿Num；

（3）將輸入動作轉換為一個空偽狀態(tài)St＿Empty＿Num 和一個輸入轉移；

（4）將輸出動作轉換為EFSM 中的一個輸出狀態(tài)和一個自動轉移Trig＿Automation；

（5）將判斷框轉換為在EFSM 中增加一個St＿Fork－Join＿Num，根據出口判斷增加Trig＿Constraint＿Num 和空偽狀態(tài)St＿Empty＿Num；

（6）連接點只起到兩條流線之間的傳遞作用，沒有狀態(tài)轉化；

（7）將結束點轉化為結束狀態(tài)sF。

根據上述轉換規(guī)則，設計了將FAD 轉換為EFSM 的算法。

算法：EFSM 自動生成produceEFSMFromFAD （fad）

算法原理：將形式化活動圖中的圖元按照從初始點到結束點的順序添加到EFSM 中。如果EFSM 中沒有則增加一個新狀態(tài)，同時添加一個轉移事件；如果擴展有限狀態(tài)機中已經有相應圖元轉化的狀態(tài)，那么只增加一個轉移事件；如果是連接點，不轉化，檢查并轉化下一個圖元。

輸入：FAD

輸出：EFSM

算法步驟：

（1）新建一個EFSM 類的對象efsm；

（2）將開始狀態(tài)s0添加到efsm；

（3）調用局部函數constructEFSM（StartObj，efsm）將FAD分解為EFSM片段；

（4）調用局部函數AddtoEFSM（NextObj，StartObj，efsm）將分解的EFSM 片段添加到擴展有限狀態(tài)機中；

（5）從結束狀態(tài)中刪除不符合定義的狀態(tài)；

（6）返回efsm。

其中，局部函數constructEFSM（StartObj，efsm）是一個遞歸函數，它的作用是將FAD 中圖元分解為EFSM 片段，按照圖元類型和轉換規(guī)則將FAD 中起始點和結束點轉化為EFSM 中的初始狀態(tài)和結束狀態(tài)，將系統(tǒng)動作轉化為EFSM 中的事件狀態(tài)和系統(tǒng)轉移，將輸入操作轉化為EFSM 中的一個輸入轉移和空偽狀態(tài)，將輸出操作轉化為EFSM 中的自動轉移和輸出狀態(tài)，將判定框轉化為EFSM 中的連接復合偽狀態(tài)，根據出口增加條件轉移和空偽狀態(tài)。constructEFSM（StartObj，efsm）中定義了遞歸函數AddtoEFSM（NextObj，StartObj，efsm），它的作用是將由FAD片段轉換生成的EFSM 片段添加到擴展有限狀態(tài)機中。

3 測試用例生成

測試用例生成是根據擴展有限狀態(tài)機轉化為測試序列，然后對測試序列進行實例化。其中，從EFSM 生成測試序列就是要找出所有從初始狀態(tài)到結束狀態(tài)的可行序列；實例化測試序列即是對EFSM 中包含的數據進行實例化，生成執(zhí)行的測試用例。

3.1 測試序列生成

測試序列是EFSM 中的所有狀態(tài)序列集合。根據有向圖的廣度優(yōu)先搜索算法將EFSM 轉換為測試序列。

算法：從擴展有限狀態(tài)機構造一個測試序列集合produceTPS

算法原理：新建一條測試序列，從EFSM 的初始狀態(tài)s0開始，對擴展有限狀態(tài)機中的狀態(tài)和轉移進行遍歷，添加到測試序列中。測試序列按照分支判定的數目劃分為相應的若干測試序列，遇到擴展有限狀態(tài)機中的結束狀態(tài)sF結束遍歷［3］。

輸入：efsm輸出：測試序列集合TPS：tps＝｛tp1，tp2，…tpn｝算法步驟：

（1）新建測試序列tp，并將efsm 的開始狀態(tài)s0加入到tp中；

（2）將新建序列加入到測試序列集合中；

（3）調用局部函數contructTP 將遍歷的狀態(tài)添加到測試序列中；

（4）去除測試序列集合中的每一條序列的空狀態(tài)；

（5）返回tps；

其中，局部函數contructTP 是一個遞歸函數，它的作用是將當前遍歷到的狀態(tài)補充到當前序列中，并更新測試序列集合。

算法produceTPS采用廣度優(yōu)先搜索算法，對EFSM 中的狀態(tài)和轉移進行遍歷，在最差的情形下，必須尋找到所有可能節(jié)點的所有序列，因此其時間復雜度為O（n＋e），其中n 是EFSM 中的狀態(tài)節(jié)點數目，e是EFSM 中的連線數目。

3.2 實例化測試序列

對測試序列實例化，是對由EFSM 生成的測試序列中的測試數據進行實例化，生成有效的測試用例。對測試數據實例化，是對測試過程中的數據包字段數值通過邊界值分析［4］和等價類劃分［5］的方法進行賦值。

邊界值分析法對字段數值域的最大值、最小值、范圍內任意值、較小于最大值、較小于最小值、較大于最大值、較大于最小值根據協議標準文本描述來分別設計測試用例。等價類劃分法將字段數值域劃分為無效等價類和有效等價類，在每一個等價類中再根據邊界值分析法設計一個測試數據。

以測試字段 “會話標識”為例設計一組測試用例進行說明，按照協議標準規(guī)定其類型為數字，大小為2B，劃分有效等價類為（0，0xFFFF］。

（1）利用邊界值法，設計如下字段數值：

字段數值取值1：0xFFFF（上界）

字段數值取值2：0（下界）

（2）利用等價類劃分法，設計如下測試用例：

字段數值取值3：－1（不符合協議標準）

字段數值取值4：0x10000（不符合協議標準）

字段數值取值5：＃￥%＆＊＠（非數字字符）

字段數值取值6：空 （即數據包中沒有 “消息長度”這個字段）

（3）根據數據包的實際長度，為其賦予1 個正確的數值。

因此，為字段 “會話標識”設計總計7個測試用例。

4 算法分析與比較

以測試IKE協議為例，從測試序列生成、測試序列錯誤覆蓋度、測試用例測試覆蓋和測試用例執(zhí)行效率，對測試序列生成算法produceTPS與UIO 方法［6］、BUIO 方法［7］進行分析比較。具體地講就是，對測試序列生成算法produceTPS與UIO 方法、BUIO 方法從測試序列生成和測試序列錯誤覆蓋度進行分析比較；對測試用例生成算法produceTC與文獻［8－11］，從測試用例測試覆蓋和測試用例執(zhí)行效率進行分析比較。

4.1 測試序列生成和錯誤覆蓋度分析

（1）測試序列生成分析

測試序列的長度及其錯誤覆蓋度決定了測試序列生成算法的優(yōu)劣。其中，測試序列的長度決定了測試過程的工作時間，測試每個狀態(tài)轉換的可用測試序列，其長度等于可用測試序列中的狀態(tài)個數；錯誤覆蓋度表征了測試序列的檢錯能力和可信賴程度。

以測試IKE協議主模式客戶端預共享驗證方式為例，UIO 方法生成的測試序列長度最長為39，BUIO 方法生成的測試序列長度最長為22［12］；produceTPS 算法生成的測試序列長度最長為11，縮短比例分別為71.79%和50%。

在EFSM 中，通過produceTPS算法生成的每個狀態(tài)的可用測試序列見表1。

則produceTPS算法生成的可用測試序列T1～T8長度與UIO 方法和BUIO 方法生成的可用測試序列長度［10］對比如圖1所示。

圖1 測試序列長度

由圖1可見，對每個狀態(tài)轉換的可用測試序列長度來說，produceTPS算法比UIO 算法短，比BUIO 算法長。測試用例中的測試步驟由測試序列的長度決定，因此produceTPS算法優(yōu)于UIO 方法；produceTPS 算法之所以比BUIO 方法生成測試序列長，是因為BUIO 方法在生成測試序列的過程中，沒有考慮到構造數據包的狀態(tài)，因此通過BUIO 方法生成的測試序列來進一步設計與生成測試用例，需要主觀上對抽象測試序列的理解。測試數據包的構造在測試用例中是一項重要環(huán)節(jié)，produceTPS算法添加了構造數據包的狀態(tài)，就可以通過測試序列自動生成測試用例，使得測試用例描述的測試過程更加完整和清楚，更容易進行測試執(zhí)行，可以減少后期工作量。

表1 可用測試序列

（2）錯誤覆蓋度分析比較

UIO 方法和BUIO 方法都是以UIO 序列為特征序列來驗證每次轉換的末狀態(tài)，對FSM 中的所有轉換進行了遍歷，其錯誤覆蓋度都超過99%［12］。而produceTPS算法基于有向圖的廣度優(yōu)先搜索算法，也是對FSM 中的所有轉換進行了遍歷，并且嚴格遵循關鍵子句邏輯覆蓋準則，因此其錯誤覆蓋度與UIO 方法和BUIO 方法相近，都超過99%。但是UIO 方法和BUIO 方法基于的FSM 沒有完全形式化，不同轉換的末狀態(tài)可能是同一個狀態(tài)（如自轉移），所以在形式化描述上UIO 方法和BUIO 方法不如produceTPS算法。

4.2 測試用例測試覆蓋和測試用例執(zhí)行效率分析比較

測試用例測試覆蓋分析比較

設計與生成的測試用例應覆蓋被測協議標準的所有功能點，顆粒度劃分適當，沒有冗余。測試數據應遵循錯誤覆蓋準則，生成的測試用例既包括測試行為與測試數據正確的測試用例，也包括測試行為與測試數據不正確的測試用例。

通過測試用例生成算法produceTC設計IPsec協議測試集，對字段數值采用等價類劃分和邊界值分析法相結合的方式進行賦值。IPsec協議包括3個子協議：IKE 協議、認證頭協議AH 和封裝安全載荷協議ESP。

采用等價類劃分和邊界值分析法為IPsec每個協議設計一個測試集，見表2。每個測試集包含若干測試項，分為有效等價類劃分項和無效等價類劃分項；再根據測試項設計相應的有效等價類測試用例和無效等價類測試用例。

表2 IPsec協議測試集

將表2設計的IPsec協議測試集與已有的IPsec協議測試集［8－11］進行對比分析。各文獻中設計的測試用例數如圖2所示。

圖2 測試集比較

對圖2中的數據進行對比分析如下：

（1）由可知，對于IKE 協議，文獻［8－10］中并沒有為其設計測試用例；文獻［11］中沒有對AH 協議和ESP協議設計測試用例。由于ESP 協議、AH 協議和IKE 協議是IPsec協議的重要組成部分，其中任意一個協議的測試用例缺失對于整個IPsec協議測試集來說都是不完備的。

（2）對于文獻［8－10］中設計的AH 和ESP 協議測試用例集，并沒有給出具體的測試用例設計過程，因此不方便對比分析。

（3）文獻［11］有91個IKE 協議測試用例，有45個功能性測試用例和46個行為性測試用例，并且行為測試用例中沒有覆蓋不正確行為的測試用例。由于IKE 協議中的功能測試用例和行為測試用例可結合進行［11］，重復設計導致測試用例冗余。

（4）本文針對IKE、AH、ESP協議分別進行了測試用例設計，如所示，共設計1785個測試用例。進行測試用例設計時，通過邊界值原則和等價類劃分原則設計字段數值生成測試用例，可以盡量避免冗余測試用例的產生。

因此根據以上分析可知，本文設計的協議測試集比現有的測試集在測試覆蓋度方面更全面。

測試用例的執(zhí)行效率分析

文獻［8－10］中，未涉及IKE 測試集，文獻［11］利用UIO 算法為IKE 協議設計了正確的行為測試用例。論文采用produceTPS算法生成測試序列，與UIO 算法相比，減少了測試序列的平均長度。因此本文在設計測試用例時，是利用produceTPS算法生成的較短測試序列上進行的，生成的測試用例中包含測試步驟更少，執(zhí)行時測試效率更高。

5 結束語

在協議的一致性測試中，通過測試用例指導測試執(zhí)行。本文提出一種基于形式化活動圖和擴展有限狀態(tài)機的協議一致性測試用例生成模型，利用FAD 對協議標準中說明的協議功能描述進行形式化建模，設計算法將FAD 轉換為EFSM 自動生成測試用例。通過一個實例與已有的測試序列生成算法進行對比分析，結果表明在測試序列、測試序列錯誤覆蓋度、測試用例測試覆蓋和測試用例執(zhí)行效率均具有一定的優(yōu)越性。

［1］TONG Yi，DONG Bidan.Test cases automatic generation from UML state diagram ［J］.Microcomputer Information，2011，27 （9）：201－203 （in Chinese）. ［佟軼，董碧丹.UML 狀態(tài)圖的測試用例自動生成 ［J］.微計算機信息，2011，27 （9）：201－203.］

［2］QI Jianye，LI Qiang，YU Xiang.Research on test case generation using formal activity diagram of protocol conformance testing ［J］.Journal of Anhui University （Natural Science Edition），2013，37 （3）：75－80 （in Chinese）. ［齊建業(yè)，李強，余祥.基于形式活動圖的協議一致性測試用例生成方法研究［J］.安徽大學學報 （自然科學版），2013，37 （3）：75－80.］

［3］YU Xiang，LI Qiang，QI Jianye.A research on automated software test case generation based on control flow ［J］.Journal of Inner Mongolia University （Natural Science Edition），2011，42 （5）：521－527 （in Chinese）. ［余祥，李強，齊建業(yè).基于控制流程的軟件測試用例自動生成方法研究 ［J］.內蒙古大學學報 （自然科學版），2011，42 （5）：521－527.］

［4］LIU Chunling，LEI Haihong.Design method of black－box testing case ［J］. Modern Electronics Technique，2012，33（20）：46－48 （in Chinese）.［劉春玲，雷海紅.黑盒測試用例設計方法研究 ［J］.現代電子技術，2012，33 （20）：46－48.］

［5］GUO Xi，ZHANG Huanguo.Approach for reduced test suite generation based on predicate abstraction ［J］.Journal on Communications，2012，33 （3）：35－43 （in Chinese）. ［郭曦，張煥國.基于謂詞抽象的測試用例約減生成方法 ［J］.通信學報，2012，33 （3）：35－43.］

［6］Gu Juan，Yuan Dongming，Hu Hefei，et al.An improved method based on UIOv for test sequence generation ［C］／／IEEE 14th International Conference on Communication Technology，2012：573－577.

［7］GAO Zhanchun，HU Xiaoling，JIANG Yanjun，et al.Research on BUIO generation and test sequences generation algorithms［J］.Computer Engineer and Applications，2011，47（6）：116－118 （in Chinese）.［高占春，胡曉玲，蔣硯軍，等.BUIO 生成及測試序列生成算法研究 ［J］.計算機工程與應用，2011，47 （6）：116－118.］

［8］TIAN Jun.Research on IPv6protocol conformance test and implementation of the test system ［D］.Beijing：Institute of Computing Technology Chinese Academy of Sciences，2001（in Chinese）.［田軍.IPv6協議一致性測試研究及測試系統(tǒng)實現 ［D］.北京：中國科學院計算技術研究所，2001.］

［9］ZHENG Hongxia.A test case design method for IPv6protocol conformance testing ［D］.Beijing：Institute of Computing Technology Chinese Academy of Sciences，2003 （in Chinese）.［鄭紅霞.IPv6協議一致性測試例設計方法 ［D］.北京：中國科學院計算技術研究所，2003.］

［10］LV Chao.Research on the design of IPSec protocol confor－mance testing system ［D］.Hefei：University of Science and Technology of China，2005 （in Chinese）.［呂超.IPSec協議一致性測試系統(tǒng)的設計研究［D］.合肥：中國科學技術大學，2005.］

［11］WANG Wenjuan.Research on the test suite generation for security protocol［D］.Zhengzhou：The PLA Information Engineering University，2009 （in Chinese）. ［王文娟.安全協議測試集生成技術研究 ［D］.鄭州：解放軍信息工程大學，2009.］

［12］MA Yan.Research on optimizing test techonolgy of IPSec protocol［D］.Zhengzhou：The PLA Information Enginee－ring University，2010 （in Chinese）.［馬艷.IPSec協議測試優(yōu)化技術研究 ［D］.鄭州：解放軍信息工程大學，2010.］