面向充電機通信協(xié)議一致性測試的用例自動生成方法

何雪楓, 賈俊國, 李旭玲

(1. 國網(wǎng)電力科學研究院有限公司, 江蘇 南京 211106; 2. 國網(wǎng)電動汽車服務有限公司, 北京 100053)

隨著國家節(jié)能環(huán)保的號召,電動汽車產(chǎn)業(yè)正在快速發(fā)展.而對于電動汽車來說,能否正常有效的充電無疑是需要著重考慮的問題.因此,針對電動汽車充電過程的通信協(xié)議一致性測試便成為整個生產(chǎn)過程中的一個重要環(huán)節(jié)[1].一般情況下,通信協(xié)議規(guī)范是由文本語言記錄的,不同操作者對協(xié)議可能會有不一樣的認識,由此導致協(xié)議的實際完成會有多個版本.更有甚者,由于對協(xié)議的理解有誤,可能出現(xiàn)錯誤實現(xiàn).本文研究的目的就是為了保持通信協(xié)議的實現(xiàn)與相應的標準保持一致性,確保對標準協(xié)議的不同實現(xiàn)之間能夠保持一致并能正確通信.

本文針對現(xiàn)有經(jīng)驗導向的一致性測試方法缺乏理論支撐,測試覆蓋性弱,可復用性較差的問題,對面向充電機通信協(xié)議一致性測試的用例自動生成方法展開研究.

1 相關工作

關于協(xié)議一致性測試的研究[2-3]一直是一個熱門的方向.現(xiàn)有的研究已經(jīng)涌現(xiàn)出一批典型的一致性測試用例生成方法[4].羅軍舟等[5]闡述了Petri網(wǎng)技術在協(xié)議描述中的優(yōu)勢.宋金晶等[6]使用一種基于通信順序進程的算法對網(wǎng)絡協(xié)議進行仿真.公彥杰等[7]提出OPC-UA一致性自動測試方法,包括構建OPC-UA協(xié)議一致性測試用例的基本方法、測試用例運行以及測試結果反饋等一系列方法,使用戶可以高效快速地構建測試用例并實現(xiàn)協(xié)議一致性測試的自動化.

有限狀態(tài)機(finite state machine,FSM)非常適用于對協(xié)議進行建模,也是應用最為廣泛的一種數(shù)學模型.因此,FSM模型常被用于測試序列生成算法.FSM由有限穩(wěn)定的狀態(tài)構成,并能在已經(jīng)確定的狀態(tài)之間實現(xiàn)狀態(tài)轉換,同時在轉換的過程中會產(chǎn)生一定的輸入輸出[8].有限狀態(tài)機作為用例測試集與協(xié)議之間關系的一種描述子,實現(xiàn)簡單,同時方便同別的形式化描述子組合使用.因此,FSM十分適合對協(xié)議的狀態(tài)轉換關系進行建模[9].

對于充電機與電池管理系統(tǒng)(battery management system,BMS)的通信協(xié)議一致性測試,劉武等[10]利用硬件板卡和LabVIEW軟件構建了一種CAN通信平臺,并在此平臺上模擬充電機,通過監(jiān)測充電機與電池管理系統(tǒng)通信中的報文發(fā)送與接收情況來測試通信過程的出錯狀況.李旭玲等[11]針對充電機監(jiān)控單元設計一套協(xié)議一致性測試系統(tǒng).黃炘等[12]針對電動汽車無線充電通信協(xié)議設計了一種一致性測試框架.但是,上述方法中充電機和BMS之間的通信協(xié)議一致性測試主要是根據(jù)專家經(jīng)驗來設計測試用例,沒有理論支撐,從而導致測試覆蓋性弱,測試結果缺乏說服力,難以形成行業(yè)標準.

因此,依據(jù)有限狀態(tài)機的優(yōu)勢,本文面向充電機與BMS的通信過程設計一種基于有限狀態(tài)機的協(xié)議一致性測試方法用于解決上述問題.首先,通過對GB/T 27930—2015協(xié)議的詳細解讀,分析充電機和BMS之間的消息交流過程.其次,使用FSM形式化語言描述充電機和BMS之間的充電過程,用以保證協(xié)議的不同實體之間的通信一致性.最后,在FSM的基礎上完成充電機活動過程中測試序列以及測試用例的獲取.

使用FSM進行測試序列生成的算法有很多種,在這么多種算法中基于唯一輸入/輸出序列(unique input/output,UIO)的U方法是最常用的[13],此方法實現(xiàn)起來較為容易,同時能夠得到簡練的測試序列.因此,本文在FSM的基礎上使用UIO方法計算測試序列,并采用遞歸算法考慮前置用例,讓每一個測試用例都有完整的輸入輸出,從而得到最終的測試用例集合.

2 有限狀態(tài)機模型簡介

有限狀態(tài)機是一種典型的形式化模型方法.在眾多的形式化描述方法中,FSM方法憑借其簡單靈活的特性被研究者們廣泛使用,出現(xiàn)了很多諸如擴展有限狀態(tài)機等的FSM衍生方法.例如,Mauricio等[14]使用了擴展有限狀態(tài)機結合UML模型來完成測試用例的自動生成.

而關于使用有限狀態(tài)機進行測試用例生成最早可以追溯到65年前Moore關于自動機的研究,之后開展的一些研究只在理論層面進行分析.到了最近幾年,使用FSM進行測試用例計算的研究開始被轉向應用到真實的工作場景中.由于有限自動機中的Mealy機定義和通信協(xié)議的內容比較吻合,因此Mealy機十分適合對通信協(xié)議進行建模,并執(zhí)行一致性測試.下面給出Mealy機的定義:

使用一個五元組來表示M=(S,I,O,δ,λ),其中:M代表Mealy有限自動機的符號;S代表FSM中所有狀態(tài)的集合{s0,s1,s2,…,sn},s0代表初始狀態(tài);I代表FSM中所有輸入的集合{i1,i2,…,in},允許輸入為空,記作“—”;O代表FSM中所有輸出的集合{o1,o2,…,on},允許輸出為空,記作“—”;δ為狀態(tài)轉移函數(shù),如S×I→S’,表示狀態(tài)S在輸入I的情況下轉移到狀態(tài)S’;λ為輸出函數(shù),如S×I→O,表示狀態(tài)S在輸入I的情況下輸出結果O.

當有限狀態(tài)機處于狀態(tài)s時,若此時狀態(tài)s的輸入為i∈I,那么由狀態(tài)s進入的下一個狀態(tài)由δ(s,i)得到,同時得到輸出λ(s,i).圖1是一個FSM的狀態(tài)轉移圖,該FSM具有4個狀態(tài){s0,s1,s2,s3},兩種輸入{i1,i2},三種輸出{o1,o2,o3}.同時此圖也是一個有向圖,有向圖中的頂點和邊分別對應表示FSM中的各個狀態(tài)以及狀態(tài)間的轉移.

圖1 有限狀態(tài)機示意圖Fig.1 Schematic diagram of finite state machine

基于FSM模型的測試用例生成包括3個步驟:

1) 根據(jù)整個待測試的系統(tǒng)行為建立相關的FSM模型;

2) 根據(jù)某個測試意圖或者測試覆蓋準則遍歷FSM模型,獲得一組測試路徑;

3) 將路徑集合轉成有效的測試輸入和預期的輸出效果.

3 充電機測試序列生成

3.1 充電機FSM模型建立

在充電機與BMS間通信一致性測試的場景中,待測試的對象為充電機與BMS間的通信系統(tǒng),系統(tǒng)行為在充電的時序流程中具體體現(xiàn).因此,在構建表達充電機狀態(tài)的FSM之前,需要先根據(jù)充電的時序流程梳理出整個充電過程中BMS和充電機通信中的各種狀態(tài).

依據(jù)GB/T 27930中的充電時序流程,整個充電時序可以劃分為5個階段.這5個階段依次為握手啟動、握手辨識、充電參數(shù)配置、充電階段和充電結束階段.

此外,將錯誤報文歸為報錯階段.如要構建充電機的FSM模型,必將充電機在每個階段中的狀態(tài)提取出來,根據(jù)協(xié)議的內容表示出不同狀態(tài)之間轉換的輸入輸出.在圖2中,本文分別針對充電時序中的5個階段和報錯階段提取充電機狀態(tài)以及狀態(tài)間的轉化信息.最后,逐步構造完整的FSM圖,如圖3所示,圖中狀態(tài)之間轉換的邊用L表示.其中各個狀態(tài)(s0～s10)和各個狀態(tài)之間轉換的邊(L1～L42)的物理意義在表1和表2中進行了說明.

表1 FSM有向圖中的轉換邊說明

表2 FSM有向圖中的狀態(tài)說明

圖2 充電機與BMS交互狀態(tài)圖

圖3 完整充電機狀態(tài)FSM圖

3.2 基于UIO方法的測試子序列生成

在生成完整的充電機FSM圖的基礎上,利用UIO方法生成測試子序列.使用UIO方法可以實現(xiàn)對每個狀態(tài)的唯一標識.根據(jù)UIO序列可以判斷是否達到了某種狀態(tài),或者說UIO序列可以幫助判斷是否從一種狀態(tài)成功轉換到了另一種狀態(tài).

對于任何一個狀態(tài)si,構建其UIO序列的方法是:

1) 對所有的狀態(tài)以及狀態(tài)之間的輸入輸出建立映射關系;

2) 找出針對某一狀態(tài)所有長度為1的輸入輸出序列;

3) 若這些長度為1的序列是唯一的,則選擇一個唯一序列作為當前狀態(tài)的UIO序列;

4) 若這些長度為1的序列中沒有唯一的情況,則考慮序列長度加一的情況,執(zhí)行下一步;

5) 在長度為K的輸入輸出序列的基礎上求出長度為K+1的序列,判斷求出的序列是否唯一,直到找出一個唯一序列作為該狀態(tài)的UIO序列.

在得到每個狀態(tài)的UIO序列之后,則可以為每個狀態(tài)轉換(si,sj;L)求出它們所相關的測試子序列.(si,sj;L)的測試子序列可以表示為

e(si,sj,sl;L)={L,UIO(sj)}

其中:si代表開始狀態(tài);sj代表si經(jīng)過L轉移后的狀態(tài);sl代表經(jīng)歷過序列UIO(sj)之后的終止狀態(tài),同時也是測試子序列的終止狀態(tài).

在計算不同狀態(tài)之間的測試子序列時,需要考慮不同的路徑.即在求狀態(tài)si到狀態(tài)sj的測試子序列時,如果從si到狀態(tài)sj的路徑有n條,最后求出的測試子序列就會有n條.但是,得到的這些測試子序列在功能上會存在一些冗余.如果一個正常狀態(tài)轉移到自身的條件是在不超時的情況下,沒有輸入或輸入不正確,那么對這種狀態(tài)轉移的測試就會暗含在該狀態(tài)轉移到超時狀態(tài)當中.因此,可以利用這一特點消除測試子序列的冗余得到最終的測試子序列.

3.3 基于廣度優(yōu)先算法的引導序列生成

在生成全部測試子序列之后,便可以根據(jù)這些序列來生成測試用例集.但是需要考慮的問題是,測試子序列測試的是其起始狀態(tài)向其他狀態(tài)轉移的情況,而不關心如何到達起始的狀態(tài),因此,還需要為每一個狀態(tài)設置一個引導序列.測試子序列包括了所有的狀態(tài)轉換情況,要求引導序列能夠到達FSM中的每一個狀態(tài).和深度優(yōu)先相比,廣度優(yōu)先遍歷FSM更容易覆蓋到每一個狀態(tài),因此采用廣度優(yōu)先的方式生成引導序列.具體算法如下:

算法1:引導序列生成算法

輸入:有限狀態(tài)機Ms

輸出:任意狀態(tài)si對應的引導序列Gi

(1) 確定狀態(tài)機Ms的初始狀態(tài)s0;

(2) 從s0開始,對Ms進行廣度優(yōu)先遍歷;

(3) if(某個狀態(tài)si已經(jīng)被訪問) {

跳過狀態(tài)si;

繼續(xù)遍歷狀態(tài)si+1;

}

(4) 構造一棵無重復狀態(tài)的廣度優(yōu)先生成樹;

(5) 輸出從樹中根節(jié)點s0出發(fā)到達任意節(jié)點si的路徑作為引導序列Gi.

3.4 完整測試序列生成

根據(jù)前面的內容,可以得到全部的測試子序列和引導序列,將引導序列和測試子序列結合即得到完整的測試序列.具體的做法是,對于每一個測試子序列,在其前面加上起始狀態(tài)對應的引導序列即可.在得到完整的測試序列之前,可以發(fā)現(xiàn)邊與邊之間存在暗含關系,比如接收報文超時的邊其實暗含了不接受任何報文自旋的過程,因此可進一步消除冗余測試序列.根據(jù)每個測試序列生成測試用例時,需要對每一條邊的內容進行考慮,設計相應的測試用例,若其他測試用例已經(jīng)完成了針對這些邊的測試,就可以將這些邊作為前置條件.

3.5 測試序列覆蓋率討論

對于測試序列的覆蓋率,本文主要考慮了狀態(tài)覆蓋和遷移覆蓋.狀態(tài)覆蓋指的是最終生成的測試序列集合至少需要完全覆蓋一次有限狀態(tài)機中的所有狀態(tài).遷移覆蓋指的是最終生成的測試序列集合至少完全覆蓋一次有限狀態(tài)機中所有的輸入集合,也即是至少覆蓋一次狀態(tài)機中所有的邊.

由于通過UIO法生成測試子序列時生成的是每個狀態(tài)和其他狀態(tài)進行轉換時的測試子序列,所以最終包含所有測試子序列的測試序列一定滿足狀態(tài)覆蓋,即最終的測試序列一定包含了所有狀態(tài).

同時,將最終測試序列中所有的邊與FSM中的邊進行對比,可以發(fā)現(xiàn)測試序列覆蓋了FSM中的所有邊,因此最終生成的測試序列一定滿足遷移覆蓋.

和傳統(tǒng)的根據(jù)狀態(tài)覆蓋和遷移覆蓋生成測試序列的方法相比,通過UIO法生成的測試序列還可以檢測狀態(tài)與狀態(tài)之間轉換時可能出現(xiàn)的錯誤,且同時滿足狀態(tài)覆蓋和遷移覆蓋,是一種準確性較高的方法.

4 充電機測試用例設計

基于FSM和測試序列生成的測試用例,本質上是一組輸入輸出集合,但是由于充電通信協(xié)議中報文內容較長,在每一個測試用例中難以將所有的輸入輸出進行表達,因此本文選擇的方式是只對最后一組輸入輸出做具體的說明,最后一組之前的輸入輸出可以作為前置條件,但是前置條件必須要包含在已有的測試用例中.針對每個測試序列產(chǎn)生測試用例,設計如下算法:

1) 對任意測試序列Ti,如果其長度為1,則產(chǎn)生一條測試用例;

2) 如果其長度為n(n>1),則需判斷已有測試用例中是否有前面長度為n-1測試子序列的測試用例,如果有,則將該測試用例作為測試前置條件,針對最后一組邊設計測試用例.如果沒有,則針對前n-1條邊組成的序列生成測試用例.

該種算法是一種采用遞歸思想的算法,通過該算法生成測試用例的具體方法如下:

針對T1=G1,e3={L1,L4,L5}這個測試序列,首先判斷是否存在測試路徑為L1、L4的測試序列,可以發(fā)現(xiàn)沒有,因此,需要提前計算L1、L4的測試用例.要計算L1、L4的測試用例,首先判斷有沒有測試路徑為L1的測試用例,可以發(fā)現(xiàn)也沒有,因此,要首先計算路徑為L1的測試用例.在生成測試用例時,用例的編號是由測試序列T1-T23決定的,測試具體操作和預期結果分別指的是FSM圖中邊上代表的輸入輸出.

有了測試用例T1-1之后,便可以生成測試子路徑L1、L4的測試用例,具體測試用例如表3所列.

表3 測試用例

有了L1、L4這個測試子序列的測試用例之后,便可以生成針對測試序列T1={L1,L4,L5}的測試用例了,具體的測試用例內容見表3.

上面得到的測試用例便是根據(jù)測試序列T1=G1,e3={L1,L4,L5}得到的測試用例.

5 結論

現(xiàn)有的測試充電機和BMS之間通信一致性的方法大多數(shù)是根據(jù)專家經(jīng)驗產(chǎn)生測試用例集,這種方法過于依賴經(jīng)驗,沒有理論支撐,導致測試覆蓋性弱,測試結果沒有說服力,而且通信協(xié)議的內容迭代更新較快,傳統(tǒng)方法的復用能力也較弱.

本文根據(jù)GB/T 27930—2015協(xié)議,詳細分析充電機和BMS之間的通信過程,提出了一種基于FSM的充電機和BMS之間的通信一致性測試方法.該方法主要的創(chuàng)新和貢獻有以下幾點:

1) 使用FSM形式化描述充電機和BMS之間的充電過程,讓不同的讀者在理解27930協(xié)議時不會產(chǎn)生分歧,保證協(xié)議的不同實體之間的通信一致性.

2) 在FSM的基礎之上使用UIO方法來生成測試序列并得到最終的測試用例集,這種測試方法不僅有理論支撐而且復用能力強.

3) 根據(jù)測試序列生成測試用例時,采用相應算法可以讓每一個測試用例都有完整的輸入輸出,前置用例也被考慮在內.因此,本文所提的基于FSM的充電機和BMS通信一致性測試用例生成方法有著廣泛的應用前景.