石磊++翁鹤

摘要：基于DD图理论能够获取覆盖整个路径的分支测试路径集合，但缺少精简无约束边集合的方法，分支测试用例选取复杂，工程应用更少。在DD图提炼无约束边集合的基础上，对程序路径树进行研究，提出通过循环计算路径树未被选中路径中包含的未被覆盖无约束边的个数，实现最优化分支覆盖测试路径集选择方法，满足基于DO-178B和GJB/Z 141军用软件语句、分支和MC/DC测试覆盖指标要求。实际工程应用结果表明，该方法实现了优化测试用例，满足了测试充分性要求。

关键词：DD图；无约束边；路径树；分支覆盖测试

DOIDOI：10.11907/rjdk.171499

中图分类号：TP319文献标识码：A文章编号：16727800（2017）010015405

0引言

随着航空武器装备系统复杂性提高，软件所占比例也越来越大[1]，基于DO178B[2]的软件测试成为保障型号软件质量的优选，满足程序语句、分支和MC/DC测试覆盖指标要求。在工程活动中由于缺乏完备、高效的分支覆盖测试技术，致使测试耗费和测试效力之间很难达到平衡[3]。鉴于航空武器装备系统软件高可靠性、高安全性和高健壮性需求，应对程序分支进行充分性验证，以确保软件产品质量。分支覆盖率是检验软件测试充分性的重要指标之一，应达到100%覆盖的指标要求[4]。

为了对程序的分支进行充分性验证，需要研究测试路径生成、测试输入数据生成以及程序切片[5]等技术，达到充分性验证目标的关键是通过DD图提炼无约束边集合，以获取覆盖整个路径的测试路径集合[6]。文献[7]通过选用十字链表结构存储程序的DD图求解无约束边，文献[8]通过改进的FindExactUE算法求解无约束边，文献[9]通过基于关键分支寻找算法求解无约束边，运用不同方法能够获取无约束边集合，但缺少精简无约束边集合的方法，工程应用更少。

本文通过引入树的理论，结合DD图提炼无约束边方法，通过循环计算路径树未被选中路径中包含未被覆盖的无约束边的个数，以最优分支测试路径集达到最充分分支覆盖目标。实验证明该方法切实可行，工程应用较好。

1基本原理与方法

1.1无约束边集

DD图是一种决策到决策的有向图，也是获取程序无约束边集合的理论基础。

定义1DD图：G=（V，E）有两个区分的边e0和ek（惟一进入的边和惟一离开的边），e0可以到达E的任何一个边，E的任何一个边都可以到达ek，对任何n∈V，n≠H（e0），n≠T（ek），indegree（n）+outdegree（n）>2，indegree（H（e0））=0，outdegree（T（e0））=l，indegree（H（ek））=l，outdegree（T（ek））=0。

以某型产品嵌入式软件为例，根据“角通道滤波”函数jkt的程序流程，可将程序流程图转换为DD图，如图1所示。

定义2主宰关系：设G=（V，E）是一个DD图，e0和ek分别是G的惟一进入的边和惟一离开的边。边ei主宰边ej，当且仅当从e0到ej的任一条路径都通过ei。

通过主宰关系，可把DD图G转换为树，该树的节点是DD图的边，树根是e0，称为主宰树DT（G），图2所示为jkt主宰树。

定义3蕴涵关系：设G=（V，E）是一个DD图，e0和ek分别是G的惟一进入的边和惟一离开的边。边ei蕴涵边ej，当且仅当从ej到ek的任何一条路径都通过ei。

通过蕴涵关系，可以把DD图G转换为树，该树的节点是DD图的边，树根是ek，称为蕴涵树IT（G），图3为jkt蕴涵树。

定义4无约束边：如果一个边eu不主宰其它的节点也不被其它节点所蕴涵，则eu称为无约束边。

根据定义，可获得程序的DD图、主宰树DT（G）和蕴涵树IT（G），从而提取程序的无约束边集合UE（G）=DT（G）∩IT（G）。

jkt的无约束边集合为：

UE（G）={e4、e5、e6、e7、e8、e9、e11、e12、e13、e14、e15、e16、e17}∩{e1、e2、e3、e4、e5、e6、e8、e9、e11、e12、e14、e15、e16}={e4、e5、e6、e8、e9、e11、e12、e14、e15、e16}，总共10个叶子节点。

按理论，覆盖程序无约束边集合就能覆盖整个程序路径，能够满足型號软件测试要求，但在工程应用中，不能达到分支覆盖测试路径集最优解目标，难以应用。

1.2程序路径树

为求解工程应用中分支覆盖测试路径集的最优解，需要引入树的理论。

定义5树：是n（n>=0）个结点的有限集，在任意一棵非空树中：①有且仅有一个特定的称为根的节点；②当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1，T2，…，Tm，其中每一个集合本身又是一棵树，并且称为根的子树。

定义6二叉树：是每个结点至多只有二棵子树（即二叉树中不存在度大于2的节点），并且二叉树的子树有左右之分，其次序不能任意颠倒。

通过DD图能够获取覆盖整个程序的无约束边集，但程序流程直观性差，测试用例集选取复杂，需要利用转换规则将DD图转换为树图。DD图转换为树图的方法包括顺序语句、判定语句和循环语句的转换规则。

（1） 顺序语句。顺序执行的两条或者两条以上语句的结点，则合并为一个结点。

（2） 分支语句。分支语句一般包括原子谓词、与谓词、或谓词、组合谓词和case分支语句，转换规则如图4所示。

（3） 循环语句。循环语句一般包括while、for和dountil循环语句，转换规则如图5所示。

依据树的理论，通过DD图转换树图的方法能够将DD图转换为路径树，其以二叉树的形式表示，当遍历二叉树叶子节点到二叉树根节点的一条路径时，即生成与该路径相对应的一组测试用例，如图6所示。例如路径1={e1→e2→e3→e4→e7→e8→e10→e11→e13→e15→e17}表示为一个测试用例。从图6可以看出，e8和e9节点下路径集在e6和e7节点下是相同的（采用示意图表示），路径图使得程序流程更加清晰，测试用例选取更加便捷，表示方法更适合工程应用。endprint

因此，通过程序路径树能够快速、准确、完整计算出100%覆盖程序分支路径的测试用例集，jkt函数所需的覆盖分支测试用例集数为26个。

1.3最优解方法

根据定义1，覆盖所有无约束边的路径集也覆盖了所有路径，而在满足覆盖所有分支路径边的集合中，无约束边是最少的。据此可推断，在选取分支覆盖测试路径时，使每一条从e0到ek的分支测试路径尽可能充分地覆盖无约束边集合UE（G）中的所有节点，就能达到精简分支覆盖测试路径集的目标，实现最优解求解。因此，可通过循环计算程序路径树未被选中路径中包含未被覆盖的无约束边的个数，选择最佳测试路径，直到无约束边全部覆盖。最优解求解流程如图7所示。

以jkt函数为例，最优解求解过程如下：

（1）独立路径总数。根据路径树可以获取jkt函数100%覆盖程序分支路径的测试用例集26个，如表1所示。

（2）第1次筛选。执行第1次筛选，表1中的路径1={e1→e2→e3→e4→e7→e8→e10→e11→e13→e15→e17}包含的无约束边最多有4个，分别是e4、e8、e11和e15，未被覆盖的无约束边集合更新为UE（G）={e5、e6、e9、e12、e14、e16}。第一次筛选后，UE（G）非空，更新独立路径总数，如表2所示。

（3）第2次筛选。执行第2次筛选，表2中的路径16={e1→e2→e3→e5→e7→e9→e10→e12→e13→e16→e17}包含的无约束边最多有4个，分别是e5、e9、e12和e16，所以被选中，未被覆盖的无约束边集合更新为UE（G）={e6、e14}。第2次筛选后，UE（G）非空，更新独立路径总数，如表3所示。

（4）第3次筛选。执行第3次筛选，表3中的路径17={e1→e2→e6→e8→e10→e11→e13→e15→e17}包含的无约束边最多有1个e6，所以被选中，未被覆盖的无约束边集合更新为UE（G）={e14}。第3次筛选后，UE（G）非空，更新独立路径总数如表4所示。

（5） 第四次筛选。执行第4次筛选，表4中的路径25={e1→e14→e15→e17}包含的无约束边最多有1个，是e14，所以被选中，则未被覆盖的无约束边集合更新为UE（G）={空}。第4次筛选后，UE（G）为空，求解结束。

经过求解，有4条分支测试路径被选中，分别是：

路径1={e1→e2→e3→e4→e7→e8→e10→e11→e13→e15→e17}

路径16={e1→e2→e3→e5→e7→e9→e10→e12→e13→e16→e17}

路径17={e1→e2→e6→e8→e10→e11→e13→e15→e17}

路径25={e1→e14→e15→e17}

因此，在执行分支覆盖测试时，只需从26个分支路径的测试用例集中选择路径1、路径16、路径17和路径25这4条路径，即可满足DO178B和GJB/Z 141对分支覆盖测试100%的指标要求，实现最优分支测试路径集达到最充分分支覆盖目标。

2工程应用

以某型产品嵌入式软件为例，对最优化分支覆盖测试路径集的研究进行工程化应用，以验证应用效果。

2.1重要度评价

由于型号嵌入式软件的大量使用，软件所要完成的功能日益复杂，导致嵌入式软件复杂度也呈正比上升。在实际工程应用中首先要对程序进行质量度量分析，以确定函数的测试优先级，对关键/重要函数进行充分性测试，以保证软件功能的正确性。一般利用McCabe质量度量模型[7]获取每个函数的质量度量数据，对于圈复杂度V（G）≥10的程序按照由大到小原则进行测试优先级排序，以确定测试顺序。

利用McCabe工具对某型产品嵌入式软件进行质量度量分析，共分析342个函数，其中圈复杂度V（G）≥10的函数有76个，按由大到小原则获取函数测试优先级，函数V（G）相同时则按照McCabe模型EV（G）指标由大到小排序，最终形成测试顺序如表5所示。

通过测试顺序排序，优先保障对复杂度高的函数进行测试验证，确保测试充分性要求，提升测试工作效率。

2.2最优化求解

按照本文提出的分支覆盖测试路径集最优解求解过程，对经过测试排序的76个函数进行最优解求解，获取76个函数的最优化分支覆盖测试路径集，过程如下：①计算每个函数的DD图、主宰树和蕴涵树，获取无约束边集合；②利用转换规则，将DD图转换为树图，获取程序路径树，计算独立路径总数；③利用求解流程，通过循环计算路径树未被选中路径中包含未被覆盖的无约束边个数，获取最优解。

通过最优解求解，能够获得满足基于DO178B和GJB/Z 141军用软件语句、分支和MC/DC测试覆盖指标要求的最优解测试用例。最优解测试路径集结果如表6所示。

2.3应用验证

为验证方法的有效性，对76个函数进行重新测试验证，未采用最优解求解的测试路径集如表7所示。

对测试结果统计分析可知，分支覆盖测试用例数均有不同程度的降低，最大降低80%，最小降低为0，平均降低率达到60%以上，方法应用效果明显。但也存在没有降低分支覆盖测试用例数的函数，即与未采用求解过程所需的分支覆盖测试用例数相同，这说明最优化分支覆盖测试路径集的方法不仅与基础原理有关，而且与程序的邏辑结构关系紧密，使用最优化求解不一定获得最优测试用例集，但大多数函数可以使用该方法获取最优分支覆盖测试路径集。

3结语

本文通过使用最优化分支覆盖测试路径集方法，对DD图无约束边在路径构造方面的使用方法进行了扩充，引入程序路径树，可解决精简覆盖无约束边的路径集合，使其数目达到充分测试整个路径的最优解目标。该方法在工程应用方面也得到了验证，降低了分支覆盖测试路径集，确保了测试的充分性。后续可利用计算机技术进行自动化处理，提升测试效率，满足实际工程需要。

参考文献：

＼[1＼]刘斌.软件验证与确认[M].北京：国防工业出版社，2011.

[2]RTCA.DO178B机载系统和设备合格审定中的软件考虑[S].RTCA/EUROCAE，1992.

[3]白晓东，刘代军，张蓬蓬.空空导弹[M].北京：国防工业出版社，2014.

[4]许聚常，朱国庆，尹平.GJB/Z1412004 军用软件测试指南[S].北京：中国人民解放军总装备部，2004.

[5]李必信，方祥圣，袁海，等.一种基于程序切片技术的软件测试方法[J].计算机科学，2001，28（12）：99101.

[6]A BERTOLINO，R MIRANDOLA，E PECILOA. A case study in branch testing automation. [J].Journal of System and Software，1997，38（1）：4759.

[7]叶俊民，王俊杰，董威.一种基于程序DD图的无约束边生成算法[J].计算机科学，2009，36（2）：296298.

[8]姜姗姗，赵中华.分支覆盖测试路径集生成系统设计与实现[J].计算机应用，2010，30（增刊1）：218224.

[9]施冬梅.分支测试中关键分支的寻找算法[J].计算机与数字工程，2011（9）：1619.

[10]尹平，许聚常，张慧颖.软件测试与软件质量评价[M].北京：国防工业出版社，2008.

责任编辑（责任编辑：杜能钢）endprint