一种列控系统安全关键软件测试用例的实例化方法

刘思琪，张亚东，杨武东，童 音，饶 畅

(西南交通大学 信息科学与技术学院，成都 611756)

1 引 言

列车运行控制系统保证列车安全、高效的运行，是现代铁路信号系统中的关键设备[1].列控系统有许多基于软件的安全相关功能，软件缺陷可能导致安全功能失效，造成严重的行车事故.因此，为提高列控系统的安全性和可靠性，铁路信号系统安全关键软件的测试尤为重要[2].

基于模型的软件测试方法(Model-based Software Testing)采用模型描述软件需求，以测试覆盖准则为依据，应用图论等算法生成测试用例，并对待测系统进行测试，测试效率与自动化程度高[3]，在铁路信号安全关键软件测试中得到了广泛的研究和应用.软件测试中常用的模型有确定性有限状态机(Deterministic Finite State Machine，DFSM)和UML状态图等模型.对于软件测试方法中的不同模型，已有不少的测试理论与测试用例生成方法被提出.文献[4-6]提出了基于模型生成测试路径方法，但实际应用时仍需从测试路径自动生成可执行测试用例.文献[7]中基于模型测试用例自动生成方法，对于不同待测系统仍需一定的人工参与才能自动生成测试输入.文献[8]精确阐述了适用于不同场景下基于规格说明的逻辑覆盖测试准则，应用准则生成的测试用例常是抽象的，实例化后得到实际测试输入.文献[9]采用输入域建模提取有限状态机测试场景的测试输入，但面对更复杂的有限状态机迁移逻辑时，无法直接得到可执行测试用例.列控系统安全关键软件功能逻辑复杂、输入空间庞大，基于模型的测试用例生成的结果主要为抽象的测试路径，为自动生成直接用于列控系统安全关键软件的测试执行，仍需要可执行的测试用例的生成方法.

本文选用DFSM描述系统行为，结合逻辑覆盖与输入空间划分方法，对模型的测试路径上各状态间迁移条件生成满足逻辑覆盖准则的测试用例，并采用输入空间划分选取抽象的测试用例的实际测试输入，自动生成待测系统可执行的测试用例.最后，以CTCS-2级车载设备手动等级转换的安全功能为例，展示该方法自动生成测试用例的过程.

2 基于DFSM模型的测试方法

DFSM能够描述软件在生命周期中的控制行为，表现为软件所经历的状态序列及引起状态迁移的事件或条件，具有表现直观、易于理解的优点，在基于模型的测试方法中得到了广泛应用.DFSM由状态与状态间迁移构成，状态描述了当前等待迁移执行的系统状况，迁移是在条件满足或事件发生时使DFSM从一个状态转至另一状态的动作，通常代表单个或多个变量的值的变化[8].DFSM可用一个五元组(∑,S,s0,δ,F)表示[10]，其中，

·∑ 表示有限的、非空的输入字符集；

·S表示有限的、非空的状态集；

·s0∈S表示一个初始状态；

·δ:S×∑→S表示状态迁移函数；

·F⊆S表示终止状态集合.

基于DFSM的软件测试用例自动生成方法主要分为DFSM生成测试路径、测试路径实例化为测试用例两个阶段组成[10].第一阶段为根据软件结构、规格说明等建立软件功能逻辑的DFSM模型，并生成满足图覆盖等准则的测试路径，测试路径即抽象测试用例，记录了图覆盖准则下从s0状态到f∈F状态的所有迁移{(s0,si),…,(sj,sk),…,(sn,f)}.第二阶段为实例化测试路径为可执行的测试用例.

3 测试用例生成基础

3.1 逻辑覆盖

逻辑覆盖准则通过分析谓词与子句逻辑关系，产生覆盖某些子句、谓词的逻辑取值的测试用例[11]，常应用在基于模型的测试.DFSM的状态迁移函数上通常定义使得迁移发生的特定变量的取值和引发迁移发生的变量值变化的触发事件[8], 常表现为迁移条件逻辑表达式，在实际中可通过分析待测系统规格说明得到.由于逻辑覆盖没有标准的术语与符号，应用逻辑覆盖时通常将逻辑表达式形式化为谓词[8].谓词，是计算结果为布尔值的子句或者复合谓词，其结构由逻辑运算符(非)、∧(与)、∨(或)、→(蕴含)、⊕(异或)和↔(等价)等构成[8]，其中子句是不含任何逻辑运算符的谓词[8]，有布尔变量和关系表达式两种常见形式[12]，复合谓词则是由若干个子句或其补和二元布尔运算符{∧,∨}构成[13].子句形式之一的关系表达式是形如EopF的表达式，其中E和F均为由算数表达式，关系运算符op∈{≤,≥,<,>,=,≠}[13].仅由布尔变量、布尔运算符和括号构成的谓词称为布尔表达式[13]，通过抽象语法树提取布尔变量及关系表达式为叶节点，布尔运算符{,∧,∨}为内部节点，得到其树形结构，用于自动化生成测试用例.在DFSM模型中，状态迁移条件表现为逻辑表达式，并已形式化为谓词，其中{,∧,∨}是软件功能的DFSM模型常用的3种逻辑运算，本文针对这3种逻辑运算符的DFSM模型应用逻辑覆盖准则生成测试用例.常见的逻辑覆盖准则有谓词覆盖、子句覆盖和组合覆盖三种[8].

1)谓词覆盖(PC)：对于谓词集的每个谓词，测试需求是谓词取得真值，谓词取得假值.

2)子句覆盖(CC)：对于谓词的每个子句，测试需求是子句取得真值，子句取得假值.

3)组合覆盖(CoC)：对于谓词集的每个谓词，测试需求是谓词中子句的所有逻辑值组合.

当谓词中有n个独立的子句，共有2n种可能的逻辑值组合.以(a=b)∧C为例，该谓词包含2个独立子句，有4种可能的逻辑值组合，以T代表True，F代表False，结果如表1.其中，满足谓词覆盖的测试集有T1,2={1,2}、T1,3={1,3}、T1,4={1,4}，满足子句覆盖的有T1,4={1,4}、T2,3={2,3}，满足组合覆盖的有T1,2,3,4={1,2,3,4}.

表1 谓词(a=b)∧C逻辑值组合与覆盖结果表Table 1 Truth table of (a=b)∧C and results of coverage criteria

3.2 输入空间划分

输入空间划分的过程称为输入域建模，它根据待测系统的接口变量定义了输入域，如图1中输入域D，再从规格说明中提取出用以划分输入域的特性C，将输入域D划分为包含同等作用值的、两两分离的b1、b2和b3三个块，并从块中选出有代表性的取值(如图1中黑点)进行测试[8].

图1 输入域D划分示意图Fig.1 Partition of input domain D

输入域建模的方法分为基于接口的方法和基于功能的方法.基于接口的方法是单独处理每个被测函数的变量xi，识别的特性仅限于一个单独的变量，易于对xi进行划分块取值.基于功能的方法的输入域模型包含了一些功能语义或者专业知识，其特性通过分析被测系统的一个行为或功能来开发，产生的测试用例比基于接口的方法可能更接近测试目标，但识别特性经常不能够匹配待测系统接口的变量，难以生成可执行用例[8].软件需求规格描述了软件的各项需求，各项功能的具体含义等内容，对基于规格说明的DFSM模型进行输入域建模时，被测函数是状态间的迁移条件，函数变量是迁移条件中的变量.迁移条件包含了待测系统的功能语义，从迁移条件开发出的特性既能从功能上划分输入域，又能与迁移条件中的变量匹配，提供了基于功能的方法识别特性后自动化选取变量取值的可能.

3.3 逻辑覆盖与输入空间划分结合方法

根据逻辑覆盖准则，DFSM的迁移条件生成的逻辑测试集是子句的逻辑值组合，常是抽象的测试用例.为使其与接口变量匹配，采用输入空间划分自动生成满足逻辑值组合的接口变量测试输入，并组成可执行的测试用例.生成测试用例的过程见图2，从测试路径生成测试用例可分为以下3步：

图2 测试用例生成过程图Fig.2 Process of test cases generation

1)生成逻辑测试集.识别迁移条件的逻辑表达式结构，生成满足特定覆盖准则的逻辑测试集.

2)生成变量取值集.通过变量定义与迁移条件提取特性，采用基于功能的输入域建模方法对待测系统建模，并计算出接口变量取值集.

3)生成测试用例.结合逻辑测试集与变量取值集，得出与逻辑测试集中各测试项子句逻辑值匹配的接口变量测试输入.若对应一次测试的变量输入组合有多种，则采用全排列方法，生成所有可能组合的可执行测试输入，最终与其他测试项的测试输入组合成满足特定逻辑覆盖的测试用例.

4 基于输入域和逻辑覆盖的测试用例生成

4.1 生成逻辑测试集

基于DFSM模型的测试路径是一组迁移序列，其中各迁移条件的逻辑表达式，通常被形式化为谓词形式.逻辑覆盖准则中的谓词覆盖准则的测试需求是每个谓词集合中的谓词需取得真值和假值[8].下面以该准则为例说明测试用例生成过程.表1中谓词(a=b)∧C，T1,2={((a=b)=true,C=true),((a=b)=true,C=false)} 这两项的测试集满足了谓词覆盖准则.在实际中，为实现自动生成满足逻辑覆盖准则的逻辑值组合，首先需要构建逻辑表达式的抽象语法树.为降低构建语法树的难度，选用布尔变量分别替换谓词中关系表达式，转换其为布尔表达式，再通过识别布尔运算符构建语法树.谓词(a=b)∧C，由关系表达式(a=b)和布尔变量C这2个子句组成，将其中(a=b)用布尔变量D替换，谓词将转换为布尔表达式D∧C，再构建其语法树并生成真值表，再从中取出满足谓词覆盖准则的逻辑值组合构成了逻辑测试集(logical tests).生成逻辑测试集的算法1如下：

算法1.generate logical tests

Input:logical expression

Output: logical tests

1.extractclausesfromlogicalexpression

2.forclauseinclausesdo

3.ifclauseis a relation expression

4.thenrenameclausewithbyname

5.endif

6.endfor

7.transformlogicalexpressiontobooleanexpression

8.generateabstractsyntaxtree

9.generatetruthtable

10.select specificlogicaltestitems and store inlogicaltests

4.2 生成变量取值集

基于功能的输入域建模生成变量取值集时，状态间的迁移条件逻辑表达式(logic expression)视为待测函数，迁移条件中变量为接口变量，通过从DFSM变量的定义与迁移条件中相应子句提取划分特性，将变量输入域划分为块(blocks).划分块是变量可能值的集合，为了从集合自动选出变量值，采用取值策略(如有效值、无效值和边界值等)选取，综合后将得到子句中变量的取值集合(variable values).其中，边界值策略认为在边界或边界附近是程序员进行软件设计和开发时常出错的地方[8]，需要进行测试.生成变量取值集的算法如算法2所示.

算法2.generate input domain values

Input: logic expression

Output: set of variable values

1.extractclausesfromlogicexpression

3. identifycharacteristicsfromclauseandvariable′sdefinition

4. createblocksforcharacteristics

5.forblockinblocks

6. selectvaluesfromblockunder strategy

7. addvaluesintovariablevalues

8.endfor

9. addvariablevaluesintosetofvariablevalues

10.end for

式中:x=(xS1,yS1,xS2,yS2,…,xSN,ySN)表示2N维的决策变量,y表示2维的目标向量;f1(x),f2(x)分别是节点安全连通度目标函数和节点网络覆盖率目标函数;∀i∈[1,N],∃j∈[1,N],i≠j,满足d(Si,Sj)≤Rc是节点的全连通约束,其中d(Si,Sj)表示节点Si,Sj之间的欧氏距离;为节点移动能耗约束,为节点优化后与节点最初位置之间的距离,dth是节点允许移动的最大值。

4.3 生成测试用例

逻辑覆盖准则考察的是逻辑运算符，生成的逻辑测试集中一次测试的逻辑值组合是谓词中各子句的测试值，但这些测试值常常是抽象的，未匹配待测系统接口变量，要与输入空间划分的结果结合转为实际变量的测试输入.两者结合算法见算法3.

算法首先对逻辑测试集中每一条测试项(logical test)中各元素(element)，应计算出满足当前元素逻辑值的变量取值集合(expected values).当计算出当前输入项对应的所有变量取值集合之后，将其视为整体，采用全排列方法或其他组合办法，以各取值集合为单个的排列变量，集合中的值视作变量的取值，对变量进行组合，生成多种测试输入组合.然后，对逻辑测试集中剩余测试项重复上述过程，得到各测试项的测试输入集合(set of test input).最后，组合各测试项的测试输入集合，得到满足逻辑覆盖准则的、可执行的测试用例(test cases).

算法3.generate executable test cases

Input: logical tests, set of variable values, logic expression

Output: test cases

1.forlogicaltestinlogicaltestsdo

2.forelementinlogicaltestdo

3. get relativeclausefromlogicexpression

4. getvariablefromclause

5. getvariablevaluesfromsetofvariablevalues

6.forvariablevalueinvariablevaluesdo

7. getresultby substituting thevariablevaluetoclause

8.iftheresultmatches theelement′svalue

9.thenrecord the currentvariablevaluetoexpectedvalues

10.endif

11.endfor

12.endfor

13. combine allexpectedvaluesand store insetoftestinput

14.endfor

15.combine allsetoftestinputand generatetestcases

5 案例研究

列控系统领域的DFSM模型图的状态用圆圈表示，终止状态用双圈表示，状态间迁移用带箭头的线表示.系统进入初始状态后开始工作，并根据变量的变化迁移至目标状态.状态间的迁移条件通常反应了接口变量之间的逻辑关系，主要由关系表达式与布尔表达式组成.本节以CTCS-2车载设备等级转换中手动切换功能为例，说明从DFSM模型生成测试用例的具体过程.

5.1 等级转换功能有限状态机模型

等级转换发生在CTCS-2(简称C2)区段与CTCS-0(简称C0)区段的边界.当C0级下车载设备不能自动切换等级时，若条件允许，司机可进行手动切换等级至C2级[14].该功能的DFSM模型如图3所示.

图3 CTCS-0级手动切换CTCS-2级的DFSM模型Fig.3 DFSM of CTCS-0/CTCS-2 manual level transition function

如图3，车载设备进入Start状态后初始化为C0等级状态，检测到司机手动选择C2等级后，转入C2手动切换状态；若列车正在输出制动且当前等级为C0级，则C2手动状态转回C0状态；若列车未输出制动、列车速度满足要求、当前状态等级为C0且司机手动选择C2等级四个条件同时满足，C2手动状态将转至C2等级状态.

从DFSM得出一条测试路径P，迁移分别是{(Start,C0),(C0,C2-ManuSwitch),(C2-ManuSwitch,C0),(C0,C2-ManuSwitch),(C2-ManuSwitch,C2-State),(C2-State,End)}.其中(C2-ManuSwitch,C2-State)的迁移条件的子句、变量、子句含义见表2.

表2 样例迁移条件表达式元素表Table 2 Elements in sample transition expression

5.2 测试用例生成

本小节以 C2-ManuSwitch转C2-State的迁移条件为例，介绍生成测试用例的具体过程.

1)生成逻辑测试集.通过解析迁移条件表达式，获得所有子句并用布尔变量替换谓词中关系表达式，将谓词转为布尔表达式，建立迁移条件的抽象语法树后求出条件表达式的所有的逻辑值组合，从中选出满足谓词覆盖准则的逻辑值组合构成了逻辑测试集.样例迁移条件包含四个子句，其中关系表达式Speed<250.0替换为布尔变量Speed-250.0 ，迁移条件变为布尔表达式，并构建抽象语法树，得到子句的十六种逻辑值组合.

其中上述4个子句{LKJBrake, Speed<250.0, CurLevelCTCS0, DrvOperCTCS2}逻辑值组合为{T,T,T,T}时，表达式值为F，而四个子句逻辑值为{F,T,T,T}时，表达式值为T.由谓词覆盖准则定义可知，{T,T,T,T}与{F,T,T,T}这两条测试项满足了谓词分别为假与真的谓词覆盖测试需求，因此，从由这两项测试项组成的逻辑测试集满足了谓词覆盖准则.

2)初始化变量取值集合.基于功能的输入域建模方法通过迁移条件中功能信息提取特性，以float型变量Speed为例，在关系表达式Speed<250.0与变量Speed的定义中提取出选取"Speed大于0且小于250km/h"特性，划分输入空间为Speed大于0且小于250km/h、 大于等于250km/h两个块，并选取有效取值范围中间值、以5为步长选取边界的附近值和边界值为测试值，符合了有效值、无效值、边界值的取值策略，变量取值集合见表3，而迁移条件中LKJBrake等为布尔型变量，取值集包括其所有可能值.

表3 样例表达式各变量取值集Table 3 Set of variables values in sample expression

3)生成测试用例.以测试项中{LKJBrake=F,Speed<250.0=T,CurLevelCTCS0=T,DrvOperCTCS2=T}为例，在子句中依次代入对应变量值，通过计算结果并判断其是否与子句逻辑值一致，求出变量取值集中所有满足子句逻辑值的取值，{F, T, T, T}测试项的变量输入子集如表4.以子句Speed<250.0为例，测试项要求该子句取值为T，因此需要求出Speed变量取值集合中小于250.0的值.

表4 样例输入项与变量输入子集Table 4 Sample test input and subset of variables inputs

由于4个变量(LKJBrake, Speed, CurLevelCTCS0, DrvOperCTCS2)的取值可能组合不唯一，本次采用全排列生成4条可执行的测试输入，分别为：

(F,0.0,T,T)、(F,5.0,T,T)、(F,125.0,T,T)、(F,245.0,T,T).

对于谓词覆盖测试集中的另一条测试项{T, T, T, T}，再次进行上述过程，也可得到生成4条测试输入，分别为：

(T,0.0,T,T)、(T,5.0,T,T)、(T,125.0,T,T)、(T,245.0,T,T).

谓词覆盖准则需对两种逻辑值组合进行测试，对于上述两项测试项有多种可能测试输入时，为使每种输入至少执行一次，需要至少四个满足谓词覆盖准则的可执行测试用例，见表5.以其中可执行测试用例{(F,0.0,T,T),(T,0.0,T,T)}为例，该用例测试了速度为0、当前等级为CTCS-0且司机手动选择了CTCS-2时，列车输出制动与未输出制动两种等级转换的情况.路径P中各迁移条件的测试用例见表5.

表5 路径P各迁移条件测试用例表Table 5 Test cases for transitions in path P

由此可见，结合输入空间的各种输入条件所生成的测试用例覆盖了更多的测试情况与实际的临界条件，可测出软件边界情况存在的软件缺陷，实现了在各种输入场景下对铁路相关软件系统的测试，提高了软件的可靠安全性.

6 结 论

本文针对基于DFSM的软件测试方法中测试路径生成测试用例的过程，结合输入空间划分和逻辑覆盖准则，提出了含连续型变量的迁移条件自动生成测试用例方法.以CTCS-2级车载设备人工等级转换的安全功能为例，对其DFSM模型测试路径生成了多种测试情况下的测试用例，减少了软件测试中测试用例配置的工作量与测试值选取的盲目性.本文提出的方法已经在CTCS-2级车载设备软件测试中得到应用，实践表明本方法具备良好的可操作性，能产生可执行测试用例.今后，在输入空间的划分及如何取值和逻辑表达式特殊结构方面将做进一步研究，提高方法的适用度.