本文關鍵詞：程序代碼相似性度量方法研究

  更多相關文章： 相似性度量 GST算法 token特征串 抽象語法樹 抄襲檢測

【摘要】：計算機信息技術的飛速發(fā)展,使得資源的獲取和使用也變得更加的快捷方便。但與此同時,信息資源之間的抄襲也變得越來越簡單和難以防范。例如在計算機的程序設計類課程中,進行程序作業(yè)完成提交及在線測試時,學生之間進行彼此抄襲的現(xiàn)象非常的普遍。這種現(xiàn)象嚴重影響了教學質(zhì)量、制約了學生素質(zhì)的提高發(fā)展,更加無法確�？己说墓焦�。此外,在軟件商業(yè)領域中,軟件產(chǎn)品發(fā)生版權(quán)爭端的事件也時有發(fā)生。對程序代碼相似性度量方法及其應用的進一步深入高效研究,將在很大程度上扼制在程序設計類課程中存在的普遍的抄襲現(xiàn)象,加大對軟件商業(yè)領域中軟件產(chǎn)品的知識產(chǎn)權(quán)保護力度。本文分析了目前國內(nèi)外在程序相似性度量領域的相關研究,對常用的相似性度量檢測方法做了綜合的對比分析。并在此基礎上對程序代碼相似性度量方法進行了以下的相關研究。首先,對于傳統(tǒng)字符串匹配算法GST算法在進行串匹配時需要逐個比較串的每個字符、造成時問復雜度相對較大的問題,提出了一種基于Java多線程并行匹配的設計方式,以此對GST算法的匹配過程進行了改進,有效的提高了算法進行匹配檢測的時間效率；然后,針對GST算法時間復雜度和參加檢測匹配的字符串長度成正比的特點,對能夠代表程序語義結(jié)構(gòu)的token序列,提出一種設計思想：在對其語義沒有影響的條件下對其長度進行縮短,可以進一步降低匹配的時間復雜度；最后,針對利用工具生成抽象語法樹時會包含大量的冗余信息,容易造成資源的極大浪費的問題,設計并實現(xiàn)了一種構(gòu)造抽象語法樹的算法,該算法通過先創(chuàng)建父節(jié)點后創(chuàng)建子節(jié)點,再將其關聯(lián)的方式,將程序中類、方法等體現(xiàn)程序語義結(jié)構(gòu)的有用信息進行抽象語法樹的構(gòu)造,并且設計了類信息表和方法信息表進行數(shù)據(jù)的存儲和更新,方便數(shù)據(jù)的使用。通過抽象語法樹的算法設計,在構(gòu)造生成語法樹后,可以遍歷解析語法樹使其生成能夠表示程序語義結(jié)構(gòu)的token序列串,再結(jié)合改進的字符串匹配算法GST進行相似度的計算,得到最終的相似性度量分析結(jié)果。根據(jù)上述的方法理論,本文設計并且實現(xiàn)了一個基于Java語言的程序代碼相似度檢測系統(tǒng),該系統(tǒng)可以計算源程序?qū)χg的相似度。在同等測試程序集和程序?qū)Φ幕A上和Moss系統(tǒng)的抄襲檢測結(jié)果進行了對比分析。實驗結(jié)果表明,本文的研究內(nèi)容,可以有效的檢測出大部分抄襲手段,并且具有較高的檢測時問效率。在代碼檢測的精度和準確度方面都具有較高的可靠性。
【關鍵詞】：相似性度量 GST算法 token特征串 抽象語法樹 抄襲檢測
【學位授予單位】：長春工業(yè)大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：TP311.1
【目錄】：

• 摘要2-3
• Abstract3-7
• 第一章 緒論7-11
• 1.1 研究背景及意義7
• 1.2 國內(nèi)外研究現(xiàn)狀及其分析7-9
• 1.2.1 國外研究現(xiàn)狀7-8
• 1.2.2 國內(nèi)研究現(xiàn)狀8-9
• 1.2.3 研究現(xiàn)狀分析及發(fā)展趨勢9
• 1.3 本文的主要工作9-10
• 1.4 本文的組織結(jié)構(gòu)10-11
• 第二章 程序代碼抄襲檢測研究概述11-18
• 2.1 代碼抄襲種類描述11-12
• 2.2 相似性度量相關概念12-13
• 2.2.1 相似度定義12-13
• 2.2.2 抄襲檢測概念13
• 2.3 相似性度量技術概述13-15
• 2.3.1 屬性計數(shù)法14
• 2.3.2 結(jié)構(gòu)度量法14-15
• 2.3.3 其他方法15
• 2.4 現(xiàn)有的相似度檢測系統(tǒng)15-17
• 2.4.1 Plague系統(tǒng)15-16
• 2.4.2 MOSS系統(tǒng)16
• 2.4.3 SIM系統(tǒng)16-17
• 2.4.4 JPlag系統(tǒng)17
• 2.5 本章小結(jié)17-18
• 第三章 字符串匹配算法比較和改進研究18-28
• 3.1 基本概念18
• 3.2 Knuth-Morris-Pratt算法18-19
• 3.3 Longest Common Subsequence算法19-20
• 3.4 動態(tài)程序設計20-21
• 3.5 Rabin-Karp算法21
• 3.6 Greedy String Tiling算法21-23
• 3.7 對GST算法的改進23-27
• 3.8 本章小結(jié)27-28
• 第四章 基于抽象語法樹的程序代碼抄襲檢測28-39
• 4.1 抽象語法樹概述28-29
• 4.1.1 抽象語法樹28
• 4.1.2 本文研究抄襲檢測流程28-29
• 4.2 代碼預處理29-30
• 4.3 生成抽象語法樹30-37
• 4.3.1 算法描述30-31
• 4.3.2 算法實現(xiàn)結(jié)果31-34
• 4.3.3 數(shù)據(jù)存儲結(jié)構(gòu)描述34
• 4.3.4 AST算法及存儲結(jié)構(gòu)分析34-37
• 4.4 相似性度量37-38
• 4.5 本章小結(jié)38-39
• 第五章 相似度檢測的實驗與結(jié)果分析39-47
• 5.1 實驗環(huán)境和實驗數(shù)據(jù)39-40
• 5.1.1 實驗環(huán)境39
• 5.1.2 實驗數(shù)據(jù)39-40
• 5.2 實驗結(jié)果分析40-46
• 5.2.1 源程序與待檢測程序檢測結(jié)果分析40-43
• 5.2.2 測試集任意兩程序匹配檢測結(jié)果分析43-46
• 5.2.3 實驗數(shù)據(jù)說明46
• 5.3 本章小結(jié)46-47
• 第六章 總結(jié)與展望47-48
• 6.1 總結(jié)47
• 6.2 展望47-48
• 致謝48-49
• 參考文獻49-52
• 作者簡介52
• 攻讀碩士學位期間研究成果52-53

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前6條

1 趙長海;晏海華;金茂忠;;基于編譯優(yōu)化和反匯編的程序相似性檢測方法[J];北京航空航天大學學報;2008年06期

2 張鵬;王國胤;陶春梅;羅海;;基于本體粗糙集的程序代碼相似度度量方法[J];重慶郵電大學學報(自然科學版);2008年06期

3 于海英;;字符串相似度度量中LCS和GST算法比較[J];電子科技;2011年03期

4 熊浩;晏海華;赫建營;趙長海;;一種基于靜態(tài)詞法樹的程序相似性檢測方法[J];計算機應用研究;2009年04期

5 張麗萍;劉東升;李彥臣;鐘美;;一種基于AST的代碼抄襲檢測方法[J];計算機應用研究;2011年12期

6 張文典,任冬偉;程序抄襲判定系統(tǒng)[J];小型微型計算機系統(tǒng);1988年10期

中國碩士學位論文全文數(shù)據(jù)庫 前4條

1 王繼遠;一種用于軟件作業(yè)評判系統(tǒng)的程序結(jié)構(gòu)分析算法的設計與實現(xiàn)[D];北京郵電大學;2007年

2 侯敏;程序代碼復制檢測中特征串提取技術研究[D];內(nèi)蒙古師范大學;2009年

3 趙彥博;基于抽象語法樹的程序代碼抄襲檢測技術研究[D];內(nèi)蒙古師范大學;2010年

4 胡正軍;程序代碼相似度檢測方法研究及應用[D];中南大學;2012年

，

本文編號：767117