软件可靠性是衡量系统质量的重要指标,软件可靠性的计算依赖于可靠性模型的选取以及所获得的软件失效数据.软件可靠性模型分为软件可靠性增长模型^{[1, 2, 3, 4, 5, 6, 7, 8, 9]}和基于架构的模型^{[11, 12, 13, 14, 15, 16, 17, 18, 19]}.这些模型都附带有一些假设条件,如测试时的程序执行和给定的操作剖面要一致,或构件的失效是相互独立的.所以在实际当中,用得最多的是Nelson模型.

失效数据的获取对可靠性及模型有非常大的影响^[20].模型中参数的确定或者模型的计算必须依赖于失效数据,失效数据将影响到可靠性计算的准确性.但是因为我们使用的模型有很多的假设,而在实际中这些假设并不能完全满足,从而导致我们获得的失效数据并不能很好地符合实际要求.因此,为了获得准确的软件可靠性,我们必须考虑失效数据的质量和收集失效数据的方案^[20].目前,有一些针对各个开发阶段的失效数据收集技术^[21],但应用最广泛的方法是软件测试技术.软件测试包括3个要素:选择输入域、执行测试用例和比较输出^[22].学者们提出了多种测试方法来获得软件失效数据^[23],然而这些方法都是通过比较实际输出结果与期望输出结果得到诸如失效次数、失效用例等的失效数据,而忽略了软件的实时行为和内部结构,从而导致这些数据并不能真实反映软件的真实行为,如:

问题1. 测试中会出现假性正确的情况.

当某一个测试用例运行到了错误行,但其结果为pass的时候,这一次测试被称为偶然性正确.如图1所示,t1覆盖了第1行~第5行、第7行、第8行、第14行,其中,第8行有一个BUG,但结果是pass.这种情况下,很明显,t1的pass是偶然性正确.当存在较多的假性正确,我们将无法获取正确的失效数据,从而导致计算出的可靠性无法评估软件的真实可靠性.更极端一点的情况是:当所有的错误用例都产生了假性正确,那么我们将无法收集到失效数据,从而得出软件的失效率为0.

图1(Fig.1)

图1 具有假性正确的例子 Fig.1 An example with false positive outputs

问题2. 测试不能显示一个输入有多个错误的输出情况.

如图2所示,考虑测试用例t1 (input: 1,1,2; output: 0),程序的输出为0.5,而正确的输出应该是0.这个用例经过了两个错误(分别为第3.2行和第5行),但我们只得到一个错误的输出.这样就无法了解到程序内部的信息,从而导致计算出的可靠性与实际程序的可靠性有一定的差距.

问题3. 不同测试方法会影响到失效数据的获取比例,从而影响可靠性的计算.

Chen等人^[24]通过实验指出,不同的测试方法(随机测试、功能测试、分块测试)获得的失效数据会产生不同的可靠性.作者认为:这是因为这样获得的失效数据并没有真正反映程序的内部信息,仅反映了在所选测试用例下粗糙的程序的信息,所以计算出来的可靠性也是不准确的,无法反映软件真实的可靠性.

图2(Fig.2)

图2 一个输入经过多个错误的例子 Fig.2 An example with one input passing multiple faults

因此,仅通过测试阶段的输入/输出所获取的失效数据并不充分,无法准确反映程序内部存在的问题,从而得到的可靠性不够准确.为了解决这个问题,我们需要程序的内部数据来计算软件的可靠性.一个解决方案是:通过观察和分析测试过程中程序的执行轨迹从中提取程序的内部信息(例如内部结构、动态行为).我们采用工具Daikon做动态分析.Daikon从程序的执行过程中发现可能的程序不变量.不变量是指程序在运行时保持不变的属性的量,刻画了程序的动态性质,体现了软件的整体行为.从这些不变量中得到不好的不变量,利用这些不好的不变量计算可靠性.尽管有个别工作,如Pietrantuono,通过程序不变量来监测和预测在线软件的可靠性^[25],丁佐华等人通过程序不变量来计算服务组合的在线可靠性计算^[26],但都没有对其可行性论述.本文通过实验来说明其可行性.我们的实验程序来自于西门子程序包.采用随机、分支覆盖和分块覆盖这3种不同的测试方法得到程序不变量,据此分别计算程序的可靠性.

为了检查所得结果的正确性,我们采用现有的可靠性方法再次计算这些软件的可靠性.两种可靠性比较后显示:它们的差别很小,而且不依赖于我们对测试方法的选择.进一步的方差分析告诉我们:用所提方法计算的可靠性比用现有的方法计算的可靠性具有更小的波动,也就是说更平稳.因此,前者更接近系统的真实可靠性.

本文第1节描述如何得到程序不变量和不好的程序不变量,即失效数据.第2节描述如何基于不变量进行可靠性计算.第3节介绍实验的准备工作,包括3种选取测试用例集的方法以及西门子程序包.第4节描述如何从西门子程序包获取失效数据.第5节是软件可靠性的计算及结果分析.第6节是所提方法的可行性分析.第7节是相关工作介绍.第8节是全文的总结.

程序不变量常被用于追踪软件缺陷^[27]、硬件错误^[28]和软件评估^[29].程序不变量揭示了程序在运行过程中保持不变的状态,这些状态对软件的发展、测试和维护有重要的意义.常用的提取不变量的工具有DIDUCE^[27]和Daikon^[29].本文采用Daikon作为提取不变量的工具.

Daikon工具作为动态不变量发现器,利用程序执行来发现可能的不变量.它通过修改目标程序来跟踪感兴趣的域,通过一组测试套件来运行修改以后的程序,从而利用跟踪得来的结果推导不变量.这些推导出来的不变量也可以作为形式化的规格说明插入到代码中作为注释,帮助提高程序可理解性.

通常,默认不变量有196个类型,这些类型基本上满足了我们的要求.当然,我们可以在此基础上定义更多的不变量类型.如果在现有的类型下所得到不变量是不完全的,这说明涉及这些不变量的语句没有被执行到.一种情况是这些语句是多余的,另一种情况是测试用例的选取不够充分.如果我们的覆盖率能够达到希望的要求,那么即便是有少量的不变量没有计算到,也不会对结果产生太大影响.

下面我们通过一个计算器例子来说明如何得到程序不变量(见表1):

表1(Table 1)

表1 计算器例子Table 1 An example of calculator Code JButton b[]=new JButton[16]; String s[]={“0”,“1”,“2”,“3”,“4”,“5”,“6”,“7”,“8”, “9”,“+”,“-”,“*”,“/”,“C”,“=”}; … public void actionPerformed(ActionEvent e)   { …      if (flag==10) m2=m1+m2;       else if (flag==11) m2=m2-m1;       else if (flag==12) m2=m2*m1;       else if (flag==13) m2=m2/m1;       else m2=m1;     …    } …

表1 计算器例子 Table 1 An example of calculator

(1) 生成测试用例集.在该例子中,我们用原先已有的测试用例生成技术^[30]生成一个测试用例集,该技术结合白盒测试和黑盒测试方法将输入域分成若干个等价类,再从等价类中选取测试用例.为了更好地提取不变量,我们还采用Gupta^[31]提出的方法进一步提炼测试用例集.在给定的例子中,测试用例集包括80个测试用例;

(2) 定义不变量类型.Daikon不变量类型有很多种,如x=a,x≠0,a≤x≤b,y=ax+b,x≤y,x=fn(y),xÎy等,我们还可以自定义程序不变量的类型;

(3) 运行程序和测试用例,得到轨迹文件;

(4) 得到程序不变量.在该例子中得到的部分不变量见表2,其中,不变量size(this.b[])==size(this.s[])是指数组b的长度等于数组s的长度.

表2(Table 2)

表2 通过原程序得到的部分不变量Table 2 A part of the program invariants of the program Code (C1) Invariants (TI) JButton b[]=new JButton[16]; String s[]={“0”,“1”,“2”,“3”,“4”,“5”,“6”,“7”,“8”, “9”,“+”,“-”,“*”,“/”,“C”,“=”}; … public void actionPerformed(ActionEvent e)    { …      if (flag==10) m2=m1+m2;       else if (flag==11) m2=m2-m1;       else if (flag==12) m2=m2*m1;       else if (flag==13) m2=m2/m1;       else m2=m1;     …     } … 1) JB:::OBJECT 2) size(this.b[])==size(this.s[]) 3) this.m1≥0 4) this.flag≥0 5) this.b!=null 6) this.b[] contains no nulls and has only one value, of length 16 7) this.b[] elements!=null 8) this.s[] contains no nulls and has only one value, of length 16 9) size(this.b[])==16 10) this.s.getClass()==java.lang.String[].class 11) this.m1≤this.m2 12) this.flag<size(this.b[])-1

表2 通过原程序得到的部分不变量 Table 2 A part of the program invariants of the program

接下来,我们描述如何得到不好的程序不变量,即失效数据.程序C1改为程序C2,将JButton b[]=new JButton^[16]中的16改为17,以及调换String s[]={“0”,“1”,“2”,“3”,“4”,“5”,“6”,“7”,“8”,“9”,“+”,“-”,“*”,“/”,“C”,“=”}中‘+’和‘-’的位置时,我们会得到新的不变量集T2,见表3.通过对比发现:不变量1)、不变量3)~不变量5)、不变量7)、不变量10)~不变量12)跟原先一样,而不变量2)、不变量6)、不变量8)、不变量9)发生了变化.如原先的不变量2)是size(this.b[])==size(this.s[]),而改变后的是size(this.b[])-1==size(this.s[]).显然,这里描述数组b的长度等于数组s的长度的不变量发生了变化,因此认为新的不变量size(this.b[])-1==size(this.s[])是一个失效数据.

表3(Table 3)

表3 修改程序后得到的部分不变量Table 3 A part of program invariants of the modified program Code (C2) Invariants (T2) JButton b[]=new JButton[17]; String s[]={“0”,“1”,“2”,“3”,“4”,“5”,“6”,“7”,“8”, “9”,“-”,“+”,“*”,“/”,“C”,“=”}; … public void actionPerformed(ActionEvent e)    { …      if (flag==10) m2=m1+m2;       else if (flag==11) m2=m2-m1;       else if (flag==12) m2=m2*m1;       else if (flag==13) m2=m2/m1;       else m2=m1;     …   } … 1) JB:::OBJECT 2) size(this.b[])-1==size(this.s[]) 3) this.m1≥0 4) this.flag≥0 5) this.b!=null 6) this.b[] contains no nulls and has only one value, of length 17 7) this.b[] elements!=null 8) this.s[] contains no nulls and has only one value, of length 17 9) size(this.b[])==17 10) this.s.getClass()==java.lang.String[].class 11) this.m1≤this.m2 12) this.flag<size(this.b[])-1

表3 修改程序后得到的部分不变量 Table 3 A part of program invariants of the modified program

在该程序中,执行上述所有测试用例,共生成不变量3 207个,其中,失效不变量有282个.

本文采取Nelson可靠性模型来计算软件的可靠性.Nelson软件可靠性模型对软件做出如下假设:

1) 程序被认为是集合E上的一个可计算函数F的一个规范,这里用E=(E_i:i=1,…,m)表示用于执行程序的所有输入数据的集合,一个输入数据对应一个程序执行回合;

2) 对于每个输入E_i,程序执行产生输出F(E_i);

3) 由于程序包含缺陷,程序实际确定函数F¢,该函数不同于希望函数F;

4) 对于某些E_i,程序实际输出F¢(E_i)在希望输出F(E_i)的容许范围之内,即|F¢(E_i)-F(E_i)|≤Δ_i.但对另一些E_j,程序实际输出F¢(E_j)超出容许范围,即|F¢(E_j)-F(E_j)|>Δ_j,这时认为程序发生一次失效;

5) 测试过程中不剔除程序缺陷.

Nelson模型计算软件可靠性的函数为

根据上述模型,接下来具体描述如何计算表1给出的计算器例子的可靠性.

Step 1. 生成测试用例集,在第1节中,我们共得到了80个测试用例.

Step 2. 将测试用例进行分类.具体的分类方法是:

a) 通过gcov编译,执行测试用例,生成测试用例对程序的覆盖信息;

b) 分析该测试用例对程序中每个分支或者子函数的覆盖率;

c) 测试用例A和测试用例B,如果覆盖程序相同的部分超过一定的值(该值需要根据程序的结构以及测试用例集来确认),那么认为测试用例A和测试用例B是同一类测试用例.

接下来,我们选取计算器中如下的4个选择分支来阐述如何进行分类:

· 分支1: if (flag==10) m2=m1+m2;

· 分支2: else if (flag==11) m2=m2-m1;

· 分支3: else if (flag==12) m2=m2*m1;

· 分支4: else if (flag==13) m2=m2/m1.

测试用例:

· T1: x1 2 3;

· T2: x1 9.1 8.5;

· T3: x2 89 63;

· T4: x2 77 34.9;

· T5: x4 9 3;

· T6: x3 76.1 63.

测试用例中,x1,x2,x3,x4表示标志位:当标志位是x1时,程序执行分支1;当标志位是x2时,程序执行分支2;当标志位是x3时,程序执行分支3;当标志位是x4时,程序执行分支4.当执行测试用例T1时,通过gcov可以知道:分支1被调用,测试用例覆盖分支1,而没有覆盖其他3个分支.同理,我们可以得到T2仅覆盖了分支1,T3和T4覆盖了分支2,T5覆盖了函数分支4,T6覆盖了分支3.因此,我们把T1和T2分为一组测试用例集,T3和T4分为一组测试用例集,T5分为一组测试用例集,T6分为一组测试用例集.

根据上述方法,我们可以将所得的80个用例分成5类,具体分类结果见表4:

表4(Table 4)

表4 测试用例的分类Table 4 Classification of the test cases Sort 1 2 3 4 5 Total Number 17 11 23 26 3 80

表4 测试用例的分类 Table 4 Classification of the test cases

Step 3. 分类后,运行每个测试用例集和程序,根据第1节所述,得到程序不变量和失效不变量.具体数据见表5.

表5(Table 5)

表5 各组用例产生的不变量和失效数据(失效不变量)Table 5 Program invariants and failure data of the test cases Sort 1 2 3 4 5 Total invariants 1 286 999 1 542 2 201 47 Failure invariants 8 192 198 269 2

表5 各组用例产生的不变量和失效数据(失效不变量) Table 5 Program invariants and failure data of the test cases

Step 4. 通过得到的失效数据进行可靠性计算.

根据Nelson模型,我们计算得到的可靠性为

为了与传统的基于不同测试方法的可靠性计算方法进行比较,以此来说明基于不变量计算可靠性的可行性和优点,我们采用了3个常用的测试用例生成方法:随机生成、基于分块覆盖生成和基于分支覆盖生成以及西门子程序包:the Software-artifact Infrastructure Repository^[32].我们在实验中验证的内容有:(1) 失效数据(失效不变量)获取的可行性,即,不同测试方法对失效数据的比例影响不大;(2) 可靠性计算的可行性,即,基于不变量计算的可靠性与传统方法计算所得的可靠性接近.验证的优点是:基于不变量计算所得的可靠性更稳定,因此更能体现程序的可靠性.

本文采用随机选取、基于分块覆盖选取和基于分支覆盖选取这3种不同的测试方法从测试用例集中选取测试用例.

随机测试即从程序的输入域中随机地选取一个测试用例,每一个测试用例都有一个被选中的概率.在我们的实验中,根据预先定义的发生概率,从程序的规格说明书中随机选取至少一个功能进行随机测试;然后,随机选取一个合适的测试用例来对这个说明书进行测试,直至选取的测试用例集覆盖程序的所有功能.分块覆盖测试是我们把只有一个入口和一个出口的顺序语句作为一个块.选取测试用例时,要覆盖所有的程序块及至少有一个测试用例覆盖一个程序块.按分支覆盖准则进行测试是指:设计若干测试用例,运行被测程序,使得程序中每个判断的取真分支和取假分支至少经历一次及判断的真假值均曾被满足.

本文采用的实验程序来源于the Software-artifact Infrastructure Repository^[32].The Siemens set包含7个C程序,见表6.它们常用于错误定位和软件可靠性计算.

表6(Table 6)

表6 Siemens setTable 6 Siemens set Program Faulty versions Test cases Description print_tokens 7 4 130 Lexical analyzer print_tokens2 10 4 115 Lexical analyzer replace 32 5 542 Pattern recognition schedule 9 2 650 Priority scheduler schedule2 10 2 710 Priority scheduler tcas 41 1 608 Altitude separation tot_info 23 1 052 Information measure

表6 Siemens set Table 6 Siemens set

表6详细描述了我们实验所需要的7个程序,每个程序包含一个正确的版本以及多个错误版本,每个错误版本包含一个错误(在我们的实验中,需要把所有的错误整合在一起,构成一个包含多个错误的版本).另外,每个程序有一个输入集(即测试用例集).

我们通过3种不同的方法来选取测试用例集T1(随机选取)、T2(基于分块覆盖选取)、T3(基于分支覆盖选取).分别运行正确版本程序C与T1、C与T2、C与T3得到程序不变量TI1,TI2和TI3,运行错误版本程序F与T1、F与T2、F与T3得到程序不变量FI1,FI2和FI3.比较TI1与FI1、TI2与FI2以及TI3与FI3的不同,分别得到各自的失效数据.

表7是3种方法得到的程序不变量总数和失效数据的个数.Random表示随机选取测试用例得到的程序不变量,Block表示基于分块覆盖选取测试用例得到的程序不变量,Branch表示基于分支覆盖选取测试用例得到的程序不变量.False指失效的程序不变量数,Total表示程序不变量的总数.由表可以发现:对于同一个程序,采用不同的测试方法获得的不变量是不一样的;当然,获得的失效数据,即不好的不变量也是不一样的.

表7(Table 7)

表7 3种方法得到的失效数据与程序不变量Table 7 Failure data and the total program invariants gotten by the three test methods Program Random Block Branch False Total False Total False Total print_tokens 1 038 16 925 1 015 16 851 998 16 832 print_tokens2 1 286 15 971 1 269 15 735 1 315 15 821 replace 2 410 18 065 2 359 17 906 2 187 17 318 schedule 1 472 15 126 1 354 14 973 1 308 14 865 schedule2 1 873 16 725 1 749 16 287 1 702 15 994 tcas 1 957 20 108 1 913 19 947 1 864 20 116 tot_info 1 965 20 294 1 870 19 083 1 897 19 525

表7 3种方法得到的失效数据与程序不变量 Table 7 Failure data and the total program invariants gotten by the three test methods

接下来计算失效数据所占的百分比.表8给出了每种方法所获得的失效数据百分比,可以发现不同方法获得的失效数据百分比基本相近,误差不大.例如:对于程序print_tokens,随机方法、基于分块覆盖方法和基于分支覆盖方法所得到的失效数据百分比分别为6.13%,6.02%,5.92%,其最大的相对误差只有(6.13%-5.92%)/ 6.13%x100%=3.4%;其次,我们计算得到3种方法平均能够发现的失效数据百分比分别为9.69%(random),9.49% (Block)和9.32%(Branch),最大相对误差为3.8%.

表8(Table 8)

表8 失效数据所占程序不变量总数的百分比Table 8 Percentages of the failure data Program Random (%) Block (%) Branch (%) print_tokens 6.13 6.02 5.92 print_tokens2 8.05 8.06 8.31 replace 13.34 13.17 12.62 schedule 9.73 9.04 8.79 schedule2 11.19 10.73 10.64 tcas 9.73 9.59 9.26 tot_info 9.68 9.79 9.71

表8 失效数据所占程序不变量总数的百分比 Table 8 Percentages of the failure data

综上所述,我们可得出结论:不同测试方法得到不同的不变量;但是就失效数据的百分比来说,它们之间相差较小,比较稳定.

根据第2节的方法,我们来计算7个程序的可靠性.我们以程序schedule为例,详细叙述失效数据的获得和可靠性的计算.通过上述3种方法,我们将随机选取的测试用例分为15个测试用例集,将基于分块覆盖选取的测试用例分为14个测试用例集,将基于分支覆盖选取的测试用例分为14个测试用例集.

Step 1. 用随机测试方法选取了260个测试用例,分块覆盖方法选取了272个测试用例,分支覆盖方法选取了295个测试用例.

Step 2. 将测试用例进行分类,分类结果见表9.

表9(Table 9)

表9 程序schedule的测试用例集分类结果 Table 9 Result of the classification of the test cases from program schedule Sort 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 总计 Random 1 25 14 2 7 82 4 6 7 40 4 34 2 3 29 260 Block 18 28 9 11 73 2 4 9 30 11 52 2 4 19 - 272 Branch 2 20 9 10 91 4 5 6 43 2 62 6 15 20 - 295

表9 程序schedule的测试用例集分类结果 Table 9 Result of the classification of the test cases from program schedule

Step 3. 分类后,运行每个测试用例集和程序,根据前一节所述办法得到总的不变量和失效数据,见表10.

表10(Table 10)

表10 分类后所得失效数据和总不变量数目Table 10 Failure data and total program invariants in each sort Sort Random Block Branch 失效数据 总不变量 失效数据 总不变量 失效数据 总不变量 1 4 27 1 054 4 742 54 606 2 554 4 208 537 3 727 1 042 5 919 3 721 5 100 0 5 100 29 372 4 8 999 2 764 12 944 1 683 8 938 5 715 10 984 2 815 13 029 2 314 12 629 6 3 983 12 546 1 162 14 764 853 7 410 7 394 9 930 1 319 3 512 983 2 864 8 912 5 054 0 5 054 861 1 511 9 77 3 710 1 835 11 987 3 349 11 409 10 1 934 10 446 791 6 421 595 1 046 11 192 3 216 4 581 13 903 778 11 086 12 1 343 11 824 1 025 6 735 475 8 964 13 257 4 369 415 4 482 1 262 6 318 14 594 4 616 1 846 12 797 1 224 4 164 15 1 236 4 486

表10 分类后所得失效数据和总不变量数目 Table 10 Failure data and total program invariants in each sort

Step 4. 将得到的数据代入Nelson模型进行可靠性计算.计算结果为:0.860 8(随机),0.862 5(基于分块覆盖),0.877 2(基于分支覆盖).

其余程序的可靠性计算结果见表11,其中,R-reliability表示随机选取测试用例计算的可靠性,Block- reliability表示基于分块覆盖选取测试用例计算的可靠性,Branch-reliability表示基于分支覆盖选取测试用例计算的可靠性.

表11(Table 11)

表11 通过不变量计算的可靠性Table 11 Reliability computed by program invariants Program R-reliability Block-reliability Branch-reliability print_tokens 0.854 1 0.860 5 0.867 9 print_tokens2 0.841 7 0.852 6 0.839 7 replace 0.804 4 0.817 0 0.820 3 schedule 0.795 0 0.800 3 0.810 7 schedule2 0.821 4 0.829 8 0.835 0 tcas 0.789 2 0.794 7 0.805 1 tot_info 0.835 3 0.827 8 0.821 3

表11 通过不变量计算的可靠性 Table 11 Reliability computed by program invariants

由表11可知:不同测试方法算出的可靠性虽然不一样,但相差较小.例如:对于程序print_tokens,随机方法算出的可靠性最低,为0.854 1;基于分支覆盖方法算出的可靠性最大,为0.867 9;而两者的差值为0.013 8.

我们再来看一下不同方法产生的可靠性的波动大小,这里采用方差来刻画.根据概率统计的理论,方差越大,个体间的波动就越大.也就是说,不同测试方法对可靠性的影响就越大.表12计算了不同程序在3种测试方法下的可靠性方差. 3种方法对不同程序可靠性的影响动荡范围在0.000 003 2~0.000 004 7之间,因此,所得的可靠性是比较稳定的,测试方法对其影响不大.这是因为不变量反映的是程序整体的行为,所计算的可靠性是软件整体的可靠性,而不是在具体测试方法下的局部可靠性.

表12(Table 12)

表12 不变量计算的可靠性方差Table 12 Variance of the computed reliability 程序 方差 print_tokens 0.000 003 2 Print_tokens2 0.000 003 2 Replace 0.000 004 7 Schedule 0.000 004 3 Schedule2 0.000 003 2 Tcas 0.000 004 4 tot_info 0.000 003 3

表12 不变量计算的可靠性方差 Table 12 Variance of the computed reliability

综上所述,我们发现:

1) 在不同测试方法下,由不变量计算出的可靠性不是完全相等,还有一定的误差,其原因是有些不好的不变量之间还有一定的依赖性;

2) 用不变量来计算可靠性时,测试方法对软件的可靠性影响不大.

本节利用现有的计算可靠性方法来计算所给7个程序的可靠性,即,用标准的Nelson模型计算.这里我们不再详细叙述计算过程,只给出计算的可靠性.然后,我们比较用不变量计算出的可靠性和用现有方法计算出的可靠性之间的差异.可靠性计算结果见表13.

由表13得知,在同一测试方法下,用不变量和用现有方法计算出的可靠性有细微差异,有时不变量计算的可靠性大,有时现有方法计算的可靠性大;但是两者相差不大,这可由表14的相对误差的绝对值得到.在表14中,最大的相对误差绝对值仅有3.787%,而大部分相对误差的绝对值在1%左右.

表13(Table 13)

表13 利用不变量和利用现有方法计算出的可靠性Table 13 Reliability computed by program invariants and by traditional method Program R-reliability Block-reliability Branch-reliability 不变量 传统方法 不变量 传统方法 不变量 传统方法 print_tokens 0.854 1 0.847 2 0.860 5 0.861 3 0.867 9 0.874 8 print_tokens2 0.841 7 0.851 8 0.852 6 0.849 1 0.839 7 0.864 7 replace 0.804 4 0.797 2 0.817 0 0.810 3 0.820 3 0.829 7 schedule 0.795 0 0.808 6 0.800 3 0.831 8 0.810 7 0.819 4 schedule2 0.821 4 0.819 9 0.829 8 0.824 7 0.835 0 0.831 5 tcas 0.789 2 0.801 7 0.794 7 0.794 8 0.805 1 0.815 9 tot_info 0.835 3 0.824 9 0.827 8 0.817 5 0.821 3 0.836 1

表13 利用不变量和利用现有方法计算出的可靠性 Table 13 Reliability computed by program invariants and by traditional method

表14(Table 14)

表14 两类可靠性的相对误差Table 14 Relative error between the two kinds of reliability Program R-reliability (%) Block-reliability (%) Branch-reliability (%) print_tokens 0.814 4 -0.092 9 -0.7888 Print_tokens2 -1.185 7 0.412 2 -2.891 2 Replace 0.903 2 0.826 9 -1.132 9 Schedule -1.681 9 -3.787 0 -1.061 8 Schedule2 0.182 9 0.618 4 0.420 9 Tcas -1.559 2 -0.012 6 -1.323 7 tot_info 1.260 8 1.259 9 -1.770 1

表14 两类可靠性的相对误差 Table 14 Relative error between the two kinds of reliability

接下来,我们比较现有方法和不变量方法计算出的两类可靠性在不同测试方法下产生的波动大小.根据前面所述,我们可以用方差来刻画这一性质.表15列出了这两类可靠性计算方法在3种测试方法下的方差.由表15可以发现:两种方法计算出的可靠性方差都不是太大;但是相比较而言,现有方法的可靠性波动远大于不变量计算出的可靠性波动.这是因为现有方法计算出的可靠性一定程度上依赖于测试方法,反映软件的局部行为,计算出的可靠性是在该测试方法下的可靠性,所以在不同的测试方法下,可靠性会产生相对较大的波动.而不变量反映软件整体的行为,虽然不同的测试方法会产生不同的不变量,但这些不变量的合成效果却是一样的,都反映软件整体的行为,所以不变量计算出的可靠性是软件的整体可靠性,其波动产生的原因在于有些失效数据(不好的不变量)之间还有一定的相关性.

表15(Table 15)

表15 两类可靠性的方差比较Table 15 Comparison on the variances of the two kinds of reliability 程序 方差 不变量(10-5) 传统方法(10-5) print_tokens 0.32 13 Print_tokens2 0. 32 4.6 Replace 0. 47 1.8 Schedule 0. 43 9.0 Schedule2 0. 32 2.7 Tcas 0. 44 7.7 tot_info 0. 33 5.8

表15 两类可靠性的方差比较 Table 15 Comparison on the variances of the two kinds of reliability

综述所述:相对于现有的计算可靠性方法,我们还可以利用不变量来计算软件的可靠性;且利用不变量计算的可靠性更接近软件的实际可靠性.

注1:Simens软件包通常被用来做软件测试、错误定位和不变量计算的开源程序包,所以我们用它来做基于不变量的软件可靠性的评价.但它只是针对序列化程序,并没有并发程序.今后的一个研究工作就是针对并发程序来验证我们的方法.并发结构可以给我们带来大规模的程序,我们将在此基础上研究我们方法的稳定性与适应性.

在过去的几十年里,有许多关于可靠性模型的研究.总的来说,这些模型大致可以分为软件可靠性增长模型(software reliability growth models,简称SRGMs)和基于架构的模型.

软件可靠性增长模型SRGMs^{[1, 2, 3, 4, 5, 6, 7, 8, 9]}是时间域模型,它们可以用来估计软件可靠性和残留故障数量.这些模型首先假设测试是按照给定的操作剖面执行的^[10],然后,通过在测试阶段的记录的故障历史来预测软件程序的行为.基于架构的可靠性模型^{[11, 12, 13, 14, 15, 16, 17, 18]}又可以分为两类,即,测试阶段的架构^{[11, 12, 16, 17, 18]}和设计阶段的架构^{[13, 14, 15]}.前者只有程序代码可用,通过执行大量的测试来获取轨迹的数据,从而根据这些数据来决定软件系统的架构.利用在覆盖测试中获得的轨迹信息,可以构建程序的架构,如离散时间马尔科夫链^[12]、连续时间马尔科夫链^[16]以及半马尔科夫过程^[11].构件的失效行为可以用泊松过程或基于覆盖测试和故障密度的时间独立失效率来建模,在这种情况下,覆盖测试和单元测试在决定所有信息过程中起重要作用.后者事先已经定义了构件以及构件之间的相关性.每个构件的可靠性依赖于操作剖面和其在系统中的位置,系统可靠性的计算等价于构件执行轨迹的可靠性,其中,构件执行轨迹可看作是一系列构件的执行,而构件执行轨迹的可靠性又等于该轨迹上所有构件可靠性的乘积.轨迹可靠性问题还可以转化为基于构件的问题^[13].在这种情况下,可靠性的计算需要假设构件的失效是相互独立的以及接口的可靠性为1.在无记忆程序中,构件运行的独立性是可接受的;但是对其他程序来说,该假设无法满足^[15].特别地,当某个构件被循环执行时,该构件多次的执行是不独立的.

失效数据的来源广、获取技术多^[21],人们可以从历史版本或者类似软件中获得失效数据,此时我们无需拥有具体的需求的软件;在设计阶段,可以从需求文档、UML图和项目计划书中获得相关信息和数据;通过测试获取相应的失效数据;用户反馈,例如故障报告、修改需求等,也可以作为获得数据的来源.通过测试来获取数据是其中使用最广泛的一种方法.测试阶段根据模型的不同主要收集两类不同的失效数据:

· 一是给定测试用例,收集失效的测试用例数^[19];

· 二是给定测试环境,运行软件一段时间,收集在这段时间内的失效次数和失效间隔时间^{[33, 34]}.

文献^[23]归纳了用来获得失效数据的各种不同的测试方法.但是这些失效数据仅仅是软件测试时间内的输入/输出信息,而并没有考虑程序内部的信息.而软件的可靠性必然是由其内部信息,包括动态行为和内部结构来决定的,因此,根据这些失效数据算出来的可靠性并不十分准确.

程序不变量是通过收集软件的动态行为获取能够反映其内部信息的数据,因此它能够反映软件内部行为,比仅仅考虑程序的输入/输出的数据携带更多的信息,似乎可以作为更好的失效数据来源.然而对这方面的研究却还不多,仅有一些尝试.Pietrantuono通过程序不变量来监测和预测在线软件可靠性^[25];丁佐华等人通过程序不变量来计算服务组合的在线可靠性计算^[26],但是这些工作并没有说明用不变量来计算可靠性的可行性.

本文通过实验来说明我们可以通过程序不变量来计算可靠性:其一,在同一测试方法下,不变量计算出的可靠性和现有方法计算出的可靠性相差不大;其二,在不同测试方法下,不变量计算出的可靠性波动较小,更接近软件的实际可靠性.从不变量的角度来刻画软件可靠性,使我们对软件的整体行为和软件可靠性有更深刻的认识,有利于软件可靠性的评估和预测.

接下来的工作是:

1) 针对不变量之间的相关性:如果不好的不变量之间存在相关性,会增加失效数据,影响计算结果.我们应尽量去掉这种相关性,使得剩下的不变量尽可能独立.一种办法是建立数据流的依赖图;

2) 针对假性测试用例:有些正确的测试用例会产生错误的不变量.在这种情况下,我们就丢失了失效数据.如果假性测试用例较多,那样计算出来的结果就不准确.为了解决这种情况,我们需要对测试用例的结果建立频谱矩阵,基于频谱矩阵去除掉这些测试用例;

3) 运用更多的测试方法来计算软件可靠性,进一步验证测试方法对软件可靠性的影响;

4) 在实际应用中,我们并不知道正确的程序,这样我们就不能通过比较来获得不好的不变量,而必须通过一定的方法,根据已有的测试用例信息和已获得的不变量信息来确定不好的不变量,这将是我们接下来要解决的关键问题之一.

致谢 我们向对本文工作给予支持和建议的同行,尤其是北京大学高可信软件技术教育部重点实验室金芝教授表示感谢.