基于方法调用关系的软件测试序列生成算法
2018-10-24王曙燕王超飞孙家泽
王曙燕，王超飞，孙家泽
(西安邮电大学 计算机学院，陕西 西安 710061)
0 引 言
获取面向对象软件的测试顺序是面向对象软件测试中重要的问题之一[1]。现有的面向对象软件测试顺序生成方法以类间集成测试序列生成为主，目前针对类间集成测试顺序生成方法主要有两类：①基于遗传算法的类间集成测试顺序生成方法[2]；②基于图论的启发式类间集成测试顺序生成算法[3]。Briand等[4]利用遗传算法提出了生成测试顺序的方法。该方法仅从类间静态依赖关系考虑，忽略了面向对象软件中的多态性，未对动态依赖关系考虑，导致测试不充分。柴玉梅等[5]对UML模型的顺序图添加了对象约束语言给出了一种测试路径生成算法。该方法同样忽略了面向对象软件中的多态性，仅从UML模型顺序图中的静态关系给出测试序列。陈建勋等[6]分析了对象关系图中的类间依赖关系，运用边删除规则去除环路，通过有向无环图的拓扑序列给出类的测试顺序。该方法在解决集成测试序列问题时，也未能考虑软件系统中的动态依赖关系，只抽取了静态依赖关系导致功能路径的缺失，并且忽略了重要的类和错误传播概率较大的类应该尽早被测试的问题。赵玉丽等[7]分析类节点的影响力和复杂性，提出一种重要节点度量方法来给出测试序列。但该方法在给出类间集成测试序列时，采用的节点重要性度量方法仅从节点之间的距离关系来确定影响度，忽略了节点自身对软件系统的影响，导致在对类的影响度分析时不够准确，并且忽略了软件系统中类的动态依赖关系，造成功能路径的缺失，导致测试不充分。
软件系统具有复杂网络的特性，利用复杂网络对软件整体分析度量的研究已经成为软件工程领域的一个热门方向[7]。本文结合类间集成测试序列生成思想，提出一种基于方法动态调用关系的软件测试序列生成算法。该算法获取软件执行过程中的方法调用关系，并以方法为节点，方法间调用关系为边，将轨迹构造成面向对象软件系统的方法级软件网络，综合考虑方法的错误传播影响范围和错误传播概率，给出重要方法重要度值计算算法。该算法能够得到有效的软件测试序列且避免了构建测试桩，降低了测试时间，提高了测试效率。
1 方法节点重要度值评估算法
软件系统中方法的复杂性与软件故障呈现一定正相关性，在对软件进行更新换代中，修改复杂性高的方法比修改复杂性低的方法引入错误的概率高，因此复杂方法的错误倾向性更高[8,9]。而错误在方法间的传播范围和对系统的影响力各不相同[10,11]。本文算法综合了软件中方法的复杂性和方法出现错误时的影响范围两方面因素，借鉴节点删除算法[12]和信息量、结构出度[13]思想,提出了一种复杂网络理论的节点重要度值计算算法(Method-FNIA)。
1.1 方法级软件网络模型
现有的针对集成测试序列生成的研究大多是基于类之间的依赖关系形成的对象关系图。本文是基于软件动态执行过程中方法的调用关系形成的方法调用关系图。由于代码只有在运行时才表现出软件故障与失效，这与程序动态执行过程中方法的调用关系密切相关。如何获取软件动态执行过程中方法的调用关系图是首要解决问题。传统方式是以人为添加代码的方式进行“插桩”，对于代码量过大的程序，工作量巨大，修改不便，不够灵活。鉴于传统插桩方法的这些局限，本文采用了应用操作简单、实用的面向切面的框架AspectJ，来获取软件方法动态调用关系图。通过AspectJ获取到的方法抽象为节点集合V={v1,v2,v3,…,vn}，方法间的调用关系抽象为边集合E={
图1 程序方法调用关系
1.2 方法调用关系图约简方法
由于有些程序规模大，方法调用图可能会产生很多冗余的节点和边，比如A方法被B方法多次调用，导致方法A与方法B之间产生许多重边。为此本文采用了子树约简算法来对类轨迹图进行约简，将冗余的边或节点去除掉，只留一个相同的边，并在这条边上记录下相同边的调用次数，作为边的权值，以此来获取有效的加权方法调用关系图，具体如图2所示，节点代表方法，边代表方法间的调用关系。
图2 子树约简法
1.3 重要方法节点优先测试的关键因素
一个复杂的方法，或者由于出错对系统造成的破坏性大的方法应该被优先测试，即重要方法节点。因此，在分析影响重要方法节点的关键因素时，本文主要从方法的自身、不同方法之间对系统造成的影响，即方法节点影响度，以及重要方法节点自身错误传播能力，即节点错误传播率两个方面来考虑。
1.3.1 方法节点影响度
软件动态方法调用关系图是一个有向图，每个节点对整个软件动态执行图的影响并不仅仅局限于其邻居节点，而会是一种连锁式的影响[12]。为了能够精确地反映节点出错后对系统造成的影响,本文引入方法节点影响度的概念。对方法调用关系图而言，方法节点的影响度越大，即通过该节点传递信息能够到达软件动态执图中更多的节点，一旦该节点出现故障，其造成的影响要远大于影响度小的节点给系统造成的影响，这样的方法应该优先被重点测试[14]。
对方法节点影响度度量主要从直接和间接影响两方面考虑：直接影响为被删除的节点不能分别再与剩余节点相互连通；间接影响为剩余节点中部分节点之间的路径，可能由于被删节点原来所起到的桥梁作用丧失而不再连通[12]。直接影响与间接影响之和称为方法节点影响度，如式(1)所示
TOIi=DOIi+IDOIi
(1)
式中：TOIi为方法节点i影响度，IDOIi为方法节点i的间接影响，DOIi为方法节点i的直接影响。
1.3.2 方法节点错误传播率
方法的复杂性研究表明方法的复杂性与面向对象软件方法的错误倾向性具有密切关系[14]。很多的复杂性度量指标忽略了方法的错误传播能力和结构复杂性。为了更准确的度量方法节点复杂性，本文基于结构度与信息量，引入方法节点错误传播率。对方法的调用关系图而言，方法节点错误传播率越高，该节点的复杂性就越高，错误传播的能力就越强；将错误间接传递到该方法自身的倾向性就越大，其测试的优先级就越高[7]。
对方法节点错误传播率的度量主要从结构出度占比和信息量权重两方面考虑：
(1)结构出度占比为方法调用关系图中节点的结构出度在该节点结构度中的占有率，如式(2)所示
(2)
(2)信息量权重为方法节点的信息量在整个方法调用关系图信息总量中的占有率，如式(3)所示
(3)
1.4 Method-FNIA算法描述
通过分析发现，方法节点的影响度与方法节点的错误传播率与面向对象软件方法的错误倾向具有密切的联系。因此，将两者结合得到方法节点的重要度值评计算方法，如式(4)所示
(4)
这里的α、β、λ为可变参数分别表示影响度、结构出度占比和节点信息量权重且满足α+β+λ=1。在确定指标的权重参数时，不同软件得到的拓扑结构不同，它们所表达的侧重点也不同，对应的参数取值也不同。在软件测试过程中，测试用例会产生差异或大或小的类调用关系执行图，它们之间的权重大小很难统一确定。因此，本文采用信息量权重法自动确定参数大小。
根据上述理论Method-FNIA，(Method-FirstNodeImportance)算法表述如下：
算法1：Method-FNIA
输入：约简后的有向加权软件网络邻接矩阵A；
输出：方法节点测试重要性结果。
步骤1 计算方法节点影响度。通过邻接矩阵A，求取A的距离矩阵D。
(1)将节点i删除后，通过距离矩阵D，计算与节点i直接相邻的节点j的距离dij，对节点i的所有dij求和得到节点i的直接影响DOIi；
步骤2 计算方法节点错误传播率，错误传播率包括结构出度占比和信息量权重两方面。首先通过邻接矩阵A，得到节点i的结构出度与其结构度，求得节点i的结构出度占比；随后，通过权值求得节点i的信息量以及整个网络的总信息量，最终计算出节点i的信息量权重。
步骤3 确定可变参数α、β、λ。根据步骤1与步骤2得到的数据，计算得到信息量权重法所需的变异系数CV,然后对得到的数据进行归一化处理，得到可变参数值。
步骤4 根据式(4)计算得到重要方法节点指标结果。
2 软件测试序列生成方法与实例分析
2.1 软件测试序列生成方法
通过前文分析，在软件系统中错误倾向性较高，错误传播影响范围大，传播率高的类，对软件的稳定性和安全性起着决定性作用[11,15]。因此本文基于重要方法节点优先测试因素，给出一种基于方法动态调用关系的软件测试序列生成方法。该方法生成软件测试序列的步骤如下：①通过AspectJ框架，运行源码来获取调用关系图；②采用Subtree算法对调用关系图进行约简，得到约简后的加权调用关系图；③运用本文算法Method-FNIA，计算方法节点重要度值。影响度和错误传播率，通过信息量权重法确定两者的权重；④对方法节点的重要度值排序，获取软件测试序列。
具体流程如图3所示。
2.2 实例分析
Siemens程序集经常被用作实验对象，并且程序差异较大，可以从不同规模、复杂性等角度来共同验证测试方法。本节以Siemens实验平台程序集合中print Tokens源程序P为例，该程序为词法分析器的源程序，详细介绍Method-FNIA算法的实现步骤，并以此说明该算法的有效性。
根据本文方法，源程序P的方法调用关系图G如图4所示。其中1号标签为起始节点，38号为终止节点。
图3 测试序列生成方法流程
通过Method-FNIA算法得到重要方法节点指标结果后，得到软件测试序列，如图6所示。
3 实 验
3.1 实验对象
为验证该方法的有效性，本文选用实验平台程序集合Siemens中的4个程序，选这4个程序的原因：软件测试实证研究中，Siemens程序集经常被用作实验对象，并且程序差异较大，可以从不同规模、复杂性等角度来共同验证测试方法，具体介绍见表1。
图4 方法调用关系图G
图5 print tokens重要性结果
图6 print tokens方法测试序列
3.2 实验结果与分析
利用本文提出的Method-FNIA算法计算4种程序的方法节点重要性，排序后结果如图7所示。由图7分析得到4种程序中只有少数节点的重要度值非常高，以REPLACE为例，节点的重要值分布在[0.18673,2.20689]之间，重要值超过1.2038的节点只有4个，而在其以下的有24，约占节点总数的85%。该数据表明，软件系统中只有少数节点具有错误传播影响大、错误传播率高的特性，这些节点所产生的错误严重性将远高于其它节点所产生的错误，应尽早优先被测试。
表1 测试程序信息
分析表2、表3可知，4种程序中节点重要度值排名前4的方法节点均具很高的被调用次数，与其它节点具有复杂的调用关系，并且节点自身的结构度很高，结构复杂性较高，同时这些节点也具有较高的直接和间接影响，节点缺失后对整个软件系统造成的影响较高，进一步验证了重要度值越高的节点具有较高的错误影响力和错误传播率，应优先被测试。
图7 程序节点重要值
表2 方法节点各项统计指标
表3 节点重要度排名前4节点各项指标
综上，本文提出的针对节点重要度值计算方法(Method-FNIA)正确有效，排序结果也可应用到软件测试序列生成方法中。
3.3 软件测试序列结果对比分析
对得到的节点重要度值进行排序，求出4种程序的测试序列，见表4。然后采用文献[7]提出的方法，得到4种程序的类间集成测试序列，并和本文方法进行对比分析，实验结果见表5。
表4 本文算法得出的测试序列
表5 对比实验结果
表5中Nump表示当测试完节点总数50%的时，测试序列排名前30%的节点已经被测试的数目，Numm表示文献[7]中Nump个类节点含有本文测试序列排名前50%方法节点的数目，Numn表示本文测试序列排名前50%方法的数目，Nums表示文献[7]中Nump个类中包含的方法总数,Timein表示构造测全部试桩所花费的时间,Timec表示生成测试序列所花费的时间，Timep表示本文方法在时间上与文献[7]的降低率。通过分析表5中4组实验的Nump、Numm、Numn、Nums这4项数据，4种程序在文献[7]中的方法节点数目Numm均小于本文中的方法节点数目Numn，并且文献[7]中的Numm也均小于自身的Nums，通过跟踪源码发现导致这种差距的来源有两方面：文献[7]中排名低于30%的类中具有错误传播范围广、错误传播率高的方法，但由于类的排名靠后，导致方法靠后；此外，有些依赖关系只在代码运行中才会表现出来，由于文献[7]的测试序列仅从类间静态依赖关系考虑，忽略了动态依赖关系，导致测试序列不够准确，本文方法是基于软件动态执行中的方法间调用关系生成的测试序列，确保了动态依赖关系。以上数据说明本文提出的方法能够很好地解决面向对象软件中由于多态性所产生的动态依赖关系问题，比文献[7]提出的方法所产生的测试序列更为充分、准确。此外，4组实验利用本文生成测试序列在不需要构造测试桩的前提下花费的时间Timec值均小于文献[7]中的结果，且从Timep分析得到随着程序的规模变大这种优势也随之增大，因此本文从时间效率上优于文献[7]。综上，本文提出的方法能够生成有效的软件测试序列。
4 结束语
本文利用复杂网络理论将软件方法动态调用关系抽象为网络，根据方法间错误传播影响范围及方法自身的错误传播能力，给出方法节点的重要度衡量指标，并借鉴类间集成测试序列生成思想，设计了一种通过分析软件动态执行过程中方法调用关系来生成软件测试序列的方法。该方法得到的软件测试序列能够保证重要节点优先被测试且避免构造测试桩，测试序列生成时间平均降低了33.45%，并且这种优势随着软件规模的扩大而增大，又保证了软件动态依赖关系和方法自身重要性的因素。
