面向充电机通信协议一致性测试的用例自动生成方法

何雪枫, 贾俊国, 李旭玲

(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通信一致性测试用例生成方法有着广泛的应用前景.