基于程序依賴圖的代碼克隆檢測算法研究.pdf

1、近年來，隨著開源軟件項(xiàng)目的興起和迅猛發(fā)展，代碼克隆檢測已經(jīng)成為軟件工程領(lǐng)域一個(gè)越來越重要的研究課題，很多軟件工程下游應(yīng)用如代碼重構(gòu)、軟件維護(hù)、bug和惡意代碼以及軟件剽竊檢測都需要將此作為第一步。目前高級別的代碼克隆檢測仍然是一項(xiàng)困難工作，PDG(Program Dependence Graph)代碼克隆檢測可應(yīng)用于語法、語義和結(jié)構(gòu)功能上相似代碼檢測，屬于高級別代碼檢測。這類研究中存在著候選PDG對規(guī)模大以及子圖同構(gòu)判定時(shí)間長等問題。為

2、此，本文在基于PDG結(jié)構(gòu)優(yōu)化、特征向量過濾和克隆判定算法上進(jìn)行了深入研究。主要工作和貢獻(xiàn)包括:
　　(1)提出并實(shí)現(xiàn)了一個(gè)基于PDG的代碼克隆檢測工具CCSharp
　　針對現(xiàn)有典型的基于PDG代碼克隆檢測方法存在PDG圖規(guī)模較大、候選PDG對數(shù)多的問題，本文設(shè)計(jì)了PDG圖優(yōu)化和候選PDG對過濾方法。首先，我們對PDG生成工具產(chǎn)生的PDG圖進(jìn)行結(jié)構(gòu)優(yōu)化，采取去除節(jié)點(diǎn)和合并節(jié)點(diǎn)的方式來降低PDG圖規(guī)模，從而減少PDG同構(gòu)判定的

3、時(shí)間消耗。其次，在優(yōu)化后的PDG上，我們設(shè)計(jì)了一種PDG特征向量過濾算法來去除掉非克隆的PDG對以降低候選PDG對數(shù)。最后，在優(yōu)化和過濾方法基礎(chǔ)上設(shè)計(jì)了一種基于PDG的代碼克隆檢測工具CCSharp。計(jì)算實(shí)驗(yàn)表明，PDG圖優(yōu)化方法能使PDG圖規(guī)模平均縮小超過1/3;特征向量過濾方法比傳統(tǒng)的GPALG過濾效果提高了上百倍;CCSharp方法同其他三種代碼克隆檢測工具相比，在less和Postgresql數(shù)據(jù)集上分別能達(dá)到91.7％和99.

4、3％的準(zhǔn)確率以及91.7％和89.8％召回率。
　　(2)提出并實(shí)現(xiàn)了一種基于圖核相似度計(jì)算的機(jī)器學(xué)習(xí)PDG代碼克隆檢測方法
　　雖然對傳統(tǒng)PDG代碼克隆檢測方法進(jìn)行優(yōu)化和過濾之后，代碼克隆檢測時(shí)間有明顯提升，但仍然存在處理時(shí)間消耗長的問題，我們嘗試將非精確的圖相似度計(jì)算方法（圖核函數(shù)）和機(jī)器學(xué)習(xí)方法應(yīng)用于PDG代碼克隆檢測中。對于一個(gè)或一組圖核函數(shù)，我們設(shè)計(jì)一個(gè)或一組PDG相似度矩陣，作為機(jī)器學(xué)習(xí)方法的輸入，再通過對數(shù)據(jù)集