不完美排錯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.