一種軟件演化活動(dòng)波及效應(yīng)混合分析方法

王　煒　李　彤　何　云　李　浩

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

(wangwei@ynu.edu.cn)

?

一種軟件演化活動(dòng)波及效應(yīng)混合分析方法

王煒李彤何云李浩

(云南大學(xué)軟件學(xué)院昆明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

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

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

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

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

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

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

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

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

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

本文提出的波及效應(yīng)混合分析方法，具有3個(gè)特點(diǎn)：

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

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

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

1本文方法

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

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

1.1執(zhí)行跡獲取

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

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

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

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

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

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

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

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

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

Table 1　Execution Traces Slice Sample of Thread main

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

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

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

1) 生成語(yǔ)料庫(kù).為源代碼中每一個(gè)類(函數(shù))建立一個(gè)文本文件，提取類代碼中蘊(yùn)含領(lǐng)域知識(shí)的關(guān)鍵詞存入該文件.所有類對(duì)應(yīng)的文本文件構(gòu)成語(yǔ)料庫(kù).

表2為1個(gè)由6個(gè)文本文件組成的語(yǔ)料庫(kù)示例.其中每一行代表一個(gè)與源代碼對(duì)應(yīng)的文本文件.

Table 2　Corpus Sample

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

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

Table 3　Term Frequency Matrix Sample

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

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

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

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

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

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

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

1.3波及效應(yīng)分析

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

1) 識(shí)別波及關(guān)系；

2) 構(gòu)造波及效應(yīng)圖；

3) 波及效應(yīng)量化分析.

1.3.1波及關(guān)系識(shí)別

代碼間的波及關(guān)系刻畫了若一個(gè)類被修改則另一個(gè)類也會(huì)被修改的事實(shí).

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

矩陣Kn×n為波及關(guān)系的存儲(chǔ)介質(zhì).以面向?qū)ο筌浖到y(tǒng)為例，類i與類j間存在波及關(guān)系，當(dāng)且僅當(dāng)i和j兩個(gè)類間存在關(guān)聯(lián)關(guān)系，或第i個(gè)類是第j個(gè)類的特殊類，或第i個(gè)類依賴第j個(gè)類，或i和j兩個(gè)類間存在實(shí)現(xiàn)關(guān)系，記為ki j=1，否則ki j=0.波及關(guān)系的方向性由行和列分別表示，行為起始類，列為終結(jié)類.例如表4第1行、第6列為1，表示c1與c5之間存在波及關(guān)系，且c1→c5.

Table 4　Ripple Effect Relationship Matrix of Some Software

1.3.2波及效應(yīng)圖構(gòu)造

波及效應(yīng)圖是波及效應(yīng)量化分析的基礎(chǔ).整個(gè)構(gòu)造過(guò)程包括2個(gè)方面：邊集合識(shí)別和波及效應(yīng)圖構(gòu)造.

1) 邊集合識(shí)別

波及效應(yīng)圖的邊集合由波及關(guān)系集合充當(dāng).算法1描述了波及關(guān)系圖邊集合的識(shí)別過(guò)程.

算法1. 波及效應(yīng)圖邊集合識(shí)別算法.

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

輸出：波及效應(yīng)圖邊集合E.

① 計(jì)算波及關(guān)系矩陣的傳遞閉包K+;

② 基于支持度Support對(duì)K+進(jìn)行頻繁類集挖掘;

③ 基于置信度Conf對(duì)頻繁類集中的波及關(guān)系進(jìn)行識(shí)別，生成波及效應(yīng)圖邊集合E.

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

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

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

集合ki={ki1,ki2,…,kin}描述了對(duì)第i個(gè)類實(shí)施演化活動(dòng)將導(dǎo)致ki集合中的類也將進(jìn)行演化活動(dòng).表5給出了與表4對(duì)應(yīng)的傳遞閉包矩陣，可以看出在演化事務(wù)k1中，若對(duì)c1實(shí)施演化活動(dòng)將導(dǎo)致c1,c2,c4,c5,c6也需要進(jìn)行演化.

Table 5　The Transitive Closure of Table 4

定義8. 設(shè)T={k1,k2,…,kn}為演化事務(wù)集合，一條波及關(guān)系ci→cj的支持度定義為

定義9. 設(shè)T={k1,k2,…,kn}為演化事務(wù)集合，一條波及關(guān)系ci→cj的置信度定義為

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

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

當(dāng)Support=60%，Conf=60%時(shí)，表5經(jīng)過(guò)算法1計(jì)算可產(chǎn)生如下計(jì)算結(jié)果：

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

2) 波及效應(yīng)圖構(gòu)造

圖2給出了與表5對(duì)應(yīng)的波及效應(yīng)圖：

Fig. 2　Ripple effect graph of Table 5.圖2　表5對(duì)應(yīng)的波及效應(yīng)圖

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

定義12. 設(shè)GRE=(V,E,L)為波及效應(yīng)圖.

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

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

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

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

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

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

Fig. 3　Add vertex v to Fig. 2.圖3　對(duì)圖2添加頂點(diǎn)v

Fig. 4　Delete vertex (c2,c4,c6) from Fig. 2.圖4　對(duì)圖2刪除頂點(diǎn)(c2,c4,c6)

Fig. 6　Migrate vertex (c2,c4,c6) for Fig. 2.圖6　對(duì)圖2遷移頂點(diǎn)(c2,c4,c6)

1.3.3波及效應(yīng)量化分析

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

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

證明. 要證明{add(GRE,v),del(GRE,v)}是軟件演化活動(dòng)集合的最小完備集，就必須證明：1)所有其他演化活動(dòng)均可以使用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)其中任一活動(dòng)，sub(GRE,v′,v)和mig(GRE,v)活動(dòng)將不能表示.

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

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

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

證畢.

根據(jù)定理1可知，軟件演化波及效應(yīng)分析可以約簡(jiǎn)為對(duì)add(GRE,v′)和del(GRE,v)演化活動(dòng)波及效應(yīng)的分析.

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

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

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

證畢.

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

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

通過(guò)波及范圍的定義可以計(jì)算對(duì)某一代碼所實(shí)施的演化活動(dòng)所影響到的范圍.

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

ImpactDegree(v)=

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

波及程度是一個(gè)概率屬性，該屬性描述了對(duì)代碼v′實(shí)施的演化活動(dòng)將導(dǎo)致代碼v發(fā)生相應(yīng)演化活動(dòng)的最大概率.取值越高說(shuō)明波及效應(yīng)發(fā)生的概率越大.如圖2所示，頂點(diǎn)(c2)對(duì)頂點(diǎn)(c2,c4)的波及程度為0.67×1.0=0.67.

對(duì)于波及效應(yīng)圖GRE而言，對(duì)某代碼實(shí)施演化活動(dòng)不產(chǎn)生波及效應(yīng)的條件是該代碼在波及效應(yīng)圖上是一個(gè)孤立點(diǎn).

定理3. 設(shè)GRE=(V,E,L)為波及效應(yīng)圖，對(duì)v∈V實(shí)施演化活動(dòng)不產(chǎn)生波及效應(yīng)，當(dāng)且僅當(dāng)v是GRE的孤立點(diǎn).

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

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

證畢.

如圖2所示，點(diǎn)(c2,c4,c6)就是孤立點(diǎn)，對(duì)該點(diǎn)實(shí)施演化活動(dòng)對(duì)其他點(diǎn)不會(huì)產(chǎn)生波及效應(yīng).

2實(shí)驗(yàn)

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

研究問(wèn)題1.與其他方法進(jìn)行對(duì)比證明本文方法的有效性.

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

2.1實(shí)驗(yàn)過(guò)程

2.1.1實(shí)驗(yàn)對(duì)象

為保證實(shí)驗(yàn)結(jié)果的客觀性，采用開源軟件jEdit①作為實(shí)驗(yàn)對(duì)象，其簡(jiǎn)要情況如表6所示：

Table 6　Brief Introduction of jEdit

2.1.2實(shí)驗(yàn)過(guò)程

本文實(shí)驗(yàn)過(guò)程包含5個(gè)步驟：

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

Table 7　Fault Use Cases Description

Continued (Table 7)

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

Table 8　Execution Trace Description

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

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

5) 與動(dòng)態(tài)、基于文本和歷史演化知識(shí)的波及效應(yīng)分析方法進(jìn)行定量比對(duì)，與靜態(tài)波及效應(yīng)分析方法進(jìn)行定性比對(duì).

Table 9　TF-IDF Matrix

2.2評(píng)價(jià)標(biāo)準(zhǔn)

度量波及效應(yīng)分析方法的好壞是看預(yù)測(cè)演化活動(dòng)影響范圍是否接近于實(shí)際影響范圍.在以往研究中提出多種指標(biāo)作為量化分析結(jié)果好壞的標(biāo)準(zhǔn)[26-27].在眾多的指標(biāo)中查準(zhǔn)率和召回率是使用最廣的2個(gè)指標(biāo)[26-29].其中,查準(zhǔn)率反映了預(yù)測(cè)影響范圍與實(shí)際影響范圍的一致性，召回率反映了預(yù)測(cè)影響范圍在實(shí)際影響范圍中的占比.高查準(zhǔn)率意味著將花費(fèi)較少的開銷來(lái)確定演化活動(dòng)的波及范圍，高召回率意味著凡是通過(guò)算法推薦的波及范圍均是可信的.

定義17. 設(shè)有限非空集合SI,SC分別表示各波及效應(yīng)分析方法檢出代碼集合和實(shí)際演化活動(dòng)所影響的代碼集合.查準(zhǔn)率、召回率分別定義如下：

針對(duì)本文提出方法，SI集合對(duì)應(yīng)于波及效應(yīng)圖的所有頂點(diǎn)集合的并集，實(shí)際波及范圍由表7中演化結(jié)果記錄.

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

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

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

由于查準(zhǔn)率和召回率具有互逆關(guān)系，無(wú)法描述波及效應(yīng)分析方法的綜合性能，本文使用調(diào)和平均數(shù)F(F-measure)度量波及效應(yīng)分析方法的綜合性能.

2.3實(shí)驗(yàn)結(jié)果

2.3.1與動(dòng)態(tài)、文本和歷史演化知識(shí)分析方法比對(duì)

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

Fig. 7　Precession comparison graph.圖7　查準(zhǔn)率對(duì)比圖

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

Fig. 8　Recall comparison graph.圖8　召回率對(duì)比圖

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

Fig. 9　Precession gain graph.圖9　查準(zhǔn)率增益圖

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

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

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

2.3.2與靜態(tài)方法實(shí)驗(yàn)對(duì)比

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

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

2.3.3波及效應(yīng)量化分析

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

Fig. 12　Ripple effect graph of failure use case 950 961.圖12　故障用例950 961對(duì)應(yīng)的波及效應(yīng)圖

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ù)的影響

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

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

Table 11Relationship Between Support Precision and Recall

表11　查準(zhǔn)率、召回率與支持度取值的關(guān)系

Table 12Relationship Between the Amount of Ripple

Effect Relationship and Confidence

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

通過(guò)分析可知，支持度取值將影響本文方法的查準(zhǔn)率和召回率，伴隨著支持度的降低，將導(dǎo)致查準(zhǔn)率的降低、召回率的增高，但查準(zhǔn)率的降低并不是一個(gè)線性過(guò)程.因此，支持度的取值需要對(duì)演化軟件具有一定的了解.置信度取值將影響對(duì)波及效應(yīng)進(jìn)行量化分析，取值越小越能夠?qū)π「怕什靶?yīng)進(jìn)行量化分析.

3結(jié)論

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

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

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

參考文獻(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)(王映輝, 張世琨, 劉瑜, 等. 基于可達(dá)矩陣的軟件體系結(jié)構(gòu)演化波及效應(yīng)分析[J]. 軟件學(xué)報(bào), 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)(鞠小林, 姜淑娟, 張艷梅, 等. 軟件故障定位技術(shù)進(jìn)展[J]. 計(jì)算機(jī)科學(xué)與探索, 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)(李云長(zhǎng), 何頻捷, 李玉龍. 軟件動(dòng)態(tài)演化技術(shù)[M]. 北京: 北京大學(xué)出版社, 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.

中圖法分類號(hào)TP311.5

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(61462092,61262024,61379032);云南省自然科學(xué)基金重點(diǎn)項(xiàng)目(2015FA014);云南省自然科學(xué)基金面上項(xiàng)目(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).