王　煒　李　彤　何　云　李　浩

(云南大學軟件學院　昆明　650091)

(wangwei@ynu.edu.cn)

?

一種軟件演化活動波及效應混合分析方法

王煒李彤何云李浩

(云南大學軟件學院昆明650091)

(wangwei@ynu.edu.cn)

A Hybrid Approach for Ripple Effect Analysis of Software Evolution Activities

Wang Wei, Li Tong, He Yun, and Li Hao

(SoftwareSchool,YunnanUniversity,Kunming650091)

AbstractRipple effect is defined as the process of determining potential effects to a subject system resulting from a proposed software evolving activity. Since software engineers perform different evolving activities to respond to different kinds of requirements, ripple effect analysis has been globally recognized as a key factor of affecting the success of software evolution projects. The precision of most existing ripple effect analysis methods is not as good as expectation and lots of methods have their inherent limitations. This paper proposes a hybrid analysis method which combines the dynamic and information retrieval based techniques to support ripple effect analysis in source code. This combination is able to keep the feature of high recall rate of dynamic method and reduce the adverse effects of noise and analysis scope by the domain knowledge which is derived from source code by information retrieval technique. In order to verify the effectiveness of the proposed approach, we have performed the ripple effect analysis and compared the analysis results produced by dynamic, static, text, historical evolving knowledge based methods with the proposed method on one open source software named jEdit. The results show that the hybrid ripple effect analysis method, across several cut points, provides statistically significant improvements in both precision and recall rate over these techniques used independently.

Key wordsripple effect analysis; dynamic ripple effect analysis; domain knowledge based noise reduction; minimal complete set of evolution activities; association rule mining

摘要確定演化活動潛在影響的過程稱之為波及效應分析.波及效應分析已經(jīng)被公認為影響軟件演化項目成敗的一個關鍵因素.針對當前波及效應分析準確率不高、各方法存在固有缺陷的問題，提出了一種混合波及效應分析方法，該方法將動態(tài)分析方法與文本分析方法相結合，在保持高召回率的基礎上，基于演化軟件領域知識降低了噪聲對分析結果的不利影響，約簡了分析范圍，提高了查準率.為驗證方法的有效性，對開源軟件jEdit分別使用動態(tài)、靜態(tài)、基于文本、基于歷史演化知識和混合分析方法進行波及效應分析.通過比對實驗結果，表明混合波及效應分析方法具有較好的綜合性能.

關鍵詞波及效應分析;動態(tài)波及效應分析;基于領域知識的降噪;演化活動最小完備集;關聯(lián)規(guī)則挖掘

確定演化活動潛在影響范圍的過程稱之為波及效應分析[1].波及效應分析是可追蹤性分析(traceability analysis)、演化代價估計(evolving cost estimation)、波及效應管理(ripple effects manage-ment)等研究的基礎[2-7].波及效應分析存在“兩高”：高成本和高難度.據(jù)統(tǒng)計，在長生命周期軟件系統(tǒng)中，50%～75%的成本用于軟件維護和演化，其中一半以上用于故障定位和波及效應分析[8].文獻[7]指出對jEdit,ArgoUML等中等規(guī)模的軟件系統(tǒng)進行波及效應分析，查準率在5%～18%.造成上述困境的原因有以下4點：1)與系統(tǒng)相關的需求文檔、設計文檔、用戶手冊、系統(tǒng)開發(fā)人員等資源遺失、不準確或無法訪問.2)傳統(tǒng)的波及效應分析是代碼驅動，即假設需要實施演化活動的目標代碼是已知的.實際情況是程序員無法直接確定演化活動的目標代碼，只能從演化意圖入手，確定演化活動的影響范圍.3)軟件系統(tǒng)規(guī)模越來越大，發(fā)生演化活動的頻度越來越高，執(zhí)行波及效應分析的時間間隔也變得越來越短.這要求分析者能夠快速響應演化需求.4)待演化軟件大多與其他軟件或操作系統(tǒng)交織在一起構成一個復雜的生態(tài)系統(tǒng)，因此很難對待演化系統(tǒng)的邊界進行明確劃分，增加了分析的難度.

按研究成果出現(xiàn)的先后順序，波及效應分析大致可以分為4類：靜態(tài)波及效應分析方法(static ripple effect analysis)、動態(tài)波及效應分析方法(dynamic ripple effect analysis)、基于文本的波及效應分析方法(text based ripple effect analysis)和基于歷史演化知識的波及效應分析方法(historical evolution knowledge based ripple effect analysis).

靜態(tài)分析方法將源代碼、設計文檔等靜態(tài)數(shù)據(jù)作為輸入，通過獲取靜態(tài)數(shù)據(jù)間的控制流、數(shù)據(jù)流關系，實現(xiàn)波及效應建模、分析.1996年Bohner[9-10]基于可達矩陣提出了最早的波及效應靜態(tài)分析方法.隨后，學者們使用不同工具(可達圖、可達矩陣等)從不同粒度(構件、類、方法，變量)分別提出了各自的分析和預測方法[11-13].靜態(tài)方法具有較強的易用性，但由于控制流和數(shù)據(jù)流在大型軟件系統(tǒng)中十分復雜，無法自動判定確切的問題邊界，需要大量人工介入，分析過程開銷隨著軟件復雜程度呈指數(shù)級增長.分析結果的準確性依賴于開發(fā)人員對軟件結構的理解程度.

動態(tài)波及效應分析方法將執(zhí)行跡(execution traces)作為輸入數(shù)據(jù)，通過捕獲執(zhí)行跡與用例間的映射關系實現(xiàn)波及效應的建模和分析.根據(jù)執(zhí)行跡獲取方式的不同，動態(tài)分析方法可以分為[14]：基于功能覆蓋[5]和基于執(zhí)行路徑的分析方法[4,15].上述方法均需要設計并執(zhí)行測試用例，區(qū)別在于測試用例是否形成對功能點或對程序執(zhí)行路徑的覆蓋.相較于靜態(tài)分析方法，此類方法可獲得較高的召回率.但由于應用軟件生態(tài)環(huán)境的復雜性，導致采集到的執(zhí)行跡中包含了大量與軟件功能不相干的噪聲數(shù)據(jù)，查準率較低.因此，傳統(tǒng)的動態(tài)分析方法需要對同一用例多次采集執(zhí)行跡，通過比對實現(xiàn)去噪.這導致了動態(tài)分析方法同樣需要大量人工介入，效率較低.

源代碼、變更請求(change request)等軟件實體(software artifacts)蘊含著大量的領域知識.基于文本的波及效應分析方法對變更請求[16-17]和源代碼[18-19]中的領域知識進行抽取，通過對比領域知識與軟件功能描述之間的相似度實現(xiàn)波及效應分析.對比靜態(tài)和動態(tài)分析方法，基于文本的波及效應分析方法具有較高的查準率，但召回率較低.另外，該方法的有效性很大程度上依賴于變更信息的多寡、代碼中變量命名的規(guī)范性以及用詞習慣等因素，上述因素導致了該方法的普適性較差.

軟件系統(tǒng)在日常運行過程中積累了大量諸如開發(fā)者來往郵件、軟件維護日志等歷史數(shù)據(jù).這些歷史數(shù)據(jù)中蘊含著豐富的軟件體系結構、演化決策等知識.學者們對上述數(shù)據(jù)進行挖掘，并據(jù)此進行波及效應分析和預測[20-21].與基于文本的波及效應分析方法類似，此類分析方法性能同樣受制于歷史演化知識的多寡、檢索關鍵詞用詞習慣等因素.

靜態(tài)、動態(tài)、基于文本和歷史演化知識的波及效應分析方法可以識別演化活動的波及范圍，但大多無法對波及范圍進行定量刻畫.同時，各方法具有各自優(yōu)點，但也存在固有缺陷.一種比較自然的想法是將上述方法進行整合，在充分發(fā)揮其優(yōu)點的基礎上，盡可能規(guī)避其固有缺陷.

本文提出的波及效應混合分析方法，具有3個特點：

1) 實現(xiàn)了對現(xiàn)有波及效應分析方法的無縫整合.在充分發(fā)揮動態(tài)分析方法召回率高的基礎上，基于文本分析方法實現(xiàn)對執(zhí)行跡的降噪，提高了查準率，縮減了分析范圍.建立波及效應圖實現(xiàn)量化分析方法.

2) 更貼近于實際應用.從故障現(xiàn)象入手是一種用例驅動的波及效應分析方法.

3) 傳統(tǒng)動態(tài)波及效應分析方法需要對執(zhí)行跡進行多次采集，而本文方法僅需要進行一次執(zhí)行跡采集，降低了分析開銷.

1本文方法

如圖1所示，本方法首先獲取與演化活動用例對應的執(zhí)行跡；其次基于文本分析方法，實現(xiàn)對執(zhí)行跡的降噪；在此基礎上識別代碼間的波及關系，構造波及效應圖，實現(xiàn)量化分析.

Fig. 1　Overview of hybrid ripple effect analysis method.圖1　混合波及效應分析方法概況

1.1執(zhí)行跡獲取

執(zhí)行跡記錄了軟件在運行過程中消息的傳遞序列，反映了特定環(huán)境下軟件系統(tǒng)的行為屬性.

定義1. 有限非空序列p=u1,u2,…,un定義為一個進程，記錄了軟件系統(tǒng)各組成單元ui間的消息傳遞序列.

根據(jù)粒度大小組成單元可分為：服務、構件、類、方法(函數(shù))等.

定義2. 有限非空集合SET={p1,p2,…,pm}為執(zhí)行用例U時產生的執(zhí)行跡，其中pi為進程.若|SET|=m,則稱SET是m元執(zhí)行跡.

執(zhí)行跡的獲取包含3個步驟：

1) 編寫與演化活動相關的用例.用例應能夠反映演化意圖，例如系統(tǒng)功能的刪除、添加、遷移等.

2) 在源代碼中設置檢查點(check point)用以觀察程序運行時消息的傳遞過程，并將帶有檢查點的代碼進行編譯形成可執(zhí)行文件.

3) 執(zhí)行用例，觀測并收集與用例相關的執(zhí)行跡.

表1為執(zhí)行跡片段示例:

Table 1　Execution Traces Slice Sample of Thread main

與傳統(tǒng)的動態(tài)分析方法需要對同一用例多次采集執(zhí)行跡，進行人工比對實現(xiàn)降噪不同.本方法僅需要進行一次執(zhí)行跡的獲取.降噪過程由1.2節(jié)實現(xiàn).這大大節(jié)省了執(zhí)行跡獲取的開銷，提高了整個分析過程的自動化程度.

1.2基于領域知識的執(zhí)行跡降噪

源代碼的變量名、函數(shù)名、類(對象)名、API函名、注釋等蘊含了豐富的領域知識.本節(jié)降噪過程描述如下：

1) 生成語料庫.為源代碼中每一個類(函數(shù))建立一個文本文件，提取類代碼中蘊含領域知識的關鍵詞存入該文件.所有類對應的文本文件構成語料庫.

表2為1個由6個文本文件組成的語料庫示例.其中每一行代表一個與源代碼對應的文本文件.

Table 2　Corpus Sample

2) 預處理.語料庫中存在很多與領域知識不相關或重復的信息，需要刪除達到降噪的目的.預處理包含去除停詞(stop words)、分詞、詞干還原3部分.去除停詞將刪除與領域知識不相關的詞，例如表2中的this,one,the,about等詞;分詞操作將連續(xù)的字符序列按照一定的規(guī)則拆分成若干單詞，例如將表2中的tableOpen拆分成為table和open兩個詞；詞干還原將意義相近的同源詞和同一個單詞的不同形態(tài)進行歸并，例如將表2中的inserting還原成為insert.

3) 生成詞頻矩陣.將經(jīng)過預處理的語料轉換為詞頻矩陣，該矩陣的行表示在語料庫中出現(xiàn)過的單詞，列是對一個類中關鍵詞的計數(shù).矩陣元素ti j表示第i個單詞在第j個類中出現(xiàn)的次數(shù).表3給出了與表2對應的詞頻矩陣.

Table 3　Term Frequency Matrix Sample

4) 獲取演化活動用例對應代碼集合.將演化活動用例的文字性描述轉化為向量作為輸入，使用潛在語義索引(latent semantic indexing, LSI)對詞頻矩陣進行索引排序.設定相似度閾值，凡大于閾值的向量所對應的類組成演化活動用例對應的代碼集合.

例如開發(fā)人員提交的演化活動用例描述為“Crash when inserts a word into a document”.如表3所示，該用例描述對應的向量為Q=(0,1,1,1,0,0,0,0,0,0,0,0,0)T，通過計算Q與表3中詞頻矩陣的相似度，有以下結果：

Sim(Q,code1)>Sim(Q,code4);

Sim(Q,code2)>Sim(Q,code5);

Sim(Q,code3)>Sim(Q,code6).

傳統(tǒng)基于文本的波及效應分析[22]使用經(jīng)驗相似度閾值α=0.007 5.但筆者在實驗中發(fā)現(xiàn)，當數(shù)據(jù)規(guī)模較大時，經(jīng)驗相似度閾值α=0.007 5效果并不理想.因此，我們使用文獻[23]推薦的方法，取相似度最高的10%～15%的代碼作為索引結果.

5) 求交運算.將執(zhí)行跡對應的代碼集合SEC與本節(jié)產生的演化活動用例對應的代碼集合求交集.凡是不在上述2集合中同時出現(xiàn)的類均認為是噪聲類.噪聲類要么沒有在用例執(zhí)行時被實際調用，要么與演化用例不相關.噪聲類的去除減少了波及效應分析的數(shù)據(jù)量.將降噪結果作為1.3節(jié)波及效應分析的輸入數(shù)據(jù).

1.3波及效應分析

本節(jié)將經(jīng)過降噪處理的執(zhí)行跡代碼作為輸入，依次執(zhí)行3個步驟，對演化活動的波及效應進行量化分析：

1) 識別波及關系；

2) 構造波及效應圖；

3) 波及效應量化分析.

1.3.1波及關系識別

代碼間的波及關系刻畫了若一個類被修改則另一個類也會被修改的事實.

筆者認為波及關系是波及效應存在的根本原因.對面向對象軟件執(zhí)行演化活動時，對象間存在依賴、關聯(lián)、泛化和實現(xiàn)關系均可以用波及關系表示.類ci和cj間的依賴關系表示了ci發(fā)生變化而影響到cj也發(fā)生變化的語義.因此，對類ci執(zhí)行演化活動時必然存在波及關系ci→cj.類ci和cj間的關聯(lián)關系是一種特殊的依賴關系，既構成依賴關系的類ci和cj間相互存在依賴關系.因此，演化活動發(fā)生時，必然存在2個關聯(lián)關系ci→cj,cj→ci.泛化關系刻畫了一般類與特殊類之間的繼承關系.若類ci和cj間存在泛化關系，且ci是特殊類、cj是一般類，則對ci進行修改必然導致cj的變化，因此必然存在波及關系ci→cj.實現(xiàn)關系是泛化關系和依賴關系的結合，表示了接口和實現(xiàn)它功能類之間的語義關系.接口ia與類ci間存在實現(xiàn)關系，對ia進行修改必然導致類ci要進行相應的修改，反之亦然.因此，若接口ia和類ci間存在實現(xiàn)關系，則存在波及關系ia→ci和ci→ia.在結構化軟件系統(tǒng)中，函數(shù)間通過調用關系實現(xiàn)具體計算功能.設函數(shù)fi調用函數(shù)fj，且fj返回計算結果給fi，顯然存在波及關系fi→fj,fj→fi關系.若fj不返回計算結果給fi，則僅存在波及關系fi→fj關系.綜上所述，針對任意演化活動，軟件各類實體具有的關系均可以用波及關系刻畫.

矩陣Kn×n為波及關系的存儲介質.以面向對象軟件系統(tǒng)為例，類i與類j間存在波及關系，當且僅當i和j兩個類間存在關聯(lián)關系，或第i個類是第j個類的特殊類，或第i個類依賴第j個類，或i和j兩個類間存在實現(xiàn)關系，記為ki j=1，否則ki j=0.波及關系的方向性由行和列分別表示，行為起始類，列為終結類.例如表4第1行、第6列為1，表示c1與c5之間存在波及關系，且c1→c5.

Table 4　Ripple Effect Relationship Matrix of Some Software

1.3.2波及效應圖構造

波及效應圖是波及效應量化分析的基礎.整個構造過程包括2個方面：邊集合識別和波及效應圖構造.

1) 邊集合識別

波及效應圖的邊集合由波及關系集合充當.算法1描述了波及關系圖邊集合的識別過程.

算法1. 波及效應圖邊集合識別算法.

輸入：軟件波及關系矩陣K、支持度Support和置信度Conf；

輸出：波及效應圖邊集合E.

① 計算波及關系矩陣的傳遞閉包K+;

② 基于支持度Support對K+進行頻繁類集挖掘;

③ 基于置信度Conf對頻繁類集中的波及關系進行識別，生成波及效應圖邊集合E.

算法1中行①K+=K∨SK1∨…∨Kn定義為波及關系矩陣K的傳遞閉包矩陣，其中Ki=K∨Ki-1.

算法1中行②③采用關聯(lián)關系挖掘方法[24]，實現(xiàn)頻繁類集和波及關系的識別.根據(jù)算法要求，做如下定義：

定義6. 傳遞閉包矩陣K+行i中取值為1的元素組成的集合ki={ki1,ki2,…,kin}定義為第i個類的演化事務.有限非空集合T={k1,k2,…,kn}是軟件系統(tǒng)的演化事務集合.

集合ki={ki1,ki2,…,kin}描述了對第i個類實施演化活動將導致ki集合中的類也將進行演化活動.表5給出了與表4對應的傳遞閉包矩陣，可以看出在演化事務k1中，若對c1實施演化活動將導致c1,c2,c4,c5,c6也需要進行演化.

Table 5　The Transitive Closure of Table 4

定義8. 設T={k1,k2,…,kn}為演化事務集合，一條波及關系ci→cj的支持度定義為

定義9. 設T={k1,k2,…,kn}為演化事務集合，一條波及關系ci→cj的置信度定義為

直觀上來看，波及關系ci→cj的支持度定義為包含(ci∪cj)的演化事務在整個演化事務集合中的百分比.置信度刻畫了演化事務集合既包含ci又包含cj的數(shù)量占所有包含ci的事務的百分比.支持度取值越小說明此波及關系的偶然性越強，取值越大說明此波及關系的必然性越強.置信度描述了類ci發(fā)生演化情況下類cj也需要進行演化的條件概率p(cj|ci)，置信度取值越高說明該波及關系前后件間的聯(lián)系越緊密.

定義10. 一個頻繁類集是支持度高于Support的類組成的集合.稱一個基數(shù)為k的頻繁類集合為k-頻繁類集，記為Fk.

當Support=60%，Conf=60%時，表5經(jīng)過算法1計算可產生如下計算結果：

F1={(c2),(c4),(c6)},F2={(c2,c4),(c2,c6),(c4,c6)},F3={(c2,c4,c6)}，波及效應圖邊集合E={c6→c4,c4→c6,c6→c2,c2→c6,c4→c2,c2→c4,c6→(c2,c4),c4→(c2,c6),c2→(c4,c6)}，各波及關系的置信度分別為{1.0,0.67,1.0,0.67,1.0,1.0,1.0,0.67,0.67}.

2) 波及效應圖構造

圖2給出了與表5對應的波及效應圖：

Fig. 2　Ripple effect graph of Table 5.圖2　表5對應的波及效應圖

軟件演化的基本活動包括添加、刪除、替換、和遷移4類活動[25].基于波及效應圖，本文對上述4類演化活動做如下定義：

定義12. 設GRE=(V,E,L)為波及效應圖.

1) 設v?V，謂詞add(GRE,v)表示在GRE中添加v以及與v存在波及關系的邊，稱為添加v活動;

2) 設v∈V，謂詞del(GRE,v)表示從GRE中刪去v以及與v存在波及關系的邊，稱為刪除v活動;

3) 設v∈V,v′?V，謂詞sub(GRE,v′,v)表示用v′替換GRE中的v，并且刪除與v存在波及關系的邊，增加與v′存在波及關系的邊，稱為替換v活動;

4) 設v∈V，謂詞mig(GRE,v)表示修改與v存在波及關系的邊的連接屬性，稱為遷移v活動.

圖3～6分別描述了對圖2實施的增加頂點v、刪除頂點(c2,c4,c6)、用頂點v′替換頂點(c2,c4,c6)和遷移頂點(c2,c4,c6)演化活動.

Fig. 5　Substitute vertex (c2,c4,c6) with v′ for Fig. 2.圖5　對圖2用頂點v′替換頂點(c2,c4,c6)

Fig. 3　Add vertex v to Fig. 2.圖3　對圖2添加頂點v

Fig. 4　Delete vertex (c2,c4,c6) from Fig. 2.圖4　對圖2刪除頂點(c2,c4,c6)

Fig. 6　Migrate vertex (c2,c4,c6) for Fig. 2.圖6　對圖2遷移頂點(c2,c4,c6)

1.3.3波及效應量化分析

本節(jié)基于波及效應圖從演化活動的波及范圍和波及程度2方面進行量化分析.

定理1. 集合{add(GRE,v),del(GRE,v)}構成軟件演化活動集合的最小完備集.

證明. 要證明{add(GRE,v),del(GRE,v)}是軟件演化活動集合的最小完備集，就必須證明：1)所有其他演化活動均可以使用add(GRE,v)和del(GRE,v)表示，即要證明sub(GRE,v′,v)和mig(GRE,v)能被add(GRE,v)和del(GRE,v)表示.2)若刪除add(GRE,v)或del(GRE,v)其中任一活動，sub(GRE,v′,v)和mig(GRE,v)活動將不能表示.

1) 根據(jù)sub(GRE,v′,v)定義可知，替換活動可視為首先從GRE中刪除v以及與v存在波及關系的邊，然后添加v′以及與v′存在波及關系的邊.因此，sub(GRE,v′,v)可認為是del(GRE,v)和add(GRE,v′)活動的復合，可以用del(GRE,v)和add(GRE,v′)表示.

2) 根據(jù)mig(GRE,v)定義可知，mig(GRE,v)是v′=v情況下sub(GRE,v′,v)的一個特例.因此，mig(GRE,v)也可以用add(GRE,v′)和del(GRE,v)表示；綜上所述，add(GRE,v′)和del(GRE,v)是軟件演化活動的完備集.

3) 根據(jù)以上分析刪除add(GRE,v′)或del(GRE,v)其中任意之一，mig(GRE,v)和sub(GRE,v′,v)均不能表達，因此add(GRE,v′)和del(GRE,v)是軟件演化活動集合的最小完備集.

證畢.

根據(jù)定理1可知，軟件演化波及效應分析可以約簡為對add(GRE,v′)和del(GRE,v)演化活動波及效應的分析.

定義13. 設波及效應圖為GRE=(V,E,L)，?v1,v2∈V,若v1,v2間存在通路，記為v1Rv2.v1,v2間的通路長度Len(v1,v2)稱為v1對v2的影響深度.若v1=v2，則Len(v1,v2)=0.

定理2. 設波及效應圖為GRE=(V,E,L)，?v1,v2∈V,若v1,v2間存在通路，則Len(v1,v2)≤|V|-1.

證明. 設W=v0v1…vl為GRE中長度為l的通路，且始點為v0，終點為vl.若l≤|V|-1，則W為滿足要求的通路；否則，即l>|V|-1，也就是W中的頂點數(shù)大于GRE的頂點數(shù).則必然存在s,k,滿足0≤s

證畢.

定義14. 設波及效應圖為GRE=(V,E,L)，del(GRE,v′)為施加于GRE上的刪除演化活動.則刪除演化活動的波及范圍dea(GRE,v′)={v|Len(v,v′)≥1或Len(v′,v)≥1}

定義15. 設波及效應圖為GRE=(V,E,L)，add(GRE,v′)為施加于GRE上的添加演化活動.則添加演化活動的波及范圍aea(GRE,v′)={v|Len(v,v′)≥1或Len(v′,v)≥1}.

通過波及范圍的定義可以計算對某一代碼所實施的演化活動所影響到的范圍.

定義16. 設波及效應圖為GRE=(V,E,L)，dea(GRE,v′)和aea(GRE,v′)分別為對節(jié)點v′實施刪除和添加演化活動的影響范圍.若v∈dea(GRE,v′)或者v∈aea(GRE,v′)，則v對v′∈V波及程度定義為

ImpactDegree(v)=

其中，idi是v到v′的第i條路徑上各邊對應置信度的乘積，n是v到v′的通路數(shù)量.

波及程度是一個概率屬性，該屬性描述了對代碼v′實施的演化活動將導致代碼v發(fā)生相應演化活動的最大概率.取值越高說明波及效應發(fā)生的概率越大.如圖2所示，頂點(c2)對頂點(c2,c4)的波及程度為0.67×1.0=0.67.

對于波及效應圖GRE而言，對某代碼實施演化活動不產生波及效應的條件是該代碼在波及效應圖上是一個孤立點.

定理3. 設GRE=(V,E,L)為波及效應圖，對v∈V實施演化活動不產生波及效應，當且僅當v是GRE的孤立點.

證明. 若頂點v是孤立點，則v無有向邊與之連接，即v不與其他類(方法、函數(shù))具有波及關系.刪除或添加v不會影響其他類(方法、函數(shù))，當然也就不存在波及效應.

若刪除和添加v不影響其他類(方法、函數(shù))的執(zhí)行，則說明v與其他類(方法、函數(shù))無波及關系，即v與其他類(方法、函數(shù))之間不存在邊連結，則v是孤立點.

證畢.

如圖2所示，點(c2,c4,c6)就是孤立點，對該點實施演化活動對其他點不會產生波及效應.

2實驗

由于本文方法與動態(tài)方法[5]、基于文本[18]和基于歷史演化知識的波及效應分析方法[21]均屬于用例驅動的方法，可以采用統(tǒng)一的指標衡量其性能.在實驗部分進行了定量對比.靜態(tài)波及效應分析方法[12]是代碼驅動的，與本文方法不屬于同一類，因此在實驗部分對靜態(tài)方法與本文方法進行了定性比對.通過對比，完成2個問題的研究和分析:

研究問題1.與其他方法進行對比證明本文方法的有效性.

研究問題2.支持度和置信度參數(shù)對本文方法的影響及其作用機理.

2.1實驗過程

2.1.1實驗對象

為保證實驗結果的客觀性，采用開源軟件jEdit①作為實驗對象，其簡要情況如表6所示：

Table 6　Brief Introduction of jEdit

2.1.2實驗過程

本文實驗過程包含5個步驟：

1) 生成用例.從jEdit缺陷追蹤系統(tǒng)②中抽取故障用例描述、演化結果信息.如表7所示，id是故障用例在缺陷追蹤系統(tǒng)中的唯一標識，用例描述是對現(xiàn)象的文字描述，演化結果記錄了修復故障用例涉及的類.

Table 7　Fault Use Cases Description

Continued (Table 7)

2) 獲取執(zhí)行跡.采用Flat3①采集與用例對應的執(zhí)行跡，將執(zhí)行跡存儲為JPAD②格式.各用例對應執(zhí)行跡概況如表8所示:

Table 8　Execution Trace Description

3) 執(zhí)行跡降噪.使用TMG③對jEdit源代碼建立TF-IDF矩陣，如表9所示.將每一個用例相對應的用例描述作為查詢條件，采用LSI計算TF-IDF矩陣中與查詢條件相似的類集合SDC.求執(zhí)行跡類集合SEC與領域知識對應類集合SDC的交集，實現(xiàn)執(zhí)行跡降噪.

4) 生成波及關系.將經(jīng)過降噪處理的代碼導入starUML④生成類圖，存儲為xml格式數(shù)據(jù).處理該xml數(shù)據(jù)產生波及關系矩陣K，計算K的傳遞閉包，并構造波及效應圖；

5) 與動態(tài)、基于文本和歷史演化知識的波及效應分析方法進行定量比對，與靜態(tài)波及效應分析方法進行定性比對.

Table 9　TF-IDF Matrix

2.2評價標準

度量波及效應分析方法的好壞是看預測演化活動影響范圍是否接近于實際影響范圍.在以往研究中提出多種指標作為量化分析結果好壞的標準[26-27].在眾多的指標中查準率和召回率是使用最廣的2個指標[26-29].其中,查準率反映了預測影響范圍與實際影響范圍的一致性，召回率反映了預測影響范圍在實際影響范圍中的占比.高查準率意味著將花費較少的開銷來確定演化活動的波及范圍，高召回率意味著凡是通過算法推薦的波及范圍均是可信的.

定義17. 設有限非空集合SI,SC分別表示各波及效應分析方法檢出代碼集合和實際演化活動所影響的代碼集合.查準率、召回率分別定義如下：

針對本文提出方法，SI集合對應于波及效應圖的所有頂點集合的并集，實際波及范圍由表7中演化結果記錄.

定義18. 設Pour,Rour分別表示使用本文方法進行波及效應分析的查準率和召回率，Pb,Rb表示使用動態(tài)、基于文本或基于歷史演化知識進行波及效應分析的查準率和召回率.查準率增益、召回率增益分別定義如下：

查準率增益PGain和召回率增益RGain二個參數(shù)刻畫了本文方法較其他方法的性能增幅.

定義19. 設P,R分別表示查準率和召回率，則調和平均數(shù)F定義為

由于查準率和召回率具有互逆關系，無法描述波及效應分析方法的綜合性能，本文使用調和平均數(shù)F(F-measure)度量波及效應分析方法的綜合性能.

2.3實驗結果

2.3.1與動態(tài)、文本和歷史演化知識分析方法比對

當Support=0.05時，各方法查準率如圖7所示，本文方法平均查準率為28.52%，動態(tài)分析方法平均查準率為4.25%，基于文本的分析方法平均查準率為5.63%，基于歷史演化知識分析方法的平均查準率為25.61%.本文方法查準率較動態(tài)和文本2方法取得了較大提高，基于歷史演化知識方法的查準率接近本文方法，特別是id=1 538 702的錯誤用例，獲得了71.43%的查準率.

Fig. 7　Precession comparison graph.圖7　查準率對比圖

當Support=0.05時，各方法召回率如圖8所示，本文方法平均R=50.07%，動態(tài)分析方法平均召回率為73.56%，基于文本的分析方法平均召回率為71.56%，基于歷史演化知識的分析方法平均召回率為16.83%.本文方法較基于歷史演化知識的波及效應分析方法召回率取得了較大提高，但較其余2方法低.

Fig. 8　Recall comparison graph.圖8　召回率對比圖

查準率增益PGain和召回率增益RGain比對結果如圖9和圖11所示.在Support=0.05情況下，本文方法相較于動態(tài)方法，查準率的平均增益為760.02%;相較于文本方法，查準率的平均增益為482.07%;相較于基于歷史演化知識方法，查準率的平均增益為10.19%.對比動態(tài)方法召回率平均增益為-35.67%，對比文本方法召回率平均增益為-33%，對比基于歷史演化知識方法召回率平均增益為219.88%.

Fig. 9　Precession gain graph.圖9　查準率增益圖

Fig. 10　Recall gain graph.圖10　召回率增益圖

調和平均數(shù)F比對結果如圖11所示.在Support=0.05情況下,4種方法平均調和平均數(shù)分別為36.34%，8.04%，10.46%，20.31%.

Fig. 11　F-measure graph.圖11　調和平均數(shù)圖

2.3.2與靜態(tài)方法實驗對比

由于演化活動用例具有直觀性，同時也較容易觀測和記錄，因此即便是未經(jīng)過專業(yè)訓練的程序員也能使用本方法進行波及效應分析.而靜態(tài)波及效應分析方法是代碼驅動的分析方法，需要在確定演化活動目標代碼的前提下才能進行波及效應分析.在缺乏有效軟件設計文檔、用戶手冊等數(shù)據(jù)支持的情況下，要明確演化活動的目標代碼將是非常困難的，后繼的波及效應分析也將難以實現(xiàn).這導致了本文提出方法較靜態(tài)波及效應分析方法更貼近實際應用.

同時，靜態(tài)波及效應分析方法需要將軟件系統(tǒng)的所有源代碼作為輸入，構造可達圖或可達矩陣實現(xiàn)波及效應分析.整個分析過程隨著代碼量的增長呈指數(shù)級增長.筆者采用文獻[13]提出的可達矩陣對jEdit4.3進行波及效應分析.結果顯示jEdit4.3對應的可達矩陣是一個531×531的方陣，矩陣的生成時間(不含數(shù)據(jù)預處理)為13 min 22 s(計算平臺CPU:Intel i5-4200，內存：4 GB，操作系統(tǒng)：Windows8).由此可見靜態(tài)波及效應分析方法對類似jEdit這樣中小規(guī)模的軟件系統(tǒng)分析有較大的計算開銷.而本文方法由于是對經(jīng)過降噪的執(zhí)行跡進行分析，在相同計算平臺下，構造波及效應圖計算時間(不含數(shù)據(jù)預處理時間)為3 min 13 s.因此本文方法較靜態(tài)方法具有更高的效率.

2.3.3波及效應量化分析

動態(tài)、靜態(tài)、基于文本和基于歷史演化知識的波及效應分析方法大多不具備量化分析能力.在實驗中為每一個用例建立了一個波及效應圖，通過對波及效應圖的分析可實現(xiàn)對任意演化活動波及范圍的量化分析.圖12給出了故障用例950 961對應的波及效應圖，圖12中頂點顏色越深表示執(zhí)行演化活動時越容易受波及.表10給出了實施每一個演化活動時最容易受到波及的代碼集合及其波及程度量化結果.

Fig. 12　Ripple effect graph of failure use case 950 961.圖12　故障用例950 961對應的波及效應圖

idTheMostTrustwrothyRippleEffectConfidence950961jedit.org.gjt.sp.jedit.textarea.BufferHandler.java→jedit.org.gjt.sp.jedit.textarea.DisplayManager.java0.851292706jedit.org.gjt.sp.jedit.browser.VFSFileNameField.java→jedit.org.gjt.sp.jedit.browser.VFSBrowser.java0.941538702jedit.org.gjt.sp.jedit.gui.DockableWindowFactory.java→jedit.org.gjt.sp.jedit.jEdit.java0.941578785jedit.org.gjt.sp.jedit.bufferset.BufferSetManager.java→jedit.org.gjt.sp.jedit.View.java0.941638642jedit.org.gjt.sp.jedit.ServiceManager.java→jedit.org.gjt.sp.jedit.jEdit.java0.871658252jedit.org.gjt.sp.jedit.bsh.BSHCastExpression.java→jedit.org.gjt.sp.jedit.syntax.TokenMarker.java0.871676041jedit.org.gjt.sp.jedit.textarea.FirstLine.java→jedit.org.gjt.sp.jedit.syntax.TokenMarker.java0.741913979jedit.org.gjt.sp.jedit.options.BrowserOptionPane.java→jedit.org.gjt.sp.jedit.indent.RegexpIndentRule.java0.912696564jedit.org.gjt.sp.jedit.bufferset.BufferSetAdapter.java→jedit.org.gjt.sp.jedit.syntax.TokenMarker.java0.712896464jedit.org.gjt.sp.jedit.pluginmgr.MirrorList.java→jedit.org.gjt.sp.util.IntegerArray.java0.72

2.3.4支持度、置信度參數(shù)的影響

為了驗證支持度、置信度對本文方法的影響，選取故障用例950 961進行測試，在所有操作均相同的前提下，分析改變支持度和置信度的取值對查準率、召回率以及波及關系生成數(shù)量的影響.詳細結果如表11、表12所示.

從表11可以看出，當支持度從0.05開始下降時，代碼檢出量增加，導致查準率持續(xù)降低，召回率保持不變;當Support=0.02時，查準率增加至13.33%，召回率也同時增加至40%;隨著支持度繼續(xù)降低，導致查準率持續(xù)降低，召回率持續(xù)提高，并最終達到100%.通過實驗可知，Support=0.02是一個最優(yōu)取值.在該取值下可以獲得較高的查準率和召回率.從表12可以看出，當置信度持續(xù)降低，產生波及關系的數(shù)量不斷增加.

Table 11Relationship Between Support Precision and Recall

表11　查準率、召回率與支持度取值的關系

Table 12Relationship Between the Amount of Ripple

Effect Relationship and Confidence

表12　波及關系數(shù)量和置信度取值的關系

通過分析可知，支持度取值將影響本文方法的查準率和召回率，伴隨著支持度的降低，將導致查準率的降低、召回率的增高，但查準率的降低并不是一個線性過程.因此，支持度的取值需要對演化軟件具有一定的了解.置信度取值將影響對波及效應進行量化分析，取值越小越能夠對小概率波及效應進行量化分析.

3結論

本文提出的混合波及效應分析方法，通過與動態(tài)、靜態(tài)、基于文本和基于歷史演化知識的波及效應分析方法進行比對實驗，結果顯示，本文方法是一種以適當犧牲召回率為代價從而大幅提高查準率的新方法.通過對調和平均數(shù)的比對，顯示本文方法具有綜合性能好的特點.

針對影響本文方法的2個重要因素：支持度和置信度，本文進行了影響機制分析.我們注意到，支持度設置將影響波及效應分析的查準率、召回率，進而影響查準率增益、召回率增益以及調和平均數(shù).該參數(shù)的有效取值依賴于對軟件系統(tǒng)的了解程度.置信度設置將影響對波及效應的量化分析，取值應該盡量小，以滿足量化小概率波及效應.

在下一步的工作中，將對支持度、置信度參數(shù)自動設置問題展開研究工作，擬實現(xiàn)在提高查準率的同時，將召回率保持在一個合理的范圍內.另外，為了驗證本文方法的普適性，將對更多的開源項目進行驗證.

參考文獻

[1]Li B, Sun X, Leung H, et al. A survey of code-based change impact analysis techniques[J]. Software Testing Verification & Reliability, 2013, 23(8): 613-646

[2]Dagenais B, Robillard M P. Using traceability links to recommend adaptive changes for documentation evolution[J]. IEEE Trans on Software Engineering, 2014, 40(11): 1126-1146

[3]Hill E, Pollock L, Vijay-Shanker K. Exploring the neighborhood with Dora to expedite software maintenance[C]Proc of the 22nd IEEEACM Int Conf on Automated Software Engineering. New York: ACM, 2007: 14-23

[4]Law J, Rothermel G. Whole program path-based dynamic impact analysis[C]Proc of the 25th Int Conf on Software Engineering. Piscataway, NJ: IEEE, 2003: 308-318

[5]Orso A, Apiwattanapong T, Law J, et al. An empirical comparison of dynamic impact analysis algorithms[C]Proc of the 26th Int Conf on Software Engineering. Piscataway, NJ: IEEE, 2004: 491-500

[6]Ren X, Shah F, Tip F, et al. Chianti: A tool for change impact analysis of Java programs[C]Proc of the 19th Annual ACM SIGPLAN Conf on Object-Oriented Programming, Systems, Languages, and Applications. New York: ACM, 2004: 432-448

[7]Gethers M, Dit B, Kagdi H, et al. Integrated impact analysis for managing software changes[C]Proc of the 34th Int Conf on Software Engineering. Piscataway, NJ: IEEE, 2012: 430-440

[8]Seacord R C, Plakosh D, Lewis G A. Modernizing Legacy Systems: Software Technologies, Engineering Processes, and Business Practices[M]. Reading, MA: Addison-Wesley, 2003

[9]Bohner S A. Software change impacts-an evolving perspective[C]Proc of the 18th Int Conf on Software Maintenance. Piscataway, NJ: IEEE, 2002: 263-272

[10]Bohner S A. Impact analysis in the software change process: A year 2000 perspective[C]Proc of the 13th Int Conf on Software Maintenance. Piscataway, NJ: IEEE, 1996: 42-51

[11]Malik H, Hassan A E. Supporting software evolution using adaptive change propagation heuristics[C]Proc of the 24th IEEE Int Conf on Software Maintenance. Piscataway, NJ: IEEE, 2008: 177-186

[12]Wang Yinghui, Zhang Shikun, Liu Yu, et al. Ripple-effect analysis of software architecture evolution based on reachability matrix[J]. Journal of Software, 2004, 15(8): 1107-1115 (in Chinese)(王映輝, 張世琨, 劉瑜, 等. 基于可達矩陣的軟件體系結構演化波及效應分析[J]. 軟件學報, 2004, 15(8): 1107-1115)

[13]Hassan A E, Holt R C. Predicting change propagation in software systems[C]Proc of the 20th IEEE Int Conf on Software Maintenance. Piscataway, NJ: IEEE, 2004: 284-293

[14]Orso A, Apiwattanapong T, Harrold M J. Leveraging field data for impact analysis and regression testing[J]. ACM SIGSOFT Software Engineering Notes, 2003, 28(5): 128-137

[15]Law J, Rothermel G. Incremental dynamic impact analysis for evolving software systems[C]Proc of the 14th Int Symp on Software Reliability Engineering. Piscataway, NJ: IEEE, 2003: 430-441

[16]Canfora G, Cerulo L. Fine grained indexing of software repositories to support impact analysis[C]Proc of the 3rd Int Workshop on Mining Software Repositories. New York: ACM, 2006: 105-111

[17]Weiss C, Premraj R, Zimmermann T, et al. How long will it take to fix this bug?[C]Proc of the 4th Int Workshop on Mining Software Repositories. Los Alamitos, CA: IEEE Computer Society, 2007

[18]Qusef A, Bavota G, Oliveto R, et al. Recovering test-to-code traceability using slicing and textual analysis[J]. Journal of Systems and Software, 2014, 88(2): 147-168

[19]Schrettner L, Jász J, Gergely T, et al. Impact analysis in the presence of dependence clusters using static execute after in WebKit[J]. Journal of Software-Evolution and Process, 2014, 26(6): 569-588

[20]Cheluvaraju B, Nagal K, Pasala A. Mining software revision history using advanced social network analysis[C]Proc of the 19th Asia-Pacific Software Engineering Conf. Piscataway, NJ: IEEE, 2012: 717-720

[21]Herzig K, Zeller A. Mining cause-effect-chains from version histories[C]Proc of the 22nd IEEE Int Symp on Software Reliability Engineering. Piscataway, NJ: IEEE, 2011: 60-69

[22]Marcus A, Sergeyev A, Rajlich V, et al. An information retrieval approach to concept location in source code[C]Proc of the 11th Working Conf on Reverse Engineering. Piscataway, NJ: IEEE, 2004: 214-223

[23]Ju Xiaolin, Jiang Shujuan, Zhang Yanmei, et al. Advances in fault localization techniques[J]. Journal of Frontiers of Computer Science and Technology, 2012, 6(6): 481-494 (in Chinese)(鞠小林, 姜淑娟, 張艷梅, 等. 軟件故障定位技術進展[J]. 計算機科學與探索, 2012, 6(6): 481-494)

[24]Liu Bing, Hsu W, Ma Yiming. Integrating classification and association rule mining[C]Proc of the 4th Int Conf on Knowledge Discovery and Data Mining. Menlo Park, CA: AAAI, 1998: 1-7

[25]Li Yunchang, He Pinjie, Li Yulong. Techniques for Software Dynamic Evolution[M]. Beijing: Peking University Press, 2007 (in Chinese)(李云長, 何頻捷, 李玉龍. 軟件動態(tài)演化技術[M]. 北京: 北京大學出版社, 2007)

[26]Arnold R S, Bohner S A. Impact analysis-towards a framework for comparison[C]Proc of the 9th Int Conf on Software Maintenance. Piscataway, NJ: IEEE, 1993: 292-301

[27]Hattori L, Guerrero D, Figueiredo J, et al. On the precision and accuracy of impact analysis techniques[C]Proc of the 7th IEEEACIS Int Conf on Computer and Information Science. Piscataway, NJ: IEEE, 2008: 513-518

[28]Poshyvanyk D, Marcus A, Ferenc R, et al. Using information retrieval based coupling measures for impact analysis[J]. Empirical Software Engineering, 2009, 14(1): 5-32

[29]Sun X, Li B, Tao C, et al. Change impact analysis based on a taxonomy of change types[C]Proc of the 34th Annual Conf on Computer Software and Applications. Piscataway, NJ: IEEE, 2010: 373-382

Wang Wei, born in 1979. PhD, associate professor of Yunnan University. Member of China Computer Federation. His research interests include software evolution, and formal method.

Li Tong, born in 1963. PhD, professor of Yunnan University. Member of China Computer Federation. His research interests include software evolution and formal method.

He Yun, born in 1989. Master. Student member of China Computer Federation. His research interests include software engineering and software evolution.

Li Hao, born in 1970. PhD, professor of Yunnan University. His research interests include software engineering and cloud computing.

中圖法分類號TP311.5

基金項目：國家自然科學基金項目(61462092,61262024,61379032);云南省自然科學基金重點項目(2015FA014);云南省自然科學基金面上項目(2013FB008)

收稿日期：2014-08-04；修回日期：2015-05-14 2014-08-04；修回日期：2015-05-14

This work was supported by the National Natural Science Foundation of China (61462092,61262024,61379032), the Key Program of the Natural Science Foundation of Yunnan Province (2015FA014), and the General Program of the Natural Science Foundation of Yunnan Province (2013FB008).