基于Word2Vec和決策樹的故障定位技術(shù)

王露露 陳軍華

摘??要：?利用Word2Vec方法對(duì)Java源代碼進(jìn)行深層語義編碼，生成文件級(jí)和行級(jí)的語義向量，并將其用作輸入數(shù)據(jù)來訓(xùn)練決策樹模型，以實(shí)現(xiàn)精確的文件級(jí)別和行級(jí)別故障定位，優(yōu)化故障檢測(cè)過程，構(gòu)建一個(gè)綜合文件級(jí)別與行級(jí)別分析的高效故障定位框架. 實(shí)驗(yàn)結(jié)果表明：該模型在各項(xiàng)目中的故障定位準(zhǔn)確率均高于83%.

關(guān)鍵詞：?故障定位；?語義表示；?Word2Vec；?決策樹

中圖分類號(hào)：?TP 18；?TP 391.1 ?文獻(xiàn)標(biāo)志碼：?A ?文章編號(hào)：?1000-5137（2024）02-0223-05

Fault location technology based on Word2Vec and decision tree

WANG Lulu，?CHEN Junhua^*

（College of Information，Mechanical and Electrical Engineering，Shanghai Normal University，Shanghai 201418，China）

Abstract：?Word2Vec technology was utilized to perform deep semantic encoding on Java source code，?generating file-level and line-level semantic vectors. These vectors were used as input data to train the decision tree model，?aiming to achieve precise file-level and line-level fault location and to optimize the fault detection process. An efficient fault localization framework was constructed by this method which integrated file-level and line-level analysis. The experimental results showed that the fault localization accuracy of the model in all projects was higher than 83%.

Key words：?fault location；?semantic representation；?Word2Vec；?decision tree

譜分析故障定位（SBFL）^［1］根據(jù)程序的執(zhí)行信息（覆蓋率信息）和程序的執(zhí)行結(jié)果（是否發(fā)生錯(cuò)誤）來計(jì)算每一行代碼可能導(dǎo)致錯(cuò)誤的概率，該方法雖然注重檢測(cè)代碼語法，卻常常忽視了對(duì)程序的語義與功能層面的檢測(cè).程序切片故障定位^［2］是一種靜態(tài)分析技術(shù)，用于識(shí)別可能影響特定變量或計(jì)算結(jié)果的代碼行，但計(jì)算復(fù)雜、內(nèi)存需求高，并不適用于大型軟件系統(tǒng)，且缺乏靈活性. 基于機(jī)器學(xué)習(xí)的軟件故障定位^［3］，是一個(gè)使用機(jī)器學(xué)習(xí)技術(shù)來識(shí)別軟件中錯(cuò)誤或缺陷位置的方法，其中構(gòu)建有效的預(yù)測(cè)模型至關(guān)重要，不僅可以識(shí)別出與軟件缺陷緊密相關(guān)的屬性，還能準(zhǔn)確地捕捉到這些屬性在源程序中的表現(xiàn).

本文作者提出了一種利用Word2Vec方法對(duì)程序源代碼的語義進(jìn)行編碼的方法，旨在提煉程序的深層語義信息，以優(yōu)化故障定位流程.通過結(jié)合文件級(jí)和行級(jí)故障定位技術(shù)，將程序文件的語義表示引入文件級(jí)故障定位框架，以篩查潛在缺陷. 一旦發(fā)現(xiàn)問題，進(jìn)一步將代碼每一行的語義表示納入行級(jí)故障定位，以精確定位錯(cuò)誤. 相較于傳統(tǒng)方法，該方法不僅深入挖掘程序的語義層面，準(zhǔn)確提取了源程序的語義特征，還展現(xiàn)了更強(qiáng)的適應(yīng)性和更高的定位效率，進(jìn)而實(shí)現(xiàn)了高效的自動(dòng)化行級(jí)故障診斷.

1 ?相關(guān)技術(shù)基礎(chǔ)

1.1 程序頻譜

故障定位是一項(xiàng)軟件維護(hù)任務(wù)，利用程序故障的相關(guān)信息來定位必須糾正的錯(cuò)誤源代碼^［4］. 程序頻譜是一種每個(gè)程序元素（語句、基本塊、分支等）執(zhí)行與否或執(zhí)行次數(shù)的信息，使用測(cè)試套件獲得這些信息，程序頻譜常見的類型為計(jì)數(shù)頻譜和命中頻譜^［5］.

1.2 程序表示

程序表示是一種對(duì)程序或代碼進(jìn)行結(jié)構(gòu)化和抽象化表示的方法，其傳統(tǒng)形式有：抽象語法樹（AST）、控制流圖（CFG）、數(shù)據(jù)流圖（DFG）以及中間表示（IR）. 程序表示學(xué)習(xí)已經(jīng)滲透在命名推薦，代碼補(bǔ)全，缺陷檢測(cè)、缺陷定位、缺陷修復(fù)等軟件開發(fā)的多個(gè)環(huán)節(jié)^［6］. 由于程序員在編寫代碼時(shí)遵循某種規(guī)律，使得代碼具有自然性^［7］，可以對(duì)大規(guī)模代碼庫進(jìn)行程序語義表示.

1.3 數(shù)據(jù)集選擇

采用Defects4J作為本研究的數(shù)據(jù)集. Defects4J是一個(gè)公開可用、內(nèi)容豐富、覆蓋多版本、囊括真實(shí)缺陷的Java程序缺陷數(shù)據(jù)庫，廣泛應(yīng)用于軟件工程的各個(gè)研究領(lǐng)域，包括自動(dòng)程序修復(fù)、缺陷預(yù)測(cè)、故障定位和軟件測(cè)試等^［8］. Defects4J包含多個(gè)不同版本的軟件項(xiàng)目以及相應(yīng)的缺陷修復(fù)記錄. 對(duì)于每個(gè)特定缺陷，Defects4J提供了存在缺陷的版本、修復(fù)后的版本，以及一組可以復(fù)現(xiàn)該缺陷的測(cè)試用例.在本研究中，將重點(diǎn)分析Defects4J中的以下5個(gè)項(xiàng)目：JFreeChart，Apache Commons Math，Apache Commons Lang，Mockito以及Joda-Time，如表1所示.

通過Defects4J中的測(cè)試框架獲取軟件的代碼覆蓋率和測(cè)試信息，方便后續(xù)提取命中頻譜所涉及的程序代碼文件級(jí)和行級(jí)語義信息. 同時(shí)，結(jié)合分布式版本控制系統(tǒng)Git的歷史提交信息，對(duì)故障文件和故障代碼行進(jìn)行標(biāo)記，以便更好地理解和分析軟件的缺陷.

2 ?基于Word2Vec提取程序語義向量

Word2Vec是一種先進(jìn)的神經(jīng)網(wǎng)絡(luò)語言模型，它構(gòu)建了一個(gè)詞嵌入空間，能夠?qū)⒃~匯表中的每個(gè)單詞轉(zhuǎn)換成向量形式. 在這個(gè)多維空間中，那些在語義上互有關(guān)聯(lián)的詞語被賦予了彼此接近的向量表示.本研究中，借助Word2Vec這一自然語言處理技術(shù)，有效地提煉出程序代碼中蘊(yùn)含的語義特征.

盡管Word2Vec的能力局限于提取代碼中單個(gè)單詞的語義向量，但是根據(jù)文獻(xiàn)［9］的論述，由Word2Vec生成的向量具有一些獨(dú)特的屬性，這些屬性允許通過向量之間的數(shù)學(xué)運(yùn)算來揭示語言結(jié)構(gòu)的內(nèi)在規(guī)律. 鑒于此，本文作者將一行代碼中所有單詞的向量進(jìn)行累加，來表示該行代碼的向量. 類似地，可以通過累加其多行代碼的向量得到整個(gè)源程序代碼的向量. 雖然源程序本質(zhì)上是文本文件，理論上可以直接用于訓(xùn)練Word2Vec模型，但其中的特殊符號(hào)和專有詞匯需要作適當(dāng)處理. 因此，在使用數(shù)據(jù)集中的源程序進(jìn)行訓(xùn)練之前，必須對(duì)其進(jìn)行預(yù)處理，以優(yōu)化模型的訓(xùn)練效果. 同時(shí)，Word2Vec能夠?qū)卧~轉(zhuǎn)化為固定維度的向量，這一維度是一個(gè)關(guān)鍵的超參數(shù)，需在模型訓(xùn)練階段確定. 維度的大小直接關(guān)聯(lián)到模型的表現(xiàn)和效率. 基于Word2Vec的程序語義向量提取模型的訓(xùn)練流程可概述為以下幾個(gè)精細(xì)化步驟：

Step1：刪除特殊字符，將特殊符號(hào)（?例如?“+”?“-”?“*”?“＼”?“［］”?）替換為一個(gè)空格字符.

Step2：拆分Camel命名法的標(biāo)識(shí)符，將該標(biāo)識(shí)符拆分成獨(dú)立的單詞. 將拆分后的每個(gè)單詞轉(zhuǎn)換為小寫.

Step3：對(duì)于Joda-Time項(xiàng)目，將每一個(gè)測(cè)試用例的源代碼通過訓(xùn)練好的Word2Vec模型轉(zhuǎn)換成向量. Word2Vec利用上下文的分布信息來捕捉詞語的語義含義，采用Word2Vec中預(yù)訓(xùn)練好的Continuous Bag of Words（CBOW）?模型，根據(jù)上下文詞預(yù)測(cè)中心詞. 計(jì)算上下文窗口內(nèi)周圍詞的詞嵌入平均值，作為模型的輸入：

， （1）

其中，是上下文窗口內(nèi)第c個(gè)詞的詞嵌入向量；C是上下文窗口的大小.預(yù)測(cè)目標(biāo)詞的條件概率^［10］

， （2）

其中，為激活函數(shù)；w是權(quán)重向量；b是偏置值.

Step4：使用轉(zhuǎn)換得到的代碼向量作為特征，將測(cè)試用例的測(cè)試結(jié)果作為標(biāo)簽，訓(xùn)練一個(gè)線性支持向量機(jī)（SVM）分類器. SVM 的目標(biāo)是找到一個(gè)決策邊界，使得樣本點(diǎn)到這個(gè)邊界的間隔最大. 這可以通過最小化權(quán)重向量的范數(shù)來實(shí)現(xiàn)：

， （3）

， （4）

其中，y_i是樣本點(diǎn)x_i的類別標(biāo)簽.

Step5：模型評(píng)估，使用線性SVM分類器對(duì)測(cè)試用例進(jìn)行分類，預(yù)測(cè)的分類結(jié)果

， （5）

其中，為決策函數(shù)；為獲取決策函數(shù)符號(hào)的函數(shù). 記錄分類的準(zhǔn)確性，判斷Word2Vec模型的效果.

3 ?文件級(jí)和行級(jí)相結(jié)合的故障定位模型

在進(jìn)行源代碼故障定位時(shí)，如果僅采用行級(jí)定位技術(shù)，那么對(duì)于平均含有n行代碼的m個(gè)文件，將執(zhí)行m×n次的逐行檢查，效率較低. 如果先通過文件級(jí)檢測(cè)來篩選出包含故障的文件，再對(duì)這些特定文件執(zhí)行行級(jí)故障定位，那么檢測(cè)的效率就會(huì)顯著提高. 具體來說，首先進(jìn)行m次的文件級(jí)檢測(cè)，識(shí)別出包含故障的文件數(shù)量k（k<m），接著針對(duì)這k個(gè)文件的每一行代碼進(jìn)行故障檢測(cè)，即進(jìn)行k×n次檢測(cè)，總體檢測(cè)次數(shù)縮減為m+k×n次.

在進(jìn)行故障定位時(shí)，選擇合適的模型對(duì)于提高定位的準(zhǔn)確性至關(guān)重要. 本研究引入的文件級(jí)和行級(jí)故障定位模型均依賴于語義向量分類的方法. 兩者的主要區(qū)別在于輸入模型的語義向量所承載的信息層級(jí)不同：文件級(jí)模型處理的語義向量映射了整個(gè)源文件的語義內(nèi)容，而行級(jí)模型關(guān)注的則是單行代碼的語義信息.

為了評(píng)估文件級(jí)故障定位模型的有效性，比較SVM、反向傳播（BP）神經(jīng)網(wǎng)絡(luò)及決策樹算法在Defects4J上的執(zhí)行性能，特別是識(shí)別含有故障的源程序文件的準(zhǔn)確率. 結(jié)果表明：決策樹算法在分類Word2Vec生成的程序向量時(shí)展現(xiàn)出了較為良好的性能.

考慮到所有選用的模型都是基于語義向量進(jìn)行分類的，將那些在文件級(jí)分類中表現(xiàn)出色的模型也作為候選模型，用于行級(jí)語義向量的分類，以期在細(xì)粒度層面上實(shí)現(xiàn)高效準(zhǔn)確的故障定位.

基于決策樹的文件級(jí)和行級(jí)相結(jié)合的故障定位模型流程可概述為以下幾個(gè)步驟：

Step 1：數(shù)據(jù)準(zhǔn)備.首先運(yùn)用Word2Vec方法來提取程序中單詞的語義向量. 捕捉單詞層面的深層語義，通過將這些單詞向量進(jìn)行累加，構(gòu)建代表各個(gè)代碼行的語義向量. 通過匯總一個(gè)文件中所有代碼行的語義向量，能夠得到反映整個(gè)文件語義的綜合向量.

Step 2：文件級(jí)故障定位.使用決策樹算法對(duì)文件級(jí)特征進(jìn)行學(xué)習(xí). 首先構(gòu)建一棵樹，其中每個(gè)內(nèi)部節(jié)點(diǎn)代表一個(gè)特征的決策，選擇一個(gè)最佳特征創(chuàng)建子節(jié)點(diǎn)，使該子節(jié)點(diǎn)在目標(biāo)變量上比原始節(jié)點(diǎn)具備更高的純度. 熵是衡量數(shù)據(jù)集不確定性的指標(biāo)，在決策樹算法中被用于衡量數(shù)據(jù)集的純度.

， （6）

其中，S是數(shù)據(jù)集；是S的熵；n是類別數(shù)；p_i是第i個(gè)類別在數(shù)據(jù)集中的比例. 信息增益是選擇分割屬性時(shí)的主要標(biāo)準(zhǔn)，基于熵的減少量來衡量分割的有效性.

（7）

其中，是某個(gè)特征；為在上的信息增益；（）是所有可能的值；是值為時(shí)的數(shù)據(jù)集子集. 對(duì)文件級(jí)的語義向量進(jìn)行二分類，預(yù)測(cè)和識(shí)別可能存在故障的文件.

Step 3：行級(jí)故障定位. 基于數(shù)據(jù)準(zhǔn)備階段所生成的文件代碼行語義向量，應(yīng)用決策樹算法對(duì)可能包含故障的文件代碼行語義向量進(jìn)行二分類.

Step 4：輸出結(jié)果. 綜合文件級(jí)和行級(jí)故障定位的結(jié)果，輸出最終的故障定位報(bào)告.

4 ?仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境

硬件環(huán)境. 計(jì)算機(jī)型號(hào)：DESKTOP-FMMKAKR；處理器：Intel（R）?Core（TM）?i5-7300HQ CPU@2.50 ?GHz；內(nèi)存：16 GB DDR4；存儲(chǔ)：16 GB SSD；顯卡：NVIDIA GeForce GTX 1050 Ti.

軟件環(huán)境. 操作系統(tǒng)：Ubuntu 18.04 LTS；編程語言及版本：Python 3.7.4；數(shù)據(jù)集：Defects4J.

4.2 實(shí)驗(yàn)結(jié)果分析

訓(xùn)練了5個(gè)不同維度（50，75，100，200及300）的模型. 實(shí)驗(yàn)結(jié)果顯示：隨著維度的增加，向量包含的信息逐漸豐富，線性SVM的分類準(zhǔn)確度也相應(yīng)提高. 因此，將Word2Vec的維度超參數(shù)設(shè)置為300.

在文件級(jí)故障定位的性能比較中，決策樹算法性能顯著，如表2所示.

此外，根據(jù)文獻(xiàn)［11］，利用西門子數(shù)據(jù)集對(duì)基于頻譜的故障定位進(jìn)行分析時(shí)，Ochiai相似系數(shù)的方法平均可以排除80%的無故障代碼塊. 相比之下，本研究的決策樹算法文件級(jí)故障定位時(shí)，這一比例提升至90%.

表3為單純的行級(jí)故障定位模型與結(jié)合文件級(jí)和行級(jí)的故障定位模型在Defects4J中的準(zhǔn)確率. 可以看出，雖然單純的行級(jí)故障定位模型與結(jié)合文件級(jí)和行級(jí)的故障定位模型在準(zhǔn)確率上稍顯不足，這可能是因?yàn)楸狙芯克捎玫臄?shù)據(jù)預(yù)處理策略會(huì)在一定程度上犧牲了故障定位的準(zhǔn)確性，但在定位速度方面，結(jié)合文件級(jí)和行級(jí)的故障定位模型表現(xiàn)更為優(yōu)異，可以作為更加高效的故障定位策略.

5 ?結(jié)語

本文作者構(gòu)建了文件級(jí)和行級(jí)相結(jié)合的故障定位模型，在標(biāo)準(zhǔn)測(cè)試中展現(xiàn)了良好的性能，相比傳統(tǒng)基于頻譜的故障定位技術(shù)，顯著縮減了調(diào)試時(shí)需要審查的代碼范圍，進(jìn)一步壓縮了自動(dòng)化故障定位所需的時(shí)間. 此外，采用決策樹算法作為核心的故障定位模型，在實(shí)驗(yàn)評(píng)估中，該模型的故障定位準(zhǔn)確率較高.

參考文獻(xiàn)：

［1］ JONES J A，?HARROLD M J，?STASKO J. Visualization of test information to assist fault localization ［C］// Proceedings of the 24th International Conference on Software Engineering. Windsor：?IEEE，?2002：467-477.

［2］ 白駿. 分布式Java程序切片及其在故障定位中的應(yīng)用?［D］. 南京：?東南大學(xué)，?2018.

BAI J. Distributed Java program slice and its application in fault localization ［D］. Nanjing：?Southeast University，?2018.

［3］ LI X，?LI W，?ZHANG Y，?et al. Deepfl：?integrating multiple fault diagnosis dimensions for deep fault localization ［C］// Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis. New York：?ACM，?2019：169-180.

［4］ LUKINS S K，?KRAFT N A，?ETZKORN L H. Source code retrieval for bug localization using latent dirichlet allocation ［C］// 2008 15th Working Conference on Reverse Engineering. Antwerp：?IEEE，?2008：155-164.

［5］ JIA Y，?HARMAN M. An analysis and survey of the development of mutation testing ［J］. IEEE Transactions on Software Engineering，?2010，37（5）：649-678.

［6］ 馬駿馳，?迪驍鑫，?段宗濤，?等. 程序表示學(xué)習(xí)綜述?［J］. 浙江大學(xué)學(xué)報(bào)（工學(xué)版），?2023，57（1）：155-169.

MA J C，?DI X X，?DUAN Z T，?et al. Survey on program representation learning ［J］. Journal of Zhejiang University （Engineering Science）?，2023，57（1）：155-169.

［7］ ALLAMANIS M，BARR E T，DEVANBU P，?et al. A survey of machine learning for big code and naturalness ［J］. ACM Computing Surveys （CSUR），?2018，51（4）：1-37.

［8］ JUST R，?JALALI D，?ERNST M D. Defects4J：?a database of existing faults to enable controlled testing studies for Java programs ［C］// International Symposium on Software Testing and Analysis. San Jose：?ACM，?2014：437-440.

［9］ MIKOLOV T，?SUTSKEVER I，?CHEN K，?et al. Distributed representations of words and phrases and their compositionality ［C］// Proceedings of the 26th International Conference on Neural Information Processing Systems. New York：?ACM，?2013：?3111-3119.

［10］ MIKOLOV T，?CHEN K，?CORRADO G，?et al. Efficient estimation of word representations in vector space ［J/OL］. arXiv：1301. 3781，?2013 ［2023-10-10］. https：// arxiv.org/abs/1301.3781v1.

［11］ ABREU R，?ZOETEWEIJ P，?VAN GEMUND A J C. On the accuracy of spectrum-based fault localization ［C］// Testing：?Academic and Industrial Conference Practice and Research Techniques-MUTATION （TAICPART-MUTATION 2007）. Windsor：?IEEE，?2007：89-98.

（責(zé)任編輯：包震宇，郁慧）

DOI：?10.3969/J.ISSN.1000-5137.2024.02.012

收稿日期：?2023-12-25

作者簡介：?王露露（1999—），男，碩士研究生，主要從事軟件工程、代碼異味方面的研究.E-mail：?1000513412@smail.shnu.edu.cn

*通信作者：?陳軍華（1968—），男，副教授，主要從事數(shù)據(jù)信息處理技術(shù)及數(shù)據(jù)庫信息系統(tǒng)方面的研究.E-mail：?chenjh@shnu.edu.cn

引用格式：?王露露，?陳軍華. 基于Word2Vec和決策樹的故障定位技術(shù)?［J］. 上海師范大學(xué)學(xué)報(bào)?（自然科學(xué)版中英文），?2024，53（2）：223?227.

Citation format：?WANG L L，?CHEN J H. Fault location technology based on Word2Vec and decision tree ［J］. Journal of Shanghai Normal University （Natural Sciences），?2024，53（2）：223?227.