近年來,隨著開源軟件項目的興起和迅猛發(fā)展,代碼克隆檢測已經(jīng)成為軟件工程領(lǐng)域一個越來越重要的研究課題,很多軟件工程下游應(yīng)用如代碼重構(gòu)、軟件維護、bug和惡意代碼以及軟件剽竊檢測都需要將此作為第一步。目前高級別的代碼克隆檢測仍然是一項困難工作,PDG(Program Dependence Graph)代碼克隆檢測可應(yīng)用于語法、語義和結(jié)構(gòu)功能上相似代碼檢測,屬于高級別代碼檢測。這類研究中存在著候選PDG對規(guī)模大以及子圖同構(gòu)判定時間長等問題。為此,本文在基于PDG結(jié)構(gòu)優(yōu)化、特征向量過濾和克隆判定算法上進行了深入研究。主要工作和貢獻包括:(1)提出并實現(xiàn)了一個基于PDG的代碼克隆檢測工具CCSharp針對現(xiàn)有典型的基于PDG代碼克隆檢測方法存在PDG圖規(guī)模較大、候選PDG對數(shù)多的問題,本文設(shè)計了 PDG圖優(yōu)化和候選PDG對過濾方法。首先,我們對PDG生成工具產(chǎn)生的PDG圖進行結(jié)構(gòu)優(yōu)化,采取去除節(jié)點和合并節(jié)點的方式來降低PDG圖規(guī)模,從而減少PDG同構(gòu)判定的時間消耗。其次,在優(yōu)化后的PDG上,我們設(shè)計了一種PDG特征向量過濾算法來去除掉非克隆的PDG對以降低候選PDG對數(shù)。最后,在優(yōu)化和過濾方法基礎(chǔ)上設(shè)計了一種基于PDG的代碼克隆檢測工具CCSharp。計算實驗表明,PDG圖優(yōu)化方法能使PDG圖規(guī)模平均縮小超過1/3;特征向量過濾方法比傳統(tǒng)的GPALG過濾效果提高了上百倍;CCSharp方法同其他三種代碼克隆檢測工具相比,在less和Postgresq1數(shù)據(jù)集上分別能達到91.7%和99.3%的準確率以及91.7%和89.8%召回率。(2)提出并實現(xiàn)了一種基于圖核相似度計算的機器學(xué)習(xí)PDG代碼克隆檢測方法雖然對傳統(tǒng)PDG代碼克隆檢測方法進行優(yōu)化和過濾之后,代碼克隆檢測時間有明顯提升,但仍然存在處理時間消耗長的問題,我們嘗試將非精確的圖相似度計算方法(圖核函數(shù))和機器學(xué)習(xí)方法應(yīng)用于PDG代碼克隆檢測中。對于一個或一組圖核函數(shù),我們設(shè)計一個或一組PDG相似度矩陣,作為機器學(xué)習(xí)方法的輸入,再通過對數(shù)據(jù)集的人工標記后,應(yīng)用SVM訓(xùn)練出一個分類模型來進行PDG克隆判定。計算實驗表明,分類模型預(yù)測的精度能達到70%-95%,同時其時間消耗要比子圖同構(gòu)判定方法要少。
【學(xué)位單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位年份】：2018
【中圖分類】：TP311.5
【部分圖文】：

１．２．２基于ｔｏｋｅｎ的代碼克隆檢測技術(shù)??基于ｔｏｋｅｎ的代碼克隆檢測方法首先將整個源系統(tǒng)代碼通過詞法解析工具轉(zhuǎn)??化為ｔｏｋｅｎ序列。源碼經(jīng)過轉(zhuǎn)化后得到的一個個單詞即稱為ｔｏｋｅｎ，如圖１．１。接??著掃描轉(zhuǎn)化后的ｔｏｋｅｎ序列以尋找相似或者相同的ｔｏｋｅｎ子序列，子序列對應(yīng)的??原代碼的部分就被報為克隆代碼。對比于基于文本的方法，基于ｔｏｋｅｎ的方法對??于檢測具有不同格式的代碼通常更有魯棒性。??先進的基于ｔｏｋｅｎ的代碼克隆檢測技術(shù)很多如ＣＰ－Ｍｉｎｅｒ［１１］，ＣＣＦｉｎｄｅｒ［１（）＾??等，其中日本的Ｋａｍｉｙａ等人發(fā)表的ＣＣＦｉｎｄｅｒ工具的做法如下：首先通過一個詞??法解析工具將所有源碼文件的每一行代碼都轉(zhuǎn)化為一個個的ｔｏｋｅｎ并將所有文件??的ｔｏｋｅｎ連接合并為一個單一的ｔｏｋｅｎ序列。然后針對所感興趣語言標識符的結(jié)??構(gòu)和標準化方法對合并的大ｔｏｋｅｎ序列做一些ｔｏｋｅｎ的增加，刪除和改變的變換。??變化的目的是將標識符包括類型，變量及常量都替換成特殊的＾１＾１１。這樣的標??識符替換方法使得那些僅是變量名不同的代碼塊也可以被檢測為克隆代碼對。接??著，用一個基于子字符串的后綴樹匹配算法在變化后的ｔｏｋｅｎ序列中尋找相似的??子序列

圖２．１控制流程圖（ＣＦＧ）??表２．１集￥?Ｓ中所有邊的控制￥賴關(guān)系Ｓ中的邊?控制依賴于?標簽??１?Ｔ１?Ｆ２?Ｔ２?Ｆ??３??Ｔ系??數(shù)據(jù)依賴子圖的構(gòu)造過程中，圖中節(jié)點所表個運算符級別的子圖。這種子圖在沒有由調(diào)用所帶來的副作用時幾乎非常容易構(gòu)建。

不管針對什么樣的語言做的檢測，使用什么樣的ＰＤＧ生成工具和應(yīng)用什么??樣的克隆尋找和判定算法，絕大多數(shù)的方法都有著總體相似的代碼克隆檢測流??程。在圖２．２中，我們給出了?ＰＤＧ代碼克隆檢測方法流程中的重要環(huán)節(jié)或步驟，??其中虛線部分表示在一些早期工作或是小規(guī)模數(shù)據(jù)集上的工作中并沒有考慮的??降低克隆比較空間的步驟，但是在實際的代碼克隆檢測過程中這卻是非常重要和??實際需要考慮的內(nèi)容。??，一＇、?ｉ?：?ｒ—＾＾??、＿＿乂通過生成?丨降低克�。�?ＰＤＧ對的?、＾??源代——＾工具產(chǎn)生——比較空間；——＾克隆判定——＾克隆??碼?源碼的?ｉ以減低時；?及克隆的?ｔ結(jié)果??＾＞?ＰＤＧ?丨間消耗?丨?聚類?＾＾??＼?Ｊ??」?Ｖ?Ｊ??圖２．２?ＰＤＧ代碼克隆檢測的流程??基于ＰＤＧ代碼克隆檢測方法的總體流程主要包括三個重要的步驟，分別如??下：??（１）?ＰＤＧ生成：源代碼中的程序語句作為一種高級抽象的邏輯和運算表示??并不能很好的簡單被機器理解和支持。在代碼的編譯運行的過程中，是先將高級??語言通過各種編譯器轉(zhuǎn)化成計算機可以支持的匯編代碼或機器指令，再生成相應(yīng)??的二進制可執(zhí)行代碼運行的。相似地，在代碼克隆檢測方法中也首先需要將這些??高級語言轉(zhuǎn)化成較容易理解和處理的形式。在基于ＰＤＧ的方法中
【相似文獻】

相關(guān)期刊論文 前10條

1 張春英;張雪;;不確定屬性圖的子圖同構(gòu)及其判定算法[J];計算機科學(xué);2013年06期

2 張一楠;鄒兆年;李建中;;不確定圖間α-β子圖同構(gòu)匹配算法[J];智能計算機與應(yīng)用;2011年05期

3 陳新泉;;圖同構(gòu)的判定研究[J];集成技術(shù);2013年06期

4 張碩;李建中;高宏;鄒兆年;;一種多到一子圖同構(gòu)檢測方法[J];軟件學(xué)報;2010年03期

5 周克元;;圖同構(gòu)的一個算法[J];和田師范�？茖W(xué)校學(xué)報;2007年02期

6 劉富貴;;兩圖同構(gòu)的一個必要條件和一個充要條件[J];武漢水運工程學(xué)院學(xué)報;1992年02期

7 劉波;房斌;張世勇;李直霖;;基于關(guān)系模型的子圖同構(gòu)檢測算法設(shè)計與實現(xiàn)[J];計算機工程;2011年11期

8 王毅;丁函;任丹;;一種無向圖同構(gòu)的判定算法[J];科技創(chuàng)新與應(yīng)用;2012年28期

9 侯愛民;郝志峰;胡傳福;陸海鵬;;無向圖同構(gòu)的快速算法[J];華南理工大學(xué)學(xué)報(自然科學(xué)版);2011年10期

10 侯愛民;;圖同構(gòu)的一個充分必要條件[J];計算機工程與應(yīng)用;2009年30期

相關(guān)博士學(xué)位論文 前4條

1 商慧亮;一種新的圖同構(gòu)判定算法[D];復(fù)旦大學(xué);2009年

2 張碩;圖數(shù)據(jù)庫查詢處理技術(shù)的研究[D];哈爾濱工業(yè)大學(xué);2010年

3 侯愛民;哈密頓環(huán)與圖同構(gòu)問題的理論研究及算法設(shè)計[D];華南理工大學(xué);2013年

4 商慧亮;一種新的圖同構(gòu)判定算法——電路模擬法[D];復(fù)旦大學(xué);2009年

相關(guān)碩士學(xué)位論文 前10條

1 汪敏;基于程序依賴圖的代碼克隆檢測算法研究[D];中國科學(xué)技術(shù)大學(xué);2018年

2 劉楊;基于大圖處理框架的分布式子圖同構(gòu)研究[D];北京郵電大學(xué);2018年

3 吳楠;有向圖子圖同構(gòu)計算算法研究[D];遼寧大學(xué);2012年

4 李美云;子圖同構(gòu)問題中索引構(gòu)建方法研究[D];燕山大學(xué);2017年

5 王小濤;基于子圖同構(gòu)搜索的徽派建筑快速建模方法研究[D];合肥工業(yè)大學(xué);2013年

6 李辰辰;基于非挖掘索引的圖查詢研究[D];遼寧大學(xué);2014年

7 韓玉;基于圖數(shù)據(jù)的子圖同構(gòu)算法研究[D];燕山大學(xué);2015年

8 張一楠;圖結(jié)構(gòu)數(shù)據(jù)上的子圖查詢[D];哈爾濱工業(yè)大學(xué);2011年

9 張海龍;圖的同構(gòu)問題算法研究[D];華中科技大學(xué);2007年

10 潘佳文;PTC-SaaS中基于圖匹配的租約推薦方法研究[D];東北大學(xué);2012年

本文編號：2871987