基于本地代理和索引信息的代码侵权检测方法

寨亮+张刚+赵逢禹

摘要：开源软件越来越丰富，企业开发人员可以方便地通过复用开源代码提高开发效率。但是开源代码的许可证非常复杂，未加管理的代码复用可能给企业带来严重的法律风险。通过侵权检测发现潜在侵权风险是企业自我保护的重要手段，然而一般企业都没有能力维护互联网级别的开源代码库，而使用第三方检测系统需要提供企业自己的源码，可能造成企业技术秘密泄露。为解决上述问题，提出了一种基于本地代理的代码侵权检测方案，该方案仅需要对外提交代码的结构和索引信息即可，无需提供完整的源码，既保护了企业源码隐私，又避免了企业维护大量开源代码库的额外负担，实现了高效的侵权检测。

关键词：侵权检测；哈希值；索引；代码抄袭；克隆检测；本地代理

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