不完美排错SRGM研究

张策　崔刚　孟凡超　刘宏伟

摘 要：软件可靠性增长模型SRGM可对测试与运行阶段的可靠性进行度量、预测与保证。不完美排错SRGM能够更加准确地建模实际测试过程，获得了广泛研究。首先介绍了随机过程类模型中的NHPP基本概念与假设。接着，从三个阶段全面回顾了不完美排错研究历程。进一步，给出了若干典型的不完美排错SRGM的建模与累计故障检测函数的求解形式。最后将从排错的不完全性，引入新故障的角度建立的不完美排错模型：IID-SRGM与现有的模型进行比较，优于其它模型。

关键词：软件可靠性；非齐次泊松过程；软件可靠性增长模型；不完美排错

中图分类号：TP311 文献标识号：A 文章编号：2095-2163（2014）02-

Study of Imperfect Debugging Dependent SRGM

ZHANG Ce1，2， CUI Gang1， MENG Fanchao2， LIU Hongwei1

（1 School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China；2 School of Computer Science and Technology， Harbin Institute of Technology at Weihai， Shandong Weihai 264209， China）

Abstract： Software reliability growth model can be used to measure， predict and ensure reliability in testing and operation stage. Imperfect debugging （ID） dependent SRGM can describe real testing process in detail and has obtained a wide range of research. First， the basic concepts and assumptions of Non-Homogeneous Poisson Process based on stochastic process are discussed. From three stages， ID research is overviewed completely. Furthermore， modelling process of ID dependent SRGM and the solution of cumulative fault detection function are presented. Finally， the special ID model： IID-SRGM considering incomplete debugging and introduction of new faults is compared with the others and performs better.

Keywords： Software Reliability； Non-Homogeneous Poisson Process； SRGM； Imperfect Debugging

0 引言

SRGMs（Software Reliability Growth Models）主要应用在软件测试阶段和操作运行阶段，其通过获得的历史数据，借助不同的建模手段，建立用以描述测试与运行阶段故障检测、排除、资源分配等相关的数学表达式，可帮助软件工程师提高可靠性的度量与预测能力的准确性[1]。

实际的软件开发过程，尤其对于大规模复杂系统，被检测到的故障要经历报告、诊断、改正与验证环节[2，3]。由于其高复杂性，排错人员的经验及熟练度差异，包括排错环境等因素则使得故障排除过程不可忽略[4]，排错过程是不完美的，引入新故障的可能性也是存在的。基于此，不完美排错的提出与应用，即将使得软件可靠性的分析更加贴近了实际情况，因而也随之得到了广泛研究。有些文献又进一步指出[5-9]，故障排除过程是不彻底的，即已检测到的故障不可能都被修复完成；另一方面，进行故障排除后，又可能引进了新的故障。例如，在回归测试中，其关联性就会导致在修复某个故障时可能将引入一个或者更多的新故障，因此对于排错中引入新故障现象，就必须给予更多关注和高度重视。同时，不完美排错又存在多种情况，有必要对其进行形式化的表示，以利于将不完全排错考虑到软件可靠性建模中，使所建立的模型更加贴合实际的软件测试过程，并取得完备效果。

1 NHPP介绍与基本的公共假设

在SRGM的众多分类中，有一类是随机过程类模型，其中以NHPP（Non-Homogeneous Poisson Process）非齐次泊松分布模型为典型代表。

假定计数过程{N（t）， t≥0}满足NHPP，其强度函数为 ，t≥0，且N（t）是期望值为m（t）的泊松分布。下面给出关于NHPP的基本假设[10-12]：

（1）失效过程具有独立增量特性：在（t， t+Δt）内失效发生的个数仅取决于当前时间t与间隔Δt；

（2）在（t， t+Δt）内失效发生的个数的概率满足：

（1）

上式表明 内失效出现一次的概率近似为 ；出现两次的概率为 ；不发生的概率近似为 ； 是无穷小量，满足 。

（3） 计数的初始满足N（0）=0。

在此基础上，可以得到：

（2）

（3）

（4）

在测试过程中，假定t时刻失效发生，则（t， t+x）内软件的可靠性为 。可见，NHPP模型的关键是确定合适的m（t）。基于m（t），软件工程师即可对测试过程进行合理的管控，获得预期的目标。

2不完美排错研究发展历程

三十几年来，研究人员对不完美排错的研究大致经历了如下几个阶段：

（1）阶段1：提出阶段 最早的不完美排错可以追溯到1985年[13]，Goel是第一个提出不完美排错的概念，并在J-M模型[14]中首次给出了不完美排错概率的概念。随后，在Obha与Chou提出的模型中[15]，进一步提出软件排错中会引入新故障，并在经典的G-O模型上进行了验证，并称之为不完美排错。但却只是从引入新故障的角度来分析的，而并未考虑到故障排除效率[16]，或者说是排错的不完全性。以此为契机，即相继提出了各种不完美排错模型。

（2）阶段2：从软件中总的故障数量a（t）变化的角度来分析 另一方面，文献 [2，17-21] 等从软件排错过程的软件中总故障个数a（t）的变化情况来进行分析，指出a（t）存在着两种情况：

① 与传统的完美排错相同，a（t）=a，也就是总故障内容并不发生改变。由此可知，并非所有已检测到的故障均能够获得排除，并称此为不完美排错。显然，在本质上，这是一种不完全排错情况。最早提出不完全排错的是Kapur[22]，在经典的G-O模型中引入不完美排错来建立SRGM。相关的不完全排错研究还有文献[23，24]，该研究结果表明排错可以立即完成，花费时间可以忽略，显然这与实际情形并不一致。失效发生后，需要进行错误的定位、识别、隔离与修复等环节，任何进行时间忽略的假设都是与现实并不相符的。按常规符号进行标记，可令m（t）表示[0， t]内检测到的故障个数，x（t）表示[0， t]内改正掉的故障，再令 ，则称之为故障减少系数[25]或故障移除率[26]这种不完全排错也可以通过下式进行描述：

a.若 ，则表示相应的SRGM是完美排错模型[27]；

b.若 ，则表示相应的SRGM是不完全排错模型[28]。

显然FRF值越靠近于1，即表明故障已完全排除的程度越高。

② a（t）会随着测试的进行有所增加[19，29-32]，这是考虑到排错过程中引入新故障的缘故，并将其称为引入新故障现象。显然，这是符合实际情况的。软件排错应由软件工程师来实施和完成，是一种复杂的认知活动CCA[20]，因此故障修复不仅存在不完全现象，还存在着引入新故障的可能。Pham[33]依据测试过程中测试人员的自学习能力，提出了S形故障检测率的不完美排错模型。当然，a（t）的表示形式有多种，现有研究中，对软件中总的故障个数a（t）即进行了如下几种函数形式的设定：

① a（t）=a，a（t）是常量，表示软件测试过程中，总的故障个数是固定的，因此无法描述软件测试过程中的引入新故障这种不完美现象；

② a（t）=a?（1+α?t）， [34]， [34]等，是随测试时间t的线性增函数[19，35，36]，有时这很可能与软件自身的特点不一致；

③ a（t） = a +α?m（t），则是随检测故障数量的线性增函数[20，37]，这虽比②中的描述要精细些，但却仍未真实地表现出a（t）随改正的故障数量的本质变化关系。

显然，仅仅从[0， t]内的软件的总故障数a（t）角度来描述不完美排错是不充分的，无法对不完美排错的全部（多种）各类情况进行完整描述。

（3）阶段3：不完全排错与引入新故障 在其后提出的SRGMs中，即有很多已将不完美排错与引入新故障都考虑到模型中的研究成果，这就使得模型对测试过程的描述更加准确[5-9，16，26，38-41]。文献[16]与[19]即从故障移除效率的不完美性，以及排错中引入新故障的角度，综合考虑了故障排错效率和故障引入率，使得所建立的模型更为有效可靠。与之相似，文献[42]也从排错的不完全性与引入新故障的角度来建立SRGM。

3 不完美排错模型SRGM建模比较

3.1 不完美排错建模过程比较

除m（t）外，现有SRGMs中还用到了如下的参函数或参变量，具体如表1所示。

失效率函数，t时刻单位时间内软件失效个数

各种不完美排错模型的主要差异是其通过建模得到的m（t）也各不相同。下面，表2给出几个典型的不完美排错的建模过程，及其所得到的m（t）。

由表2可以看出，不同的SRGM由于在软件测试过程中对排错认识与理解的差异，使得建模的过程也随之不同，这就会导致求得的m（t）复杂各异。

3.2 Ohba-Chou模型解释

现有的众多不完美排错模型均是基于较多的假设，表2中列出的不同模型的差异主要就起因于研究中所做假设的不同，此处即以Ohba-Chou模型为例进行阐述。在建立Ohba-Chou模型的过程中，是基于下面的假设：

（1） 故障排除过程满足NHPP；

（2） 在（t， t+ ）内检测到的故障数量m（t）与当前软件中尚未检测的故障成正比，比例函数为b；

（3） 被检测到的故障可获得完全排除；

（4） 故障修改中存在引入新故障现象，新故障引入的概率与t时刻检测的故障m（t）成正比，比例函数为r。

在以上假设的基础上，可以给出下面的微分方程组：

（5）

显然，Ohba-Chou模型可解析为故障修复100%成功，但会导致新故障的引入。与以上分析相似，即可、能对表2中各个模型的建立过程做到轻松掌握和理解。

4 不完美排错模型比较

在本文前期的研究工作中[44]，已经从排错的不完全性与引入新故障角度建立了更为全面的不完美排错模型，如表2中IID-SRGM所示。可以证明，ID-SRGM能够涵盖现有的几个典型模型，下面即给出表2中各个模型的差异性比较。

表3给出了表2中各个模型在比较标准上的差异。经过比较得知，本文提出的模型（IID-SRGM）在MSE与Variance上最小，同时R-square最接近于1，而IID-SRGM是最优的。

表3 不同模型的拟合结果值

Tab.3 Fitting results of the models

比较标准 Hou 模型 Pham 模型 Ohba-Chou模型 Xie模型 IID-SRGM

MSE 99.8644 106.7352 99.8644 120.6461 82.5242

R-square 0.9618 0.9522 0.9618 0.9927 0.9949

Variance 10.1828 10.5598 10.1828 11.0524 9.1409

这一结果可作如下解释，相较于表2中的其它模型，IID-SRGM对不完美排错的描述更为细致，并且与软件测试的实际更相符合。

在比较各个模型的预测能力上，画出了其相应的RE曲线，如图1所示。由图1可得，本文所提出的模型能够快速趋近于0，并且偏差较小。此外，在刚开始的一段时间内IID-SRGM出现了一小段的“突起”，这主要是因为在预测过程中，用于参数拟合的数据较少所引起的误差，但随着用于拟合数据量的迅速变大，IID-SRGM的预测能力显著增强，达到最优。

图1 各个模型RE曲线

Fig.1 RE curves of the models

综上所述，可以认为所提出的不完美排错模型IID-SRGM相较于其它模型，能够更加准确地描述实际的软件测试过程。

5 结束语

不完美排错是对实际排错过程的一种近似。显然，在不同的测试环境下，由于多种因素的影响，所建立的不完美排错SRGM差异较大。本文对随机过程中，基于NHPP类的不完美排错模型SRGM进行了全面的介绍，给出了其建模的基本过程，并将现有的较为典型的不完美排错模型进行了比较与分析。实际上，在后续研究中，不完美排错的研究范畴应该进一步拓宽，使之更加贴近真实的软件测试过程。

参考文献：

[1] ALMERING V， van GENUCHTEN M， CLOUDT G， et al. Using software reliability growth models in practice[J]. IEEE Software， 2007， 24（6）： 82-88.

[2] KAPUR P K， PHAM H， ANAND S， et al. A Unified Approach for developing software reliability growth models in the presence of imperfect debugging and error generation[J]. IEEE Trans on Reliability， 2011， 60（1）： 331-340.

[3] WU Y P， HU Q P， XIE M， et al.， Modeling and analysis of software fault detection and correction process by considering time dependency[J]. IEEE Trans on Reliability， 2007， 56（4）： 629-642.

[4] XIE M， HU Q P， WU Y P， et al， A study of the modeling and analysis of software fault-detection and fault-correction processes[J]. Quality and Reliability Engineering International， 2007，23（4）：459-470.

[5] GUPTA D， KAPUR R， JHA P C. Bicriterion release policy for a discrete software reliability growth model with imperfect fault debugging and fault generation[J]. Communications in Dependability and Quality Management， 2007，10（3）： 5-31.

[6] SINGH O， KAPUR R， SINGH J. Considering the effect of learning with two types of imperfect debugging in software reliability growth modeling[J]. Communications in Dependability and Quality Management， 2010， 13（4）： 29-39.

[7] KUMAR D， KAPUR R， SEHGAL V K， JHA P C. On the development of software reliability growth models with two types of imperfect debugging[J]. Communications in Dependability and Quality Management， 2007， 10（3）： 105-122.

[8] XIE M， YANG B. A study of the effect of imperfect debugging on software development cost[J]. IEEE Trans on Software Engineering， 2003， 29（5）： 471-473.

[9] KAPUR P K， SHATNAWI O， YADAVALLI V S S. A software fault classification model[J]. South African Computer Journal， 2004， 33： 1-9.

[10] HOANG PHAM. A software cost model with imperfect debugging， random life cycle and penalty cost[J]. International Journal of System Science， 1996， 27（5）： 455-463

[11] PRINCE WILLIAMS D R. Study of the warranty cost model for software reliability with an imperfect debugging phenomenon， 2007， 15（3）： 369-381.

[12] ZHANG Xuemei， PHAM H. A software cost model with error removal times and risk costs[J]. International Journal of System Science， 1998， 29（4）： 435-442.

[13] GOEL A L. Software reliability models： assumption， limitation and applicability[J]. IEEE Transactions on Software Engineering， 1985， 11（21）： 1411-1423.

[14] JELINSKI Z， MORANDA P B， Software Reliability Research[J]. Statistical Computer Performance Evaluation， 1972： 465-497.

[15] OHBA M， CHOU X M. Does imperfect debugging effect software reliability growth[C]//proceeding of 11th International Conference of Software Engineering， 1989： 237-244.

[16] ZHANG X M， TENG X L， PHAM H. Considering fault removal efficiency in software reliability assessment[J]. IEEE Trans. on Systems， Man， and Cybernetics： Systems and Humans， 2003， 33（1）： 114?120.

[17] YADAVALLI V S S， AGGARWAL A G， KAPUR P K， et al. Unified framework for developing testing effort dependent software reliability growth models with change point and imperfect debugging[C]//Proceedings of the 4th National Conference， INDIACom-2010：

[18] KAPUR P K， SHATNAWI O， AGGARWAL A G， et al. Unified Framework for Development Testing Effort Dependent Software Reliability Growth Models[J]. WSEAS TRANSACTIONS on SYSTEMS， 2009， 8（4）： 521-531.

[19] YAMADA S， TOKUNO K， OSAKI S. Imperfect debugging models with fault introduction rate for software reliability assessment[J]. International Journal of System Science， 1992， 23（12）： 2241-2252.

[20] HUANG C Y， KUO S Y， LYU M R. An assessment of testing-effort dependent software reliability growth models[J]. IEEE Trans on Reliability， 2007， 56（2）： 198-211.

[21] HUANG C Y， LYU M R. Optimal release time for software systems considering cost， testing-effort， and test efficiency[J]. IEEE Trans on Reliability， 2005， 54（4）： 583-591.

[22] KAPUR P K， GARG R B. A software reliability growth model for an error removal Phenomenon[J]. Software Engineering Journal， 1992， 7： 291-294.

[23] LO J H， HUANG C Y. Incorporating imperfect debugging into software fault correction process[C]// Proceedings of the IEEE Region 10 Annual International Conference （TENCON 2004）， Chiang Mai， Thailand， Nov. 2004： 326-329.

[24] GOSEVA-POPSTOJANOVA K， TRIVEDI K. Failure correlation in software reliability models[J]. IEEE Trans on Reliability， 2000， 49（1）： 37-48.

[25] HSU C J， HUANG C Y， CHANG J R. Enhancing software reliability modeling and prediction through the introduction of time-variable fault reduction factor[J]. Applied Mathematical Modeling， 2011， 35： 506-521.

[26] KHATRI S K， KAPUR P K， JOHRI P. Flexible discrete software reliability growth model for distributed environment incorporating two type of imperfect debugging[C]//2012 Second International Conference on Advanced Computing & Communication Technologies， 2012： 57-63.

[27] GOEL A L， OKUMOTO K. Time-dependent error-detection rate model for software reliability and other performance measures[J]. IEEE Trans on Reliability， 1979， R-28（3）： 206-211.

[28] 刘宏伟， 杨孝宗， 岳晓光， 等. 一个考虑多种排错延迟的NHPP类软件可靠性增长模型[J]. 计算机工程与应用， 2004， 40（30）： 11-14.

[29] PHAM H， ZHANG X. An NHPP software reliability models and its comparison[J]. International Journal of Reliability， Quality and Safety Engineer， 1997， 4（3）： 269-282.

[30] KAPUR P K， GARG R B， KUMAR S. Contributions to hardware and software reliability[J]. World Scientific， 1999.

[31] KAPUR P K， YOUNES S. Modelling an imperfect debugging phenomenon in software reliability[J]. Microelectronics reliability， 1996， 36（5）： 645-650.

[32] PHAM H. A software cost model with imperfect debugging random life cycle and penalty cost[J]. International Journal of Systems Science， 1996， 27（5）： 455-463.

[33] PHAM H， NORDMANN L， ZHANG Z. A General Imperfect-software-debugging Model with S-shaped fault-detection Rate[J]. IEEE Trans on Reliability， 1999，48（2）： 169-175.

[34] PHAM H. System Software Reliability[M]， Springer； 1st Edition， 2006.

[35] 谢景燕， 安金霞， 朱纪洪. 考虑不完美排错情况的NHPP类软件可靠性增长模型[J]. 软件学报， 2010， 21（5）： 942-949.

[36] PHAM H. An imperfect-debugging fault-detection dependent-parameter software[J]. International Journal of Automation and Computing， 2007， 4（4）： 325-328.

[37] AHAMD N， KHAN M G M， RAFI L S. A study of testing-effort dependent inflection s-shaped software reliability growth models with imperfect debugging[J]. International Journal of Quality & Reliability Management， 2010， 27（1）： 89-110.

[38] KAPUR P K， KUMAR D， GUPTA A， JHA P C. On how to model software reliability growth in the presence of imperfect debugging and error generation[C]//Proc， of the 2nd Intl Conference on Reliability and Safety Engineering， Chennai， India， 2006： 515-523.

[39] BODHISUWAN W， ZEEPHONGSEKUL P. Asymptotic properties of a statistical model in software reliability with imperfect debugging and introduction rate[C]//Proceedings of the 9th ISSAT International Conference on Reliability and Quality in Design， Honolulu， Hawaii， 2003.

[40] AMMANN P E， BRILLIANT S S， KNIGHT J C. The Effect of Imperfect Error Detection on Reliability Assessment via Life Testing[J]. IEEE Trans. Software Engineering， 1994， 20（2）： 142-148.

[41] GOSWAMI D N， JHA P C， PRASHANT J， et al. Software reliability growth model for distributed environment incorporating two types of imperfect debugging[C]//Proceedings of 3rd International Conference on Reliability and Safety Engineering. 2007： 308-319.

[42] KAPUR P K， GUPTA D， GUPTA A， et al.， Effect of introduction of fault and imperfect debugging on release time[J]. Ration mathematical， 2008， 18： 62-90.

[43] HOU C Y， CUI G， LIU H W， et al， A hybrid queueing model with imperfect debugging for component software reliability analysis[J]. Intelligent Automation and Soft Computing， 17（5）： 559-570， 2011.

[44] ZHANG C， CUI G， LIU H W， et al.， Unified and flexible SRGM framework incorporating two types of imperfect debugging[J]. Journal of Convergence Information Technology， 2013， 8（8）： 751-758.