基于明考斯基最優(yōu)距離的不完美排錯(cuò)SRGM決策機(jī)制

張 策, 王金勇, 徐早輝, 江文倩, 白 睿, 李文毓, 王建遠(yuǎn)

(1.哈爾濱工業(yè)大學(xué)(威海) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 山東 威海 264209; 2.山西大學(xué) 自動(dòng)化與 軟件學(xué)院 山西 太原 030006; 3.中國(guó)科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心 北京 100083; 4.華為技術(shù)有限公司 南京研究所 江蘇 南京 210012; 5.哈爾濱工業(yè)大學(xué) 計(jì)算學(xué)部 黑龍江 哈爾濱 150006; 6.華為技術(shù)有限公司 蘇州研發(fā)中心 江蘇 蘇州 215028)

0 引言

為了定量化地提高軟件系統(tǒng)的可靠性,軟件可靠性增長(zhǎng)模型(software reliability growth model,SRGM)得到了深入的研究?；趯?duì)故障檢測(cè)至修復(fù)過程的不同假設(shè),目前所建立的可靠性模型有數(shù)百種,但并不存在一個(gè)能夠適用于所有失效數(shù)據(jù)集和評(píng)測(cè)標(biāo)準(zhǔn)的模型。因此,如何評(píng)測(cè)SRGM的性能優(yōu)劣從而選擇合適的SRGM,成為當(dāng)前研究中亟待解決的問題。

在SRGM的評(píng)價(jià)與選擇機(jī)制上,文獻(xiàn)[1]基于歐幾里得距離進(jìn)行SRGM的最優(yōu)選擇,通過計(jì)算模型與理想解之間的最短距離來確定最優(yōu)者,但其缺少對(duì)更多評(píng)測(cè)性能標(biāo)準(zhǔn)的考慮。文獻(xiàn)[2]從決策軟件發(fā)布角度提出了在工程實(shí)際應(yīng)用中選擇SRGM的方法,其通過評(píng)價(jià)模型預(yù)測(cè)軟件中剩余故障的準(zhǔn)確性來進(jìn)行SRGM的選擇與評(píng)判。在多屬性決策[3]方面,文獻(xiàn)[4]通過MSE擬合標(biāo)準(zhǔn)和自定義的預(yù)測(cè)指標(biāo)對(duì)SRGM進(jìn)行評(píng)價(jià),并給出了具體的SRGM選擇執(zhí)行流程。就整體而言,已有的研究?jī)H孤立地比較SRGM的擬合性能,未考慮不同標(biāo)準(zhǔn)重要性的差異,也沒有考慮測(cè)試過程中由于測(cè)試環(huán)境和測(cè)試策略的改變而引發(fā)的各種實(shí)際問題。由于軟件公司對(duì)失效數(shù)據(jù)集的發(fā)布不具備及時(shí)性,發(fā)布的信息往往有限(通常只有測(cè)試時(shí)間、失效故障數(shù)量以及測(cè)試工作量[5-6]等),使得科研人員對(duì)基于失效數(shù)據(jù)集的SRGM研究具有被動(dòng)性、滯后性和片面性。

筆者在前期工作中提出了統(tǒng)一的與不完美排錯(cuò)相關(guān)的SRGM[7],研究了不完美排錯(cuò)環(huán)境下的軟件最優(yōu)發(fā)布問題[8],并分析了不同的SRGM[9-10]性能存在差異的原因。本文從矩陣分析的角度對(duì)SRGM的性能評(píng)估與選擇問題進(jìn)行形式化描述,提出成本受限下的雙最優(yōu)化排序方法,建立基于明考斯基距離的SRGM決策機(jī)制,并給出SRGM間的性能偏序關(guān)系。在公開發(fā)表的真實(shí)失效數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明了所提出方法的有效性,可以為模型決策提供定量化的參考。

1 真實(shí)軟件測(cè)試過程與可靠性模型

真實(shí)軟件測(cè)試過程描述如圖1所示?？梢钥闯?真實(shí)的測(cè)試流程是執(zhí)行測(cè)試策略、發(fā)現(xiàn)故障、分析原因、排錯(cuò)、檢查,之后再執(zhí)行測(cè)試策略的周期性過程。

隨著測(cè)試的執(zhí)行,故障不斷地被檢測(cè)和修復(fù),從而使得軟件可靠性得以逐漸提升。從研究的視角來看,科研人員希望能夠定量地評(píng)定該過程結(jié)束時(shí)系統(tǒng)的可靠性。為此,需要從數(shù)學(xué)定量分析的角度對(duì)測(cè)試過程進(jìn)行建模,得到主要變量之間的數(shù)值關(guān)系,為可靠性增長(zhǎng)找到研究的突破口。相比于完美排錯(cuò),不完美排錯(cuò)[11-12]是針對(duì)更加真實(shí)的測(cè)試過程的可靠性研究,包含了多種測(cè)試過程中的實(shí)際因素。在當(dāng)前研究中,由于各個(gè)模型所做的假設(shè)有所不同,可以得到多種類型的可靠性模型。因此,需要選擇出與實(shí)際工程特征相接近的可靠性模型作為預(yù)選集合。

圖1 真實(shí)軟件測(cè)試過程描述Figure 1 Description of the real software testing process

2 不完美排錯(cuò)軟件可靠性模型決策

2.1 SRGM評(píng)價(jià)問題的形式化描述

設(shè)有K個(gè)SRGM模型構(gòu)成集合M,M={Mi|1≤i≤K}={M1,M2,…,MK}, 其中模型Mi由擬合與預(yù)測(cè)兩大類指標(biāo)構(gòu)成。

定義1評(píng)測(cè)指標(biāo)。模型Mi有N個(gè)擬合指標(biāo)Fi={fij|1≤j≤N},L個(gè)預(yù)測(cè)指標(biāo)Qi={qik|1≤k≤L}, 1≤i≤K,這些評(píng)測(cè)指標(biāo)是由K個(gè)模型在指定失效數(shù)據(jù)集上進(jìn)行參數(shù)擬合后計(jì)算得到的。

K個(gè)SRGM模型的擬合標(biāo)準(zhǔn)值和預(yù)測(cè)標(biāo)準(zhǔn)值構(gòu)成了評(píng)測(cè)決策矩陣D,

(1)

D是包含N+L個(gè)屬性、K個(gè)方案的決策矩陣。為便于計(jì)算以及更加清晰地呈現(xiàn)模型間的數(shù)值差異,需要對(duì)D中的元素進(jìn)行標(biāo)準(zhǔn)化處理。

7個(gè)擬合評(píng)測(cè)標(biāo)準(zhǔn)為MSE、MEOP、Variation、RMS-PE、TS、BMMRE和R-square,將這些標(biāo)準(zhǔn)值變換為[0, 1] 區(qū)間內(nèi)正向增長(zhǎng)的無量綱數(shù)值。

對(duì)于評(píng)測(cè)標(biāo)準(zhǔn)MSE、MEOP、Variation、RMS-PE、TS、BMMRE,

對(duì)于評(píng)測(cè)標(biāo)準(zhǔn)R-square,

式中:1≤j≤N+L。

對(duì)得到的評(píng)測(cè)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理,

(2)

至此,可以得到標(biāo)準(zhǔn)化矩陣R,

(3)

(4)

2.2 考慮雙最優(yōu)化距離的SRGM決策

基于式(4)的描述,可將K個(gè)模型抽象為K個(gè)節(jié)點(diǎn)N1,N2,…,NK。為了評(píng)測(cè)K個(gè)模型的性能差異,可以采用基于距離的SRGM決策方法,如圖2所示。其中,N0節(jié)點(diǎn)表示理想解節(jié)點(diǎn),是基于某種標(biāo)準(zhǔn)構(gòu)造的用于衡量K個(gè)節(jié)點(diǎn)性能的節(jié)點(diǎn),因此被標(biāo)記為虛擬節(jié)點(diǎn)N0。

圖2 基于距離的SRGM決策Figure 2 SRGM decision based on distance

采用明考斯基距離(Minkowski distance,MD)函數(shù)來度量不同模型(即對(duì)象)間的差異,

dk(i,j)=

(5)

式中:i=(xi1,xi2, …,xip)和j=(xj1,xj2, …,xjp) 是兩個(gè)p維的數(shù)據(jù)對(duì)象;k是一個(gè)正整數(shù),表示k重度量距離。

顯然,明考斯基距離滿足如下基本性質(zhì):d(i,j)≥0,d(i,i)=0,d(i,j)=d(j,i),d(i,j)≤d(i,k)+d(k,j)。這使得明考斯基距離可以用來度量不同節(jié)點(diǎn)間的差異。

當(dāng)k=1時(shí),d稱為曼哈坦距離;當(dāng)k=2時(shí),d稱為歐幾里德距離。這里,考慮N+L個(gè)評(píng)測(cè)屬性,令k=N+L,表示N+L維的距離度量。通常,在度量某節(jié)點(diǎn)的性能時(shí),是通過計(jì)算該節(jié)點(diǎn)與最優(yōu)評(píng)測(cè)標(biāo)準(zhǔn)構(gòu)成的虛擬節(jié)點(diǎn)之間的距離來實(shí)施的,但這種評(píng)測(cè)方法不能保證一定有效。這是由于在多維空間中每個(gè)模型的標(biāo)準(zhǔn)所占有的權(quán)重并不一樣,使得此多維空間不具備傳統(tǒng)二維空間與三維空間的對(duì)稱性,從而導(dǎo)致距離最優(yōu)評(píng)測(cè)標(biāo)準(zhǔn)構(gòu)成的虛擬節(jié)點(diǎn)最近的節(jié)點(diǎn)不一定距離最差標(biāo)準(zhǔn)構(gòu)成的虛擬節(jié)點(diǎn)最遠(yuǎn)。為此,提出了雙最優(yōu)化排序方法(MMIMMD),用于度量不同模型(對(duì)象)間的差異,

(6)

式中:Np和Nq分別表示正向最優(yōu)節(jié)點(diǎn)和負(fù)向最差節(jié)點(diǎn),由評(píng)測(cè)標(biāo)準(zhǔn)中最優(yōu)值和最差值的k維數(shù)據(jù)構(gòu)成,即Np=(x1p,x2p,…,xkp),Nq=(x1q,x2q,…,xkq),其中:xip=max{xij|1≤j≤k},xiq=min{xij|1≤j≤k}, 1≤i≤K。

顯然,D(Ni,Np)越小,表示節(jié)點(diǎn)Ni距離正向最優(yōu)節(jié)點(diǎn)Np越近,評(píng)測(cè)模型性能的指標(biāo)趨向較好;D(Ni,Nq)越大,表示節(jié)點(diǎn)Ni距離負(fù)向最差節(jié)點(diǎn)Nq越遠(yuǎn),評(píng)測(cè)模型性能的指標(biāo)趨向較好。

D(Ni,Np)和D(Ni,Nq)均采用明考斯基距離公式來計(jì)算,

1≤i≤K;

(7)

1≤i≤K。

(8)

D(Ni,Np)和D(Ni,Nq)均包含t時(shí)刻累積檢測(cè)的故障數(shù)量表達(dá)式m(t),因此m(t)是可靠性模型研究的關(guān)鍵。

3 數(shù)值算例評(píng)價(jià)

3.1 SRGM實(shí)例與數(shù)據(jù)集

選取8個(gè)典型的不完美排錯(cuò)SRGM進(jìn)行實(shí)驗(yàn)和評(píng)價(jià)分析,具體情況如表1所示。

表1 8個(gè)典型的不完美排錯(cuò)SRGMTable 1 Eight typical imperfect debugging SRGM

可靠性模型的驗(yàn)證集由公開發(fā)表的真實(shí)失效數(shù)據(jù)集來完成,這里選擇4個(gè)實(shí)際計(jì)算機(jī)應(yīng)用系統(tǒng)測(cè)試過程中記錄的失效數(shù)據(jù)集DS1～DS4[18-21]來進(jìn)行實(shí)驗(yàn),這4個(gè)數(shù)據(jù)集已被廣泛用來驗(yàn)證SRGM的性能。

3.2 SRGM的擬合曲線和RE預(yù)測(cè)曲線

將表1中的8個(gè)模型在4個(gè)數(shù)據(jù)集上進(jìn)行參數(shù)擬合,基于擬合的參數(shù)數(shù)值得到模型的m(t)表達(dá)式,用以估計(jì)模型的性能表現(xiàn)。圖3為不同模型的擬合度量曲線,展現(xiàn)了模型與真實(shí)失效數(shù)據(jù)集的接近程度。圖4為不同模型的RE預(yù)測(cè)曲線,展現(xiàn)了模型對(duì)未來失效數(shù)據(jù)的預(yù)測(cè)能力,曲線越接近于零線表明其預(yù)測(cè)性能越優(yōu)。

從圖3可以看出,在不同的失效數(shù)據(jù)集上,部分模型曲線與真實(shí)的失效數(shù)據(jù)曲線發(fā)生較大程度重合,表明擬合性能較好;另一部分模型曲線則發(fā)生較大偏離,表明擬合性能并不理想。例如,在DS1上,SRGM1和SRGM6出現(xiàn)了明顯偏差;在DS2上,SRGM1和SRGM4出現(xiàn)了明顯偏差。

圖3 不同模型的擬合度量曲線Figure 3 Fit metric curves of different models

從圖4可以看出,不同模型的RE曲線或正偏向或負(fù)偏向趨近于零線,難以區(qū)分模型間的RE曲線性能。在DS3和DS4上,RE曲線都是在第16周之前發(fā)生較大幅度的波動(dòng)并逐漸收斂,但相互之間的性能并不容易直接區(qū)分。

3.3 數(shù)據(jù)處理與結(jié)果分析

3.3.1數(shù)據(jù)處理 對(duì)于各模型在不同失效數(shù)據(jù)集上的性能指標(biāo)進(jìn)行歸一化處理,形成[0,1]區(qū)間內(nèi)的數(shù)值(由于篇幅原因,更多數(shù)據(jù)不再列出)。

3.3.2結(jié)果分析

1)權(quán)重設(shè)置

目前對(duì)可靠性模型的評(píng)測(cè)主要從擬合與預(yù)測(cè)兩個(gè)方面進(jìn)行,二者的重要性基本相同,故將擬合與預(yù)測(cè)的權(quán)重均設(shè)置為0.5。

在擬合指標(biāo)上,相比MEOP、TS、RMS-PE和BMMRE標(biāo)準(zhǔn),MSE、R-square和Variation標(biāo)準(zhǔn)被更廣泛地用來衡量模型的擬合性能。因此,將后三者權(quán)重設(shè)定為前四者的兩倍以示區(qū)別。預(yù)測(cè)指標(biāo)RE權(quán)重設(shè)置與7個(gè)擬合指標(biāo)權(quán)重相同。擬合與預(yù)測(cè)指標(biāo)權(quán)重設(shè)置如表2所示。

此外,對(duì)比了帶權(quán)重的最優(yōu)節(jié)點(diǎn)距離與最差節(jié)點(diǎn)距離,分析了不同數(shù)據(jù)集下模型距離最優(yōu)節(jié)點(diǎn)遠(yuǎn)近和距離最差節(jié)點(diǎn)遠(yuǎn)近這兩種排序,發(fā)現(xiàn)單純通過簡(jiǎn)單的模型優(yōu)劣計(jì)算方法來評(píng)判模型性能會(huì)導(dǎo)致較大的偏差。

2)模型性能比較及權(quán)重的敏感性分析

采用本文提出的雙最優(yōu)化排序方法MMIMMD計(jì)算模型的性能排序,同時(shí)為了進(jìn)行對(duì)比,也實(shí)現(xiàn)了

圖4 不同模型的RE預(yù)測(cè)曲線Figure 4 RE prediction curves of different models

表2 擬合與預(yù)測(cè)指標(biāo)權(quán)重設(shè)置Table 2 Settings of fitting and prediction weights

基于簡(jiǎn)單加權(quán)法與基于歐幾里得距離法的模型性能排序。其中,簡(jiǎn)單加權(quán)法是依據(jù)加權(quán)平均值的大小進(jìn)行排序;歐幾里得距離法則是計(jì)算各個(gè)模型與理想解之間的最短距離來排序。表3給出了3種決策方法的排序結(jié)果。

為了觀察不同擬合標(biāo)準(zhǔn)權(quán)重對(duì)模型性能排序的影響,取消了7個(gè)擬合標(biāo)準(zhǔn)的權(quán)重?cái)?shù)值,得到表4所示的結(jié)果?？梢钥闯?權(quán)重的設(shè)置會(huì)對(duì)模型的預(yù)測(cè)性能產(chǎn)生影響。例如,SRGM4模型在DS1上和SRGM8模型在DS2上,當(dāng)無權(quán)重設(shè)置時(shí)雙最優(yōu)距離評(píng)估較好,有權(quán)重設(shè)置時(shí)雙最優(yōu)距離評(píng)估較差。但這并不是決定模型預(yù)測(cè)性能的最關(guān)鍵因素,因此這也證明了當(dāng)前文獻(xiàn)中多采用此標(biāo)準(zhǔn)的合理性。

3.4 討論

3.4.1關(guān)于權(quán)重設(shè)置 對(duì)于刻畫擬合性能的多個(gè)指標(biāo)屬性,以及除了RE以外更多的評(píng)價(jià)預(yù)測(cè)性能的指標(biāo)屬性,屬性權(quán)重完全可以根據(jù)實(shí)際需要采用有關(guān)方法進(jìn)行設(shè)置。例如,當(dāng)認(rèn)為擬合更重要時(shí),可利用特征向量法、最小加權(quán)法或信息熵等方法來確定具體的擬合指標(biāo)權(quán)重。

3.4.2關(guān)于真實(shí)工程環(huán)境下的決策 在大型的復(fù)雜軟件測(cè)試過程中,選擇合適的可靠性模型作為指導(dǎo)來提高可靠性,仍面臨著更多的考驗(yàn)。例如,需要明晰整體測(cè)試策略,掌握測(cè)試過程的消耗情況(涉及對(duì)測(cè)試工作量變化的觀測(cè)),確定故障檢測(cè)數(shù)量的基本走勢(shì),據(jù)此再進(jìn)行分類選擇,這都會(huì)加重模型選擇的難度。本文對(duì)此進(jìn)行了初步探索,后續(xù)更為具體和深入的研究亟須加強(qiáng)。

3.4.3關(guān)于計(jì)算復(fù)雜性 趨近真實(shí)測(cè)試過程的可靠性模型往往包含大量的參數(shù),具有較為復(fù)雜的表達(dá)式結(jié)構(gòu),觀測(cè)模型更多的性能指標(biāo)也會(huì)引發(fā)巨大的計(jì)算量,甚至超出人工能力范疇。針對(duì)上述情況,

表3 3種決策方法的排序結(jié)果Table 3 Ranking results of three decision methods

表4 MMIMMD決策方法的無權(quán)重排序結(jié)果Table 4 Ranking results without weight of MMIMMD decision method

需要借助具備復(fù)雜模型分析與處理的數(shù)值軟件來完成,通常會(huì)進(jìn)行近似計(jì)算處理,而這將成為一種普遍的現(xiàn)象。

4 結(jié)語

針對(duì)當(dāng)前可靠性模型數(shù)量多以及難以實(shí)施有效決策的問題,提出了具體的SRGM選擇方法。依據(jù)模型在擬合與預(yù)測(cè)兩個(gè)方面的性能,建立基于明考斯基距離的雙最優(yōu)化排序模型,定量化地對(duì)模型性能進(jìn)行標(biāo)準(zhǔn)歸一化處理,建立模型間的偏序關(guān)系,從而實(shí)施有效決策。通過在公開發(fā)表的真實(shí)失效數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)和分析,驗(yàn)證了所提出方法的有效性,為定量決策模型提供了有力支持。模型性能評(píng)價(jià)可以歸屬到多屬性決策問題的范疇,對(duì)于偏好上的差異將直接影響決策結(jié)果。因此,通常需要設(shè)定一系列的決策條件并考慮模型的使用場(chǎng)景,選擇合適的方法進(jìn)行決策。后續(xù)研究中要區(qū)分測(cè)試環(huán)境與運(yùn)行環(huán)境的差異性,依據(jù)用戶的輸入條件,充分利用模型性能的多類描述信息進(jìn)行決策,采用不確定多屬性決策方法(特別是隨機(jī)多屬性、模糊多屬性和粗糙多屬性等)進(jìn)行決策,不斷豐富研究?jī)?nèi)容。