基于軟件網(wǎng)絡錯誤傳播分析的軟件質(zhì)量量度

潘偉豐，李兵

(1.浙江工商大學 計算機與信息工程學院，浙江 杭州，310018；2.武漢大學 軟件工程國家重點實驗室，湖北 武漢，430072；3.武漢大學 計算機學院，湖北 武漢，430072)

復雜網(wǎng)絡可以用來描述從技術到生物直至社會各類開放復雜系統(tǒng)的骨架，而且是研究它們拓撲結(jié)構和動力學性質(zhì)的有力工具，已成為極其重要且富有挑戰(zhàn)性的科學前沿。近年來，統(tǒng)計物理和復雜系統(tǒng)科學領域的研究人員嘗試將軟件結(jié)構用網(wǎng)絡的形式來描述，即將軟件元素(方法、類、包等)視為節(jié)點，元素之間關系(調(diào)用、繼承、關聯(lián)等)作為邊的軟件網(wǎng)絡，并結(jié)合復雜網(wǎng)絡的最新研究成果，對大量開源軟件系統(tǒng)進行了深入研究。如在軟件網(wǎng)絡拓撲結(jié)構特性研究方面，Potanin等[1-3]在不同層次(方法、類和包等)對大量開源軟件的依賴網(wǎng)絡進行了分析，發(fā)現(xiàn)這些網(wǎng)絡都具有“小世界”和“無標度”特性；韓明暢等[4-5]對Java和Linux等軟件系統(tǒng)進行分析，也發(fā)現(xiàn)了類似的結(jié)果。在軟件網(wǎng)絡演化機理研究方面，Krapivsky等[6]提出了一種基于復制和分岔規(guī)則的軟件演化模型；He等[7]從設計模式的角度提出了基于模式冷凍部分的軟件演化生長模型；Pan等[8]根據(jù)軟件網(wǎng)絡中節(jié)點和邊之間的交互與動態(tài)變化，提出了一種基于軟件網(wǎng)絡的軟件演化模型。在軟件復雜性度量和評估方面，Vasa等[9]提出了一套度量指標來檢測軟件開發(fā)過程中軟件結(jié)構的穩(wěn)定性變化；Ma等[10]提出了一個層次型的度量體系，從不同層次、不同角度度量大規(guī)模軟件系統(tǒng)的各種結(jié)構特性。在軟件網(wǎng)絡指導工程實踐方面，Pan等[11]提出了一種基于復雜網(wǎng)絡社區(qū)發(fā)現(xiàn)的軟件重構技術。但是，目前從軟件系統(tǒng)復雜網(wǎng)絡的角度來研究軟件結(jié)構，揭示軟件內(nèi)部結(jié)構和外部質(zhì)量間關系的文獻較少。MacCormack等[12]提出了傳播代價(Propagation cost)的概念，并用于研究文件間的耦合網(wǎng)絡，從易變性角度衡量軟件的質(zhì)量。劉婧等[13]定義了平均傳播代價(Average Propagation Ratio)，探討了面向?qū)ο筌浖W(wǎng)絡的結(jié)構與平均傳播代價的內(nèi)在關系，并用平均傳播代價對類級軟件網(wǎng)絡的質(zhì)量進行量化。這些方法都是先求得單個節(jié)點的影響范圍，然后求所有節(jié)點影響范圍之和，最后將這個和進行單位化，作為系統(tǒng)質(zhì)量的度量指標。實際上，這些方法考慮的僅僅是單個節(jié)點對整個軟件網(wǎng)絡結(jié)構的平均影響范圍，即單個節(jié)點改變(如修改、出錯等)會影響到的其他節(jié)點的數(shù)量，以此來評估軟件的質(zhì)量。然而，現(xiàn)實中往往是多個節(jié)點同時改變，如多個節(jié)點同時被修改、出錯等，此時，研究這些改變對軟件網(wǎng)絡結(jié)構的影響對衡量軟件的質(zhì)量至關重要。鑒于此，本文作者提出一種用于研究軟件質(zhì)量的新方法，該方法將面向?qū)ο筌浖到y(tǒng)在方法層次抽象成網(wǎng)絡模型——方法調(diào)用網(wǎng)絡，通過隨機和受控的方式向網(wǎng)絡中植入錯誤，研究錯誤在網(wǎng)絡中的傳播行為，并定義新的度量來刻畫錯誤傳播對軟件結(jié)構造成的影響，以此來量度軟件的質(zhì)量。

1 基本概念及分析方法

圖1所示為本文分析方法的基本框架。以OO(Object-Oriented，OO)軟件為研究對象，對其源代碼進行語法/詞法分析，得到方法及方法間的調(diào)用關系；提取方法調(diào)用網(wǎng)絡；基于方法調(diào)用網(wǎng)絡進行錯誤植入研究；通過錯誤植入研究量度軟件質(zhì)量。

1.1 OO軟件源代碼

本文選擇開源的OO軟件(主要指以c++和Java開發(fā)的系統(tǒng))作為研究對象，主要出于以下考慮：(1)現(xiàn)有的相關研究工作，主要以OO軟件系統(tǒng)為研究對象，采用相同的編程范型，便于結(jié)果的比較和分析；(2)OO編程范型從20世紀90年代開始就廣為流傳，網(wǎng)上具有大量的開源軟件系統(tǒng)，便于獲取大量實驗源數(shù)據(jù)；(3)采用OO編程技術開發(fā)的軟件系統(tǒng)，內(nèi)部結(jié)構比較清晰，軟件元素(方法、類、包等)及它們之間的關系比較容易提取。

1.2 軟件網(wǎng)絡模型

目前，使用復雜網(wǎng)絡模型研究軟件系統(tǒng)主要集中于3個層次，即方法層次、類層次和包層次。本文主要研究方法層次的軟件網(wǎng)絡的質(zhì)量。

定義1 方法調(diào)用網(wǎng)絡MCN(Method-calling network)。面向?qū)ο筌浖到y(tǒng)的方法調(diào)用網(wǎng)絡MCN可以用1個有向圖表示，即N=(M,C)。其中：N為網(wǎng)絡MCN；M為節(jié)點的集合，代表軟件中所有方法的集合；C為有向邊的集合，表示方法間的調(diào)用關系，由調(diào)用者指向被調(diào)用者。如圖2所示，方法b( )調(diào)用方法a( )，則MCN中有1條從b( )指向a( )的有向邊。

圖1 方法基本框架Fig.1 Framework of proposed method

圖2給出了1段Java寫的源代碼及其對應的MCN。

圖2 代碼段及對應的MCNFig.2 Code segment and its MCN

目前還沒有一種開源的工具能夠直接從軟件源代碼提取方法調(diào)用網(wǎng)絡。本文所有軟件的MCN都是由我們自主研發(fā)的軟件網(wǎng)絡分析工具SNAT[14](Software network analysis tool)自動提取的。SNAT可以實現(xiàn)從OO軟件源代碼生成各個層次(方法、類、包)的軟件網(wǎng)絡，然后，對軟件網(wǎng)絡進行一系列的度量、分析、可視化等，但該工具目前還不是開源的。

1.3 錯誤傳播特征及錯誤植入算法

錯誤傳播是分析可靠性系統(tǒng)不確定性的基本問題，可以發(fā)現(xiàn)系統(tǒng)中最易受到毀壞的部分及各部分之間的相互影響[15]。目前已有很多關于錯誤傳播方面的研究，如Voas等[16]提出了軟件中的錯誤傳播分析，主要用于計算某一源代碼位置傳播數(shù)據(jù)錯誤的概率；Hiller等[17]提出了一個分析軟件中數(shù)據(jù)錯誤傳播的框架；Johansson等[18]對操作系統(tǒng)內(nèi)部的錯誤傳播進行了分析，等。但是，本文的錯誤傳播分析方法與以往的不同，是基于軟件拓撲結(jié)構的。

軟件錯誤種類各異，對系統(tǒng)的破壞性也不盡相同。有些軟件錯誤能夠?qū)е孪到y(tǒng)的崩潰(如內(nèi)存非法訪問)，而大部分的錯誤一般只是造成系統(tǒng)的輸出不能滿足用戶的要求。本文從軟件拓撲結(jié)構(方法調(diào)用網(wǎng)絡)的角度，通過錯誤植入來對軟件的質(zhì)量進行研究，并不能詳盡地表達這些錯誤種類間的差別。為了簡化問題的研究，忽略了不同錯誤對軟件破壞程度的差異，并假設：(1)所有的錯誤僅僅會對軟件的運行正確性造成影響；(2)錯誤僅僅會在方法調(diào)用網(wǎng)絡中傳播。也就是說，錯誤只會出現(xiàn)在方法中，這些錯誤僅僅造成軟件不能完成既定的功能，不會給系統(tǒng)帶來嚴重的影響(如崩潰)，某個方法(節(jié)點)若存在錯誤，錯誤僅僅會傳播到與之有直接或間接關系的其他方法(節(jié)點)。

為了嚴格描述錯誤在MCN中的傳播過程，首先給出錯誤傳播關系及其他相關概念的形式化定義。

定義2 錯誤傳播關系(Error propagation relation)EPR(i,j)。設EPR是MCN節(jié)點集上的二元關系，i和j表示2個不同的節(jié)點。對于任一有序的節(jié)點對(i,j)，當且僅當j有1條有向路徑通向節(jié)點i時，稱節(jié)點i和節(jié)點j存在錯誤傳播關系EPR(i,j)，表示若節(jié)點i為錯誤節(jié)點，那么節(jié)點i的錯誤會傳播到節(jié)點j，使節(jié)點j也成為錯誤節(jié)點。

性質(zhì)1 錯誤傳播關系具有自相關性，即(i,i)∈EPR恒成立。

性質(zhì)2 錯誤傳播關系具有傳遞性。如果(i,j)∈

定義3 錯誤傳播域(Error-propagation field)EPF(i)。設EPF是MCN節(jié)點集上的一元關系，i和j示節(jié)點i的錯誤傳播域。顯然，1個節(jié)點的錯誤傳播域是該節(jié)點存在錯誤情況下，可能影響的最大范圍的一種描述。它由所有與節(jié)點i具有錯誤傳播關系的節(jié)點特別說明，|*|都表示集合*中元素的個數(shù)。

定義4 錯誤反向傳播域(Error back-propagation field)EBPF(i)。設EBPF是MCN節(jié)點集上的一元關系，達的所有節(jié)點的集合。

定義5 錯誤介數(shù)(Error betweenness)EB(i)。節(jié)點i的錯誤介數(shù)定義為其錯誤反向傳播域EBPF(i)中節(jié)點的個數(shù)，記為EB(i)=|EBPF(i)|。

顯然，EBPF(i)描述的是節(jié)點i可能受其影響的節(jié)點的集合，而EB(i)正是對這種影響能力的度量，即EB(i)越大的節(jié)點越容易受其他節(jié)點的影響而產(chǎn)生錯誤。

錯誤介數(shù)與文獻[10]中提出的波及度在形式上類似，但兩者含義不同。文獻主要用波及度對OO軟件的結(jié)構復雜性進行分析，而本文中的錯誤介數(shù)是對節(jié)點出錯可能性的一種衡量。

通過深度優(yōu)先遍歷算法，可以在O(|M|+ |C|)時間內(nèi)得到節(jié)點i的EPF(i)，EBPF(i)和EB(i)等值。

為了清楚地說明上面的定義和性質(zhì)，以1個簡單有向網(wǎng)絡為例(圖3)。這個網(wǎng)絡由6個節(jié)點和5條有向邊組成。若節(jié)點D存在錯誤，因為B存在到節(jié)點D的有向路徑B→D，F(xiàn)存在到節(jié)點D的有向路徑所以，D，B，F(xiàn)和E都與D存在錯誤傳播關系，即：EPR(D,D)，EPR(D,B)，EPR(D,F)和EPR(D,E)∈EPR，EPF(D)={D,B,F,E}，|EPF(D)|=4。因為從B出發(fā)可達的節(jié)點集是{B,D,A}，所以DBPF(B)={B,D,A}，EB(B)=3。

圖3 簡單的有向網(wǎng)絡Fig.3 Simple direct network

軟件中的錯誤通常有2種引入方式：(1)程序員在軟件開發(fā)中不小心引入的錯誤，這些錯誤的引入往往是隨機的，其錯誤的引入位置、時間等都是不確定的；(2)人為地惡意破壞程序中的代碼。為了研究軟件的質(zhì)量，模擬軟件錯誤的2種引入方式，進行了軟件MCN上的錯誤植入實驗，即：在MCN上選擇節(jié)點植入錯誤，根據(jù)錯誤傳播關系計算其錯誤傳播域，分析錯誤植入對軟件MCN造成的影響，并以此對軟件的質(zhì)量進行評價。但是，這里考慮的是一種極端的情況，即不斷地選擇節(jié)點植入錯誤，一直到MCN中所有節(jié)點都成為錯誤節(jié)點為止。根據(jù)錯誤植入位置選擇方式的不同，分錯誤隨機植入和錯誤受控植入2種情況來進行研究。

為了衡量錯誤植入對MCN的影響，首先定義MCN的結(jié)構健壯度(Structure robustness)SR。

定義6 結(jié)構健壯度SR定義為錯誤植入后，未受影響的節(jié)點數(shù)占網(wǎng)絡總節(jié)點數(shù)|M|的比例，即：

其中：ierrorSet表示MCN中已被選擇植入錯誤的節(jié)點集合。以圖3為例，若節(jié)點B被首先選擇植入錯誤，那么ierrorSet={B}，SR=1-3/6=0.5；若A也被選擇植入錯誤，那么，ierrorSet={A，B}，SR=1-5/6=1/6，以此類推。

從SR的定義可以看出：在相同的錯誤植入數(shù)(即相同的|ierrorSet|)下，SR越大，表明ierrorSet中節(jié)點的錯誤只會傳播到較少一部分的節(jié)點中去，錯誤通過軟件結(jié)構進行傳播的能力比較弱，軟件結(jié)構的容錯能力比較強。反之，SR越小，表明ierrorSet中節(jié)點的錯誤對軟件造成的影響比較大，錯誤極易通過MCN傳播到其他的部分，并對軟件造成極大破壞。因此，可以通過SR來對軟件結(jié)構的質(zhì)量進行評價。在相同的錯誤植入數(shù)下，一個結(jié)構設計良好的軟件應使錯誤傳播控制在盡可能小的范圍內(nèi)(SR盡可能的大)，以降低錯誤通過軟件結(jié)構傳播對軟件造成的影響。

算法1 錯誤隨機植入。錯誤隨機植入，即隨機的選擇節(jié)點植入錯誤，根據(jù)錯誤傳播關系，分析錯誤在軟件MCN中的傳播行為，及其對軟件(SR)造成的影響。算法步驟如下：

步驟1 提取軟件方法調(diào)用網(wǎng)絡MCN(其實是MCN最大連通子圖，見實證部分的說明)作為算法的輸入；

步驟2 初始化算法運行的參數(shù)，包括：軟件MCN的節(jié)點數(shù)nNodes:=|M|；已經(jīng)植入的錯誤數(shù)iErrors:=0；MCN中總共的錯誤節(jié)點數(shù)nErrors:=0；被選擇植入錯誤的節(jié)點集合ierrorSet:=NULL；錯誤節(jié)點集合errorSet:=NULL；

步驟3 若nErrors=nNodes，令fc1:=iError，并保存fc1，轉(zhuǎn)步驟6執(zhí)行；否則，轉(zhuǎn)步驟4執(zhí)行；

步驟4 隨機的選擇節(jié)點i(i∈(M-ierrorSet))植入錯誤，并將其放入集合ierrorSet，即ierrorSet:=ierrorSet∪{i}，計算結(jié)構健壯度SR，errorSet:=errorSet∪EPF(i)；iError:=iError+1，nError:=|errorSet|，保存iError和對應的SR；

步驟5 若nErrors＜nNodes，返回步驟3繼續(xù)執(zhí)行；否則，執(zhí)行步驟6；

步驟6 保存數(shù)據(jù)，結(jié)束算法執(zhí)行。

算法2 錯誤受控植入。錯誤受控植入，即按使SR下降最快的節(jié)點順序植入錯誤。算法如下：

步驟1 提取軟件方法調(diào)用網(wǎng)絡MCN(其實是MCN最大連通子圖，見實證部分的說明)作為算法的輸入；

步驟2 初始化算法運行的參數(shù)，包括：軟件MCN的節(jié)點數(shù)nNodes:=|M|；已經(jīng)植入的錯誤數(shù)iErrors:=0；MCN中總共的錯誤節(jié)點數(shù)nErrors:=0；被選擇植入錯誤的節(jié)點集合ierrorSet:=NULL；錯誤節(jié)點集合errorSet:=NULL；

步驟3 計算MCN中所有節(jié)點i的|EPF(i)|，i∈M。選擇具有最大|EPF|的節(jié)點im，植入錯誤，并將其放入集合ierrorSet，即ierrorSet:=ierrorSet∪{im}，并將EPF(im)中的所有節(jié)點放入errorSet集，即errorSet:=EPF(im)∪errorSet，并使iError:=iError +1，nError:=|errorSet|，保存iError和對應SR；

步驟4 若nErrors=nNodes，令fc2=iError，并保存fc2，轉(zhuǎn)步驟7執(zhí)行；否則，轉(zhuǎn)步驟5執(zhí)行；

步驟5 計算(M-errorSet)集合中各個節(jié)點j的EPF(j)，j∈(M-errorSet)，令|EPF(j)|=|EPF(j)|- |EPF(j)∩errorSet|，即：排除EPF(j)中已在errorSet中的那些點；

步驟6 選擇具有最大|EPF|的節(jié)點jm，植入錯誤，并將EPF(jm)中的所有節(jié)點放入errorSet集，并使iError:=iError +1，nError:=|errorSet|，保存iError和對應SR，轉(zhuǎn)步驟4繼續(xù)執(zhí)行；

步驟7 保存數(shù)據(jù)，結(jié)束算法執(zhí)行。

比較算法1和算法2可以發(fā)現(xiàn)：算法1和算法執(zhí)行的次數(shù)可能不同，但2種算法最終都將使MCN中所有節(jié)點都成為錯誤節(jié)點。算法1中，受植入錯誤節(jié)點影響的節(jié)點也有可能被選擇植入錯誤；算法2中，一旦某一節(jié)點被選擇植入錯誤，則受該節(jié)點影響而出錯的其他節(jié)點將不可能被選擇植入錯誤。

雖然結(jié)構健壯度SR可用來描述錯誤動態(tài)植入過程中軟件結(jié)構的變化，但是，仍缺乏相應的度量來對軟件整體的結(jié)構質(zhì)量進行衡量。基于錯誤植入實驗中保存的SR值，提出了一個新的度量指標——軟件質(zhì)量系數(shù)(Software quality coefficient)SQC，用于從整體上對軟件的質(zhì)量進行評估。

從SQC的定義可以看出：它綜合考慮了軟件錯誤隨機植入和受控植入對軟件造成的影響，能夠比較全面的從錯誤傳播的角度對軟件的質(zhì)量進行度量。用SQC評價軟件質(zhì)量，SQC值越大說明軟件結(jié)構的質(zhì)量越好，錯誤通過軟件結(jié)構進行傳播的能力比較弱，軟件結(jié)構具有好的容錯能力；SQC越小，說明軟件結(jié)構對軟件錯誤比較敏感，軟件錯誤比較容易通過軟件的拓撲結(jié)構“放大”，從而對軟件造成極大破壞。因此，結(jié)構設計良好的軟件應使SQC盡可能大，以降低錯誤引入對軟件造成的影響。

2 實例驗證

2.1 數(shù)據(jù)來源

對將近20個開源的面向?qū)ο笙到y(tǒng)進行實例研究，都發(fā)現(xiàn)了類似的結(jié)果。這里以其中4個有代表性的系統(tǒng)為例進行說明。這些系統(tǒng)包括Tomcat 6.0.18(用java編寫的免費的Web服務器，支持Servlet和JSP規(guī)范，源代碼可在http://to mcat.apache.org/下載)、Azureus(用java編寫的BitTorrent的客戶端應用程序，用于下載發(fā)布的網(wǎng)上資源，源代碼可在http://azureus.sourceforge.net/下載)、Jxtaim0.1i(用java編寫的基于java加密擴展JCE和JXTA的即時通訊系統(tǒng)，源代碼可在http://jxtaim.sourceforge.net/下載)和jfreechart1.0.12(用java編寫的開放的圖表繪制類庫，是為application，applets，servlets以及JSP等使用所設計的。源代碼可在http://www.jfree.org/jfreechart/下載)。軟件規(guī)模(即方法的個數(shù))從1萬多到3萬多不等。結(jié)果如表1所示。

從軟件源代碼提取的MCN，并非是全連通的，往往有幾個子圖構成。由于一個子圖上的錯誤不會傳播到另外一個子圖，所以本文只關注各軟件MCN的最大弱連通子圖MWCC[19](Maximal Weekly Connected Components)，以此來對軟件的結(jié)構質(zhì)量進行研究。實驗中，算法1和算法2的輸入為MCN的最大弱連通子圖MWCC。圖4所示為各軟件MCN最大弱連通子圖的網(wǎng)絡圖。

表1 實驗系統(tǒng)的規(guī)模Table1 Statistics of subjects

圖4 軟件MCN的網(wǎng)絡圖Fig.4 Networks for MCNs of software

本文的實驗策略如下：首先，用MCN模型來描述這4個軟件系統(tǒng)，提取各個系統(tǒng)的MCN；然后，采用錯誤植入方法研究錯誤隨機植入和錯誤受控植入對MCN結(jié)構健壯度SR的影響，并分析決定SR的一些關鍵因素；最后，計算軟件質(zhì)量系數(shù)SQC，從整體上評價軟件的質(zhì)量，同時引入隨機有向網(wǎng)絡模型分析不同因素對軟件質(zhì)量系數(shù)SQC的影響。

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

圖5(a)～(d)所示為4個軟件MCN的結(jié)構健壯度SR與植入錯誤節(jié)點比例P(即|ierrorSet|/總的節(jié)點數(shù))的關系曲線圖。為了降低隨機因素對實驗結(jié)果的影響，每個錯誤隨機植入實驗都獨立運行了10 000次，計算每次運行中的SR，然后取平均值。

從圖5(a)～(d)可以發(fā)現(xiàn)：(1)在錯誤隨機植入和錯誤受控植入時，隨著P從0增加到1，4個系統(tǒng)MCN的SR都從1迅速下降，這說明軟件系統(tǒng)是非常脆弱的，軟件錯誤極易通過軟件的拓撲結(jié)構進行傳播，造成軟件大部分功能的失效；(2)錯誤受控植入時，SR的下降速度都比在錯誤隨機植入時要快。這說明軟件MCN對隨機錯誤具有一定的容錯能力，但是，對錯誤受控植入側(cè)很脆弱，少量節(jié)點的出錯就會使整個系統(tǒng)的性能降低一半；(3)在錯誤隨機植入和錯誤受控植入的過程中，一旦P超過某一臨界值(錯誤隨機植入時的Pc1，錯誤受控植入時的Pc2)，SR都減為0，出現(xiàn)了一種類似于“反向滲流轉(zhuǎn)變”的現(xiàn)象[20]。這說明，一旦P超過某一臨界值，錯誤就傳播到了MCN的所有節(jié)點中。并且錯誤受控植入時的臨界值Pc2一般比錯誤隨機植入時的Pc1要低得多。這是因為在錯誤受控植入是按SR下降最快的節(jié)點順序植入錯誤的。

由于MCN的SR值是通過|EPF|來計算的，因此，可以推測上述這些特征可能與節(jié)點的|EPF|有關。為此，研究了上述4個系統(tǒng)的|EPF|及其與其他參數(shù)的相互關系。

圖5(e)～(h)所示為4個系統(tǒng)相應的累積|EPF|分布?？梢姡哼@些系統(tǒng)的累積|EPF|分布大致服從冪率分布，而且具有“長尾”特征。這說明，網(wǎng)絡中大多數(shù)的節(jié)點只有很小的|EPF|，而少數(shù)節(jié)點卻擁有很大的|EPF|。所以，在錯誤隨機植入時，擁有較小|EPF|的節(jié)點更有可能先被選擇植入錯誤，而錯誤受控植入是按SR下降最快的順序選擇節(jié)點植入錯誤的，因此，錯誤選擇性植入時，SR的下降速度比在錯誤隨機植入時更快。

同時，研究了節(jié)點|EPF|和EB的相互關系，其散

點圖如圖6所示。圖中每個節(jié)點代表1個方法(|EPF|，EB)對?？梢园l(fā)現(xiàn)：雖然這些系統(tǒng)來自不同的領域，但|EPF|和EB的相關性都展現(xiàn)了相似的趨勢，即：|EPF|大的節(jié)點一般擁有較小的EB，而EB大的節(jié)點一般|EPF|較小。這說明那些EB大的節(jié)點(處于較高層次的方法)若植入錯誤，對系統(tǒng)其他部分的影響比較小，而|EPF|大的節(jié)點(處于較低層次)對系統(tǒng)的影響比較大，若它們被植入錯誤，將導致其他很多部分也出錯。在錯誤隨機實驗過程中發(fā)現(xiàn)，導致錯誤隨機植入時SR快速下降的不是那些具有較大|EPF|的節(jié)點(如圖6中矩形框內(nèi)的點)，因為這些節(jié)點數(shù)量較少，而是圖6中直線以上的節(jié)點，這些節(jié)點為數(shù)眾多，而且EB比較大，極易受其錯誤反向傳播域中節(jié)點的影響而成為錯誤節(jié)點。而那些同時具有較大|EPF|和EB的節(jié)點(如圖中橢圓框內(nèi)的節(jié)點)是最易出錯且危害也比較大的節(jié)點。因為這些節(jié)點擁有較大的EB，極易受到其錯誤反向傳播域中節(jié)點的影響而成為錯誤節(jié)點，一旦這些節(jié)點出錯，它又將影響其EPF中的節(jié)點，導致錯誤快速的在MCN上傳播，使SR迅速下降。

圖5 SR vs.P和Pcum(|EPF|)vs.|EPF|圖Fig.5 SR vs.P and Pcum(|EPF|)vs.|EPF|

圖6 各系統(tǒng)|EPF|和EB的散點圖Fig.6 Scatter point graph of |EPF| and EB

各個節(jié)點|EPF|與其入度和出度的pearson線性相關性分析結(jié)果如表2所示，其中，Kin和Kout分別表示節(jié)點的入度和出度。從表2可以發(fā)現(xiàn)：節(jié)點的|EPF|和其入度之間具有顯著度為0.01的正相關性。這說明入度大(重用率高)的節(jié)點，它們的|EPF|(影響范圍)往往很大，一旦這些入度大的節(jié)點出錯，將給系統(tǒng)帶來比較大的危害。這一點與文獻[10]中的研究結(jié)果相符。所以，重用雖然提高了軟件開發(fā)的效率，但是，也可能給軟件質(zhì)量帶來威脅，一旦重用率高的方法出錯，將造成其他很多方法也出錯。因此，對重用率高的方法，應該加大測試的力度，確保其正確性。同時還發(fā)現(xiàn)|EPF|與其出度具有顯著度為0.01負相關性，這說明處于較低層次的方法(|EPF|大的節(jié)點)不傾向于調(diào)用其他的方法。

表2 |EPF|和出/入度的相關性分析Table2 Correlation analysis of |EPF| and in/out-degree

為了從總體上評價錯誤植入對軟件造成的影響，從而評價軟件結(jié)構的質(zhì)量，計算了各個系統(tǒng)的SQC，結(jié)果如表3所示。通過對比表1和表3可以發(fā)現(xiàn)：SQC大的系統(tǒng)，其規(guī)模不一定小(如Azureus的SQC在4個系統(tǒng)中排第2，但其規(guī)模在4個系統(tǒng)中是最大的)，反之亦然。這表明并不是規(guī)模越大的系統(tǒng)就越難以保障其質(zhì)量，越簡單的系統(tǒng)其質(zhì)量就越容易控制，軟件的質(zhì)量與軟件的規(guī)模間并沒有必然的因果關系。

表3 MCN的SQC值Table3 SQC of MCN

由于網(wǎng)絡的結(jié)構可以通過各種參數(shù)來進行描述，如結(jié)構熵、平均度等[10]。為了進一步研究SQC和這些網(wǎng)絡統(tǒng)計參數(shù)之間的關系，引入文獻[21]中的隨機有向網(wǎng)絡模型，用該模型生成具有相同規(guī)模(即節(jié)點數(shù))、不同邊數(shù)的有向網(wǎng)絡，并研究了網(wǎng)絡結(jié)構熵、平均度、平均|EFP|(各節(jié)點|EFP|之和取平均值)、平均EB(各節(jié)點EB值之和取平均值)與SQC之間的相互關系。生成的網(wǎng)絡節(jié)點數(shù)為1 000，邊數(shù)從3 000到10 000不等。每種邊數(shù)的網(wǎng)絡都生成100個實例，計算得到的網(wǎng)絡的結(jié)構熵、平均度、平均|EFP|、平均EB和SQC，然后取平均值，以降低隨機因素的影響。圖7所示為具有相同節(jié)點數(shù)，不同邊數(shù)的網(wǎng)絡的結(jié)構熵、平均度、平均|EFP|、平均EB和SQC。其中：H表示網(wǎng)絡的結(jié)構熵；avg(Degree)表示平均度；avg(|EPF|)表示平均|EFP|；avg(EB)表示平均EB。表4所示為部分參數(shù)間的pearson線性相關性分析。

圖7 Tomcat 6.0.18有向網(wǎng)絡Fig.7 Direct networks of Tomcat 6.0.18

表4 參數(shù)間線性相關性分析Table4 Correlation analysis of parameters

從圖7和表4可以發(fā)現(xiàn)：(1)在網(wǎng)絡規(guī)模一定的情況下，隨著網(wǎng)絡中邊數(shù)的增加，結(jié)構熵H、平均度avg(Degree)，avg(|EPF|)和avg(EB)也隨之增大，但是，SQC逐漸減小。這說明在網(wǎng)絡規(guī)模一定的情況下，邊數(shù)的增加使網(wǎng)絡越來越“無序”，網(wǎng)絡的連通性增強，avg|EPF|和avg(EB)增大，軟件質(zhì)量系數(shù)SQC下降，即軟件的結(jié)構比較便于錯誤在其上傳播。因此，在軟件開發(fā)中，要將方法間的交互關系數(shù)控制在一定的范圍內(nèi)；(2)網(wǎng)絡結(jié)構熵H和平均|EPF|之間存在著顯著度為**的強正相關性，與SQC間存在顯著度為**的負相關性。這說明在網(wǎng)絡規(guī)模一定的情況下，網(wǎng)絡越“無序”，其平均錯誤傳播域就越高，軟件質(zhì)量就越低，極易被破壞。因此，軟件開發(fā)應該使軟件保持一定的“有序”性，這有利于提高軟件的質(zhì)量。這與文獻[10]中的研究結(jié)果相符；(3)avg|EPF|與軟件質(zhì)量系數(shù)SQC存在顯著度為**的負相關性。這說明網(wǎng)絡的平均錯誤傳播域越大，軟件質(zhì)量就越低。

3 結(jié)論

(1)將復雜軟件系統(tǒng)抽象成方法調(diào)用網(wǎng)絡，研究了錯誤在該網(wǎng)絡上的傳播行為，提出了量度軟件質(zhì)量的新度量——軟件質(zhì)量系數(shù)(SQC)。

(2)SQC能有效度量軟件質(zhì)量，并與其他結(jié)構參數(shù)具有密切的聯(lián)系：①節(jié)點|EPF|的冪律分布且具有“長尾”特征使軟件結(jié)構在錯誤隨機植入時比錯誤受控植入時更加健壯；②錯誤介數(shù)大的節(jié)點的大量存在使得軟件系統(tǒng)比較脆弱，極易被破壞；③入度大(重用率高)的節(jié)點是系統(tǒng)的關鍵點，這些點的出錯將給系統(tǒng)造成極大的損壞；④軟件質(zhì)量系數(shù)與網(wǎng)絡中的邊數(shù)有關，在網(wǎng)絡規(guī)模一定的情況下，邊數(shù)的增大將降低軟件質(zhì)量系數(shù)；⑤軟件質(zhì)量系數(shù)與軟件的結(jié)構熵有關，在網(wǎng)絡規(guī)模一定的情況下，軟件的結(jié)構熵越大(“無序”)，軟件質(zhì)量系數(shù)就越低；⑥軟件質(zhì)量系數(shù)與軟件的平均錯誤傳播域有關，在網(wǎng)絡規(guī)模一定的情況下，平均錯誤傳播域越大，軟件質(zhì)量系數(shù)就越低。

[1]Potanin A, Noble J, Frean M, et al.Scale-free geometry in OO programs[J].Communications of the ACM, 2005, 48(5):99-103.

[2]Concas G, Marchesi M, Pinna S, et al.Power-laws in a large object-oriented software systems[J].IEEE Transactions on Software Engineering, 2007, 33(10): 687-708.

[3]Pan W F, Li B, Ma Y T, et al.Multi-granularity evolution analysis of software using complex network theory[J].Journal of Systems Science and Complexity, 2011, 24(6): 1068-1082.

[4]韓明暢, 李德毅, 劉常昱, 等.軟件中的網(wǎng)絡化特征及其對軟件質(zhì)量的貢獻[J].計算機工程與應用, 2006, 42(20): 29-31.HAN Ming-chang, LI De-yi, LIU Chang-yu, et al.Networked characteristics in software and its contribution to software quality[J].Computer Engineering and Application, 2006, 42(20):29-31.

[5]閆棟, 祁國寧.大規(guī)模軟件系統(tǒng)的無標度特性與演化模型[J].物理學報, 2006, 55(8): 3799-3084.YAN Dong, QI Guo-ning.The scale-free feature and evolving model of large-scale software systems[J].Acta Phsica Sinica,2006, 55(8): 3799-3084.

[6]Krapivsky P L, Redner S.Network growth by copying[J].Physical Review E, 2005, 71(3): 036118.

[7]He K Q, Peng R, Liu J, et al.Design methodology of networked software evolution growth based on software patterns[J].Journalof Systems Science and Complexity, 2006, 19(2): 157-181.

[8]Pan W F, Li B, Ma Y T, et al.A novel software evolution model based on software networks[C]//1st International Conference of Complex Networks.Shanghai, 2009: 1281-1291.

[9]Vasa R, Schneider J G, Nierstrasz O.The inevitable stability of software change[C]//23nd IEEE International Conference on Software Maintenance.Paris, 2007: 4-13.

[10]Ma Y T, He K Q, Du D H, et al.A complexity metrics set for large-scale object-oriented software systems[C]//6th IEEE International Conference on Computer and Information Technology.Seoul, 2006: 189-194.

[11]Pan W F, Li B, Ma Y T, et al.Class structure refactoring of object-oriented software using community detection in dependency networks[J].Frontier of Computer Science in China,2009, 3(3): 396-404.

[12]MacCormack A, Rusnak J, Bald Win C Y.Exploring the structure of complex software designs: An Empirical Study of Open Source and Proprietary code[J].Manag Sci, 2006, 52:1015-1030.

[13]Liu J, Lu J H, He K Q, et al.Characterizing the structural quality of general complex software networks[J].International Journal of Bifurcation and Chaos, 2008, 18(4): 605-613.

[14]劉婧.基于復雜網(wǎng)絡的軟件結(jié)構分析及優(yōu)化研究[D].武漢:武漢大學軟件工程國家重點實驗室, 2007L 10-32.LIU Jing.Research on software structure analysis and optimization by applying complex network methodology[D].Wuhan: Wuhan University.State Key Laboratory of Software Engineering, 2007: 10-32.

[15]李愛國, 洪炳镕, 王司.基于錯誤傳播分析的軟件脆弱點識別方法研究[J].計算機學報, 2007, 30(11): 1910-1921.LI Ai-guo, HONG Bing-rong, WANG Si.An approach for identifying software vulnerabilities based on error propagation analysis[J].Chinese Journal of Computers, 2007, 30(11):1910-1921.

[16]Voas J, Morell L J.Propagation and infection analysis (PIA)applied to debugging [C]//IEEE Southeastcon’90.New Orleans,LA, 1990: 379-383.

[17]Hiller M, Jhumka A, Suri N.EPIC: Profiling the propagation and effect of data errors in software[J].IEEE Transactions on Computers, 2004, 53(5): 512-530.

[18]Johansson A, Suri N.Error propagation profiling of operating systems[C]//2005 International Conference on Dependable Systems and Networks (DSN).Yokohama, 2005: 86-95.

[19]Myers C R.Software systems as complex networks: Structure,function, and evolvability of software collaboration graphs[J].Physical Review E, 2003, 68(4): 046116.

[20]Albert R, Jeong H, Barabasi A L.Error and attack tolerance of complex networks[J].Nature, 2000, 406(6794): 378-382.

[21]Batagelj V, Mrvar A.Pajek 1.24[EB/OL].[2012-10-11].http://pajek.imfm.si/doku.php?id=down load