朱麗娜，蔣曹清，夏國恩，張作昌

1(廣西財經(jīng)學院 信息與統(tǒng)計學院，南寧 530003)2(廣西財經(jīng)學院 廣西跨境電商智能信息處理重點實驗室，南寧 530003)

1 引 言

與硬件相比，軟件的可靠性評測有許多特殊之處.例如，軟件壽命與其失效率無關(guān)，在其他各項指標保持不變的情況下，軟件可以持續(xù)正常運行，不存在硬件系統(tǒng)的種種損耗機理；另外，由于軟件的不可觸摸性，判斷軟件產(chǎn)品的可靠性時，無法從其尺寸、質(zhì)量、技術(shù)規(guī)范等直觀衡量尺度著手，只有當軟件運行之后才能對其可靠性進行評測.失效數(shù)據(jù)的收集是評測軟件可靠性的關(guān)鍵前提，同時也是其瓶頸之一.這是由于軟件在系統(tǒng)測試或投入運行之后，其操作周期往往較長，且此時故障引發(fā)失效的概率較低，導致收集到的失效數(shù)據(jù)極其有限，直接影響可靠性預測模型的建立.此外，迫于競爭壓力，很多企業(yè)選擇保護其實驗或測試階段收集的失效數(shù)據(jù)，使得該領(lǐng)域缺乏充足的公開數(shù)據(jù)集.這些都直接阻礙了軟件可靠性的研究工作.

盡管軟、硬件存在諸多差異，但也有相似之處.例如，軟、硬件的可靠性均為復雜度的函數(shù)，后者是設(shè)備復雜度的函數(shù)，前者是代碼量、算法復雜度的函數(shù).對于硬件設(shè)備來說，造成失效的缺陷是在制造環(huán)節(jié)引入的，若在制造期間嚴格保證質(zhì)量，設(shè)備可在較長時間的使用過程中發(fā)現(xiàn)零耗損機理，軟件亦然.嚴格控制編碼階段引入的錯誤量可以保證較高的軟件可靠性.類比元器件的失效機理，是否可對軟件失效機理做類似區(qū)分？這既是本文的研究動機，也是核心內(nèi)容.

本文將探討軟件是否存在某種特定的失效機理，使得它可以區(qū)別于其他軟件，并呈現(xiàn)出某種特定的可靠性特征？對這一抽象問題的研究可歸結(jié)為：是否有一種針對軟件的分類方法，可以將具有同種特質(zhì)的軟件劃歸為一類，使得類內(nèi)的軟件具有相似的可靠性屬性？本文的研究工作建立在文獻[1]的基礎(chǔ)上，對程序的狀態(tài)特征描述采用基于細粒度基本塊(Fine Granularity Basic Block，F(xiàn)GBB)的程序狀態(tài)提取方法，依據(jù)程序“首錯誤”特征進行狀態(tài)劃分.

2 相關(guān)工作

失效機理原指機械工程領(lǐng)域引發(fā)失效的物理、化學或其他的原因和過程，主要特點包括：失效機理是失效模式的原因；失效機理的類別有限，且相對容易被識別；通過對失效機理分析而積累的工程知識可用于同領(lǐng)域的其他產(chǎn)品.類似的，分析軟件的失效機理可從以下方面著手：

1)程序的結(jié)構(gòu)特征；

2)故障在軟件系統(tǒng)中的傳播特征；

3)軟件失效的回溯過程，即失效與故障的映射關(guān)系.

現(xiàn)從這三個方面梳理相關(guān)研究進展.

失效機理的研究初衷是為了探討軟件與其可靠性之間的關(guān)系，而失效數(shù)據(jù)是可靠性研究的重要前提.對程序結(jié)構(gòu)特征的研究主要是指基于白盒測試、故障分類、故障診斷等程序結(jié)構(gòu)建模與分析.文獻[2]提出一種基于可靠性的故障關(guān)聯(lián)靜態(tài)分析優(yōu)化方法，用以對大型嵌入式系統(tǒng)進行故障檢測.文獻[3-5]通過白盒、灰盒測試，分析測試用例的覆蓋率，對軟件錯誤做出定性分析.

故障傳播作為一個獨立的領(lǐng)域，包括故障定位和檢測、可靠性預測等，是軟件失效機理的研究熱點之一.多數(shù)文獻將故障傳播的研究視為自身研究領(lǐng)域的延展，故障傳播的各類建模方法之間并不通用.目前，該領(lǐng)域主要有兩大研究趨勢，一是假定軟件的結(jié)構(gòu)特征決定故障傳播行為，重點研究故障在軟件自身的體系結(jié)構(gòu)內(nèi)的傳播規(guī)律[6-8]；二是假定故障行為特征(而非程序固有的結(jié)構(gòu)特征)本身決定其傳播規(guī)律，從而將研究著眼于故障特性上[9,10].

從軟件失效到故障或錯誤的回溯分析，較為出眾的研究成果常以程序譜系作為研究起點.譜系是一種描述程序行為特征的有效方法，首次在文獻[11]中提出.目前，程序頻譜主要以程序的語句、分支、函數(shù)或謂詞等作為程序?qū)嶓w類型，用以建模分析程序行為.在網(wǎng)絡(luò)安全(Masri提出了Tarantula方法，針對信息流的程序?qū)嶓w間關(guān)系建模)[12]、故障定位與檢測(Chen等人提出了包含程序頻譜構(gòu)造、測試套件構(gòu)成和維護、內(nèi)在缺陷數(shù)量、測試用例預言設(shè)置等方面的故障定位研究框架)[13]等領(lǐng)域均有不錯的研究成果.而試圖通過聚類的方法判斷和尋找程序的失效機理的研究，近年來，以文獻[14]為典型.Zhang等人通過建立程序行為在多種條件下的特征譜(正常行為、故障行為和失效行為等)并對其聚類分析，用以探討軟件故障、錯誤或失效行為與正常行為之間的關(guān)系，結(jié)果表明，在特定的系統(tǒng)平臺下，程序確實具有某種固有屬性可用于分類程序的行為特征.

本文研究與文獻[14]有相近之處，即試圖通過建立程序行為并劃分類別來探討軟件失效機理的問題.不同之處在于，本文在文獻[1]的基礎(chǔ)上，建立與首錯誤特征相關(guān)的程序行為譜，并基于故障的時空間分布特性對故障、錯誤和失效行為進行特征提取，更符合軟件可靠性的核心研究思路.主要內(nèi)容包括：定義三種與程序行為特征相關(guān)的特征譜系表達，即黃金運行、錯誤行為和失效行為；根據(jù)譜系表達的特點提出各個表達之間相似性的度量方法和分類方法，闡述對分類準確性的評定方法；以SPEC 2006基準程序為研究對象，將服從真實場景時空間分布的正交缺陷分類(Orthogonal Defect Classification，ODC)故障注入程序中，獲取真實的現(xiàn)場失效數(shù)據(jù)；分析三種分類方式下的程序行為特征，對其呈現(xiàn)的軟件失效機理的效果做出詳細分析和評定，探討研究軟件失效機理的合理性及意義.

3 三種程序特征表達的定義方法

3.1 基于FGBB的程序黃金運行特征表達

程序運行過程可總結(jié)為：在特定的操作剖面下，程序經(jīng)過一組指令序列執(zhí)行后得到輸出值的過程.“可重復性”是程序的本質(zhì)，即在無故障條件下，相同的操作剖面一定會產(chǎn)生相同的程序輸出.本文采用“黃金運行”來定義這種“可重復性”，試圖以此為切入點來探討軟件的失效機理問題.此處，在文獻[1]提出的FGBB方法的基礎(chǔ)上，進一步定義和探討程序的黃金運行及其特征表達.

FGBB方法的主要思想是，在錯誤發(fā)生時能做出及時的性質(zhì)判定和位置判定，盡可能在故障引發(fā)的首個程序異常狀態(tài)處做出響應.FGBB方法將程序的運行狀態(tài)分為5類：

狀態(tài)類型1：指無條件跳轉(zhuǎn)指令之后對應的程序狀態(tài)(包含跳轉(zhuǎn)條件和當前棧幀信息)，記做UJS.根據(jù)其指令特性，在記錄中間狀態(tài)時，將表示控制流特性的標志位始終置1，表示如下：

UJS={stat1,jmpCond,%ebp,stackSize,stackContent},jmpCond=1

狀態(tài)類型2：指條件跳轉(zhuǎn)指令之后對應的程序狀態(tài)(包括跳轉(zhuǎn)條件和當前棧幀信息)，其中，跳轉(zhuǎn)條件是根據(jù)寄存器EFLAGS中條件碼的特定組合得到的布爾表達式的值，記做CJS，表示如下：

CJS={stat2,jmpCond,%ebp,stackSize,stackContent}

狀態(tài)類型3：call指令執(zhí)行之后獲取的與棧幀結(jié)構(gòu)相關(guān)的程序狀態(tài)，記做CLS，表示如下：

CLS={stat3,%ebp,stackSize,stackContent}

狀態(tài)類型4：在被調(diào)函數(shù)返回前，且從被調(diào)函數(shù)棧幀切換至調(diào)用函數(shù)棧幀前，執(zhí)行的最后一條指令后的程序狀態(tài)，記做BRETS，表示如下：

BRETS={stat4,%eax,stackSize,stackContent},or

BRETS={star4,stackSize,stackContent}

狀態(tài)類型5：ret指令執(zhí)行后獲得的與當前棧幀結(jié)構(gòu)相關(guān)的程序狀態(tài)，記做ARETS，表示如下：

ARETS={stat5,%ebp,stackSize,stackContent}

若考慮用上述狀態(tài)集Ω={UJS,CJS,CLS,BRETS,ARETS}表征程序的一次運行過程，則可以用如下狀態(tài)序列表示：{s1,s2,…,sn}，其中si∈Ω，即所有的程序狀態(tài)序列都可看作是由Ω集合中的5種狀態(tài)構(gòu)成的線性序列.采用長度為k的滑動窗口沿狀態(tài)序列以步長為1的方式依次移動直至最末狀態(tài)，則可將程序狀態(tài)分解為由多個k-長狀態(tài)子序列過程的狀態(tài)集合.程序狀態(tài)序列對應程序的結(jié)構(gòu)特征，如CJS對應一次條件判斷，一組對應一次函數(shù)調(diào)用等.為確定最佳k值，統(tǒng)計SPEC 2006基準程序狀態(tài)序列中的平均長度，該長度為6，即6-長子序列能夠覆蓋包含條件結(jié)構(gòu)、順序結(jié)構(gòu)、循環(huán)結(jié)構(gòu)和單次完整的函數(shù)調(diào)用在內(nèi)的全部程序基本結(jié)構(gòu).后續(xù)研究都將基于程序的6-長狀態(tài)子序列展開.

單次程序的狀態(tài)序列并不能全面反映程序的行為特征，為得到統(tǒng)計意義上的程序行為特征，必須基于一簇輸入值下的程序狀態(tài)序列來分析，且該輸入集合盡可能接近真實的用戶操作剖面.

把獲得的狀態(tài)序列集合依次提取6-長子序列，若狀態(tài)序列長度為L，則子序列個數(shù)為L-5.統(tǒng)計不同子序列出現(xiàn)的次數(shù)得到頻率分布：{P(seq1),P(seq2),…,P(seqn)}.其中，seqi表示一個特定的6-長子序列，且n=56=15625.為保證實驗結(jié)果的準確性，在實驗獲得的全部子序列頻率分布中seqi的絕對位置不變.

每個程序在給定的操作剖面下均可獲得一個關(guān)于子序列的頻率分布，由于子序列能反映程序固有的結(jié)構(gòu)特征，而結(jié)構(gòu)特征通常由程序功能特征決定，因此，子序列的頻率分布是具有統(tǒng)計意義的程序黃金運行.考慮程序無故障的運行情況，若實驗環(huán)境下的操作剖面越接近用戶的真實使用場景，該頻率分布越能準確地反映程序的基本運行特征.

3.2 基于FGBB的程序故障行為特征表達

程序的故障行為特征表達包含錯誤行為特征和失效行為特征，分別在3.2.1節(jié)中3.2.2節(jié)中定義和闡述.

3.2.1 程序的錯誤行為特征

根據(jù)程序的可重復性，運行時的中間數(shù)據(jù)具有多次運行呈現(xiàn)的某種不變性約束的邏輯關(guān)系特征.基于文獻[1]，假定U(stari,stati+1)是程序在某輸入條件下無故障時的一次狀態(tài)轉(zhuǎn)移過程，F(xiàn)為故障集，把程序在故障條件下的錯誤行為劃分為如下4類：

錯誤類型1：程序狀態(tài)類型在運行時出錯，即由于故障的影響，產(chǎn)生了一個非正常的程序狀態(tài)，記做：

錯誤類型2：當前棧幀結(jié)構(gòu)中的返回地址出錯，可能導致程序的控制流發(fā)生改變，并影響程序的后續(xù)運行，記做：

=stati+1(stack)

錯誤類型3：包括函數(shù)參數(shù)、局部變量和其他中間計算特征等中間數(shù)據(jù)出錯.該錯誤通常有潛伏期，若程序具有良好的容錯能力，錯誤可能會被屏蔽，記做：

=stati+1(retval)

錯誤類型4：函數(shù)的返回值出錯，可能影響包括變量賦值、函數(shù)參數(shù)值等在內(nèi)的中間數(shù)據(jù)，記做：

=stati+1(stack)

故障觸發(fā)的類型和位置均與程序的代碼片段特征有關(guān)，將代碼片段的特點和故障的發(fā)生位置相關(guān)聯(lián)，用如下序列表示故障在特定程序中的空間分布：

{P(f1),P(f2),…,P(fn)}

其中，fi表示故障類型，P(fi)表示故障發(fā)生概率.

假定程序中某一類錯誤發(fā)生的概率為P(ei)(ei∈{Errstat,Errretaddr,Errstack,Errretval},i=1,2,3,4)，基于全概率公式，程序在故障條件下觸發(fā)某類錯誤的概率為：

另外，考慮具有較長潛伏期的故障，程序的狀態(tài)序列可能與黃金運行相同，程序的錯誤行為特征可抽象為頻率分布{P(e0),P(e1),P(e2),P(e3),P(e4)}，其中e0表示程序未發(fā)生任何錯誤，狀態(tài)序列與黃金運行一致.為保證結(jié)果的一致性，ei在各頻率分布中的絕對位置不變.

3.2.2 程序的失效行為特征

程序的失效行為分為異常終止、響應超時和非法輸出.與3.2.1節(jié)類似，定義程序的失效行為時考慮故障的空間分布特征：假定程序的某一失效類型為failj，基于全概率公式，程序在故障條件下引發(fā)失效failj的概率計算如下：

考慮程序在故障條件下輸出正常的情況，程序的失效行為特征可定義為{P(fail0),P(fail1),P(fail2),P(fail3)}，其中，fail0為正常輸出的行為，后三者分別對應異常終止、響應超時和非法輸出，failj在頻率分布中的絕對位置不變.

4 程序特征表達間的相似性度量及分類方法

由上節(jié)可知，程序的黃金運行、錯誤行為和失效行為表達均被定義為頻率分布.6-長子序列、錯誤和失效為隨機變量，其行為的特征表達即為概率分布.采用Kullback熵(即KL散度)[15]度量各個特征表達之間的相似性，根據(jù)相似性對程序集進行分類，得到三組不同的分類結(jié)果，分別為黃金運行、錯誤行為和失效行為.上述過程總結(jié)如下：

1)對每個程序的三組特征表達分別做Kullback熵度量，得到兩兩程序之間關(guān)于每組特征表達的相似性度量值；

2)根據(jù)相似性度量得到程序的相似矩陣，一共生成三個相似矩陣；

3)將相似矩陣變換為二維空間中的點集，使得每個程序?qū)S空間中的一個標識；

4)采用聚類方法將二維空間中的點集分成三類，即黃金運行分類、錯誤行為分類和失效行為分類.

4.1 程序特征表達的相似性度量方法

程序行為的譜系表達均為概率分布，采用Kullback熵衡量兩個程序行為之間的距離，以表征兩兩行為之間的相似性.假設(shè)兩個程序的行為特征表達分別記作P和Q，其中P={p1,p2,…,pn}，Q={q1,q2,…,qn}，pi和qi分別是兩個程序的行為特征，n值依賴于被度量的程序行為類型，當度量黃金運行時，n取15626；當度量錯誤行為時，n取5；當度量失效行為時，n取4.兩兩程序行為的相似性度量如下：

兩個程序行為特征表達之間的差異性越大，D(P,Q)越大；當且僅當兩者完全相同時，D(P,Q)為0.若選取的目標程序數(shù)為M，則基于上述度量可獲得三個M×M的相似矩陣.

4.2 基于程序特征表達的程序分類方法

為與文獻[1]進行實驗對比，采用模糊聚類(Fuzzy Compactness and separation，F(xiàn)CS)算法分類程序行為特征[16].該算法同時考慮類內(nèi)程序行為間的緊湊性和類間各行為的離散性，大大提高了聚類算法的準確性.

類間距離權(quán)重ηi、隸屬度μij和聚類中心vi的優(yōu)化如下：

(1)

(2)

(3)

算法步驟如下：

5 實驗分析與討論

實驗主要探討兩個方面的問題：

1)程序黃金運行的分類方式是否同樣適用于劃分其錯誤行為和失效行為？

2)程序黃金運行的分類方式是否能有效將具有相似可靠性特征的程序劃分到一類中？若結(jié)果是正面的，則該研究提供了一種以軟件的失效機理來衡量軟件可靠性的方法.

3)對比文獻[1]的分類效果.

5.1 實驗對象選取

為獲得充足的實驗數(shù)據(jù)，且盡可能的讓其接近真實的用戶場景，選取SPEC 2006作為實驗對象.SPEC 2006是一組計算密集型程序，包含整型運行程序和浮點型運行程序，覆蓋了解釋器、編譯器、游戲、隱馬爾科夫模型運算等典型的計算型程序，在工業(yè)界常用來衡量系統(tǒng)的全面性能.以該程序集作為研究對象，在分析失效機理和可靠性方面具有更強的統(tǒng)計意義.

在故障類型的選取方面，與文獻[1]一致，采用正交缺陷分類方法，將軟件故障劃分為賦值類、校驗類、接口類、算法類和功能類等.采用文獻[1]提出的故障分類作為實施故障注入實驗的主體，故障細分類型如表1所示.

表1 ODC故障細分類型及描述Table 1 ODC sub-types and descriptions

選取12個SPEC 2006基準程序，每個程序的操作剖面為程序集中給定的輸入集，即ref、test和train類.通過掃描程序的目標代碼確定可注入故障的位置和類型，用以表征每個程序的故障空間分布.所選程序及其注入故障空間分布的特征如表2所示.需要說明的是，用于分類的程序以單個輸入值下的程序行為特征為單位，實驗中不考慮程序的具體類型，僅考慮與操作剖面相結(jié)合的特定程序行為特征，聚焦失效機理的研究，因此，分類前程序均“匿名”標識.

表2 SPEC 2006 基準程序的故障空間分布情況Table 2 ODC-based fault distribution for SPEC 2006 benchmark

5.2 實驗步驟

步驟1.50個程序在無故障條件下運行，生成50組基準程序特征表達，即6-長子序列的頻率分布；

步驟2.對50組程序?qū)嵤㎡DC故障注入，分別收集錯誤行為和失效行為的特征表達，即錯誤和失效的頻率分布；

步驟3.將黃金運行、錯誤行為和失效行為的特征表達分別進行聚類，得到Cluster_norm，Cluster_err和Cluster_fail，計算各類內(nèi)兩兩程序之間的平均相似度；

步驟4.將程序的錯誤行為和失效行為用黃金運行的分類方法進行劃分，計算各類內(nèi)兩兩程序之間的平均相似度；

步驟5.為獲取程序與可靠性相關(guān)的特征，考慮故障的時間分布特性，對程序?qū)嵤┮灾笖?shù)分布為前提的故障注入時間，并記錄程序的失效時間和計數(shù)；

步驟6.將獲得的程序失效按照等間隔時間計數(shù)方式對應到二維空間中；

步驟7.分別計算三種分類中程序失效分布的相似性，具體方法如下：

步驟7.1.按照Cluster_norm對程序的失效分布進行分類，計算類內(nèi)兩兩程序之間的樣本標準差，并最終算得類內(nèi)全部樣本的標準差平均值；

步驟7.2.按照Cluster_err和Cluster_fail分別對程序的失效分布進行分類，計算各個類內(nèi)的樣本標準差平均值；

步驟8.實驗完畢.

關(guān)于步驟5，采用J-M(Jelinski-Moranda)模型為故障注入的假設(shè)前提，如下：

假設(shè)1.在程序中，其原本存在的故障數(shù)為N0，且為一個未知常數(shù)；

假設(shè)2.程序中的錯誤均相互獨立，每個錯誤引發(fā)系統(tǒng)失效的概率基本相同，且失效間隔也相互獨立；

假設(shè)3.在測試階段檢測到的故障均被排除，且單次排錯數(shù)為1(排錯時間忽略不計，且在排錯時，不會引入新的錯誤)；

假設(shè)4.程序的失效率在每次失效間隔內(nèi)均為常數(shù)，數(shù)值正比于殘留故障數(shù)，在第i個測試區(qū)間內(nèi)：

失效率Z(xi)=φ(N0-i+1)

假設(shè)5.程序的運行方式與人們預期的方式相似.

5.3 實驗結(jié)果與分析

表3展示了SPEC 2006基準程序在FGBB和BIP[1]兩種程序行為表征方法的條件下，通過特定的聚類算法得到的程序黃金運行和錯誤、失效行為的分類結(jié)果.其中，分類質(zhì)量是指，程序的故障行為和失效行為按照黃金運行的行為特征分類結(jié)果聚合，隨后得到的類內(nèi)各個程序間的平均相似度.由于FGBB和BIP方法采用的聚類算法基本一致，且兩兩程序間的相似度度量方法也相同，那么，類內(nèi)行為的平均相似度越高，說明“黃金運行”的行為特征提取機制越優(yōu).

FGBB方法選取6-長子序列，而BIP方法選取7-子序列(根據(jù)文獻[14]中的實驗分析獲得的子序列最優(yōu)值)，兩者均把程序分為3類.從表3可以看出，F(xiàn)GBB在黃金運行的行為分類上取得的類間相似度略高于基于BIP方法的黃金運行.針對錯誤行為的分類結(jié)果中，F(xiàn)GBB方法在每個故障細分類型下都表現(xiàn)出較高于BIP方法的分類質(zhì)量，即每個類間程序的錯誤行為更加近似.以O(shè)WPFV故障類型為例，它表示函數(shù)參數(shù)被設(shè)置了錯誤的值，由于FGBB方法是基于首錯誤的行為特征表達，其BRETS和ARETS兩個程序狀態(tài)可以提前檢測到由于函參導致的中間變量或跳轉(zhuǎn)條件上的錯誤.因此，對于函數(shù)嵌套調(diào)用和條件語句頻繁執(zhí)行的程序，F(xiàn)GBB方法對錯誤的檢測更加敏感.

從失效行為的分類結(jié)果看，兩種方法不分伯仲.在FGBB優(yōu)于BIP的幾組故障細分類型中，多以與函數(shù)相關(guān)的故障為主，如OWPFV、OMFC和OMIFS.這進一步說明，為函數(shù)返回前后定義兩種不同的程序狀態(tài)類型，把函參、返回值及中間變量作為判斷程序錯誤/失效的條件之一，可以更準確和高效地定位程序的脆弱點，提升程序的容錯能力.

表3 基于黃金運行行為的程序故障/失效行為的類內(nèi)平均相似度Table 3 Intra-cluster average similarity of error/failure behavior based on golden run behavior

1FGBB表示基于本文方法提取程序狀態(tài)并完成行為分類

2BIP表示基于文獻[14]方法提取程序狀態(tài)并完成行為分類

3Δ為FGBB和BIP方法獲得的錯誤/失效行為的類內(nèi)平均相似度的差值，即分類質(zhì)量

圖1展示了FGBB方法和BIP方法在分類質(zhì)量上的直觀統(tǒng)計.可以看出，絕大多數(shù)錯誤行為和失效行為在FGBB方法的分類過程中可以更準確地被聚合，尤其是針對錯誤行為，其黃金運行的行為特征基本能揭示不同ODC細分故障類型下的錯誤行為發(fā)生規(guī)律，對故障具有較為敏感和準確地提前判斷和定位.

圖1 基于FGBB/BIP方法的分類質(zhì)量對比Fig.1 Similarity measurement of error/failure behavior based on FGBB/BIP clustering

為探討程序結(jié)構(gòu)與其錯誤和失效行為之間的關(guān)聯(lián)，進一步分析黃金運行特征中的高頻狀態(tài)序列.圖2(a)-圖2(c)展示了基于FGBB方法聚類得到的三類程序行為的狀態(tài)序列頻度分布.在圖2中，橫坐標為15625個不同的狀態(tài)序列，分別以0-4編號對應的狀態(tài)類型，即UJS、CJS、CLS、BRETS、ARETS.由于橫坐標密度較大，頻度較高的狀態(tài)序列實際為一簇值，圖2(a)-圖2(c)中標號主要標注頻度最高的狀態(tài)序列.

不同分類中的高頻狀態(tài)序列特征明顯.Cluster 1中幾個高頻序列為111111、*111**、343434.其中，111111和*111**說明程序中的條件判斷多且連續(xù)，結(jié)合程序結(jié)構(gòu)特征發(fā)現(xiàn)，其中包含大量循環(huán)結(jié)構(gòu)，如程序Liquantum和H264ref；而343434則說明程序中含有較多嵌套函數(shù)，如程序Gobmk.Cluster 2中高頻狀態(tài)序列有011111、122223、211111等.其中，011111說明條件判斷語句較多，而122223為明顯的函數(shù)嵌套調(diào)用過程，211111說明子函數(shù)中含有大量循環(huán)結(jié)構(gòu)執(zhí)行，程序Xalancbmk屬于這種類型.同理，Cluster 3的程序大多具有執(zhí)行大量循環(huán)結(jié)構(gòu)的特征，如程序Gcc，以及較多選擇結(jié)構(gòu)的Astar和Bzip2程序.

圖2 基于FGBB方法的狀態(tài)序列譜系特征Fig.2 Status sequence characterization based on FGBB

為了對比基于BIP方法的程序分類情況，根據(jù)文獻[14]，收集如表4所列出的兩種方法在每一類中的最高頻的三種程序狀態(tài)序列.可以看出，每類中的典型行為特征在兩種方法中均有比較一致的體現(xiàn)，如類1中均包含擁有大量循環(huán)結(jié)構(gòu)的程序Liquantum和H264ref，和函數(shù)嵌套執(zhí)行較多的程序Gobmk；類2集中包含執(zhí)行了大量循環(huán)體和函數(shù)調(diào)用的程序行為，如Xalancbmk；類3中的程序在執(zhí)行過程中多以循環(huán)和選擇結(jié)構(gòu)為主，如程序Gcc，Astar和Bzip2等.

表4 基于FGBB與BIP方法的高頻狀態(tài)序列統(tǒng)計Table 4 Sequence occurrence of top-3 frequency for FGBB and BIP method

基于上述分析可知，F(xiàn)GBB方法與BIP方法一樣，均能以其狀態(tài)序列及頻率分布表征程序的結(jié)構(gòu)特征及其運行時的行為特征.在利用黃金運行對程序的錯誤和失效行為進行歸類的過程中，F(xiàn)GBB方法表現(xiàn)出更優(yōu)的表征錯誤行為并提取其行為特征的能力，尤其是在對函數(shù)調(diào)用過程中的程序故障行為的表征和檢測，可以做到在狀態(tài)序列變更并造成更嚴重的程序運行偏差之前表征出相應的錯誤，與文獻[1]對首錯誤的研究結(jié)果一致.此外，在針對失效行為的分類方面，實驗結(jié)果與文獻[14]基本一致，但在針對函數(shù)的ODC細分故障類型下的判斷和分類更加準確一些.文獻[1]也提出，程序控制流的改變對程序的運行狀態(tài)有較大影響，且控制流改變引發(fā)程序失效的概率通常較高.因此，及時監(jiān)測并確保程序運行時的控制流的正確性十分重要.FGBB方法正是基于上述思想實現(xiàn)了對程序行為的特征表達，從實驗結(jié)果可以看出，在對故障條件下的程序行為表征和分類質(zhì)量方面，F(xiàn)GBB方法較BIP方法略優(yōu).

6 結(jié)束語

軟件可靠性是代碼量、算法復雜度的函數(shù)，本文從“故障觸發(fā)錯誤+錯誤導致失效”的過程出發(fā)，在文獻[1]對“首錯誤”研究基礎(chǔ)上開展后續(xù)工作，探討與軟件可靠性相關(guān)的特征行為分類，并與文獻[1]做類比.結(jié)果表明，在針對錯誤行為的分類方面，由于FGBB方法以軟件“首錯誤”定義狀態(tài)序列，得到的基于ODC細分類型故障下的程序錯誤行為的各異性比文獻[14]的BIP方法略優(yōu).本文研究工作的意義在于，能夠像硬件一樣，將軟件的固有特征體現(xiàn)在其運行行為中，使得對軟件行為的分類可以類比硬件，即基于某種“失效機理”，這將有利于軟件可靠性評測的進一步展開.