一种基于马尔科夫链的构件化软件可靠性评估方法

摘要

本发明一种全面准确的，基于马尔科夫链的构件化软件可靠性评估方法，包括如下步骤，(1)通过分析软件结构，得到软件状态转移概率矩阵、各构件包含函数体数量和各构件危害程度；(2)使用不少于最低测试用例的用例数量对软件进行测试，统计各构件的被执行次数、失效数和失效修复数，得到各构件执行概率；(3)根据步骤(1)中得到的构件间转移概率和根据步骤(2)中得到的各构件执行概率计算得到各构件占用率；(4)计算各构件失效率；(5)根据步骤(1)中得到的各构件包含函数体数量计算得到各构件复杂度；(6)根据步骤(1)中得到的各构件危害程度计算得到各构件重要度；(7)评估各构件可靠性；(8)评估软件可靠性。

说明书

技术领域

本发明属于软件工程领域，涉及到软件评估方法，具体为一种基于马尔科夫链的构件化软件可靠性评估方法。

背景技术

大型实时软件系统在随着软件规模不断扩大和功能不断更新，软件结构也越来越复杂，对其可靠性的要求也越来越高，故需要建立软件可靠性评价模型，对实时软件进行可靠性评价。目前的大型实时软件系统由许多软件构件组成，而且每个构件的使用频率和关键程度都不一样，因此需要从软件内部架构和软件构件的角度去评估软件可靠性。典型的构件软件评估方法有三种：基于剖面的方法、基于状态的方法和基于路径的方法。基于剖面的方法主要通过分析不同的软件输入数据集，计算不同剖面出现的概率和各构件间的转移概率来评估软件可靠性；基于路径的方法主要针对测试用例所经历的路径，统计该路径上各构件的使用频率和概率，计算软件系统可靠性；基于状态的方法假设软件系统的运行过程为各构件间的状态转移过程，利用随机过程理论评估软件系统可靠性。其中主流的随机过程模型有两种：马尔科夫过程模型(Markov Process Model)和非齐次泊松过程模型(NonhomogeneousPoission Model)。马尔科夫过程模型以J-M模型为代表，由Jelinski和Moranda于1972年提出，其主要的目标是软件估计失效时刻、剩余错误个数和可靠度。

现有的软件系统的可靠性评估方法主要考虑构件占用率单个因素，认为占用率高的构件的失效率会对软件系统的失效率产生重要影响。但是构件的复杂度和重要度对软件系统的可靠性也很重要，构件结构越复杂，软件系统可靠性越低；某类重要构件虽然使用率不高，但其失效将会对软件系统产生毁灭性影响。现有的都无法对其进行客观全面的评价，不能满足实际需求。

发明内容

针对现有技术中存在的问题，本发明提供一种能够综合考虑软件占用率、复杂度和重要度，进行全面评价的基于马尔科夫链的构件化软件可靠性评估方法。

本发明是通过以下技术方案来实现：

本发明一种基于马尔科夫链的构件化软件可靠性评估方法，包括如下步骤，

(1)通过分析软件结构，得到软件状态转移概率矩阵、各构件包含函数体数量和各构件危害程度；其中，状态转移概率矩阵P由构件间的转移概率p_ij组成，p_ij指的是构件i到构件j的概率，矩阵的维数为软件构件的总数；

(2)使用不少于最低测试用例的用例数量对软件进行测试，统计各构件的被执行次数、失效数和失效修复数，得到各构件执行概率；在最低测试用例的数量下软件中所有构件执行数不少于2次；失效构件在测试过程中将会被实时修复，并得到修复成功概率；

(3)根据步骤(1)中得到的构件间转移概率和根据步骤(2)中得到的各构件执行概率计算得到各构件占用率；

(4)计算各构件失效率；构件的失效率指的是构件从正常状态到异常状态的概率，具体步骤如下：

步骤4.1：设某构件有正常和异常两种状态，形成构件级马尔科夫链，建立由g_i,j组成的状态转移概率矩阵G；g_i,j表示由状态i转移到状态j的概率，由步骤(2)中的被执行次数、失效数和失效修复数计算得到；

步骤4.2：计算该构件在n个周期后的状态概率向量B⁽ⁿ⁾：B⁽ⁿ⁾＝B⁽⁰⁾G⁽ⁿ⁾，其中，初始概率向量B⁽⁰⁾＝[01]，G⁽ⁿ⁾表示矩阵G的n次方；根据平稳马尔科夫链的性质，B⁽ⁿ⁾将会收敛至固定值；

步骤4.3：计算该构件的失效率；

当前时刻的失效率等于状态概率向量B⁽⁰⁾的第二个元素，即λ⁽⁰⁾＝g₁₂；

n个周期后的失效率等于收敛后的状态概率向量B⁽ⁿ⁾的第二个元素，即$>{\lambda }^{\left(n\right)}=g_{12}^{\left(n\right)}\text{;}$>

(5)根据步骤(1)中得到的各构件包含函数体数量计算得到各构件复杂度；

(6)根据步骤(1)中得到的各构件危害程度计算得到各构件重要度；

(7)评估各构件可靠性；根据如下构件可靠性模型得到各构件的可靠性评估值和预测值；

R(λ_j,γ_j,π_j,μ_j；t)＝exp(-γ_jλ_jπ_jμ_jt)，

其中，λ_j为构件j的失效率，γ_j为构件j的占用率，π_j为构件j的复杂度，μ_j为构件j的重要度，t为软件运行周期数。

(8)评估软件可靠性；根据如下软件可靠性模型和步骤(7)中得到的各构件可靠性得到软件的可靠性评估值和预测值，对软件的可靠性进行评估；

$>R({\lambda }_{1,...,n},{\pi }_{1,...,n},{\mu }_{1,...,n};t)=\underset{j=1}{\overset{n}{\Pi }}\exp (-{\gamma }_j{\lambda }_j{\pi }_j{\mu }_{j}t),$>

其中，λ_j为构件j的失效率，γ_j为构件j的占用率，π_j为构件j的复杂度，μ_j为构件j的重要度，t为软件运行周期数，n为软件中的构件数。

优选的，步骤(1)中，函数体数量由软件详细设计说明书中得到；构件危害程度指的是构件对整个软件的关键程度，分为高、中、低和无危害四个等级；

当构件故障将引起软件崩溃，造成巨大损失的危害程度为高；

当构件故障将引起软件的主要功能失效，但不会导致软件崩溃的危害程度为中；

当构件故障将引起软件某功能失效，但不影响软件的主要功能的危害程度为低；

当构件故障不会影响软件的正常运行的危害程度为无。

进一步，步骤(6)中，将构件危害程度的四个等级随机赋予递减的值，高、中、低和无分别对应为lev4～lev1，则构件j的重要度为：

优选的，步骤(3)中，占用率指的是构件在任务中被执行的比例，构件j的占用率其中，b_i表示执行构件i的概率，p_ij表示由构件i执行到构件j的概率。

优选的，步骤(5)中，构件j的复杂度其中，β_j为构件j包含的函数体数量，由步骤(1)得到。

优选的，步骤(7)中，当t＝1得到当前时刻构件j的可靠性评估值为R(λ_j,γ_j,π_j,μ_j；t)＝exp(-γ_jλ_jπ_jμ_j)；当t＝k得到未来k个周期后构件j的可靠性预测值为)式中：k不等于1，$>{\lambda }_j^{\left(k\right)}=g_{12}^{\left(k\right)}.$>

优选的，步骤(8)中，当t＝1得到当前时刻软件的可靠性评估值为当t＝k得到未来k个周期后软件的可靠性预测值为$>R({\lambda }_j^{\left(k\right)},{\gamma }_j^{\left(k\right)},{\pi }_{1,...,n},{\mu }_{1,...,n};k)=\underset{j=1}{\overset{n}{\Pi }}\exp (-{\gamma }_j^{\left(k\right)}{\lambda }_j^{\left(k\right)}{\pi }_j{\mu }_{j}k),$>式中：k不等于1，$>{\gamma }_j^{\left(k\right)}=\underset{i=1}{\overset{n}{\Sigma }}{b}_i{p}_{\mathrm{ij}}^{\left(k\right)},{\lambda }_j^{\left(k\right)}=g_{12}^{\left(k\right)}\text{.}$>

与现有技术相比，本发明具有以下有益的技术效果：

本发明充分考虑了软件体系结构和构件特点对软件可靠性的影响，提出了综合评估因素集。综合评估因素集不仅关注了高频率调用的构件可靠性对软件系统可靠性的影响，也考虑了构件的复杂性和重要性对软件系统可靠性的影响。建立了以函数体为标量粒度的复杂性度量模型，兼顾了构件的复杂度和结构性；建立了优先级和指数模型结合的重要性度量模型，避免了人工赋值的主观干扰。

进一步的，利用建立的模型既能对软件构件进行可靠性评估，也能对软件系统进行可靠性评估；通过对模型中周期的不同选定和赋值，既能对软件当前可靠性进行评估，也能对软件后期的可靠性进行预测，使用范围较广，这对提高软件系统的整体可靠性，控制软件质量具有重要意义。

附图说明

图1是本发明所述评估方法流程图。

图2是本发明实例中所述的构件级马尔科夫链示意图。

具体实施方式

下面结合具体的实施例对本发明做进一步的详细说明，所述是对本发明的解释而不是限定。

将本发明所述的方法应用到某大型实时软件可靠性的评估当中，通过综合考虑构件占用率、复杂度和重要度对软件可靠性的影响，建立了复杂度模型和重要度模型，借鉴马尔科夫链思想分别创建了构件级和软件系统级的可靠性评估模型，对软件进行完整全面的可靠性评估。

如图1所示，具体步骤如下。

步骤(1)，通过分析该大型实时软件结构，得到软件状态转移概率矩阵、各构件包含函数体数量和各构件危害程度。其中，函数体指的是构件中完成特定功能的可被调用的代码集合，是构件的主要组成部分，能够由软件详细设计说明书中得到。

状态转移概率矩阵P由构件间的转移概率p_i,j组成，p_i,j指的是构件i到构件j的概率，矩阵的维数为6；构件危害程度指的是构件对整个软件的关键程度，分为四个等级：高、中、低、无危害。统计结果如表1-1所示；而构件危害程度的划分和对应的序号如表1-2所示。

$>P=\left(\begin{array}{cccccc}0.2& 0.15& 0.15& 0.35& 0.1& 0.05\\ 0.15& 0.3& 0.05& 0.1& 0.2& 0.2\\ 0.05& 0.15& 0.3& 0.1& 0.1& 0.3\\ 0.1& 0.3& 0.1& 0.4& 0.05& 0.05\\ 0.05& 0.25& 0.2& 0.05& 0.3& 0.15\\ 0.1& 0.15& 0.25& 0.1& 0.1& 0.3\end{array}\right)$>

表1-1 该软件结构分析表

表1-2 该软件中构件危害程度分类表

步骤(2)，使用1932例的测试用例对软件进行测试，统计各构件的被执行次数、失效数、失效修复数。其中，失效数指的是构件在测试中发生错误的次数；通过引入失效修复机制，使得失效构件在测试过程中将会被实时修复，从而能够得到其修复成功概率，失效修复数指的是构件失效后成功修复的次数。统计结果如表2所示。

表2 用例测试记录表

步骤(3)，计算各构件占用率。占用率指的是构件在任务中被执行的比例，构件j的占用率γ_j可由下式求得：其中，b_i表示执行构件i的概率，p_ij表示由构件i执行到构件j的概率。

故当前时刻各构件在系统中的占用率为γ⁽⁰⁾＝(0.11,0.22,0.19，0.15,0.13,0.2)，未来n个周期后各构件在系统中的占用率为：γ⁽ⁿ⁾＝γ⁽⁰⁾P⁽ⁿ⁾＝(0.1061，0.2233，0.1705，0.1706，0.1423，0.1871)。

步骤(4)，计算各构件失效率。构件的失效率指的是构件从正常状态到异常状态的概率，具体求解步骤是：

步骤4.1：设构件有正常和异常两种状态，形成构件级马尔科夫链，如图2所示。建立由g_i,j组成的状态转移概率矩阵G，g_i,j表示由状态i转移到状态j的概率，可由步骤(2)中的被执行次数、失效数、失效修复数计算得到。6个构件的状态转移概率矩阵为：

$>G_1=\left(\begin{array}{cc}0.8704& 0.1296\\ 0.9286& 0.0714\end{array}\right),G_2=\left(\begin{array}{cc}0.9299& 0.0701\\ 1& 0\end{array}\right),G_3=\left(\begin{array}{cc}0.9515& 0.0485\\ 1& 0\end{array}\right);$>

$>G_4=\left(\begin{array}{cc}0.9620& 0.0380\\ 1& 0\end{array}\right),G_5=\left(\begin{array}{cc}0.9118& 0.0882\\ 0.9167& 0.0833\end{array}\right),G_6=\left(\begin{array}{cc}0.8811& 0.1189\\ 1& 0\end{array}\right);$>

步骤4.2：计算构件在n个周期后的状态概率向量B⁽ⁿ⁾，其方法为：B⁽ⁿ⁾＝B⁽⁰⁾G⁽ⁿ⁾，其中，初始概率向量B⁽⁰⁾＝[01]，G⁽ⁿ⁾表示矩阵G的n次方。6个构件n个周期后的状态概率向量为：

$>B_1^{\left(n\right)}=\left(\begin{array}{cc}0.8775& 0.1225\end{array}\right),B_2^{\left(n\right)}=\left(\begin{array}{cc}0.9345& 0.0655\end{array}\right),B_3^{\left(n\right)}=\left(\begin{array}{cc}0.9538& 0.0462\end{array}\right);$>

$>B_4^{\left(n\right)}=\left(\begin{array}{cc}0.9634& 0.0366\end{array}\right),B_5^{\left(n\right)}=\left(\begin{array}{cc}0.9122& 0.0878\end{array}\right),B_6^{\left(n\right)}=\left(\begin{array}{cc}0.8937& 0.1063\end{array}\right);$>

步骤4.3：计算构件的失效率。失效率等于收敛后的状态概率向量B⁽ⁿ⁾的第二个元素，即λ＝g₁₂。则各构件n个周期后失效率组成的失效率向量$>{\lambda }^{\left(n\right)}=({\lambda }_1^{\left(n\right)},{\lambda }_2^{\left(n\right)},...,{\lambda }_6^{\left(n\right)})=(\mathrm{0.1225,0.0655},\mathrm{0.0462,0.0366},0.0878,0.1063),$>各构件当前时刻失效率组成的失效率向量λ＝(λ₁,λ₂,…,λ₆)＝(0.1296，0.0701，0.0485，0.0380，0.0882，0.1189)。

步骤(5)，计算各构件的复杂度。构件j的复杂度π_j的计算方法是：其中，β_j为构件j包含的函数体数量，可由表1得到。故各构件的复杂度为：π＝{π_j；j＝1...6}＝(0.0857，0.2000，0.1429，0.2214，0.1929，0.1571)。

步骤(6)，计算各构件的重要度。构件重要度与构件危害程度有关，将构件危害程度的四个等级随机赋予递减的值，分别为lev4～lev1，赋值及对应的重要度如表3所示，则构件j的重要度计算公式为：

表3 构件重要度分配表

故各构件的重要度组成的向量为：μ＝{μ_j；j＝1...n}＝(0.6412，0.5134，0.4111，0.5134，0.3679，0.4111)。

步骤(7)，评估各构件可靠性。模型中的值均已在步骤(3)到(6)中求得，取t＝1可得到当前时刻构件j的可靠性评估：R(λ_j,γ_j,π_j,μ_j；t)＝exp(-γ_jλ_jπ_jμ_j)，评估结果如表4所示：

表4 构件可靠性评估表

取t＝k可得到未来k个周期后构件j的可靠性预测：$>R({\lambda }_j,{\gamma }_j,{\pi }_j,{\mu }_j;k)=\exp \left({-\lambda }_j^{\left(k\right)}{\gamma }_j^{\left(k\right)}{\pi }_j{\mu }_{j}k\right),$>式中：$>{\gamma }_j^{\left(k\right)}=\underset{i=1}{\overset{n}{\Sigma }}{b}_i{p}_{\mathrm{ij}}^{\left(k\right)},{\lambda }_j^{\left(k\right)}=g_{12}^{\left(k\right)}\text{.}$>

步骤(8)，评估软件系统可靠性。模型中的值均已在步骤(3)到(6)中求得，取t＝1可得到当前时刻软件系统的可靠性评估值：$>R({\lambda }_{1,...,n},{\pi }_{1,...,n},{\mu }_{1,...,n};t)=\underset{j=1}{\overset{n}{\Pi }}\exp (-{\gamma }_j{\lambda }_j{\pi }_j{\mu }_j)=0.9942;$>取t＝k可得到未来k个周期后软件系统的可靠性预测：

$>R({\lambda }_j^{\left(k\right)},{\gamma }_j^{\left(k\right)},{\pi }_{1,...,n},{\mu }_{1,...,n};k)=\underset{j=1}{\overset{n}{\Pi }}\exp (-{\gamma }_j^{\left(k\right)}{\lambda }_j^{\left(k\right)}{\pi }_j{\mu }_{j}k),$>式中：$>{\gamma }_j^{\left(k\right)}=\underset{i=1}{\overset{n}{\Sigma }}{b}_i{p}_{\mathrm{ij}}^{\left(k\right)},{\lambda }_j^{\left(k\right)}=g_{12}^{\left(k\right)}\text{.}$>