基于本地代理和索引信息的代碼侵權檢測方法

寨亮+張剛+趙逢禹

摘要：開源軟件越來越豐富，企業開發人員可以方便地通過復用開源代碼提高開發效率。但是開源代碼的許可證非常復雜，未加管理的代碼復用可能給企業帶來嚴重的法律風險。通過侵權檢測發現潛在侵權風險是企業自我保護的重要手段，然而一般企業都沒有能力維護互聯網級別的開源代碼庫，而使用第三方檢測系統需要提供企業自己的源碼，可能造成企業技術秘密泄露。為解決上述問題，提出了一種基于本地代理的代碼侵權檢測方案，該方案僅需要對外提交代碼的結構和索引信息即可，無需提供完整的源碼，既保護了企業源碼隱私，又避免了企業維護大量開源代碼庫的額外負擔，實現了高效的侵權檢測。

關鍵詞：侵權檢測；哈希值；索引；代碼抄襲；克隆檢測；本地代理

DOIDOI：10.11907/rjdk.171685

中圖分類號：TP306

文獻標識碼：A 文章編號：1672-7800（2017）006-0005-06

0 引言

軟件開發人員在進行軟件編碼時，往往會參考他人的代碼，特別是通過網絡獲取大量代碼。大量開源代碼為這種開發模式帶來了很大的便利，但是由于開源代碼采用的許可證種類多樣，每種許可證的約束都不相同，盲目復用軟件很可能給企業帶來嚴重的法律風險。Oracle和谷歌曠日持久的侵權官司就是一例。Oracle在2012年起訴谷歌，控告谷歌的軟件代碼侵權，包括了多項指控，其中包括9行代碼重復。該官司前后打了4年，直到2016年才塵埃落定。雖然最終Oracle敗訴，但由于代碼抄襲帶來的法律風險仍然給企業造成了巨大損失[1]。

開源軟件的許可證包括MIT許可證、Apache許可證、GPL許可證、LGPL許可證等[2]。不同的許可證信息賦予代碼使用者不同權利。例如GPL許可證就具備典型的傳染性質。GPL允許開發者對開源代碼自由使用和修改，但是，基于GPL許可證的代碼修改和新開發的代碼必須遵循GPL許可證，對代碼公開，不允許將修改、衍生的代碼作為閉源的商業軟件發布和銷售。

由于企業軟件開發人員數量多，代碼量大，而開源軟件的數量更是數不勝數，對各種許可證及侵權風險進行手工檢查幾乎不可能。因此，為了幫助企業規避潛在的法律風險，就需要一個可以檢測并報告潛在軟件侵權風險的方法和系統。

在軟件抄襲檢測方面，已經研究和開發了較多的方法和系統[3]，較常用的檢測系統包括JPlag[4]、MOSS[5]、YAP3[6]、GPLAG[8]等。一般來說，抄襲檢測需要將檢測的代碼完整提供給軟件抄襲檢測系統，如果企業使用第三方檢測服務，就意味著企業需將待檢測的軟件源碼上傳給第三方，這給企業源碼安全構成一定風險，并有可能造成企業技術秘密、甚至業務秘密泄露。如果不使用第三方服務，企業就需要自己構建和維護一套完整的抄襲檢測系統。為了有效檢測，該系統需要擁有互聯網上所有帶有許可證的開源代碼，這對一般企業來說負擔巨大，甚至是不可完成的任務。因此，一種既可以保護企業源碼安全又能高效快速進行軟件侵權檢測的方法對企業具有重要的現實意義。

為了解決上述問題，本文提出了一種基于本地代理和代碼塊哈希索引的代碼侵權檢測方案，該方案能很好地保護企業源碼隱私，避免企業維護大量開源代碼庫的額外負擔。

本文方法主要優點：①通過本地代理，僅需要上傳代碼塊的哈希索引特征和結構特征，無需企業提供原始代碼，能夠很好地保護企業技術秘密；②基于代碼塊的哈希索引和結構信息對于侵權檢測仍然是信息完備的，不影響檢測效果，而且這種形式較源碼而言占用內存空間更少，傳輸速度更快，檢索速度也更快；③特征定義清晰，檢測規則可以靈活調整和持續改進；④檢測時比對項目眾多，能夠基于整個互聯網的項目進行檢測，并且能夠基于統計信息自動降低誤報率，檢測結果更加準確。

1 相關工作

現有程序代碼抄襲檢測方法主要包括兩類：基于屬性統計的檢測技術和基于結構度量的檢測技術。

屬性統計技術只對程序的屬性進行統計處理，不考慮程序的內部結構。文獻[11]最早把屬性統計技術用于程序代碼抄襲檢測。Halstead統計了4個屬性，即N1為運算符出現的次數，N2為運算數出現的次數，n1為不同運算符的數量，n2為不同運算數的數量，則源程序被轉化為一個四元組（n1，n2，N1，N2），當兩個源程序的四元組相同時將其判定為抄襲。不同學者[12-14]引入了許多度量指標，但這些嘗試都收效甚微。由于屬性統計技術是對整個程序進行度量，忽略了大部分結構信息，僅增加度量指標對程序的檢測結果沒有實質性提升。該方法對直接復制粘貼的代碼抄襲檢測效果較好，當對源程序進行結構修改或增加刪除代碼段時效果卻不理想，存在很多漏報。

結構度量技術是根據程序的內部結構信息來判斷兩個程序之間是否相似。結構度量技術是代碼克隆檢測方法[9]的一個子集，包括基于文本的方法、基于Token的方法、基于抽象語法樹（AST）的方法、基于程序依賴圖（PDG）的方法等。

基于文本的抄襲檢測方法從源代碼的文本結構入手來檢測程序的相似度，其中的代表性工具如Dup[15]，是以源代碼的每一行作為比較單元，通過構建后綴樹來計算代碼的相似度。而文獻[10]利用滑窗來分割代碼行，配合基于索引的方式提出了一種較為高效的檢測方法。基于文本的方法較少反映程序的語法語義信息，檢測精確度較低。

基于Token的檢測是將源碼轉換為Token序列的形式。在克隆檢測領域比較典型的是文獻[7]的CCFinder。在抄襲檢測領域，JPlag、YAP3都是這種類型的抄襲檢測系統。它們首先將源代碼轉換成Token序列，然后使用RKR-GST算法來計算代碼相似度。基于Token的方法忽略了程序的語法語義信息，僅對詞法級別的代碼抄襲檢測效果良好。

基于程序依賴圖的檢測方法通過分析源代碼的語法結構、函數的調用關系等，構建程序的依賴關系圖，通過子圖同構來判斷代碼的相似度。如GPLAG系統使用子圖相似方法來計算源碼的相似度。基于PDG的方法雖然準確，但由于計算量大，無法應用于大規模場景。

基于抽象語法樹的抄襲檢測方法將源碼轉換為抽象語法樹，通過尋找相似子樹計算相似。如文獻[16]直接在抽象語法樹上尋找相似子樹來計算語法樹的相似度。在克隆檢測領域，文獻[17]開發了工具DECKARD，通過聚類將相似子樹來檢測克隆代碼。基于AST的方法建立樹結構的代價較高，較難應用在大型軟件的檢測場景。

本文提出的基于抽象語法樹和索引信息的代碼檢測方法，通過抽象語法樹生成的代碼塊結構信息和基于代碼塊的哈希索引，較完備地保存了源碼信息，不影響檢測效果，而且這種形式較源碼而言占用內存空間少，傳輸速度更快，檢索速度也更快。該方法能夠基于整個互聯網的項目進行檢測，并且能夠基于統計信息自動降低誤報率，檢測結果更加準確。

2 方法概述

本文方法包括本地客戶端和服務器端兩部分。服務器端負責構建互聯網級別的開源代碼庫信息，接收來自客戶端的檢測請求和代碼特征信息，進行代碼侵權檢測計算；本地客戶端則負責提取待檢測代碼的特征信息，包括代碼塊結構信息和哈希索引信息，上報信息到服務器端，并對服務器端下發的重復信息進行本地化解讀。方法結構如圖1所示。

2.1 代碼特征提取

代碼特征提取是服務器端和本地客戶端的公用模塊，負責提取代碼結構和哈希索引特征，包含兩個子單元：代碼結構解析和索引信息生成。

（1）代碼結構解析。通過抽象語法樹將程序源代碼解析為代碼塊結構，然后將代碼塊作為后續分析檢測的基本單元。定義解析后的源碼結構為一個五元組（fileID，segmentID，parentSegmentID，segmentInfo，hashIndex）。其中fileId和segmentID分別為數字形式文件和代碼塊唯一標識。通過fileID和segmentID可以唯一識別一個代碼塊，同時又隱藏了代碼的細節信息。parentSegmentID為代碼塊父節點的ID，用于找出segmentID的父節點，segmentInfo為代碼塊中的其它信息，包括startLine、endLine、textLength、sequence、startCol等，startLine為代碼塊在文件中的起始行，endLine為代碼塊在文件中的終止行，textLength為代碼塊的文本長度信息，startCol為代碼塊的起始列，sequence為同一文件中不同代碼塊出現的次序等。圖2是抽象語法樹的代碼塊結構示例。如代碼塊N4（122，3，2…）中，122為代碼塊的fileID，3為代碼塊的segmentID，2為代碼塊的parentSegmentID。

（2）代碼索引生成。在代碼結構解析的基礎上，對每個代碼塊生成索引，通過索引來唯一表示一個代碼塊的特征。代碼索引生成包括歸一化和哈希值計算兩個步驟。歸一化是代碼重復檢測的常用策略，通過移除空格、用一致的符號替換變量名和數字等，消除由于代碼格式、變量名等因素不同對檢測效果的影響。在歸一化的代碼上使用MD5哈希算法，為每個結點生成一個128位的哈希值[18]。最后，將獲得的哈希索引寫入代碼塊信息的hashIndex。

2.2 本地映射表構建

本地映射表維護上傳到服務器端的代碼塊和本地可閱讀代碼的對應關系。當服務器端傳回以索引信息表達的重復信息時，可在本地解析為可讀的代碼形式。圖3展示了本地映射表的結構。其中，每一行代表一個代碼塊，使用該代碼塊的fileID和segmentID為索引。parentSegmentID和segmentInfo反映了和原代碼的對應信息，hashIndex則代表了該代碼塊的哈希索引特征信息（見表1）。

2.3 構建全局特征信息表

為了能和待檢測的代碼進行特征匹配，服務器端也需要維護全局特征信息表。服務端將項目源代碼轉化為一張全局索引表。全局特征信息表除了維護所有代碼塊的結構特征和索引特征外，還需要維護項目信息、項目許可證信息。

2.4 上傳代碼塊信息

將代碼塊信息上傳至服務器，用于代碼重復檢測。上傳前將代碼塊信息中的原始信息去除，如segmentInfo中的起始列、終止列、代碼塊出現順序等信息。保留起始行、終止行、代碼塊長度信息、版本信息，然后將代碼塊信息上傳至服務器。服務器端接收本地代理傳來的代碼塊信息，并使用侵權檢測引擎進行檢測。

2.5 侵權檢測引擎

服務器端基于本地代理上傳的代碼塊結構信息判斷代碼塊的重復性以及是否侵權。如果發現侵權，就將侵權的重復信息發送給本地代理，由本地代理進行解析。

為此，將上傳的代碼塊信息對照全局索引表，并按照重復檢測規則進行檢測，下面給出幾個參考規則。

規則一：簡單索引重復

簡單索引重復即將索引表中的索引同全局索引表中的索引進行匹配，若索引值相同并且代碼行數大于5行則視為一個重復。

其中，S為服務器端接收到的索引表，表中含有起始行startLine，中止行endLine，索引值hash，由規則三檢測到的索引值將存入索引表S2中。

根據重復檢測規則找到重復片段后，對重復片段所在文件的許可證信息進行檢測，若重復代碼所在項目的許可證信息允許用戶進行修改再發布，則視為不侵權，反之則視為侵權。比如GPL許可證信息中不允許其衍生代碼進行非開源的商業用途，若直接復用其項目代碼則引起侵權。

2.6 下發侵權檢測報告

服務器將檢測到的代碼塊重復序列傳回本地代理。本地代理對接收到的侵權檢測報告進行解析，按照代碼塊ID還原成本地代碼進行展示。

3 系統實現

侵權檢測系統本地端主要負責提取軟件代碼的索引特征，上報到服務器以及對服務器下發的重復信息進行本地化解讀。服務器端主要負責重復檢測，如圖3所示。

項目解析器同時作用于本地和服務器端，本地為項目代理，服務器端為項目解析器，主要功能都是將源碼經過語法樹、索引生成一張索引表。本文使用Eclipse的JDT內建的代碼解析器生成抽象語法樹，采用MD5哈希算法來生成索引。本地項目代理在接收到服務器端傳來的重復時，將其轉換為可閱讀的代碼形式。

爬蟲主要收集網上的項目資源，這里以GitHub項目托管平臺上的JAVA項目為抓取目標。GitHub作為目前規模最大的開源軟件托管平臺，提供了較友好的API，可以方便獲取項目源碼。

項目數據庫主要在服務器端存儲抓取的代碼。由于開源項目眾多，即使轉換成索引形式仍然占用很大空間，內存不足以存儲，此時對項目進行持久化，將其存儲在數據庫中。

重復匹配模塊主要對本地項目代理傳輸的代碼塊索引信息與服務器端的全局索引表進行重復匹配，利用重復匹配方法確定是否重復。

4 實驗及結果

為了驗證文中提出的軟件侵權檢測方案，選取一個健康方面的商業軟件（本文中代號為INCH）作為實驗對象，在其中注入抄襲信息。選擇GitHub的50個開源JAVA項目進行侵權檢測。50個開源項目的版本信息分為MIT許可證、Apache許可證、GPL許可證3種。本文實驗環境為：操作系統Win10 64位，CPU Intel Core i5-7300HQ，內存8G。

本實驗分別對不同重復規則下的侵權方法進行驗證。由于INCH項目為企業開發人員獨立完成的程序，INCH中并不含有侵權代碼，為了對侵權算法進行驗證，將一段侵權代碼人為注入INCH項目進行檢測。

實驗步驟：

（1）選取許可證為GPL的項目CoreNLP，將CoreNLP項目文件中的一段源碼復制到INCH項目文件中，作為侵權代碼來源。

（2）構建開源項目代碼庫。啟動服務器，并抓取前述的開源項目代碼庫信息緩存到本地，然后對項目進行解析，解析后的代碼塊存入全局索引表。

（3）選取重復檢測規則，分別選用規則一、規則二、規則三，然后啟動檢測客戶端對項目進行檢驗。

實驗一：驗證簡單侵權規則的檢測能力（規則一）

選取50個開源項目中含有GPL許可證的CoreNLP項目，將ArgUtils.Java中的getWeightedTreebankDescription（）方法（get（）方法）復制到INCH的LoginDTO.java文件中。根據文獻[19]提出的代碼抄襲手段，分別對get（）方法進行代碼混淆操作，如原樣復制、修改注釋信息、標識符名稱替換、替換數據類型、添加無意義的代碼等。選取規則一進行侵權檢測，實驗結果見表2，運用規則一的侵權檢測方法僅需要6秒即可檢測出所有注入的侵權代碼。標識符名稱替換后的實驗檢測報告如圖4所示。

實驗二：驗證基于統計特征的重復項檢測能力（規則二）

選取CoreNLP項目，將ArgUtils.Java中的get（）方法分別進行try..catch語句塊移除，調整if語句出現順序，分別命名為get（）1方法、get（）2方法，然后將get（）1、get（）2復制到INCH項目中。選取規則二進行檢測，實驗結果如表3。其中try..catch語句塊移除后的實驗檢測報告見圖5。

實驗三：驗證基于統計特征的非侵權特征（規則三）

上述實驗中有些代碼塊如try..catch語句塊在項目中經常使用，一般不應識別為侵權。在此選取junit4項目TimeoutTest.java文件中的try {Thread.sleep（200）；} catch （InterruptedException e） {}代碼塊復制到其余49個項目中，利用規則三進行檢測。由于項目庫僅有50個項目，因此把規則三中重復項特征統計的臨界值改為30。實驗結果表明運用規則三的檢測方法僅需6.2秒即可完成任務，未發現侵權代碼。

實驗四：同JPlag系統對比

選取INCH項目為待檢測項目，CoreNLP項目為對比項目。分別選取規則一中的標識符替換，原樣復制規則二中的移除語句塊的3種抄襲手段，對ArgUtils.Java中的get（）方法進行變換。利用本文提出的檢測方法同JPlag檢測系統進行對比。由于JPlag系統的檢測結果為代碼相似度數值，所以用時間的度量進行對比，實驗結果如表4所示。

根據實驗一數據可以看出，利用原樣復制、修改注釋信息、標識符名稱替換、替換數據類型、添加無意義的代碼這些方式進行代碼抄襲，本文檢測方法均能正確檢測，并且檢測時間在6s左右。實驗二在移除get（）方法中的try..catch語句或調整if語句順序后，檢測到的重復符合規則二提出的區域分布。實驗三未找出侵權片段，是由于按照規則三，同一段代碼出現在較多的項目中則認為是正常復用，在這50個項目中可以很好地消除誤報。實驗四中JPlag系統的檢測時間為6.8s，本文方法為5.2s，在時間上優于JPlag系統。由實驗一實驗二的檢測報告可以看出，返回的侵權代碼以代碼塊形式顯示，用戶可以根據本地映射表找到侵權代碼，保護了用戶隱私。

5 結語

本文提出了一種基于本地代理和索引信息的代碼侵權檢測方案，實現了高效的侵權檢測，具備良好的可定制性。該方法可較好地保護企業源碼安全，檢測時間較快，達到了預期效果。但該侵權檢測系統目前僅實現了對JAVA語言代碼的侵權檢測，后續仍需要對其它編程語言如C/C++、Python語言等進行完善。此外，本實驗測試數據集規模較小，下一步將擴大規模，進一步驗證侵權檢測系統的有效性。

參考文獻：

[1] JAMES NICCOLAI.Oracle seeks $9.3 billion for Google′s use of Java in Android[EB/OL].[2016-05-28].http：//www.infoworld.com/article/3048726/android/oracle-seeks-93-billion-for-googles-use-of-java-in-android.html？utm_source=tuicool&utm_medium=referral.

[2] FREE SOFTWARE FOUNDATION.Various licenses and comments about them，2017[EB/OL].https：//www.gnu.org/licenses/license-list.html.

[3] 田振洲，劉烴，鄭慶華，等.軟件抄襲檢測研究綜述[J].信息安全學報，2016，1（3）：158-161.

[4] PRECHELT L，MALPOHL G.Finding plagiarisms among a set of programs with JPlag[EB/OL].https：//www.researchgate.net/publication/2832828_Finding_Plagiarisms_among_a_Set_of_Programs_with_JPlag.

[5] WISE M J.YAP3：improved detection of similarities in computer program and other texts[J].Acm Sigcse Bulletin，1996，28（1）：130-134.

[6] LIVIERI S，HIGO Y，MATUSHITA M，et al.Very-large scale code clone analysis and visualization of open source programs using distributed CCFinder： D-CCFinder[C].International Conference on Software Engineering.IEEE，2007：106-115.

[7] LIU C，CHEN C，HAN J，et al.GPLAG： detection of software plagiarism by program dependence graph analysis[C].ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM，2006：872--881.

[8] 史慶慶，孟繁軍，張麗萍，等.克隆代碼技術研究綜述[J].計算機應用研究，2013，30（6）：1617-1623.

[9] HUMMEL B，JUERGENS E，HEINEMANN L，et al.Index-based code clone detection： incremental，distributed，scalable[C].IEEE International Conference on Software Maintenance.IEEE Computer Society，2010：1-9.

[10] HALSTEAD M H.Elements of software science[M].Elsevierence，1977.

[11] OTTENSTEIN K J.An algorithmic approach to the detection and prevention of plagiarism[J].Acm Sigcse Bulletin，1976，8（4）：30-41.

[12] GRIER S.A tool that detects plagiarism in pascal programs[J].ACM SIGCSE Bulletin，1981，13（1）：15-20.

[13] VERCO K L，WISE M J.Software for detecting suspected plagiarism： comparing structure and attribute-counting systems[C].Australasian Conference on Computer Science Education.ACM，1996：81-88.

[14] BAKER B S.A program for identifying duplicated code[M].Computing Science & Statistics，1992.

[15] KIM Y C，CHO Y Y，MOON J B.A plagiarism detection system using a syntax-tree.[C].International Conference on Computational Intelligence，ICCI 2004.

[16] JIANG L，MISHERGHI G，SU Z，et al.DECKARD：scalable and accurate tree-based detection of code clones[C].International Conference on Software Engineering.IEEE，2007：96-105.

[17] RIVEST R.The MD5 message-digest algorithm[M].RFC Editor，1992.

[18] JONES E L.Metrics based plagiarism monitoring[C].Ccsc Northeastern Conference，2001：1-8.

（責任編輯：杜能鋼）

英文摘要Abstract：With the growing of open source software，enterprise developers tends to reuse existing open source code to improve development efficiency.But the complexity and variety of open source licenses may bring serious legal risks to enterprises.As a result，the immediate infringement detection is important to help enterprises to avoid such risks.However，general enterprises are unable to maintain the Internet-level open source code library，and needs to provide their own source code when using the third-party detection system which may cause the disclosure of enterprises technological secrets.In order to solve those problems，our paper proposes a local proxy code infringement detection approach.It only require enterprises providing the code structure and index information，without necessary of all of its source code.Our approach can protect enterprise source privacy and achieve efficient infringement detection.

英文關鍵詞Key Words：Infringement Detection；Hash；Index；Code Plagiarism；Clone Detection；Local Proxy