程序代碼相似度檢測(cè)方法研究及應(yīng)用.pdf

1、程序語(yǔ)言課程是計(jì)算機(jī)及其相關(guān)專業(yè)非常重要的一門專業(yè)基礎(chǔ)課，程序語(yǔ)言的教學(xué)顯得尤為重要。隨著互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展，信息化教育成為現(xiàn)代化新型教育模式，然而互聯(lián)網(wǎng)帶來(lái)便利的同時(shí)，也為程序代碼抄襲提供了方便。程序代碼相似度檢測(cè)不僅可以幫助教師檢測(cè)學(xué)生的程序作業(yè)抄襲情況，同時(shí)對(duì)軟件版權(quán)的鑒定也具有好的現(xiàn)實(shí)意義。
　　 代碼相似度檢測(cè)技術(shù)的研究已有幾十年的歷史，基本歸結(jié)為兩大類技術(shù):屬性計(jì)數(shù)技術(shù)和結(jié)構(gòu)度量技術(shù)。本文在分析各種代碼相似度檢測(cè)系

2、統(tǒng)的基礎(chǔ)后，對(duì)相似度檢測(cè)方法展開(kāi)研究。屬性計(jì)數(shù)技術(shù)被證明只對(duì)完全抄襲的代碼檢測(cè)有效，當(dāng)今比較成熟的系統(tǒng)都采用結(jié)構(gòu)度量技術(shù)，主要利用GST字符串匹配算法進(jìn)行結(jié)構(gòu)度量。首先分析了基于串匹配算法的代碼相似度檢測(cè)方法，并對(duì)其進(jìn)行了改進(jìn);然后充分挖掘程序代碼的結(jié)構(gòu)信息，設(shè)計(jì)了基于子圖同構(gòu)算法的代碼相似度檢測(cè)方法。該方法采用基于回溯搜索的子圖同構(gòu)算法，把程序源碼按節(jié)點(diǎn)類型和邊類型轉(zhuǎn)換成程序依賴圖。代碼的結(jié)構(gòu)信息主要是由各行代碼間的數(shù)據(jù)依賴和控制依賴

3、關(guān)系構(gòu)成，代碼行轉(zhuǎn)換成七種類型的節(jié)點(diǎn)，根據(jù)代碼層次樹(shù)結(jié)構(gòu)將節(jié)點(diǎn)之間的數(shù)據(jù)依賴和控制依賴關(guān)系進(jìn)行查找，獲得程序依賴圖。為了去除對(duì)輸出結(jié)果沒(méi)有影響的無(wú)用代碼，程序依賴圖經(jīng)過(guò)主數(shù)據(jù)流的抽取最終變?yōu)橹鲾?shù)據(jù)流圖。把需要進(jìn)行檢測(cè)的兩段代碼的主數(shù)據(jù)流圖使用基于回溯搜素的子圖同構(gòu)算法找出兩個(gè)圖的最大公共子圖，根據(jù)公共子圖的大小來(lái)確定兩段代碼的相似度，可以有效排除一些無(wú)用的結(jié)構(gòu)和變量，提高檢測(cè)的準(zhǔn)確性。
　　 基于GST串匹配和子圖同構(gòu)的相似度檢