面向对象软件由于具有封装性、多态性和继承性等特点，在软件测试技术上与传统的面向过程软件有很大区别.其中，类的集成测试是在类单元测试完成的基础上，对类集成过程的测试^[1].由于类的测试顺序关系到软件缺陷发现的时间和设计测试桩造成的测试成本，类的集成测试顺序成为集成测试中的一个重要问题^[2].

目前，针对类间集成测试顺序的生成方法主要有两类：1) 基于遗传算法的类间集成测试顺序生成方法.该方法首先初始化一个种群代表类的测试顺序，然后对其进行选择、交叉、变异操作，从而得到一个满足预定条件的类间集成测试顺序^[3];2) 基于图论的启发式类间集成测试顺序生成算法.该方法从类中提取依赖关系，依据打破最多环路、不同类型边的权重等标准移除有环结构的关联边，对类图进行拓扑排序，从而得到类间集成测试顺序^[4].

类间集成测试顺序问题在国内的研究相对较少.陈建勋等分析了对象关系图中的类间依赖关系，运用边删除规则去除环路，通过有向无环图的拓扑序列给出类的测试顺序，有效减少了测试桩的数量^[5].柴玉梅等对UML模型的顺序图添加了对象约束语言，给出一种测试路径生成算法^[6].姜淑娟等以降低测试桩复杂度为优化目标，提出一种基于耦合度量的类间集成测试顺序的确定方法^[7].上述方法在解决类间测试排序问题时，仅仅考虑了减少测试桩数目和降低测试桩复杂度两个方面，忽略了重要的类和错误传播概率较大的类应尽早被测试的问题.

软件系统具有复杂网络特性，运用复杂网络的统计方法对软件整体分析度量的研究^{[8, 9]}已经成为软件工程领域最为活跃的一个分支.本文将类抽象为节点，类之间的依赖关系抽象为边，构造面向对象软件系统的类级软件网络，提出一种类间集成测试序列生成方法，综合考虑类的复杂性及软件网络中类的依赖关系，给出类重要性度量指标；设计基于重要节点与测试桩复杂度的打破环路的有效算法，得到合理的类间集成测试顺序，在保证测试桩复杂度较小的前提下，使得重要类优先测试.

在软件系统中，80%的功能仅被20%的类所承担，20%的类在软件系统中起着决定性的作用，应该被重点测试.因此，如何在软件系统中找到20%的重要类节点是一个亟待解决的问题^[10].

本文根据面向对象软件系统中类间的调用关系建立软件网络结构，当且仅当类B调用了类A的属性或方法时，网络中存在一条由类B指向类A的连边.

在软件网络中，不仅类之间存在复杂性，同时类内部也拥有自己的属性和方法，类本身也具有一定的复杂性.本节首先综合评估了软件类本身的复杂性及其对其他类的影响、类的复用性等因素，定义了两个软件网络重要节点的度量指标：影响因子和复杂因子.

通常情况下，类的入度越大，说明越多的类依赖于该类，即该类的影响力较大.另外，一个类通过某个类调用第三个类在面向对象软件中也是屡见不鲜的，所以，在考虑类的影响力时，应该同时考虑类的直接依赖影响和间接依赖影响.

定义1 特征集合F(A)定义为类A的所有属性和方法所在的集合.

定义2 可达特征集合RF(A,B)定义为类A中能够由类B中的特征直接或间接调用的特征集合.

其中：RF_D(A, B)表示类B直接依赖类A的特征集合；RF_I(A,B)表示类B间接依赖类A的特征集合.

定义3 类A的影响因子定义为

其中：i∈V，i≠A； 为类A对类i的影响因子；N为软件网络的规模；V为软件网络中类节点所在的集合.图1所示为类A~G共7个类的调用关系构成的网络结构.类A中有2个属性和2个方法，即4个特征.类D直接调用类A中的属性a2，类D通过类B间接调用类A中的属性a₁，那么类A对类D的影响因子为2/4.

图 1(Figure 1)

Fig. 1

图 1 7个类的调用关系构成的软件网络 Fig. 1 Software network constructed according to the invocation relationship among 7 classes

定义4 类的复杂因子CF定义为

其中：i∈V，i≠A，α+β=1；d(i,A)表示类A和类i的平均距离，即，从类A经过多少层调用到达类i.复杂因子随着调用层次的增加而递减，可见，错误的传播概率与类间的距离成反比.

定义5 节点重要度.综合考虑类的影响因子和复杂因子得到类的节点重要度为

其中：σ+δ=1； CF(i)′= .IF_max，IF_min，CF_max和CF_min分别表示整个网络中节点影响因子和复杂因子的最大值和最小值.

在集成测试中，如果测试类A时，类B尚未被测试，且短时间内很难构建出类B，此时需要为类A模拟一个类B的对象.这种用来开发或测试一个调用或者依赖桩的组件被称为测试桩^[10].

构建测试桩的代价由桩复杂度估算.本文引用Briand等提出的估算测试桩复杂度的方法^[11]，其计算方法如式(5)所示.

其中：SCplx(i,j)表示移除边e(i,j)表示的依赖关系，为类i构造测试桩j的复杂度；W_A和W_M表示权重，W_A+W_M=1；A(i,j)表示类i调用类j的属性的个数；M(i,j)表示类i调用类j的方法的个数.A(i,j)和M(i,j)分别表示归一化后的结果.

类的测试顺序需要保证每个类在测试前，其依赖的类已经测试完毕，从而确保尽量少的测试桩和集成测试的完整性.生成的类测试顺序的目标在于保证较小的测试桩复杂度，同时满足重要节点被优先测试.以此为基础，本文提出一种基于重要节点与测试桩复杂度的破环算法.首先使用Tarjan算法深度优先遍历有向图G中的每一个节点，找到G中的所有强连通分量SCC；由强连通分量的定义可知，有向图的环路一定存在于SCC中.因此，只需要在每个SCC中查找环路，然后将环路中的每条边按照式(6)赋予权值，进行删边操作.

其中：W(i)表示节点i的重要度；SCplx(i,j)表示删除了边e(i,j)后，需要给节点i构建测试桩的复杂度.

在删除边时，遵循以下四个原则： 1) 当环路中边权值最大的边只有一条时，删除环路中边权值最高的边； 2) 如果边权值最大的边不止一条，且每条边的测试桩复杂度均不等，则删除其中测试桩复杂度最小的边； 3) 如果边权值最大的边不止一条，且这几条边的测试桩复杂度也相等，那么删除其中节点重要度值最大的节点的出边； 4) 直到有向图中再无环路时，删边结束.

定义网络中任意一条从入度为0出度不为0的起始节点出发，到达出度为0入度不为0的终端节点的所有路径为最长依赖路径Path_D.除孤立节点外，节点处于最长路径中的位置由变量依赖深度Depth描述.假设任意一条最长依赖路径的终端节点的依赖深度等于1，那么该路径上任意节点i的依赖深度等于节点i到终端节点的距离d_i加1.通常经过非孤立节点i的最长依赖路径有N_i条(N_i≥1)，Depth_max表示节点i在所有最长依赖路径中依赖深度的最大值.

基于上述定义，分析无环网络数据，得到类间集成测试的顺序，主要过程为： 1) 过滤孤立节点，计算剩余每个节点的最大依赖深度Depth_max; 2) 将节点按照Depth_max升序排序，对于其中存在两个或多个Depth_max值相同的节点按照其重要度值排序； 3) 孤立节点随机插入到已排序列的前面； 4) 输出集成测试序列O.

为了验证本文提出方法的有效性，将其应用于软件DNS 1.2.0，得到该软件的类间集成测试顺序，并将其与文献^[11]所得结果进行对比分析.

根据类间依赖关系，DNS 1.2.0的软件网络结构如图2所示.

图 2(Figure 2)

Fig. 2

图 2 DNS 1.2.0软件的网络结构 Fig. 2 The complex network of DNS 1.2.0

以图2为基础，采用式(4)可得DNS 1.2.0的61个类的节点重要度，如图3所示.由图3可知，DNS 1.2.0软件的类节点重要度值区间为[0.0296,0.5134]，其中，重要度值超过0.3的节点有7个；重要度值在0.2以下的节点有48个，约占总节点数的78.7%.少数重要度值较高的类节点具有较高的复杂性或较高的重用概率，成为软件的核心类节点.错误发生在这些核心节点上所引起的严重性将远远高于其他节点引起的严重性，因此，这些少数重要度值较高的节点应该尽早被测试.

图 3(Figure 3)

Fig. 3

图 3 DNS 1.2.0的类节点重要度 Fig. 3 The significance of each class node in DNS 1.2.0

表1列出了重要度值排名前5和后5的类节点的特征总数Φ，入度d_in，特征被调用次数t，出度 d_out，调用其他类特征次数φ等统计特性.

表 1

Table 1

表 1(Table 1)

表 1 类节点统计特性 Table 1 The statistics characteristics of class nodes 排名 序号 Φ din t d out φ IF CF W 1 8 5 29 329 1 3 1.000 0.03 0.5134 2 38 26 2 8 18 75 0.007 1.00 0.5035 3 55 38 9 79 12 106 0.062 0.68 0.3690 4 21 33 40 135 5 48 0.300 0.39 0.3453 5 51 34 1 49 17 157 0.011 0.63 0.3199 57 13 7 3 4 0 0 0.039 0.02 0.0296 58 27 8 2 3 0 0 0.046 0.03 0.0395 59 9 13 3 11 0 0 0.042 0.04 0.0411 60 33 6 2 2 5 14 0.030 0.05 0.0420 61 15 12 4 4 0 0 0.038 0.05 0.0425

表 1 类节点统计特性 Table 1 The statistics characteristics of class nodes

分析表1可知，重要度排名前5的类节点均具有较高的被调用次数或调用其他类特征的次数，相应地这些类也拥有较高的复杂因子或影响因子，进一步验证了重要度值大的节点具有较高的复杂性和影响力，应该尽早测试.而重要度排名后5的节点，缺乏由于调用其他类特征产生的复杂性，并且调用该类的特征次数也较少，因此，这些类发生错误传播到软件系统中其他类的概率相对较小，具有较低的测试优先级.

进一步应用本文提出算法对软件网络中存在的环路进行破环操作，并按类的最大依赖路径深度及重要度值排序，给出DNS 1.2.0软件的类间集成测试序列.

DNS 1.2.0软件网络包含两个SCC，16个环路.假设式(5)中W_A=W_M=0.5，破环过程如表2所示，其中NC为删边前SCC中包含的环路个数.

表 2

Table 2

表 2(Table 2)

表 2 SCC破环过程 Table 2 The process of breaking in SCC 序号 处理的 SCC NC 删边 W(i) W e(i,j) SCplx ( i,j) 1 SCC 1 16 21→11 0.345 8.422 0.0410 2 {58,48,32, 6 21→8 0.345 2.468 0.1399 3 25,11,8, 5 32→48 0.305 2.182 0.1399 4 21} 4 32→58 0.305 0.502 0.6077 5 SCC 2 3 38→33 0.504 1.860 0.2707 6 {33,38,52} 1 52→33 0.188 0.695 0.2707 7 End 0 —

表 2 SCC破环过程 Table 2 The process of breaking in SCC

破环结束后，可得一个有向无环软件网络.根据网络拓扑结构，计算每个类节点的最大依赖深度，并结合类节点的重要度，得到类间集成测试的顺序，如图4所示.

图 4(Figure 4)

Fig. 4

图 4 类间集成测试顺序 Fig. 4 The class integration test order

根据式(5)计算可知，本文提出方法的平均桩复杂度为0.245，总测试桩复杂度为1.47.在相同参数条件下，本文提出算法与文献^[11]提出算法的平均桩复杂度和总测试桩复杂度相同.另外，本文得到的测试序列，当测试完节点总数的50%时，14个重要节点已经测试完毕，而文献^[11]附录E8给出的10条测试序列中，在测试完成50%时，重要度排名前20的节点，平均只测试完成了6.7个重要节点.由此可见，本文提出算法的生成测试序列在桩复杂度不变的前提下，使得重要节点能够优先测试.

本文运用复杂网络理论对面向对象软件的类间依赖进行建模，根据类间调用关系及类本身的特征，给出类节点重要度的衡量指标.并以此为基础，设计了一种综合考虑桩复杂度和节点重要性的破环算法，从而得到依据节点最大依赖深度及节点重要度的类间集成测试顺序.本文方法在保证桩复杂度较小的前提下，使得软件中的重要类节点优先被测试.