基于布尔运算符替换算法的机载系统测试用例生成

基于布尔运算符替换算法的机载系统测试用例生成

嵌入式软件通常对可靠性的要求高于普通软件，因此需要对嵌入式软件进行严格测试，以提高产品的可靠性。DO-178B是国际公认的机载软件开发指南。通过人工构造测试用例时,需要分析每个条件对结果的影响,往往出现考虑不周,或设计冗余的问题,无法保证设计出来的测试用例既精简又能对需求进行充分的覆盖。本文针对目前软件测试过程中测试用例设计的特点,依据DO-178B的A级覆盖的标准———MC/DC准则,研究了一个布尔运算符替换算法,并实现了工具。在将需求用布尔表达式描述基础上,利用该工具能自动生成满足MC/DC准则要求的测试用例。1测试用例有效性分析MC/DC是ModifiedCondition/DeeisionCoverage的缩写,含义是修正条件/判定覆盖。条件表示不含有布尔操作符号的布尔表达式;判定表由条件和零或者多个布尔操作符号组成的布尔表达式。MC/DC准则主要用来测试飞行性软件的安全性审查。它具有多重条件覆盖的优点,同时只是线性增加测试用例的数量,可以得到理想的目标码覆盖率。该准则要求:(1)判定中的每个点的入口和出口至少被测试一次;(2)判定中每一个条件的每种可能的结果至少发生一次;(3)每一个条件都能单独地影响判定的结果,即在其他条件不变的情况下改变这个条件的值,使得判定结果改变。因此,在测试用例集中,必须针对每个条件出现一对测试用例来满足MC/DC覆盖要求。布尔表达式是由布尔算符(and、or、not)施于布尔变量或关系表达式而成。对于布尔表达式AandB和AorB,其完备测试用例对相同为邀(0,0),(0,1),(1,0),(1,1)妖。满足MC/DC准则要求的测试用例对集合却不同,如表1、表2所示。2测试系统的程序Chilenski指出:对于一个具有N个条件的布尔表达式,测试集合中至少包括N+1组元素。布尔运算符替换算法实现对一个布尔表达式求出至少N+1组的这些元素,设计条件独立的影响结果的最小测试用例集。该算法流程如图1所示。首先根据编译原理的布尔表达式文法构造操作符优先关系表。当输入布尔表达式后提取出布尔常量和操作符,根据优先关系表计算各操作符的优先级权值,按权值对各个操作符排序。按序生成每个操作符的真值表并将结果带入表达式,最终优先级最低的操作符生成初始真值表。初始真值表可能存在冗余的测试用例,故接下来利用树的广度优先遍历的思想对其做优化找到满足MC/DC准则的对应于每个布尔常量的测试用例对,最终求得MC/DC的最小测试用例集。现分四个步骤说明这个算法。2.1编码g的算法定义布尔表达式文法G如下:终结符是:or、and、not、(、)、const。其中const是布尔变量。该文法是算符优先文法为了构造终结符优先关系表,首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)。构造结果如下:FIRSTVT(NOT_EXP)=邀not,(,const妖LASTVT(NOT_EXP)=邀not,),const妖使用每个非终结符P的FIRSTVT(P)和LASTVT(P),根据构造优先表的算法,能够构造文法G的优先表如表3。表中的空白格表示相应终结符偶没有优先关系。2.2操作符优先关系的处理输入布尔表达式后,将操作符与布尔常量分离。每个操作符优先级权值初始化为1。设b1与b2为左右相邻两个操作符,初始化后P(b1)=P(b2)=1,当前计算b2的优先级权值。根据优先关系表,按以上函数规则计算各操作符优先级权值。然后按权值从大到小的顺序,利用快速排序算法对所有操作符排序。因括号匹配原则,左右括号的优先级权值一致。排序后只将“and”、“or”和“not”的优先级权值取出存入优先级队列。例如输入的布尔表达式是(AandB)and(CorD)。操作符与布尔常量分离后,操作符按从左到右的顺序放入数组b中,即b=″(″,b=″and″,b=″)″,b=″and″,b=″(″,b=″or″,b=″)″。根据优先关系表及上述函数规则。计算出各操作符权值如下:P(b)=P(b)=2;P(b)=P(b)=P(b)=P(b)=1;P(b)=0;排序后按先进先出入优先级队列的是:b、b、b。2.3基于c/dc的布尔运算符替换规则由表1、表2可看出,当遇到操作符“and”,只需考虑测试用例对邀(1,1)、(1,0)、(0,1)妖;当遇到操作符“or”,只需考虑测试用例对邀(0,0)、(1,0)、(0,1)妖就可满足MC/DC覆盖要求。基于上述原因,定义布尔运算符替换规则表(表4)。将布尔操作符从优先级队列依次出队,根据替换规则表,得到每个操作符的对应真值表放入链表中临时保存。真值表中一、二列为该操作符在布尔表达式中的左右两个布尔常量,第三列为逻辑表达式计算结果Ri。当同一优先级的布尔操作符替换完毕后,将Ri代回表达式以便进行下一优先级的布尔操作符替换。最终由优先级最低的操作符生成初始真值表。以布尔表达式(AandB)and(CorD)为例,当优先级队列中第一个元素b出队,根据布尔运算符替换规则表得到真值表如表5所示。b出队得到真值表(表6)后,将R1和R2回代,表达式变为R1andR2。继续作出队操作直到队空,由优先级最小的操作符生成初始真值表(表7)。2.4用树优化检测初始真值表可能存在冗余的测试用例,利用树的广度优先遍历的思想对其做优化,以找到满足MC/DC准则的对应于每个布尔常量的测试用例对。把初始真值表的每一行作为树的一个节点,第一行为根节点,建立一颗树。为了方便查找每个布尔常量独立影响表达式结果的测试用例对,建树过程保证父子节点的真假值不同。利用树的广度优先遍历,按顺序将父子节点做按位异或操作,当且仅当按位异或结果含有一个“1”时,根据“1”的位置标记该父子对的独立影响布尔常量。当所有布尔变量都被标记,即每个布尔变量都找到了独立影响对,树的遍历完成。取出标记过的节点,生成优化真值表。继续上面的例子,把初始真值表的每一行作为树的一个节点Ni,建立了如图2所示的树。对树进行广度优先遍历,比较每一对父子节点后,找到了布尔变量A~D的独立影响对如图3所示。最后取出作过标记的节点,生成优化真值表。3设置测试用例MC/DC测试用例生成工具以布尔运算符替换算法为核心,辅助设计覆盖全面而又简化的测试用例。该工具输入为一个布尔表达式,输出为符合MC/DC准则要求的最小测试用例集。以某卫星导航系统的白盒测试为实验案例,为了达到DO-178B软件验证的目标,对机载软件的测试通常分为以下几步:基于需求设计测试用例;结合源代码运行测试用例,分析测试结果;在宿主机上进行MC/DC结构覆盖测试,判断软件是否实现了需求描述的功能。首先利用MC/DC测试用例生成工具辅助生成测试用例。根据DO-178B中需求覆盖要求,每一条需求要有对应的测试用例。例如下面这条需求“WheninFLSmodeandlabel271indicatesSelectedModeStatus(bit26)isModeFailed(0)orlabel270hasnotbeenreceivedafter10secondshaveelapsedfrompowerup.label177shallsetbetransmittedwithSSM=FW.”从该需求中抽象出布尔表达式[FLSmode]and([bit26oflabel271=0]or([label270notbeenreceived]and[10shaveelapsedfrompowerup]))和预期结果:setlabel177betransmittedwithSSM=FW作为MC/DC测试用例生成工具输入,运行后根据优化真值表,可设计5个符合MC/DC准则的测试用例如图4所示。第二步结合源代码编写测试驱动,运行测试用例。比较期望结果和预期结果是否一致,若出现“Fail“,则说明需求与代码不一致,在分析代码后写出问题报