近年來(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)題。為此,本文在基于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)判定的時(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和Postgresq1數(shù)據(jù)集上分別能達(dá)到91.7%和99.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ù)集的人工標(biāo)記后,應(yīng)用SVM訓(xùn)練出一個(gè)分類(lèi)模型來(lái)進(jìn)行PDG克隆判定。計(jì)算實(shí)驗(yàn)表明,分類(lèi)模型預(yù)測(cè)的精度能達(dá)到70%-95%,同時(shí)其時(shí)間消耗要比子圖同構(gòu)判定方法要少。
【學(xué)位單位】：中國(guó)科學(xué)技術(shù)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位年份】：2018
【中圖分類(lèi)】：TP311.5
【部分圖文】：

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

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

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

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

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

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

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

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

5 周克元;;圖同構(gòu)的一個(gè)算法[J];和田師范專(zhuān)科學(xué)校學(xué)報(bào);2007年02期

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 李美云;子圖同構(gòu)問(wèn)題中索引構(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)問(wèn)題算法研究[D];華中科技大學(xué);2007年

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

本文編號(hào)：2871987