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

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

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

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

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