基于AST 的程序代碼相似性度量研究

朱 波，鄭 虹，孫琳琳，楊友星

(長春工業(yè)大學計算機科學與工程學院，長春130012)

0 引言

隨著計算機網(wǎng)絡技術的飛速發(fā)展，信息資源在方便快捷獲取的同時，資源的抄襲現(xiàn)象愈加普遍。其中，在計算機程序設計類課程中，學生間的抄襲情況極為嚴重。澳大利亞蒙納什(Monash)大學對其學生中的代碼抄襲現(xiàn)象進行調(diào)查統(tǒng)計顯示:高達85.4%的學生承認抄襲過他人的作業(yè)［1，2］。另外，在軟件商業(yè)領域，不同軟件企業(yè)因為軟件產(chǎn)品相似所引發(fā)的產(chǎn)權糾紛也越來越多。為扼制不良抄襲學風，加強對知識產(chǎn)權的保護力度，對程序代碼相似性度量的研究顯得日趨重要。

筆者在研究國內(nèi)外程序代碼抄襲檢測的基礎上，針對Java程序中常見的抄襲手段，提出一種基于AST的檢測Java程序代碼抄襲的方法。首先對程序代碼進行預處理，減少冗余信息;然后對預處理后的代碼進行遍歷生成AST;最后通過采用自適應閾值選取方式，對AST進行相似度計算，判定是否抄襲，最終生成相似度檢測報告。

1 相關定義

1.1 相似度定義

Yamamoto等［3］給出了兩個軟件系統(tǒng)的相似度的定義。對于兩個軟件P和X，軟件P是由元素P1，P2，…，Pm組成，P 的集合構成表示為{P1，P2，…，Pm}。同樣，軟件 X 由元素 X1，X2，…，Xn組成，其元素的集合表示為{X1，X2，…，Xn}。其中P，X中的元素可以表示軟件P和X中的文件或代碼行。

假設能求出Pi與Xj(1≤i≤m且1≤j≤n)間的匹配，用集合Rs表示所有的匹配對(Pi，Xj)，其中Rs?P×X，則P和X的相似性定義為

根據(jù)式(1)可看出，相似性S為一個比值，由Rs中元素的個數(shù)比上P和X中元素的個數(shù)和所得。如果Rs較小，相應的S也較小。……