[發明專利]代碼克隆的檢測方法

有效

• 申請號: 201410730368.3
• 申請日: 2014-12-04
• 公開（公告）號: CN104407872B
• 公開（公告）日: 2018-01-16
• 發明（設計）人: 張程鵬;李祺;李承澤;董楓;楊昕雨
• 申請（專利權）人: 北京郵電大學
• 主分類號: G06F9/44
• 分類號: G06F9/44
• 代理公司: 北京德琦知識產權代理有限公司11018
• 代理人: 王一斌,王琦

技術領域

本發明涉及計算機應用技術，特別是涉及一種代碼克隆的檢測方法。

背景技術

代碼克隆(Code Clone)是指軟件源代碼中重復出現的相同或相似的代碼片斷。這些代碼片斷可能完全相同，也可能經過了一些編輯性(如修改變量名)或邏輯性的修改(如修改為相似但不相同的功能)。被認為互相克隆的代碼片段往往具有相似的邏輯運算，實現了類似的功能。代碼克隆一般是由于復制粘貼式的代碼復用造成的，也可能是由于解決相似問題的模式化思維造成的。代碼克隆大量存在于大型軟件系統以及若干相似的軟件系統中。克隆代碼在軟件工程中與許多問題密切相關，如軟件的質量、復雜性、架構、進化、專利和剽竊等。克隆代碼檢測有廣泛的應用：首先，隨著開源項目的發展、代碼復用規模的擴大，代碼復用的廣泛程度可以作為代碼質量的評判標準和選擇所復用的代碼模塊的參考依據；其次，通過克隆代碼檢測可以找出大型系統中的克隆代碼，并進行重構，從而消除克隆代碼，提高源代碼的質量。

目前業內普遍依據源代碼的文本相似性與功能相似性將克隆代碼分成四類：1)除了空格與注釋外都相同的代碼段；2)除了標志符、類型、空格和注釋外句法上都相同的代碼段；3)對語句做了增/刪/改的復制代碼段；4)功能上相同但句法上不同的代碼段。其中，一些研究者將第1類稱為完全克隆，將第2、3類稱為近似克隆，將第4類稱為語義克隆。

國內外學者已提出許多克隆檢測方法及技術并開發出相應的克隆檢測工具。這些方法可大致地分成基于文本、基于詞法(token)、基于語法(syntax)、基于語義等。

1)基于文本的檢測方法。該方法是在軟件系統的源代碼上直接進行比較處理(只過濾源代碼的注釋和布局上的不同點)，而不將源代碼轉換成某種中間表示形式。Johnson首次提出基于文本的克隆檢測技術：首先將固定行數的代碼段哈希，然后利用增量哈希函數來識別出具有相同哈希值的代碼段即克隆代碼，同時結合使用滑動窗口技術來查找不同長度的克隆代碼。

2)基于詞法的檢測方法。該方法(也稱為基于token的方法)首先使用詞法分析工具(如lex)將所有源代碼的每一行轉換成一個token序列，并將所有序列連接成一個token串；接著掃描這個token以查找相似的token子序列，然后報告這些相似子串所對應的源代碼為克隆。

3)基于語法的檢測方法。該方法是根據相似的代碼段應該也有相似的句法結構而設計的。程序被解析成一棵語法樹，其中相似的子樹所對應的源代碼段就是克隆代碼。Baxter等人首次將抽象語法樹(AST)技術應用在克隆代碼檢測上，首先將源代碼解析成帶有標注的語法樹，接著將子樹哈希到N個桶(bucket)中，然后對同一個桶中的子樹比較相似性，進而獲得克隆代碼。

4)基于語義的檢測方法。該技術主要以程序依賴圖(PDG)方法為代表，即給定一個程序，根據程序語句之間的數據流和控制依賴關系建立一個PDG的集合，在此集合中的同構子圖所對應的代碼段為克隆代碼。近年來，也有學者使用動態分析的方法去檢測語義上相似的代碼段，如加州大學的Jiang等人通過對代碼段給定一組輸入數據，比較它們的輸出結果，進而得到語義上相似的克隆代碼。Marcus等人使用信息檢索技術(潛在的語義索引)去靜態地分析軟件系統的源代碼進而檢測出語義克隆。

基于文本的方法不需考慮程序句法的正確性，時空復雜度最低，可克隆的查全率偏低。該方法主要用來檢測第l類克隆。但Lee等人利用n-neighbor方法也能檢測到部分近似克隆，效果不理想。

基于token的方法能有效地檢測第1、2類克隆，時空復雜度較低，也不需考慮程序句法的正確性，且獨立于源代碼，但在處理第3類的克隆時會有許多誤檢。

基于語法的方法能有效地檢測第1-3類克隆，但由于需將源代碼解析成AST后再查找相似子樹，所以時空復雜度偏高。不過后來Jiang等人采用歐式距離和特征向量來優化基于AST的檢測方法，降低了尋找同構子樹的復雜度。

與基于語法的比較方法相比，基于PDG的技術從一個更高層面去分析源代碼，以獲得程序的語義信息，所以該技術能檢測到一些被打亂順序、但語義相同的代碼段。但建立PDG和尋找同構子圖花費的代價亦非常高，難以應用于大規模軟件。

由此可見，現有的代碼克隆的檢測方法存在克隆類型檢測不全面、準確度低、復雜度高不易于實現等問題。

發明內容

有鑒于此，本發明的主要目的在于提供一種代碼克隆的檢測方法，該方法可以有效判斷出兩個程序代碼之間是否存在代碼克隆關系，且易于實現。