网站首页  词典首页

请输入您要查询的论文：

　

标题 基于AOE网的软件关键路径覆盖测试
范文 职晓+张江华



摘要：嵌入式软件的复杂度越来越高。作为软件可靠性测试的一种重要方法，完全路径覆盖在实际项目测试中越来越不现实。针对这种现状，提出了一种易于操作的关键路径覆盖测试方法。该方法利用AOE网生成全路径矩阵（APM）算法求出待测程序的关键路径，然后利用自动化测试工具对程序进行线性代码与跳转（LCSAJ）分析，最后在其辅助下完成关键路径覆盖测试。实验结果表明：在保障软件可靠性的前提下，该方法节约了测试成本，显著提升了测试效率，具有一定的工程应用价值。
关键词：AOE网；关键路径；邻接矩阵；APM矩阵
中图分类号：TP306
文献标识码：A 文章编号：1672-7800（2015）003-0026-04
0 引言
嵌入式软件在嵌入式系统中越来越重要，嵌入式软件的可靠性成为软件开发中的重要因素。路径覆盖作为软件可靠性测试的重要指标，在嵌入式软件测试中应用越来越广泛。然而，由于工程中的代码逻辑复杂分支繁多，完全的路径覆盖测试用例个数会随着程序中分支的增加呈指数级增长[1]，造成测试成本过高。为了兼顾软件可靠性和测试成本，从众多路径中选出关键路径进行测试成为近年来嵌入式软件测试研究的重要课题。
传统的关键路径求解算法往往是分别求出所有路径的最早发生时间和最迟发生时间，以及每项路径的最早开始时间和最迟开始时间，然后判断哪些路径是关键路径，算法过程复杂。对此，一些研究人员对传统的算法进行了改进，文献[2]在广度优先搜索的基础上，给出了一种求解关键路径的算法。该算法采用图的十字链表结构形式，不需要拓扑排序来求解关键路径。然而，此算法需要对图进行3次广度优先搜索才能输出所有关键活动，而且不能将所有的关键路径输出。文献[3]在深度优先搜索的基础上，求出从源点到汇点的所有路径，经过分析比较求取关键路径。由于在求解过程中需要进行多次递归回溯，算法的执行效率较低。同时，传统的路径覆盖测试用例设计，是通过人工分析各个判定中的条件来确定用例中各个变量的取值，对于程序较为复杂的判定，这种方法往往效率较低，而且容易出错。
针对上述问题，本文提出了一种全新的关键路径覆盖测试方法。首先利用程序的AOE网的邻接矩阵生成矩阵APM算法，求解出待测程序的关键路径，然后，基于LCSAJ的概念设计相应的测试用例。这种方法不但可以输出所有关键路径，而且提高了关键路径的生成效率。同时，由于存在大量的测试工具可以进行LCSAJ分析，因此可以快速准确地完成测试用例的设计。总之，这种方法在保证软件的可靠性前提下，不仅合理地分配了测试资源，而且大大提高了测试的自动化程度。
1 基本概念
1.1 关键路径
控制关系是一个程序正常运行的关键因素，通常用控制流程图来表征。控制流图中有两个要素，如图1所示，结点以标有编号的圆圈表示，代表一个或多个无分支的语句；控制流以箭头表示，表征控制的顺序[4]。为了评估程序的控制结构，控制流图中的连接加入连接权值a～e，通常把这种带权值的控制流图称为AOE网。AOE网中入度为零的点称为源点，出度为零的点称为汇点。通常AOE网中从源点出发到汇点结束的有序结点序列称为该AOE网的路径。路径中连接权值的和称为路径长度。通常，一个AOE网中最长的路径就叫关键路径。
AOE网也可以表示成矩阵的形式，称为AOE网的邻接矩阵。一个邻接矩阵是一个方阵，其行列数目为AOE网中的结点数，行列依次对应被标识的结点，矩阵元素对应到相应结点间的连接。元素a～e的值代表连接权值。图1对应的邻接矩阵如图2所示。
1.2 线性代码与跳转
LCSAJ（linear coded sequence and jump）是指可执行代码的线性序列，这个序列的开始可以是程序的开始或控制流中可能跳转的一个起点，它的终点可以是一个明确的控制流跳转点或程序的结束[5]。这个线性代码序列可以由一个或多个连续的基本模块组成。因此，为了控制流执行线性代码序列和跳转，必须有相应的代码满足相关条件。一个LCSAJ由3个要素——开始行、结束行、跳转目的行组成。程序的一条路径可能由几个首尾相连LCSAJ组成，其中第一个LCSAJ起点为程序起点，最后一个LCSAJ的终点为程序终点。
路径的执行关键就是代码中每一个谓词条件的选取。基于LCSAJ概念，将源代码分割成若干子代码段，通过组合即可实现相应的路径覆盖。现在有许多测试工具可供LCSAJ分析，故可借助这些工具得到相关路径对应的谓词取值组合，进而准确迅速地完成指定路径的覆盖测试。
2 求解关键路径
2.1 权值确定算法
2.1.1 权值影响因子
（1）分支执行概率。嵌入式软件往往有实际的应用背景，因此当程序运行到判决结点时，不同的分支选择通常对应着不同的物理意义，当程序运行到判决结点时，相应分支执行的概率将影响这些分支权值的确定。事实上，此概率值通常要根据软件用户的使用情况确定。
（2）函数接口参数。被测函数的接口参数包括传值参数、引用参数、指针参数3种类型。传值参数调用单元函数时传给函数的实参并不因函数调用而改变，而引用参数会因函数的调用而存在随时被修改的危险。指针参数虽然不会因为函数的调用改变传入实参的地址，但会因此存在指针指向的变量值被修改和指针指向内存单元改变的可能[6]。综上所述，指针参数在函数调用时情况最复杂，因此设定权值为2。引用参数次之，设定权值为1.5。权值参数最低，设定权值为1。式（1）表示函数的接口参数对任一分支连接的权值加权值Hc的算法，其中Nd为该连接的传值参数个数，Na为引用参数的个数，Np为指针参数的个数。
（3）全局变量。全局变量的作用域从定义开始，到程序结束终止，其影响范围相对较大，全局变量使得程序各模块之间的耦合度增加，函数依赖这些全局变量。当一个全局变量值被误操作时，会对其它模块造成影响。由于全局变量对源程序影响很大，测试时要特别小心，因此设定权值为3。式（2）表示函数的全局变量对任一分支连接的权值加权值Hg的算法，其中Ng为该连接的传值参数个数。
（4）局部变量。局部变量的作用域是从变量定义开始到该单元函数结束终止。局部变量的影响区域表示了该函数对该局部变量的敏感性。当局域变量值改变时，仅影响函数内部作用域的语句，相对全局变量来说，其影响范围较小，因此其权值设为1。式（3）表示函数的局部变量对任一分支连接的权值加权值Hc的算法，其中Nd为该连接的权值参数个数，Na为引用参数的个数，Np为指针参数的个数。
2.1.2 权值的数学模型
通常，控制流图矩阵中的连接权值初始值设为1。根据以上权值影响因子对分支连接权值的影响，可以得到该连接的附加权值，最终将两部分相加便可得到最终的权值，如公式（4）所示。其中Wij表示i结点到j结点之间的连接权值，Pij表示该连接的执行概率。
2.2 关键路径求解算法
关键路径求解算法实际上是利用被测程序的AOE网络邻接矩阵G[i][j]来生成全路径矩阵APM的过程。APM顾名思义，其每行分别代表程序可能的执行路径及其路径的累加权值。矩阵的最后一列为每条路径的权值和，其余每个元素分别代表了该路径中的各个结点号。具体算法描述如下：
①初始化矩阵APMG，存储每条路径的权值累加值向量a[n]；②在邻接矩阵G的第一行中逐一查找所有的非零元素，并在APMG中记录相应的列号和此行的直接后序结点数k，最后累加APMG中前k行相邻元素间的权值，并存在a[n]中；③设i=2，m为G的行数；④若i>m，则转至⑧，否则查找G的第i行，依次找出非零元素的列号，共计cout个；⑤查找APMG中元素最大值等于i-1的行。若查找到，则执行步骤⑥；若查找不到，则转至步骤⑦；⑥将找到的APMG行复制count-1个，然后依次将步骤④找到的结点列号添加到APMG中，上述找到的APMG行和复制生成的行相应列进行更新，最后累加更新后的APMG权累加值；⑦继续查找APMG中满足步骤⑤条件的行。若找到，则转至步骤⑤继续执行；若查找不到，则转至步骤⑧；⑧i=i+1，返回步骤④；⑨结合APMG和a[n]生成输出的APM矩阵，每行即为一个程序执行路径；B10APM中最后一列的最大元素所在行即为关键路径，结束。
3 实例分析
为了验证上述关键路径覆盖测试方法，以下面的程序为例加以分析说明，程序代码如下：
3.1 静态分析
对上面代码进行静态分析，可以得到相应的控制流图，如图3所示。
同时，通过静态分析还可得到源代码中变量的类型以及定义使用情况，进而根据式（4）的权值数学模型计算得到图3中相应的连接权值，结果如表1所示。将图3的连接赋以表1中求得的权值，即得到源代码的AOE网。
根据求解关键路径算法，MATLAB仿真可以得到矩阵APM，如公式（6）所示。从式（6）可以看到，矩阵的每一行即代表一条程序路径，分别为（0，1，2，3，5，6，7，9，10）、（0，1，4，5，6，7，9，10）、（0，1，2，3，5，6，8，9，10）、（0，1，4，5，6，8，9，10），对应的路径权值分别为19.3、14.7、20.6、16，故得出路径（0，1，2，3，5，6，8，9，10）的权值最大，此即为所求的关键路径。
APM=012356791019.3014567910014.7012356891020.60145689100164×10（6）
3.3 基于LCSAJ关键路径覆盖测试
利用自动化测试工具Testbed对被测源代码进行分析。首先，得到源代码的LCSAJ表，如表2所示，LCSAJ由3个要素即3个行号（A，B，C）来确定标识，其中A是开始行，B是结束行，C是跳转目的行。表中的每个LCSAJ的3个行号均对应待测源代码中的标识行号。
其次，Testbed还提供了各个LCSAJ的组合关系表（LCSAJ Precondition Table），结合步骤2得到的关键路径（0，1，2，3，5，6，8，9，10），经过简单分析可以得出，关键路径对应的LCSAJ组合对应表2中的LCSAJ编号序列（3，10，14）。
最后依照Testbed分析给出的LCSAJ内部条件表（LCSAJ Internal Condition Table），可以迅速得出此条关键路径对应的判定条件组合为（（x>3）&&（z<10））， x≠4和*y≤5，即最终的关键路径覆盖测试用例只需满足：Ψ={（x，y，z）|（x>3）&&（x≠4）&&（*y≤5）&&（z<10）}。经验证，上述测试用例在程序实际运行中可以完整地执行，实现了该代码关键路径的最终覆盖。
采用本文关键路径覆盖测试，在保证关键路径覆盖的同时，语句覆盖达到71%，分支覆盖达到50%。在此基础上只需再补充1个用例即可实现相关软件测试需求中的语句和分支的100%覆盖。相比传统的随机生成用例的路径覆盖测试方法，本方法可以有针对性地调整测试用例的优先级，达到在测试资源有限的情况下，优化测试资源分配、提升测试效率的目的。
4 结语
本文针对传统的路径覆盖方法存在工作量大不易实施的问题，提出了一种易于操作的路径覆盖测试方法。首先利用AOE网生成矩阵APM算法求出待测程序的关键路径，然后利用自动化测试工具对程序进行LCSAJ分析，最终在其辅助下完成关键路径覆盖的测试。实践证明，该方法不仅提高了关键路径的求解效率，而且简化了路径覆盖测试用例的设计过程，因而在实际工程中节省了测试资源，提升了测试效率。
参考文献：
[1] 周涛.航天型号软件测试[M].北京：宇航出版社，1999：83-86.
[2] 徐凤生，黄倩.关键路径求解的新算法[J].计算机应用，2004，24（12）：108-109.
[3] 孟繁桢.求关键路径的一个算法[J].计算机工程，2001，21（4）：6-9.
[4] 周元哲，张庆生，王伟伟，等.软件测试案例教程[M].北京：机械工业出版社，2013：87-88.
[5] LDRA.C_C++ LDRA testbed technical description[EB/OL].2000.http：//wenku.baidu.com/link？url=lF Mx3z1sT Wi3qTB hS7QQlQ QWZTL SYDxgE ppb 5fIO8-yS0y-gZ WEtU3E SySwxC gG4kYVghE vgy2h MHQUdl8 x6V4k2uH_8 32m2 UW6 NA5 bzTZe.
[6] 高峰，郑纯，刘厂.基于优先级的单元测试技术应用研究[J].应用科技，2010，37（7）：30-32.
（责任编辑：杜能钢）
随便看

　

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。

　

Copyright © 2004-2023 puapp.net All Rights Reserved
更新时间：2025/3/17 15:26:29