《電子技術(shù)應(yīng)用》
您所在的位置：首頁 > 其他 > 設(shè)計(jì)應(yīng)用 > 基于改進(jìn)WL圖核的代碼克隆檢測(cè)方法
基于改進(jìn)WL圖核的代碼克隆檢測(cè)方法
網(wǎng)絡(luò)安全與數(shù)據(jù)治理 3期
班必奐1，2，徐 云2，3
(1.中國科學(xué)技術(shù)大學(xué) 大數(shù)據(jù)學(xué)院，安徽 合肥230026； 2.安徽省高性能計(jì)算重點(diǎn)實(shí)驗(yàn)室，安徽 合肥230026； 3.中國科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥230026)
摘要： 基于程序依賴圖(Program Dependency Graph，PDG)的代碼克隆檢測(cè)方法是檢測(cè)代碼克隆的重要方法之一，近年來提出的基于Weisfeiler-Lehman(WL)圖核迭代的近似圖匹配方法在克隆檢測(cè)中取得了較好的效果，但PDG中少量頂點(diǎn)的差異會(huì)隨著圖核迭代傳播到越來越多的頂點(diǎn)，從而導(dǎo)致算法召回率的下降。為此，針對(duì)WL圖核在克隆檢測(cè)應(yīng)用中存在的問題，提出了一種基于改進(jìn)WL圖核的代碼克隆檢測(cè)方法，將WL圖核迭代過程中采用的普通哈希算法替換為局部敏感哈希，同時(shí)引入向量的相似性度量方法，進(jìn)一步提升了對(duì)PDG近似子結(jié)構(gòu)的識(shí)別能力。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的方法不僅可以檢測(cè)出更多的差異克隆對(duì)，同時(shí)還保持了良好的精度和時(shí)間性能。
中圖分類號(hào)： TP311.5
文獻(xiàn)標(biāo)識(shí)碼： A
DOI： 10.20044/j.csdg.2097-1788.2022.03.010
引用格式： 班必奐，徐云. 基于改進(jìn)WL圖核的代碼克隆檢測(cè)方法[J].網(wǎng)絡(luò)安全與數(shù)據(jù)治理，2022，41(3)：60-66.
An improved WL graph kernel-based code clone detection method
Ban Bihuan1，2，Xu Yun2，3
(1.School of Data Science，University of Science and Technology of China，Hefei 230026，China； 2.Key Laboratory of High Performance Computing of Anhui Province，Hefei 230026，China； 3.School of Computer Science and Technology，University of Science and Technology of China，Hefei 230026，China)
Abstract： Code clone detection based on Program Dependency Graph(PDG) is one of the important methods in code clone detection domain. In recent years, a code clone detector that based on Weisfeiler-Lehman(WL) graph kernel has achieved success in detecting code clones. However, several different vertices in the PDG will ″spread″ to the whole PDG with iterations and finally results in a decline in recall rate. Therefore, an improved WL kernel-based clone detector is proposed to address the problem of the WL kernel when applied in clone detections. The ordinary hash algorithm used in the iterations of WL kernel is replaced with the local sensitive hash algorithm, and the vector similarity measure approach is employed, which enhances the ability to identify the similar PDG sub-structures. The experimental results show that compared to the original WL graph kernel-based detector, the improved method can not only detect more clones but also keep good accuracy and a low computing time.
Key words : code clone detection；program dependency graph；Weisfeiler-Lehman kernel

0 引言

在實(shí)際的軟件系統(tǒng)開發(fā)過程中，開發(fā)人員出于提高開發(fā)效率或者降低軟件錯(cuò)誤風(fēng)險(xiǎn)的原因，通常會(huì)將其他模塊中功能相同或者相近的代碼片段通過復(fù)制—修改(或不修改)—粘貼的模式引入到當(dāng)前正在開發(fā)的模塊中，這些粘貼而來的功能相同或相似的代碼片段在學(xué)術(shù)界通常被稱為克隆代碼[1]。大量的研究表明，過多的克隆代碼會(huì)給軟件系統(tǒng)帶來維護(hù)成本提高[2]和Bug蔓延[3]等問題。例如，假設(shè)某一段代碼中存在Bug并且這段代碼被復(fù)制粘貼在不同的位置，那么這個(gè)Bug將會(huì)隨著這些克隆代碼在整個(gè)軟件中傳播，進(jìn)而增加了維護(hù)的難度。因此，檢測(cè)出軟件系統(tǒng)中的克隆代碼并對(duì)其進(jìn)行統(tǒng)一管理是非常有必要的。

隨著代碼克隆檢測(cè)技術(shù)的不斷發(fā)展，高級(jí)別代碼克隆(即Type-3和Type-4克隆)的檢測(cè)成為當(dāng)前的研究熱點(diǎn)之一。由于高級(jí)別克隆代碼往往在復(fù)制粘貼之后還進(jìn)行了一些修改，因此也更有可能存在Bug[4]。另外，修改所導(dǎo)致的差異性也使得這一類型的克隆更加難以被檢測(cè)。

得益于程序依賴圖(Program Dependency Graph，PDG)中所包含的大量語法結(jié)構(gòu)信息和語義信息，基于PDG的克隆檢測(cè)方法在檢測(cè)高級(jí)別克隆上更具優(yōu)勢(shì)，能夠檢測(cè)出更多的結(jié)構(gòu)相似但文本差異較大的高級(jí)別克隆代碼。但在已有的方法中，采用精確圖匹配算法的CCSharp[5]、GPLAG[6]等克隆檢測(cè)方法存在時(shí)間性能差和召回率低的缺點(diǎn)，而采用Weisfeiler-Lehman(WL)圖核進(jìn)行近似圖匹配計(jì)算的CCGraph[7]，受限于節(jié)點(diǎn)初始標(biāo)簽的單一性和WL圖核迭代過程中對(duì)近似子結(jié)構(gòu)識(shí)別能力的缺失，召回率也相對(duì)較低。為此，本文針對(duì)WL圖核算法在PDG克隆檢測(cè)應(yīng)用中存在的缺陷，提出了一種改進(jìn)思路：首先利用語法分析技術(shù)將PDG節(jié)點(diǎn)所包含的源代碼信息解析為特征向量的形式來作為該節(jié)點(diǎn)的初始標(biāo)簽，使其能夠保留更多的語義信息；然后通過引入局部敏感哈希技術(shù)提升PDG中近似子結(jié)構(gòu)的識(shí)別能力，進(jìn)而提升高級(jí)別克隆的召回率。





本文詳細(xì)內(nèi)容請(qǐng)下載：http://ihrv.cn/resource/share/2000004907





作者信息：

班必奐1，2，徐  云2，3

(1.中國科學(xué)技術(shù)大學(xué) 大數(shù)據(jù)學(xué)院，安徽 合肥230026；

2.安徽省高性能計(jì)算重點(diǎn)實(shí)驗(yàn)室，安徽 合肥230026；

3.中國科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥230026)


微信圖片_20210517164139.jpg

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。