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

何雪楓, 賈俊國, 李旭玲

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

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

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

1 相關工作

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

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

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

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

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

2 有限狀態機模型簡介

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

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

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

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

圖1 有限狀態機示意圖Fig.1 Schematic diagram of finite state machine

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

1) 根據整個待測試的系統行為建立相關的FSM模型;

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

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

3 充電機測試序列生成

3.1 充電機FSM模型建立

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

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

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

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

表2 FSM有向圖中的狀態說明

圖2 充電機與BMS交互狀態圖

圖3 完整充電機狀態FSM圖

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

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

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

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

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

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

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

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

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

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

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

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

3.3 基于廣度優先算法的引導序列生成

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

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

輸入:有限狀態機Ms

輸出:任意狀態si對應的引導序列Gi

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

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

(3) if(某個狀態si已經被訪問) {

跳過狀態si;

繼續遍歷狀態si+1;

}

(4) 構造一棵無重復狀態的廣度優先生成樹;

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

3.4 完整測試序列生成

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

3.5 測試序列覆蓋率討論

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

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

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

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

4 充電機測試用例設計

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

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

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

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

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

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

表3 測試用例

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

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

5 結論

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

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

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

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

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