基于构件影响因子的软件可靠性评估方法

李克文，雷永秀，张震涛

(中国石油大学(华东) 计算机科学与技术学院，山东 青岛 266580)

0 引 言

随着科学技术的发展，构件式软件系统开发成为一种主流的软件开发方式[1]。构件位于软件系统的不同位置，并且每个构件在系统中的作用也不尽相同，如果构件失效对整个软件系统的影响是不同的，因此需要根据软件的网络结构计算每个构件的影响因子。国内外研究者提出结合复杂网络理论对软件工程领域的相关问题进行研究，目前，使用复杂网络理论对软件工程领域的研究多数使用其节点的要性评估方法，得到构件的影响因子。

Bhattacharya等[2]使用复杂网络中节点的度衡量节点的重要性，即与该节点连接的边数目越多，该节点越重要。Subelj等[3]认为节点介数可以度量复杂网络中节点的重要性，即经过该节点最短路径的数量越多表示该节点越重要。Maksim Kitsak等[4]利用K-shell分解方法划分复杂网络节点的重要性，通过递归的删除值小于或等于k的节点及连边(k为整数)，重要性大的节点后删除。这些方法从不同的角度评估了复杂网络节点的重要性，但是这些方法主要针对无向无权网络，而构件式软件系统被认为是有向加权的网络结构。

本文针对以上问题，提出了一种基于构件影响因子的软件可靠性评估方法，使用改进的PageRank算法评估有向加权软件网络中构件的影响因子，然后提出基于构件影响因子的软件可靠性评估方法。

1 研究基础

1.1 基于PageRank算法的复杂网络节点重要性评估

PageRank算法是谷歌的创始人提出的，使用PageRank值评估节点的重要性。其基本思想为：一个节点的重要性与指向它的邻居节点的重要性相关。对于有向网络G=(V,E)，V={v1,v2,…vn} 表示节点的集合，E={e1,e2…em}⊂V×V表示节点之间是否有边相连，PageRank算法的数学公式表示为

(1)

式中:PR(vi) 表示复杂网络中节点vi的PageRank值，其值越大代表节点vi在整个复杂网络中越重要；PR(vj) 为连接到节点vi的节点vj的PageRank值；O(vj) 为节点vj的出度。由PageRank算法的公式可知，指向节点vi的节点数量越多，节点vi的PageRank值越大，即其重要性越高；并且指向节点vi的节点的重要性越高，节点vi的PageRank值也越大。

1.2 构件式软件可靠性理论

随着数十年软件技术的发展，目前的软件可靠性评估模型已有上百种，总的来说可以分为黑盒、白盒方法。基于黑盒的软件可靠性评估方法，使用软件开发后期收集到的软件系统历史失效数据，使用统计学的方法进行建模，对软件系统的可靠性进行评估，这种方法在评估过程中只分析运行环境与系统的交互[5]，将软件系统作为一个整体，不考虑软件的内部结构，该模型评估的效率低、结果的准确性差。近年来，面向对象的构件式软件不断发展，这种基于黑盒的软件评估模型逐渐淘汰，基于构件的软件可靠性评估模型受到更多的关注[1,6]。与传统的基于黑盒的软件可靠性评估模型相比，这种基于白盒的评估模型，能够将软件的内部结构信息与构件的可靠性考虑在内，还能够在软件设计的早期评估其可靠性，因此，基于白盒的方法可以更加准确、合理的对软件系统可靠性进行评估。

目前基于白盒的可靠性评估模型，一般是依据Cheung[5]提出的软件可靠性评估思想。Cheung的模型把软件系统构建为基于离散时间的马尔科夫模型，使用网络结构表示软件系统结构，rvi代表构件vi的可靠性，p(vi,vj) 代表构件vi转移到构件vj的概率，若这两个构件之间不存在转移关系，则p(vi,vj)=0， 可得到控制转移矩阵为

(2)

R=S(1,n)rvn

(3)

当Q为有限矩阵时S=(I-Q)-1， 则软件系统可靠性可表示为

R=S(1,n)rvn=((I-Q)-1)(1,n)rvn

(4)

2 基于构件影响因子的软件可靠性评估方法

2.1 基于PageRank算法的构件影响因子计算方法

随着互联网技术的进步，也逐渐提升了软件系统功能和结构的复杂度，复杂性变成构件式软件系统的基本属性之一[7]，通常把大型软件系统当作一个复杂系统。国内外研究者使用复杂网络的理论与统计学的方法分析构件式软件系统的结构特性，研究结果表明，构件式软件系统结构具有复杂网络的特性，可以将软件系统的结构抽象为一个复杂网络模型。如何结合复杂网络理论对软件系统性能及结构进行分析，国内外研究者已积累了大量的研究成果[8-10]。

在构件式软件系统中，利用已有的构件组装开发软件系统，可以将构件视为网络中的节点，构件之间的连接为有向边，软件系统就成为复杂的关系网[11]。基于PageRank算法的思想，若构件vi调用了构件vk， 则构件vk的重要性分配给了构件vi， 构件vk的被调用次数也决定了构件vi的重要性[12]。但是构件式软件系统中有输入/输出构件，而复杂网络中没有输入/输出节点的概念，并且PageRank算法用于有向复杂网络，而软件系统网络是有向加权的复杂网络，所以需要加入边的权重对节点的影响，使用改进的PageRank算法评估构件的影响因子。为了提高构件重要性计算的准确性，首先将构件分为输入/输出构件节点及普通构件，分别计算构件的重要性，在计算普通构件重要性时采用改进的PageRank算法，然后与构件式软件系统的可靠性评估模型结合，对整个软件系统的可靠性进行评估，并用于指导、优化软件系统的可靠性。

评估输入/输出构件的影响因子公式为

(5)

其中，E(vi) 为完整运行软件系统时构件vi的执行次数的数学期望，该值可以通过分析操作剖面得到；m为软件系统中输入构件或者输出构件的数量。特别说明，当输入/输出构件执行次数的数学期望等于输入/输出构件总的执行次数时，输入/输出构件的影响因子为1，如：该软件系统只有一个输入/输出构件；运行整个软件系统时只有一个输入/输出构件被执行。由公式可知，输入/输出构件的重要性与其执行次数的数学期望成正相关，即输入/输出构件在软件系统中执行的次数越多，说明构件的影响因子越大，对软件系统的影响越高。

基于PageRank算法对软件系统网络中普通构件的影响因子进行评估，以一个有向图来表示软件系统的结构，其中每个节点vi(i=1,2…n) 表示一个构件，有向边 (vk,vi) 表示构件vk到vi的可能转移，p(vk,vi) 表示构件vk到构件vi的转移概率。评估普通构件vi影响因子的计算公式为

(6)

公式中使用构件vk到构件vi的控制转移概率p(vk,vi)， 相当于引入了加权网络中边的权重，改进了传统PageRank算法中重要性平均分配的不合理性。通过对不同构件的转移赋予不同的权重，提高重要构件的影响因子SPR值，降低不重要构件的影响因子SPR值。

使用矩阵方法计算各类构件的影响因子，将上述式(5)及式(6)合并为一个公式。若构件v1为输入构件，则任意构件不会转移到构件v1， 即p(vi,v1)=0， 此时使用PageRank算法得到构件v1的影响因子为0；若构件vn为输出构件则构件vn不会转移到任意构件，即p(vn,vi)=0， 而此时所有构件的重要性都会转移到输出构件vn， 其它任意构件的影响因子都为0。所以，使用矩阵型的PageRank算法时，需要引入一个参数q， 使输出构件的重要性能够转移到输入构件，避免出现影响因子为0的情况。矩阵方法计算各类构件影响因子的公式为

Ai+1=M*Ai

(7)

2.2 基于构件影响因子的构件式软件可靠性评估

Cheung的模型[5]在计算软件系统的可靠性时没有考虑构件的重要性，软件系统中处于不同的位置的不同构件，不同构件在失效时对软件系统的影响也有差别，所以需要引入构件影响因子来评估软件系统的可靠性。

基于Cheung提出的软件可靠性评估方法，本文将通过PageRank算法得到的构件影响因子引入到软件可靠性评估模型中，提出了基于构件影响因子的软件系统可靠性评估方法。引入影响因子后的控制转移矩阵为

(8)

软件系统的可靠性表示为

(9)

基于构件影响因子的软件可靠性评估方法执行步骤如图1所示。

图1 基于构件影响因子的软件可靠性评估流程

3 实验与分析

3.1 实验对象

为了验证本文提出的软件可靠性评估方法的性能，以文献[13]中的某仿真软件系统为实验对象，该仿真系统在软件可靠性评估领域被广泛引用。图2为仿真软件系统的体系结构图，其中构件v1为输入构件，v10为输出构件，构件间的转移概率p(vi,vj) 见表1，根据文献[14]构件vi的可靠性rvi见表2。

图2 仿真系统体系结构

3.2 基于PageRank算法构件影响因子有效性分析

由于该仿真系统软件结构中只有一个输入/输出构件，则输入构件v1的影响因子α1与输出构件v10的影响因子α10都为1，即α1=p(v10,v1)α10且α1=α10， 为了保证输出构件与输入构件的影响因子相等，所以矩阵M中的参数q=p(v10,v1)=1， 则矩阵M为

取A0=(0.1,0.1,…,0.1)T，δ=0.00001， 按照式(7)进行迭代，迭代48次后满足终止条件 |Ai+1-Ai|<0.00001， 得到各构件vi(1,2,…10) 的影响因子A， 为了使输入/输出构件的影响因子为1，对影响因子A进行归一化得到A′。 各构件的影响因子计算结果见表3。

表1 构件间转移概率

表2 构件可靠性

由表3可得构件v5、v1、v10的影响因子最高，其中构件v1为输入构件，v10为输出构件，其发生失效对整个软件系统理应有比较大的影响，即其影响因子应该比较大。构件v5的影响因子最大，它位于软件系统的中心位置，它的失效影响到的构件数量比较多，所以为整个系统的影响也比较大。为了验证影响因子评估的有效性，通过Cheung模型对提高构件可靠性对软件系统可靠性优化效果进行分析，由于构件v5与构件v8的可靠性相同，所以基于Cheung模型验证构件v5、v8对软件系统可靠性的优化效果如图3所示。

由图3可得，提高构件v5的可靠性比提高构件v8的可靠性对整个软件可靠性的影响更有效，由此可见，优化影响因子大的构件能够更大效率地提高软件系统的可靠性。因此，利用本文提出的构件影响因子度量方法可以指导软件系统可靠性的优化。

表3 各构件影响因子

3.3 构件式软件系统可靠性评估实验

使用式(9)对该仿真系统的可靠性进行评估，首先根据表1～表3中构件的可靠性、构件间的转移概率、构件的影响因子及式(8)，可以得到控制转移矩阵Q为

图3 基于Cheung模型的软件系统可靠性优化效果

针对图1中的软件结构，根据文献[13]提出的实际软件系统可靠性为0.8426，将本文的计算结果与几种不同的软件可靠性评估方法进行比较，对比结果见表4。

表4 几种可靠性评估方法对比

由表4可得，使用本文方法得到的该仿真系统的可靠性评估结果的误差最小，仅为1.31%，因此，采用本文的构件影响因子计算方法，评估软件系统的可靠性能够更加符合实际，并且能够判断出对整个软件系统影响性大的构件，便于指导优化整个软件系统。

4 结束语

随着构件式软件开发技术的发展，对构件式软件系统的可靠性评估也成为目前研究的重要方向之一，但是常用的Cheung模型在评估软件系统的可靠性时，没有考虑到构件重要性对整个软件系统的影响。因此，本文提出了一种基于构件影响因子的软件可靠性评估方法，使用引入了构件转移概率的加权PageRank算法评估构件的影响因子，并将影响因子引入到软件可靠性评估模型中，通过仿真系统验证该方法的有效性，并且所提出的方法在软件开发前期能够指导软件系统的优化。本文提出的软件可靠性评估方法没有考虑不同结构风格对软件系统可靠性的影响，今后将进一步对基于构件影响因子及结构分析的软件可靠性评估方法进行研究。