0 概述

软件可靠性测试是软件开发过程中的一个重要环节, 其目的是对软件的可靠性进行验证, 判断其是否满足用户的需求。如果得到的可靠性满足需求, 则停止可靠性测试, 否则, 需对软件中的缺陷进行纠正, 提高软件产品的可靠性。

运行剖面是软件可靠性工程的基础, 文献[1]将软件运行剖面定义为软件系统如何被使用的一种定量描述。一个简单且被广泛采用的模型是以概率分布描述软件的不同输入值被选取的可能性^[2]。如令D表示软件的输入域, 将D划分为m个不相交的等价类{D_i; 1≤i≤m}, p_i表示选择第i个等价类D_i中元素作为输入的概率, 则$P = \left\{ {{p_1}, {p_2}, \cdots, {p_m}} \right\}, \sum\limits_{i = 1}^m {{p_i}} = 1$就是所谓的运行剖面。

基于运行剖面的测试在软件可靠性领域是一种基本的测试方法。传统方法通过调试测试找出系统中导致失效的漏洞, 而不考虑实际运行中的失效概率, 基于运行剖面的测试则把测试用例的概率, 即软件的运行剖面考虑在内, 选择在实时运行中导致软件失效的高发生率输入, 这些输入对软件可靠性的影响较大, 移除这些漏洞可以极大地提高软件可靠性。因此, 基于运行剖面的测试可有效提高软件可靠性^[3-5], 同时, 运行剖面测试技术也被广泛应用于软件可靠性的评估中^[6-7]。例如, 文献[8]将运行剖面测试应用于实时嵌入式软件, 文献[9-10]研究了运行剖面测试与Web应用可靠性之间的关系。此外, 运行剖面测试还被应用于构件软件系统中^[11]。

然而, 任何测试选择技术都存在饱和点^[12], 基于运行剖面的测试也一样, 其主要关注高发生率的故障, 而当软件需要达到较高的可靠性, 即超出了基于运行剖面的测试的临界点时, 需要找到低发生率的故障(高发生率导致故障的漏洞已被移除)^[13]。因此, 基于运行剖面的测试并不适用于需要高可靠性的关键系统中。

文献[6-7]提出一种基于运行剖面的自适应测试策略, 通过测试用例的反馈驱动选择进行可靠性评估, 将软件测试描述为一个反馈和自适应控制问题, 并使用一个受控的马尔科夫链来描述测试过程, 以最小化可靠性估计的方差。文献[14]将自适应测试与梯度下降法相结合, 其测试结果优于传统的基于运行剖面的测试。文献[15]使用置信区间作为驱动标准自适应地选择测试用例, 以更准确地评估软件的可靠性。不同的测试技术可以发现不同的故障, 针对这一特点, 可以将不同的测试技术相结合, 而不是仅使用一种测试方法。文献[16]把运行测试和调试测试结合起来, 形成一种混合自适应测试技术, 文献[17]将这种混合自适应测试技术应用于软件可靠性的评估。

为了更好地将基于运行剖面的测试技术应用于高可靠性要求的系统, 本文提出一种基于运行剖面的测试用例分配和选择方法。该方法在测试用例分配和选择过程中, 通过每一次迭代的结果对下一次测试进行动态调整, 以提高测试的有效性。

1 相关定义与假设

软件测试主要包括以下2个步骤:

1) 根据选择标准, 从测试集中选取不同的测试用例进行测试。

2) 将得到的输出结果与预期结果进行比较, 如果不一致, 则判定软件发生失效。

本文把引起软件失效的测试用例定义为失效点, 程序移除错误可使许多失效点消失, 把这些失效点的集合定义为失效域, 失效点数量占总执行测试用例数量的比例定义为失效率。设D是待测软件的输入域, T为测试用例集, 现作如下假设:

1) 运行剖面的划分依赖于被测试的应用软件^[18], 测试人员可选择不同的分区标准, 如根据功能、结构等进行划分, 把输入域D分成m个子域, 即测试人员的测试目标可决定分区标准。

2) 假设每个测试用例只能导致失效或成功, 即肯定可以得到运行后的实际结果, 并能够和预期结果进行比较。

3) 每个测试用例都是独立执行的, 相互之间没有影响, 即一个导致系统失效的测试用例总是导致失效, 而不会被之前执行的测试用例影响。

2 测试方法

测试过程可分成测试用例的分配和测试用例的选择两个部分。测试用例的分配需要确定每次迭代中每个子域D_i要执行的测试用例数量, 测试用例的选择则要确定每个子域D_i中选择哪些测试用例, 具体操作过程如图 1所示。其中, T的上标为迭代的次数, 下标为子域的编号, 例如, T_i^k表示在第k次迭代中第i个子域的测试用例数量。

2.1 测试用例的分配

在测试时, 需要根据之前迭代得到的结果定期重新分配测试用例, 利用重要性抽样方法^[19-20]使预测的测试用例概率分布近似于真实概率分布。在第i个子域D_i中, 定义p_i为选择第i个子域中的元素作为输入的概率, 定义φ_i为失效率, 表示失效测试用例占总执行测试用例的比例。在第k次迭代中, 定义一个概率向量π_i^k表示在第i个子域的第k次迭代能够提高可靠性的概率。定义θ_i=p_iφ_i为加权失效率, 并对其进行归一化, 使得$\sum\limits_{i = 1}^m {{\theta _i}} = 1$。概率向量π_i^k的计算公式如下:

$ \mathit{\boldsymbol{\pi }}_i^k = \gamma \mathit{\boldsymbol{\pi }}_i^{k - 1} + (1 - \gamma )\theta _i^{k - 1} $

(1)

上述自适应方法取决于参数γ∈[0, 1], 其决定了算法如何考虑过去迭代结果与当前迭代结果的关系, 将π_i^k的值进行标准化$\mathit{\boldsymbol{\pi }}_i^k = \mathit{\boldsymbol{\pi }}_i^k/\sum\limits_{i \in D} {\mathit{\boldsymbol{\pi }}_i^k} $。在第k+1次迭代中, T_i^k+1个测试被分配到子域D_i中, 则T_i^k+1≈T^k+1π_i^k。根据重要性抽样, 随着获得的信息增多, 样本数量会减少, 本文考虑一种重要性抽样的自适应策略^[19], T^k+1的求解公式如下:

$ \begin{array}{l} {T^{k + 1}} = \frac{1}{{2\xi }}\chi _{\rho - 1, 1 - \delta }^2 \approx \\ \;\;\;\;\;\;\;\;\;\;\frac{{\rho - 1}}{{2\xi }}{\left( {1 - \frac{2}{{9(\rho - 1)}} + \sqrt {\frac{2}{{9(\rho - 1)}}} \cdot {z_{1 - \delta }}} \right)^3} \end{array} $

(2)

其中, ξ是基于采样的估计分布和真实分布之间的误差, 1－δ是对这种近似的期望, ρ是在第k次迭代中至少有一个测试用例被执行的子域数, z_1－δ是具有显著性水平δ的正态分布, T^k+1即为在k+1次迭代中要执行的测试用例数, 具体过程如算法1所示。

算法1   测试用例分配算法

输入  D_i, {π_i^k}, i∈[1, m]

输出  {T_i^k}, i∈[1, m]

//排序, 使得π_i^k≥π_i+1^k

b₁=π₁^k; //初始化累计分布

for i=1 to m T_i^k+1=0;//初始化

end for for i=2 to m b_i=b_i-1+π_i^k; //计算累计分布

end for

//根据式(2)计算T^k+1

${{\rm{r}}_1} \sim {\rm{U}}\left[{0, \frac{1}{{{{\rm{T}}^{{\rm{k + 1}}}}}}} \right]$ //从均匀分布中抽取样本

//将测试用例分到每一个子域

i=1;

for j=1 to T^k+1

while r_j>b_i do//找到要分配测试用例的子域

i=i+1;

end while T_i^k+1=T_i^k+1+1;//分配测试用例

${{\rm{r}}_{{\rm{j + 1}}}}{\rm{ = }}{{\rm{r}}_{\rm{j}}}{\rm{ + }}\frac{{\rm{1}}}{{{{\rm{T}}^{{\rm{k + 1}}}}}}$;

end for

//返回重新排序的{T_i^k+1}:i∈[1, m]

在这一阶段, 第1次迭代在未给定各子域使用概率的情况下, 可先假设每个子域D_i, i∈[1, m]的概率向量π_i⁰都相同, 即$\mathit{\boldsymbol{\pi }}_i^0 = \frac{1}{m}$(如给定了各子域的使用概率, 则可令π_i⁰等于第i个子域的使用概率)。从测试用例分配程序中得到T_i⁰, 之后根据测试结果算出加权失效率θ_i, 由式(1)计算出下一次迭代的π_i。其中, 参数γ一般设置为0.5, 可得到每一次迭代的T_i^k, 并把T_i^k个测试用例分配到子域D_i中, 完成测试用例的分配。概率向量π_i^k根据测试结果一直在动态变化, 因此, 每个子域的概率也在动态变化, 从而测试效率得到提高。

2.2 测试用例的选择

从测试用例的分配阶段中得到输出T_i^k, 表示在每一个子域中要执行的测试用例数量。测试用例的选择是要在第k次迭代的第i个子域中, 选出T_i^k个测试用例, 组成TC_i^k进行执行。本文使用RHC采样方法, 把第i个子域D_i中的测试用例分成g个组, g=T_i^k, D_i中的测试用例总数为N_i。通过不放回抽样方法选出G₁个测试用例, 第2次则从(N_i-G₁)中选取G₂个测试用例, 以此类推, 最终使得$\sum\limits_{r = 1}^g {{G_r}} = {N_i}$。在这一过程中, 一般使g个组的测试用例数量相同, 即${G_1} = {G_2} = \cdots = {G_g} = \frac{{{N_i}}}{g}$, 随机从每一个组中选择一个测试用例组成TC_i^k, 如算法2所示。

算法2   测试用例选择算法

输入   T_i^k

输出   TC_i^k测试用例集

g=T_i^k;

${\rm{h}} = \frac{{{{\rm{N}}_{\rm{i}}}}}{{\rm{g}}}$;

for r=1 to g

//从N_i中选择h个测试用例放入G_r

N_i=N_i－G_r;

end for for r=1 to g

//从G_r中随机选择一个测试用例放入TC_i^k

end for

//返回TC_i^k

在这一阶段, 根据前一阶段得到的T_i^k, 使用RHC采样方法把子域D_i中的测试用例分成T_i^k个组, 从每一组中随机抽取一个测试用例进行测试, 从而完成测试用例的选择。

综上, 本文方法在测试阶段通过每一次迭代的结果对下一次测试进行动态调整, 是一种自适应的测试方法。因此, 该方法的效率比传统的运行测试方法更高。

3 实例分析

为了验证本文方法的有效性, 设计实验分析以下问题:

问题1   在测试过程中各子域概率的变化情况。

问题2   与传统基于运行剖面测试对比的优势。

本文设计实例并对其进行分析, 假设按照软件的功能可将其划分为5个子域, 表 1给出各子域中测试用例的情况。

在测试用例的分配阶段, T⁰设置为10, 给定各子域的使用概率, 令π_i⁰, i∈[1,5]等于第i个子域的使用概率, 即π₁⁰=0.2, π₂⁰=0.1, π₃⁰=0.3, π₄⁰=0.3, π₅⁰=0.1, 将其输入到测试用例的分配程序中, 得到T₁¹=2, T₂¹=1, T₃¹=3, T₄¹=3, T₅¹=1, 然后从每个子域中抽取对应数量的测试用例进行测试。

在测试用例选择阶段, 从子域D₁~D₅中分别选择t₂、t₅、t₇、t₁₀、t₁₁、t₁₄、t₁₉、t₂₀、t₂₁和t₂₅共10个测试用例进行测试。其中, t₇、t₁₀、t₁₄和t₁₉为失效点, 导致程序失效, 因此, 5个子域的失效率φ_i分别为0、1、0.67、0.33和0, 加权失效率θ_i=p_iφ_i, 故θ₁⁰、θ₂⁰、θ₃⁰、θ₄⁰、θ₅⁰分别为0、0.1、0.2、0.1和0, 归一化为0、0.25、0.5、0.25和0, 将它们代入式(1), 计算出π₁¹、π₂¹、π₃¹、π₄¹、π₅¹分别为$\frac{1}{{10}}、\frac{7}{{40}}、\frac{2}{5}、\frac{{11}}{{40}}、\frac{1}{{20}}$。

对于问题1, 虽然子域D₂实际的使用概率只有10 %, 但其在第1次迭代测试中的失效率较高, 相应地, 该子域的概率向量得到提高, 因此, 在之后的测试中会对该子域进行更多的测试, 而对于上一次迭代没有出现失效点的子域D₁和D₅, 其概率向量有所减少, 在接下来的测试中会减少其比例。若使用传统的基于运行剖面的方法对表 1给定的实例进行测试, 其根据每个子域的运行剖面(即实际使用概率)分配测试, 更着重于使用概率大的子域。

对于问题2, 传统的基于运行剖面的测试倾向于使用概率较大的子域D₃和D₄进行更多测试, 本文测试会根据前一次迭代的测试结果进行动态调整, 当子域D₃和D₄中的故障被移除后, 传统的基于运行剖面测试将难以继续提高系统的可靠性, 而本文测试将把测试重心转移到那些使用概率较低而失效率较高的子域上, 移除其中的故障后可进一步提高系统的可靠性, 因此, 本文测试方法相比于传统基于运行剖面的测试具有一定优势。

4 结束语

本文提出一种基于运行剖面的测试用例分配和选择方法。采用自适应的学习方法, 根据每次迭代的结果动态调整下一次测试。当高发生率的故障被移除后继续聚焦低发生率故障, 以提高软件的可靠性。实例分析结果验证了该方法的有效性。然而, 本文仅给出测试方法有效性的简单分析, 下一步将进行大量实验验证, 并对相关定义与假设部分提出的假设进行研究, 以提高测试的准确性。