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

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

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

3、時(shí)間消耗。其次，在優(yōu)化后的PDG上，我們?cè)O(shè)計(jì)了一種PDG特征向量過(guò)濾算法來(lái)去除掉非克隆的PDG對(duì)以降低候選PDG對(duì)數(shù)。最后，在優(yōu)化和過(guò)濾方法基礎(chǔ)上設(shè)計(jì)了一種基于PDG的代碼克隆檢測(cè)工具CCSharp。計(jì)算實(shí)驗(yàn)表明，PDG圖優(yōu)化方法能使PDG圖規(guī)模平均縮小超過(guò)1/3;特征向量過(guò)濾方法比傳統(tǒng)的GPALG過(guò)濾效果提高了上百倍;CCSharp方法同其他三種代碼克隆檢測(cè)工具相比，在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代碼克隆檢測(cè)方法
　　雖然對(duì)傳統(tǒng)PDG代碼克隆檢測(cè)方法進(jìn)行優(yōu)化和過(guò)濾之后，代碼克隆檢測(cè)時(shí)間有明顯提升，但仍然存在處理時(shí)間消耗長(zhǎng)的問(wèn)題，我們嘗試將非精確的圖相似度計(jì)算方法（圖核函數(shù)）和機(jī)器學(xué)習(xí)方法應(yīng)用于PDG代碼克隆檢測(cè)中。對(duì)于一個(gè)或一組圖核函數(shù)，我們?cè)O(shè)計(jì)一個(gè)或一組PDG相似度矩陣，作為機(jī)器學(xué)習(xí)方法的輸入，再通過(guò)對(duì)數(shù)據(jù)集